| //===-- AArch64ConditionalCompares.cpp --- CCMP formation for AArch64 -----===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the AArch64ConditionalCompares pass which reduces |
| // branching and code size by using the conditional compare instructions CCMP, |
| // CCMN, and FCMP. |
| // |
| // The CFG transformations for forming conditional compares are very similar to |
| // if-conversion, and this pass should run immediately before the early |
| // if-conversion pass. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "AArch64.h" |
| #include "llvm/ADT/DepthFirstIterator.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" |
| #include "llvm/CodeGen/MachineDominators.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/MachineLoopInfo.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include "llvm/CodeGen/MachineTraceMetrics.h" |
| #include "llvm/CodeGen/Passes.h" |
| #include "llvm/CodeGen/TargetInstrInfo.h" |
| #include "llvm/CodeGen/TargetRegisterInfo.h" |
| #include "llvm/CodeGen/TargetSubtargetInfo.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "aarch64-ccmp" |
| |
| // Absolute maximum number of instructions allowed per speculated block. |
| // This bypasses all other heuristics, so it should be set fairly high. |
| static cl::opt<unsigned> BlockInstrLimit( |
| "aarch64-ccmp-limit", cl::init(30), cl::Hidden, |
| cl::desc("Maximum number of instructions per speculated block.")); |
| |
| // Stress testing mode - disable heuristics. |
| static cl::opt<bool> Stress("aarch64-stress-ccmp", cl::Hidden, |
| cl::desc("Turn all knobs to 11")); |
| |
| STATISTIC(NumConsidered, "Number of ccmps considered"); |
| STATISTIC(NumPhiRejs, "Number of ccmps rejected (PHI)"); |
| STATISTIC(NumPhysRejs, "Number of ccmps rejected (Physregs)"); |
| STATISTIC(NumPhi2Rejs, "Number of ccmps rejected (PHI2)"); |
| STATISTIC(NumHeadBranchRejs, "Number of ccmps rejected (Head branch)"); |
| STATISTIC(NumCmpBranchRejs, "Number of ccmps rejected (CmpBB branch)"); |
| STATISTIC(NumCmpTermRejs, "Number of ccmps rejected (CmpBB is cbz...)"); |
| STATISTIC(NumImmRangeRejs, "Number of ccmps rejected (Imm out of range)"); |
| STATISTIC(NumLiveDstRejs, "Number of ccmps rejected (Cmp dest live)"); |
| STATISTIC(NumMultNZCVUses, "Number of ccmps rejected (NZCV used)"); |
| STATISTIC(NumUnknNZCVDefs, "Number of ccmps rejected (NZCV def unknown)"); |
| |
| STATISTIC(NumSpeculateRejs, "Number of ccmps rejected (Can't speculate)"); |
| |
| STATISTIC(NumConverted, "Number of ccmp instructions created"); |
| STATISTIC(NumCompBranches, "Number of cbz/cbnz branches converted"); |
| |
| //===----------------------------------------------------------------------===// |
| // SSACCmpConv |
| //===----------------------------------------------------------------------===// |
| // |
| // The SSACCmpConv class performs ccmp-conversion on SSA form machine code |
| // after determining if it is possible. The class contains no heuristics; |
| // external code should be used to determine when ccmp-conversion is a good |
| // idea. |
| // |
| // CCmp-formation works on a CFG representing chained conditions, typically |
| // from C's short-circuit || and && operators: |
| // |
| // From: Head To: Head |
| // / | CmpBB |
| // / | / | |
| // | CmpBB / | |
| // | / | Tail | |
| // | / | | | |
| // Tail | | | |
| // | | | | |
| // ... ... ... ... |
| // |
| // The Head block is terminated by a br.cond instruction, and the CmpBB block |
| // contains compare + br.cond. Tail must be a successor of both. |
| // |
| // The cmp-conversion turns the compare instruction in CmpBB into a conditional |
| // compare, and merges CmpBB into Head, speculatively executing its |
| // instructions. The AArch64 conditional compare instructions have an immediate |
| // operand that specifies the NZCV flag values when the condition is false and |
| // the compare isn't executed. This makes it possible to chain compares with |
| // different condition codes. |
| // |
| // Example: |
| // |
| // if (a == 5 || b == 17) |
| // foo(); |
| // |
| // Head: |
| // cmp w0, #5 |
| // b.eq Tail |
| // CmpBB: |
| // cmp w1, #17 |
| // b.eq Tail |
| // ... |
| // Tail: |
| // bl _foo |
| // |
| // Becomes: |
| // |
| // Head: |
| // cmp w0, #5 |
| // ccmp w1, #17, 4, ne ; 4 = nZcv |
| // b.eq Tail |
| // ... |
| // Tail: |
| // bl _foo |
| // |
| // The ccmp condition code is the one that would cause the Head terminator to |
| // branch to CmpBB. |
| // |
| // FIXME: It should also be possible to speculate a block on the critical edge |
| // between Head and Tail, just like if-converting a diamond. |
| // |
| // FIXME: Handle PHIs in Tail by turning them into selects (if-conversion). |
| |
| namespace { |
| class SSACCmpConv { |
| MachineFunction *MF; |
| const TargetInstrInfo *TII; |
| const TargetRegisterInfo *TRI; |
| MachineRegisterInfo *MRI; |
| const MachineBranchProbabilityInfo *MBPI; |
| |
| public: |
| /// The first block containing a conditional branch, dominating everything |
| /// else. |
| MachineBasicBlock *Head; |
| |
| /// The block containing cmp+br.cond with a successor shared with Head. |
| MachineBasicBlock *CmpBB; |
| |
| /// The common successor for Head and CmpBB. |
| MachineBasicBlock *Tail; |
| |
| /// The compare instruction in CmpBB that can be converted to a ccmp. |
| MachineInstr *CmpMI; |
| |
| private: |
| /// The branch condition in Head as determined by analyzeBranch. |
| SmallVector<MachineOperand, 4> HeadCond; |
| |
| /// The condition code that makes Head branch to CmpBB. |
| AArch64CC::CondCode HeadCmpBBCC; |
| |
| /// The branch condition in CmpBB. |
| SmallVector<MachineOperand, 4> CmpBBCond; |
| |
| /// The condition code that makes CmpBB branch to Tail. |
| AArch64CC::CondCode CmpBBTailCC; |
| |
| /// Check if the Tail PHIs are trivially convertible. |
| bool trivialTailPHIs(); |
| |
| /// Remove CmpBB from the Tail PHIs. |
| void updateTailPHIs(); |
| |
| /// Check if an operand defining DstReg is dead. |
| bool isDeadDef(unsigned DstReg); |
| |
| /// Find the compare instruction in MBB that controls the conditional branch. |
| /// Return NULL if a convertible instruction can't be found. |
| MachineInstr *findConvertibleCompare(MachineBasicBlock *MBB); |
| |
| /// Return true if all non-terminator instructions in MBB can be safely |
| /// speculated. |
| bool canSpeculateInstrs(MachineBasicBlock *MBB, const MachineInstr *CmpMI); |
| |
| public: |
| /// runOnMachineFunction - Initialize per-function data structures. |
| void runOnMachineFunction(MachineFunction &MF, |
| const MachineBranchProbabilityInfo *MBPI) { |
| this->MF = &MF; |
| this->MBPI = MBPI; |
| TII = MF.getSubtarget().getInstrInfo(); |
| TRI = MF.getSubtarget().getRegisterInfo(); |
| MRI = &MF.getRegInfo(); |
| } |
| |
| /// If the sub-CFG headed by MBB can be cmp-converted, initialize the |
| /// internal state, and return true. |
| bool canConvert(MachineBasicBlock *MBB); |
| |
| /// Cmo-convert the last block passed to canConvertCmp(), assuming |
| /// it is possible. Add any erased blocks to RemovedBlocks. |
| void convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks); |
| |
| /// Return the expected code size delta if the conversion into a |
| /// conditional compare is performed. |
| int expectedCodeSizeDelta() const; |
| }; |
| } // end anonymous namespace |
| |
| // Check that all PHIs in Tail are selecting the same value from Head and CmpBB. |
| // This means that no if-conversion is required when merging CmpBB into Head. |
| bool SSACCmpConv::trivialTailPHIs() { |
| for (auto &I : *Tail) { |
| if (!I.isPHI()) |
| break; |
| unsigned HeadReg = 0, CmpBBReg = 0; |
| // PHI operands come in (VReg, MBB) pairs. |
| for (unsigned oi = 1, oe = I.getNumOperands(); oi != oe; oi += 2) { |
| MachineBasicBlock *MBB = I.getOperand(oi + 1).getMBB(); |
| Register Reg = I.getOperand(oi).getReg(); |
| if (MBB == Head) { |
| assert((!HeadReg || HeadReg == Reg) && "Inconsistent PHI operands"); |
| HeadReg = Reg; |
| } |
| if (MBB == CmpBB) { |
| assert((!CmpBBReg || CmpBBReg == Reg) && "Inconsistent PHI operands"); |
| CmpBBReg = Reg; |
| } |
| } |
| if (HeadReg != CmpBBReg) |
| return false; |
| } |
| return true; |
| } |
| |
| // Assuming that trivialTailPHIs() is true, update the Tail PHIs by simply |
| // removing the CmpBB operands. The Head operands will be identical. |
| void SSACCmpConv::updateTailPHIs() { |
| for (auto &I : *Tail) { |
| if (!I.isPHI()) |
| break; |
| // I is a PHI. It can have multiple entries for CmpBB. |
| for (unsigned oi = I.getNumOperands(); oi > 2; oi -= 2) { |
| // PHI operands are (Reg, MBB) at (oi-2, oi-1). |
| if (I.getOperand(oi - 1).getMBB() == CmpBB) { |
| I.RemoveOperand(oi - 1); |
| I.RemoveOperand(oi - 2); |
| } |
| } |
| } |
| } |
| |
| // This pass runs before the AArch64DeadRegisterDefinitions pass, so compares |
| // are still writing virtual registers without any uses. |
| bool SSACCmpConv::isDeadDef(unsigned DstReg) { |
| // Writes to the zero register are dead. |
| if (DstReg == AArch64::WZR || DstReg == AArch64::XZR) |
| return true; |
| if (!Register::isVirtualRegister(DstReg)) |
| return false; |
| // A virtual register def without any uses will be marked dead later, and |
| // eventually replaced by the zero register. |
| return MRI->use_nodbg_empty(DstReg); |
| } |
| |
| // Parse a condition code returned by analyzeBranch, and compute the CondCode |
| // corresponding to TBB. |
| // Return |
| static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) { |
| // A normal br.cond simply has the condition code. |
| if (Cond[0].getImm() != -1) { |
| assert(Cond.size() == 1 && "Unknown Cond array format"); |
| CC = (AArch64CC::CondCode)(int)Cond[0].getImm(); |
| return true; |
| } |
| // For tbz and cbz instruction, the opcode is next. |
| switch (Cond[1].getImm()) { |
| default: |
| // This includes tbz / tbnz branches which can't be converted to |
| // ccmp + br.cond. |
| return false; |
| case AArch64::CBZW: |
| case AArch64::CBZX: |
| assert(Cond.size() == 3 && "Unknown Cond array format"); |
| CC = AArch64CC::EQ; |
| return true; |
| case AArch64::CBNZW: |
| case AArch64::CBNZX: |
| assert(Cond.size() == 3 && "Unknown Cond array format"); |
| CC = AArch64CC::NE; |
| return true; |
| } |
| } |
| |
| MachineInstr *SSACCmpConv::findConvertibleCompare(MachineBasicBlock *MBB) { |
| MachineBasicBlock::iterator I = MBB->getFirstTerminator(); |
| if (I == MBB->end()) |
| return nullptr; |
| // The terminator must be controlled by the flags. |
| if (!I->readsRegister(AArch64::NZCV)) { |
| switch (I->getOpcode()) { |
| case AArch64::CBZW: |
| case AArch64::CBZX: |
| case AArch64::CBNZW: |
| case AArch64::CBNZX: |
| // These can be converted into a ccmp against #0. |
| return &*I; |
| } |
| ++NumCmpTermRejs; |
| LLVM_DEBUG(dbgs() << "Flags not used by terminator: " << *I); |
| return nullptr; |
| } |
| |
| // Now find the instruction controlling the terminator. |
| for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) { |
| I = prev_nodbg(I, MBB->begin()); |
| assert(!I->isTerminator() && "Spurious terminator"); |
| switch (I->getOpcode()) { |
| // cmp is an alias for subs with a dead destination register. |
| case AArch64::SUBSWri: |
| case AArch64::SUBSXri: |
| // cmn is an alias for adds with a dead destination register. |
| case AArch64::ADDSWri: |
| case AArch64::ADDSXri: |
| // Check that the immediate operand is within range, ccmp wants a uimm5. |
| // Rd = SUBSri Rn, imm, shift |
| if (I->getOperand(3).getImm() || !isUInt<5>(I->getOperand(2).getImm())) { |
| LLVM_DEBUG(dbgs() << "Immediate out of range for ccmp: " << *I); |
| ++NumImmRangeRejs; |
| return nullptr; |
| } |
| LLVM_FALLTHROUGH; |
| case AArch64::SUBSWrr: |
| case AArch64::SUBSXrr: |
| case AArch64::ADDSWrr: |
| case AArch64::ADDSXrr: |
| if (isDeadDef(I->getOperand(0).getReg())) |
| return &*I; |
| LLVM_DEBUG(dbgs() << "Can't convert compare with live destination: " |
| << *I); |
| ++NumLiveDstRejs; |
| return nullptr; |
| case AArch64::FCMPSrr: |
| case AArch64::FCMPDrr: |
| case AArch64::FCMPESrr: |
| case AArch64::FCMPEDrr: |
| return &*I; |
| } |
| |
| // Check for flag reads and clobbers. |
| PhysRegInfo PRI = AnalyzePhysRegInBundle(*I, AArch64::NZCV, TRI); |
| |
| if (PRI.Read) { |
| // The ccmp doesn't produce exactly the same flags as the original |
| // compare, so reject the transform if there are uses of the flags |
| // besides the terminators. |
| LLVM_DEBUG(dbgs() << "Can't create ccmp with multiple uses: " << *I); |
| ++NumMultNZCVUses; |
| return nullptr; |
| } |
| |
| if (PRI.Defined || PRI.Clobbered) { |
| LLVM_DEBUG(dbgs() << "Not convertible compare: " << *I); |
| ++NumUnknNZCVDefs; |
| return nullptr; |
| } |
| } |
| LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB) |
| << '\n'); |
| return nullptr; |
| } |
| |
| /// Determine if all the instructions in MBB can safely |
| /// be speculated. The terminators are not considered. |
| /// |
| /// Only CmpMI is allowed to clobber the flags. |
| /// |
| bool SSACCmpConv::canSpeculateInstrs(MachineBasicBlock *MBB, |
| const MachineInstr *CmpMI) { |
| // Reject any live-in physregs. It's probably NZCV/EFLAGS, and very hard to |
| // get right. |
| if (!MBB->livein_empty()) { |
| LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); |
| return false; |
| } |
| |
| unsigned InstrCount = 0; |
| |
| // Check all instructions, except the terminators. It is assumed that |
| // terminators never have side effects or define any used register values. |
| for (auto &I : make_range(MBB->begin(), MBB->getFirstTerminator())) { |
| if (I.isDebugInstr()) |
| continue; |
| |
| if (++InstrCount > BlockInstrLimit && !Stress) { |
| LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than " |
| << BlockInstrLimit << " instructions.\n"); |
| return false; |
| } |
| |
| // There shouldn't normally be any phis in a single-predecessor block. |
| if (I.isPHI()) { |
| LLVM_DEBUG(dbgs() << "Can't hoist: " << I); |
| return false; |
| } |
| |
| // Don't speculate loads. Note that it may be possible and desirable to |
| // speculate GOT or constant pool loads that are guaranteed not to trap, |
| // but we don't support that for now. |
| if (I.mayLoad()) { |
| LLVM_DEBUG(dbgs() << "Won't speculate load: " << I); |
| return false; |
| } |
| |
| // We never speculate stores, so an AA pointer isn't necessary. |
| bool DontMoveAcrossStore = true; |
| if (!I.isSafeToMove(nullptr, DontMoveAcrossStore)) { |
| LLVM_DEBUG(dbgs() << "Can't speculate: " << I); |
| return false; |
| } |
| |
| // Only CmpMI is allowed to clobber the flags. |
| if (&I != CmpMI && I.modifiesRegister(AArch64::NZCV, TRI)) { |
| LLVM_DEBUG(dbgs() << "Clobbers flags: " << I); |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /// Analyze the sub-cfg rooted in MBB, and return true if it is a potential |
| /// candidate for cmp-conversion. Fill out the internal state. |
| /// |
| bool SSACCmpConv::canConvert(MachineBasicBlock *MBB) { |
| Head = MBB; |
| Tail = CmpBB = nullptr; |
| |
| if (Head->succ_size() != 2) |
| return false; |
| MachineBasicBlock *Succ0 = Head->succ_begin()[0]; |
| MachineBasicBlock *Succ1 = Head->succ_begin()[1]; |
| |
| // CmpBB can only have a single predecessor. Tail is allowed many. |
| if (Succ0->pred_size() != 1) |
| std::swap(Succ0, Succ1); |
| |
| // Succ0 is our candidate for CmpBB. |
| if (Succ0->pred_size() != 1 || Succ0->succ_size() != 2) |
| return false; |
| |
| CmpBB = Succ0; |
| Tail = Succ1; |
| |
| if (!CmpBB->isSuccessor(Tail)) |
| return false; |
| |
| // The CFG topology checks out. |
| LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> " |
| << printMBBReference(*CmpBB) << " -> " |
| << printMBBReference(*Tail) << '\n'); |
| ++NumConsidered; |
| |
| // Tail is allowed to have many predecessors, but we can't handle PHIs yet. |
| // |
| // FIXME: Real PHIs could be if-converted as long as the CmpBB values are |
| // defined before The CmpBB cmp clobbers the flags. Alternatively, it should |
| // always be safe to sink the ccmp down to immediately before the CmpBB |
| // terminators. |
| if (!trivialTailPHIs()) { |
| LLVM_DEBUG(dbgs() << "Can't handle phis in Tail.\n"); |
| ++NumPhiRejs; |
| return false; |
| } |
| |
| if (!Tail->livein_empty()) { |
| LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in Tail.\n"); |
| ++NumPhysRejs; |
| return false; |
| } |
| |
| // CmpBB should never have PHIs since Head is its only predecessor. |
| // FIXME: Clean them up if it happens. |
| if (!CmpBB->empty() && CmpBB->front().isPHI()) { |
| LLVM_DEBUG(dbgs() << "Can't handle phis in CmpBB.\n"); |
| ++NumPhi2Rejs; |
| return false; |
| } |
| |
| if (!CmpBB->livein_empty()) { |
| LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in CmpBB.\n"); |
| ++NumPhysRejs; |
| return false; |
| } |
| |
| // The branch we're looking to eliminate must be analyzable. |
| HeadCond.clear(); |
| MachineBasicBlock *TBB = nullptr, *FBB = nullptr; |
| if (TII->analyzeBranch(*Head, TBB, FBB, HeadCond)) { |
| LLVM_DEBUG(dbgs() << "Head branch not analyzable.\n"); |
| ++NumHeadBranchRejs; |
| return false; |
| } |
| |
| // This is weird, probably some sort of degenerate CFG, or an edge to a |
| // landing pad. |
| if (!TBB || HeadCond.empty()) { |
| LLVM_DEBUG( |
| dbgs() << "analyzeBranch didn't find conditional branch in Head.\n"); |
| ++NumHeadBranchRejs; |
| return false; |
| } |
| |
| if (!parseCond(HeadCond, HeadCmpBBCC)) { |
| LLVM_DEBUG(dbgs() << "Unsupported branch type on Head\n"); |
| ++NumHeadBranchRejs; |
| return false; |
| } |
| |
| // Make sure the branch direction is right. |
| if (TBB != CmpBB) { |
| assert(TBB == Tail && "Unexpected TBB"); |
| HeadCmpBBCC = AArch64CC::getInvertedCondCode(HeadCmpBBCC); |
| } |
| |
| CmpBBCond.clear(); |
| TBB = FBB = nullptr; |
| if (TII->analyzeBranch(*CmpBB, TBB, FBB, CmpBBCond)) { |
| LLVM_DEBUG(dbgs() << "CmpBB branch not analyzable.\n"); |
| ++NumCmpBranchRejs; |
| return false; |
| } |
| |
| if (!TBB || CmpBBCond.empty()) { |
| LLVM_DEBUG( |
| dbgs() << "analyzeBranch didn't find conditional branch in CmpBB.\n"); |
| ++NumCmpBranchRejs; |
| return false; |
| } |
| |
| if (!parseCond(CmpBBCond, CmpBBTailCC)) { |
| LLVM_DEBUG(dbgs() << "Unsupported branch type on CmpBB\n"); |
| ++NumCmpBranchRejs; |
| return false; |
| } |
| |
| if (TBB != Tail) |
| CmpBBTailCC = AArch64CC::getInvertedCondCode(CmpBBTailCC); |
| |
| LLVM_DEBUG(dbgs() << "Head->CmpBB on " |
| << AArch64CC::getCondCodeName(HeadCmpBBCC) |
| << ", CmpBB->Tail on " |
| << AArch64CC::getCondCodeName(CmpBBTailCC) << '\n'); |
| |
| CmpMI = findConvertibleCompare(CmpBB); |
| if (!CmpMI) |
| return false; |
| |
| if (!canSpeculateInstrs(CmpBB, CmpMI)) { |
| ++NumSpeculateRejs; |
| return false; |
| } |
| return true; |
| } |
| |
| void SSACCmpConv::convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks) { |
| LLVM_DEBUG(dbgs() << "Merging " << printMBBReference(*CmpBB) << " into " |
| << printMBBReference(*Head) << ":\n" |
| << *CmpBB); |
| |
| // All CmpBB instructions are moved into Head, and CmpBB is deleted. |
| // Update the CFG first. |
| updateTailPHIs(); |
| |
| // Save successor probabilties before removing CmpBB and Tail from their |
| // parents. |
| BranchProbability Head2CmpBB = MBPI->getEdgeProbability(Head, CmpBB); |
| BranchProbability CmpBB2Tail = MBPI->getEdgeProbability(CmpBB, Tail); |
| |
| Head->removeSuccessor(CmpBB); |
| CmpBB->removeSuccessor(Tail); |
| |
| // If Head and CmpBB had successor probabilties, udpate the probabilities to |
| // reflect the ccmp-conversion. |
| if (Head->hasSuccessorProbabilities() && CmpBB->hasSuccessorProbabilities()) { |
| |
| // Head is allowed two successors. We've removed CmpBB, so the remaining |
| // successor is Tail. We need to increase the successor probability for |
| // Tail to account for the CmpBB path we removed. |
| // |
| // Pr(Tail|Head) += Pr(CmpBB|Head) * Pr(Tail|CmpBB). |
| assert(*Head->succ_begin() == Tail && "Head successor is not Tail"); |
| BranchProbability Head2Tail = MBPI->getEdgeProbability(Head, Tail); |
| Head->setSuccProbability(Head->succ_begin(), |
| Head2Tail + Head2CmpBB * CmpBB2Tail); |
| |
| // We will transfer successors of CmpBB to Head in a moment without |
| // normalizing the successor probabilities. Set the successor probabilites |
| // before doing so. |
| // |
| // Pr(I|Head) = Pr(CmpBB|Head) * Pr(I|CmpBB). |
| for (auto I = CmpBB->succ_begin(), E = CmpBB->succ_end(); I != E; ++I) { |
| BranchProbability CmpBB2I = MBPI->getEdgeProbability(CmpBB, *I); |
| CmpBB->setSuccProbability(I, Head2CmpBB * CmpBB2I); |
| } |
| } |
| |
| Head->transferSuccessorsAndUpdatePHIs(CmpBB); |
| DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc(); |
| TII->removeBranch(*Head); |
| |
| // If the Head terminator was one of the cbz / tbz branches with built-in |
| // compare, we need to insert an explicit compare instruction in its place. |
| if (HeadCond[0].getImm() == -1) { |
| ++NumCompBranches; |
| unsigned Opc = 0; |
| switch (HeadCond[1].getImm()) { |
| case AArch64::CBZW: |
| case AArch64::CBNZW: |
| Opc = AArch64::SUBSWri; |
| break; |
| case AArch64::CBZX: |
| case AArch64::CBNZX: |
| Opc = AArch64::SUBSXri; |
| break; |
| default: |
| llvm_unreachable("Cannot convert Head branch"); |
| } |
| const MCInstrDesc &MCID = TII->get(Opc); |
| // Create a dummy virtual register for the SUBS def. |
| Register DestReg = |
| MRI->createVirtualRegister(TII->getRegClass(MCID, 0, TRI, *MF)); |
| // Insert a SUBS Rn, #0 instruction instead of the cbz / cbnz. |
| BuildMI(*Head, Head->end(), TermDL, MCID) |
| .addReg(DestReg, RegState::Define | RegState::Dead) |
| .add(HeadCond[2]) |
| .addImm(0) |
| .addImm(0); |
| // SUBS uses the GPR*sp register classes. |
| MRI->constrainRegClass(HeadCond[2].getReg(), |
| TII->getRegClass(MCID, 1, TRI, *MF)); |
| } |
| |
| Head->splice(Head->end(), CmpBB, CmpBB->begin(), CmpBB->end()); |
| |
| // Now replace CmpMI with a ccmp instruction that also considers the incoming |
| // flags. |
| unsigned Opc = 0; |
| unsigned FirstOp = 1; // First CmpMI operand to copy. |
| bool isZBranch = false; // CmpMI is a cbz/cbnz instruction. |
| switch (CmpMI->getOpcode()) { |
| default: |
| llvm_unreachable("Unknown compare opcode"); |
| case AArch64::SUBSWri: Opc = AArch64::CCMPWi; break; |
| case AArch64::SUBSWrr: Opc = AArch64::CCMPWr; break; |
| case AArch64::SUBSXri: Opc = AArch64::CCMPXi; break; |
| case AArch64::SUBSXrr: Opc = AArch64::CCMPXr; break; |
| case AArch64::ADDSWri: Opc = AArch64::CCMNWi; break; |
| case AArch64::ADDSWrr: Opc = AArch64::CCMNWr; break; |
| case AArch64::ADDSXri: Opc = AArch64::CCMNXi; break; |
| case AArch64::ADDSXrr: Opc = AArch64::CCMNXr; break; |
| case AArch64::FCMPSrr: Opc = AArch64::FCCMPSrr; FirstOp = 0; break; |
| case AArch64::FCMPDrr: Opc = AArch64::FCCMPDrr; FirstOp = 0; break; |
| case AArch64::FCMPESrr: Opc = AArch64::FCCMPESrr; FirstOp = 0; break; |
| case AArch64::FCMPEDrr: Opc = AArch64::FCCMPEDrr; FirstOp = 0; break; |
| case AArch64::CBZW: |
| case AArch64::CBNZW: |
| Opc = AArch64::CCMPWi; |
| FirstOp = 0; |
| isZBranch = true; |
| break; |
| case AArch64::CBZX: |
| case AArch64::CBNZX: |
| Opc = AArch64::CCMPXi; |
| FirstOp = 0; |
| isZBranch = true; |
| break; |
| } |
| |
| // The ccmp instruction should set the flags according to the comparison when |
| // Head would have branched to CmpBB. |
| // The NZCV immediate operand should provide flags for the case where Head |
| // would have branched to Tail. These flags should cause the new Head |
| // terminator to branch to tail. |
| unsigned NZCV = AArch64CC::getNZCVToSatisfyCondCode(CmpBBTailCC); |
| const MCInstrDesc &MCID = TII->get(Opc); |
| MRI->constrainRegClass(CmpMI->getOperand(FirstOp).getReg(), |
| TII->getRegClass(MCID, 0, TRI, *MF)); |
| if (CmpMI->getOperand(FirstOp + 1).isReg()) |
| MRI->constrainRegClass(CmpMI->getOperand(FirstOp + 1).getReg(), |
| TII->getRegClass(MCID, 1, TRI, *MF)); |
| MachineInstrBuilder MIB = BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), MCID) |
| .add(CmpMI->getOperand(FirstOp)); // Register Rn |
| if (isZBranch) |
| MIB.addImm(0); // cbz/cbnz Rn -> ccmp Rn, #0 |
| else |
| MIB.add(CmpMI->getOperand(FirstOp + 1)); // Register Rm / Immediate |
| MIB.addImm(NZCV).addImm(HeadCmpBBCC); |
| |
| // If CmpMI was a terminator, we need a new conditional branch to replace it. |
| // This now becomes a Head terminator. |
| if (isZBranch) { |
| bool isNZ = CmpMI->getOpcode() == AArch64::CBNZW || |
| CmpMI->getOpcode() == AArch64::CBNZX; |
| BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), TII->get(AArch64::Bcc)) |
| .addImm(isNZ ? AArch64CC::NE : AArch64CC::EQ) |
| .add(CmpMI->getOperand(1)); // Branch target. |
| } |
| CmpMI->eraseFromParent(); |
| Head->updateTerminator(CmpBB->getNextNode()); |
| |
| RemovedBlocks.push_back(CmpBB); |
| CmpBB->eraseFromParent(); |
| LLVM_DEBUG(dbgs() << "Result:\n" << *Head); |
| ++NumConverted; |
| } |
| |
| int SSACCmpConv::expectedCodeSizeDelta() const { |
| int delta = 0; |
| // If the Head terminator was one of the cbz / tbz branches with built-in |
| // compare, we need to insert an explicit compare instruction in its place |
| // plus a branch instruction. |
| if (HeadCond[0].getImm() == -1) { |
| switch (HeadCond[1].getImm()) { |
| case AArch64::CBZW: |
| case AArch64::CBNZW: |
| case AArch64::CBZX: |
| case AArch64::CBNZX: |
| // Therefore delta += 1 |
| delta = 1; |
| break; |
| default: |
| llvm_unreachable("Cannot convert Head branch"); |
| } |
| } |
| // If the Cmp terminator was one of the cbz / tbz branches with |
| // built-in compare, it will be turned into a compare instruction |
| // into Head, but we do not save any instruction. |
| // Otherwise, we save the branch instruction. |
| switch (CmpMI->getOpcode()) { |
| default: |
| --delta; |
| break; |
| case AArch64::CBZW: |
| case AArch64::CBNZW: |
| case AArch64::CBZX: |
| case AArch64::CBNZX: |
| break; |
| } |
| return delta; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // AArch64ConditionalCompares Pass |
| //===----------------------------------------------------------------------===// |
| |
| namespace { |
| class AArch64ConditionalCompares : public MachineFunctionPass { |
| const MachineBranchProbabilityInfo *MBPI; |
| const TargetInstrInfo *TII; |
| const TargetRegisterInfo *TRI; |
| MCSchedModel SchedModel; |
| // Does the proceeded function has Oz attribute. |
| bool MinSize; |
| MachineRegisterInfo *MRI; |
| MachineDominatorTree *DomTree; |
| MachineLoopInfo *Loops; |
| MachineTraceMetrics *Traces; |
| MachineTraceMetrics::Ensemble *MinInstr; |
| SSACCmpConv CmpConv; |
| |
| public: |
| static char ID; |
| AArch64ConditionalCompares() : MachineFunctionPass(ID) { |
| initializeAArch64ConditionalComparesPass(*PassRegistry::getPassRegistry()); |
| } |
| void getAnalysisUsage(AnalysisUsage &AU) const override; |
| bool runOnMachineFunction(MachineFunction &MF) override; |
| StringRef getPassName() const override { |
| return "AArch64 Conditional Compares"; |
| } |
| |
| private: |
| bool tryConvert(MachineBasicBlock *); |
| void updateDomTree(ArrayRef<MachineBasicBlock *> Removed); |
| void updateLoops(ArrayRef<MachineBasicBlock *> Removed); |
| void invalidateTraces(); |
| bool shouldConvert(); |
| }; |
| } // end anonymous namespace |
| |
| char AArch64ConditionalCompares::ID = 0; |
| |
| INITIALIZE_PASS_BEGIN(AArch64ConditionalCompares, "aarch64-ccmp", |
| "AArch64 CCMP Pass", false, false) |
| INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) |
| INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
| INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics) |
| INITIALIZE_PASS_END(AArch64ConditionalCompares, "aarch64-ccmp", |
| "AArch64 CCMP Pass", false, false) |
| |
| FunctionPass *llvm::createAArch64ConditionalCompares() { |
| return new AArch64ConditionalCompares(); |
| } |
| |
| void AArch64ConditionalCompares::getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<MachineBranchProbabilityInfo>(); |
| AU.addRequired<MachineDominatorTree>(); |
| AU.addPreserved<MachineDominatorTree>(); |
| AU.addRequired<MachineLoopInfo>(); |
| AU.addPreserved<MachineLoopInfo>(); |
| AU.addRequired<MachineTraceMetrics>(); |
| AU.addPreserved<MachineTraceMetrics>(); |
| MachineFunctionPass::getAnalysisUsage(AU); |
| } |
| |
| /// Update the dominator tree after if-conversion erased some blocks. |
| void AArch64ConditionalCompares::updateDomTree( |
| ArrayRef<MachineBasicBlock *> Removed) { |
| // convert() removes CmpBB which was previously dominated by Head. |
| // CmpBB children should be transferred to Head. |
| MachineDomTreeNode *HeadNode = DomTree->getNode(CmpConv.Head); |
| for (MachineBasicBlock *RemovedMBB : Removed) { |
| MachineDomTreeNode *Node = DomTree->getNode(RemovedMBB); |
| assert(Node != HeadNode && "Cannot erase the head node"); |
| assert(Node->getIDom() == HeadNode && "CmpBB should be dominated by Head"); |
| while (Node->getNumChildren()) |
| DomTree->changeImmediateDominator(Node->back(), HeadNode); |
| DomTree->eraseNode(RemovedMBB); |
| } |
| } |
| |
| /// Update LoopInfo after if-conversion. |
| void |
| AArch64ConditionalCompares::updateLoops(ArrayRef<MachineBasicBlock *> Removed) { |
| if (!Loops) |
| return; |
| for (MachineBasicBlock *RemovedMBB : Removed) |
| Loops->removeBlock(RemovedMBB); |
| } |
| |
| /// Invalidate MachineTraceMetrics before if-conversion. |
| void AArch64ConditionalCompares::invalidateTraces() { |
| Traces->invalidate(CmpConv.Head); |
| Traces->invalidate(CmpConv.CmpBB); |
| } |
| |
| /// Apply cost model and heuristics to the if-conversion in IfConv. |
| /// Return true if the conversion is a good idea. |
| /// |
| bool AArch64ConditionalCompares::shouldConvert() { |
| // Stress testing mode disables all cost considerations. |
| if (Stress) |
| return true; |
| if (!MinInstr) |
| MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount); |
| |
| // Head dominates CmpBB, so it is always included in its trace. |
| MachineTraceMetrics::Trace Trace = MinInstr->getTrace(CmpConv.CmpBB); |
| |
| // If code size is the main concern |
| if (MinSize) { |
| int CodeSizeDelta = CmpConv.expectedCodeSizeDelta(); |
| LLVM_DEBUG(dbgs() << "Code size delta: " << CodeSizeDelta << '\n'); |
| // If we are minimizing the code size, do the conversion whatever |
| // the cost is. |
| if (CodeSizeDelta < 0) |
| return true; |
| if (CodeSizeDelta > 0) { |
| LLVM_DEBUG(dbgs() << "Code size is increasing, give up on this one.\n"); |
| return false; |
| } |
| // CodeSizeDelta == 0, continue with the regular heuristics |
| } |
| |
| // Heuristic: The compare conversion delays the execution of the branch |
| // instruction because we must wait for the inputs to the second compare as |
| // well. The branch has no dependent instructions, but delaying it increases |
| // the cost of a misprediction. |
| // |
| // Set a limit on the delay we will accept. |
| unsigned DelayLimit = SchedModel.MispredictPenalty * 3 / 4; |
| |
| // Instruction depths can be computed for all trace instructions above CmpBB. |
| unsigned HeadDepth = |
| Trace.getInstrCycles(*CmpConv.Head->getFirstTerminator()).Depth; |
| unsigned CmpBBDepth = |
| Trace.getInstrCycles(*CmpConv.CmpBB->getFirstTerminator()).Depth; |
| LLVM_DEBUG(dbgs() << "Head depth: " << HeadDepth |
| << "\nCmpBB depth: " << CmpBBDepth << '\n'); |
| if (CmpBBDepth > HeadDepth + DelayLimit) { |
| LLVM_DEBUG(dbgs() << "Branch delay would be larger than " << DelayLimit |
| << " cycles.\n"); |
| return false; |
| } |
| |
| // Check the resource depth at the bottom of CmpBB - these instructions will |
| // be speculated. |
| unsigned ResDepth = Trace.getResourceDepth(true); |
| LLVM_DEBUG(dbgs() << "Resources: " << ResDepth << '\n'); |
| |
| // Heuristic: The speculatively executed instructions must all be able to |
| // merge into the Head block. The Head critical path should dominate the |
| // resource cost of the speculated instructions. |
| if (ResDepth > HeadDepth) { |
| LLVM_DEBUG(dbgs() << "Too many instructions to speculate.\n"); |
| return false; |
| } |
| return true; |
| } |
| |
| bool AArch64ConditionalCompares::tryConvert(MachineBasicBlock *MBB) { |
| bool Changed = false; |
| while (CmpConv.canConvert(MBB) && shouldConvert()) { |
| invalidateTraces(); |
| SmallVector<MachineBasicBlock *, 4> RemovedBlocks; |
| CmpConv.convert(RemovedBlocks); |
| Changed = true; |
| updateDomTree(RemovedBlocks); |
| updateLoops(RemovedBlocks); |
| } |
| return Changed; |
| } |
| |
| bool AArch64ConditionalCompares::runOnMachineFunction(MachineFunction &MF) { |
| LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n" |
| << "********** Function: " << MF.getName() << '\n'); |
| if (skipFunction(MF.getFunction())) |
| return false; |
| |
| TII = MF.getSubtarget().getInstrInfo(); |
| TRI = MF.getSubtarget().getRegisterInfo(); |
| SchedModel = MF.getSubtarget().getSchedModel(); |
| MRI = &MF.getRegInfo(); |
| DomTree = &getAnalysis<MachineDominatorTree>(); |
| Loops = getAnalysisIfAvailable<MachineLoopInfo>(); |
| MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); |
| Traces = &getAnalysis<MachineTraceMetrics>(); |
| MinInstr = nullptr; |
| MinSize = MF.getFunction().hasMinSize(); |
| |
| bool Changed = false; |
| CmpConv.runOnMachineFunction(MF, MBPI); |
| |
| // Visit blocks in dominator tree pre-order. The pre-order enables multiple |
| // cmp-conversions from the same head block. |
| // Note that updateDomTree() modifies the children of the DomTree node |
| // currently being visited. The df_iterator supports that; it doesn't look at |
| // child_begin() / child_end() until after a node has been visited. |
| for (auto *I : depth_first(DomTree)) |
| if (tryConvert(I->getBlock())) |
| Changed = true; |
| |
| return Changed; |
| } |