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