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

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