1 //===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===// 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 // Early if-conversion is for out-of-order CPUs that don't have a lot of 10 // predicable instructions. The goal is to eliminate conditional branches that 11 // may mispredict. 12 // 13 // Instructions from both sides of the branch are executed specutatively, and a 14 // cmov instruction selects the result. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "llvm/ADT/BitVector.h" 19 #include "llvm/ADT/PostOrderIterator.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallPtrSet.h" 22 #include "llvm/ADT/SparseSet.h" 23 #include "llvm/ADT/Statistic.h" 24 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 25 #include "llvm/CodeGen/MachineDominators.h" 26 #include "llvm/CodeGen/MachineFunction.h" 27 #include "llvm/CodeGen/MachineFunctionPass.h" 28 #include "llvm/CodeGen/MachineInstr.h" 29 #include "llvm/CodeGen/MachineLoopInfo.h" 30 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 31 #include "llvm/CodeGen/MachineRegisterInfo.h" 32 #include "llvm/CodeGen/MachineTraceMetrics.h" 33 #include "llvm/CodeGen/Passes.h" 34 #include "llvm/CodeGen/TargetInstrInfo.h" 35 #include "llvm/CodeGen/TargetRegisterInfo.h" 36 #include "llvm/CodeGen/TargetSubtargetInfo.h" 37 #include "llvm/InitializePasses.h" 38 #include "llvm/Support/CommandLine.h" 39 #include "llvm/Support/Debug.h" 40 #include "llvm/Support/raw_ostream.h" 41 42 using namespace llvm; 43 44 #define DEBUG_TYPE "early-ifcvt" 45 46 // Absolute maximum number of instructions allowed per speculated block. 47 // This bypasses all other heuristics, so it should be set fairly high. 48 static cl::opt<unsigned> 49 BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden, 50 cl::desc("Maximum number of instructions per speculated block.")); 51 52 // Stress testing mode - disable heuristics. 53 static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden, 54 cl::desc("Turn all knobs to 11")); 55 56 STATISTIC(NumDiamondsSeen, "Number of diamonds"); 57 STATISTIC(NumDiamondsConv, "Number of diamonds converted"); 58 STATISTIC(NumTrianglesSeen, "Number of triangles"); 59 STATISTIC(NumTrianglesConv, "Number of triangles converted"); 60 61 //===----------------------------------------------------------------------===// 62 // SSAIfConv 63 //===----------------------------------------------------------------------===// 64 // 65 // The SSAIfConv class performs if-conversion on SSA form machine code after 66 // determining if it is possible. The class contains no heuristics; external 67 // code should be used to determine when if-conversion is a good idea. 68 // 69 // SSAIfConv can convert both triangles and diamonds: 70 // 71 // Triangle: Head Diamond: Head 72 // | \ / \_ 73 // | \ / | 74 // | [TF]BB FBB TBB 75 // | / \ / 76 // | / \ / 77 // Tail Tail 78 // 79 // Instructions in the conditional blocks TBB and/or FBB are spliced into the 80 // Head block, and phis in the Tail block are converted to select instructions. 81 // 82 namespace { 83 class SSAIfConv { 84 const TargetInstrInfo *TII; 85 const TargetRegisterInfo *TRI; 86 MachineRegisterInfo *MRI; 87 88 public: 89 /// The block containing the conditional branch. 90 MachineBasicBlock *Head; 91 92 /// The block containing phis after the if-then-else. 93 MachineBasicBlock *Tail; 94 95 /// The 'true' conditional block as determined by analyzeBranch. 96 MachineBasicBlock *TBB; 97 98 /// The 'false' conditional block as determined by analyzeBranch. 99 MachineBasicBlock *FBB; 100 101 /// isTriangle - When there is no 'else' block, either TBB or FBB will be 102 /// equal to Tail. 103 bool isTriangle() const { return TBB == Tail || FBB == Tail; } 104 105 /// Returns the Tail predecessor for the True side. 106 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; } 107 108 /// Returns the Tail predecessor for the False side. 109 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; } 110 111 /// Information about each phi in the Tail block. 112 struct PHIInfo { 113 MachineInstr *PHI; 114 unsigned TReg, FReg; 115 // Latencies from Cond+Branch, TReg, and FReg to DstReg. 116 int CondCycles, TCycles, FCycles; 117 118 PHIInfo(MachineInstr *phi) 119 : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {} 120 }; 121 122 SmallVector<PHIInfo, 8> PHIs; 123 124 private: 125 /// The branch condition determined by analyzeBranch. 126 SmallVector<MachineOperand, 4> Cond; 127 128 /// Instructions in Head that define values used by the conditional blocks. 129 /// The hoisted instructions must be inserted after these instructions. 130 SmallPtrSet<MachineInstr*, 8> InsertAfter; 131 132 /// Register units clobbered by the conditional blocks. 133 BitVector ClobberedRegUnits; 134 135 // Scratch pad for findInsertionPoint. 136 SparseSet<unsigned> LiveRegUnits; 137 138 /// Insertion point in Head for speculatively executed instructions form TBB 139 /// and FBB. 140 MachineBasicBlock::iterator InsertionPoint; 141 142 /// Return true if all non-terminator instructions in MBB can be safely 143 /// speculated. 144 bool canSpeculateInstrs(MachineBasicBlock *MBB); 145 146 /// Return true if all non-terminator instructions in MBB can be safely 147 /// predicated. 148 bool canPredicateInstrs(MachineBasicBlock *MBB); 149 150 /// Scan through instruction dependencies and update InsertAfter array. 151 /// Return false if any dependency is incompatible with if conversion. 152 bool InstrDependenciesAllowIfConv(MachineInstr *I); 153 154 /// Predicate all instructions of the basic block with current condition 155 /// except for terminators. Reverse the condition if ReversePredicate is set. 156 void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate); 157 158 /// Find a valid insertion point in Head. 159 bool findInsertionPoint(); 160 161 /// Replace PHI instructions in Tail with selects. 162 void replacePHIInstrs(); 163 164 /// Insert selects and rewrite PHI operands to use them. 165 void rewritePHIOperands(); 166 167 public: 168 /// runOnMachineFunction - Initialize per-function data structures. 169 void runOnMachineFunction(MachineFunction &MF) { 170 TII = MF.getSubtarget().getInstrInfo(); 171 TRI = MF.getSubtarget().getRegisterInfo(); 172 MRI = &MF.getRegInfo(); 173 LiveRegUnits.clear(); 174 LiveRegUnits.setUniverse(TRI->getNumRegUnits()); 175 ClobberedRegUnits.clear(); 176 ClobberedRegUnits.resize(TRI->getNumRegUnits()); 177 } 178 179 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted, 180 /// initialize the internal state, and return true. 181 /// If predicate is set try to predicate the block otherwise try to 182 /// speculatively execute it. 183 bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false); 184 185 /// convertIf - If-convert the last block passed to canConvertIf(), assuming 186 /// it is possible. Add any erased blocks to RemovedBlocks. 187 void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks, 188 bool Predicate = false); 189 }; 190 } // end anonymous namespace 191 192 193 /// canSpeculateInstrs - Returns true if all the instructions in MBB can safely 194 /// be speculated. The terminators are not considered. 195 /// 196 /// If instructions use any values that are defined in the head basic block, 197 /// the defining instructions are added to InsertAfter. 198 /// 199 /// Any clobbered regunits are added to ClobberedRegUnits. 200 /// 201 bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) { 202 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to 203 // get right. 204 if (!MBB->livein_empty()) { 205 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); 206 return false; 207 } 208 209 unsigned InstrCount = 0; 210 211 // Check all instructions, except the terminators. It is assumed that 212 // terminators never have side effects or define any used register values. 213 for (MachineBasicBlock::iterator I = MBB->begin(), 214 E = MBB->getFirstTerminator(); I != E; ++I) { 215 if (I->isDebugInstr()) 216 continue; 217 218 if (++InstrCount > BlockInstrLimit && !Stress) { 219 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than " 220 << BlockInstrLimit << " instructions.\n"); 221 return false; 222 } 223 224 // There shouldn't normally be any phis in a single-predecessor block. 225 if (I->isPHI()) { 226 LLVM_DEBUG(dbgs() << "Can't hoist: " << *I); 227 return false; 228 } 229 230 // Don't speculate loads. Note that it may be possible and desirable to 231 // speculate GOT or constant pool loads that are guaranteed not to trap, 232 // but we don't support that for now. 233 if (I->mayLoad()) { 234 LLVM_DEBUG(dbgs() << "Won't speculate load: " << *I); 235 return false; 236 } 237 238 // We never speculate stores, so an AA pointer isn't necessary. 239 bool DontMoveAcrossStore = true; 240 if (!I->isSafeToMove(nullptr, DontMoveAcrossStore)) { 241 LLVM_DEBUG(dbgs() << "Can't speculate: " << *I); 242 return false; 243 } 244 245 // Check for any dependencies on Head instructions. 246 if (!InstrDependenciesAllowIfConv(&(*I))) 247 return false; 248 } 249 return true; 250 } 251 252 /// Check that there is no dependencies preventing if conversion. 253 /// 254 /// If instruction uses any values that are defined in the head basic block, 255 /// the defining instructions are added to InsertAfter. 256 bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) { 257 for (const MachineOperand &MO : I->operands()) { 258 if (MO.isRegMask()) { 259 LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I); 260 return false; 261 } 262 if (!MO.isReg()) 263 continue; 264 Register Reg = MO.getReg(); 265 266 // Remember clobbered regunits. 267 if (MO.isDef() && Register::isPhysicalRegister(Reg)) 268 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid(); 269 ++Units) 270 ClobberedRegUnits.set(*Units); 271 272 if (!MO.readsReg() || !Register::isVirtualRegister(Reg)) 273 continue; 274 MachineInstr *DefMI = MRI->getVRegDef(Reg); 275 if (!DefMI || DefMI->getParent() != Head) 276 continue; 277 if (InsertAfter.insert(DefMI).second) 278 LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on " 279 << *DefMI); 280 if (DefMI->isTerminator()) { 281 LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n"); 282 return false; 283 } 284 } 285 return true; 286 } 287 288 /// canPredicateInstrs - Returns true if all the instructions in MBB can safely 289 /// be predicates. The terminators are not considered. 290 /// 291 /// If instructions use any values that are defined in the head basic block, 292 /// the defining instructions are added to InsertAfter. 293 /// 294 /// Any clobbered regunits are added to ClobberedRegUnits. 295 /// 296 bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) { 297 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to 298 // get right. 299 if (!MBB->livein_empty()) { 300 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); 301 return false; 302 } 303 304 unsigned InstrCount = 0; 305 306 // Check all instructions, except the terminators. It is assumed that 307 // terminators never have side effects or define any used register values. 308 for (MachineBasicBlock::iterator I = MBB->begin(), 309 E = MBB->getFirstTerminator(); 310 I != E; ++I) { 311 if (I->isDebugInstr()) 312 continue; 313 314 if (++InstrCount > BlockInstrLimit && !Stress) { 315 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than " 316 << BlockInstrLimit << " instructions.\n"); 317 return false; 318 } 319 320 // There shouldn't normally be any phis in a single-predecessor block. 321 if (I->isPHI()) { 322 LLVM_DEBUG(dbgs() << "Can't predicate: " << *I); 323 return false; 324 } 325 326 // Check that instruction is predicable and that it is not already 327 // predicated. 328 if (!TII->isPredicable(*I) || TII->isPredicated(*I)) { 329 return false; 330 } 331 332 // Check for any dependencies on Head instructions. 333 if (!InstrDependenciesAllowIfConv(&(*I))) 334 return false; 335 } 336 return true; 337 } 338 339 // Apply predicate to all instructions in the machine block. 340 void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) { 341 auto Condition = Cond; 342 if (ReversePredicate) 343 TII->reverseBranchCondition(Condition); 344 // Terminators don't need to be predicated as they will be removed. 345 for (MachineBasicBlock::iterator I = MBB->begin(), 346 E = MBB->getFirstTerminator(); 347 I != E; ++I) { 348 if (I->isDebugInstr()) 349 continue; 350 TII->PredicateInstruction(*I, Condition); 351 } 352 } 353 354 /// Find an insertion point in Head for the speculated instructions. The 355 /// insertion point must be: 356 /// 357 /// 1. Before any terminators. 358 /// 2. After any instructions in InsertAfter. 359 /// 3. Not have any clobbered regunits live. 360 /// 361 /// This function sets InsertionPoint and returns true when successful, it 362 /// returns false if no valid insertion point could be found. 363 /// 364 bool SSAIfConv::findInsertionPoint() { 365 // Keep track of live regunits before the current position. 366 // Only track RegUnits that are also in ClobberedRegUnits. 367 LiveRegUnits.clear(); 368 SmallVector<MCRegister, 8> Reads; 369 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 370 MachineBasicBlock::iterator I = Head->end(); 371 MachineBasicBlock::iterator B = Head->begin(); 372 while (I != B) { 373 --I; 374 // Some of the conditional code depends in I. 375 if (InsertAfter.count(&*I)) { 376 LLVM_DEBUG(dbgs() << "Can't insert code after " << *I); 377 return false; 378 } 379 380 // Update live regunits. 381 for (const MachineOperand &MO : I->operands()) { 382 // We're ignoring regmask operands. That is conservatively correct. 383 if (!MO.isReg()) 384 continue; 385 Register Reg = MO.getReg(); 386 if (!Register::isPhysicalRegister(Reg)) 387 continue; 388 // I clobbers Reg, so it isn't live before I. 389 if (MO.isDef()) 390 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid(); 391 ++Units) 392 LiveRegUnits.erase(*Units); 393 // Unless I reads Reg. 394 if (MO.readsReg()) 395 Reads.push_back(Reg.asMCReg()); 396 } 397 // Anything read by I is live before I. 398 while (!Reads.empty()) 399 for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid(); 400 ++Units) 401 if (ClobberedRegUnits.test(*Units)) 402 LiveRegUnits.insert(*Units); 403 404 // We can't insert before a terminator. 405 if (I != FirstTerm && I->isTerminator()) 406 continue; 407 408 // Some of the clobbered registers are live before I, not a valid insertion 409 // point. 410 if (!LiveRegUnits.empty()) { 411 LLVM_DEBUG({ 412 dbgs() << "Would clobber"; 413 for (SparseSet<unsigned>::const_iterator 414 i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i) 415 dbgs() << ' ' << printRegUnit(*i, TRI); 416 dbgs() << " live before " << *I; 417 }); 418 continue; 419 } 420 421 // This is a valid insertion point. 422 InsertionPoint = I; 423 LLVM_DEBUG(dbgs() << "Can insert before " << *I); 424 return true; 425 } 426 LLVM_DEBUG(dbgs() << "No legal insertion point found.\n"); 427 return false; 428 } 429 430 431 432 /// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is 433 /// a potential candidate for if-conversion. Fill out the internal state. 434 /// 435 bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) { 436 Head = MBB; 437 TBB = FBB = Tail = nullptr; 438 439 if (Head->succ_size() != 2) 440 return false; 441 MachineBasicBlock *Succ0 = Head->succ_begin()[0]; 442 MachineBasicBlock *Succ1 = Head->succ_begin()[1]; 443 444 // Canonicalize so Succ0 has MBB as its single predecessor. 445 if (Succ0->pred_size() != 1) 446 std::swap(Succ0, Succ1); 447 448 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) 449 return false; 450 451 Tail = Succ0->succ_begin()[0]; 452 453 // This is not a triangle. 454 if (Tail != Succ1) { 455 // Check for a diamond. We won't deal with any critical edges. 456 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 || 457 Succ1->succ_begin()[0] != Tail) 458 return false; 459 LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> " 460 << printMBBReference(*Succ0) << "/" 461 << printMBBReference(*Succ1) << " -> " 462 << printMBBReference(*Tail) << '\n'); 463 464 // Live-in physregs are tricky to get right when speculating code. 465 if (!Tail->livein_empty()) { 466 LLVM_DEBUG(dbgs() << "Tail has live-ins.\n"); 467 return false; 468 } 469 } else { 470 LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> " 471 << printMBBReference(*Succ0) << " -> " 472 << printMBBReference(*Tail) << '\n'); 473 } 474 475 // This is a triangle or a diamond. 476 // Skip if we cannot predicate and there are no phis skip as there must be 477 // side effects that can only be handled with predication. 478 if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) { 479 LLVM_DEBUG(dbgs() << "No phis in tail.\n"); 480 return false; 481 } 482 483 // The branch we're looking to eliminate must be analyzable. 484 Cond.clear(); 485 if (TII->analyzeBranch(*Head, TBB, FBB, Cond)) { 486 LLVM_DEBUG(dbgs() << "Branch not analyzable.\n"); 487 return false; 488 } 489 490 // This is weird, probably some sort of degenerate CFG. 491 if (!TBB) { 492 LLVM_DEBUG(dbgs() << "analyzeBranch didn't find conditional branch.\n"); 493 return false; 494 } 495 496 // Make sure the analyzed branch is conditional; one of the successors 497 // could be a landing pad. (Empty landing pads can be generated on Windows.) 498 if (Cond.empty()) { 499 LLVM_DEBUG(dbgs() << "analyzeBranch found an unconditional branch.\n"); 500 return false; 501 } 502 503 // analyzeBranch doesn't set FBB on a fall-through branch. 504 // Make sure it is always set. 505 FBB = TBB == Succ0 ? Succ1 : Succ0; 506 507 // Any phis in the tail block must be convertible to selects. 508 PHIs.clear(); 509 MachineBasicBlock *TPred = getTPred(); 510 MachineBasicBlock *FPred = getFPred(); 511 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end(); 512 I != E && I->isPHI(); ++I) { 513 PHIs.push_back(&*I); 514 PHIInfo &PI = PHIs.back(); 515 // Find PHI operands corresponding to TPred and FPred. 516 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) { 517 if (PI.PHI->getOperand(i+1).getMBB() == TPred) 518 PI.TReg = PI.PHI->getOperand(i).getReg(); 519 if (PI.PHI->getOperand(i+1).getMBB() == FPred) 520 PI.FReg = PI.PHI->getOperand(i).getReg(); 521 } 522 assert(Register::isVirtualRegister(PI.TReg) && "Bad PHI"); 523 assert(Register::isVirtualRegister(PI.FReg) && "Bad PHI"); 524 525 // Get target information. 526 if (!TII->canInsertSelect(*Head, Cond, PI.PHI->getOperand(0).getReg(), 527 PI.TReg, PI.FReg, PI.CondCycles, PI.TCycles, 528 PI.FCycles)) { 529 LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI); 530 return false; 531 } 532 } 533 534 // Check that the conditional instructions can be speculated. 535 InsertAfter.clear(); 536 ClobberedRegUnits.reset(); 537 if (Predicate) { 538 if (TBB != Tail && !canPredicateInstrs(TBB)) 539 return false; 540 if (FBB != Tail && !canPredicateInstrs(FBB)) 541 return false; 542 } else { 543 if (TBB != Tail && !canSpeculateInstrs(TBB)) 544 return false; 545 if (FBB != Tail && !canSpeculateInstrs(FBB)) 546 return false; 547 } 548 549 // Try to find a valid insertion point for the speculated instructions in the 550 // head basic block. 551 if (!findInsertionPoint()) 552 return false; 553 554 if (isTriangle()) 555 ++NumTrianglesSeen; 556 else 557 ++NumDiamondsSeen; 558 return true; 559 } 560 561 /// replacePHIInstrs - Completely replace PHI instructions with selects. 562 /// This is possible when the only Tail predecessors are the if-converted 563 /// blocks. 564 void SSAIfConv::replacePHIInstrs() { 565 assert(Tail->pred_size() == 2 && "Cannot replace PHIs"); 566 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 567 assert(FirstTerm != Head->end() && "No terminators"); 568 DebugLoc HeadDL = FirstTerm->getDebugLoc(); 569 570 // Convert all PHIs to select instructions inserted before FirstTerm. 571 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 572 PHIInfo &PI = PHIs[i]; 573 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI); 574 Register DstReg = PI.PHI->getOperand(0).getReg(); 575 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); 576 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); 577 PI.PHI->eraseFromParent(); 578 PI.PHI = nullptr; 579 } 580 } 581 582 /// rewritePHIOperands - When there are additional Tail predecessors, insert 583 /// select instructions in Head and rewrite PHI operands to use the selects. 584 /// Keep the PHI instructions in Tail to handle the other predecessors. 585 void SSAIfConv::rewritePHIOperands() { 586 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); 587 assert(FirstTerm != Head->end() && "No terminators"); 588 DebugLoc HeadDL = FirstTerm->getDebugLoc(); 589 590 // Convert all PHIs to select instructions inserted before FirstTerm. 591 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 592 PHIInfo &PI = PHIs[i]; 593 unsigned DstReg = 0; 594 595 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI); 596 if (PI.TReg == PI.FReg) { 597 // We do not need the select instruction if both incoming values are 598 // equal. 599 DstReg = PI.TReg; 600 } else { 601 Register PHIDst = PI.PHI->getOperand(0).getReg(); 602 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst)); 603 TII->insertSelect(*Head, FirstTerm, HeadDL, 604 DstReg, Cond, PI.TReg, PI.FReg); 605 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); 606 } 607 608 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred. 609 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) { 610 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB(); 611 if (MBB == getTPred()) { 612 PI.PHI->getOperand(i-1).setMBB(Head); 613 PI.PHI->getOperand(i-2).setReg(DstReg); 614 } else if (MBB == getFPred()) { 615 PI.PHI->RemoveOperand(i-1); 616 PI.PHI->RemoveOperand(i-2); 617 } 618 } 619 LLVM_DEBUG(dbgs() << " --> " << *PI.PHI); 620 } 621 } 622 623 /// convertIf - Execute the if conversion after canConvertIf has determined the 624 /// feasibility. 625 /// 626 /// Any basic blocks erased will be added to RemovedBlocks. 627 /// 628 void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks, 629 bool Predicate) { 630 assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); 631 632 // Update statistics. 633 if (isTriangle()) 634 ++NumTrianglesConv; 635 else 636 ++NumDiamondsConv; 637 638 // Move all instructions into Head, except for the terminators. 639 if (TBB != Tail) { 640 if (Predicate) 641 PredicateBlock(TBB, /*ReversePredicate=*/false); 642 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); 643 } 644 if (FBB != Tail) { 645 if (Predicate) 646 PredicateBlock(FBB, /*ReversePredicate=*/true); 647 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); 648 } 649 // Are there extra Tail predecessors? 650 bool ExtraPreds = Tail->pred_size() != 2; 651 if (ExtraPreds) 652 rewritePHIOperands(); 653 else 654 replacePHIInstrs(); 655 656 // Fix up the CFG, temporarily leave Head without any successors. 657 Head->removeSuccessor(TBB); 658 Head->removeSuccessor(FBB, true); 659 if (TBB != Tail) 660 TBB->removeSuccessor(Tail, true); 661 if (FBB != Tail) 662 FBB->removeSuccessor(Tail, true); 663 664 // Fix up Head's terminators. 665 // It should become a single branch or a fallthrough. 666 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc(); 667 TII->removeBranch(*Head); 668 669 // Erase the now empty conditional blocks. It is likely that Head can fall 670 // through to Tail, and we can join the two blocks. 671 if (TBB != Tail) { 672 RemovedBlocks.push_back(TBB); 673 TBB->eraseFromParent(); 674 } 675 if (FBB != Tail) { 676 RemovedBlocks.push_back(FBB); 677 FBB->eraseFromParent(); 678 } 679 680 assert(Head->succ_empty() && "Additional head successors?"); 681 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) { 682 // Splice Tail onto the end of Head. 683 LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail) 684 << " into head " << printMBBReference(*Head) << '\n'); 685 Head->splice(Head->end(), Tail, 686 Tail->begin(), Tail->end()); 687 Head->transferSuccessorsAndUpdatePHIs(Tail); 688 RemovedBlocks.push_back(Tail); 689 Tail->eraseFromParent(); 690 } else { 691 // We need a branch to Tail, let code placement work it out later. 692 LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n"); 693 SmallVector<MachineOperand, 0> EmptyCond; 694 TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL); 695 Head->addSuccessor(Tail); 696 } 697 LLVM_DEBUG(dbgs() << *Head); 698 } 699 700 //===----------------------------------------------------------------------===// 701 // EarlyIfConverter Pass 702 //===----------------------------------------------------------------------===// 703 704 namespace { 705 class EarlyIfConverter : public MachineFunctionPass { 706 const TargetInstrInfo *TII; 707 const TargetRegisterInfo *TRI; 708 MCSchedModel SchedModel; 709 MachineRegisterInfo *MRI; 710 MachineDominatorTree *DomTree; 711 MachineLoopInfo *Loops; 712 MachineTraceMetrics *Traces; 713 MachineTraceMetrics::Ensemble *MinInstr; 714 SSAIfConv IfConv; 715 716 public: 717 static char ID; 718 EarlyIfConverter() : MachineFunctionPass(ID) {} 719 void getAnalysisUsage(AnalysisUsage &AU) const override; 720 bool runOnMachineFunction(MachineFunction &MF) override; 721 StringRef getPassName() const override { return "Early If-Conversion"; } 722 723 private: 724 bool tryConvertIf(MachineBasicBlock*); 725 void invalidateTraces(); 726 bool shouldConvertIf(); 727 }; 728 } // end anonymous namespace 729 730 char EarlyIfConverter::ID = 0; 731 char &llvm::EarlyIfConverterID = EarlyIfConverter::ID; 732 733 INITIALIZE_PASS_BEGIN(EarlyIfConverter, DEBUG_TYPE, 734 "Early If Converter", false, false) 735 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 736 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 737 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics) 738 INITIALIZE_PASS_END(EarlyIfConverter, DEBUG_TYPE, 739 "Early If Converter", false, false) 740 741 void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const { 742 AU.addRequired<MachineBranchProbabilityInfo>(); 743 AU.addRequired<MachineDominatorTree>(); 744 AU.addPreserved<MachineDominatorTree>(); 745 AU.addRequired<MachineLoopInfo>(); 746 AU.addPreserved<MachineLoopInfo>(); 747 AU.addRequired<MachineTraceMetrics>(); 748 AU.addPreserved<MachineTraceMetrics>(); 749 MachineFunctionPass::getAnalysisUsage(AU); 750 } 751 752 namespace { 753 /// Update the dominator tree after if-conversion erased some blocks. 754 void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv, 755 ArrayRef<MachineBasicBlock *> Removed) { 756 // convertIf can remove TBB, FBB, and Tail can be merged into Head. 757 // TBB and FBB should not dominate any blocks. 758 // Tail children should be transferred to Head. 759 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head); 760 for (auto B : Removed) { 761 MachineDomTreeNode *Node = DomTree->getNode(B); 762 assert(Node != HeadNode && "Cannot erase the head node"); 763 while (Node->getNumChildren()) { 764 assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); 765 DomTree->changeImmediateDominator(Node->back(), HeadNode); 766 } 767 DomTree->eraseNode(B); 768 } 769 } 770 771 /// Update LoopInfo after if-conversion. 772 void updateLoops(MachineLoopInfo *Loops, 773 ArrayRef<MachineBasicBlock *> Removed) { 774 if (!Loops) 775 return; 776 // If-conversion doesn't change loop structure, and it doesn't mess with back 777 // edges, so updating LoopInfo is simply removing the dead blocks. 778 for (auto B : Removed) 779 Loops->removeBlock(B); 780 } 781 } // namespace 782 783 /// Invalidate MachineTraceMetrics before if-conversion. 784 void EarlyIfConverter::invalidateTraces() { 785 Traces->verifyAnalysis(); 786 Traces->invalidate(IfConv.Head); 787 Traces->invalidate(IfConv.Tail); 788 Traces->invalidate(IfConv.TBB); 789 Traces->invalidate(IfConv.FBB); 790 Traces->verifyAnalysis(); 791 } 792 793 // Adjust cycles with downward saturation. 794 static unsigned adjCycles(unsigned Cyc, int Delta) { 795 if (Delta < 0 && Cyc + Delta > Cyc) 796 return 0; 797 return Cyc + Delta; 798 } 799 800 namespace { 801 /// Helper class to simplify emission of cycle counts into optimization remarks. 802 struct Cycles { 803 const char *Key; 804 unsigned Value; 805 }; 806 template <typename Remark> Remark &operator<<(Remark &R, Cycles C) { 807 return R << ore::NV(C.Key, C.Value) << (C.Value == 1 ? " cycle" : " cycles"); 808 } 809 } // anonymous namespace 810 811 /// Apply cost model and heuristics to the if-conversion in IfConv. 812 /// Return true if the conversion is a good idea. 813 /// 814 bool EarlyIfConverter::shouldConvertIf() { 815 // Stress testing mode disables all cost considerations. 816 if (Stress) 817 return true; 818 819 if (!MinInstr) 820 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount); 821 822 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred()); 823 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred()); 824 LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace); 825 unsigned MinCrit = std::min(TBBTrace.getCriticalPath(), 826 FBBTrace.getCriticalPath()); 827 828 // Set a somewhat arbitrary limit on the critical path extension we accept. 829 unsigned CritLimit = SchedModel.MispredictPenalty/2; 830 831 MachineBasicBlock &MBB = *IfConv.Head; 832 MachineOptimizationRemarkEmitter MORE(*MBB.getParent(), nullptr); 833 834 // If-conversion only makes sense when there is unexploited ILP. Compute the 835 // maximum-ILP resource length of the trace after if-conversion. Compare it 836 // to the shortest critical path. 837 SmallVector<const MachineBasicBlock*, 1> ExtraBlocks; 838 if (IfConv.TBB != IfConv.Tail) 839 ExtraBlocks.push_back(IfConv.TBB); 840 unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks); 841 LLVM_DEBUG(dbgs() << "Resource length " << ResLength 842 << ", minimal critical path " << MinCrit << '\n'); 843 if (ResLength > MinCrit + CritLimit) { 844 LLVM_DEBUG(dbgs() << "Not enough available ILP.\n"); 845 MORE.emit([&]() { 846 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion", 847 MBB.findDebugLoc(MBB.back()), &MBB); 848 R << "did not if-convert branch: the resulting critical path (" 849 << Cycles{"ResLength", ResLength} 850 << ") would extend the shorter leg's critical path (" 851 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of " 852 << Cycles{"CritLimit", CritLimit} 853 << ", which cannot be hidden by available ILP."; 854 return R; 855 }); 856 return false; 857 } 858 859 // Assume that the depth of the first head terminator will also be the depth 860 // of the select instruction inserted, as determined by the flag dependency. 861 // TBB / FBB data dependencies may delay the select even more. 862 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head); 863 unsigned BranchDepth = 864 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth; 865 LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n'); 866 867 // Look at all the tail phis, and compute the critical path extension caused 868 // by inserting select instructions. 869 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail); 870 struct CriticalPathInfo { 871 unsigned Extra; // Count of extra cycles that the component adds. 872 unsigned Depth; // Absolute depth of the component in cycles. 873 }; 874 CriticalPathInfo Cond{}; 875 CriticalPathInfo TBlock{}; 876 CriticalPathInfo FBlock{}; 877 bool ShouldConvert = true; 878 for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) { 879 SSAIfConv::PHIInfo &PI = IfConv.PHIs[i]; 880 unsigned Slack = TailTrace.getInstrSlack(*PI.PHI); 881 unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth; 882 LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI); 883 884 // The condition is pulled into the critical path. 885 unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles); 886 if (CondDepth > MaxDepth) { 887 unsigned Extra = CondDepth - MaxDepth; 888 LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n"); 889 if (Extra > Cond.Extra) 890 Cond = {Extra, CondDepth}; 891 if (Extra > CritLimit) { 892 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 893 ShouldConvert = false; 894 } 895 } 896 897 // The TBB value is pulled into the critical path. 898 unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles); 899 if (TDepth > MaxDepth) { 900 unsigned Extra = TDepth - MaxDepth; 901 LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n"); 902 if (Extra > TBlock.Extra) 903 TBlock = {Extra, TDepth}; 904 if (Extra > CritLimit) { 905 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 906 ShouldConvert = false; 907 } 908 } 909 910 // The FBB value is pulled into the critical path. 911 unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles); 912 if (FDepth > MaxDepth) { 913 unsigned Extra = FDepth - MaxDepth; 914 LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n"); 915 if (Extra > FBlock.Extra) 916 FBlock = {Extra, FDepth}; 917 if (Extra > CritLimit) { 918 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); 919 ShouldConvert = false; 920 } 921 } 922 } 923 924 // Organize by "short" and "long" legs, since the diagnostics get confusing 925 // when referring to the "true" and "false" sides of the branch, given that 926 // those don't always correlate with what the user wrote in source-terms. 927 const CriticalPathInfo Short = TBlock.Extra > FBlock.Extra ? FBlock : TBlock; 928 const CriticalPathInfo Long = TBlock.Extra > FBlock.Extra ? TBlock : FBlock; 929 930 if (ShouldConvert) { 931 MORE.emit([&]() { 932 MachineOptimizationRemark R(DEBUG_TYPE, "IfConversion", 933 MBB.back().getDebugLoc(), &MBB); 934 R << "performing if-conversion on branch: the condition adds " 935 << Cycles{"CondCycles", Cond.Extra} << " to the critical path"; 936 if (Short.Extra > 0) 937 R << ", and the short leg adds another " 938 << Cycles{"ShortCycles", Short.Extra}; 939 if (Long.Extra > 0) 940 R << ", and the long leg adds another " 941 << Cycles{"LongCycles", Long.Extra}; 942 R << ", each staying under the threshold of " 943 << Cycles{"CritLimit", CritLimit} << "."; 944 return R; 945 }); 946 } else { 947 MORE.emit([&]() { 948 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "IfConversion", 949 MBB.back().getDebugLoc(), &MBB); 950 R << "did not if-convert branch: the condition would add " 951 << Cycles{"CondCycles", Cond.Extra} << " to the critical path"; 952 if (Cond.Extra > CritLimit) 953 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit}; 954 if (Short.Extra > 0) { 955 R << ", and the short leg would add another " 956 << Cycles{"ShortCycles", Short.Extra}; 957 if (Short.Extra > CritLimit) 958 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit}; 959 } 960 if (Long.Extra > 0) { 961 R << ", and the long leg would add another " 962 << Cycles{"LongCycles", Long.Extra}; 963 if (Long.Extra > CritLimit) 964 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit}; 965 } 966 R << "."; 967 return R; 968 }); 969 } 970 971 return ShouldConvert; 972 } 973 974 /// Attempt repeated if-conversion on MBB, return true if successful. 975 /// 976 bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) { 977 bool Changed = false; 978 while (IfConv.canConvertIf(MBB) && shouldConvertIf()) { 979 // If-convert MBB and update analyses. 980 invalidateTraces(); 981 SmallVector<MachineBasicBlock*, 4> RemovedBlocks; 982 IfConv.convertIf(RemovedBlocks); 983 Changed = true; 984 updateDomTree(DomTree, IfConv, RemovedBlocks); 985 updateLoops(Loops, RemovedBlocks); 986 } 987 return Changed; 988 } 989 990 bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) { 991 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" 992 << "********** Function: " << MF.getName() << '\n'); 993 if (skipFunction(MF.getFunction())) 994 return false; 995 996 // Only run if conversion if the target wants it. 997 const TargetSubtargetInfo &STI = MF.getSubtarget(); 998 if (!STI.enableEarlyIfConversion()) 999 return false; 1000 1001 TII = STI.getInstrInfo(); 1002 TRI = STI.getRegisterInfo(); 1003 SchedModel = STI.getSchedModel(); 1004 MRI = &MF.getRegInfo(); 1005 DomTree = &getAnalysis<MachineDominatorTree>(); 1006 Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 1007 Traces = &getAnalysis<MachineTraceMetrics>(); 1008 MinInstr = nullptr; 1009 1010 bool Changed = false; 1011 IfConv.runOnMachineFunction(MF); 1012 1013 // Visit blocks in dominator tree post-order. The post-order enables nested 1014 // if-conversion in a single pass. The tryConvertIf() function may erase 1015 // blocks, but only blocks dominated by the head block. This makes it safe to 1016 // update the dominator tree while the post-order iterator is still active. 1017 for (auto DomNode : post_order(DomTree)) 1018 if (tryConvertIf(DomNode->getBlock())) 1019 Changed = true; 1020 1021 return Changed; 1022 } 1023 1024 //===----------------------------------------------------------------------===// 1025 // EarlyIfPredicator Pass 1026 //===----------------------------------------------------------------------===// 1027 1028 namespace { 1029 class EarlyIfPredicator : public MachineFunctionPass { 1030 const TargetInstrInfo *TII; 1031 const TargetRegisterInfo *TRI; 1032 TargetSchedModel SchedModel; 1033 MachineRegisterInfo *MRI; 1034 MachineDominatorTree *DomTree; 1035 MachineBranchProbabilityInfo *MBPI; 1036 MachineLoopInfo *Loops; 1037 SSAIfConv IfConv; 1038 1039 public: 1040 static char ID; 1041 EarlyIfPredicator() : MachineFunctionPass(ID) {} 1042 void getAnalysisUsage(AnalysisUsage &AU) const override; 1043 bool runOnMachineFunction(MachineFunction &MF) override; 1044 StringRef getPassName() const override { return "Early If-predicator"; } 1045 1046 protected: 1047 bool tryConvertIf(MachineBasicBlock *); 1048 bool shouldConvertIf(); 1049 }; 1050 } // end anonymous namespace 1051 1052 #undef DEBUG_TYPE 1053 #define DEBUG_TYPE "early-if-predicator" 1054 1055 char EarlyIfPredicator::ID = 0; 1056 char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID; 1057 1058 INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", 1059 false, false) 1060 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1061 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 1062 INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false, 1063 false) 1064 1065 void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const { 1066 AU.addRequired<MachineBranchProbabilityInfo>(); 1067 AU.addRequired<MachineDominatorTree>(); 1068 AU.addPreserved<MachineDominatorTree>(); 1069 AU.addRequired<MachineLoopInfo>(); 1070 AU.addPreserved<MachineLoopInfo>(); 1071 MachineFunctionPass::getAnalysisUsage(AU); 1072 } 1073 1074 /// Apply the target heuristic to decide if the transformation is profitable. 1075 bool EarlyIfPredicator::shouldConvertIf() { 1076 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB); 1077 if (IfConv.isTriangle()) { 1078 MachineBasicBlock &IfBlock = 1079 (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB; 1080 1081 unsigned ExtraPredCost = 0; 1082 unsigned Cycles = 0; 1083 for (MachineInstr &I : IfBlock) { 1084 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false); 1085 if (NumCycles > 1) 1086 Cycles += NumCycles - 1; 1087 ExtraPredCost += TII->getPredicationCost(I); 1088 } 1089 1090 return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost, 1091 TrueProbability); 1092 } 1093 unsigned TExtra = 0; 1094 unsigned FExtra = 0; 1095 unsigned TCycle = 0; 1096 unsigned FCycle = 0; 1097 for (MachineInstr &I : *IfConv.TBB) { 1098 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false); 1099 if (NumCycles > 1) 1100 TCycle += NumCycles - 1; 1101 TExtra += TII->getPredicationCost(I); 1102 } 1103 for (MachineInstr &I : *IfConv.FBB) { 1104 unsigned NumCycles = SchedModel.computeInstrLatency(&I, false); 1105 if (NumCycles > 1) 1106 FCycle += NumCycles - 1; 1107 FExtra += TII->getPredicationCost(I); 1108 } 1109 return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB, 1110 FCycle, FExtra, TrueProbability); 1111 } 1112 1113 /// Attempt repeated if-conversion on MBB, return true if successful. 1114 /// 1115 bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) { 1116 bool Changed = false; 1117 while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) { 1118 // If-convert MBB and update analyses. 1119 SmallVector<MachineBasicBlock *, 4> RemovedBlocks; 1120 IfConv.convertIf(RemovedBlocks, /*Predicate*/ true); 1121 Changed = true; 1122 updateDomTree(DomTree, IfConv, RemovedBlocks); 1123 updateLoops(Loops, RemovedBlocks); 1124 } 1125 return Changed; 1126 } 1127 1128 bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) { 1129 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n" 1130 << "********** Function: " << MF.getName() << '\n'); 1131 if (skipFunction(MF.getFunction())) 1132 return false; 1133 1134 const TargetSubtargetInfo &STI = MF.getSubtarget(); 1135 TII = STI.getInstrInfo(); 1136 TRI = STI.getRegisterInfo(); 1137 MRI = &MF.getRegInfo(); 1138 SchedModel.init(&STI); 1139 DomTree = &getAnalysis<MachineDominatorTree>(); 1140 Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 1141 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 1142 1143 bool Changed = false; 1144 IfConv.runOnMachineFunction(MF); 1145 1146 // Visit blocks in dominator tree post-order. The post-order enables nested 1147 // if-conversion in a single pass. The tryConvertIf() function may erase 1148 // blocks, but only blocks dominated by the head block. This makes it safe to 1149 // update the dominator tree while the post-order iterator is still active. 1150 for (auto DomNode : post_order(DomTree)) 1151 if (tryConvertIf(DomNode->getBlock())) 1152 Changed = true; 1153 1154 return Changed; 1155 } 1156