/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SafeStackColoring.h
Line | Count | Source (jump to first uncovered line) |
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/Instructions.h" |
17 | | #include "llvm/Support/raw_ostream.h" |
18 | | #include <cassert> |
19 | | #include <utility> |
20 | | |
21 | | namespace llvm { |
22 | | |
23 | | class BasicBlock; |
24 | | class Function; |
25 | | class Instruction; |
26 | | |
27 | | namespace safestack { |
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. |
37 | | class StackColoring { |
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 | | /// Which slots BEGINs in each basic block. |
43 | | BitVector Begin; |
44 | | |
45 | | /// Which slots ENDs in each basic block. |
46 | | BitVector End; |
47 | | |
48 | | /// Which slots are marked as LIVE_IN, coming into each basic block. |
49 | | BitVector LiveIn; |
50 | | |
51 | | /// Which slots are marked as LIVE_OUT, coming out of each basic block. |
52 | | BitVector LiveOut; |
53 | | }; |
54 | | |
55 | | public: |
56 | | /// This class represents a set of interesting instructions where an alloca is |
57 | | /// live. |
58 | | struct LiveRange { |
59 | | BitVector bv; |
60 | | |
61 | 257 | void SetMaximum(int size) { bv.resize(size); } |
62 | 314 | void AddRange(unsigned start, unsigned end) { bv.set(start, end); } |
63 | | |
64 | 251 | bool Overlaps(const LiveRange &Other) const { |
65 | 251 | return bv.anyCommon(Other.bv); |
66 | 251 | } |
67 | | |
68 | 254 | void Join(const LiveRange &Other) { bv |= Other.bv; } |
69 | | }; |
70 | | |
71 | | private: |
72 | | Function &F; |
73 | | |
74 | | /// Maps active slots (per bit) for each basic block. |
75 | | using LivenessMap = DenseMap<BasicBlock *, BlockLifetimeInfo>; |
76 | | LivenessMap BlockLiveness; |
77 | | |
78 | | /// Number of interesting instructions. |
79 | | int NumInst = -1; |
80 | | |
81 | | /// Numeric ids for interesting instructions. |
82 | | DenseMap<Instruction *, unsigned> InstructionNumbering; |
83 | | |
84 | | /// A range [Start, End) of instruction ids for each basic block. |
85 | | /// Instructions inside each BB have monotonic and consecutive ids. |
86 | | DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange; |
87 | | |
88 | | ArrayRef<AllocaInst *> Allocas; |
89 | | unsigned NumAllocas; |
90 | | DenseMap<AllocaInst *, unsigned> AllocaNumbering; |
91 | | |
92 | | /// LiveRange for allocas. |
93 | | SmallVector<LiveRange, 8> LiveRanges; |
94 | | |
95 | | /// The set of allocas that have at least one lifetime.start. All other |
96 | | /// allocas get LiveRange that corresponds to the entire function. |
97 | | BitVector InterestingAllocas; |
98 | | SmallVector<Instruction *, 8> Markers; |
99 | | |
100 | | struct Marker { |
101 | | unsigned AllocaNo; |
102 | | bool IsStart; |
103 | | }; |
104 | | |
105 | | /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo. |
106 | | DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers; |
107 | | |
108 | | void dumpAllocas(); |
109 | | void dumpBlockLiveness(); |
110 | | void dumpLiveRanges(); |
111 | | |
112 | | bool readMarker(Instruction *I, bool *IsStart); |
113 | | void collectMarkers(); |
114 | | void calculateLocalLiveness(); |
115 | | void calculateLiveIntervals(); |
116 | | |
117 | | public: |
118 | | StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas) |
119 | 152 | : F(F), Allocas(Allocas), NumAllocas(Allocas.size()) {} |
120 | | |
121 | | void run(); |
122 | | void removeAllMarkers(); |
123 | | |
124 | | /// Returns a set of "interesting" instructions where the given alloca is |
125 | | /// live. Not all instructions in a function are interesting: we pick a set |
126 | | /// that is large enough for LiveRange::Overlaps to be correct. |
127 | | const LiveRange &getLiveRange(AllocaInst *AI); |
128 | | |
129 | | /// Returns a live range that represents an alloca that is live throughout the |
130 | | /// entire function. |
131 | 25 | LiveRange getFullLiveRange() { |
132 | 25 | assert(NumInst >= 0); |
133 | 25 | LiveRange R; |
134 | 25 | R.SetMaximum(NumInst); |
135 | 25 | R.AddRange(0, NumInst); |
136 | 25 | return R; |
137 | 25 | } |
138 | | }; |
139 | | |
140 | 0 | static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) { |
141 | 0 | OS << "{"; |
142 | 0 | int idx = V.find_first(); |
143 | 0 | bool first = true; |
144 | 0 | while (idx >= 0) { |
145 | 0 | if (!first) { |
146 | 0 | OS << ", "; |
147 | 0 | } |
148 | 0 | first = false; |
149 | 0 | OS << idx; |
150 | 0 | idx = V.find_next(idx); |
151 | 0 | } |
152 | 0 | OS << "}"; |
153 | 0 | return OS; |
154 | 0 | } Unexecuted instantiation: SafeStack.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::BitVector const&) Unexecuted instantiation: SafeStackColoring.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::BitVector const&) Unexecuted instantiation: SafeStackLayout.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::BitVector const&) |
155 | | |
156 | | static inline raw_ostream &operator<<(raw_ostream &OS, |
157 | 0 | const StackColoring::LiveRange &R) { |
158 | 0 | return OS << R.bv; |
159 | 0 | } Unexecuted instantiation: SafeStack.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::safestack::StackColoring::LiveRange const&) Unexecuted instantiation: SafeStackColoring.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::safestack::StackColoring::LiveRange const&) Unexecuted instantiation: SafeStackLayout.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::safestack::StackColoring::LiveRange const&) |
160 | | |
161 | | } // end namespace safestack |
162 | | |
163 | | } // end namespace llvm |
164 | | |
165 | | #endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H |