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