LLVM  14.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/IntrinsicInst.h"
18 #include "llvm/IR/PassManager.h"
20 #include <cassert>
21 #include <utility>
22 
23 namespace llvm {
24 
25 class AllocaInst;
26 class BasicBlock;
27 class Function;
28 class Instruction;
29 
30 /// Compute live ranges of allocas.
31 /// Live ranges are represented as sets of "interesting" instructions, which are
32 /// defined as instructions that may start or end an alloca's lifetime. These
33 /// are:
34 /// * lifetime.start and lifetime.end intrinsics
35 /// * first instruction of any basic block
36 /// Interesting instructions are numbered in the depth-first walk of the CFG,
37 /// and in the program order inside each basic block.
39  /// A class representing liveness information for a single basic block.
40  /// Each bit in the BitVector represents the liveness property
41  /// for a different stack slot.
42  struct BlockLifetimeInfo {
43  explicit BlockLifetimeInfo(unsigned Size)
44  : Begin(Size), End(Size), LiveIn(Size), LiveOut(Size) {}
45 
46  /// Which slots BEGINs in each basic block.
47  BitVector Begin;
48 
49  /// Which slots ENDs in each basic block.
50  BitVector End;
51 
52  /// Which slots are marked as LIVE_IN, coming into each basic block.
53  BitVector LiveIn;
54 
55  /// Which slots are marked as LIVE_OUT, coming out of each basic block.
56  BitVector LiveOut;
57  };
58 
59 public:
61 
62  /// This class represents a set of interesting instructions where an alloca is
63  /// live.
64  class LiveRange {
65  BitVector Bits;
67  const StackLifetime::LiveRange &R);
68 
69  public:
70  LiveRange(unsigned Size, bool Set = false) : Bits(Size, Set) {}
71  void addRange(unsigned Start, unsigned End) { Bits.set(Start, End); }
72 
73  bool overlaps(const LiveRange &Other) const {
74  return Bits.anyCommon(Other.Bits);
75  }
76 
77  void join(const LiveRange &Other) { Bits |= Other.Bits; }
78 
79  bool test(unsigned Idx) const { return Bits.test(Idx); }
80  };
81 
82  // Controls what is "alive" if control flow may reach the instruction
83  // with a different liveness of the alloca.
84  enum class LivenessType {
85  May, // May be alive on some path.
86  Must, // Must be alive on every path.
87  };
88 
89 private:
90  const Function &F;
92 
93  /// Maps active slots (per bit) for each basic block.
95  LivenessMap BlockLiveness;
96 
97  /// Interesting instructions. Instructions of the same block are adjustent
98  /// preserve in-block order.
100 
101  /// A range [Start, End) of instruction ids for each basic block.
102  /// Instructions inside each BB have monotonic and consecutive ids.
104 
106  unsigned NumAllocas;
108 
109  /// LiveRange for allocas.
110  SmallVector<LiveRange, 8> LiveRanges;
111 
112  /// The set of allocas that have at least one lifetime.start. All other
113  /// allocas get LiveRange that corresponds to the entire function.
114  BitVector InterestingAllocas;
115 
116  struct Marker {
117  unsigned AllocaNo;
118  bool IsStart;
119  };
120 
121  /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
122  DenseMap<const BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>>
123  BBMarkers;
124 
125  bool HasUnknownLifetimeStartOrEnd = false;
126 
127  void dumpAllocas() const;
128  void dumpBlockLiveness() const;
129  void dumpLiveRanges() const;
130 
131  void collectMarkers();
132  void calculateLocalLiveness();
133  void calculateLiveIntervals();
134 
135 public:
136  StackLifetime(const Function &F, ArrayRef<const AllocaInst *> Allocas,
137  LivenessType Type);
138 
139  void run();
140 
141  iterator_range<
142  filter_iterator<ArrayRef<const IntrinsicInst *>::const_iterator,
143  std::function<bool(const IntrinsicInst *)>>>
144  getMarkers() const {
145  std::function<bool(const IntrinsicInst *)> NotNull(
146  [](const IntrinsicInst *I) -> bool { return I; });
147  return make_filter_range(Instructions, NotNull);
148  }
149 
150  /// Returns a set of "interesting" instructions where the given alloca is
151  /// live. Not all instructions in a function are interesting: we pick a set
152  /// that is large enough for LiveRange::Overlaps to be correct.
153  const LiveRange &getLiveRange(const AllocaInst *AI) const;
154 
155  /// Returns true if instruction is reachable from entry.
156  bool isReachable(const Instruction *I) const;
157 
158  /// Returns true if the alloca is alive after the instruction.
159  bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const;
160 
161  /// Returns a live range that represents an alloca that is live throughout the
162  /// entire function.
164  return LiveRange(Instructions.size(), true);
165  }
166 
167  void print(raw_ostream &O);
168 };
169 
170 static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
171  OS << "{";
172  ListSeparator LS;
173  for (int Idx = V.find_first(); Idx >= 0; Idx = V.find_next(Idx))
174  OS << LS << Idx;
175  OS << "}";
176  return OS;
177 }
178 
180  const StackLifetime::LiveRange &R) {
181  return OS << R.Bits;
182 }
183 
184 /// Printer pass for testing.
186  : public PassInfoMixin<StackLifetimePrinterPass> {
188  raw_ostream &OS;
189 
190 public:
192  : Type(Type), OS(OS) {}
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
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
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:50
IntrinsicInst.h
llvm::StackLifetime::getMarkers
iterator_range< filter_iterator< ArrayRef< const IntrinsicInst * >::const_iterator, std::function< bool(const IntrinsicInst *)> > > getMarkers() const
Definition: StackLifetime.h:144
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:62
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::StackLifetime::StackLifetime
StackLifetime(const Function &F, ArrayRef< const AllocaInst * > Allocas, LivenessType Type)
Definition: StackLifetime.cpp:307
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:185
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:56
llvm::StackLifetime::LiveRange::addRange
void addRange(unsigned Start, unsigned End)
Definition: StackLifetime.h:71
llvm::StackLifetime::print
void print(raw_ostream &O)
Definition: StackLifetime.cpp:385
llvm::StackLifetime::isReachable
bool isReachable(const Instruction *I) const
Returns true if instruction is reachable from entry.
Definition: StackLifetime.cpp:46
llvm::Instruction
Definition: Instruction.h:45
llvm::StackLifetime::LiveRange::operator<<
friend raw_ostream & operator<<(raw_ostream &OS, const StackLifetime::LiveRange &R)
Definition: StackLifetime.h:179
llvm::StackLifetimePrinterPass::StackLifetimePrinterPass
StackLifetimePrinterPass(raw_ostream &OS, StackLifetime::LivenessType Type)
Definition: StackLifetime.h:191
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
BitVector.h
llvm::BitVector
Definition: BitVector.h:74
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::StackLifetime::LivenessType::May
@ May
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
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:40
llvm::DenseMap< const BasicBlock *, BlockLifetimeInfo >
I
#define I(x, y, z)
Definition: MD5.cpp:59
StringExtras.h
llvm::StackLifetime
Compute live ranges of allocas.
Definition: StackLifetime.h:38
ArrayRef.h
llvm::StackLifetime::LiveRange::join
void join(const LiveRange &Other)
Definition: StackLifetime.h:77
llvm::StackLifetime::LivenessType
LivenessType
Definition: StackLifetime.h:84
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
LiveRange
SI Optimize VGPR LiveRange
Definition: SIOptimizeVGPRLiveRange.cpp:570
llvm::StackLifetimePrinterPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: StackLifetime.cpp:402
llvm::StackLifetimePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: StackLifetime.cpp:390
llvm::StackLifetime::run
void run()
Definition: StackLifetime.cpp:319
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:64
llvm::StackLifetime::getFullLiveRange
LiveRange getFullLiveRange() const
Returns a live range that represents an alloca that is live throughout the entire function.
Definition: StackLifetime.h:163
llvm::StackLifetime::LiveRange::overlaps
bool overlaps(const LiveRange &Other) const
Definition: StackLifetime.h:73
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:490
llvm::StackLifetime::LifetimeAnnotationWriter
Definition: StackLifetime.cpp:345
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:300
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
SmallVector.h
llvm::StackLifetime::LiveRange::LiveRange
LiveRange(unsigned Size, bool Set=false)
Definition: StackLifetime.h:70
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:292
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::StackLifetime::LiveRange::test
bool test(unsigned Idx) const
Definition: StackLifetime.h:79
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
raw_ostream.h
llvm::codeview::PublicSymFlags::Function
@ Function
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1184