//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "ssaupdater"
-#include "llvm/Transforms/Utils/SSAUpdater.h"
+#include "llvm/Constants.h"
#include "llvm/Instructions.h"
+#include "llvm/IntrinsicInst.h"
#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/TinyPtrVector.h"
+#include "llvm/Analysis/InstructionSimplify.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:
- BasicBlock *BB; // Back-pointer to the corresponding block.
- Value *AvailableVal; // Value to use in this block.
- BBInfo *DefBB; // Block that defines the available value.
- int BlkNum; // Postorder number.
- BBInfo *IDom; // Immediate dominator.
- unsigned NumPreds; // Number of predecessor blocks.
- BBInfo **Preds; // Array[NumPreds] of predecessor blocks.
- PHINode *PHITag; // Marker for existing PHIs that match.
-
- BBInfo(BasicBlock *ThisBB, Value *V)
- : BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0),
- NumPreds(0), Preds(0), PHITag(0) { }
-};
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/SSAUpdater.h"
+#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
-typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy;
+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);
-}
-
SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
- : AV(0), PrototypeValue(0), BM(0), InsertedPHIs(NewPHI) {}
+ : AV(0), ProtoType(0), ProtoName(), InsertedPHIs(NewPHI) {}
SSAUpdater::~SSAUpdater() {
delete &getAvailableVals(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 && "Unexpected Internal State");
Value *Res = GetValueAtEndOfBlockInternal(BB);
- assert(BM == 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 DebugLoc.
+ InsertedPHI->setDebugLoc(GetFirstDebugLocInBasicBlock(BB));
+
// If the client wants to know about all new instructions, tell it.
if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
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 Allocator;
- BBMapTy BBMapObj;
- BM = &BBMapObj;
-
- SmallVector<BBInfo*, 100> BlockList;
- BuildBlockList(BB, &BlockList, &Allocator);
-
- // Special case: bail out if BB is unreachable.
- if (BlockList.size() == 0) {
- BM = 0;
- return UndefValue::get(PrototypeValue->getType());
- }
-
- FindDominators(&BlockList);
- FindPHIPlacement(&BlockList);
- FindAvailableVals(&BlockList);
+/// 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);
+}
- BM = 0;
- return BBMapObj[BB]->DefBB->AvailableVal;
+/// PHIiter - Iterator for PHI operands. This is used for the PHI_iterator
+/// in the SSAUpdaterImpl template.
+namespace {
+ class PHIiter {
+ private:
+ PHINode *PHI;
+ unsigned idx;
+
+ public:
+ explicit PHIiter(PHINode *P) // begin iterator
+ : PHI(P), idx(0) {}
+ PHIiter(PHINode *P, bool) // end iterator
+ : PHI(P), idx(PHI->getNumIncomingValues()) {}
+
+ PHIiter &operator++() { ++idx; return *this; }
+ bool operator==(const PHIiter& x) const { return idx == x.idx; }
+ bool operator!=(const PHIiter& x) const { return !operator==(x); }
+ Value *getIncomingValue() { return PHI->getIncomingValue(idx); }
+ BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); }
+ };
}
-/// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
-/// vector, set Info->NumPreds, and allocate space in Info->Preds.
-static void FindPredecessorBlocks(SSAUpdater::BBInfo *Info,
- SmallVectorImpl<BasicBlock*> *Preds,
- BumpPtrAllocator *Allocator) {
- // 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.
- BasicBlock *BB = Info->BB;
- 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);
+/// 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); }
+
+ typedef PHIiter PHI_iterator;
+ static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
+ static inline PHI_iterator PHI_end(PhiT *PHI) {
+ return PHI_iterator(PHI, true);
}
- Info->NumPreds = Preds->size();
- Info->Preds = static_cast<SSAUpdater::BBInfo**>
- (Allocator->Allocate(Info->NumPreds * sizeof(SSAUpdater::BBInfo*),
- AlignOf<SSAUpdater::BBInfo*>::Alignment));
-}
-
-/// BuildBlockList - Starting from the specified basic block, traverse back
-/// through its predecessors until reaching blocks with known values. Create
-/// BBInfo structures for the blocks and append them to the block list.
-void SSAUpdater::BuildBlockList(BasicBlock *BB, BlockListTy *BlockList,
- BumpPtrAllocator *Allocator) {
- AvailableValsTy &AvailableVals = getAvailableVals(AV);
- BBMapTy *BBMap = getBBMap(BM);
- SmallVector<BBInfo*, 10> RootList;
- SmallVector<BBInfo*, 64> WorkList;
-
- BBInfo *Info = new (*Allocator) BBInfo(BB, 0);
- (*BBMap)[BB] = Info;
- WorkList.push_back(Info);
-
- // Search backward from BB, creating BBInfos along the way and stopping when
- // reaching blocks that define the value. Record those defining blocks on
- // the RootList.
- SmallVector<BasicBlock*, 10> Preds;
- while (!WorkList.empty()) {
- Info = WorkList.pop_back_val();
- Preds.clear();
- FindPredecessorBlocks(Info, &Preds, Allocator);
-
- // Treat an unreachable predecessor as a definition with 'undef'.
- if (Info->NumPreds == 0) {
- Info->AvailableVal = UndefValue::get(PrototypeValue->getType());
- Info->DefBB = Info;
- RootList.push_back(Info);
- continue;
+ /// 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);
}
+ }
- for (unsigned p = 0; p != Info->NumPreds; ++p) {
- BasicBlock *Pred = Preds[p];
- // Check if BBMap already has a BBInfo for the predecessor block.
- BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
- if (BBMapBucket.second) {
- Info->Preds[p] = BBMapBucket.second;
- continue;
- }
-
- // Create a new BBInfo for the predecessor.
- Value *PredVal = AvailableVals.lookup(Pred);
- BBInfo *PredInfo = new (*Allocator) BBInfo(Pred, PredVal);
- BBMapBucket.second = PredInfo;
- Info->Preds[p] = PredInfo;
-
- if (PredInfo->AvailableVal) {
- RootList.push_back(PredInfo);
- continue;
- }
- WorkList.push_back(PredInfo);
- }
+ /// 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);
}
- // Now that we know what blocks are backwards-reachable from the starting
- // block, do a forward depth-first traversal to assign postorder numbers
- // to those blocks.
- BBInfo *PseudoEntry = new (*Allocator) BBInfo(0, 0);
- unsigned BlkNum = 1;
-
- // Initialize the worklist with the roots from the backward traversal.
- while (!RootList.empty()) {
- Info = RootList.pop_back_val();
- Info->IDom = PseudoEntry;
- Info->BlkNum = -1;
- WorkList.push_back(Info);
+ /// 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;
}
- while (!WorkList.empty()) {
- Info = WorkList.back();
+ /// 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);
+ }
- if (Info->BlkNum == -2) {
- // All the successors have been handled; assign the postorder number.
- Info->BlkNum = BlkNum++;
- // If not a root, put it on the BlockList.
- if (!Info->AvailableVal)
- BlockList->push_back(Info);
- WorkList.pop_back();
- continue;
- }
+ /// InstrIsPHI - Check if an instruction is a PHI.
+ ///
+ static PHINode *InstrIsPHI(Instruction *I) {
+ return dyn_cast<PHINode>(I);
+ }
- // Leave this entry on the worklist, but set its BlkNum to mark that its
- // successors have been put on the worklist. When it returns to the top
- // the list, after handling its successors, it will be assigned a number.
- Info->BlkNum = -2;
+ /// ValueIsPHI - Check if a value is a PHI.
+ ///
+ static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) {
+ return dyn_cast<PHINode>(Val);
+ }
- // Add unvisited successors to the work list.
- for (succ_iterator SI = succ_begin(Info->BB), E = succ_end(Info->BB);
- SI != E; ++SI) {
- BBInfo *SuccInfo = (*BBMap)[*SI];
- if (!SuccInfo || SuccInfo->BlkNum)
- continue;
- SuccInfo->BlkNum = -1;
- WorkList.push_back(SuccInfo);
- }
+ /// 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;
}
- PseudoEntry->BlkNum = BlkNum;
-}
-/// IntersectDominators - This is the dataflow lattice "meet" operation for
-/// finding dominators. Given two basic blocks, it walks up the dominator
-/// tree until it finds a common dominator of both. It uses the postorder
-/// number of the blocks to determine how to do that.
-static SSAUpdater::BBInfo *IntersectDominators(SSAUpdater::BBInfo *Blk1,
- SSAUpdater::BBInfo *Blk2) {
- while (Blk1 != Blk2) {
- while (Blk1->BlkNum < Blk2->BlkNum) {
- Blk1 = Blk1->IDom;
- if (!Blk1)
- return Blk2;
- }
- while (Blk2->BlkNum < Blk1->BlkNum) {
- Blk2 = Blk2->IDom;
- if (!Blk2)
- return Blk1;
- }
+ /// GetPHIValue - For the specified PHI instruction, return the value
+ /// that it defines.
+ static Value *GetPHIValue(PHINode *PHI) {
+ return PHI;
}
- return Blk1;
-}
+};
-/// FindDominators - Calculate the dominator tree for the subset of the CFG
-/// corresponding to the basic blocks on the BlockList. This uses the
-/// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey and
-/// Kennedy, published in Software--Practice and Experience, 2001, 4:1-10.
-/// Because the CFG subset does not include any edges leading into blocks that
-/// define the value, the results are not the usual dominator tree. The CFG
-/// subset has a single pseudo-entry node with edges to a set of root nodes
-/// for blocks that define the value. The dominators for this subset CFG are
-/// not the standard dominators but they are adequate for placing PHIs within
-/// the subset CFG.
-void SSAUpdater::FindDominators(BlockListTy *BlockList) {
- bool Changed;
- do {
- Changed = false;
- // Iterate over the list in reverse order, i.e., forward on CFG edges.
- for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
- E = BlockList->rend(); I != E; ++I) {
- BBInfo *Info = *I;
-
- // Start with the first predecessor.
- assert(Info->NumPreds > 0 && "unreachable block");
- BBInfo *NewIDom = Info->Preds[0];
-
- // Iterate through the block's other predecessors.
- for (unsigned p = 1; p != Info->NumPreds; ++p) {
- BBInfo *Pred = Info->Preds[p];
- NewIDom = IntersectDominators(NewIDom, Pred);
- }
+} // End llvm namespace
- // Check if the IDom value has changed.
- if (NewIDom != Info->IDom) {
- Info->IDom = NewIDom;
- Changed = true;
- }
- }
- } while (Changed);
-}
+/// 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;
-/// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
-/// any blocks containing definitions of the value. If one is found, then the
-/// successor of Pred is in the dominance frontier for the definition, and
-/// this function returns true.
-static bool IsDefInDomFrontier(const SSAUpdater::BBInfo *Pred,
- const SSAUpdater::BBInfo *IDom) {
- for (; Pred != IDom; Pred = Pred->IDom) {
- if (Pred->DefBB == Pred)
- return true;
- }
- return false;
+ SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
+ return Impl.GetValue(BB);
}
-/// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of
-/// the known definitions. Iteratively add PHIs in the dom frontiers until
-/// nothing changes. Along the way, keep track of the nearest dominating
-/// definitions for non-PHI blocks.
-void SSAUpdater::FindPHIPlacement(BlockListTy *BlockList) {
- bool Changed;
- do {
- Changed = false;
- // Iterate over the list in reverse order, i.e., forward on CFG edges.
- for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
- E = BlockList->rend(); I != E; ++I) {
- BBInfo *Info = *I;
-
- // If this block already needs a PHI, there is nothing to do here.
- if (Info->DefBB == Info)
- continue;
+//===----------------------------------------------------------------------===//
+// LoadAndStorePromoter Implementation
+//===----------------------------------------------------------------------===//
- // Default to use the same def as the immediate dominator.
- BBInfo *NewDefBB = Info->IDom->DefBB;
- for (unsigned p = 0; p != Info->NumPreds; ++p) {
- if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
- // Need a PHI here.
- NewDefBB = Info;
- break;
- }
- }
+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 anything changed.
- if (NewDefBB != Info->DefBB) {
- Info->DefBB = NewDefBB;
- Changed = true;
- }
- }
- } while (Changed);
+ if (BaseName.empty())
+ BaseName = SomeVal->getName();
+ SSA.Initialize(SomeVal->getType(), BaseName);
}
-/// 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::FindAvailableVals(BlockListTy *BlockList) {
- AvailableValsTy &AvailableVals = getAvailableVals(AV);
-
- // Go through the worklist in forward order (i.e., backward through the CFG)
- // and check if existing PHIs can be used. If not, create empty PHIs where
- // they are needed.
- for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end();
- I != E; ++I) {
- BBInfo *Info = *I;
- // Check if there needs to be a PHI in BB.
- if (Info->DefBB != Info)
- continue;
-
- // Look for an existing PHI.
- FindExistingPHI(Info->BB, BlockList);
- if (Info->AvailableVal)
- continue;
- PHINode *PHI = PHINode::Create(PrototypeValue->getType(),
- PrototypeValue->getName(),
- &Info->BB->front());
- PHI->reserveOperandSpace(Info->NumPreds);
- Info->AvailableVal = PHI;
- AvailableVals[Info->BB] = PHI;
+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);
}
-
- // Now go back through the worklist in reverse order to fill in the arguments
- // for any new PHIs added in the forward traversal.
- for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
- E = BlockList->rend(); I != E; ++I) {
- BBInfo *Info = *I;
-
- if (Info->DefBB != Info) {
- // Record the available value at join nodes to speed up subsequent
- // uses of this SSAUpdater for the same value.
- if (Info->NumPreds > 1)
- AvailableVals[Info->BB] = Info->DefBB->AvailableVal;
+
+ // 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;
}
-
- // Check if this block contains a newly added PHI.
- PHINode *PHI = dyn_cast<PHINode>(Info->AvailableVal);
- if (!PHI || PHI->getNumIncomingValues() == Info->NumPreds)
+
+ // 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;
-
- // Iterate through the block's predecessors.
- for (unsigned p = 0; p != Info->NumPreds; ++p) {
- BBInfo *PredInfo = Info->Preds[p];
- BasicBlock *Pred = PredInfo->BB;
- // Skip to the nearest preceding definition.
- if (PredInfo->DefBB != PredInfo)
- PredInfo = PredInfo->DefBB;
- PHI->addIncoming(PredInfo->AvailableVal, Pred);
}
-
- DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n");
-
- // If the client wants to know about all new instructions, tell it.
- if (InsertedPHIs) InsertedPHIs->push_back(PHI);
- }
-}
-
-/// FindExistingPHI - Look through the PHI nodes in a block to see if any of
-/// them match what is needed.
-void SSAUpdater::FindExistingPHI(BasicBlock *BB, BlockListTy *BlockList) {
- PHINode *SomePHI;
- for (BasicBlock::iterator It = BB->begin();
- (SomePHI = dyn_cast<PHINode>(It)); ++It) {
- if (CheckIfPHIMatches(SomePHI)) {
- RecordMatchingPHI(SomePHI);
- break;
+
+ // 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);
+ }
}
- // Match failed: clear all the PHITag values.
- for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end();
- I != E; ++I)
- (*I)->PHITag = 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();
}
-}
-
-/// 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);
- BBInfo *PredInfo = (*BBMap)[PHI->getIncomingBlock(i)];
- // Skip to the nearest preceding definition.
- if (PredInfo->DefBB != PredInfo)
- PredInfo = PredInfo->DefBB;
-
- // Check if it matches the expected value.
- if (PredInfo->AvailableVal) {
- if (IncomingVal == PredInfo->AvailableVal)
- continue;
- return false;
- }
-
- // Check if the value is a PHI in the correct block.
- PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal);
- if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
- return false;
-
- // If this block has already been visited, check if this PHI matches.
- if (PredInfo->PHITag) {
- if (IncomingPHIVal == PredInfo->PHITag)
- continue;
- return false;
+
+ // 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);
}
- PredInfo->PHITag = IncomingPHIVal;
-
- WorkList.push_back(IncomingPHIVal);
+
+ replaceLoadWithValue(cast<LoadInst>(User), NewVal);
+ User->replaceAllUsesWith(NewVal);
}
+
+ instructionDeleted(User);
+ User->eraseFromParent();
}
- 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);
-
- // Record this PHI.
- BasicBlock *BB = PHI->getParent();
- AvailableVals[BB] = PHI;
- (*BBMap)[BB]->AvailableVal = 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) {
- PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
- if (!IncomingPHIVal) continue;
- BB = IncomingPHIVal->getParent();
- BBInfo *Info = (*BBMap)[BB];
- if (!Info || Info->AvailableVal)
- continue;
-
- // Record the PHI and add it to the worklist.
- AvailableVals[BB] = IncomingPHIVal;
- Info->AvailableVal = IncomingPHIVal;
- WorkList.push_back(IncomingPHIVal);
- }
- }
+bool
+LoadAndStorePromoter::isInstInList(Instruction *I,
+ const SmallVectorImpl<Instruction*> &Insts)
+ const {
+ return std::find(Insts.begin(), Insts.end(), I) != Insts.end();
}