1 //===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the SSAUpdater class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Utils/SSAUpdater.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/TinyPtrVector.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
25 #include "llvm/Transforms/Utils/Local.h"
26 #include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
30 #define DEBUG_TYPE "ssaupdater"
32 typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
33 static AvailableValsTy &getAvailableVals(void *AV) {
34 return *static_cast<AvailableValsTy*>(AV);
37 SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
38 : AV(nullptr), ProtoType(nullptr), ProtoName(), InsertedPHIs(NewPHI) {}
40 SSAUpdater::~SSAUpdater() {
41 delete static_cast<AvailableValsTy*>(AV);
44 void SSAUpdater::Initialize(Type *Ty, StringRef Name) {
46 AV = new AvailableValsTy();
48 getAvailableVals(AV).clear();
53 bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
54 return getAvailableVals(AV).count(BB);
57 void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
58 assert(ProtoType && "Need to initialize SSAUpdater");
59 assert(ProtoType == V->getType() &&
60 "All rewritten values must have the same type");
61 getAvailableVals(AV)[BB] = V;
64 static bool IsEquivalentPHI(PHINode *PHI,
65 SmallDenseMap<BasicBlock*, Value*, 8> &ValueMapping) {
66 unsigned PHINumValues = PHI->getNumIncomingValues();
67 if (PHINumValues != ValueMapping.size())
70 // Scan the phi to see if it matches.
71 for (unsigned i = 0, e = PHINumValues; i != e; ++i)
72 if (ValueMapping[PHI->getIncomingBlock(i)] !=
73 PHI->getIncomingValue(i)) {
80 Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
81 Value *Res = GetValueAtEndOfBlockInternal(BB);
85 Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
86 // If there is no definition of the renamed variable in this block, just use
87 // GetValueAtEndOfBlock to do our work.
88 if (!HasValueForBlock(BB))
89 return GetValueAtEndOfBlock(BB);
91 // Otherwise, we have the hard case. Get the live-in values for each
93 SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues;
94 Value *SingularValue = nullptr;
96 // We can get our predecessor info by walking the pred_iterator list, but it
97 // is relatively slow. If we already have PHI nodes in this block, walk one
98 // of them to get the predecessor list instead.
99 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
100 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
101 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
102 Value *PredVal = GetValueAtEndOfBlock(PredBB);
103 PredValues.push_back(std::make_pair(PredBB, PredVal));
105 // Compute SingularValue.
107 SingularValue = PredVal;
108 else if (PredVal != SingularValue)
109 SingularValue = nullptr;
112 bool isFirstPred = true;
113 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
114 BasicBlock *PredBB = *PI;
115 Value *PredVal = GetValueAtEndOfBlock(PredBB);
116 PredValues.push_back(std::make_pair(PredBB, PredVal));
118 // Compute SingularValue.
120 SingularValue = PredVal;
122 } else if (PredVal != SingularValue)
123 SingularValue = nullptr;
127 // If there are no predecessors, just return undef.
128 if (PredValues.empty())
129 return UndefValue::get(ProtoType);
131 // Otherwise, if all the merged values are the same, just use it.
133 return SingularValue;
135 // Otherwise, we do need a PHI: check to see if we already have one available
136 // in this block that produces the right value.
137 if (isa<PHINode>(BB->begin())) {
138 SmallDenseMap<BasicBlock*, Value*, 8> ValueMapping(PredValues.begin(),
141 for (BasicBlock::iterator It = BB->begin();
142 (SomePHI = dyn_cast<PHINode>(It)); ++It) {
143 if (IsEquivalentPHI(SomePHI, ValueMapping))
148 // Ok, we have no way out, insert a new one now.
149 PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(),
150 ProtoName, &BB->front());
152 // Fill in all the predecessors of the PHI.
153 for (const auto &PredValue : PredValues)
154 InsertedPHI->addIncoming(PredValue.second, PredValue.first);
156 // See if the PHI node can be merged to a single value. This can happen in
157 // loop cases when we get a PHI of itself and one other value.
158 if (Value *V = SimplifyInstruction(InsertedPHI)) {
159 InsertedPHI->eraseFromParent();
163 // Set the DebugLoc of the inserted PHI, if available.
165 if (const Instruction *I = BB->getFirstNonPHI())
166 DL = I->getDebugLoc();
167 InsertedPHI->setDebugLoc(DL);
169 // If the client wants to know about all new instructions, tell it.
170 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
172 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
176 void SSAUpdater::RewriteUse(Use &U) {
177 Instruction *User = cast<Instruction>(U.getUser());
180 if (PHINode *UserPN = dyn_cast<PHINode>(User))
181 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
183 V = GetValueInMiddleOfBlock(User->getParent());
185 // Notify that users of the existing value that it is being replaced.
186 Value *OldVal = U.get();
187 if (OldVal != V && OldVal->hasValueHandle())
188 ValueHandleBase::ValueIsRAUWd(OldVal, V);
193 void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
194 Instruction *User = cast<Instruction>(U.getUser());
197 if (PHINode *UserPN = dyn_cast<PHINode>(User))
198 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
200 V = GetValueAtEndOfBlock(User->getParent());
207 class SSAUpdaterTraits<SSAUpdater> {
209 typedef BasicBlock BlkT;
211 typedef PHINode PhiT;
213 typedef succ_iterator BlkSucc_iterator;
214 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }
215 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }
223 explicit PHI_iterator(PHINode *P) // begin iterator
225 PHI_iterator(PHINode *P, bool) // end iterator
226 : PHI(P), idx(PHI->getNumIncomingValues()) {}
228 PHI_iterator &operator++() { ++idx; return *this; }
229 bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
230 bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
231 Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
232 BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }
235 static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
236 static PHI_iterator PHI_end(PhiT *PHI) {
237 return PHI_iterator(PHI, true);
240 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
241 /// vector, set Info->NumPreds, and allocate space in Info->Preds.
242 static void FindPredecessorBlocks(BasicBlock *BB,
243 SmallVectorImpl<BasicBlock*> *Preds) {
244 // We can get our predecessor info by walking the pred_iterator list,
245 // but it is relatively slow. If we already have PHI nodes in this
246 // block, walk one of them to get the predecessor list instead.
247 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
248 Preds->append(SomePhi->block_begin(), SomePhi->block_end());
250 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
251 Preds->push_back(*PI);
255 /// GetUndefVal - Get an undefined value of the same type as the value
257 static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) {
258 return UndefValue::get(Updater->ProtoType);
261 /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
262 /// Reserve space for the operands but do not fill them in yet.
263 static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
264 SSAUpdater *Updater) {
265 PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds,
266 Updater->ProtoName, &BB->front());
270 /// AddPHIOperand - Add the specified value as an operand of the PHI for
271 /// the specified predecessor block.
272 static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
273 PHI->addIncoming(Val, Pred);
276 /// InstrIsPHI - Check if an instruction is a PHI.
278 static PHINode *InstrIsPHI(Instruction *I) {
279 return dyn_cast<PHINode>(I);
282 /// ValueIsPHI - Check if a value is a PHI.
284 static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
285 return dyn_cast<PHINode>(Val);
288 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
289 /// operands, i.e., it was just added.
290 static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
291 PHINode *PHI = ValueIsPHI(Val, Updater);
292 if (PHI && PHI->getNumIncomingValues() == 0)
297 /// GetPHIValue - For the specified PHI instruction, return the value
299 static Value *GetPHIValue(PHINode *PHI) {
304 } // End llvm namespace
306 /// Check to see if AvailableVals has an entry for the specified BB and if so,
307 /// return it. If not, construct SSA form by first calculating the required
308 /// placement of PHIs and then inserting new PHIs where needed.
309 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
310 AvailableValsTy &AvailableVals = getAvailableVals(AV);
311 if (Value *V = AvailableVals[BB])
314 SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
315 return Impl.GetValue(BB);
318 //===----------------------------------------------------------------------===//
319 // LoadAndStorePromoter Implementation
320 //===----------------------------------------------------------------------===//
322 LoadAndStorePromoter::
323 LoadAndStorePromoter(const SmallVectorImpl<Instruction*> &Insts,
324 SSAUpdater &S, StringRef BaseName) : SSA(S) {
325 if (Insts.empty()) return;
328 if (LoadInst *LI = dyn_cast<LoadInst>(Insts[0]))
331 SomeVal = cast<StoreInst>(Insts[0])->getOperand(0);
333 if (BaseName.empty())
334 BaseName = SomeVal->getName();
335 SSA.Initialize(SomeVal->getType(), BaseName);
339 void LoadAndStorePromoter::
340 run(const SmallVectorImpl<Instruction*> &Insts) const {
342 // First step: bucket up uses of the alloca by the block they occur in.
343 // This is important because we have to handle multiple defs/uses in a block
344 // ourselves: SSAUpdater is purely for cross-block references.
345 DenseMap<BasicBlock*, TinyPtrVector<Instruction*> > UsesByBlock;
347 for (Instruction *User : Insts)
348 UsesByBlock[User->getParent()].push_back(User);
350 // Okay, now we can iterate over all the blocks in the function with uses,
351 // processing them. Keep track of which loads are loading a live-in value.
352 // Walk the uses in the use-list order to be determinstic.
353 SmallVector<LoadInst*, 32> LiveInLoads;
354 DenseMap<Value*, Value*> ReplacedLoads;
356 for (Instruction *User : Insts) {
357 BasicBlock *BB = User->getParent();
358 TinyPtrVector<Instruction*> &BlockUses = UsesByBlock[BB];
360 // If this block has already been processed, ignore this repeat use.
361 if (BlockUses.empty()) continue;
363 // Okay, this is the first use in the block. If this block just has a
364 // single user in it, we can rewrite it trivially.
365 if (BlockUses.size() == 1) {
366 // If it is a store, it is a trivial def of the value in the block.
367 if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
369 SSA.AddAvailableValue(BB, SI->getOperand(0));
371 // Otherwise it is a load, queue it to rewrite as a live-in load.
372 LiveInLoads.push_back(cast<LoadInst>(User));
377 // Otherwise, check to see if this block is all loads.
378 bool HasStore = false;
379 for (Instruction *I : BlockUses) {
380 if (isa<StoreInst>(I)) {
386 // If so, we can queue them all as live in loads. We don't have an
387 // efficient way to tell which on is first in the block and don't want to
388 // scan large blocks, so just add all loads as live ins.
390 for (Instruction *I : BlockUses)
391 LiveInLoads.push_back(cast<LoadInst>(I));
396 // Otherwise, we have mixed loads and stores (or just a bunch of stores).
397 // Since SSAUpdater is purely for cross-block values, we need to determine
398 // the order of these instructions in the block. If the first use in the
399 // block is a load, then it uses the live in value. The last store defines
400 // the live out value. We handle this by doing a linear scan of the block.
401 Value *StoredValue = nullptr;
402 for (Instruction &I : *BB) {
403 if (LoadInst *L = dyn_cast<LoadInst>(&I)) {
404 // If this is a load from an unrelated pointer, ignore it.
405 if (!isInstInList(L, Insts)) continue;
407 // If we haven't seen a store yet, this is a live in use, otherwise
408 // use the stored value.
410 replaceLoadWithValue(L, StoredValue);
411 L->replaceAllUsesWith(StoredValue);
412 ReplacedLoads[L] = StoredValue;
414 LiveInLoads.push_back(L);
419 if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
420 // If this is a store to an unrelated pointer, ignore it.
421 if (!isInstInList(SI, Insts)) continue;
424 // Remember that this is the active value in the block.
425 StoredValue = SI->getOperand(0);
429 // The last stored value that happened is the live-out for the block.
430 assert(StoredValue && "Already checked that there is a store in block");
431 SSA.AddAvailableValue(BB, StoredValue);
435 // Okay, now we rewrite all loads that use live-in values in the loop,
436 // inserting PHI nodes as necessary.
437 for (LoadInst *ALoad : LiveInLoads) {
438 Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());
439 replaceLoadWithValue(ALoad, NewVal);
441 // Avoid assertions in unreachable code.
442 if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType());
443 ALoad->replaceAllUsesWith(NewVal);
444 ReplacedLoads[ALoad] = NewVal;
447 // Allow the client to do stuff before we start nuking things.
448 doExtraRewritesBeforeFinalDeletion();
450 // Now that everything is rewritten, delete the old instructions from the
451 // function. They should all be dead now.
452 for (Instruction *User : Insts) {
453 // If this is a load that still has uses, then the load must have been added
454 // as a live value in the SSAUpdate data structure for a block (e.g. because
455 // the loaded value was stored later). In this case, we need to recursively
456 // propagate the updates until we get to the real value.
457 if (!User->use_empty()) {
458 Value *NewVal = ReplacedLoads[User];
459 assert(NewVal && "not a replaced load?");
461 // Propagate down to the ultimate replacee. The intermediately loads
462 // could theoretically already have been deleted, so we don't want to
463 // dereference the Value*'s.
464 DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);
465 while (RLI != ReplacedLoads.end()) {
466 NewVal = RLI->second;
467 RLI = ReplacedLoads.find(NewVal);
470 replaceLoadWithValue(cast<LoadInst>(User), NewVal);
471 User->replaceAllUsesWith(NewVal);
474 instructionDeleted(User);
475 User->eraseFromParent();
480 LoadAndStorePromoter::isInstInList(Instruction *I,
481 const SmallVectorImpl<Instruction*> &Insts)
483 return std::find(Insts.begin(), Insts.end(), I) != Insts.end();