LLVM  11.0.0git
SafeStackColoring.h
Go to the documentation of this file.
1 //===- SafeStackColoring.h - SafeStack frame coloring ----------*- 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_LIB_CODEGEN_SAFESTACKCOLORING_H
10 #define LLVM_LIB_CODEGEN_SAFESTACKCOLORING_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/IR/IntrinsicInst.h"
18 #include <cassert>
19 #include <utility>
20 
21 namespace llvm {
22 
23 class AllocaInst;
24 class BasicBlock;
25 class Function;
26 class Instruction;
27 
28 namespace safestack {
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:
60  /// This class represents a set of interesting instructions where an alloca is
61  /// live.
62  class LiveRange {
65  const StackColoring::LiveRange &R);
66 
67  public:
68  LiveRange(unsigned Size, bool Set = false) : Bits(Size, Set) {}
69  void addRange(unsigned Start, unsigned End) { Bits.set(Start, End); }
70 
71  bool overlaps(const LiveRange &Other) const {
72  return Bits.anyCommon(Other.Bits);
73  }
74 
75  void join(const LiveRange &Other) { Bits |= Other.Bits; }
76  };
77 
78 private:
79  const Function &F;
80 
81  /// Maps active slots (per bit) for each basic block.
83  LivenessMap BlockLiveness;
84 
85  /// Number of interesting instructions.
86  int NumInst = -1;
87 
88  /// Numeric ids for interesting instructions.
89  DenseMap<const IntrinsicInst *, unsigned> InstructionNumbering;
90 
91  /// A range [Start, End) of instruction ids for each basic block.
92  /// Instructions inside each BB have monotonic and consecutive ids.
94 
96  unsigned NumAllocas;
98 
99  /// LiveRange for allocas.
100  SmallVector<LiveRange, 8> LiveRanges;
101 
102  /// The set of allocas that have at least one lifetime.start. All other
103  /// allocas get LiveRange that corresponds to the entire function.
104  BitVector InterestingAllocas;
105 
106  struct Marker {
107  unsigned AllocaNo;
108  bool IsStart;
109  };
110 
111  /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
113  BBMarkers;
114 
115  void dumpAllocas() const;
116  void dumpBlockLiveness() const;
117  void dumpLiveRanges() const;
118 
119  void collectMarkers();
120  void calculateLocalLiveness();
121  void calculateLiveIntervals();
122 
123 public:
125 
126  void run();
127  std::vector<const IntrinsicInst *> getMarkers() const;
128 
129  /// Returns a set of "interesting" instructions where the given alloca is
130  /// live. Not all instructions in a function are interesting: we pick a set
131  /// that is large enough for LiveRange::Overlaps to be correct.
132  const LiveRange &getLiveRange(const AllocaInst *AI) const;
133 
134  /// Returns a live range that represents an alloca that is live throughout the
135  /// entire function.
137  assert(NumInst >= 0);
138  return LiveRange(NumInst, true);
139  }
140 };
141 
142 static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
143  OS << "{";
144  int Idx = V.find_first();
145  bool First = true;
146  while (Idx >= 0) {
147  if (!First) {
148  OS << ", ";
149  }
150  First = false;
151  OS << Idx;
152  Idx = V.find_next(Idx);
153  }
154  OS << "}";
155  return OS;
156 }
157 
159  const StackColoring::LiveRange &R) {
160  return OS << R.Bits;
161 }
162 
163 } // end namespace safestack
164 
165 } // end namespace llvm
166 
167 #endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
This class represents a set of interesting instructions where an alloca is live.
BitVector & set()
Definition: BitVector.h:398
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:63
static raw_ostream & operator<<(raw_ostream &OS, const BitVector &V)
Compute live ranges of allocas.
std::vector< const IntrinsicInst * > getMarkers() const
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:332
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:340
#define F(x, y, z)
Definition: MD5.cpp:56
LiveRange getFullLiveRange() const
Returns a live range that represents an alloca that is live throughout the entire function...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
Definition: BitVector.h:524
StackColoring(const Function &F, ArrayRef< const AllocaInst *> Allocas)
bool overlaps(const LiveRange &Other) const
LiveRange(unsigned Size, bool Set=false)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
const LiveRange & getLiveRange(const AllocaInst *AI) const
Returns a set of "interesting" instructions where the given alloca is live.
void addRange(unsigned Start, unsigned End)
uint32_t Size
Definition: Profile.cpp:46
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
an instruction to allocate memory on the stack
Definition: Instructions.h:59