LLVM  14.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 
20 namespace llvm {
21 
22 class BasicBlock;
23 class Instruction;
24 class LoadInst;
25 class PHINode;
26 template <typename T> class SmallVectorImpl;
27 template <typename T> class SSAUpdaterTraits;
28 class Type;
29 class Use;
30 class Value;
31 
32 /// Helper class for SSA formation on a set of values defined in
33 /// multiple blocks.
34 ///
35 /// This is used when code duplication or another unstructured
36 /// transformation wants to rewrite a set of uses of one value with uses of a
37 /// set of values.
38 class SSAUpdater {
40 
41 private:
42  /// This keeps track of which value to use on a per-block basis. When we
43  /// insert PHI nodes, we keep track of them here.
44  void *AV = nullptr;
45 
46  /// ProtoType holds the type of the values being rewritten.
47  Type *ProtoType = nullptr;
48 
49  /// PHI nodes are given a name based on ProtoName.
50  std::string ProtoName;
51 
52  /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to
53  /// the vector.
54  SmallVectorImpl<PHINode *> *InsertedPHIs;
55 
56 public:
57  /// If InsertedPHIs is specified, it will be filled
58  /// in with all PHI Nodes created by rewriting.
59  explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
60  SSAUpdater(const SSAUpdater &) = delete;
61  SSAUpdater &operator=(const SSAUpdater &) = delete;
62  ~SSAUpdater();
63 
64  /// Reset this object to get ready for a new set of SSA updates with
65  /// type 'Ty'.
66  ///
67  /// PHI nodes get a name based on 'Name'.
68  void Initialize(Type *Ty, StringRef Name);
69 
70  /// Indicate that a rewritten value is available in the specified block
71  /// with the specified value.
73 
74  /// Return true if the SSAUpdater already has a value for the specified
75  /// block.
76  bool HasValueForBlock(BasicBlock *BB) const;
77 
78  /// Return the value for the specified block if the SSAUpdater has one,
79  /// otherwise return nullptr.
81 
82  /// Construct SSA form, materializing a value that is live at the end
83  /// of the specified block.
85 
86  /// Construct SSA form, materializing a value that is live in the
87  /// middle of the specified block.
88  ///
89  /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except
90  /// in one important case: if there is a definition of the rewritten value
91  /// after the 'use' in BB. Consider code like this:
92  ///
93  /// \code
94  /// X1 = ...
95  /// SomeBB:
96  /// use(X)
97  /// X2 = ...
98  /// br Cond, SomeBB, OutBB
99  /// \endcode
100  ///
101  /// In this case, there are two values (X1 and X2) added to the AvailableVals
102  /// set by the client of the rewriter, and those values are both live out of
103  /// their respective blocks. However, the use of X happens in the *middle* of
104  /// a block. Because of this, we need to insert a new PHI node in SomeBB to
105  /// merge the appropriate values, and this value isn't live out of the block.
107 
108  /// Rewrite a use of the symbolic value.
109  ///
110  /// This handles PHI nodes, which use their value in the corresponding
111  /// predecessor. Note that this will not work if the use is supposed to be
112  /// rewritten to a value defined in the same block as the use, but above it.
113  /// Any 'AddAvailableValue's added for the use's block will be considered to
114  /// be below it.
115  void RewriteUse(Use &U);
116 
117  /// Rewrite a use like \c RewriteUse but handling in-block definitions.
118  ///
119  /// This version of the method can rewrite uses in the same block as
120  /// a definition, because it assumes that all uses of a value are below any
121  /// inserted values.
123 
124 private:
125  Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
126 };
127 
128 /// Helper class for promoting a collection of loads and stores into SSA
129 /// Form using the SSAUpdater.
130 ///
131 /// This handles complexities that SSAUpdater doesn't, such as multiple loads
132 /// and stores in one block.
133 ///
134 /// Clients of this class are expected to subclass this and implement the
135 /// virtual methods.
137 protected:
139 
140 public:
143  virtual ~LoadAndStorePromoter() = default;
144 
145  /// This does the promotion.
146  ///
147  /// Insts is a list of loads and stores to promote, and Name is the basename
148  /// for the PHIs to insert. After this is complete, the loads and stores are
149  /// removed from the code.
150  void run(const SmallVectorImpl<Instruction *> &Insts);
151 
152  /// Return true if the specified instruction is in the Inst list.
153  ///
154  /// The Insts list is the one passed into the constructor. Clients should
155  /// implement this with a more efficient version if possible.
156  virtual bool isInstInList(Instruction *I,
157  const SmallVectorImpl<Instruction *> &Insts) const;
158 
159  /// This hook is invoked after all the stores are found and inserted as
160  /// available values.
162 
163  /// Clients can choose to implement this to get notified right before
164  /// a load is RAUW'd another value.
165  virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {}
166 
167  /// Called before each instruction is deleted.
168  virtual void instructionDeleted(Instruction *I) const {}
169 
170  /// Called to update debug info associated with the instruction.
171  virtual void updateDebugInfo(Instruction *I) const {}
172 };
173 
174 } // end namespace llvm
175 
176 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
llvm::SSAUpdater::Initialize
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
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SSAUpdater::SSAUpdater
SSAUpdater(SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
If InsertedPHIs is specified, it will be filled in with all PHI Nodes created by rewriting.
Definition: SSAUpdater.cpp:46
llvm::LoadAndStorePromoter
Helper class for promoting a collection of loads and stores into SSA Form using the SSAUpdater.
Definition: SSAUpdater.h:136
StringRef.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::LoadAndStorePromoter::updateDebugInfo
virtual void updateDebugInfo(Instruction *I) const
Called to update debug info associated with the instruction.
Definition: SSAUpdater.h:171
llvm::LoadAndStorePromoter::replaceLoadWithValue
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:165
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::LoadAndStorePromoter::run
void run(const SmallVectorImpl< Instruction * > &Insts)
This does the promotion.
Definition: SSAUpdater.cpp:337
llvm::SSAUpdater::RewriteUseAfterInsertions
void RewriteUseAfterInsertions(Use &U)
Rewrite a use like RewriteUse but handling in-block definitions.
Definition: SSAUpdater.cpp:199
llvm::Instruction
Definition: Instruction.h:45
llvm::SSAUpdater::~SSAUpdater
~SSAUpdater()
Definition: SSAUpdater.cpp:49
llvm::LoadAndStorePromoter::~LoadAndStorePromoter
virtual ~LoadAndStorePromoter()=default
llvm::SSAUpdater::GetValueInMiddleOfBlock
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
Definition: SSAUpdater.cpp:98
I
#define I(x, y, z)
Definition: MD5.cpp:59
ArrayRef.h
TemplateParamKind::Type
@ Type
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::SSAUpdater::operator=
SSAUpdater & operator=(const SSAUpdater &)=delete
llvm::LoadAndStorePromoter::SSA
SSAUpdater & SSA
Definition: SSAUpdater.h:138
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::SSAUpdater::GetValueAtEndOfBlock
Value * GetValueAtEndOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live at the end of the specified block.
Definition: SSAUpdater.cpp:93
llvm::SSAUpdater::FindValueForBlock
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
Definition: SSAUpdater.cpp:66
llvm::LoadAndStorePromoter::LoadAndStorePromoter
LoadAndStorePromoter(ArrayRef< const Instruction * > Insts, SSAUpdater &S, StringRef Name=StringRef())
Definition: SSAUpdater.cpp:322
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::SSAUpdater::HasValueForBlock
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Definition: SSAUpdater.cpp:62
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SSAUpdaterTraits
Definition: MachineSSAUpdater.h:28
llvm::LoadAndStorePromoter::doExtraRewritesBeforeFinalDeletion
virtual void doExtraRewritesBeforeFinalDeletion()
This hook is invoked after all the stores are found and inserted as available values.
Definition: SSAUpdater.h:161
llvm::SSAUpdater::RewriteUse
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
Definition: SSAUpdater.cpp:187
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::LoadAndStorePromoter::instructionDeleted
virtual void instructionDeleted(Instruction *I) const
Called before each instruction is deleted.
Definition: SSAUpdater.h:168
llvm::SSAUpdater::AddAvailableValue
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
llvm::SSAUpdater
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:38
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::LoadAndStorePromoter::isInstInList
virtual bool isInstInList(Instruction *I, const SmallVectorImpl< Instruction * > &Insts) const
Return true if the specified instruction is in the Inst list.
Definition: SSAUpdater.cpp:476