LLVM 18.0.0git
SSAUpdater.cpp
Go to the documentation of this file.
1//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
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 implements the SSAUpdater class.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/STLExtras.h"
19#include "llvm/IR/BasicBlock.h"
20#include "llvm/IR/CFG.h"
21#include "llvm/IR/Constants.h"
22#include "llvm/IR/DebugInfo.h"
23#include "llvm/IR/DebugLoc.h"
24#include "llvm/IR/Instruction.h"
26#include "llvm/IR/Module.h"
27#include "llvm/IR/Use.h"
28#include "llvm/IR/Value.h"
30#include "llvm/Support/Debug.h"
33#include <cassert>
34#include <utility>
35
36using namespace llvm;
37
38#define DEBUG_TYPE "ssaupdater"
39
41
43 return *static_cast<AvailableValsTy*>(AV);
44}
45
47 : InsertedPHIs(NewPHI) {}
48
50 delete static_cast<AvailableValsTy*>(AV);
51}
52
54 if (!AV)
55 AV = new AvailableValsTy();
56 else
58 ProtoType = Ty;
59 ProtoName = std::string(Name);
60}
61
63 return getAvailableVals(AV).count(BB);
64}
65
67 return getAvailableVals(AV).lookup(BB);
68}
69
71 assert(ProtoType && "Need to initialize SSAUpdater");
72 assert(ProtoType == V->getType() &&
73 "All rewritten values must have the same type");
74 getAvailableVals(AV)[BB] = V;
75}
76
79 unsigned PHINumValues = PHI->getNumIncomingValues();
80 if (PHINumValues != ValueMapping.size())
81 return false;
82
83 // Scan the phi to see if it matches.
84 for (unsigned i = 0, e = PHINumValues; i != e; ++i)
85 if (ValueMapping[PHI->getIncomingBlock(i)] !=
86 PHI->getIncomingValue(i)) {
87 return false;
88 }
89
90 return true;
91}
92
94 Value *Res = GetValueAtEndOfBlockInternal(BB);
95 return Res;
96}
97
99 // If there is no definition of the renamed variable in this block, just use
100 // GetValueAtEndOfBlock to do our work.
101 if (!HasValueForBlock(BB))
102 return GetValueAtEndOfBlock(BB);
103
104 // Otherwise, we have the hard case. Get the live-in values for each
105 // predecessor.
107 Value *SingularValue = nullptr;
108
109 // We can get our predecessor info by walking the pred_iterator list, but it
110 // is relatively slow. If we already have PHI nodes in this block, walk one
111 // of them to get the predecessor list instead.
112 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
113 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
114 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
115 Value *PredVal = GetValueAtEndOfBlock(PredBB);
116 PredValues.push_back(std::make_pair(PredBB, PredVal));
117
118 // Compute SingularValue.
119 if (i == 0)
120 SingularValue = PredVal;
121 else if (PredVal != SingularValue)
122 SingularValue = nullptr;
123 }
124 } else {
125 bool isFirstPred = true;
126 for (BasicBlock *PredBB : predecessors(BB)) {
127 Value *PredVal = GetValueAtEndOfBlock(PredBB);
128 PredValues.push_back(std::make_pair(PredBB, PredVal));
129
130 // Compute SingularValue.
131 if (isFirstPred) {
132 SingularValue = PredVal;
133 isFirstPred = false;
134 } else if (PredVal != SingularValue)
135 SingularValue = nullptr;
136 }
137 }
138
139 // If there are no predecessors, just return undef.
140 if (PredValues.empty())
141 return UndefValue::get(ProtoType);
142
143 // Otherwise, if all the merged values are the same, just use it.
144 if (SingularValue)
145 return SingularValue;
146
147 // Otherwise, we do need a PHI: check to see if we already have one available
148 // in this block that produces the right value.
149 if (isa<PHINode>(BB->begin())) {
150 SmallDenseMap<BasicBlock *, Value *, 8> ValueMapping(PredValues.begin(),
151 PredValues.end());
152 for (PHINode &SomePHI : BB->phis()) {
153 if (IsEquivalentPHI(&SomePHI, ValueMapping))
154 return &SomePHI;
155 }
156 }
157
158 // Ok, we have no way out, insert a new one now.
159 PHINode *InsertedPHI =
160 PHINode::Create(ProtoType, PredValues.size(), ProtoName);
161 InsertedPHI->insertBefore(BB->begin());
162
163 // Fill in all the predecessors of the PHI.
164 for (const auto &PredValue : PredValues)
165 InsertedPHI->addIncoming(PredValue.second, PredValue.first);
166
167 // See if the PHI node can be merged to a single value. This can happen in
168 // loop cases when we get a PHI of itself and one other value.
169 if (Value *V =
170 simplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) {
171 InsertedPHI->eraseFromParent();
172 return V;
173 }
174
175 // Set the DebugLoc of the inserted PHI, if available.
176 DebugLoc DL;
177 if (const Instruction *I = BB->getFirstNonPHI())
178 DL = I->getDebugLoc();
179 InsertedPHI->setDebugLoc(DL);
180
181 // If the client wants to know about all new instructions, tell it.
182 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
183
184 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
185 return InsertedPHI;
186}
187
189 Instruction *User = cast<Instruction>(U.getUser());
190
191 Value *V;
192 if (PHINode *UserPN = dyn_cast<PHINode>(User))
193 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
194 else
195 V = GetValueInMiddleOfBlock(User->getParent());
196
197 U.set(V);
198}
199
202 llvm::findDbgValues(DbgValues, I);
203 for (auto &DbgValue : DbgValues) {
204 if (DbgValue->getParent() == I->getParent())
205 continue;
206 UpdateDebugValue(I, DbgValue);
207 }
208}
209
212 for (auto &DbgValue : DbgValues) {
213 UpdateDebugValue(I, DbgValue);
214 }
215}
216
217void SSAUpdater::UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue) {
218 BasicBlock *UserBB = DbgValue->getParent();
219 if (HasValueForBlock(UserBB)) {
220 Value *NewVal = GetValueAtEndOfBlock(UserBB);
221 DbgValue->replaceVariableLocationOp(I, NewVal);
222 }
223 else
224 DbgValue->setKillLocation();
225}
226
228 Instruction *User = cast<Instruction>(U.getUser());
229
230 Value *V;
231 if (PHINode *UserPN = dyn_cast<PHINode>(User))
232 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
233 else
234 V = GetValueAtEndOfBlock(User->getParent());
235
236 U.set(V);
237}
238
239namespace llvm {
240
241template<>
243public:
245 using ValT = Value *;
246 using PhiT = PHINode;
248
249 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }
250 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }
251
252 class PHI_iterator {
253 private:
254 PHINode *PHI;
255 unsigned idx;
256
257 public:
258 explicit PHI_iterator(PHINode *P) // begin iterator
259 : PHI(P), idx(0) {}
260 PHI_iterator(PHINode *P, bool) // end iterator
261 : PHI(P), idx(PHI->getNumIncomingValues()) {}
262
263 PHI_iterator &operator++() { ++idx; return *this; }
264 bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
265 bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
266
267 Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
268 BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }
269 };
270
271 static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
272 static PHI_iterator PHI_end(PhiT *PHI) {
273 return PHI_iterator(PHI, true);
274 }
275
276 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
277 /// vector, set Info->NumPreds, and allocate space in Info->Preds.
280 // We can get our predecessor info by walking the pred_iterator list,
281 // but it is relatively slow. If we already have PHI nodes in this
282 // block, walk one of them to get the predecessor list instead.
283 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin()))
284 append_range(*Preds, SomePhi->blocks());
285 else
286 append_range(*Preds, predecessors(BB));
287 }
288
289 /// GetUndefVal - Get an undefined value of the same type as the value
290 /// being handled.
291 static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) {
292 return UndefValue::get(Updater->ProtoType);
293 }
294
295 /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
296 /// Reserve space for the operands but do not fill them in yet.
297 static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
298 SSAUpdater *Updater) {
299 PHINode *PHI =
300 PHINode::Create(Updater->ProtoType, NumPreds, Updater->ProtoName);
301 PHI->insertBefore(BB->begin());
302 return PHI;
303 }
304
305 /// AddPHIOperand - Add the specified value as an operand of the PHI for
306 /// the specified predecessor block.
307 static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
308 PHI->addIncoming(Val, Pred);
309 }
310
311 /// ValueIsPHI - Check if a value is a PHI.
312 static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
313 return dyn_cast<PHINode>(Val);
314 }
315
316 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
317 /// operands, i.e., it was just added.
318 static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
319 PHINode *PHI = ValueIsPHI(Val, Updater);
320 if (PHI && PHI->getNumIncomingValues() == 0)
321 return PHI;
322 return nullptr;
323 }
324
325 /// GetPHIValue - For the specified PHI instruction, return the value
326 /// that it defines.
328 return PHI;
329 }
330};
331
332} // end namespace llvm
333
334/// Check to see if AvailableVals has an entry for the specified BB and if so,
335/// return it. If not, construct SSA form by first calculating the required
336/// placement of PHIs and then inserting new PHIs where needed.
337Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
338 AvailableValsTy &AvailableVals = getAvailableVals(AV);
339 if (Value *V = AvailableVals[BB])
340 return V;
341
342 SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
343 return Impl.GetValue(BB);
344}
345
346//===----------------------------------------------------------------------===//
347// LoadAndStorePromoter Implementation
348//===----------------------------------------------------------------------===//
349
352 SSAUpdater &S, StringRef BaseName) : SSA(S) {
353 if (Insts.empty()) return;
354
355 const Value *SomeVal;
356 if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0]))
357 SomeVal = LI;
358 else
359 SomeVal = cast<StoreInst>(Insts[0])->getOperand(0);
360
361 if (BaseName.empty())
362 BaseName = SomeVal->getName();
363 SSA.Initialize(SomeVal->getType(), BaseName);
364}
365
367 // First step: bucket up uses of the alloca by the block they occur in.
368 // This is important because we have to handle multiple defs/uses in a block
369 // ourselves: SSAUpdater is purely for cross-block references.
371
372 for (Instruction *User : Insts)
373 UsesByBlock[User->getParent()].push_back(User);
374
375 // Okay, now we can iterate over all the blocks in the function with uses,
376 // processing them. Keep track of which loads are loading a live-in value.
377 // Walk the uses in the use-list order to be determinstic.
378 SmallVector<LoadInst *, 32> LiveInLoads;
379 DenseMap<Value *, Value *> ReplacedLoads;
380
381 for (Instruction *User : Insts) {
382 BasicBlock *BB = User->getParent();
383 TinyPtrVector<Instruction *> &BlockUses = UsesByBlock[BB];
384
385 // If this block has already been processed, ignore this repeat use.
386 if (BlockUses.empty()) continue;
387
388 // Okay, this is the first use in the block. If this block just has a
389 // single user in it, we can rewrite it trivially.
390 if (BlockUses.size() == 1) {
391 // If it is a store, it is a trivial def of the value in the block.
392 if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
393 updateDebugInfo(SI);
394 SSA.AddAvailableValue(BB, SI->getOperand(0));
395 } else
396 // Otherwise it is a load, queue it to rewrite as a live-in load.
397 LiveInLoads.push_back(cast<LoadInst>(User));
398 BlockUses.clear();
399 continue;
400 }
401
402 // Otherwise, check to see if this block is all loads.
403 bool HasStore = false;
404 for (Instruction *I : BlockUses) {
405 if (isa<StoreInst>(I)) {
406 HasStore = true;
407 break;
408 }
409 }
410
411 // If so, we can queue them all as live in loads. We don't have an
412 // efficient way to tell which on is first in the block and don't want to
413 // scan large blocks, so just add all loads as live ins.
414 if (!HasStore) {
415 for (Instruction *I : BlockUses)
416 LiveInLoads.push_back(cast<LoadInst>(I));
417 BlockUses.clear();
418 continue;
419 }
420
421 // Otherwise, we have mixed loads and stores (or just a bunch of stores).
422 // Since SSAUpdater is purely for cross-block values, we need to determine
423 // the order of these instructions in the block. If the first use in the
424 // block is a load, then it uses the live in value. The last store defines
425 // the live out value. We handle this by doing a linear scan of the block.
426 Value *StoredValue = nullptr;
427 for (Instruction &I : *BB) {
428 if (LoadInst *L = dyn_cast<LoadInst>(&I)) {
429 // If this is a load from an unrelated pointer, ignore it.
430 if (!isInstInList(L, Insts)) continue;
431
432 // If we haven't seen a store yet, this is a live in use, otherwise
433 // use the stored value.
434 if (StoredValue) {
435 replaceLoadWithValue(L, StoredValue);
436 L->replaceAllUsesWith(StoredValue);
437 ReplacedLoads[L] = StoredValue;
438 } else {
439 LiveInLoads.push_back(L);
440 }
441 continue;
442 }
443
444 if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
445 // If this is a store to an unrelated pointer, ignore it.
446 if (!isInstInList(SI, Insts)) continue;
447 updateDebugInfo(SI);
448
449 // Remember that this is the active value in the block.
450 StoredValue = SI->getOperand(0);
451 }
452 }
453
454 // The last stored value that happened is the live-out for the block.
455 assert(StoredValue && "Already checked that there is a store in block");
456 SSA.AddAvailableValue(BB, StoredValue);
457 BlockUses.clear();
458 }
459
460 // Okay, now we rewrite all loads that use live-in values in the loop,
461 // inserting PHI nodes as necessary.
462 for (LoadInst *ALoad : LiveInLoads) {
463 Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());
464 replaceLoadWithValue(ALoad, NewVal);
465
466 // Avoid assertions in unreachable code.
467 if (NewVal == ALoad) NewVal = PoisonValue::get(NewVal->getType());
468 ALoad->replaceAllUsesWith(NewVal);
469 ReplacedLoads[ALoad] = NewVal;
470 }
471
472 // Allow the client to do stuff before we start nuking things.
474
475 // Now that everything is rewritten, delete the old instructions from the
476 // function. They should all be dead now.
477 for (Instruction *User : Insts) {
478 if (!shouldDelete(User))
479 continue;
480
481 // If this is a load that still has uses, then the load must have been added
482 // as a live value in the SSAUpdate data structure for a block (e.g. because
483 // the loaded value was stored later). In this case, we need to recursively
484 // propagate the updates until we get to the real value.
485 if (!User->use_empty()) {
486 Value *NewVal = ReplacedLoads[User];
487 assert(NewVal && "not a replaced load?");
488
489 // Propagate down to the ultimate replacee. The intermediately loads
490 // could theoretically already have been deleted, so we don't want to
491 // dereference the Value*'s.
492 DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);
493 while (RLI != ReplacedLoads.end()) {
494 NewVal = RLI->second;
495 RLI = ReplacedLoads.find(NewVal);
496 }
497
498 replaceLoadWithValue(cast<LoadInst>(User), NewVal);
499 User->replaceAllUsesWith(NewVal);
500 }
501
503 User->eraseFromParent();
504 }
505}
506
507bool
510 const {
511 return is_contained(Insts, I);
512}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
std::string Name
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define I(x, y, z)
Definition: MD5.cpp:58
static AvailableValsTy & getAvailableVals(void *AV)
DenseMap< MachineBasicBlock *, Register > AvailableValsTy
Memory SSA
Definition: MemorySSA.cpp:71
Module.h This file contains the declarations for the Module class.
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static AvailableValsTy & getAvailableVals(void *AV)
Definition: SSAUpdater.cpp:42
static bool IsEquivalentPHI(PHINode *PHI, SmallDenseMap< BasicBlock *, Value *, 8 > &ValueMapping)
Definition: SSAUpdater.cpp:77
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
This defines the Use class.
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
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:335
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:393
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:145
This represents the llvm.dbg.value instruction.
A debug info location.
Definition: DebugLoc.h:33
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
unsigned size() const
Definition: DenseMap.h:99
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:89
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:83
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:389
virtual void instructionDeleted(Instruction *I) const
Called before each instruction is deleted.
Definition: SSAUpdater.h:179
virtual void doExtraRewritesBeforeFinalDeletion()
This hook is invoked after all the stores are found and inserted as available values.
Definition: SSAUpdater.h:172
LoadAndStorePromoter(ArrayRef< const Instruction * > Insts, SSAUpdater &S, StringRef Name=StringRef())
Definition: SSAUpdater.cpp:351
virtual bool isInstInList(Instruction *I, const SmallVectorImpl< Instruction * > &Insts) const
Return true if the specified instruction is in the Inst list.
Definition: SSAUpdater.cpp:508
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:176
void run(const SmallVectorImpl< Instruction * > &Insts)
This does the promotion.
Definition: SSAUpdater.cpp:366
virtual void updateDebugInfo(Instruction *I) const
Called to update debug info associated with the instruction.
Definition: SSAUpdater.h:182
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:186
An instruction for reading from memory.
Definition: Instructions.h:177
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:254
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1743
bool operator!=(const PHI_iterator &x) const
Definition: SSAUpdater.cpp:265
bool operator==(const PHI_iterator &x) const
Definition: SSAUpdater.cpp:264
static BlkSucc_iterator BlkSucc_end(BlkT *BB)
Definition: SSAUpdater.cpp:250
static BlkSucc_iterator BlkSucc_begin(BlkT *BB)
Definition: SSAUpdater.cpp:249
static void FindPredecessorBlocks(BasicBlock *BB, SmallVectorImpl< BasicBlock * > *Preds)
FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds vector, set Info->NumPreds,...
Definition: SSAUpdater.cpp:278
static Value * CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, SSAUpdater *Updater)
CreateEmptyPHI - Create a new PHI instruction in the specified block.
Definition: SSAUpdater.cpp:297
static PHINode * ValueIsNewPHI(Value *Val, SSAUpdater *Updater)
ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source operands, i....
Definition: SSAUpdater.cpp:318
static PHI_iterator PHI_begin(PhiT *PHI)
Definition: SSAUpdater.cpp:271
static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred)
AddPHIOperand - Add the specified value as an operand of the PHI for the specified predecessor block.
Definition: SSAUpdater.cpp:307
static Value * GetPHIValue(PHINode *PHI)
GetPHIValue - For the specified PHI instruction, return the value that it defines.
Definition: SSAUpdater.cpp:327
static PHI_iterator PHI_end(PhiT *PHI)
Definition: SSAUpdater.cpp:272
static PHINode * ValueIsPHI(Value *Val, SSAUpdater *Updater)
ValueIsPHI - Check if a value is a PHI.
Definition: SSAUpdater.cpp:312
static Value * GetUndefVal(BasicBlock *BB, SSAUpdater *Updater)
GetUndefVal - Get an undefined value of the same type as the value being handled.
Definition: SSAUpdater.cpp:291
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:39
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:227
Value * FindValueForBlock(BasicBlock *BB) const
Return the value for the specified block if the SSAUpdater has one, otherwise return nullptr.
Definition: SSAUpdater.cpp:66
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
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
void UpdateDebugValues(Instruction *I)
Rewrite debug value intrinsics to conform to a new SSA form.
Definition: SSAUpdater.cpp:200
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
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
constexpr bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:134
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:29
bool empty() const
unsigned size() const
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1724
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:535
bool use_empty() const
Definition: Value.h:344
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2037
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:242
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:99
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1884