1 | //===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- 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 | // This file declares the SSAUpdater class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H |
14 | #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H |
15 | |
16 | #include "llvm/ADT/ArrayRef.h" |
17 | #include "llvm/ADT/StringRef.h" |
18 | #include <string> |
19 | |
20 | namespace llvm { |
21 | |
22 | class BasicBlock; |
23 | class Instruction; |
24 | class LoadInst; |
25 | class PHINode; |
26 | class DPValue; |
27 | template <typename T> class SmallVectorImpl; |
28 | template <typename T> class SSAUpdaterTraits; |
29 | class Type; |
30 | class Use; |
31 | class Value; |
32 | class DbgValueInst; |
33 | |
34 | /// Helper class for SSA formation on a set of values defined in |
35 | /// multiple blocks. |
36 | /// |
37 | /// This is used when code duplication or another unstructured |
38 | /// transformation wants to rewrite a set of uses of one value with uses of a |
39 | /// set of values. |
40 | class SSAUpdater { |
41 | friend class SSAUpdaterTraits<SSAUpdater>; |
42 | |
43 | private: |
44 | /// This keeps track of which value to use on a per-block basis. When we |
45 | /// insert PHI nodes, we keep track of them here. |
46 | void *AV = nullptr; |
47 | |
48 | /// ProtoType holds the type of the values being rewritten. |
49 | Type *ProtoType = nullptr; |
50 | |
51 | /// PHI nodes are given a name based on ProtoName. |
52 | std::string ProtoName; |
53 | |
54 | /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to |
55 | /// the vector. |
56 | SmallVectorImpl<PHINode *> *InsertedPHIs; |
57 | |
58 | public: |
59 | /// If InsertedPHIs is specified, it will be filled |
60 | /// in with all PHI Nodes created by rewriting. |
61 | explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); |
62 | SSAUpdater(const SSAUpdater &) = delete; |
63 | SSAUpdater &operator=(const SSAUpdater &) = delete; |
64 | ~SSAUpdater(); |
65 | |
66 | /// Reset this object to get ready for a new set of SSA updates with |
67 | /// type 'Ty'. |
68 | /// |
69 | /// PHI nodes get a name based on 'Name'. |
70 | void Initialize(Type *Ty, StringRef Name); |
71 | |
72 | /// Indicate that a rewritten value is available in the specified block |
73 | /// with the specified value. |
74 | void AddAvailableValue(BasicBlock *BB, Value *V); |
75 | |
76 | /// Return true if the SSAUpdater already has a value for the specified |
77 | /// block. |
78 | bool HasValueForBlock(BasicBlock *BB) const; |
79 | |
80 | /// Return the value for the specified block if the SSAUpdater has one, |
81 | /// otherwise return nullptr. |
82 | Value *FindValueForBlock(BasicBlock *BB) const; |
83 | |
84 | /// Construct SSA form, materializing a value that is live at the end |
85 | /// of the specified block. |
86 | Value *GetValueAtEndOfBlock(BasicBlock *BB); |
87 | |
88 | /// Construct SSA form, materializing a value that is live in the |
89 | /// middle of the specified block. |
90 | /// |
91 | /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except |
92 | /// in one important case: if there is a definition of the rewritten value |
93 | /// after the 'use' in BB. Consider code like this: |
94 | /// |
95 | /// \code |
96 | /// X1 = ... |
97 | /// SomeBB: |
98 | /// use(X) |
99 | /// X2 = ... |
100 | /// br Cond, SomeBB, OutBB |
101 | /// \endcode |
102 | /// |
103 | /// In this case, there are two values (X1 and X2) added to the AvailableVals |
104 | /// set by the client of the rewriter, and those values are both live out of |
105 | /// their respective blocks. However, the use of X happens in the *middle* of |
106 | /// a block. Because of this, we need to insert a new PHI node in SomeBB to |
107 | /// merge the appropriate values, and this value isn't live out of the block. |
108 | Value *GetValueInMiddleOfBlock(BasicBlock *BB); |
109 | |
110 | /// Rewrite a use of the symbolic value. |
111 | /// |
112 | /// This handles PHI nodes, which use their value in the corresponding |
113 | /// predecessor. Note that this will not work if the use is supposed to be |
114 | /// rewritten to a value defined in the same block as the use, but above it. |
115 | /// Any 'AddAvailableValue's added for the use's block will be considered to |
116 | /// be below it. |
117 | void RewriteUse(Use &U); |
118 | |
119 | /// Rewrite debug value intrinsics to conform to a new SSA form. |
120 | /// |
121 | /// This will scout out all the debug value instrinsics associated with |
122 | /// the instruction. Anything outside of its block will have its |
123 | /// value set to the new SSA value if available, and undef if not. |
124 | void UpdateDebugValues(Instruction *I); |
125 | void UpdateDebugValues(Instruction *I, |
126 | SmallVectorImpl<DbgValueInst *> &DbgValues); |
127 | void UpdateDebugValues(Instruction *I, SmallVectorImpl<DPValue *> &DbgValues); |
128 | |
129 | /// Rewrite a use like \c RewriteUse but handling in-block definitions. |
130 | /// |
131 | /// This version of the method can rewrite uses in the same block as |
132 | /// a definition, because it assumes that all uses of a value are below any |
133 | /// inserted values. |
134 | void RewriteUseAfterInsertions(Use &U); |
135 | |
136 | private: |
137 | Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); |
138 | void UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue); |
139 | void UpdateDebugValue(Instruction *I, DPValue *DbgValue); |
140 | }; |
141 | |
142 | /// Helper class for promoting a collection of loads and stores into SSA |
143 | /// Form using the SSAUpdater. |
144 | /// |
145 | /// This handles complexities that SSAUpdater doesn't, such as multiple loads |
146 | /// and stores in one block. |
147 | /// |
148 | /// Clients of this class are expected to subclass this and implement the |
149 | /// virtual methods. |
150 | class LoadAndStorePromoter { |
151 | protected: |
152 | SSAUpdater &SSA; |
153 | |
154 | public: |
155 | LoadAndStorePromoter(ArrayRef<const Instruction *> Insts, |
156 | SSAUpdater &S, StringRef Name = StringRef()); |
157 | virtual ~LoadAndStorePromoter() = default; |
158 | |
159 | /// This does the promotion. |
160 | /// |
161 | /// Insts is a list of loads and stores to promote, and Name is the basename |
162 | /// for the PHIs to insert. After this is complete, the loads and stores are |
163 | /// removed from the code. |
164 | void run(const SmallVectorImpl<Instruction *> &Insts); |
165 | |
166 | /// Return true if the specified instruction is in the Inst list. |
167 | /// |
168 | /// The Insts list is the one passed into the constructor. Clients should |
169 | /// implement this with a more efficient version if possible. |
170 | virtual bool isInstInList(Instruction *I, |
171 | const SmallVectorImpl<Instruction *> &Insts) const; |
172 | |
173 | /// This hook is invoked after all the stores are found and inserted as |
174 | /// available values. |
175 | virtual void doExtraRewritesBeforeFinalDeletion() {} |
176 | |
177 | /// Clients can choose to implement this to get notified right before |
178 | /// a load is RAUW'd another value. |
179 | virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {} |
180 | |
181 | /// Called before each instruction is deleted. |
182 | virtual void instructionDeleted(Instruction *I) const {} |
183 | |
184 | /// Called to update debug info associated with the instruction. |
185 | virtual void updateDebugInfo(Instruction *I) const {} |
186 | |
187 | /// Return false if a sub-class wants to keep one of the loads/stores |
188 | /// after the SSA construction. |
189 | virtual bool shouldDelete(Instruction *I) const { return true; } |
190 | }; |
191 | |
192 | } // end namespace llvm |
193 | |
194 | #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H |
195 | |