LLVM 19.0.0git
StackLifetime.h
Go to the documentation of this file.
1//===- StackLifetime.h - Alloca Lifetime Analysis --------------*- C++ -*--===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_ANALYSIS_STACKLIFETIME_H
10#define LLVM_ANALYSIS_STACKLIFETIME_H
11
12#include "llvm/ADT/ArrayRef.h"
13#include "llvm/ADT/BitVector.h"
14#include "llvm/ADT/DenseMap.h"
17#include "llvm/IR/PassManager.h"
19#include <utility>
20
21namespace llvm {
22
23class AllocaInst;
24class BasicBlock;
25class Function;
26class Instruction;
27class IntrinsicInst;
28
29/// Compute live ranges of allocas.
30/// Live ranges are represented as sets of "interesting" instructions, which are
31/// defined as instructions that may start or end an alloca's lifetime. These
32/// are:
33/// * lifetime.start and lifetime.end intrinsics
34/// * first instruction of any basic block
35/// Interesting instructions are numbered in the depth-first walk of the CFG,
36/// and in the program order inside each basic block.
38 /// A class representing liveness information for a single basic block.
39 /// Each bit in the BitVector represents the liveness property
40 /// for a different stack slot.
41 struct BlockLifetimeInfo {
42 explicit BlockLifetimeInfo(unsigned Size)
43 : Begin(Size), End(Size), LiveIn(Size), LiveOut(Size) {}
44
45 /// Which slots BEGINs in each basic block.
46 BitVector Begin;
47
48 /// Which slots ENDs in each basic block.
50
51 /// Which slots are marked as LIVE_IN, coming into each basic block.
52 BitVector LiveIn;
53
54 /// Which slots are marked as LIVE_OUT, coming out of each basic block.
55 BitVector LiveOut;
56 };
57
58public:
60
61 /// This class represents a set of interesting instructions where an alloca is
62 /// live.
63 class LiveRange {
64 BitVector Bits;
67
68 public:
69 LiveRange(unsigned Size, bool Set = false) : Bits(Size, Set) {}
70 void addRange(unsigned Start, unsigned End) { Bits.set(Start, End); }
71
72 bool overlaps(const LiveRange &Other) const {
73 return Bits.anyCommon(Other.Bits);
74 }
75
76 void join(const LiveRange &Other) { Bits |= Other.Bits; }
77
78 bool test(unsigned Idx) const { return Bits.test(Idx); }
79 };
80
81 // Controls what is "alive" if control flow may reach the instruction
82 // with a different liveness of the alloca.
83 enum class LivenessType {
84 May, // May be alive on some path.
85 Must, // Must be alive on every path.
86 };
87
88private:
89 const Function &F;
91
92 /// Maps active slots (per bit) for each basic block.
94 LivenessMap BlockLiveness;
95
96 /// Interesting instructions. Instructions of the same block are adjustent
97 /// preserve in-block order.
99
100 /// A range [Start, End) of instruction ids for each basic block.
101 /// Instructions inside each BB have monotonic and consecutive ids.
103
105 unsigned NumAllocas;
107
108 /// LiveRange for allocas.
109 SmallVector<LiveRange, 8> LiveRanges;
110
111 /// The set of allocas that have at least one lifetime.start. All other
112 /// allocas get LiveRange that corresponds to the entire function.
113 BitVector InterestingAllocas;
114
115 struct Marker {
116 unsigned AllocaNo;
117 bool IsStart;
118 };
119
120 /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
121 DenseMap<const BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>>
122 BBMarkers;
123
124 bool HasUnknownLifetimeStartOrEnd = false;
125
126 void dumpAllocas() const;
127 void dumpBlockLiveness() const;
128 void dumpLiveRanges() const;
129
130 void collectMarkers();
131 void calculateLocalLiveness();
132 void calculateLiveIntervals();
133
134public:
135 StackLifetime(const Function &F, ArrayRef<const AllocaInst *> Allocas,
136 LivenessType Type);
137
138 void run();
139
140 iterator_range<
141 filter_iterator<ArrayRef<const IntrinsicInst *>::const_iterator,
142 std::function<bool(const IntrinsicInst *)>>>
143 getMarkers() const {
144 std::function<bool(const IntrinsicInst *)> NotNull(
145 [](const IntrinsicInst *I) -> bool { return I; });
146 return make_filter_range(Instructions, NotNull);
147 }
148
149 /// Returns a set of "interesting" instructions where the given alloca is
150 /// live. Not all instructions in a function are interesting: we pick a set
151 /// that is large enough for LiveRange::Overlaps to be correct.
152 const LiveRange &getLiveRange(const AllocaInst *AI) const;
153
154 /// Returns true if instruction is reachable from entry.
155 bool isReachable(const Instruction *I) const;
156
157 /// Returns true if the alloca is alive after the instruction.
158 bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const;
159
160 /// Returns a live range that represents an alloca that is live throughout the
161 /// entire function.
163 return LiveRange(Instructions.size(), true);
164 }
165
166 void print(raw_ostream &O);
167};
168
169static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
170 OS << "{";
171 ListSeparator LS;
172 for (int Idx = V.find_first(); Idx >= 0; Idx = V.find_next(Idx))
173 OS << LS << Idx;
174 OS << "}";
175 return OS;
176}
177
179 const StackLifetime::LiveRange &R) {
180 return OS << R.Bits;
181}
182
183/// Printer pass for testing.
185 : public PassInfoMixin<StackLifetimePrinterPass> {
187 raw_ostream &OS;
188
189public:
191 : Type(Type), OS(OS) {}
193 static bool isRequired() { return true; }
194 void printPipeline(raw_ostream &OS,
195 function_ref<StringRef(StringRef)> MapClassName2PassName);
196};
197
198} // end namespace llvm
199
200#endif // LLVM_ANALYSIS_STACKLIFETIME_H
This file implements the BitVector class.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
uint64_t Size
bool End
Definition: ELF_riscv.cpp:480
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
raw_pwrite_stream & OS
This file defines the SmallVector class.
This file contains some functions that are useful when dealing with strings.
an instruction to allocate memory on the stack
Definition: Instructions.h:59
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Printer pass for testing.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
StackLifetimePrinterPass(raw_ostream &OS, StackLifetime::LivenessType Type)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This class represents a set of interesting instructions where an alloca is live.
Definition: StackLifetime.h:63
bool overlaps(const LiveRange &Other) const
Definition: StackLifetime.h:72
void addRange(unsigned Start, unsigned End)
Definition: StackLifetime.h:70
void join(const LiveRange &Other)
Definition: StackLifetime.h:76
bool test(unsigned Idx) const
Definition: StackLifetime.h:78
friend raw_ostream & operator<<(raw_ostream &OS, const StackLifetime::LiveRange &R)
LiveRange(unsigned Size, bool Set=false)
Definition: StackLifetime.h:69
Compute live ranges of allocas.
Definition: StackLifetime.h:37
void print(raw_ostream &O)
iterator_range< filter_iterator< ArrayRef< const IntrinsicInst * >::const_iterator, std::function< bool(const IntrinsicInst *)> > > getMarkers() const
bool isReachable(const Instruction *I) const
Returns true if instruction is reachable from entry.
LiveRange getFullLiveRange() const
Returns a live range that represents an alloca that is live throughout the entire function.
const LiveRange & getLiveRange(const AllocaInst *AI) const
Returns a set of "interesting" instructions where the given alloca is live.
bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const
Returns true if the alloca is alive after the instruction.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:581
@ Other
Any other memory.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:91