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