//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "mem2reg"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>
using namespace llvm;
+STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
+STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store");
+STATISTIC(NumDeadAlloca, "Number of dead alloca's removed");
+
// Provide DenseMapKeyInfo for all pointers.
namespace llvm {
template<>
/// isAllocaPromotable - Return true if this alloca is legal for promotion.
/// This is true if there are only loads and stores to the alloca.
///
-bool llvm::isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) {
+bool llvm::isAllocaPromotable(const AllocaInst *AI) {
// FIXME: If the memory unit is of pointer or integer type, we can permit
// assignments to subsections of the memory unit.
}
namespace {
+ struct AllocaInfo;
// Data package used by RenamePass()
class VISIBILITY_HIDDEN RenamePassData {
public:
+ typedef std::vector<Value *> ValVector;
+
+ RenamePassData() {}
RenamePassData(BasicBlock *B, BasicBlock *P,
- const std::vector<Value *> &V) : BB(B), Pred(P), Values(V) {}
+ const ValVector &V) : BB(B), Pred(P), Values(V) {}
BasicBlock *BB;
BasicBlock *Pred;
- std::vector<Value *> Values;
+ ValVector Values;
+
+ void swap(RenamePassData &RHS) {
+ std::swap(BB, RHS.BB);
+ std::swap(Pred, RHS.Pred);
+ Values.swap(RHS.Values);
+ }
};
struct VISIBILITY_HIDDEN PromoteMem2Reg {
///
std::vector<AllocaInst*> Allocas;
SmallVector<AllocaInst*, 16> &RetryList;
- ETForest &ET;
+ DominatorTree &DT;
DominanceFrontier &DF;
- const TargetData &TD;
/// AST - An AliasSetTracker object to update. If null, don't update it.
///
/// non-determinstic behavior.
DenseMap<BasicBlock*, unsigned> BBNumbers;
- /// RenamePassWorkList - Worklist used by RenamePass()
- std::vector<RenamePassData> RenamePassWorkList;
-
public:
PromoteMem2Reg(const std::vector<AllocaInst*> &A,
- SmallVector<AllocaInst*, 16> &Retry, ETForest &et,
- DominanceFrontier &df, const TargetData &td,
- AliasSetTracker *ast)
- : Allocas(A), RetryList(Retry), ET(et), DF(df), TD(td), AST(ast) {}
+ SmallVector<AllocaInst*, 16> &Retry, DominatorTree &dt,
+ DominanceFrontier &df, AliasSetTracker *ast)
+ : Allocas(A), RetryList(Retry), DT(dt), DF(df), AST(ast) {}
void run();
bool properlyDominates(Instruction *I1, Instruction *I2) const {
if (InvokeInst *II = dyn_cast<InvokeInst>(I1))
I1 = II->getNormalDest()->begin();
- return ET.properlyDominates(I1->getParent(), I2->getParent());
+ return DT.properlyDominates(I1->getParent(), I2->getParent());
}
/// dominates - Return true if BB1 dominates BB2 using the DominatorTree.
///
bool dominates(BasicBlock *BB1, BasicBlock *BB2) const {
- return ET.dominates(BB1, BB2);
+ return DT.dominates(BB1, BB2);
}
private:
+ void RemoveFromAllocasList(unsigned &AllocaIdx) {
+ Allocas[AllocaIdx] = Allocas.back();
+ Allocas.pop_back();
+ --AllocaIdx;
+ }
+
+ void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info);
+
void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum,
SmallPtrSet<PHINode*, 16> &DeadPHINodes);
bool PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI);
const std::vector<AllocaInst*> &AIs);
void RenamePass(BasicBlock *BB, BasicBlock *Pred,
- std::vector<Value*> &IncVals);
+ RenamePassData::ValVector &IncVals,
+ std::vector<RenamePassData> &Worklist);
bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version,
SmallPtrSet<PHINode*, 16> &InsertedPHINodes);
};
+
+ struct AllocaInfo {
+ std::vector<BasicBlock*> DefiningBlocks;
+ std::vector<BasicBlock*> UsingBlocks;
+
+ StoreInst *OnlyStore;
+ BasicBlock *OnlyBlock;
+ bool OnlyUsedInOneBlock;
+
+ Value *AllocaPointerVal;
+
+ void clear() {
+ DefiningBlocks.clear();
+ UsingBlocks.clear();
+ OnlyStore = 0;
+ OnlyBlock = 0;
+ OnlyUsedInOneBlock = true;
+ AllocaPointerVal = 0;
+ }
+
+ /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our
+ /// ivars.
+ void AnalyzeAlloca(AllocaInst *AI) {
+ clear();
+
+ // As we scan the uses of the alloca instruction, keep track of stores,
+ // and decide whether all of the loads and stores to the alloca are within
+ // the same basic block.
+ for (Value::use_iterator U = AI->use_begin(), E = AI->use_end();
+ U != E; ++U){
+ Instruction *User = cast<Instruction>(*U);
+ if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
+ // Remember the basic blocks which define new values for the alloca
+ DefiningBlocks.push_back(SI->getParent());
+ AllocaPointerVal = SI->getOperand(0);
+ OnlyStore = SI;
+ } else {
+ LoadInst *LI = cast<LoadInst>(User);
+ // Otherwise it must be a load instruction, keep track of variable reads
+ UsingBlocks.push_back(LI->getParent());
+ AllocaPointerVal = LI;
+ }
+
+ if (OnlyUsedInOneBlock) {
+ if (OnlyBlock == 0)
+ OnlyBlock = User->getParent();
+ else if (OnlyBlock != User->getParent())
+ OnlyUsedInOneBlock = false;
+ }
+ }
+ }
+ };
} // end of anonymous namespace
+
void PromoteMem2Reg::run() {
Function &F = *DF.getRoot()->getParent();
if (AST) PointerAllocaValues.resize(Allocas.size());
+ AllocaInfo Info;
+
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
AllocaInst *AI = Allocas[AllocaNum];
- assert(isAllocaPromotable(AI, TD) &&
+ assert(isAllocaPromotable(AI) &&
"Cannot promote non-promotable alloca!");
assert(AI->getParent()->getParent() == &F &&
"All allocas should be in the same function, which is same as DF!");
AI->eraseFromParent();
// Remove the alloca from the Allocas list, since it has been processed
- Allocas[AllocaNum] = Allocas.back();
- Allocas.pop_back();
- --AllocaNum;
+ RemoveFromAllocasList(AllocaNum);
+ ++NumDeadAlloca;
continue;
}
-
+
// Calculate the set of read and write-locations for each alloca. This is
// analogous to finding the 'uses' and 'definitions' of each variable.
- std::vector<BasicBlock*> DefiningBlocks;
- std::vector<BasicBlock*> UsingBlocks;
-
- StoreInst *OnlyStore = 0;
- BasicBlock *OnlyBlock = 0;
- bool OnlyUsedInOneBlock = true;
-
- // As we scan the uses of the alloca instruction, keep track of stores, and
- // decide whether all of the loads and stores to the alloca are within the
- // same basic block.
- Value *AllocaPointerVal = 0;
- for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E;++U){
- Instruction *User = cast<Instruction>(*U);
- if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
- // Remember the basic blocks which define new values for the alloca
- DefiningBlocks.push_back(SI->getParent());
- AllocaPointerVal = SI->getOperand(0);
- OnlyStore = SI;
- } else {
- LoadInst *LI = cast<LoadInst>(User);
- // Otherwise it must be a load instruction, keep track of variable reads
- UsingBlocks.push_back(LI->getParent());
- AllocaPointerVal = LI;
- }
-
- if (OnlyUsedInOneBlock) {
- if (OnlyBlock == 0)
- OnlyBlock = User->getParent();
- else if (OnlyBlock != User->getParent())
- OnlyUsedInOneBlock = false;
- }
- }
+ Info.AnalyzeAlloca(AI);
// If the alloca is only read and written in one basic block, just perform a
// linear sweep over the block to eliminate it.
- if (OnlyUsedInOneBlock) {
- LocallyUsedAllocas[OnlyBlock].push_back(AI);
+ if (Info.OnlyUsedInOneBlock) {
+ LocallyUsedAllocas[Info.OnlyBlock].push_back(AI);
// Remove the alloca from the Allocas list, since it will be processed.
- Allocas[AllocaNum] = Allocas.back();
- Allocas.pop_back();
- --AllocaNum;
+ RemoveFromAllocasList(AllocaNum);
continue;
}
// If there is only a single store to this value, replace any loads of
// it that are directly dominated by the definition with the value stored.
- if (DefiningBlocks.size() == 1) {
- // Be aware of loads before the store.
- std::set<BasicBlock*> ProcessedBlocks;
- for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i)
- // If the store dominates the block and if we haven't processed it yet,
- // do so now.
- if (dominates(OnlyStore->getParent(), UsingBlocks[i]))
- if (ProcessedBlocks.insert(UsingBlocks[i]).second) {
- BasicBlock *UseBlock = UsingBlocks[i];
-
- // If the use and store are in the same block, do a quick scan to
- // verify that there are no uses before the store.
- if (UseBlock == OnlyStore->getParent()) {
- BasicBlock::iterator I = UseBlock->begin();
- for (; &*I != OnlyStore; ++I) { // scan block for store.
- if (isa<LoadInst>(I) && I->getOperand(0) == AI)
- break;
- }
- if (&*I != OnlyStore) break; // Do not handle this case.
- }
-
- // Otherwise, if this is a different block or if all uses happen
- // after the store, do a simple linear scan to replace loads with
- // the stored value.
- for (BasicBlock::iterator I = UseBlock->begin(),E = UseBlock->end();
- I != E; ) {
- if (LoadInst *LI = dyn_cast<LoadInst>(I++)) {
- if (LI->getOperand(0) == AI) {
- LI->replaceAllUsesWith(OnlyStore->getOperand(0));
- if (AST && isa<PointerType>(LI->getType()))
- AST->deleteValue(LI);
- LI->eraseFromParent();
- }
- }
- }
-
- // Finally, remove this block from the UsingBlock set.
- UsingBlocks[i] = UsingBlocks.back();
- --i; --e;
- }
+ if (Info.DefiningBlocks.size() == 1) {
+ RewriteSingleStoreAlloca(AI, Info);
// Finally, after the scan, check to see if the store is all that is left.
- if (UsingBlocks.empty()) {
+ if (Info.UsingBlocks.empty()) {
+ ++NumSingleStore;
// The alloca has been processed, move on.
- Allocas[AllocaNum] = Allocas.back();
- Allocas.pop_back();
- --AllocaNum;
+ RemoveFromAllocasList(AllocaNum);
continue;
}
}
if (AST)
- PointerAllocaValues[AllocaNum] = AllocaPointerVal;
+ PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal;
// If we haven't computed a numbering for the BB's in the function, do so
// now.
unsigned CurrentVersion = 0;
SmallPtrSet<PHINode*, 16> InsertedPHINodes;
std::vector<std::pair<unsigned, BasicBlock*> > DFBlocks;
- while (!DefiningBlocks.empty()) {
- BasicBlock *BB = DefiningBlocks.back();
- DefiningBlocks.pop_back();
+ while (!Info.DefiningBlocks.empty()) {
+ BasicBlock *BB = Info.DefiningBlocks.back();
+ Info.DefiningBlocks.pop_back();
// Look up the DF for this write, add it to PhiNodes
DominanceFrontier::const_iterator it = DF.find(BB);
for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) {
BasicBlock *BB = DFBlocks[i].second;
if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes))
- DefiningBlocks.push_back(BB);
+ Info.DefiningBlocks.push_back(BB);
}
DFBlocks.clear();
}
// marked alive because of loads which are dominated by stores, but there
// will be no unmarked PHI nodes which are actually used.
//
- for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i)
- MarkDominatingPHILive(UsingBlocks[i], AllocaNum, InsertedPHINodes);
- UsingBlocks.clear();
+ for (unsigned i = 0, e = Info.UsingBlocks.size(); i != e; ++i)
+ MarkDominatingPHILive(Info.UsingBlocks[i], AllocaNum, InsertedPHINodes);
+ Info.UsingBlocks.clear();
// If there are any PHI nodes which are now known to be dead, remove them!
for (SmallPtrSet<PHINode*, 16>::iterator I = InsertedPHINodes.begin(),
// the alloca's. We do this in case there is a load of a value that has not
// been stored yet. In this case, it will get this null value.
//
- std::vector<Value *> Values(Allocas.size());
+ RenamePassData::ValVector Values(Allocas.size());
for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
Values[i] = UndefValue::get(Allocas[i]->getAllocatedType());
// Walks all basic blocks in the function performing the SSA rename algorithm
// and inserting the phi nodes we marked as necessary
//
- RenamePassWorkList.clear();
+ std::vector<RenamePassData> RenamePassWorkList;
RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values));
- while(!RenamePassWorkList.empty()) {
- RenamePassData RPD = RenamePassWorkList.back();
+ while (!RenamePassWorkList.empty()) {
+ RenamePassData RPD;
+ RPD.swap(RenamePassWorkList.back());
RenamePassWorkList.pop_back();
// RenamePass may add new worklist entries.
- RenamePass(RPD.BB, RPD.Pred, RPD.Values);
+ RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList);
}
// The renamer uses the Visited set to avoid infinite loops. Clear it now.
NewPhiNodes.clear();
}
+
+/// RewriteSingleStoreAlloca - If there is only a single store to this value,
+/// replace any loads of it that are directly dominated by the definition with
+/// the value stored.
+void PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI,
+ AllocaInfo &Info) {
+ // Be aware of loads before the store.
+ std::set<BasicBlock*> ProcessedBlocks;
+ for (unsigned i = 0, e = Info.UsingBlocks.size(); i != e; ++i) {
+ // If the store dominates the block and if we haven't processed it yet,
+ // do so now.
+ if (!dominates(Info.OnlyStore->getParent(), Info.UsingBlocks[i]))
+ continue;
+
+ if (!ProcessedBlocks.insert(Info.UsingBlocks[i]).second)
+ continue;
+
+ BasicBlock *UseBlock = Info.UsingBlocks[i];
+
+ // If the use and store are in the same block, do a quick scan to
+ // verify that there are no uses before the store.
+ if (UseBlock == Info.OnlyStore->getParent()) {
+ BasicBlock::iterator I = UseBlock->begin();
+ for (; &*I != Info.OnlyStore; ++I) { // scan block for store.
+ if (isa<LoadInst>(I) && I->getOperand(0) == AI)
+ break;
+ }
+ if (&*I != Info.OnlyStore) break; // Do not handle this case.
+ }
+
+ // Otherwise, if this is a different block or if all uses happen
+ // after the store, do a simple linear scan to replace loads with
+ // the stored value.
+ for (BasicBlock::iterator I = UseBlock->begin(),E = UseBlock->end();
+ I != E; ) {
+ if (LoadInst *LI = dyn_cast<LoadInst>(I++)) {
+ if (LI->getOperand(0) == AI) {
+ LI->replaceAllUsesWith(Info.OnlyStore->getOperand(0));
+ if (AST && isa<PointerType>(LI->getType()))
+ AST->deleteValue(LI);
+ LI->eraseFromParent();
+ }
+ }
+ }
+
+ // Finally, remove this block from the UsingBlock set.
+ Info.UsingBlocks[i] = Info.UsingBlocks.back();
+ --i; --e;
+ }
+}
+
+
// MarkDominatingPHILive - Mem2Reg wants to construct "pruned" SSA form, not
// "minimal" SSA form. To do this, it inserts all of the PHI nodes on the IDF
// as usual (inserting the PHI nodes in the DeadPHINodes set), then processes
SmallPtrSet<PHINode*, 16> &DeadPHINodes) {
// Scan the immediate dominators of this block looking for a block which has a
// PHI node for Alloca num. If we find it, mark the PHI node as being alive!
- for (BasicBlock* DomBB = BB; DomBB; DomBB = ET.getIDom(DomBB)) {
+ DomTreeNode *IDomNode = DT.getNode(BB);
+ for (DomTreeNode *IDom = IDomNode; IDom; IDom = IDom->getIDom()) {
+ BasicBlock *DomBB = IDom->getBlock();
DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator
I = NewPhiNodes.find(std::make_pair(DomBB, AllocaNum));
if (I != NewPhiNodes.end()) {
assert(AI->use_empty() && "Uses of alloca from more than one BB??");
if (AST) AST->deleteValue(AI);
AI->getParent()->getInstList().erase(AI);
+
+ ++NumLocalPromoted;
return false;
}
// value each Alloca contains on exit from the predecessor block Pred.
//
void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
- std::vector<Value*> &IncomingVals) {
+ RenamePassData::ValVector &IncomingVals,
+ std::vector<RenamePassData> &Worklist) {
// If we are inserting any phi nodes into this BB, they will already be in the
// block.
if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) {
// Recurse to our successors.
TerminatorInst *TI = BB->getTerminator();
for (unsigned i = 0; i != TI->getNumSuccessors(); i++)
- RenamePassWorkList.push_back(RenamePassData(TI->getSuccessor(i), BB, IncomingVals));
+ Worklist.push_back(RenamePassData(TI->getSuccessor(i), BB, IncomingVals));
}
/// PromoteMemToReg - Promote the specified list of alloca instructions into
/// made to the IR.
///
void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
- ETForest &ET, DominanceFrontier &DF,
- const TargetData &TD, AliasSetTracker *AST) {
+ DominatorTree &DT, DominanceFrontier &DF,
+ AliasSetTracker *AST) {
// If there is nothing to do, bail out...
if (Allocas.empty()) return;
SmallVector<AllocaInst*, 16> RetryList;
- PromoteMem2Reg(Allocas, RetryList, ET, DF, TD, AST).run();
+ PromoteMem2Reg(Allocas, RetryList, DT, DF, AST).run();
// PromoteMem2Reg may not have been able to promote all of the allocas in one
// pass, run it again if needed.
NewAllocas.assign(RetryList.begin(), RetryList.end());
RetryList.clear();
- PromoteMem2Reg(NewAllocas, RetryList, ET, DF, TD, AST).run();
+ PromoteMem2Reg(NewAllocas, RetryList, DT, DF, AST).run();
NewAllocas.clear();
}
}
projects / oota-llvm.git / blobdiff