[MIPS GlobalISel] Select MSA vector generic and builtin add
[llvm-complete.git] / lib / Target / AArch64 / AArch64ConditionOptimizer.cpp
bloba6efb115ed4448871c56c569e7cdd6c265bbf991
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.
19 // Consider the following example in C:
21 // if ((a < 5 && ...) || (a > 5 && ...)) {
22 // ~~~~~ ~~~~~
23 // ^ ^
24 // x y
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:
32 // ...
33 // cmp w8, #4
34 // b.gt .LBB0_3
35 // ...
36 // .LBB0_3:
37 // cmp w8, #6
38 // b.lt .LBB0_6
39 // ...
41 // Same assembly after the pass:
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 // ...
52 // Currently only SUBS and ADDS followed by b.?? are supported.
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
58 //===----------------------------------------------------------------------===//
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>
85 using namespace llvm;
87 #define DEBUG_TYPE "aarch64-condopt"
89 STATISTIC(NumConditionsAdjusted, "Number of conditions adjusted");
91 namespace {
93 class AArch64ConditionOptimizer : public MachineFunctionPass {
94 const TargetInstrInfo *TII;
95 MachineDominatorTree *DomTree;
96 const MachineRegisterInfo *MRI;
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>;
103 static char ID;
105 AArch64ConditionOptimizer() : MachineFunctionPass(ID) {
106 initializeAArch64ConditionOptimizerPass(*PassRegistry::getPassRegistry());
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;
117 StringRef getPassName() const override {
118 return "AArch64 Condition Optimizer";
122 } // end anonymous namespace
124 char AArch64ConditionOptimizer::ID = 0;
126 INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer, "aarch64-condopt",
127 "AArch64 CondOpt Pass", false, false)
128 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
129 INITIALIZE_PASS_END(AArch64ConditionOptimizer, "aarch64-condopt",
130 "AArch64 CondOpt Pass", false, false)
132 FunctionPass *llvm::createAArch64ConditionOptimizerPass() {
133 return new AArch64ConditionOptimizer();
136 void AArch64ConditionOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
137 AU.addRequired<MachineDominatorTree>();
138 AU.addPreserved<MachineDominatorTree>();
139 MachineFunctionPass::getAnalysisUsage(AU);
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 MachineBasicBlock *MBB) {
147 MachineBasicBlock::iterator I = MBB->getFirstTerminator();
148 if (I == MBB->end())
149 return nullptr;
151 if (I->getOpcode() != AArch64::Bcc)
152 return nullptr;
154 // Since we may modify cmp of this MBB, make sure NZCV does not live out.
155 for (auto SuccBB : MBB->successors())
156 if (SuccBB->isLiveIn(AArch64::NZCV))
157 return nullptr;
159 // Now find the instruction controlling the terminator.
160 for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) {
161 --I;
162 assert(!I->isTerminator() && "Spurious terminator");
163 // Check if there is any use of NZCV between CMP and Bcc.
164 if (I->readsRegister(AArch64::NZCV))
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(I->getOperand(3).getImm());
174 if (!I->getOperand(2).isImm()) {
175 LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << *I << '\n');
176 return nullptr;
177 } else if (I->getOperand(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_empty(I->getOperand(0).getReg())) {
182 LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << *I << '\n');
183 return nullptr;
185 return &*I;
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:
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;
210 LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB)
211 << '\n');
212 return nullptr;
215 // Changes opcode adds <-> subs considering register operand width.
216 static 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");
227 // Changes form of comparison inclusive <-> exclusive.
228 static 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");
239 // Transforms GT -> GE, GE -> GT, LT -> LE, LE -> LT by updating comparison
240 // operator and condition code.
241 AArch64ConditionOptimizer::CmpInfo AArch64ConditionOptimizer::adjustCmp(
242 MachineInstr *CmpMI, AArch64CC::CondCode Cmp) {
243 unsigned Opc = CmpMI->getOpcode();
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);
249 int Correction = (Cmp == AArch64CC::GT) ? 1 : -1;
250 // Negate Correction value for comparison with negative immediate (CMN).
251 if (Negative) {
252 Correction = -Correction;
255 const int OldImm = (int)CmpMI->getOperand(2).getImm();
256 const int NewImm = std::abs(OldImm + Correction);
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);
265 return CmpInfo(NewImm, Opc, getAdjustedCmp(Cmp));
268 // Applies changes to comparison instruction suggested by adjustCmp().
269 void AArch64ConditionOptimizer::modifyCmp(MachineInstr *CmpMI,
270 const CmpInfo &Info) {
271 int Imm;
272 unsigned Opc;
273 AArch64CC::CondCode Cmp;
274 std::tie(Imm, Opc, Cmp) = Info;
276 MachineBasicBlock *const MBB = CmpMI->getParent();
278 // Change immediate in comparison instruction (ADDS or SUBS).
279 BuildMI(*MBB, CmpMI, CmpMI->getDebugLoc(), TII->get(Opc))
280 .add(CmpMI->getOperand(0))
281 .add(CmpMI->getOperand(1))
282 .addImm(Imm)
283 .add(CmpMI->getOperand(3));
284 CmpMI->eraseFromParent();
286 // The fact that this comparison was picked ensures that it's related to the
287 // first terminator instruction.
288 MachineInstr &BrMI = *MBB->getFirstTerminator();
290 // Change condition in branch instruction.
291 BuildMI(*MBB, BrMI, BrMI.getDebugLoc(), TII->get(AArch64::Bcc))
292 .addImm(Cmp)
293 .add(BrMI.getOperand(1));
294 BrMI.eraseFromParent();
296 MBB->updateTerminator();
298 ++NumConditionsAdjusted;
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 static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) {
305 // A normal br.cond simply has the condition code.
306 if (Cond[0].getImm() != -1) {
307 assert(Cond.size() == 1 && "Unknown Cond array format");
308 CC = (AArch64CC::CondCode)(int)Cond[0].getImm();
309 return true;
311 return false;
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)
320 CmpInfo Info = adjustCmp(CmpMI, Cmp);
321 if (std::get<0>(Info) == ToImm && std::get<1>(Info) == To->getOpcode()) {
322 modifyCmp(CmpMI, Info);
323 return true;
325 return false;
328 bool AArch64ConditionOptimizer::runOnMachineFunction(MachineFunction &MF) {
329 LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
330 << "********** Function: " << MF.getName() << '\n');
331 if (skipFunction(MF.getFunction()))
332 return false;
334 TII = MF.getSubtarget().getInstrInfo();
335 DomTree = &getAnalysis<MachineDominatorTree>();
336 MRI = &MF.getRegInfo();
338 bool Changed = false;
340 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
341 // cmp-conversions from the same head block.
342 // Note that updateDomTree() modifies the children of the DomTree node
343 // currently being visited. The df_iterator supports that; it doesn't look at
344 // child_begin() / child_end() until after a node has been visited.
345 for (MachineDomTreeNode *I : depth_first(DomTree)) {
346 MachineBasicBlock *HBB = I->getBlock();
348 SmallVector<MachineOperand, 4> HeadCond;
349 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
350 if (TII->analyzeBranch(*HBB, TBB, FBB, HeadCond)) {
351 continue;
354 // Equivalence check is to skip loops.
355 if (!TBB || TBB == HBB) {
356 continue;
359 SmallVector<MachineOperand, 4> TrueCond;
360 MachineBasicBlock *TBB_TBB = nullptr, *TBB_FBB = nullptr;
361 if (TII->analyzeBranch(*TBB, TBB_TBB, TBB_FBB, TrueCond)) {
362 continue;
365 MachineInstr *HeadCmpMI = findSuitableCompare(HBB);
366 if (!HeadCmpMI) {
367 continue;
370 MachineInstr *TrueCmpMI = findSuitableCompare(TBB);
371 if (!TrueCmpMI) {
372 continue;
375 AArch64CC::CondCode HeadCmp;
376 if (HeadCond.empty() || !parseCond(HeadCond, HeadCmp)) {
377 continue;
380 AArch64CC::CondCode TrueCmp;
381 if (TrueCond.empty() || !parseCond(TrueCond, TrueCmp)) {
382 continue;
385 const int HeadImm = (int)HeadCmpMI->getOperand(2).getImm();
386 const int TrueImm = (int)TrueCmpMI->getOperand(2).getImm();
388 LLVM_DEBUG(dbgs() << "Head branch:\n");
389 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(HeadCmp)
390 << '\n');
391 LLVM_DEBUG(dbgs() << "\timmediate: " << HeadImm << '\n');
393 LLVM_DEBUG(dbgs() << "True branch:\n");
394 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(TrueCmp)
395 << '\n');
396 LLVM_DEBUG(dbgs() << "\timmediate: " << TrueImm << '\n');
398 if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::LT) ||
399 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::GT)) &&
400 std::abs(TrueImm - HeadImm) == 2) {
401 // This branch transforms machine instructions that correspond to
403 // 1) (a > {TrueImm} && ...) || (a < {HeadImm} && ...)
404 // 2) (a < {TrueImm} && ...) || (a > {HeadImm} && ...)
406 // into
408 // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)
409 // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)
411 CmpInfo HeadCmpInfo = adjustCmp(HeadCmpMI, HeadCmp);
412 CmpInfo TrueCmpInfo = adjustCmp(TrueCmpMI, TrueCmp);
413 if (std::get<0>(HeadCmpInfo) == std::get<0>(TrueCmpInfo) &&
414 std::get<1>(HeadCmpInfo) == std::get<1>(TrueCmpInfo)) {
415 modifyCmp(HeadCmpMI, HeadCmpInfo);
416 modifyCmp(TrueCmpMI, TrueCmpInfo);
417 Changed = true;
419 } else if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::GT) ||
420 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::LT)) &&
421 std::abs(TrueImm - HeadImm) == 1) {
422 // This branch transforms machine instructions that correspond to
424 // 1) (a > {TrueImm} && ...) || (a > {HeadImm} && ...)
425 // 2) (a < {TrueImm} && ...) || (a < {HeadImm} && ...)
427 // into
429 // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)
430 // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)
432 // GT -> GE transformation increases immediate value, so picking the
433 // smaller one; LT -> LE decreases immediate value so invert the choice.
434 bool adjustHeadCond = (HeadImm < TrueImm);
435 if (HeadCmp == AArch64CC::LT) {
436 adjustHeadCond = !adjustHeadCond;
439 if (adjustHeadCond) {
440 Changed |= adjustTo(HeadCmpMI, HeadCmp, TrueCmpMI, TrueImm);
441 } else {
442 Changed |= adjustTo(TrueCmpMI, TrueCmp, HeadCmpMI, HeadImm);
445 // Other transformation cases almost never occur due to generation of < or >
446 // comparisons instead of <= and >=.
449 return Changed;