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