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