1198090Srdivacky//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===// 2198090Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198090Srdivacky// 7198090Srdivacky//===----------------------------------------------------------------------===// 8198090Srdivacky// 9198090Srdivacky// This file implements the SSAUpdater class. 10198090Srdivacky// 11198090Srdivacky//===----------------------------------------------------------------------===// 12198090Srdivacky 13249423Sdim#include "llvm/Transforms/Utils/SSAUpdater.h" 14198090Srdivacky#include "llvm/ADT/DenseMap.h" 15321369Sdim#include "llvm/ADT/STLExtras.h" 16321369Sdim#include "llvm/ADT/SmallVector.h" 17226633Sdim#include "llvm/ADT/TinyPtrVector.h" 18218893Sdim#include "llvm/Analysis/InstructionSimplify.h" 19321369Sdim#include "llvm/IR/BasicBlock.h" 20276479Sdim#include "llvm/IR/CFG.h" 21249423Sdim#include "llvm/IR/Constants.h" 22321369Sdim#include "llvm/IR/DebugLoc.h" 23321369Sdim#include "llvm/IR/Instruction.h" 24249423Sdim#include "llvm/IR/Instructions.h" 25288943Sdim#include "llvm/IR/Module.h" 26321369Sdim#include "llvm/IR/Use.h" 27321369Sdim#include "llvm/IR/Value.h" 28321369Sdim#include "llvm/IR/ValueHandle.h" 29321369Sdim#include "llvm/Support/Casting.h" 30198090Srdivacky#include "llvm/Support/Debug.h" 31198090Srdivacky#include "llvm/Support/raw_ostream.h" 32208599Srdivacky#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" 33321369Sdim#include <cassert> 34321369Sdim#include <utility> 35221345Sdim 36198090Srdivackyusing namespace llvm; 37198090Srdivacky 38276479Sdim#define DEBUG_TYPE "ssaupdater" 39276479Sdim 40327952Sdimusing AvailableValsTy = DenseMap<BasicBlock *, Value *>; 41327952Sdim 42198090Srdivackystatic AvailableValsTy &getAvailableVals(void *AV) { 43198090Srdivacky return *static_cast<AvailableValsTy*>(AV); 44198090Srdivacky} 45198090Srdivacky 46327952SdimSSAUpdater::SSAUpdater(SmallVectorImpl<PHINode *> *NewPHI) 47321369Sdim : InsertedPHIs(NewPHI) {} 48198090Srdivacky 49198090SrdivackySSAUpdater::~SSAUpdater() { 50243830Sdim delete static_cast<AvailableValsTy*>(AV); 51198090Srdivacky} 52198090Srdivacky 53226633Sdimvoid SSAUpdater::Initialize(Type *Ty, StringRef Name) { 54276479Sdim if (!AV) 55198090Srdivacky AV = new AvailableValsTy(); 56198090Srdivacky else 57198090Srdivacky getAvailableVals(AV).clear(); 58212904Sdim ProtoType = Ty; 59212904Sdim ProtoName = Name; 60198090Srdivacky} 61198090Srdivacky 62198090Srdivackybool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 63198090Srdivacky return getAvailableVals(AV).count(BB); 64198090Srdivacky} 65198090Srdivacky 66341825SdimValue *SSAUpdater::FindValueForBlock(BasicBlock *BB) const { 67341825Sdim AvailableValsTy::iterator AVI = getAvailableVals(AV).find(BB); 68341825Sdim return (AVI != getAvailableVals(AV).end()) ? AVI->second : nullptr; 69341825Sdim} 70341825Sdim 71198090Srdivackyvoid SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 72276479Sdim assert(ProtoType && "Need to initialize SSAUpdater"); 73212904Sdim assert(ProtoType == V->getType() && 74198090Srdivacky "All rewritten values must have the same type"); 75198090Srdivacky getAvailableVals(AV)[BB] = V; 76198090Srdivacky} 77198090Srdivacky 78207618Srdivackystatic bool IsEquivalentPHI(PHINode *PHI, 79327952Sdim SmallDenseMap<BasicBlock *, Value *, 8> &ValueMapping) { 80203954Srdivacky unsigned PHINumValues = PHI->getNumIncomingValues(); 81203954Srdivacky if (PHINumValues != ValueMapping.size()) 82203954Srdivacky return false; 83203954Srdivacky 84203954Srdivacky // Scan the phi to see if it matches. 85203954Srdivacky for (unsigned i = 0, e = PHINumValues; i != e; ++i) 86203954Srdivacky if (ValueMapping[PHI->getIncomingBlock(i)] != 87203954Srdivacky PHI->getIncomingValue(i)) { 88203954Srdivacky return false; 89203954Srdivacky } 90203954Srdivacky 91203954Srdivacky return true; 92203954Srdivacky} 93203954Srdivacky 94198090SrdivackyValue *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 95198090Srdivacky Value *Res = GetValueAtEndOfBlockInternal(BB); 96198090Srdivacky return Res; 97198090Srdivacky} 98198090Srdivacky 99198090SrdivackyValue *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 100198090Srdivacky // If there is no definition of the renamed variable in this block, just use 101198090Srdivacky // GetValueAtEndOfBlock to do our work. 102207618Srdivacky if (!HasValueForBlock(BB)) 103198090Srdivacky return GetValueAtEndOfBlock(BB); 104198396Srdivacky 105198090Srdivacky // Otherwise, we have the hard case. Get the live-in values for each 106198090Srdivacky // predecessor. 107327952Sdim SmallVector<std::pair<BasicBlock *, Value *>, 8> PredValues; 108276479Sdim Value *SingularValue = nullptr; 109198396Srdivacky 110198090Srdivacky // We can get our predecessor info by walking the pred_iterator list, but it 111198090Srdivacky // is relatively slow. If we already have PHI nodes in this block, walk one 112198090Srdivacky // of them to get the predecessor list instead. 113198090Srdivacky if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 114198090Srdivacky for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 115198090Srdivacky BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 116198090Srdivacky Value *PredVal = GetValueAtEndOfBlock(PredBB); 117198090Srdivacky PredValues.push_back(std::make_pair(PredBB, PredVal)); 118198396Srdivacky 119198090Srdivacky // Compute SingularValue. 120198090Srdivacky if (i == 0) 121198090Srdivacky SingularValue = PredVal; 122198090Srdivacky else if (PredVal != SingularValue) 123276479Sdim SingularValue = nullptr; 124198090Srdivacky } 125198090Srdivacky } else { 126198090Srdivacky bool isFirstPred = true; 127198090Srdivacky for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 128198090Srdivacky BasicBlock *PredBB = *PI; 129198090Srdivacky Value *PredVal = GetValueAtEndOfBlock(PredBB); 130198090Srdivacky PredValues.push_back(std::make_pair(PredBB, PredVal)); 131198396Srdivacky 132198090Srdivacky // Compute SingularValue. 133198090Srdivacky if (isFirstPred) { 134198090Srdivacky SingularValue = PredVal; 135198090Srdivacky isFirstPred = false; 136198090Srdivacky } else if (PredVal != SingularValue) 137276479Sdim SingularValue = nullptr; 138198090Srdivacky } 139198090Srdivacky } 140198396Srdivacky 141198090Srdivacky // If there are no predecessors, just return undef. 142198090Srdivacky if (PredValues.empty()) 143212904Sdim return UndefValue::get(ProtoType); 144198396Srdivacky 145198090Srdivacky // Otherwise, if all the merged values are the same, just use it. 146276479Sdim if (SingularValue) 147198090Srdivacky return SingularValue; 148198396Srdivacky 149207618Srdivacky // Otherwise, we do need a PHI: check to see if we already have one available 150207618Srdivacky // in this block that produces the right value. 151207618Srdivacky if (isa<PHINode>(BB->begin())) { 152327952Sdim SmallDenseMap<BasicBlock *, Value *, 8> ValueMapping(PredValues.begin(), 153327952Sdim PredValues.end()); 154327952Sdim for (PHINode &SomePHI : BB->phis()) { 155327952Sdim if (IsEquivalentPHI(&SomePHI, ValueMapping)) 156327952Sdim return &SomePHI; 157207618Srdivacky } 158207618Srdivacky } 159203954Srdivacky 160201360Srdivacky // Ok, we have no way out, insert a new one now. 161221345Sdim PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(), 162221345Sdim ProtoName, &BB->front()); 163198396Srdivacky 164198090Srdivacky // Fill in all the predecessors of the PHI. 165288943Sdim for (const auto &PredValue : PredValues) 166288943Sdim InsertedPHI->addIncoming(PredValue.second, PredValue.first); 167198396Srdivacky 168198090Srdivacky // See if the PHI node can be merged to a single value. This can happen in 169198090Srdivacky // loop cases when we get a PHI of itself and one other value. 170288943Sdim if (Value *V = 171288943Sdim SimplifyInstruction(InsertedPHI, BB->getModule()->getDataLayout())) { 172198090Srdivacky InsertedPHI->eraseFromParent(); 173218893Sdim return V; 174198090Srdivacky } 175198090Srdivacky 176239462Sdim // Set the DebugLoc of the inserted PHI, if available. 177239462Sdim DebugLoc DL; 178239462Sdim if (const Instruction *I = BB->getFirstNonPHI()) 179239462Sdim DL = I->getDebugLoc(); 180239462Sdim InsertedPHI->setDebugLoc(DL); 181221345Sdim 182198090Srdivacky // If the client wants to know about all new instructions, tell it. 183198090Srdivacky if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 184198396Srdivacky 185341825Sdim LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 186198090Srdivacky return InsertedPHI; 187198090Srdivacky} 188198090Srdivacky 189198090Srdivackyvoid SSAUpdater::RewriteUse(Use &U) { 190198090Srdivacky Instruction *User = cast<Instruction>(U.getUser()); 191207618Srdivacky 192198396Srdivacky Value *V; 193198090Srdivacky if (PHINode *UserPN = dyn_cast<PHINode>(User)) 194198396Srdivacky V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 195198396Srdivacky else 196198396Srdivacky V = GetValueInMiddleOfBlock(User->getParent()); 197198396Srdivacky 198239462Sdim // Notify that users of the existing value that it is being replaced. 199239462Sdim Value *OldVal = U.get(); 200239462Sdim if (OldVal != V && OldVal->hasValueHandle()) 201239462Sdim ValueHandleBase::ValueIsRAUWd(OldVal, V); 202239462Sdim 203198396Srdivacky U.set(V); 204198090Srdivacky} 205198090Srdivacky 206212904Sdimvoid SSAUpdater::RewriteUseAfterInsertions(Use &U) { 207212904Sdim Instruction *User = cast<Instruction>(U.getUser()); 208341825Sdim 209212904Sdim Value *V; 210212904Sdim if (PHINode *UserPN = dyn_cast<PHINode>(User)) 211212904Sdim V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 212212904Sdim else 213212904Sdim V = GetValueAtEndOfBlock(User->getParent()); 214341825Sdim 215212904Sdim U.set(V); 216212904Sdim} 217212904Sdim 218208599Srdivackynamespace llvm { 219321369Sdim 220208599Srdivackytemplate<> 221208599Srdivackyclass SSAUpdaterTraits<SSAUpdater> { 222208599Srdivackypublic: 223327952Sdim using BlkT = BasicBlock; 224327952Sdim using ValT = Value *; 225327952Sdim using PhiT = PHINode; 226327952Sdim using BlkSucc_iterator = succ_iterator; 227198396Srdivacky 228208599Srdivacky static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); } 229208599Srdivacky static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); } 230198396Srdivacky 231239462Sdim class PHI_iterator { 232239462Sdim private: 233239462Sdim PHINode *PHI; 234239462Sdim unsigned idx; 235239462Sdim 236239462Sdim public: 237239462Sdim explicit PHI_iterator(PHINode *P) // begin iterator 238239462Sdim : PHI(P), idx(0) {} 239239462Sdim PHI_iterator(PHINode *P, bool) // end iterator 240239462Sdim : PHI(P), idx(PHI->getNumIncomingValues()) {} 241239462Sdim 242341825Sdim PHI_iterator &operator++() { ++idx; return *this; } 243239462Sdim bool operator==(const PHI_iterator& x) const { return idx == x.idx; } 244239462Sdim bool operator!=(const PHI_iterator& x) const { return !operator==(x); } 245321369Sdim 246239462Sdim Value *getIncomingValue() { return PHI->getIncomingValue(idx); } 247239462Sdim BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); } 248239462Sdim }; 249239462Sdim 250239462Sdim static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } 251239462Sdim static PHI_iterator PHI_end(PhiT *PHI) { 252208599Srdivacky return PHI_iterator(PHI, true); 253207618Srdivacky } 254198396Srdivacky 255208599Srdivacky /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds 256208599Srdivacky /// vector, set Info->NumPreds, and allocate space in Info->Preds. 257208599Srdivacky static void FindPredecessorBlocks(BasicBlock *BB, 258327952Sdim SmallVectorImpl<BasicBlock *> *Preds) { 259208599Srdivacky // We can get our predecessor info by walking the pred_iterator list, 260208599Srdivacky // but it is relatively slow. If we already have PHI nodes in this 261208599Srdivacky // block, walk one of them to get the predecessor list instead. 262208599Srdivacky if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 263288943Sdim Preds->append(SomePhi->block_begin(), SomePhi->block_end()); 264208599Srdivacky } else { 265208599Srdivacky for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 266208599Srdivacky Preds->push_back(*PI); 267198090Srdivacky } 268198090Srdivacky } 269198396Srdivacky 270208599Srdivacky /// GetUndefVal - Get an undefined value of the same type as the value 271208599Srdivacky /// being handled. 272208599Srdivacky static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) { 273212904Sdim return UndefValue::get(Updater->ProtoType); 274207618Srdivacky } 275198396Srdivacky 276208599Srdivacky /// CreateEmptyPHI - Create a new PHI instruction in the specified block. 277208599Srdivacky /// Reserve space for the operands but do not fill them in yet. 278208599Srdivacky static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, 279208599Srdivacky SSAUpdater *Updater) { 280221345Sdim PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds, 281221345Sdim Updater->ProtoName, &BB->front()); 282208599Srdivacky return PHI; 283198090Srdivacky } 284198396Srdivacky 285208599Srdivacky /// AddPHIOperand - Add the specified value as an operand of the PHI for 286208599Srdivacky /// the specified predecessor block. 287208599Srdivacky static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) { 288208599Srdivacky PHI->addIncoming(Val, Pred); 289207618Srdivacky } 290198396Srdivacky 291208599Srdivacky /// InstrIsPHI - Check if an instruction is a PHI. 292208599Srdivacky /// 293208599Srdivacky static PHINode *InstrIsPHI(Instruction *I) { 294208599Srdivacky return dyn_cast<PHINode>(I); 295207618Srdivacky } 296207618Srdivacky 297208599Srdivacky /// ValueIsPHI - Check if a value is a PHI. 298208599Srdivacky static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) { 299208599Srdivacky return dyn_cast<PHINode>(Val); 300207618Srdivacky } 301207618Srdivacky 302208599Srdivacky /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source 303208599Srdivacky /// operands, i.e., it was just added. 304208599Srdivacky static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) { 305208599Srdivacky PHINode *PHI = ValueIsPHI(Val, Updater); 306208599Srdivacky if (PHI && PHI->getNumIncomingValues() == 0) 307208599Srdivacky return PHI; 308276479Sdim return nullptr; 309198090Srdivacky } 310198396Srdivacky 311208599Srdivacky /// GetPHIValue - For the specified PHI instruction, return the value 312208599Srdivacky /// that it defines. 313208599Srdivacky static Value *GetPHIValue(PHINode *PHI) { 314208599Srdivacky return PHI; 315207618Srdivacky } 316208599Srdivacky}; 317207618Srdivacky 318321369Sdim} // end namespace llvm 319207618Srdivacky 320261991Sdim/// Check to see if AvailableVals has an entry for the specified BB and if so, 321261991Sdim/// return it. If not, construct SSA form by first calculating the required 322261991Sdim/// placement of PHIs and then inserting new PHIs where needed. 323208599SrdivackyValue *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 324207618Srdivacky AvailableValsTy &AvailableVals = getAvailableVals(AV); 325208599Srdivacky if (Value *V = AvailableVals[BB]) 326208599Srdivacky return V; 327207618Srdivacky 328208599Srdivacky SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); 329208599Srdivacky return Impl.GetValue(BB); 330207618Srdivacky} 331218893Sdim 332218893Sdim//===----------------------------------------------------------------------===// 333218893Sdim// LoadAndStorePromoter Implementation 334218893Sdim//===----------------------------------------------------------------------===// 335218893Sdim 336218893SdimLoadAndStorePromoter:: 337327952SdimLoadAndStorePromoter(ArrayRef<const Instruction *> Insts, 338224145Sdim SSAUpdater &S, StringRef BaseName) : SSA(S) { 339218893Sdim if (Insts.empty()) return; 340341825Sdim 341288943Sdim const Value *SomeVal; 342288943Sdim if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0])) 343218893Sdim SomeVal = LI; 344218893Sdim else 345218893Sdim SomeVal = cast<StoreInst>(Insts[0])->getOperand(0); 346218893Sdim 347218893Sdim if (BaseName.empty()) 348218893Sdim BaseName = SomeVal->getName(); 349218893Sdim SSA.Initialize(SomeVal->getType(), BaseName); 350218893Sdim} 351218893Sdim 352353358Sdimvoid LoadAndStorePromoter::run(const SmallVectorImpl<Instruction *> &Insts) { 353218893Sdim // First step: bucket up uses of the alloca by the block they occur in. 354218893Sdim // This is important because we have to handle multiple defs/uses in a block 355218893Sdim // ourselves: SSAUpdater is purely for cross-block references. 356327952Sdim DenseMap<BasicBlock *, TinyPtrVector<Instruction *>> UsesByBlock; 357288943Sdim 358288943Sdim for (Instruction *User : Insts) 359218893Sdim UsesByBlock[User->getParent()].push_back(User); 360341825Sdim 361218893Sdim // Okay, now we can iterate over all the blocks in the function with uses, 362218893Sdim // processing them. Keep track of which loads are loading a live-in value. 363218893Sdim // Walk the uses in the use-list order to be determinstic. 364327952Sdim SmallVector<LoadInst *, 32> LiveInLoads; 365327952Sdim DenseMap<Value *, Value *> ReplacedLoads; 366288943Sdim 367288943Sdim for (Instruction *User : Insts) { 368218893Sdim BasicBlock *BB = User->getParent(); 369327952Sdim TinyPtrVector<Instruction *> &BlockUses = UsesByBlock[BB]; 370341825Sdim 371218893Sdim // If this block has already been processed, ignore this repeat use. 372218893Sdim if (BlockUses.empty()) continue; 373341825Sdim 374218893Sdim // Okay, this is the first use in the block. If this block just has a 375218893Sdim // single user in it, we can rewrite it trivially. 376218893Sdim if (BlockUses.size() == 1) { 377218893Sdim // If it is a store, it is a trivial def of the value in the block. 378223017Sdim if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 379224145Sdim updateDebugInfo(SI); 380218893Sdim SSA.AddAvailableValue(BB, SI->getOperand(0)); 381341825Sdim } else 382218893Sdim // Otherwise it is a load, queue it to rewrite as a live-in load. 383218893Sdim LiveInLoads.push_back(cast<LoadInst>(User)); 384218893Sdim BlockUses.clear(); 385218893Sdim continue; 386218893Sdim } 387341825Sdim 388218893Sdim // Otherwise, check to see if this block is all loads. 389218893Sdim bool HasStore = false; 390288943Sdim for (Instruction *I : BlockUses) { 391288943Sdim if (isa<StoreInst>(I)) { 392218893Sdim HasStore = true; 393218893Sdim break; 394218893Sdim } 395218893Sdim } 396341825Sdim 397218893Sdim // If so, we can queue them all as live in loads. We don't have an 398218893Sdim // efficient way to tell which on is first in the block and don't want to 399218893Sdim // scan large blocks, so just add all loads as live ins. 400218893Sdim if (!HasStore) { 401288943Sdim for (Instruction *I : BlockUses) 402288943Sdim LiveInLoads.push_back(cast<LoadInst>(I)); 403218893Sdim BlockUses.clear(); 404218893Sdim continue; 405218893Sdim } 406341825Sdim 407218893Sdim // Otherwise, we have mixed loads and stores (or just a bunch of stores). 408218893Sdim // Since SSAUpdater is purely for cross-block values, we need to determine 409218893Sdim // the order of these instructions in the block. If the first use in the 410218893Sdim // block is a load, then it uses the live in value. The last store defines 411218893Sdim // the live out value. We handle this by doing a linear scan of the block. 412276479Sdim Value *StoredValue = nullptr; 413288943Sdim for (Instruction &I : *BB) { 414288943Sdim if (LoadInst *L = dyn_cast<LoadInst>(&I)) { 415218893Sdim // If this is a load from an unrelated pointer, ignore it. 416218893Sdim if (!isInstInList(L, Insts)) continue; 417341825Sdim 418218893Sdim // If we haven't seen a store yet, this is a live in use, otherwise 419218893Sdim // use the stored value. 420218893Sdim if (StoredValue) { 421218893Sdim replaceLoadWithValue(L, StoredValue); 422218893Sdim L->replaceAllUsesWith(StoredValue); 423218893Sdim ReplacedLoads[L] = StoredValue; 424218893Sdim } else { 425218893Sdim LiveInLoads.push_back(L); 426218893Sdim } 427218893Sdim continue; 428218893Sdim } 429288943Sdim 430288943Sdim if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { 431218893Sdim // If this is a store to an unrelated pointer, ignore it. 432223017Sdim if (!isInstInList(SI, Insts)) continue; 433224145Sdim updateDebugInfo(SI); 434223017Sdim 435218893Sdim // Remember that this is the active value in the block. 436223017Sdim StoredValue = SI->getOperand(0); 437218893Sdim } 438218893Sdim } 439341825Sdim 440218893Sdim // The last stored value that happened is the live-out for the block. 441218893Sdim assert(StoredValue && "Already checked that there is a store in block"); 442218893Sdim SSA.AddAvailableValue(BB, StoredValue); 443218893Sdim BlockUses.clear(); 444218893Sdim } 445341825Sdim 446218893Sdim // Okay, now we rewrite all loads that use live-in values in the loop, 447218893Sdim // inserting PHI nodes as necessary. 448288943Sdim for (LoadInst *ALoad : LiveInLoads) { 449218893Sdim Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent()); 450218893Sdim replaceLoadWithValue(ALoad, NewVal); 451218893Sdim 452218893Sdim // Avoid assertions in unreachable code. 453218893Sdim if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType()); 454218893Sdim ALoad->replaceAllUsesWith(NewVal); 455218893Sdim ReplacedLoads[ALoad] = NewVal; 456218893Sdim } 457341825Sdim 458218893Sdim // Allow the client to do stuff before we start nuking things. 459218893Sdim doExtraRewritesBeforeFinalDeletion(); 460341825Sdim 461218893Sdim // Now that everything is rewritten, delete the old instructions from the 462218893Sdim // function. They should all be dead now. 463288943Sdim for (Instruction *User : Insts) { 464218893Sdim // If this is a load that still has uses, then the load must have been added 465218893Sdim // as a live value in the SSAUpdate data structure for a block (e.g. because 466218893Sdim // the loaded value was stored later). In this case, we need to recursively 467218893Sdim // propagate the updates until we get to the real value. 468218893Sdim if (!User->use_empty()) { 469218893Sdim Value *NewVal = ReplacedLoads[User]; 470218893Sdim assert(NewVal && "not a replaced load?"); 471341825Sdim 472218893Sdim // Propagate down to the ultimate replacee. The intermediately loads 473218893Sdim // could theoretically already have been deleted, so we don't want to 474218893Sdim // dereference the Value*'s. 475218893Sdim DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal); 476218893Sdim while (RLI != ReplacedLoads.end()) { 477218893Sdim NewVal = RLI->second; 478218893Sdim RLI = ReplacedLoads.find(NewVal); 479218893Sdim } 480341825Sdim 481218893Sdim replaceLoadWithValue(cast<LoadInst>(User), NewVal); 482218893Sdim User->replaceAllUsesWith(NewVal); 483218893Sdim } 484341825Sdim 485218893Sdim instructionDeleted(User); 486218893Sdim User->eraseFromParent(); 487218893Sdim } 488218893Sdim} 489234353Sdim 490234353Sdimbool 491234353SdimLoadAndStorePromoter::isInstInList(Instruction *I, 492327952Sdim const SmallVectorImpl<Instruction *> &Insts) 493234353Sdim const { 494314564Sdim return is_contained(Insts, I); 495234353Sdim} 496