1 //===- PatternMatchTest.cpp -----------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/CodeGen/GlobalISel/ConstantFoldingMIRBuilder.h"
11 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
12 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
13 #include "llvm/CodeGen/GlobalISel/Utils.h"
14 #include "llvm/CodeGen/MIRParser/MIRParser.h"
15 #include "llvm/CodeGen/MachineFunction.h"
16 #include "llvm/CodeGen/MachineModuleInfo.h"
17 #include "llvm/CodeGen/TargetFrameLowering.h"
18 #include "llvm/CodeGen/TargetInstrInfo.h"
19 #include "llvm/CodeGen/TargetLowering.h"
20 #include "llvm/CodeGen/TargetSubtargetInfo.h"
21 #include "llvm/Support/SourceMgr.h"
22 #include "llvm/Support/TargetRegistry.h"
23 #include "llvm/Support/TargetSelect.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Target/TargetOptions.h"
26 #include "gtest/gtest.h"
27 
28 using namespace llvm;
29 using namespace MIPatternMatch;
30 
31 namespace {
32 
33 void initLLVM() {
34   InitializeAllTargets();
35   InitializeAllTargetMCs();
36   InitializeAllAsmPrinters();
37   InitializeAllAsmParsers();
38 
39   PassRegistry *Registry = PassRegistry::getPassRegistry();
40   initializeCore(*Registry);
41   initializeCodeGen(*Registry);
42 }
43 
44 /// Create a TargetMachine. As we lack a dedicated always available target for
45 /// unittests, we go for "AArch64".
46 std::unique_ptr<TargetMachine> createTargetMachine() {
47   Triple TargetTriple("aarch64--");
48   std::string Error;
49   const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
50   if (!T)
51     return nullptr;
52 
53   TargetOptions Options;
54   return std::unique_ptr<TargetMachine>(T->createTargetMachine(
55       "AArch64", "", "", Options, None, None, CodeGenOpt::Aggressive));
56 }
57 
58 std::unique_ptr<Module> parseMIR(LLVMContext &Context,
59                                  std::unique_ptr<MIRParser> &MIR,
60                                  const TargetMachine &TM, StringRef MIRCode,
61                                  const char *FuncName, MachineModuleInfo &MMI) {
62   SMDiagnostic Diagnostic;
63   std::unique_ptr<MemoryBuffer> MBuffer = MemoryBuffer::getMemBuffer(MIRCode);
64   MIR = createMIRParser(std::move(MBuffer), Context);
65   if (!MIR)
66     return nullptr;
67 
68   std::unique_ptr<Module> M = MIR->parseIRModule();
69   if (!M)
70     return nullptr;
71 
72   M->setDataLayout(TM.createDataLayout());
73 
74   if (MIR->parseMachineFunctions(*M, MMI))
75     return nullptr;
76 
77   return M;
78 }
79 
80 std::pair<std::unique_ptr<Module>, std::unique_ptr<MachineModuleInfo>>
81 createDummyModule(LLVMContext &Context, const TargetMachine &TM,
82                   StringRef MIRFunc) {
83   SmallString<512> S;
84   StringRef MIRString = (Twine(R"MIR(
85 ---
86 ...
87 name: func
88 registers:
89   - { id: 0, class: _ }
90   - { id: 1, class: _ }
91   - { id: 2, class: _ }
92   - { id: 3, class: _ }
93 body: |
94   bb.1:
95     %0(s64) = COPY $x0
96     %1(s64) = COPY $x1
97     %2(s64) = COPY $x2
98 )MIR") + Twine(MIRFunc) + Twine("...\n"))
99                             .toNullTerminatedStringRef(S);
100   std::unique_ptr<MIRParser> MIR;
101   auto MMI = make_unique<MachineModuleInfo>(&TM);
102   std::unique_ptr<Module> M =
103       parseMIR(Context, MIR, TM, MIRString, "func", *MMI);
104   return make_pair(std::move(M), std::move(MMI));
105 }
106 
107 static MachineFunction *getMFFromMMI(const Module *M,
108                                      const MachineModuleInfo *MMI) {
109   Function *F = M->getFunction("func");
110   auto *MF = MMI->getMachineFunction(*F);
111   return MF;
112 }
113 
114 static void collectCopies(SmallVectorImpl<unsigned> &Copies,
115                           MachineFunction *MF) {
116   for (auto &MBB : *MF)
117     for (MachineInstr &MI : MBB) {
118       if (MI.getOpcode() == TargetOpcode::COPY)
119         Copies.push_back(MI.getOperand(0).getReg());
120     }
121 }
122 
123 TEST(PatternMatchInstr, MatchIntConstant) {
124   LLVMContext Context;
125   std::unique_ptr<TargetMachine> TM = createTargetMachine();
126   if (!TM)
127     return;
128   auto ModuleMMIPair = createDummyModule(Context, *TM, "");
129   MachineFunction *MF =
130       getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
131   SmallVector<unsigned, 4> Copies;
132   collectCopies(Copies, MF);
133   MachineBasicBlock *EntryMBB = &*MF->begin();
134   MachineIRBuilder B(*MF);
135   MachineRegisterInfo &MRI = MF->getRegInfo();
136   B.setInsertPt(*EntryMBB, EntryMBB->end());
137   auto MIBCst = B.buildConstant(LLT::scalar(64), 42);
138   int64_t Cst;
139   bool match = mi_match(MIBCst->getOperand(0).getReg(), MRI, m_ICst(Cst));
140   ASSERT_TRUE(match);
141   ASSERT_EQ(Cst, 42);
142 }
143 
144 TEST(PatternMatchInstr, MatchBinaryOp) {
145   LLVMContext Context;
146   std::unique_ptr<TargetMachine> TM = createTargetMachine();
147   if (!TM)
148     return;
149   auto ModuleMMIPair = createDummyModule(Context, *TM, "");
150   MachineFunction *MF =
151       getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
152   SmallVector<unsigned, 4> Copies;
153   collectCopies(Copies, MF);
154   MachineBasicBlock *EntryMBB = &*MF->begin();
155   MachineIRBuilder B(*MF);
156   MachineRegisterInfo &MRI = MF->getRegInfo();
157   B.setInsertPt(*EntryMBB, EntryMBB->end());
158   LLT s64 = LLT::scalar(64);
159   auto MIBAdd = B.buildAdd(s64, Copies[0], Copies[1]);
160   // Test case for no bind.
161   bool match =
162       mi_match(MIBAdd->getOperand(0).getReg(), MRI, m_GAdd(m_Reg(), m_Reg()));
163   ASSERT_TRUE(match);
164   unsigned Src0, Src1, Src2;
165   match = mi_match(MIBAdd->getOperand(0).getReg(), MRI,
166                    m_GAdd(m_Reg(Src0), m_Reg(Src1)));
167   ASSERT_TRUE(match);
168   ASSERT_EQ(Src0, Copies[0]);
169   ASSERT_EQ(Src1, Copies[1]);
170 
171   // Build MUL(ADD %0, %1), %2
172   auto MIBMul = B.buildMul(s64, MIBAdd, Copies[2]);
173 
174   // Try to match MUL.
175   match = mi_match(MIBMul->getOperand(0).getReg(), MRI,
176                    m_GMul(m_Reg(Src0), m_Reg(Src1)));
177   ASSERT_TRUE(match);
178   ASSERT_EQ(Src0, MIBAdd->getOperand(0).getReg());
179   ASSERT_EQ(Src1, Copies[2]);
180 
181   // Try to match MUL(ADD)
182   match = mi_match(MIBMul->getOperand(0).getReg(), MRI,
183                    m_GMul(m_GAdd(m_Reg(Src0), m_Reg(Src1)), m_Reg(Src2)));
184   ASSERT_TRUE(match);
185   ASSERT_EQ(Src0, Copies[0]);
186   ASSERT_EQ(Src1, Copies[1]);
187   ASSERT_EQ(Src2, Copies[2]);
188 
189   // Test Commutativity.
190   auto MIBMul2 = B.buildMul(s64, Copies[0], B.buildConstant(s64, 42));
191   // Try to match MUL(Cst, Reg) on src of MUL(Reg, Cst) to validate
192   // commutativity.
193   int64_t Cst;
194   match = mi_match(MIBMul2->getOperand(0).getReg(), MRI,
195                    m_GMul(m_ICst(Cst), m_Reg(Src0)));
196   ASSERT_TRUE(match);
197   ASSERT_EQ(Cst, 42);
198   ASSERT_EQ(Src0, Copies[0]);
199 
200   // Make sure commutative doesn't work with something like SUB.
201   auto MIBSub = B.buildSub(s64, Copies[0], B.buildConstant(s64, 42));
202   match = mi_match(MIBSub->getOperand(0).getReg(), MRI,
203                    m_GSub(m_ICst(Cst), m_Reg(Src0)));
204   ASSERT_FALSE(match);
205 
206   auto MIBFMul = B.buildInstr(TargetOpcode::G_FMUL, s64, Copies[0],
207                               B.buildConstant(s64, 42));
208   // Match and test commutativity for FMUL.
209   match = mi_match(MIBFMul->getOperand(0).getReg(), MRI,
210                    m_GFMul(m_ICst(Cst), m_Reg(Src0)));
211   ASSERT_TRUE(match);
212   ASSERT_EQ(Cst, 42);
213   ASSERT_EQ(Src0, Copies[0]);
214 
215   // FSUB
216   auto MIBFSub = B.buildInstr(TargetOpcode::G_FSUB, s64, Copies[0],
217                               B.buildConstant(s64, 42));
218   match = mi_match(MIBFSub->getOperand(0).getReg(), MRI,
219                    m_GFSub(m_Reg(Src0), m_Reg()));
220   ASSERT_TRUE(match);
221   ASSERT_EQ(Src0, Copies[0]);
222 
223   // Build AND %0, %1
224   auto MIBAnd = B.buildAnd(s64, Copies[0], Copies[1]);
225   // Try to match AND.
226   match = mi_match(MIBAnd->getOperand(0).getReg(), MRI,
227                    m_GAnd(m_Reg(Src0), m_Reg(Src1)));
228   ASSERT_TRUE(match);
229   ASSERT_EQ(Src0, Copies[0]);
230   ASSERT_EQ(Src1, Copies[1]);
231 
232   // Build OR %0, %1
233   auto MIBOr = B.buildOr(s64, Copies[0], Copies[1]);
234   // Try to match OR.
235   match = mi_match(MIBOr->getOperand(0).getReg(), MRI,
236                    m_GOr(m_Reg(Src0), m_Reg(Src1)));
237   ASSERT_TRUE(match);
238   ASSERT_EQ(Src0, Copies[0]);
239   ASSERT_EQ(Src1, Copies[1]);
240 
241   // Try to use the FoldableInstructionsBuilder to build binary ops.
242   ConstantFoldingMIRBuilder CFB(B.getState());
243   LLT s32 = LLT::scalar(32);
244   auto MIBCAdd =
245       CFB.buildAdd(s32, CFB.buildConstant(s32, 0), CFB.buildConstant(s32, 1));
246   // This should be a constant now.
247   match = mi_match(MIBCAdd->getOperand(0).getReg(), MRI, m_ICst(Cst));
248   ASSERT_TRUE(match);
249   ASSERT_EQ(Cst, 1);
250   auto MIBCAdd1 =
251       CFB.buildInstr(TargetOpcode::G_ADD, s32, CFB.buildConstant(s32, 0),
252                      CFB.buildConstant(s32, 1));
253   // This should be a constant now.
254   match = mi_match(MIBCAdd1->getOperand(0).getReg(), MRI, m_ICst(Cst));
255   ASSERT_TRUE(match);
256   ASSERT_EQ(Cst, 1);
257 
258   // Try one of the other constructors of MachineIRBuilder to make sure it's
259   // compatible.
260   ConstantFoldingMIRBuilder CFB1(*MF);
261   CFB1.setInsertPt(*EntryMBB, EntryMBB->end());
262   auto MIBCSub =
263       CFB1.buildInstr(TargetOpcode::G_SUB, s32, CFB1.buildConstant(s32, 1),
264                       CFB1.buildConstant(s32, 1));
265   // This should be a constant now.
266   match = mi_match(MIBCSub->getOperand(0).getReg(), MRI, m_ICst(Cst));
267   ASSERT_TRUE(match);
268   ASSERT_EQ(Cst, 0);
269 }
270 
271 TEST(PatternMatchInstr, MatchFPUnaryOp) {
272   LLVMContext Context;
273   std::unique_ptr<TargetMachine> TM = createTargetMachine();
274   if (!TM)
275     return;
276   auto ModuleMMIPair = createDummyModule(Context, *TM, "");
277   MachineFunction *MF =
278       getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
279   SmallVector<unsigned, 4> Copies;
280   collectCopies(Copies, MF);
281   MachineBasicBlock *EntryMBB = &*MF->begin();
282   MachineIRBuilder B(*MF);
283   MachineRegisterInfo &MRI = MF->getRegInfo();
284   B.setInsertPt(*EntryMBB, EntryMBB->end());
285 
286   // Truncate s64 to s32.
287   LLT s32 = LLT::scalar(32);
288   auto Copy0s32 = B.buildFPTrunc(s32, Copies[0]);
289 
290   // Match G_FABS.
291   auto MIBFabs = B.buildInstr(TargetOpcode::G_FABS, s32, Copy0s32);
292   bool match = mi_match(MIBFabs->getOperand(0).getReg(), MRI, m_GFabs(m_Reg()));
293   ASSERT_TRUE(match);
294 
295   unsigned Src;
296   auto MIBFNeg = B.buildInstr(TargetOpcode::G_FNEG, s32, Copy0s32);
297   match = mi_match(MIBFNeg->getOperand(0).getReg(), MRI, m_GFNeg(m_Reg(Src)));
298   ASSERT_TRUE(match);
299   ASSERT_EQ(Src, Copy0s32->getOperand(0).getReg());
300 
301   match = mi_match(MIBFabs->getOperand(0).getReg(), MRI, m_GFabs(m_Reg(Src)));
302   ASSERT_TRUE(match);
303   ASSERT_EQ(Src, Copy0s32->getOperand(0).getReg());
304 
305   // Build and match FConstant.
306   auto MIBFCst = B.buildFConstant(s32, .5);
307   const ConstantFP *TmpFP{};
308   match = mi_match(MIBFCst->getOperand(0).getReg(), MRI, m_GFCst(TmpFP));
309   ASSERT_TRUE(match);
310   ASSERT_TRUE(TmpFP);
311   APFloat APF((float).5);
312   auto *CFP = ConstantFP::get(Context, APF);
313   ASSERT_EQ(CFP, TmpFP);
314 
315   // Build double float.
316   LLT s64 = LLT::scalar(64);
317   auto MIBFCst64 = B.buildFConstant(s64, .5);
318   const ConstantFP *TmpFP64{};
319   match = mi_match(MIBFCst64->getOperand(0).getReg(), MRI, m_GFCst(TmpFP64));
320   ASSERT_TRUE(match);
321   ASSERT_TRUE(TmpFP64);
322   APFloat APF64(.5);
323   auto CFP64 = ConstantFP::get(Context, APF64);
324   ASSERT_EQ(CFP64, TmpFP64);
325   ASSERT_NE(TmpFP64, TmpFP);
326 
327   // Build half float.
328   LLT s16 = LLT::scalar(16);
329   auto MIBFCst16 = B.buildFConstant(s16, .5);
330   const ConstantFP *TmpFP16{};
331   match = mi_match(MIBFCst16->getOperand(0).getReg(), MRI, m_GFCst(TmpFP16));
332   ASSERT_TRUE(match);
333   ASSERT_TRUE(TmpFP16);
334   bool Ignored;
335   APFloat APF16(.5);
336   APF16.convert(APFloat::IEEEhalf(), APFloat::rmNearestTiesToEven, &Ignored);
337   auto CFP16 = ConstantFP::get(Context, APF16);
338   ASSERT_EQ(TmpFP16, CFP16);
339   ASSERT_NE(TmpFP16, TmpFP);
340 }
341 
342 TEST(PatternMatchInstr, MatchExtendsTrunc) {
343   LLVMContext Context;
344   std::unique_ptr<TargetMachine> TM = createTargetMachine();
345   if (!TM)
346     return;
347   auto ModuleMMIPair = createDummyModule(Context, *TM, "");
348   MachineFunction *MF =
349       getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
350   SmallVector<unsigned, 4> Copies;
351   collectCopies(Copies, MF);
352   MachineBasicBlock *EntryMBB = &*MF->begin();
353   MachineIRBuilder B(*MF);
354   MachineRegisterInfo &MRI = MF->getRegInfo();
355   B.setInsertPt(*EntryMBB, EntryMBB->end());
356   LLT s64 = LLT::scalar(64);
357   LLT s32 = LLT::scalar(32);
358 
359   auto MIBTrunc = B.buildTrunc(s32, Copies[0]);
360   auto MIBAExt = B.buildAnyExt(s64, MIBTrunc);
361   auto MIBZExt = B.buildZExt(s64, MIBTrunc);
362   auto MIBSExt = B.buildSExt(s64, MIBTrunc);
363   unsigned Src0;
364   bool match =
365       mi_match(MIBTrunc->getOperand(0).getReg(), MRI, m_GTrunc(m_Reg(Src0)));
366   ASSERT_TRUE(match);
367   ASSERT_EQ(Src0, Copies[0]);
368   match =
369       mi_match(MIBAExt->getOperand(0).getReg(), MRI, m_GAnyExt(m_Reg(Src0)));
370   ASSERT_TRUE(match);
371   ASSERT_EQ(Src0, MIBTrunc->getOperand(0).getReg());
372 
373   match = mi_match(MIBSExt->getOperand(0).getReg(), MRI, m_GSExt(m_Reg(Src0)));
374   ASSERT_TRUE(match);
375   ASSERT_EQ(Src0, MIBTrunc->getOperand(0).getReg());
376 
377   match = mi_match(MIBZExt->getOperand(0).getReg(), MRI, m_GZExt(m_Reg(Src0)));
378   ASSERT_TRUE(match);
379   ASSERT_EQ(Src0, MIBTrunc->getOperand(0).getReg());
380 
381   // Match ext(trunc src)
382   match = mi_match(MIBAExt->getOperand(0).getReg(), MRI,
383                    m_GAnyExt(m_GTrunc(m_Reg(Src0))));
384   ASSERT_TRUE(match);
385   ASSERT_EQ(Src0, Copies[0]);
386 
387   match = mi_match(MIBSExt->getOperand(0).getReg(), MRI,
388                    m_GSExt(m_GTrunc(m_Reg(Src0))));
389   ASSERT_TRUE(match);
390   ASSERT_EQ(Src0, Copies[0]);
391 
392   match = mi_match(MIBZExt->getOperand(0).getReg(), MRI,
393                    m_GZExt(m_GTrunc(m_Reg(Src0))));
394   ASSERT_TRUE(match);
395   ASSERT_EQ(Src0, Copies[0]);
396 }
397 
398 TEST(PatternMatchInstr, MatchSpecificType) {
399   LLVMContext Context;
400   std::unique_ptr<TargetMachine> TM = createTargetMachine();
401   if (!TM)
402     return;
403   auto ModuleMMIPair = createDummyModule(Context, *TM, "");
404   MachineFunction *MF =
405       getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
406   SmallVector<unsigned, 4> Copies;
407   collectCopies(Copies, MF);
408   MachineBasicBlock *EntryMBB = &*MF->begin();
409   MachineIRBuilder B(*MF);
410   MachineRegisterInfo &MRI = MF->getRegInfo();
411   B.setInsertPt(*EntryMBB, EntryMBB->end());
412 
413   // Try to match a 64bit add.
414   LLT s64 = LLT::scalar(64);
415   LLT s32 = LLT::scalar(32);
416   auto MIBAdd = B.buildAdd(s64, Copies[0], Copies[1]);
417   ASSERT_FALSE(mi_match(MIBAdd->getOperand(0).getReg(), MRI,
418                         m_GAdd(m_SpecificType(s32), m_Reg())));
419   ASSERT_TRUE(mi_match(MIBAdd->getOperand(0).getReg(), MRI,
420                        m_GAdd(m_SpecificType(s64), m_Reg())));
421 
422   // Try to match the destination type of a bitcast.
423   LLT v2s32 = LLT::vector(2, 32);
424   auto MIBCast = B.buildCast(v2s32, Copies[0]);
425   ASSERT_TRUE(
426       mi_match(MIBCast->getOperand(0).getReg(), MRI, m_GBitcast(m_Reg())));
427   ASSERT_TRUE(
428       mi_match(MIBCast->getOperand(0).getReg(), MRI, m_SpecificType(v2s32)));
429   ASSERT_TRUE(
430       mi_match(MIBCast->getOperand(1).getReg(), MRI, m_SpecificType(s64)));
431 
432   // Build a PTRToInt and INTTOPTR and match and test them.
433   LLT PtrTy = LLT::pointer(0, 64);
434   auto MIBIntToPtr = B.buildCast(PtrTy, Copies[0]);
435   auto MIBPtrToInt = B.buildCast(s64, MIBIntToPtr);
436   unsigned Src0;
437 
438   // match the ptrtoint(inttoptr reg)
439   bool match = mi_match(MIBPtrToInt->getOperand(0).getReg(), MRI,
440                         m_GPtrToInt(m_GIntToPtr(m_Reg(Src0))));
441   ASSERT_TRUE(match);
442   ASSERT_EQ(Src0, Copies[0]);
443 }
444 
445 TEST(PatternMatchInstr, MatchCombinators) {
446   LLVMContext Context;
447   std::unique_ptr<TargetMachine> TM = createTargetMachine();
448   if (!TM)
449     return;
450   auto ModuleMMIPair = createDummyModule(Context, *TM, "");
451   MachineFunction *MF =
452       getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get());
453   SmallVector<unsigned, 4> Copies;
454   collectCopies(Copies, MF);
455   MachineBasicBlock *EntryMBB = &*MF->begin();
456   MachineIRBuilder B(*MF);
457   MachineRegisterInfo &MRI = MF->getRegInfo();
458   B.setInsertPt(*EntryMBB, EntryMBB->end());
459   LLT s64 = LLT::scalar(64);
460   LLT s32 = LLT::scalar(32);
461   auto MIBAdd = B.buildAdd(s64, Copies[0], Copies[1]);
462   unsigned Src0, Src1;
463   bool match =
464       mi_match(MIBAdd->getOperand(0).getReg(), MRI,
465                m_all_of(m_SpecificType(s64), m_GAdd(m_Reg(Src0), m_Reg(Src1))));
466   ASSERT_TRUE(match);
467   ASSERT_EQ(Src0, Copies[0]);
468   ASSERT_EQ(Src1, Copies[1]);
469   // Check for s32 (which should fail).
470   match =
471       mi_match(MIBAdd->getOperand(0).getReg(), MRI,
472                m_all_of(m_SpecificType(s32), m_GAdd(m_Reg(Src0), m_Reg(Src1))));
473   ASSERT_FALSE(match);
474   match =
475       mi_match(MIBAdd->getOperand(0).getReg(), MRI,
476                m_any_of(m_SpecificType(s32), m_GAdd(m_Reg(Src0), m_Reg(Src1))));
477   ASSERT_TRUE(match);
478   ASSERT_EQ(Src0, Copies[0]);
479   ASSERT_EQ(Src1, Copies[1]);
480 
481   // Match a case where none of the predicates hold true.
482   match = mi_match(
483       MIBAdd->getOperand(0).getReg(), MRI,
484       m_any_of(m_SpecificType(LLT::scalar(16)), m_GSub(m_Reg(), m_Reg())));
485   ASSERT_FALSE(match);
486 }
487 } // namespace
488 
489 int main(int argc, char **argv) {
490   ::testing::InitGoogleTest(&argc, argv);
491   initLLVM();
492   return RUN_ALL_TESTS();
493 }
494