contrib/llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

   1 //===- StructurizeCFG.cpp -------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/ADT/DenseMap.h"
  11 #include "llvm/ADT/MapVector.h"
  12 #include "llvm/ADT/PostOrderIterator.h"
  13 #include "llvm/ADT/STLExtras.h"
  14 #include "llvm/ADT/SmallPtrSet.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/Analysis/DivergenceAnalysis.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/Analysis/RegionInfo.h"
  19 #include "llvm/Analysis/RegionIterator.h"
  20 #include "llvm/Analysis/RegionPass.h"
  21 #include "llvm/IR/Argument.h"
  22 #include "llvm/IR/BasicBlock.h"
  23 #include "llvm/IR/CFG.h"
  24 #include "llvm/IR/Constant.h"
  25 #include "llvm/IR/Constants.h"
  26 #include "llvm/IR/Dominators.h"
  27 #include "llvm/IR/Function.h"
  28 #include "llvm/IR/InstrTypes.h"
  29 #include "llvm/IR/Instruction.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/PatternMatch.h"
  33 #include "llvm/IR/Type.h"
  34 #include "llvm/IR/Use.h"
  35 #include "llvm/IR/User.h"
  36 #include "llvm/IR/Value.h"
  37 #include "llvm/Pass.h"
  38 #include "llvm/Support/Casting.h"
  39 #include "llvm/Support/Debug.h"
  40 #include "llvm/Support/ErrorHandling.h"
  41 #include "llvm/Support/raw_ostream.h"
  42 #include "llvm/Transforms/Scalar.h"
  43 #include "llvm/Transforms/Utils/SSAUpdater.h"
  44 #include <algorithm>
  45 #include <cassert>
  46 #include <utility>
  47
  48 using namespace llvm;
  49 using namespace llvm::PatternMatch;
  50
  51 #define DEBUG_TYPE "structurizecfg"
  52
  53 // The name for newly created blocks.
  54 static const char *const FlowBlockName = "Flow";
  55
  56 namespace {
  57
  58 // Definition of the complex types used in this pass.
  59
  60 using BBValuePair = std::pair<BasicBlock *, Value *>;
  61
  62 using RNVector = SmallVector<RegionNode *, 8>;
  63 using BBVector = SmallVector<BasicBlock *, 8>;
  64 using BranchVector = SmallVector<BranchInst *, 8>;
  65 using BBValueVector = SmallVector<BBValuePair, 2>;
  66
  67 using BBSet = SmallPtrSet<BasicBlock *, 8>;
  68
  69 using PhiMap = MapVector<PHINode *, BBValueVector>;
  70 using BB2BBVecMap = MapVector<BasicBlock *, BBVector>;
  71
  72 using BBPhiMap = DenseMap<BasicBlock *, PhiMap>;
  73 using BBPredicates = DenseMap<BasicBlock *, Value *>;
  74 using PredMap = DenseMap<BasicBlock *, BBPredicates>;
  75 using BB2BBMap = DenseMap<BasicBlock *, BasicBlock *>;
  76
  77 /// Finds the nearest common dominator of a set of BasicBlocks.
  78 ///
  79 /// For every BB you add to the set, you can specify whether we "remember" the
  80 /// block.  When you get the common dominator, you can also ask whether it's one
  81 /// of the blocks we remembered.
  82 class NearestCommonDominator {
  83   DominatorTree *DT;
  84   BasicBlock *Result = nullptr;
  85   bool ResultIsRemembered = false;
  86
  87   /// Add BB to the resulting dominator.
  88   void addBlock(BasicBlock *BB, bool Remember) {
  89     if (!Result) {
  90       Result = BB;
  91       ResultIsRemembered = Remember;
  92       return;
  93     }
  94
  95     BasicBlock *NewResult = DT->findNearestCommonDominator(Result, BB);
  96     if (NewResult != Result)
  97       ResultIsRemembered = false;
  98     if (NewResult == BB)
  99       ResultIsRemembered |= Remember;
 100     Result = NewResult;
 101   }
 102
 103 public:
 104   explicit NearestCommonDominator(DominatorTree *DomTree) : DT(DomTree) {}
 105
 106   void addBlock(BasicBlock *BB) {
 107     addBlock(BB, /* Remember = */ false);
 108   }
 109
 110   void addAndRememberBlock(BasicBlock *BB) {
 111     addBlock(BB, /* Remember = */ true);
 112   }
 113
 114   /// Get the nearest common dominator of all the BBs added via addBlock() and
 115   /// addAndRememberBlock().
 116   BasicBlock *result() { return Result; }
 117
 118   /// Is the BB returned by getResult() one of the blocks we added to the set
 119   /// with addAndRememberBlock()?
 120   bool resultIsRememberedBlock() { return ResultIsRemembered; }
 121 };
 122
 123 /// @brief Transforms the control flow graph on one single entry/exit region
 124 /// at a time.
 125 ///
 126 /// After the transform all "If"/"Then"/"Else" style control flow looks like
 127 /// this:
 128 ///
 129 /// \verbatim
 130 /// 1
 131 /// ||
 132 /// | |
 133 /// 2 |
 134 /// | /
 135 /// |/
 136 /// 3
 137 /// ||   Where:
 138 /// | |  1 = "If" block, calculates the condition
 139 /// 4 |  2 = "Then" subregion, runs if the condition is true
 140 /// | /  3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
 141 /// |/   4 = "Else" optional subregion, runs if the condition is false
 142 /// 5    5 = "End" block, also rejoins the control flow
 143 /// \endverbatim
 144 ///
 145 /// Control flow is expressed as a branch where the true exit goes into the
 146 /// "Then"/"Else" region, while the false exit skips the region
 147 /// The condition for the optional "Else" region is expressed as a PHI node.
 148 /// The incoming values of the PHI node are true for the "If" edge and false
 149 /// for the "Then" edge.
 150 ///
 151 /// Additionally to that even complicated loops look like this:
 152 ///
 153 /// \verbatim
 154 /// 1
 155 /// ||
 156 /// | |
 157 /// 2 ^  Where:
 158 /// | /  1 = "Entry" block
 159 /// |/   2 = "Loop" optional subregion, with all exits at "Flow" block
 160 /// 3    3 = "Flow" block, with back edge to entry block
 161 /// |
 162 /// \endverbatim
 163 ///
 164 /// The back edge of the "Flow" block is always on the false side of the branch
 165 /// while the true side continues the general flow. So the loop condition
 166 /// consist of a network of PHI nodes where the true incoming values expresses
 167 /// breaks and the false values expresses continue states.
 168 class StructurizeCFG : public RegionPass {
 169   bool SkipUniformRegions;
 170
 171   Type *Boolean;
 172   ConstantInt *BoolTrue;
 173   ConstantInt *BoolFalse;
 174   UndefValue *BoolUndef;
 175
 176   Function *Func;
 177   Region *ParentRegion;
 178
 179   DominatorTree *DT;
 180   LoopInfo *LI;
 181
 182   SmallVector<RegionNode *, 8> Order;
 183   BBSet Visited;
 184
 185   BBPhiMap DeletedPhis;
 186   BB2BBVecMap AddedPhis;
 187
 188   PredMap Predicates;
 189   BranchVector Conditions;
 190
 191   BB2BBMap Loops;
 192   PredMap LoopPreds;
 193   BranchVector LoopConds;
 194
 195   RegionNode *PrevNode;
 196
 197   void orderNodes();
 198
 199   void analyzeLoops(RegionNode *N);
 200
 201   Value *invert(Value *Condition);
 202
 203   Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
 204
 205   void gatherPredicates(RegionNode *N);
 206
 207   void collectInfos();
 208
 209   void insertConditions(bool Loops);
 210
 211   void delPhiValues(BasicBlock *From, BasicBlock *To);
 212
 213   void addPhiValues(BasicBlock *From, BasicBlock *To);
 214
 215   void setPhiValues();
 216
 217   void killTerminator(BasicBlock *BB);
 218
 219   void changeExit(RegionNode *Node, BasicBlock *NewExit,
 220                   bool IncludeDominator);
 221
 222   BasicBlock *getNextFlow(BasicBlock *Dominator);
 223
 224   BasicBlock *needPrefix(bool NeedEmpty);
 225
 226   BasicBlock *needPostfix(BasicBlock *Flow, bool ExitUseAllowed);
 227
 228   void setPrevNode(BasicBlock *BB);
 229
 230   bool dominatesPredicates(BasicBlock *BB, RegionNode *Node);
 231
 232   bool isPredictableTrue(RegionNode *Node);
 233
 234   void wireFlow(bool ExitUseAllowed, BasicBlock *LoopEnd);
 235
 236   void handleLoops(bool ExitUseAllowed, BasicBlock *LoopEnd);
 237
 238   void createFlow();
 239
 240   void rebuildSSA();
 241
 242 public:
 243   static char ID;
 244
 245   explicit StructurizeCFG(bool SkipUniformRegions = false)
 246       : RegionPass(ID), SkipUniformRegions(SkipUniformRegions) {
 247     initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
 248   }
 249
 250   bool doInitialization(Region *R, RGPassManager &RGM) override;
 251
 252   bool runOnRegion(Region *R, RGPassManager &RGM) override;
 253
 254   StringRef getPassName() const override { return "Structurize control flow"; }
 255
 256   void getAnalysisUsage(AnalysisUsage &AU) const override {
 257     if (SkipUniformRegions)
 258       AU.addRequired<DivergenceAnalysis>();
 259     AU.addRequiredID(LowerSwitchID);
 260     AU.addRequired<DominatorTreeWrapperPass>();
 261     AU.addRequired<LoopInfoWrapperPass>();
 262
 263     AU.addPreserved<DominatorTreeWrapperPass>();
 264     RegionPass::getAnalysisUsage(AU);
 265   }
 266 };
 267
 268 } // end anonymous namespace
 269
 270 char StructurizeCFG::ID = 0;
 271
 272 INITIALIZE_PASS_BEGIN(StructurizeCFG, "structurizecfg", "Structurize the CFG",
 273                       false, false)
 274 INITIALIZE_PASS_DEPENDENCY(DivergenceAnalysis)
 275 INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
 276 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 277 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass)
 278 INITIALIZE_PASS_END(StructurizeCFG, "structurizecfg", "Structurize the CFG",
 279                     false, false)
 280
 281 /// \brief Initialize the types and constants used in the pass
 282 bool StructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
 283   LLVMContext &Context = R->getEntry()->getContext();
 284
 285   Boolean = Type::getInt1Ty(Context);
 286   BoolTrue = ConstantInt::getTrue(Context);
 287   BoolFalse = ConstantInt::getFalse(Context);
 288   BoolUndef = UndefValue::get(Boolean);
 289
 290   return false;
 291 }
 292
 293 /// \brief Build up the general order of nodes
 294 void StructurizeCFG::orderNodes() {
 295   ReversePostOrderTraversal<Region*> RPOT(ParentRegion);
 296   SmallDenseMap<Loop*, unsigned, 8> LoopBlocks;
 297
 298   // The reverse post-order traversal of the list gives us an ordering close
 299   // to what we want.  The only problem with it is that sometimes backedges
 300   // for outer loops will be visited before backedges for inner loops.
 301   for (RegionNode *RN : RPOT) {
 302     BasicBlock *BB = RN->getEntry();
 303     Loop *Loop = LI->getLoopFor(BB);
 304     ++LoopBlocks[Loop];
 305   }
 306
 307   unsigned CurrentLoopDepth = 0;
 308   Loop *CurrentLoop = nullptr;
 309   for (auto I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
 310     BasicBlock *BB = (*I)->getEntry();
 311     unsigned LoopDepth = LI->getLoopDepth(BB);
 312
 313     if (is_contained(Order, *I))
 314       continue;
 315
 316     if (LoopDepth < CurrentLoopDepth) {
 317       // Make sure we have visited all blocks in this loop before moving back to
 318       // the outer loop.
 319
 320       auto LoopI = I;
 321       while (unsigned &BlockCount = LoopBlocks[CurrentLoop]) {
 322         LoopI++;
 323         BasicBlock *LoopBB = (*LoopI)->getEntry();
 324         if (LI->getLoopFor(LoopBB) == CurrentLoop) {
 325           --BlockCount;
 326           Order.push_back(*LoopI);
 327         }
 328       }
 329     }
 330
 331     CurrentLoop = LI->getLoopFor(BB);
 332     if (CurrentLoop)
 333       LoopBlocks[CurrentLoop]--;
 334
 335     CurrentLoopDepth = LoopDepth;
 336     Order.push_back(*I);
 337   }
 338
 339   // This pass originally used a post-order traversal and then operated on
 340   // the list in reverse. Now that we are using a reverse post-order traversal
 341   // rather than re-working the whole pass to operate on the list in order,
 342   // we just reverse the list and continue to operate on it in reverse.
 343   std::reverse(Order.begin(), Order.end());
 344 }
 345
 346 /// \brief Determine the end of the loops
 347 void StructurizeCFG::analyzeLoops(RegionNode *N) {
 348   if (N->isSubRegion()) {
 349     // Test for exit as back edge
 350     BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
 351     if (Visited.count(Exit))
 352       Loops[Exit] = N->getEntry();
 353
 354   } else {
 355     // Test for successors as back edge
 356     BasicBlock *BB = N->getNodeAs<BasicBlock>();
 357     BranchInst *Term = cast<BranchInst>(BB->getTerminator());
 358
 359     for (BasicBlock *Succ : Term->successors())
 360       if (Visited.count(Succ))
 361         Loops[Succ] = BB;
 362   }
 363 }
 364
 365 /// \brief Invert the given condition
 366 Value *StructurizeCFG::invert(Value *Condition) {
 367   // First: Check if it's a constant
 368   if (Constant *C = dyn_cast<Constant>(Condition))
 369     return ConstantExpr::getNot(C);
 370
 371   // Second: If the condition is already inverted, return the original value
 372   if (match(Condition, m_Not(m_Value(Condition))))
 373     return Condition;
 374
 375   if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
 376     // Third: Check all the users for an invert
 377     BasicBlock *Parent = Inst->getParent();
 378     for (User *U : Condition->users())
 379       if (Instruction *I = dyn_cast<Instruction>(U))
 380         if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
 381           return I;
 382
 383     // Last option: Create a new instruction
 384     return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator());
 385   }
 386
 387   if (Argument *Arg = dyn_cast<Argument>(Condition)) {
 388     BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
 389     return BinaryOperator::CreateNot(Condition,
 390                                      Arg->getName() + ".inv",
 391                                      EntryBlock.getTerminator());
 392   }
 393
 394   llvm_unreachable("Unhandled condition to invert");
 395 }
 396
 397 /// \brief Build the condition for one edge
 398 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
 399                                       bool Invert) {
 400   Value *Cond = Invert ? BoolFalse : BoolTrue;
 401   if (Term->isConditional()) {
 402     Cond = Term->getCondition();
 403
 404     if (Idx != (unsigned)Invert)
 405       Cond = invert(Cond);
 406   }
 407   return Cond;
 408 }
 409
 410 /// \brief Analyze the predecessors of each block and build up predicates
 411 void StructurizeCFG::gatherPredicates(RegionNode *N) {
 412   RegionInfo *RI = ParentRegion->getRegionInfo();
 413   BasicBlock *BB = N->getEntry();
 414   BBPredicates &Pred = Predicates[BB];
 415   BBPredicates &LPred = LoopPreds[BB];
 416
 417   for (BasicBlock *P : predecessors(BB)) {
 418     // Ignore it if it's a branch from outside into our region entry
 419     if (!ParentRegion->contains(P))
 420       continue;
 421
 422     Region *R = RI->getRegionFor(P);
 423     if (R == ParentRegion) {
 424       // It's a top level block in our region
 425       BranchInst *Term = cast<BranchInst>(P->getTerminator());
 426       for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
 427         BasicBlock *Succ = Term->getSuccessor(i);
 428         if (Succ != BB)
 429           continue;
 430
 431         if (Visited.count(P)) {
 432           // Normal forward edge
 433           if (Term->isConditional()) {
 434             // Try to treat it like an ELSE block
 435             BasicBlock *Other = Term->getSuccessor(!i);
 436             if (Visited.count(Other) && !Loops.count(Other) &&
 437                 !Pred.count(Other) && !Pred.count(P)) {
 438
 439               Pred[Other] = BoolFalse;
 440               Pred[P] = BoolTrue;
 441               continue;
 442             }
 443           }
 444           Pred[P] = buildCondition(Term, i, false);
 445         } else {
 446           // Back edge
 447           LPred[P] = buildCondition(Term, i, true);
 448         }
 449       }
 450     } else {
 451       // It's an exit from a sub region
 452       while (R->getParent() != ParentRegion)
 453         R = R->getParent();
 454
 455       // Edge from inside a subregion to its entry, ignore it
 456       if (*R == *N)
 457         continue;
 458
 459       BasicBlock *Entry = R->getEntry();
 460       if (Visited.count(Entry))
 461         Pred[Entry] = BoolTrue;
 462       else
 463         LPred[Entry] = BoolFalse;
 464     }
 465   }
 466 }
 467
 468 /// \brief Collect various loop and predicate infos
 469 void StructurizeCFG::collectInfos() {
 470   // Reset predicate
 471   Predicates.clear();
 472
 473   // and loop infos
 474   Loops.clear();
 475   LoopPreds.clear();
 476
 477   // Reset the visited nodes
 478   Visited.clear();
 479
 480   for (RegionNode *RN : reverse(Order)) {
 481     DEBUG(dbgs() << "Visiting: "
 482                  << (RN->isSubRegion() ? "SubRegion with entry: " : "")
 483                  << RN->getEntry()->getName() << " Loop Depth: "
 484                  << LI->getLoopDepth(RN->getEntry()) << "\n");
 485
 486     // Analyze all the conditions leading to a node
 487     gatherPredicates(RN);
 488
 489     // Remember that we've seen this node
 490     Visited.insert(RN->getEntry());
 491
 492     // Find the last back edges
 493     analyzeLoops(RN);
 494   }
 495 }
 496
 497 /// \brief Insert the missing branch conditions
 498 void StructurizeCFG::insertConditions(bool Loops) {
 499   BranchVector &Conds = Loops ? LoopConds : Conditions;
 500   Value *Default = Loops ? BoolTrue : BoolFalse;
 501   SSAUpdater PhiInserter;
 502
 503   for (BranchInst *Term : Conds) {
 504     assert(Term->isConditional());
 505
 506     BasicBlock *Parent = Term->getParent();
 507     BasicBlock *SuccTrue = Term->getSuccessor(0);
 508     BasicBlock *SuccFalse = Term->getSuccessor(1);
 509
 510     PhiInserter.Initialize(Boolean, "");
 511     PhiInserter.AddAvailableValue(&Func->getEntryBlock(), Default);
 512     PhiInserter.AddAvailableValue(Loops ? SuccFalse : Parent, Default);
 513
 514     BBPredicates &Preds = Loops ? LoopPreds[SuccFalse] : Predicates[SuccTrue];
 515
 516     NearestCommonDominator Dominator(DT);
 517     Dominator.addBlock(Parent);
 518
 519     Value *ParentValue = nullptr;
 520     for (std::pair<BasicBlock *, Value *> BBAndPred : Preds) {
 521       BasicBlock *BB = BBAndPred.first;
 522       Value *Pred = BBAndPred.second;
 523
 524       if (BB == Parent) {
 525         ParentValue = Pred;
 526         break;
 527       }
 528       PhiInserter.AddAvailableValue(BB, Pred);
 529       Dominator.addAndRememberBlock(BB);
 530     }
 531
 532     if (ParentValue) {
 533       Term->setCondition(ParentValue);
 534     } else {
 535       if (!Dominator.resultIsRememberedBlock())
 536         PhiInserter.AddAvailableValue(Dominator.result(), Default);
 537
 538       Term->setCondition(PhiInserter.GetValueInMiddleOfBlock(Parent));
 539     }
 540   }
 541 }
 542
 543 /// \brief Remove all PHI values coming from "From" into "To" and remember
 544 /// them in DeletedPhis
 545 void StructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
 546   PhiMap &Map = DeletedPhis[To];
 547   for (PHINode &Phi : To->phis()) {
 548     while (Phi.getBasicBlockIndex(From) != -1) {
 549       Value *Deleted = Phi.removeIncomingValue(From, false);
 550       Map[&Phi].push_back(std::make_pair(From, Deleted));
 551     }
 552   }
 553 }
 554
 555 /// \brief Add a dummy PHI value as soon as we knew the new predecessor
 556 void StructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
 557   for (PHINode &Phi : To->phis()) {
 558     Value *Undef = UndefValue::get(Phi.getType());
 559     Phi.addIncoming(Undef, From);
 560   }
 561   AddedPhis[To].push_back(From);
 562 }
 563
 564 /// \brief Add the real PHI value as soon as everything is set up
 565 void StructurizeCFG::setPhiValues() {
 566   SSAUpdater Updater;
 567   for (const auto &AddedPhi : AddedPhis) {
 568     BasicBlock *To = AddedPhi.first;
 569     const BBVector &From = AddedPhi.second;
 570
 571     if (!DeletedPhis.count(To))
 572       continue;
 573
 574     PhiMap &Map = DeletedPhis[To];
 575     for (const auto &PI : Map) {
 576       PHINode *Phi = PI.first;
 577       Value *Undef = UndefValue::get(Phi->getType());
 578       Updater.Initialize(Phi->getType(), "");
 579       Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
 580       Updater.AddAvailableValue(To, Undef);
 581
 582       NearestCommonDominator Dominator(DT);
 583       Dominator.addBlock(To);
 584       for (const auto &VI : PI.second) {
 585         Updater.AddAvailableValue(VI.first, VI.second);
 586         Dominator.addAndRememberBlock(VI.first);
 587       }
 588
 589       if (!Dominator.resultIsRememberedBlock())
 590         Updater.AddAvailableValue(Dominator.result(), Undef);
 591
 592       for (BasicBlock *FI : From) {
 593         int Idx = Phi->getBasicBlockIndex(FI);
 594         assert(Idx != -1);
 595         Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(FI));
 596       }
 597     }
 598
 599     DeletedPhis.erase(To);
 600   }
 601   assert(DeletedPhis.empty());
 602 }
 603
 604 /// \brief Remove phi values from all successors and then remove the terminator.
 605 void StructurizeCFG::killTerminator(BasicBlock *BB) {
 606   TerminatorInst *Term = BB->getTerminator();
 607   if (!Term)
 608     return;
 609
 610   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
 611        SI != SE; ++SI)
 612     delPhiValues(BB, *SI);
 613
 614   Term->eraseFromParent();
 615 }
 616
 617 /// \brief Let node exit(s) point to NewExit
 618 void StructurizeCFG::changeExit(RegionNode *Node, BasicBlock *NewExit,
 619                                 bool IncludeDominator) {
 620   if (Node->isSubRegion()) {
 621     Region *SubRegion = Node->getNodeAs<Region>();
 622     BasicBlock *OldExit = SubRegion->getExit();
 623     BasicBlock *Dominator = nullptr;
 624
 625     // Find all the edges from the sub region to the exit
 626     for (auto BBI = pred_begin(OldExit), E = pred_end(OldExit); BBI != E;) {
 627       // Incrememt BBI before mucking with BB's terminator.
 628       BasicBlock *BB = *BBI++;
 629
 630       if (!SubRegion->contains(BB))
 631         continue;
 632
 633       // Modify the edges to point to the new exit
 634       delPhiValues(BB, OldExit);
 635       BB->getTerminator()->replaceUsesOfWith(OldExit, NewExit);
 636       addPhiValues(BB, NewExit);
 637
 638       // Find the new dominator (if requested)
 639       if (IncludeDominator) {
 640         if (!Dominator)
 641           Dominator = BB;
 642         else
 643           Dominator = DT->findNearestCommonDominator(Dominator, BB);
 644       }
 645     }
 646
 647     // Change the dominator (if requested)
 648     if (Dominator)
 649       DT->changeImmediateDominator(NewExit, Dominator);
 650
 651     // Update the region info
 652     SubRegion->replaceExit(NewExit);
 653   } else {
 654     BasicBlock *BB = Node->getNodeAs<BasicBlock>();
 655     killTerminator(BB);
 656     BranchInst::Create(NewExit, BB);
 657     addPhiValues(BB, NewExit);
 658     if (IncludeDominator)
 659       DT->changeImmediateDominator(NewExit, BB);
 660   }
 661 }
 662
 663 /// \brief Create a new flow node and update dominator tree and region info
 664 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
 665   LLVMContext &Context = Func->getContext();
 666   BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
 667                        Order.back()->getEntry();
 668   BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
 669                                         Func, Insert);
 670   DT->addNewBlock(Flow, Dominator);
 671   ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
 672   return Flow;
 673 }
 674
 675 /// \brief Create a new or reuse the previous node as flow node
 676 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
 677   BasicBlock *Entry = PrevNode->getEntry();
 678
 679   if (!PrevNode->isSubRegion()) {
 680     killTerminator(Entry);
 681     if (!NeedEmpty || Entry->getFirstInsertionPt() == Entry->end())
 682       return Entry;
 683   }
 684
 685   // create a new flow node
 686   BasicBlock *Flow = getNextFlow(Entry);
 687
 688   // and wire it up
 689   changeExit(PrevNode, Flow, true);
 690   PrevNode = ParentRegion->getBBNode(Flow);
 691   return Flow;
 692 }
 693
 694 /// \brief Returns the region exit if possible, otherwise just a new flow node
 695 BasicBlock *StructurizeCFG::needPostfix(BasicBlock *Flow,
 696                                         bool ExitUseAllowed) {
 697   if (!Order.empty() || !ExitUseAllowed)
 698     return getNextFlow(Flow);
 699
 700   BasicBlock *Exit = ParentRegion->getExit();
 701   DT->changeImmediateDominator(Exit, Flow);
 702   addPhiValues(Flow, Exit);
 703   return Exit;
 704 }
 705
 706 /// \brief Set the previous node
 707 void StructurizeCFG::setPrevNode(BasicBlock *BB) {
 708   PrevNode = ParentRegion->contains(BB) ? ParentRegion->getBBNode(BB)
 709                                         : nullptr;
 710 }
 711
 712 /// \brief Does BB dominate all the predicates of Node?
 713 bool StructurizeCFG::dominatesPredicates(BasicBlock *BB, RegionNode *Node) {
 714   BBPredicates &Preds = Predicates[Node->getEntry()];
 715   return llvm::all_of(Preds, [&](std::pair<BasicBlock *, Value *> Pred) {
 716     return DT->dominates(BB, Pred.first);
 717   });
 718 }
 719
 720 /// \brief Can we predict that this node will always be called?
 721 bool StructurizeCFG::isPredictableTrue(RegionNode *Node) {
 722   BBPredicates &Preds = Predicates[Node->getEntry()];
 723   bool Dominated = false;
 724
 725   // Regionentry is always true
 726   if (!PrevNode)
 727     return true;
 728
 729   for (std::pair<BasicBlock*, Value*> Pred : Preds) {
 730     BasicBlock *BB = Pred.first;
 731     Value *V = Pred.second;
 732
 733     if (V != BoolTrue)
 734       return false;
 735
 736     if (!Dominated && DT->dominates(BB, PrevNode->getEntry()))
 737       Dominated = true;
 738   }
 739
 740   // TODO: The dominator check is too strict
 741   return Dominated;
 742 }
 743
 744 /// Take one node from the order vector and wire it up
 745 void StructurizeCFG::wireFlow(bool ExitUseAllowed,
 746                               BasicBlock *LoopEnd) {
 747   RegionNode *Node = Order.pop_back_val();
 748   Visited.insert(Node->getEntry());
 749
 750   if (isPredictableTrue(Node)) {
 751     // Just a linear flow
 752     if (PrevNode) {
 753       changeExit(PrevNode, Node->getEntry(), true);
 754     }
 755     PrevNode = Node;
 756   } else {
 757     // Insert extra prefix node (or reuse last one)
 758     BasicBlock *Flow = needPrefix(false);
 759
 760     // Insert extra postfix node (or use exit instead)
 761     BasicBlock *Entry = Node->getEntry();
 762     BasicBlock *Next = needPostfix(Flow, ExitUseAllowed);
 763
 764     // let it point to entry and next block
 765     Conditions.push_back(BranchInst::Create(Entry, Next, BoolUndef, Flow));
 766     addPhiValues(Flow, Entry);
 767     DT->changeImmediateDominator(Entry, Flow);
 768
 769     PrevNode = Node;
 770     while (!Order.empty() && !Visited.count(LoopEnd) &&
 771            dominatesPredicates(Entry, Order.back())) {
 772       handleLoops(false, LoopEnd);
 773     }
 774
 775     changeExit(PrevNode, Next, false);
 776     setPrevNode(Next);
 777   }
 778 }
 779
 780 void StructurizeCFG::handleLoops(bool ExitUseAllowed,
 781                                  BasicBlock *LoopEnd) {
 782   RegionNode *Node = Order.back();
 783   BasicBlock *LoopStart = Node->getEntry();
 784
 785   if (!Loops.count(LoopStart)) {
 786     wireFlow(ExitUseAllowed, LoopEnd);
 787     return;
 788   }
 789
 790   if (!isPredictableTrue(Node))
 791     LoopStart = needPrefix(true);
 792
 793   LoopEnd = Loops[Node->getEntry()];
 794   wireFlow(false, LoopEnd);
 795   while (!Visited.count(LoopEnd)) {
 796     handleLoops(false, LoopEnd);
 797   }
 798
 799   // If the start of the loop is the entry block, we can't branch to it so
 800   // insert a new dummy entry block.
 801   Function *LoopFunc = LoopStart->getParent();
 802   if (LoopStart == &LoopFunc->getEntryBlock()) {
 803     LoopStart->setName("entry.orig");
 804
 805     BasicBlock *NewEntry =
 806       BasicBlock::Create(LoopStart->getContext(),
 807                          "entry",
 808                          LoopFunc,
 809                          LoopStart);
 810     BranchInst::Create(LoopStart, NewEntry);
 811     DT->setNewRoot(NewEntry);
 812   }
 813
 814   // Create an extra loop end node
 815   LoopEnd = needPrefix(false);
 816   BasicBlock *Next = needPostfix(LoopEnd, ExitUseAllowed);
 817   LoopConds.push_back(BranchInst::Create(Next, LoopStart,
 818                                          BoolUndef, LoopEnd));
 819   addPhiValues(LoopEnd, LoopStart);
 820   setPrevNode(Next);
 821 }
 822
 823 /// After this function control flow looks like it should be, but
 824 /// branches and PHI nodes only have undefined conditions.
 825 void StructurizeCFG::createFlow() {
 826   BasicBlock *Exit = ParentRegion->getExit();
 827   bool EntryDominatesExit = DT->dominates(ParentRegion->getEntry(), Exit);
 828
 829   DeletedPhis.clear();
 830   AddedPhis.clear();
 831   Conditions.clear();
 832   LoopConds.clear();
 833
 834   PrevNode = nullptr;
 835   Visited.clear();
 836
 837   while (!Order.empty()) {
 838     handleLoops(EntryDominatesExit, nullptr);
 839   }
 840
 841   if (PrevNode)
 842     changeExit(PrevNode, Exit, EntryDominatesExit);
 843   else
 844     assert(EntryDominatesExit);
 845 }
 846
 847 /// Handle a rare case where the disintegrated nodes instructions
 848 /// no longer dominate all their uses. Not sure if this is really nessasary
 849 void StructurizeCFG::rebuildSSA() {
 850   SSAUpdater Updater;
 851   for (BasicBlock *BB : ParentRegion->blocks())
 852     for (Instruction &I : *BB) {
 853       bool Initialized = false;
 854       // We may modify the use list as we iterate over it, so be careful to
 855       // compute the next element in the use list at the top of the loop.
 856       for (auto UI = I.use_begin(), E = I.use_end(); UI != E;) {
 857         Use &U = *UI++;
 858         Instruction *User = cast<Instruction>(U.getUser());
 859         if (User->getParent() == BB) {
 860           continue;
 861         } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
 862           if (UserPN->getIncomingBlock(U) == BB)
 863             continue;
 864         }
 865
 866         if (DT->dominates(&I, User))
 867           continue;
 868
 869         if (!Initialized) {
 870           Value *Undef = UndefValue::get(I.getType());
 871           Updater.Initialize(I.getType(), "");
 872           Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
 873           Updater.AddAvailableValue(BB, &I);
 874           Initialized = true;
 875         }
 876         Updater.RewriteUseAfterInsertions(U);
 877       }
 878     }
 879 }
 880
 881 static bool hasOnlyUniformBranches(const Region *R,
 882                                    const DivergenceAnalysis &DA) {
 883   for (const BasicBlock *BB : R->blocks()) {
 884     const BranchInst *Br = dyn_cast<BranchInst>(BB->getTerminator());
 885     if (!Br || !Br->isConditional())
 886       continue;
 887
 888     if (!DA.isUniform(Br->getCondition()))
 889       return false;
 890     DEBUG(dbgs() << "BB: " << BB->getName() << " has uniform terminator\n");
 891   }
 892   return true;
 893 }
 894
 895 /// \brief Run the transformation for each region found
 896 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
 897   if (R->isTopLevelRegion())
 898     return false;
 899
 900   if (SkipUniformRegions) {
 901     // TODO: We could probably be smarter here with how we handle sub-regions.
 902     auto &DA = getAnalysis<DivergenceAnalysis>();
 903     if (hasOnlyUniformBranches(R, DA)) {
 904       DEBUG(dbgs() << "Skipping region with uniform control flow: " << *R << '\n');
 905
 906       // Mark all direct child block terminators as having been treated as
 907       // uniform. To account for a possible future in which non-uniform
 908       // sub-regions are treated more cleverly, indirect children are not
 909       // marked as uniform.
 910       MDNode *MD = MDNode::get(R->getEntry()->getParent()->getContext(), {});
 911       for (RegionNode *E : R->elements()) {
 912         if (E->isSubRegion())
 913           continue;
 914
 915         if (Instruction *Term = E->getEntry()->getTerminator())
 916           Term->setMetadata("structurizecfg.uniform", MD);
 917       }
 918
 919       return false;
 920     }
 921   }
 922
 923   Func = R->getEntry()->getParent();
 924   ParentRegion = R;
 925
 926   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 927   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 928
 929   orderNodes();
 930   collectInfos();
 931   createFlow();
 932   insertConditions(false);
 933   insertConditions(true);
 934   setPhiValues();
 935   rebuildSSA();
 936
 937   // Cleanup
 938   Order.clear();
 939   Visited.clear();
 940   DeletedPhis.clear();
 941   AddedPhis.clear();
 942   Predicates.clear();
 943   Conditions.clear();
 944   Loops.clear();
 945   LoopPreds.clear();
 946   LoopConds.clear();
 947
 948   return true;
 949 }
 950
 951 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
 952   return new StructurizeCFG(SkipUniformRegions);
 953 }