llvm/unittests/MI/LiveIntervalTest.cpp

   1 #include "llvm/ADT/STLExtras.h"
   2 #include "llvm/CodeGen/LiveIntervals.h"
   3 #include "llvm/CodeGen/LiveVariables.h"
   4 #include "llvm/CodeGen/MIRParser/MIRParser.h"
   5 #include "llvm/CodeGen/MachineFunction.h"
   6 #include "llvm/CodeGen/MachineModuleInfo.h"
   7 #include "llvm/CodeGen/TargetRegisterInfo.h"
   8 #include "llvm/CodeGen/TargetSubtargetInfo.h"
   9 #include "llvm/IR/LegacyPassManager.h"
  10 #include "llvm/IR/Module.h"
  11 #include "llvm/InitializePasses.h"
  12 #include "llvm/MC/TargetRegistry.h"
  13 #include "llvm/Support/MemoryBuffer.h"
  14 #include "llvm/Support/SourceMgr.h"
  15 #include "llvm/Support/TargetSelect.h"
  16 #include "llvm/Target/TargetMachine.h"
  17 #include "llvm/Target/TargetOptions.h"
  18 #include "gtest/gtest.h"
  19
  20 #include "../lib/CodeGen/RegisterCoalescer.h"
  21
  22 using namespace llvm;
  23
  24 namespace llvm {
  25   void initializeTestPassPass(PassRegistry &);
  26 }
  27
  28 namespace {
  29
  30 void initLLVM() {
  31   InitializeAllTargets();
  32   InitializeAllTargetMCs();
  33   InitializeAllAsmPrinters();
  34   InitializeAllAsmParsers();
  35
  36   PassRegistry *Registry = PassRegistry::getPassRegistry();
  37   initializeCore(*Registry);
  38   initializeCodeGen(*Registry);
  39 }
  40
  41 /// Create a TargetMachine. As we lack a dedicated always available target for
  42 /// unittests, we go for "AMDGPU" to be able to test normal and subregister
  43 /// liveranges.
  44 std::unique_ptr<TargetMachine> createTargetMachine() {
  45   Triple TargetTriple("amdgcn--");
  46   std::string Error;
  47   const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
  48   if (!T)
  49     return nullptr;
  50
  51   TargetOptions Options;
  52   return std::unique_ptr<TargetMachine>(
  53       T->createTargetMachine("AMDGPU", "gfx900", "", Options, std::nullopt,
  54                              std::nullopt, CodeGenOptLevel::Aggressive));
  55 }
  56
  57 std::unique_ptr<Module> parseMIR(LLVMContext &Context,
  58                                  legacy::PassManagerBase &PM,
  59                                  std::unique_ptr<MIRParser> &MIR,
  60                                  const TargetMachine &TM, StringRef MIRCode) {
  61   SMDiagnostic Diagnostic;
  62   std::unique_ptr<MemoryBuffer> MBuffer = MemoryBuffer::getMemBuffer(MIRCode);
  63   MIR = createMIRParser(std::move(MBuffer), Context);
  64   if (!MIR)
  65     return nullptr;
  66
  67   std::unique_ptr<Module> M = MIR->parseIRModule();
  68   if (!M)
  69     return nullptr;
  70
  71   M->setDataLayout(TM.createDataLayout());
  72
  73   MachineModuleInfoWrapperPass *MMIWP = new MachineModuleInfoWrapperPass(&TM);
  74   if (MIR->parseMachineFunctions(*M, MMIWP->getMMI()))
  75     return nullptr;
  76   PM.add(MMIWP);
  77
  78   return M;
  79 }
  80
  81 struct TestPass : public MachineFunctionPass {
  82   static char ID;
  83   TestPass() : MachineFunctionPass(ID) {}
  84 };
  85
  86 template <typename AnalysisType>
  87 struct TestPassT : public TestPass {
  88
  89   typedef std::function<void(MachineFunction&,AnalysisType&)> TestFx;
  90
  91   TestPassT() {
  92     // We should never call this but always use PM.add(new TestPass(...))
  93     abort();
  94   }
  95   TestPassT(TestFx T, bool ShouldPass)
  96       : T(T), ShouldPass(ShouldPass) {
  97     initializeTestPassPass(*PassRegistry::getPassRegistry());
  98   }
  99
 100   bool runOnMachineFunction(MachineFunction &MF) override {
 101     AnalysisType &A = getAnalysis<AnalysisType>();
 102     T(MF, A);
 103     EXPECT_EQ(MF.verify(this, /* Banner=*/nullptr,
 104                         /*OS=*/nullptr,
 105                         /* AbortOnError=*/false),
 106               ShouldPass);
 107     return true;
 108   }
 109
 110   void getAnalysisUsage(AnalysisUsage &AU) const override {
 111     AU.setPreservesAll();
 112     AU.addRequired<AnalysisType>();
 113     AU.addPreserved<AnalysisType>();
 114     MachineFunctionPass::getAnalysisUsage(AU);
 115   }
 116 private:
 117   TestFx T;
 118   bool ShouldPass;
 119 };
 120
 121 static MachineInstr &getMI(MachineFunction &MF, unsigned At,
 122                            unsigned BlockNum) {
 123   MachineBasicBlock &MBB = *MF.getBlockNumbered(BlockNum);
 124
 125   unsigned I = 0;
 126   for (MachineInstr &MI : MBB) {
 127     if (I == At)
 128       return MI;
 129     ++I;
 130   }
 131   llvm_unreachable("Instruction not found");
 132 }
 133
 134 /**
 135  * Move instruction number \p From in front of instruction number \p To and
 136  * update affected liveness intervals with LiveIntervalAnalysis::handleMove().
 137  */
 138 static void testHandleMove(MachineFunction &MF, LiveIntervals &LIS,
 139                            unsigned From, unsigned To, unsigned BlockNum = 0) {
 140   MachineInstr &FromInstr = getMI(MF, From, BlockNum);
 141   MachineInstr &ToInstr = getMI(MF, To, BlockNum);
 142
 143   MachineBasicBlock &MBB = *FromInstr.getParent();
 144   MBB.splice(ToInstr.getIterator(), &MBB, FromInstr.getIterator());
 145   LIS.handleMove(FromInstr, true);
 146 }
 147
 148 /**
 149  * Move instructions numbered \p From inclusive through instruction number
 150  * \p To into a newly formed bundle and update affected liveness intervals
 151  * with LiveIntervalAnalysis::handleMoveIntoNewBundle().
 152  */
 153 static void testHandleMoveIntoNewBundle(MachineFunction &MF, LiveIntervals &LIS,
 154                                         unsigned From, unsigned To,
 155                                         unsigned BlockNum = 0) {
 156   MachineInstr &FromInstr = getMI(MF, From, BlockNum);
 157   MachineInstr &ToInstr = getMI(MF, To, BlockNum);
 158   MachineBasicBlock &MBB = *FromInstr.getParent();
 159   MachineBasicBlock::instr_iterator I = FromInstr.getIterator();
 160
 161   // Build bundle
 162   finalizeBundle(MBB, I, std::next(ToInstr.getIterator()));
 163   MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA);
 164
 165   // Update LiveIntervals
 166   MachineBasicBlock::instr_iterator BundleStart = std::prev(I);
 167   LIS.handleMoveIntoNewBundle(*BundleStart, true);
 168 }
 169
 170 /**
 171  * Split block numbered \p BlockNum at instruction \p SplitAt using
 172  * MachineBasicBlock::splitAt updating liveness intervals.
 173  */
 174 static void testSplitAt(MachineFunction &MF, LiveIntervals &LIS,
 175                         unsigned SplitAt, unsigned BlockNum) {
 176   MachineInstr &SplitInstr = getMI(MF, SplitAt, BlockNum);
 177   MachineBasicBlock &MBB = *SplitInstr.getParent();
 178
 179   // Split block and update live intervals
 180   MBB.splitAt(SplitInstr, false, &LIS);
 181 }
 182
 183 /**
 184  * Helper function to test for interference between a hard register and a
 185  * virtual register live ranges.
 186  */
 187 static bool checkRegUnitInterference(LiveIntervals &LIS,
 188                                      const TargetRegisterInfo &TRI,
 189                                      const LiveInterval &VirtReg,
 190                                      MCRegister PhysReg) {
 191   if (VirtReg.empty())
 192     return false;
 193   CoalescerPair CP(VirtReg.reg(), PhysReg, TRI);
 194
 195   for (MCRegUnit Unit : TRI.regunits(PhysReg)) {
 196     const LiveRange &UnitRange = LIS.getRegUnit(Unit);
 197     if (VirtReg.overlaps(UnitRange, CP, *LIS.getSlotIndexes()))
 198       return true;
 199   }
 200   return false;
 201 }
 202
 203 template <typename AnalysisType>
 204 static void doTest(StringRef MIRFunc,
 205                    typename TestPassT<AnalysisType>::TestFx T,
 206                    bool ShouldPass = true) {
 207   LLVMContext Context;
 208   std::unique_ptr<TargetMachine> TM = createTargetMachine();
 209   // This test is designed for the X86 backend; stop if it is not available.
 210   if (!TM)
 211     return;
 212
 213   legacy::PassManager PM;
 214   std::unique_ptr<MIRParser> MIR;
 215   std::unique_ptr<Module> M = parseMIR(Context, PM, MIR, *TM, MIRFunc);
 216   ASSERT_TRUE(M);
 217
 218   PM.add(new TestPassT<AnalysisType>(T, ShouldPass));
 219
 220   PM.run(*M);
 221 }
 222
 223 static void liveIntervalTest(StringRef MIRFunc,
 224                              TestPassT<LiveIntervalsWrapperPass>::TestFx T,
 225                              bool ShouldPass = true) {
 226   SmallString<160> S;
 227   StringRef MIRString = (Twine(R"MIR(
 228 ---
 229 ...
 230 name: func
 231 registers:
 232   - { id: 0, class: sreg_64 }
 233 body: |
 234   bb.0:
 235 )MIR") + Twine(MIRFunc) + Twine("...\n")).toNullTerminatedStringRef(S);
 236
 237   doTest<LiveIntervalsWrapperPass>(MIRString, T, ShouldPass);
 238 }
 239
 240 static void liveVariablesTest(StringRef MIRFunc,
 241                               TestPassT<LiveVariablesWrapperPass>::TestFx T,
 242                               bool ShouldPass = true) {
 243   SmallString<160> S;
 244   StringRef MIRString = (Twine(R"MIR(
 245 ---
 246 ...
 247 name: func
 248 tracksRegLiveness: true
 249 registers:
 250   - { id: 0, class: sreg_64 }
 251 body: |
 252   bb.0:
 253 )MIR") + Twine(MIRFunc) + Twine("...\n")).toNullTerminatedStringRef(S);
 254   doTest<LiveVariablesWrapperPass>(MIRString, T, ShouldPass);
 255 }
 256
 257 } // End of anonymous namespace.
 258
 259 char TestPass::ID = 0;
 260 INITIALIZE_PASS(TestPass, "testpass", "testpass", false, false)
 261
 262 TEST(LiveIntervalTest, MoveUpDef) {
 263   // Value defined.
 264   liveIntervalTest(
 265       R"MIR(
 266     S_NOP 0
 267     S_NOP 0
 268     early-clobber %0 = IMPLICIT_DEF
 269     S_NOP 0, implicit %0
 270 )MIR",
 271       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 272         testHandleMove(MF, LISWrapper.getLIS(), 2, 1);
 273       });
 274 }
 275
 276 TEST(LiveIntervalTest, MoveUpRedef) {
 277   liveIntervalTest(R"MIR(
 278     %0 = IMPLICIT_DEF
 279     S_NOP 0
 280     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 281     S_NOP 0, implicit %0
 282 )MIR",
 283                    [](MachineFunction &MF, LiveIntervalsWrapperPass &LIS) {
 284                      testHandleMove(MF, LIS.getLIS(), 2, 1);
 285                    });
 286 }
 287
 288 TEST(LiveIntervalTest, MoveUpEarlyDef) {
 289   liveIntervalTest(
 290       R"MIR(
 291     S_NOP 0
 292     S_NOP 0
 293     early-clobber %0 = IMPLICIT_DEF
 294     S_NOP 0, implicit %0
 295 )MIR",
 296       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 297         testHandleMove(MF, LISWrapper.getLIS(), 2, 1);
 298       });
 299 }
 300
 301 TEST(LiveIntervalTest, MoveUpEarlyRedef) {
 302   liveIntervalTest(
 303       R"MIR(
 304     %0 = IMPLICIT_DEF
 305     S_NOP 0
 306     early-clobber %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 307     S_NOP 0, implicit %0
 308 )MIR",
 309       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 310         testHandleMove(MF, LISWrapper.getLIS(), 2, 1);
 311       });
 312 }
 313
 314 TEST(LiveIntervalTest, MoveUpKill) {
 315   liveIntervalTest(
 316       R"MIR(
 317     %0 = IMPLICIT_DEF
 318     S_NOP 0
 319     S_NOP 0, implicit %0
 320 )MIR",
 321       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 322         testHandleMove(MF, LISWrapper.getLIS(), 2, 1);
 323       });
 324 }
 325
 326 TEST(LiveIntervalTest, MoveUpKillFollowing) {
 327   liveIntervalTest(
 328       R"MIR(
 329     %0 = IMPLICIT_DEF
 330     S_NOP 0
 331     S_NOP 0, implicit %0
 332     S_NOP 0, implicit %0
 333 )MIR",
 334       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 335         testHandleMove(MF, LISWrapper.getLIS(), 2, 1);
 336       });
 337 }
 338
 339 // TODO: Construct a situation where we have intervals following a hole
 340 // while still having connected components.
 341
 342 TEST(LiveIntervalTest, MoveDownDef) {
 343   // Value defined.
 344   liveIntervalTest(
 345       R"MIR(
 346     S_NOP 0
 347     early-clobber %0 = IMPLICIT_DEF
 348     S_NOP 0
 349     S_NOP 0, implicit %0
 350 )MIR",
 351       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 352         testHandleMove(MF, LISWrapper.getLIS(), 1, 2);
 353       });
 354 }
 355
 356 TEST(LiveIntervalTest, MoveDownRedef) {
 357   liveIntervalTest(
 358       R"MIR(
 359     %0 = IMPLICIT_DEF
 360     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 361     S_NOP 0
 362     S_NOP 0, implicit %0
 363 )MIR",
 364       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 365         testHandleMove(MF, LISWrapper.getLIS(), 1, 2);
 366       });
 367 }
 368
 369 TEST(LiveIntervalTest, MoveDownEarlyDef) {
 370   liveIntervalTest(
 371       R"MIR(
 372     S_NOP 0
 373     early-clobber %0 = IMPLICIT_DEF
 374     S_NOP 0
 375     S_NOP 0, implicit %0
 376 )MIR",
 377       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 378         testHandleMove(MF, LISWrapper.getLIS(), 1, 2);
 379       });
 380 }
 381
 382 TEST(LiveIntervalTest, MoveDownEarlyRedef) {
 383   liveIntervalTest(
 384       R"MIR(
 385     %0 = IMPLICIT_DEF
 386     early-clobber %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 387     S_NOP 0
 388     S_NOP 0, implicit %0
 389 )MIR",
 390       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 391         testHandleMove(MF, LISWrapper.getLIS(), 1, 2);
 392       });
 393 }
 394
 395 TEST(LiveIntervalTest, MoveDownKill) {
 396   liveIntervalTest(
 397       R"MIR(
 398     %0 = IMPLICIT_DEF
 399     S_NOP 0, implicit %0
 400     S_NOP 0
 401 )MIR",
 402       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 403         testHandleMove(MF, LISWrapper.getLIS(), 1, 2);
 404       });
 405 }
 406
 407 TEST(LiveIntervalTest, MoveDownKillFollowing) {
 408   liveIntervalTest(
 409       R"MIR(
 410     %0 = IMPLICIT_DEF
 411     S_NOP 0
 412     S_NOP 0, implicit %0
 413     S_NOP 0, implicit %0
 414 )MIR",
 415       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 416         testHandleMove(MF, LISWrapper.getLIS(), 1, 2);
 417       });
 418 }
 419
 420 TEST(LiveIntervalTest, MoveUndefUse) {
 421   liveIntervalTest(
 422       R"MIR(
 423     %0 = IMPLICIT_DEF
 424     S_NOP 0, implicit undef %0
 425     S_NOP 0, implicit %0
 426     S_NOP 0
 427 )MIR",
 428       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 429         testHandleMove(MF, LISWrapper.getLIS(), 1, 3);
 430       });
 431 }
 432
 433 TEST(LiveIntervalTest, MoveUpValNos) {
 434   // handleMoveUp() had a bug where it would reuse the value number of the
 435   // destination segment, even though we have no guarantee that this valno
 436   // wasn't used in other segments.
 437   liveIntervalTest(
 438       R"MIR(
 439     successors: %bb.1, %bb.2
 440     %0 = IMPLICIT_DEF
 441     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
 442     S_BRANCH %bb.1
 443   bb.2:
 444     S_NOP 0, implicit %0
 445   bb.1:
 446     successors: %bb.2
 447     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 448     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 449     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 450     S_BRANCH %bb.2
 451 )MIR",
 452       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 453         testHandleMove(MF, LISWrapper.getLIS(), 2, 0, 2);
 454       });
 455 }
 456
 457 TEST(LiveIntervalTest, MoveOverUndefUse0) {
 458   // findLastUseBefore() used by handleMoveUp() must ignore undef operands.
 459   liveIntervalTest(
 460       R"MIR(
 461     %0 = IMPLICIT_DEF
 462     S_NOP 0
 463     S_NOP 0, implicit undef %0
 464     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 465 )MIR",
 466       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 467         testHandleMove(MF, LISWrapper.getLIS(), 3, 1);
 468       });
 469 }
 470
 471 TEST(LiveIntervalTest, MoveOverUndefUse1) {
 472   // findLastUseBefore() used by handleMoveUp() must ignore undef operands.
 473   liveIntervalTest(
 474       R"MIR(
 475     $sgpr0 = IMPLICIT_DEF
 476     S_NOP 0
 477     S_NOP 0, implicit undef $sgpr0
 478     $sgpr0 = IMPLICIT_DEF implicit $sgpr0(tied-def 0)
 479 )MIR",
 480       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 481         testHandleMove(MF, LISWrapper.getLIS(), 3, 1);
 482       });
 483 }
 484
 485 TEST(LiveIntervalTest, SubRegMoveDown) {
 486   // Subregister ranges can have holes inside a basic block. Check for a
 487   // movement of the form 32->150 in a liverange [16, 32) [100,200).
 488   liveIntervalTest(
 489       R"MIR(
 490     successors: %bb.1, %bb.2
 491     %0 = IMPLICIT_DEF
 492     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
 493     S_BRANCH %bb.1
 494   bb.2:
 495     successors: %bb.1
 496     S_NOP 0, implicit %0.sub0
 497     S_NOP 0, implicit %0.sub1
 498     S_NOP 0
 499     undef %0.sub0 = IMPLICIT_DEF
 500     %0.sub1 = IMPLICIT_DEF
 501   bb.1:
 502     S_NOP 0, implicit %0
 503 )MIR",
 504       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 505         // Scheduler behaviour: Clear def,read-undef flag and move.
 506         MachineInstr &MI = getMI(MF, 3, /*BlockNum=*/1);
 507         MI.getOperand(0).setIsUndef(false);
 508         testHandleMove(MF, LISWrapper.getLIS(), 1, 4, /*BlockNum=*/1);
 509       });
 510 }
 511
 512 TEST(LiveIntervalTest, SubRegMoveUp) {
 513   // handleMoveUp had a bug not updating valno of segment incoming to bb.2
 514   // after swapping subreg definitions.
 515   liveIntervalTest(
 516       R"MIR(
 517     successors: %bb.1, %bb.2
 518     undef %0.sub0 = IMPLICIT_DEF
 519     %0.sub1 = IMPLICIT_DEF
 520     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
 521     S_BRANCH %bb.1
 522   bb.1:
 523     S_NOP 0, implicit %0.sub1
 524   bb.2:
 525     S_NOP 0, implicit %0.sub1
 526 )MIR",
 527       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 528         testHandleMove(MF, LISWrapper.getLIS(), 1, 0);
 529       });
 530 }
 531
 532 TEST(LiveIntervalTest, DeadSubRegMoveUp) {
 533   // handleMoveUp had a bug where moving a dead subreg def into the middle of
 534   // an earlier segment resulted in an invalid live range.
 535   liveIntervalTest(
 536       R"MIR(
 537     undef %125.sub0:vreg_128 = V_MOV_B32_e32 0, implicit $exec
 538     %125.sub1:vreg_128 = COPY %125.sub0
 539     %125.sub2:vreg_128 = COPY %125.sub0
 540     undef %51.sub0:vreg_128 = V_MOV_B32_e32 898625526, implicit $exec
 541     %51.sub1:vreg_128 = COPY %51.sub0
 542     %51.sub2:vreg_128 = COPY %51.sub0
 543     %52:vgpr_32 = V_MOV_B32_e32 986714345, implicit $exec
 544     %54:vgpr_32 = V_MOV_B32_e32 1742342378, implicit $exec
 545     %57:vgpr_32 = V_MOV_B32_e32 3168768712, implicit $exec
 546     %59:vgpr_32 = V_MOV_B32_e32 1039972644, implicit $exec
 547     %60:vgpr_32 = nofpexcept V_MAD_F32_e64 0, %52, 0, undef %61:vgpr_32, 0, %59, 0, 0, implicit $mode, implicit $exec
 548     %63:vgpr_32 = nofpexcept V_ADD_F32_e32 %51.sub3, undef %64:vgpr_32, implicit $mode, implicit $exec
 549     dead %66:vgpr_32 = nofpexcept V_MAD_F32_e64 0, %60, 0, undef %67:vgpr_32, 0, %125.sub2, 0, 0, implicit $mode, implicit $exec
 550     undef %124.sub1:vreg_128 = nofpexcept V_MAD_F32_e64 0, %57, 0, undef %70:vgpr_32, 0, %125.sub1, 0, 0, implicit $mode, implicit $exec
 551     %124.sub0:vreg_128 = nofpexcept V_MAD_F32_e64 0, %54, 0, undef %73:vgpr_32, 0, %125.sub0, 0, 0, implicit $mode, implicit $exec
 552     dead undef %125.sub3:vreg_128 = nofpexcept V_MAC_F32_e32 %63, undef %76:vgpr_32, %125.sub3, implicit $mode, implicit $exec
 553 )MIR",
 554       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 555         testHandleMove(MF, LISWrapper.getLIS(), 15, 12);
 556       });
 557 }
 558
 559 TEST(LiveIntervalTest, EarlyClobberSubRegMoveUp) {
 560   // handleMoveUp had a bug where moving an early-clobber subreg def into the
 561   // middle of an earlier segment resulted in an invalid live range.
 562   liveIntervalTest(
 563       R"MIR(
 564     %4:sreg_32 = IMPLICIT_DEF
 565     %6:sreg_32 = IMPLICIT_DEF
 566     undef early-clobber %9.sub0:sreg_64 = STRICT_WWM %4:sreg_32, implicit $exec
 567     %5:sreg_32 = S_FLBIT_I32_B32 %9.sub0:sreg_64
 568     early-clobber %9.sub1:sreg_64 = STRICT_WWM %6:sreg_32, implicit $exec
 569     %7:sreg_32 = S_FLBIT_I32_B32 %9.sub1:sreg_64
 570 )MIR",
 571       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 572         testHandleMove(MF, LISWrapper.getLIS(), 4, 3);
 573       });
 574 }
 575
 576 TEST(LiveIntervalTest, TestMoveSubRegDefAcrossUseDef) {
 577   liveIntervalTest(
 578       R"MIR(
 579     %1:vreg_64 = IMPLICIT_DEF
 580
 581   bb.1:
 582     %2:vgpr_32 = V_MOV_B32_e32 2, implicit $exec
 583     %3:vgpr_32 = V_ADD_U32_e32 %2, %1.sub0, implicit $exec
 584     undef %1.sub0:vreg_64 = V_ADD_U32_e32 %2, %2, implicit $exec
 585     %1.sub1:vreg_64 = COPY %2
 586     S_NOP 0, implicit %1.sub1
 587     S_BRANCH %bb.1
 588
 589 )MIR",
 590       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 591         MachineInstr &UndefSubregDef = getMI(MF, 2, 1);
 592         // The scheduler clears undef from subregister defs before moving
 593         UndefSubregDef.getOperand(0).setIsUndef(false);
 594         testHandleMove(MF, LISWrapper.getLIS(), 3, 1, 1);
 595       });
 596 }
 597
 598 TEST(LiveIntervalTest, TestMoveSubRegDefAcrossUseDefMulti) {
 599   liveIntervalTest(
 600       R"MIR(
 601     %1:vreg_96 = IMPLICIT_DEF
 602
 603   bb.1:
 604     %2:vgpr_32 = V_MOV_B32_e32 2, implicit $exec
 605     %3:vgpr_32 = V_ADD_U32_e32 %2, %1.sub0, implicit $exec
 606     undef %1.sub0:vreg_96 = V_ADD_U32_e32 %2, %2, implicit $exec
 607     %1.sub1:vreg_96 = COPY %2
 608     %1.sub2:vreg_96 = COPY %2
 609     S_NOP 0, implicit %1.sub1, implicit %1.sub2
 610     S_BRANCH %bb.1
 611
 612 )MIR",
 613       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 614         MachineInstr &UndefSubregDef = getMI(MF, 2, 1);
 615         // The scheduler clears undef from subregister defs before moving
 616         UndefSubregDef.getOperand(0).setIsUndef(false);
 617         testHandleMove(MF, LISWrapper.getLIS(), 4, 1, 1);
 618       });
 619 }
 620
 621 TEST(LiveIntervalTest, TestMoveSubRegUseAcrossMainRangeHole) {
 622   liveIntervalTest(
 623       R"MIR(
 624     %1:sgpr_128 = IMPLICIT_DEF
 625   bb.1:
 626     %2:sgpr_32 = COPY %1.sub2
 627     %3:sgpr_32 = COPY %1.sub1
 628     %1.sub2 = COPY %2
 629     undef %1.sub0 = IMPLICIT_DEF
 630     %1.sub2 = IMPLICIT_DEF
 631     S_CBRANCH_SCC1 %bb.1, implicit undef $scc
 632     S_BRANCH %bb.2
 633   bb.2:
 634 )MIR",
 635       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 636         MachineInstr &MI = getMI(MF, 3, /*BlockNum=*/1);
 637         MI.getOperand(0).setIsUndef(false);
 638         testHandleMove(MF, LISWrapper.getLIS(), 4, 3, 1);
 639         testHandleMove(MF, LISWrapper.getLIS(), 1, 4, 1);
 640       });
 641 }
 642
 643 TEST(LiveIntervalTest, TestMoveSubRegsOfOneReg) {
 644   liveIntervalTest(
 645       R"MIR(
 646     INLINEASM &"", 0, 1835018, def undef %4.sub0:vreg_64, 1835018, def undef %4.sub1:vreg_64
 647     %1:vreg_64 = COPY %4
 648     undef %2.sub0:vreg_64 = V_MOV_B32_e32 0, implicit $exec
 649     %2.sub1:vreg_64 = COPY %2.sub0
 650     %3:vreg_64 = COPY %2
 651 )MIR",
 652       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 653         testHandleMove(MF, LISWrapper.getLIS(), 1, 4);
 654         testHandleMove(MF, LISWrapper.getLIS(), 0, 3);
 655       });
 656 }
 657
 658 TEST(LiveIntervalTest, BundleUse) {
 659   liveIntervalTest(
 660       R"MIR(
 661     %0 = IMPLICIT_DEF
 662     S_NOP 0
 663     S_NOP 0, implicit %0
 664     S_NOP 0
 665 )MIR",
 666       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 667         testHandleMoveIntoNewBundle(MF, LISWrapper.getLIS(), 1, 2);
 668       });
 669 }
 670
 671 TEST(LiveIntervalTest, BundleDef) {
 672   liveIntervalTest(
 673       R"MIR(
 674     %0 = IMPLICIT_DEF
 675     S_NOP 0
 676     S_NOP 0, implicit %0
 677     S_NOP 0
 678 )MIR",
 679       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 680         testHandleMoveIntoNewBundle(MF, LISWrapper.getLIS(), 0, 1);
 681       });
 682 }
 683
 684 TEST(LiveIntervalTest, BundleRedef) {
 685   liveIntervalTest(
 686       R"MIR(
 687     %0 = IMPLICIT_DEF
 688     S_NOP 0
 689     %0 = IMPLICIT_DEF implicit %0(tied-def 0)
 690     S_NOP 0, implicit %0
 691 )MIR",
 692       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 693         testHandleMoveIntoNewBundle(MF, LISWrapper.getLIS(), 1, 2);
 694       });
 695 }
 696
 697 TEST(LiveIntervalTest, BundleInternalUse) {
 698   liveIntervalTest(
 699       R"MIR(
 700     %0 = IMPLICIT_DEF
 701     S_NOP 0
 702     S_NOP 0, implicit %0
 703     S_NOP 0
 704 )MIR",
 705       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 706         testHandleMoveIntoNewBundle(MF, LISWrapper.getLIS(), 0, 2);
 707       });
 708 }
 709
 710 TEST(LiveIntervalTest, BundleUndefUse) {
 711   liveIntervalTest(
 712       R"MIR(
 713     %0 = IMPLICIT_DEF
 714     S_NOP 0
 715     S_NOP 0, implicit undef %0
 716     S_NOP 0
 717 )MIR",
 718       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 719         testHandleMoveIntoNewBundle(MF, LISWrapper.getLIS(), 1, 2);
 720       });
 721 }
 722
 723 TEST(LiveIntervalTest, BundleSubRegUse) {
 724   liveIntervalTest(
 725       R"MIR(
 726     successors: %bb.1, %bb.2
 727     undef %0.sub0 = IMPLICIT_DEF
 728     %0.sub1 = IMPLICIT_DEF
 729     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
 730     S_BRANCH %bb.1
 731   bb.1:
 732     S_NOP 0
 733     S_NOP 0, implicit %0.sub1
 734   bb.2:
 735     S_NOP 0, implicit %0.sub1
 736 )MIR",
 737       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 738         testHandleMoveIntoNewBundle(MF, LISWrapper.getLIS(), 0, 1, 1);
 739       });
 740 }
 741
 742 TEST(LiveIntervalTest, BundleSubRegDef) {
 743   liveIntervalTest(
 744       R"MIR(
 745     successors: %bb.1, %bb.2
 746     undef %0.sub0 = IMPLICIT_DEF
 747     %0.sub1 = IMPLICIT_DEF
 748     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
 749     S_BRANCH %bb.1
 750   bb.1:
 751     S_NOP 0
 752     S_NOP 0, implicit %0.sub1
 753   bb.2:
 754     S_NOP 0, implicit %0.sub1
 755 )MIR",
 756       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 757         testHandleMoveIntoNewBundle(MF, LISWrapper.getLIS(), 0, 1, 0);
 758       });
 759 }
 760
 761 TEST(LiveIntervalTest, SplitAtOneInstruction) {
 762   liveIntervalTest(
 763       R"MIR(
 764     successors: %bb.1
 765     %0 = IMPLICIT_DEF
 766     S_BRANCH %bb.1
 767   bb.1:
 768     S_NOP 0
 769 )MIR",
 770       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 771         testSplitAt(MF, LISWrapper.getLIS(), 1, 0);
 772       });
 773 }
 774
 775 TEST(LiveIntervalTest, SplitAtMultiInstruction) {
 776   liveIntervalTest(
 777       R"MIR(
 778     successors: %bb.1
 779     %0 = IMPLICIT_DEF
 780     S_NOP 0
 781     S_NOP 0
 782     S_NOP 0
 783     S_NOP 0
 784     S_BRANCH %bb.1
 785   bb.1:
 786     S_NOP 0
 787 )MIR",
 788       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 789         testSplitAt(MF, LISWrapper.getLIS(), 0, 0);
 790       });
 791 }
 792
 793 TEST(LiveIntervalTest, RepairIntervals) {
 794   liveIntervalTest(
 795       R"MIR(
 796   %1:sgpr_32 = IMPLICIT_DEF
 797   dead %2:sgpr_32 = COPY undef %3.sub0:sgpr_128
 798   undef %4.sub2:sgpr_128 = COPY %1:sgpr_32
 799   %5:sgpr_32 = COPY %4.sub2:sgpr_128
 800 )MIR",
 801       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 802         auto &LIS = LISWrapper.getLIS();
 803         MachineInstr &Instr1 = getMI(MF, 1, 0);
 804         MachineInstr &Instr2 = getMI(MF, 2, 0);
 805         MachineInstr &Instr3 = getMI(MF, 3, 0);
 806         LIS.RemoveMachineInstrFromMaps(Instr2);
 807         MachineBasicBlock *MBB = Instr1.getParent();
 808         SmallVector<Register> OrigRegs{
 809             Instr1.getOperand(0).getReg(),
 810             Instr2.getOperand(0).getReg(),
 811             Instr2.getOperand(1).getReg(),
 812         };
 813         LIS.repairIntervalsInRange(MBB, Instr2, Instr3, OrigRegs);
 814       });
 815 }
 816
 817 TEST(LiveIntervalTest, AdjacentIntervals) {
 818   liveIntervalTest(
 819       R"MIR(
 820     successors: %bb.1, %bb.2
 821
 822     $vgpr1 = IMPLICIT_DEF
 823     S_NOP 0, implicit $vgpr1
 824     %1:vgpr_32 = IMPLICIT_DEF
 825     %2:vgpr_32 = IMPLICIT_DEF
 826     S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
 827     S_BRANCH %bb.1
 828   bb.1:
 829     $vgpr0, dead renamable $vcc = V_ADD_CO_U32_e64 %1, %2, 0, implicit $exec
 830     S_NOP 0, implicit $vgpr0
 831     S_BRANCH %bb.3
 832   bb.2:
 833     $vgpr0 = IMPLICIT_DEF
 834     $vgpr1, dead renamable $vcc = V_ADD_CO_U32_e64 %1, %2, 0, implicit $exec
 835     S_NOP 0, implicit $vgpr0, implicit $vgpr1
 836     S_BRANCH %bb.3
 837   bb.3:
 838 )MIR",
 839       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 840         auto &LIS = LISWrapper.getLIS();
 841         const auto &R1 =
 842             LIS.getInterval(getMI(MF, 2, 0).getOperand(0).getReg());
 843         const auto &R2 =
 844             LIS.getInterval(getMI(MF, 3, 0).getOperand(0).getReg());
 845         MCRegister V1 = getMI(MF, 1, 2).getOperand(0).getReg().asMCReg();
 846
 847         ASSERT_FALSE(checkRegUnitInterference(
 848             LIS, *MF.getSubtarget().getRegisterInfo(), R1, V1));
 849         ASSERT_FALSE(checkRegUnitInterference(
 850             LIS, *MF.getSubtarget().getRegisterInfo(), R2, V1));
 851       });
 852 }
 853
 854 TEST(LiveIntervalTest, LiveThroughSegments) {
 855   liveIntervalTest(
 856       R"MIR(
 857     %0 = IMPLICIT_DEF
 858     S_BRANCH %bb.2
 859   bb.1:
 860     S_NOP 0, implicit %0
 861     S_ENDPGM 0
 862   bb.2:
 863     S_BRANCH %bb.1
 864 )MIR",
 865       [](MachineFunction &MF, LiveIntervalsWrapperPass &LISWrapper) {
 866         auto &LIS = LISWrapper.getLIS();
 867         MachineInstr &ImpDef = getMI(MF, 0, 0);
 868         MachineInstr &Nop = getMI(MF, 0, 1);
 869         LiveInterval &LI = LIS.getInterval(ImpDef.getOperand(0).getReg());
 870         SlotIndex OrigIdx = LIS.getInstructionIndex(ImpDef).getRegSlot();
 871         LiveInterval::iterator FirstSeg = LI.FindSegmentContaining(OrigIdx);
 872
 873         // %0 is live through bb.2. Move its def into bb.1 and update LIS but do
 874         // not remove the segment for bb.2. This should cause machine
 875         // verification to fail.
 876         LIS.RemoveMachineInstrFromMaps(ImpDef);
 877         ImpDef.moveBefore(&Nop);
 878         LIS.InsertMachineInstrInMaps(ImpDef);
 879
 880         SlotIndex NewIdx = LIS.getInstructionIndex(ImpDef).getRegSlot();
 881         FirstSeg->start = NewIdx;
 882         FirstSeg->valno->def = NewIdx;
 883       },
 884       false);
 885 }
 886
 887 TEST(LiveVariablesTest, recomputeForSingleDefVirtReg_handle_undef1) {
 888   liveVariablesTest(
 889       R"MIR(
 890     %0 = IMPLICIT_DEF
 891     S_NOP 0, implicit %0
 892     S_NOP 0, implicit undef %0
 893 )MIR",
 894       [](MachineFunction &MF, LiveVariablesWrapperPass &LVWrapper) {
 895         auto &LV = LVWrapper.getLV();
 896         auto &FirstNop = getMI(MF, 1, 0);
 897         auto &SecondNop = getMI(MF, 2, 0);
 898         EXPECT_TRUE(FirstNop.getOperand(1).isKill());
 899         EXPECT_FALSE(SecondNop.getOperand(1).isKill());
 900
 901         Register R = Register::index2VirtReg(0);
 902         LV.recomputeForSingleDefVirtReg(R);
 903
 904         EXPECT_TRUE(FirstNop.getOperand(1).isKill());
 905         EXPECT_FALSE(SecondNop.getOperand(1).isKill());
 906       });
 907 }
 908
 909 TEST(LiveVariablesTest, recomputeForSingleDefVirtReg_handle_undef2) {
 910   liveVariablesTest(
 911       R"MIR(
 912     %0 = IMPLICIT_DEF
 913     S_NOP 0, implicit %0
 914     S_NOP 0, implicit undef %0, implicit %0
 915 )MIR",
 916       [](MachineFunction &MF, LiveVariablesWrapperPass &LVWrapper) {
 917         auto &LV = LVWrapper.getLV();
 918         auto &FirstNop = getMI(MF, 1, 0);
 919         auto &SecondNop = getMI(MF, 2, 0);
 920         EXPECT_FALSE(FirstNop.getOperand(1).isKill());
 921         EXPECT_FALSE(SecondNop.getOperand(1).isKill());
 922         EXPECT_TRUE(SecondNop.getOperand(2).isKill());
 923
 924         Register R = Register::index2VirtReg(0);
 925         LV.recomputeForSingleDefVirtReg(R);
 926
 927         EXPECT_FALSE(FirstNop.getOperand(1).isKill());
 928         EXPECT_FALSE(SecondNop.getOperand(1).isKill());
 929         EXPECT_TRUE(SecondNop.getOperand(2).isKill());
 930       });
 931 }
 932
 933 int main(int argc, char **argv) {
 934   ::testing::InitGoogleTest(&argc, argv);
 935   initLLVM();
 936   return RUN_ALL_TESTS();
 937 }