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