unittests/MI/LiveIntervalTest.cpp

   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 }