contrib/llvm/lib/Target/AArch64/AArch64ConditionOptimizer.cpp

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