lib/Transforms/Scalar/StructurizeCFG.cpp

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