lib/Target/ARM64/ARM64ConditionalCompares.cpp

   1 //===-- ARM64ConditionalCompares.cpp --- CCMP formation for ARM64 ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the ARM64ConditionalCompares pass which reduces
  11 // branching and code size by using the conditional compare instructions CCMP,
  12 // CCMN, and FCMP.
  13 //
  14 // The CFG transformations for forming conditional compares are very similar to
  15 // if-conversion, and this pass should run immediately before the early
  16 // if-conversion pass.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "arm64-ccmp"
  21 #include "ARM64.h"
  22 #include "llvm/ADT/BitVector.h"
  23 #include "llvm/ADT/DepthFirstIterator.h"
  24 #include "llvm/ADT/SetVector.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include "llvm/ADT/SparseSet.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  29 #include "llvm/CodeGen/MachineDominators.h"
  30 #include "llvm/CodeGen/MachineFunction.h"
  31 #include "llvm/CodeGen/MachineFunctionPass.h"
  32 #include "llvm/CodeGen/MachineInstrBuilder.h"
  33 #include "llvm/CodeGen/MachineLoopInfo.h"
  34 #include "llvm/CodeGen/MachineRegisterInfo.h"
  35 #include "llvm/CodeGen/MachineTraceMetrics.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/Support/CommandLine.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/raw_ostream.h"
  40 #include "llvm/Target/TargetInstrInfo.h"
  41 #include "llvm/Target/TargetRegisterInfo.h"
  42 #include "llvm/Target/TargetSubtargetInfo.h"
  43
  44 using namespace llvm;
  45
  46 // Absolute maximum number of instructions allowed per speculated block.
  47 // This bypasses all other heuristics, so it should be set fairly high.
  48 static cl::opt<unsigned> BlockInstrLimit(
  49     "arm64-ccmp-limit", cl::init(30), cl::Hidden,
  50     cl::desc("Maximum number of instructions per speculated block."));
  51
  52 // Stress testing mode - disable heuristics.
  53 static cl::opt<bool> Stress("arm64-stress-ccmp", cl::Hidden,
  54                             cl::desc("Turn all knobs to 11"));
  55
  56 STATISTIC(NumConsidered, "Number of ccmps considered");
  57 STATISTIC(NumPhiRejs, "Number of ccmps rejected (PHI)");
  58 STATISTIC(NumPhysRejs, "Number of ccmps rejected (Physregs)");
  59 STATISTIC(NumPhi2Rejs, "Number of ccmps rejected (PHI2)");
  60 STATISTIC(NumHeadBranchRejs, "Number of ccmps rejected (Head branch)");
  61 STATISTIC(NumCmpBranchRejs, "Number of ccmps rejected (CmpBB branch)");
  62 STATISTIC(NumCmpTermRejs, "Number of ccmps rejected (CmpBB is cbz...)");
  63 STATISTIC(NumImmRangeRejs, "Number of ccmps rejected (Imm out of range)");
  64 STATISTIC(NumLiveDstRejs, "Number of ccmps rejected (Cmp dest live)");
  65 STATISTIC(NumMultCPSRUses, "Number of ccmps rejected (CPSR used)");
  66 STATISTIC(NumUnknCPSRDefs, "Number of ccmps rejected (CPSR def unknown)");
  67
  68 STATISTIC(NumSpeculateRejs, "Number of ccmps rejected (Can't speculate)");
  69
  70 STATISTIC(NumConverted, "Number of ccmp instructions created");
  71 STATISTIC(NumCompBranches, "Number of cbz/cbnz branches converted");
  72
  73 //===----------------------------------------------------------------------===//
  74 //                                 SSACCmpConv
  75 //===----------------------------------------------------------------------===//
  76 //
  77 // The SSACCmpConv class performs ccmp-conversion on SSA form machine code
  78 // after determining if it is possible. The class contains no heuristics;
  79 // external code should be used to determine when ccmp-conversion is a good
  80 // idea.
  81 //
  82 // CCmp-formation works on a CFG representing chained conditions, typically
  83 // from C's short-circuit || and && operators:
  84 //
  85 //   From:         Head            To:         Head
  86 //                 / |                         CmpBB
  87 //                /  |                         / |
  88 //               |  CmpBB                     /  |
  89 //               |  / |                    Tail  |
  90 //               | /  |                      |   |
  91 //              Tail  |                      |   |
  92 //                |   |                      |   |
  93 //               ... ...                    ... ...
  94 //
  95 // The Head block is terminated by a br.cond instruction, and the CmpBB block
  96 // contains compare + br.cond. Tail must be a successor of both.
  97 //
  98 // The cmp-conversion turns the compare instruction in CmpBB into a conditional
  99 // compare, and merges CmpBB into Head, speculatively executing its
 100 // instructions. The ARM64 conditional compare instructions have an immediate
 101 // operand that specifies the NZCV flag values when the condition is false and
 102 // the compare isn't executed. This makes it possible to chain compares with
 103 // different condition codes.
 104 //
 105 // Example:
 106 //
 107 //    if (a == 5 || b == 17)
 108 //      foo();
 109 //
 110 //    Head:
 111 //       cmp  w0, #5
 112 //       b.eq Tail
 113 //    CmpBB:
 114 //       cmp  w1, #17
 115 //       b.eq Tail
 116 //    ...
 117 //    Tail:
 118 //      bl _foo
 119 //
 120 //  Becomes:
 121 //
 122 //    Head:
 123 //       cmp  w0, #5
 124 //       ccmp w1, #17, 4, ne  ; 4 = nZcv
 125 //       b.eq Tail
 126 //    ...
 127 //    Tail:
 128 //      bl _foo
 129 //
 130 // The ccmp condition code is the one that would cause the Head terminator to
 131 // branch to CmpBB.
 132 //
 133 // FIXME: It should also be possible to speculate a block on the critical edge
 134 // between Head and Tail, just like if-converting a diamond.
 135 //
 136 // FIXME: Handle PHIs in Tail by turning them into selects (if-conversion).
 137
 138 namespace {
 139 class SSACCmpConv {
 140   MachineFunction *MF;
 141   const TargetInstrInfo *TII;
 142   const TargetRegisterInfo *TRI;
 143   MachineRegisterInfo *MRI;
 144
 145 public:
 146   /// The first block containing a conditional branch, dominating everything
 147   /// else.
 148   MachineBasicBlock *Head;
 149
 150   /// The block containing cmp+br.cond with a sucessor shared with Head.
 151   MachineBasicBlock *CmpBB;
 152
 153   /// The common successor for Head and CmpBB.
 154   MachineBasicBlock *Tail;
 155
 156   /// The compare instruction in CmpBB that can be converted to a ccmp.
 157   MachineInstr *CmpMI;
 158
 159 private:
 160   /// The branch condition in Head as determined by AnalyzeBranch.
 161   SmallVector<MachineOperand, 4> HeadCond;
 162
 163   /// The condition code that makes Head branch to CmpBB.
 164   ARM64CC::CondCode HeadCmpBBCC;
 165
 166   /// The branch condition in CmpBB.
 167   SmallVector<MachineOperand, 4> CmpBBCond;
 168
 169   /// The condition code that makes CmpBB branch to Tail.
 170   ARM64CC::CondCode CmpBBTailCC;
 171
 172   /// Check if the Tail PHIs are trivially convertible.
 173   bool trivialTailPHIs();
 174
 175   /// Remove CmpBB from the Tail PHIs.
 176   void updateTailPHIs();
 177
 178   /// Check if an operand defining DstReg is dead.
 179   bool isDeadDef(unsigned DstReg);
 180
 181   /// Find the compare instruction in MBB that controls the conditional branch.
 182   /// Return NULL if a convertible instruction can't be found.
 183   MachineInstr *findConvertibleCompare(MachineBasicBlock *MBB);
 184
 185   /// Return true if all non-terminator instructions in MBB can be safely
 186   /// speculated.
 187   bool canSpeculateInstrs(MachineBasicBlock *MBB, const MachineInstr *CmpMI);
 188
 189 public:
 190   /// runOnMachineFunction - Initialize per-function data structures.
 191   void runOnMachineFunction(MachineFunction &MF) {
 192     this->MF = &MF;
 193     TII = MF.getTarget().getInstrInfo();
 194     TRI = MF.getTarget().getRegisterInfo();
 195     MRI = &MF.getRegInfo();
 196   }
 197
 198   /// If the sub-CFG headed by MBB can be cmp-converted, initialize the
 199   /// internal state, and return true.
 200   bool canConvert(MachineBasicBlock *MBB);
 201
 202   /// Cmo-convert the last block passed to canConvertCmp(), assuming
 203   /// it is possible. Add any erased blocks to RemovedBlocks.
 204   void convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks);
 205
 206   /// Return the expected code size delta if the conversion into a
 207   /// conditional compare is performed.
 208   int expectedCodeSizeDelta() const;
 209 };
 210 } // end anonymous namespace
 211
 212 // Check that all PHIs in Tail are selecting the same value from Head and CmpBB.
 213 // This means that no if-conversion is required when merging CmpBB into Head.
 214 bool SSACCmpConv::trivialTailPHIs() {
 215   for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
 216        I != E && I->isPHI(); ++I) {
 217     unsigned HeadReg = 0, CmpBBReg = 0;
 218     // PHI operands come in (VReg, MBB) pairs.
 219     for (unsigned oi = 1, oe = I->getNumOperands(); oi != oe; oi += 2) {
 220       MachineBasicBlock *MBB = I->getOperand(oi + 1).getMBB();
 221       unsigned Reg = I->getOperand(oi).getReg();
 222       if (MBB == Head) {
 223         assert((!HeadReg || HeadReg == Reg) && "Inconsistent PHI operands");
 224         HeadReg = Reg;
 225       }
 226       if (MBB == CmpBB) {
 227         assert((!CmpBBReg || CmpBBReg == Reg) && "Inconsistent PHI operands");
 228         CmpBBReg = Reg;
 229       }
 230     }
 231     if (HeadReg != CmpBBReg)
 232       return false;
 233   }
 234   return true;
 235 }
 236
 237 // Assuming that trivialTailPHIs() is true, update the Tail PHIs by simply
 238 // removing the CmpBB operands. The Head operands will be identical.
 239 void SSACCmpConv::updateTailPHIs() {
 240   for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end();
 241        I != E && I->isPHI(); ++I) {
 242     // I is a PHI. It can have multiple entries for CmpBB.
 243     for (unsigned oi = I->getNumOperands(); oi > 2; oi -= 2) {
 244       // PHI operands are (Reg, MBB) at (oi-2, oi-1).
 245       if (I->getOperand(oi - 1).getMBB() == CmpBB) {
 246         I->RemoveOperand(oi - 1);
 247         I->RemoveOperand(oi - 2);
 248       }
 249     }
 250   }
 251 }
 252
 253 // This pass runs before the ARM64DeadRegisterDefinitions pass, so compares are
 254 // still writing virtual registers without any uses.
 255 bool SSACCmpConv::isDeadDef(unsigned DstReg) {
 256   // Writes to the zero register are dead.
 257   if (DstReg == ARM64::WZR || DstReg == ARM64::XZR)
 258     return true;
 259   if (!TargetRegisterInfo::isVirtualRegister(DstReg))
 260     return false;
 261   // A virtual register def without any uses will be marked dead later, and
 262   // eventually replaced by the zero register.
 263   return MRI->use_nodbg_empty(DstReg);
 264 }
 265
 266 // Parse a condition code returned by AnalyzeBranch, and compute the CondCode
 267 // corresponding to TBB.
 268 // Return
 269 bool parseCond(ArrayRef<MachineOperand> Cond, ARM64CC::CondCode &CC) {
 270   // A normal br.cond simply has the condition code.
 271   if (Cond[0].getImm() != -1) {
 272     assert(Cond.size() == 1 && "Unknown Cond array format");
 273     CC = (ARM64CC::CondCode)(int)Cond[0].getImm();
 274     return true;
 275   }
 276   // For tbz and cbz instruction, the opcode is next.
 277   switch (Cond[1].getImm()) {
 278   default:
 279     // This includes tbz / tbnz branches which can't be converted to
 280     // ccmp + br.cond.
 281     return false;
 282   case ARM64::CBZW:
 283   case ARM64::CBZX:
 284     assert(Cond.size() == 3 && "Unknown Cond array format");
 285     CC = ARM64CC::EQ;
 286     return true;
 287   case ARM64::CBNZW:
 288   case ARM64::CBNZX:
 289     assert(Cond.size() == 3 && "Unknown Cond array format");
 290     CC = ARM64CC::NE;
 291     return true;
 292   }
 293 }
 294
 295 MachineInstr *SSACCmpConv::findConvertibleCompare(MachineBasicBlock *MBB) {
 296   MachineBasicBlock::iterator I = MBB->getFirstTerminator();
 297   if (I == MBB->end())
 298     return 0;
 299   // The terminator must be controlled by the flags.
 300   if (!I->readsRegister(ARM64::CPSR)) {
 301     switch (I->getOpcode()) {
 302     case ARM64::CBZW:
 303     case ARM64::CBZX:
 304     case ARM64::CBNZW:
 305     case ARM64::CBNZX:
 306       // These can be converted into a ccmp against #0.
 307       return I;
 308     }
 309     ++NumCmpTermRejs;
 310     DEBUG(dbgs() << "Flags not used by terminator: " << *I);
 311     return 0;
 312   }
 313
 314   // Now find the instruction controlling the terminator.
 315   for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) {
 316     --I;
 317     assert(!I->isTerminator() && "Spurious terminator");
 318     switch (I->getOpcode()) {
 319     // cmp is an alias for subs with a dead destination register.
 320     case ARM64::SUBSWri:
 321     case ARM64::SUBSXri:
 322     // cmn is an alias for adds with a dead destination register.
 323     case ARM64::ADDSWri:
 324     case ARM64::ADDSXri:
 325       // Check that the immediate operand is within range, ccmp wants a uimm5.
 326       // Rd = SUBSri Rn, imm, shift
 327       if (I->getOperand(3).getImm() || !isUInt<5>(I->getOperand(2).getImm())) {
 328         DEBUG(dbgs() << "Immediate out of range for ccmp: " << *I);
 329         ++NumImmRangeRejs;
 330         return 0;
 331       }
 332     // Fall through.
 333     case ARM64::SUBSWrr:
 334     case ARM64::SUBSXrr:
 335     case ARM64::ADDSWrr:
 336     case ARM64::ADDSXrr:
 337       if (isDeadDef(I->getOperand(0).getReg()))
 338         return I;
 339       DEBUG(dbgs() << "Can't convert compare with live destination: " << *I);
 340       ++NumLiveDstRejs;
 341       return 0;
 342     case ARM64::FCMPSrr:
 343     case ARM64::FCMPDrr:
 344     case ARM64::FCMPESrr:
 345     case ARM64::FCMPEDrr:
 346       return I;
 347     }
 348
 349     // Check for flag reads and clobbers.
 350     MIOperands::PhysRegInfo PRI =
 351         MIOperands(I).analyzePhysReg(ARM64::CPSR, TRI);
 352
 353     if (PRI.Reads) {
 354       // The ccmp doesn't produce exactly the same flags as the original
 355       // compare, so reject the transform if there are uses of the flags
 356       // besides the terminators.
 357       DEBUG(dbgs() << "Can't create ccmp with multiple uses: " << *I);
 358       ++NumMultCPSRUses;
 359       return 0;
 360     }
 361
 362     if (PRI.Clobbers) {
 363       DEBUG(dbgs() << "Not convertible compare: " << *I);
 364       ++NumUnknCPSRDefs;
 365       return 0;
 366     }
 367   }
 368   DEBUG(dbgs() << "Flags not defined in BB#" << MBB->getNumber() << '\n');
 369   return 0;
 370 }
 371
 372 /// Determine if all the instructions in MBB can safely
 373 /// be speculated. The terminators are not considered.
 374 ///
 375 /// Only CmpMI is allowed to clobber the flags.
 376 ///
 377 bool SSACCmpConv::canSpeculateInstrs(MachineBasicBlock *MBB,
 378                                      const MachineInstr *CmpMI) {
 379   // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
 380   // get right.
 381   if (!MBB->livein_empty()) {
 382     DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n");
 383     return false;
 384   }
 385
 386   unsigned InstrCount = 0;
 387
 388   // Check all instructions, except the terminators. It is assumed that
 389   // terminators never have side effects or define any used register values.
 390   for (MachineBasicBlock::iterator I = MBB->begin(),
 391                                    E = MBB->getFirstTerminator();
 392        I != E; ++I) {
 393     if (I->isDebugValue())
 394       continue;
 395
 396     if (++InstrCount > BlockInstrLimit && !Stress) {
 397       DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than "
 398                    << BlockInstrLimit << " instructions.\n");
 399       return false;
 400     }
 401
 402     // There shouldn't normally be any phis in a single-predecessor block.
 403     if (I->isPHI()) {
 404       DEBUG(dbgs() << "Can't hoist: " << *I);
 405       return false;
 406     }
 407
 408     // Don't speculate loads. Note that it may be possible and desirable to
 409     // speculate GOT or constant pool loads that are guaranteed not to trap,
 410     // but we don't support that for now.
 411     if (I->mayLoad()) {
 412       DEBUG(dbgs() << "Won't speculate load: " << *I);
 413       return false;
 414     }
 415
 416     // We never speculate stores, so an AA pointer isn't necessary.
 417     bool DontMoveAcrossStore = true;
 418     if (!I->isSafeToMove(TII, 0, DontMoveAcrossStore)) {
 419       DEBUG(dbgs() << "Can't speculate: " << *I);
 420       return false;
 421     }
 422
 423     // Only CmpMI is alowed to clobber the flags.
 424     if (&*I != CmpMI && I->modifiesRegister(ARM64::CPSR, TRI)) {
 425       DEBUG(dbgs() << "Clobbers flags: " << *I);
 426       return false;
 427     }
 428   }
 429   return true;
 430 }
 431
 432 /// Analyze the sub-cfg rooted in MBB, and return true if it is a potential
 433 /// candidate for cmp-conversion. Fill out the internal state.
 434 ///
 435 bool SSACCmpConv::canConvert(MachineBasicBlock *MBB) {
 436   Head = MBB;
 437   Tail = CmpBB = 0;
 438
 439   if (Head->succ_size() != 2)
 440     return false;
 441   MachineBasicBlock *Succ0 = Head->succ_begin()[0];
 442   MachineBasicBlock *Succ1 = Head->succ_begin()[1];
 443
 444   // CmpBB can only have a single predecessor. Tail is allowed many.
 445   if (Succ0->pred_size() != 1)
 446     std::swap(Succ0, Succ1);
 447
 448   // Succ0 is our candidate for CmpBB.
 449   if (Succ0->pred_size() != 1 || Succ0->succ_size() != 2)
 450     return false;
 451
 452   CmpBB = Succ0;
 453   Tail = Succ1;
 454
 455   if (!CmpBB->isSuccessor(Tail))
 456     return false;
 457
 458   // The CFG topology checks out.
 459   DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber() << " -> BB#"
 460                << CmpBB->getNumber() << " -> BB#" << Tail->getNumber() << '\n');
 461   ++NumConsidered;
 462
 463   // Tail is allowed to have many predecessors, but we can't handle PHIs yet.
 464   //
 465   // FIXME: Real PHIs could be if-converted as long as the CmpBB values are
 466   // defined before The CmpBB cmp clobbers the flags. Alternatively, it should
 467   // always be safe to sink the ccmp down to immediately before the CmpBB
 468   // terminators.
 469   if (!trivialTailPHIs()) {
 470     DEBUG(dbgs() << "Can't handle phis in Tail.\n");
 471     ++NumPhiRejs;
 472     return false;
 473   }
 474
 475   if (!Tail->livein_empty()) {
 476     DEBUG(dbgs() << "Can't handle live-in physregs in Tail.\n");
 477     ++NumPhysRejs;
 478     return false;
 479   }
 480
 481   // CmpBB should never have PHIs since Head is its only predecessor.
 482   // FIXME: Clean them up if it happens.
 483   if (!CmpBB->empty() && CmpBB->front().isPHI()) {
 484     DEBUG(dbgs() << "Can't handle phis in CmpBB.\n");
 485     ++NumPhi2Rejs;
 486     return false;
 487   }
 488
 489   if (!CmpBB->livein_empty()) {
 490     DEBUG(dbgs() << "Can't handle live-in physregs in CmpBB.\n");
 491     ++NumPhysRejs;
 492     return false;
 493   }
 494
 495   // The branch we're looking to eliminate must be analyzable.
 496   HeadCond.clear();
 497   MachineBasicBlock *TBB = 0, *FBB = 0;
 498   if (TII->AnalyzeBranch(*Head, TBB, FBB, HeadCond)) {
 499     DEBUG(dbgs() << "Head branch not analyzable.\n");
 500     ++NumHeadBranchRejs;
 501     return false;
 502   }
 503
 504   // This is weird, probably some sort of degenerate CFG, or an edge to a
 505   // landing pad.
 506   if (!TBB || HeadCond.empty()) {
 507     DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch in Head.\n");
 508     ++NumHeadBranchRejs;
 509     return false;
 510   }
 511
 512   if (!parseCond(HeadCond, HeadCmpBBCC)) {
 513     DEBUG(dbgs() << "Unsupported branch type on Head\n");
 514     ++NumHeadBranchRejs;
 515     return false;
 516   }
 517
 518   // Make sure the branch direction is right.
 519   if (TBB != CmpBB) {
 520     assert(TBB == Tail && "Unexpected TBB");
 521     HeadCmpBBCC = ARM64CC::getInvertedCondCode(HeadCmpBBCC);
 522   }
 523
 524   CmpBBCond.clear();
 525   TBB = FBB = 0;
 526   if (TII->AnalyzeBranch(*CmpBB, TBB, FBB, CmpBBCond)) {
 527     DEBUG(dbgs() << "CmpBB branch not analyzable.\n");
 528     ++NumCmpBranchRejs;
 529     return false;
 530   }
 531
 532   if (!TBB || CmpBBCond.empty()) {
 533     DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch in CmpBB.\n");
 534     ++NumCmpBranchRejs;
 535     return false;
 536   }
 537
 538   if (!parseCond(CmpBBCond, CmpBBTailCC)) {
 539     DEBUG(dbgs() << "Unsupported branch type on CmpBB\n");
 540     ++NumCmpBranchRejs;
 541     return false;
 542   }
 543
 544   if (TBB != Tail)
 545     CmpBBTailCC = ARM64CC::getInvertedCondCode(CmpBBTailCC);
 546
 547   DEBUG(dbgs() << "Head->CmpBB on " << ARM64CC::getCondCodeName(HeadCmpBBCC)
 548                << ", CmpBB->Tail on " << ARM64CC::getCondCodeName(CmpBBTailCC)
 549                << '\n');
 550
 551   CmpMI = findConvertibleCompare(CmpBB);
 552   if (!CmpMI)
 553     return false;
 554
 555   if (!canSpeculateInstrs(CmpBB, CmpMI)) {
 556     ++NumSpeculateRejs;
 557     return false;
 558   }
 559   return true;
 560 }
 561
 562 void SSACCmpConv::convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks) {
 563   DEBUG(dbgs() << "Merging BB#" << CmpBB->getNumber() << " into BB#"
 564                << Head->getNumber() << ":\n" << *CmpBB);
 565
 566   // All CmpBB instructions are moved into Head, and CmpBB is deleted.
 567   // Update the CFG first.
 568   updateTailPHIs();
 569   Head->removeSuccessor(CmpBB);
 570   CmpBB->removeSuccessor(Tail);
 571   Head->transferSuccessorsAndUpdatePHIs(CmpBB);
 572   DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc();
 573   TII->RemoveBranch(*Head);
 574
 575   // If the Head terminator was one of the cbz / tbz branches with built-in
 576   // compare, we need to insert an explicit compare instruction in its place.
 577   if (HeadCond[0].getImm() == -1) {
 578     ++NumCompBranches;
 579     unsigned Opc = 0;
 580     switch (HeadCond[1].getImm()) {
 581     case ARM64::CBZW:
 582     case ARM64::CBNZW:
 583       Opc = ARM64::SUBSWri;
 584       break;
 585     case ARM64::CBZX:
 586     case ARM64::CBNZX:
 587       Opc = ARM64::SUBSXri;
 588       break;
 589     default:
 590       llvm_unreachable("Cannot convert Head branch");
 591     }
 592     const MCInstrDesc &MCID = TII->get(Opc);
 593     // Create a dummy virtual register for the SUBS def.
 594     unsigned DestReg =
 595         MRI->createVirtualRegister(TII->getRegClass(MCID, 0, TRI, *MF));
 596     // Insert a SUBS Rn, #0 instruction instead of the cbz / cbnz.
 597     BuildMI(*Head, Head->end(), TermDL, MCID)
 598         .addReg(DestReg, RegState::Define | RegState::Dead)
 599         .addOperand(HeadCond[2])
 600         .addImm(0)
 601         .addImm(0);
 602     // SUBS uses the GPR*sp register classes.
 603     MRI->constrainRegClass(HeadCond[2].getReg(),
 604                            TII->getRegClass(MCID, 1, TRI, *MF));
 605   }
 606
 607   Head->splice(Head->end(), CmpBB, CmpBB->begin(), CmpBB->end());
 608
 609   // Now replace CmpMI with a ccmp instruction that also considers the incoming
 610   // flags.
 611   unsigned Opc = 0;
 612   unsigned FirstOp = 1;   // First CmpMI operand to copy.
 613   bool isZBranch = false; // CmpMI is a cbz/cbnz instruction.
 614   switch (CmpMI->getOpcode()) {
 615   default:
 616     llvm_unreachable("Unknown compare opcode");
 617   case ARM64::SUBSWri:    Opc = ARM64::CCMPWi; break;
 618   case ARM64::SUBSWrr:    Opc = ARM64::CCMPWr; break;
 619   case ARM64::SUBSXri:    Opc = ARM64::CCMPXi; break;
 620   case ARM64::SUBSXrr:    Opc = ARM64::CCMPXr; break;
 621   case ARM64::ADDSWri:    Opc = ARM64::CCMNWi; break;
 622   case ARM64::ADDSWrr:    Opc = ARM64::CCMNWr; break;
 623   case ARM64::ADDSXri:    Opc = ARM64::CCMNXi; break;
 624   case ARM64::ADDSXrr:    Opc = ARM64::CCMNXr; break;
 625   case ARM64::FCMPSrr:    Opc = ARM64::FCCMPSrr; FirstOp = 0; break;
 626   case ARM64::FCMPDrr:    Opc = ARM64::FCCMPDrr; FirstOp = 0; break;
 627   case ARM64::FCMPESrr:   Opc = ARM64::FCCMPESrr; FirstOp = 0; break;
 628   case ARM64::FCMPEDrr:   Opc = ARM64::FCCMPEDrr; FirstOp = 0; break;
 629   case ARM64::CBZW:
 630   case ARM64::CBNZW:
 631     Opc = ARM64::CCMPWi;
 632     FirstOp = 0;
 633     isZBranch = true;
 634     break;
 635   case ARM64::CBZX:
 636   case ARM64::CBNZX:
 637     Opc = ARM64::CCMPXi;
 638     FirstOp = 0;
 639     isZBranch = true;
 640     break;
 641   }
 642
 643   // The ccmp instruction should set the flags according to the comparison when
 644   // Head would have branched to CmpBB.
 645   // The NZCV immediate operand should provide flags for the case where Head
 646   // would have branched to Tail. These flags should cause the new Head
 647   // terminator to branch to tail.
 648   unsigned NZCV = ARM64CC::getNZCVToSatisfyCondCode(CmpBBTailCC);
 649   const MCInstrDesc &MCID = TII->get(Opc);
 650   MRI->constrainRegClass(CmpMI->getOperand(FirstOp).getReg(),
 651                          TII->getRegClass(MCID, 0, TRI, *MF));
 652   if (CmpMI->getOperand(FirstOp + 1).isReg())
 653     MRI->constrainRegClass(CmpMI->getOperand(FirstOp + 1).getReg(),
 654                            TII->getRegClass(MCID, 1, TRI, *MF));
 655   MachineInstrBuilder MIB =
 656       BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), MCID)
 657           .addOperand(CmpMI->getOperand(FirstOp)); // Register Rn
 658   if (isZBranch)
 659     MIB.addImm(0); // cbz/cbnz Rn -> ccmp Rn, #0
 660   else
 661     MIB.addOperand(CmpMI->getOperand(FirstOp + 1)); // Register Rm / Immediate
 662   MIB.addImm(NZCV).addImm(HeadCmpBBCC);
 663
 664   // If CmpMI was a terminator, we need a new conditional branch to replace it.
 665   // This now becomes a Head terminator.
 666   if (isZBranch) {
 667     bool isNZ = CmpMI->getOpcode() == ARM64::CBNZW ||
 668                 CmpMI->getOpcode() == ARM64::CBNZX;
 669     BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), TII->get(ARM64::Bcc))
 670         .addImm(isNZ ? ARM64CC::NE : ARM64CC::EQ)
 671         .addOperand(CmpMI->getOperand(1)); // Branch target.
 672   }
 673   CmpMI->eraseFromParent();
 674   Head->updateTerminator();
 675
 676   RemovedBlocks.push_back(CmpBB);
 677   CmpBB->eraseFromParent();
 678   DEBUG(dbgs() << "Result:\n" << *Head);
 679   ++NumConverted;
 680 }
 681
 682 int SSACCmpConv::expectedCodeSizeDelta() const {
 683   int delta = 0;
 684   // If the Head terminator was one of the cbz / tbz branches with built-in
 685   // compare, we need to insert an explicit compare instruction in its place
 686   // plus a branch instruction.
 687   if (HeadCond[0].getImm() == -1) {
 688     switch (HeadCond[1].getImm()) {
 689     case ARM64::CBZW:
 690     case ARM64::CBNZW:
 691     case ARM64::CBZX:
 692     case ARM64::CBNZX:
 693       // Therefore delta += 1
 694       delta = 1;
 695       break;
 696     default:
 697       llvm_unreachable("Cannot convert Head branch");
 698     }
 699   }
 700   // If the Cmp terminator was one of the cbz / tbz branches with
 701   // built-in compare, it will be turned into a compare instruction
 702   // into Head, but we do not save any instruction.
 703   // Otherwise, we save the branch instruction.
 704   switch (CmpMI->getOpcode()) {
 705   default:
 706     --delta;
 707     break;
 708   case ARM64::CBZW:
 709   case ARM64::CBNZW:
 710   case ARM64::CBZX:
 711   case ARM64::CBNZX:
 712     break;
 713   }
 714   return delta;
 715 }
 716
 717 //===----------------------------------------------------------------------===//
 718 //                       ARM64ConditionalCompares Pass
 719 //===----------------------------------------------------------------------===//
 720
 721 namespace {
 722 class ARM64ConditionalCompares : public MachineFunctionPass {
 723   const TargetInstrInfo *TII;
 724   const TargetRegisterInfo *TRI;
 725   const MCSchedModel *SchedModel;
 726   // Does the proceeded function has Oz attribute.
 727   bool MinSize;
 728   MachineRegisterInfo *MRI;
 729   MachineDominatorTree *DomTree;
 730   MachineLoopInfo *Loops;
 731   MachineTraceMetrics *Traces;
 732   MachineTraceMetrics::Ensemble *MinInstr;
 733   SSACCmpConv CmpConv;
 734
 735 public:
 736   static char ID;
 737   ARM64ConditionalCompares() : MachineFunctionPass(ID) {}
 738   void getAnalysisUsage(AnalysisUsage &AU) const;
 739   bool runOnMachineFunction(MachineFunction &MF);
 740   const char *getPassName() const { return "ARM64 Conditional Compares"; }
 741
 742 private:
 743   bool tryConvert(MachineBasicBlock *);
 744   void updateDomTree(ArrayRef<MachineBasicBlock *> Removed);
 745   void updateLoops(ArrayRef<MachineBasicBlock *> Removed);
 746   void invalidateTraces();
 747   bool shouldConvert();
 748 };
 749 } // end anonymous namespace
 750
 751 char ARM64ConditionalCompares::ID = 0;
 752
 753 namespace llvm {
 754 void initializeARM64ConditionalComparesPass(PassRegistry &);
 755 }
 756
 757 INITIALIZE_PASS_BEGIN(ARM64ConditionalCompares, "arm64-ccmp", "ARM64 CCMP Pass",
 758                       false, false)
 759 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 760 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 761 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
 762 INITIALIZE_PASS_END(ARM64ConditionalCompares, "arm64-ccmp", "ARM64 CCMP Pass",
 763                     false, false)
 764
 765 FunctionPass *llvm::createARM64ConditionalCompares() {
 766   return new ARM64ConditionalCompares();
 767 }
 768
 769 void ARM64ConditionalCompares::getAnalysisUsage(AnalysisUsage &AU) const {
 770   AU.addRequired<MachineBranchProbabilityInfo>();
 771   AU.addRequired<MachineDominatorTree>();
 772   AU.addPreserved<MachineDominatorTree>();
 773   AU.addRequired<MachineLoopInfo>();
 774   AU.addPreserved<MachineLoopInfo>();
 775   AU.addRequired<MachineTraceMetrics>();
 776   AU.addPreserved<MachineTraceMetrics>();
 777   MachineFunctionPass::getAnalysisUsage(AU);
 778 }
 779
 780 /// Update the dominator tree after if-conversion erased some blocks.
 781 void
 782 ARM64ConditionalCompares::updateDomTree(ArrayRef<MachineBasicBlock *> Removed) {
 783   // convert() removes CmpBB which was previously dominated by Head.
 784   // CmpBB children should be transferred to Head.
 785   MachineDomTreeNode *HeadNode = DomTree->getNode(CmpConv.Head);
 786   for (unsigned i = 0, e = Removed.size(); i != e; ++i) {
 787     MachineDomTreeNode *Node = DomTree->getNode(Removed[i]);
 788     assert(Node != HeadNode && "Cannot erase the head node");
 789     assert(Node->getIDom() == HeadNode && "CmpBB should be dominated by Head");
 790     while (Node->getNumChildren())
 791       DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode);
 792     DomTree->eraseNode(Removed[i]);
 793   }
 794 }
 795
 796 /// Update LoopInfo after if-conversion.
 797 void
 798 ARM64ConditionalCompares::updateLoops(ArrayRef<MachineBasicBlock *> Removed) {
 799   if (!Loops)
 800     return;
 801   for (unsigned i = 0, e = Removed.size(); i != e; ++i)
 802     Loops->removeBlock(Removed[i]);
 803 }
 804
 805 /// Invalidate MachineTraceMetrics before if-conversion.
 806 void ARM64ConditionalCompares::invalidateTraces() {
 807   Traces->invalidate(CmpConv.Head);
 808   Traces->invalidate(CmpConv.CmpBB);
 809 }
 810
 811 /// Apply cost model and heuristics to the if-conversion in IfConv.
 812 /// Return true if the conversion is a good idea.
 813 ///
 814 bool ARM64ConditionalCompares::shouldConvert() {
 815   // Stress testing mode disables all cost considerations.
 816   if (Stress)
 817     return true;
 818   if (!MinInstr)
 819     MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
 820
 821   // Head dominates CmpBB, so it is always included in its trace.
 822   MachineTraceMetrics::Trace Trace = MinInstr->getTrace(CmpConv.CmpBB);
 823
 824   // If code size is the main concern
 825   if (MinSize) {
 826     int CodeSizeDelta = CmpConv.expectedCodeSizeDelta();
 827     DEBUG(dbgs() << "Code size delta:  " << CodeSizeDelta << '\n');
 828     // If we are minimizing the code size, do the conversion whatever
 829     // the cost is.
 830     if (CodeSizeDelta < 0)
 831       return true;
 832     if (CodeSizeDelta > 0) {
 833       DEBUG(dbgs() << "Code size is increasing, give up on this one.\n");
 834       return false;
 835     }
 836     // CodeSizeDelta == 0, continue with the regular heuristics
 837   }
 838
 839   // Heuristic: The compare conversion delays the execution of the branch
 840   // instruction because we must wait for the inputs to the second compare as
 841   // well. The branch has no dependent instructions, but delaying it increases
 842   // the cost of a misprediction.
 843   //
 844   // Set a limit on the delay we will accept.
 845   unsigned DelayLimit = SchedModel->MispredictPenalty * 3 / 4;
 846
 847   // Instruction depths can be computed for all trace instructions above CmpBB.
 848   unsigned HeadDepth =
 849       Trace.getInstrCycles(CmpConv.Head->getFirstTerminator()).Depth;
 850   unsigned CmpBBDepth =
 851       Trace.getInstrCycles(CmpConv.CmpBB->getFirstTerminator()).Depth;
 852   DEBUG(dbgs() << "Head depth:  " << HeadDepth
 853                << "\nCmpBB depth: " << CmpBBDepth << '\n');
 854   if (CmpBBDepth > HeadDepth + DelayLimit) {
 855     DEBUG(dbgs() << "Branch delay would be larger than " << DelayLimit
 856                  << " cycles.\n");
 857     return false;
 858   }
 859
 860   // Check the resource depth at the bottom of CmpBB - these instructions will
 861   // be speculated.
 862   unsigned ResDepth = Trace.getResourceDepth(true);
 863   DEBUG(dbgs() << "Resources:   " << ResDepth << '\n');
 864
 865   // Heuristic: The speculatively executed instructions must all be able to
 866   // merge into the Head block. The Head critical path should dominate the
 867   // resource cost of the speculated instructions.
 868   if (ResDepth > HeadDepth) {
 869     DEBUG(dbgs() << "Too many instructions to speculate.\n");
 870     return false;
 871   }
 872   return true;
 873 }
 874
 875 bool ARM64ConditionalCompares::tryConvert(MachineBasicBlock *MBB) {
 876   bool Changed = false;
 877   while (CmpConv.canConvert(MBB) && shouldConvert()) {
 878     invalidateTraces();
 879     SmallVector<MachineBasicBlock *, 4> RemovedBlocks;
 880     CmpConv.convert(RemovedBlocks);
 881     Changed = true;
 882     updateDomTree(RemovedBlocks);
 883     updateLoops(RemovedBlocks);
 884   }
 885   return Changed;
 886 }
 887
 888 bool ARM64ConditionalCompares::runOnMachineFunction(MachineFunction &MF) {
 889   DEBUG(dbgs() << "********** ARM64 Conditional Compares **********\n"
 890                << "********** Function: " << MF.getName() << '\n');
 891   TII = MF.getTarget().getInstrInfo();
 892   TRI = MF.getTarget().getRegisterInfo();
 893   SchedModel =
 894       MF.getTarget().getSubtarget<TargetSubtargetInfo>().getSchedModel();
 895   MRI = &MF.getRegInfo();
 896   DomTree = &getAnalysis<MachineDominatorTree>();
 897   Loops = getAnalysisIfAvailable<MachineLoopInfo>();
 898   Traces = &getAnalysis<MachineTraceMetrics>();
 899   MinInstr = 0;
 900   MinSize = MF.getFunction()->getAttributes().hasAttribute(
 901       AttributeSet::FunctionIndex, Attribute::MinSize);
 902
 903   bool Changed = false;
 904   CmpConv.runOnMachineFunction(MF);
 905
 906   // Visit blocks in dominator tree pre-order. The pre-order enables multiple
 907   // cmp-conversions from the same head block.
 908   // Note that updateDomTree() modifies the children of the DomTree node
 909   // currently being visited. The df_iterator supports that, it doesn't look at
 910   // child_begin() / child_end() until after a node has been visited.
 911   for (df_iterator<MachineDominatorTree *> I = df_begin(DomTree),
 912                                            E = df_end(DomTree);
 913        I != E; ++I)
 914     if (tryConvert(I->getBlock()))
 915       Changed = true;
 916
 917   return Changed;
 918 }