Mercurial > hg > CbC > CbC_llvm
diff lib/Transforms/Scalar/StructurizeCFG.cpp @ 121:803732b1fca8
LLVM 5.0
author | kono |
---|---|
date | Fri, 27 Oct 2017 17:07:41 +0900 |
parents | 1172e4bd9c6f |
children | 3a76565eade5 |
line wrap: on
line diff
--- a/lib/Transforms/Scalar/StructurizeCFG.cpp Fri Nov 25 19:14:25 2016 +0900 +++ b/lib/Transforms/Scalar/StructurizeCFG.cpp Fri Oct 27 17:07:41 2017 +0900 @@ -1,4 +1,4 @@ -//===-- StructurizeCFG.cpp ------------------------------------------------===// +//===- StructurizeCFG.cpp -------------------------------------------------===// // // The LLVM Compiler Infrastructure // @@ -7,113 +7,117 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/SCCIterator.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/DivergenceAnalysis.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/Argument.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Metadata.h" #include "llvm/IR/PatternMatch.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/SSAUpdater.h" +#include <algorithm> +#include <cassert> +#include <utility> using namespace llvm; using namespace llvm::PatternMatch; #define DEBUG_TYPE "structurizecfg" +// The name for newly created blocks. +static const char *const FlowBlockName = "Flow"; + namespace { // Definition of the complex types used in this pass. -typedef std::pair<BasicBlock *, Value *> BBValuePair; +using BBValuePair = std::pair<BasicBlock *, Value *>; -typedef SmallVector<RegionNode*, 8> RNVector; -typedef SmallVector<BasicBlock*, 8> BBVector; -typedef SmallVector<BranchInst*, 8> BranchVector; -typedef SmallVector<BBValuePair, 2> BBValueVector; +using RNVector = SmallVector<RegionNode *, 8>; +using BBVector = SmallVector<BasicBlock *, 8>; +using BranchVector = SmallVector<BranchInst *, 8>; +using BBValueVector = SmallVector<BBValuePair, 2>; -typedef SmallPtrSet<BasicBlock *, 8> BBSet; - -typedef MapVector<PHINode *, BBValueVector> PhiMap; -typedef MapVector<BasicBlock *, BBVector> BB2BBVecMap; +using BBSet = SmallPtrSet<BasicBlock *, 8>; -typedef DenseMap<DomTreeNode *, unsigned> DTN2UnsignedMap; -typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap; -typedef DenseMap<BasicBlock *, Value *> BBPredicates; -typedef DenseMap<BasicBlock *, BBPredicates> PredMap; -typedef DenseMap<BasicBlock *, BasicBlock*> BB2BBMap; +using PhiMap = MapVector<PHINode *, BBValueVector>; +using BB2BBVecMap = MapVector<BasicBlock *, BBVector>; -// The name for newly created blocks. - -static const char *const FlowBlockName = "Flow"; +using BBPhiMap = DenseMap<BasicBlock *, PhiMap>; +using BBPredicates = DenseMap<BasicBlock *, Value *>; +using PredMap = DenseMap<BasicBlock *, BBPredicates>; +using BB2BBMap = DenseMap<BasicBlock *, BasicBlock *>; -/// @brief Find the nearest common dominator for multiple BasicBlocks +/// Finds the nearest common dominator of a set of BasicBlocks. /// -/// Helper class for StructurizeCFG -/// TODO: Maybe move into common code +/// For every BB you add to the set, you can specify whether we "remember" the +/// block. When you get the common dominator, you can also ask whether it's one +/// of the blocks we remembered. class NearestCommonDominator { DominatorTree *DT; - - DTN2UnsignedMap IndexMap; - - BasicBlock *Result; - unsigned ResultIndex; - bool ExplicitMentioned; + BasicBlock *Result = nullptr; + bool ResultIsRemembered = false; -public: - /// \brief Start a new query - NearestCommonDominator(DominatorTree *DomTree) { - DT = DomTree; - Result = nullptr; - } - - /// \brief Add BB to the resulting dominator - void addBlock(BasicBlock *BB, bool Remember = true) { - DomTreeNode *Node = DT->getNode(BB); - + /// Add BB to the resulting dominator. + void addBlock(BasicBlock *BB, bool Remember) { if (!Result) { - unsigned Numbering = 0; - for (;Node;Node = Node->getIDom()) - IndexMap[Node] = ++Numbering; Result = BB; - ResultIndex = 1; - ExplicitMentioned = Remember; + ResultIsRemembered = Remember; return; } - for (;Node;Node = Node->getIDom()) - if (IndexMap.count(Node)) - break; - else - IndexMap[Node] = 0; - - assert(Node && "Dominator tree invalid!"); - - unsigned Numbering = IndexMap[Node]; - if (Numbering > ResultIndex) { - Result = Node->getBlock(); - ResultIndex = Numbering; - ExplicitMentioned = Remember && (Result == BB); - } else if (Numbering == ResultIndex) { - ExplicitMentioned |= Remember; - } + BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB); + if (NewResult != Result) + ResultIsRemembered = false; + if (NewResult == BB) + ResultIsRemembered |= Remember; + Result = NewResult; } - /// \brief Is "Result" one of the BBs added with "Remember" = True? - bool wasResultExplicitMentioned() { - return ExplicitMentioned; +public: + explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {} + + void addBlock(BasicBlock *BB) { + addBlock(BB, /* Remember = */ false); } - /// \brief Get the query result - BasicBlock *getResult() { - return Result; + void addAndRememberBlock(BasicBlock *BB) { + addBlock(BB, /* Remember = */ true); } + + /// Get the nearest common dominator of all the BBs added via addBlock() and + /// addAndRememberBlock(). + BasicBlock *result() { return Result; } + + /// Is the BB returned by getResult() one of the blocks we added to the set + /// with addAndRememberBlock()? + bool resultIsRememberedBlock() { return ResultIsRemembered; } }; /// @brief Transforms the control flow graph on one single entry/exit region @@ -348,7 +352,7 @@ Loops[Exit] = N->getEntry(); } else { - // Test for sucessors as back edge + // Test for successors as back edge BasicBlock *BB = N->getNodeAs<BasicBlock>(); BranchInst *Term = cast<BranchInst>(BB->getTerminator()); @@ -410,46 +414,40 @@ BBPredicates &Pred = Predicates[BB]; BBPredicates &LPred = LoopPreds[BB]; - for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); - PI != PE; ++PI) { - + for (BasicBlock *P : predecessors(BB)) { // Ignore it if it's a branch from outside into our region entry - if (!ParentRegion->contains(*PI)) + if (!ParentRegion->contains(P)) continue; - Region *R = RI->getRegionFor(*PI); + Region *R = RI->getRegionFor(P); if (R == ParentRegion) { - // It's a top level block in our region - BranchInst *Term = cast<BranchInst>((*PI)->getTerminator()); + BranchInst *Term = cast<BranchInst>(P->getTerminator()); for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) { BasicBlock *Succ = Term->getSuccessor(i); if (Succ != BB) continue; - if (Visited.count(*PI)) { + if (Visited.count(P)) { // Normal forward edge if (Term->isConditional()) { // Try to treat it like an ELSE block BasicBlock *Other = Term->getSuccessor(!i); if (Visited.count(Other) && !Loops.count(Other) && - !Pred.count(Other) && !Pred.count(*PI)) { + !Pred.count(Other) && !Pred.count(P)) { Pred[Other] = BoolFalse; - Pred[*PI] = BoolTrue; + Pred[P] = BoolTrue; continue; } } - Pred[*PI] = buildCondition(Term, i, false); - + Pred[P] = buildCondition(Term, i, false); } else { // Back edge - LPred[*PI] = buildCondition(Term, i, true); + LPred[P] = buildCondition(Term, i, true); } } - } else { - // It's an exit from a sub region while (R->getParent() != ParentRegion) R = R->getParent(); @@ -480,7 +478,6 @@ Visited.clear(); for (RegionNode *RN : reverse(Order)) { - DEBUG(dbgs() << "Visiting: " << (RN->isSubRegion() ? "SubRegion with entry: " : "") << RN->getEntry()->getName() << " Loop Depth: " @@ -517,25 +514,26 @@ BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue]; NearestCommonDominator Dominator(DT); - Dominator.addBlock(Parent, false); + Dominator.addBlock(Parent); Value *ParentValue = nullptr; - for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); - PI != PE; ++PI) { + for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) { + BasicBlock *BB = BBAndPred.first; + Value *Pred = BBAndPred.second; - if (PI->first == Parent) { - ParentValue = PI->second; + if (BB == Parent) { + ParentValue = Pred; break; } - PhiInserter.AddAvailableValue(PI->first, PI->second); - Dominator.addBlock(PI->first); + PhiInserter.AddAvailableValue(BB, Pred); + Dominator.addAndRememberBlock(BB); } if (ParentValue) { Term->setCondition(ParentValue); } else { - if (!Dominator.wasResultExplicitMentioned()) - PhiInserter.AddAvailableValue(Dominator.getResult(), Default); + if (!Dominator.resultIsRememberedBlock()) + PhiInserter.AddAvailableValue(Dominator.result(), Default); Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent)); } @@ -546,10 +544,10 @@ /// them in DeletedPhis void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) { PhiMap &Map = DeletedPhis[To]; - for (BasicBlock::iterator I = To->begin(), E = To->end(); - I != E && isa<PHINode>(*I);) { - - PHINode &Phi = cast<PHINode>(*I++); + for (Instruction &I : *To) { + if (!isa<PHINode>(I)) + break; + PHINode &Phi = cast<PHINode>(I); while (Phi.getBasicBlockIndex(From) != -1) { Value *Deleted = Phi.removeIncomingValue(From, false); Map[&Phi].push_back(std::make_pair(From, Deleted)); @@ -559,10 +557,10 @@ /// \brief Add a dummy PHI value as soon as we knew the new predecessor void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) { - for (BasicBlock::iterator I = To->begin(), E = To->end(); - I != E && isa<PHINode>(*I);) { - - PHINode &Phi = cast<PHINode>(*I++); + for (Instruction &I : *To) { + if (!isa<PHINode>(I)) + break; + PHINode &Phi = cast<PHINode>(I); Value *Undef = UndefValue::get(Phi.getType()); Phi.addIncoming(Undef, From); } @@ -573,7 +571,6 @@ void StructurizeCFG::setPhiValues() { SSAUpdater Updater; for (const auto &AddedPhi : AddedPhis) { - BasicBlock *To = AddedPhi.first; const BBVector &From = AddedPhi.second; @@ -582,7 +579,6 @@ PhiMap &Map = DeletedPhis[To]; for (const auto &PI : Map) { - PHINode *Phi = PI.first; Value *Undef = UndefValue::get(Phi->getType()); Updater.Initialize(Phi->getType(), ""); @@ -590,18 +586,16 @@ Updater.AddAvailableValue(To, Undef); NearestCommonDominator Dominator(DT); - Dominator.addBlock(To, false); + Dominator.addBlock(To); for (const auto &VI : PI.second) { - Updater.AddAvailableValue(VI.first, VI.second); - Dominator.addBlock(VI.first); + Dominator.addAndRememberBlock(VI.first); } - if (!Dominator.wasResultExplicitMentioned()) - Updater.AddAvailableValue(Dominator.getResult(), Undef); + if (!Dominator.resultIsRememberedBlock()) + Updater.AddAvailableValue(Dominator.result(), Undef); for (BasicBlock *FI : From) { - int Idx = Phi->getBasicBlockIndex(FI); assert(Idx != -1); Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(FI)); @@ -620,10 +614,8 @@ return; for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); - SI != SE; ++SI) { - + SI != SE; ++SI) delPhiValues(BB, *SI); - } Term->eraseFromParent(); } @@ -637,10 +629,10 @@ 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); - I != E;) { + for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) { + // Incrememt BBI before mucking with BB's terminator. + BasicBlock *BB = *BBI++; - BasicBlock *BB = *I++; if (!SubRegion->contains(BB)) continue; @@ -664,7 +656,6 @@ // Update the region info SubRegion->replaceExit(NewExit); - } else { BasicBlock *BB = Node->getNodeAs<BasicBlock>(); killTerminator(BB); @@ -695,7 +686,6 @@ killTerminator(Entry); if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end()) return Entry; - } // create a new flow node @@ -710,13 +700,13 @@ /// \brief Returns the region exit if possible, otherwise just a new flow node BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow, bool ExitUseAllowed) { - if (Order.empty() && ExitUseAllowed) { - BasicBlock *Exit = ParentRegion->getExit(); - DT->changeImmediateDominator(Exit, Flow); - addPhiValues(Flow, Exit); - return Exit; - } - return getNextFlow(Flow); + if (!Order.empty() || !ExitUseAllowed) + return getNextFlow(Flow); + + BasicBlock *Exit = ParentRegion->getExit(); + DT->changeImmediateDominator(Exit, Flow); + addPhiValues(Flow, Exit); + return Exit; } /// \brief Set the previous node @@ -725,16 +715,12 @@ : nullptr; } -/// \brief Does BB dominate all the predicates of Node ? +/// \brief Does BB dominate all the predicates of Node? bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { BBPredicates &Preds = Predicates[Node->getEntry()]; - for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end(); - PI != PE; ++PI) { - - if (!DT->dominates(BB, PI->first)) - return false; - } - return true; + return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) { + return DT->dominates(BB, Pred.first); + }); } /// \brief Can we predict that this node will always be called? @@ -746,13 +732,14 @@ if (!PrevNode) return true; - for (BBPredicates::iterator I = Preds.begin(), E = Preds.end(); - I != E; ++I) { + for (std::pair<BasicBlock*, Value*> Pred : Preds) { + BasicBlock *BB = Pred.first; + Value *V = Pred.second; - if (I->second != BoolTrue) + if (V != BoolTrue) return false; - if (!Dominated && DT->dominates(I->first, PrevNode->getEntry())) + if (!Dominated && DT->dominates(BB, PrevNode->getEntry())) Dominated = true; } @@ -772,7 +759,6 @@ changeExit(PrevNode, Node->getEntry(), true); } PrevNode = Node; - } else { // Insert extra prefix node (or reuse last one) BasicBlock *Flow = needPrefix(false); @@ -828,6 +814,7 @@ LoopFunc, LoopStart); BranchInst::Create(LoopStart, NewEntry); + DT->setNewRoot(NewEntry); } // Create an extra loop end node @@ -867,30 +854,29 @@ /// no longer dominate all their uses. Not sure if this is really nessasary void StructurizeCFG::rebuildSSA() { SSAUpdater Updater; - for (auto *BB : ParentRegion->blocks()) - for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); - II != IE; ++II) { - + for (BasicBlock *BB : ParentRegion->blocks()) + for (Instruction &I : *BB) { bool Initialized = false; - for (auto I = II->use_begin(), E = II->use_end(); I != E;) { - Use &U = *I++; + // We may modify the use list as we iterate over it, so be careful to + // compute the next element in the use list at the top of the loop. + for (auto UI = I.use_begin(), E = I.use_end(); UI != E;) { + Use &U = *UI++; Instruction *User = cast<Instruction>(U.getUser()); if (User->getParent() == BB) { continue; - } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) { if (UserPN->getIncomingBlock(U) == BB) continue; } - if (DT->dominates(&*II, User)) + if (DT->dominates(&I, User)) continue; if (!Initialized) { - Value *Undef = UndefValue::get(II->getType()); - Updater.Initialize(II->getType(), ""); + Value *Undef = UndefValue::get(I.getType()); + Updater.Initialize(I.getType(), ""); Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); - Updater.AddAvailableValue(BB, &*II); + Updater.AddAvailableValue(BB, &I); Initialized = true; } Updater.RewriteUseAfterInsertions(U);