//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "loopsimplify"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constant.h"
#include "llvm/Instructions.h"
#include "llvm/ADT/DepthFirstIterator.h"
using namespace llvm;
-namespace {
- Statistic
- NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted");
- Statistic
- NumNested("loopsimplify", "Number of nested loops split out");
+STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
+STATISTIC(NumNested , "Number of nested loops split out");
+namespace {
struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass {
// AA - If we have an alias analysis object to update, this is it, otherwise
// this is null.
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
// We need loop information to identify the loops...
AU.addRequired<LoopInfo>();
- AU.addRequired<DominatorSet>();
AU.addRequired<DominatorTree>();
+ AU.addRequired<ETForest>();
AU.addPreserved<LoopInfo>();
- AU.addPreserved<DominatorSet>();
AU.addPreserved<ImmediateDominators>();
AU.addPreserved<ETForest>();
AU.addPreserved<DominatorTree>();
// Can we eliminate this phi node now?
if (Value *V = PN->hasConstantValue(true)) {
- if (!isa<Instruction>(V) ||
- getAnalysis<DominatorSet>().dominates(cast<Instruction>(V), PN)) {
+ Instruction *I = dyn_cast<Instruction>(V);
+ // If I is in NewBB, the ETForest call will fail, because NewBB isn't
+ // registered in ETForest yet. Handle this case explicitly.
+ if (!I || (I->getParent() != NewBB &&
+ getAnalysis<ETForest>().dominates(I, PN))) {
PN->replaceAllUsesWith(V);
if (AA) AA->deleteValue(PN);
BB->getInstList().erase(PN);
/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
/// PHI node that tells us how to partition the loops.
-static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS,
+static PHINode *FindPHIToPartitionLoops(Loop *L, ETForest *EF,
AliasAnalysis *AA) {
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
PHINode *PN = cast<PHINode>(I);
++I;
if (Value *V = PN->hasConstantValue())
- if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) {
+ if (!isa<Instruction>(V) || EF->dominates(cast<Instruction>(V), PN)) {
// This is a degenerate PHI already, don't modify it!
PN->replaceAllUsesWith(V);
if (AA) AA->deleteValue(PN);
/// created.
///
Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
- PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>(), AA);
+ ETForest *EF = getAnalysisToUpdate<ETForest>();
+ PHINode *PN = FindPHIToPartitionLoops(L, EF, AA);
if (PN == 0) return 0; // No known way to partition.
// Pull out all predecessors that have varying values in the loop. This
// Determine which blocks should stay in L and which should be moved out to
// the Outer loop now.
- DominatorSet &DS = getAnalysis<DominatorSet>();
std::set<BasicBlock*> BlocksInL;
for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI)
- if (DS.dominates(Header, *PI))
+ if (EF->dominates(Header, *PI))
AddBlockAndPredsToSet(*PI, Header, BlocksInL);
UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks);
}
+// Returns true if BasicBlock A dominates at least one block in vector B
+// Helper function for UpdateDomInfoForRevectoredPreds
+static bool BlockDominatesAny(BasicBlock* A, const std::vector<BasicBlock*>& B, const ETForest& ETF) {
+ for (std::vector<BasicBlock*>::iterator BI = B.begin(), BE = B.end(); BI != BE; ++BI) {
+ if (ETF.dominates(A, *BI))
+ return true;
+ }
+ return false;
+}
+
/// UpdateDomInfoForRevectoredPreds - This method is used to update the four
-/// different kinds of dominator information (dominator sets, immediate
-/// dominators, dominator trees, and dominance frontiers) after a new block has
+/// different kinds of dominator information (immediate dominators,
+/// dominator trees, et-forest and dominance frontiers) after a new block has
/// been added to the CFG.
///
/// This only supports the case when an existing block (known as "NewBBSucc"),
++succ_begin(NewBB) == succ_end(NewBB) &&
"NewBB should have a single successor!");
BasicBlock *NewBBSucc = *succ_begin(NewBB);
- DominatorSet &DS = getAnalysis<DominatorSet>();
-
- // Update dominator information... The blocks that dominate NewBB are the
- // intersection of the dominators of predecessors, plus the block itself.
- //
- DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]);
- {
- unsigned i, e = PredBlocks.size();
- // It is possible for some preds to not be reachable, and thus have empty
- // dominator sets (all blocks must dom themselves, so no domset would
- // otherwise be empty). If we see any of these, don't intersect with them,
- // as that would certainly leave the resultant set empty.
- for (i = 1; NewBBDomSet.empty(); ++i) {
- assert(i != e && "Didn't find reachable pred?");
- NewBBDomSet = DS.getDominators(PredBlocks[i]);
- }
-
- // Intersect the rest of the non-empty sets.
- for (; i != e; ++i) {
- const DominatorSet::DomSetType &PredDS = DS.getDominators(PredBlocks[i]);
- if (!PredDS.empty())
- set_intersect(NewBBDomSet, PredDS);
- }
- NewBBDomSet.insert(NewBB); // All blocks dominate themselves.
- DS.addBasicBlock(NewBB, NewBBDomSet);
- }
-
+ ETForest& ETF = getAnalysis<ETForest>();
+
// The newly inserted basic block will dominate existing basic blocks iff the
// PredBlocks dominate all of the non-pred blocks. If all predblocks dominate
// the non-pred blocks, then they all must be the same block!
bool NewBBDominatesNewBBSucc = true;
{
BasicBlock *OnePred = PredBlocks[0];
- unsigned i, e = PredBlocks.size();
- for (i = 1; !DS.isReachable(OnePred); ++i) {
+ unsigned i = 1, e = PredBlocks.size();
+ for (i = 1; !ETF.isReachableFromEntry(OnePred); ++i) {
assert(i != e && "Didn't find reachable pred?");
OnePred = PredBlocks[i];
}
for (; i != e; ++i)
- if (PredBlocks[i] != OnePred && DS.isReachable(PredBlocks[i])) {
+ if (PredBlocks[i] != OnePred && ETF.isReachableFromEntry(OnePred)){
NewBBDominatesNewBBSucc = false;
break;
}
if (NewBBDominatesNewBBSucc)
for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
PI != E; ++PI)
- if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
+ if (*PI != NewBB && !ETF.dominates(NewBBSucc, *PI)) {
NewBBDominatesNewBBSucc = false;
break;
}
NewBBDominatesNewBBSucc = true;
for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc);
PI != E; ++PI)
- if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) {
+ if (*PI != NewBB && !ETF.dominates(NewBBSucc, *PI)) {
NewBBDominatesNewBBSucc = false;
break;
}
}
- // If NewBB dominates some blocks, then it will dominate all blocks that
- // NewBBSucc does.
- if (NewBBDominatesNewBBSucc) {
- Function *F = NewBB->getParent();
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
- if (DS.dominates(NewBBSucc, I))
- DS.addDominator(I, NewBB);
- }
-
- // Update immediate dominator information if we have it.
BasicBlock *NewBBIDom = 0;
+
+ // Update immediate dominator information if we have it.
if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
- // To find the immediate dominator of the new exit node, we trace up the
- // immediate dominators of a predecessor until we find a basic block that
- // dominates the exit block.
- //
- BasicBlock *Dom = PredBlocks[0]; // Some random predecessor.
-
- // Find a reachable pred.
- for (unsigned i = 1; !DS.isReachable(Dom); ++i) {
- assert(i != PredBlocks.size() && "Didn't find reachable pred!");
- Dom = PredBlocks[i];
- }
-
- while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator.
- assert(Dom != 0 && "No shared dominator found???");
- Dom = ID->get(Dom);
+ unsigned i = 0;
+ for (i = 0; i < PredBlocks.size(); ++i)
+ if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) {
+ NewBBIDom = PredBlocks[i];
+ break;
+ }
+ assert(i != PredBlocks.size() && "No reachable preds?");
+ for (i = i + 1; i < PredBlocks.size(); ++i) {
+ if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i]))
+ NewBBIDom = ETF.nearestCommonDominator(NewBBIDom, PredBlocks[i]);
}
-
+ assert(NewBBIDom && "No immediate dominator found??");
+
// Set the immediate dominator now...
- ID->addNewBlock(NewBB, Dom);
- NewBBIDom = Dom; // Reuse this if calculating DominatorTree info...
+ ID->addNewBlock(NewBB, NewBBIDom);
// If NewBB strictly dominates other blocks, we need to update their idom's
// now. The only block that need adjustment is the NewBBSucc block, whose
if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
// If we don't have ImmediateDominator info around, calculate the idom as
// above.
- DominatorTree::Node *NewBBIDomNode;
- if (NewBBIDom) {
- NewBBIDomNode = DT->getNode(NewBBIDom);
- } else {
- // Scan all the pred blocks that were pulled out. Any individual one may
- // actually be unreachable, which would mean it doesn't have dom info.
- NewBBIDomNode = 0;
- for (unsigned i = 0; !NewBBIDomNode; ++i) {
- assert(i != PredBlocks.size() && "No reachable preds?");
- NewBBIDomNode = DT->getNode(PredBlocks[i]);
- }
-
- while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) {
- NewBBIDomNode = NewBBIDomNode->getIDom();
- assert(NewBBIDomNode && "No shared dominator found??");
+ if (!NewBBIDom) {
+ unsigned i = 0;
+ for (i = 0; i < PredBlocks.size(); ++i)
+ if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) {
+ NewBBIDom = PredBlocks[i];
+ break;
+ }
+ assert(i != PredBlocks.size() && "No reachable preds?");
+ for (i = i + 1; i < PredBlocks.size(); ++i) {
+ if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i]))
+ NewBBIDom = ETF.nearestCommonDominator(NewBBIDom, PredBlocks[i]);
}
- NewBBIDom = NewBBIDomNode->getBlock();
+ assert(NewBBIDom && "No immediate dominator found??");
}
+ DominatorTree::Node *NewBBIDomNode = DT->getNode(NewBBIDom);
// Create the new dominator tree node... and set the idom of NewBB.
DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode);
bool DominatesPred = false;
for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
PI != E; ++PI)
- if (DS.dominates(NewBB, *PI))
+ if (ETF.dominates(NewBB, *PI))
DominatesPred = true;
if (!DominatesPred)
Set.erase(SetI++);
// blocks that dominate a block in PredBlocks and contained NewBBSucc in
// their dominance frontier must be updated to contain NewBB instead.
//
- for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) {
- BasicBlock *Pred = PredBlocks[i];
- // Get all of the dominators of the predecessor...
- const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred);
- for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(),
- PDE = PredDoms.end(); PDI != PDE; ++PDI) {
- BasicBlock *PredDom = *PDI;
-
- // If the NewBBSucc node is in DF(PredDom), then PredDom didn't
- // dominate NewBBSucc but did dominate a predecessor of it. Now we
- // change this entry to include NewBB in the DF instead of NewBBSucc.
- DominanceFrontier::iterator DFI = DF->find(PredDom);
- assert(DFI != DF->end() && "No dominance frontier for node?");
- if (DFI->second.count(NewBBSucc)) {
- // If NewBBSucc should not stay in our dominator frontier, remove it.
- // We remove it unless there is a predecessor of NewBBSucc that we
- // dominate, but we don't strictly dominate NewBBSucc.
- bool ShouldRemove = true;
- if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) {
- // Okay, we know that PredDom does not strictly dominate NewBBSucc.
- // Check to see if it dominates any predecessors of NewBBSucc.
- for (pred_iterator PI = pred_begin(NewBBSucc),
- E = pred_end(NewBBSucc); PI != E; ++PI)
- if (DS.dominates(PredDom, *PI)) {
- ShouldRemove = false;
- break;
- }
- }
-
+ for (Function::iterator FI = NewBB->getParent()->begin(),
+ FE = NewBB->getParent()->end(); FI != FE; ++FI) {
+ DominanceFrontier::iterator DFI = DF->find(FI);
+ if (DFI == DF->end()) continue; // unreachable block.
+
+ // Only consider dominators of NewBBSucc
+ if (!DFI->second.count(NewBBSucc)) continue;
+
+ if (BlockDominatesAny(FI, PredBlocks, ETF)) {
+ // If NewBBSucc should not stay in our dominator frontier, remove it.
+ // We remove it unless there is a predecessor of NewBBSucc that we
+ // dominate, but we don't strictly dominate NewBBSucc.
+ bool ShouldRemove = true;
+ if ((BasicBlock*)FI == NewBBSucc || !ETF.dominates(FI, NewBBSucc)) {
+ // Okay, we know that PredDom does not strictly dominate NewBBSucc.
+ // Check to see if it dominates any predecessors of NewBBSucc.
+ for (pred_iterator PI = pred_begin(NewBBSucc),
+ E = pred_end(NewBBSucc); PI != E; ++PI)
+ if (ETF.dominates(FI, *PI)) {
+ ShouldRemove = false;
+ break;
+ }
+
if (ShouldRemove)
DF->removeFromFrontier(DFI, NewBBSucc);
DF->addToFrontier(DFI, NewBB);
+
+ break;
}
}
}
}
}
+
projects / oota-llvm.git / blobdiff