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