LCOV - code coverage report
Current view: top level - lib/Target/AArch64 - AArch64ConditionalCompares.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 215 242 88.8 %
Date: 2018-06-17 00:07:59 Functions: 23 24 95.8 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13