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