llvm/lib/CodeGen/EarlyIfConversion.cpp

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