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