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