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