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