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