Coverage Report

Created: 2019-07-24 05:18

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