From 4f9e58ecdf247f87a9b7cef69b1fa37fb5b07f0d Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Sat, 7 Apr 2007 06:56:47 +0000 Subject: [PATCH] Completely purge DomSet from LoopSimplify. This is part of the continuing work on PR1171. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35730 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/LoopSimplify.cpp | 128 +++++++++----------------- 1 file changed, 46 insertions(+), 82 deletions(-) diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index b6c262cd491..530e3b7a66a 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -64,12 +64,10 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { // We need loop information to identify the loops... AU.addRequired(); - AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -692,33 +690,8 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, ++succ_begin(NewBB) == succ_end(NewBB) && "NewBB should have a single successor!"); BasicBlock *NewBBSucc = *succ_begin(NewBB); - DominatorSet &DS = getAnalysis(); - - // 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(); + // 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! @@ -727,13 +700,14 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, { BasicBlock *OnePred = PredBlocks[0]; unsigned i, e = PredBlocks.size(); - for (i = 1; !DS.isReachable(OnePred); ++i) { + for (i = 1; !ETF.dominates(&OnePred->getParent()->getEntryBlock(), 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.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), OnePred)) { NewBBDominatesNewBBSucc = false; break; } @@ -741,7 +715,7 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 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; } @@ -754,44 +728,31 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 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()) { - // 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 @@ -804,24 +765,21 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, if (DominatorTree *DT = getAnalysisToUpdate()) { // 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); @@ -856,7 +814,7 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 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++); @@ -884,8 +842,14 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 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(), + // FIXME: There's probably a better way to do this... + std::vector PredDoms; + for (Function::iterator I = Pred->getParent()->begin(), + E = Pred->getParent()->end(); I != E; ++I) + if (ETF.dominates(&(*I), Pred)) + PredDoms.push_back(I); + + for (std::vector::const_iterator PDI = PredDoms.begin(), PDE = PredDoms.end(); PDI != PDE; ++PDI) { BasicBlock *PredDom = *PDI; @@ -899,12 +863,12 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, // 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)) { + if (PredDom == NewBBSucc || !ETF.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)) { + if (ETF.dominates(PredDom, *PI)) { ShouldRemove = false; break; } -- 2.34.1