1 //=== lib/CodeGen/GlobalISel/AArch64PreLegalizerCombiner.cpp --------------===//
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 does combining of machine instructions at the generic MI level,
10 // before the legalizer.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "AArch64TargetMachine.h"
15 #include "llvm/CodeGen/GlobalISel/Combiner.h"
16 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
17 #include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
18 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
19 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
20 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
21 #include "llvm/CodeGen/MachineDominators.h"
22 #include "llvm/CodeGen/MachineFunction.h"
23 #include "llvm/CodeGen/MachineFunctionPass.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/TargetPassConfig.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/Support/Debug.h"
28 
29 #define DEBUG_TYPE "aarch64-prelegalizer-combiner"
30 
31 using namespace llvm;
32 using namespace MIPatternMatch;
33 
34 /// Return true if a G_FCONSTANT instruction is known to be better-represented
35 /// as a G_CONSTANT.
36 static bool matchFConstantToConstant(MachineInstr &MI,
37                                      MachineRegisterInfo &MRI) {
38   assert(MI.getOpcode() == TargetOpcode::G_FCONSTANT);
39   Register DstReg = MI.getOperand(0).getReg();
40   const unsigned DstSize = MRI.getType(DstReg).getSizeInBits();
41   if (DstSize != 32 && DstSize != 64)
42     return false;
43 
44   // When we're storing a value, it doesn't matter what register bank it's on.
45   // Since not all floating point constants can be materialized using a fmov,
46   // it makes more sense to just use a GPR.
47   return all_of(MRI.use_nodbg_instructions(DstReg),
48                 [](const MachineInstr &Use) { return Use.mayStore(); });
49 }
50 
51 /// Change a G_FCONSTANT into a G_CONSTANT.
52 static void applyFConstantToConstant(MachineInstr &MI) {
53   assert(MI.getOpcode() == TargetOpcode::G_FCONSTANT);
54   MachineIRBuilder MIB(MI);
55   const APFloat &ImmValAPF = MI.getOperand(1).getFPImm()->getValueAPF();
56   MIB.buildConstant(MI.getOperand(0).getReg(), ImmValAPF.bitcastToAPInt());
57   MI.eraseFromParent();
58 }
59 
60 /// Try to match a G_ICMP of a G_TRUNC with zero, in which the truncated bits
61 /// are sign bits. In this case, we can transform the G_ICMP to directly compare
62 /// the wide value with a zero.
63 static bool matchICmpRedundantTrunc(MachineInstr &MI, MachineRegisterInfo &MRI,
64                                     GISelKnownBits *KB, Register &MatchInfo) {
65   assert(MI.getOpcode() == TargetOpcode::G_ICMP && KB);
66 
67   auto Pred = (CmpInst::Predicate)MI.getOperand(1).getPredicate();
68   if (!ICmpInst::isEquality(Pred))
69     return false;
70 
71   Register LHS = MI.getOperand(2).getReg();
72   LLT LHSTy = MRI.getType(LHS);
73   if (!LHSTy.isScalar())
74     return false;
75 
76   Register RHS = MI.getOperand(3).getReg();
77   Register WideReg;
78 
79   if (!mi_match(LHS, MRI, m_GTrunc(m_Reg(WideReg))) ||
80       !mi_match(RHS, MRI, m_SpecificICst(0)))
81     return false;
82 
83   LLT WideTy = MRI.getType(WideReg);
84   if (KB->computeNumSignBits(WideReg) <=
85       WideTy.getSizeInBits() - LHSTy.getSizeInBits())
86     return false;
87 
88   MatchInfo = WideReg;
89   return true;
90 }
91 
92 static bool applyICmpRedundantTrunc(MachineInstr &MI, MachineRegisterInfo &MRI,
93                                     MachineIRBuilder &Builder,
94                                     GISelChangeObserver &Observer,
95                                     Register &WideReg) {
96   assert(MI.getOpcode() == TargetOpcode::G_ICMP);
97 
98   LLT WideTy = MRI.getType(WideReg);
99   // We're going to directly use the wide register as the LHS, and then use an
100   // equivalent size zero for RHS.
101   Builder.setInstrAndDebugLoc(MI);
102   auto WideZero = Builder.buildConstant(WideTy, 0);
103   Observer.changingInstr(MI);
104   MI.getOperand(2).setReg(WideReg);
105   MI.getOperand(3).setReg(WideZero.getReg(0));
106   Observer.changedInstr(MI);
107   return true;
108 }
109 
110 /// \returns true if it is possible to fold a constant into a G_GLOBAL_VALUE.
111 ///
112 /// e.g.
113 ///
114 /// %g = G_GLOBAL_VALUE @x -> %g = G_GLOBAL_VALUE @x + cst
115 static bool matchFoldGlobalOffset(MachineInstr &MI, MachineRegisterInfo &MRI,
116                                   std::pair<uint64_t, uint64_t> &MatchInfo) {
117   assert(MI.getOpcode() == TargetOpcode::G_GLOBAL_VALUE);
118   MachineFunction &MF = *MI.getMF();
119   auto &GlobalOp = MI.getOperand(1);
120   auto *GV = GlobalOp.getGlobal();
121   if (GV->isThreadLocal())
122     return false;
123 
124   // Don't allow anything that could represent offsets etc.
125   if (MF.getSubtarget<AArch64Subtarget>().ClassifyGlobalReference(
126           GV, MF.getTarget()) != AArch64II::MO_NO_FLAG)
127     return false;
128 
129   // Look for a G_GLOBAL_VALUE only used by G_PTR_ADDs against constants:
130   //
131   //  %g = G_GLOBAL_VALUE @x
132   //  %ptr1 = G_PTR_ADD %g, cst1
133   //  %ptr2 = G_PTR_ADD %g, cst2
134   //  ...
135   //  %ptrN = G_PTR_ADD %g, cstN
136   //
137   // Identify the *smallest* constant. We want to be able to form this:
138   //
139   //  %offset_g = G_GLOBAL_VALUE @x + min_cst
140   //  %g = G_PTR_ADD %offset_g, -min_cst
141   //  %ptr1 = G_PTR_ADD %g, cst1
142   //  ...
143   Register Dst = MI.getOperand(0).getReg();
144   uint64_t MinOffset = -1ull;
145   for (auto &UseInstr : MRI.use_nodbg_instructions(Dst)) {
146     if (UseInstr.getOpcode() != TargetOpcode::G_PTR_ADD)
147       return false;
148     auto Cst =
149         getConstantVRegValWithLookThrough(UseInstr.getOperand(2).getReg(), MRI);
150     if (!Cst)
151       return false;
152     MinOffset = std::min(MinOffset, Cst->Value.getZExtValue());
153   }
154 
155   // Require that the new offset is larger than the existing one to avoid
156   // infinite loops.
157   uint64_t CurrOffset = GlobalOp.getOffset();
158   uint64_t NewOffset = MinOffset + CurrOffset;
159   if (NewOffset <= CurrOffset)
160     return false;
161 
162   // Check whether folding this offset is legal. It must not go out of bounds of
163   // the referenced object to avoid violating the code model, and must be
164   // smaller than 2^21 because this is the largest offset expressible in all
165   // object formats.
166   //
167   // This check also prevents us from folding negative offsets, which will end
168   // up being treated in the same way as large positive ones. They could also
169   // cause code model violations, and aren't really common enough to matter.
170   if (NewOffset >= (1 << 21))
171     return false;
172 
173   Type *T = GV->getValueType();
174   if (!T->isSized() ||
175       NewOffset > GV->getParent()->getDataLayout().getTypeAllocSize(T))
176     return false;
177   MatchInfo = std::make_pair(NewOffset, MinOffset);
178   return true;
179 }
180 
181 static bool applyFoldGlobalOffset(MachineInstr &MI, MachineRegisterInfo &MRI,
182                                   MachineIRBuilder &B,
183                                   GISelChangeObserver &Observer,
184                                   std::pair<uint64_t, uint64_t> &MatchInfo) {
185   // Change:
186   //
187   //  %g = G_GLOBAL_VALUE @x
188   //  %ptr1 = G_PTR_ADD %g, cst1
189   //  %ptr2 = G_PTR_ADD %g, cst2
190   //  ...
191   //  %ptrN = G_PTR_ADD %g, cstN
192   //
193   // To:
194   //
195   //  %offset_g = G_GLOBAL_VALUE @x + min_cst
196   //  %g = G_PTR_ADD %offset_g, -min_cst
197   //  %ptr1 = G_PTR_ADD %g, cst1
198   //  ...
199   //  %ptrN = G_PTR_ADD %g, cstN
200   //
201   // Then, the original G_PTR_ADDs should be folded later on so that they look
202   // like this:
203   //
204   //  %ptrN = G_PTR_ADD %offset_g, cstN - min_cst
205   uint64_t Offset, MinOffset;
206   std::tie(Offset, MinOffset) = MatchInfo;
207   B.setInstrAndDebugLoc(MI);
208   Observer.changingInstr(MI);
209   auto &GlobalOp = MI.getOperand(1);
210   auto *GV = GlobalOp.getGlobal();
211   GlobalOp.ChangeToGA(GV, Offset, GlobalOp.getTargetFlags());
212   Register Dst = MI.getOperand(0).getReg();
213   Register NewGVDst = MRI.cloneVirtualRegister(Dst);
214   MI.getOperand(0).setReg(NewGVDst);
215   Observer.changedInstr(MI);
216   B.buildPtrAdd(
217       Dst, NewGVDst,
218       B.buildConstant(LLT::scalar(64), -static_cast<int64_t>(MinOffset)));
219   return true;
220 }
221 
222 /// Replace a G_MEMSET with a value of 0 with a G_BZERO instruction if it is
223 /// supported and beneficial to do so.
224 ///
225 /// \note This only applies on Darwin.
226 ///
227 /// \returns true if \p MI was replaced with a G_BZERO.
228 static bool tryEmitBZero(MachineInstr &MI, MachineIRBuilder &MIRBuilder,
229                          bool MinSize) {
230   assert(MI.getOpcode() == TargetOpcode::G_MEMSET);
231   MachineRegisterInfo &MRI = *MIRBuilder.getMRI();
232   auto &TLI = *MIRBuilder.getMF().getSubtarget().getTargetLowering();
233   if (!TLI.getLibcallName(RTLIB::BZERO))
234     return false;
235   auto Zero = getConstantVRegValWithLookThrough(MI.getOperand(1).getReg(), MRI);
236   if (!Zero || Zero->Value.getSExtValue() != 0)
237     return false;
238 
239   // It's not faster to use bzero rather than memset for sizes <= 256.
240   // However, it *does* save us a mov from wzr, so if we're going for
241   // minsize, use bzero even if it's slower.
242   if (!MinSize) {
243     // If the size is known, check it. If it is not known, assume using bzero is
244     // better.
245     if (auto Size =
246             getConstantVRegValWithLookThrough(MI.getOperand(2).getReg(), MRI)) {
247       if (Size->Value.getSExtValue() <= 256)
248         return false;
249     }
250   }
251 
252   MIRBuilder.setInstrAndDebugLoc(MI);
253   MIRBuilder
254       .buildInstr(TargetOpcode::G_BZERO, {},
255                   {MI.getOperand(0), MI.getOperand(2)})
256       .addImm(MI.getOperand(3).getImm())
257       .addMemOperand(*MI.memoperands_begin());
258   MI.eraseFromParent();
259   return true;
260 }
261 
262 class AArch64PreLegalizerCombinerHelperState {
263 protected:
264   CombinerHelper &Helper;
265 
266 public:
267   AArch64PreLegalizerCombinerHelperState(CombinerHelper &Helper)
268       : Helper(Helper) {}
269 };
270 
271 #define AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
272 #include "AArch64GenPreLegalizeGICombiner.inc"
273 #undef AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
274 
275 namespace {
276 #define AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
277 #include "AArch64GenPreLegalizeGICombiner.inc"
278 #undef AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
279 
280 class AArch64PreLegalizerCombinerInfo : public CombinerInfo {
281   GISelKnownBits *KB;
282   MachineDominatorTree *MDT;
283   AArch64GenPreLegalizerCombinerHelperRuleConfig GeneratedRuleCfg;
284 
285 public:
286   AArch64PreLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
287                                   GISelKnownBits *KB, MachineDominatorTree *MDT)
288       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
289                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
290         KB(KB), MDT(MDT) {
291     if (!GeneratedRuleCfg.parseCommandLineOption())
292       report_fatal_error("Invalid rule identifier");
293   }
294 
295   virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
296                        MachineIRBuilder &B) const override;
297 };
298 
299 bool AArch64PreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
300                                               MachineInstr &MI,
301                                               MachineIRBuilder &B) const {
302   CombinerHelper Helper(Observer, B, KB, MDT);
303   AArch64GenPreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper);
304 
305   if (Generated.tryCombineAll(Observer, MI, B))
306     return true;
307 
308   unsigned Opc = MI.getOpcode();
309   switch (Opc) {
310   case TargetOpcode::G_CONCAT_VECTORS:
311     return Helper.tryCombineConcatVectors(MI);
312   case TargetOpcode::G_SHUFFLE_VECTOR:
313     return Helper.tryCombineShuffleVector(MI);
314   case TargetOpcode::G_MEMCPY:
315   case TargetOpcode::G_MEMMOVE:
316   case TargetOpcode::G_MEMSET: {
317     // If we're at -O0 set a maxlen of 32 to inline, otherwise let the other
318     // heuristics decide.
319     unsigned MaxLen = EnableOpt ? 0 : 32;
320     // Try to inline memcpy type calls if optimizations are enabled.
321     if (!EnableMinSize && Helper.tryCombineMemCpyFamily(MI, MaxLen))
322       return true;
323     if (Opc == TargetOpcode::G_MEMSET)
324       return tryEmitBZero(MI, B, EnableMinSize);
325     return false;
326   }
327   }
328 
329   return false;
330 }
331 
332 #define AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
333 #include "AArch64GenPreLegalizeGICombiner.inc"
334 #undef AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
335 
336 // Pass boilerplate
337 // ================
338 
339 class AArch64PreLegalizerCombiner : public MachineFunctionPass {
340 public:
341   static char ID;
342 
343   AArch64PreLegalizerCombiner(bool IsOptNone = false);
344 
345   StringRef getPassName() const override { return "AArch64PreLegalizerCombiner"; }
346 
347   bool runOnMachineFunction(MachineFunction &MF) override;
348 
349   void getAnalysisUsage(AnalysisUsage &AU) const override;
350 private:
351   bool IsOptNone;
352 };
353 } // end anonymous namespace
354 
355 void AArch64PreLegalizerCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
356   AU.addRequired<TargetPassConfig>();
357   AU.setPreservesCFG();
358   getSelectionDAGFallbackAnalysisUsage(AU);
359   AU.addRequired<GISelKnownBitsAnalysis>();
360   AU.addPreserved<GISelKnownBitsAnalysis>();
361   if (!IsOptNone) {
362     AU.addRequired<MachineDominatorTree>();
363     AU.addPreserved<MachineDominatorTree>();
364   }
365   AU.addRequired<GISelCSEAnalysisWrapperPass>();
366   AU.addPreserved<GISelCSEAnalysisWrapperPass>();
367   MachineFunctionPass::getAnalysisUsage(AU);
368 }
369 
370 AArch64PreLegalizerCombiner::AArch64PreLegalizerCombiner(bool IsOptNone)
371     : MachineFunctionPass(ID), IsOptNone(IsOptNone) {
372   initializeAArch64PreLegalizerCombinerPass(*PassRegistry::getPassRegistry());
373 }
374 
375 bool AArch64PreLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
376   if (MF.getProperties().hasProperty(
377           MachineFunctionProperties::Property::FailedISel))
378     return false;
379   auto &TPC = getAnalysis<TargetPassConfig>();
380 
381   // Enable CSE.
382   GISelCSEAnalysisWrapper &Wrapper =
383       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
384   auto *CSEInfo = &Wrapper.get(TPC.getCSEConfig());
385 
386   const Function &F = MF.getFunction();
387   bool EnableOpt =
388       MF.getTarget().getOptLevel() != CodeGenOpt::None && !skipFunction(F);
389   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
390   MachineDominatorTree *MDT =
391       IsOptNone ? nullptr : &getAnalysis<MachineDominatorTree>();
392   AArch64PreLegalizerCombinerInfo PCInfo(EnableOpt, F.hasOptSize(),
393                                          F.hasMinSize(), KB, MDT);
394   Combiner C(PCInfo, &TPC);
395   return C.combineMachineInstrs(MF, CSEInfo);
396 }
397 
398 char AArch64PreLegalizerCombiner::ID = 0;
399 INITIALIZE_PASS_BEGIN(AArch64PreLegalizerCombiner, DEBUG_TYPE,
400                       "Combine AArch64 machine instrs before legalization",
401                       false, false)
402 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
403 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
404 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
405 INITIALIZE_PASS_END(AArch64PreLegalizerCombiner, DEBUG_TYPE,
406                     "Combine AArch64 machine instrs before legalization", false,
407                     false)
408 
409 
410 namespace llvm {
411 FunctionPass *createAArch64PreLegalizerCombiner(bool IsOptNone) {
412   return new AArch64PreLegalizerCombiner(IsOptNone);
413 }
414 } // end namespace llvm
415