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