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