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