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 
47   DebugLoc OutermostLoc, InBlockLoc, NotNestedBlockLoc, InlinedLoc;
48 
49   MachineBasicBlock *MBB1, *MBB2, *MBB3, *MBB4, *MBB5;
50 
51   std::unique_ptr<InstrRefBasedLDV> LDV;
52   std::unique_ptr<MLocTracker> MTracker;
53 
54   InstrRefLDVTest() : Ctx(), Mod("beehives", Ctx) {
55   }
56 
57   void SetUp() {
58     // Boilerplate that creates a MachineFunction and associated blocks.
59 
60     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");
61     Triple TargetTriple("x86_64--");
62     std::string Error;
63     const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
64     if (!T)
65       GTEST_SKIP();
66 
67     TargetOptions Options;
68     Machine = std::unique_ptr<TargetMachine>(T->createTargetMachine(
69         "X86", "", "", Options, None, None, CodeGenOpt::Aggressive));
70 
71     auto Type = FunctionType::get(Type::getVoidTy(Ctx), false);
72     auto F = Function::Create(Type, GlobalValue::ExternalLinkage, "Test", &Mod);
73 
74     unsigned FunctionNum = 42;
75     MachineModuleInfo MMI((LLVMTargetMachine*)&*Machine);
76     const TargetSubtargetInfo &STI = *Machine->getSubtargetImpl(*F);
77 
78     MF = std::make_unique<MachineFunction>(*F, (LLVMTargetMachine&)*Machine, STI, FunctionNum, MMI);
79 
80     // Create metadata: CU, subprogram, some blocks and an inline function
81     // scope.
82     DIBuilder DIB(Mod);
83     OurFile = DIB.createFile("xyzzy.c", "/cave");
84     OurCU =
85         DIB.createCompileUnit(dwarf::DW_LANG_C99, OurFile, "nou", false, "", 0);
86     auto OurSubT = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
87     OurFunc =
88         DIB.createFunction(OurCU, "bees", "", OurFile, 1, OurSubT, 1,
89                            DINode::FlagZero, DISubprogram::SPFlagDefinition);
90     F->setSubprogram(OurFunc);
91     OurBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 3);
92     AnotherBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 6);
93     ToInlineFunc =
94         DIB.createFunction(OurFile, "shoes", "", OurFile, 10, OurSubT, 10,
95                            DINode::FlagZero, DISubprogram::SPFlagDefinition);
96 
97     // Make some nested scopes.
98     OutermostLoc = DILocation::get(Ctx, 3, 1, OurFunc);
99     InBlockLoc = DILocation::get(Ctx, 4, 1, OurBlock);
100     InlinedLoc = DILocation::get(Ctx, 10, 1, ToInlineFunc, InBlockLoc.get());
101 
102     // Make a scope that isn't nested within the others.
103     NotNestedBlockLoc = DILocation::get(Ctx, 4, 1, AnotherBlock);
104 
105     DIB.finalize();
106   }
107 
108   Register getRegByName(const char *WantedName) {
109     auto *TRI = MF->getRegInfo().getTargetRegisterInfo();
110     // Slow, but works.
111     for (unsigned int I = 1; I < TRI->getNumRegs(); ++I) {
112       const char *Name = TRI->getName(I);
113       if (strcmp(WantedName, Name) == 0)
114         return I;
115     }
116 
117     // If this ever fails, something is very wrong with this unit test.
118     llvm_unreachable("Can't find register by name");
119   }
120 
121   InstrRefBasedLDV *setupLDVObj() {
122     // Create a new LDV object, and plug some relevant object ptrs into it.
123     LDV = std::make_unique<InstrRefBasedLDV>();
124     const TargetSubtargetInfo &STI = MF->getSubtarget();
125     LDV->TII = STI.getInstrInfo();
126     LDV->TRI = STI.getRegisterInfo();
127     LDV->TFI = STI.getFrameLowering();
128     LDV->MFI = &MF->getFrameInfo();
129 
130     DomTree = std::make_unique<MachineDominatorTree>(*MF);
131     LDV->DomTree = &*DomTree;
132 
133     // Future work: unit tests for mtracker / vtracker / ttracker.
134 
135     // Setup things like the artifical block map, and BlockNo <=> RPO Order
136     // mappings.
137     LDV->initialSetup(*MF);
138     addMTracker();
139     return &*LDV;
140   }
141 
142   void addMTracker() {
143     ASSERT_TRUE(LDV);
144     // Add a machine-location-tracking object to LDV. Don't initialize any
145     // register locations within it though.
146     const TargetSubtargetInfo &STI = MF->getSubtarget();
147     MTracker = std::make_unique<MLocTracker>(
148           *MF, *LDV->TII, *LDV->TRI, *STI.getTargetLowering());
149     LDV->MTracker = &*MTracker;
150   }
151 
152   // Some routines for bouncing into LDV,
153   void buildMLocValueMap(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
154                          SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
155     LDV->buildMLocValueMap(*MF, MInLocs, MOutLocs, MLocTransfer);
156   }
157 
158   void initValueArray(ValueIDNum **Nums, unsigned Blks, unsigned Locs) {
159     for (unsigned int I = 0; I < Blks; ++I)
160       for (unsigned int J = 0; J < Locs; ++J)
161         Nums[I][J] = ValueIDNum::EmptyValue;
162   }
163 };
164 
165 TEST_F(InstrRefLDVTest, MLocSingleBlock) {
166   // Test some very simple properties about interpreting the transfer function.
167 
168   // Add an entry block with nothing but 'ret void' in it.
169   Function &F = const_cast<llvm::Function &>(MF->getFunction());
170   auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
171   IRBuilder<> IRB(BB1);
172   IRB.CreateRetVoid();
173   MBB1 = MF->CreateMachineBasicBlock(BB1);
174   MF->insert(MF->end(), MBB1);
175   MF->RenumberBlocks();
176 
177   setupLDVObj();
178   // We should start with a single location, the stack pointer.
179   ASSERT_TRUE(MTracker->getNumLocs() == 1);
180   LocIdx RspLoc(0);
181 
182   // Set up live-in and live-out tables for this function: two locations (we
183   // add one later) in a single block.
184   ValueIDNum InLocs[2], OutLocs[2];
185   ValueIDNum *InLocsPtr[1] = {&InLocs[0]};
186   ValueIDNum *OutLocsPtr[1] = {&OutLocs[0]};
187 
188   // Transfer function: nothing.
189   SmallVector<MLocTransferMap, 1> TransferFunc = {{}};
190 
191   // Try and build value maps...
192   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
193 
194   // The result should be that RSP is marked as a live-in-PHI -- this represents
195   // an argument. And as there's no transfer function, the block live-out should
196   // be the same.
197   EXPECT_EQ(InLocs[0], ValueIDNum(0, 0, RspLoc));
198   EXPECT_EQ(OutLocs[0], ValueIDNum(0, 0, RspLoc));
199 
200   // Try again, this time initialising the in-locs to be defined by an
201   // instruction. The entry block should always be re-assigned to be the
202   // arguments.
203   initValueArray(InLocsPtr, 1, 2);
204   initValueArray(OutLocsPtr, 1, 2);
205   InLocs[0] = ValueIDNum(0, 1, RspLoc);
206   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
207   EXPECT_EQ(InLocs[0], ValueIDNum(0, 0, RspLoc));
208   EXPECT_EQ(OutLocs[0], ValueIDNum(0, 0, RspLoc));
209 
210   // Now insert something into the transfer function to assign to the single
211   // machine location.
212   TransferFunc[0].insert({RspLoc, ValueIDNum(0, 1, RspLoc)});
213   initValueArray(InLocsPtr, 1, 2);
214   initValueArray(OutLocsPtr, 1, 2);
215   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
216   EXPECT_EQ(InLocs[0], ValueIDNum(0, 0, RspLoc));
217   EXPECT_EQ(OutLocs[0], ValueIDNum(0, 1, RspLoc));
218   TransferFunc[0].clear();
219 
220   // Add a new register to be tracked, and insert it into the transfer function
221   // as a copy. The output of $rax should be the live-in value of $rsp.
222   Register RAX = getRegByName("RAX");
223   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
224   TransferFunc[0].insert({RspLoc, ValueIDNum(0, 1, RspLoc)});
225   TransferFunc[0].insert({RaxLoc, ValueIDNum(0, 0, RspLoc)});
226   initValueArray(InLocsPtr, 1, 2);
227   initValueArray(OutLocsPtr, 1, 2);
228   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
229   EXPECT_EQ(InLocs[0], ValueIDNum(0, 0, RspLoc));
230   EXPECT_EQ(InLocs[1], ValueIDNum(0, 0, RaxLoc));
231   EXPECT_EQ(OutLocs[0], ValueIDNum(0, 1, RspLoc));
232   EXPECT_EQ(OutLocs[1], ValueIDNum(0, 0, RspLoc)); // Rax contains RspLoc.
233   TransferFunc[0].clear();
234 }
235 
236 TEST_F(InstrRefLDVTest, MLocDiamondBlocks) {
237   // Test that information flows from the entry block to two successors.
238 
239   //        entry
240   //        /  \
241   //      br1  br2
242   //        \  /
243   //         ret
244   llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
245   auto *BB1 = BasicBlock::Create(Ctx, "a", &F);
246   auto *BB2 = BasicBlock::Create(Ctx, "b", &F);
247   auto *BB3 = BasicBlock::Create(Ctx, "c", &F);
248   auto *BB4 = BasicBlock::Create(Ctx, "d", &F);
249   IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4);
250   IRB1.CreateBr(BB2);
251   IRB2.CreateBr(BB3);
252   IRB3.CreateBr(BB4);
253   IRB4.CreateRetVoid();
254   MBB1 = MF->CreateMachineBasicBlock(BB1);
255   MF->insert(MF->end(), MBB1);
256   MBB2 = MF->CreateMachineBasicBlock(BB2);
257   MF->insert(MF->end(), MBB2);
258   MBB3 = MF->CreateMachineBasicBlock(BB3);
259   MF->insert(MF->end(), MBB3);
260   MBB4 = MF->CreateMachineBasicBlock(BB4);
261   MF->insert(MF->end(), MBB4);
262   MBB1->addSuccessor(MBB2);
263   MBB1->addSuccessor(MBB3);
264   MBB2->addSuccessor(MBB4);
265   MBB3->addSuccessor(MBB4);
266   MF->RenumberBlocks();
267 
268   setupLDVObj();
269 
270   ASSERT_TRUE(MTracker->getNumLocs() == 1);
271   LocIdx RspLoc(0);
272   Register RAX = getRegByName("RAX");
273   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
274 
275   ValueIDNum InLocs[4][2], OutLocs[4][2];
276   ValueIDNum *InLocsPtr[4] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3]};
277   ValueIDNum *OutLocsPtr[4] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3]};
278 
279   // Transfer function: start with nothing.
280   SmallVector<MLocTransferMap, 1> TransferFunc;
281   TransferFunc.resize(4);
282 
283   // Name some values.
284   ValueIDNum LiveInRsp(0, 0, RspLoc);
285   ValueIDNum RspDefInBlk0(0, 1, RspLoc);
286   ValueIDNum RspDefInBlk1(1, 1, RspLoc);
287   ValueIDNum RspDefInBlk2(2, 1, RspLoc);
288   ValueIDNum RspPHIInBlk3(3, 0, RspLoc);
289   ValueIDNum RaxLiveInBlk1(1, 0, RaxLoc);
290   ValueIDNum RaxLiveInBlk2(2, 0, RaxLoc);
291 
292   // With no transfer function, the live-in values to the entry block should
293   // propagate to all live-outs and the live-ins to the two successor blocks.
294   // IN ADDITION: this checks that the exit block doesn't get a PHI put in it.
295   initValueArray(InLocsPtr, 4, 2);
296   initValueArray(OutLocsPtr, 4, 2);
297   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
298   EXPECT_EQ(InLocs[0][0], LiveInRsp);
299   EXPECT_EQ(InLocs[1][0], LiveInRsp);
300   EXPECT_EQ(InLocs[2][0], LiveInRsp);
301   EXPECT_EQ(InLocs[3][0], LiveInRsp);
302   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
303   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
304   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
305   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
306   // (Skipped writing out locations for $rax).
307 
308   // Check that a def of $rsp in the entry block will likewise reach all the
309   // successors.
310   TransferFunc[0].insert({RspLoc, RspDefInBlk0});
311   initValueArray(InLocsPtr, 4, 2);
312   initValueArray(OutLocsPtr, 4, 2);
313   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
314   EXPECT_EQ(InLocs[0][0], LiveInRsp);
315   EXPECT_EQ(InLocs[1][0], RspDefInBlk0);
316   EXPECT_EQ(InLocs[2][0], RspDefInBlk0);
317   EXPECT_EQ(InLocs[3][0], RspDefInBlk0);
318   EXPECT_EQ(OutLocs[0][0], RspDefInBlk0);
319   EXPECT_EQ(OutLocs[1][0], RspDefInBlk0);
320   EXPECT_EQ(OutLocs[2][0], RspDefInBlk0);
321   EXPECT_EQ(OutLocs[3][0], RspDefInBlk0);
322   TransferFunc[0].clear();
323 
324   // Def in one branch of the diamond means that we need a PHI in the ret block
325   TransferFunc[0].insert({RspLoc, RspDefInBlk0});
326   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
327   initValueArray(InLocsPtr, 4, 2);
328   initValueArray(OutLocsPtr, 4, 2);
329   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
330   // This value map: like above, where RspDefInBlk0 is propagated through one
331   // branch of the diamond, but is def'ed in the live-outs of the other. The
332   // ret / merging block should have a PHI in its live-ins.
333   EXPECT_EQ(InLocs[0][0], LiveInRsp);
334   EXPECT_EQ(InLocs[1][0], RspDefInBlk0);
335   EXPECT_EQ(InLocs[2][0], RspDefInBlk0);
336   EXPECT_EQ(InLocs[3][0], RspPHIInBlk3);
337   EXPECT_EQ(OutLocs[0][0], RspDefInBlk0);
338   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
339   EXPECT_EQ(OutLocs[2][0], RspDefInBlk0);
340   EXPECT_EQ(OutLocs[3][0], RspPHIInBlk3);
341   TransferFunc[0].clear();
342   TransferFunc[1].clear();
343 
344   // If we have differeing defs in either side of the diamond, we should
345   // continue to produce a PHI,
346   TransferFunc[0].insert({RspLoc, RspDefInBlk0});
347   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
348   TransferFunc[2].insert({RspLoc, RspDefInBlk2});
349   initValueArray(InLocsPtr, 4, 2);
350   initValueArray(OutLocsPtr, 4, 2);
351   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
352   EXPECT_EQ(InLocs[0][0], LiveInRsp);
353   EXPECT_EQ(InLocs[1][0], RspDefInBlk0);
354   EXPECT_EQ(InLocs[2][0], RspDefInBlk0);
355   EXPECT_EQ(InLocs[3][0], RspPHIInBlk3);
356   EXPECT_EQ(OutLocs[0][0], RspDefInBlk0);
357   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
358   EXPECT_EQ(OutLocs[2][0], RspDefInBlk2);
359   EXPECT_EQ(OutLocs[3][0], RspPHIInBlk3);
360   TransferFunc[0].clear();
361   TransferFunc[1].clear();
362   TransferFunc[2].clear();
363 
364   // If we have defs of the same value on either side of the branch, a PHI will
365   // initially be created, however value propagation should then eliminate it.
366   // Encode this by copying the live-in value to $rax, and copying it to $rsp
367   // from $rax in each branch of the diamond. We don't allow the definition of
368   // arbitary values in transfer functions.
369   TransferFunc[0].insert({RspLoc, RspDefInBlk0});
370   TransferFunc[0].insert({RaxLoc, LiveInRsp});
371   TransferFunc[1].insert({RspLoc, RaxLiveInBlk1});
372   TransferFunc[2].insert({RspLoc, RaxLiveInBlk2});
373   initValueArray(InLocsPtr, 4, 2);
374   initValueArray(OutLocsPtr, 4, 2);
375   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
376   EXPECT_EQ(InLocs[0][0], LiveInRsp);
377   EXPECT_EQ(InLocs[1][0], RspDefInBlk0);
378   EXPECT_EQ(InLocs[2][0], RspDefInBlk0);
379   EXPECT_EQ(InLocs[3][0], LiveInRsp);
380   EXPECT_EQ(OutLocs[0][0], RspDefInBlk0);
381   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
382   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
383   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
384   TransferFunc[0].clear();
385   TransferFunc[1].clear();
386   TransferFunc[2].clear();
387 }
388 
389 TEST_F(InstrRefLDVTest, MLocSimpleLoop) {
390   //    entry
391   //     |
392   //     |/-----\
393   //    loopblk |
394   //     |\-----/
395   //     |
396   //     ret
397   llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
398   auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
399   auto *BB2 = BasicBlock::Create(Ctx, "loop", &F);
400   auto *BB3 = BasicBlock::Create(Ctx, "ret", &F);
401   IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3);
402   IRB1.CreateBr(BB2);
403   IRB2.CreateBr(BB3);
404   IRB3.CreateRetVoid();
405   MBB1 = MF->CreateMachineBasicBlock(BB1);
406   MF->insert(MF->end(), MBB1);
407   MBB2 = MF->CreateMachineBasicBlock(BB2);
408   MF->insert(MF->end(), MBB2);
409   MBB3 = MF->CreateMachineBasicBlock(BB3);
410   MF->insert(MF->end(), MBB3);
411   MBB1->addSuccessor(MBB2);
412   MBB2->addSuccessor(MBB3);
413   MBB2->addSuccessor(MBB2);
414   MF->RenumberBlocks();
415 
416   setupLDVObj();
417 
418   ASSERT_TRUE(MTracker->getNumLocs() == 1);
419   LocIdx RspLoc(0);
420   Register RAX = getRegByName("RAX");
421   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
422 
423   ValueIDNum InLocs[3][2], OutLocs[3][2];
424   ValueIDNum *InLocsPtr[3] = {InLocs[0], InLocs[1], InLocs[2]};
425   ValueIDNum *OutLocsPtr[3] = {OutLocs[0], OutLocs[1], OutLocs[2]};
426 
427   SmallVector<MLocTransferMap, 1> TransferFunc;
428   TransferFunc.resize(3);
429 
430   // Name some values.
431   ValueIDNum LiveInRsp(0, 0, RspLoc);
432   ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
433   ValueIDNum RspDefInBlk1(1, 1, RspLoc);
434   ValueIDNum LiveInRax(0, 0, RaxLoc);
435   ValueIDNum RaxPHIInBlk1(1, 0, RaxLoc);
436   ValueIDNum RaxPHIInBlk2(2, 0, RaxLoc);
437 
438   // Begin test with all locations being live-through.
439   initValueArray(InLocsPtr, 3, 2);
440   initValueArray(OutLocsPtr, 3, 2);
441   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
442   EXPECT_EQ(InLocs[0][0], LiveInRsp);
443   EXPECT_EQ(InLocs[1][0], LiveInRsp);
444   EXPECT_EQ(InLocs[2][0], LiveInRsp);
445   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
446   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
447   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
448 
449   // Add a def of $rsp to the loop block: it should be in the live-outs, but
450   // should cause a PHI to be placed in the live-ins. Test the transfer function
451   // by copying that PHI into $rax in the loop, then back to $rsp in the ret
452   // block.
453   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
454   TransferFunc[1].insert({RaxLoc, RspPHIInBlk1});
455   TransferFunc[2].insert({RspLoc, RaxPHIInBlk2});
456   initValueArray(InLocsPtr, 3, 2);
457   initValueArray(OutLocsPtr, 3, 2);
458   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
459   EXPECT_EQ(InLocs[0][0], LiveInRsp);
460   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
461   EXPECT_EQ(InLocs[2][0], RspDefInBlk1);
462   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
463   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
464   EXPECT_EQ(OutLocs[2][0], RspPHIInBlk1);
465   // Check rax as well,
466   EXPECT_EQ(InLocs[0][1], LiveInRax);
467   EXPECT_EQ(InLocs[1][1], RaxPHIInBlk1);
468   EXPECT_EQ(InLocs[2][1], RspPHIInBlk1);
469   EXPECT_EQ(OutLocs[0][1], LiveInRax);
470   EXPECT_EQ(OutLocs[1][1], RspPHIInBlk1);
471   EXPECT_EQ(OutLocs[2][1], RspPHIInBlk1);
472   TransferFunc[1].clear();
473   TransferFunc[2].clear();
474 
475   // As with the diamond case, a PHI will be created if there's a (implicit)
476   // def in the entry block and loop block; but should be value propagated away
477   // if it copies in the same value. Copy live-in $rsp to $rax, then copy it
478   // into $rsp in the loop. Encoded as copying the live-in $rax value in block 1
479   // to $rsp.
480   TransferFunc[0].insert({RaxLoc, LiveInRsp});
481   TransferFunc[1].insert({RspLoc, RaxPHIInBlk1});
482   initValueArray(InLocsPtr, 3, 2);
483   initValueArray(OutLocsPtr, 3, 2);
484   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
485   EXPECT_EQ(InLocs[0][0], LiveInRsp);
486   EXPECT_EQ(InLocs[1][0], LiveInRsp);
487   EXPECT_EQ(InLocs[2][0], LiveInRsp);
488   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
489   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
490   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
491   // Check $rax's values.
492   EXPECT_EQ(InLocs[0][1], LiveInRax);
493   EXPECT_EQ(InLocs[1][1], LiveInRsp);
494   EXPECT_EQ(InLocs[2][1], LiveInRsp);
495   EXPECT_EQ(OutLocs[0][1], LiveInRsp);
496   EXPECT_EQ(OutLocs[1][1], LiveInRsp);
497   EXPECT_EQ(OutLocs[2][1], LiveInRsp);
498   TransferFunc[0].clear();
499   TransferFunc[1].clear();
500 }
501 
502 TEST_F(InstrRefLDVTest, MLocNestedLoop) {
503   //    entry
504   //     |
505   //    loop1
506   //     ^\
507   //     | \    /-\
508   //     |  loop2  |
509   //     |  /   \-/
510   //     ^ /
511   //     join
512   //     |
513   //     ret
514   llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
515   auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
516   auto *BB2 = BasicBlock::Create(Ctx, "loop1", &F);
517   auto *BB3 = BasicBlock::Create(Ctx, "loop2", &F);
518   auto *BB4 = BasicBlock::Create(Ctx, "join", &F);
519   auto *BB5 = BasicBlock::Create(Ctx, "ret", &F);
520   IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4), IRB5(BB5);
521   IRB1.CreateBr(BB2);
522   IRB2.CreateBr(BB3);
523   IRB3.CreateBr(BB4);
524   IRB4.CreateBr(BB5);
525   IRB5.CreateRetVoid();
526   MBB1 = MF->CreateMachineBasicBlock(BB1);
527   MF->insert(MF->end(), MBB1);
528   MBB2 = MF->CreateMachineBasicBlock(BB2);
529   MF->insert(MF->end(), MBB2);
530   MBB3 = MF->CreateMachineBasicBlock(BB3);
531   MF->insert(MF->end(), MBB3);
532   MBB4 = MF->CreateMachineBasicBlock(BB4);
533   MF->insert(MF->end(), MBB4);
534   MBB5 = MF->CreateMachineBasicBlock(BB5);
535   MF->insert(MF->end(), MBB5);
536   MBB1->addSuccessor(MBB2);
537   MBB2->addSuccessor(MBB3);
538   MBB3->addSuccessor(MBB3);
539   MBB3->addSuccessor(MBB4);
540   MBB4->addSuccessor(MBB2);
541   MBB4->addSuccessor(MBB5);
542   MF->RenumberBlocks();
543 
544   setupLDVObj();
545 
546   ASSERT_TRUE(MTracker->getNumLocs() == 1);
547   LocIdx RspLoc(0);
548   Register RAX = getRegByName("RAX");
549   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
550 
551   ValueIDNum InLocs[5][2], OutLocs[5][2];
552   ValueIDNum *InLocsPtr[5] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3],
553                               InLocs[4]};
554   ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3],
555                                OutLocs[4]};
556 
557   SmallVector<MLocTransferMap, 1> TransferFunc;
558   TransferFunc.resize(5);
559 
560   ValueIDNum LiveInRsp(0, 0, RspLoc);
561   ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
562   ValueIDNum RspDefInBlk1(1, 1, RspLoc);
563   ValueIDNum RspPHIInBlk2(2, 0, RspLoc);
564   ValueIDNum RspDefInBlk2(2, 1, RspLoc);
565   ValueIDNum RspDefInBlk3(3, 1, RspLoc);
566   ValueIDNum LiveInRax(0, 0, RaxLoc);
567   ValueIDNum RaxPHIInBlk1(1, 0, RaxLoc);
568   ValueIDNum RaxPHIInBlk2(2, 0, RaxLoc);
569 
570   // Like the other tests: first ensure that if there's nothing in the transfer
571   // function, then everything is live-through (check $rsp).
572   initValueArray(InLocsPtr, 5, 2);
573   initValueArray(OutLocsPtr, 5, 2);
574   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
575   EXPECT_EQ(InLocs[0][0], LiveInRsp);
576   EXPECT_EQ(InLocs[1][0], LiveInRsp);
577   EXPECT_EQ(InLocs[2][0], LiveInRsp);
578   EXPECT_EQ(InLocs[3][0], LiveInRsp);
579   EXPECT_EQ(InLocs[4][0], LiveInRsp);
580   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
581   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
582   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
583   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
584   EXPECT_EQ(OutLocs[4][0], LiveInRsp);
585 
586   // A def in the inner loop means we should get PHIs at the heads of both
587   // loops. Live-outs of the last three blocks will be the def, as it dominates
588   // those.
589   TransferFunc[2].insert({RspLoc, RspDefInBlk2});
590   initValueArray(InLocsPtr, 5, 2);
591   initValueArray(OutLocsPtr, 5, 2);
592   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
593   EXPECT_EQ(InLocs[0][0], LiveInRsp);
594   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
595   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
596   EXPECT_EQ(InLocs[3][0], RspDefInBlk2);
597   EXPECT_EQ(InLocs[4][0], RspDefInBlk2);
598   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
599   EXPECT_EQ(OutLocs[1][0], RspPHIInBlk1);
600   EXPECT_EQ(OutLocs[2][0], RspDefInBlk2);
601   EXPECT_EQ(OutLocs[3][0], RspDefInBlk2);
602   EXPECT_EQ(OutLocs[4][0], RspDefInBlk2);
603   TransferFunc[2].clear();
604 
605   // Adding a def to the outer loop header shouldn't affect this much -- the
606   // live-out of block 1 changes.
607   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
608   TransferFunc[2].insert({RspLoc, RspDefInBlk2});
609   initValueArray(InLocsPtr, 5, 2);
610   initValueArray(OutLocsPtr, 5, 2);
611   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
612   EXPECT_EQ(InLocs[0][0], LiveInRsp);
613   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
614   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
615   EXPECT_EQ(InLocs[3][0], RspDefInBlk2);
616   EXPECT_EQ(InLocs[4][0], RspDefInBlk2);
617   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
618   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
619   EXPECT_EQ(OutLocs[2][0], RspDefInBlk2);
620   EXPECT_EQ(OutLocs[3][0], RspDefInBlk2);
621   EXPECT_EQ(OutLocs[4][0], RspDefInBlk2);
622   TransferFunc[1].clear();
623   TransferFunc[2].clear();
624 
625   // Likewise, putting a def in the outer loop tail shouldn't affect where
626   // the PHIs go, and should propagate into the ret block.
627 
628   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
629   TransferFunc[2].insert({RspLoc, RspDefInBlk2});
630   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
631   initValueArray(InLocsPtr, 5, 2);
632   initValueArray(OutLocsPtr, 5, 2);
633   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
634   EXPECT_EQ(InLocs[0][0], LiveInRsp);
635   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
636   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
637   EXPECT_EQ(InLocs[3][0], RspDefInBlk2);
638   EXPECT_EQ(InLocs[4][0], RspDefInBlk3);
639   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
640   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
641   EXPECT_EQ(OutLocs[2][0], RspDefInBlk2);
642   EXPECT_EQ(OutLocs[3][0], RspDefInBlk3);
643   EXPECT_EQ(OutLocs[4][0], RspDefInBlk3);
644   TransferFunc[1].clear();
645   TransferFunc[2].clear();
646   TransferFunc[3].clear();
647 
648   // However: if we don't def in the inner-loop, then we just have defs in the
649   // head and tail of the outer loop. The inner loop should be live-through.
650   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
651   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
652   initValueArray(InLocsPtr, 5, 2);
653   initValueArray(OutLocsPtr, 5, 2);
654   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
655   EXPECT_EQ(InLocs[0][0], LiveInRsp);
656   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
657   EXPECT_EQ(InLocs[2][0], RspDefInBlk1);
658   EXPECT_EQ(InLocs[3][0], RspDefInBlk1);
659   EXPECT_EQ(InLocs[4][0], RspDefInBlk3);
660   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
661   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
662   EXPECT_EQ(OutLocs[2][0], RspDefInBlk1);
663   EXPECT_EQ(OutLocs[3][0], RspDefInBlk3);
664   EXPECT_EQ(OutLocs[4][0], RspDefInBlk3);
665   TransferFunc[1].clear();
666   TransferFunc[3].clear();
667 
668   // Check that this still works if we copy RspDefInBlk1 to $rax and then
669   // copy it back into $rsp in the inner loop.
670   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
671   TransferFunc[1].insert({RaxLoc, RspDefInBlk1});
672   TransferFunc[2].insert({RspLoc, RaxPHIInBlk2});
673   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
674   initValueArray(InLocsPtr, 5, 2);
675   initValueArray(OutLocsPtr, 5, 2);
676   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
677   EXPECT_EQ(InLocs[0][0], LiveInRsp);
678   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
679   EXPECT_EQ(InLocs[2][0], RspDefInBlk1);
680   EXPECT_EQ(InLocs[3][0], RspDefInBlk1);
681   EXPECT_EQ(InLocs[4][0], RspDefInBlk3);
682   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
683   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
684   EXPECT_EQ(OutLocs[2][0], RspDefInBlk1);
685   EXPECT_EQ(OutLocs[3][0], RspDefInBlk3);
686   EXPECT_EQ(OutLocs[4][0], RspDefInBlk3);
687   // Look at raxes value in the relevant blocks,
688   EXPECT_EQ(InLocs[2][1], RspDefInBlk1);
689   EXPECT_EQ(OutLocs[1][1], RspDefInBlk1);
690   TransferFunc[1].clear();
691   TransferFunc[2].clear();
692   TransferFunc[3].clear();
693 
694   // If we have a single def in the tail of the outer loop, that should produce
695   // a PHI at the loop head, and be live-through the inner loop.
696   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
697   initValueArray(InLocsPtr, 5, 2);
698   initValueArray(OutLocsPtr, 5, 2);
699   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
700   EXPECT_EQ(InLocs[0][0], LiveInRsp);
701   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
702   EXPECT_EQ(InLocs[2][0], RspPHIInBlk1);
703   EXPECT_EQ(InLocs[3][0], RspPHIInBlk1);
704   EXPECT_EQ(InLocs[4][0], RspDefInBlk3);
705   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
706   EXPECT_EQ(OutLocs[1][0], RspPHIInBlk1);
707   EXPECT_EQ(OutLocs[2][0], RspPHIInBlk1);
708   EXPECT_EQ(OutLocs[3][0], RspDefInBlk3);
709   EXPECT_EQ(OutLocs[4][0], RspDefInBlk3);
710   TransferFunc[3].clear();
711 
712   // And if we copy from $rsp to $rax in block 2, it should resolve to the PHI
713   // in block 1, and we should keep that value in rax until the ret block.
714   // There'll be a PHI in block 1 and 2, because we're putting a def in the
715   // inner loop.
716   TransferFunc[2].insert({RaxLoc, RspPHIInBlk2});
717   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
718   initValueArray(InLocsPtr, 5, 2);
719   initValueArray(OutLocsPtr, 5, 2);
720   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
721   // Examining the values of rax,
722   EXPECT_EQ(InLocs[0][1], LiveInRax);
723   EXPECT_EQ(InLocs[1][1], RaxPHIInBlk1);
724   EXPECT_EQ(InLocs[2][1], RaxPHIInBlk2);
725   EXPECT_EQ(InLocs[3][1], RspPHIInBlk1);
726   EXPECT_EQ(InLocs[4][1], RspPHIInBlk1);
727   EXPECT_EQ(OutLocs[0][1], LiveInRax);
728   EXPECT_EQ(OutLocs[1][1], RaxPHIInBlk1);
729   EXPECT_EQ(OutLocs[2][1], RspPHIInBlk1);
730   EXPECT_EQ(OutLocs[3][1], RspPHIInBlk1);
731   EXPECT_EQ(OutLocs[4][1], RspPHIInBlk1);
732   TransferFunc[2].clear();
733   TransferFunc[3].clear();
734 }
735 
736 TEST_F(InstrRefLDVTest, MLocNoDominatingLoop) {
737   //           entry
738   //            / \
739   //           /   \
740   //          /     \
741   //        head1   head2
742   //        ^  \   /   ^
743   //        ^   \ /    ^
744   //        \-joinblk -/
745   //             |
746   //            ret
747   llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
748   auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
749   auto *BB2 = BasicBlock::Create(Ctx, "head1", &F);
750   auto *BB3 = BasicBlock::Create(Ctx, "head2", &F);
751   auto *BB4 = BasicBlock::Create(Ctx, "joinblk", &F);
752   auto *BB5 = BasicBlock::Create(Ctx, "ret", &F);
753   IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4), IRB5(BB5);
754   IRB1.CreateBr(BB2);
755   IRB2.CreateBr(BB3);
756   IRB3.CreateBr(BB4);
757   IRB4.CreateBr(BB5);
758   IRB5.CreateRetVoid();
759   MBB1 = MF->CreateMachineBasicBlock(BB1);
760   MF->insert(MF->end(), MBB1);
761   MBB2 = MF->CreateMachineBasicBlock(BB2);
762   MF->insert(MF->end(), MBB2);
763   MBB3 = MF->CreateMachineBasicBlock(BB3);
764   MF->insert(MF->end(), MBB3);
765   MBB4 = MF->CreateMachineBasicBlock(BB4);
766   MF->insert(MF->end(), MBB4);
767   MBB5 = MF->CreateMachineBasicBlock(BB5);
768   MF->insert(MF->end(), MBB5);
769   MBB1->addSuccessor(MBB2);
770   MBB1->addSuccessor(MBB3);
771   MBB2->addSuccessor(MBB4);
772   MBB3->addSuccessor(MBB4);
773   MBB4->addSuccessor(MBB2);
774   MBB4->addSuccessor(MBB3);
775   MBB4->addSuccessor(MBB5);
776   MF->RenumberBlocks();
777 
778   setupLDVObj();
779 
780   ASSERT_TRUE(MTracker->getNumLocs() == 1);
781   LocIdx RspLoc(0);
782   Register RAX = getRegByName("RAX");
783   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
784 
785   ValueIDNum InLocs[5][2], OutLocs[5][2];
786   ValueIDNum *InLocsPtr[5] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3],
787                               InLocs[4]};
788   ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3],
789                                OutLocs[4]};
790 
791   SmallVector<MLocTransferMap, 1> TransferFunc;
792   TransferFunc.resize(5);
793 
794   ValueIDNum LiveInRsp(0, 0, RspLoc);
795   ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
796   ValueIDNum RspDefInBlk1(1, 1, RspLoc);
797   ValueIDNum RspPHIInBlk2(2, 0, RspLoc);
798   ValueIDNum RspDefInBlk2(2, 1, RspLoc);
799   ValueIDNum RspPHIInBlk3(3, 0, RspLoc);
800   ValueIDNum RspDefInBlk3(3, 1, RspLoc);
801   ValueIDNum RaxPHIInBlk1(1, 0, RaxLoc);
802   ValueIDNum RaxPHIInBlk2(2, 0, RaxLoc);
803 
804   // As ever, test that everything is live-through if there are no defs.
805   initValueArray(InLocsPtr, 5, 2);
806   initValueArray(OutLocsPtr, 5, 2);
807   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
808   EXPECT_EQ(InLocs[0][0], LiveInRsp);
809   EXPECT_EQ(InLocs[1][0], LiveInRsp);
810   EXPECT_EQ(InLocs[2][0], LiveInRsp);
811   EXPECT_EQ(InLocs[3][0], LiveInRsp);
812   EXPECT_EQ(InLocs[4][0], LiveInRsp);
813   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
814   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
815   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
816   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
817   EXPECT_EQ(OutLocs[4][0], LiveInRsp);
818 
819   // Putting a def in the 'join' block will cause us to have two distinct
820   // PHIs in each loop head, then on entry to the join block.
821   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
822   initValueArray(InLocsPtr, 5, 2);
823   initValueArray(OutLocsPtr, 5, 2);
824   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
825   EXPECT_EQ(InLocs[0][0], LiveInRsp);
826   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
827   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
828   EXPECT_EQ(InLocs[3][0], RspPHIInBlk3);
829   EXPECT_EQ(InLocs[4][0], RspDefInBlk3);
830   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
831   EXPECT_EQ(OutLocs[1][0], RspPHIInBlk1);
832   EXPECT_EQ(OutLocs[2][0], RspPHIInBlk2);
833   EXPECT_EQ(OutLocs[3][0], RspDefInBlk3);
834   EXPECT_EQ(OutLocs[4][0], RspDefInBlk3);
835   TransferFunc[3].clear();
836 
837   // We should get the same behaviour if we put the def in either of the
838   // loop heads -- it should force the other head to be a PHI.
839   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
840   initValueArray(InLocsPtr, 5, 2);
841   initValueArray(OutLocsPtr, 5, 2);
842   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
843   EXPECT_EQ(InLocs[0][0], LiveInRsp);
844   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
845   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
846   EXPECT_EQ(InLocs[3][0], RspPHIInBlk3);
847   EXPECT_EQ(InLocs[4][0], RspPHIInBlk3);
848   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
849   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
850   EXPECT_EQ(OutLocs[2][0], RspPHIInBlk2);
851   EXPECT_EQ(OutLocs[3][0], RspPHIInBlk3);
852   EXPECT_EQ(OutLocs[4][0], RspPHIInBlk3);
853   TransferFunc[1].clear();
854 
855   // Check symmetry,
856   TransferFunc[2].insert({RspLoc, RspDefInBlk2});
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], RspPHIInBlk2);
863   EXPECT_EQ(InLocs[3][0], RspPHIInBlk3);
864   EXPECT_EQ(InLocs[4][0], RspPHIInBlk3);
865   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
866   EXPECT_EQ(OutLocs[1][0], RspPHIInBlk1);
867   EXPECT_EQ(OutLocs[2][0], RspDefInBlk2);
868   EXPECT_EQ(OutLocs[3][0], RspPHIInBlk3);
869   EXPECT_EQ(OutLocs[4][0], RspPHIInBlk3);
870   TransferFunc[2].clear();
871 
872   // Test some scenarios where there _shouldn't_ be any PHIs created at heads.
873   // These are those PHIs are created, but value propagation eliminates them.
874   // For example, lets copy rsp-livein to $rsp inside each loop head, so that
875   // there's no need for a PHI in the join block. Put a def of $rsp in block 3
876   // to force PHIs elsewhere.
877   TransferFunc[0].insert({RaxLoc, LiveInRsp});
878   TransferFunc[1].insert({RspLoc, RaxPHIInBlk1});
879   TransferFunc[2].insert({RspLoc, RaxPHIInBlk2});
880   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
881   initValueArray(InLocsPtr, 5, 2);
882   initValueArray(OutLocsPtr, 5, 2);
883   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
884   EXPECT_EQ(InLocs[0][0], LiveInRsp);
885   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
886   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
887   EXPECT_EQ(InLocs[3][0], LiveInRsp);
888   EXPECT_EQ(InLocs[4][0], RspDefInBlk3);
889   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
890   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
891   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
892   EXPECT_EQ(OutLocs[3][0], RspDefInBlk3);
893   EXPECT_EQ(OutLocs[4][0], RspDefInBlk3);
894   TransferFunc[0].clear();
895   TransferFunc[1].clear();
896   TransferFunc[2].clear();
897   TransferFunc[3].clear();
898 
899   // In fact, if we eliminate the def in block 3, none of those PHIs are
900   // necessary, as we're just repeatedly copying LiveInRsp into $rsp. They
901   // should all be value propagated out.
902   TransferFunc[0].insert({RaxLoc, LiveInRsp});
903   TransferFunc[1].insert({RspLoc, RaxPHIInBlk1});
904   TransferFunc[2].insert({RspLoc, RaxPHIInBlk2});
905   initValueArray(InLocsPtr, 5, 2);
906   initValueArray(OutLocsPtr, 5, 2);
907   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
908   EXPECT_EQ(InLocs[0][0], LiveInRsp);
909   EXPECT_EQ(InLocs[1][0], LiveInRsp);
910   EXPECT_EQ(InLocs[2][0], LiveInRsp);
911   EXPECT_EQ(InLocs[3][0], LiveInRsp);
912   EXPECT_EQ(InLocs[4][0], LiveInRsp);
913   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
914   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
915   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
916   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
917   EXPECT_EQ(OutLocs[4][0], LiveInRsp);
918   TransferFunc[0].clear();
919   TransferFunc[1].clear();
920   TransferFunc[2].clear();
921 }
922 
923 TEST_F(InstrRefLDVTest, MLocBadlyNestedLoops) {
924   //           entry
925   //             |
926   //           loop1 -o
927   //             | ^
928   //             | ^
929   //           loop2 -o
930   //             | ^
931   //             | ^
932   //           loop3 -o
933   //             |
934   //            ret
935   //
936   // NB: the loop blocks self-loop, which is a bit too fiddly to draw on
937   // accurately.
938   llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
939   auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
940   auto *BB2 = BasicBlock::Create(Ctx, "loop1", &F);
941   auto *BB3 = BasicBlock::Create(Ctx, "loop2", &F);
942   auto *BB4 = BasicBlock::Create(Ctx, "loop3", &F);
943   auto *BB5 = BasicBlock::Create(Ctx, "ret", &F);
944   IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4), IRB5(BB5);
945   IRB1.CreateBr(BB2);
946   IRB2.CreateBr(BB3);
947   IRB3.CreateBr(BB4);
948   IRB4.CreateBr(BB5);
949   IRB5.CreateRetVoid();
950   MBB1 = MF->CreateMachineBasicBlock(BB1);
951   MF->insert(MF->end(), MBB1);
952   MBB2 = MF->CreateMachineBasicBlock(BB2);
953   MF->insert(MF->end(), MBB2);
954   MBB3 = MF->CreateMachineBasicBlock(BB3);
955   MF->insert(MF->end(), MBB3);
956   MBB4 = MF->CreateMachineBasicBlock(BB4);
957   MF->insert(MF->end(), MBB4);
958   MBB5 = MF->CreateMachineBasicBlock(BB5);
959   MF->insert(MF->end(), MBB5);
960   MBB1->addSuccessor(MBB2);
961   MBB2->addSuccessor(MBB2);
962   MBB2->addSuccessor(MBB3);
963   MBB3->addSuccessor(MBB2);
964   MBB3->addSuccessor(MBB3);
965   MBB3->addSuccessor(MBB4);
966   MBB4->addSuccessor(MBB3);
967   MBB4->addSuccessor(MBB4);
968   MBB4->addSuccessor(MBB5);
969   MF->RenumberBlocks();
970 
971   setupLDVObj();
972 
973   ASSERT_TRUE(MTracker->getNumLocs() == 1);
974   LocIdx RspLoc(0);
975   Register RAX = getRegByName("RAX");
976   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
977 
978   ValueIDNum InLocs[5][2], OutLocs[5][2];
979   ValueIDNum *InLocsPtr[5] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3],
980                               InLocs[4]};
981   ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3],
982                                OutLocs[4]};
983 
984   SmallVector<MLocTransferMap, 1> TransferFunc;
985   TransferFunc.resize(5);
986 
987   ValueIDNum LiveInRsp(0, 0, RspLoc);
988   ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
989   ValueIDNum RspDefInBlk1(1, 1, RspLoc);
990   ValueIDNum RspPHIInBlk2(2, 0, RspLoc);
991   ValueIDNum RspPHIInBlk3(3, 0, RspLoc);
992   ValueIDNum RspDefInBlk3(3, 1, RspLoc);
993   ValueIDNum LiveInRax(0, 0, RaxLoc);
994   ValueIDNum RaxPHIInBlk3(3, 0, RaxLoc);
995 
996   // As ever, test that everything is live-through if there are no defs.
997   initValueArray(InLocsPtr, 5, 2);
998   initValueArray(OutLocsPtr, 5, 2);
999   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
1000   EXPECT_EQ(InLocs[0][0], LiveInRsp);
1001   EXPECT_EQ(InLocs[1][0], LiveInRsp);
1002   EXPECT_EQ(InLocs[2][0], LiveInRsp);
1003   EXPECT_EQ(InLocs[3][0], LiveInRsp);
1004   EXPECT_EQ(InLocs[4][0], LiveInRsp);
1005   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
1006   EXPECT_EQ(OutLocs[1][0], LiveInRsp);
1007   EXPECT_EQ(OutLocs[2][0], LiveInRsp);
1008   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
1009   EXPECT_EQ(OutLocs[4][0], LiveInRsp);
1010 
1011   // A def in loop3 should cause PHIs in every loop block: they're all
1012   // reachable from each other.
1013   TransferFunc[3].insert({RspLoc, RspDefInBlk3});
1014   initValueArray(InLocsPtr, 5, 2);
1015   initValueArray(OutLocsPtr, 5, 2);
1016   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
1017   EXPECT_EQ(InLocs[0][0], LiveInRsp);
1018   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
1019   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
1020   EXPECT_EQ(InLocs[3][0], RspPHIInBlk3);
1021   EXPECT_EQ(InLocs[4][0], RspDefInBlk3);
1022   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
1023   EXPECT_EQ(OutLocs[1][0], RspPHIInBlk1);
1024   EXPECT_EQ(OutLocs[2][0], RspPHIInBlk2);
1025   EXPECT_EQ(OutLocs[3][0], RspDefInBlk3);
1026   EXPECT_EQ(OutLocs[4][0], RspDefInBlk3);
1027   TransferFunc[3].clear();
1028 
1029   // A def in loop1 should cause a PHI in loop1, but not the other blocks.
1030   // loop2 and loop3 are dominated by the def in loop1, so they should have
1031   // that value live-through.
1032   TransferFunc[1].insert({RspLoc, RspDefInBlk1});
1033   initValueArray(InLocsPtr, 5, 2);
1034   initValueArray(OutLocsPtr, 5, 2);
1035   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
1036   EXPECT_EQ(InLocs[0][0], LiveInRsp);
1037   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
1038   EXPECT_EQ(InLocs[2][0], RspDefInBlk1);
1039   EXPECT_EQ(InLocs[3][0], RspDefInBlk1);
1040   EXPECT_EQ(InLocs[4][0], RspDefInBlk1);
1041   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
1042   EXPECT_EQ(OutLocs[1][0], RspDefInBlk1);
1043   EXPECT_EQ(OutLocs[2][0], RspDefInBlk1);
1044   EXPECT_EQ(OutLocs[3][0], RspDefInBlk1);
1045   EXPECT_EQ(OutLocs[4][0], RspDefInBlk1);
1046   TransferFunc[1].clear();
1047 
1048   // As with earlier tricks: copy $rsp to $rax in the entry block, then $rax
1049   // to $rsp in block 3. The only def of $rsp is simply copying the same value
1050   // back into itself, and the value of $rsp is LiveInRsp all the way through.
1051   // PHIs should be created, then value-propagated away...  however this
1052   // doesn't work in practice.
1053   // Consider the entry to loop3: we can determine that there's an incoming
1054   // PHI value from loop2, and LiveInRsp from the self-loop. This would still
1055   // justify having a PHI on entry to loop3. The only way to completely
1056   // value-propagate these PHIs away would be to speculatively explore what
1057   // PHIs could be eliminated and what that would lead to; which is
1058   // combinatorially complex.
1059   // Happily:
1060   //  a) In this scenario, we always have a tracked location for LiveInRsp
1061   //     anyway, so there's no loss in availability,
1062   //  b) Only DBG_PHIs of a register would be vunlerable to this scenario, and
1063   //     even then only if a true PHI became a DBG_PHI and was then optimised
1064   //     through branch folding to no longer be at a CFG join,
1065   //  c) The register allocator can spot this kind of redundant COPY easily,
1066   //     and eliminate it.
1067   //
1068   // This unit test left in as a reference for the limitations of this
1069   // approach. PHIs will be left in $rsp on entry to each block.
1070   TransferFunc[0].insert({RaxLoc, LiveInRsp});
1071   TransferFunc[3].insert({RspLoc, RaxPHIInBlk3});
1072   initValueArray(InLocsPtr, 5, 2);
1073   initValueArray(OutLocsPtr, 5, 2);
1074   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
1075   EXPECT_EQ(InLocs[0][0], LiveInRsp);
1076   EXPECT_EQ(InLocs[1][0], RspPHIInBlk1);
1077   EXPECT_EQ(InLocs[2][0], RspPHIInBlk2);
1078   EXPECT_EQ(InLocs[3][0], RspPHIInBlk3);
1079   EXPECT_EQ(InLocs[4][0], LiveInRsp);
1080   EXPECT_EQ(OutLocs[0][0], LiveInRsp);
1081   EXPECT_EQ(OutLocs[1][0], RspPHIInBlk1);
1082   EXPECT_EQ(OutLocs[2][0], RspPHIInBlk2);
1083   EXPECT_EQ(OutLocs[3][0], LiveInRsp);
1084   EXPECT_EQ(OutLocs[4][0], LiveInRsp);
1085   // Check $rax's value. It should have $rsps value from the entry block
1086   // onwards.
1087   EXPECT_EQ(InLocs[0][1], LiveInRax);
1088   EXPECT_EQ(InLocs[1][1], LiveInRsp);
1089   EXPECT_EQ(InLocs[2][1], LiveInRsp);
1090   EXPECT_EQ(InLocs[3][1], LiveInRsp);
1091   EXPECT_EQ(InLocs[4][1], LiveInRsp);
1092   EXPECT_EQ(OutLocs[0][1], LiveInRsp);
1093   EXPECT_EQ(OutLocs[1][1], LiveInRsp);
1094   EXPECT_EQ(OutLocs[2][1], LiveInRsp);
1095   EXPECT_EQ(OutLocs[3][1], LiveInRsp);
1096   EXPECT_EQ(OutLocs[4][1], LiveInRsp);
1097 }
1098