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