diff options
Diffstat (limited to 'gnu/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp')
| -rw-r--r-- | gnu/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp | 1040 |
1 files changed, 0 insertions, 1040 deletions
diff --git a/gnu/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp b/gnu/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp deleted file mode 100644 index 0db762d846f..00000000000 --- a/gnu/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp +++ /dev/null @@ -1,1040 +0,0 @@ -//===- StructurizeCFG.cpp -------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/MapVector.h" -#include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/InstructionSimplify.h" -#include "llvm/Analysis/LegacyDivergenceAnalysis.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/RegionInfo.h" -#include "llvm/Analysis/RegionIterator.h" -#include "llvm/Analysis/RegionPass.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.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 { - -static cl::opt<bool> ForceSkipUniformRegions( - "structurizecfg-skip-uniform-regions", - cl::Hidden, - cl::desc("Force whether the StructurizeCFG pass skips uniform regions"), - cl::init(false)); - -// Definition of the complex types used in this pass. - -using BBValuePair = std::pair<BasicBlock *, Value *>; - -using RNVector = SmallVector<RegionNode *, 8>; -using BBVector = SmallVector<BasicBlock *, 8>; -using BranchVector = SmallVector<BranchInst *, 8>; -using BBValueVector = SmallVector<BBValuePair, 2>; - -using BBSet = SmallPtrSet<BasicBlock *, 8>; - -using PhiMap = MapVector<PHINode *, BBValueVector>; -using BB2BBVecMap = MapVector<BasicBlock *, BBVector>; - -using BBPhiMap = DenseMap<BasicBlock *, PhiMap>; -using BBPredicates = DenseMap<BasicBlock *, Value *>; -using PredMap = DenseMap<BasicBlock *, BBPredicates>; -using BB2BBMap = DenseMap<BasicBlock *, BasicBlock *>; - -/// Finds the nearest common dominator of a set of BasicBlocks. -/// -/// 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; - BasicBlock *Result = nullptr; - bool ResultIsRemembered = false; - - /// Add BB to the resulting dominator. - void addBlock(BasicBlock *BB, bool Remember) { - if (!Result) { - Result = BB; - ResultIsRemembered = Remember; - return; - } - - BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB); - if (NewResult != Result) - ResultIsRemembered = false; - if (NewResult == BB) - ResultIsRemembered |= Remember; - Result = NewResult; - } - -public: - explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {} - - void addBlock(BasicBlock *BB) { - addBlock(BB, /* Remember = */ false); - } - - 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; } -}; - -/// Transforms the control flow graph on one single entry/exit region -/// at a time. -/// -/// After the transform all "If"/"Then"/"Else" style control flow looks like -/// this: -/// -/// \verbatim -/// 1 -/// || -/// | | -/// 2 | -/// | / -/// |/ -/// 3 -/// || Where: -/// | | 1 = "If" block, calculates the condition -/// 4 | 2 = "Then" subregion, runs if the condition is true -/// | / 3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow -/// |/ 4 = "Else" optional subregion, runs if the condition is false -/// 5 5 = "End" block, also rejoins the control flow -/// \endverbatim -/// -/// Control flow is expressed as a branch where the true exit goes into the -/// "Then"/"Else" region, while the false exit skips the region -/// The condition for the optional "Else" region is expressed as a PHI node. -/// The incoming values of the PHI node are true for the "If" edge and false -/// for the "Then" edge. -/// -/// Additionally to that even complicated loops look like this: -/// -/// \verbatim -/// 1 -/// || -/// | | -/// 2 ^ Where: -/// | / 1 = "Entry" block -/// |/ 2 = "Loop" optional subregion, with all exits at "Flow" block -/// 3 3 = "Flow" block, with back edge to entry block -/// | -/// \endverbatim -/// -/// The back edge of the "Flow" block is always on the false side of the branch -/// while the true side continues the general flow. So the loop condition -/// consist of a network of PHI nodes where the true incoming values expresses -/// breaks and the false values expresses continue states. -class StructurizeCFG : public RegionPass { - bool SkipUniformRegions; - - Type *Boolean; - ConstantInt *BoolTrue; - ConstantInt *BoolFalse; - UndefValue *BoolUndef; - - Function *Func; - Region *ParentRegion; - - LegacyDivergenceAnalysis *DA; - DominatorTree *DT; - LoopInfo *LI; - - SmallVector<RegionNode *, 8> Order; - BBSet Visited; - - BBPhiMap DeletedPhis; - BB2BBVecMap AddedPhis; - - PredMap Predicates; - BranchVector Conditions; - - BB2BBMap Loops; - PredMap LoopPreds; - BranchVector LoopConds; - - RegionNode *PrevNode; - - void orderNodes(); - - Loop *getAdjustedLoop(RegionNode *RN); - unsigned getAdjustedLoopDepth(RegionNode *RN); - - void analyzeLoops(RegionNode *N); - - Value *invert(Value *Condition); - - Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert); - - void gatherPredicates(RegionNode *N); - - void collectInfos(); - - void insertConditions(bool Loops); - - void delPhiValues(BasicBlock *From, BasicBlock *To); - - void addPhiValues(BasicBlock *From, BasicBlock *To); - - void setPhiValues(); - - void killTerminator(BasicBlock *BB); - - void changeExit(RegionNode *Node, BasicBlock *NewExit, - bool IncludeDominator); - - BasicBlock *getNextFlow(BasicBlock *Dominator); - - BasicBlock *needPrefix(bool NeedEmpty); - - BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed); - - void setPrevNode(BasicBlock *BB); - - bool dominatesPredicates(BasicBlock *BB, RegionNode *Node); - - bool isPredictableTrue(RegionNode *Node); - - void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd); - - void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd); - - void createFlow(); - - void rebuildSSA(); - -public: - static char ID; - - explicit StructurizeCFG(bool SkipUniformRegions_ = false) - : RegionPass(ID), - SkipUniformRegions(SkipUniformRegions_) { - if (ForceSkipUniformRegions.getNumOccurrences()) - SkipUniformRegions = ForceSkipUniformRegions.getValue(); - initializeStructurizeCFGPass(*PassRegistry::getPassRegistry()); - } - - bool doInitialization(Region *R, RGPassManager &RGM) override; - - bool runOnRegion(Region *R, RGPassManager &RGM) override; - - StringRef getPassName() const override { return "Structurize control flow"; } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - if (SkipUniformRegions) - AU.addRequired<LegacyDivergenceAnalysis>(); - AU.addRequiredID(LowerSwitchID); - AU.addRequired<DominatorTreeWrapperPass>(); - AU.addRequired<LoopInfoWrapperPass>(); - - AU.addPreserved<DominatorTreeWrapperPass>(); - RegionPass::getAnalysisUsage(AU); - } -}; - -} // end anonymous namespace - -char StructurizeCFG::ID = 0; - -INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG", - false, false) -INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis) -INITIALIZE_PASS_DEPENDENCY(LowerSwitch) -INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(RegionInfoPass) -INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG", - false, false) - -/// Initialize the types and constants used in the pass -bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) { - LLVMContext &Context = R->getEntry()->getContext(); - - Boolean = Type::getInt1Ty(Context); - BoolTrue = ConstantInt::getTrue(Context); - BoolFalse = ConstantInt::getFalse(Context); - BoolUndef = UndefValue::get(Boolean); - - return false; -} - -/// Use the exit block to determine the loop if RN is a SubRegion. -Loop *StructurizeCFG::getAdjustedLoop(RegionNode *RN) { - if (RN->isSubRegion()) { - Region *SubRegion = RN->getNodeAs<Region>(); - return LI->getLoopFor(SubRegion->getExit()); - } - - return LI->getLoopFor(RN->getEntry()); -} - -/// Use the exit block to determine the loop depth if RN is a SubRegion. -unsigned StructurizeCFG::getAdjustedLoopDepth(RegionNode *RN) { - if (RN->isSubRegion()) { - Region *SubR = RN->getNodeAs<Region>(); - return LI->getLoopDepth(SubR->getExit()); - } - - return LI->getLoopDepth(RN->getEntry()); -} - -/// Build up the general order of nodes -void StructurizeCFG::orderNodes() { - ReversePostOrderTraversal<Region*> RPOT(ParentRegion); - SmallDenseMap<Loop*, unsigned, 8> 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 : RPOT) { - Loop *Loop = getAdjustedLoop(RN); - ++LoopBlocks[Loop]; - } - - unsigned CurrentLoopDepth = 0; - Loop *CurrentLoop = nullptr; - for (auto I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { - RegionNode *RN = cast<RegionNode>(*I); - unsigned LoopDepth = getAdjustedLoopDepth(RN); - - if (is_contained(Order, *I)) - continue; - - if (LoopDepth < CurrentLoopDepth) { - // Make sure we have visited all blocks in this loop before moving back to - // the outer loop. - - auto LoopI = I; - while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) { - LoopI++; - if (getAdjustedLoop(cast<RegionNode>(*LoopI)) == CurrentLoop) { - --BlockCount; - Order.push_back(*LoopI); - } - } - } - - CurrentLoop = getAdjustedLoop(RN); - 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()); -} - -/// Determine the end of the loops -void StructurizeCFG::analyzeLoops(RegionNode *N) { - if (N->isSubRegion()) { - // Test for exit as back edge - BasicBlock *Exit = N->getNodeAs<Region>()->getExit(); - if (Visited.count(Exit)) - Loops[Exit] = N->getEntry(); - - } else { - // Test for successors as back edge - BasicBlock *BB = N->getNodeAs<BasicBlock>(); - BranchInst *Term = cast<BranchInst>(BB->getTerminator()); - - for (BasicBlock *Succ : Term->successors()) - if (Visited.count(Succ)) - Loops[Succ] = BB; - } -} - -/// Invert the given condition -Value *StructurizeCFG::invert(Value *Condition) { - // First: Check if it's a constant - if (Constant *C = dyn_cast<Constant>(Condition)) - return ConstantExpr::getNot(C); - - // Second: If the condition is already inverted, return the original value - Value *NotCondition; - if (match(Condition, m_Not(m_Value(NotCondition)))) - return NotCondition; - - if (Instruction *Inst = dyn_cast<Instruction>(Condition)) { - // Third: Check all the users for an invert - BasicBlock *Parent = Inst->getParent(); - for (User *U : Condition->users()) - if (Instruction *I = dyn_cast<Instruction>(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()); - } - - if (Argument *Arg = dyn_cast<Argument>(Condition)) { - BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock(); - return BinaryOperator::CreateNot(Condition, - Arg->getName() + ".inv", - EntryBlock.getTerminator()); - } - - llvm_unreachable("Unhandled condition to invert"); -} - -/// Build the condition for one edge -Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx, - bool Invert) { - Value *Cond = Invert ? BoolFalse : BoolTrue; - if (Term->isConditional()) { - Cond = Term->getCondition(); - - if (Idx != (unsigned)Invert) - Cond = invert(Cond); - } - return Cond; -} - -/// Analyze the predecessors of each block and build up predicates -void StructurizeCFG::gatherPredicates(RegionNode *N) { - RegionInfo *RI = ParentRegion->getRegionInfo(); - BasicBlock *BB = N->getEntry(); - BBPredicates &Pred = Predicates[BB]; - BBPredicates &LPred = LoopPreds[BB]; - - for (BasicBlock *P : predecessors(BB)) { - // Ignore it if it's a branch from outside into our region entry - if (!ParentRegion->contains(P)) - continue; - - Region *R = RI->getRegionFor(P); - if (R == ParentRegion) { - // It's a top level block in our region - 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(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(P)) { - - Pred[Other] = BoolFalse; - Pred[P] = BoolTrue; - continue; - } - } - Pred[P] = buildCondition(Term, i, false); - } else { - // Back edge - LPred[P] = buildCondition(Term, i, true); - } - } - } else { - // It's an exit from a sub region - while (R->getParent() != ParentRegion) - R = R->getParent(); - - // Edge from inside a subregion to its entry, ignore it - if (*R == *N) - continue; - - BasicBlock *Entry = R->getEntry(); - if (Visited.count(Entry)) - Pred[Entry] = BoolTrue; - else - LPred[Entry] = BoolFalse; - } - } -} - -/// Collect various loop and predicate infos -void StructurizeCFG::collectInfos() { - // Reset predicate - Predicates.clear(); - - // and loop infos - Loops.clear(); - LoopPreds.clear(); - - // Reset the visited nodes - Visited.clear(); - - for (RegionNode *RN : reverse(Order)) { - LLVM_DEBUG(dbgs() << "Visiting: " - << (RN->isSubRegion() ? "SubRegion with entry: " : "") - << RN->getEntry()->getName() << " Loop Depth: " - << LI->getLoopDepth(RN->getEntry()) << "\n"); - - // Analyze all the conditions leading to a node - gatherPredicates(RN); - - // Remember that we've seen this node - Visited.insert(RN->getEntry()); - - // Find the last back edges - analyzeLoops(RN); - } -} - -/// Insert the missing branch conditions -void StructurizeCFG::insertConditions(bool Loops) { - BranchVector &Conds = Loops ? LoopConds : Conditions; - Value *Default = Loops ? BoolTrue : BoolFalse; - SSAUpdater PhiInserter; - - for (BranchInst *Term : Conds) { - assert(Term->isConditional()); - - BasicBlock *Parent = Term->getParent(); - BasicBlock *SuccTrue = Term->getSuccessor(0); - BasicBlock *SuccFalse = Term->getSuccessor(1); - - PhiInserter.Initialize(Boolean, ""); - PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default); - PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default); - - BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue]; - - NearestCommonDominator Dominator(DT); - Dominator.addBlock(Parent); - - Value *ParentValue = nullptr; - for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) { - BasicBlock *BB = BBAndPred.first; - Value *Pred = BBAndPred.second; - - if (BB == Parent) { - ParentValue = Pred; - break; - } - PhiInserter.AddAvailableValue(BB, Pred); - Dominator.addAndRememberBlock(BB); - } - - if (ParentValue) { - Term->setCondition(ParentValue); - } else { - if (!Dominator.resultIsRememberedBlock()) - PhiInserter.AddAvailableValue(Dominator.result(), Default); - - Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent)); - } - } -} - -/// Remove all PHI values coming from "From" into "To" and remember -/// them in DeletedPhis -void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) { - PhiMap &Map = DeletedPhis[To]; - for (PHINode &Phi : To->phis()) { - while (Phi.getBasicBlockIndex(From) != -1) { - Value *Deleted = Phi.removeIncomingValue(From, false); - Map[&Phi].push_back(std::make_pair(From, Deleted)); - } - } -} - -/// Add a dummy PHI value as soon as we knew the new predecessor -void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) { - for (PHINode &Phi : To->phis()) { - Value *Undef = UndefValue::get(Phi.getType()); - Phi.addIncoming(Undef, From); - } - AddedPhis[To].push_back(From); -} - -/// Add the real PHI value as soon as everything is set up -void StructurizeCFG::setPhiValues() { - SmallVector<PHINode *, 8> InsertedPhis; - SSAUpdater Updater(&InsertedPhis); - for (const auto &AddedPhi : AddedPhis) { - BasicBlock *To = AddedPhi.first; - const BBVector &From = AddedPhi.second; - - if (!DeletedPhis.count(To)) - continue; - - PhiMap &Map = DeletedPhis[To]; - for (const auto &PI : Map) { - PHINode *Phi = PI.first; - Value *Undef = UndefValue::get(Phi->getType()); - Updater.Initialize(Phi->getType(), ""); - Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); - Updater.AddAvailableValue(To, Undef); - - NearestCommonDominator Dominator(DT); - Dominator.addBlock(To); - for (const auto &VI : PI.second) { - Updater.AddAvailableValue(VI.first, VI.second); - Dominator.addAndRememberBlock(VI.first); - } - - 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)); - } - } - - DeletedPhis.erase(To); - } - assert(DeletedPhis.empty()); - - // Simplify any phis inserted by the SSAUpdater if possible - bool Changed; - do { - Changed = false; - - SimplifyQuery Q(Func->getParent()->getDataLayout()); - Q.DT = DT; - for (size_t i = 0; i < InsertedPhis.size(); ++i) { - PHINode *Phi = InsertedPhis[i]; - if (Value *V = SimplifyInstruction(Phi, Q)) { - Phi->replaceAllUsesWith(V); - Phi->eraseFromParent(); - InsertedPhis[i] = InsertedPhis.back(); - InsertedPhis.pop_back(); - i--; - Changed = true; - } - } - } while (Changed); -} - -/// Remove phi values from all successors and then remove the terminator. -void StructurizeCFG::killTerminator(BasicBlock *BB) { - Instruction *Term = BB->getTerminator(); - if (!Term) - return; - - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); - SI != SE; ++SI) - delPhiValues(BB, *SI); - - if (DA) - DA->removeValue(Term); - Term->eraseFromParent(); -} - -/// Let node exit(s) point to NewExit -void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit, - bool IncludeDominator) { - if (Node->isSubRegion()) { - Region *SubRegion = Node->getNodeAs<Region>(); - BasicBlock *OldExit = SubRegion->getExit(); - BasicBlock *Dominator = nullptr; - - // Find all the edges from the sub region to the exit - for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) { - // Incrememt BBI before mucking with BB's terminator. - BasicBlock *BB = *BBI++; - - if (!SubRegion->contains(BB)) - continue; - - // Modify the edges to point to the new exit - delPhiValues(BB, OldExit); - BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit); - addPhiValues(BB, NewExit); - - // Find the new dominator (if requested) - if (IncludeDominator) { - if (!Dominator) - Dominator = BB; - else - Dominator = DT->findNearestCommonDominator(Dominator, BB); - } - } - - // Change the dominator (if requested) - if (Dominator) - DT->changeImmediateDominator(NewExit, Dominator); - - // Update the region info - SubRegion->replaceExit(NewExit); - } else { - BasicBlock *BB = Node->getNodeAs<BasicBlock>(); - killTerminator(BB); - BranchInst::Create(NewExit, BB); - addPhiValues(BB, NewExit); - if (IncludeDominator) - DT->changeImmediateDominator(NewExit, BB); - } -} - -/// Create a new flow node and update dominator tree and region info -BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) { - LLVMContext &Context = Func->getContext(); - BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() : - Order.back()->getEntry(); - BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName, - Func, Insert); - DT->addNewBlock(Flow, Dominator); - ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion); - return Flow; -} - -/// Create a new or reuse the previous node as flow node -BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) { - BasicBlock *Entry = PrevNode->getEntry(); - - if (!PrevNode->isSubRegion()) { - killTerminator(Entry); - if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end()) - return Entry; - } - - // create a new flow node - BasicBlock *Flow = getNextFlow(Entry); - - // and wire it up - changeExit(PrevNode, Flow, true); - PrevNode = ParentRegion->getBBNode(Flow); - return Flow; -} - -/// Returns the region exit if possible, otherwise just a new flow node -BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow, - bool ExitUseAllowed) { - if (!Order.empty() || !ExitUseAllowed) - return getNextFlow(Flow); - - BasicBlock *Exit = ParentRegion->getExit(); - DT->changeImmediateDominator(Exit, Flow); - addPhiValues(Flow, Exit); - return Exit; -} - -/// Set the previous node -void StructurizeCFG::setPrevNode(BasicBlock *BB) { - PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB) - : nullptr; -} - -/// Does BB dominate all the predicates of Node? -bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) { - BBPredicates &Preds = Predicates[Node->getEntry()]; - return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) { - return DT->dominates(BB, Pred.first); - }); -} - -/// Can we predict that this node will always be called? -bool StructurizeCFG::isPredictableTrue(RegionNode *Node) { - BBPredicates &Preds = Predicates[Node->getEntry()]; - bool Dominated = false; - - // Regionentry is always true - if (!PrevNode) - return true; - - for (std::pair<BasicBlock*, Value*> Pred : Preds) { - BasicBlock *BB = Pred.first; - Value *V = Pred.second; - - if (V != BoolTrue) - return false; - - if (!Dominated && DT->dominates(BB, PrevNode->getEntry())) - Dominated = true; - } - - // TODO: The dominator check is too strict - return Dominated; -} - -/// Take one node from the order vector and wire it up -void StructurizeCFG::wireFlow(bool ExitUseAllowed, - BasicBlock *LoopEnd) { - RegionNode *Node = Order.pop_back_val(); - Visited.insert(Node->getEntry()); - - if (isPredictableTrue(Node)) { - // Just a linear flow - if (PrevNode) { - changeExit(PrevNode, Node->getEntry(), true); - } - PrevNode = Node; - } else { - // Insert extra prefix node (or reuse last one) - BasicBlock *Flow = needPrefix(false); - - // Insert extra postfix node (or use exit instead) - BasicBlock *Entry = Node->getEntry(); - BasicBlock *Next = needPostfix(Flow, ExitUseAllowed); - - // let it point to entry and next block - Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow)); - addPhiValues(Flow, Entry); - DT->changeImmediateDominator(Entry, Flow); - - PrevNode = Node; - while (!Order.empty() && !Visited.count(LoopEnd) && - dominatesPredicates(Entry, Order.back())) { - handleLoops(false, LoopEnd); - } - - changeExit(PrevNode, Next, false); - setPrevNode(Next); - } -} - -void StructurizeCFG::handleLoops(bool ExitUseAllowed, - BasicBlock *LoopEnd) { - RegionNode *Node = Order.back(); - BasicBlock *LoopStart = Node->getEntry(); - - if (!Loops.count(LoopStart)) { - wireFlow(ExitUseAllowed, LoopEnd); - return; - } - - if (!isPredictableTrue(Node)) - LoopStart = needPrefix(true); - - LoopEnd = Loops[Node->getEntry()]; - wireFlow(false, LoopEnd); - while (!Visited.count(LoopEnd)) { - 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); - DT->setNewRoot(NewEntry); - } - - // Create an extra loop end node - LoopEnd = needPrefix(false); - BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed); - LoopConds.push_back(BranchInst::Create(Next, LoopStart, - BoolUndef, LoopEnd)); - addPhiValues(LoopEnd, LoopStart); - setPrevNode(Next); -} - -/// After this function control flow looks like it should be, but -/// branches and PHI nodes only have undefined conditions. -void StructurizeCFG::createFlow() { - BasicBlock *Exit = ParentRegion->getExit(); - bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit); - - DeletedPhis.clear(); - AddedPhis.clear(); - Conditions.clear(); - LoopConds.clear(); - - PrevNode = nullptr; - Visited.clear(); - - while (!Order.empty()) { - handleLoops(EntryDominatesExit, nullptr); - } - - if (PrevNode) - changeExit(PrevNode, Exit, EntryDominatesExit); - else - assert(EntryDominatesExit); -} - -/// Handle a rare case where the disintegrated nodes instructions -/// no longer dominate all their uses. Not sure if this is really necessary -void StructurizeCFG::rebuildSSA() { - SSAUpdater Updater; - for (BasicBlock *BB : ParentRegion->blocks()) - for (Instruction &I : *BB) { - bool Initialized = false; - // 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(&I, User)) - continue; - - if (!Initialized) { - Value *Undef = UndefValue::get(I.getType()); - Updater.Initialize(I.getType(), ""); - Updater.AddAvailableValue(&Func->getEntryBlock(), Undef); - Updater.AddAvailableValue(BB, &I); - Initialized = true; - } - Updater.RewriteUseAfterInsertions(U); - } - } -} - -static bool hasOnlyUniformBranches(Region *R, unsigned UniformMDKindID, - const LegacyDivergenceAnalysis &DA) { - for (auto E : R->elements()) { - if (!E->isSubRegion()) { - auto Br = dyn_cast<BranchInst>(E->getEntry()->getTerminator()); - if (!Br || !Br->isConditional()) - continue; - - if (!DA.isUniform(Br)) - return false; - LLVM_DEBUG(dbgs() << "BB: " << Br->getParent()->getName() - << " has uniform terminator\n"); - } else { - // Explicitly refuse to treat regions as uniform if they have non-uniform - // subregions. We cannot rely on DivergenceAnalysis for branches in - // subregions because those branches may have been removed and re-created, - // so we look for our metadata instead. - // - // Warning: It would be nice to treat regions as uniform based only on - // their direct child basic blocks' terminators, regardless of whether - // subregions are uniform or not. However, this requires a very careful - // look at SIAnnotateControlFlow to make sure nothing breaks there. - for (auto BB : E->getNodeAs<Region>()->blocks()) { - auto Br = dyn_cast<BranchInst>(BB->getTerminator()); - if (!Br || !Br->isConditional()) - continue; - - if (!Br->getMetadata(UniformMDKindID)) - return false; - } - } - } - return true; -} - -/// Run the transformation for each region found -bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) { - if (R->isTopLevelRegion()) - return false; - - DA = nullptr; - - if (SkipUniformRegions) { - // TODO: We could probably be smarter here with how we handle sub-regions. - // We currently rely on the fact that metadata is set by earlier invocations - // of the pass on sub-regions, and that this metadata doesn't get lost -- - // but we shouldn't rely on metadata for correctness! - unsigned UniformMDKindID = - R->getEntry()->getContext().getMDKindID("structurizecfg.uniform"); - DA = &getAnalysis<LegacyDivergenceAnalysis>(); - - if (hasOnlyUniformBranches(R, UniformMDKindID, *DA)) { - LLVM_DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R - << '\n'); - - // Mark all direct child block terminators as having been treated as - // uniform. To account for a possible future in which non-uniform - // sub-regions are treated more cleverly, indirect children are not - // marked as uniform. - MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {}); - for (RegionNode *E : R->elements()) { - if (E->isSubRegion()) - continue; - - if (Instruction *Term = E->getEntry()->getTerminator()) - Term->setMetadata(UniformMDKindID, MD); - } - - return false; - } - } - - Func = R->getEntry()->getParent(); - ParentRegion = R; - - DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); - LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); - - orderNodes(); - collectInfos(); - createFlow(); - insertConditions(false); - insertConditions(true); - setPhiValues(); - rebuildSSA(); - - // Cleanup - Order.clear(); - Visited.clear(); - DeletedPhis.clear(); - AddedPhis.clear(); - Predicates.clear(); - Conditions.clear(); - Loops.clear(); - LoopPreds.clear(); - LoopConds.clear(); - - return true; -} - -Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) { - return new StructurizeCFG(SkipUniformRegions); -} |