10b57cec5SDimitry Andric //===-- AArch64ConditionalCompares.cpp --- CCMP formation for AArch64 -----===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file implements the AArch64ConditionalCompares pass which reduces 100b57cec5SDimitry Andric // branching and code size by using the conditional compare instructions CCMP, 110b57cec5SDimitry Andric // CCMN, and FCMP. 120b57cec5SDimitry Andric // 130b57cec5SDimitry Andric // The CFG transformations for forming conditional compares are very similar to 140b57cec5SDimitry Andric // if-conversion, and this pass should run immediately before the early 150b57cec5SDimitry Andric // if-conversion pass. 160b57cec5SDimitry Andric // 170b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 180b57cec5SDimitry Andric 190b57cec5SDimitry Andric #include "AArch64.h" 200b57cec5SDimitry Andric #include "llvm/ADT/DepthFirstIterator.h" 210b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h" 220b57cec5SDimitry Andric #include "llvm/ADT/Statistic.h" 230b57cec5SDimitry Andric #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 240b57cec5SDimitry Andric #include "llvm/CodeGen/MachineDominators.h" 250b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunction.h" 260b57cec5SDimitry Andric #include "llvm/CodeGen/MachineFunctionPass.h" 270b57cec5SDimitry Andric #include "llvm/CodeGen/MachineInstrBuilder.h" 280b57cec5SDimitry Andric #include "llvm/CodeGen/MachineLoopInfo.h" 290b57cec5SDimitry Andric #include "llvm/CodeGen/MachineRegisterInfo.h" 300b57cec5SDimitry Andric #include "llvm/CodeGen/MachineTraceMetrics.h" 310b57cec5SDimitry Andric #include "llvm/CodeGen/Passes.h" 320b57cec5SDimitry Andric #include "llvm/CodeGen/TargetInstrInfo.h" 330b57cec5SDimitry Andric #include "llvm/CodeGen/TargetRegisterInfo.h" 340b57cec5SDimitry Andric #include "llvm/CodeGen/TargetSubtargetInfo.h" 35480093f4SDimitry Andric #include "llvm/InitializePasses.h" 360b57cec5SDimitry Andric #include "llvm/Support/CommandLine.h" 370b57cec5SDimitry Andric #include "llvm/Support/Debug.h" 380b57cec5SDimitry Andric #include "llvm/Support/raw_ostream.h" 390b57cec5SDimitry Andric 400b57cec5SDimitry Andric using namespace llvm; 410b57cec5SDimitry Andric 420b57cec5SDimitry Andric #define DEBUG_TYPE "aarch64-ccmp" 430b57cec5SDimitry Andric 440b57cec5SDimitry Andric // Absolute maximum number of instructions allowed per speculated block. 450b57cec5SDimitry Andric // This bypasses all other heuristics, so it should be set fairly high. 460b57cec5SDimitry Andric static cl::opt<unsigned> BlockInstrLimit( 470b57cec5SDimitry Andric "aarch64-ccmp-limit", cl::init(30), cl::Hidden, 480b57cec5SDimitry Andric cl::desc("Maximum number of instructions per speculated block.")); 490b57cec5SDimitry Andric 500b57cec5SDimitry Andric // Stress testing mode - disable heuristics. 510b57cec5SDimitry Andric static cl::opt<bool> Stress("aarch64-stress-ccmp", cl::Hidden, 520b57cec5SDimitry Andric cl::desc("Turn all knobs to 11")); 530b57cec5SDimitry Andric 540b57cec5SDimitry Andric STATISTIC(NumConsidered, "Number of ccmps considered"); 550b57cec5SDimitry Andric STATISTIC(NumPhiRejs, "Number of ccmps rejected (PHI)"); 560b57cec5SDimitry Andric STATISTIC(NumPhysRejs, "Number of ccmps rejected (Physregs)"); 570b57cec5SDimitry Andric STATISTIC(NumPhi2Rejs, "Number of ccmps rejected (PHI2)"); 580b57cec5SDimitry Andric STATISTIC(NumHeadBranchRejs, "Number of ccmps rejected (Head branch)"); 590b57cec5SDimitry Andric STATISTIC(NumCmpBranchRejs, "Number of ccmps rejected (CmpBB branch)"); 600b57cec5SDimitry Andric STATISTIC(NumCmpTermRejs, "Number of ccmps rejected (CmpBB is cbz...)"); 610b57cec5SDimitry Andric STATISTIC(NumImmRangeRejs, "Number of ccmps rejected (Imm out of range)"); 620b57cec5SDimitry Andric STATISTIC(NumLiveDstRejs, "Number of ccmps rejected (Cmp dest live)"); 630b57cec5SDimitry Andric STATISTIC(NumMultNZCVUses, "Number of ccmps rejected (NZCV used)"); 640b57cec5SDimitry Andric STATISTIC(NumUnknNZCVDefs, "Number of ccmps rejected (NZCV def unknown)"); 650b57cec5SDimitry Andric 660b57cec5SDimitry Andric STATISTIC(NumSpeculateRejs, "Number of ccmps rejected (Can't speculate)"); 670b57cec5SDimitry Andric 680b57cec5SDimitry Andric STATISTIC(NumConverted, "Number of ccmp instructions created"); 690b57cec5SDimitry Andric STATISTIC(NumCompBranches, "Number of cbz/cbnz branches converted"); 700b57cec5SDimitry Andric 710b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 720b57cec5SDimitry Andric // SSACCmpConv 730b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 740b57cec5SDimitry Andric // 750b57cec5SDimitry Andric // The SSACCmpConv class performs ccmp-conversion on SSA form machine code 760b57cec5SDimitry Andric // after determining if it is possible. The class contains no heuristics; 770b57cec5SDimitry Andric // external code should be used to determine when ccmp-conversion is a good 780b57cec5SDimitry Andric // idea. 790b57cec5SDimitry Andric // 800b57cec5SDimitry Andric // CCmp-formation works on a CFG representing chained conditions, typically 810b57cec5SDimitry Andric // from C's short-circuit || and && operators: 820b57cec5SDimitry Andric // 830b57cec5SDimitry Andric // From: Head To: Head 840b57cec5SDimitry Andric // / | CmpBB 850b57cec5SDimitry Andric // / | / | 860b57cec5SDimitry Andric // | CmpBB / | 870b57cec5SDimitry Andric // | / | Tail | 880b57cec5SDimitry Andric // | / | | | 890b57cec5SDimitry Andric // Tail | | | 900b57cec5SDimitry Andric // | | | | 910b57cec5SDimitry Andric // ... ... ... ... 920b57cec5SDimitry Andric // 930b57cec5SDimitry Andric // The Head block is terminated by a br.cond instruction, and the CmpBB block 940b57cec5SDimitry Andric // contains compare + br.cond. Tail must be a successor of both. 950b57cec5SDimitry Andric // 960b57cec5SDimitry Andric // The cmp-conversion turns the compare instruction in CmpBB into a conditional 970b57cec5SDimitry Andric // compare, and merges CmpBB into Head, speculatively executing its 980b57cec5SDimitry Andric // instructions. The AArch64 conditional compare instructions have an immediate 990b57cec5SDimitry Andric // operand that specifies the NZCV flag values when the condition is false and 1000b57cec5SDimitry Andric // the compare isn't executed. This makes it possible to chain compares with 1010b57cec5SDimitry Andric // different condition codes. 1020b57cec5SDimitry Andric // 1030b57cec5SDimitry Andric // Example: 1040b57cec5SDimitry Andric // 1050b57cec5SDimitry Andric // if (a == 5 || b == 17) 1060b57cec5SDimitry Andric // foo(); 1070b57cec5SDimitry Andric // 1080b57cec5SDimitry Andric // Head: 1090b57cec5SDimitry Andric // cmp w0, #5 1100b57cec5SDimitry Andric // b.eq Tail 1110b57cec5SDimitry Andric // CmpBB: 1120b57cec5SDimitry Andric // cmp w1, #17 1130b57cec5SDimitry Andric // b.eq Tail 1140b57cec5SDimitry Andric // ... 1150b57cec5SDimitry Andric // Tail: 1160b57cec5SDimitry Andric // bl _foo 1170b57cec5SDimitry Andric // 1180b57cec5SDimitry Andric // Becomes: 1190b57cec5SDimitry Andric // 1200b57cec5SDimitry Andric // Head: 1210b57cec5SDimitry Andric // cmp w0, #5 1220b57cec5SDimitry Andric // ccmp w1, #17, 4, ne ; 4 = nZcv 1230b57cec5SDimitry Andric // b.eq Tail 1240b57cec5SDimitry Andric // ... 1250b57cec5SDimitry Andric // Tail: 1260b57cec5SDimitry Andric // bl _foo 1270b57cec5SDimitry Andric // 1280b57cec5SDimitry Andric // The ccmp condition code is the one that would cause the Head terminator to 1290b57cec5SDimitry Andric // branch to CmpBB. 1300b57cec5SDimitry Andric // 1310b57cec5SDimitry Andric // FIXME: It should also be possible to speculate a block on the critical edge 1320b57cec5SDimitry Andric // between Head and Tail, just like if-converting a diamond. 1330b57cec5SDimitry Andric // 1340b57cec5SDimitry Andric // FIXME: Handle PHIs in Tail by turning them into selects (if-conversion). 1350b57cec5SDimitry Andric 1360b57cec5SDimitry Andric namespace { 1370b57cec5SDimitry Andric class SSACCmpConv { 1380b57cec5SDimitry Andric MachineFunction *MF; 1390b57cec5SDimitry Andric const TargetInstrInfo *TII; 1400b57cec5SDimitry Andric const TargetRegisterInfo *TRI; 1410b57cec5SDimitry Andric MachineRegisterInfo *MRI; 1420b57cec5SDimitry Andric const MachineBranchProbabilityInfo *MBPI; 1430b57cec5SDimitry Andric 1440b57cec5SDimitry Andric public: 1450b57cec5SDimitry Andric /// The first block containing a conditional branch, dominating everything 1460b57cec5SDimitry Andric /// else. 1470b57cec5SDimitry Andric MachineBasicBlock *Head; 1480b57cec5SDimitry Andric 1490b57cec5SDimitry Andric /// The block containing cmp+br.cond with a successor shared with Head. 1500b57cec5SDimitry Andric MachineBasicBlock *CmpBB; 1510b57cec5SDimitry Andric 1520b57cec5SDimitry Andric /// The common successor for Head and CmpBB. 1530b57cec5SDimitry Andric MachineBasicBlock *Tail; 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric /// The compare instruction in CmpBB that can be converted to a ccmp. 1560b57cec5SDimitry Andric MachineInstr *CmpMI; 1570b57cec5SDimitry Andric 1580b57cec5SDimitry Andric private: 1595ffd83dbSDimitry Andric /// The branch condition in Head as determined by analyzeBranch. 1600b57cec5SDimitry Andric SmallVector<MachineOperand, 4> HeadCond; 1610b57cec5SDimitry Andric 1620b57cec5SDimitry Andric /// The condition code that makes Head branch to CmpBB. 1630b57cec5SDimitry Andric AArch64CC::CondCode HeadCmpBBCC; 1640b57cec5SDimitry Andric 1650b57cec5SDimitry Andric /// The branch condition in CmpBB. 1660b57cec5SDimitry Andric SmallVector<MachineOperand, 4> CmpBBCond; 1670b57cec5SDimitry Andric 1680b57cec5SDimitry Andric /// The condition code that makes CmpBB branch to Tail. 1690b57cec5SDimitry Andric AArch64CC::CondCode CmpBBTailCC; 1700b57cec5SDimitry Andric 1710b57cec5SDimitry Andric /// Check if the Tail PHIs are trivially convertible. 1720b57cec5SDimitry Andric bool trivialTailPHIs(); 1730b57cec5SDimitry Andric 1740b57cec5SDimitry Andric /// Remove CmpBB from the Tail PHIs. 1750b57cec5SDimitry Andric void updateTailPHIs(); 1760b57cec5SDimitry Andric 1770b57cec5SDimitry Andric /// Check if an operand defining DstReg is dead. 1780b57cec5SDimitry Andric bool isDeadDef(unsigned DstReg); 1790b57cec5SDimitry Andric 1800b57cec5SDimitry Andric /// Find the compare instruction in MBB that controls the conditional branch. 1810b57cec5SDimitry Andric /// Return NULL if a convertible instruction can't be found. 1820b57cec5SDimitry Andric MachineInstr *findConvertibleCompare(MachineBasicBlock *MBB); 1830b57cec5SDimitry Andric 1840b57cec5SDimitry Andric /// Return true if all non-terminator instructions in MBB can be safely 1850b57cec5SDimitry Andric /// speculated. 1860b57cec5SDimitry Andric bool canSpeculateInstrs(MachineBasicBlock *MBB, const MachineInstr *CmpMI); 1870b57cec5SDimitry Andric 1880b57cec5SDimitry Andric public: 1890b57cec5SDimitry Andric /// runOnMachineFunction - Initialize per-function data structures. 1900b57cec5SDimitry Andric void runOnMachineFunction(MachineFunction &MF, 1910b57cec5SDimitry Andric const MachineBranchProbabilityInfo *MBPI) { 1920b57cec5SDimitry Andric this->MF = &MF; 1930b57cec5SDimitry Andric this->MBPI = MBPI; 1940b57cec5SDimitry Andric TII = MF.getSubtarget().getInstrInfo(); 1950b57cec5SDimitry Andric TRI = MF.getSubtarget().getRegisterInfo(); 1960b57cec5SDimitry Andric MRI = &MF.getRegInfo(); 1970b57cec5SDimitry Andric } 1980b57cec5SDimitry Andric 1990b57cec5SDimitry Andric /// If the sub-CFG headed by MBB can be cmp-converted, initialize the 2000b57cec5SDimitry Andric /// internal state, and return true. 2010b57cec5SDimitry Andric bool canConvert(MachineBasicBlock *MBB); 2020b57cec5SDimitry Andric 2030b57cec5SDimitry Andric /// Cmo-convert the last block passed to canConvertCmp(), assuming 2040b57cec5SDimitry Andric /// it is possible. Add any erased blocks to RemovedBlocks. 2050b57cec5SDimitry Andric void convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks); 2060b57cec5SDimitry Andric 2070b57cec5SDimitry Andric /// Return the expected code size delta if the conversion into a 2080b57cec5SDimitry Andric /// conditional compare is performed. 2090b57cec5SDimitry Andric int expectedCodeSizeDelta() const; 2100b57cec5SDimitry Andric }; 2110b57cec5SDimitry Andric } // end anonymous namespace 2120b57cec5SDimitry Andric 2130b57cec5SDimitry Andric // Check that all PHIs in Tail are selecting the same value from Head and CmpBB. 2140b57cec5SDimitry Andric // This means that no if-conversion is required when merging CmpBB into Head. 2150b57cec5SDimitry Andric bool SSACCmpConv::trivialTailPHIs() { 2160b57cec5SDimitry Andric for (auto &I : *Tail) { 2170b57cec5SDimitry Andric if (!I.isPHI()) 2180b57cec5SDimitry Andric break; 2190b57cec5SDimitry Andric unsigned HeadReg = 0, CmpBBReg = 0; 2200b57cec5SDimitry Andric // PHI operands come in (VReg, MBB) pairs. 2210b57cec5SDimitry Andric for (unsigned oi = 1, oe = I.getNumOperands(); oi != oe; oi += 2) { 2220b57cec5SDimitry Andric MachineBasicBlock *MBB = I.getOperand(oi + 1).getMBB(); 2238bcb0991SDimitry Andric Register Reg = I.getOperand(oi).getReg(); 2240b57cec5SDimitry Andric if (MBB == Head) { 2250b57cec5SDimitry Andric assert((!HeadReg || HeadReg == Reg) && "Inconsistent PHI operands"); 2260b57cec5SDimitry Andric HeadReg = Reg; 2270b57cec5SDimitry Andric } 2280b57cec5SDimitry Andric if (MBB == CmpBB) { 2290b57cec5SDimitry Andric assert((!CmpBBReg || CmpBBReg == Reg) && "Inconsistent PHI operands"); 2300b57cec5SDimitry Andric CmpBBReg = Reg; 2310b57cec5SDimitry Andric } 2320b57cec5SDimitry Andric } 2330b57cec5SDimitry Andric if (HeadReg != CmpBBReg) 2340b57cec5SDimitry Andric return false; 2350b57cec5SDimitry Andric } 2360b57cec5SDimitry Andric return true; 2370b57cec5SDimitry Andric } 2380b57cec5SDimitry Andric 2390b57cec5SDimitry Andric // Assuming that trivialTailPHIs() is true, update the Tail PHIs by simply 2400b57cec5SDimitry Andric // removing the CmpBB operands. The Head operands will be identical. 2410b57cec5SDimitry Andric void SSACCmpConv::updateTailPHIs() { 2420b57cec5SDimitry Andric for (auto &I : *Tail) { 2430b57cec5SDimitry Andric if (!I.isPHI()) 2440b57cec5SDimitry Andric break; 2450b57cec5SDimitry Andric // I is a PHI. It can have multiple entries for CmpBB. 2460b57cec5SDimitry Andric for (unsigned oi = I.getNumOperands(); oi > 2; oi -= 2) { 2470b57cec5SDimitry Andric // PHI operands are (Reg, MBB) at (oi-2, oi-1). 2480b57cec5SDimitry Andric if (I.getOperand(oi - 1).getMBB() == CmpBB) { 24981ad6265SDimitry Andric I.removeOperand(oi - 1); 25081ad6265SDimitry Andric I.removeOperand(oi - 2); 2510b57cec5SDimitry Andric } 2520b57cec5SDimitry Andric } 2530b57cec5SDimitry Andric } 2540b57cec5SDimitry Andric } 2550b57cec5SDimitry Andric 2560b57cec5SDimitry Andric // This pass runs before the AArch64DeadRegisterDefinitions pass, so compares 2570b57cec5SDimitry Andric // are still writing virtual registers without any uses. 2580b57cec5SDimitry Andric bool SSACCmpConv::isDeadDef(unsigned DstReg) { 2590b57cec5SDimitry Andric // Writes to the zero register are dead. 2600b57cec5SDimitry Andric if (DstReg == AArch64::WZR || DstReg == AArch64::XZR) 2610b57cec5SDimitry Andric return true; 2628bcb0991SDimitry Andric if (!Register::isVirtualRegister(DstReg)) 2630b57cec5SDimitry Andric return false; 2640b57cec5SDimitry Andric // A virtual register def without any uses will be marked dead later, and 2650b57cec5SDimitry Andric // eventually replaced by the zero register. 2660b57cec5SDimitry Andric return MRI->use_nodbg_empty(DstReg); 2670b57cec5SDimitry Andric } 2680b57cec5SDimitry Andric 2695ffd83dbSDimitry Andric // Parse a condition code returned by analyzeBranch, and compute the CondCode 2700b57cec5SDimitry Andric // corresponding to TBB. 2710b57cec5SDimitry Andric // Return 2720b57cec5SDimitry Andric static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) { 2730b57cec5SDimitry Andric // A normal br.cond simply has the condition code. 2740b57cec5SDimitry Andric if (Cond[0].getImm() != -1) { 2750b57cec5SDimitry Andric assert(Cond.size() == 1 && "Unknown Cond array format"); 2760b57cec5SDimitry Andric CC = (AArch64CC::CondCode)(int)Cond[0].getImm(); 2770b57cec5SDimitry Andric return true; 2780b57cec5SDimitry Andric } 2790b57cec5SDimitry Andric // For tbz and cbz instruction, the opcode is next. 2800b57cec5SDimitry Andric switch (Cond[1].getImm()) { 2810b57cec5SDimitry Andric default: 2820b57cec5SDimitry Andric // This includes tbz / tbnz branches which can't be converted to 2830b57cec5SDimitry Andric // ccmp + br.cond. 2840b57cec5SDimitry Andric return false; 2850b57cec5SDimitry Andric case AArch64::CBZW: 2860b57cec5SDimitry Andric case AArch64::CBZX: 2870b57cec5SDimitry Andric assert(Cond.size() == 3 && "Unknown Cond array format"); 2880b57cec5SDimitry Andric CC = AArch64CC::EQ; 2890b57cec5SDimitry Andric return true; 2900b57cec5SDimitry Andric case AArch64::CBNZW: 2910b57cec5SDimitry Andric case AArch64::CBNZX: 2920b57cec5SDimitry Andric assert(Cond.size() == 3 && "Unknown Cond array format"); 2930b57cec5SDimitry Andric CC = AArch64CC::NE; 2940b57cec5SDimitry Andric return true; 2950b57cec5SDimitry Andric } 2960b57cec5SDimitry Andric } 2970b57cec5SDimitry Andric 2980b57cec5SDimitry Andric MachineInstr *SSACCmpConv::findConvertibleCompare(MachineBasicBlock *MBB) { 2990b57cec5SDimitry Andric MachineBasicBlock::iterator I = MBB->getFirstTerminator(); 3000b57cec5SDimitry Andric if (I == MBB->end()) 3010b57cec5SDimitry Andric return nullptr; 3020b57cec5SDimitry Andric // The terminator must be controlled by the flags. 3030b57cec5SDimitry Andric if (!I->readsRegister(AArch64::NZCV)) { 3040b57cec5SDimitry Andric switch (I->getOpcode()) { 3050b57cec5SDimitry Andric case AArch64::CBZW: 3060b57cec5SDimitry Andric case AArch64::CBZX: 3070b57cec5SDimitry Andric case AArch64::CBNZW: 3080b57cec5SDimitry Andric case AArch64::CBNZX: 3090b57cec5SDimitry Andric // These can be converted into a ccmp against #0. 3100b57cec5SDimitry Andric return &*I; 3110b57cec5SDimitry Andric } 3120b57cec5SDimitry Andric ++NumCmpTermRejs; 3130b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Flags not used by terminator: " << *I); 3140b57cec5SDimitry Andric return nullptr; 3150b57cec5SDimitry Andric } 3160b57cec5SDimitry Andric 3170b57cec5SDimitry Andric // Now find the instruction controlling the terminator. 3180b57cec5SDimitry Andric for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) { 3195ffd83dbSDimitry Andric I = prev_nodbg(I, MBB->begin()); 3200b57cec5SDimitry Andric assert(!I->isTerminator() && "Spurious terminator"); 3210b57cec5SDimitry Andric switch (I->getOpcode()) { 3220b57cec5SDimitry Andric // cmp is an alias for subs with a dead destination register. 3230b57cec5SDimitry Andric case AArch64::SUBSWri: 3240b57cec5SDimitry Andric case AArch64::SUBSXri: 3250b57cec5SDimitry Andric // cmn is an alias for adds with a dead destination register. 3260b57cec5SDimitry Andric case AArch64::ADDSWri: 3270b57cec5SDimitry Andric case AArch64::ADDSXri: 3280b57cec5SDimitry Andric // Check that the immediate operand is within range, ccmp wants a uimm5. 3290b57cec5SDimitry Andric // Rd = SUBSri Rn, imm, shift 3300b57cec5SDimitry Andric if (I->getOperand(3).getImm() || !isUInt<5>(I->getOperand(2).getImm())) { 3310b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Immediate out of range for ccmp: " << *I); 3320b57cec5SDimitry Andric ++NumImmRangeRejs; 3330b57cec5SDimitry Andric return nullptr; 3340b57cec5SDimitry Andric } 335bdd1243dSDimitry Andric [[fallthrough]]; 3360b57cec5SDimitry Andric case AArch64::SUBSWrr: 3370b57cec5SDimitry Andric case AArch64::SUBSXrr: 3380b57cec5SDimitry Andric case AArch64::ADDSWrr: 3390b57cec5SDimitry Andric case AArch64::ADDSXrr: 3400b57cec5SDimitry Andric if (isDeadDef(I->getOperand(0).getReg())) 3410b57cec5SDimitry Andric return &*I; 3420b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't convert compare with live destination: " 3430b57cec5SDimitry Andric << *I); 3440b57cec5SDimitry Andric ++NumLiveDstRejs; 3450b57cec5SDimitry Andric return nullptr; 3460b57cec5SDimitry Andric case AArch64::FCMPSrr: 3470b57cec5SDimitry Andric case AArch64::FCMPDrr: 3480b57cec5SDimitry Andric case AArch64::FCMPESrr: 3490b57cec5SDimitry Andric case AArch64::FCMPEDrr: 3500b57cec5SDimitry Andric return &*I; 3510b57cec5SDimitry Andric } 3520b57cec5SDimitry Andric 3530b57cec5SDimitry Andric // Check for flag reads and clobbers. 354480093f4SDimitry Andric PhysRegInfo PRI = AnalyzePhysRegInBundle(*I, AArch64::NZCV, TRI); 3550b57cec5SDimitry Andric 3560b57cec5SDimitry Andric if (PRI.Read) { 3570b57cec5SDimitry Andric // The ccmp doesn't produce exactly the same flags as the original 3580b57cec5SDimitry Andric // compare, so reject the transform if there are uses of the flags 3590b57cec5SDimitry Andric // besides the terminators. 3600b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't create ccmp with multiple uses: " << *I); 3610b57cec5SDimitry Andric ++NumMultNZCVUses; 3620b57cec5SDimitry Andric return nullptr; 3630b57cec5SDimitry Andric } 3640b57cec5SDimitry Andric 3650b57cec5SDimitry Andric if (PRI.Defined || PRI.Clobbered) { 3660b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Not convertible compare: " << *I); 3670b57cec5SDimitry Andric ++NumUnknNZCVDefs; 3680b57cec5SDimitry Andric return nullptr; 3690b57cec5SDimitry Andric } 3700b57cec5SDimitry Andric } 3710b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB) 3720b57cec5SDimitry Andric << '\n'); 3730b57cec5SDimitry Andric return nullptr; 3740b57cec5SDimitry Andric } 3750b57cec5SDimitry Andric 3760b57cec5SDimitry Andric /// Determine if all the instructions in MBB can safely 3770b57cec5SDimitry Andric /// be speculated. The terminators are not considered. 3780b57cec5SDimitry Andric /// 3790b57cec5SDimitry Andric /// Only CmpMI is allowed to clobber the flags. 3800b57cec5SDimitry Andric /// 3810b57cec5SDimitry Andric bool SSACCmpConv::canSpeculateInstrs(MachineBasicBlock *MBB, 3820b57cec5SDimitry Andric const MachineInstr *CmpMI) { 3830b57cec5SDimitry Andric // Reject any live-in physregs. It's probably NZCV/EFLAGS, and very hard to 3840b57cec5SDimitry Andric // get right. 3850b57cec5SDimitry Andric if (!MBB->livein_empty()) { 3860b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); 3870b57cec5SDimitry Andric return false; 3880b57cec5SDimitry Andric } 3890b57cec5SDimitry Andric 3900b57cec5SDimitry Andric unsigned InstrCount = 0; 3910b57cec5SDimitry Andric 3920b57cec5SDimitry Andric // Check all instructions, except the terminators. It is assumed that 3930b57cec5SDimitry Andric // terminators never have side effects or define any used register values. 3940b57cec5SDimitry Andric for (auto &I : make_range(MBB->begin(), MBB->getFirstTerminator())) { 3950b57cec5SDimitry Andric if (I.isDebugInstr()) 3960b57cec5SDimitry Andric continue; 3970b57cec5SDimitry Andric 3980b57cec5SDimitry Andric if (++InstrCount > BlockInstrLimit && !Stress) { 3990b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than " 4000b57cec5SDimitry Andric << BlockInstrLimit << " instructions.\n"); 4010b57cec5SDimitry Andric return false; 4020b57cec5SDimitry Andric } 4030b57cec5SDimitry Andric 4040b57cec5SDimitry Andric // There shouldn't normally be any phis in a single-predecessor block. 4050b57cec5SDimitry Andric if (I.isPHI()) { 4060b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't hoist: " << I); 4070b57cec5SDimitry Andric return false; 4080b57cec5SDimitry Andric } 4090b57cec5SDimitry Andric 4100b57cec5SDimitry Andric // Don't speculate loads. Note that it may be possible and desirable to 4110b57cec5SDimitry Andric // speculate GOT or constant pool loads that are guaranteed not to trap, 4120b57cec5SDimitry Andric // but we don't support that for now. 4130b57cec5SDimitry Andric if (I.mayLoad()) { 4140b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Won't speculate load: " << I); 4150b57cec5SDimitry Andric return false; 4160b57cec5SDimitry Andric } 4170b57cec5SDimitry Andric 4180b57cec5SDimitry Andric // We never speculate stores, so an AA pointer isn't necessary. 4190b57cec5SDimitry Andric bool DontMoveAcrossStore = true; 4200b57cec5SDimitry Andric if (!I.isSafeToMove(nullptr, DontMoveAcrossStore)) { 4210b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't speculate: " << I); 4220b57cec5SDimitry Andric return false; 4230b57cec5SDimitry Andric } 4240b57cec5SDimitry Andric 4250b57cec5SDimitry Andric // Only CmpMI is allowed to clobber the flags. 4260b57cec5SDimitry Andric if (&I != CmpMI && I.modifiesRegister(AArch64::NZCV, TRI)) { 4270b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Clobbers flags: " << I); 4280b57cec5SDimitry Andric return false; 4290b57cec5SDimitry Andric } 4300b57cec5SDimitry Andric } 4310b57cec5SDimitry Andric return true; 4320b57cec5SDimitry Andric } 4330b57cec5SDimitry Andric 4340b57cec5SDimitry Andric /// Analyze the sub-cfg rooted in MBB, and return true if it is a potential 4350b57cec5SDimitry Andric /// candidate for cmp-conversion. Fill out the internal state. 4360b57cec5SDimitry Andric /// 4370b57cec5SDimitry Andric bool SSACCmpConv::canConvert(MachineBasicBlock *MBB) { 4380b57cec5SDimitry Andric Head = MBB; 4390b57cec5SDimitry Andric Tail = CmpBB = nullptr; 4400b57cec5SDimitry Andric 4410b57cec5SDimitry Andric if (Head->succ_size() != 2) 4420b57cec5SDimitry Andric return false; 4430b57cec5SDimitry Andric MachineBasicBlock *Succ0 = Head->succ_begin()[0]; 4440b57cec5SDimitry Andric MachineBasicBlock *Succ1 = Head->succ_begin()[1]; 4450b57cec5SDimitry Andric 4460b57cec5SDimitry Andric // CmpBB can only have a single predecessor. Tail is allowed many. 4470b57cec5SDimitry Andric if (Succ0->pred_size() != 1) 4480b57cec5SDimitry Andric std::swap(Succ0, Succ1); 4490b57cec5SDimitry Andric 4500b57cec5SDimitry Andric // Succ0 is our candidate for CmpBB. 4510b57cec5SDimitry Andric if (Succ0->pred_size() != 1 || Succ0->succ_size() != 2) 4520b57cec5SDimitry Andric return false; 4530b57cec5SDimitry Andric 4540b57cec5SDimitry Andric CmpBB = Succ0; 4550b57cec5SDimitry Andric Tail = Succ1; 4560b57cec5SDimitry Andric 4570b57cec5SDimitry Andric if (!CmpBB->isSuccessor(Tail)) 4580b57cec5SDimitry Andric return false; 4590b57cec5SDimitry Andric 4600b57cec5SDimitry Andric // The CFG topology checks out. 4610b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> " 4620b57cec5SDimitry Andric << printMBBReference(*CmpBB) << " -> " 4630b57cec5SDimitry Andric << printMBBReference(*Tail) << '\n'); 4640b57cec5SDimitry Andric ++NumConsidered; 4650b57cec5SDimitry Andric 4660b57cec5SDimitry Andric // Tail is allowed to have many predecessors, but we can't handle PHIs yet. 4670b57cec5SDimitry Andric // 4680b57cec5SDimitry Andric // FIXME: Real PHIs could be if-converted as long as the CmpBB values are 4690b57cec5SDimitry Andric // defined before The CmpBB cmp clobbers the flags. Alternatively, it should 4700b57cec5SDimitry Andric // always be safe to sink the ccmp down to immediately before the CmpBB 4710b57cec5SDimitry Andric // terminators. 4720b57cec5SDimitry Andric if (!trivialTailPHIs()) { 4730b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't handle phis in Tail.\n"); 4740b57cec5SDimitry Andric ++NumPhiRejs; 4750b57cec5SDimitry Andric return false; 4760b57cec5SDimitry Andric } 4770b57cec5SDimitry Andric 4780b57cec5SDimitry Andric if (!Tail->livein_empty()) { 4790b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in Tail.\n"); 4800b57cec5SDimitry Andric ++NumPhysRejs; 4810b57cec5SDimitry Andric return false; 4820b57cec5SDimitry Andric } 4830b57cec5SDimitry Andric 4840b57cec5SDimitry Andric // CmpBB should never have PHIs since Head is its only predecessor. 4850b57cec5SDimitry Andric // FIXME: Clean them up if it happens. 4860b57cec5SDimitry Andric if (!CmpBB->empty() && CmpBB->front().isPHI()) { 4870b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't handle phis in CmpBB.\n"); 4880b57cec5SDimitry Andric ++NumPhi2Rejs; 4890b57cec5SDimitry Andric return false; 4900b57cec5SDimitry Andric } 4910b57cec5SDimitry Andric 4920b57cec5SDimitry Andric if (!CmpBB->livein_empty()) { 4930b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in CmpBB.\n"); 4940b57cec5SDimitry Andric ++NumPhysRejs; 4950b57cec5SDimitry Andric return false; 4960b57cec5SDimitry Andric } 4970b57cec5SDimitry Andric 4980b57cec5SDimitry Andric // The branch we're looking to eliminate must be analyzable. 4990b57cec5SDimitry Andric HeadCond.clear(); 5000b57cec5SDimitry Andric MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 5010b57cec5SDimitry Andric if (TII->analyzeBranch(*Head, TBB, FBB, HeadCond)) { 5020b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Head branch not analyzable.\n"); 5030b57cec5SDimitry Andric ++NumHeadBranchRejs; 5040b57cec5SDimitry Andric return false; 5050b57cec5SDimitry Andric } 5060b57cec5SDimitry Andric 5070b57cec5SDimitry Andric // This is weird, probably some sort of degenerate CFG, or an edge to a 5080b57cec5SDimitry Andric // landing pad. 5090b57cec5SDimitry Andric if (!TBB || HeadCond.empty()) { 5100b57cec5SDimitry Andric LLVM_DEBUG( 5115ffd83dbSDimitry Andric dbgs() << "analyzeBranch didn't find conditional branch in Head.\n"); 5120b57cec5SDimitry Andric ++NumHeadBranchRejs; 5130b57cec5SDimitry Andric return false; 5140b57cec5SDimitry Andric } 5150b57cec5SDimitry Andric 5160b57cec5SDimitry Andric if (!parseCond(HeadCond, HeadCmpBBCC)) { 5170b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Unsupported branch type on Head\n"); 5180b57cec5SDimitry Andric ++NumHeadBranchRejs; 5190b57cec5SDimitry Andric return false; 5200b57cec5SDimitry Andric } 5210b57cec5SDimitry Andric 5220b57cec5SDimitry Andric // Make sure the branch direction is right. 5230b57cec5SDimitry Andric if (TBB != CmpBB) { 5240b57cec5SDimitry Andric assert(TBB == Tail && "Unexpected TBB"); 5250b57cec5SDimitry Andric HeadCmpBBCC = AArch64CC::getInvertedCondCode(HeadCmpBBCC); 5260b57cec5SDimitry Andric } 5270b57cec5SDimitry Andric 5280b57cec5SDimitry Andric CmpBBCond.clear(); 5290b57cec5SDimitry Andric TBB = FBB = nullptr; 5300b57cec5SDimitry Andric if (TII->analyzeBranch(*CmpBB, TBB, FBB, CmpBBCond)) { 5310b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "CmpBB branch not analyzable.\n"); 5320b57cec5SDimitry Andric ++NumCmpBranchRejs; 5330b57cec5SDimitry Andric return false; 5340b57cec5SDimitry Andric } 5350b57cec5SDimitry Andric 5360b57cec5SDimitry Andric if (!TBB || CmpBBCond.empty()) { 5370b57cec5SDimitry Andric LLVM_DEBUG( 5385ffd83dbSDimitry Andric dbgs() << "analyzeBranch didn't find conditional branch in CmpBB.\n"); 5390b57cec5SDimitry Andric ++NumCmpBranchRejs; 5400b57cec5SDimitry Andric return false; 5410b57cec5SDimitry Andric } 5420b57cec5SDimitry Andric 5430b57cec5SDimitry Andric if (!parseCond(CmpBBCond, CmpBBTailCC)) { 5440b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Unsupported branch type on CmpBB\n"); 5450b57cec5SDimitry Andric ++NumCmpBranchRejs; 5460b57cec5SDimitry Andric return false; 5470b57cec5SDimitry Andric } 5480b57cec5SDimitry Andric 5490b57cec5SDimitry Andric if (TBB != Tail) 5500b57cec5SDimitry Andric CmpBBTailCC = AArch64CC::getInvertedCondCode(CmpBBTailCC); 5510b57cec5SDimitry Andric 5520b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Head->CmpBB on " 5530b57cec5SDimitry Andric << AArch64CC::getCondCodeName(HeadCmpBBCC) 5540b57cec5SDimitry Andric << ", CmpBB->Tail on " 5550b57cec5SDimitry Andric << AArch64CC::getCondCodeName(CmpBBTailCC) << '\n'); 5560b57cec5SDimitry Andric 5570b57cec5SDimitry Andric CmpMI = findConvertibleCompare(CmpBB); 5580b57cec5SDimitry Andric if (!CmpMI) 5590b57cec5SDimitry Andric return false; 5600b57cec5SDimitry Andric 5610b57cec5SDimitry Andric if (!canSpeculateInstrs(CmpBB, CmpMI)) { 5620b57cec5SDimitry Andric ++NumSpeculateRejs; 5630b57cec5SDimitry Andric return false; 5640b57cec5SDimitry Andric } 5650b57cec5SDimitry Andric return true; 5660b57cec5SDimitry Andric } 5670b57cec5SDimitry Andric 5680b57cec5SDimitry Andric void SSACCmpConv::convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks) { 5690b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Merging " << printMBBReference(*CmpBB) << " into " 5700b57cec5SDimitry Andric << printMBBReference(*Head) << ":\n" 5710b57cec5SDimitry Andric << *CmpBB); 5720b57cec5SDimitry Andric 5730b57cec5SDimitry Andric // All CmpBB instructions are moved into Head, and CmpBB is deleted. 5740b57cec5SDimitry Andric // Update the CFG first. 5750b57cec5SDimitry Andric updateTailPHIs(); 5760b57cec5SDimitry Andric 5770b57cec5SDimitry Andric // Save successor probabilties before removing CmpBB and Tail from their 5780b57cec5SDimitry Andric // parents. 5790b57cec5SDimitry Andric BranchProbability Head2CmpBB = MBPI->getEdgeProbability(Head, CmpBB); 5800b57cec5SDimitry Andric BranchProbability CmpBB2Tail = MBPI->getEdgeProbability(CmpBB, Tail); 5810b57cec5SDimitry Andric 5820b57cec5SDimitry Andric Head->removeSuccessor(CmpBB); 5830b57cec5SDimitry Andric CmpBB->removeSuccessor(Tail); 5840b57cec5SDimitry Andric 5850b57cec5SDimitry Andric // If Head and CmpBB had successor probabilties, udpate the probabilities to 5860b57cec5SDimitry Andric // reflect the ccmp-conversion. 5870b57cec5SDimitry Andric if (Head->hasSuccessorProbabilities() && CmpBB->hasSuccessorProbabilities()) { 5880b57cec5SDimitry Andric 5890b57cec5SDimitry Andric // Head is allowed two successors. We've removed CmpBB, so the remaining 5900b57cec5SDimitry Andric // successor is Tail. We need to increase the successor probability for 5910b57cec5SDimitry Andric // Tail to account for the CmpBB path we removed. 5920b57cec5SDimitry Andric // 5930b57cec5SDimitry Andric // Pr(Tail|Head) += Pr(CmpBB|Head) * Pr(Tail|CmpBB). 5940b57cec5SDimitry Andric assert(*Head->succ_begin() == Tail && "Head successor is not Tail"); 5950b57cec5SDimitry Andric BranchProbability Head2Tail = MBPI->getEdgeProbability(Head, Tail); 5960b57cec5SDimitry Andric Head->setSuccProbability(Head->succ_begin(), 5970b57cec5SDimitry Andric Head2Tail + Head2CmpBB * CmpBB2Tail); 5980b57cec5SDimitry Andric 5990b57cec5SDimitry Andric // We will transfer successors of CmpBB to Head in a moment without 6000b57cec5SDimitry Andric // normalizing the successor probabilities. Set the successor probabilites 6010b57cec5SDimitry Andric // before doing so. 6020b57cec5SDimitry Andric // 6030b57cec5SDimitry Andric // Pr(I|Head) = Pr(CmpBB|Head) * Pr(I|CmpBB). 6040b57cec5SDimitry Andric for (auto I = CmpBB->succ_begin(), E = CmpBB->succ_end(); I != E; ++I) { 6050b57cec5SDimitry Andric BranchProbability CmpBB2I = MBPI->getEdgeProbability(CmpBB, *I); 6060b57cec5SDimitry Andric CmpBB->setSuccProbability(I, Head2CmpBB * CmpBB2I); 6070b57cec5SDimitry Andric } 6080b57cec5SDimitry Andric } 6090b57cec5SDimitry Andric 6100b57cec5SDimitry Andric Head->transferSuccessorsAndUpdatePHIs(CmpBB); 6110b57cec5SDimitry Andric DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc(); 6120b57cec5SDimitry Andric TII->removeBranch(*Head); 6130b57cec5SDimitry Andric 6140b57cec5SDimitry Andric // If the Head terminator was one of the cbz / tbz branches with built-in 6150b57cec5SDimitry Andric // compare, we need to insert an explicit compare instruction in its place. 6160b57cec5SDimitry Andric if (HeadCond[0].getImm() == -1) { 6170b57cec5SDimitry Andric ++NumCompBranches; 6180b57cec5SDimitry Andric unsigned Opc = 0; 6190b57cec5SDimitry Andric switch (HeadCond[1].getImm()) { 6200b57cec5SDimitry Andric case AArch64::CBZW: 6210b57cec5SDimitry Andric case AArch64::CBNZW: 6220b57cec5SDimitry Andric Opc = AArch64::SUBSWri; 6230b57cec5SDimitry Andric break; 6240b57cec5SDimitry Andric case AArch64::CBZX: 6250b57cec5SDimitry Andric case AArch64::CBNZX: 6260b57cec5SDimitry Andric Opc = AArch64::SUBSXri; 6270b57cec5SDimitry Andric break; 6280b57cec5SDimitry Andric default: 6290b57cec5SDimitry Andric llvm_unreachable("Cannot convert Head branch"); 6300b57cec5SDimitry Andric } 6310b57cec5SDimitry Andric const MCInstrDesc &MCID = TII->get(Opc); 6320b57cec5SDimitry Andric // Create a dummy virtual register for the SUBS def. 6338bcb0991SDimitry Andric Register DestReg = 6340b57cec5SDimitry Andric MRI->createVirtualRegister(TII->getRegClass(MCID, 0, TRI, *MF)); 6350b57cec5SDimitry Andric // Insert a SUBS Rn, #0 instruction instead of the cbz / cbnz. 6360b57cec5SDimitry Andric BuildMI(*Head, Head->end(), TermDL, MCID) 6370b57cec5SDimitry Andric .addReg(DestReg, RegState::Define | RegState::Dead) 6380b57cec5SDimitry Andric .add(HeadCond[2]) 6390b57cec5SDimitry Andric .addImm(0) 6400b57cec5SDimitry Andric .addImm(0); 6410b57cec5SDimitry Andric // SUBS uses the GPR*sp register classes. 6420b57cec5SDimitry Andric MRI->constrainRegClass(HeadCond[2].getReg(), 6430b57cec5SDimitry Andric TII->getRegClass(MCID, 1, TRI, *MF)); 6440b57cec5SDimitry Andric } 6450b57cec5SDimitry Andric 6460b57cec5SDimitry Andric Head->splice(Head->end(), CmpBB, CmpBB->begin(), CmpBB->end()); 6470b57cec5SDimitry Andric 6480b57cec5SDimitry Andric // Now replace CmpMI with a ccmp instruction that also considers the incoming 6490b57cec5SDimitry Andric // flags. 6500b57cec5SDimitry Andric unsigned Opc = 0; 6510b57cec5SDimitry Andric unsigned FirstOp = 1; // First CmpMI operand to copy. 6520b57cec5SDimitry Andric bool isZBranch = false; // CmpMI is a cbz/cbnz instruction. 6530b57cec5SDimitry Andric switch (CmpMI->getOpcode()) { 6540b57cec5SDimitry Andric default: 6550b57cec5SDimitry Andric llvm_unreachable("Unknown compare opcode"); 6560b57cec5SDimitry Andric case AArch64::SUBSWri: Opc = AArch64::CCMPWi; break; 6570b57cec5SDimitry Andric case AArch64::SUBSWrr: Opc = AArch64::CCMPWr; break; 6580b57cec5SDimitry Andric case AArch64::SUBSXri: Opc = AArch64::CCMPXi; break; 6590b57cec5SDimitry Andric case AArch64::SUBSXrr: Opc = AArch64::CCMPXr; break; 6600b57cec5SDimitry Andric case AArch64::ADDSWri: Opc = AArch64::CCMNWi; break; 6610b57cec5SDimitry Andric case AArch64::ADDSWrr: Opc = AArch64::CCMNWr; break; 6620b57cec5SDimitry Andric case AArch64::ADDSXri: Opc = AArch64::CCMNXi; break; 6630b57cec5SDimitry Andric case AArch64::ADDSXrr: Opc = AArch64::CCMNXr; break; 6640b57cec5SDimitry Andric case AArch64::FCMPSrr: Opc = AArch64::FCCMPSrr; FirstOp = 0; break; 6650b57cec5SDimitry Andric case AArch64::FCMPDrr: Opc = AArch64::FCCMPDrr; FirstOp = 0; break; 6660b57cec5SDimitry Andric case AArch64::FCMPESrr: Opc = AArch64::FCCMPESrr; FirstOp = 0; break; 6670b57cec5SDimitry Andric case AArch64::FCMPEDrr: Opc = AArch64::FCCMPEDrr; FirstOp = 0; break; 6680b57cec5SDimitry Andric case AArch64::CBZW: 6690b57cec5SDimitry Andric case AArch64::CBNZW: 6700b57cec5SDimitry Andric Opc = AArch64::CCMPWi; 6710b57cec5SDimitry Andric FirstOp = 0; 6720b57cec5SDimitry Andric isZBranch = true; 6730b57cec5SDimitry Andric break; 6740b57cec5SDimitry Andric case AArch64::CBZX: 6750b57cec5SDimitry Andric case AArch64::CBNZX: 6760b57cec5SDimitry Andric Opc = AArch64::CCMPXi; 6770b57cec5SDimitry Andric FirstOp = 0; 6780b57cec5SDimitry Andric isZBranch = true; 6790b57cec5SDimitry Andric break; 6800b57cec5SDimitry Andric } 6810b57cec5SDimitry Andric 6820b57cec5SDimitry Andric // The ccmp instruction should set the flags according to the comparison when 6830b57cec5SDimitry Andric // Head would have branched to CmpBB. 6840b57cec5SDimitry Andric // The NZCV immediate operand should provide flags for the case where Head 6850b57cec5SDimitry Andric // would have branched to Tail. These flags should cause the new Head 6860b57cec5SDimitry Andric // terminator to branch to tail. 6870b57cec5SDimitry Andric unsigned NZCV = AArch64CC::getNZCVToSatisfyCondCode(CmpBBTailCC); 6880b57cec5SDimitry Andric const MCInstrDesc &MCID = TII->get(Opc); 6890b57cec5SDimitry Andric MRI->constrainRegClass(CmpMI->getOperand(FirstOp).getReg(), 6900b57cec5SDimitry Andric TII->getRegClass(MCID, 0, TRI, *MF)); 6910b57cec5SDimitry Andric if (CmpMI->getOperand(FirstOp + 1).isReg()) 6920b57cec5SDimitry Andric MRI->constrainRegClass(CmpMI->getOperand(FirstOp + 1).getReg(), 6930b57cec5SDimitry Andric TII->getRegClass(MCID, 1, TRI, *MF)); 6940b57cec5SDimitry Andric MachineInstrBuilder MIB = BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), MCID) 6950b57cec5SDimitry Andric .add(CmpMI->getOperand(FirstOp)); // Register Rn 6960b57cec5SDimitry Andric if (isZBranch) 6970b57cec5SDimitry Andric MIB.addImm(0); // cbz/cbnz Rn -> ccmp Rn, #0 6980b57cec5SDimitry Andric else 6990b57cec5SDimitry Andric MIB.add(CmpMI->getOperand(FirstOp + 1)); // Register Rm / Immediate 7000b57cec5SDimitry Andric MIB.addImm(NZCV).addImm(HeadCmpBBCC); 7010b57cec5SDimitry Andric 7020b57cec5SDimitry Andric // If CmpMI was a terminator, we need a new conditional branch to replace it. 7030b57cec5SDimitry Andric // This now becomes a Head terminator. 7040b57cec5SDimitry Andric if (isZBranch) { 7050b57cec5SDimitry Andric bool isNZ = CmpMI->getOpcode() == AArch64::CBNZW || 7060b57cec5SDimitry Andric CmpMI->getOpcode() == AArch64::CBNZX; 7070b57cec5SDimitry Andric BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), TII->get(AArch64::Bcc)) 7080b57cec5SDimitry Andric .addImm(isNZ ? AArch64CC::NE : AArch64CC::EQ) 7090b57cec5SDimitry Andric .add(CmpMI->getOperand(1)); // Branch target. 7100b57cec5SDimitry Andric } 7110b57cec5SDimitry Andric CmpMI->eraseFromParent(); 7125ffd83dbSDimitry Andric Head->updateTerminator(CmpBB->getNextNode()); 7130b57cec5SDimitry Andric 7140b57cec5SDimitry Andric RemovedBlocks.push_back(CmpBB); 7150b57cec5SDimitry Andric CmpBB->eraseFromParent(); 7160b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Result:\n" << *Head); 7170b57cec5SDimitry Andric ++NumConverted; 7180b57cec5SDimitry Andric } 7190b57cec5SDimitry Andric 7200b57cec5SDimitry Andric int SSACCmpConv::expectedCodeSizeDelta() const { 7210b57cec5SDimitry Andric int delta = 0; 7220b57cec5SDimitry Andric // If the Head terminator was one of the cbz / tbz branches with built-in 7230b57cec5SDimitry Andric // compare, we need to insert an explicit compare instruction in its place 7240b57cec5SDimitry Andric // plus a branch instruction. 7250b57cec5SDimitry Andric if (HeadCond[0].getImm() == -1) { 7260b57cec5SDimitry Andric switch (HeadCond[1].getImm()) { 7270b57cec5SDimitry Andric case AArch64::CBZW: 7280b57cec5SDimitry Andric case AArch64::CBNZW: 7290b57cec5SDimitry Andric case AArch64::CBZX: 7300b57cec5SDimitry Andric case AArch64::CBNZX: 7310b57cec5SDimitry Andric // Therefore delta += 1 7320b57cec5SDimitry Andric delta = 1; 7330b57cec5SDimitry Andric break; 7340b57cec5SDimitry Andric default: 7350b57cec5SDimitry Andric llvm_unreachable("Cannot convert Head branch"); 7360b57cec5SDimitry Andric } 7370b57cec5SDimitry Andric } 7380b57cec5SDimitry Andric // If the Cmp terminator was one of the cbz / tbz branches with 7390b57cec5SDimitry Andric // built-in compare, it will be turned into a compare instruction 7400b57cec5SDimitry Andric // into Head, but we do not save any instruction. 7410b57cec5SDimitry Andric // Otherwise, we save the branch instruction. 7420b57cec5SDimitry Andric switch (CmpMI->getOpcode()) { 7430b57cec5SDimitry Andric default: 7440b57cec5SDimitry Andric --delta; 7450b57cec5SDimitry Andric break; 7460b57cec5SDimitry Andric case AArch64::CBZW: 7470b57cec5SDimitry Andric case AArch64::CBNZW: 7480b57cec5SDimitry Andric case AArch64::CBZX: 7490b57cec5SDimitry Andric case AArch64::CBNZX: 7500b57cec5SDimitry Andric break; 7510b57cec5SDimitry Andric } 7520b57cec5SDimitry Andric return delta; 7530b57cec5SDimitry Andric } 7540b57cec5SDimitry Andric 7550b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 7560b57cec5SDimitry Andric // AArch64ConditionalCompares Pass 7570b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 7580b57cec5SDimitry Andric 7590b57cec5SDimitry Andric namespace { 7600b57cec5SDimitry Andric class AArch64ConditionalCompares : public MachineFunctionPass { 7610b57cec5SDimitry Andric const MachineBranchProbabilityInfo *MBPI; 7620b57cec5SDimitry Andric const TargetInstrInfo *TII; 7630b57cec5SDimitry Andric const TargetRegisterInfo *TRI; 7640b57cec5SDimitry Andric MCSchedModel SchedModel; 7650b57cec5SDimitry Andric // Does the proceeded function has Oz attribute. 7660b57cec5SDimitry Andric bool MinSize; 7670b57cec5SDimitry Andric MachineRegisterInfo *MRI; 7680b57cec5SDimitry Andric MachineDominatorTree *DomTree; 7690b57cec5SDimitry Andric MachineLoopInfo *Loops; 7700b57cec5SDimitry Andric MachineTraceMetrics *Traces; 7710b57cec5SDimitry Andric MachineTraceMetrics::Ensemble *MinInstr; 7720b57cec5SDimitry Andric SSACCmpConv CmpConv; 7730b57cec5SDimitry Andric 7740b57cec5SDimitry Andric public: 7750b57cec5SDimitry Andric static char ID; 7760b57cec5SDimitry Andric AArch64ConditionalCompares() : MachineFunctionPass(ID) { 7770b57cec5SDimitry Andric initializeAArch64ConditionalComparesPass(*PassRegistry::getPassRegistry()); 7780b57cec5SDimitry Andric } 7790b57cec5SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override; 7800b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 7810b57cec5SDimitry Andric StringRef getPassName() const override { 7820b57cec5SDimitry Andric return "AArch64 Conditional Compares"; 7830b57cec5SDimitry Andric } 7840b57cec5SDimitry Andric 7850b57cec5SDimitry Andric private: 7860b57cec5SDimitry Andric bool tryConvert(MachineBasicBlock *); 7870b57cec5SDimitry Andric void updateDomTree(ArrayRef<MachineBasicBlock *> Removed); 7880b57cec5SDimitry Andric void updateLoops(ArrayRef<MachineBasicBlock *> Removed); 7890b57cec5SDimitry Andric void invalidateTraces(); 7900b57cec5SDimitry Andric bool shouldConvert(); 7910b57cec5SDimitry Andric }; 7920b57cec5SDimitry Andric } // end anonymous namespace 7930b57cec5SDimitry Andric 7940b57cec5SDimitry Andric char AArch64ConditionalCompares::ID = 0; 7950b57cec5SDimitry Andric 7960b57cec5SDimitry Andric INITIALIZE_PASS_BEGIN(AArch64ConditionalCompares, "aarch64-ccmp", 7970b57cec5SDimitry Andric "AArch64 CCMP Pass", false, false) 7980b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 7990b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 8000b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics) 8010b57cec5SDimitry Andric INITIALIZE_PASS_END(AArch64ConditionalCompares, "aarch64-ccmp", 8020b57cec5SDimitry Andric "AArch64 CCMP Pass", false, false) 8030b57cec5SDimitry Andric 8040b57cec5SDimitry Andric FunctionPass *llvm::createAArch64ConditionalCompares() { 8050b57cec5SDimitry Andric return new AArch64ConditionalCompares(); 8060b57cec5SDimitry Andric } 8070b57cec5SDimitry Andric 8080b57cec5SDimitry Andric void AArch64ConditionalCompares::getAnalysisUsage(AnalysisUsage &AU) const { 8090b57cec5SDimitry Andric AU.addRequired<MachineBranchProbabilityInfo>(); 8100b57cec5SDimitry Andric AU.addRequired<MachineDominatorTree>(); 8110b57cec5SDimitry Andric AU.addPreserved<MachineDominatorTree>(); 8120b57cec5SDimitry Andric AU.addRequired<MachineLoopInfo>(); 8130b57cec5SDimitry Andric AU.addPreserved<MachineLoopInfo>(); 8140b57cec5SDimitry Andric AU.addRequired<MachineTraceMetrics>(); 8150b57cec5SDimitry Andric AU.addPreserved<MachineTraceMetrics>(); 8160b57cec5SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 8170b57cec5SDimitry Andric } 8180b57cec5SDimitry Andric 8190b57cec5SDimitry Andric /// Update the dominator tree after if-conversion erased some blocks. 8200b57cec5SDimitry Andric void AArch64ConditionalCompares::updateDomTree( 8210b57cec5SDimitry Andric ArrayRef<MachineBasicBlock *> Removed) { 8220b57cec5SDimitry Andric // convert() removes CmpBB which was previously dominated by Head. 8230b57cec5SDimitry Andric // CmpBB children should be transferred to Head. 8240b57cec5SDimitry Andric MachineDomTreeNode *HeadNode = DomTree->getNode(CmpConv.Head); 8250b57cec5SDimitry Andric for (MachineBasicBlock *RemovedMBB : Removed) { 8260b57cec5SDimitry Andric MachineDomTreeNode *Node = DomTree->getNode(RemovedMBB); 8270b57cec5SDimitry Andric assert(Node != HeadNode && "Cannot erase the head node"); 8280b57cec5SDimitry Andric assert(Node->getIDom() == HeadNode && "CmpBB should be dominated by Head"); 8290b57cec5SDimitry Andric while (Node->getNumChildren()) 8305ffd83dbSDimitry Andric DomTree->changeImmediateDominator(Node->back(), HeadNode); 8310b57cec5SDimitry Andric DomTree->eraseNode(RemovedMBB); 8320b57cec5SDimitry Andric } 8330b57cec5SDimitry Andric } 8340b57cec5SDimitry Andric 8350b57cec5SDimitry Andric /// Update LoopInfo after if-conversion. 8360b57cec5SDimitry Andric void 8370b57cec5SDimitry Andric AArch64ConditionalCompares::updateLoops(ArrayRef<MachineBasicBlock *> Removed) { 8380b57cec5SDimitry Andric if (!Loops) 8390b57cec5SDimitry Andric return; 8400b57cec5SDimitry Andric for (MachineBasicBlock *RemovedMBB : Removed) 8410b57cec5SDimitry Andric Loops->removeBlock(RemovedMBB); 8420b57cec5SDimitry Andric } 8430b57cec5SDimitry Andric 8440b57cec5SDimitry Andric /// Invalidate MachineTraceMetrics before if-conversion. 8450b57cec5SDimitry Andric void AArch64ConditionalCompares::invalidateTraces() { 8460b57cec5SDimitry Andric Traces->invalidate(CmpConv.Head); 8470b57cec5SDimitry Andric Traces->invalidate(CmpConv.CmpBB); 8480b57cec5SDimitry Andric } 8490b57cec5SDimitry Andric 8500b57cec5SDimitry Andric /// Apply cost model and heuristics to the if-conversion in IfConv. 8510b57cec5SDimitry Andric /// Return true if the conversion is a good idea. 8520b57cec5SDimitry Andric /// 8530b57cec5SDimitry Andric bool AArch64ConditionalCompares::shouldConvert() { 8540b57cec5SDimitry Andric // Stress testing mode disables all cost considerations. 8550b57cec5SDimitry Andric if (Stress) 8560b57cec5SDimitry Andric return true; 8570b57cec5SDimitry Andric if (!MinInstr) 85806c3fb27SDimitry Andric MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount); 8590b57cec5SDimitry Andric 8600b57cec5SDimitry Andric // Head dominates CmpBB, so it is always included in its trace. 8610b57cec5SDimitry Andric MachineTraceMetrics::Trace Trace = MinInstr->getTrace(CmpConv.CmpBB); 8620b57cec5SDimitry Andric 8630b57cec5SDimitry Andric // If code size is the main concern 8640b57cec5SDimitry Andric if (MinSize) { 8650b57cec5SDimitry Andric int CodeSizeDelta = CmpConv.expectedCodeSizeDelta(); 8660b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Code size delta: " << CodeSizeDelta << '\n'); 8670b57cec5SDimitry Andric // If we are minimizing the code size, do the conversion whatever 8680b57cec5SDimitry Andric // the cost is. 8690b57cec5SDimitry Andric if (CodeSizeDelta < 0) 8700b57cec5SDimitry Andric return true; 8710b57cec5SDimitry Andric if (CodeSizeDelta > 0) { 8720b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Code size is increasing, give up on this one.\n"); 8730b57cec5SDimitry Andric return false; 8740b57cec5SDimitry Andric } 8750b57cec5SDimitry Andric // CodeSizeDelta == 0, continue with the regular heuristics 8760b57cec5SDimitry Andric } 8770b57cec5SDimitry Andric 8780b57cec5SDimitry Andric // Heuristic: The compare conversion delays the execution of the branch 8790b57cec5SDimitry Andric // instruction because we must wait for the inputs to the second compare as 8800b57cec5SDimitry Andric // well. The branch has no dependent instructions, but delaying it increases 8810b57cec5SDimitry Andric // the cost of a misprediction. 8820b57cec5SDimitry Andric // 8830b57cec5SDimitry Andric // Set a limit on the delay we will accept. 8840b57cec5SDimitry Andric unsigned DelayLimit = SchedModel.MispredictPenalty * 3 / 4; 8850b57cec5SDimitry Andric 8860b57cec5SDimitry Andric // Instruction depths can be computed for all trace instructions above CmpBB. 8870b57cec5SDimitry Andric unsigned HeadDepth = 8880b57cec5SDimitry Andric Trace.getInstrCycles(*CmpConv.Head->getFirstTerminator()).Depth; 8890b57cec5SDimitry Andric unsigned CmpBBDepth = 8900b57cec5SDimitry Andric Trace.getInstrCycles(*CmpConv.CmpBB->getFirstTerminator()).Depth; 8910b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Head depth: " << HeadDepth 8920b57cec5SDimitry Andric << "\nCmpBB depth: " << CmpBBDepth << '\n'); 8930b57cec5SDimitry Andric if (CmpBBDepth > HeadDepth + DelayLimit) { 8940b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Branch delay would be larger than " << DelayLimit 8950b57cec5SDimitry Andric << " cycles.\n"); 8960b57cec5SDimitry Andric return false; 8970b57cec5SDimitry Andric } 8980b57cec5SDimitry Andric 8990b57cec5SDimitry Andric // Check the resource depth at the bottom of CmpBB - these instructions will 9000b57cec5SDimitry Andric // be speculated. 9010b57cec5SDimitry Andric unsigned ResDepth = Trace.getResourceDepth(true); 9020b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Resources: " << ResDepth << '\n'); 9030b57cec5SDimitry Andric 9040b57cec5SDimitry Andric // Heuristic: The speculatively executed instructions must all be able to 9050b57cec5SDimitry Andric // merge into the Head block. The Head critical path should dominate the 9060b57cec5SDimitry Andric // resource cost of the speculated instructions. 9070b57cec5SDimitry Andric if (ResDepth > HeadDepth) { 9080b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Too many instructions to speculate.\n"); 9090b57cec5SDimitry Andric return false; 9100b57cec5SDimitry Andric } 9110b57cec5SDimitry Andric return true; 9120b57cec5SDimitry Andric } 9130b57cec5SDimitry Andric 9140b57cec5SDimitry Andric bool AArch64ConditionalCompares::tryConvert(MachineBasicBlock *MBB) { 9150b57cec5SDimitry Andric bool Changed = false; 9160b57cec5SDimitry Andric while (CmpConv.canConvert(MBB) && shouldConvert()) { 9170b57cec5SDimitry Andric invalidateTraces(); 9180b57cec5SDimitry Andric SmallVector<MachineBasicBlock *, 4> RemovedBlocks; 9190b57cec5SDimitry Andric CmpConv.convert(RemovedBlocks); 9200b57cec5SDimitry Andric Changed = true; 9210b57cec5SDimitry Andric updateDomTree(RemovedBlocks); 9220b57cec5SDimitry Andric updateLoops(RemovedBlocks); 9230b57cec5SDimitry Andric } 9240b57cec5SDimitry Andric return Changed; 9250b57cec5SDimitry Andric } 9260b57cec5SDimitry Andric 9270b57cec5SDimitry Andric bool AArch64ConditionalCompares::runOnMachineFunction(MachineFunction &MF) { 9280b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n" 9290b57cec5SDimitry Andric << "********** Function: " << MF.getName() << '\n'); 9300b57cec5SDimitry Andric if (skipFunction(MF.getFunction())) 9310b57cec5SDimitry Andric return false; 9320b57cec5SDimitry Andric 9330b57cec5SDimitry Andric TII = MF.getSubtarget().getInstrInfo(); 9340b57cec5SDimitry Andric TRI = MF.getSubtarget().getRegisterInfo(); 9350b57cec5SDimitry Andric SchedModel = MF.getSubtarget().getSchedModel(); 9360b57cec5SDimitry Andric MRI = &MF.getRegInfo(); 9370b57cec5SDimitry Andric DomTree = &getAnalysis<MachineDominatorTree>(); 9380b57cec5SDimitry Andric Loops = getAnalysisIfAvailable<MachineLoopInfo>(); 9390b57cec5SDimitry Andric MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 9400b57cec5SDimitry Andric Traces = &getAnalysis<MachineTraceMetrics>(); 9410b57cec5SDimitry Andric MinInstr = nullptr; 9420b57cec5SDimitry Andric MinSize = MF.getFunction().hasMinSize(); 9430b57cec5SDimitry Andric 9440b57cec5SDimitry Andric bool Changed = false; 9450b57cec5SDimitry Andric CmpConv.runOnMachineFunction(MF, MBPI); 9460b57cec5SDimitry Andric 9470b57cec5SDimitry Andric // Visit blocks in dominator tree pre-order. The pre-order enables multiple 9480b57cec5SDimitry Andric // cmp-conversions from the same head block. 9490b57cec5SDimitry Andric // Note that updateDomTree() modifies the children of the DomTree node 9500b57cec5SDimitry Andric // currently being visited. The df_iterator supports that; it doesn't look at 9510b57cec5SDimitry Andric // child_begin() / child_end() until after a node has been visited. 9520b57cec5SDimitry Andric for (auto *I : depth_first(DomTree)) 9530b57cec5SDimitry Andric if (tryConvert(I->getBlock())) 9540b57cec5SDimitry Andric Changed = true; 9550b57cec5SDimitry Andric 9560b57cec5SDimitry Andric return Changed; 9570b57cec5SDimitry Andric } 958