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