1 #include "llvm/ADT/STLExtras.h"
2 #include "llvm/CodeGen/LiveIntervals.h"
3 #include "llvm/CodeGen/MIRParser/MIRParser.h"
4 #include "llvm/CodeGen/MachineFunction.h"
5 #include "llvm/CodeGen/MachineModuleInfo.h"
6 #include "llvm/CodeGen/TargetRegisterInfo.h"
7 #include "llvm/IR/LegacyPassManager.h"
8 #include "llvm/Support/MemoryBuffer.h"
9 #include "llvm/Support/SourceMgr.h"
10 #include "llvm/Support/TargetRegistry.h"
11 #include "llvm/Support/TargetSelect.h"
12 #include "llvm/Target/TargetMachine.h"
13 #include "llvm/Target/TargetOptions.h"
14 #include "gtest/gtest.h"
15 
16 using namespace llvm;
17 
18 namespace llvm {
19   void initializeTestPassPass(PassRegistry &);
20 }
21 
22 namespace {
23 
24 void initLLVM() {
25   InitializeAllTargets();
26   InitializeAllTargetMCs();
27   InitializeAllAsmPrinters();
28   InitializeAllAsmParsers();
29 
30   PassRegistry *Registry = PassRegistry::getPassRegistry();
31   initializeCore(*Registry);
32   initializeCodeGen(*Registry);
33 }
34 
35 /// Create a TargetMachine. As we lack a dedicated always available target for
36 /// unittests, we go for "AMDGPU" to be able to test normal and subregister
37 /// liveranges.
38 std::unique_ptr<LLVMTargetMachine> createTargetMachine() {
39   Triple TargetTriple("amdgcn--");
40   std::string Error;
41   const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
42   if (!T)
43     return nullptr;
44 
45   TargetOptions Options;
46   return std::unique_ptr<LLVMTargetMachine>(static_cast<LLVMTargetMachine*>(
47       T->createTargetMachine("AMDGPU", "", "", Options, None, None,
48                              CodeGenOpt::Aggressive)));
49 }
50 
51 std::unique_ptr<Module> parseMIR(LLVMContext &Context,
52     legacy::PassManagerBase &PM, std::unique_ptr<MIRParser> &MIR,
53     const LLVMTargetMachine &TM, StringRef MIRCode, const char *FuncName) {
54   SMDiagnostic Diagnostic;
55   std::unique_ptr<MemoryBuffer> MBuffer = MemoryBuffer::getMemBuffer(MIRCode);
56   MIR = createMIRParser(std::move(MBuffer), Context);
57   if (!MIR)
58     return nullptr;
59 
60   std::unique_ptr<Module> M = MIR->parseIRModule();
61   if (!M)
62     return nullptr;
63 
64   M->setDataLayout(TM.createDataLayout());
65 
66   MachineModuleInfoWrapperPass *MMIWP = new MachineModuleInfoWrapperPass(&TM);
67   if (MIR->parseMachineFunctions(*M, MMIWP->getMMI()))
68     return nullptr;
69   PM.add(MMIWP);
70 
71   return M;
72 }
73 
74 typedef std::function<void(MachineFunction&,LiveIntervals&)> LiveIntervalTest;
75 
76 struct TestPass : public MachineFunctionPass {
77   static char ID;
78   TestPass() : MachineFunctionPass(ID) {
79     // We should never call this but always use PM.add(new TestPass(...))
80     abort();
81   }
82   TestPass(LiveIntervalTest T) : MachineFunctionPass(ID), T(T) {
83     initializeTestPassPass(*PassRegistry::getPassRegistry());
84   }
85 
86   bool runOnMachineFunction(MachineFunction &MF) override {
87     LiveIntervals &LIS = getAnalysis<LiveIntervals>();
88     T(MF, LIS);
89     EXPECT_TRUE(MF.verify(this));
90     return true;
91   }
92 
93   void getAnalysisUsage(AnalysisUsage &AU) const override {
94     AU.setPreservesAll();
95     AU.addRequired<LiveIntervals>();
96     AU.addPreserved<LiveIntervals>();
97     MachineFunctionPass::getAnalysisUsage(AU);
98   }
99 private:
100   LiveIntervalTest T;
101 };
102 
103 static MachineInstr &getMI(MachineFunction &MF, unsigned At,
104                            unsigned BlockNum) {
105   MachineBasicBlock &MBB = *MF.getBlockNumbered(BlockNum);
106 
107   unsigned I = 0;
108   for (MachineInstr &MI : MBB) {
109     if (I == At)
110       return MI;
111     ++I;
112   }
113   llvm_unreachable("Instruction not found");
114 }
115 
116 /**
117  * Move instruction number \p From in front of instruction number \p To and
118  * update affected liveness intervals with LiveIntervalAnalysis::handleMove().
119  */
120 static void testHandleMove(MachineFunction &MF, LiveIntervals &LIS,
121                            unsigned From, unsigned To, unsigned BlockNum = 0) {
122   MachineInstr &FromInstr = getMI(MF, From, BlockNum);
123   MachineInstr &ToInstr = getMI(MF, To, BlockNum);
124 
125   MachineBasicBlock &MBB = *FromInstr.getParent();
126   MBB.splice(ToInstr.getIterator(), &MBB, FromInstr.getIterator());
127   LIS.handleMove(FromInstr, true);
128 }
129 
130 static void liveIntervalTest(StringRef MIRFunc, LiveIntervalTest T) {
131   LLVMContext Context;
132   std::unique_ptr<LLVMTargetMachine> TM = createTargetMachine();
133   // This test is designed for the X86 backend; stop if it is not available.
134   if (!TM)
135     return;
136 
137   legacy::PassManager PM;
138 
139   SmallString<160> S;
140   StringRef MIRString = (Twine(R"MIR(
141 ---
142 ...
143 name: func
144 registers:
145   - { id: 0, class: sreg_64 }
146 body: |
147   bb.0:
148 )MIR") + Twine(MIRFunc) + Twine("...\n")).toNullTerminatedStringRef(S);
149   std::unique_ptr<MIRParser> MIR;
150   std::unique_ptr<Module> M = parseMIR(Context, PM, MIR, *TM, MIRString,
151                                        "func");
152   ASSERT_TRUE(M);
153 
154   PM.add(new TestPass(T));
155 
156   PM.run(*M);
157 }
158 
159 } // End of anonymous namespace.
160 
161 char TestPass::ID = 0;
162 INITIALIZE_PASS(TestPass, "testpass", "testpass", false, false)
163 
164 TEST(LiveIntervalTest, MoveUpDef) {
165   // Value defined.
166   liveIntervalTest(R"MIR(
167     S_NOP 0
168     S_NOP 0
169     early-clobber %0 = IMPLICIT_DEF
170     S_NOP 0, implicit %0
171 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
172     testHandleMove(MF, LIS, 2, 1);
173   });
174 }
175 
176 TEST(LiveIntervalTest, MoveUpRedef) {
177   liveIntervalTest(R"MIR(
178     %0 = IMPLICIT_DEF
179     S_NOP 0
180     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
181     S_NOP 0, implicit %0
182 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
183     testHandleMove(MF, LIS, 2, 1);
184   });
185 }
186 
187 TEST(LiveIntervalTest, MoveUpEarlyDef) {
188   liveIntervalTest(R"MIR(
189     S_NOP 0
190     S_NOP 0
191     early-clobber %0 = IMPLICIT_DEF
192     S_NOP 0, implicit %0
193 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
194     testHandleMove(MF, LIS, 2, 1);
195   });
196 }
197 
198 TEST(LiveIntervalTest, MoveUpEarlyRedef) {
199   liveIntervalTest(R"MIR(
200     %0 = IMPLICIT_DEF
201     S_NOP 0
202     early-clobber %0 = IMPLICIT_DEF implicit %0(tied-def 0)
203     S_NOP 0, implicit %0
204 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
205     testHandleMove(MF, LIS, 2, 1);
206   });
207 }
208 
209 TEST(LiveIntervalTest, MoveUpKill) {
210   liveIntervalTest(R"MIR(
211     %0 = IMPLICIT_DEF
212     S_NOP 0
213     S_NOP 0, implicit %0
214 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
215     testHandleMove(MF, LIS, 2, 1);
216   });
217 }
218 
219 TEST(LiveIntervalTest, MoveUpKillFollowing) {
220   liveIntervalTest(R"MIR(
221     %0 = IMPLICIT_DEF
222     S_NOP 0
223     S_NOP 0, implicit %0
224     S_NOP 0, implicit %0
225 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
226     testHandleMove(MF, LIS, 2, 1);
227   });
228 }
229 
230 // TODO: Construct a situation where we have intervals following a hole
231 // while still having connected components.
232 
233 TEST(LiveIntervalTest, MoveDownDef) {
234   // Value defined.
235   liveIntervalTest(R"MIR(
236     S_NOP 0
237     early-clobber %0 = IMPLICIT_DEF
238     S_NOP 0
239     S_NOP 0, implicit %0
240 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
241     testHandleMove(MF, LIS, 1, 2);
242   });
243 }
244 
245 TEST(LiveIntervalTest, MoveDownRedef) {
246   liveIntervalTest(R"MIR(
247     %0 = IMPLICIT_DEF
248     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
249     S_NOP 0
250     S_NOP 0, implicit %0
251 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
252     testHandleMove(MF, LIS, 1, 2);
253   });
254 }
255 
256 TEST(LiveIntervalTest, MoveDownEarlyDef) {
257   liveIntervalTest(R"MIR(
258     S_NOP 0
259     early-clobber %0 = IMPLICIT_DEF
260     S_NOP 0
261     S_NOP 0, implicit %0
262 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
263     testHandleMove(MF, LIS, 1, 2);
264   });
265 }
266 
267 TEST(LiveIntervalTest, MoveDownEarlyRedef) {
268   liveIntervalTest(R"MIR(
269     %0 = IMPLICIT_DEF
270     early-clobber %0 = IMPLICIT_DEF implicit %0(tied-def 0)
271     S_NOP 0
272     S_NOP 0, implicit %0
273 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
274     testHandleMove(MF, LIS, 1, 2);
275   });
276 }
277 
278 TEST(LiveIntervalTest, MoveDownKill) {
279   liveIntervalTest(R"MIR(
280     %0 = IMPLICIT_DEF
281     S_NOP 0, implicit %0
282     S_NOP 0
283 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
284     testHandleMove(MF, LIS, 1, 2);
285   });
286 }
287 
288 TEST(LiveIntervalTest, MoveDownKillFollowing) {
289   liveIntervalTest(R"MIR(
290     %0 = IMPLICIT_DEF
291     S_NOP 0
292     S_NOP 0, implicit %0
293     S_NOP 0, implicit %0
294 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
295     testHandleMove(MF, LIS, 1, 2);
296   });
297 }
298 
299 TEST(LiveIntervalTest, MoveUndefUse) {
300   liveIntervalTest(R"MIR(
301     %0 = IMPLICIT_DEF
302     S_NOP 0, implicit undef %0
303     S_NOP 0, implicit %0
304     S_NOP 0
305 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
306     testHandleMove(MF, LIS, 1, 3);
307   });
308 }
309 
310 TEST(LiveIntervalTest, MoveUpValNos) {
311   // handleMoveUp() had a bug where it would reuse the value number of the
312   // destination segment, even though we have no guarantee that this valno
313   // wasn't used in other segments.
314   liveIntervalTest(R"MIR(
315     successors: %bb.1, %bb.2
316     %0 = IMPLICIT_DEF
317     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
318     S_BRANCH %bb.1
319   bb.2:
320     S_NOP 0, implicit %0
321   bb.1:
322     successors: %bb.2
323     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
324     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
325     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
326     S_BRANCH %bb.2
327 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
328     testHandleMove(MF, LIS, 2, 0, 2);
329   });
330 }
331 
332 TEST(LiveIntervalTest, MoveOverUndefUse0) {
333   // findLastUseBefore() used by handleMoveUp() must ignore undef operands.
334   liveIntervalTest(R"MIR(
335     %0 = IMPLICIT_DEF
336     S_NOP 0
337     S_NOP 0, implicit undef %0
338     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
339 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
340     testHandleMove(MF, LIS, 3, 1);
341   });
342 }
343 
344 TEST(LiveIntervalTest, MoveOverUndefUse1) {
345   // findLastUseBefore() used by handleMoveUp() must ignore undef operands.
346   liveIntervalTest(R"MIR(
347     $sgpr0 = IMPLICIT_DEF
348     S_NOP 0
349     S_NOP 0, implicit undef $sgpr0
350     $sgpr0 = IMPLICIT_DEF implicit $sgpr0(tied-def 0)
351 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
352     testHandleMove(MF, LIS, 3, 1);
353   });
354 }
355 
356 TEST(LiveIntervalTest, SubRegMoveDown) {
357   // Subregister ranges can have holes inside a basic block. Check for a
358   // movement of the form 32->150 in a liverange [16, 32) [100,200).
359   liveIntervalTest(R"MIR(
360     successors: %bb.1, %bb.2
361     %0 = IMPLICIT_DEF
362     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
363     S_BRANCH %bb.1
364   bb.2:
365     successors: %bb.1
366     S_NOP 0, implicit %0.sub0
367     S_NOP 0, implicit %0.sub1
368     S_NOP 0
369     undef %0.sub0 = IMPLICIT_DEF
370     %0.sub1 = IMPLICIT_DEF
371   bb.1:
372     S_NOP 0, implicit %0
373 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
374     // Scheduler behaviour: Clear def,read-undef flag and move.
375     MachineInstr &MI = getMI(MF, 3, /*BlockNum=*/1);
376     MI.getOperand(0).setIsUndef(false);
377     testHandleMove(MF, LIS, 1, 4, /*BlockNum=*/1);
378   });
379 }
380 
381 TEST(LiveIntervalTest, SubRegMoveUp) {
382   // handleMoveUp had a bug not updating valno of segment incoming to bb.2
383   // after swapping subreg definitions.
384   liveIntervalTest(R"MIR(
385     successors: %bb.1, %bb.2
386     undef %0.sub0 = IMPLICIT_DEF
387     %0.sub1 = IMPLICIT_DEF
388     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
389     S_BRANCH %bb.1
390   bb.1:
391     S_NOP 0, implicit %0.sub1
392   bb.2:
393     S_NOP 0, implicit %0.sub1
394 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
395     testHandleMove(MF, LIS, 1, 0);
396   });
397 }
398 
399 TEST(LiveIntervalTest, DeadSubRegMoveUp) {
400   // handleMoveUp had a bug where moving a dead subreg def into the middle of
401   // an earlier segment resulted in an invalid live range.
402   liveIntervalTest(R"MIR(
403     undef %125.sub0:vreg_128 = V_MOV_B32_e32 0, implicit $exec
404     %125.sub1:vreg_128 = COPY %125.sub0
405     %125.sub2:vreg_128 = COPY %125.sub0
406     undef %51.sub0:vreg_128 = V_MOV_B32_e32 898625526, implicit $exec
407     %51.sub1:vreg_128 = COPY %51.sub0
408     %51.sub2:vreg_128 = COPY %51.sub0
409     %52:vgpr_32 = V_MOV_B32_e32 986714345, implicit $exec
410     %54:vgpr_32 = V_MOV_B32_e32 1742342378, implicit $exec
411     %57:vgpr_32 = V_MOV_B32_e32 3168768712, implicit $exec
412     %59:vgpr_32 = V_MOV_B32_e32 1039972644, implicit $exec
413     %60:vgpr_32 = V_MAD_F32 0, %52, 0, undef %61:vgpr_32, 0, %59, 0, 0, implicit $exec
414     %63:vgpr_32 = V_ADD_F32_e32 %51.sub3, undef %64:vgpr_32, implicit $exec
415     dead %66:vgpr_32 = V_MAD_F32 0, %60, 0, undef %67:vgpr_32, 0, %125.sub2, 0, 0, implicit $exec
416     undef %124.sub1:vreg_128 = V_MAD_F32 0, %57, 0, undef %70:vgpr_32, 0, %125.sub1, 0, 0, implicit $exec
417     %124.sub0:vreg_128 = V_MAD_F32 0, %54, 0, undef %73:vgpr_32, 0, %125.sub0, 0, 0, implicit $exec
418     dead undef %125.sub3:vreg_128 = V_MAC_F32_e32 %63, undef %76:vgpr_32, %125.sub3, implicit $exec
419 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
420     testHandleMove(MF, LIS, 15, 12);
421   });
422 }
423 
424 TEST(LiveIntervalTest, TestMoveSubRegDefAcrossUseDef) {
425   liveIntervalTest(R"MIR(
426     %1:vreg_64 = IMPLICIT_DEF
427 
428   bb.1:
429     %2:vgpr_32 = V_MOV_B32_e32 2, implicit $exec
430     %3:vgpr_32 = V_ADD_U32_e32 %2, %1.sub0, implicit $exec
431     undef %1.sub0:vreg_64 = V_ADD_U32_e32 %2, %2, implicit $exec
432     %1.sub1:vreg_64 = COPY %2
433     S_NOP 0, implicit %1.sub1
434     S_BRANCH %bb.1
435 
436 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
437      MachineInstr &UndefSubregDef = getMI(MF, 2, 1);
438      // The scheduler clears undef from subregister defs before moving
439      UndefSubregDef.getOperand(0).setIsUndef(false);
440      testHandleMove(MF, LIS, 3, 1, 1);
441   });
442 }
443 
444 TEST(LiveIntervalTest, TestMoveSubRegDefAcrossUseDefMulti) {
445   liveIntervalTest(R"MIR(
446     %1:vreg_96 = IMPLICIT_DEF
447 
448   bb.1:
449     %2:vgpr_32 = V_MOV_B32_e32 2, implicit $exec
450     %3:vgpr_32 = V_ADD_U32_e32 %2, %1.sub0, implicit $exec
451     undef %1.sub0:vreg_96 = V_ADD_U32_e32 %2, %2, implicit $exec
452     %1.sub1:vreg_96 = COPY %2
453     %1.sub2:vreg_96 = COPY %2
454     S_NOP 0, implicit %1.sub1, implicit %1.sub2
455     S_BRANCH %bb.1
456 
457 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
458      MachineInstr &UndefSubregDef = getMI(MF, 2, 1);
459      // The scheduler clears undef from subregister defs before moving
460      UndefSubregDef.getOperand(0).setIsUndef(false);
461      testHandleMove(MF, LIS, 4, 1, 1);
462   });
463 }
464 int main(int argc, char **argv) {
465   ::testing::InitGoogleTest(&argc, argv);
466   initLLVM();
467   return RUN_ALL_TESTS();
468 }
469