1 //=== AArch64PostLegalizerCombiner.cpp --------------------------*- C++ -*-===//
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 /// \file
10 /// Post-legalization combines on generic MachineInstrs.
11 ///
12 /// The combines here must preserve instruction legality.
13 ///
14 /// Lowering combines (e.g. pseudo matching) should be handled by
15 /// AArch64PostLegalizerLowering.
16 ///
17 /// Combines which don't rely on instruction legality should go in the
18 /// AArch64PreLegalizerCombiner.
19 ///
20 //===----------------------------------------------------------------------===//
21 
22 #include "AArch64TargetMachine.h"
23 #include "llvm/CodeGen/GlobalISel/Combiner.h"
24 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
25 #include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
26 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
27 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
28 #include "llvm/CodeGen/GlobalISel/Utils.h"
29 #include "llvm/CodeGen/MachineDominators.h"
30 #include "llvm/CodeGen/MachineFunctionPass.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/CodeGen/TargetOpcodes.h"
33 #include "llvm/CodeGen/TargetPassConfig.h"
34 #include "llvm/Support/Debug.h"
35 
36 #define DEBUG_TYPE "aarch64-postlegalizer-combiner"
37 
38 using namespace llvm;
39 
40 /// This combine tries do what performExtractVectorEltCombine does in SDAG.
41 /// Rewrite for pairwise fadd pattern
42 ///   (s32 (g_extract_vector_elt
43 ///           (g_fadd (vXs32 Other)
44 ///                  (g_vector_shuffle (vXs32 Other) undef <1,X,...> )) 0))
45 /// ->
46 ///   (s32 (g_fadd (g_extract_vector_elt (vXs32 Other) 0)
47 ///              (g_extract_vector_elt (vXs32 Other) 1))
48 bool matchExtractVecEltPairwiseAdd(
49     MachineInstr &MI, MachineRegisterInfo &MRI,
50     std::tuple<unsigned, LLT, Register> &MatchInfo) {
51   Register Src1 = MI.getOperand(1).getReg();
52   Register Src2 = MI.getOperand(2).getReg();
53   LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
54 
55   auto Cst = getConstantVRegValWithLookThrough(Src2, MRI);
56   if (!Cst || Cst->Value != 0)
57     return false;
58   // SDAG also checks for FullFP16, but this looks to be beneficial anyway.
59 
60   // Now check for an fadd operation. TODO: expand this for integer add?
61   auto *FAddMI = getOpcodeDef(TargetOpcode::G_FADD, Src1, MRI);
62   if (!FAddMI)
63     return false;
64 
65   // If we add support for integer add, must restrict these types to just s64.
66   unsigned DstSize = DstTy.getSizeInBits();
67   if (DstSize != 16 && DstSize != 32 && DstSize != 64)
68     return false;
69 
70   Register Src1Op1 = FAddMI->getOperand(1).getReg();
71   Register Src1Op2 = FAddMI->getOperand(2).getReg();
72   MachineInstr *Shuffle =
73       getOpcodeDef(TargetOpcode::G_SHUFFLE_VECTOR, Src1Op2, MRI);
74   MachineInstr *Other = MRI.getVRegDef(Src1Op1);
75   if (!Shuffle) {
76     Shuffle = getOpcodeDef(TargetOpcode::G_SHUFFLE_VECTOR, Src1Op1, MRI);
77     Other = MRI.getVRegDef(Src1Op2);
78   }
79 
80   // We're looking for a shuffle that moves the second element to index 0.
81   if (Shuffle && Shuffle->getOperand(3).getShuffleMask()[0] == 1 &&
82       Other == MRI.getVRegDef(Shuffle->getOperand(1).getReg())) {
83     std::get<0>(MatchInfo) = TargetOpcode::G_FADD;
84     std::get<1>(MatchInfo) = DstTy;
85     std::get<2>(MatchInfo) = Other->getOperand(0).getReg();
86     return true;
87   }
88   return false;
89 }
90 
91 bool applyExtractVecEltPairwiseAdd(
92     MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &B,
93     std::tuple<unsigned, LLT, Register> &MatchInfo) {
94   unsigned Opc = std::get<0>(MatchInfo);
95   assert(Opc == TargetOpcode::G_FADD && "Unexpected opcode!");
96   // We want to generate two extracts of elements 0 and 1, and add them.
97   LLT Ty = std::get<1>(MatchInfo);
98   Register Src = std::get<2>(MatchInfo);
99   LLT s64 = LLT::scalar(64);
100   B.setInstrAndDebugLoc(MI);
101   auto Elt0 = B.buildExtractVectorElement(Ty, Src, B.buildConstant(s64, 0));
102   auto Elt1 = B.buildExtractVectorElement(Ty, Src, B.buildConstant(s64, 1));
103   B.buildInstr(Opc, {MI.getOperand(0).getReg()}, {Elt0, Elt1});
104   MI.eraseFromParent();
105   return true;
106 }
107 
108 static bool isSignExtended(Register R, MachineRegisterInfo &MRI) {
109   // TODO: check if extended build vector as well.
110   unsigned Opc = MRI.getVRegDef(R)->getOpcode();
111   return Opc == TargetOpcode::G_SEXT || Opc == TargetOpcode::G_SEXT_INREG;
112 }
113 
114 static bool isZeroExtended(Register R, MachineRegisterInfo &MRI) {
115   // TODO: check if extended build vector as well.
116   return MRI.getVRegDef(R)->getOpcode() == TargetOpcode::G_ZEXT;
117 }
118 
119 bool matchAArch64MulConstCombine(
120     MachineInstr &MI, MachineRegisterInfo &MRI,
121     std::function<void(MachineIRBuilder &B, Register DstReg)> &ApplyFn) {
122   assert(MI.getOpcode() == TargetOpcode::G_MUL);
123   Register LHS = MI.getOperand(1).getReg();
124   Register RHS = MI.getOperand(2).getReg();
125   Register Dst = MI.getOperand(0).getReg();
126   const LLT Ty = MRI.getType(LHS);
127 
128   // The below optimizations require a constant RHS.
129   auto Const = getConstantVRegValWithLookThrough(RHS, MRI);
130   if (!Const)
131     return false;
132 
133   const APInt ConstValue = Const->Value.sextOrSelf(Ty.getSizeInBits());
134   // The following code is ported from AArch64ISelLowering.
135   // Multiplication of a power of two plus/minus one can be done more
136   // cheaply as as shift+add/sub. For now, this is true unilaterally. If
137   // future CPUs have a cheaper MADD instruction, this may need to be
138   // gated on a subtarget feature. For Cyclone, 32-bit MADD is 4 cycles and
139   // 64-bit is 5 cycles, so this is always a win.
140   // More aggressively, some multiplications N0 * C can be lowered to
141   // shift+add+shift if the constant C = A * B where A = 2^N + 1 and B = 2^M,
142   // e.g. 6=3*2=(2+1)*2.
143   // TODO: consider lowering more cases, e.g. C = 14, -6, -14 or even 45
144   // which equals to (1+2)*16-(1+2).
145   // TrailingZeroes is used to test if the mul can be lowered to
146   // shift+add+shift.
147   unsigned TrailingZeroes = ConstValue.countTrailingZeros();
148   if (TrailingZeroes) {
149     // Conservatively do not lower to shift+add+shift if the mul might be
150     // folded into smul or umul.
151     if (MRI.hasOneNonDBGUse(LHS) &&
152         (isSignExtended(LHS, MRI) || isZeroExtended(LHS, MRI)))
153       return false;
154     // Conservatively do not lower to shift+add+shift if the mul might be
155     // folded into madd or msub.
156     if (MRI.hasOneNonDBGUse(Dst)) {
157       MachineInstr &UseMI = *MRI.use_instr_begin(Dst);
158       unsigned UseOpc = UseMI.getOpcode();
159       if (UseOpc == TargetOpcode::G_ADD || UseOpc == TargetOpcode::G_PTR_ADD ||
160           UseOpc == TargetOpcode::G_SUB)
161         return false;
162     }
163   }
164   // Use ShiftedConstValue instead of ConstValue to support both shift+add/sub
165   // and shift+add+shift.
166   APInt ShiftedConstValue = ConstValue.ashr(TrailingZeroes);
167 
168   unsigned ShiftAmt, AddSubOpc;
169   // Is the shifted value the LHS operand of the add/sub?
170   bool ShiftValUseIsLHS = true;
171   // Do we need to negate the result?
172   bool NegateResult = false;
173 
174   if (ConstValue.isNonNegative()) {
175     // (mul x, 2^N + 1) => (add (shl x, N), x)
176     // (mul x, 2^N - 1) => (sub (shl x, N), x)
177     // (mul x, (2^N + 1) * 2^M) => (shl (add (shl x, N), x), M)
178     APInt SCVMinus1 = ShiftedConstValue - 1;
179     APInt CVPlus1 = ConstValue + 1;
180     if (SCVMinus1.isPowerOf2()) {
181       ShiftAmt = SCVMinus1.logBase2();
182       AddSubOpc = TargetOpcode::G_ADD;
183     } else if (CVPlus1.isPowerOf2()) {
184       ShiftAmt = CVPlus1.logBase2();
185       AddSubOpc = TargetOpcode::G_SUB;
186     } else
187       return false;
188   } else {
189     // (mul x, -(2^N - 1)) => (sub x, (shl x, N))
190     // (mul x, -(2^N + 1)) => - (add (shl x, N), x)
191     APInt CVNegPlus1 = -ConstValue + 1;
192     APInt CVNegMinus1 = -ConstValue - 1;
193     if (CVNegPlus1.isPowerOf2()) {
194       ShiftAmt = CVNegPlus1.logBase2();
195       AddSubOpc = TargetOpcode::G_SUB;
196       ShiftValUseIsLHS = false;
197     } else if (CVNegMinus1.isPowerOf2()) {
198       ShiftAmt = CVNegMinus1.logBase2();
199       AddSubOpc = TargetOpcode::G_ADD;
200       NegateResult = true;
201     } else
202       return false;
203   }
204 
205   if (NegateResult && TrailingZeroes)
206     return false;
207 
208   ApplyFn = [=](MachineIRBuilder &B, Register DstReg) {
209     auto Shift = B.buildConstant(LLT::scalar(64), ShiftAmt);
210     auto ShiftedVal = B.buildShl(Ty, LHS, Shift);
211 
212     Register AddSubLHS = ShiftValUseIsLHS ? ShiftedVal.getReg(0) : LHS;
213     Register AddSubRHS = ShiftValUseIsLHS ? LHS : ShiftedVal.getReg(0);
214     auto Res = B.buildInstr(AddSubOpc, {Ty}, {AddSubLHS, AddSubRHS});
215     assert(!(NegateResult && TrailingZeroes) &&
216            "NegateResult and TrailingZeroes cannot both be true for now.");
217     // Negate the result.
218     if (NegateResult) {
219       B.buildSub(DstReg, B.buildConstant(Ty, 0), Res);
220       return;
221     }
222     // Shift the result.
223     if (TrailingZeroes) {
224       B.buildShl(DstReg, Res, B.buildConstant(LLT::scalar(64), TrailingZeroes));
225       return;
226     }
227     B.buildCopy(DstReg, Res.getReg(0));
228   };
229   return true;
230 }
231 
232 bool applyAArch64MulConstCombine(
233     MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &B,
234     std::function<void(MachineIRBuilder &B, Register DstReg)> &ApplyFn) {
235   B.setInstrAndDebugLoc(MI);
236   ApplyFn(B, MI.getOperand(0).getReg());
237   MI.eraseFromParent();
238   return true;
239 }
240 
241 #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
242 #include "AArch64GenPostLegalizeGICombiner.inc"
243 #undef AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
244 
245 namespace {
246 #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
247 #include "AArch64GenPostLegalizeGICombiner.inc"
248 #undef AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
249 
250 class AArch64PostLegalizerCombinerInfo : public CombinerInfo {
251   GISelKnownBits *KB;
252   MachineDominatorTree *MDT;
253 
254 public:
255   AArch64GenPostLegalizerCombinerHelperRuleConfig GeneratedRuleCfg;
256 
257   AArch64PostLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
258                                    GISelKnownBits *KB,
259                                    MachineDominatorTree *MDT)
260       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
261                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
262         KB(KB), MDT(MDT) {
263     if (!GeneratedRuleCfg.parseCommandLineOption())
264       report_fatal_error("Invalid rule identifier");
265   }
266 
267   virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
268                        MachineIRBuilder &B) const override;
269 };
270 
271 bool AArch64PostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
272                                                MachineInstr &MI,
273                                                MachineIRBuilder &B) const {
274   const auto *LI =
275       MI.getParent()->getParent()->getSubtarget().getLegalizerInfo();
276   CombinerHelper Helper(Observer, B, KB, MDT, LI);
277   AArch64GenPostLegalizerCombinerHelper Generated(GeneratedRuleCfg);
278   return Generated.tryCombineAll(Observer, MI, B, Helper);
279 }
280 
281 #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
282 #include "AArch64GenPostLegalizeGICombiner.inc"
283 #undef AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
284 
285 class AArch64PostLegalizerCombiner : public MachineFunctionPass {
286 public:
287   static char ID;
288 
289   AArch64PostLegalizerCombiner(bool IsOptNone = false);
290 
291   StringRef getPassName() const override {
292     return "AArch64PostLegalizerCombiner";
293   }
294 
295   bool runOnMachineFunction(MachineFunction &MF) override;
296   void getAnalysisUsage(AnalysisUsage &AU) const override;
297 
298 private:
299   bool IsOptNone;
300 };
301 } // end anonymous namespace
302 
303 void AArch64PostLegalizerCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
304   AU.addRequired<TargetPassConfig>();
305   AU.setPreservesCFG();
306   getSelectionDAGFallbackAnalysisUsage(AU);
307   AU.addRequired<GISelKnownBitsAnalysis>();
308   AU.addPreserved<GISelKnownBitsAnalysis>();
309   if (!IsOptNone) {
310     AU.addRequired<MachineDominatorTree>();
311     AU.addPreserved<MachineDominatorTree>();
312   }
313   MachineFunctionPass::getAnalysisUsage(AU);
314 }
315 
316 AArch64PostLegalizerCombiner::AArch64PostLegalizerCombiner(bool IsOptNone)
317     : MachineFunctionPass(ID), IsOptNone(IsOptNone) {
318   initializeAArch64PostLegalizerCombinerPass(*PassRegistry::getPassRegistry());
319 }
320 
321 bool AArch64PostLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
322   if (MF.getProperties().hasProperty(
323           MachineFunctionProperties::Property::FailedISel))
324     return false;
325   assert(MF.getProperties().hasProperty(
326              MachineFunctionProperties::Property::Legalized) &&
327          "Expected a legalized function?");
328   auto *TPC = &getAnalysis<TargetPassConfig>();
329   const Function &F = MF.getFunction();
330   bool EnableOpt =
331       MF.getTarget().getOptLevel() != CodeGenOpt::None && !skipFunction(F);
332   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
333   MachineDominatorTree *MDT =
334       IsOptNone ? nullptr : &getAnalysis<MachineDominatorTree>();
335   AArch64PostLegalizerCombinerInfo PCInfo(EnableOpt, F.hasOptSize(),
336                                           F.hasMinSize(), KB, MDT);
337   Combiner C(PCInfo, TPC);
338   return C.combineMachineInstrs(MF, /*CSEInfo*/ nullptr);
339 }
340 
341 char AArch64PostLegalizerCombiner::ID = 0;
342 INITIALIZE_PASS_BEGIN(AArch64PostLegalizerCombiner, DEBUG_TYPE,
343                       "Combine AArch64 MachineInstrs after legalization", false,
344                       false)
345 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
346 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
347 INITIALIZE_PASS_END(AArch64PostLegalizerCombiner, DEBUG_TYPE,
348                     "Combine AArch64 MachineInstrs after legalization", false,
349                     false)
350 
351 namespace llvm {
352 FunctionPass *createAArch64PostLegalizerCombiner(bool IsOptNone) {
353   return new AArch64PostLegalizerCombiner(IsOptNone);
354 }
355 } // end namespace llvm
356