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