// else else
// X2 = ... X2 = ...
// X3 = phi(X1, X2) X3 = phi(X1, X2)
-// ... = X3 + 4 X4 = phi(X3)
-// ... = X4 + 4
+// ... = X3 + 4 X4 = phi(X3)
+// ... = X4 + 4
//
// This is still valid LLVM; the extra phi nodes are purely redundant, and will
// be trivially eliminated by InstCombine. The major benefit of this
namespace {
struct VISIBILITY_HIDDEN LCSSA : public LoopPass {
static char ID; // Pass identification, replacement for typeid
- LCSSA() : LoopPass((intptr_t)&ID) {}
+ LCSSA() : LoopPass(&ID) {}
// Cached analysis information for the current function.
LoopInfo *LI;
SetVector<Instruction*> &AffectedValues);
Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst,
- std::map<DomTreeNode*, Value*> &Phis);
+ DenseMap<DomTreeNode*, Value*> &Phis);
/// inLoop - returns true if the given block is within the current loop
bool inLoop(BasicBlock* B) {
return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
}
};
-
- char LCSSA::ID = 0;
- RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
}
+
+char LCSSA::ID = 0;
+static RegisterPass<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
-LoopPass *llvm::createLCSSAPass() { return new LCSSA(); }
-const PassInfo *llvm::LCSSAID = X.getPassInfo();
+Pass *llvm::createLCSSAPass() { return new LCSSA(); }
+const PassInfo *const llvm::LCSSAID = &X;
/// runOnFunction - Process all loops in the function, inner-most out.
bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) {
++NumLCSSA; // We are applying the transformation
// Keep track of the blocks that have the value available already.
- std::map<DomTreeNode*, Value*> Phis;
+ DenseMap<DomTreeNode*, Value*> Phis;
DomTreeNode *InstrNode = DT->getNode(Instr->getParent());
UI != E;) {
BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
if (PHINode *P = dyn_cast<PHINode>(*UI)) {
- unsigned OperandNo = UI.getOperandNo();
- UserBB = P->getIncomingBlock(OperandNo/2);
+ UserBB = P->getIncomingBlock(UI);
}
// If the user is in the loop, don't rewrite it!
++UI) {
BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
if (PHINode* p = dyn_cast<PHINode>(*UI)) {
- unsigned OperandNo = UI.getOperandNo();
- UserBB = p->getIncomingBlock(OperandNo/2);
+ UserBB = p->getIncomingBlock(UI);
}
if (*BB != UserBB && !inLoop(UserBB)) {
/// GetValueForBlock - Get the value to use within the specified basic block.
/// available values are in Phis.
Value *LCSSA::GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst,
- std::map<DomTreeNode*, Value*> &Phis) {
+ DenseMap<DomTreeNode*, Value*> &Phis) {
// If there is no dominator info for this BB, it is unreachable.
if (BB == 0)
return UndefValue::get(OrigInst->getType());
// If we have already computed this value, return the previously computed val.
- Value *&V = Phis[BB];
- if (V) return V;
+ if (Phis.count(BB)) return Phis[BB];
DomTreeNode *IDom = BB->getIDom();
if (!inLoop(IDom->getBlock())) {
// Idom is not in the loop, we must still be "below" the exit block and must
// be fully dominated by the value live in the idom.
- return V = GetValueForBlock(IDom, OrigInst, Phis);
+ Value* val = GetValueForBlock(IDom, OrigInst, Phis);
+ Phis.insert(std::make_pair(BB, val));
+ return val;
}
BasicBlock *BBN = BB->getBlock();
// Otherwise, the idom is the loop, so we need to insert a PHI node. Do so
// now, then get values to fill in the incoming values for the PHI.
- PHINode *PN = PHINode::Create(OrigInst->getType(), OrigInst->getName()+".lcssa",
- BBN->begin());
+ PHINode *PN = PHINode::Create(OrigInst->getType(),
+ OrigInst->getName() + ".lcssa", BBN->begin());
PN->reserveOperandSpace(std::distance(pred_begin(BBN), pred_end(BBN)));
- V = PN;
+ Phis.insert(std::make_pair(BB, PN));
// Fill in the incoming values for the block.
for (pred_iterator PI = pred_begin(BBN), E = pred_end(BBN); PI != E; ++PI)