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