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