//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar.h"
+#include "llvm/Constants.h"
#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
LoopInfo *LI; // Loop information
- DominatorTree *DT; // Dominator Tree for the current Loop...
+ DominatorTree *DT; // Dominator Tree for the current Function...
DominanceFrontier *DF; // Current Dominance Frontier
- std::vector<BasicBlock*> *LoopBlocks;
+ std::vector<BasicBlock*> LoopBlocks;
virtual bool runOnFunction(Function &F);
bool visitSubloop(Loop* L);
}
private:
SetVector<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L);
- Instruction *getValueDominatingBlock(BasicBlock *BB,
- std::map<BasicBlock*, Instruction*>& PotDoms);
-
- bool inLoopBlocks(BasicBlock* B) { return std::binary_search(
- LoopBlocks->begin(), LoopBlocks->end(), B); }
+ Value *getValueDominatingBlock(BasicBlock *BB,
+ std::map<BasicBlock*, Value*>& PotDoms) {
+ return getValueDominatingDTNode(DT->getNode(BB), PotDoms);
+ }
+ Value *getValueDominatingDTNode(DominatorTree::Node *Node,
+ std::map<BasicBlock*, Value*>& PotDoms);
+
+ /// inLoop - returns true if the given block is within the current loop
+ const bool inLoop(BasicBlock* B) {
+ return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
+ }
};
RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
}
FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); }
+const PassInfo *llvm::LCSSAID = X.getPassInfo();
+/// runOnFunction - Process all loops in the function, inner-most out.
bool LCSSA::runOnFunction(Function &F) {
bool changed = false;
+
LI = &getAnalysis<LoopInfo>();
DF = &getAnalysis<DominanceFrontier>();
DT = &getAnalysis<DominatorTree>();
- LoopBlocks = new std::vector<BasicBlock*>;
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
changed |= visitSubloop(*I);
return changed;
}
+/// visitSubloop - Recursively process all subloops, and then process the given
+/// loop if it has live-out values.
bool LCSSA::visitSubloop(Loop* L) {
for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
visitSubloop(*I);
-
+
// Speed up queries by creating a sorted list of blocks
- LoopBlocks->clear();
- LoopBlocks->insert(LoopBlocks->end(), L->block_begin(), L->block_end());
- std::sort(LoopBlocks->begin(), LoopBlocks->end());
+ LoopBlocks.clear();
+ LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
+ std::sort(LoopBlocks.begin(), LoopBlocks.end());
SetVector<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L);
processInstruction(*I, exitBlocks);
}
- return true; // FIXME: Should be more intelligent in our return value.
+ assert(L->isLCSSAForm());
+
+ return true;
}
-/// processInstruction -
+/// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes,
+/// eliminate all out-of-loop uses.
void LCSSA::processInstruction(Instruction* Instr,
const std::vector<BasicBlock*>& exitBlocks)
{
++NumLCSSA; // We are applying the transformation
- std::map<BasicBlock*, Instruction*> Phis;
+ std::map<BasicBlock*, Value*> Phis;
// Add the base instruction to the Phis list. This makes tracking down
// the dominating values easier when we're filling in Phi nodes. This will
std::vector<PHINode*> workList;
for (std::vector<BasicBlock*>::const_iterator BBI = exitBlocks.begin(),
- BBE = exitBlocks.end(); BBI != BBE; ++BBI)
- if (DT->getNode(Instr->getParent())->dominates(DT->getNode(*BBI))) {
- PHINode *phi = new PHINode(Instr->getType(), "lcssa", (*BBI)->begin());
- workList.push_back(phi);
- Phis[*BBI] = phi;
+ BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
+ Value*& phi = Phis[*BBI];
+ if (phi == 0 &&
+ DT->getNode(Instr->getParent())->dominates(DT->getNode(*BBI))) {
+ phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa",
+ (*BBI)->begin());
+ workList.push_back(cast<PHINode>(phi));
}
+ }
// Phi nodes that need to have their incoming values filled.
std::vector<PHINode*> needIncomingValues;
const DominanceFrontier::DomSetType &S = it->second;
for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
PE = S.end(); P != PE; ++P) {
- Instruction *&Phi = Phis[*P];
- if (Phi == 0) {
- // Still doesn't have operands...
- Phi = new PHINode(Instr->getType(), "lcssa", (*P)->begin());
+ if (DT->getNode(Instr->getParent())->dominates(DT->getNode(*P))) {
+ Value *&Phi = Phis[*P];
+ if (Phi == 0) {
+ // Still doesn't have operands...
+ Phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa",
+ (*P)->begin());
- workList.push_back(cast<PHINode>(Phi));
+ workList.push_back(cast<PHINode>(Phi));
+ }
}
}
}
// Fill in all Phis we've inserted that need their incoming values filled in.
for (std::vector<PHINode*>::iterator IVI = needIncomingValues.begin(),
- IVE = needIncomingValues.end(); IVI != IVE; ++IVI) {
+ IVE = needIncomingValues.end(); IVI != IVE; ++IVI)
for (pred_iterator PI = pred_begin((*IVI)->getParent()),
E = pred_end((*IVI)->getParent()); PI != E; ++PI)
(*IVI)->addIncoming(getValueDominatingBlock(*PI, Phis),
*PI);
- }
// Find all uses of the affected value, and replace them with the
// appropriate Phi.
for (Instruction::use_iterator UI = Instr->use_begin(), UE = Instr->use_end();
UI != UE; ++UI) {
Instruction* use = cast<Instruction>(*UI);
- // Don't need to update uses within the loop body, and we don't want to
- // overwrite the Phi nodes that we inserted into the exit blocks either.
- if (!inLoopBlocks(use->getParent()) &&
- !(std::binary_search(exitBlocks.begin(), exitBlocks.end(),
- use->getParent()) && isa<PHINode>(use)))
+ BasicBlock* UserBB = use->getParent();
+ if (PHINode* p = dyn_cast<PHINode>(use)) {
+ unsigned OperandNo = UI.getOperandNo();
+ UserBB = p->getIncomingBlock(OperandNo/2);
+ }
+
+ // Don't need to update uses within the loop body.
+ if (!inLoop(use->getParent()))
Uses.push_back(use);
}
- // Deliberately remove the initial instruction from Phis set. It would mess
- // up use-replacement.
- Phis.erase(Instr->getParent());
-
for (std::vector<Instruction*>::iterator II = Uses.begin(), IE = Uses.end();
II != IE; ++II) {
if (PHINode* phi = dyn_cast<PHINode>(*II)) {
for (unsigned int i = 0; i < phi->getNumIncomingValues(); ++i) {
if (phi->getIncomingValue(i) == Instr) {
- Instruction* dominator =
+ Value* dominator =
getValueDominatingBlock(phi->getIncomingBlock(i), Phis);
phi->setIncomingValue(i, dominator);
}
}
} else {
- Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis);
- (*II)->replaceUsesOfWith(Instr, NewVal);
+ Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis);
+ (*II)->replaceUsesOfWith(Instr, NewVal);
}
}
}
for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
++UI) {
BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
- if (!std::binary_search(LoopBlocks->begin(), LoopBlocks->end(), UserBB))
- {
+ if (PHINode* p = dyn_cast<PHINode>(*UI)) {
+ unsigned OperandNo = UI.getOperandNo();
+ UserBB = p->getIncomingBlock(OperandNo/2);
+ }
+
+ if (!inLoop(UserBB)) {
AffectedValues.insert(I);
break;
}
return AffectedValues;
}
-Instruction *LCSSA::getValueDominatingBlock(BasicBlock *BB,
- std::map<BasicBlock*, Instruction*>& PotDoms) {
- DominatorTree::Node* bbNode = DT->getNode(BB);
- while (bbNode != 0) {
- std::map<BasicBlock*, Instruction*>::iterator I =
- PotDoms.find(bbNode->getBlock());
- if (I != PotDoms.end()) {
- return (*I).second;
- }
- bbNode = bbNode->getIDom();
- }
+/// getValueDominatingBlock - Return the value within the potential dominators
+/// map that dominates the given block.
+Value *LCSSA::getValueDominatingDTNode(DominatorTree::Node *Node,
+ std::map<BasicBlock*, Value*>& PotDoms) {
+ // FIXME: The following insertion should be in place rather than the if
+ // statement. Currently, this is due to the fact that LCSSA isn't smart
+ // enough to avoid inserting IDF Phis that don't dominate any uses. In some
+ // of those cases, it could ask us to provide a dominating value for a block
+ // that has none, so we need to return undef.
+ //assert(Node != 0 && "Didn't find dom value?");
+ if (Node == 0) return UndefValue::get(PotDoms.begin()->second->getType());
- assert(0 && "No dominating value found.");
+ Value *&CacheSlot = PotDoms[Node->getBlock()];
+ if (CacheSlot) return CacheSlot;
- return 0;
+ // Otherwise, return the value of the idom and remember this for next time.
+ return CacheSlot = getValueDominatingDTNode(Node->getIDom(), PotDoms);
}
projects / oota-llvm.git / blobdiff