/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/SafeStackColoring.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- SafeStackColoring.h - SafeStack frame coloring ---------*- C++ -*--===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | |
10 | | #ifndef LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H |
11 | | #define LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H |
12 | | |
13 | | #include "llvm/ADT/BitVector.h" |
14 | | #include "llvm/ADT/DenseMap.h" |
15 | | #include "llvm/ADT/SmallVector.h" |
16 | | #include "llvm/IR/Function.h" |
17 | | #include "llvm/Support/raw_os_ostream.h" |
18 | | |
19 | | namespace llvm { |
20 | | class AllocaInst; |
21 | | |
22 | | namespace safestack { |
23 | | /// Compute live ranges of allocas. |
24 | | /// Live ranges are represented as sets of "interesting" instructions, which are |
25 | | /// defined as instructions that may start or end an alloca's lifetime. These |
26 | | /// are: |
27 | | /// * lifetime.start and lifetime.end intrinsics |
28 | | /// * first instruction of any basic block |
29 | | /// Interesting instructions are numbered in the depth-first walk of the CFG, |
30 | | /// and in the program order inside each basic block. |
31 | | class StackColoring { |
32 | | /// A class representing liveness information for a single basic block. |
33 | | /// Each bit in the BitVector represents the liveness property |
34 | | /// for a different stack slot. |
35 | | struct BlockLifetimeInfo { |
36 | | /// Which slots BEGINs in each basic block. |
37 | | BitVector Begin; |
38 | | /// Which slots ENDs in each basic block. |
39 | | BitVector End; |
40 | | /// Which slots are marked as LIVE_IN, coming into each basic block. |
41 | | BitVector LiveIn; |
42 | | /// Which slots are marked as LIVE_OUT, coming out of each basic block. |
43 | | BitVector LiveOut; |
44 | | }; |
45 | | |
46 | | public: |
47 | | /// This class represents a set of interesting instructions where an alloca is |
48 | | /// live. |
49 | | struct LiveRange { |
50 | | BitVector bv; |
51 | 251 | void SetMaximum(int size) { bv.resize(size); } |
52 | 309 | void AddRange(unsigned start, unsigned end) { bv.set(start, end); } |
53 | 253 | bool Overlaps(const LiveRange &Other) const { |
54 | 253 | return bv.anyCommon(Other.bv); |
55 | 253 | } |
56 | 249 | void Join(const LiveRange &Other) { bv |= Other.bv; } |
57 | | }; |
58 | | |
59 | | private: |
60 | | Function &F; |
61 | | |
62 | | /// Maps active slots (per bit) for each basic block. |
63 | | typedef DenseMap<BasicBlock *, BlockLifetimeInfo> LivenessMap; |
64 | | LivenessMap BlockLiveness; |
65 | | |
66 | | /// Number of interesting instructions. |
67 | | int NumInst; |
68 | | /// Numeric ids for interesting instructions. |
69 | | DenseMap<Instruction *, unsigned> InstructionNumbering; |
70 | | /// A range [Start, End) of instruction ids for each basic block. |
71 | | /// Instructions inside each BB have monotonic and consecutive ids. |
72 | | DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange; |
73 | | |
74 | | ArrayRef<AllocaInst *> Allocas; |
75 | | unsigned NumAllocas; |
76 | | DenseMap<AllocaInst *, unsigned> AllocaNumbering; |
77 | | /// LiveRange for allocas. |
78 | | SmallVector<LiveRange, 8> LiveRanges; |
79 | | |
80 | | /// The set of allocas that have at least one lifetime.start. All other |
81 | | /// allocas get LiveRange that corresponds to the entire function. |
82 | | BitVector InterestingAllocas; |
83 | | SmallVector<Instruction *, 8> Markers; |
84 | | |
85 | | struct Marker { |
86 | | unsigned AllocaNo; |
87 | | bool IsStart; |
88 | | }; |
89 | | |
90 | | /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo. |
91 | | DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers; |
92 | | |
93 | | void dumpAllocas(); |
94 | | void dumpBlockLiveness(); |
95 | | void dumpLiveRanges(); |
96 | | |
97 | | bool readMarker(Instruction *I, bool *IsStart); |
98 | | void collectMarkers(); |
99 | | void calculateLocalLiveness(); |
100 | | void calculateLiveIntervals(); |
101 | | |
102 | | public: |
103 | | StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas) |
104 | 145 | : F(F), NumInst(-1), Allocas(Allocas), NumAllocas(Allocas.size()) {} |
105 | | |
106 | | void run(); |
107 | | void removeAllMarkers(); |
108 | | |
109 | | /// Returns a set of "interesting" instructions where the given alloca is |
110 | | /// live. Not all instructions in a function are interesting: we pick a set |
111 | | /// that is large enough for LiveRange::Overlaps to be correct. |
112 | | const LiveRange &getLiveRange(AllocaInst *AI); |
113 | | |
114 | | /// Returns a live range that represents an alloca that is live throughout the |
115 | | /// entire function. |
116 | 25 | LiveRange getFullLiveRange() { |
117 | 25 | assert(NumInst >= 0); |
118 | 25 | LiveRange R; |
119 | 25 | R.SetMaximum(NumInst); |
120 | 25 | R.AddRange(0, NumInst); |
121 | 25 | return R; |
122 | 25 | } |
123 | | }; |
124 | | |
125 | 0 | static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) { |
126 | 0 | OS << "{"; |
127 | 0 | int idx = V.find_first(); |
128 | 0 | bool first = true; |
129 | 0 | while (idx >= 00 ) { |
130 | 0 | if (!first0 ) { |
131 | 0 | OS << ", "; |
132 | 0 | } |
133 | 0 | first = false; |
134 | 0 | OS << idx; |
135 | 0 | idx = V.find_next(idx); |
136 | 0 | } |
137 | 0 | OS << "}"; |
138 | 0 | return OS; |
139 | 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&) |
140 | | |
141 | | static inline raw_ostream &operator<<(raw_ostream &OS, |
142 | 0 | const StackColoring::LiveRange &R) { |
143 | 0 | return OS << R.bv; |
144 | 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&) |
145 | | |
146 | | } // namespace safestack |
147 | | } // namespace llvm |
148 | | |
149 | | #endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H |