lib/Target/R600/AMDGPUStructurizeCFG.cpp

   1 //===-- AMDGPUStructurizeCFG.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 /// \file
  11 /// The pass implemented in this file transforms the programs control flow
  12 /// graph into a form that's suitable for code generation on hardware that
  13 /// implements control flow by execution masking. This currently includes all
  14 /// AMD GPUs but may as well be useful for other types of hardware.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "AMDGPU.h"
  19 #include "llvm/Module.h"
  20 #include "llvm/ADT/SCCIterator.h"
  21 #include "llvm/Analysis/RegionIterator.h"
  22 #include "llvm/Analysis/RegionInfo.h"
  23 #include "llvm/Analysis/RegionPass.h"
  24 #include "llvm/Transforms/Utils/SSAUpdater.h"
  25
  26 using namespace llvm;
  27
  28 namespace {
  29
  30 // Definition of the complex types used in this pass.
  31
  32 typedef std::pair<BasicBlock *, Value *> BBValuePair;
  33 typedef ArrayRef<BasicBlock*> BBVecRef;
  34
  35 typedef SmallVector<RegionNode*, 8> RNVector;
  36 typedef SmallVector<BasicBlock*, 8> BBVector;
  37 typedef SmallVector<BBValuePair, 2> BBValueVector;
  38
  39 typedef DenseMap<PHINode *, BBValueVector> PhiMap;
  40 typedef DenseMap<BasicBlock *, PhiMap> BBPhiMap;
  41 typedef DenseMap<BasicBlock *, Value *> BBPredicates;
  42 typedef DenseMap<BasicBlock *, BBPredicates> PredMap;
  43 typedef DenseMap<BasicBlock *, unsigned> VisitedMap;
  44
  45 // The name for newly created blocks.
  46
  47 static const char *FlowBlockName = "Flow";
  48
  49 /// @brief Transforms the control flow graph on one single entry/exit region
  50 /// at a time.
  51 ///
  52 /// After the transform all "If"/"Then"/"Else" style control flow looks like
  53 /// this:
  54 ///
  55 /// \verbatim
  56 /// 1
  57 /// ||
  58 /// | |
  59 /// 2 |
  60 /// | /
  61 /// |/
  62 /// 3
  63 /// ||   Where:
  64 /// | |  1 = "If" block, calculates the condition
  65 /// 4 |  2 = "Then" subregion, runs if the condition is true
  66 /// | /  3 = "Flow" blocks, newly inserted flow blocks, rejoins the flow
  67 /// |/   4 = "Else" optional subregion, runs if the condition is false
  68 /// 5    5 = "End" block, also rejoins the control flow
  69 /// \endverbatim
  70 ///
  71 /// Control flow is expressed as a branch where the true exit goes into the
  72 /// "Then"/"Else" region, while the false exit skips the region
  73 /// The condition for the optional "Else" region is expressed as a PHI node.
  74 /// The incomming values of the PHI node are true for the "If" edge and false
  75 /// for the "Then" edge.
  76 ///
  77 /// Additionally to that even complicated loops look like this:
  78 ///
  79 /// \verbatim
  80 /// 1
  81 /// ||
  82 /// | |
  83 /// 2 ^  Where:
  84 /// | /  1 = "Entry" block
  85 /// |/   2 = "Loop" optional subregion, with all exits at "Flow" block
  86 /// 3    3 = "Flow" block, with back edge to entry block
  87 /// |
  88 /// \endverbatim
  89 ///
  90 /// The back edge of the "Flow" block is always on the false side of the branch
  91 /// while the true side continues the general flow. So the loop condition
  92 /// consist of a network of PHI nodes where the true incoming values expresses
  93 /// breaks and the false values expresses continue states.
  94 class AMDGPUStructurizeCFG : public RegionPass {
  95
  96   static char ID;
  97
  98   Type *Boolean;
  99   ConstantInt *BoolTrue;
 100   ConstantInt *BoolFalse;
 101   UndefValue *BoolUndef;
 102
 103   Function *Func;
 104   Region *ParentRegion;
 105
 106   DominatorTree *DT;
 107
 108   RNVector Order;
 109   VisitedMap Visited;
 110   PredMap Predicates;
 111   BBPhiMap DeletedPhis;
 112   BBVector FlowsInserted;
 113
 114   BasicBlock *LoopStart;
 115   BasicBlock *LoopEnd;
 116   BBPredicates LoopPred;
 117
 118   void orderNodes();
 119
 120   void buildPredicate(BranchInst *Term, unsigned Idx,
 121                       BBPredicates &Pred, bool Invert);
 122
 123   void analyzeBlock(BasicBlock *BB);
 124
 125   void analyzeLoop(BasicBlock *BB, unsigned &LoopIdx);
 126
 127   void collectInfos();
 128
 129   bool dominatesPredicates(BasicBlock *A, BasicBlock *B);
 130
 131   void killTerminator(BasicBlock *BB);
 132
 133   RegionNode *skipChained(RegionNode *Node);
 134
 135   void delPhiValues(BasicBlock *From, BasicBlock *To);
 136
 137   void addPhiValues(BasicBlock *From, BasicBlock *To);
 138
 139   BasicBlock *getNextFlow(BasicBlock *Prev);
 140
 141   bool isPredictableTrue(BasicBlock *Prev, BasicBlock *Node);
 142
 143   BasicBlock *wireFlowBlock(BasicBlock *Prev, RegionNode *Node);
 144
 145   void createFlow();
 146
 147   void insertConditions();
 148
 149   void rebuildSSA();
 150
 151 public:
 152   AMDGPUStructurizeCFG():
 153     RegionPass(ID) {
 154
 155     initializeRegionInfoPass(*PassRegistry::getPassRegistry());
 156   }
 157
 158   virtual bool doInitialization(Region *R, RGPassManager &RGM);
 159
 160   virtual bool runOnRegion(Region *R, RGPassManager &RGM);
 161
 162   virtual const char *getPassName() const {
 163     return "AMDGPU simplify control flow";
 164   }
 165
 166   void getAnalysisUsage(AnalysisUsage &AU) const {
 167
 168     AU.addRequired<DominatorTree>();
 169     AU.addPreserved<DominatorTree>();
 170     RegionPass::getAnalysisUsage(AU);
 171   }
 172
 173 };
 174
 175 } // end anonymous namespace
 176
 177 char AMDGPUStructurizeCFG::ID = 0;
 178
 179 /// \brief Initialize the types and constants used in the pass
 180 bool AMDGPUStructurizeCFG::doInitialization(Region *R, RGPassManager &RGM) {
 181
 182   LLVMContext &Context = R->getEntry()->getContext();
 183
 184   Boolean = Type::getInt1Ty(Context);
 185   BoolTrue = ConstantInt::getTrue(Context);
 186   BoolFalse = ConstantInt::getFalse(Context);
 187   BoolUndef = UndefValue::get(Boolean);
 188
 189   return false;
 190 }
 191
 192 /// \brief Build up the general order of nodes
 193 void AMDGPUStructurizeCFG::orderNodes() {
 194
 195   scc_iterator<Region *> I = scc_begin(ParentRegion),
 196                          E = scc_end(ParentRegion);
 197   for (Order.clear(); I != E; ++I) {
 198     std::vector<RegionNode *> &Nodes = *I;
 199     Order.append(Nodes.begin(), Nodes.end());
 200   }
 201 }
 202
 203 /// \brief Build blocks and loop predicates
 204 void AMDGPUStructurizeCFG::buildPredicate(BranchInst *Term, unsigned Idx,
 205                                           BBPredicates &Pred, bool Invert) {
 206
 207   Value *True = Invert ? BoolFalse : BoolTrue;
 208   Value *False = Invert ? BoolTrue : BoolFalse;
 209
 210   RegionInfo *RI = ParentRegion->getRegionInfo();
 211   BasicBlock *BB = Term->getParent();
 212
 213   // Handle the case where multiple regions start at the same block
 214   Region *R = BB != ParentRegion->getEntry() ?
 215               RI->getRegionFor(BB) : ParentRegion;
 216
 217   if (R == ParentRegion) {
 218     // It's a top level block in our region
 219     Value *Cond = True;
 220     if (Term->isConditional()) {
 221       BasicBlock *Other = Term->getSuccessor(!Idx);
 222
 223       if (Visited.count(Other)) {
 224         if (!Pred.count(Other))
 225           Pred[Other] = False;
 226
 227         if (!Pred.count(BB))
 228           Pred[BB] = True;
 229         return;
 230       }
 231       Cond = Term->getCondition();
 232
 233       if (Idx != Invert)
 234         Cond = BinaryOperator::CreateNot(Cond, "", Term);
 235     }
 236
 237     Pred[BB] = Cond;
 238
 239   } else if (ParentRegion->contains(R)) {
 240     // It's a block in a sub region
 241     while(R->getParent() != ParentRegion)
 242       R = R->getParent();
 243
 244     Pred[R->getEntry()] = True;
 245
 246   } else {
 247     // It's a branch from outside into our parent region
 248     Pred[BB] = True;
 249   }
 250 }
 251
 252 /// \brief Analyze the successors of each block and build up predicates
 253 void AMDGPUStructurizeCFG::analyzeBlock(BasicBlock *BB) {
 254
 255   pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 256   BBPredicates &Pred = Predicates[BB];
 257
 258   for (; PI != PE; ++PI) {
 259     BranchInst *Term = cast<BranchInst>((*PI)->getTerminator());
 260
 261     for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
 262       BasicBlock *Succ = Term->getSuccessor(i);
 263       if (Succ != BB)
 264         continue;
 265       buildPredicate(Term, i, Pred, false);
 266     }
 267   }
 268 }
 269
 270 /// \brief Analyze the conditions leading to loop to a previous block
 271 void AMDGPUStructurizeCFG::analyzeLoop(BasicBlock *BB, unsigned &LoopIdx) {
 272
 273   BranchInst *Term = cast<BranchInst>(BB->getTerminator());
 274
 275   for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
 276     BasicBlock *Succ = Term->getSuccessor(i);
 277
 278     // Ignore it if it's not a back edge
 279     if (!Visited.count(Succ))
 280       continue;
 281
 282     buildPredicate(Term, i, LoopPred, true);
 283
 284     LoopEnd = BB;
 285     if (Visited[Succ] < LoopIdx) {
 286       LoopIdx = Visited[Succ];
 287       LoopStart = Succ;
 288     }
 289   }
 290 }
 291
 292 /// \brief Collect various loop and predicate infos
 293 void AMDGPUStructurizeCFG::collectInfos() {
 294
 295   unsigned Number = 0, LoopIdx = ~0;
 296
 297   // Reset predicate
 298   Predicates.clear();
 299
 300   // and loop infos
 301   LoopStart = LoopEnd = 0;
 302   LoopPred.clear();
 303
 304   RNVector::reverse_iterator OI = Order.rbegin(), OE = Order.rend();
 305   for (Visited.clear(); OI != OE; Visited[(*OI++)->getEntry()] = ++Number) {
 306
 307     // Analyze all the conditions leading to a node
 308     analyzeBlock((*OI)->getEntry());
 309
 310     if ((*OI)->isSubRegion())
 311       continue;
 312
 313     // Find the first/last loop nodes and loop predicates
 314     analyzeLoop((*OI)->getNodeAs<BasicBlock>(), LoopIdx);
 315   }
 316 }
 317
 318 /// \brief Does A dominate all the predicates of B ?
 319 bool AMDGPUStructurizeCFG::dominatesPredicates(BasicBlock *A, BasicBlock *B) {
 320
 321   BBPredicates &Preds = Predicates[B];
 322   for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end();
 323        PI != PE; ++PI) {
 324
 325     if (!DT->dominates(A, PI->first))
 326       return false;
 327   }
 328   return true;
 329 }
 330
 331 /// \brief Remove phi values from all successors and the remove the terminator.
 332 void AMDGPUStructurizeCFG::killTerminator(BasicBlock *BB) {
 333
 334   TerminatorInst *Term = BB->getTerminator();
 335   if (!Term)
 336     return;
 337
 338   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
 339        SI != SE; ++SI) {
 340
 341     delPhiValues(BB, *SI);
 342   }
 343
 344   Term->eraseFromParent();
 345 }
 346
 347 /// First: Skip forward to the first region node that either isn't a subregion or not
 348 /// dominating it's exit, remove all the skipped nodes from the node order.
 349 ///
 350 /// Second: Handle the first successor directly if the resulting nodes successor
 351 /// predicates are still dominated by the original entry
 352 RegionNode *AMDGPUStructurizeCFG::skipChained(RegionNode *Node) {
 353
 354   BasicBlock *Entry = Node->getEntry();
 355
 356   // Skip forward as long as it is just a linear flow
 357   while (true) {
 358     BasicBlock *Entry = Node->getEntry();
 359     BasicBlock *Exit;
 360
 361     if (Node->isSubRegion()) {
 362       Exit = Node->getNodeAs<Region>()->getExit();
 363     } else {
 364       TerminatorInst *Term = Entry->getTerminator();
 365       if (Term->getNumSuccessors() != 1)
 366         break;
 367       Exit = Term->getSuccessor(0);
 368     }
 369
 370     // It's a back edge, break here so we can insert a loop node
 371     if (!Visited.count(Exit))
 372       return Node;
 373
 374     // More than node edges are pointing to exit
 375     if (!DT->dominates(Entry, Exit))
 376       return Node;
 377
 378     RegionNode *Next = ParentRegion->getNode(Exit);
 379     RNVector::iterator I = std::find(Order.begin(), Order.end(), Next);
 380     assert(I != Order.end());
 381
 382     Visited.erase(Next->getEntry());
 383     Order.erase(I);
 384     Node = Next;
 385   }
 386
 387   BasicBlock *BB = Node->getEntry();
 388   TerminatorInst *Term = BB->getTerminator();
 389   if (Term->getNumSuccessors() != 2)
 390     return Node;
 391
 392   // Our node has exactly two succesors, check if we can handle
 393   // any of them directly
 394   BasicBlock *Succ = Term->getSuccessor(0);
 395   if (!Visited.count(Succ) || !dominatesPredicates(Entry, Succ)) {
 396     Succ = Term->getSuccessor(1);
 397     if (!Visited.count(Succ) || !dominatesPredicates(Entry, Succ))
 398       return Node;
 399   } else {
 400     BasicBlock *Succ2 = Term->getSuccessor(1);
 401     if (Visited.count(Succ2) && Visited[Succ] > Visited[Succ2] &&
 402         dominatesPredicates(Entry, Succ2))
 403       Succ = Succ2;
 404   }
 405
 406   RegionNode *Next = ParentRegion->getNode(Succ);
 407   RNVector::iterator E = Order.end();
 408   RNVector::iterator I = std::find(Order.begin(), E, Next);
 409   assert(I != E);
 410
 411   killTerminator(BB);
 412   FlowsInserted.push_back(BB);
 413   Visited.erase(Succ);
 414   Order.erase(I);
 415   return ParentRegion->getNode(wireFlowBlock(BB, Next));
 416 }
 417
 418 /// \brief Remove all PHI values coming from "From" into "To" and remember
 419 /// them in DeletedPhis
 420 void AMDGPUStructurizeCFG::delPhiValues(BasicBlock *From, BasicBlock *To) {
 421
 422   PhiMap &Map = DeletedPhis[To];
 423   for (BasicBlock::iterator I = To->begin(), E = To->end();
 424        I != E && isa<PHINode>(*I);) {
 425
 426     PHINode &Phi = cast<PHINode>(*I++);
 427     while (Phi.getBasicBlockIndex(From) != -1) {
 428       Value *Deleted = Phi.removeIncomingValue(From, false);
 429       Map[&Phi].push_back(std::make_pair(From, Deleted));
 430     }
 431   }
 432 }
 433
 434 /// \brief Add the PHI values back once we knew the new predecessor
 435 void AMDGPUStructurizeCFG::addPhiValues(BasicBlock *From, BasicBlock *To) {
 436
 437   if (!DeletedPhis.count(To))
 438     return;
 439
 440   PhiMap &Map = DeletedPhis[To];
 441   SSAUpdater Updater;
 442
 443   for (PhiMap::iterator I = Map.begin(), E = Map.end(); I != E; ++I) {
 444
 445     PHINode *Phi = I->first;
 446     Updater.Initialize(Phi->getType(), "");
 447     BasicBlock *Fallback = To;
 448     bool HaveFallback = false;
 449
 450     for (BBValueVector::iterator VI = I->second.begin(), VE = I->second.end();
 451          VI != VE; ++VI) {
 452
 453       Updater.AddAvailableValue(VI->first, VI->second);
 454       BasicBlock *Dom = DT->findNearestCommonDominator(Fallback, VI->first);
 455       if (Dom == VI->first)
 456         HaveFallback = true;
 457       else if (Dom != Fallback)
 458         HaveFallback = false;
 459       Fallback = Dom;
 460     }
 461     if (!HaveFallback) {
 462       Value *Undef = UndefValue::get(Phi->getType());
 463       Updater.AddAvailableValue(Fallback, Undef);
 464     }
 465
 466     Phi->addIncoming(Updater.GetValueAtEndOfBlock(From), From);
 467   }
 468   DeletedPhis.erase(To);
 469 }
 470
 471 /// \brief Create a new flow node and update dominator tree and region info
 472 BasicBlock *AMDGPUStructurizeCFG::getNextFlow(BasicBlock *Prev) {
 473
 474   LLVMContext &Context = Func->getContext();
 475   BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
 476                        Order.back()->getEntry();
 477   BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
 478                                         Func, Insert);
 479   DT->addNewBlock(Flow, Prev);
 480   ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
 481   FlowsInserted.push_back(Flow);
 482   return Flow;
 483 }
 484
 485 /// \brief Can we predict that this node will always be called?
 486 bool AMDGPUStructurizeCFG::isPredictableTrue(BasicBlock *Prev,
 487                                              BasicBlock *Node) {
 488
 489   BBPredicates &Preds = Predicates[Node];
 490   bool Dominated = false;
 491
 492   for (BBPredicates::iterator I = Preds.begin(), E = Preds.end();
 493        I != E; ++I) {
 494
 495     if (I->second != BoolTrue)
 496       return false;
 497
 498     if (!Dominated && DT->dominates(I->first, Prev))
 499       Dominated = true;
 500   }
 501   return Dominated;
 502 }
 503
 504 /// \brief Wire up the new control flow by inserting or updating the branch
 505 /// instructions at node exits
 506 BasicBlock *AMDGPUStructurizeCFG::wireFlowBlock(BasicBlock *Prev,
 507                                                 RegionNode *Node) {
 508
 509   BasicBlock *Entry = Node->getEntry();
 510
 511   if (LoopStart == Entry) {
 512     LoopStart = Prev;
 513     LoopPred[Prev] = BoolTrue;
 514   }
 515
 516   // Wire it up temporary, skipChained may recurse into us
 517   BranchInst::Create(Entry, Prev);
 518   DT->changeImmediateDominator(Entry, Prev);
 519   addPhiValues(Prev, Entry);
 520
 521   Node = skipChained(Node);
 522
 523   BasicBlock *Next = getNextFlow(Prev);
 524   if (!isPredictableTrue(Prev, Entry)) {
 525     // Let Prev point to entry and next block
 526     Prev->getTerminator()->eraseFromParent();
 527     BranchInst::Create(Entry, Next, BoolUndef, Prev);
 528   } else {
 529     DT->changeImmediateDominator(Next, Entry);
 530   }
 531
 532   // Let node exit(s) point to next block
 533   if (Node->isSubRegion()) {
 534     Region *SubRegion = Node->getNodeAs<Region>();
 535     BasicBlock *Exit = SubRegion->getExit();
 536
 537     // Find all the edges from the sub region to the exit
 538     BBVector ToDo;
 539     for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) {
 540       if (SubRegion->contains(*I))
 541         ToDo.push_back(*I);
 542     }
 543
 544     // Modify the edges to point to the new flow block
 545     for (BBVector::iterator I = ToDo.begin(), E = ToDo.end(); I != E; ++I) {
 546       delPhiValues(*I, Exit);
 547       TerminatorInst *Term = (*I)->getTerminator();
 548       Term->replaceUsesOfWith(Exit, Next);
 549     }
 550
 551     // Update the region info
 552     SubRegion->replaceExit(Next);
 553
 554   } else {
 555     BasicBlock *BB = Node->getNodeAs<BasicBlock>();
 556     killTerminator(BB);
 557     BranchInst::Create(Next, BB);
 558
 559     if (BB == LoopEnd)
 560       LoopEnd = 0;
 561   }
 562
 563   return Next;
 564 }
 565
 566 /// Destroy node order and visited map, build up flow order instead.
 567 /// After this function control flow looks like it should be, but
 568 /// branches only have undefined conditions.
 569 void AMDGPUStructurizeCFG::createFlow() {
 570
 571   DeletedPhis.clear();
 572
 573   BasicBlock *Prev = Order.pop_back_val()->getEntry();
 574   assert(Prev == ParentRegion->getEntry() && "Incorrect node order!");
 575   Visited.erase(Prev);
 576
 577   if (LoopStart == Prev) {
 578     // Loop starts at entry, split entry so that we can predicate it
 579     BasicBlock::iterator Insert = Prev->getFirstInsertionPt();
 580     BasicBlock *Split = Prev->splitBasicBlock(Insert, FlowBlockName);
 581     DT->addNewBlock(Split, Prev);
 582     ParentRegion->getRegionInfo()->setRegionFor(Split, ParentRegion);
 583     Predicates[Split] = Predicates[Prev];
 584     Order.push_back(ParentRegion->getBBNode(Split));
 585     LoopPred[Prev] = BoolTrue;
 586
 587   } else if (LoopStart == Order.back()->getEntry()) {
 588     // Loop starts behind entry, split entry so that we can jump to it
 589     Instruction *Term = Prev->getTerminator();
 590     BasicBlock *Split = Prev->splitBasicBlock(Term, FlowBlockName);
 591     DT->addNewBlock(Split, Prev);
 592     ParentRegion->getRegionInfo()->setRegionFor(Split, ParentRegion);
 593     Prev = Split;
 594   }
 595
 596   killTerminator(Prev);
 597   FlowsInserted.clear();
 598   FlowsInserted.push_back(Prev);
 599
 600   while (!Order.empty()) {
 601     RegionNode *Node = Order.pop_back_val();
 602     Visited.erase(Node->getEntry());
 603     Prev = wireFlowBlock(Prev, Node);
 604     if (LoopStart && !LoopEnd) {
 605       // Create an extra loop end node
 606       LoopEnd = Prev;
 607       Prev = getNextFlow(LoopEnd);
 608       BranchInst::Create(Prev, LoopStart, BoolUndef, LoopEnd);
 609       addPhiValues(LoopEnd, LoopStart);
 610     }
 611   }
 612
 613   BasicBlock *Exit = ParentRegion->getExit();
 614   BranchInst::Create(Exit, Prev);
 615   addPhiValues(Prev, Exit);
 616   if (DT->dominates(ParentRegion->getEntry(), Exit))
 617     DT->changeImmediateDominator(Exit, Prev);
 618
 619   if (LoopStart && LoopEnd) {
 620     BBVector::iterator FI = std::find(FlowsInserted.begin(),
 621                                       FlowsInserted.end(),
 622                                       LoopStart);
 623     for (; *FI != LoopEnd; ++FI) {
 624       addPhiValues(*FI, (*FI)->getTerminator()->getSuccessor(0));
 625     }
 626   }
 627
 628   assert(Order.empty());
 629   assert(Visited.empty());
 630   assert(DeletedPhis.empty());
 631 }
 632
 633 /// \brief Insert the missing branch conditions
 634 void AMDGPUStructurizeCFG::insertConditions() {
 635
 636   SSAUpdater PhiInserter;
 637
 638   for (BBVector::iterator FI = FlowsInserted.begin(), FE = FlowsInserted.end();
 639        FI != FE; ++FI) {
 640
 641     BranchInst *Term = cast<BranchInst>((*FI)->getTerminator());
 642     if (Term->isUnconditional())
 643       continue;
 644
 645     PhiInserter.Initialize(Boolean, "");
 646     PhiInserter.AddAvailableValue(&Func->getEntryBlock(), BoolFalse);
 647
 648     BasicBlock *Succ = Term->getSuccessor(0);
 649     BBPredicates &Preds = (*FI == LoopEnd) ? LoopPred : Predicates[Succ];
 650     for (BBPredicates::iterator PI = Preds.begin(), PE = Preds.end();
 651          PI != PE; ++PI) {
 652
 653       PhiInserter.AddAvailableValue(PI->first, PI->second);
 654     }
 655
 656     Term->setCondition(PhiInserter.GetValueAtEndOfBlock(*FI));
 657   }
 658 }
 659
 660 /// Handle a rare case where the disintegrated nodes instructions
 661 /// no longer dominate all their uses. Not sure if this is really nessasary
 662 void AMDGPUStructurizeCFG::rebuildSSA() {
 663
 664   SSAUpdater Updater;
 665   for (Region::block_iterator I = ParentRegion->block_begin(),
 666                               E = ParentRegion->block_end();
 667        I != E; ++I) {
 668
 669     BasicBlock *BB = *I;
 670     for (BasicBlock::iterator II = BB->begin(), IE = BB->end();
 671          II != IE; ++II) {
 672
 673       bool Initialized = false;
 674       for (Use *I = &II->use_begin().getUse(), *Next; I; I = Next) {
 675
 676         Next = I->getNext();
 677
 678         Instruction *User = cast<Instruction>(I->getUser());
 679         if (User->getParent() == BB) {
 680           continue;
 681
 682         } else if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
 683           if (UserPN->getIncomingBlock(*I) == BB)
 684             continue;
 685         }
 686
 687         if (DT->dominates(II, User))
 688           continue;
 689
 690         if (!Initialized) {
 691           Value *Undef = UndefValue::get(II->getType());
 692           Updater.Initialize(II->getType(), "");
 693           Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
 694           Updater.AddAvailableValue(BB, II);
 695           Initialized = true;
 696         }
 697         Updater.RewriteUseAfterInsertions(*I);
 698       }
 699     }
 700   }
 701 }
 702
 703 /// \brief Run the transformation for each region found
 704 bool AMDGPUStructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {
 705
 706   if (R->isTopLevelRegion())
 707     return false;
 708
 709   Func = R->getEntry()->getParent();
 710   ParentRegion = R;
 711
 712   DT = &getAnalysis<DominatorTree>();
 713
 714   orderNodes();
 715   collectInfos();
 716   createFlow();
 717   insertConditions();
 718   rebuildSSA();
 719
 720   Order.clear();
 721   Visited.clear();
 722   Predicates.clear();
 723   DeletedPhis.clear();
 724   FlowsInserted.clear();
 725
 726   return true;
 727 }
 728
 729 /// \brief Create the pass
 730 Pass *llvm::createAMDGPUStructurizeCFGPass() {
 731   return new AMDGPUStructurizeCFG();
 732 }