lib/Transforms/Scalar/StructurizeCFG.cpp

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