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