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