LLVM  15.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"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/StringExtras.h"
17 #include "llvm/IR/PassManager.h"
19 #include <utility>
20 
21 namespace llvm {
22 
23 class AllocaInst;
24 class BasicBlock;
25 class Function;
26 class Instruction;
27 class 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.
49  BitVector End;
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 
58 public:
60 
61  /// This class represents a set of interesting instructions where an alloca is
62  /// live.
63  class LiveRange {
64  BitVector Bits;
66  const StackLifetime::LiveRange &R);
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 
88 private:
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 
134 public:
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 
169 static 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 
189 public:
191  : Type(Type), OS(OS) {}
193  void printPipeline(raw_ostream &OS,
194  function_ref<StringRef(StringRef)> MapClassName2PassName);
195 };
196 
197 } // end namespace llvm
198 
199 #endif // LLVM_ANALYSIS_STACKLIFETIME_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::StackLifetime::isAliveAfter
bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const
Returns true if the alloca is alive after the instruction.
Definition: StackLifetime.cpp:45
llvm::StackLifetime::getMarkers
iterator_range< filter_iterator< ArrayRef< const IntrinsicInst * >::const_iterator, std::function< bool(const IntrinsicInst *)> > > getMarkers() const
Definition: StackLifetime.h:143
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::StackLifetime::StackLifetime
StackLifetime(const Function &F, ArrayRef< const AllocaInst * > Allocas, LivenessType Type)
Definition: StackLifetime.cpp:302
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::StackLifetimePrinterPass
Printer pass for testing.
Definition: StackLifetime.h:184
Instructions
Code Generation Notes for reduce the size of the ISel and reduce repetition in the implementation In a small number of this can cause even when no optimisation has taken place Instructions
Definition: MSA.txt:11
llvm::StackLifetime::LivenessType::Must
@ Must
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::StackLifetime::LiveRange::addRange
void addRange(unsigned Start, unsigned End)
Definition: StackLifetime.h:70
llvm::StackLifetime::print
void print(raw_ostream &O)
Definition: StackLifetime.cpp:380
llvm::StackLifetime::isReachable
bool isReachable(const Instruction *I) const
Returns true if instruction is reachable from entry.
Definition: StackLifetime.cpp:41
llvm::Instruction
Definition: Instruction.h:42
llvm::StackLifetime::LiveRange::operator<<
friend raw_ostream & operator<<(raw_ostream &OS, const StackLifetime::LiveRange &R)
Definition: StackLifetime.h:178
llvm::StackLifetimePrinterPass::StackLifetimePrinterPass
StackLifetimePrinterPass(raw_ostream &OS, StackLifetime::LivenessType Type)
Definition: StackLifetime.h:190
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
BitVector.h
llvm::BitVector
Definition: BitVector.h:75
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::StackLifetime::LivenessType::May
@ May
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::StackLifetime::getLiveRange
const LiveRange & getLiveRange(const AllocaInst *AI) const
Returns a set of "interesting" instructions where the given alloca is live.
Definition: StackLifetime.cpp:35
llvm::DenseMap< const BasicBlock *, BlockLifetimeInfo >
I
#define I(x, y, z)
Definition: MD5.cpp:58
StringExtras.h
llvm::StackLifetime
Compute live ranges of allocas.
Definition: StackLifetime.h:37
ArrayRef.h
llvm::StackLifetime::LiveRange::join
void join(const LiveRange &Other)
Definition: StackLifetime.h:76
llvm::StackLifetime::LivenessType
LivenessType
Definition: StackLifetime.h:83
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
LiveRange
SI Optimize VGPR LiveRange
Definition: SIOptimizeVGPRLiveRange.cpp:616
llvm::StackLifetimePrinterPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: StackLifetime.cpp:397
llvm::StackLifetimePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: StackLifetime.cpp:385
llvm::StackLifetime::run
void run()
Definition: StackLifetime.cpp:314
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::StackLifetime::LiveRange
This class represents a set of interesting instructions where an alloca is live.
Definition: StackLifetime.h:63
llvm::StackLifetime::getFullLiveRange
LiveRange getFullLiveRange() const
Returns a live range that represents an alloca that is live throughout the entire function.
Definition: StackLifetime.h:162
llvm::StackLifetime::LiveRange::overlaps
bool overlaps(const LiveRange &Other) const
Definition: StackLifetime.h:72
llvm::make_filter_range
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:534
llvm::StackLifetime::LifetimeAnnotationWriter
Definition: StackLifetime.cpp:340
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:264
PassManager.h
llvm::BitVector::find_next
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:301
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
SmallVector.h
llvm::StackLifetime::LiveRange::LiveRange
LiveRange(unsigned Size, bool Set=false)
Definition: StackLifetime.h:69
llvm::BitVector::find_first
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:293
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::StackLifetime::LiveRange::test
bool test(unsigned Idx) const
Definition: StackLifetime.h:78
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
raw_ostream.h
llvm::codeview::PublicSymFlags::Function
@ Function
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236