Home | History | Annotate | Download | only in AArch64 
      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