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