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
initLLVM()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 "x86_64" which should be available in most builds.
createTargetMachine()39 std::unique_ptr<TargetMachine> createTargetMachine() {
40 Triple TargetTriple("x86_64--");
41 std::string Error;
42 const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
43 if (!T)
44 return nullptr;
45
46 TargetOptions Options;
47 return std::unique_ptr<TargetMachine>(
48 T->createTargetMachine("x86_64", "", "", Options, None,
49 CodeModel::Default, CodeGenOpt::Aggressive));
50 }
51
parseMIR(LLVMContext & Context,legacy::PassManagerBase & PM,std::unique_ptr<MIRParser> & MIR,const TargetMachine & TM,StringRef MIRCode,const char * FuncName)52 std::unique_ptr<Module> parseMIR(LLVMContext &Context,
53 legacy::PassManagerBase &PM, std::unique_ptr<MIRParser> &MIR,
54 const TargetMachine &TM, StringRef MIRCode, const char *FuncName) {
55 SMDiagnostic Diagnostic;
56 std::unique_ptr<MemoryBuffer> MBuffer = MemoryBuffer::getMemBuffer(MIRCode);
57 MIR = createMIRParser(std::move(MBuffer), Context);
58 if (!MIR)
59 return nullptr;
60
61 std::unique_ptr<Module> M = MIR->parseLLVMModule();
62 if (!M)
63 return nullptr;
64
65 M->setDataLayout(TM.createDataLayout());
66
67 Function *F = M->getFunction(FuncName);
68 if (!F)
69 return nullptr;
70
71 const LLVMTargetMachine &LLVMTM = static_cast<const LLVMTargetMachine&>(TM);
72 LLVMTM.addMachineModuleInfo(PM);
73 LLVMTM.addMachineFunctionAnalysis(PM, MIR.get());
74
75 return M;
76 }
77
78 typedef std::function<void(MachineFunction&,LiveIntervals&)> LiveIntervalTest;
79
80 struct TestPass : public MachineFunctionPass {
81 static char ID;
TestPass__anon2f4cfd450111::TestPass82 TestPass() : MachineFunctionPass(ID) {
83 // We should never call this but always use PM.add(new TestPass(...))
84 abort();
85 }
TestPass__anon2f4cfd450111::TestPass86 TestPass(LiveIntervalTest T) : MachineFunctionPass(ID), T(T) {
87 initializeTestPassPass(*PassRegistry::getPassRegistry());
88 }
89
runOnMachineFunction__anon2f4cfd450111::TestPass90 bool runOnMachineFunction(MachineFunction &MF) override {
91 LiveIntervals &LIS = getAnalysis<LiveIntervals>();
92 T(MF, LIS);
93 EXPECT_TRUE(MF.verify(this));
94 return true;
95 }
96
getAnalysisUsage__anon2f4cfd450111::TestPass97 void getAnalysisUsage(AnalysisUsage &AU) const override {
98 AU.setPreservesAll();
99 AU.addRequired<LiveIntervals>();
100 AU.addPreserved<LiveIntervals>();
101 MachineFunctionPass::getAnalysisUsage(AU);
102 }
103 private:
104 LiveIntervalTest T;
105 };
106
107 /**
108 * Move instruction number \p From in front of instruction number \p To and
109 * update affected liveness intervals with LiveIntervalAnalysis::handleMove().
110 */
testHandleMove(MachineFunction & MF,LiveIntervals & LIS,unsigned From,unsigned To,unsigned BlockNum=0)111 static void testHandleMove(MachineFunction &MF, LiveIntervals &LIS,
112 unsigned From, unsigned To, unsigned BlockNum = 0) {
113 MachineBasicBlock &MBB = *MF.getBlockNumbered(BlockNum);
114
115 unsigned I = 0;
116 MachineInstr *FromInstr = nullptr;
117 MachineInstr *ToInstr = nullptr;
118 for (MachineInstr &MI : MBB) {
119 if (I == From)
120 FromInstr = &MI;
121 if (I == To)
122 ToInstr = &MI;
123 ++I;
124 }
125 assert(FromInstr != nullptr && ToInstr != nullptr);
126
127 MBB.splice(ToInstr->getIterator(), &MBB, FromInstr->getIterator());
128 LIS.handleMove(*FromInstr, true);
129 }
130
liveIntervalTest(StringRef MIRFunc,LiveIntervalTest T)131 static void liveIntervalTest(StringRef MIRFunc, LiveIntervalTest T) {
132 LLVMContext Context;
133 std::unique_ptr<TargetMachine> TM = createTargetMachine();
134 // This test is designed for the X86 backend; stop if it is not available.
135 if (!TM)
136 return;
137
138 legacy::PassManager PM;
139
140 SmallString<160> S;
141 StringRef MIRString = (Twine(
142 "---\n"
143 "...\n"
144 "name: func\n"
145 "registers:\n"
146 " - { id: 0, class: gr64 }\n"
147 "body: |\n"
148 " bb.0:\n"
149 ) + Twine(MIRFunc) + Twine("...\n")).toNullTerminatedStringRef(S);
150 std::unique_ptr<MIRParser> MIR;
151 std::unique_ptr<Module> M = parseMIR(Context, PM, MIR, *TM, MIRString,
152 "func");
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
TEST(LiveIntervalTest,MoveUpDef)164 TEST(LiveIntervalTest, MoveUpDef) {
165 // Value defined.
166 liveIntervalTest(
167 " NOOP\n"
168 " NOOP\n"
169 " early-clobber %0 = IMPLICIT_DEF\n"
170 " RETQ %0\n",
171 [](MachineFunction &MF, LiveIntervals &LIS) {
172 testHandleMove(MF, LIS, 2, 1);
173 });
174 }
175
TEST(LiveIntervalTest,MoveUpRedef)176 TEST(LiveIntervalTest, MoveUpRedef) {
177 liveIntervalTest(
178 " %0 = IMPLICIT_DEF\n"
179 " NOOP\n"
180 " %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n"
181 " RETQ %0\n",
182 [](MachineFunction &MF, LiveIntervals &LIS) {
183 testHandleMove(MF, LIS, 2, 1);
184 });
185 }
186
TEST(LiveIntervalTest,MoveUpEarlyDef)187 TEST(LiveIntervalTest, MoveUpEarlyDef) {
188 liveIntervalTest(
189 " NOOP\n"
190 " NOOP\n"
191 " early-clobber %0 = IMPLICIT_DEF\n"
192 " RETQ %0\n",
193 [](MachineFunction &MF, LiveIntervals &LIS) {
194 testHandleMove(MF, LIS, 2, 1);
195 });
196 }
197
TEST(LiveIntervalTest,MoveUpEarlyRedef)198 TEST(LiveIntervalTest, MoveUpEarlyRedef) {
199 liveIntervalTest(
200 " %0 = IMPLICIT_DEF\n"
201 " NOOP\n"
202 " early-clobber %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n"
203 " RETQ %0\n",
204 [](MachineFunction &MF, LiveIntervals &LIS) {
205 testHandleMove(MF, LIS, 2, 1);
206 });
207 }
208
TEST(LiveIntervalTest,MoveUpKill)209 TEST(LiveIntervalTest, MoveUpKill) {
210 liveIntervalTest(
211 " %0 = IMPLICIT_DEF\n"
212 " NOOP\n"
213 " NOOP implicit %0\n",
214 [](MachineFunction &MF, LiveIntervals &LIS) {
215 testHandleMove(MF, LIS, 2, 1);
216 });
217 }
218
TEST(LiveIntervalTest,MoveUpKillFollowing)219 TEST(LiveIntervalTest, MoveUpKillFollowing) {
220 liveIntervalTest(
221 " %0 = IMPLICIT_DEF\n"
222 " NOOP\n"
223 " NOOP implicit %0\n"
224 " RETQ %0\n",
225 [](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
TEST(LiveIntervalTest,MoveDownDef)233 TEST(LiveIntervalTest, MoveDownDef) {
234 // Value defined.
235 liveIntervalTest(
236 " NOOP\n"
237 " early-clobber %0 = IMPLICIT_DEF\n"
238 " NOOP\n"
239 " RETQ %0\n",
240 [](MachineFunction &MF, LiveIntervals &LIS) {
241 testHandleMove(MF, LIS, 1, 2);
242 });
243 }
244
TEST(LiveIntervalTest,MoveDownRedef)245 TEST(LiveIntervalTest, MoveDownRedef) {
246 liveIntervalTest(
247 " %0 = IMPLICIT_DEF\n"
248 " %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n"
249 " NOOP\n"
250 " RETQ %0\n",
251 [](MachineFunction &MF, LiveIntervals &LIS) {
252 testHandleMove(MF, LIS, 1, 2);
253 });
254 }
255
TEST(LiveIntervalTest,MoveDownEarlyDef)256 TEST(LiveIntervalTest, MoveDownEarlyDef) {
257 liveIntervalTest(
258 " NOOP\n"
259 " early-clobber %0 = IMPLICIT_DEF\n"
260 " NOOP\n"
261 " RETQ %0\n",
262 [](MachineFunction &MF, LiveIntervals &LIS) {
263 testHandleMove(MF, LIS, 1, 2);
264 });
265 }
266
TEST(LiveIntervalTest,MoveDownEarlyRedef)267 TEST(LiveIntervalTest, MoveDownEarlyRedef) {
268 liveIntervalTest(
269 " %0 = IMPLICIT_DEF\n"
270 " early-clobber %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n"
271 " NOOP\n"
272 " RETQ %0\n",
273 [](MachineFunction &MF, LiveIntervals &LIS) {
274 testHandleMove(MF, LIS, 1, 2);
275 });
276 }
277
TEST(LiveIntervalTest,MoveDownKill)278 TEST(LiveIntervalTest, MoveDownKill) {
279 liveIntervalTest(
280 " %0 = IMPLICIT_DEF\n"
281 " NOOP implicit %0\n"
282 " NOOP\n",
283 [](MachineFunction &MF, LiveIntervals &LIS) {
284 testHandleMove(MF, LIS, 1, 2);
285 });
286 }
287
TEST(LiveIntervalTest,MoveDownKillFollowing)288 TEST(LiveIntervalTest, MoveDownKillFollowing) {
289 liveIntervalTest(
290 " %0 = IMPLICIT_DEF\n"
291 " NOOP\n"
292 " NOOP implicit %0\n"
293 " RETQ %0\n",
294 [](MachineFunction &MF, LiveIntervals &LIS) {
295 testHandleMove(MF, LIS, 1, 2);
296 });
297 }
298
TEST(LiveIntervalTest,MoveUndefUse)299 TEST(LiveIntervalTest, MoveUndefUse) {
300 liveIntervalTest(
301 " %0 = IMPLICIT_DEF\n"
302 " NOOP implicit undef %0\n"
303 " NOOP implicit %0\n"
304 " NOOP\n",
305 [](MachineFunction &MF, LiveIntervals &LIS) {
306 testHandleMove(MF, LIS, 1, 3);
307 });
308 }
309
TEST(LiveIntervalTest,MoveUpValNos)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 guarntee that this valno wasn't
313 // used in other segments.
314 liveIntervalTest(
315 " successors: %bb.1, %bb.2\n"
316 " %0 = IMPLICIT_DEF\n"
317 " JG_1 %bb.2, implicit %eflags\n"
318 " JMP_1 %bb.1\n"
319 " bb.2:\n"
320 " NOOP implicit %0\n"
321 " bb.1:\n"
322 " successors: %bb.2\n"
323 " %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n"
324 " %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n"
325 " %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n"
326 " JMP_1 %bb.2\n",
327 [](MachineFunction &MF, LiveIntervals &LIS) {
328 testHandleMove(MF, LIS, 2, 0, 2);
329 });
330 }
331
TEST(LiveIntervalTest,MoveOverUndefUse0)332 TEST(LiveIntervalTest, MoveOverUndefUse0) {
333 // findLastUseBefore() used by handleMoveUp() must ignore undef operands.
334 liveIntervalTest(
335 " %0 = IMPLICIT_DEF\n"
336 " NOOP\n"
337 " NOOP implicit undef %0\n"
338 " %0 = IMPLICIT_DEF implicit %0(tied-def 0)\n",
339 [](MachineFunction &MF, LiveIntervals &LIS) {
340 testHandleMove(MF, LIS, 3, 1);
341 });
342 }
343
TEST(LiveIntervalTest,MoveOverUndefUse1)344 TEST(LiveIntervalTest, MoveOverUndefUse1) {
345 // findLastUseBefore() used by handleMoveUp() must ignore undef operands.
346 liveIntervalTest(
347 " %rax = IMPLICIT_DEF\n"
348 " NOOP\n"
349 " NOOP implicit undef %rax\n"
350 " %rax = IMPLICIT_DEF implicit %rax(tied-def 0)\n",
351 [](MachineFunction &MF, LiveIntervals &LIS) {
352 testHandleMove(MF, LIS, 3, 1);
353 });
354 }
355
main(int argc,char ** argv)356 int main(int argc, char **argv) {
357 ::testing::InitGoogleTest(&argc, argv);
358 initLLVM();
359 return RUN_ALL_TESTS();
360 }
361