//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "ssaupdater"
#include "llvm/Transforms/Utils/SSAUpdater.h"
-#include "llvm/Instructions.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/TinyPtrVector.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/IntrinsicInst.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
-using namespace llvm;
-
-/// BBInfo - Per-basic block information used internally by SSAUpdater.
-/// The predecessors of each block are cached here since pred_iterator is
-/// slow and we need to iterate over the blocks at least a few times.
-class SSAUpdater::BBInfo {
-public:
- Value *AvailableVal; // Value to use in this block.
- BasicBlock *DefBB; // Block that defines the available value.
- unsigned NumPreds; // Number of predecessor blocks.
- BasicBlock **Preds; // Array[NumPreds] of predecessor blocks.
- unsigned Counter; // Marker to identify blocks already visited.
- PHINode *PHITag; // Marker for existing PHIs that match.
-
- BBInfo(BasicBlock *BB, Value *V, BumpPtrAllocator *Allocator);
-};
-typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy;
-
-SSAUpdater::BBInfo::BBInfo(BasicBlock *BB, Value *V,
- BumpPtrAllocator *Allocator)
- : AvailableVal(V), DefBB(0), NumPreds(0), Preds(0), Counter(0), PHITag(0) {
- // If this block has a known value, don't bother finding its predecessors.
- if (V) {
- DefBB = BB;
- return;
- }
-
- // We can get our predecessor info by walking the pred_iterator list, but it
- // is relatively slow. If we already have PHI nodes in this block, walk one
- // of them to get the predecessor list instead.
- if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
- NumPreds = SomePhi->getNumIncomingValues();
- Preds = static_cast<BasicBlock**>
- (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
- AlignOf<BasicBlock*>::Alignment));
- for (unsigned pi = 0; pi != NumPreds; ++pi)
- Preds[pi] = SomePhi->getIncomingBlock(pi);
- return;
- }
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
- // Stash the predecessors in a temporary vector until we know how much space
- // to allocate for them.
- SmallVector<BasicBlock*, 10> TmpPreds;
- for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
- TmpPreds.push_back(*PI);
- ++NumPreds;
- }
- Preds = static_cast<BasicBlock**>
- (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
- AlignOf<BasicBlock*>::Alignment));
- memcpy(Preds, TmpPreds.data(), NumPreds * sizeof(BasicBlock*));
-}
+using namespace llvm;
typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
static AvailableValsTy &getAvailableVals(void *AV) {
return *static_cast<AvailableValsTy*>(AV);
}
-static BBMapTy *getBBMap(void *BM) {
- return static_cast<BBMapTy*>(BM);
-}
-
-static BumpPtrAllocator *getAllocator(void *BPA) {
- return static_cast<BumpPtrAllocator*>(BPA);
-}
-
SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
- : AV(0), PrototypeValue(0), BM(0), BPA(0), InsertedPHIs(NewPHI) {}
+ : AV(0), ProtoType(0), ProtoName(), InsertedPHIs(NewPHI) {}
SSAUpdater::~SSAUpdater() {
- delete &getAvailableVals(AV);
+ delete static_cast<AvailableValsTy*>(AV);
}
/// Initialize - Reset this object to get ready for a new set of SSA
-/// updates. ProtoValue is the value used to name PHI nodes.
-void SSAUpdater::Initialize(Value *ProtoValue) {
+/// updates with type 'Ty'. PHI nodes get a name based on 'Name'.
+void SSAUpdater::Initialize(Type *Ty, StringRef Name) {
if (AV == 0)
AV = new AvailableValsTy();
else
getAvailableVals(AV).clear();
- PrototypeValue = ProtoValue;
+ ProtoType = Ty;
+ ProtoName = Name;
}
/// HasValueForBlock - Return true if the SSAUpdater already has a value for
/// AddAvailableValue - Indicate that a rewritten value is available in the
/// specified block with the specified value.
void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
- assert(PrototypeValue != 0 && "Need to initialize SSAUpdater");
- assert(PrototypeValue->getType() == V->getType() &&
+ assert(ProtoType != 0 && "Need to initialize SSAUpdater");
+ assert(ProtoType == V->getType() &&
"All rewritten values must have the same type");
getAvailableVals(AV)[BB] = V;
}
/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
/// live at the end of the specified block.
Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
- assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
Value *Res = GetValueAtEndOfBlockInternal(BB);
- assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
return Res;
}
// If there are no predecessors, just return undef.
if (PredValues.empty())
- return UndefValue::get(PrototypeValue->getType());
+ return UndefValue::get(ProtoType);
// Otherwise, if all the merged values are the same, just use it.
if (SingularValue != 0)
}
// Ok, we have no way out, insert a new one now.
- PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(),
- PrototypeValue->getName(),
- &BB->front());
- InsertedPHI->reserveOperandSpace(PredValues.size());
+ PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(),
+ ProtoName, &BB->front());
// Fill in all the predecessors of the PHI.
for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
// See if the PHI node can be merged to a single value. This can happen in
// loop cases when we get a PHI of itself and one other value.
- if (Value *ConstVal = InsertedPHI->hasConstantValue()) {
+ if (Value *V = SimplifyInstruction(InsertedPHI)) {
InsertedPHI->eraseFromParent();
- return ConstVal;
+ return V;
}
+ // Set the DebugLoc of the inserted PHI, if available.
+ DebugLoc DL;
+ if (const Instruction *I = BB->getFirstNonPHI())
+ DL = I->getDebugLoc();
+ InsertedPHI->setDebugLoc(DL);
+
// If the client wants to know about all new instructions, tell it.
if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
else
V = GetValueInMiddleOfBlock(User->getParent());
+ // Notify that users of the existing value that it is being replaced.
+ Value *OldVal = U.get();
+ if (OldVal != V && OldVal->hasValueHandle())
+ ValueHandleBase::ValueIsRAUWd(OldVal, V);
+
U.set(V);
}
-/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
-/// for the specified BB and if so, return it. If not, construct SSA form by
-/// first calculating the required placement of PHIs and then inserting new
-/// PHIs where needed.
-Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
- AvailableValsTy &AvailableVals = getAvailableVals(AV);
- if (Value *V = AvailableVals[BB])
- return V;
-
- // Pool allocation used internally by GetValueAtEndOfBlock.
- BumpPtrAllocator AllocatorObj;
- BBMapTy BBMapObj;
- BPA = &AllocatorObj;
- BM = &BBMapObj;
-
- BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj);
- BBMapObj[BB] = Info;
-
- bool Changed;
- unsigned Counter = 1;
- do {
- Changed = false;
- FindPHIPlacement(BB, Info, Changed, Counter);
- ++Counter;
- } while (Changed);
-
- FindAvailableVal(BB, Info, Counter);
-
- BPA = 0;
- BM = 0;
- return Info->AvailableVal;
+/// RewriteUseAfterInsertions - Rewrite a use, just like RewriteUse. However,
+/// this version of the method can rewrite uses in the same block as a
+/// definition, because it assumes that all uses of a value are below any
+/// inserted values.
+void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
+ Instruction *User = cast<Instruction>(U.getUser());
+
+ Value *V;
+ if (PHINode *UserPN = dyn_cast<PHINode>(User))
+ V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
+ else
+ V = GetValueAtEndOfBlock(User->getParent());
+
+ U.set(V);
}
-/// FindPHIPlacement - Recursively visit the predecessors of a block to find
-/// the reaching definition for each predecessor and then determine whether
-/// a PHI is needed in this block.
-void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed,
- unsigned Counter) {
- AvailableValsTy &AvailableVals = getAvailableVals(AV);
- BBMapTy *BBMap = getBBMap(BM);
- BumpPtrAllocator *Allocator = getAllocator(BPA);
- bool BBNeedsPHI = false;
- BasicBlock *SamePredDefBB = 0;
-
- // If there are no predecessors, then we must have found an unreachable
- // block. Treat it as a definition with 'undef'.
- if (Info->NumPreds == 0) {
- Info->AvailableVal = UndefValue::get(PrototypeValue->getType());
- Info->DefBB = BB;
- return;
+/// SSAUpdaterTraits<SSAUpdater> - Traits for the SSAUpdaterImpl template,
+/// specialized for SSAUpdater.
+namespace llvm {
+template<>
+class SSAUpdaterTraits<SSAUpdater> {
+public:
+ typedef BasicBlock BlkT;
+ typedef Value *ValT;
+ typedef PHINode PhiT;
+
+ typedef succ_iterator BlkSucc_iterator;
+ static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); }
+ static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); }
+
+ class PHI_iterator {
+ private:
+ PHINode *PHI;
+ unsigned idx;
+
+ public:
+ explicit PHI_iterator(PHINode *P) // begin iterator
+ : PHI(P), idx(0) {}
+ PHI_iterator(PHINode *P, bool) // end iterator
+ : PHI(P), idx(PHI->getNumIncomingValues()) {}
+
+ PHI_iterator &operator++() { ++idx; return *this; }
+ bool operator==(const PHI_iterator& x) const { return idx == x.idx; }
+ bool operator!=(const PHI_iterator& x) const { return !operator==(x); }
+ Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
+ BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }
+ };
+
+ static PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
+ static PHI_iterator PHI_end(PhiT *PHI) {
+ return PHI_iterator(PHI, true);
}
- Info->Counter = Counter;
- for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
- BasicBlock *Pred = Info->Preds[pi];
- BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
- if (!BBMapBucket.second) {
- Value *PredVal = AvailableVals.lookup(Pred);
- BBMapBucket.second = new (*Allocator) BBInfo(Pred, PredVal, Allocator);
+ /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
+ /// vector, set Info->NumPreds, and allocate space in Info->Preds.
+ static void FindPredecessorBlocks(BasicBlock *BB,
+ SmallVectorImpl<BasicBlock*> *Preds) {
+ // We can get our predecessor info by walking the pred_iterator list,
+ // but it is relatively slow. If we already have PHI nodes in this
+ // block, walk one of them to get the predecessor list instead.
+ if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
+ for (unsigned PI = 0, E = SomePhi->getNumIncomingValues(); PI != E; ++PI)
+ Preds->push_back(SomePhi->getIncomingBlock(PI));
+ } else {
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+ Preds->push_back(*PI);
}
- BBInfo *PredInfo = BBMapBucket.second;
- BasicBlock *DefBB = 0;
- if (!PredInfo->AvailableVal) {
- if (PredInfo->Counter != Counter)
- FindPHIPlacement(Pred, PredInfo, Changed, Counter);
-
- // Ignore back edges where the value is not yet known.
- if (!PredInfo->DefBB)
- continue;
- }
- DefBB = PredInfo->DefBB;
-
- if (!SamePredDefBB)
- SamePredDefBB = DefBB;
- else if (DefBB != SamePredDefBB)
- BBNeedsPHI = true;
}
- BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB);
- if (Info->DefBB != NewDefBB) {
- Changed = true;
- Info->DefBB = NewDefBB;
+ /// GetUndefVal - Get an undefined value of the same type as the value
+ /// being handled.
+ static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) {
+ return UndefValue::get(Updater->ProtoType);
}
-}
-/// FindAvailableVal - If this block requires a PHI, first check if an existing
-/// PHI matches the PHI placement and reaching definitions computed earlier,
-/// and if not, create a new PHI. Visit all the block's predecessors to
-/// calculate the available value for each one and fill in the incoming values
-/// for a new PHI.
-void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info,
- unsigned Counter) {
- if (Info->AvailableVal || Info->Counter == Counter)
- return;
+ /// CreateEmptyPHI - Create a new PHI instruction in the specified block.
+ /// Reserve space for the operands but do not fill them in yet.
+ static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds,
+ SSAUpdater *Updater) {
+ PHINode *PHI = PHINode::Create(Updater->ProtoType, NumPreds,
+ Updater->ProtoName, &BB->front());
+ return PHI;
+ }
- AvailableValsTy &AvailableVals = getAvailableVals(AV);
- BBMapTy *BBMap = getBBMap(BM);
-
- // Check if there needs to be a PHI in BB.
- PHINode *NewPHI = 0;
- if (Info->DefBB == BB) {
- // Look for an existing PHI.
- FindExistingPHI(BB);
- if (!Info->AvailableVal) {
- NewPHI = PHINode::Create(PrototypeValue->getType(),
- PrototypeValue->getName(), &BB->front());
- NewPHI->reserveOperandSpace(Info->NumPreds);
- Info->AvailableVal = NewPHI;
- AvailableVals[BB] = NewPHI;
- }
+ /// AddPHIOperand - Add the specified value as an operand of the PHI for
+ /// the specified predecessor block.
+ static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) {
+ PHI->addIncoming(Val, Pred);
}
- // Iterate through the block's predecessors.
- Info->Counter = Counter;
- for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
- BasicBlock *Pred = Info->Preds[pi];
- BBInfo *PredInfo = (*BBMap)[Pred];
- FindAvailableVal(Pred, PredInfo, Counter);
- if (NewPHI) {
- // Skip to the nearest preceding definition.
- if (PredInfo->DefBB != Pred)
- PredInfo = (*BBMap)[PredInfo->DefBB];
- NewPHI->addIncoming(PredInfo->AvailableVal, Pred);
- } else if (!Info->AvailableVal)
- Info->AvailableVal = PredInfo->AvailableVal;
+ /// InstrIsPHI - Check if an instruction is a PHI.
+ ///
+ static PHINode *InstrIsPHI(Instruction *I) {
+ return dyn_cast<PHINode>(I);
}
- if (NewPHI) {
- DEBUG(dbgs() << " Inserted PHI: " << *NewPHI << "\n");
+ /// ValueIsPHI - Check if a value is a PHI.
+ ///
+ static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
+ return dyn_cast<PHINode>(Val);
+ }
- // If the client wants to know about all new instructions, tell it.
- if (InsertedPHIs) InsertedPHIs->push_back(NewPHI);
+ /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
+ /// operands, i.e., it was just added.
+ static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) {
+ PHINode *PHI = ValueIsPHI(Val, Updater);
+ if (PHI && PHI->getNumIncomingValues() == 0)
+ return PHI;
+ return 0;
}
-}
-/// FindExistingPHI - Look through the PHI nodes in a block to see if any of
-/// them match what is needed.
-void SSAUpdater::FindExistingPHI(BasicBlock *BB) {
- PHINode *SomePHI;
- for (BasicBlock::iterator It = BB->begin();
- (SomePHI = dyn_cast<PHINode>(It)); ++It) {
- if (CheckIfPHIMatches(SomePHI)) {
- RecordMatchingPHI(SomePHI);
- break;
- }
- ClearPHITags(SomePHI);
+ /// GetPHIValue - For the specified PHI instruction, return the value
+ /// that it defines.
+ static Value *GetPHIValue(PHINode *PHI) {
+ return PHI;
}
+};
+
+} // End llvm namespace
+
+/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
+/// for the specified BB and if so, return it. If not, construct SSA form by
+/// first calculating the required placement of PHIs and then inserting new
+/// PHIs where needed.
+Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
+ AvailableValsTy &AvailableVals = getAvailableVals(AV);
+ if (Value *V = AvailableVals[BB])
+ return V;
+
+ SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
+ return Impl.GetValue(BB);
}
-/// CheckIfPHIMatches - Check if a PHI node matches the placement and values
-/// in the BBMap.
-bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) {
- BBMapTy *BBMap = getBBMap(BM);
- SmallVector<PHINode*, 20> WorkList;
- WorkList.push_back(PHI);
-
- // Mark that the block containing this PHI has been visited.
- (*BBMap)[PHI->getParent()]->PHITag = PHI;
-
- while (!WorkList.empty()) {
- PHI = WorkList.pop_back_val();
-
- // Iterate through the PHI's incoming values.
- for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
- Value *IncomingVal = PHI->getIncomingValue(i);
- BasicBlock *Pred = PHI->getIncomingBlock(i);
- BBInfo *PredInfo = (*BBMap)[Pred];
- // Skip to the nearest preceding definition.
- if (PredInfo->DefBB != Pred) {
- Pred = PredInfo->DefBB;
- PredInfo = (*BBMap)[Pred];
- }
+//===----------------------------------------------------------------------===//
+// LoadAndStorePromoter Implementation
+//===----------------------------------------------------------------------===//
- // Check if it matches the expected value.
- if (PredInfo->AvailableVal) {
- if (IncomingVal == PredInfo->AvailableVal)
- continue;
- return false;
- }
+LoadAndStorePromoter::
+LoadAndStorePromoter(const SmallVectorImpl<Instruction*> &Insts,
+ SSAUpdater &S, StringRef BaseName) : SSA(S) {
+ if (Insts.empty()) return;
+
+ Value *SomeVal;
+ if (LoadInst *LI = dyn_cast<LoadInst>(Insts[0]))
+ SomeVal = LI;
+ else
+ SomeVal = cast<StoreInst>(Insts[0])->getOperand(0);
- // Check if the value is a PHI in the correct block.
- PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal);
- if (!IncomingPHIVal || IncomingPHIVal->getParent() != Pred)
- return false;
+ if (BaseName.empty())
+ BaseName = SomeVal->getName();
+ SSA.Initialize(SomeVal->getType(), BaseName);
+}
- // If this block has already been visited, check if this PHI matches.
- if (PredInfo->PHITag) {
- if (IncomingPHIVal == PredInfo->PHITag)
- continue;
- return false;
- }
- PredInfo->PHITag = IncomingPHIVal;
- WorkList.push_back(IncomingPHIVal);
+void LoadAndStorePromoter::
+run(const SmallVectorImpl<Instruction*> &Insts) const {
+
+ // First step: bucket up uses of the alloca by the block they occur in.
+ // This is important because we have to handle multiple defs/uses in a block
+ // ourselves: SSAUpdater is purely for cross-block references.
+ DenseMap<BasicBlock*, TinyPtrVector<Instruction*> > UsesByBlock;
+
+ for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
+ Instruction *User = Insts[i];
+ UsesByBlock[User->getParent()].push_back(User);
+ }
+
+ // Okay, now we can iterate over all the blocks in the function with uses,
+ // processing them. Keep track of which loads are loading a live-in value.
+ // Walk the uses in the use-list order to be determinstic.
+ SmallVector<LoadInst*, 32> LiveInLoads;
+ DenseMap<Value*, Value*> ReplacedLoads;
+
+ for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
+ Instruction *User = Insts[i];
+ BasicBlock *BB = User->getParent();
+ TinyPtrVector<Instruction*> &BlockUses = UsesByBlock[BB];
+
+ // If this block has already been processed, ignore this repeat use.
+ if (BlockUses.empty()) continue;
+
+ // Okay, this is the first use in the block. If this block just has a
+ // single user in it, we can rewrite it trivially.
+ if (BlockUses.size() == 1) {
+ // If it is a store, it is a trivial def of the value in the block.
+ if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
+ updateDebugInfo(SI);
+ SSA.AddAvailableValue(BB, SI->getOperand(0));
+ } else
+ // Otherwise it is a load, queue it to rewrite as a live-in load.
+ LiveInLoads.push_back(cast<LoadInst>(User));
+ BlockUses.clear();
+ continue;
+ }
+
+ // Otherwise, check to see if this block is all loads.
+ bool HasStore = false;
+ for (unsigned i = 0, e = BlockUses.size(); i != e; ++i) {
+ if (isa<StoreInst>(BlockUses[i])) {
+ HasStore = true;
+ break;
+ }
+ }
+
+ // If so, we can queue them all as live in loads. We don't have an
+ // efficient way to tell which on is first in the block and don't want to
+ // scan large blocks, so just add all loads as live ins.
+ if (!HasStore) {
+ for (unsigned i = 0, e = BlockUses.size(); i != e; ++i)
+ LiveInLoads.push_back(cast<LoadInst>(BlockUses[i]));
+ BlockUses.clear();
+ continue;
+ }
+
+ // Otherwise, we have mixed loads and stores (or just a bunch of stores).
+ // Since SSAUpdater is purely for cross-block values, we need to determine
+ // the order of these instructions in the block. If the first use in the
+ // block is a load, then it uses the live in value. The last store defines
+ // the live out value. We handle this by doing a linear scan of the block.
+ Value *StoredValue = 0;
+ for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) {
+ if (LoadInst *L = dyn_cast<LoadInst>(II)) {
+ // If this is a load from an unrelated pointer, ignore it.
+ if (!isInstInList(L, Insts)) continue;
+
+ // If we haven't seen a store yet, this is a live in use, otherwise
+ // use the stored value.
+ if (StoredValue) {
+ replaceLoadWithValue(L, StoredValue);
+ L->replaceAllUsesWith(StoredValue);
+ ReplacedLoads[L] = StoredValue;
+ } else {
+ LiveInLoads.push_back(L);
+ }
+ continue;
+ }
+
+ if (StoreInst *SI = dyn_cast<StoreInst>(II)) {
+ // If this is a store to an unrelated pointer, ignore it.
+ if (!isInstInList(SI, Insts)) continue;
+ updateDebugInfo(SI);
+
+ // Remember that this is the active value in the block.
+ StoredValue = SI->getOperand(0);
+ }
}
+
+ // The last stored value that happened is the live-out for the block.
+ assert(StoredValue && "Already checked that there is a store in block");
+ SSA.AddAvailableValue(BB, StoredValue);
+ BlockUses.clear();
}
- return true;
-}
-
-/// RecordMatchingPHI - For a PHI node that matches, record it and its input
-/// PHIs in both the BBMap and the AvailableVals mapping.
-void SSAUpdater::RecordMatchingPHI(PHINode *PHI) {
- BBMapTy *BBMap = getBBMap(BM);
- AvailableValsTy &AvailableVals = getAvailableVals(AV);
- SmallVector<PHINode*, 20> WorkList;
- WorkList.push_back(PHI);
-
- while (!WorkList.empty()) {
- PHI = WorkList.pop_back_val();
- BasicBlock *BB = PHI->getParent();
- BBInfo *Info = (*BBMap)[BB];
- if (!Info || Info->AvailableVal)
- return;
-
- // Record the PHI.
- AvailableVals[BB] = PHI;
- Info->AvailableVal = PHI;
-
- // Iterate through the PHI's incoming values.
- for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
- PHINode *IncomingVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
- if (!IncomingVal) continue;
- WorkList.push_back(IncomingVal);
+
+ // Okay, now we rewrite all loads that use live-in values in the loop,
+ // inserting PHI nodes as necessary.
+ for (unsigned i = 0, e = LiveInLoads.size(); i != e; ++i) {
+ LoadInst *ALoad = LiveInLoads[i];
+ Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());
+ replaceLoadWithValue(ALoad, NewVal);
+
+ // Avoid assertions in unreachable code.
+ if (NewVal == ALoad) NewVal = UndefValue::get(NewVal->getType());
+ ALoad->replaceAllUsesWith(NewVal);
+ ReplacedLoads[ALoad] = NewVal;
+ }
+
+ // Allow the client to do stuff before we start nuking things.
+ doExtraRewritesBeforeFinalDeletion();
+
+ // Now that everything is rewritten, delete the old instructions from the
+ // function. They should all be dead now.
+ for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
+ Instruction *User = Insts[i];
+
+ // If this is a load that still has uses, then the load must have been added
+ // as a live value in the SSAUpdate data structure for a block (e.g. because
+ // the loaded value was stored later). In this case, we need to recursively
+ // propagate the updates until we get to the real value.
+ if (!User->use_empty()) {
+ Value *NewVal = ReplacedLoads[User];
+ assert(NewVal && "not a replaced load?");
+
+ // Propagate down to the ultimate replacee. The intermediately loads
+ // could theoretically already have been deleted, so we don't want to
+ // dereference the Value*'s.
+ DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);
+ while (RLI != ReplacedLoads.end()) {
+ NewVal = RLI->second;
+ RLI = ReplacedLoads.find(NewVal);
+ }
+
+ replaceLoadWithValue(cast<LoadInst>(User), NewVal);
+ User->replaceAllUsesWith(NewVal);
}
+
+ instructionDeleted(User);
+ User->eraseFromParent();
}
}
-/// ClearPHITags - When one of the existing PHI nodes fails to match, clear
-/// the PHITag values that were stored in the BBMap when checking to see if
-/// it matched.
-void SSAUpdater::ClearPHITags(PHINode *PHI) {
- BBMapTy *BBMap = getBBMap(BM);
- SmallVector<PHINode*, 20> WorkList;
- WorkList.push_back(PHI);
-
- while (!WorkList.empty()) {
- PHI = WorkList.pop_back_val();
- BasicBlock *BB = PHI->getParent();
- BBInfo *Info = (*BBMap)[BB];
- if (!Info || Info->AvailableVal || !Info->PHITag)
- continue;
-
- // Clear the tag.
- Info->PHITag = 0;
-
- // Iterate through the PHI's incoming values.
- for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
- PHINode *IncomingVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
- if (!IncomingVal) continue;
- WorkList.push_back(IncomingVal);
- }
- }
+bool
+LoadAndStorePromoter::isInstInList(Instruction *I,
+ const SmallVectorImpl<Instruction*> &Insts)
+ const {
+ return std::find(Insts.begin(), Insts.end(), I) != Insts.end();
}
projects / oota-llvm.git / blobdiff