#include "llvm/Instructions.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/AliasSetTracker.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/StableBasicBlockNumbering.h"
+#include "llvm/Support/Compiler.h"
#include <algorithm>
using namespace llvm;
}
namespace {
- struct PromoteMem2Reg {
+ struct VISIBILITY_HIDDEN PromoteMem2Reg {
/// Allocas - The alloca instructions being promoted.
///
std::vector<AllocaInst*> Allocas;
- std::vector<AllocaInst*> &RetryList;
+ SmallVector<AllocaInst*, 16> &RetryList;
DominatorTree &DT;
DominanceFrontier &DF;
const TargetData &TD;
public:
PromoteMem2Reg(const std::vector<AllocaInst*> &A,
- std::vector<AllocaInst*> &Retry, DominatorTree &dt,
+ SmallVector<AllocaInst*, 16> &Retry, DominatorTree &dt,
DominanceFrontier &df, const TargetData &td,
AliasSetTracker *ast)
: Allocas(A), RetryList(Retry), DT(dt), DF(df), TD(td), AST(ast) {}
if (AI->use_empty()) {
// If there are no uses of the alloca, just delete it now.
if (AST) AST->deleteValue(AI);
- AI->getParent()->getInstList().erase(AI);
+ AI->eraseFromParent();
// Remove the alloca from the Allocas list, since it has been processed
Allocas[AllocaNum] = Allocas.back();
std::vector<BasicBlock*> DefiningBlocks;
std::vector<BasicBlock*> UsingBlocks;
+ StoreInst *OnlyStore = 0;
BasicBlock *OnlyBlock = 0;
bool OnlyUsedInOneBlock = true;
// 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
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;
+ }
+
+ // Finally, after the scan, check to see if the store is all that is left.
+ if (UsingBlocks.empty()) {
+ // The alloca has been processed, move on.
+ Allocas[AllocaNum] = Allocas.back();
+ Allocas.pop_back();
+ --AllocaNum;
+ continue;
+ }
+ }
+
if (AST)
PointerAllocaValues[AllocaNum] = AllocaPointerVal;
if (AST && isa<PointerType>(PN->getType()))
AST->deleteValue(PN);
- PN->getParent()->getInstList().erase(PN);
+ PN->eraseFromParent();
}
// Keep the reverse mapping of the 'Allocas' array.
// The renamer uses the Visited set to avoid infinite loops. Clear it now.
Visited.clear();
- // Remove the allocas themselves from the function...
+ // Remove the allocas themselves from the function.
for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
Instruction *A = Allocas[i];
if (!A->use_empty())
A->replaceAllUsesWith(UndefValue::get(A->getType()));
if (AST) AST->deleteValue(A);
- A->getParent()->getInstList().erase(A);
+ A->eraseFromParent();
}
+
+ // Loop over all of the PHI nodes and see if there are any that we can get
+ // rid of because they merge all of the same incoming values. This can
+ // happen due to undef values coming into the PHI nodes. This process is
+ // iterative, because eliminating one PHI node can cause others to be removed.
+ bool EliminatedAPHI = true;
+ while (EliminatedAPHI) {
+ EliminatedAPHI = false;
+
+ for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I =
+ NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) {
+ std::vector<PHINode*> &PNs = I->second;
+ for (unsigned i = 0, e = PNs.size(); i != e; ++i) {
+ if (!PNs[i]) continue;
+
+ // If this PHI node merges one value and/or undefs, get the value.
+ if (Value *V = PNs[i]->hasConstantValue(true)) {
+ if (!isa<Instruction>(V) ||
+ properlyDominates(cast<Instruction>(V), PNs[i])) {
+ if (AST && isa<PointerType>(PNs[i]->getType()))
+ AST->deleteValue(PNs[i]);
+ PNs[i]->replaceAllUsesWith(V);
+ PNs[i]->eraseFromParent();
+ PNs[i] = 0;
+ EliminatedAPHI = true;
+ continue;
+ }
+ }
+ }
+ }
+ }
+
// At this point, the renamer has added entries to PHI nodes for all reachable
// code. Unfortunately, there may be blocks which are not reachable, which
// the renamer hasn't traversed. If this is the case, the PHI nodes may not
std::vector<BasicBlock*> Preds(pred_begin(I->first), pred_end(I->first));
std::vector<PHINode*> &PNs = I->second;
assert(!PNs.empty() && "Empty PHI node list??");
-
- // Loop over all of the PHI nodes and see if there are any that we can get
- // rid of because they merge all of the same incoming values. This can
- // happen due to undef values coming into the PHI nodes.
PHINode *SomePHI = 0;
for (unsigned i = 0, e = PNs.size(); i != e; ++i)
if (PNs[i]) {
- if (Value *V = PNs[i]->hasConstantValue(true)) {
- if (!isa<Instruction>(V) ||
- properlyDominates(cast<Instruction>(V), PNs[i])) {
- if (AST && isa<PointerType>(PNs[i]->getType()))
- AST->deleteValue(PNs[i]);
- PNs[i]->replaceAllUsesWith(V);
- PNs[i]->eraseFromParent();
- PNs[i] = 0;
- }
- }
- if (PNs[i])
- SomePHI = PNs[i];
+ SomePHI = PNs[i];
+ break;
}
// Only do work here if there the PHI nodes are missing incoming values. We
// If there is nothing to do, bail out...
if (Allocas.empty()) return;
- std::vector<AllocaInst*> RetryList;
+ SmallVector<AllocaInst*, 16> RetryList;
PromoteMem2Reg(Allocas, RetryList, DT, DF, TD, AST).run();
// PromoteMem2Reg may not have been able to promote all of the allocas in one
// pass, run it again if needed.
+ std::vector<AllocaInst*> NewAllocas;
while (!RetryList.empty()) {
// If we need to retry some allocas, this is due to there being no store
// before a read in a local block. To counteract this, insert a store of
RetryList[i], ++BBI);
}
- std::vector<AllocaInst*> NewAllocas;
- std::swap(NewAllocas, RetryList);
+ NewAllocas.assign(RetryList.begin(), RetryList.end());
+ RetryList.clear();
PromoteMem2Reg(NewAllocas, RetryList, DT, DF, TD, AST).run();
+ NewAllocas.clear();
}
}
projects / oota-llvm.git / blobdiff