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