contrib/llvm-project/llvm/lib/CodeGen/EarlyIfConversion.cpp

   1 //===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Early if-conversion is for out-of-order CPUs that don't have a lot of
  10 // predicable instructions. The goal is to eliminate conditional branches that
  11 // may mispredict.
  12 //
  13 // Instructions from both sides of the branch are executed specutatively, and a
  14 // cmov instruction selects the result.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/ADT/BitVector.h"
  19 #include "llvm/ADT/PostOrderIterator.h"
  20 #include "llvm/ADT/SetVector.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/ADT/SparseSet.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  25 #include "llvm/CodeGen/MachineDominators.h"
  26 #include "llvm/CodeGen/MachineFunction.h"
  27 #include "llvm/CodeGen/MachineFunctionPass.h"
  28 #include "llvm/CodeGen/MachineInstr.h"
  29 #include "llvm/CodeGen/MachineLoopInfo.h"
  30 #include "llvm/CodeGen/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/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, FReg;
 114     // Latencies from Cond+Branch, TReg, and FReg to DstReg.
 115     int CondCycles, TCycles, FCycles;
 116
 117     PHIInfo(MachineInstr *phi)
 118       : PHI(phi), TReg(0), FReg(0), CondCycles(0), TCycles(0), FCycles(0) {}
 119   };
 120
 121   SmallVector<PHIInfo, 8> PHIs;
 122
 123 private:
 124   /// The branch condition determined by AnalyzeBranch.
 125   SmallVector<MachineOperand, 4> Cond;
 126
 127   /// Instructions in Head that define values used by the conditional blocks.
 128   /// The hoisted instructions must be inserted after these instructions.
 129   SmallPtrSet<MachineInstr*, 8> InsertAfter;
 130
 131   /// Register units clobbered by the conditional blocks.
 132   BitVector ClobberedRegUnits;
 133
 134   // Scratch pad for findInsertionPoint.
 135   SparseSet<unsigned> LiveRegUnits;
 136
 137   /// Insertion point in Head for speculatively executed instructions form TBB
 138   /// and FBB.
 139   MachineBasicBlock::iterator InsertionPoint;
 140
 141   /// Return true if all non-terminator instructions in MBB can be safely
 142   /// speculated.
 143   bool canSpeculateInstrs(MachineBasicBlock *MBB);
 144
 145   /// Return true if all non-terminator instructions in MBB can be safely
 146   /// predicated.
 147   bool canPredicateInstrs(MachineBasicBlock *MBB);
 148
 149   /// Scan through instruction dependencies and update InsertAfter array.
 150   /// Return false if any dependency is incompatible with if conversion.
 151   bool InstrDependenciesAllowIfConv(MachineInstr *I);
 152
 153   /// Predicate all instructions of the basic block with current condition
 154   /// except for terminators. Reverse the condition if ReversePredicate is set.
 155   void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate);
 156
 157   /// Find a valid insertion point in Head.
 158   bool findInsertionPoint();
 159
 160   /// Replace PHI instructions in Tail with selects.
 161   void replacePHIInstrs();
 162
 163   /// Insert selects and rewrite PHI operands to use them.
 164   void rewritePHIOperands();
 165
 166 public:
 167   /// runOnMachineFunction - Initialize per-function data structures.
 168   void runOnMachineFunction(MachineFunction &MF) {
 169     TII = MF.getSubtarget().getInstrInfo();
 170     TRI = MF.getSubtarget().getRegisterInfo();
 171     MRI = &MF.getRegInfo();
 172     LiveRegUnits.clear();
 173     LiveRegUnits.setUniverse(TRI->getNumRegUnits());
 174     ClobberedRegUnits.clear();
 175     ClobberedRegUnits.resize(TRI->getNumRegUnits());
 176   }
 177
 178   /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
 179   /// initialize the internal state, and return true.
 180   /// If predicate is set try to predicate the block otherwise try to
 181   /// speculatively execute it.
 182   bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false);
 183
 184   /// convertIf - If-convert the last block passed to canConvertIf(), assuming
 185   /// it is possible. Add any erased blocks to RemovedBlocks.
 186   void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
 187                  bool Predicate = false);
 188 };
 189 } // end anonymous namespace
 190
 191
 192 /// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
 193 /// be speculated. The terminators are not considered.
 194 ///
 195 /// If instructions use any values that are defined in the head basic block,
 196 /// the defining instructions are added to InsertAfter.
 197 ///
 198 /// Any clobbered regunits are added to ClobberedRegUnits.
 199 ///
 200 bool SSAIfConv::canSpeculateInstrs(MachineBasicBlock *MBB) {
 201   // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
 202   // get right.
 203   if (!MBB->livein_empty()) {
 204     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
 205     return false;
 206   }
 207
 208   unsigned InstrCount = 0;
 209
 210   // Check all instructions, except the terminators. It is assumed that
 211   // terminators never have side effects or define any used register values.
 212   for (MachineBasicBlock::iterator I = MBB->begin(),
 213        E = MBB->getFirstTerminator(); I != E; ++I) {
 214     if (I->isDebugInstr())
 215       continue;
 216
 217     if (++InstrCount > BlockInstrLimit && !Stress) {
 218       LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
 219                         << BlockInstrLimit << " instructions.\n");
 220       return false;
 221     }
 222
 223     // There shouldn't normally be any phis in a single-predecessor block.
 224     if (I->isPHI()) {
 225       LLVM_DEBUG(dbgs() << "Can't hoist: " << *I);
 226       return false;
 227     }
 228
 229     // Don't speculate loads. Note that it may be possible and desirable to
 230     // speculate GOT or constant pool loads that are guaranteed not to trap,
 231     // but we don't support that for now.
 232     if (I->mayLoad()) {
 233       LLVM_DEBUG(dbgs() << "Won't speculate load: " << *I);
 234       return false;
 235     }
 236
 237     // We never speculate stores, so an AA pointer isn't necessary.
 238     bool DontMoveAcrossStore = true;
 239     if (!I->isSafeToMove(nullptr, DontMoveAcrossStore)) {
 240       LLVM_DEBUG(dbgs() << "Can't speculate: " << *I);
 241       return false;
 242     }
 243
 244     // Check for any dependencies on Head instructions.
 245     if (!InstrDependenciesAllowIfConv(&(*I)))
 246       return false;
 247   }
 248   return true;
 249 }
 250
 251 /// Check that there is no dependencies preventing if conversion.
 252 ///
 253 /// If instruction uses any values that are defined in the head basic block,
 254 /// the defining instructions are added to InsertAfter.
 255 bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) {
 256   for (const MachineOperand &MO : I->operands()) {
 257     if (MO.isRegMask()) {
 258       LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
 259       return false;
 260     }
 261     if (!MO.isReg())
 262       continue;
 263     Register Reg = MO.getReg();
 264
 265     // Remember clobbered regunits.
 266     if (MO.isDef() && Register::isPhysicalRegister(Reg))
 267       for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++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<unsigned, 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, TRI); Units.isValid(); ++Units)
 389           LiveRegUnits.erase(*Units);
 390       // Unless I reads Reg.
 391       if (MO.readsReg())
 392         Reads.push_back(Reg);
 393     }
 394     // Anything read by I is live before I.
 395     while (!Reads.empty())
 396       for (MCRegUnitIterator Units(Reads.pop_back_val(), TRI); Units.isValid();
 397            ++Units)
 398         if (ClobberedRegUnits.test(*Units))
 399           LiveRegUnits.insert(*Units);
 400
 401     // We can't insert before a terminator.
 402     if (I != FirstTerm && I->isTerminator())
 403       continue;
 404
 405     // Some of the clobbered registers are live before I, not a valid insertion
 406     // point.
 407     if (!LiveRegUnits.empty()) {
 408       LLVM_DEBUG({
 409         dbgs() << "Would clobber";
 410         for (SparseSet<unsigned>::const_iterator
 411              i = LiveRegUnits.begin(), e = LiveRegUnits.end(); i != e; ++i)
 412           dbgs() << ' ' << printRegUnit(*i, 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.TReg, PI.FReg,
 524                               PI.CondCycles, PI.TCycles, PI.FCycles)) {
 525       LLVM_DEBUG(dbgs() << "Can't convert: " << *PI.PHI);
 526       return false;
 527     }
 528   }
 529
 530   // Check that the conditional instructions can be speculated.
 531   InsertAfter.clear();
 532   ClobberedRegUnits.reset();
 533   if (Predicate) {
 534     if (TBB != Tail && !canPredicateInstrs(TBB))
 535       return false;
 536     if (FBB != Tail && !canPredicateInstrs(FBB))
 537       return false;
 538   } else {
 539     if (TBB != Tail && !canSpeculateInstrs(TBB))
 540       return false;
 541     if (FBB != Tail && !canSpeculateInstrs(FBB))
 542       return false;
 543   }
 544
 545   // Try to find a valid insertion point for the speculated instructions in the
 546   // head basic block.
 547   if (!findInsertionPoint())
 548     return false;
 549
 550   if (isTriangle())
 551     ++NumTrianglesSeen;
 552   else
 553     ++NumDiamondsSeen;
 554   return true;
 555 }
 556
 557 /// replacePHIInstrs - Completely replace PHI instructions with selects.
 558 /// This is possible when the only Tail predecessors are the if-converted
 559 /// blocks.
 560 void SSAIfConv::replacePHIInstrs() {
 561   assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
 562   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
 563   assert(FirstTerm != Head->end() && "No terminators");
 564   DebugLoc HeadDL = FirstTerm->getDebugLoc();
 565
 566   // Convert all PHIs to select instructions inserted before FirstTerm.
 567   for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
 568     PHIInfo &PI = PHIs[i];
 569     LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
 570     Register DstReg = PI.PHI->getOperand(0).getReg();
 571     TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
 572     LLVM_DEBUG(dbgs() << "          --> " << *std::prev(FirstTerm));
 573     PI.PHI->eraseFromParent();
 574     PI.PHI = nullptr;
 575   }
 576 }
 577
 578 /// rewritePHIOperands - When there are additional Tail predecessors, insert
 579 /// select instructions in Head and rewrite PHI operands to use the selects.
 580 /// Keep the PHI instructions in Tail to handle the other predecessors.
 581 void SSAIfConv::rewritePHIOperands() {
 582   MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
 583   assert(FirstTerm != Head->end() && "No terminators");
 584   DebugLoc HeadDL = FirstTerm->getDebugLoc();
 585
 586   // Convert all PHIs to select instructions inserted before FirstTerm.
 587   for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
 588     PHIInfo &PI = PHIs[i];
 589     unsigned DstReg = 0;
 590
 591     LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI);
 592     if (PI.TReg == PI.FReg) {
 593       // We do not need the select instruction if both incoming values are
 594       // equal.
 595       DstReg = PI.TReg;
 596     } else {
 597       Register PHIDst = PI.PHI->getOperand(0).getReg();
 598       DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
 599       TII->insertSelect(*Head, FirstTerm, HeadDL,
 600                          DstReg, Cond, PI.TReg, PI.FReg);
 601       LLVM_DEBUG(dbgs() << "          --> " << *std::prev(FirstTerm));
 602     }
 603
 604     // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
 605     for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
 606       MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
 607       if (MBB == getTPred()) {
 608         PI.PHI->getOperand(i-1).setMBB(Head);
 609         PI.PHI->getOperand(i-2).setReg(DstReg);
 610       } else if (MBB == getFPred()) {
 611         PI.PHI->RemoveOperand(i-1);
 612         PI.PHI->RemoveOperand(i-2);
 613       }
 614     }
 615     LLVM_DEBUG(dbgs() << "          --> " << *PI.PHI);
 616   }
 617 }
 618
 619 /// convertIf - Execute the if conversion after canConvertIf has determined the
 620 /// feasibility.
 621 ///
 622 /// Any basic blocks erased will be added to RemovedBlocks.
 623 ///
 624 void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
 625                           bool Predicate) {
 626   assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
 627
 628   // Update statistics.
 629   if (isTriangle())
 630     ++NumTrianglesConv;
 631   else
 632     ++NumDiamondsConv;
 633
 634   // Move all instructions into Head, except for the terminators.
 635   if (TBB != Tail) {
 636     if (Predicate)
 637       PredicateBlock(TBB, /*ReversePredicate=*/false);
 638     Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
 639   }
 640   if (FBB != Tail) {
 641     if (Predicate)
 642       PredicateBlock(FBB, /*ReversePredicate=*/true);
 643     Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
 644   }
 645   // Are there extra Tail predecessors?
 646   bool ExtraPreds = Tail->pred_size() != 2;
 647   if (ExtraPreds)
 648     rewritePHIOperands();
 649   else
 650     replacePHIInstrs();
 651
 652   // Fix up the CFG, temporarily leave Head without any successors.
 653   Head->removeSuccessor(TBB);
 654   Head->removeSuccessor(FBB, true);
 655   if (TBB != Tail)
 656     TBB->removeSuccessor(Tail, true);
 657   if (FBB != Tail)
 658     FBB->removeSuccessor(Tail, true);
 659
 660   // Fix up Head's terminators.
 661   // It should become a single branch or a fallthrough.
 662   DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
 663   TII->removeBranch(*Head);
 664
 665   // Erase the now empty conditional blocks. It is likely that Head can fall
 666   // through to Tail, and we can join the two blocks.
 667   if (TBB != Tail) {
 668     RemovedBlocks.push_back(TBB);
 669     TBB->eraseFromParent();
 670   }
 671   if (FBB != Tail) {
 672     RemovedBlocks.push_back(FBB);
 673     FBB->eraseFromParent();
 674   }
 675
 676   assert(Head->succ_empty() && "Additional head successors?");
 677   if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
 678     // Splice Tail onto the end of Head.
 679     LLVM_DEBUG(dbgs() << "Joining tail " << printMBBReference(*Tail)
 680                       << " into head " << printMBBReference(*Head) << '\n');
 681     Head->splice(Head->end(), Tail,
 682                      Tail->begin(), Tail->end());
 683     Head->transferSuccessorsAndUpdatePHIs(Tail);
 684     RemovedBlocks.push_back(Tail);
 685     Tail->eraseFromParent();
 686   } else {
 687     // We need a branch to Tail, let code placement work it out later.
 688     LLVM_DEBUG(dbgs() << "Converting to unconditional branch.\n");
 689     SmallVector<MachineOperand, 0> EmptyCond;
 690     TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
 691     Head->addSuccessor(Tail);
 692   }
 693   LLVM_DEBUG(dbgs() << *Head);
 694 }
 695
 696 //===----------------------------------------------------------------------===//
 697 //                           EarlyIfConverter Pass
 698 //===----------------------------------------------------------------------===//
 699
 700 namespace {
 701 class EarlyIfConverter : public MachineFunctionPass {
 702   const TargetInstrInfo *TII;
 703   const TargetRegisterInfo *TRI;
 704   MCSchedModel SchedModel;
 705   MachineRegisterInfo *MRI;
 706   MachineDominatorTree *DomTree;
 707   MachineLoopInfo *Loops;
 708   MachineTraceMetrics *Traces;
 709   MachineTraceMetrics::Ensemble *MinInstr;
 710   SSAIfConv IfConv;
 711
 712 public:
 713   static char ID;
 714   EarlyIfConverter() : MachineFunctionPass(ID) {}
 715   void getAnalysisUsage(AnalysisUsage &AU) const override;
 716   bool runOnMachineFunction(MachineFunction &MF) override;
 717   StringRef getPassName() const override { return "Early If-Conversion"; }
 718
 719 private:
 720   bool tryConvertIf(MachineBasicBlock*);
 721   void invalidateTraces();
 722   bool shouldConvertIf();
 723 };
 724 } // end anonymous namespace
 725
 726 char EarlyIfConverter::ID = 0;
 727 char &llvm::EarlyIfConverterID = EarlyIfConverter::ID;
 728
 729 INITIALIZE_PASS_BEGIN(EarlyIfConverter, DEBUG_TYPE,
 730                       "Early If Converter", false, false)
 731 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 732 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 733 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
 734 INITIALIZE_PASS_END(EarlyIfConverter, DEBUG_TYPE,
 735                     "Early If Converter", false, false)
 736
 737 void EarlyIfConverter::getAnalysisUsage(AnalysisUsage &AU) const {
 738   AU.addRequired<MachineBranchProbabilityInfo>();
 739   AU.addRequired<MachineDominatorTree>();
 740   AU.addPreserved<MachineDominatorTree>();
 741   AU.addRequired<MachineLoopInfo>();
 742   AU.addPreserved<MachineLoopInfo>();
 743   AU.addRequired<MachineTraceMetrics>();
 744   AU.addPreserved<MachineTraceMetrics>();
 745   MachineFunctionPass::getAnalysisUsage(AU);
 746 }
 747
 748 namespace {
 749 /// Update the dominator tree after if-conversion erased some blocks.
 750 void updateDomTree(MachineDominatorTree *DomTree, const SSAIfConv &IfConv,
 751                    ArrayRef<MachineBasicBlock *> Removed) {
 752   // convertIf can remove TBB, FBB, and Tail can be merged into Head.
 753   // TBB and FBB should not dominate any blocks.
 754   // Tail children should be transferred to Head.
 755   MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
 756   for (auto B : Removed) {
 757     MachineDomTreeNode *Node = DomTree->getNode(B);
 758     assert(Node != HeadNode && "Cannot erase the head node");
 759     while (Node->getNumChildren()) {
 760       assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
 761       DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode);
 762     }
 763     DomTree->eraseNode(B);
 764   }
 765 }
 766
 767 /// Update LoopInfo after if-conversion.
 768 void updateLoops(MachineLoopInfo *Loops,
 769                  ArrayRef<MachineBasicBlock *> Removed) {
 770   if (!Loops)
 771     return;
 772   // If-conversion doesn't change loop structure, and it doesn't mess with back
 773   // edges, so updating LoopInfo is simply removing the dead blocks.
 774   for (auto B : Removed)
 775     Loops->removeBlock(B);
 776 }
 777 } // namespace
 778
 779 /// Invalidate MachineTraceMetrics before if-conversion.
 780 void EarlyIfConverter::invalidateTraces() {
 781   Traces->verifyAnalysis();
 782   Traces->invalidate(IfConv.Head);
 783   Traces->invalidate(IfConv.Tail);
 784   Traces->invalidate(IfConv.TBB);
 785   Traces->invalidate(IfConv.FBB);
 786   Traces->verifyAnalysis();
 787 }
 788
 789 // Adjust cycles with downward saturation.
 790 static unsigned adjCycles(unsigned Cyc, int Delta) {
 791   if (Delta < 0 && Cyc + Delta > Cyc)
 792     return 0;
 793   return Cyc + Delta;
 794 }
 795
 796 /// Apply cost model and heuristics to the if-conversion in IfConv.
 797 /// Return true if the conversion is a good idea.
 798 ///
 799 bool EarlyIfConverter::shouldConvertIf() {
 800   // Stress testing mode disables all cost considerations.
 801   if (Stress)
 802     return true;
 803
 804   if (!MinInstr)
 805     MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
 806
 807   MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred());
 808   MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred());
 809   LLVM_DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace);
 810   unsigned MinCrit = std::min(TBBTrace.getCriticalPath(),
 811                               FBBTrace.getCriticalPath());
 812
 813   // Set a somewhat arbitrary limit on the critical path extension we accept.
 814   unsigned CritLimit = SchedModel.MispredictPenalty/2;
 815
 816   // If-conversion only makes sense when there is unexploited ILP. Compute the
 817   // maximum-ILP resource length of the trace after if-conversion. Compare it
 818   // to the shortest critical path.
 819   SmallVector<const MachineBasicBlock*, 1> ExtraBlocks;
 820   if (IfConv.TBB != IfConv.Tail)
 821     ExtraBlocks.push_back(IfConv.TBB);
 822   unsigned ResLength = FBBTrace.getResourceLength(ExtraBlocks);
 823   LLVM_DEBUG(dbgs() << "Resource length " << ResLength
 824                     << ", minimal critical path " << MinCrit << '\n');
 825   if (ResLength > MinCrit + CritLimit) {
 826     LLVM_DEBUG(dbgs() << "Not enough available ILP.\n");
 827     return false;
 828   }
 829
 830   // Assume that the depth of the first head terminator will also be the depth
 831   // of the select instruction inserted, as determined by the flag dependency.
 832   // TBB / FBB data dependencies may delay the select even more.
 833   MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head);
 834   unsigned BranchDepth =
 835       HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth;
 836   LLVM_DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n');
 837
 838   // Look at all the tail phis, and compute the critical path extension caused
 839   // by inserting select instructions.
 840   MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
 841   for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
 842     SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
 843     unsigned Slack = TailTrace.getInstrSlack(*PI.PHI);
 844     unsigned MaxDepth = Slack + TailTrace.getInstrCycles(*PI.PHI).Depth;
 845     LLVM_DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
 846
 847     // The condition is pulled into the critical path.
 848     unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
 849     if (CondDepth > MaxDepth) {
 850       unsigned Extra = CondDepth - MaxDepth;
 851       LLVM_DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
 852       if (Extra > CritLimit) {
 853         LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
 854         return false;
 855       }
 856     }
 857
 858     // The TBB value is pulled into the critical path.
 859     unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(*PI.PHI), PI.TCycles);
 860     if (TDepth > MaxDepth) {
 861       unsigned Extra = TDepth - MaxDepth;
 862       LLVM_DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
 863       if (Extra > CritLimit) {
 864         LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
 865         return false;
 866       }
 867     }
 868
 869     // The FBB value is pulled into the critical path.
 870     unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(*PI.PHI), PI.FCycles);
 871     if (FDepth > MaxDepth) {
 872       unsigned Extra = FDepth - MaxDepth;
 873       LLVM_DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
 874       if (Extra > CritLimit) {
 875         LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
 876         return false;
 877       }
 878     }
 879   }
 880   return true;
 881 }
 882
 883 /// Attempt repeated if-conversion on MBB, return true if successful.
 884 ///
 885 bool EarlyIfConverter::tryConvertIf(MachineBasicBlock *MBB) {
 886   bool Changed = false;
 887   while (IfConv.canConvertIf(MBB) && shouldConvertIf()) {
 888     // If-convert MBB and update analyses.
 889     invalidateTraces();
 890     SmallVector<MachineBasicBlock*, 4> RemovedBlocks;
 891     IfConv.convertIf(RemovedBlocks);
 892     Changed = true;
 893     updateDomTree(DomTree, IfConv, RemovedBlocks);
 894     updateLoops(Loops, RemovedBlocks);
 895   }
 896   return Changed;
 897 }
 898
 899 bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
 900   LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
 901                     << "********** Function: " << MF.getName() << '\n');
 902   if (skipFunction(MF.getFunction()))
 903     return false;
 904
 905   // Only run if conversion if the target wants it.
 906   const TargetSubtargetInfo &STI = MF.getSubtarget();
 907   if (!STI.enableEarlyIfConversion())
 908     return false;
 909
 910   TII = STI.getInstrInfo();
 911   TRI = STI.getRegisterInfo();
 912   SchedModel = STI.getSchedModel();
 913   MRI = &MF.getRegInfo();
 914   DomTree = &getAnalysis<MachineDominatorTree>();
 915   Loops = getAnalysisIfAvailable<MachineLoopInfo>();
 916   Traces = &getAnalysis<MachineTraceMetrics>();
 917   MinInstr = nullptr;
 918
 919   bool Changed = false;
 920   IfConv.runOnMachineFunction(MF);
 921
 922   // Visit blocks in dominator tree post-order. The post-order enables nested
 923   // if-conversion in a single pass. The tryConvertIf() function may erase
 924   // blocks, but only blocks dominated by the head block. This makes it safe to
 925   // update the dominator tree while the post-order iterator is still active.
 926   for (auto DomNode : post_order(DomTree))
 927     if (tryConvertIf(DomNode->getBlock()))
 928       Changed = true;
 929
 930   return Changed;
 931 }
 932
 933 //===----------------------------------------------------------------------===//
 934 //                           EarlyIfPredicator Pass
 935 //===----------------------------------------------------------------------===//
 936
 937 namespace {
 938 class EarlyIfPredicator : public MachineFunctionPass {
 939   const TargetInstrInfo *TII;
 940   const TargetRegisterInfo *TRI;
 941   TargetSchedModel SchedModel;
 942   MachineRegisterInfo *MRI;
 943   MachineDominatorTree *DomTree;
 944   MachineBranchProbabilityInfo *MBPI;
 945   MachineLoopInfo *Loops;
 946   SSAIfConv IfConv;
 947
 948 public:
 949   static char ID;
 950   EarlyIfPredicator() : MachineFunctionPass(ID) {}
 951   void getAnalysisUsage(AnalysisUsage &AU) const override;
 952   bool runOnMachineFunction(MachineFunction &MF) override;
 953   StringRef getPassName() const override { return "Early If-predicator"; }
 954
 955 protected:
 956   bool tryConvertIf(MachineBasicBlock *);
 957   bool shouldConvertIf();
 958 };
 959 } // end anonymous namespace
 960
 961 #undef DEBUG_TYPE
 962 #define DEBUG_TYPE "early-if-predicator"
 963
 964 char EarlyIfPredicator::ID = 0;
 965 char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
 966
 967 INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator",
 968                       false, false)
 969 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 970 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 971 INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE, "Early If Predicator", false,
 972                     false)
 973
 974 void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
 975   AU.addRequired<MachineBranchProbabilityInfo>();
 976   AU.addRequired<MachineDominatorTree>();
 977   AU.addPreserved<MachineDominatorTree>();
 978   AU.addRequired<MachineLoopInfo>();
 979   AU.addPreserved<MachineLoopInfo>();
 980   MachineFunctionPass::getAnalysisUsage(AU);
 981 }
 982
 983 /// Apply the target heuristic to decide if the transformation is profitable.
 984 bool EarlyIfPredicator::shouldConvertIf() {
 985   auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB);
 986   if (IfConv.isTriangle()) {
 987     MachineBasicBlock &IfBlock =
 988         (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
 989
 990     unsigned ExtraPredCost = 0;
 991     unsigned Cycles = 0;
 992     for (MachineInstr &I : IfBlock) {
 993       unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
 994       if (NumCycles > 1)
 995         Cycles += NumCycles - 1;
 996       ExtraPredCost += TII->getPredicationCost(I);
 997     }
 998
 999     return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
1000                                     TrueProbability);
1001   }
1002   unsigned TExtra = 0;
1003   unsigned FExtra = 0;
1004   unsigned TCycle = 0;
1005   unsigned FCycle = 0;
1006   for (MachineInstr &I : *IfConv.TBB) {
1007     unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1008     if (NumCycles > 1)
1009       TCycle += NumCycles - 1;
1010     TExtra += TII->getPredicationCost(I);
1011   }
1012   for (MachineInstr &I : *IfConv.FBB) {
1013     unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
1014     if (NumCycles > 1)
1015       FCycle += NumCycles - 1;
1016     FExtra += TII->getPredicationCost(I);
1017   }
1018   return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
1019                                   FCycle, FExtra, TrueProbability);
1020 }
1021
1022 /// Attempt repeated if-conversion on MBB, return true if successful.
1023 ///
1024 bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
1025   bool Changed = false;
1026   while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
1027     // If-convert MBB and update analyses.
1028     SmallVector<MachineBasicBlock *, 4> RemovedBlocks;
1029     IfConv.convertIf(RemovedBlocks, /*Predicate*/ true);
1030     Changed = true;
1031     updateDomTree(DomTree, IfConv, RemovedBlocks);
1032     updateLoops(Loops, RemovedBlocks);
1033   }
1034   return Changed;
1035 }
1036
1037 bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
1038   LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
1039                     << "********** Function: " << MF.getName() << '\n');
1040   if (skipFunction(MF.getFunction()))
1041     return false;
1042
1043   const TargetSubtargetInfo &STI = MF.getSubtarget();
1044   TII = STI.getInstrInfo();
1045   TRI = STI.getRegisterInfo();
1046   MRI = &MF.getRegInfo();
1047   SchedModel.init(&STI);
1048   DomTree = &getAnalysis<MachineDominatorTree>();
1049   Loops = getAnalysisIfAvailable<MachineLoopInfo>();
1050   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
1051
1052   bool Changed = false;
1053   IfConv.runOnMachineFunction(MF);
1054
1055   // Visit blocks in dominator tree post-order. The post-order enables nested
1056   // if-conversion in a single pass. The tryConvertIf() function may erase
1057   // blocks, but only blocks dominated by the head block. This makes it safe to
1058   // update the dominator tree while the post-order iterator is still active.
1059   for (auto DomNode : post_order(DomTree))
1060     if (tryConvertIf(DomNode->getBlock()))
1061       Changed = true;
1062
1063   return Changed;
1064 }