llvm/lib/Target/AArch64/AArch64ConditionOptimizer.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-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 }