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