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
13#include "llvm/Transforms/Utils/SSAUpdater.h"
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/TinyPtrVector.h"
18#include "llvm/Analysis/InstructionSimplify.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"
25#include "llvm/IR/Instructions.h"
26#include "llvm/IR/Module.h"
27#include "llvm/IR/Use.h"
28#include "llvm/IR/Value.h"
29#include "llvm/Support/Casting.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Support/raw_ostream.h"
32#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
33#include <cassert>
34#include <utility>
35
36using namespace llvm;
37
38#define DEBUG_TYPE "ssaupdater"
39
40using AvailableValsTy = DenseMap<BasicBlock *, Value *>;
41
42static AvailableValsTy &getAvailableVals(void *AV) {
43 return *static_cast<AvailableValsTy*>(AV);
44}
45
46SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode *> *NewPHI)
47 : InsertedPHIs(NewPHI) {}
48
49SSAUpdater::~SSAUpdater() {
50 delete static_cast<AvailableValsTy*>(AV);
51}
52
53void SSAUpdater::Initialize(Type *Ty, StringRef Name) {
54 if (!AV)
55 AV = new AvailableValsTy();
56 else
57 getAvailableVals(AV).clear();
58 ProtoType = Ty;
59 ProtoName = std::string(Name);
60}
61
62bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
63 return getAvailableVals(AV).count(Val: BB);
64}
65
66Value *SSAUpdater::FindValueForBlock(BasicBlock *BB) const {
67 return getAvailableVals(AV).lookup(Val: BB);
68}
69
70void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
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
77static bool IsEquivalentPHI(PHINode *PHI,
78 SmallDenseMap<BasicBlock *, Value *, 8> &ValueMapping) {
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
93Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
94 Value *Res = GetValueAtEndOfBlockInternal(BB);
95 return Res;
96}
97
98Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
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.
106 SmallVector<std::pair<BasicBlock *, Value *>, 8> PredValues;
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>(Val: BB->begin())) {
113 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
114 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
115 Value *PredVal = GetValueAtEndOfBlock(BB: PredBB);
116 PredValues.push_back(Elt: std::make_pair(x&: PredBB, y&: 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(BB: PredBB);
128 PredValues.push_back(Elt: std::make_pair(x&: PredBB, y&: 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 poison.
140 if (PredValues.empty())
141 return PoisonValue::get(T: 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>(Val: BB->begin())) {
150 SmallDenseMap<BasicBlock *, Value *, 8> ValueMapping(PredValues.begin(),
151 PredValues.end());
152 for (PHINode &SomePHI : BB->phis()) {
153 if (IsEquivalentPHI(PHI: &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(Ty: ProtoType, NumReservedValues: PredValues.size(), NameStr: ProtoName);
161 InsertedPHI->insertBefore(InsertPos: BB->begin());
162
163 // Fill in all the predecessors of the PHI.
164 for (const auto &PredValue : PredValues)
165 InsertedPHI->addIncoming(V: PredValue.second, BB: 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(I: InsertedPHI, Q: BB->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(Elt: InsertedPHI);
183
184 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
185 return InsertedPHI;
186}
187
188void SSAUpdater::RewriteUse(Use &U) {
189 Instruction *User = cast<Instruction>(Val: U.getUser());
190
191 Value *V;
192 if (PHINode *UserPN = dyn_cast<PHINode>(Val: User))
193 V = GetValueAtEndOfBlock(BB: UserPN->getIncomingBlock(U));
194 else
195 V = GetValueInMiddleOfBlock(BB: User->getParent());
196
197 U.set(V);
198}
199
200void SSAUpdater::UpdateDebugValues(Instruction *I) {
201 SmallVector<DbgValueInst *, 4> DbgValues;
202 SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;
203 llvm::findDbgValues(DbgValues, V: I, DbgVariableRecords: &DbgVariableRecords);
204 for (auto &DbgValue : DbgValues) {
205 if (DbgValue->getParent() == I->getParent())
206 continue;
207 UpdateDebugValue(I, DbgValue);
208 }
209 for (auto &DVR : DbgVariableRecords) {
210 if (DVR->getParent() == I->getParent())
211 continue;
212 UpdateDebugValue(I, DbgValue: DVR);
213 }
214}
215
216void SSAUpdater::UpdateDebugValues(Instruction *I,
217 SmallVectorImpl<DbgValueInst *> &DbgValues) {
218 for (auto &DbgValue : DbgValues) {
219 UpdateDebugValue(I, DbgValue);
220 }
221}
222
223void SSAUpdater::UpdateDebugValues(
224 Instruction *I, SmallVectorImpl<DbgVariableRecord *> &DbgVariableRecords) {
225 for (auto &DVR : DbgVariableRecords) {
226 UpdateDebugValue(I, DbgValue: DVR);
227 }
228}
229
230void SSAUpdater::UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue) {
231 BasicBlock *UserBB = DbgValue->getParent();
232 if (HasValueForBlock(BB: UserBB)) {
233 Value *NewVal = GetValueAtEndOfBlock(BB: UserBB);
234 DbgValue->replaceVariableLocationOp(OldValue: I, NewValue: NewVal);
235 } else
236 DbgValue->setKillLocation();
237}
238
239void SSAUpdater::UpdateDebugValue(Instruction *I, DbgVariableRecord *DVR) {
240 BasicBlock *UserBB = DVR->getParent();
241 if (HasValueForBlock(BB: UserBB)) {
242 Value *NewVal = GetValueAtEndOfBlock(BB: UserBB);
243 DVR->replaceVariableLocationOp(OldValue: I, NewValue: NewVal);
244 } else
245 DVR->setKillLocation();
246}
247
248void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
249 Instruction *User = cast<Instruction>(Val: U.getUser());
250
251 Value *V;
252 if (PHINode *UserPN = dyn_cast<PHINode>(Val: User))
253 V = GetValueAtEndOfBlock(BB: UserPN->getIncomingBlock(U));
254 else
255 V = GetValueAtEndOfBlock(BB: User->getParent());
256
257 U.set(V);
258}
259
260namespace llvm {
261
262template<>
263class SSAUpdaterTraits<SSAUpdater> {
264public:
265 using BlkT = BasicBlock;
266 using ValT = Value *;
267 using PhiT = PHINode;
268 using BlkSucc_iterator = succ_iterator;
269
270 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }
271 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }
272
273 class PHI_iterator {
274 private:
275 PHINode *PHI;
276 unsigned idx;
277
278 public:
279 explicit PHI_iterator(PHINode *P) // begin iterator
280 : PHI(P), idx(0) {}
281 PHI_iterator(PHINode *P, bool) // end iterator
282 : PHI(P), idx(PHI->getNumIncomingValues()) {}
283
284 PHI_iterator &operator++() { ++idx; return *this; }
285 bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
286 bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
287
288 Value *getIncomingValue() { return PHI->getIncomingValue(i: idx); }
289 BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(i: idx); }
290 };
291
292 static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
293 static PHI_iterator PHI_end(PhiT *PHI) {
294 return PHI_iterator(PHI, true);
295 }
296
297 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
298 /// vector, set Info->NumPreds, and allocate space in Info->Preds.
299 static void FindPredecessorBlocks(BasicBlock *BB,
300 SmallVectorImpl<BasicBlock *> *Preds) {
301 // We can get our predecessor info by walking the pred_iterator list,
302 // but it is relatively slow. If we already have PHI nodes in this
303 // block, walk one of them to get the predecessor list instead.
304 if (PHINode *SomePhi = dyn_cast<PHINode>(Val: BB->begin()))
305 append_range(C&: *Preds, R: SomePhi->blocks());
306 else
307 append_range(C&: *Preds, R: predecessors(BB));
308 }
309
310 /// GetPoisonVal - Get a poison value of the same type as the value
311 /// being handled.
312 static Value *GetPoisonVal(BasicBlock *BB, SSAUpdater *Updater) {
313 return PoisonValue::get(T: Updater->ProtoType);
314 }
315
316 /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
317 /// Reserve space for the operands but do not fill them in yet.
318 static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
319 SSAUpdater *Updater) {
320 PHINode *PHI =
321 PHINode::Create(Ty: Updater->ProtoType, NumReservedValues: NumPreds, NameStr: Updater->ProtoName);
322 PHI->insertBefore(InsertPos: BB->begin());
323 return PHI;
324 }
325
326 /// AddPHIOperand - Add the specified value as an operand of the PHI for
327 /// the specified predecessor block.
328 static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
329 PHI->addIncoming(V: Val, BB: Pred);
330 }
331
332 /// ValueIsPHI - Check if a value is a PHI.
333 static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
334 return dyn_cast<PHINode>(Val);
335 }
336
337 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
338 /// operands, i.e., it was just added.
339 static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
340 PHINode *PHI = ValueIsPHI(Val, Updater);
341 if (PHI && PHI->getNumIncomingValues() == 0)
342 return PHI;
343 return nullptr;
344 }
345
346 /// GetPHIValue - For the specified PHI instruction, return the value
347 /// that it defines.
348 static Value *GetPHIValue(PHINode *PHI) {
349 return PHI;
350 }
351};
352
353} // end namespace llvm
354
355/// Check to see if AvailableVals has an entry for the specified BB and if so,
356/// return it. If not, construct SSA form by first calculating the required
357/// placement of PHIs and then inserting new PHIs where needed.
358Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
359 AvailableValsTy &AvailableVals = getAvailableVals(AV);
360 if (Value *V = AvailableVals[BB])
361 return V;
362
363 SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
364 return Impl.GetValue(BB);
365}
366
367//===----------------------------------------------------------------------===//
368// LoadAndStorePromoter Implementation
369//===----------------------------------------------------------------------===//
370
371LoadAndStorePromoter::
372LoadAndStorePromoter(ArrayRef<const Instruction *> Insts,
373 SSAUpdater &S, StringRef BaseName) : SSA(S) {
374 if (Insts.empty()) return;
375
376 const Value *SomeVal;
377 if (const LoadInst *LI = dyn_cast<LoadInst>(Val: Insts[0]))
378 SomeVal = LI;
379 else
380 SomeVal = cast<StoreInst>(Val: Insts[0])->getOperand(i_nocapture: 0);
381
382 if (BaseName.empty())
383 BaseName = SomeVal->getName();
384 SSA.Initialize(Ty: SomeVal->getType(), Name: BaseName);
385}
386
387void LoadAndStorePromoter::run(const SmallVectorImpl<Instruction *> &Insts) {
388 // First step: bucket up uses of the alloca by the block they occur in.
389 // This is important because we have to handle multiple defs/uses in a block
390 // ourselves: SSAUpdater is purely for cross-block references.
391 DenseMap<BasicBlock *, TinyPtrVector<Instruction *>> UsesByBlock;
392
393 for (Instruction *User : Insts)
394 UsesByBlock[User->getParent()].push_back(NewVal: User);
395
396 // Okay, now we can iterate over all the blocks in the function with uses,
397 // processing them. Keep track of which loads are loading a live-in value.
398 // Walk the uses in the use-list order to be determinstic.
399 SmallVector<LoadInst *, 32> LiveInLoads;
400 DenseMap<Value *, Value *> ReplacedLoads;
401
402 for (Instruction *User : Insts) {
403 BasicBlock *BB = User->getParent();
404 TinyPtrVector<Instruction *> &BlockUses = UsesByBlock[BB];
405
406 // If this block has already been processed, ignore this repeat use.
407 if (BlockUses.empty()) continue;
408
409 // Okay, this is the first use in the block. If this block just has a
410 // single user in it, we can rewrite it trivially.
411 if (BlockUses.size() == 1) {
412 // If it is a store, it is a trivial def of the value in the block.
413 if (StoreInst *SI = dyn_cast<StoreInst>(Val: User)) {
414 updateDebugInfo(I: SI);
415 SSA.AddAvailableValue(BB, V: SI->getOperand(i_nocapture: 0));
416 } else
417 // Otherwise it is a load, queue it to rewrite as a live-in load.
418 LiveInLoads.push_back(Elt: cast<LoadInst>(Val: User));
419 BlockUses.clear();
420 continue;
421 }
422
423 // Otherwise, check to see if this block is all loads.
424 bool HasStore = false;
425 for (Instruction *I : BlockUses) {
426 if (isa<StoreInst>(Val: I)) {
427 HasStore = true;
428 break;
429 }
430 }
431
432 // If so, we can queue them all as live in loads. We don't have an
433 // efficient way to tell which on is first in the block and don't want to
434 // scan large blocks, so just add all loads as live ins.
435 if (!HasStore) {
436 for (Instruction *I : BlockUses)
437 LiveInLoads.push_back(Elt: cast<LoadInst>(Val: I));
438 BlockUses.clear();
439 continue;
440 }
441
442 // Otherwise, we have mixed loads and stores (or just a bunch of stores).
443 // Since SSAUpdater is purely for cross-block values, we need to determine
444 // the order of these instructions in the block. If the first use in the
445 // block is a load, then it uses the live in value. The last store defines
446 // the live out value. We handle this by doing a linear scan of the block.
447 Value *StoredValue = nullptr;
448 for (Instruction &I : *BB) {
449 if (LoadInst *L = dyn_cast<LoadInst>(Val: &I)) {
450 // If this is a load from an unrelated pointer, ignore it.
451 if (!isInstInList(I: L, Insts)) continue;
452
453 // If we haven't seen a store yet, this is a live in use, otherwise
454 // use the stored value.
455 if (StoredValue) {
456 replaceLoadWithValue(LI: L, V: StoredValue);
457 L->replaceAllUsesWith(V: StoredValue);
458 ReplacedLoads[L] = StoredValue;
459 } else {
460 LiveInLoads.push_back(Elt: L);
461 }
462 continue;
463 }
464
465 if (StoreInst *SI = dyn_cast<StoreInst>(Val: &I)) {
466 // If this is a store to an unrelated pointer, ignore it.
467 if (!isInstInList(I: SI, Insts)) continue;
468 updateDebugInfo(I: SI);
469
470 // Remember that this is the active value in the block.
471 StoredValue = SI->getOperand(i_nocapture: 0);
472 }
473 }
474
475 // The last stored value that happened is the live-out for the block.
476 assert(StoredValue && "Already checked that there is a store in block");
477 SSA.AddAvailableValue(BB, V: StoredValue);
478 BlockUses.clear();
479 }
480
481 // Okay, now we rewrite all loads that use live-in values in the loop,
482 // inserting PHI nodes as necessary.
483 for (LoadInst *ALoad : LiveInLoads) {
484 Value *NewVal = SSA.GetValueInMiddleOfBlock(BB: ALoad->getParent());
485 replaceLoadWithValue(LI: ALoad, V: NewVal);
486
487 // Avoid assertions in unreachable code.
488 if (NewVal == ALoad) NewVal = PoisonValue::get(T: NewVal->getType());
489 ALoad->replaceAllUsesWith(V: NewVal);
490 ReplacedLoads[ALoad] = NewVal;
491 }
492
493 // Allow the client to do stuff before we start nuking things.
494 doExtraRewritesBeforeFinalDeletion();
495
496 // Now that everything is rewritten, delete the old instructions from the
497 // function. They should all be dead now.
498 for (Instruction *User : Insts) {
499 if (!shouldDelete(I: User))
500 continue;
501
502 // If this is a load that still has uses, then the load must have been added
503 // as a live value in the SSAUpdate data structure for a block (e.g. because
504 // the loaded value was stored later). In this case, we need to recursively
505 // propagate the updates until we get to the real value.
506 if (!User->use_empty()) {
507 Value *NewVal = ReplacedLoads[User];
508 assert(NewVal && "not a replaced load?");
509
510 // Propagate down to the ultimate replacee. The intermediately loads
511 // could theoretically already have been deleted, so we don't want to
512 // dereference the Value*'s.
513 DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(Val: NewVal);
514 while (RLI != ReplacedLoads.end()) {
515 NewVal = RLI->second;
516 RLI = ReplacedLoads.find(Val: NewVal);
517 }
518
519 replaceLoadWithValue(LI: cast<LoadInst>(Val: User), V: NewVal);
520 User->replaceAllUsesWith(V: NewVal);
521 }
522
523 instructionDeleted(I: User);
524 User->eraseFromParent();
525 }
526}
527
528bool
529LoadAndStorePromoter::isInstInList(Instruction *I,
530 const SmallVectorImpl<Instruction *> &Insts)
531 const {
532 return is_contained(Range: Insts, Element: I);
533}
534