X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FStructurizeCFG.cpp;h=662513c7d8ae0faa4fed88e6ab2bfa04849f86f5;hb=64294426eaa0965184b12c1355bf4389514a4601;hp=72fea80e65a4f2f81e10afe82a14afdff23e5135;hpb=af7ae9d6890ce5fae27e38ccebb5da09288c49e0;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/StructurizeCFG.cpp b/lib/Transforms/Scalar/StructurizeCFG.cpp index 72fea80e65a..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/Support/PatternMatch.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; @@ -235,18 +241,19 @@ public: } using Pass::doInitialization; - virtual bool doInitialization(Region *R, RGPassManager &RGM); + bool doInitialization(Region *R, RGPassManager &RGM) override; - virtual bool runOnRegion(Region *R, RGPassManager &RGM); + bool runOnRegion(Region *R, RGPassManager &RGM) override; - virtual const char *getPassName() const { + const char *getPassName() const override { return "Structurize control flow"; } - void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequiredID(LowerSwitchID); - AU.addRequired(); - AU.addPreserved(); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); RegionPass::getAnalysisUsage(AU); } }; @@ -258,8 +265,8 @@ char StructurizeCFG::ID = 0; INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", false, false) INITIALIZE_PASS_DEPENDENCY(LowerSwitch) -INITIALIZE_PASS_DEPENDENCY(DominatorTree) -INITIALIZE_PASS_DEPENDENCY(RegionInfo) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG", false, false) @@ -277,12 +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), - E = scc_end(ParentRegion); - for (Order.clear(); I != E; ++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 @@ -298,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; - } } } @@ -323,21 +380,26 @@ Value *StructurizeCFG::invert(Value *Condition) { if (match(Condition, m_Not(m_Value(Condition)))) return Condition; - // Third: Check all the users for an invert - BasicBlock *Parent = cast(Condition)->getParent(); - for (Value::use_iterator I = Condition->use_begin(), - E = Condition->use_end(); I != E; ++I) { + if (Instruction *Inst = dyn_cast(Condition)) { + // Third: Check all the users for an invert + BasicBlock *Parent = Inst->getParent(); + for (User *U : Condition->users()) + if (Instruction *I = dyn_cast(U)) + if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) + return I; - Instruction *User = dyn_cast(*I); - if (!User || User->getParent() != Parent) - continue; + // Last option: Create a new instruction + return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator()); + } - if (match(*I, m_Not(m_Specific(Condition)))) - return *I; + if (Argument *Arg = dyn_cast(Condition)) { + BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock(); + return BinaryOperator::CreateNot(Condition, + Arg->getName() + ".inv", + EntryBlock.getTerminator()); } - // Last option: Create a new instruction - return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator()); + llvm_unreachable("Unhandled condition to invert"); } /// \brief Build the condition for one edge @@ -401,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(); @@ -432,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); @@ -449,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(); @@ -468,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) { @@ -587,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); @@ -674,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 ? @@ -695,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(); @@ -768,6 +832,20 @@ void StructurizeCFG::handleLoops(bool ExitUseAllowed, handleLoops(false, LoopEnd); } + // If the start of the loop is the entry block, we can't branch to it so + // insert a new dummy entry block. + Function *LoopFunc = LoopStart->getParent(); + if (LoopStart == &LoopFunc->getEntryBlock()) { + LoopStart->setName("entry.orig"); + + BasicBlock *NewEntry = + BasicBlock::Create(LoopStart->getContext(), + "entry", + LoopFunc, + LoopStart); + BranchInst::Create(LoopStart, NewEntry); + } + // Create an extra loop end node LoopEnd = needPrefix(false); BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed); @@ -788,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) @@ -805,42 +883,35 @@ void StructurizeCFG::createFlow() { /// no longer dominate all their uses. Not sure if this is really nessasary void StructurizeCFG::rebuildSSA() { SSAUpdater Updater; - for (Region::block_iterator I = ParentRegion->block_begin(), - E = ParentRegion->block_end(); - I != E; ++I) { - - BasicBlock *BB = *I; + 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); } } - } } /// \brief Run the transformation for each region found @@ -851,7 +922,8 @@ bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { Func = R->getEntry()->getParent(); ParentRegion = R; - DT = &getAnalysis(); + DT = &getAnalysis().getDomTree(); + LI = &getAnalysis().getLoopInfo(); orderNodes(); collectInfos();