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