/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Transforms/Scalar/SROA.h
Line | Count | Source |
1 | | //===- SROA.h - Scalar Replacement Of Aggregates ----------------*- 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 | | /// \file |
10 | | /// This file provides the interface for LLVM's Scalar Replacement of |
11 | | /// Aggregates pass. This pass provides both aggregate splitting and the |
12 | | /// primary SSA formation used in the compiler. |
13 | | /// |
14 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #ifndef LLVM_TRANSFORMS_SCALAR_SROA_H |
17 | | #define LLVM_TRANSFORMS_SCALAR_SROA_H |
18 | | |
19 | | #include "llvm/ADT/SetVector.h" |
20 | | #include "llvm/ADT/SmallVector.h" |
21 | | #include "llvm/IR/PassManager.h" |
22 | | #include "llvm/Support/Compiler.h" |
23 | | #include <vector> |
24 | | |
25 | | namespace llvm { |
26 | | |
27 | | class AllocaInst; |
28 | | class AssumptionCache; |
29 | | class DominatorTree; |
30 | | class Function; |
31 | | class Instruction; |
32 | | class LLVMContext; |
33 | | class PHINode; |
34 | | class SelectInst; |
35 | | class Use; |
36 | | |
37 | | /// A private "module" namespace for types and utilities used by SROA. These |
38 | | /// are implementation details and should not be used by clients. |
39 | | namespace sroa LLVM_LIBRARY_VISIBILITY { |
40 | | |
41 | | class AllocaSliceRewriter; |
42 | | class AllocaSlices; |
43 | | class Partition; |
44 | | class SROALegacyPass; |
45 | | |
46 | | } // end namespace sroa |
47 | | |
48 | | /// \brief An optimization pass providing Scalar Replacement of Aggregates. |
49 | | /// |
50 | | /// This pass takes allocations which can be completely analyzed (that is, they |
51 | | /// don't escape) and tries to turn them into scalar SSA values. There are |
52 | | /// a few steps to this process. |
53 | | /// |
54 | | /// 1) It takes allocations of aggregates and analyzes the ways in which they |
55 | | /// are used to try to split them into smaller allocations, ideally of |
56 | | /// a single scalar data type. It will split up memcpy and memset accesses |
57 | | /// as necessary and try to isolate individual scalar accesses. |
58 | | /// 2) It will transform accesses into forms which are suitable for SSA value |
59 | | /// promotion. This can be replacing a memset with a scalar store of an |
60 | | /// integer value, or it can involve speculating operations on a PHI or |
61 | | /// select to be a PHI or select of the results. |
62 | | /// 3) Finally, this will try to detect a pattern of accesses which map cleanly |
63 | | /// onto insert and extract operations on a vector value, and convert them to |
64 | | /// this form. By doing so, it will enable promotion of vector aggregates to |
65 | | /// SSA vector values. |
66 | | class SROA : public PassInfoMixin<SROA> { |
67 | | LLVMContext *C = nullptr; |
68 | | DominatorTree *DT = nullptr; |
69 | | AssumptionCache *AC = nullptr; |
70 | | |
71 | | /// \brief Worklist of alloca instructions to simplify. |
72 | | /// |
73 | | /// Each alloca in the function is added to this. Each new alloca formed gets |
74 | | /// added to it as well to recursively simplify unless that alloca can be |
75 | | /// directly promoted. Finally, each time we rewrite a use of an alloca other |
76 | | /// the one being actively rewritten, we add it back onto the list if not |
77 | | /// already present to ensure it is re-visited. |
78 | | SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist; |
79 | | |
80 | | /// \brief A collection of instructions to delete. |
81 | | /// We try to batch deletions to simplify code and make things a bit more |
82 | | /// efficient. |
83 | | SetVector<Instruction *, SmallVector<Instruction *, 8>> DeadInsts; |
84 | | |
85 | | /// \brief Post-promotion worklist. |
86 | | /// |
87 | | /// Sometimes we discover an alloca which has a high probability of becoming |
88 | | /// viable for SROA after a round of promotion takes place. In those cases, |
89 | | /// the alloca is enqueued here for re-processing. |
90 | | /// |
91 | | /// Note that we have to be very careful to clear allocas out of this list in |
92 | | /// the event they are deleted. |
93 | | SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist; |
94 | | |
95 | | /// \brief A collection of alloca instructions we can directly promote. |
96 | | std::vector<AllocaInst *> PromotableAllocas; |
97 | | |
98 | | /// \brief A worklist of PHIs to speculate prior to promoting allocas. |
99 | | /// |
100 | | /// All of these PHIs have been checked for the safety of speculation and by |
101 | | /// being speculated will allow promoting allocas currently in the promotable |
102 | | /// queue. |
103 | | SetVector<PHINode *, SmallVector<PHINode *, 2>> SpeculatablePHIs; |
104 | | |
105 | | /// \brief A worklist of select instructions to speculate prior to promoting |
106 | | /// allocas. |
107 | | /// |
108 | | /// All of these select instructions have been checked for the safety of |
109 | | /// speculation and by being speculated will allow promoting allocas |
110 | | /// currently in the promotable queue. |
111 | | SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects; |
112 | | |
113 | | public: |
114 | 36.5k | SROA() = default; |
115 | | |
116 | | /// \brief Run the pass over the function. |
117 | | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
118 | | |
119 | | private: |
120 | | friend class sroa::AllocaSliceRewriter; |
121 | | friend class sroa::SROALegacyPass; |
122 | | |
123 | | /// Helper used by both the public run method and by the legacy pass. |
124 | | PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT, |
125 | | AssumptionCache &RunAC); |
126 | | |
127 | | bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS); |
128 | | AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS, |
129 | | sroa::Partition &P); |
130 | | bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS); |
131 | | bool runOnAlloca(AllocaInst &AI); |
132 | | void clobberUse(Use &U); |
133 | | void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas); |
134 | | bool promoteAllocas(Function &F); |
135 | | }; |
136 | | |
137 | | } // end namespace llvm |
138 | | |
139 | | #endif // LLVM_TRANSFORMS_SCALAR_SROA_H |