516 lines · cpp
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-exception6//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/Use.h"27#include "llvm/IR/Value.h"28#include "llvm/Support/Casting.h"29#include "llvm/Support/Debug.h"30#include "llvm/Support/raw_ostream.h"31#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"32#include <cassert>33#include <utility>34 35using namespace llvm;36 37#define DEBUG_TYPE "ssaupdater"38 39using AvailableValsTy = DenseMap<BasicBlock *, Value *>;40 41static AvailableValsTy &getAvailableVals(void *AV) {42 return *static_cast<AvailableValsTy*>(AV);43}44 45SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode *> *NewPHI)46 : InsertedPHIs(NewPHI) {}47 48SSAUpdater::~SSAUpdater() {49 delete static_cast<AvailableValsTy*>(AV);50}51 52void SSAUpdater::Initialize(Type *Ty, StringRef Name) {53 if (!AV)54 AV = new AvailableValsTy();55 else56 getAvailableVals(AV).clear();57 ProtoType = Ty;58 ProtoName = std::string(Name);59}60 61bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {62 return getAvailableVals(AV).count(BB);63}64 65Value *SSAUpdater::FindValueForBlock(BasicBlock *BB) const {66 return getAvailableVals(AV).lookup(BB);67}68 69void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {70 assert(ProtoType && "Need to initialize SSAUpdater");71 assert(ProtoType == V->getType() &&72 "All rewritten values must have the same type");73 getAvailableVals(AV)[BB] = V;74}75 76static bool IsEquivalentPHI(PHINode *PHI,77 SmallDenseMap<BasicBlock *, Value *, 8> &ValueMapping) {78 unsigned PHINumValues = PHI->getNumIncomingValues();79 if (PHINumValues != ValueMapping.size())80 return false;81 82 // Scan the phi to see if it matches.83 for (unsigned i = 0, e = PHINumValues; i != e; ++i)84 if (ValueMapping[PHI->getIncomingBlock(i)] !=85 PHI->getIncomingValue(i)) {86 return false;87 }88 89 return true;90}91 92Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {93 Value *Res = GetValueAtEndOfBlockInternal(BB);94 return Res;95}96 97Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {98 // If there is no definition of the renamed variable in this block, just use99 // GetValueAtEndOfBlock to do our work.100 if (!HasValueForBlock(BB))101 return GetValueAtEndOfBlock(BB);102 103 // Otherwise, we have the hard case. Get the live-in values for each104 // predecessor.105 SmallVector<std::pair<BasicBlock *, Value *>, 8> PredValues;106 Value *SingularValue = nullptr;107 108 // We can get our predecessor info by walking the pred_iterator list, but it109 // is relatively slow. If we already have PHI nodes in this block, walk one110 // of them to get the predecessor list instead.111 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {112 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {113 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);114 Value *PredVal = GetValueAtEndOfBlock(PredBB);115 PredValues.push_back(std::make_pair(PredBB, PredVal));116 117 // Compute SingularValue.118 if (i == 0)119 SingularValue = PredVal;120 else if (PredVal != SingularValue)121 SingularValue = nullptr;122 }123 } else {124 bool isFirstPred = true;125 for (BasicBlock *PredBB : predecessors(BB)) {126 Value *PredVal = GetValueAtEndOfBlock(PredBB);127 PredValues.push_back(std::make_pair(PredBB, PredVal));128 129 // Compute SingularValue.130 if (isFirstPred) {131 SingularValue = PredVal;132 isFirstPred = false;133 } else if (PredVal != SingularValue)134 SingularValue = nullptr;135 }136 }137 138 // If there are no predecessors, just return poison.139 if (PredValues.empty())140 return PoisonValue::get(ProtoType);141 142 // Otherwise, if all the merged values are the same, just use it.143 if (SingularValue)144 return SingularValue;145 146 // Otherwise, we do need a PHI: check to see if we already have one available147 // in this block that produces the right value.148 if (isa<PHINode>(BB->begin())) {149 SmallDenseMap<BasicBlock *, Value *, 8> ValueMapping(PredValues.begin(),150 PredValues.end());151 for (PHINode &SomePHI : BB->phis()) {152 if (IsEquivalentPHI(&SomePHI, ValueMapping))153 return &SomePHI;154 }155 }156 157 // Ok, we have no way out, insert a new one now.158 PHINode *InsertedPHI =159 PHINode::Create(ProtoType, PredValues.size(), ProtoName);160 InsertedPHI->insertBefore(BB->begin());161 162 // Fill in all the predecessors of the PHI.163 for (const auto &PredValue : PredValues)164 InsertedPHI->addIncoming(PredValue.second, PredValue.first);165 166 // See if the PHI node can be merged to a single value. This can happen in167 // loop cases when we get a PHI of itself and one other value.168 if (Value *V =169 simplifyInstruction(InsertedPHI, BB->getDataLayout())) {170 InsertedPHI->eraseFromParent();171 return V;172 }173 174 // Set the DebugLoc of the inserted PHI, if available.175 DebugLoc DL;176 if (BasicBlock::iterator It = BB->getFirstNonPHIIt(); It != BB->end())177 DL = It->getDebugLoc();178 InsertedPHI->setDebugLoc(DL);179 180 // If the client wants to know about all new instructions, tell it.181 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);182 183 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");184 return InsertedPHI;185}186 187void SSAUpdater::RewriteUse(Use &U) {188 Instruction *User = cast<Instruction>(U.getUser());189 190 Value *V;191 if (PHINode *UserPN = dyn_cast<PHINode>(User))192 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));193 else194 V = GetValueInMiddleOfBlock(User->getParent());195 196 U.set(V);197}198 199void SSAUpdater::UpdateDebugValues(Instruction *I) {200 SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;201 llvm::findDbgValues(I, DbgVariableRecords);202 for (auto &DVR : DbgVariableRecords) {203 if (DVR->getParent() == I->getParent())204 continue;205 UpdateDebugValue(I, DVR);206 }207}208 209void SSAUpdater::UpdateDebugValues(210 Instruction *I, SmallVectorImpl<DbgVariableRecord *> &DbgVariableRecords) {211 for (auto &DVR : DbgVariableRecords) {212 UpdateDebugValue(I, DVR);213 }214}215 216void SSAUpdater::UpdateDebugValue(Instruction *I, DbgVariableRecord *DVR) {217 BasicBlock *UserBB = DVR->getParent();218 if (HasValueForBlock(UserBB)) {219 Value *NewVal = GetValueAtEndOfBlock(UserBB);220 DVR->replaceVariableLocationOp(I, NewVal);221 } else222 DVR->setKillLocation();223}224 225void SSAUpdater::RewriteUseAfterInsertions(Use &U) {226 Instruction *User = cast<Instruction>(U.getUser());227 228 Value *V;229 if (PHINode *UserPN = dyn_cast<PHINode>(User))230 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));231 else232 V = GetValueAtEndOfBlock(User->getParent());233 234 U.set(V);235}236 237namespace llvm {238 239template<>240class SSAUpdaterTraits<SSAUpdater> {241public:242 using BlkT = BasicBlock;243 using ValT = Value *;244 using PhiT = PHINode;245 using BlkSucc_iterator = succ_iterator;246 247 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }248 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }249 250 class PHI_iterator {251 private:252 PHINode *PHI;253 unsigned idx;254 255 public:256 explicit PHI_iterator(PHINode *P) // begin iterator257 : PHI(P), idx(0) {}258 PHI_iterator(PHINode *P, bool) // end iterator259 : PHI(P), idx(PHI->getNumIncomingValues()) {}260 261 PHI_iterator &operator++() { ++idx; return *this; }262 bool operator==(const PHI_iterator& x) const { return idx == x.idx; }263 bool operator!=(const PHI_iterator& x) const { return !operator==(x); }264 265 Value *getIncomingValue() { return PHI->getIncomingValue(idx); }266 BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }267 };268 269 static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }270 static PHI_iterator PHI_end(PhiT *PHI) {271 return PHI_iterator(PHI, true);272 }273 274 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds275 /// vector, set Info->NumPreds, and allocate space in Info->Preds.276 static void FindPredecessorBlocks(BasicBlock *BB,277 SmallVectorImpl<BasicBlock *> *Preds) {278 // We can get our predecessor info by walking the pred_iterator list,279 // but it is relatively slow. If we already have PHI nodes in this280 // block, walk one of them to get the predecessor list instead.281 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin()))282 append_range(*Preds, SomePhi->blocks());283 else284 append_range(*Preds, predecessors(BB));285 }286 287 /// GetPoisonVal - Get a poison value of the same type as the value288 /// being handled.289 static Value *GetPoisonVal(BasicBlock *BB, SSAUpdater *Updater) {290 return PoisonValue::get(Updater->ProtoType);291 }292 293 /// CreateEmptyPHI - Create a new PHI instruction in the specified block.294 /// Reserve space for the operands but do not fill them in yet.295 static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,296 SSAUpdater *Updater) {297 PHINode *PHI =298 PHINode::Create(Updater->ProtoType, NumPreds, Updater->ProtoName);299 // FIXME: Ordinarily we don't care about or try to assign DebugLocs to PHI300 // nodes, but loop optimizations may try to use a PHI node as a DebugLoc301 // source (e.g. if this is an induction variable), and it's not clear what302 // location we could attach here, so mark this unknown for now.303 PHI->setDebugLoc(DebugLoc::getUnknown());304 PHI->insertBefore(BB->begin());305 return PHI;306 }307 308 /// AddPHIOperand - Add the specified value as an operand of the PHI for309 /// the specified predecessor block.310 static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {311 PHI->addIncoming(Val, Pred);312 }313 314 /// ValueIsPHI - Check if a value is a PHI.315 static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {316 return dyn_cast<PHINode>(Val);317 }318 319 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source320 /// operands, i.e., it was just added.321 static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {322 PHINode *PHI = ValueIsPHI(Val, Updater);323 if (PHI && PHI->getNumIncomingValues() == 0)324 return PHI;325 return nullptr;326 }327 328 /// GetPHIValue - For the specified PHI instruction, return the value329 /// that it defines.330 static Value *GetPHIValue(PHINode *PHI) {331 return PHI;332 }333};334 335} // end namespace llvm336 337/// Check to see if AvailableVals has an entry for the specified BB and if so,338/// return it. If not, construct SSA form by first calculating the required339/// placement of PHIs and then inserting new PHIs where needed.340Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {341 AvailableValsTy &AvailableVals = getAvailableVals(AV);342 if (Value *V = AvailableVals[BB])343 return V;344 345 SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);346 return Impl.GetValue(BB);347}348 349//===----------------------------------------------------------------------===//350// LoadAndStorePromoter Implementation351//===----------------------------------------------------------------------===//352 353LoadAndStorePromoter::354LoadAndStorePromoter(ArrayRef<const Instruction *> Insts,355 SSAUpdater &S, StringRef BaseName) : SSA(S) {356 if (Insts.empty()) return;357 358 const Value *SomeVal;359 if (const LoadInst *LI = dyn_cast<LoadInst>(Insts[0]))360 SomeVal = LI;361 else362 SomeVal = cast<StoreInst>(Insts[0])->getOperand(0);363 364 if (BaseName.empty())365 BaseName = SomeVal->getName();366 SSA.Initialize(SomeVal->getType(), BaseName);367}368 369void LoadAndStorePromoter::run(const SmallVectorImpl<Instruction *> &Insts) {370 // First step: bucket up uses of the alloca by the block they occur in.371 // This is important because we have to handle multiple defs/uses in a block372 // ourselves: SSAUpdater is purely for cross-block references.373 DenseMap<BasicBlock *, TinyPtrVector<Instruction *>> UsesByBlock;374 375 for (Instruction *User : Insts)376 UsesByBlock[User->getParent()].push_back(User);377 378 // Okay, now we can iterate over all the blocks in the function with uses,379 // processing them. Keep track of which loads are loading a live-in value.380 // Walk the uses in the use-list order to be determinstic.381 SmallVector<LoadInst *, 32> LiveInLoads;382 DenseMap<Value *, Value *> ReplacedLoads;383 384 for (Instruction *User : Insts) {385 BasicBlock *BB = User->getParent();386 TinyPtrVector<Instruction *> &BlockUses = UsesByBlock[BB];387 388 // If this block has already been processed, ignore this repeat use.389 if (BlockUses.empty()) continue;390 391 // Okay, this is the first use in the block. If this block just has a392 // single user in it, we can rewrite it trivially.393 if (BlockUses.size() == 1) {394 // If it is a store, it is a trivial def of the value in the block.395 if (StoreInst *SI = dyn_cast<StoreInst>(User)) {396 updateDebugInfo(SI);397 SSA.AddAvailableValue(BB, SI->getOperand(0));398 } else if (auto *AI = dyn_cast<AllocaInst>(User)) {399 // We treat AllocaInst as a store of an getValueToUseForAlloca value.400 SSA.AddAvailableValue(BB, getValueToUseForAlloca(AI));401 } else {402 // Otherwise it is a load, queue it to rewrite as a live-in load.403 LiveInLoads.push_back(cast<LoadInst>(User));404 }405 BlockUses.clear();406 continue;407 }408 409 // Otherwise, check to see if this block is all loads.410 bool HasStore = false;411 for (Instruction *I : BlockUses) {412 if (isa<StoreInst>(I) || isa<AllocaInst>(I)) {413 HasStore = true;414 break;415 }416 }417 418 // If so, we can queue them all as live in loads.419 if (!HasStore) {420 for (Instruction *I : BlockUses)421 LiveInLoads.push_back(cast<LoadInst>(I));422 BlockUses.clear();423 continue;424 }425 426 // Sort all of the interesting instructions in the block so that we don't427 // have to scan a large block just to find a few instructions.428 llvm::sort(429 BlockUses.begin(), BlockUses.end(),430 [](Instruction *A, Instruction *B) { return A->comesBefore(B); });431 432 // Otherwise, we have mixed loads and stores (or just a bunch of stores).433 // Since SSAUpdater is purely for cross-block values, we need to determine434 // the order of these instructions in the block. If the first use in the435 // block is a load, then it uses the live in value. The last store defines436 // the live out value.437 Value *StoredValue = nullptr;438 for (Instruction *I : BlockUses) {439 if (LoadInst *L = dyn_cast<LoadInst>(I)) {440 // If we haven't seen a store yet, this is a live in use, otherwise441 // use the stored value.442 if (StoredValue) {443 replaceLoadWithValue(L, StoredValue);444 L->replaceAllUsesWith(StoredValue);445 ReplacedLoads[L] = StoredValue;446 } else {447 LiveInLoads.push_back(L);448 }449 continue;450 }451 452 if (StoreInst *SI = dyn_cast<StoreInst>(I)) {453 updateDebugInfo(SI);454 455 // Remember that this is the active value in the block.456 StoredValue = SI->getOperand(0);457 } else if (auto *AI = dyn_cast<AllocaInst>(I)) {458 // Check if this an alloca, in which case we treat it as a store of459 // getValueToUseForAlloca.460 StoredValue = getValueToUseForAlloca(AI);461 }462 }463 464 // The last stored value that happened is the live-out for the block.465 assert(StoredValue && "Already checked that there is a store in block");466 SSA.AddAvailableValue(BB, StoredValue);467 BlockUses.clear();468 }469 470 // Okay, now we rewrite all loads that use live-in values in the loop,471 // inserting PHI nodes as necessary.472 for (LoadInst *ALoad : LiveInLoads) {473 Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());474 replaceLoadWithValue(ALoad, NewVal);475 476 // Avoid assertions in unreachable code.477 if (NewVal == ALoad) NewVal = PoisonValue::get(NewVal->getType());478 ALoad->replaceAllUsesWith(NewVal);479 ReplacedLoads[ALoad] = NewVal;480 }481 482 // Allow the client to do stuff before we start nuking things.483 doExtraRewritesBeforeFinalDeletion();484 485 // Now that everything is rewritten, delete the old instructions from the486 // function. They should all be dead now.487 for (Instruction *User : Insts) {488 if (!shouldDelete(User))489 continue;490 491 // If this is a load that still has uses, then the load must have been added492 // as a live value in the SSAUpdate data structure for a block (e.g. because493 // the loaded value was stored later). In this case, we need to recursively494 // propagate the updates until we get to the real value.495 if (!User->use_empty()) {496 Value *NewVal = ReplacedLoads[User];497 assert(NewVal && "not a replaced load?");498 499 // Propagate down to the ultimate replacee. The intermediately loads500 // could theoretically already have been deleted, so we don't want to501 // dereference the Value*'s.502 DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);503 while (RLI != ReplacedLoads.end()) {504 NewVal = RLI->second;505 RLI = ReplacedLoads.find(NewVal);506 }507 508 replaceLoadWithValue(cast<LoadInst>(User), NewVal);509 User->replaceAllUsesWith(NewVal);510 }511 512 instructionDeleted(User);513 User->eraseFromParent();514 }515}516