#define DEBUG_TYPE "lcssa"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Constants.h"
-#include "llvm/Pass.h"
-#include "llvm/Function.h"
-#include "llvm/Instructions.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Transforms/Utils/SSAUpdater.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
#include "llvm/Support/PredIteratorCache.h"
+#include "llvm/Transforms/Utils/SSAUpdater.h"
using namespace llvm;
STATISTIC(NumLCSSA, "Number of live out of a loop variables");
namespace {
struct LCSSA : public LoopPass {
static char ID; // Pass identification, replacement for typeid
- LCSSA() : LoopPass(&ID) {}
+ LCSSA() : LoopPass(ID) {
+ initializeLCSSAPass(*PassRegistry::getPassRegistry());
+ }
// Cached analysis information for the current function.
DominatorTree *DT;
+ LoopInfo *LI;
+ ScalarEvolution *SE;
std::vector<BasicBlock*> LoopBlocks;
PredIteratorCache PredCache;
Loop *L;
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
- // LCSSA doesn't actually require LoopSimplify, but the PassManager
- // doesn't know how to schedule LoopSimplify by itself.
- AU.addRequiredID(LoopSimplifyID);
+ AU.addRequired<DominatorTree>();
+ AU.addRequired<LoopInfo>();
AU.addPreservedID(LoopSimplifyID);
- AU.addRequiredTransitive<LoopInfo>();
- AU.addPreserved<LoopInfo>();
- AU.addRequiredTransitive<DominatorTree>();
AU.addPreserved<ScalarEvolution>();
- AU.addPreserved<DominatorTree>();
-
- // Request DominanceFrontier now, even though LCSSA does
- // not use it. This allows Pass Manager to schedule Dominance
- // Frontier early enough such that one LPPassManager can handle
- // multiple loop transformation passes.
- AU.addRequired<DominanceFrontier>();
- AU.addPreserved<DominanceFrontier>();
}
private:
bool ProcessInstruction(Instruction *Inst,
/// verifyAnalysis() - Verify loop nest.
virtual void verifyAnalysis() const {
// Check the special guarantees that LCSSA makes.
- assert(L->isLCSSAForm() && "LCSSA form not preserved!");
+ assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!");
}
/// inLoop - returns true if the given block is within the current loop
}
char LCSSA::ID = 0;
-static RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
+INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTree)
+INITIALIZE_PASS_DEPENDENCY(LoopInfo)
+INITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
Pass *llvm::createLCSSAPass() { return new LCSSA(); }
-const PassInfo *const llvm::LCSSAID = &X;
+char &llvm::LCSSAID = LCSSA::ID;
/// BlockDominatesAnExit - Return true if the specified block dominates at least
L = TheLoop;
DT = &getAnalysis<DominatorTree>();
+ LI = &getAnalysis<LoopInfo>();
+ SE = getAnalysisIfAvailable<ScalarEvolution>();
// Get the set of exiting blocks.
SmallVector<BasicBlock*, 8> ExitBlocks;
MadeChange |= ProcessInstruction(I, ExitBlocks);
}
}
+
+ // If we modified the code, remove any caches about the loop from SCEV to
+ // avoid dangling entries.
+ // FIXME: This is a big hammer, can we clear the cache more selectively?
+ if (SE && MadeChange)
+ SE->forgetLoop(L);
- assert(L->isLCSSAForm());
+ assert(L->isLCSSAForm(*DT));
PredCache.clear();
return MadeChange;
for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end();
UI != E; ++UI) {
- BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
- if (PHINode *PN = dyn_cast<PHINode>(*UI))
+ User *U = *UI;
+ BasicBlock *UserBB = cast<Instruction>(U)->getParent();
+ if (PHINode *PN = dyn_cast<PHINode>(U))
UserBB = PN->getIncomingBlock(UI);
if (InstBB != UserBB && !inLoop(UserBB))
UsesToRewrite.push_back(&UI.getUse());
}
-
+
// If there are no uses outside the loop, exit with no change.
if (UsesToRewrite.empty()) return false;
DomTreeNode *DomNode = DT->getNode(DomBB);
+ SmallVector<PHINode*, 16> AddedPHIs;
+
SSAUpdater SSAUpdate;
- SSAUpdate.Initialize(Inst);
+ SSAUpdate.Initialize(Inst->getType(), Inst->getName());
// Insert the LCSSA phi's into all of the exit blocks dominated by the
// value, and add them to the Phi's map.
// If we already inserted something for this BB, don't reprocess it.
if (SSAUpdate.HasValueForBlock(ExitBB)) continue;
- PHINode *PN = PHINode::Create(Inst->getType(), Inst->getName()+".lcssa",
+ PHINode *PN = PHINode::Create(Inst->getType(),
+ PredCache.GetNumPreds(ExitBB),
+ Inst->getName()+".lcssa",
ExitBB->begin());
- PN->reserveOperandSpace(PredCache.GetNumPreds(ExitBB));
// Add inputs from inside the loop for this PHI.
for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) {
PN->addIncoming(Inst, *PI);
// If the exit block has a predecessor not within the loop, arrange for
- // the incomging value use corresponding to that predecessor to be
+ // the incoming value use corresponding to that predecessor to be
// rewritten in terms of a different LCSSA PHI.
if (!inLoop(*PI))
UsesToRewrite.push_back(
&PN->getOperandUse(
PN->getOperandNumForIncomingValue(PN->getNumIncomingValues()-1)));
}
+
+ AddedPHIs.push_back(PN);
// Remember that this phi makes the value alive in this block.
SSAUpdate.AddAvailableValue(ExitBB, PN);
}
-
+
// Rewrite all uses outside the loop in terms of the new PHIs we just
// inserted.
for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) {
if (isa<PHINode>(UserBB->begin()) &&
isExitBlock(UserBB, ExitBlocks)) {
+ // Tell the VHs that the uses changed. This updates SCEV's caches.
+ if (UsesToRewrite[i]->get()->hasValueHandle())
+ ValueHandleBase::ValueIsRAUWd(*UsesToRewrite[i], UserBB->begin());
UsesToRewrite[i]->set(UserBB->begin());
continue;
}
// Otherwise, do full PHI insertion.
SSAUpdate.RewriteUse(*UsesToRewrite[i]);
}
+
+ // Remove PHI nodes that did not have any uses rewritten.
+ for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) {
+ if (AddedPHIs[i]->use_empty())
+ AddedPHIs[i]->eraseFromParent();
+ }
return true;
}
projects / oota-llvm.git / blobdiff