LLVM 20.0.0git
SSAUpdater.h
Go to the documentation of this file.
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
20namespace llvm {
21
22class BasicBlock;
23class Instruction;
24class LoadInst;
25class PHINode;
27template <typename T> class SmallVectorImpl;
28template <typename T> class SSAUpdaterTraits;
29class Type;
30class Use;
31class Value;
32class 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.
41 friend class SSAUpdaterTraits<SSAUpdater>;
42
43private:
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
58public:
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;
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.
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.
83
84 /// Construct SSA form, materializing a value that is live at the end
85 /// of the specified block.
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.
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.
129
130 /// Rewrite a use like \c RewriteUse but handling in-block definitions.
131 ///
132 /// This version of the method can rewrite uses in the same block as
133 /// a definition, because it assumes that all uses of a value are below any
134 /// inserted values.
136
137private:
138 Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
139 void UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue);
140 void UpdateDebugValue(Instruction *I, DbgVariableRecord *DbgValue);
141};
142
143/// Helper class for promoting a collection of loads and stores into SSA
144/// Form using the SSAUpdater.
145///
146/// This handles complexities that SSAUpdater doesn't, such as multiple loads
147/// and stores in one block.
148///
149/// Clients of this class are expected to subclass this and implement the
150/// virtual methods.
152protected:
154
155public:
158 virtual ~LoadAndStorePromoter() = default;
159
160 /// This does the promotion.
161 ///
162 /// Insts is a list of loads and stores to promote, and Name is the basename
163 /// for the PHIs to insert. After this is complete, the loads and stores are
164 /// removed from the code.
165 void run(const SmallVectorImpl<Instruction *> &Insts);
166
167 /// Return true if the specified instruction is in the Inst list.
168 ///
169 /// The Insts list is the one passed into the constructor. Clients should
170 /// implement this with a more efficient version if possible.
171 virtual bool isInstInList(Instruction *I,
172 const SmallVectorImpl<Instruction *> &Insts) const;
173
174 /// This hook is invoked after all the stores are found and inserted as
175 /// available values.
177
178 /// Clients can choose to implement this to get notified right before
179 /// a load is RAUW'd another value.
180 virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {}
181
182 /// Called before each instruction is deleted.
183 virtual void instructionDeleted(Instruction *I) const {}
184
185 /// Called to update debug info associated with the instruction.
186 virtual void updateDebugInfo(Instruction *I) const {}
187
188 /// Return false if a sub-class wants to keep one of the loads/stores
189 /// after the SSA construction.
190 virtual bool shouldDelete(Instruction *I) const { return true; }
191};
192
193} // end namespace llvm
194
195#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
std::string Name
#define I(x, y, z)
Definition: MD5.cpp:58
Class recording the (high level) value of a variable.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
This represents the llvm.dbg.value instruction.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
Helper class for promoting a collection of loads and stores into SSA Form using the SSAUpdater.
Definition: SSAUpdater.h:151
virtual void instructionDeleted(Instruction *I) const
Called before each instruction is deleted.
Definition: SSAUpdater.h:183
virtual void doExtraRewritesBeforeFinalDeletion()
This hook is invoked after all the stores are found and inserted as available values.
Definition: SSAUpdater.h:176
virtual bool isInstInList(Instruction *I, const SmallVectorImpl< Instruction * > &Insts) const
Return true if the specified instruction is in the Inst list.
Definition: SSAUpdater.cpp:529
virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const
Clients can choose to implement this to get notified right before a load is RAUW'd another value.
Definition: SSAUpdater.h:180
void run(const SmallVectorImpl< Instruction * > &Insts)
This does the promotion.
Definition: SSAUpdater.cpp:387
virtual ~LoadAndStorePromoter()=default
virtual void updateDebugInfo(Instruction *I) const
Called to update debug info associated with the instruction.
Definition: SSAUpdater.h:186
virtual bool shouldDelete(Instruction *I) const
Return false if a sub-class wants to keep one of the loads/stores after the SSA construction.
Definition: SSAUpdater.h:190
An instruction for reading from memory.
Definition: Instructions.h:174
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:40
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:188
void RewriteUseAfterInsertions(Use &U)
Rewrite a use like RewriteUse but handling in-block definitions.
Definition: SSAUpdater.cpp:248
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
Definition: SSAUpdater.cpp:66
SSAUpdater & operator=(const SSAUpdater &)=delete
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:53
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
Definition: SSAUpdater.cpp:98
void UpdateDebugValues(Instruction *I)
Rewrite debug value intrinsics to conform to a new SSA form.
Definition: SSAUpdater.cpp:200
SSAUpdater(const SSAUpdater &)=delete
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Definition: SSAUpdater.cpp:62
Value * GetValueAtEndOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live at the end of the specified block.
Definition: SSAUpdater.cpp:93
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18