Line data Source code
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 : /// 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 : /// 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 : /// 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 : /// 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 : /// A collection of alloca instructions we can directly promote.
96 : std::vector<AllocaInst *> PromotableAllocas;
97 :
98 : /// 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 : /// 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 5278 : SROA() = default;
115 :
116 : /// 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 : bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
134 : bool promoteAllocas(Function &F);
135 : };
136 :
137 : } // end namespace llvm
138 :
139 : #endif // LLVM_TRANSFORMS_SCALAR_SROA_H
|
