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