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
18using namespace llvm;
19
20namespace llvm {
21  void initializeTestPassPass(PassRegistry &);
22}
23
24namespace {
25
26void 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.
39std::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
52std::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
78typedef std::function<void(MachineFunction&,LiveIntervals&)> LiveIntervalTest;
79
80struct TestPass : public MachineFunctionPass {
81  static char ID;
82  TestPass() : MachineFunctionPass(ID) {
83    // We should never call this but always use PM.add(new TestPass(...))
84    abort();
85  }
86  TestPass(LiveIntervalTest T) : MachineFunctionPass(ID), T(T) {
87    initializeTestPassPass(*PassRegistry::getPassRegistry());
88  }
89
90  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
97  void getAnalysisUsage(AnalysisUsage &AU) const override {
98    AU.setPreservesAll();
99    AU.addRequired<LiveIntervals>();
100    AU.addPreserved<LiveIntervals>();
101    MachineFunctionPass::getAnalysisUsage(AU);
102  }
103private:
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 */
111static 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
131static 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
161char TestPass::ID = 0;
162INITIALIZE_PASS(TestPass, "testpass", "testpass", false, false)
163
164TEST(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
176TEST(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
187TEST(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
198TEST(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
209TEST(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
219TEST(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
233TEST(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
245TEST(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
256TEST(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
267TEST(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
278TEST(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
288TEST(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
299TEST(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
310TEST(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
332TEST(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
344TEST(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
356int main(int argc, char **argv) {
357  ::testing::InitGoogleTest(&argc, argv);
358  initLLVM();
359  return RUN_ALL_TESTS();
360}
361