X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FStructurizeCFG.cpp;h=662513c7d8ae0faa4fed88e6ab2bfa04849f86f5;hb=64294426eaa0965184b12c1355bf4389514a4601;hp=8d4aaca8c2d6d4dac0e734ac6403247f8deae7bd;hpb=7b62be28cbc6cce31852831570a87d9699fbcecd;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/StructurizeCFG.cpp b/lib/Transforms/Scalar/StructurizeCFG.cpp index 8d4aaca8c2d..662513c7d8a 100644 --- a/lib/Transforms/Scalar/StructurizeCFG.cpp +++ b/lib/Transforms/Scalar/StructurizeCFG.cpp @@ -7,20 +7,25 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "structurizecfg" #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SCCIterator.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/RegionIterator.h" #include "llvm/Analysis/RegionPass.h" #include "llvm/IR/Module.h" #include "llvm/IR/PatternMatch.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/SSAUpdater.h" using namespace llvm; using namespace llvm::PatternMatch; +#define DEBUG_TYPE "structurizecfg" + namespace { // Definition of the complex types used in this pass. @@ -64,14 +69,14 @@ public: /// \brief Start a new query NearestCommonDominator(DominatorTree *DomTree) { DT = DomTree; - Result = 0; + Result = nullptr; } /// \brief Add BB to the resulting dominator void addBlock(BasicBlock *BB, bool Remember = true) { DomTreeNode *Node = DT->getNode(BB); - if (Result == 0) { + if (!Result) { unsigned Numbering = 0; for (;Node;Node = Node->getIDom()) IndexMap[Node] = ++Numbering; @@ -165,6 +170,7 @@ class StructurizeCFG : public RegionPass { Region *ParentRegion; DominatorTree *DT; + LoopInfo *LI; RNVector Order; BBSet Visited; @@ -246,6 +252,7 @@ public: void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequiredID(LowerSwitchID); AU.addRequired(); + AU.addRequired(); AU.addPreserved(); RegionPass::getAnalysisUsage(AU); } @@ -259,7 +266,7 @@ INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", false, false) INITIALIZE_PASS_DEPENDENCY(LowerSwitch) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(RegionInfo) +INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG", false, false) @@ -277,11 +284,65 @@ bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) { /// \brief Build up the general order of nodes void StructurizeCFG::orderNodes() { - scc_iterator I = scc_begin(ParentRegion); - for (Order.clear(); !I.isAtEnd(); ++I) { - std::vector &Nodes = *I; - Order.append(Nodes.begin(), Nodes.end()); + RNVector TempOrder; + ReversePostOrderTraversal RPOT(ParentRegion); + TempOrder.append(RPOT.begin(), RPOT.end()); + + std::map LoopBlocks; + + + // The reverse post-order traversal of the list gives us an ordering close + // to what we want. The only problem with it is that sometimes backedges + // for outer loops will be visited before backedges for inner loops. + for (RegionNode *RN : TempOrder) { + BasicBlock *BB = RN->getEntry(); + Loop *Loop = LI->getLoopFor(BB); + if (!LoopBlocks.count(Loop)) { + LoopBlocks[Loop] = 1; + continue; + } + LoopBlocks[Loop]++; + } + + unsigned CurrentLoopDepth = 0; + Loop *CurrentLoop = nullptr; + BBSet TempVisited; + for (RNVector::iterator I = TempOrder.begin(), E = TempOrder.end(); I != E; ++I) { + BasicBlock *BB = (*I)->getEntry(); + unsigned LoopDepth = LI->getLoopDepth(BB); + + if (std::find(Order.begin(), Order.end(), *I) != Order.end()) + continue; + + if (LoopDepth < CurrentLoopDepth) { + // Make sure we have visited all blocks in this loop before moving back to + // the outer loop. + + RNVector::iterator LoopI = I; + while(LoopBlocks[CurrentLoop]) { + LoopI++; + BasicBlock *LoopBB = (*LoopI)->getEntry(); + if (LI->getLoopFor(LoopBB) == CurrentLoop) { + LoopBlocks[CurrentLoop]--; + Order.push_back(*LoopI); + } + } + } + + CurrentLoop = LI->getLoopFor(BB); + if (CurrentLoop) { + LoopBlocks[CurrentLoop]--; + } + + CurrentLoopDepth = LoopDepth; + Order.push_back(*I); } + + // This pass originally used a post-order traversal and then operated on + // the list in reverse. Now that we are using a reverse post-order traversal + // rather than re-working the whole pass to operate on the list in order, + // we just reverse the list and continue to operate on it in reverse. + std::reverse(Order.begin(), Order.end()); } /// \brief Determine the end of the loops @@ -297,12 +358,9 @@ void StructurizeCFG::analyzeLoops(RegionNode *N) { BasicBlock *BB = N->getNodeAs(); BranchInst *Term = cast(BB->getTerminator()); - for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { - BasicBlock *Succ = Term->getSuccessor(i); - + for (BasicBlock *Succ : Term->successors()) if (Visited.count(Succ)) Loops[Succ] = BB; - } } } @@ -325,16 +383,10 @@ Value *StructurizeCFG::invert(Value *Condition) { if (Instruction *Inst = dyn_cast(Condition)) { // Third: Check all the users for an invert BasicBlock *Parent = Inst->getParent(); - for (Value::use_iterator I = Condition->use_begin(), - E = Condition->use_end(); I != E; ++I) { - - Instruction *User = dyn_cast(*I); - if (!User || User->getParent() != Parent) - continue; - - if (match(*I, m_Not(m_Specific(Condition)))) - return *I; - } + for (User *U : Condition->users()) + if (Instruction *I = dyn_cast(U)) + if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) + return I; // Last option: Create a new instruction return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator()); @@ -411,11 +463,11 @@ void StructurizeCFG::gatherPredicates(RegionNode *N) { } else { // It's an exit from a sub region - while(R->getParent() != ParentRegion) + while (R->getParent() != ParentRegion) R = R->getParent(); // Edge from inside a subregion to its entry, ignore it - if (R == N) + if (*R == *N) continue; BasicBlock *Entry = R->getEntry(); @@ -442,6 +494,10 @@ void StructurizeCFG::collectInfos() { for (RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend(); OI != OE; ++OI) { + DEBUG(dbgs() << "Visiting: " << + ((*OI)->isSubRegion() ? "SubRegion with entry: " : "") << + (*OI)->getEntry()->getName() << " Loop Depth: " << LI->getLoopDepth((*OI)->getEntry()) << "\n"); + // Analyze all the conditions leading to a node gatherPredicates(*OI); @@ -459,10 +515,7 @@ void StructurizeCFG::insertConditions(bool Loops) { Value *Default = Loops ? BoolTrue : BoolFalse; SSAUpdater PhiInserter; - for (BranchVector::iterator I = Conds.begin(), - E = Conds.end(); I != E; ++I) { - - BranchInst *Term = *I; + for (BranchInst *Term : Conds) { assert(Term->isConditional()); BasicBlock *Parent = Term->getParent(); @@ -478,7 +531,7 @@ void StructurizeCFG::insertConditions(bool Loops) { NearestCommonDominator Dominator(DT); Dominator.addBlock(Parent, false); - Value *ParentValue = 0; + Value *ParentValue = nullptr; for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); PI != PE; ++PI) { @@ -597,7 +650,7 @@ void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit, if (Node->isSubRegion()) { Region *SubRegion = Node->getNodeAs(); BasicBlock *OldExit = SubRegion->getExit(); - BasicBlock *Dominator = 0; + BasicBlock *Dominator = nullptr; // Find all the edges from the sub region to the exit for (pred_iterator I = pred_begin(OldExit), E = pred_end(OldExit); @@ -684,7 +737,8 @@ BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow, /// \brief Set the previous node void StructurizeCFG::setPrevNode(BasicBlock *BB) { - PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) : 0; + PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) + : nullptr; } /// \brief Does BB dominate all the predicates of Node ? @@ -705,7 +759,7 @@ bool StructurizeCFG::isPredictableTrue(RegionNode *Node) { bool Dominated = false; // Regionentry is always true - if (PrevNode == 0) + if (!PrevNode) return true; for (BBPredicates::iterator I = Preds.begin(), E = Preds.end(); @@ -812,11 +866,11 @@ void StructurizeCFG::createFlow() { Conditions.clear(); LoopConds.clear(); - PrevNode = 0; + PrevNode = nullptr; Visited.clear(); while (!Order.empty()) { - handleLoops(EntryDominatesExit, 0); + handleLoops(EntryDominatesExit, nullptr); } if (PrevNode) @@ -829,35 +883,33 @@ void StructurizeCFG::createFlow() { /// no longer dominate all their uses. Not sure if this is really nessasary void StructurizeCFG::rebuildSSA() { SSAUpdater Updater; - for (const auto &BB : ParentRegion->blocks()) + for (auto *BB : ParentRegion->blocks()) for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II) { bool Initialized = false; - for (Use *I = &II->use_begin().getUse(), *Next; I; I = Next) { - - Next = I->getNext(); - - Instruction *User = cast(I->getUser()); + for (auto I = II->use_begin(), E = II->use_end(); I != E;) { + Use &U = *I++; + Instruction *User = cast(U.getUser()); if (User->getParent() == BB) { continue; } else if (PHINode *UserPN = dyn_cast(User)) { - if (UserPN->getIncomingBlock(*I) == BB) + if (UserPN->getIncomingBlock(U) == BB) continue; } - if (DT->dominates(II, User)) + if (DT->dominates(&*II, User)) continue; if (!Initialized) { Value *Undef = UndefValue::get(II->getType()); Updater.Initialize(II->getType(), ""); Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); - Updater.AddAvailableValue(BB, II); + Updater.AddAvailableValue(BB, &*II); Initialized = true; } - Updater.RewriteUseAfterInsertions(*I); + Updater.RewriteUseAfterInsertions(U); } } } @@ -871,6 +923,7 @@ bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { ParentRegion = R; DT = &getAnalysis().getDomTree(); + LI = &getAnalysis().getLoopInfo(); orderNodes(); collectInfos();