449 lines · cpp
1//=- AArch64ConditionOptimizer.cpp - Remove useless comparisons 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 pass tries to make consecutive compares of values use same operands to10// allow CSE pass to remove duplicated instructions. For this it analyzes11// branches and adjusts comparisons with immediate values by converting:12// * GE -> GT13// * GT -> GE14// * LT -> LE15// * LE -> LT16// and adjusting immediate values appropriately. It basically corrects two17// immediate values towards each other to make them equal.18//19// Consider the following example in C:20//21// if ((a < 5 && ...) || (a > 5 && ...)) {22// ~~~~~ ~~~~~23// ^ ^24// x y25//26// Here both "x" and "y" expressions compare "a" with "5". When "x" evaluates27// to "false", "y" can just check flags set by the first comparison. As a28// result of the canonicalization employed by29// SelectionDAGBuilder::visitSwitchCase, DAGCombine, and other target-specific30// code, assembly ends up in the form that is not CSE friendly:31//32// ...33// cmp w8, #434// b.gt .LBB0_335// ...36// .LBB0_3:37// cmp w8, #638// b.lt .LBB0_639// ...40//41// Same assembly after the pass:42//43// ...44// cmp w8, #545// b.ge .LBB0_346// ...47// .LBB0_3:48// cmp w8, #5 // <-- CSE pass removes this instruction49// b.le .LBB0_650// ...51//52// Currently only SUBS and ADDS followed by b.?? are supported.53//54// TODO: maybe handle TBNZ/TBZ the same way as CMP when used instead for "a < 0"55// TODO: handle other conditional instructions (e.g. CSET)56// TODO: allow second branching to be anything if it doesn't require adjusting57//58//===----------------------------------------------------------------------===//59 60#include "AArch64.h"61#include "MCTargetDesc/AArch64AddressingModes.h"62#include "Utils/AArch64BaseInfo.h"63#include "llvm/ADT/ArrayRef.h"64#include "llvm/ADT/DepthFirstIterator.h"65#include "llvm/ADT/SmallVector.h"66#include "llvm/ADT/Statistic.h"67#include "llvm/CodeGen/MachineBasicBlock.h"68#include "llvm/CodeGen/MachineDominators.h"69#include "llvm/CodeGen/MachineFunction.h"70#include "llvm/CodeGen/MachineFunctionPass.h"71#include "llvm/CodeGen/MachineInstr.h"72#include "llvm/CodeGen/MachineInstrBuilder.h"73#include "llvm/CodeGen/MachineOperand.h"74#include "llvm/CodeGen/MachineRegisterInfo.h"75#include "llvm/CodeGen/TargetInstrInfo.h"76#include "llvm/CodeGen/TargetSubtargetInfo.h"77#include "llvm/InitializePasses.h"78#include "llvm/Pass.h"79#include "llvm/Support/Debug.h"80#include "llvm/Support/ErrorHandling.h"81#include "llvm/Support/raw_ostream.h"82#include <cassert>83#include <cstdlib>84#include <tuple>85 86using namespace llvm;87 88#define DEBUG_TYPE "aarch64-condopt"89 90STATISTIC(NumConditionsAdjusted, "Number of conditions adjusted");91 92namespace {93 94class AArch64ConditionOptimizer : public MachineFunctionPass {95 const TargetInstrInfo *TII;96 MachineDominatorTree *DomTree;97 const MachineRegisterInfo *MRI;98 99public:100 // Stores immediate, compare instruction opcode and branch condition (in this101 // order) of adjusted comparison.102 using CmpInfo = std::tuple<int, unsigned, AArch64CC::CondCode>;103 104 static char ID;105 106 AArch64ConditionOptimizer() : MachineFunctionPass(ID) {}107 108 void getAnalysisUsage(AnalysisUsage &AU) const override;109 MachineInstr *findSuitableCompare(MachineBasicBlock *MBB);110 CmpInfo adjustCmp(MachineInstr *CmpMI, AArch64CC::CondCode Cmp);111 void modifyCmp(MachineInstr *CmpMI, const CmpInfo &Info);112 bool adjustTo(MachineInstr *CmpMI, AArch64CC::CondCode Cmp, MachineInstr *To,113 int ToImm);114 bool runOnMachineFunction(MachineFunction &MF) override;115 116 StringRef getPassName() const override {117 return "AArch64 Condition Optimizer";118 }119};120 121} // end anonymous namespace122 123char AArch64ConditionOptimizer::ID = 0;124 125INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer, "aarch64-condopt",126 "AArch64 CondOpt Pass", false, false)127INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)128INITIALIZE_PASS_END(AArch64ConditionOptimizer, "aarch64-condopt",129 "AArch64 CondOpt Pass", false, false)130 131FunctionPass *llvm::createAArch64ConditionOptimizerPass() {132 return new AArch64ConditionOptimizer();133}134 135void AArch64ConditionOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {136 AU.addRequired<MachineDominatorTreeWrapperPass>();137 AU.addPreserved<MachineDominatorTreeWrapperPass>();138 MachineFunctionPass::getAnalysisUsage(AU);139}140 141// Finds compare instruction that corresponds to supported types of branching.142// Returns the instruction or nullptr on failures or detecting unsupported143// instructions.144MachineInstr *AArch64ConditionOptimizer::findSuitableCompare(145 MachineBasicBlock *MBB) {146 MachineBasicBlock::iterator Term = MBB->getFirstTerminator();147 if (Term == MBB->end())148 return nullptr;149 150 if (Term->getOpcode() != AArch64::Bcc)151 return nullptr;152 153 // Since we may modify cmp of this MBB, make sure NZCV does not live out.154 for (auto *SuccBB : MBB->successors())155 if (SuccBB->isLiveIn(AArch64::NZCV))156 return nullptr;157 158 // Now find the instruction controlling the terminator.159 for (MachineBasicBlock::iterator B = MBB->begin(), It = Term; It != B;) {160 It = prev_nodbg(It, B);161 MachineInstr &I = *It;162 assert(!I.isTerminator() && "Spurious terminator");163 // Check if there is any use of NZCV between CMP and Bcc.164 if (I.readsRegister(AArch64::NZCV, /*TRI=*/nullptr))165 return nullptr;166 switch (I.getOpcode()) {167 // cmp is an alias for subs with a dead destination register.168 case AArch64::SUBSWri:169 case AArch64::SUBSXri:170 // cmn is an alias for adds with a dead destination register.171 case AArch64::ADDSWri:172 case AArch64::ADDSXri: {173 unsigned ShiftAmt = AArch64_AM::getShiftValue(I.getOperand(3).getImm());174 if (!I.getOperand(2).isImm()) {175 LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << I << '\n');176 return nullptr;177 } else if (I.getOperand(2).getImm() << ShiftAmt >= 0xfff) {178 LLVM_DEBUG(dbgs() << "Immediate of cmp may be out of range, " << I179 << '\n');180 return nullptr;181 } else if (!MRI->use_nodbg_empty(I.getOperand(0).getReg())) {182 LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << I << '\n');183 return nullptr;184 }185 return &I;186 }187 // Prevent false positive case like:188 // cmp w19, #0189 // cinc w0, w19, gt190 // ...191 // fcmp d8, #0.0192 // b.gt .LBB0_5193 case AArch64::FCMPDri:194 case AArch64::FCMPSri:195 case AArch64::FCMPESri:196 case AArch64::FCMPEDri:197 198 case AArch64::SUBSWrr:199 case AArch64::SUBSXrr:200 case AArch64::ADDSWrr:201 case AArch64::ADDSXrr:202 case AArch64::FCMPSrr:203 case AArch64::FCMPDrr:204 case AArch64::FCMPESrr:205 case AArch64::FCMPEDrr:206 // Skip comparison instructions without immediate operands.207 return nullptr;208 }209 }210 LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB)211 << '\n');212 return nullptr;213}214 215// Changes opcode adds <-> subs considering register operand width.216static int getComplementOpc(int Opc) {217 switch (Opc) {218 case AArch64::ADDSWri: return AArch64::SUBSWri;219 case AArch64::ADDSXri: return AArch64::SUBSXri;220 case AArch64::SUBSWri: return AArch64::ADDSWri;221 case AArch64::SUBSXri: return AArch64::ADDSXri;222 default:223 llvm_unreachable("Unexpected opcode");224 }225}226 227// Changes form of comparison inclusive <-> exclusive.228static AArch64CC::CondCode getAdjustedCmp(AArch64CC::CondCode Cmp) {229 switch (Cmp) {230 case AArch64CC::GT: return AArch64CC::GE;231 case AArch64CC::GE: return AArch64CC::GT;232 case AArch64CC::LT: return AArch64CC::LE;233 case AArch64CC::LE: return AArch64CC::LT;234 default:235 llvm_unreachable("Unexpected condition code");236 }237}238 239// Transforms GT -> GE, GE -> GT, LT -> LE, LE -> LT by updating comparison240// operator and condition code.241AArch64ConditionOptimizer::CmpInfo AArch64ConditionOptimizer::adjustCmp(242 MachineInstr *CmpMI, AArch64CC::CondCode Cmp) {243 unsigned Opc = CmpMI->getOpcode();244 245 // CMN (compare with negative immediate) is an alias to ADDS (as246 // "operand - negative" == "operand + positive")247 bool Negative = (Opc == AArch64::ADDSWri || Opc == AArch64::ADDSXri);248 249 int Correction = (Cmp == AArch64CC::GT) ? 1 : -1;250 // Negate Correction value for comparison with negative immediate (CMN).251 if (Negative) {252 Correction = -Correction;253 }254 255 const int OldImm = (int)CmpMI->getOperand(2).getImm();256 const int NewImm = std::abs(OldImm + Correction);257 258 // Handle +0 -> -1 and -0 -> +1 (CMN with 0 immediate) transitions by259 // adjusting compare instruction opcode.260 if (OldImm == 0 && ((Negative && Correction == 1) ||261 (!Negative && Correction == -1))) {262 Opc = getComplementOpc(Opc);263 }264 265 return CmpInfo(NewImm, Opc, getAdjustedCmp(Cmp));266}267 268// Applies changes to comparison instruction suggested by adjustCmp().269void AArch64ConditionOptimizer::modifyCmp(MachineInstr *CmpMI,270 const CmpInfo &Info) {271 int Imm;272 unsigned Opc;273 AArch64CC::CondCode Cmp;274 std::tie(Imm, Opc, Cmp) = Info;275 276 MachineBasicBlock *const MBB = CmpMI->getParent();277 278 // Change immediate in comparison instruction (ADDS or SUBS).279 BuildMI(*MBB, CmpMI, CmpMI->getDebugLoc(), TII->get(Opc))280 .add(CmpMI->getOperand(0))281 .add(CmpMI->getOperand(1))282 .addImm(Imm)283 .add(CmpMI->getOperand(3));284 CmpMI->eraseFromParent();285 286 // The fact that this comparison was picked ensures that it's related to the287 // first terminator instruction.288 MachineInstr &BrMI = *MBB->getFirstTerminator();289 290 // Change condition in branch instruction.291 BuildMI(*MBB, BrMI, BrMI.getDebugLoc(), TII->get(AArch64::Bcc))292 .addImm(Cmp)293 .add(BrMI.getOperand(1));294 BrMI.eraseFromParent();295 296 ++NumConditionsAdjusted;297}298 299// Parse a condition code returned by analyzeBranch, and compute the CondCode300// corresponding to TBB.301// Returns true if parsing was successful, otherwise false is returned.302static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) {303 // A normal br.cond simply has the condition code.304 if (Cond[0].getImm() != -1) {305 assert(Cond.size() == 1 && "Unknown Cond array format");306 CC = (AArch64CC::CondCode)(int)Cond[0].getImm();307 return true;308 }309 return false;310}311 312// Adjusts one cmp instruction to another one if result of adjustment will allow313// CSE. Returns true if compare instruction was changed, otherwise false is314// returned.315bool AArch64ConditionOptimizer::adjustTo(MachineInstr *CmpMI,316 AArch64CC::CondCode Cmp, MachineInstr *To, int ToImm)317{318 CmpInfo Info = adjustCmp(CmpMI, Cmp);319 if (std::get<0>(Info) == ToImm && std::get<1>(Info) == To->getOpcode()) {320 modifyCmp(CmpMI, Info);321 return true;322 }323 return false;324}325 326bool AArch64ConditionOptimizer::runOnMachineFunction(MachineFunction &MF) {327 LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"328 << "********** Function: " << MF.getName() << '\n');329 if (skipFunction(MF.getFunction()))330 return false;331 332 TII = MF.getSubtarget().getInstrInfo();333 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();334 MRI = &MF.getRegInfo();335 336 bool Changed = false;337 338 // Visit blocks in dominator tree pre-order. The pre-order enables multiple339 // cmp-conversions from the same head block.340 // Note that updateDomTree() modifies the children of the DomTree node341 // currently being visited. The df_iterator supports that; it doesn't look at342 // child_begin() / child_end() until after a node has been visited.343 for (MachineDomTreeNode *I : depth_first(DomTree)) {344 MachineBasicBlock *HBB = I->getBlock();345 346 SmallVector<MachineOperand, 4> HeadCond;347 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;348 if (TII->analyzeBranch(*HBB, TBB, FBB, HeadCond)) {349 continue;350 }351 352 // Equivalence check is to skip loops.353 if (!TBB || TBB == HBB) {354 continue;355 }356 357 SmallVector<MachineOperand, 4> TrueCond;358 MachineBasicBlock *TBB_TBB = nullptr, *TBB_FBB = nullptr;359 if (TII->analyzeBranch(*TBB, TBB_TBB, TBB_FBB, TrueCond)) {360 continue;361 }362 363 MachineInstr *HeadCmpMI = findSuitableCompare(HBB);364 if (!HeadCmpMI) {365 continue;366 }367 368 MachineInstr *TrueCmpMI = findSuitableCompare(TBB);369 if (!TrueCmpMI) {370 continue;371 }372 373 AArch64CC::CondCode HeadCmp;374 if (HeadCond.empty() || !parseCond(HeadCond, HeadCmp)) {375 continue;376 }377 378 AArch64CC::CondCode TrueCmp;379 if (TrueCond.empty() || !parseCond(TrueCond, TrueCmp)) {380 continue;381 }382 383 const int HeadImm = (int)HeadCmpMI->getOperand(2).getImm();384 const int TrueImm = (int)TrueCmpMI->getOperand(2).getImm();385 386 LLVM_DEBUG(dbgs() << "Head branch:\n");387 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(HeadCmp)388 << '\n');389 LLVM_DEBUG(dbgs() << "\timmediate: " << HeadImm << '\n');390 391 LLVM_DEBUG(dbgs() << "True branch:\n");392 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(TrueCmp)393 << '\n');394 LLVM_DEBUG(dbgs() << "\timmediate: " << TrueImm << '\n');395 396 if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::LT) ||397 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::GT)) &&398 std::abs(TrueImm - HeadImm) == 2) {399 // This branch transforms machine instructions that correspond to400 //401 // 1) (a > {TrueImm} && ...) || (a < {HeadImm} && ...)402 // 2) (a < {TrueImm} && ...) || (a > {HeadImm} && ...)403 //404 // into405 //406 // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)407 // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)408 409 CmpInfo HeadCmpInfo = adjustCmp(HeadCmpMI, HeadCmp);410 CmpInfo TrueCmpInfo = adjustCmp(TrueCmpMI, TrueCmp);411 if (std::get<0>(HeadCmpInfo) == std::get<0>(TrueCmpInfo) &&412 std::get<1>(HeadCmpInfo) == std::get<1>(TrueCmpInfo)) {413 modifyCmp(HeadCmpMI, HeadCmpInfo);414 modifyCmp(TrueCmpMI, TrueCmpInfo);415 Changed = true;416 }417 } else if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::GT) ||418 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::LT)) &&419 std::abs(TrueImm - HeadImm) == 1) {420 // This branch transforms machine instructions that correspond to421 //422 // 1) (a > {TrueImm} && ...) || (a > {HeadImm} && ...)423 // 2) (a < {TrueImm} && ...) || (a < {HeadImm} && ...)424 //425 // into426 //427 // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)428 // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)429 430 // GT -> GE transformation increases immediate value, so picking the431 // smaller one; LT -> LE decreases immediate value so invert the choice.432 bool adjustHeadCond = (HeadImm < TrueImm);433 if (HeadCmp == AArch64CC::LT) {434 adjustHeadCond = !adjustHeadCond;435 }436 437 if (adjustHeadCond) {438 Changed |= adjustTo(HeadCmpMI, HeadCmp, TrueCmpMI, TrueImm);439 } else {440 Changed |= adjustTo(TrueCmpMI, TrueCmp, HeadCmpMI, HeadImm);441 }442 }443 // Other transformation cases almost never occur due to generation of < or >444 // comparisons instead of <= and >=.445 }446 447 return Changed;448}449