diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/StructurizeCFG.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/StructurizeCFG.cpp | 1063 |
1 files changed, 1063 insertions, 0 deletions
diff --git a/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp new file mode 100644 index 000000000000..9791cf41f621 --- /dev/null +++ b/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp @@ -0,0 +1,1063 @@ +//===- StructurizeCFG.cpp -------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#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)); + +static cl::opt<bool> + RelaxedUniformRegions("structurizecfg-relaxed-uniform-regions", cl::Hidden, + cl::desc("Allow relaxed uniform region checks"), + cl::init(true)); + +// 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) + Phi->setIncomingValueForBlock(FI, 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) { + // Bool for if all sub-regions are uniform. + bool SubRegionsAreUniform = true; + // Count of how many direct children are conditional. + unsigned ConditionalDirectChildren = 0; + + 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; + + // One of our direct children is conditional. + ConditionalDirectChildren++; + + 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)) { + // Early exit if we cannot have relaxed uniform regions. + if (!RelaxedUniformRegions) + return false; + + SubRegionsAreUniform = false; + break; + } + } + } + } + + // Our region is uniform if: + // 1. All conditional branches that are direct children are uniform (checked + // above). + // 2. And either: + // a. All sub-regions are uniform. + // b. There is one or less conditional branches among the direct children. + return SubRegionsAreUniform || (ConditionalDirectChildren <= 1); +} + +/// 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); +} |