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