1 //===------------- llvm/unittest/CodeGen/InstrRefLDVTest.cpp --------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/CodeGen/CodeGenTargetMachineImpl.h" 10 #include "llvm/CodeGen/MIRParser/MIRParser.h" 11 #include "llvm/CodeGen/MachineDominators.h" 12 #include "llvm/CodeGen/MachineModuleInfo.h" 13 #include "llvm/CodeGen/TargetFrameLowering.h" 14 #include "llvm/CodeGen/TargetInstrInfo.h" 15 #include "llvm/CodeGen/TargetLowering.h" 16 #include "llvm/CodeGen/TargetRegisterInfo.h" 17 #include "llvm/CodeGen/TargetSubtargetInfo.h" 18 #include "llvm/IR/DIBuilder.h" 19 #include "llvm/IR/DebugInfoMetadata.h" 20 #include "llvm/IR/IRBuilder.h" 21 #include "llvm/IR/Module.h" 22 #include "llvm/MC/TargetRegistry.h" 23 #include "llvm/Support/MemoryBuffer.h" 24 #include "llvm/Support/TargetSelect.h" 25 #include "llvm/Target/TargetOptions.h" 26 27 #include "../lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h" 28 29 #include "gtest/gtest.h" 30 31 using namespace llvm; 32 using namespace LiveDebugValues; 33 34 // Include helper functions to ease the manipulation of MachineFunctions 35 #include "MFCommon.inc" 36 37 class InstrRefLDVTest : public testing::Test { 38 public: 39 friend class InstrRefBasedLDV; 40 using MLocTransferMap = InstrRefBasedLDV::MLocTransferMap; 41 42 LLVMContext Ctx; 43 std::unique_ptr<Module> Mod; 44 std::unique_ptr<TargetMachine> Machine; 45 std::unique_ptr<MachineFunction> MF; 46 std::unique_ptr<MachineDominatorTree> DomTree; 47 std::unique_ptr<MachineModuleInfo> MMI; 48 DICompileUnit *OurCU; 49 DIFile *OurFile; 50 DISubprogram *OurFunc; 51 DILexicalBlock *OurBlock, *AnotherBlock; 52 DISubprogram *ToInlineFunc; 53 DILexicalBlock *ToInlineBlock; 54 DILocalVariable *FuncVariable; 55 DIBasicType *LongInt; 56 DIExpression *EmptyExpr; 57 LiveDebugValues::OverlapMap Overlaps; 58 LiveDebugValues::DebugVariableMap DVMap; 59 60 DebugLoc OutermostLoc, InBlockLoc, NotNestedBlockLoc, InlinedLoc; 61 62 MachineBasicBlock *MBB0, *MBB1, *MBB2, *MBB3, *MBB4; 63 64 std::unique_ptr<InstrRefBasedLDV> LDV; 65 std::unique_ptr<MLocTracker> MTracker; 66 std::unique_ptr<VLocTracker> VTracker; 67 68 SmallString<256> MIRStr; 69 70 InstrRefLDVTest() : Ctx(), Mod(std::make_unique<Module>("beehives", Ctx)) {} 71 72 void SetUp() { 73 // Boilerplate that creates a MachineFunction and associated blocks. 74 75 Mod->setDataLayout("e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-" 76 "f80:128-n8:16:32:64-S128"); 77 Triple TargetTriple("x86_64--"); 78 std::string Error; 79 const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error); 80 if (!T) 81 GTEST_SKIP(); 82 83 TargetOptions Options; 84 Machine = std::unique_ptr<TargetMachine>(T->createTargetMachine( 85 Triple::normalize("x86_64--"), "", "", Options, std::nullopt, 86 std::nullopt, CodeGenOptLevel::Aggressive)); 87 88 auto Type = FunctionType::get(Type::getVoidTy(Ctx), false); 89 auto F = 90 Function::Create(Type, GlobalValue::ExternalLinkage, "Test", &*Mod); 91 92 unsigned FunctionNum = 42; 93 MMI = std::make_unique<MachineModuleInfo>(Machine.get()); 94 const TargetSubtargetInfo &STI = *Machine->getSubtargetImpl(*F); 95 96 MF = std::make_unique<MachineFunction>(*F, *Machine, STI, MMI->getContext(), 97 FunctionNum); 98 99 // Create metadata: CU, subprogram, some blocks and an inline function 100 // scope. 101 DIBuilder DIB(*Mod); 102 OurFile = DIB.createFile("xyzzy.c", "/cave"); 103 OurCU = 104 DIB.createCompileUnit(dwarf::DW_LANG_C99, OurFile, "nou", false, "", 0); 105 auto OurSubT = DIB.createSubroutineType(DIB.getOrCreateTypeArray({})); 106 OurFunc = 107 DIB.createFunction(OurCU, "bees", "", OurFile, 1, OurSubT, 1, 108 DINode::FlagZero, DISubprogram::SPFlagDefinition); 109 F->setSubprogram(OurFunc); 110 OurBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 3); 111 AnotherBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 6); 112 ToInlineFunc = 113 DIB.createFunction(OurFile, "shoes", "", OurFile, 10, OurSubT, 10, 114 DINode::FlagZero, DISubprogram::SPFlagDefinition); 115 116 // Make some nested scopes. 117 OutermostLoc = DILocation::get(Ctx, 3, 1, OurFunc); 118 InBlockLoc = DILocation::get(Ctx, 4, 1, OurBlock); 119 InlinedLoc = DILocation::get(Ctx, 10, 1, ToInlineFunc, InBlockLoc.get()); 120 121 // Make a scope that isn't nested within the others. 122 NotNestedBlockLoc = DILocation::get(Ctx, 4, 1, AnotherBlock); 123 124 LongInt = DIB.createBasicType("long", 64, llvm::dwarf::DW_ATE_unsigned); 125 FuncVariable = DIB.createAutoVariable(OurFunc, "lala", OurFile, 1, LongInt); 126 EmptyExpr = DIExpression::get(Ctx, {}); 127 128 DIB.finalize(); 129 } 130 131 Register getRegByName(const char *WantedName) { 132 auto *TRI = MF->getRegInfo().getTargetRegisterInfo(); 133 // Slow, but works. 134 for (unsigned int I = 1; I < TRI->getNumRegs(); ++I) { 135 const char *Name = TRI->getName(I); 136 if (strcmp(WantedName, Name) == 0) 137 return I; 138 } 139 140 // If this ever fails, something is very wrong with this unit test. 141 llvm_unreachable("Can't find register by name"); 142 } 143 144 InstrRefBasedLDV *setupLDVObj(MachineFunction *MF) { 145 // Create a new LDV object, and plug some relevant object ptrs into it. 146 LDV = std::make_unique<InstrRefBasedLDV>(); 147 const TargetSubtargetInfo &STI = MF->getSubtarget(); 148 LDV->TII = STI.getInstrInfo(); 149 LDV->TRI = STI.getRegisterInfo(); 150 LDV->TFI = STI.getFrameLowering(); 151 LDV->MFI = &MF->getFrameInfo(); 152 LDV->MRI = &MF->getRegInfo(); 153 154 DomTree = std::make_unique<MachineDominatorTree>(*MF); 155 LDV->DomTree = &*DomTree; 156 157 // Future work: unit tests for mtracker / vtracker / ttracker. 158 159 // Setup things like the artifical block map, and BlockNo <=> RPO Order 160 // mappings. 161 LDV->initialSetup(*MF); 162 LDV->LS.initialize(*MF); 163 addMTracker(MF); 164 return &*LDV; 165 } 166 167 void addMTracker(MachineFunction *MF) { 168 ASSERT_TRUE(LDV); 169 // Add a machine-location-tracking object to LDV. Don't initialize any 170 // register locations within it though. 171 const TargetSubtargetInfo &STI = MF->getSubtarget(); 172 MTracker = std::make_unique<MLocTracker>( 173 *MF, *LDV->TII, *LDV->TRI, *STI.getTargetLowering()); 174 LDV->MTracker = &*MTracker; 175 } 176 177 void addVTracker() { 178 ASSERT_TRUE(LDV); 179 VTracker = std::make_unique<VLocTracker>(DVMap, Overlaps, EmptyExpr); 180 LDV->VTracker = &*VTracker; 181 } 182 183 DbgOpID addValueDbgOp(ValueIDNum V) { 184 return LDV->DbgOpStore.insert(DbgOp(V)); 185 } 186 DbgOpID addConstDbgOp(MachineOperand MO) { 187 return LDV->DbgOpStore.insert(DbgOp(MO)); 188 } 189 190 // Some routines for bouncing into LDV, 191 void buildMLocValueMap(FuncValueTable &MInLocs, FuncValueTable &MOutLocs, 192 SmallVectorImpl<MLocTransferMap> &MLocTransfer) { 193 LDV->buildMLocValueMap(*MF, MInLocs, MOutLocs, MLocTransfer); 194 } 195 196 void placeMLocPHIs(MachineFunction &MF, 197 SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks, 198 FuncValueTable &MInLocs, 199 SmallVectorImpl<MLocTransferMap> &MLocTransfer) { 200 LDV->placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer); 201 } 202 203 bool 204 pickVPHILoc(SmallVectorImpl<DbgOpID> &OutValues, const MachineBasicBlock &MBB, 205 const InstrRefBasedLDV::LiveIdxT &LiveOuts, 206 FuncValueTable &MOutLocs, 207 const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) { 208 return LDV->pickVPHILoc(OutValues, MBB, LiveOuts, MOutLocs, BlockOrders); 209 } 210 211 bool vlocJoin(MachineBasicBlock &MBB, InstrRefBasedLDV::LiveIdxT &VLOCOutLocs, 212 SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, 213 DbgValue &InLoc) { 214 return LDV->vlocJoin(MBB, VLOCOutLocs, BlocksToExplore, InLoc); 215 } 216 217 void buildVLocValueMap(const DILocation *DILoc, 218 const SmallSet<DebugVariableID, 4> &VarsWeCareAbout, 219 SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, 220 InstrRefBasedLDV::LiveInsT &Output, FuncValueTable &MOutLocs, 221 FuncValueTable &MInLocs, 222 SmallVectorImpl<VLocTracker> &AllTheVLocs) { 223 LDV->buildVLocValueMap(DILoc, VarsWeCareAbout, AssignBlocks, Output, 224 MOutLocs, MInLocs, AllTheVLocs); 225 } 226 227 void initValueArray(FuncValueTable &Nums, unsigned Blks, unsigned Locs) { 228 for (unsigned int I = 0; I < Blks; ++I) 229 for (unsigned int J = 0; J < Locs; ++J) 230 Nums[I][J] = ValueIDNum::EmptyValue; 231 } 232 233 void setupSingleBlock() { 234 // Add an entry block with nothing but 'ret void' in it. 235 Function &F = const_cast<llvm::Function &>(MF->getFunction()); 236 auto *BB0 = BasicBlock::Create(Ctx, "entry", &F); 237 IRBuilder<> IRB(BB0); 238 IRB.CreateRetVoid(); 239 MBB0 = MF->CreateMachineBasicBlock(BB0); 240 MF->insert(MF->end(), MBB0); 241 MF->RenumberBlocks(); 242 243 setupLDVObj(&*MF); 244 } 245 246 void setupDiamondBlocks() { 247 // entry 248 // / \ 249 // br1 br2 250 // \ / 251 // ret 252 llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction()); 253 auto *BB0 = BasicBlock::Create(Ctx, "a", &F); 254 auto *BB1 = BasicBlock::Create(Ctx, "b", &F); 255 auto *BB2 = BasicBlock::Create(Ctx, "c", &F); 256 auto *BB3 = BasicBlock::Create(Ctx, "d", &F); 257 IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3); 258 IRB0.CreateBr(BB1); 259 IRB1.CreateBr(BB2); 260 IRB2.CreateBr(BB3); 261 IRB3.CreateRetVoid(); 262 MBB0 = MF->CreateMachineBasicBlock(BB0); 263 MF->insert(MF->end(), MBB0); 264 MBB1 = MF->CreateMachineBasicBlock(BB1); 265 MF->insert(MF->end(), MBB1); 266 MBB2 = MF->CreateMachineBasicBlock(BB2); 267 MF->insert(MF->end(), MBB2); 268 MBB3 = MF->CreateMachineBasicBlock(BB3); 269 MF->insert(MF->end(), MBB3); 270 MBB0->addSuccessor(MBB1); 271 MBB0->addSuccessor(MBB2); 272 MBB1->addSuccessor(MBB3); 273 MBB2->addSuccessor(MBB3); 274 MF->RenumberBlocks(); 275 276 setupLDVObj(&*MF); 277 } 278 279 void setupSimpleLoop() { 280 // entry 281 // | 282 // |/-----\ 283 // loopblk | 284 // |\-----/ 285 // | 286 // ret 287 llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction()); 288 auto *BB0 = BasicBlock::Create(Ctx, "entry", &F); 289 auto *BB1 = BasicBlock::Create(Ctx, "loop", &F); 290 auto *BB2 = BasicBlock::Create(Ctx, "ret", &F); 291 IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2); 292 IRB0.CreateBr(BB1); 293 IRB1.CreateBr(BB2); 294 IRB2.CreateRetVoid(); 295 MBB0 = MF->CreateMachineBasicBlock(BB0); 296 MF->insert(MF->end(), MBB0); 297 MBB1 = MF->CreateMachineBasicBlock(BB1); 298 MF->insert(MF->end(), MBB1); 299 MBB2 = MF->CreateMachineBasicBlock(BB2); 300 MF->insert(MF->end(), MBB2); 301 MBB0->addSuccessor(MBB1); 302 MBB1->addSuccessor(MBB2); 303 MBB1->addSuccessor(MBB1); 304 MF->RenumberBlocks(); 305 306 setupLDVObj(&*MF); 307 } 308 309 void setupNestedLoops() { 310 // entry 311 // | 312 // loop1 313 // ^\ 314 // | \ /-\ 315 // | loop2 | 316 // | / \-/ 317 // ^ / 318 // join 319 // | 320 // ret 321 llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction()); 322 auto *BB0 = BasicBlock::Create(Ctx, "entry", &F); 323 auto *BB1 = BasicBlock::Create(Ctx, "loop1", &F); 324 auto *BB2 = BasicBlock::Create(Ctx, "loop2", &F); 325 auto *BB3 = BasicBlock::Create(Ctx, "join", &F); 326 auto *BB4 = BasicBlock::Create(Ctx, "ret", &F); 327 IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4); 328 IRB0.CreateBr(BB1); 329 IRB1.CreateBr(BB2); 330 IRB2.CreateBr(BB3); 331 IRB3.CreateBr(BB4); 332 IRB4.CreateRetVoid(); 333 MBB0 = MF->CreateMachineBasicBlock(BB0); 334 MF->insert(MF->end(), MBB0); 335 MBB1 = MF->CreateMachineBasicBlock(BB1); 336 MF->insert(MF->end(), MBB1); 337 MBB2 = MF->CreateMachineBasicBlock(BB2); 338 MF->insert(MF->end(), MBB2); 339 MBB3 = MF->CreateMachineBasicBlock(BB3); 340 MF->insert(MF->end(), MBB3); 341 MBB4 = MF->CreateMachineBasicBlock(BB4); 342 MF->insert(MF->end(), MBB4); 343 MBB0->addSuccessor(MBB1); 344 MBB1->addSuccessor(MBB2); 345 MBB2->addSuccessor(MBB2); 346 MBB2->addSuccessor(MBB3); 347 MBB3->addSuccessor(MBB1); 348 MBB3->addSuccessor(MBB4); 349 MF->RenumberBlocks(); 350 351 setupLDVObj(&*MF); 352 } 353 354 void setupNoDominatingLoop() { 355 // entry 356 // / \ 357 // / \ 358 // / \ 359 // head1 head2 360 // ^ \ / ^ 361 // ^ \ / ^ 362 // \-joinblk -/ 363 // | 364 // ret 365 llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction()); 366 auto *BB0 = BasicBlock::Create(Ctx, "entry", &F); 367 auto *BB1 = BasicBlock::Create(Ctx, "head1", &F); 368 auto *BB2 = BasicBlock::Create(Ctx, "head2", &F); 369 auto *BB3 = BasicBlock::Create(Ctx, "joinblk", &F); 370 auto *BB4 = BasicBlock::Create(Ctx, "ret", &F); 371 IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4); 372 IRB0.CreateBr(BB1); 373 IRB1.CreateBr(BB2); 374 IRB2.CreateBr(BB3); 375 IRB3.CreateBr(BB4); 376 IRB4.CreateRetVoid(); 377 MBB0 = MF->CreateMachineBasicBlock(BB0); 378 MF->insert(MF->end(), MBB0); 379 MBB1 = MF->CreateMachineBasicBlock(BB1); 380 MF->insert(MF->end(), MBB1); 381 MBB2 = MF->CreateMachineBasicBlock(BB2); 382 MF->insert(MF->end(), MBB2); 383 MBB3 = MF->CreateMachineBasicBlock(BB3); 384 MF->insert(MF->end(), MBB3); 385 MBB4 = MF->CreateMachineBasicBlock(BB4); 386 MF->insert(MF->end(), MBB4); 387 MBB0->addSuccessor(MBB1); 388 MBB0->addSuccessor(MBB2); 389 MBB1->addSuccessor(MBB3); 390 MBB2->addSuccessor(MBB3); 391 MBB3->addSuccessor(MBB1); 392 MBB3->addSuccessor(MBB2); 393 MBB3->addSuccessor(MBB4); 394 MF->RenumberBlocks(); 395 396 setupLDVObj(&*MF); 397 } 398 399 void setupBadlyNestedLoops() { 400 // entry 401 // | 402 // loop1 -o 403 // | ^ 404 // | ^ 405 // loop2 -o 406 // | ^ 407 // | ^ 408 // loop3 -o 409 // | 410 // ret 411 // 412 // NB: the loop blocks self-loop, which is a bit too fiddly to draw on 413 // accurately. 414 llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction()); 415 auto *BB0 = BasicBlock::Create(Ctx, "entry", &F); 416 auto *BB1 = BasicBlock::Create(Ctx, "loop1", &F); 417 auto *BB2 = BasicBlock::Create(Ctx, "loop2", &F); 418 auto *BB3 = BasicBlock::Create(Ctx, "loop3", &F); 419 auto *BB4 = BasicBlock::Create(Ctx, "ret", &F); 420 IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4); 421 IRB0.CreateBr(BB1); 422 IRB1.CreateBr(BB2); 423 IRB2.CreateBr(BB3); 424 IRB3.CreateBr(BB4); 425 IRB4.CreateRetVoid(); 426 MBB0 = MF->CreateMachineBasicBlock(BB0); 427 MF->insert(MF->end(), MBB0); 428 MBB1 = MF->CreateMachineBasicBlock(BB1); 429 MF->insert(MF->end(), MBB1); 430 MBB2 = MF->CreateMachineBasicBlock(BB2); 431 MF->insert(MF->end(), MBB2); 432 MBB3 = MF->CreateMachineBasicBlock(BB3); 433 MF->insert(MF->end(), MBB3); 434 MBB4 = MF->CreateMachineBasicBlock(BB4); 435 MF->insert(MF->end(), MBB4); 436 MBB0->addSuccessor(MBB1); 437 MBB1->addSuccessor(MBB1); 438 MBB1->addSuccessor(MBB2); 439 MBB2->addSuccessor(MBB1); 440 MBB2->addSuccessor(MBB2); 441 MBB2->addSuccessor(MBB3); 442 MBB3->addSuccessor(MBB2); 443 MBB3->addSuccessor(MBB3); 444 MBB3->addSuccessor(MBB4); 445 MF->RenumberBlocks(); 446 447 setupLDVObj(&*MF); 448 } 449 450 MachineFunction *readMIRBlock(const char *Input) { 451 MIRStr.clear(); 452 StringRef S = Twine(Twine(R"MIR( 453 --- | 454 target triple = "x86_64-unknown-linux-gnu" 455 define void @test() { ret void } 456 ... 457 --- 458 name: test 459 tracksRegLiveness: true 460 stack: 461 - { id: 0, name: '', type: spill-slot, offset: -16, size: 8, alignment: 8, 462 stack-id: default, callee-saved-register: '', callee-saved-restored: true, 463 debug-info-variable: '', debug-info-expression: '', debug-info-location: '' } 464 body: | 465 bb.0: 466 liveins: $rdi, $rsi 467 )MIR") + Twine(Input) + Twine("...\n")) 468 .toNullTerminatedStringRef(MIRStr); 469 ; 470 471 // Clear the "test" function from MMI if it's still present. 472 if (Function *Fn = Mod->getFunction("test")) 473 MMI->deleteMachineFunctionFor(*Fn); 474 475 auto MemBuf = MemoryBuffer::getMemBuffer(S, "<input>"); 476 auto MIRParse = createMIRParser(std::move(MemBuf), Ctx); 477 Mod = MIRParse->parseIRModule(); 478 assert(Mod); 479 Mod->setDataLayout("e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-" 480 "f80:128-n8:16:32:64-S128"); 481 482 bool Result = MIRParse->parseMachineFunctions(*Mod, *MMI); 483 assert(!Result && "Failed to parse unit test machine function?"); 484 (void)Result; 485 486 Function *Fn = Mod->getFunction("test"); 487 assert(Fn && "Failed to parse a unit test module string?"); 488 Fn->setSubprogram(OurFunc); 489 return MMI->getMachineFunction(*Fn); 490 } 491 492 void 493 produceMLocTransferFunction(MachineFunction &MF, 494 SmallVectorImpl<MLocTransferMap> &MLocTransfer, 495 unsigned MaxNumBlocks) { 496 LDV->produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks); 497 } 498 499 std::pair<FuncValueTable, FuncValueTable> 500 allocValueTables(unsigned Blocks, unsigned Locs) { 501 return {FuncValueTable(Blocks, Locs), FuncValueTable(Blocks, Locs)}; 502 } 503 }; 504 505 TEST_F(InstrRefLDVTest, MTransferDefs) { 506 MachineFunction *MF = readMIRBlock( 507 " $rax = MOV64ri 0\n" 508 " RET64 $rax\n"); 509 setupLDVObj(MF); 510 511 // We should start with only SP tracked. 512 EXPECT_TRUE(MTracker->getNumLocs() == 1); 513 514 SmallVector<MLocTransferMap, 1> TransferMap; 515 TransferMap.resize(1); 516 produceMLocTransferFunction(*MF, TransferMap, 1); 517 518 // Code contains only one register write: that should assign to each of the 519 // aliasing registers. Test that all of them get locations, and have a 520 // corresponding def at the first instr in the function. 521 const char *RegNames[] = {"RAX", "HAX", "EAX", "AX", "AH", "AL"}; 522 EXPECT_TRUE(MTracker->getNumLocs() == 7); 523 for (const char *RegName : RegNames) { 524 Register R = getRegByName(RegName); 525 ASSERT_TRUE(MTracker->isRegisterTracked(R)); 526 LocIdx L = MTracker->getRegMLoc(R); 527 ValueIDNum V = MTracker->readReg(R); 528 // Value of this register should be: block zero, instruction 1, and the 529 // location it's defined in is itself. 530 ValueIDNum ToCmp(0, 1, L); 531 EXPECT_EQ(V, ToCmp); 532 } 533 534 // Do the same again, but with an aliasing write. This should write to all 535 // the same registers again, except $ah and $hax (the upper 8 bits of $ax 536 // and 32 bits of $rax resp.). 537 MF = readMIRBlock( 538 " $rax = MOV64ri 0\n" 539 " $al = MOV8ri 0\n" 540 " RET64 $rax\n"); 541 setupLDVObj(MF); 542 TransferMap.clear(); 543 TransferMap.resize(1); 544 produceMLocTransferFunction(*MF, TransferMap, 1); 545 546 auto TestRegSetSite = [&](const char *Name, unsigned InstrNum) { 547 Register R = getRegByName(Name); 548 ASSERT_TRUE(MTracker->isRegisterTracked(R)); 549 LocIdx L = MTracker->getRegMLoc(R); 550 ValueIDNum V = MTracker->readMLoc(L); 551 ValueIDNum ToCmp(0, InstrNum, L); 552 EXPECT_EQ(V, ToCmp); 553 }; 554 555 TestRegSetSite("AL", 2); 556 TestRegSetSite("AH", 1); 557 TestRegSetSite("AX", 2); 558 TestRegSetSite("EAX", 2); 559 TestRegSetSite("HAX", 1); 560 TestRegSetSite("RAX", 2); 561 562 // This call should: 563 // * Def rax via the implicit-def, 564 // * Clobber rsi/rdi and all their subregs, via the register mask 565 // * Same for rcx, despite it not being a use in the instr, it's in the mask 566 // * NOT clobber $rsp / $esp $ sp, LiveDebugValues deliberately ignores 567 // these. 568 // * NOT clobber $rbx, because it's non-volatile 569 // * Not track every other register in the machine, only those needed. 570 MF = readMIRBlock( 571 " $rax = MOV64ri 0\n" // instr 1 572 " $rbx = MOV64ri 0\n" // instr 2 573 " $rcx = MOV64ri 0\n" // instr 3 574 " $rdi = MOV64ri 0\n" // instr 4 575 " $rsi = MOV64ri 0\n" // instr 5 576 " CALL64r $rax, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit $rsi, implicit-def $rsp, implicit-def $ssp, implicit-def $rax, implicit-def $esp, implicit-def $sp\n\n\n\n" // instr 6 577 " RET64 $rax\n"); // instr 7 578 setupLDVObj(MF); 579 TransferMap.clear(); 580 TransferMap.resize(1); 581 produceMLocTransferFunction(*MF, TransferMap, 1); 582 583 const char *RegsSetInCall[] = {"AL", "AH", "AX", "EAX", "HAX", "RAX", 584 "DIL", "DIH", "DI", "EDI", "HDI", "RDI", 585 "SIL", "SIH", "SI", "ESI", "HSI", "RSI", 586 "CL", "CH", "CX", "ECX", "HCX", "RCX"}; 587 for (const char *RegSetInCall : RegsSetInCall) 588 TestRegSetSite(RegSetInCall, 6); 589 590 const char *RegsLeftAlone[] = {"BL", "BH", "BX", "EBX", "HBX", "RBX"}; 591 for (const char *RegLeftAlone : RegsLeftAlone) 592 TestRegSetSite(RegLeftAlone, 2); 593 594 // Stack pointer should be the live-in to the function, instruction zero. 595 TestRegSetSite("RSP", 0); 596 // These stack regs should not be tracked either. Nor the (fake) subregs. 597 EXPECT_FALSE(MTracker->isRegisterTracked(getRegByName("ESP"))); 598 EXPECT_FALSE(MTracker->isRegisterTracked(getRegByName("SP"))); 599 EXPECT_FALSE(MTracker->isRegisterTracked(getRegByName("SPL"))); 600 EXPECT_FALSE(MTracker->isRegisterTracked(getRegByName("SPH"))); 601 EXPECT_FALSE(MTracker->isRegisterTracked(getRegByName("HSP"))); 602 603 // Should only be tracking: 6 x {A, B, C, DI, SI} registers = 30, 604 // Plus RSP, SSP = 32. 605 EXPECT_EQ(32u, MTracker->getNumLocs()); 606 607 608 // When we DBG_PHI something, we should track all its subregs. 609 MF = readMIRBlock( 610 " DBG_PHI $rdi, 0\n" 611 " RET64\n"); 612 setupLDVObj(MF); 613 TransferMap.clear(); 614 TransferMap.resize(1); 615 produceMLocTransferFunction(*MF, TransferMap, 1); 616 617 // All DI regs and RSP tracked. 618 EXPECT_EQ(7u, MTracker->getNumLocs()); 619 620 // All the DI registers should have block live-in values, i.e. the argument 621 // to the function. 622 const char *DIRegs[] = {"DIL", "DIH", "DI", "EDI", "HDI", "RDI"}; 623 for (const char *DIReg : DIRegs) 624 TestRegSetSite(DIReg, 0); 625 } 626 627 TEST_F(InstrRefLDVTest, MTransferMeta) { 628 // Meta instructions should not have any effect on register values. 629 SmallVector<MLocTransferMap, 1> TransferMap; 630 MachineFunction *MF = readMIRBlock( 631 " $rax = MOV64ri 0\n" 632 " $rax = IMPLICIT_DEF\n" 633 " $rax = KILL killed $rax\n" 634 " RET64 $rax\n"); 635 setupLDVObj(MF); 636 TransferMap.clear(); 637 TransferMap.resize(1); 638 produceMLocTransferFunction(*MF, TransferMap, 1); 639 640 LocIdx RaxLoc = MTracker->getRegMLoc(getRegByName("RAX")); 641 ValueIDNum V = MTracker->readMLoc(RaxLoc); 642 // Def of rax should be from instruction 1, i.e., unmodified. 643 ValueIDNum Cmp(0, 1, RaxLoc); 644 EXPECT_EQ(Cmp, V); 645 } 646 647 TEST_F(InstrRefLDVTest, MTransferCopies) { 648 SmallVector<MLocTransferMap, 1> TransferMap; 649 // This memory spill should be recognised, and a spill slot created. 650 MachineFunction *MF = readMIRBlock( 651 " $rax = MOV64ri 0\n" 652 " MOV64mr $rsp, 1, $noreg, 16, $noreg, $rax :: (store 8 into %stack.0)\n" 653 " RET64 $rax\n"); 654 setupLDVObj(MF); 655 TransferMap.clear(); 656 TransferMap.resize(1); 657 produceMLocTransferFunction(*MF, TransferMap, 1); 658 659 // Check that the spill location contains the value defined in rax by 660 // instruction 1. The MIR header says -16 offset, but it's stored as -8; 661 // it's not completely clear why, but here we only care about correctly 662 // identifying the slot, not that all the surrounding data is correct. 663 SpillLoc L = {getRegByName("RSP"), StackOffset::getFixed(-8)}; 664 SpillLocationNo SpillNo = *MTracker->getOrTrackSpillLoc(L); 665 unsigned SpillLocID = MTracker->getLocID(SpillNo, {64, 0}); 666 LocIdx SpillLoc = MTracker->getSpillMLoc(SpillLocID); 667 ValueIDNum V = MTracker->readMLoc(SpillLoc); 668 Register RAX = getRegByName("RAX"); 669 LocIdx RaxLoc = MTracker->getRegMLoc(RAX); 670 ValueIDNum Cmp(0, 1, RaxLoc); 671 EXPECT_EQ(V, Cmp); 672 673 // A spill and restore should be recognised. 674 MF = readMIRBlock( 675 " $rax = MOV64ri 0\n" 676 " MOV64mr $rsp, 1, $noreg, 16, $noreg, $rax :: (store 8 into %stack.0)\n" 677 " $rbx = MOV64rm $rsp, 1, $noreg, 0, $noreg :: (load 8 from %stack.0)\n" 678 " RET64\n"); 679 setupLDVObj(MF); 680 TransferMap.clear(); 681 TransferMap.resize(1); 682 produceMLocTransferFunction(*MF, TransferMap, 1); 683 684 // Test that rbx contains rax from instruction 1. 685 RAX = getRegByName("RAX"); 686 RaxLoc = MTracker->getRegMLoc(RAX); 687 Register RBX = getRegByName("RBX"); 688 LocIdx RbxLoc = MTracker->getRegMLoc(RBX); 689 Cmp = ValueIDNum(0, 1, RaxLoc); 690 ValueIDNum RbxVal = MTracker->readMLoc(RbxLoc); 691 EXPECT_EQ(RbxVal, Cmp); 692 693 // Testing that all the subregisters are transferred happens in 694 // MTransferSubregSpills. 695 696 // Copies and x86 movs should be recognised and honoured. In addition, all 697 // of the subregisters should be copied across too. 698 MF = readMIRBlock( 699 " $rax = MOV64ri 0\n" 700 " $rcx = COPY $rax\n" 701 " $rbx = MOV64rr $rcx\n" 702 " RET64\n"); 703 setupLDVObj(MF); 704 TransferMap.clear(); 705 TransferMap.resize(1); 706 produceMLocTransferFunction(*MF, TransferMap, 1); 707 708 const char *ARegs[] = {"AL", "AH", "AX", "EAX", "HAX", "RAX"}; 709 const char *BRegs[] = {"BL", "BH", "BX", "EBX", "HBX", "RBX"}; 710 const char *CRegs[] = {"CL", "CH", "CX", "ECX", "HCX", "RCX"}; 711 auto CheckReg = [&](unsigned int I) { 712 LocIdx A = MTracker->getRegMLoc(getRegByName(ARegs[I])); 713 LocIdx B = MTracker->getRegMLoc(getRegByName(BRegs[I])); 714 LocIdx C = MTracker->getRegMLoc(getRegByName(CRegs[I])); 715 ValueIDNum ARefVal(0, 1, A); 716 ValueIDNum AVal = MTracker->readMLoc(A); 717 ValueIDNum BVal = MTracker->readMLoc(B); 718 ValueIDNum CVal = MTracker->readMLoc(C); 719 EXPECT_EQ(ARefVal, AVal); 720 EXPECT_EQ(ARefVal, BVal); 721 EXPECT_EQ(ARefVal, CVal); 722 }; 723 724 for (unsigned int I = 0; I < 6; ++I) 725 CheckReg(I); 726 727 // When we copy to a subregister, the super-register should be def'd too: it's 728 // value will have changed. 729 MF = readMIRBlock( 730 " $rax = MOV64ri 0\n" 731 " $ecx = COPY $eax\n" 732 " RET64\n"); 733 setupLDVObj(MF); 734 TransferMap.clear(); 735 TransferMap.resize(1); 736 produceMLocTransferFunction(*MF, TransferMap, 1); 737 738 // First four regs [al, ah, ax, eax] should be copied to *cx. 739 for (unsigned int I = 0; I < 4; ++I) { 740 LocIdx A = MTracker->getRegMLoc(getRegByName(ARegs[I])); 741 LocIdx C = MTracker->getRegMLoc(getRegByName(CRegs[I])); 742 ValueIDNum ARefVal(0, 1, A); 743 ValueIDNum AVal = MTracker->readMLoc(A); 744 ValueIDNum CVal = MTracker->readMLoc(C); 745 EXPECT_EQ(ARefVal, AVal); 746 EXPECT_EQ(ARefVal, CVal); 747 } 748 749 // But rcx should contain a value defined by the COPY. 750 LocIdx RcxLoc = MTracker->getRegMLoc(getRegByName("RCX")); 751 ValueIDNum RcxVal = MTracker->readMLoc(RcxLoc); 752 ValueIDNum RcxDefVal(0, 2, RcxLoc); // instr 2 -> the copy 753 EXPECT_EQ(RcxVal, RcxDefVal); 754 } 755 756 TEST_F(InstrRefLDVTest, MTransferSubregSpills) { 757 SmallVector<MLocTransferMap, 1> TransferMap; 758 MachineFunction *MF = readMIRBlock( 759 " $rax = MOV64ri 0\n" 760 " MOV64mr $rsp, 1, $noreg, 16, $noreg, $rax :: (store 8 into %stack.0)\n" 761 " $rbx = MOV64rm $rsp, 1, $noreg, 0, $noreg :: (load 8 from %stack.0)\n" 762 " RET64\n"); 763 setupLDVObj(MF); 764 TransferMap.clear(); 765 TransferMap.resize(1); 766 produceMLocTransferFunction(*MF, TransferMap, 1); 767 768 // Check that all the subregs of rax and rbx contain the same values. One 769 // should completely transfer to the other. 770 const char *ARegs[] = {"AL", "AH", "AX", "EAX", "HAX", "RAX"}; 771 const char *BRegs[] = {"BL", "BH", "BX", "EBX", "HBX", "RBX"}; 772 for (unsigned int I = 0; I < 6; ++I) { 773 LocIdx A = MTracker->getRegMLoc(getRegByName(ARegs[I])); 774 LocIdx B = MTracker->getRegMLoc(getRegByName(BRegs[I])); 775 EXPECT_EQ(MTracker->readMLoc(A), MTracker->readMLoc(B)); 776 } 777 778 // Explicitly check what's in the different subreg slots, on the stack. 779 // Pair up subreg idx fields with the corresponding subregister in $rax. 780 MLocTracker::StackSlotPos SubRegIdxes[] = {{8, 0}, {8, 8}, {16, 0}, {32, 0}, {64, 0}}; 781 const char *SubRegNames[] = {"AL", "AH", "AX", "EAX", "RAX"}; 782 for (unsigned int I = 0; I < 5; ++I) { 783 // Value number where it's defined, 784 LocIdx RegLoc = MTracker->getRegMLoc(getRegByName(SubRegNames[I])); 785 ValueIDNum DefNum(0, 1, RegLoc); 786 // Read the corresponding subreg field from the stack. 787 SpillLoc L = {getRegByName("RSP"), StackOffset::getFixed(-8)}; 788 SpillLocationNo SpillNo = *MTracker->getOrTrackSpillLoc(L); 789 unsigned SpillID = MTracker->getLocID(SpillNo, SubRegIdxes[I]); 790 LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID); 791 ValueIDNum SpillValue = MTracker->readMLoc(SpillLoc); 792 EXPECT_EQ(DefNum, SpillValue); 793 } 794 795 // If we have exactly the same code, but we write $eax to the stack slot after 796 // $rax, then we should still have exactly the same output in the lower five 797 // subregisters. Storing $eax to the start of the slot will overwrite with the 798 // same values. $rax, as an aliasing register, should be reset to something 799 // else by that write. 800 // In theory, we could try and recognise that we're writing the _same_ values 801 // to the stack again, and so $rax doesn't need to be reset to something else. 802 // It seems vanishingly unlikely that LLVM would generate such code though, 803 // so the benefits would be small. 804 MF = readMIRBlock( 805 " $rax = MOV64ri 0\n" 806 " MOV64mr $rsp, 1, $noreg, 16, $noreg, $rax :: (store 8 into %stack.0)\n" 807 " MOV32mr $rsp, 1, $noreg, 16, $noreg, $eax :: (store 4 into %stack.0)\n" 808 " $rbx = MOV64rm $rsp, 1, $noreg, 0, $noreg :: (load 8 from %stack.0)\n" 809 " RET64\n"); 810 setupLDVObj(MF); 811 TransferMap.clear(); 812 TransferMap.resize(1); 813 produceMLocTransferFunction(*MF, TransferMap, 1); 814 815 // Check lower five registers up to and include $eax == $ebx, 816 for (unsigned int I = 0; I < 5; ++I) { 817 LocIdx A = MTracker->getRegMLoc(getRegByName(ARegs[I])); 818 LocIdx B = MTracker->getRegMLoc(getRegByName(BRegs[I])); 819 EXPECT_EQ(MTracker->readMLoc(A), MTracker->readMLoc(B)); 820 } 821 822 // $rbx should contain something else; today it's a def at the spill point 823 // of the 4 byte value. 824 SpillLoc L = {getRegByName("RSP"), StackOffset::getFixed(-8)}; 825 SpillLocationNo SpillNo = *MTracker->getOrTrackSpillLoc(L); 826 unsigned SpillID = MTracker->getLocID(SpillNo, {64, 0}); 827 LocIdx Spill64Loc = MTracker->getSpillMLoc(SpillID); 828 ValueIDNum DefAtSpill64(0, 3, Spill64Loc); 829 LocIdx RbxLoc = MTracker->getRegMLoc(getRegByName("RBX")); 830 EXPECT_EQ(MTracker->readMLoc(RbxLoc), DefAtSpill64); 831 832 // Same again, test that the lower four subreg slots on the stack are the 833 // value defined by $rax in instruction 1. 834 for (unsigned int I = 0; I < 4; ++I) { 835 // Value number where it's defined, 836 LocIdx RegLoc = MTracker->getRegMLoc(getRegByName(SubRegNames[I])); 837 ValueIDNum DefNum(0, 1, RegLoc); 838 // Read the corresponding subreg field from the stack. 839 SpillNo = *MTracker->getOrTrackSpillLoc(L); 840 SpillID = MTracker->getLocID(SpillNo, SubRegIdxes[I]); 841 LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID); 842 ValueIDNum SpillValue = MTracker->readMLoc(SpillLoc); 843 EXPECT_EQ(DefNum, SpillValue); 844 } 845 846 // Stack slot for $rax should be a different value, today it's EmptyValue. 847 ValueIDNum SpillValue = MTracker->readMLoc(Spill64Loc); 848 EXPECT_EQ(SpillValue, DefAtSpill64); 849 850 // If we write something to the stack, then over-write with some register 851 // from a completely different hierarchy, none of the "old" values should be 852 // readable. 853 // NB: slight hack, store 16 in to a 8 byte stack slot. 854 MF = readMIRBlock( 855 " $rax = MOV64ri 0\n" 856 " MOV64mr $rsp, 1, $noreg, 16, $noreg, $rax :: (store 8 into %stack.0)\n" 857 " $xmm0 = IMPLICIT_DEF\n" 858 " MOVUPDmr $rsp, 1, $noreg, 16, $noreg, killed $xmm0 :: (store (s128) into %stack.0)\n" 859 " $rbx = MOV64rm $rsp, 1, $noreg, 0, $noreg :: (load 8 from %stack.0)\n" 860 " RET64\n"); 861 setupLDVObj(MF); 862 TransferMap.clear(); 863 TransferMap.resize(1); 864 produceMLocTransferFunction(*MF, TransferMap, 1); 865 866 for (unsigned int I = 0; I < 5; ++I) { 867 // Read subreg fields from the stack. 868 SpillLocationNo SpillNo = *MTracker->getOrTrackSpillLoc(L); 869 unsigned SpillID = MTracker->getLocID(SpillNo, SubRegIdxes[I]); 870 LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID); 871 ValueIDNum SpillValue = MTracker->readMLoc(SpillLoc); 872 873 // Value should be defined by the spill-to-xmm0 instr, get value of a def 874 // at the point of the spill. 875 ValueIDNum SpillDef(0, 4, SpillLoc); 876 EXPECT_EQ(SpillValue, SpillDef); 877 } 878 879 // Read xmm0's position and ensure it has a value. Should be the live-in 880 // value to the block, as IMPLICIT_DEF isn't a real def. 881 SpillNo = *MTracker->getOrTrackSpillLoc(L); 882 SpillID = MTracker->getLocID(SpillNo, {128, 0}); 883 LocIdx Spill128Loc = MTracker->getSpillMLoc(SpillID); 884 SpillValue = MTracker->readMLoc(Spill128Loc); 885 Register XMM0 = getRegByName("XMM0"); 886 LocIdx Xmm0Loc = MTracker->getRegMLoc(XMM0); 887 EXPECT_EQ(ValueIDNum(0, 0, Xmm0Loc), SpillValue); 888 889 // What happens if we spill ah to the stack, then load al? It should find 890 // the same value. 891 MF = readMIRBlock( 892 " $rax = MOV64ri 0\n" 893 " MOV8mr $rsp, 1, $noreg, 16, $noreg, $ah :: (store 1 into %stack.0)\n" 894 " $al = MOV8rm $rsp, 1, $noreg, 0, $noreg :: (load 1 from %stack.0)\n" 895 " RET64\n"); 896 setupLDVObj(MF); 897 TransferMap.clear(); 898 TransferMap.resize(1); 899 produceMLocTransferFunction(*MF, TransferMap, 1); 900 901 Register AL = getRegByName("AL"); 902 Register AH = getRegByName("AH"); 903 LocIdx AlLoc = MTracker->getRegMLoc(AL); 904 LocIdx AhLoc = MTracker->getRegMLoc(AH); 905 ValueIDNum AHDef(0, 1, AhLoc); 906 ValueIDNum ALValue = MTracker->readMLoc(AlLoc); 907 EXPECT_EQ(ALValue, AHDef); 908 } 909 910 TEST_F(InstrRefLDVTest, MLocSingleBlock) { 911 // Test some very simple properties about interpreting the transfer function. 912 setupSingleBlock(); 913 914 // We should start with a single location, the stack pointer. 915 ASSERT_TRUE(MTracker->getNumLocs() == 1); 916 LocIdx RspLoc(0); 917 918 // Set up live-in and live-out tables for this function: two locations (we 919 // add one later) in a single block. 920 auto [MOutLocs, MInLocs] = allocValueTables(1, 2); 921 922 // Transfer function: nothing. 923 SmallVector<MLocTransferMap, 1> TransferFunc; 924 TransferFunc.resize(1); 925 926 // Try and build value maps... 927 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 928 929 // The result should be that RSP is marked as a live-in-PHI -- this represents 930 // an argument. And as there's no transfer function, the block live-out should 931 // be the same. 932 EXPECT_EQ(MInLocs[0][0], ValueIDNum(0, 0, RspLoc)); 933 EXPECT_EQ(MOutLocs[0][0], ValueIDNum(0, 0, RspLoc)); 934 935 // Try again, this time initialising the in-locs to be defined by an 936 // instruction. The entry block should always be re-assigned to be the 937 // arguments. 938 initValueArray(MInLocs, 1, 2); 939 initValueArray(MOutLocs, 1, 2); 940 MInLocs[0][0] = ValueIDNum(0, 1, RspLoc); 941 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 942 EXPECT_EQ(MInLocs[0][0], ValueIDNum(0, 0, RspLoc)); 943 EXPECT_EQ(MOutLocs[0][0], ValueIDNum(0, 0, RspLoc)); 944 945 // Now insert something into the transfer function to assign to the single 946 // machine location. 947 TransferFunc[0].insert({RspLoc, ValueIDNum(0, 1, RspLoc)}); 948 initValueArray(MInLocs, 1, 2); 949 initValueArray(MOutLocs, 1, 2); 950 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 951 EXPECT_EQ(MInLocs[0][0], ValueIDNum(0, 0, RspLoc)); 952 EXPECT_EQ(MOutLocs[0][0], ValueIDNum(0, 1, RspLoc)); 953 TransferFunc[0].clear(); 954 955 // Add a new register to be tracked, and insert it into the transfer function 956 // as a copy. The output of $rax should be the live-in value of $rsp. 957 Register RAX = getRegByName("RAX"); 958 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 959 TransferFunc[0].insert({RspLoc, ValueIDNum(0, 1, RspLoc)}); 960 TransferFunc[0].insert({RaxLoc, ValueIDNum(0, 0, RspLoc)}); 961 initValueArray(MInLocs, 1, 2); 962 initValueArray(MOutLocs, 1, 2); 963 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 964 EXPECT_EQ(MInLocs[0][0], ValueIDNum(0, 0, RspLoc)); 965 EXPECT_EQ(MInLocs[0][1], ValueIDNum(0, 0, RaxLoc)); 966 EXPECT_EQ(MOutLocs[0][0], ValueIDNum(0, 1, RspLoc)); 967 EXPECT_EQ(MOutLocs[0][1], ValueIDNum(0, 0, RspLoc)); // Rax contains RspLoc. 968 TransferFunc[0].clear(); 969 } 970 971 TEST_F(InstrRefLDVTest, MLocDiamondBlocks) { 972 // Test that information flows from the entry block to two successors. 973 // entry 974 // / \ 975 // br1 br2 976 // \ / 977 // ret 978 setupDiamondBlocks(); 979 980 ASSERT_TRUE(MTracker->getNumLocs() == 1); 981 LocIdx RspLoc(0); 982 Register RAX = getRegByName("RAX"); 983 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 984 985 auto [MInLocs, MOutLocs] = allocValueTables(4, 2); 986 987 // Transfer function: start with nothing. 988 SmallVector<MLocTransferMap, 1> TransferFunc; 989 TransferFunc.resize(4); 990 991 // Name some values. 992 unsigned EntryBlk = 0, BrBlk1 = 1, BrBlk2 = 2, RetBlk = 3; 993 994 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 995 ValueIDNum RspDefInBlk0(EntryBlk, 1, RspLoc); 996 ValueIDNum RspDefInBlk1(BrBlk1, 1, RspLoc); 997 ValueIDNum RspDefInBlk2(BrBlk2, 1, RspLoc); 998 ValueIDNum RspPHIInBlk3(RetBlk, 0, RspLoc); 999 ValueIDNum RaxLiveInBlk1(BrBlk1, 0, RaxLoc); 1000 ValueIDNum RaxLiveInBlk2(BrBlk2, 0, RaxLoc); 1001 1002 // With no transfer function, the live-in values to the entry block should 1003 // propagate to all live-outs and the live-ins to the two successor blocks. 1004 // IN ADDITION: this checks that the exit block doesn't get a PHI put in it. 1005 initValueArray(MInLocs, 4, 2); 1006 initValueArray(MOutLocs, 4, 2); 1007 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1008 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1009 EXPECT_EQ(MInLocs[1][0], LiveInRsp); 1010 EXPECT_EQ(MInLocs[2][0], LiveInRsp); 1011 EXPECT_EQ(MInLocs[3][0], LiveInRsp); 1012 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1013 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1014 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1015 EXPECT_EQ(MOutLocs[3][0], LiveInRsp); 1016 // (Skipped writing out locations for $rax). 1017 1018 // Check that a def of $rsp in the entry block will likewise reach all the 1019 // successors. 1020 TransferFunc[0].insert({RspLoc, RspDefInBlk0}); 1021 initValueArray(MInLocs, 4, 2); 1022 initValueArray(MOutLocs, 4, 2); 1023 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1024 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1025 EXPECT_EQ(MInLocs[1][0], RspDefInBlk0); 1026 EXPECT_EQ(MInLocs[2][0], RspDefInBlk0); 1027 EXPECT_EQ(MInLocs[3][0], RspDefInBlk0); 1028 EXPECT_EQ(MOutLocs[0][0], RspDefInBlk0); 1029 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk0); 1030 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk0); 1031 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk0); 1032 TransferFunc[0].clear(); 1033 1034 // Def in one branch of the diamond means that we need a PHI in the ret block 1035 TransferFunc[0].insert({RspLoc, RspDefInBlk0}); 1036 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1037 initValueArray(MInLocs, 4, 2); 1038 initValueArray(MOutLocs, 4, 2); 1039 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1040 // This value map: like above, where RspDefInBlk0 is propagated through one 1041 // branch of the diamond, but is def'ed in the live-outs of the other. The 1042 // ret / merging block should have a PHI in its live-ins. 1043 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1044 EXPECT_EQ(MInLocs[1][0], RspDefInBlk0); 1045 EXPECT_EQ(MInLocs[2][0], RspDefInBlk0); 1046 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk3); 1047 EXPECT_EQ(MOutLocs[0][0], RspDefInBlk0); 1048 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1049 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk0); 1050 EXPECT_EQ(MOutLocs[3][0], RspPHIInBlk3); 1051 TransferFunc[0].clear(); 1052 TransferFunc[1].clear(); 1053 1054 // If we have differeing defs in either side of the diamond, we should 1055 // continue to produce a PHI, 1056 TransferFunc[0].insert({RspLoc, RspDefInBlk0}); 1057 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1058 TransferFunc[2].insert({RspLoc, RspDefInBlk2}); 1059 initValueArray(MInLocs, 4, 2); 1060 initValueArray(MOutLocs, 4, 2); 1061 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1062 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1063 EXPECT_EQ(MInLocs[1][0], RspDefInBlk0); 1064 EXPECT_EQ(MInLocs[2][0], RspDefInBlk0); 1065 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk3); 1066 EXPECT_EQ(MOutLocs[0][0], RspDefInBlk0); 1067 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1068 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk2); 1069 EXPECT_EQ(MOutLocs[3][0], RspPHIInBlk3); 1070 TransferFunc[0].clear(); 1071 TransferFunc[1].clear(); 1072 TransferFunc[2].clear(); 1073 1074 // If we have defs of the same value on either side of the branch, a PHI will 1075 // initially be created, however value propagation should then eliminate it. 1076 // Encode this by copying the live-in value to $rax, and copying it to $rsp 1077 // from $rax in each branch of the diamond. We don't allow the definition of 1078 // arbitary values in transfer functions. 1079 TransferFunc[0].insert({RspLoc, RspDefInBlk0}); 1080 TransferFunc[0].insert({RaxLoc, LiveInRsp}); 1081 TransferFunc[1].insert({RspLoc, RaxLiveInBlk1}); 1082 TransferFunc[2].insert({RspLoc, RaxLiveInBlk2}); 1083 initValueArray(MInLocs, 4, 2); 1084 initValueArray(MOutLocs, 4, 2); 1085 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1086 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1087 EXPECT_EQ(MInLocs[1][0], RspDefInBlk0); 1088 EXPECT_EQ(MInLocs[2][0], RspDefInBlk0); 1089 EXPECT_EQ(MInLocs[3][0], LiveInRsp); 1090 EXPECT_EQ(MOutLocs[0][0], RspDefInBlk0); 1091 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1092 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1093 EXPECT_EQ(MOutLocs[3][0], LiveInRsp); 1094 TransferFunc[0].clear(); 1095 TransferFunc[1].clear(); 1096 TransferFunc[2].clear(); 1097 } 1098 1099 TEST_F(InstrRefLDVTest, MLocDiamondSpills) { 1100 // Test that defs in stack locations that require PHIs, cause PHIs to be 1101 // installed in aliasing locations. i.e., if there's a PHI in the lower 1102 // 8 bits of the stack, there should be PHIs for 16/32/64 bit locations 1103 // on the stack too. 1104 // Technically this isn't needed for accuracy: we should calculate PHIs 1105 // independently for each location. However, because there's an optimisation 1106 // that only places PHIs for the lower "interfering" parts of stack slots, 1107 // test for this behaviour. 1108 setupDiamondBlocks(); 1109 1110 ASSERT_TRUE(MTracker->getNumLocs() == 1); 1111 LocIdx RspLoc(0); 1112 1113 // Create a stack location and ensure it's tracked. 1114 SpillLoc SL = {getRegByName("RSP"), StackOffset::getFixed(-8)}; 1115 SpillLocationNo SpillNo = *MTracker->getOrTrackSpillLoc(SL); 1116 ASSERT_EQ(MTracker->getNumLocs(), 13u); // Tracks all possible stack locs. 1117 // Locations are: RSP, stack slots from 2^3 bits wide up to 2^9 for zmm regs, 1118 // then slots for sub_8bit_hi and sub_16bit_hi ({8, 8} and {16, 16}). 1119 // Finally, one for spilt fp80 registers. 1120 1121 // Pick out the locations on the stack that various x86 regs would be written 1122 // to. HAX is the upper 16 bits of EAX. 1123 unsigned ALID = MTracker->getLocID(SpillNo, {8, 0}); 1124 unsigned AHID = MTracker->getLocID(SpillNo, {8, 8}); 1125 unsigned AXID = MTracker->getLocID(SpillNo, {16, 0}); 1126 unsigned EAXID = MTracker->getLocID(SpillNo, {32, 0}); 1127 unsigned HAXID = MTracker->getLocID(SpillNo, {16, 16}); 1128 unsigned RAXID = MTracker->getLocID(SpillNo, {64, 0}); 1129 LocIdx ALStackLoc = MTracker->getSpillMLoc(ALID); 1130 LocIdx AHStackLoc = MTracker->getSpillMLoc(AHID); 1131 LocIdx AXStackLoc = MTracker->getSpillMLoc(AXID); 1132 LocIdx EAXStackLoc = MTracker->getSpillMLoc(EAXID); 1133 LocIdx HAXStackLoc = MTracker->getSpillMLoc(HAXID); 1134 LocIdx RAXStackLoc = MTracker->getSpillMLoc(RAXID); 1135 // There are other locations, for things like xmm0, which we're going to 1136 // ignore here. 1137 1138 auto [MInLocs, MOutLocs] = allocValueTables(4, 13); 1139 1140 // Transfer function: start with nothing. 1141 SmallVector<MLocTransferMap, 1> TransferFunc; 1142 TransferFunc.resize(4); 1143 1144 // Name some values. 1145 unsigned EntryBlk = 0, Blk1 = 1, RetBlk = 3; 1146 1147 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 1148 ValueIDNum ALLiveIn(EntryBlk, 0, ALStackLoc); 1149 ValueIDNum AHLiveIn(EntryBlk, 0, AHStackLoc); 1150 ValueIDNum HAXLiveIn(EntryBlk, 0, HAXStackLoc); 1151 ValueIDNum ALPHI(RetBlk, 0, ALStackLoc); 1152 ValueIDNum AXPHI(RetBlk, 0, AXStackLoc); 1153 ValueIDNum EAXPHI(RetBlk, 0, EAXStackLoc); 1154 ValueIDNum HAXPHI(RetBlk, 0, HAXStackLoc); 1155 ValueIDNum RAXPHI(RetBlk, 0, RAXStackLoc); 1156 1157 ValueIDNum ALDefInBlk1(Blk1, 1, ALStackLoc); 1158 ValueIDNum HAXDefInBlk1(Blk1, 1, HAXStackLoc); 1159 1160 SmallPtrSet<MachineBasicBlock *, 4> AllBlocks{MBB0, MBB1, MBB2, MBB3}; 1161 1162 // If we put defs into one side of the diamond, for AL and HAX, then we should 1163 // find all aliasing positions have PHIs placed. This isn't technically what 1164 // the transfer function says to do: but we're testing that the optimisation 1165 // to reduce IDF calculation does the right thing. 1166 // AH should not be def'd: it don't alias AL or HAX. 1167 // 1168 // NB: we don't call buildMLocValueMap, because it will try to eliminate the 1169 // upper-slot PHIs, and succeed because of our slightly cooked transfer 1170 // function. 1171 TransferFunc[1].insert({ALStackLoc, ALDefInBlk1}); 1172 TransferFunc[1].insert({HAXStackLoc, HAXDefInBlk1}); 1173 initValueArray(MInLocs, 4, 13); 1174 placeMLocPHIs(*MF, AllBlocks, MInLocs, TransferFunc); 1175 EXPECT_EQ(MInLocs[3][ALStackLoc.asU64()], ALPHI); 1176 EXPECT_EQ(MInLocs[3][AXStackLoc.asU64()], AXPHI); 1177 EXPECT_EQ(MInLocs[3][EAXStackLoc.asU64()], EAXPHI); 1178 EXPECT_EQ(MInLocs[3][HAXStackLoc.asU64()], HAXPHI); 1179 EXPECT_EQ(MInLocs[3][RAXStackLoc.asU64()], RAXPHI); 1180 // AH should be left untouched, 1181 EXPECT_EQ(MInLocs[3][AHStackLoc.asU64()], ValueIDNum::EmptyValue); 1182 } 1183 1184 TEST_F(InstrRefLDVTest, MLocSimpleLoop) { 1185 // entry 1186 // | 1187 // |/-----\ 1188 // loopblk | 1189 // |\-----/ 1190 // | 1191 // ret 1192 setupSimpleLoop(); 1193 1194 ASSERT_TRUE(MTracker->getNumLocs() == 1); 1195 LocIdx RspLoc(0); 1196 Register RAX = getRegByName("RAX"); 1197 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 1198 1199 auto [MInLocs, MOutLocs] = allocValueTables(3, 2); 1200 1201 SmallVector<MLocTransferMap, 1> TransferFunc; 1202 TransferFunc.resize(3); 1203 1204 // Name some values. 1205 unsigned EntryBlk = 0, LoopBlk = 1, RetBlk = 2; 1206 1207 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 1208 ValueIDNum RspPHIInBlk1(LoopBlk, 0, RspLoc); 1209 ValueIDNum RspDefInBlk1(LoopBlk, 1, RspLoc); 1210 ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc); 1211 ValueIDNum RaxPHIInBlk1(LoopBlk, 0, RaxLoc); 1212 ValueIDNum RaxPHIInBlk2(RetBlk, 0, RaxLoc); 1213 1214 // Begin test with all locations being live-through. 1215 initValueArray(MInLocs, 3, 2); 1216 initValueArray(MOutLocs, 3, 2); 1217 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1218 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1219 EXPECT_EQ(MInLocs[1][0], LiveInRsp); 1220 EXPECT_EQ(MInLocs[2][0], LiveInRsp); 1221 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1222 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1223 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1224 1225 // Add a def of $rsp to the loop block: it should be in the live-outs, but 1226 // should cause a PHI to be placed in the live-ins. Test the transfer function 1227 // by copying that PHI into $rax in the loop, then back to $rsp in the ret 1228 // block. 1229 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1230 TransferFunc[1].insert({RaxLoc, RspPHIInBlk1}); 1231 TransferFunc[2].insert({RspLoc, RaxPHIInBlk2}); 1232 initValueArray(MInLocs, 3, 2); 1233 initValueArray(MOutLocs, 3, 2); 1234 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1235 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1236 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1237 EXPECT_EQ(MInLocs[2][0], RspDefInBlk1); 1238 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1239 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1240 EXPECT_EQ(MOutLocs[2][0], RspPHIInBlk1); 1241 // Check rax as well, 1242 EXPECT_EQ(MInLocs[0][1], LiveInRax); 1243 EXPECT_EQ(MInLocs[1][1], RaxPHIInBlk1); 1244 EXPECT_EQ(MInLocs[2][1], RspPHIInBlk1); 1245 EXPECT_EQ(MOutLocs[0][1], LiveInRax); 1246 EXPECT_EQ(MOutLocs[1][1], RspPHIInBlk1); 1247 EXPECT_EQ(MOutLocs[2][1], RspPHIInBlk1); 1248 TransferFunc[1].clear(); 1249 TransferFunc[2].clear(); 1250 1251 // As with the diamond case, a PHI will be created if there's a (implicit) 1252 // def in the entry block and loop block; but should be value propagated away 1253 // if it copies in the same value. Copy live-in $rsp to $rax, then copy it 1254 // into $rsp in the loop. Encoded as copying the live-in $rax value in block 1 1255 // to $rsp. 1256 TransferFunc[0].insert({RaxLoc, LiveInRsp}); 1257 TransferFunc[1].insert({RspLoc, RaxPHIInBlk1}); 1258 initValueArray(MInLocs, 3, 2); 1259 initValueArray(MOutLocs, 3, 2); 1260 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1261 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1262 EXPECT_EQ(MInLocs[1][0], LiveInRsp); 1263 EXPECT_EQ(MInLocs[2][0], LiveInRsp); 1264 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1265 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1266 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1267 // Check $rax's values. 1268 EXPECT_EQ(MInLocs[0][1], LiveInRax); 1269 EXPECT_EQ(MInLocs[1][1], LiveInRsp); 1270 EXPECT_EQ(MInLocs[2][1], LiveInRsp); 1271 EXPECT_EQ(MOutLocs[0][1], LiveInRsp); 1272 EXPECT_EQ(MOutLocs[1][1], LiveInRsp); 1273 EXPECT_EQ(MOutLocs[2][1], LiveInRsp); 1274 TransferFunc[0].clear(); 1275 TransferFunc[1].clear(); 1276 } 1277 1278 TEST_F(InstrRefLDVTest, MLocNestedLoop) { 1279 // entry 1280 // | 1281 // loop1 1282 // ^\ 1283 // | \ /-\ 1284 // | loop2 | 1285 // | / \-/ 1286 // ^ / 1287 // join 1288 // | 1289 // ret 1290 setupNestedLoops(); 1291 1292 ASSERT_TRUE(MTracker->getNumLocs() == 1); 1293 LocIdx RspLoc(0); 1294 Register RAX = getRegByName("RAX"); 1295 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 1296 1297 auto [MInLocs, MOutLocs] = allocValueTables(5, 2); 1298 1299 SmallVector<MLocTransferMap, 1> TransferFunc; 1300 TransferFunc.resize(5); 1301 1302 unsigned EntryBlk = 0, Loop1Blk = 1, Loop2Blk = 2, JoinBlk = 3; 1303 1304 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 1305 ValueIDNum RspPHIInBlk1(Loop1Blk, 0, RspLoc); 1306 ValueIDNum RspDefInBlk1(Loop1Blk, 1, RspLoc); 1307 ValueIDNum RspPHIInBlk2(Loop2Blk, 0, RspLoc); 1308 ValueIDNum RspDefInBlk2(Loop2Blk, 1, RspLoc); 1309 ValueIDNum RspDefInBlk3(JoinBlk, 1, RspLoc); 1310 ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc); 1311 ValueIDNum RaxPHIInBlk1(Loop1Blk, 0, RaxLoc); 1312 ValueIDNum RaxPHIInBlk2(Loop2Blk, 0, RaxLoc); 1313 1314 // Like the other tests: first ensure that if there's nothing in the transfer 1315 // function, then everything is live-through (check $rsp). 1316 initValueArray(MInLocs, 5, 2); 1317 initValueArray(MOutLocs, 5, 2); 1318 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1319 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1320 EXPECT_EQ(MInLocs[1][0], LiveInRsp); 1321 EXPECT_EQ(MInLocs[2][0], LiveInRsp); 1322 EXPECT_EQ(MInLocs[3][0], LiveInRsp); 1323 EXPECT_EQ(MInLocs[4][0], LiveInRsp); 1324 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1325 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1326 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1327 EXPECT_EQ(MOutLocs[3][0], LiveInRsp); 1328 EXPECT_EQ(MOutLocs[4][0], LiveInRsp); 1329 1330 // A def in the inner loop means we should get PHIs at the heads of both 1331 // loops. Live-outs of the last three blocks will be the def, as it dominates 1332 // those. 1333 TransferFunc[2].insert({RspLoc, RspDefInBlk2}); 1334 initValueArray(MInLocs, 5, 2); 1335 initValueArray(MOutLocs, 5, 2); 1336 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1337 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1338 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1339 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1340 EXPECT_EQ(MInLocs[3][0], RspDefInBlk2); 1341 EXPECT_EQ(MInLocs[4][0], RspDefInBlk2); 1342 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1343 EXPECT_EQ(MOutLocs[1][0], RspPHIInBlk1); 1344 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk2); 1345 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk2); 1346 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk2); 1347 TransferFunc[2].clear(); 1348 1349 // Adding a def to the outer loop header shouldn't affect this much -- the 1350 // live-out of block 1 changes. 1351 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1352 TransferFunc[2].insert({RspLoc, RspDefInBlk2}); 1353 initValueArray(MInLocs, 5, 2); 1354 initValueArray(MOutLocs, 5, 2); 1355 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1356 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1357 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1358 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1359 EXPECT_EQ(MInLocs[3][0], RspDefInBlk2); 1360 EXPECT_EQ(MInLocs[4][0], RspDefInBlk2); 1361 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1362 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1363 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk2); 1364 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk2); 1365 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk2); 1366 TransferFunc[1].clear(); 1367 TransferFunc[2].clear(); 1368 1369 // Likewise, putting a def in the outer loop tail shouldn't affect where 1370 // the PHIs go, and should propagate into the ret block. 1371 1372 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1373 TransferFunc[2].insert({RspLoc, RspDefInBlk2}); 1374 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1375 initValueArray(MInLocs, 5, 2); 1376 initValueArray(MOutLocs, 5, 2); 1377 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1378 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1379 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1380 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1381 EXPECT_EQ(MInLocs[3][0], RspDefInBlk2); 1382 EXPECT_EQ(MInLocs[4][0], RspDefInBlk3); 1383 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1384 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1385 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk2); 1386 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk3); 1387 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk3); 1388 TransferFunc[1].clear(); 1389 TransferFunc[2].clear(); 1390 TransferFunc[3].clear(); 1391 1392 // However: if we don't def in the inner-loop, then we just have defs in the 1393 // head and tail of the outer loop. The inner loop should be live-through. 1394 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1395 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1396 initValueArray(MInLocs, 5, 2); 1397 initValueArray(MOutLocs, 5, 2); 1398 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1399 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1400 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1401 EXPECT_EQ(MInLocs[2][0], RspDefInBlk1); 1402 EXPECT_EQ(MInLocs[3][0], RspDefInBlk1); 1403 EXPECT_EQ(MInLocs[4][0], RspDefInBlk3); 1404 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1405 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1406 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk1); 1407 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk3); 1408 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk3); 1409 TransferFunc[1].clear(); 1410 TransferFunc[3].clear(); 1411 1412 // Check that this still works if we copy RspDefInBlk1 to $rax and then 1413 // copy it back into $rsp in the inner loop. 1414 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1415 TransferFunc[1].insert({RaxLoc, RspDefInBlk1}); 1416 TransferFunc[2].insert({RspLoc, RaxPHIInBlk2}); 1417 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1418 initValueArray(MInLocs, 5, 2); 1419 initValueArray(MOutLocs, 5, 2); 1420 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1421 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1422 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1423 EXPECT_EQ(MInLocs[2][0], RspDefInBlk1); 1424 EXPECT_EQ(MInLocs[3][0], RspDefInBlk1); 1425 EXPECT_EQ(MInLocs[4][0], RspDefInBlk3); 1426 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1427 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1428 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk1); 1429 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk3); 1430 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk3); 1431 // Look at raxes value in the relevant blocks, 1432 EXPECT_EQ(MInLocs[2][1], RspDefInBlk1); 1433 EXPECT_EQ(MOutLocs[1][1], RspDefInBlk1); 1434 TransferFunc[1].clear(); 1435 TransferFunc[2].clear(); 1436 TransferFunc[3].clear(); 1437 1438 // If we have a single def in the tail of the outer loop, that should produce 1439 // a PHI at the loop head, and be live-through the inner loop. 1440 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1441 initValueArray(MInLocs, 5, 2); 1442 initValueArray(MOutLocs, 5, 2); 1443 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1444 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1445 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1446 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk1); 1447 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk1); 1448 EXPECT_EQ(MInLocs[4][0], RspDefInBlk3); 1449 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1450 EXPECT_EQ(MOutLocs[1][0], RspPHIInBlk1); 1451 EXPECT_EQ(MOutLocs[2][0], RspPHIInBlk1); 1452 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk3); 1453 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk3); 1454 TransferFunc[3].clear(); 1455 1456 // And if we copy from $rsp to $rax in block 2, it should resolve to the PHI 1457 // in block 1, and we should keep that value in rax until the ret block. 1458 // There'll be a PHI in block 1 and 2, because we're putting a def in the 1459 // inner loop. 1460 TransferFunc[2].insert({RaxLoc, RspPHIInBlk2}); 1461 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1462 initValueArray(MInLocs, 5, 2); 1463 initValueArray(MOutLocs, 5, 2); 1464 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1465 // Examining the values of rax, 1466 EXPECT_EQ(MInLocs[0][1], LiveInRax); 1467 EXPECT_EQ(MInLocs[1][1], RaxPHIInBlk1); 1468 EXPECT_EQ(MInLocs[2][1], RaxPHIInBlk2); 1469 EXPECT_EQ(MInLocs[3][1], RspPHIInBlk1); 1470 EXPECT_EQ(MInLocs[4][1], RspPHIInBlk1); 1471 EXPECT_EQ(MOutLocs[0][1], LiveInRax); 1472 EXPECT_EQ(MOutLocs[1][1], RaxPHIInBlk1); 1473 EXPECT_EQ(MOutLocs[2][1], RspPHIInBlk1); 1474 EXPECT_EQ(MOutLocs[3][1], RspPHIInBlk1); 1475 EXPECT_EQ(MOutLocs[4][1], RspPHIInBlk1); 1476 TransferFunc[2].clear(); 1477 TransferFunc[3].clear(); 1478 } 1479 1480 TEST_F(InstrRefLDVTest, MLocNoDominatingLoop) { 1481 // entry 1482 // / \ 1483 // / \ 1484 // / \ 1485 // head1 head2 1486 // ^ \ / ^ 1487 // ^ \ / ^ 1488 // \-joinblk -/ 1489 // | 1490 // ret 1491 setupNoDominatingLoop(); 1492 1493 ASSERT_TRUE(MTracker->getNumLocs() == 1); 1494 LocIdx RspLoc(0); 1495 Register RAX = getRegByName("RAX"); 1496 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 1497 1498 auto [MInLocs, MOutLocs] = allocValueTables(5, 2); 1499 1500 SmallVector<MLocTransferMap, 1> TransferFunc; 1501 TransferFunc.resize(5); 1502 1503 unsigned EntryBlk = 0, Head1Blk = 1, Head2Blk = 2, JoinBlk = 3; 1504 1505 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 1506 ValueIDNum RspPHIInBlk1(Head1Blk, 0, RspLoc); 1507 ValueIDNum RspDefInBlk1(Head1Blk, 1, RspLoc); 1508 ValueIDNum RspPHIInBlk2(Head2Blk, 0, RspLoc); 1509 ValueIDNum RspDefInBlk2(Head2Blk, 1, RspLoc); 1510 ValueIDNum RspPHIInBlk3(JoinBlk, 0, RspLoc); 1511 ValueIDNum RspDefInBlk3(JoinBlk, 1, RspLoc); 1512 ValueIDNum RaxPHIInBlk1(Head1Blk, 0, RaxLoc); 1513 ValueIDNum RaxPHIInBlk2(Head2Blk, 0, RaxLoc); 1514 1515 // As ever, test that everything is live-through if there are no defs. 1516 initValueArray(MInLocs, 5, 2); 1517 initValueArray(MOutLocs, 5, 2); 1518 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1519 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1520 EXPECT_EQ(MInLocs[1][0], LiveInRsp); 1521 EXPECT_EQ(MInLocs[2][0], LiveInRsp); 1522 EXPECT_EQ(MInLocs[3][0], LiveInRsp); 1523 EXPECT_EQ(MInLocs[4][0], LiveInRsp); 1524 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1525 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1526 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1527 EXPECT_EQ(MOutLocs[3][0], LiveInRsp); 1528 EXPECT_EQ(MOutLocs[4][0], LiveInRsp); 1529 1530 // Putting a def in the 'join' block will cause us to have two distinct 1531 // PHIs in each loop head, then on entry to the join block. 1532 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1533 initValueArray(MInLocs, 5, 2); 1534 initValueArray(MOutLocs, 5, 2); 1535 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1536 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1537 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1538 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1539 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk3); 1540 EXPECT_EQ(MInLocs[4][0], RspDefInBlk3); 1541 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1542 EXPECT_EQ(MOutLocs[1][0], RspPHIInBlk1); 1543 EXPECT_EQ(MOutLocs[2][0], RspPHIInBlk2); 1544 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk3); 1545 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk3); 1546 TransferFunc[3].clear(); 1547 1548 // We should get the same behaviour if we put the def in either of the 1549 // loop heads -- it should force the other head to be a PHI. 1550 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1551 initValueArray(MInLocs, 5, 2); 1552 initValueArray(MOutLocs, 5, 2); 1553 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1554 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1555 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1556 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1557 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk3); 1558 EXPECT_EQ(MInLocs[4][0], RspPHIInBlk3); 1559 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1560 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1561 EXPECT_EQ(MOutLocs[2][0], RspPHIInBlk2); 1562 EXPECT_EQ(MOutLocs[3][0], RspPHIInBlk3); 1563 EXPECT_EQ(MOutLocs[4][0], RspPHIInBlk3); 1564 TransferFunc[1].clear(); 1565 1566 // Check symmetry, 1567 TransferFunc[2].insert({RspLoc, RspDefInBlk2}); 1568 initValueArray(MInLocs, 5, 2); 1569 initValueArray(MOutLocs, 5, 2); 1570 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1571 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1572 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1573 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1574 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk3); 1575 EXPECT_EQ(MInLocs[4][0], RspPHIInBlk3); 1576 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1577 EXPECT_EQ(MOutLocs[1][0], RspPHIInBlk1); 1578 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk2); 1579 EXPECT_EQ(MOutLocs[3][0], RspPHIInBlk3); 1580 EXPECT_EQ(MOutLocs[4][0], RspPHIInBlk3); 1581 TransferFunc[2].clear(); 1582 1583 // Test some scenarios where there _shouldn't_ be any PHIs created at heads. 1584 // These are those PHIs are created, but value propagation eliminates them. 1585 // For example, lets copy rsp-livein to $rsp inside each loop head, so that 1586 // there's no need for a PHI in the join block. Put a def of $rsp in block 3 1587 // to force PHIs elsewhere. 1588 TransferFunc[0].insert({RaxLoc, LiveInRsp}); 1589 TransferFunc[1].insert({RspLoc, RaxPHIInBlk1}); 1590 TransferFunc[2].insert({RspLoc, RaxPHIInBlk2}); 1591 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1592 initValueArray(MInLocs, 5, 2); 1593 initValueArray(MOutLocs, 5, 2); 1594 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1595 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1596 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1597 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1598 EXPECT_EQ(MInLocs[3][0], LiveInRsp); 1599 EXPECT_EQ(MInLocs[4][0], RspDefInBlk3); 1600 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1601 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1602 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1603 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk3); 1604 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk3); 1605 TransferFunc[0].clear(); 1606 TransferFunc[1].clear(); 1607 TransferFunc[2].clear(); 1608 TransferFunc[3].clear(); 1609 1610 // In fact, if we eliminate the def in block 3, none of those PHIs are 1611 // necessary, as we're just repeatedly copying LiveInRsp into $rsp. They 1612 // should all be value propagated out. 1613 TransferFunc[0].insert({RaxLoc, LiveInRsp}); 1614 TransferFunc[1].insert({RspLoc, RaxPHIInBlk1}); 1615 TransferFunc[2].insert({RspLoc, RaxPHIInBlk2}); 1616 initValueArray(MInLocs, 5, 2); 1617 initValueArray(MOutLocs, 5, 2); 1618 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1619 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1620 EXPECT_EQ(MInLocs[1][0], LiveInRsp); 1621 EXPECT_EQ(MInLocs[2][0], LiveInRsp); 1622 EXPECT_EQ(MInLocs[3][0], LiveInRsp); 1623 EXPECT_EQ(MInLocs[4][0], LiveInRsp); 1624 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1625 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1626 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1627 EXPECT_EQ(MOutLocs[3][0], LiveInRsp); 1628 EXPECT_EQ(MOutLocs[4][0], LiveInRsp); 1629 TransferFunc[0].clear(); 1630 TransferFunc[1].clear(); 1631 TransferFunc[2].clear(); 1632 } 1633 1634 TEST_F(InstrRefLDVTest, MLocBadlyNestedLoops) { 1635 // entry 1636 // | 1637 // loop1 -o 1638 // | ^ 1639 // | ^ 1640 // loop2 -o 1641 // | ^ 1642 // | ^ 1643 // loop3 -o 1644 // | 1645 // ret 1646 setupBadlyNestedLoops(); 1647 1648 ASSERT_TRUE(MTracker->getNumLocs() == 1); 1649 LocIdx RspLoc(0); 1650 Register RAX = getRegByName("RAX"); 1651 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 1652 1653 auto [MInLocs, MOutLocs] = allocValueTables(5, 2); 1654 1655 SmallVector<MLocTransferMap, 1> TransferFunc; 1656 TransferFunc.resize(5); 1657 1658 unsigned EntryBlk = 0, Loop1Blk = 1, Loop2Blk = 2, Loop3Blk = 3; 1659 1660 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 1661 ValueIDNum RspPHIInBlk1(Loop1Blk, 0, RspLoc); 1662 ValueIDNum RspDefInBlk1(Loop1Blk, 1, RspLoc); 1663 ValueIDNum RspPHIInBlk2(Loop2Blk, 0, RspLoc); 1664 ValueIDNum RspPHIInBlk3(Loop3Blk, 0, RspLoc); 1665 ValueIDNum RspDefInBlk3(Loop3Blk, 1, RspLoc); 1666 ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc); 1667 ValueIDNum RaxPHIInBlk3(Loop3Blk, 0, RaxLoc); 1668 1669 // As ever, test that everything is live-through if there are no defs. 1670 initValueArray(MInLocs, 5, 2); 1671 initValueArray(MOutLocs, 5, 2); 1672 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1673 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1674 EXPECT_EQ(MInLocs[1][0], LiveInRsp); 1675 EXPECT_EQ(MInLocs[2][0], LiveInRsp); 1676 EXPECT_EQ(MInLocs[3][0], LiveInRsp); 1677 EXPECT_EQ(MInLocs[4][0], LiveInRsp); 1678 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1679 EXPECT_EQ(MOutLocs[1][0], LiveInRsp); 1680 EXPECT_EQ(MOutLocs[2][0], LiveInRsp); 1681 EXPECT_EQ(MOutLocs[3][0], LiveInRsp); 1682 EXPECT_EQ(MOutLocs[4][0], LiveInRsp); 1683 1684 // A def in loop3 should cause PHIs in every loop block: they're all 1685 // reachable from each other. 1686 TransferFunc[3].insert({RspLoc, RspDefInBlk3}); 1687 initValueArray(MInLocs, 5, 2); 1688 initValueArray(MOutLocs, 5, 2); 1689 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1690 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1691 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1692 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1693 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk3); 1694 EXPECT_EQ(MInLocs[4][0], RspDefInBlk3); 1695 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1696 EXPECT_EQ(MOutLocs[1][0], RspPHIInBlk1); 1697 EXPECT_EQ(MOutLocs[2][0], RspPHIInBlk2); 1698 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk3); 1699 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk3); 1700 TransferFunc[3].clear(); 1701 1702 // A def in loop1 should cause a PHI in loop1, but not the other blocks. 1703 // loop2 and loop3 are dominated by the def in loop1, so they should have 1704 // that value live-through. 1705 TransferFunc[1].insert({RspLoc, RspDefInBlk1}); 1706 initValueArray(MInLocs, 5, 2); 1707 initValueArray(MOutLocs, 5, 2); 1708 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1709 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1710 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1711 EXPECT_EQ(MInLocs[2][0], RspDefInBlk1); 1712 EXPECT_EQ(MInLocs[3][0], RspDefInBlk1); 1713 EXPECT_EQ(MInLocs[4][0], RspDefInBlk1); 1714 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1715 EXPECT_EQ(MOutLocs[1][0], RspDefInBlk1); 1716 EXPECT_EQ(MOutLocs[2][0], RspDefInBlk1); 1717 EXPECT_EQ(MOutLocs[3][0], RspDefInBlk1); 1718 EXPECT_EQ(MOutLocs[4][0], RspDefInBlk1); 1719 TransferFunc[1].clear(); 1720 1721 // As with earlier tricks: copy $rsp to $rax in the entry block, then $rax 1722 // to $rsp in block 3. The only def of $rsp is simply copying the same value 1723 // back into itself, and the value of $rsp is LiveInRsp all the way through. 1724 // PHIs should be created, then value-propagated away... however this 1725 // doesn't work in practice. 1726 // Consider the entry to loop3: we can determine that there's an incoming 1727 // PHI value from loop2, and LiveInRsp from the self-loop. This would still 1728 // justify having a PHI on entry to loop3. The only way to completely 1729 // value-propagate these PHIs away would be to speculatively explore what 1730 // PHIs could be eliminated and what that would lead to; which is 1731 // combinatorially complex. 1732 // Happily: 1733 // a) In this scenario, we always have a tracked location for LiveInRsp 1734 // anyway, so there's no loss in availability, 1735 // b) Only DBG_PHIs of a register would be vunlerable to this scenario, and 1736 // even then only if a true PHI became a DBG_PHI and was then optimised 1737 // through branch folding to no longer be at a CFG join, 1738 // c) The register allocator can spot this kind of redundant COPY easily, 1739 // and eliminate it. 1740 // 1741 // This unit test left in as a reference for the limitations of this 1742 // approach. PHIs will be left in $rsp on entry to each block. 1743 TransferFunc[0].insert({RaxLoc, LiveInRsp}); 1744 TransferFunc[3].insert({RspLoc, RaxPHIInBlk3}); 1745 initValueArray(MInLocs, 5, 2); 1746 initValueArray(MOutLocs, 5, 2); 1747 buildMLocValueMap(MInLocs, MOutLocs, TransferFunc); 1748 EXPECT_EQ(MInLocs[0][0], LiveInRsp); 1749 EXPECT_EQ(MInLocs[1][0], RspPHIInBlk1); 1750 EXPECT_EQ(MInLocs[2][0], RspPHIInBlk2); 1751 EXPECT_EQ(MInLocs[3][0], RspPHIInBlk3); 1752 EXPECT_EQ(MInLocs[4][0], LiveInRsp); 1753 EXPECT_EQ(MOutLocs[0][0], LiveInRsp); 1754 EXPECT_EQ(MOutLocs[1][0], RspPHIInBlk1); 1755 EXPECT_EQ(MOutLocs[2][0], RspPHIInBlk2); 1756 EXPECT_EQ(MOutLocs[3][0], LiveInRsp); 1757 EXPECT_EQ(MOutLocs[4][0], LiveInRsp); 1758 // Check $rax's value. It should have $rsps value from the entry block 1759 // onwards. 1760 EXPECT_EQ(MInLocs[0][1], LiveInRax); 1761 EXPECT_EQ(MInLocs[1][1], LiveInRsp); 1762 EXPECT_EQ(MInLocs[2][1], LiveInRsp); 1763 EXPECT_EQ(MInLocs[3][1], LiveInRsp); 1764 EXPECT_EQ(MInLocs[4][1], LiveInRsp); 1765 EXPECT_EQ(MOutLocs[0][1], LiveInRsp); 1766 EXPECT_EQ(MOutLocs[1][1], LiveInRsp); 1767 EXPECT_EQ(MOutLocs[2][1], LiveInRsp); 1768 EXPECT_EQ(MOutLocs[3][1], LiveInRsp); 1769 EXPECT_EQ(MOutLocs[4][1], LiveInRsp); 1770 } 1771 1772 TEST_F(InstrRefLDVTest, pickVPHILocDiamond) { 1773 // entry 1774 // / \ 1775 // br1 br2 1776 // \ / 1777 // ret 1778 setupDiamondBlocks(); 1779 1780 ASSERT_TRUE(MTracker->getNumLocs() == 1); 1781 LocIdx RspLoc(0); 1782 Register RAX = getRegByName("RAX"); 1783 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 1784 1785 auto [MInLocs, MOutLocs] = allocValueTables(4, 2); 1786 1787 initValueArray(MOutLocs, 4, 2); 1788 1789 unsigned EntryBlk = 0, Br2Blk = 2, RetBlk = 3; 1790 1791 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 1792 ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc); 1793 ValueIDNum RspPHIInBlk2(Br2Blk, 0, RspLoc); 1794 ValueIDNum RspPHIInBlk3(RetBlk, 0, RspLoc); 1795 ValueIDNum RaxPHIInBlk3(RetBlk, 0, RaxLoc); 1796 DbgOpID LiveInRspID = addValueDbgOp(LiveInRsp); 1797 DbgOpID LiveInRaxID = addValueDbgOp(LiveInRax); 1798 DbgOpID RspPHIInBlk2ID = addValueDbgOp(RspPHIInBlk2); 1799 DbgOpID RspPHIInBlk3ID = addValueDbgOp(RspPHIInBlk3); 1800 DbgOpID RaxPHIInBlk3ID = addValueDbgOp(RaxPHIInBlk3); 1801 DbgOpID ConstZeroID = addConstDbgOp(MachineOperand::CreateImm(0)); 1802 1803 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 1804 DbgValueProperties EmptyProps(EmptyExpr, false, false); 1805 DIExpression *TwoOpExpr = 1806 DIExpression::get(Ctx, {dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_LLVM_arg, 1807 1, dwarf::DW_OP_plus}); 1808 DbgValueProperties TwoOpProps(TwoOpExpr, false, true); 1809 SmallVector<DbgValue, 32> VLiveOuts; 1810 VLiveOuts.resize(4, DbgValue(EmptyProps, DbgValue::Undef)); 1811 InstrRefBasedLDV::LiveIdxT VLiveOutIdx; 1812 VLiveOutIdx[MBB0] = &VLiveOuts[0]; 1813 VLiveOutIdx[MBB1] = &VLiveOuts[1]; 1814 VLiveOutIdx[MBB2] = &VLiveOuts[2]; 1815 VLiveOutIdx[MBB3] = &VLiveOuts[3]; 1816 1817 SmallVector<const MachineBasicBlock *, 2> Preds; 1818 for (const auto *Pred : MBB3->predecessors()) 1819 Preds.push_back(Pred); 1820 1821 // Specify the live-outs around the joining block. 1822 MOutLocs[1][0] = LiveInRsp; 1823 MOutLocs[2][0] = LiveInRax; 1824 1825 bool Result; 1826 SmallVector<DbgOpID> OutValues; 1827 1828 // Simple case: join two distinct values on entry to the block. 1829 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 1830 VLiveOuts[2] = DbgValue(LiveInRaxID, EmptyProps); 1831 OutValues.clear(); 1832 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1833 // Should have picked a PHI in $rsp in block 3. 1834 EXPECT_TRUE(Result); 1835 if (Result) { 1836 EXPECT_EQ(OutValues[0], RspPHIInBlk3ID); 1837 } 1838 1839 // If the incoming values are swapped between blocks, we should not 1840 // successfully join. The CFG merge would select the right values, but in 1841 // the wrong conditions. 1842 std::swap(VLiveOuts[1], VLiveOuts[2]); 1843 OutValues.clear(); 1844 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1845 EXPECT_FALSE(Result); 1846 1847 // Swap back, 1848 std::swap(VLiveOuts[1], VLiveOuts[2]); 1849 // Setting one of these to being a constant should prohibit merging. 1850 VLiveOuts[1].setDbgOpIDs(ConstZeroID); 1851 OutValues.clear(); 1852 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1853 EXPECT_FALSE(Result); 1854 1855 // Setting both to being identical constants should result in a valid join 1856 // with a constant value. 1857 VLiveOuts[2] = VLiveOuts[1]; 1858 OutValues.clear(); 1859 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1860 EXPECT_TRUE(Result); 1861 if (Result) { 1862 EXPECT_EQ(OutValues[0], ConstZeroID); 1863 } 1864 1865 // NoVals shouldn't join with anything else. 1866 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 1867 VLiveOuts[2] = DbgValue(2, EmptyProps, DbgValue::NoVal); 1868 OutValues.clear(); 1869 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1870 EXPECT_FALSE(Result); 1871 1872 // We might merge in another VPHI in such a join. Present pickVPHILoc with 1873 // such a scenario: first, where one incoming edge has a VPHI with no known 1874 // value. This represents an edge where there was a PHI value that can't be 1875 // found in the register file -- we can't subsequently find a PHI here. 1876 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 1877 VLiveOuts[2] = DbgValue(2, EmptyProps, DbgValue::VPHI); 1878 OutValues.clear(); 1879 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1880 EXPECT_FALSE(Result); 1881 1882 // However, if we know the value of the incoming VPHI, we can search for its 1883 // location. Use a PHI machine-value for doing this, as VPHIs should always 1884 // have PHI values, or they should have been eliminated. 1885 MOutLocs[2][0] = RspPHIInBlk2; 1886 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 1887 VLiveOuts[2] = DbgValue(2, EmptyProps, DbgValue::VPHI); 1888 VLiveOuts[2].setDbgOpIDs(RspPHIInBlk2ID); // Set location where PHI happens. 1889 OutValues.clear(); 1890 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1891 EXPECT_TRUE(Result); 1892 if (Result) { 1893 EXPECT_EQ(OutValues[0], RspPHIInBlk3ID); 1894 } 1895 1896 // If that value isn't available from that block, don't join. 1897 MOutLocs[2][0] = LiveInRsp; 1898 OutValues.clear(); 1899 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1900 EXPECT_FALSE(Result); 1901 1902 // Check that we don't pick values when the properties disagree, for example 1903 // different indirectness or DIExpression. 1904 MOutLocs[2][0] = LiveInRax; 1905 DIExpression *NewExpr = 1906 DIExpression::prepend(EmptyExpr, DIExpression::ApplyOffset, 4); 1907 DbgValueProperties PropsWithExpr(NewExpr, false, false); 1908 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 1909 VLiveOuts[2] = DbgValue(LiveInRspID, PropsWithExpr); 1910 OutValues.clear(); 1911 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1912 EXPECT_FALSE(Result); 1913 1914 DbgValueProperties PropsWithIndirect(EmptyExpr, true, false); 1915 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 1916 VLiveOuts[2] = DbgValue(LiveInRspID, PropsWithIndirect); 1917 OutValues.clear(); 1918 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1919 EXPECT_FALSE(Result); 1920 1921 // When we have operands with values [A, B] and [B, A], we do not necessarily 1922 // pick identical join locations for each operand if the locations of those 1923 // values differ between incoming basic blocks. 1924 MOutLocs[1][0] = LiveInRsp; 1925 MOutLocs[2][0] = LiveInRax; 1926 MOutLocs[1][1] = LiveInRax; 1927 MOutLocs[2][1] = LiveInRsp; 1928 DbgOpID Locs0[] = {LiveInRspID, LiveInRaxID}; 1929 DbgOpID Locs1[] = {LiveInRaxID, LiveInRspID}; 1930 VLiveOuts[1] = DbgValue(Locs0, TwoOpProps); 1931 VLiveOuts[2] = DbgValue(Locs1, TwoOpProps); 1932 OutValues.clear(); 1933 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1934 // Should have picked PHIs in block 3. 1935 EXPECT_TRUE(Result); 1936 if (Result) { 1937 EXPECT_EQ(OutValues[0], RspPHIInBlk3ID); 1938 EXPECT_EQ(OutValues[1], RaxPHIInBlk3ID); 1939 } 1940 1941 // When joining identical constants for an operand, we should simply keep that 1942 // constant while joining the remaining operands as normal. 1943 DbgOpID Locs2[] = {LiveInRspID, ConstZeroID}; 1944 DbgOpID Locs3[] = {LiveInRaxID, ConstZeroID}; 1945 VLiveOuts[1] = DbgValue(Locs2, TwoOpProps); 1946 VLiveOuts[2] = DbgValue(Locs3, TwoOpProps); 1947 OutValues.clear(); 1948 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1949 EXPECT_TRUE(Result); 1950 if (Result) { 1951 EXPECT_EQ(OutValues[0], RspPHIInBlk3ID); 1952 EXPECT_EQ(OutValues[1], ConstZeroID); 1953 } 1954 1955 // If the debug values have different constants for the same operand, they 1956 // cannot be joined. 1957 DbgOpID ConstOneID = addConstDbgOp(MachineOperand::CreateImm(1)); 1958 DbgOpID Locs4[] = {LiveInRaxID, ConstOneID}; 1959 VLiveOuts[1] = DbgValue(Locs3, TwoOpProps); 1960 VLiveOuts[2] = DbgValue(Locs4, TwoOpProps); 1961 OutValues.clear(); 1962 Result = pickVPHILoc(OutValues, *MBB3, VLiveOutIdx, MOutLocs, Preds); 1963 EXPECT_FALSE(Result); 1964 } 1965 1966 TEST_F(InstrRefLDVTest, pickVPHILocLoops) { 1967 setupSimpleLoop(); 1968 // entry 1969 // | 1970 // |/-----\ 1971 // loopblk | 1972 // |\-----/ 1973 // | 1974 // ret 1975 1976 ASSERT_TRUE(MTracker->getNumLocs() == 1); 1977 LocIdx RspLoc(0); 1978 Register RAX = getRegByName("RAX"); 1979 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 1980 1981 auto [MInLocs, MOutLocs] = allocValueTables(3, 2); 1982 1983 initValueArray(MOutLocs, 3, 2); 1984 1985 unsigned EntryBlk = 0, LoopBlk = 1; 1986 1987 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 1988 ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc); 1989 ValueIDNum RspPHIInBlk1(LoopBlk, 0, RspLoc); 1990 ValueIDNum RaxPHIInBlk1(LoopBlk, 0, RaxLoc); 1991 DbgOpID LiveInRspID = addValueDbgOp(LiveInRsp); 1992 DbgOpID LiveInRaxID = addValueDbgOp(LiveInRax); 1993 DbgOpID RspPHIInBlk1ID = addValueDbgOp(RspPHIInBlk1); 1994 DbgOpID RaxPHIInBlk1ID = addValueDbgOp(RaxPHIInBlk1); 1995 1996 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 1997 DbgValueProperties EmptyProps(EmptyExpr, false, false); 1998 DIExpression *TwoOpExpr = 1999 DIExpression::get(Ctx, {dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_LLVM_arg, 2000 1, dwarf::DW_OP_plus}); 2001 DbgValueProperties TwoOpProps(TwoOpExpr, false, true); 2002 SmallVector<DbgValue, 32> VLiveOuts; 2003 VLiveOuts.resize(3, DbgValue(EmptyProps, DbgValue::Undef)); 2004 InstrRefBasedLDV::LiveIdxT VLiveOutIdx; 2005 VLiveOutIdx[MBB0] = &VLiveOuts[0]; 2006 VLiveOutIdx[MBB1] = &VLiveOuts[1]; 2007 VLiveOutIdx[MBB2] = &VLiveOuts[2]; 2008 2009 SmallVector<const MachineBasicBlock *, 2> Preds; 2010 for (const auto *Pred : MBB1->predecessors()) 2011 Preds.push_back(Pred); 2012 2013 // Specify the live-outs around the joining block. 2014 MOutLocs[0][0] = LiveInRsp; 2015 MOutLocs[1][0] = LiveInRax; 2016 2017 bool Result; 2018 SmallVector<DbgOpID> OutValues; 2019 2020 // See that we can merge as normal on a backedge. 2021 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2022 VLiveOuts[1] = DbgValue(LiveInRaxID, EmptyProps); 2023 OutValues.clear(); 2024 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2025 // Should have picked a PHI in $rsp in block 1. 2026 EXPECT_TRUE(Result); 2027 if (Result) { 2028 EXPECT_EQ(OutValues[0], RspPHIInBlk1ID); 2029 } 2030 2031 // And that, if the desired values aren't available, we don't merge. 2032 MOutLocs[1][0] = LiveInRsp; 2033 OutValues.clear(); 2034 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2035 EXPECT_FALSE(Result); 2036 2037 // Test the backedge behaviour: PHIs that feed back into themselves can 2038 // carry this variables value. Feed in LiveInRsp in both $rsp and $rax 2039 // from the entry block, but only put an appropriate backedge PHI in $rax. 2040 // Only the $rax location can form the correct PHI. 2041 MOutLocs[0][0] = LiveInRsp; 2042 MOutLocs[0][1] = LiveInRsp; 2043 MOutLocs[1][0] = RaxPHIInBlk1; 2044 MOutLocs[1][1] = RaxPHIInBlk1; 2045 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2046 // Crucially, a VPHI originating in this block: 2047 VLiveOuts[1] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2048 OutValues.clear(); 2049 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2050 EXPECT_TRUE(Result); 2051 if (Result) { 2052 EXPECT_EQ(OutValues[0], RaxPHIInBlk1ID); 2053 } 2054 2055 // Test that we can also find a location when joining a backedge PHI with 2056 // a variadic debug value. 2057 MOutLocs[1][0] = RspPHIInBlk1; 2058 MOutLocs[0][1] = LiveInRax; 2059 DbgOpID Locs0[] = {LiveInRspID, LiveInRaxID}; 2060 VLiveOuts[0] = DbgValue(Locs0, TwoOpProps); 2061 // Crucially, a VPHI originating in this block: 2062 VLiveOuts[1] = DbgValue(1, TwoOpProps, DbgValue::VPHI); 2063 OutValues.clear(); 2064 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2065 EXPECT_TRUE(Result); 2066 if (Result) { 2067 EXPECT_EQ(OutValues[0], RspPHIInBlk1ID); 2068 EXPECT_EQ(OutValues[1], RaxPHIInBlk1ID); 2069 } 2070 2071 // Merging should not be permitted if there's a usable PHI on the backedge, 2072 // but it's in the wrong place. (Overwrite $rax). 2073 MOutLocs[1][1] = LiveInRax; 2074 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2075 OutValues.clear(); 2076 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2077 EXPECT_FALSE(Result); 2078 2079 // Additionally, if the VPHI coming back on the loop backedge isn't from 2080 // this block (block 1), we can't merge it. 2081 MOutLocs[1][1] = RaxPHIInBlk1; 2082 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2083 VLiveOuts[1] = DbgValue(0, EmptyProps, DbgValue::VPHI); 2084 OutValues.clear(); 2085 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2086 EXPECT_FALSE(Result); 2087 } 2088 2089 TEST_F(InstrRefLDVTest, pickVPHILocBadlyNestedLoops) { 2090 // Run some tests similar to pickVPHILocLoops, with more than one backedge, 2091 // and check that we merge correctly over many candidate locations. 2092 setupBadlyNestedLoops(); 2093 // entry 2094 // | 2095 // loop1 -o 2096 // | ^ 2097 // | ^ 2098 // loop2 -o 2099 // | ^ 2100 // | ^ 2101 // loop3 -o 2102 // | 2103 // ret 2104 ASSERT_TRUE(MTracker->getNumLocs() == 1); 2105 LocIdx RspLoc(0); 2106 Register RAX = getRegByName("RAX"); 2107 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 2108 Register RBX = getRegByName("RBX"); 2109 LocIdx RbxLoc = MTracker->lookupOrTrackRegister(RBX); 2110 2111 auto [MInLocs, MOutLocs] = allocValueTables(5, 3); 2112 2113 initValueArray(MOutLocs, 5, 3); 2114 2115 unsigned EntryBlk = 0, Loop1Blk = 1; 2116 2117 ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); 2118 ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc); 2119 ValueIDNum LiveInRbx(EntryBlk, 0, RbxLoc); 2120 ValueIDNum RspPHIInBlk1(Loop1Blk, 0, RspLoc); 2121 ValueIDNum RaxPHIInBlk1(Loop1Blk, 0, RaxLoc); 2122 ValueIDNum RbxPHIInBlk1(Loop1Blk, 0, RbxLoc); 2123 DbgOpID LiveInRspID = addValueDbgOp(LiveInRsp); 2124 DbgOpID LiveInRaxID = addValueDbgOp(LiveInRax); 2125 DbgOpID LiveInRbxID = addValueDbgOp(LiveInRbx); 2126 DbgOpID RspPHIInBlk1ID = addValueDbgOp(RspPHIInBlk1); 2127 addValueDbgOp(RaxPHIInBlk1); 2128 DbgOpID RbxPHIInBlk1ID = addValueDbgOp(RbxPHIInBlk1); 2129 2130 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 2131 DbgValueProperties EmptyProps(EmptyExpr, false, false); 2132 SmallVector<DbgValue, 32> VLiveOuts; 2133 VLiveOuts.resize(5, DbgValue(EmptyProps, DbgValue::Undef)); 2134 InstrRefBasedLDV::LiveIdxT VLiveOutIdx; 2135 VLiveOutIdx[MBB0] = &VLiveOuts[0]; 2136 VLiveOutIdx[MBB1] = &VLiveOuts[1]; 2137 VLiveOutIdx[MBB2] = &VLiveOuts[2]; 2138 VLiveOutIdx[MBB3] = &VLiveOuts[3]; 2139 VLiveOutIdx[MBB4] = &VLiveOuts[4]; 2140 2141 // We're going to focus on block 1. 2142 SmallVector<const MachineBasicBlock *, 2> Preds; 2143 for (const auto *Pred : MBB1->predecessors()) 2144 Preds.push_back(Pred); 2145 2146 // Specify the live-outs around the joining block. Incoming edges from the 2147 // entry block, self, and loop2. 2148 MOutLocs[0][0] = LiveInRsp; 2149 MOutLocs[1][0] = LiveInRax; 2150 MOutLocs[2][0] = LiveInRbx; 2151 2152 bool Result; 2153 SmallVector<DbgOpID> OutValues; 2154 2155 // See that we can merge as normal on a backedge. 2156 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2157 VLiveOuts[1] = DbgValue(LiveInRaxID, EmptyProps); 2158 VLiveOuts[2] = DbgValue(LiveInRbxID, EmptyProps); 2159 OutValues.clear(); 2160 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2161 // Should have picked a PHI in $rsp in block 1. 2162 EXPECT_TRUE(Result); 2163 if (Result) { 2164 EXPECT_EQ(OutValues[0], RspPHIInBlk1ID); 2165 } 2166 2167 // Check too that permuting the live-out locations prevents merging 2168 MOutLocs[0][0] = LiveInRax; 2169 MOutLocs[1][0] = LiveInRbx; 2170 MOutLocs[2][0] = LiveInRsp; 2171 OutValues.clear(); 2172 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2173 EXPECT_FALSE(Result); 2174 2175 MOutLocs[0][0] = LiveInRsp; 2176 MOutLocs[1][0] = LiveInRax; 2177 MOutLocs[2][0] = LiveInRbx; 2178 2179 // Feeding a PHI back on one backedge shouldn't merge (block 1 self backedge 2180 // wants LiveInRax). 2181 MOutLocs[1][0] = RspPHIInBlk1; 2182 OutValues.clear(); 2183 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2184 EXPECT_FALSE(Result); 2185 2186 // If the variables value on that edge is a VPHI feeding into itself, that's 2187 // fine. 2188 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2189 VLiveOuts[1] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2190 VLiveOuts[2] = DbgValue(LiveInRbxID, EmptyProps); 2191 OutValues.clear(); 2192 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2193 EXPECT_TRUE(Result); 2194 if (Result) { 2195 EXPECT_EQ(OutValues[0], RspPHIInBlk1ID); 2196 } 2197 2198 // Likewise: the other backedge being a VPHI from block 1 should be accepted. 2199 MOutLocs[2][0] = RspPHIInBlk1; 2200 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2201 VLiveOuts[1] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2202 VLiveOuts[2] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2203 OutValues.clear(); 2204 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2205 EXPECT_TRUE(Result); 2206 if (Result) { 2207 EXPECT_EQ(OutValues[0], RspPHIInBlk1ID); 2208 } 2209 2210 // Here's where it becomes tricky: we should not merge if there are two 2211 // _distinct_ backedge PHIs. We can't have a PHI that happens in both rsp 2212 // and rax for example. We can only pick one location as the live-in. 2213 MOutLocs[2][0] = RaxPHIInBlk1; 2214 OutValues.clear(); 2215 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2216 EXPECT_FALSE(Result); 2217 2218 // The above test sources correct machine-PHI-value from two places. Now 2219 // try with one machine-PHI-value, but placed in two different locations 2220 // on the backedge. Again, we can't merge a location here, there's no 2221 // location that works on all paths. 2222 MOutLocs[0][0] = LiveInRsp; 2223 MOutLocs[1][0] = RspPHIInBlk1; 2224 MOutLocs[2][0] = LiveInRsp; 2225 MOutLocs[2][1] = RspPHIInBlk1; 2226 OutValues.clear(); 2227 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2228 EXPECT_FALSE(Result); 2229 2230 // Scatter various PHI values across the available locations. Only rbx (loc 2) 2231 // has the right value in both backedges -- that's the loc that should be 2232 // picked. 2233 MOutLocs[0][2] = LiveInRsp; 2234 MOutLocs[1][0] = RspPHIInBlk1; 2235 MOutLocs[1][1] = RaxPHIInBlk1; 2236 MOutLocs[1][2] = RbxPHIInBlk1; 2237 MOutLocs[2][0] = LiveInRsp; 2238 MOutLocs[2][1] = RspPHIInBlk1; 2239 MOutLocs[2][2] = RbxPHIInBlk1; 2240 OutValues.clear(); 2241 Result = pickVPHILoc(OutValues, *MBB1, VLiveOutIdx, MOutLocs, Preds); 2242 EXPECT_TRUE(Result); 2243 if (Result) { 2244 EXPECT_EQ(OutValues[0], RbxPHIInBlk1ID); 2245 } 2246 } 2247 2248 TEST_F(InstrRefLDVTest, vlocJoinDiamond) { 2249 // entry 2250 // / \ 2251 // br1 br2 2252 // \ / 2253 // ret 2254 setupDiamondBlocks(); 2255 2256 ASSERT_TRUE(MTracker->getNumLocs() == 1); 2257 LocIdx RspLoc(0); 2258 Register RAX = getRegByName("RAX"); 2259 MTracker->lookupOrTrackRegister(RAX); 2260 2261 DbgOpID LiveInRspID = DbgOpID(false, 0); 2262 DbgOpID LiveInRaxID = DbgOpID(false, 1); 2263 2264 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 2265 DbgValueProperties EmptyProps(EmptyExpr, false, false); 2266 SmallVector<DbgValue, 32> VLiveOuts; 2267 VLiveOuts.resize(4, DbgValue(EmptyProps, DbgValue::Undef)); 2268 InstrRefBasedLDV::LiveIdxT VLiveOutIdx; 2269 VLiveOutIdx[MBB0] = &VLiveOuts[0]; 2270 VLiveOutIdx[MBB1] = &VLiveOuts[1]; 2271 VLiveOutIdx[MBB2] = &VLiveOuts[2]; 2272 VLiveOutIdx[MBB3] = &VLiveOuts[3]; 2273 2274 SmallPtrSet<const MachineBasicBlock *, 8> AllBlocks; 2275 AllBlocks.insert(MBB0); 2276 AllBlocks.insert(MBB1); 2277 AllBlocks.insert(MBB2); 2278 AllBlocks.insert(MBB3); 2279 2280 SmallVector<const MachineBasicBlock *, 2> Preds; 2281 for (const auto *Pred : MBB3->predecessors()) 2282 Preds.push_back(Pred); 2283 2284 SmallSet<DebugVariable, 4> AllVars; 2285 AllVars.insert(Var); 2286 2287 // vlocJoin is here to propagate incoming values, and eliminate PHIs. Start 2288 // off by propagating a value into the merging block, number 3. 2289 DbgValue JoinedLoc = DbgValue(3, EmptyProps, DbgValue::NoVal); 2290 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2291 VLiveOuts[2] = DbgValue(LiveInRspID, EmptyProps); 2292 bool Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2293 EXPECT_TRUE(Result); // Output locs should have changed. 2294 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2295 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRspID); 2296 2297 // And if we did it a second time, leaving the live-ins as it was, then 2298 // we should report no change. 2299 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2300 EXPECT_FALSE(Result); 2301 2302 // If the live-in variable values are different, but there's no PHI placed 2303 // in this block, then just pick a location. It should be the first (in RPO) 2304 // predecessor to avoid being a backedge. 2305 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2306 VLiveOuts[2] = DbgValue(LiveInRaxID, EmptyProps); 2307 JoinedLoc = DbgValue(3, EmptyProps, DbgValue::NoVal); 2308 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2309 EXPECT_TRUE(Result); 2310 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2311 // RPO is blocks 0 2 1 3, so LiveInRax is picked as the first predecessor 2312 // of this join. 2313 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRaxID); 2314 2315 // No tests for whether vlocJoin will pass-through a variable with differing 2316 // expressions / properties. Those can only come about due to assignments; and 2317 // for any assignment at all, a PHI should have been placed at the dominance 2318 // frontier. We rely on the IDF calculator being accurate (which is OK, 2319 // because so does the rest of LLVM). 2320 2321 // Try placing a PHI. With differing input values (LiveInRsp, LiveInRax), 2322 // this PHI should not be eliminated. 2323 JoinedLoc = DbgValue(3, EmptyProps, DbgValue::VPHI); 2324 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2325 // Expect no change. 2326 EXPECT_FALSE(Result); 2327 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2328 // This should not have been assigned a fixed value. 2329 EXPECT_EQ(JoinedLoc.getDbgOpID(0), DbgOpID::UndefID); 2330 EXPECT_EQ(JoinedLoc.BlockNo, 3); 2331 2332 // Try a simple PHI elimination. Put a PHI in block 3, but LiveInRsp on both 2333 // incoming edges. Re-load in and out-locs with unrelated values; they're 2334 // irrelevant. 2335 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2336 VLiveOuts[2] = DbgValue(LiveInRspID, EmptyProps); 2337 JoinedLoc = DbgValue(3, EmptyProps, DbgValue::VPHI); 2338 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2339 EXPECT_TRUE(Result); 2340 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2341 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRspID); 2342 2343 // Try the same PHI elimination but with one incoming value being a VPHI 2344 // referring to the same value. 2345 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2346 VLiveOuts[2] = DbgValue(2, EmptyProps, DbgValue::VPHI); 2347 VLiveOuts[2].setDbgOpIDs(LiveInRspID); 2348 JoinedLoc = DbgValue(3, EmptyProps, DbgValue::VPHI); 2349 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2350 EXPECT_TRUE(Result); 2351 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2352 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRspID); 2353 2354 // If the "current" live-in is a VPHI, but not a VPHI generated in the current 2355 // block, then it's the remains of an earlier value propagation. We should 2356 // value propagate through this merge. Even if the current incoming values 2357 // disagree, because we've previously determined any VPHI here is redundant. 2358 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2359 VLiveOuts[2] = DbgValue(LiveInRaxID, EmptyProps); 2360 JoinedLoc = DbgValue(2, EmptyProps, DbgValue::VPHI); 2361 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2362 EXPECT_TRUE(Result); 2363 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2364 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRaxID); // from block 2 2365 2366 // The above test, but test that we will install one value-propagated VPHI 2367 // over another. 2368 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2369 VLiveOuts[2] = DbgValue(0, EmptyProps, DbgValue::VPHI); 2370 JoinedLoc = DbgValue(2, EmptyProps, DbgValue::VPHI); 2371 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2372 EXPECT_TRUE(Result); 2373 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2374 EXPECT_EQ(JoinedLoc.BlockNo, 0); 2375 2376 // We shouldn't eliminate PHIs when properties disagree. 2377 DbgValueProperties PropsWithIndirect(EmptyExpr, true, false); 2378 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2379 VLiveOuts[2] = DbgValue(LiveInRspID, PropsWithIndirect); 2380 JoinedLoc = DbgValue(3, EmptyProps, DbgValue::VPHI); 2381 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2382 EXPECT_FALSE(Result); 2383 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2384 EXPECT_EQ(JoinedLoc.BlockNo, 3); 2385 2386 // Even if properties disagree, we should still value-propagate if there's no 2387 // PHI to be eliminated. The disagreeing values should work themselves out, 2388 // seeing how we've determined no PHI is necessary. 2389 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2390 VLiveOuts[2] = DbgValue(LiveInRspID, PropsWithIndirect); 2391 JoinedLoc = DbgValue(2, EmptyProps, DbgValue::VPHI); 2392 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2393 EXPECT_TRUE(Result); 2394 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2395 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRspID); 2396 // Also check properties come from block 2, the first RPO predecessor to block 2397 // three. 2398 EXPECT_EQ(JoinedLoc.Properties, PropsWithIndirect); 2399 2400 // Again, disagreeing properties, this time the expr, should cause a PHI to 2401 // not be eliminated. 2402 DIExpression *NewExpr = 2403 DIExpression::prepend(EmptyExpr, DIExpression::ApplyOffset, 4); 2404 DbgValueProperties PropsWithExpr(NewExpr, false, false); 2405 VLiveOuts[1] = DbgValue(LiveInRspID, EmptyProps); 2406 VLiveOuts[2] = DbgValue(LiveInRspID, PropsWithExpr); 2407 JoinedLoc = DbgValue(3, EmptyProps, DbgValue::VPHI); 2408 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2409 EXPECT_FALSE(Result); 2410 2411 // Try placing a PHI with variadic debug values. With differing input values 2412 // (LiveInRsp, LiveInRax), this PHI should not be eliminated. 2413 DIExpression *TwoOpExpr = 2414 DIExpression::get(Ctx, {dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_LLVM_arg, 2415 1, dwarf::DW_OP_plus}); 2416 DbgValueProperties TwoOpProps(TwoOpExpr, false, true); 2417 DbgOpID Locs0[] = {LiveInRspID, LiveInRaxID}; 2418 DbgOpID Locs1[] = {LiveInRaxID, LiveInRspID}; 2419 JoinedLoc = DbgValue(3, TwoOpProps, DbgValue::VPHI); 2420 VLiveOuts[1] = DbgValue(Locs0, TwoOpProps); 2421 VLiveOuts[2] = DbgValue(Locs1, TwoOpProps); 2422 Result = vlocJoin(*MBB3, VLiveOutIdx, AllBlocks, JoinedLoc); 2423 // Expect no change. 2424 EXPECT_FALSE(Result); 2425 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2426 // This should not have been assigned a fixed value. 2427 EXPECT_EQ(JoinedLoc.getDbgOpID(0), DbgOpID::UndefID); 2428 EXPECT_EQ(JoinedLoc.BlockNo, 3); 2429 } 2430 2431 TEST_F(InstrRefLDVTest, vlocJoinLoops) { 2432 setupSimpleLoop(); 2433 // entry 2434 // | 2435 // |/-----\ 2436 // loopblk | 2437 // |\-----/ 2438 // | 2439 // ret 2440 ASSERT_TRUE(MTracker->getNumLocs() == 1); 2441 LocIdx RspLoc(0); 2442 Register RAX = getRegByName("RAX"); 2443 MTracker->lookupOrTrackRegister(RAX); 2444 2445 DbgOpID LiveInRspID = DbgOpID(false, 0); 2446 DbgOpID LiveInRaxID = DbgOpID(false, 1); 2447 2448 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 2449 DbgValueProperties EmptyProps(EmptyExpr, false, false); 2450 SmallVector<DbgValue, 32> VLiveOuts; 2451 VLiveOuts.resize(3, DbgValue(EmptyProps, DbgValue::Undef)); 2452 InstrRefBasedLDV::LiveIdxT VLiveOutIdx; 2453 VLiveOutIdx[MBB0] = &VLiveOuts[0]; 2454 VLiveOutIdx[MBB1] = &VLiveOuts[1]; 2455 VLiveOutIdx[MBB2] = &VLiveOuts[2]; 2456 2457 SmallPtrSet<const MachineBasicBlock *, 8> AllBlocks; 2458 AllBlocks.insert(MBB0); 2459 AllBlocks.insert(MBB1); 2460 AllBlocks.insert(MBB2); 2461 2462 SmallVector<const MachineBasicBlock *, 2> Preds; 2463 for (const auto *Pred : MBB1->predecessors()) 2464 Preds.push_back(Pred); 2465 2466 SmallSet<DebugVariable, 4> AllVars; 2467 AllVars.insert(Var); 2468 2469 // Test some back-edge-specific behaviours of vloc join. Mostly: the fact that 2470 // VPHIs that arrive on backedges can be eliminated, despite having different 2471 // values to the predecessor. 2472 2473 // First: when there's no VPHI placed already, propagate the live-in value of 2474 // the first RPO predecessor. 2475 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2476 VLiveOuts[1] = DbgValue(LiveInRaxID, EmptyProps); 2477 DbgValue JoinedLoc = DbgValue(LiveInRaxID, EmptyProps); 2478 bool Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2479 EXPECT_TRUE(Result); 2480 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2481 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRspID); 2482 2483 // If there is a VPHI: don't elimiante it if there are disagreeing values. 2484 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2485 VLiveOuts[1] = DbgValue(LiveInRaxID, EmptyProps); 2486 JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2487 Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2488 EXPECT_FALSE(Result); 2489 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2490 EXPECT_EQ(JoinedLoc.BlockNo, 1); 2491 2492 // If we feed this VPHI back into itself though, we can eliminate it. 2493 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2494 VLiveOuts[1] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2495 JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2496 Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2497 EXPECT_TRUE(Result); 2498 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2499 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRspID); 2500 2501 // Don't eliminate backedge VPHIs if the predecessors have different 2502 // properties. 2503 DIExpression *NewExpr = 2504 DIExpression::prepend(EmptyExpr, DIExpression::ApplyOffset, 4); 2505 DbgValueProperties PropsWithExpr(NewExpr, false, false); 2506 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2507 VLiveOuts[1] = DbgValue(1, PropsWithExpr, DbgValue::VPHI); 2508 JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2509 Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2510 EXPECT_FALSE(Result); 2511 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2512 EXPECT_EQ(JoinedLoc.BlockNo, 1); 2513 2514 // Backedges with VPHIs, but from the wrong block, shouldn't be eliminated. 2515 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2516 VLiveOuts[1] = DbgValue(0, EmptyProps, DbgValue::VPHI); 2517 JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2518 Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2519 EXPECT_FALSE(Result); 2520 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2521 EXPECT_EQ(JoinedLoc.BlockNo, 1); 2522 } 2523 2524 TEST_F(InstrRefLDVTest, vlocJoinBadlyNestedLoops) { 2525 // Test PHI elimination in the presence of multiple backedges. 2526 setupBadlyNestedLoops(); 2527 // entry 2528 // | 2529 // loop1 -o 2530 // | ^ 2531 // | ^ 2532 // loop2 -o 2533 // | ^ 2534 // | ^ 2535 // loop3 -o 2536 // | 2537 // ret 2538 ASSERT_TRUE(MTracker->getNumLocs() == 1); 2539 LocIdx RspLoc(0); 2540 Register RAX = getRegByName("RAX"); 2541 MTracker->lookupOrTrackRegister(RAX); 2542 Register RBX = getRegByName("RBX"); 2543 MTracker->lookupOrTrackRegister(RBX); 2544 2545 DbgOpID LiveInRspID = DbgOpID(false, 0); 2546 DbgOpID LiveInRaxID = DbgOpID(false, 1); 2547 DbgOpID LiveInRbxID = DbgOpID(false, 2); 2548 2549 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 2550 DbgValueProperties EmptyProps(EmptyExpr, false, false); 2551 SmallVector<DbgValue, 32> VLiveOuts; 2552 VLiveOuts.resize(5, DbgValue(EmptyProps, DbgValue::Undef)); 2553 InstrRefBasedLDV::LiveIdxT VLiveOutIdx; 2554 VLiveOutIdx[MBB0] = &VLiveOuts[0]; 2555 VLiveOutIdx[MBB1] = &VLiveOuts[1]; 2556 VLiveOutIdx[MBB2] = &VLiveOuts[2]; 2557 VLiveOutIdx[MBB3] = &VLiveOuts[3]; 2558 VLiveOutIdx[MBB4] = &VLiveOuts[4]; 2559 2560 SmallPtrSet<const MachineBasicBlock *, 8> AllBlocks; 2561 AllBlocks.insert(MBB0); 2562 AllBlocks.insert(MBB1); 2563 AllBlocks.insert(MBB2); 2564 AllBlocks.insert(MBB3); 2565 AllBlocks.insert(MBB4); 2566 2567 // We're going to focus on block 1. 2568 SmallVector<const MachineBasicBlock *, 3> Preds; 2569 for (const auto *Pred : MBB1->predecessors()) 2570 Preds.push_back(Pred); 2571 2572 SmallSet<DebugVariable, 4> AllVars; 2573 AllVars.insert(Var); 2574 2575 // Test a normal VPHI isn't eliminated. 2576 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2577 VLiveOuts[1] = DbgValue(LiveInRaxID, EmptyProps); 2578 VLiveOuts[2] = DbgValue(LiveInRbxID, EmptyProps); 2579 DbgValue JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2580 bool Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2581 EXPECT_FALSE(Result); 2582 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2583 EXPECT_EQ(JoinedLoc.BlockNo, 1); 2584 2585 // Common VPHIs on backedges should merge. 2586 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2587 VLiveOuts[1] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2588 VLiveOuts[2] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2589 JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2590 Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2591 EXPECT_TRUE(Result); 2592 EXPECT_EQ(JoinedLoc.Kind, DbgValue::Def); 2593 EXPECT_EQ(JoinedLoc.getDbgOpID(0), LiveInRspID); 2594 2595 // They shouldn't merge if one of their properties is different. 2596 DbgValueProperties PropsWithIndirect(EmptyExpr, true, false); 2597 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2598 VLiveOuts[1] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2599 VLiveOuts[2] = DbgValue(1, PropsWithIndirect, DbgValue::VPHI); 2600 JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2601 Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2602 EXPECT_FALSE(Result); 2603 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2604 EXPECT_EQ(JoinedLoc.BlockNo, 1); 2605 2606 // VPHIs from different blocks should not merge. 2607 VLiveOuts[0] = DbgValue(LiveInRspID, EmptyProps); 2608 VLiveOuts[1] = DbgValue(1, EmptyProps, DbgValue::VPHI); 2609 VLiveOuts[2] = DbgValue(2, EmptyProps, DbgValue::VPHI); 2610 JoinedLoc = DbgValue(1, EmptyProps, DbgValue::VPHI); 2611 Result = vlocJoin(*MBB1, VLiveOutIdx, AllBlocks, JoinedLoc); 2612 EXPECT_FALSE(Result); 2613 EXPECT_EQ(JoinedLoc.Kind, DbgValue::VPHI); 2614 EXPECT_EQ(JoinedLoc.BlockNo, 1); 2615 } 2616 2617 // Above are tests for picking VPHI locations, and eliminating VPHIs. No 2618 // unit-tests are written for evaluating the transfer function as that's 2619 // pretty straight forwards, or applying VPHI-location-picking to live-ins. 2620 // Instead, pre-set some machine locations and apply buildVLocValueMap to the 2621 // existing CFG patterns. 2622 TEST_F(InstrRefLDVTest, VLocSingleBlock) { 2623 setupSingleBlock(); 2624 2625 ASSERT_TRUE(MTracker->getNumLocs() == 1); 2626 LocIdx RspLoc(0); 2627 2628 auto [MInLocs, MOutLocs] = allocValueTables(1, 2); 2629 2630 ValueIDNum LiveInRsp = ValueIDNum(0, 0, RspLoc); 2631 DbgOpID LiveInRspID = addValueDbgOp(LiveInRsp); 2632 MInLocs[0][0] = MOutLocs[0][0] = LiveInRsp; 2633 2634 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 2635 DebugVariableID VarID = LDV->getDVMap().insertDVID(Var, OutermostLoc); 2636 DbgValueProperties EmptyProps(EmptyExpr, false, false); 2637 2638 SmallSet<DebugVariableID, 4> AllVars; 2639 AllVars.insert(VarID); 2640 2641 // Mild hack: rather than constructing machine instructions in each block 2642 // and creating lexical scopes across them, instead just tell 2643 // buildVLocValueMap that there's an assignment in every block. That makes 2644 // every block in scope. 2645 SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks; 2646 AssignBlocks.insert(MBB0); 2647 2648 SmallVector<VLocTracker, 1> VLocs; 2649 VLocs.resize(1, VLocTracker(LDV->getDVMap(), Overlaps, EmptyExpr)); 2650 2651 InstrRefBasedLDV::LiveInsT Output; 2652 2653 // Test that, with no assignments at all, no mappings are created for the 2654 // variable in this function. 2655 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2656 MOutLocs, MInLocs, VLocs); 2657 EXPECT_EQ(Output.size(), 0ul); 2658 2659 // If we put an assignment in the transfer function, that should... well, 2660 // do nothing, because we don't store the live-outs. 2661 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2662 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2663 MOutLocs, MInLocs, VLocs); 2664 EXPECT_EQ(Output.size(), 0ul); 2665 2666 // There is pretty much nothing else of interest to test with a single block. 2667 // It's not relevant to the SSA-construction parts of variable values. 2668 } 2669 2670 TEST_F(InstrRefLDVTest, VLocDiamondBlocks) { 2671 setupDiamondBlocks(); 2672 // entry 2673 // / \ 2674 // br1 br2 2675 // \ / 2676 // ret 2677 2678 ASSERT_TRUE(MTracker->getNumLocs() == 1); 2679 LocIdx RspLoc(0); 2680 Register RAX = getRegByName("RAX"); 2681 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 2682 2683 unsigned EntryBlk = 0, RetBlk = 3; 2684 2685 ValueIDNum LiveInRsp = ValueIDNum(EntryBlk, 0, RspLoc); 2686 ValueIDNum LiveInRax = ValueIDNum(EntryBlk, 0, RaxLoc); 2687 ValueIDNum RspPHIInBlk3 = ValueIDNum(RetBlk, 0, RspLoc); 2688 DbgOpID LiveInRspID = addValueDbgOp(LiveInRsp); 2689 DbgOpID LiveInRaxID = addValueDbgOp(LiveInRax); 2690 DbgOpID RspPHIInBlk3ID = addValueDbgOp(RspPHIInBlk3); 2691 2692 auto [MInLocs, MOutLocs] = allocValueTables(4, 2); 2693 2694 initValueArray(MInLocs, 4, 2); 2695 initValueArray(MOutLocs, 4, 2); 2696 2697 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 2698 DebugVariableID VarID = LDV->getDVMap().insertDVID(Var, OutermostLoc); 2699 DbgValueProperties EmptyProps(EmptyExpr, false, false); 2700 2701 SmallSet<DebugVariableID, 4> AllVars; 2702 AllVars.insert(VarID); 2703 2704 // Mild hack: rather than constructing machine instructions in each block 2705 // and creating lexical scopes across them, instead just tell 2706 // buildVLocValueMap that there's an assignment in every block. That makes 2707 // every block in scope. 2708 SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks; 2709 AssignBlocks.insert(MBB0); 2710 AssignBlocks.insert(MBB1); 2711 AssignBlocks.insert(MBB2); 2712 AssignBlocks.insert(MBB3); 2713 2714 SmallVector<VLocTracker, 1> VLocs; 2715 VLocs.resize(4, VLocTracker(LDV->getDVMap(), Overlaps, EmptyExpr)); 2716 2717 InstrRefBasedLDV::LiveInsT Output; 2718 2719 // Start off with LiveInRsp in every location. 2720 for (unsigned int I = 0; I < 4; ++I) { 2721 MInLocs[I][0] = MInLocs[I][1] = LiveInRsp; 2722 MOutLocs[I][0] = MOutLocs[I][1] = LiveInRsp; 2723 } 2724 2725 auto ClearOutputs = [&]() { 2726 for (auto &Elem : Output) 2727 Elem.clear(); 2728 }; 2729 Output.resize(4); 2730 2731 // No assignments -> no values. 2732 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2733 MOutLocs, MInLocs, VLocs); 2734 EXPECT_EQ(Output[0].size(), 0ul); 2735 EXPECT_EQ(Output[1].size(), 0ul); 2736 EXPECT_EQ(Output[2].size(), 0ul); 2737 EXPECT_EQ(Output[3].size(), 0ul); 2738 2739 // An assignment in the end block should also not affect other blocks; or 2740 // produce any live-ins. 2741 VLocs[3].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2742 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2743 MOutLocs, MInLocs, VLocs); 2744 EXPECT_EQ(Output[0].size(), 0ul); 2745 EXPECT_EQ(Output[1].size(), 0ul); 2746 EXPECT_EQ(Output[2].size(), 0ul); 2747 EXPECT_EQ(Output[3].size(), 0ul); 2748 ClearOutputs(); 2749 2750 // Assignments in either of the side-of-diamond blocks should also not be 2751 // propagated anywhere. 2752 VLocs[3].Vars.clear(); 2753 VLocs[2].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2754 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2755 MOutLocs, MInLocs, VLocs); 2756 EXPECT_EQ(Output[0].size(), 0ul); 2757 EXPECT_EQ(Output[1].size(), 0ul); 2758 EXPECT_EQ(Output[2].size(), 0ul); 2759 EXPECT_EQ(Output[3].size(), 0ul); 2760 VLocs[2].Vars.clear(); 2761 ClearOutputs(); 2762 2763 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2764 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2765 MOutLocs, MInLocs, VLocs); 2766 EXPECT_EQ(Output[0].size(), 0ul); 2767 EXPECT_EQ(Output[1].size(), 0ul); 2768 EXPECT_EQ(Output[2].size(), 0ul); 2769 EXPECT_EQ(Output[3].size(), 0ul); 2770 VLocs[1].Vars.clear(); 2771 ClearOutputs(); 2772 2773 // However: putting an assignment in the first block should propagate variable 2774 // values through to all other blocks, as it dominates. 2775 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2776 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2777 MOutLocs, MInLocs, VLocs); 2778 EXPECT_EQ(Output[0].size(), 0ul); 2779 ASSERT_EQ(Output[1].size(), 1ul); 2780 ASSERT_EQ(Output[2].size(), 1ul); 2781 ASSERT_EQ(Output[3].size(), 1ul); 2782 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 2783 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 2784 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 2785 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 2786 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 2787 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRspID); 2788 ClearOutputs(); 2789 VLocs[0].Vars.clear(); 2790 2791 // Additionally, even if that value isn't available in the register file, it 2792 // should still be propagated, as buildVLocValueMap shouldn't care about 2793 // what's in the registers (except for PHIs). 2794 // values through to all other blocks, as it dominates. 2795 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 2796 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2797 MOutLocs, MInLocs, VLocs); 2798 EXPECT_EQ(Output[0].size(), 0ul); 2799 ASSERT_EQ(Output[1].size(), 1ul); 2800 ASSERT_EQ(Output[2].size(), 1ul); 2801 ASSERT_EQ(Output[3].size(), 1ul); 2802 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 2803 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRaxID); 2804 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 2805 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRaxID); 2806 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 2807 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRaxID); 2808 ClearOutputs(); 2809 VLocs[0].Vars.clear(); 2810 2811 // We should get a live-in to the merging block, if there are two assigns of 2812 // the same value in either side of the diamond. 2813 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2814 VLocs[2].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2815 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2816 MOutLocs, MInLocs, VLocs); 2817 EXPECT_EQ(Output[0].size(), 0ul); 2818 EXPECT_EQ(Output[1].size(), 0ul); 2819 EXPECT_EQ(Output[2].size(), 0ul); 2820 ASSERT_EQ(Output[3].size(), 1ul); 2821 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 2822 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRspID); 2823 ClearOutputs(); 2824 VLocs[1].Vars.clear(); 2825 VLocs[2].Vars.clear(); 2826 2827 // If we assign a value in the entry block, then 'undef' on a branch, we 2828 // shouldn't have a live-in in the merge block. 2829 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2830 VLocs[1].Vars.insert({VarID, DbgValue(EmptyProps, DbgValue::Undef)}); 2831 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2832 MOutLocs, MInLocs, VLocs); 2833 EXPECT_EQ(Output[0].size(), 0ul); 2834 ASSERT_EQ(Output[1].size(), 1ul); 2835 ASSERT_EQ(Output[2].size(), 1ul); 2836 EXPECT_EQ(Output[3].size(), 0ul); 2837 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 2838 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 2839 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 2840 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 2841 ClearOutputs(); 2842 VLocs[0].Vars.clear(); 2843 VLocs[1].Vars.clear(); 2844 2845 // Having different values joining into the merge block should mean we have 2846 // no live-in in that block. Block ones LiveInRax value doesn't appear as a 2847 // live-in anywhere, it's block internal. 2848 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2849 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 2850 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2851 MOutLocs, MInLocs, VLocs); 2852 EXPECT_EQ(Output[0].size(), 0ul); 2853 ASSERT_EQ(Output[1].size(), 1ul); 2854 ASSERT_EQ(Output[2].size(), 1ul); 2855 EXPECT_EQ(Output[3].size(), 0ul); 2856 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 2857 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 2858 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 2859 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 2860 ClearOutputs(); 2861 VLocs[0].Vars.clear(); 2862 VLocs[1].Vars.clear(); 2863 2864 // But on the other hand, if there's a location in the register file where 2865 // those two values can be joined, do so. 2866 MOutLocs[1][0] = LiveInRax; 2867 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2868 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 2869 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2870 MOutLocs, MInLocs, VLocs); 2871 EXPECT_EQ(Output[0].size(), 0ul); 2872 ASSERT_EQ(Output[1].size(), 1ul); 2873 ASSERT_EQ(Output[2].size(), 1ul); 2874 ASSERT_EQ(Output[3].size(), 1ul); 2875 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 2876 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 2877 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 2878 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 2879 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 2880 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), RspPHIInBlk3ID); 2881 ClearOutputs(); 2882 VLocs[0].Vars.clear(); 2883 VLocs[1].Vars.clear(); 2884 } 2885 2886 TEST_F(InstrRefLDVTest, VLocSimpleLoop) { 2887 setupSimpleLoop(); 2888 // entry 2889 // | 2890 // |/-----\ 2891 // loopblk | 2892 // |\-----/ 2893 // | 2894 // ret 2895 2896 ASSERT_TRUE(MTracker->getNumLocs() == 1); 2897 LocIdx RspLoc(0); 2898 Register RAX = getRegByName("RAX"); 2899 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 2900 2901 unsigned EntryBlk = 0, LoopBlk = 1; 2902 2903 ValueIDNum LiveInRsp = ValueIDNum(EntryBlk, 0, RspLoc); 2904 ValueIDNum LiveInRax = ValueIDNum(EntryBlk, 0, RaxLoc); 2905 ValueIDNum RspPHIInBlk1 = ValueIDNum(LoopBlk, 0, RspLoc); 2906 ValueIDNum RspDefInBlk1 = ValueIDNum(LoopBlk, 1, RspLoc); 2907 ValueIDNum RaxPHIInBlk1 = ValueIDNum(LoopBlk, 0, RaxLoc); 2908 DbgOpID LiveInRspID = addValueDbgOp(LiveInRsp); 2909 DbgOpID LiveInRaxID = addValueDbgOp(LiveInRax); 2910 DbgOpID RspPHIInBlk1ID = addValueDbgOp(RspPHIInBlk1); 2911 DbgOpID RspDefInBlk1ID = addValueDbgOp(RspDefInBlk1); 2912 DbgOpID RaxPHIInBlk1ID = addValueDbgOp(RaxPHIInBlk1); 2913 2914 auto [MInLocs, MOutLocs] = allocValueTables(3, 2); 2915 2916 initValueArray(MInLocs, 3, 2); 2917 initValueArray(MOutLocs, 3, 2); 2918 2919 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 2920 DebugVariableID VarID = LDV->getDVMap().insertDVID(Var, OutermostLoc); 2921 DbgValueProperties EmptyProps(EmptyExpr, false, false); 2922 DIExpression *TwoOpExpr = 2923 DIExpression::get(Ctx, {dwarf::DW_OP_LLVM_arg, 0, dwarf::DW_OP_LLVM_arg, 2924 1, dwarf::DW_OP_plus}); 2925 DbgValueProperties VariadicProps(TwoOpExpr, false, true); 2926 2927 SmallSet<DebugVariableID, 4> AllVars; 2928 AllVars.insert(VarID); 2929 2930 SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks; 2931 AssignBlocks.insert(MBB0); 2932 AssignBlocks.insert(MBB1); 2933 AssignBlocks.insert(MBB2); 2934 2935 SmallVector<VLocTracker, 3> VLocs; 2936 VLocs.resize(3, VLocTracker(LDV->getDVMap(), Overlaps, EmptyExpr)); 2937 2938 InstrRefBasedLDV::LiveInsT Output; 2939 2940 // Start off with LiveInRsp in every location. 2941 for (unsigned int I = 0; I < 3; ++I) { 2942 MInLocs[I][0] = MInLocs[I][1] = LiveInRsp; 2943 MOutLocs[I][0] = MOutLocs[I][1] = LiveInRsp; 2944 } 2945 2946 auto ClearOutputs = [&]() { 2947 for (auto &Elem : Output) 2948 Elem.clear(); 2949 }; 2950 Output.resize(3); 2951 2952 // Easy starter: a dominating assign should propagate to all blocks. 2953 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2954 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2955 MOutLocs, MInLocs, VLocs); 2956 EXPECT_EQ(Output[0].size(), 0ul); 2957 ASSERT_EQ(Output[1].size(), 1ul); 2958 ASSERT_EQ(Output[2].size(), 1ul); 2959 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 2960 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 2961 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 2962 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 2963 ClearOutputs(); 2964 VLocs[0].Vars.clear(); 2965 VLocs[1].Vars.clear(); 2966 2967 // A variadic assignment should behave the same. 2968 DbgOpID Locs0[] = {LiveInRspID, LiveInRaxID}; 2969 VLocs[0].Vars.insert({VarID, DbgValue(Locs0, VariadicProps)}); 2970 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, MOutLocs, 2971 MInLocs, VLocs); 2972 EXPECT_EQ(Output[0].size(), 0ul); 2973 ASSERT_EQ(Output[1].size(), 1ul); 2974 ASSERT_EQ(Output[2].size(), 1ul); 2975 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 2976 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 2977 EXPECT_EQ(Output[1][0].second.getDbgOpID(1), LiveInRaxID); 2978 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 2979 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 2980 ClearOutputs(); 2981 VLocs[0].Vars.clear(); 2982 VLocs[1].Vars.clear(); 2983 2984 // Put an undef assignment in the loop. Should get no live-in value. 2985 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2986 VLocs[1].Vars.insert({VarID, DbgValue(EmptyProps, DbgValue::Undef)}); 2987 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 2988 MOutLocs, MInLocs, VLocs); 2989 EXPECT_EQ(Output[0].size(), 0ul); 2990 EXPECT_EQ(Output[1].size(), 0ul); 2991 EXPECT_EQ(Output[2].size(), 0ul); 2992 ClearOutputs(); 2993 VLocs[0].Vars.clear(); 2994 VLocs[1].Vars.clear(); 2995 2996 // Assignment of the same value should naturally join. 2997 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2998 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 2999 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3000 MOutLocs, MInLocs, VLocs); 3001 EXPECT_EQ(Output[0].size(), 0ul); 3002 ASSERT_EQ(Output[1].size(), 1ul); 3003 ASSERT_EQ(Output[2].size(), 1ul); 3004 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3005 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 3006 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3007 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 3008 ClearOutputs(); 3009 VLocs[0].Vars.clear(); 3010 VLocs[1].Vars.clear(); 3011 3012 // Assignment of different values shouldn't join with no machine PHI vals. 3013 // Will be live-in to exit block as it's dominated. 3014 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3015 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 3016 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3017 MOutLocs, MInLocs, VLocs); 3018 EXPECT_EQ(Output[0].size(), 0ul); 3019 EXPECT_EQ(Output[1].size(), 0ul); 3020 ASSERT_EQ(Output[2].size(), 1ul); 3021 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3022 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRaxID); 3023 ClearOutputs(); 3024 VLocs[0].Vars.clear(); 3025 VLocs[1].Vars.clear(); 3026 3027 // Install a completely unrelated PHI value, that we should not join on. Try 3028 // with unrelated assign in loop block again. 3029 MInLocs[1][0] = RspPHIInBlk1; 3030 MOutLocs[1][0] = RspDefInBlk1; 3031 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3032 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 3033 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3034 MOutLocs, MInLocs, VLocs); 3035 EXPECT_EQ(Output[0].size(), 0ul); 3036 EXPECT_EQ(Output[1].size(), 0ul); 3037 ASSERT_EQ(Output[2].size(), 1ul); 3038 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3039 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRaxID); 3040 ClearOutputs(); 3041 VLocs[0].Vars.clear(); 3042 VLocs[1].Vars.clear(); 3043 3044 // Now, if we assign RspDefInBlk1 in the loop block, we should be able to 3045 // find the appropriate PHI. 3046 MInLocs[1][0] = RspPHIInBlk1; 3047 MOutLocs[1][0] = RspDefInBlk1; 3048 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3049 VLocs[1].Vars.insert({VarID, DbgValue(RspDefInBlk1ID, EmptyProps)}); 3050 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3051 MOutLocs, MInLocs, VLocs); 3052 EXPECT_EQ(Output[0].size(), 0ul); 3053 ASSERT_EQ(Output[1].size(), 1ul); 3054 ASSERT_EQ(Output[2].size(), 1ul); 3055 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3056 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), RspPHIInBlk1ID); 3057 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3058 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), RspDefInBlk1ID); 3059 ClearOutputs(); 3060 VLocs[0].Vars.clear(); 3061 VLocs[1].Vars.clear(); 3062 3063 // If the PHI happens in a different location, the live-in should happen 3064 // there. 3065 MInLocs[1][0] = LiveInRsp; 3066 MOutLocs[1][0] = LiveInRsp; 3067 MInLocs[1][1] = RaxPHIInBlk1; 3068 MOutLocs[1][1] = RspDefInBlk1; 3069 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3070 VLocs[1].Vars.insert({VarID, DbgValue(RspDefInBlk1ID, EmptyProps)}); 3071 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3072 MOutLocs, MInLocs, VLocs); 3073 EXPECT_EQ(Output[0].size(), 0ul); 3074 ASSERT_EQ(Output[1].size(), 1ul); 3075 ASSERT_EQ(Output[2].size(), 1ul); 3076 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3077 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), RaxPHIInBlk1ID); 3078 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3079 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), RspDefInBlk1ID); 3080 ClearOutputs(); 3081 VLocs[0].Vars.clear(); 3082 VLocs[1].Vars.clear(); 3083 3084 // The PHI happening in both places should be handled too. Exactly where 3085 // isn't important, but if the location picked changes, this test will let 3086 // you know. 3087 MInLocs[1][0] = RaxPHIInBlk1; 3088 MOutLocs[1][0] = RspDefInBlk1; 3089 MInLocs[1][1] = RaxPHIInBlk1; 3090 MOutLocs[1][1] = RspDefInBlk1; 3091 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3092 VLocs[1].Vars.insert({VarID, DbgValue(RspDefInBlk1ID, EmptyProps)}); 3093 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3094 MOutLocs, MInLocs, VLocs); 3095 EXPECT_EQ(Output[0].size(), 0ul); 3096 ASSERT_EQ(Output[1].size(), 1ul); 3097 ASSERT_EQ(Output[2].size(), 1ul); 3098 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3099 // Today, the first register is picked. 3100 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), RspPHIInBlk1ID); 3101 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3102 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), RspDefInBlk1ID); 3103 ClearOutputs(); 3104 VLocs[0].Vars.clear(); 3105 VLocs[1].Vars.clear(); 3106 3107 // If the loop block looked a bit like this: 3108 // %0 = PHI %1, %2 3109 // [...] 3110 // DBG_VALUE %0 3111 // Then with instr-ref it becomes: 3112 // DBG_PHI %0 3113 // [...] 3114 // DBG_INSTR_REF 3115 // And we would be feeding a machine PHI-value back around the loop. However: 3116 // this does not mean we can eliminate the variable value PHI and use the 3117 // variable value from the entry block: they are distinct values that must be 3118 // joined at some location by the control flow. 3119 // [This test input would never occur naturally, the machine-PHI would be 3120 // eliminated] 3121 MInLocs[1][0] = RspPHIInBlk1; 3122 MOutLocs[1][0] = RspPHIInBlk1; 3123 MInLocs[1][1] = LiveInRax; 3124 MOutLocs[1][1] = LiveInRax; 3125 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3126 VLocs[1].Vars.insert({VarID, DbgValue(RspPHIInBlk1ID, EmptyProps)}); 3127 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3128 MOutLocs, MInLocs, VLocs); 3129 EXPECT_EQ(Output[0].size(), 0ul); 3130 ASSERT_EQ(Output[1].size(), 1ul); 3131 ASSERT_EQ(Output[2].size(), 1ul); 3132 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3133 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), RspPHIInBlk1ID); 3134 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3135 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), RspPHIInBlk1ID); 3136 ClearOutputs(); 3137 VLocs[0].Vars.clear(); 3138 VLocs[1].Vars.clear(); 3139 3140 // Test that we can eliminate PHIs. A PHI will be placed at the loop head 3141 // because there's a def in it. 3142 MInLocs[1][0] = LiveInRsp; 3143 MOutLocs[1][0] = LiveInRsp; 3144 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3145 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3146 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3147 MOutLocs, MInLocs, VLocs); 3148 EXPECT_EQ(Output[0].size(), 0ul); 3149 ASSERT_EQ(Output[1].size(), 1ul); 3150 ASSERT_EQ(Output[2].size(), 1ul); 3151 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3152 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 3153 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3154 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 3155 ClearOutputs(); 3156 VLocs[0].Vars.clear(); 3157 VLocs[1].Vars.clear(); 3158 } 3159 3160 // test phi elimination with the nested situation 3161 TEST_F(InstrRefLDVTest, VLocNestedLoop) { 3162 // entry 3163 // | 3164 // loop1 3165 // ^\ 3166 // | \ /-\ 3167 // | loop2 | 3168 // | / \-/ 3169 // ^ / 3170 // join 3171 // | 3172 // ret 3173 setupNestedLoops(); 3174 3175 ASSERT_TRUE(MTracker->getNumLocs() == 1); 3176 LocIdx RspLoc(0); 3177 Register RAX = getRegByName("RAX"); 3178 LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX); 3179 3180 unsigned EntryBlk = 0, Loop1Blk = 1, Loop2Blk = 2; 3181 3182 ValueIDNum LiveInRsp = ValueIDNum(EntryBlk, 0, RspLoc); 3183 ValueIDNum LiveInRax = ValueIDNum(EntryBlk, 0, RaxLoc); 3184 ValueIDNum RspPHIInBlk1 = ValueIDNum(Loop1Blk, 0, RspLoc); 3185 ValueIDNum RspPHIInBlk2 = ValueIDNum(Loop2Blk, 0, RspLoc); 3186 ValueIDNum RspDefInBlk2 = ValueIDNum(Loop2Blk, 1, RspLoc); 3187 DbgOpID LiveInRspID = addValueDbgOp(LiveInRsp); 3188 DbgOpID LiveInRaxID = addValueDbgOp(LiveInRax); 3189 DbgOpID RspPHIInBlk1ID = addValueDbgOp(RspPHIInBlk1); 3190 DbgOpID RspPHIInBlk2ID = addValueDbgOp(RspPHIInBlk2); 3191 DbgOpID RspDefInBlk2ID = addValueDbgOp(RspDefInBlk2); 3192 3193 auto [MInLocs, MOutLocs] = allocValueTables(5, 2); 3194 3195 initValueArray(MInLocs, 5, 2); 3196 initValueArray(MOutLocs, 5, 2); 3197 3198 DebugVariable Var(FuncVariable, std::nullopt, nullptr); 3199 DebugVariableID VarID = LDV->getDVMap().insertDVID(Var, OutermostLoc); 3200 DbgValueProperties EmptyProps(EmptyExpr, false, false); 3201 3202 SmallSet<DebugVariableID, 4> AllVars; 3203 AllVars.insert(VarID); 3204 3205 SmallPtrSet<MachineBasicBlock *, 5> AssignBlocks; 3206 AssignBlocks.insert(MBB0); 3207 AssignBlocks.insert(MBB1); 3208 AssignBlocks.insert(MBB2); 3209 AssignBlocks.insert(MBB3); 3210 AssignBlocks.insert(MBB4); 3211 3212 SmallVector<VLocTracker, 5> VLocs; 3213 VLocs.resize(5, VLocTracker(LDV->getDVMap(), Overlaps, EmptyExpr)); 3214 3215 InstrRefBasedLDV::LiveInsT Output; 3216 3217 // Start off with LiveInRsp in every location. 3218 for (unsigned int I = 0; I < 5; ++I) { 3219 MInLocs[I][0] = MInLocs[I][1] = LiveInRsp; 3220 MOutLocs[I][0] = MOutLocs[I][1] = LiveInRsp; 3221 } 3222 3223 auto ClearOutputs = [&]() { 3224 for (auto &Elem : Output) 3225 Elem.clear(); 3226 }; 3227 Output.resize(5); 3228 3229 // A dominating assign should propagate to all blocks. 3230 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3231 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3232 MOutLocs, MInLocs, VLocs); 3233 EXPECT_EQ(Output[0].size(), 0ul); 3234 ASSERT_EQ(Output[1].size(), 1ul); 3235 ASSERT_EQ(Output[2].size(), 1ul); 3236 ASSERT_EQ(Output[3].size(), 1ul); 3237 ASSERT_EQ(Output[4].size(), 1ul); 3238 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3239 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 3240 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3241 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 3242 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 3243 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRspID); 3244 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3245 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), LiveInRspID); 3246 ClearOutputs(); 3247 VLocs[0].Vars.clear(); 3248 3249 // Test that an assign in the inner loop causes unresolved PHIs at the heads 3250 // of both loops, and no output location. Dominated blocks do get values. 3251 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3252 VLocs[2].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 3253 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3254 MOutLocs, MInLocs, VLocs); 3255 EXPECT_EQ(Output[0].size(), 0ul); 3256 EXPECT_EQ(Output[1].size(), 0ul); 3257 EXPECT_EQ(Output[2].size(), 0ul); 3258 ASSERT_EQ(Output[3].size(), 1ul); 3259 ASSERT_EQ(Output[4].size(), 1ul); 3260 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 3261 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRaxID); 3262 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3263 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), LiveInRaxID); 3264 ClearOutputs(); 3265 VLocs[0].Vars.clear(); 3266 VLocs[2].Vars.clear(); 3267 3268 // Same test, but with no assignment in block 0. We should still get values 3269 // in dominated blocks. 3270 VLocs[2].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 3271 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3272 MOutLocs, MInLocs, VLocs); 3273 EXPECT_EQ(Output[0].size(), 0ul); 3274 EXPECT_EQ(Output[1].size(), 0ul); 3275 EXPECT_EQ(Output[2].size(), 0ul); 3276 ASSERT_EQ(Output[3].size(), 1ul); 3277 ASSERT_EQ(Output[4].size(), 1ul); 3278 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 3279 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRaxID); 3280 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3281 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), LiveInRaxID); 3282 ClearOutputs(); 3283 VLocs[2].Vars.clear(); 3284 3285 // Similarly, assignments in the outer loop gives location to dominated 3286 // blocks, but no PHI locations are found at the outer loop head. 3287 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3288 VLocs[3].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 3289 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3290 MOutLocs, MInLocs, VLocs); 3291 EXPECT_EQ(Output[0].size(), 0ul); 3292 EXPECT_EQ(Output[1].size(), 0ul); 3293 EXPECT_EQ(Output[2].size(), 0ul); 3294 EXPECT_EQ(Output[3].size(), 0ul); 3295 ASSERT_EQ(Output[4].size(), 1ul); 3296 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3297 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), LiveInRaxID); 3298 ClearOutputs(); 3299 VLocs[0].Vars.clear(); 3300 VLocs[3].Vars.clear(); 3301 3302 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3303 VLocs[1].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 3304 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3305 MOutLocs, MInLocs, VLocs); 3306 EXPECT_EQ(Output[0].size(), 0ul); 3307 EXPECT_EQ(Output[1].size(), 0ul); 3308 ASSERT_EQ(Output[2].size(), 1ul); 3309 ASSERT_EQ(Output[3].size(), 1ul); 3310 ASSERT_EQ(Output[4].size(), 1ul); 3311 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3312 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRaxID); 3313 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 3314 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRaxID); 3315 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3316 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), LiveInRaxID); 3317 ClearOutputs(); 3318 VLocs[0].Vars.clear(); 3319 VLocs[1].Vars.clear(); 3320 3321 // With an assignment of the same value in the inner loop, we should work out 3322 // that all PHIs can be eliminated and the same value is live-through the 3323 // whole function. 3324 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3325 VLocs[2].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3326 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3327 MOutLocs, MInLocs, VLocs); 3328 EXPECT_EQ(Output[0].size(), 0ul); 3329 EXPECT_EQ(Output[1].size(), 1ul); 3330 EXPECT_EQ(Output[2].size(), 1ul); 3331 ASSERT_EQ(Output[3].size(), 1ul); 3332 ASSERT_EQ(Output[4].size(), 1ul); 3333 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3334 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), LiveInRspID); 3335 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3336 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), LiveInRspID); 3337 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 3338 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRspID); 3339 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3340 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), LiveInRspID); 3341 ClearOutputs(); 3342 VLocs[0].Vars.clear(); 3343 VLocs[2].Vars.clear(); 3344 3345 // If we have an assignment in the inner loop, and a PHI for it at the inner 3346 // loop head, we could find a live-in location for the inner loop. But because 3347 // the outer loop has no PHI, we can't find a variable value for outer loop 3348 // head, so can't have a live-in value for the inner loop head. 3349 MInLocs[2][0] = RspPHIInBlk2; 3350 MOutLocs[2][0] = LiveInRax; 3351 // NB: all other machine locations are LiveInRsp, disallowing a PHI in block 3352 // one. Even though RspPHIInBlk2 isn't available later in the function, we 3353 // should still produce a live-in value. The fact it's unavailable is a 3354 // different concern. 3355 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3356 VLocs[2].Vars.insert({VarID, DbgValue(LiveInRaxID, EmptyProps)}); 3357 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3358 MOutLocs, MInLocs, VLocs); 3359 EXPECT_EQ(Output[0].size(), 0ul); 3360 EXPECT_EQ(Output[1].size(), 0ul); 3361 EXPECT_EQ(Output[2].size(), 0ul); 3362 ASSERT_EQ(Output[3].size(), 1ul); 3363 ASSERT_EQ(Output[4].size(), 1ul); 3364 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 3365 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), LiveInRaxID); 3366 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3367 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), LiveInRaxID); 3368 ClearOutputs(); 3369 VLocs[0].Vars.clear(); 3370 VLocs[2].Vars.clear(); 3371 3372 // Have an assignment in inner loop that can have a PHI resolved; and add a 3373 // machine value PHI to the outer loop head, so that we can find a location 3374 // all the way through the function. 3375 MInLocs[1][0] = RspPHIInBlk1; 3376 MOutLocs[1][0] = RspPHIInBlk1; 3377 MInLocs[2][0] = RspPHIInBlk2; 3378 MOutLocs[2][0] = RspDefInBlk2; 3379 MInLocs[3][0] = RspDefInBlk2; 3380 MOutLocs[3][0] = RspDefInBlk2; 3381 VLocs[0].Vars.insert({VarID, DbgValue(LiveInRspID, EmptyProps)}); 3382 VLocs[2].Vars.insert({VarID, DbgValue(RspDefInBlk2ID, EmptyProps)}); 3383 buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output, 3384 MOutLocs, MInLocs, VLocs); 3385 EXPECT_EQ(Output[0].size(), 0ul); 3386 ASSERT_EQ(Output[1].size(), 1ul); 3387 ASSERT_EQ(Output[2].size(), 1ul); 3388 ASSERT_EQ(Output[3].size(), 1ul); 3389 ASSERT_EQ(Output[4].size(), 1ul); 3390 EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def); 3391 EXPECT_EQ(Output[1][0].second.getDbgOpID(0), RspPHIInBlk1ID); 3392 EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def); 3393 EXPECT_EQ(Output[2][0].second.getDbgOpID(0), RspPHIInBlk2ID); 3394 EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def); 3395 EXPECT_EQ(Output[3][0].second.getDbgOpID(0), RspDefInBlk2ID); 3396 EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def); 3397 EXPECT_EQ(Output[4][0].second.getDbgOpID(0), RspDefInBlk2ID); 3398 ClearOutputs(); 3399 VLocs[0].Vars.clear(); 3400 VLocs[2].Vars.clear(); 3401 } 3402