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 
122   // Don't allow anything that could represent offsets etc.
123   if (MF.getSubtarget<AArch64Subtarget>().ClassifyGlobalReference(
124           GV, MF.getTarget()) != AArch64II::MO_NO_FLAG)
125     return false;
126 
127   // Look for a G_GLOBAL_VALUE only used by G_PTR_ADDs against constants:
128   //
129   //  %g = G_GLOBAL_VALUE @x
130   //  %ptr1 = G_PTR_ADD %g, cst1
131   //  %ptr2 = G_PTR_ADD %g, cst2
132   //  ...
133   //  %ptrN = G_PTR_ADD %g, cstN
134   //
135   // Identify the *smallest* constant. We want to be able to form this:
136   //
137   //  %offset_g = G_GLOBAL_VALUE @x + min_cst
138   //  %g = G_PTR_ADD %offset_g, -min_cst
139   //  %ptr1 = G_PTR_ADD %g, cst1
140   //  ...
141   Register Dst = MI.getOperand(0).getReg();
142   uint64_t MinOffset = -1ull;
143   for (auto &UseInstr : MRI.use_nodbg_instructions(Dst)) {
144     if (UseInstr.getOpcode() != TargetOpcode::G_PTR_ADD)
145       return false;
146     auto Cst =
147         getConstantVRegValWithLookThrough(UseInstr.getOperand(2).getReg(), MRI);
148     if (!Cst)
149       return false;
150     MinOffset = std::min(MinOffset, Cst->Value.getZExtValue());
151   }
152 
153   // Require that the new offset is larger than the existing one to avoid
154   // infinite loops.
155   uint64_t CurrOffset = GlobalOp.getOffset();
156   uint64_t NewOffset = MinOffset + CurrOffset;
157   if (NewOffset <= CurrOffset)
158     return false;
159 
160   // Check whether folding this offset is legal. It must not go out of bounds of
161   // the referenced object to avoid violating the code model, and must be
162   // smaller than 2^21 because this is the largest offset expressible in all
163   // object formats.
164   //
165   // This check also prevents us from folding negative offsets, which will end
166   // up being treated in the same way as large positive ones. They could also
167   // cause code model violations, and aren't really common enough to matter.
168   if (NewOffset >= (1 << 21))
169     return false;
170 
171   Type *T = GV->getValueType();
172   if (!T->isSized() ||
173       NewOffset > GV->getParent()->getDataLayout().getTypeAllocSize(T))
174     return false;
175   MatchInfo = std::make_pair(NewOffset, MinOffset);
176   return true;
177 }
178 
179 static bool applyFoldGlobalOffset(MachineInstr &MI, MachineRegisterInfo &MRI,
180                                   MachineIRBuilder &B,
181                                   GISelChangeObserver &Observer,
182                                   std::pair<uint64_t, uint64_t> &MatchInfo) {
183   // Change:
184   //
185   //  %g = G_GLOBAL_VALUE @x
186   //  %ptr1 = G_PTR_ADD %g, cst1
187   //  %ptr2 = G_PTR_ADD %g, cst2
188   //  ...
189   //  %ptrN = G_PTR_ADD %g, cstN
190   //
191   // To:
192   //
193   //  %offset_g = G_GLOBAL_VALUE @x + min_cst
194   //  %g = G_PTR_ADD %offset_g, -min_cst
195   //  %ptr1 = G_PTR_ADD %g, cst1
196   //  ...
197   //  %ptrN = G_PTR_ADD %g, cstN
198   //
199   // Then, the original G_PTR_ADDs should be folded later on so that they look
200   // like this:
201   //
202   //  %ptrN = G_PTR_ADD %offset_g, cstN - min_cst
203   uint64_t Offset, MinOffset;
204   std::tie(Offset, MinOffset) = MatchInfo;
205   B.setInstrAndDebugLoc(MI);
206   Observer.changingInstr(MI);
207   auto &GlobalOp = MI.getOperand(1);
208   auto *GV = GlobalOp.getGlobal();
209   GlobalOp.ChangeToGA(GV, Offset, GlobalOp.getTargetFlags());
210   Register Dst = MI.getOperand(0).getReg();
211   Register NewGVDst = MRI.cloneVirtualRegister(Dst);
212   MI.getOperand(0).setReg(NewGVDst);
213   Observer.changedInstr(MI);
214   B.buildPtrAdd(
215       Dst, NewGVDst,
216       B.buildConstant(LLT::scalar(64), -static_cast<int64_t>(MinOffset)));
217   return true;
218 }
219 
220 class AArch64PreLegalizerCombinerHelperState {
221 protected:
222   CombinerHelper &Helper;
223 
224 public:
225   AArch64PreLegalizerCombinerHelperState(CombinerHelper &Helper)
226       : Helper(Helper) {}
227 };
228 
229 #define AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
230 #include "AArch64GenPreLegalizeGICombiner.inc"
231 #undef AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_DEPS
232 
233 namespace {
234 #define AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
235 #include "AArch64GenPreLegalizeGICombiner.inc"
236 #undef AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_H
237 
238 class AArch64PreLegalizerCombinerInfo : public CombinerInfo {
239   GISelKnownBits *KB;
240   MachineDominatorTree *MDT;
241   AArch64GenPreLegalizerCombinerHelperRuleConfig GeneratedRuleCfg;
242 
243 public:
244   AArch64PreLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
245                                   GISelKnownBits *KB, MachineDominatorTree *MDT)
246       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
247                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
248         KB(KB), MDT(MDT) {
249     if (!GeneratedRuleCfg.parseCommandLineOption())
250       report_fatal_error("Invalid rule identifier");
251   }
252 
253   virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
254                        MachineIRBuilder &B) const override;
255 };
256 
257 bool AArch64PreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
258                                               MachineInstr &MI,
259                                               MachineIRBuilder &B) const {
260   CombinerHelper Helper(Observer, B, KB, MDT);
261   AArch64GenPreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper);
262 
263   if (Generated.tryCombineAll(Observer, MI, B))
264     return true;
265 
266   switch (MI.getOpcode()) {
267   case TargetOpcode::G_CONCAT_VECTORS:
268     return Helper.tryCombineConcatVectors(MI);
269   case TargetOpcode::G_SHUFFLE_VECTOR:
270     return Helper.tryCombineShuffleVector(MI);
271   case TargetOpcode::G_MEMCPY:
272   case TargetOpcode::G_MEMMOVE:
273   case TargetOpcode::G_MEMSET: {
274     // If we're at -O0 set a maxlen of 32 to inline, otherwise let the other
275     // heuristics decide.
276     unsigned MaxLen = EnableOpt ? 0 : 32;
277     // Try to inline memcpy type calls if optimizations are enabled.
278     return !EnableMinSize ? Helper.tryCombineMemCpyFamily(MI, MaxLen) : false;
279   }
280   }
281 
282   return false;
283 }
284 
285 #define AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
286 #include "AArch64GenPreLegalizeGICombiner.inc"
287 #undef AARCH64PRELEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP
288 
289 // Pass boilerplate
290 // ================
291 
292 class AArch64PreLegalizerCombiner : public MachineFunctionPass {
293 public:
294   static char ID;
295 
296   AArch64PreLegalizerCombiner(bool IsOptNone = false);
297 
298   StringRef getPassName() const override { return "AArch64PreLegalizerCombiner"; }
299 
300   bool runOnMachineFunction(MachineFunction &MF) override;
301 
302   void getAnalysisUsage(AnalysisUsage &AU) const override;
303 private:
304   bool IsOptNone;
305 };
306 } // end anonymous namespace
307 
308 void AArch64PreLegalizerCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
309   AU.addRequired<TargetPassConfig>();
310   AU.setPreservesCFG();
311   getSelectionDAGFallbackAnalysisUsage(AU);
312   AU.addRequired<GISelKnownBitsAnalysis>();
313   AU.addPreserved<GISelKnownBitsAnalysis>();
314   if (!IsOptNone) {
315     AU.addRequired<MachineDominatorTree>();
316     AU.addPreserved<MachineDominatorTree>();
317   }
318   AU.addRequired<GISelCSEAnalysisWrapperPass>();
319   AU.addPreserved<GISelCSEAnalysisWrapperPass>();
320   MachineFunctionPass::getAnalysisUsage(AU);
321 }
322 
323 AArch64PreLegalizerCombiner::AArch64PreLegalizerCombiner(bool IsOptNone)
324     : MachineFunctionPass(ID), IsOptNone(IsOptNone) {
325   initializeAArch64PreLegalizerCombinerPass(*PassRegistry::getPassRegistry());
326 }
327 
328 bool AArch64PreLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
329   if (MF.getProperties().hasProperty(
330           MachineFunctionProperties::Property::FailedISel))
331     return false;
332   auto &TPC = getAnalysis<TargetPassConfig>();
333 
334   // Enable CSE.
335   GISelCSEAnalysisWrapper &Wrapper =
336       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
337   auto *CSEInfo = &Wrapper.get(TPC.getCSEConfig());
338 
339   const Function &F = MF.getFunction();
340   bool EnableOpt =
341       MF.getTarget().getOptLevel() != CodeGenOpt::None && !skipFunction(F);
342   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
343   MachineDominatorTree *MDT =
344       IsOptNone ? nullptr : &getAnalysis<MachineDominatorTree>();
345   AArch64PreLegalizerCombinerInfo PCInfo(EnableOpt, F.hasOptSize(),
346                                          F.hasMinSize(), KB, MDT);
347   Combiner C(PCInfo, &TPC);
348   return C.combineMachineInstrs(MF, CSEInfo);
349 }
350 
351 char AArch64PreLegalizerCombiner::ID = 0;
352 INITIALIZE_PASS_BEGIN(AArch64PreLegalizerCombiner, DEBUG_TYPE,
353                       "Combine AArch64 machine instrs before legalization",
354                       false, false)
355 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
356 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
357 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
358 INITIALIZE_PASS_END(AArch64PreLegalizerCombiner, DEBUG_TYPE,
359                     "Combine AArch64 machine instrs before legalization", false,
360                     false)
361 
362 
363 namespace llvm {
364 FunctionPass *createAArch64PreLegalizerCombiner(bool IsOptNone) {
365   return new AArch64PreLegalizerCombiner(IsOptNone);
366 }
367 } // end namespace llvm
368