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
80using namespace llvm;
81
82#define DEBUG_TYPE "aarch64-condopt"
83
84STATISTIC(NumConditionsAdjusted, "Number of conditions adjusted");
85
86namespace {
87class AArch64ConditionOptimizer : public MachineFunctionPass {
88  const TargetInstrInfo *TII;
89  MachineDominatorTree *DomTree;
90  const MachineRegisterInfo *MRI;
91
92public:
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
112char AArch64ConditionOptimizer::ID = 0;
113
114namespace llvm {
115void initializeAArch64ConditionOptimizerPass(PassRegistry &);
116}
117
118INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer, "aarch64-condopt",
119                      "AArch64 CondOpt Pass", false, false)
120INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
121INITIALIZE_PASS_END(AArch64ConditionOptimizer, "aarch64-condopt",
122                    "AArch64 CondOpt Pass", false, false)
123
124FunctionPass *llvm::createAArch64ConditionOptimizerPass() {
125  return new AArch64ConditionOptimizer();
126}
127
128void 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.
137MachineInstr *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.
206static 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.
218static 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.
231AArch64ConditionOptimizer::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().
259void 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.
294static 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.
307bool 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
318bool 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