1	//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface ------===//
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	// This file implements the generic RegisterCoalescer interface which
10	// is used as the common interface used by all clients and
11	// implementations of register coalescing.
12	//
13	//===----------------------------------------------------------------------===//
14
15	#include "RegisterCoalescer.h"
16	#include "llvm/ADT/ArrayRef.h"
17	#include "llvm/ADT/BitVector.h"
18	#include "llvm/ADT/DenseSet.h"
19	#include "llvm/ADT/STLExtras.h"
20	#include "llvm/ADT/SmallPtrSet.h"
21	#include "llvm/ADT/SmallVector.h"
22	#include "llvm/ADT/Statistic.h"
23	#include "llvm/Analysis/AliasAnalysis.h"
24	#include "llvm/CodeGen/LiveInterval.h"
25	#include "llvm/CodeGen/LiveIntervals.h"
26	#include "llvm/CodeGen/LiveRangeEdit.h"
27	#include "llvm/CodeGen/MachineBasicBlock.h"
28	#include "llvm/CodeGen/MachineFunction.h"
29	#include "llvm/CodeGen/MachineFunctionPass.h"
30	#include "llvm/CodeGen/MachineInstr.h"
31	#include "llvm/CodeGen/MachineInstrBuilder.h"
32	#include "llvm/CodeGen/MachineLoopInfo.h"
33	#include "llvm/CodeGen/MachineOperand.h"
34	#include "llvm/CodeGen/MachineRegisterInfo.h"
35	#include "llvm/CodeGen/Passes.h"
36	#include "llvm/CodeGen/RegisterClassInfo.h"
37	#include "llvm/CodeGen/SlotIndexes.h"
38	#include "llvm/CodeGen/TargetInstrInfo.h"
39	#include "llvm/CodeGen/TargetOpcodes.h"
40	#include "llvm/CodeGen/TargetRegisterInfo.h"
41	#include "llvm/CodeGen/TargetSubtargetInfo.h"
42	#include "llvm/IR/DebugLoc.h"
43	#include "llvm/InitializePasses.h"
44	#include "llvm/MC/LaneBitmask.h"
45	#include "llvm/MC/MCInstrDesc.h"
46	#include "llvm/MC/MCRegisterInfo.h"
47	#include "llvm/Pass.h"
48	#include "llvm/Support/CommandLine.h"
49	#include "llvm/Support/Compiler.h"
50	#include "llvm/Support/Debug.h"
51	#include "llvm/Support/ErrorHandling.h"
52	#include "llvm/Support/raw_ostream.h"
53	#include <algorithm>
54	#include <cassert>
55	#include <iterator>
56	#include <limits>
57	#include <tuple>
58	#include <utility>
59	#include <vector>
60
61	using namespace llvm;
62
63	#define DEBUG_TYPE "regalloc"
64
65	STATISTIC(numJoins , "Number of interval joins performed");
66	STATISTIC(numCrossRCs , "Number of cross class joins performed");
67	STATISTIC(numCommutes , "Number of instruction commuting performed");
68	STATISTIC(numExtends , "Number of copies extended");
69	STATISTIC(NumReMats , "Number of instructions re-materialized");
70	STATISTIC(NumInflated , "Number of register classes inflated");
71	STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested");
72	STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved");
73	STATISTIC(NumShrinkToUses, "Number of shrinkToUses called");
74
75	static cl::opt<bool> EnableJoining("join-liveintervals",
76	cl::desc("Coalesce copies (default=true)"),
77	cl::init(Val: true), cl::Hidden);
78
79	static cl::opt<bool> UseTerminalRule("terminal-rule",
80	cl::desc("Apply the terminal rule"),
81	cl::init(Val: false), cl::Hidden);
82
83	/// Temporary flag to test critical edge unsplitting.
84	static cl::opt<bool>
85	EnableJoinSplits("join-splitedges",
86	cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden);
87
88	/// Temporary flag to test global copy optimization.
89	static cl::opt<cl::boolOrDefault>
90	EnableGlobalCopies("join-globalcopies",
91	cl::desc("Coalesce copies that span blocks (default=subtarget)"),
92	cl::init(Val: cl::BOU_UNSET), cl::Hidden);
93
94	static cl::opt<bool>
95	VerifyCoalescing("verify-coalescing",
96	cl::desc("Verify machine instrs before and after register coalescing"),
97	cl::Hidden);
98
99	static cl::opt<unsigned> LateRematUpdateThreshold(
100	"late-remat-update-threshold", cl::Hidden,
101	cl::desc("During rematerialization for a copy, if the def instruction has "
102	"many other copy uses to be rematerialized, delay the multiple "
103	"separate live interval update work and do them all at once after "
104	"all those rematerialization are done. It will save a lot of "
105	"repeated work. "),
106	cl::init(Val: 100));
107
108	static cl::opt<unsigned> LargeIntervalSizeThreshold(
109	"large-interval-size-threshold", cl::Hidden,
110	cl::desc("If the valnos size of an interval is larger than the threshold, "
111	"it is regarded as a large interval. "),
112	cl::init(Val: 100));
113
114	static cl::opt<unsigned> LargeIntervalFreqThreshold(
115	"large-interval-freq-threshold", cl::Hidden,
116	cl::desc("For a large interval, if it is coalesed with other live "
117	"intervals many times more than the threshold, stop its "
118	"coalescing to control the compile time. "),
119	cl::init(Val: 256));
120
121	namespace {
122
123	class JoinVals;
124
125	class RegisterCoalescer : public MachineFunctionPass,
126	private LiveRangeEdit::Delegate {
127	MachineFunction* MF = nullptr;
128	MachineRegisterInfo* MRI = nullptr;
129	const TargetRegisterInfo* TRI = nullptr;
130	const TargetInstrInfo* TII = nullptr;
131	LiveIntervals *LIS = nullptr;
132	const MachineLoopInfo* Loops = nullptr;
133	AliasAnalysis *AA = nullptr;
134	RegisterClassInfo RegClassInfo;
135
136	/// Position and VReg of a PHI instruction during coalescing.
137	struct PHIValPos {
138	SlotIndex SI; ///< Slot where this PHI occurs.
139	Register Reg; ///< VReg the PHI occurs in.
140	unsigned SubReg; ///< Qualifying subregister for Reg.
141	};
142
143	/// Map from debug instruction number to PHI position during coalescing.
144	DenseMap<unsigned, PHIValPos> PHIValToPos;
145	/// Index of, for each VReg, which debug instruction numbers and
146	/// corresponding PHIs are sensitive to coalescing. Each VReg may have
147	/// multiple PHI defs, at different positions.
148	DenseMap<Register, SmallVector<unsigned, 2>> RegToPHIIdx;
149
150	/// Debug variable location tracking -- for each VReg, maintain an
151	/// ordered-by-slot-index set of DBG_VALUEs, to help quick
152	/// identification of whether coalescing may change location validity.
153	using DbgValueLoc = std::pair<SlotIndex, MachineInstr*>;
154	DenseMap<Register, std::vector<DbgValueLoc>> DbgVRegToValues;
155
156	/// A LaneMask to remember on which subregister live ranges we need to call
157	/// shrinkToUses() later.
158	LaneBitmask ShrinkMask;
159
160	/// True if the main range of the currently coalesced intervals should be
161	/// checked for smaller live intervals.
162	bool ShrinkMainRange = false;
163
164	/// True if the coalescer should aggressively coalesce global copies
165	/// in favor of keeping local copies.
166	bool JoinGlobalCopies = false;
167
168	/// True if the coalescer should aggressively coalesce fall-thru
169	/// blocks exclusively containing copies.
170	bool JoinSplitEdges = false;
171
172	/// Copy instructions yet to be coalesced.
173	SmallVector<MachineInstr*, 8> WorkList;
174	SmallVector<MachineInstr*, 8> LocalWorkList;
175
176	/// Set of instruction pointers that have been erased, and
177	/// that may be present in WorkList.
178	SmallPtrSet<MachineInstr*, 8> ErasedInstrs;
179
180	/// Dead instructions that are about to be deleted.
181	SmallVector<MachineInstr*, 8> DeadDefs;
182
183	/// Virtual registers to be considered for register class inflation.
184	SmallVector<Register, 8> InflateRegs;
185
186	/// The collection of live intervals which should have been updated
187	/// immediately after rematerialiation but delayed until
188	/// lateLiveIntervalUpdate is called.
189	DenseSet<Register> ToBeUpdated;
190
191	/// Record how many times the large live interval with many valnos
192	/// has been tried to join with other live interval.
193	DenseMap<Register, unsigned long> LargeLIVisitCounter;
194
195	/// Recursively eliminate dead defs in DeadDefs.
196	void eliminateDeadDefs(LiveRangeEdit *Edit = nullptr);
197
198	/// LiveRangeEdit callback for eliminateDeadDefs().
199	void LRE_WillEraseInstruction(MachineInstr *MI) override;
200
201	/// Coalesce the LocalWorkList.
202	void coalesceLocals();
203
204	/// Join compatible live intervals
205	void joinAllIntervals();
206
207	/// Coalesce copies in the specified MBB, putting
208	/// copies that cannot yet be coalesced into WorkList.
209	void copyCoalesceInMBB(MachineBasicBlock *MBB);
210
211	/// Tries to coalesce all copies in CurrList. Returns true if any progress
212	/// was made.
213	bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList);
214
215	/// If one def has many copy like uses, and those copy uses are all
216	/// rematerialized, the live interval update needed for those
217	/// rematerializations will be delayed and done all at once instead
218	/// of being done multiple times. This is to save compile cost because
219	/// live interval update is costly.
220	void lateLiveIntervalUpdate();
221
222	/// Check if the incoming value defined by a COPY at \p SLRQ in the subrange
223	/// has no value defined in the predecessors. If the incoming value is the
224	/// same as defined by the copy itself, the value is considered undefined.
225	bool copyValueUndefInPredecessors(LiveRange &S,
226	const MachineBasicBlock *MBB,
227	LiveQueryResult SLRQ);
228
229	/// Set necessary undef flags on subregister uses after pruning out undef
230	/// lane segments from the subrange.
231	void setUndefOnPrunedSubRegUses(LiveInterval &LI, Register Reg,
232	LaneBitmask PrunedLanes);
233
234	/// Attempt to join intervals corresponding to SrcReg/DstReg, which are the
235	/// src/dst of the copy instruction CopyMI. This returns true if the copy
236	/// was successfully coalesced away. If it is not currently possible to
237	/// coalesce this interval, but it may be possible if other things get
238	/// coalesced, then it returns true by reference in 'Again'.
239	bool joinCopy(MachineInstr *CopyMI, bool &Again,
240	SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs);
241
242	/// Attempt to join these two intervals. On failure, this
243	/// returns false. The output "SrcInt" will not have been modified, so we
244	/// can use this information below to update aliases.
245	bool joinIntervals(CoalescerPair &CP);
246
247	/// Attempt joining two virtual registers. Return true on success.
248	bool joinVirtRegs(CoalescerPair &CP);
249
250	/// If a live interval has many valnos and is coalesced with other
251	/// live intervals many times, we regard such live interval as having
252	/// high compile time cost.
253	bool isHighCostLiveInterval(LiveInterval &LI);
254
255	/// Attempt joining with a reserved physreg.
256	bool joinReservedPhysReg(CoalescerPair &CP);
257
258	/// Add the LiveRange @p ToMerge as a subregister liverange of @p LI.
259	/// Subranges in @p LI which only partially interfere with the desired
260	/// LaneMask are split as necessary. @p LaneMask are the lanes that
261	/// @p ToMerge will occupy in the coalescer register. @p LI has its subrange
262	/// lanemasks already adjusted to the coalesced register.
263	void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
264	LaneBitmask LaneMask, CoalescerPair &CP,
265	unsigned DstIdx);
266
267	/// Join the liveranges of two subregisters. Joins @p RRange into
268	/// @p LRange, @p RRange may be invalid afterwards.
269	void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
270	LaneBitmask LaneMask, const CoalescerPair &CP);
271
272	/// We found a non-trivially-coalescable copy. If the source value number is
273	/// defined by a copy from the destination reg see if we can merge these two
274	/// destination reg valno# into a single value number, eliminating a copy.
275	/// This returns true if an interval was modified.
276	bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
277
278	/// Return true if there are definitions of IntB
279	/// other than BValNo val# that can reach uses of AValno val# of IntA.
280	bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,
281	VNInfo *AValNo, VNInfo *BValNo);
282
283	/// We found a non-trivially-coalescable copy.
284	/// If the source value number is defined by a commutable instruction and
285	/// its other operand is coalesced to the copy dest register, see if we
286	/// can transform the copy into a noop by commuting the definition.
287	/// This returns a pair of two flags:
288	/// - the first element is true if an interval was modified,
289	/// - the second element is true if the destination interval needs
290	/// to be shrunk after deleting the copy.
291	std::pair<bool,bool> removeCopyByCommutingDef(const CoalescerPair &CP,
292	MachineInstr *CopyMI);
293
294	/// We found a copy which can be moved to its less frequent predecessor.
295	bool removePartialRedundancy(const CoalescerPair &CP, MachineInstr &CopyMI);
296
297	/// If the source of a copy is defined by a
298	/// trivial computation, replace the copy by rematerialize the definition.
299	bool reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI,
300	bool &IsDefCopy);
301
302	/// Return true if a copy involving a physreg should be joined.
303	bool canJoinPhys(const CoalescerPair &CP);
304
305	/// Replace all defs and uses of SrcReg to DstReg and update the subregister
306	/// number if it is not zero. If DstReg is a physical register and the
307	/// existing subregister number of the def / use being updated is not zero,
308	/// make sure to set it to the correct physical subregister.
309	void updateRegDefsUses(Register SrcReg, Register DstReg, unsigned SubIdx);
310
311	/// If the given machine operand reads only undefined lanes add an undef
312	/// flag.
313	/// This can happen when undef uses were previously concealed by a copy
314	/// which we coalesced. Example:
315	/// %0:sub0<def,read-undef> = ...
316	/// %1 = COPY %0 <-- Coalescing COPY reveals undef
317	/// = use %1:sub1 <-- hidden undef use
318	void addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
319	MachineOperand &MO, unsigned SubRegIdx);
320
321	/// Handle copies of undef values. If the undef value is an incoming
322	/// PHI value, it will convert @p CopyMI to an IMPLICIT_DEF.
323	/// Returns nullptr if @p CopyMI was not in any way eliminable. Otherwise,
324	/// it returns @p CopyMI (which could be an IMPLICIT_DEF at this point).
325	MachineInstr *eliminateUndefCopy(MachineInstr *CopyMI);
326
327	/// Check whether or not we should apply the terminal rule on the
328	/// destination (Dst) of \p Copy.
329	/// When the terminal rule applies, Copy is not profitable to
330	/// coalesce.
331	/// Dst is terminal if it has exactly one affinity (Dst, Src) and
332	/// at least one interference (Dst, Dst2). If Dst is terminal, the
333	/// terminal rule consists in checking that at least one of
334	/// interfering node, say Dst2, has an affinity of equal or greater
335	/// weight with Src.
336	/// In that case, Dst2 and Dst will not be able to be both coalesced
337	/// with Src. Since Dst2 exposes more coalescing opportunities than
338	/// Dst, we can drop \p Copy.
339	bool applyTerminalRule(const MachineInstr &Copy) const;
340
341	/// Wrapper method for \see LiveIntervals::shrinkToUses.
342	/// This method does the proper fixing of the live-ranges when the afore
343	/// mentioned method returns true.
344	void shrinkToUses(LiveInterval *LI,
345	SmallVectorImpl<MachineInstr * > *Dead = nullptr) {
346	NumShrinkToUses++;
347	if (LIS->shrinkToUses(li: LI, dead: Dead)) {
348	/// Check whether or not \p LI is composed by multiple connected
349	/// components and if that is the case, fix that.
350	SmallVector<LiveInterval*, 8> SplitLIs;
351	LIS->splitSeparateComponents(LI&: *LI, SplitLIs);
352	}
353	}
354
355	/// Wrapper Method to do all the necessary work when an Instruction is
356	/// deleted.
357	/// Optimizations should use this to make sure that deleted instructions
358	/// are always accounted for.
359	void deleteInstr(MachineInstr* MI) {
360	ErasedInstrs.insert(Ptr: MI);
361	LIS->RemoveMachineInstrFromMaps(MI&: *MI);
362	MI->eraseFromParent();
363	}
364
365	/// Walk over function and initialize the DbgVRegToValues map.
366	void buildVRegToDbgValueMap(MachineFunction &MF);
367
368	/// Test whether, after merging, any DBG_VALUEs would refer to a
369	/// different value number than before merging, and whether this can
370	/// be resolved. If not, mark the DBG_VALUE as being undef.
371	void checkMergingChangesDbgValues(CoalescerPair &CP, LiveRange &LHS,
372	JoinVals &LHSVals, LiveRange &RHS,
373	JoinVals &RHSVals);
374
375	void checkMergingChangesDbgValuesImpl(Register Reg, LiveRange &OtherRange,
376	LiveRange &RegRange, JoinVals &Vals2);
377
378	public:
379	static char ID; ///< Class identification, replacement for typeinfo
380
381	RegisterCoalescer() : MachineFunctionPass(ID) {
382	initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
383	}
384
385	void getAnalysisUsage(AnalysisUsage &AU) const override;
386
387	MachineFunctionProperties getClearedProperties() const override {
388	return MachineFunctionProperties().set(
389	MachineFunctionProperties::Property::IsSSA);
390	}
391
392	void releaseMemory() override;
393
394	/// This is the pass entry point.
395	bool runOnMachineFunction(MachineFunction&) override;
396
397	/// Implement the dump method.
398	void print(raw_ostream &O, const Module* = nullptr) const override;
399	};
400
401	} // end anonymous namespace
402
403	char RegisterCoalescer::ID = 0;
404
405	char &llvm::RegisterCoalescerID = RegisterCoalescer::ID;
406
407	INITIALIZE_PASS_BEGIN(RegisterCoalescer, "register-coalescer",
408	"Register Coalescer", false, false)
409	INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
410	INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
411	INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
412	INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
413	INITIALIZE_PASS_END(RegisterCoalescer, "register-coalescer",
414	"Register Coalescer", false, false)
415
416	[[nodiscard]] static bool isMoveInstr(const TargetRegisterInfo &tri,
417	const MachineInstr *MI, Register &Src,
418	Register &Dst, unsigned &SrcSub,
419	unsigned &DstSub) {
420	if (MI->isCopy()) {
421	Dst = MI->getOperand(i: 0).getReg();
422	DstSub = MI->getOperand(i: 0).getSubReg();
423	Src = MI->getOperand(i: 1).getReg();
424	SrcSub = MI->getOperand(i: 1).getSubReg();
425	} else if (MI->isSubregToReg()) {
426	Dst = MI->getOperand(i: 0).getReg();
427	DstSub = tri.composeSubRegIndices(a: MI->getOperand(i: 0).getSubReg(),
428	b: MI->getOperand(i: 3).getImm());
429	Src = MI->getOperand(i: 2).getReg();
430	SrcSub = MI->getOperand(i: 2).getSubReg();
431	} else
432	return false;
433	return true;
434	}
435
436	/// Return true if this block should be vacated by the coalescer to eliminate
437	/// branches. The important cases to handle in the coalescer are critical edges
438	/// split during phi elimination which contain only copies. Simple blocks that
439	/// contain non-branches should also be vacated, but this can be handled by an
440	/// earlier pass similar to early if-conversion.
441	static bool isSplitEdge(const MachineBasicBlock *MBB) {
442	if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
443	return false;
444
445	for (const auto &MI : *MBB) {
446	if (!MI.isCopyLike() && !MI.isUnconditionalBranch())
447	return false;
448	}
449	return true;
450	}
451
452	bool CoalescerPair::setRegisters(const MachineInstr *MI) {
453	SrcReg = DstReg = Register();
454	SrcIdx = DstIdx = 0;
455	NewRC = nullptr;
456	Flipped = CrossClass = false;
457
458	Register Src, Dst;
459	unsigned SrcSub = 0, DstSub = 0;
460	if (!isMoveInstr(tri: TRI, MI, Src, Dst, SrcSub, DstSub))
461	return false;
462	Partial = SrcSub || DstSub;
463
464	// If one register is a physreg, it must be Dst.
465	if (Src.isPhysical()) {
466	if (Dst.isPhysical())
467	return false;
468	std::swap(a&: Src, b&: Dst);
469	std::swap(a&: SrcSub, b&: DstSub);
470	Flipped = true;
471	}
472
473	const MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
474
475	if (Dst.isPhysical()) {
476	// Eliminate DstSub on a physreg.
477	if (DstSub) {
478	Dst = TRI.getSubReg(Reg: Dst, Idx: DstSub);
479	if (!Dst) return false;
480	DstSub = 0;
481	}
482
483	// Eliminate SrcSub by picking a corresponding Dst superregister.
484	if (SrcSub) {
485	Dst = TRI.getMatchingSuperReg(Reg: Dst, SubIdx: SrcSub, RC: MRI.getRegClass(Reg: Src));
486	if (!Dst) return false;
487	} else if (!MRI.getRegClass(Reg: Src)->contains(Reg: Dst)) {
488	return false;
489	}
490	} else {
491	// Both registers are virtual.
492	const TargetRegisterClass *SrcRC = MRI.getRegClass(Reg: Src);
493	const TargetRegisterClass *DstRC = MRI.getRegClass(Reg: Dst);
494
495	// Both registers have subreg indices.
496	if (SrcSub && DstSub) {
497	// Copies between different sub-registers are never coalescable.
498	if (Src == Dst && SrcSub != DstSub)
499	return false;
500
501	NewRC = TRI.getCommonSuperRegClass(RCA: SrcRC, SubA: SrcSub, RCB: DstRC, SubB: DstSub,
502	PreA&: SrcIdx, PreB&: DstIdx);
503	if (!NewRC)
504	return false;
505	} else if (DstSub) {
506	// SrcReg will be merged with a sub-register of DstReg.
507	SrcIdx = DstSub;
508	NewRC = TRI.getMatchingSuperRegClass(A: DstRC, B: SrcRC, Idx: DstSub);
509	} else if (SrcSub) {
510	// DstReg will be merged with a sub-register of SrcReg.
511	DstIdx = SrcSub;
512	NewRC = TRI.getMatchingSuperRegClass(A: SrcRC, B: DstRC, Idx: SrcSub);
513	} else {
514	// This is a straight copy without sub-registers.
515	NewRC = TRI.getCommonSubClass(A: DstRC, B: SrcRC);
516	}
517
518	// The combined constraint may be impossible to satisfy.
519	if (!NewRC)
520	return false;
521
522	// Prefer SrcReg to be a sub-register of DstReg.
523	// FIXME: Coalescer should support subregs symmetrically.
524	if (DstIdx && !SrcIdx) {
525	std::swap(a&: Src, b&: Dst);
526	std::swap(a&: SrcIdx, b&: DstIdx);
527	Flipped = !Flipped;
528	}
529
530	CrossClass = NewRC != DstRC || NewRC != SrcRC;
531	}
532	// Check our invariants
533	assert(Src.isVirtual() && "Src must be virtual");
534	assert(!(Dst.isPhysical() && DstSub) && "Cannot have a physical SubIdx");
535	SrcReg = Src;
536	DstReg = Dst;
537	return true;
538	}
539
540	bool CoalescerPair::flip() {
541	if (DstReg.isPhysical())
542	return false;
543	std::swap(a&: SrcReg, b&: DstReg);
544	std::swap(a&: SrcIdx, b&: DstIdx);
545	Flipped = !Flipped;
546	return true;
547	}
548
549	bool CoalescerPair::isCoalescable(const MachineInstr *MI) const {
550	if (!MI)
551	return false;
552	Register Src, Dst;
553	unsigned SrcSub = 0, DstSub = 0;
554	if (!isMoveInstr(tri: TRI, MI, Src, Dst, SrcSub, DstSub))
555	return false;
556
557	// Find the virtual register that is SrcReg.
558	if (Dst == SrcReg) {
559	std::swap(a&: Src, b&: Dst);
560	std::swap(a&: SrcSub, b&: DstSub);
561	} else if (Src != SrcReg) {
562	return false;
563	}
564
565	// Now check that Dst matches DstReg.
566	if (DstReg.isPhysical()) {
567	if (!Dst.isPhysical())
568	return false;
569	assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state.");
570	// DstSub could be set for a physreg from INSERT_SUBREG.
571	if (DstSub)
572	Dst = TRI.getSubReg(Reg: Dst, Idx: DstSub);
573	// Full copy of Src.
574	if (!SrcSub)
575	return DstReg == Dst;
576	// This is a partial register copy. Check that the parts match.
577	return Register(TRI.getSubReg(Reg: DstReg, Idx: SrcSub)) == Dst;
578	} else {
579	// DstReg is virtual.
580	if (DstReg != Dst)
581	return false;
582	// Registers match, do the subregisters line up?
583	return TRI.composeSubRegIndices(a: SrcIdx, b: SrcSub) ==
584	TRI.composeSubRegIndices(a: DstIdx, b: DstSub);
585	}
586	}
587
588	void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const {
589	AU.setPreservesCFG();
590	AU.addRequired<AAResultsWrapperPass>();
591	AU.addRequired<LiveIntervals>();
592	AU.addPreserved<LiveIntervals>();
593	AU.addPreserved<SlotIndexes>();
594	AU.addRequired<MachineLoopInfo>();
595	AU.addPreserved<MachineLoopInfo>();
596	AU.addPreservedID(ID&: MachineDominatorsID);
597	MachineFunctionPass::getAnalysisUsage(AU);
598	}
599
600	void RegisterCoalescer::eliminateDeadDefs(LiveRangeEdit *Edit) {
601	if (Edit) {
602	Edit->eliminateDeadDefs(Dead&: DeadDefs);
603	return;
604	}
605	SmallVector<Register, 8> NewRegs;
606	LiveRangeEdit(nullptr, NewRegs, *MF, *LIS,
607	nullptr, this).eliminateDeadDefs(Dead&: DeadDefs);
608	}
609
610	void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) {
611	// MI may be in WorkList. Make sure we don't visit it.
612	ErasedInstrs.insert(Ptr: MI);
613	}
614
615	bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
616	MachineInstr *CopyMI) {
617	assert(!CP.isPartial() && "This doesn't work for partial copies.");
618	assert(!CP.isPhys() && "This doesn't work for physreg copies.");
619
620	LiveInterval &IntA =
621	LIS->getInterval(Reg: CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
622	LiveInterval &IntB =
623	LIS->getInterval(Reg: CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
624	SlotIndex CopyIdx = LIS->getInstructionIndex(Instr: *CopyMI).getRegSlot();
625
626	// We have a non-trivially-coalescable copy with IntA being the source and
627	// IntB being the dest, thus this defines a value number in IntB. If the
628	// source value number (in IntA) is defined by a copy from B, see if we can
629	// merge these two pieces of B into a single value number, eliminating a copy.
630	// For example:
631	//
632	// A3 = B0
633	// ...
634	// B1 = A3 <- this copy
635	//
636	// In this case, B0 can be extended to where the B1 copy lives, allowing the
637	// B1 value number to be replaced with B0 (which simplifies the B
638	// liveinterval).
639
640	// BValNo is a value number in B that is defined by a copy from A. 'B1' in
641	// the example above.
642	LiveInterval::iterator BS = IntB.FindSegmentContaining(Idx: CopyIdx);
643	if (BS == IntB.end()) return false;
644	VNInfo *BValNo = BS->valno;
645
646	// Get the location that B is defined at. Two options: either this value has
647	// an unknown definition point or it is defined at CopyIdx. If unknown, we
648	// can't process it.
649	if (BValNo->def != CopyIdx) return false;
650
651	// AValNo is the value number in A that defines the copy, A3 in the example.
652	SlotIndex CopyUseIdx = CopyIdx.getRegSlot(EC: true);
653	LiveInterval::iterator AS = IntA.FindSegmentContaining(Idx: CopyUseIdx);
654	// The live segment might not exist after fun with physreg coalescing.
655	if (AS == IntA.end()) return false;
656	VNInfo *AValNo = AS->valno;
657
658	// If AValNo is defined as a copy from IntB, we can potentially process this.
659	// Get the instruction that defines this value number.
660	MachineInstr *ACopyMI = LIS->getInstructionFromIndex(index: AValNo->def);
661	// Don't allow any partial copies, even if isCoalescable() allows them.
662	if (!CP.isCoalescable(MI: ACopyMI) || !ACopyMI->isFullCopy())
663	return false;
664
665	// Get the Segment in IntB that this value number starts with.
666	LiveInterval::iterator ValS =
667	IntB.FindSegmentContaining(Idx: AValNo->def.getPrevSlot());
668	if (ValS == IntB.end())
669	return false;
670
671	// Make sure that the end of the live segment is inside the same block as
672	// CopyMI.
673	MachineInstr *ValSEndInst =
674	LIS->getInstructionFromIndex(index: ValS->end.getPrevSlot());
675	if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent())
676	return false;
677
678	// Okay, we now know that ValS ends in the same block that the CopyMI
679	// live-range starts. If there are no intervening live segments between them
680	// in IntB, we can merge them.
681	if (ValS+1 != BS) return false;
682
683	LLVM_DEBUG(dbgs() << "Extending: " << printReg(IntB.reg(), TRI));
684
685	SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
686	// We are about to delete CopyMI, so need to remove it as the 'instruction
687	// that defines this value #'. Update the valnum with the new defining
688	// instruction #.
689	BValNo->def = FillerStart;
690
691	// Okay, we can merge them. We need to insert a new liverange:
692	// [ValS.end, BS.begin) of either value number, then we merge the
693	// two value numbers.
694	IntB.addSegment(S: LiveInterval::Segment(FillerStart, FillerEnd, BValNo));
695
696	// Okay, merge "B1" into the same value number as "B0".
697	if (BValNo != ValS->valno)
698	IntB.MergeValueNumberInto(V1: BValNo, V2: ValS->valno);
699
700	// Do the same for the subregister segments.
701	for (LiveInterval::SubRange &S : IntB.subranges()) {
702	// Check for SubRange Segments of the form [1234r,1234d:0) which can be
703	// removed to prevent creating bogus SubRange Segments.
704	LiveInterval::iterator SS = S.FindSegmentContaining(Idx: CopyIdx);
705	if (SS != S.end() && SlotIndex::isSameInstr(A: SS->start, B: SS->end)) {
706	S.removeSegment(S: *SS, RemoveDeadValNo: true);
707	continue;
708	}
709	// The subrange may have ended before FillerStart. If so, extend it.
710	if (!S.getVNInfoAt(Idx: FillerStart)) {
711	SlotIndex BBStart =
712	LIS->getMBBStartIdx(mbb: LIS->getMBBFromIndex(index: FillerStart));
713	S.extendInBlock(StartIdx: BBStart, Kill: FillerStart);
714	}
715	VNInfo *SubBValNo = S.getVNInfoAt(Idx: CopyIdx);
716	S.addSegment(S: LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
717	VNInfo *SubValSNo = S.getVNInfoAt(Idx: AValNo->def.getPrevSlot());
718	if (SubBValNo != SubValSNo)
719	S.MergeValueNumberInto(V1: SubBValNo, V2: SubValSNo);
720	}
721
722	LLVM_DEBUG(dbgs() << " result = " << IntB << '\n');
723
724	// If the source instruction was killing the source register before the
725	// merge, unset the isKill marker given the live range has been extended.
726	int UIdx =
727	ValSEndInst->findRegisterUseOperandIdx(Reg: IntB.reg(), /*TRI=*/nullptr, isKill: true);
728	if (UIdx != -1) {
729	ValSEndInst->getOperand(i: UIdx).setIsKill(false);
730	}
731
732	// Rewrite the copy.
733	CopyMI->substituteRegister(FromReg: IntA.reg(), ToReg: IntB.reg(), SubIdx: 0, RegInfo: *TRI);
734	// If the copy instruction was killing the destination register or any
735	// subrange before the merge trim the live range.
736	bool RecomputeLiveRange = AS->end == CopyIdx;
737	if (!RecomputeLiveRange) {
738	for (LiveInterval::SubRange &S : IntA.subranges()) {
739	LiveInterval::iterator SS = S.FindSegmentContaining(Idx: CopyUseIdx);
740	if (SS != S.end() && SS->end == CopyIdx) {
741	RecomputeLiveRange = true;
742	break;
743	}
744	}
745	}
746	if (RecomputeLiveRange)
747	shrinkToUses(LI: &IntA);
748
749	++numExtends;
750	return true;
751	}
752
753	bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA,
754	LiveInterval &IntB,
755	VNInfo *AValNo,
756	VNInfo *BValNo) {
757	// If AValNo has PHI kills, conservatively assume that IntB defs can reach
758	// the PHI values.
759	if (LIS->hasPHIKill(LI: IntA, VNI: AValNo))
760	return true;
761
762	for (LiveRange::Segment &ASeg : IntA.segments) {
763	if (ASeg.valno != AValNo) continue;
764	LiveInterval::iterator BI = llvm::upper_bound(Range&: IntB, Value&: ASeg.start);
765	if (BI != IntB.begin())
766	--BI;
767	for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) {
768	if (BI->valno == BValNo)
769	continue;
770	if (BI->start <= ASeg.start && BI->end > ASeg.start)
771	return true;
772	if (BI->start > ASeg.start && BI->start < ASeg.end)
773	return true;
774	}
775	}
776	return false;
777	}
778
779	/// Copy segments with value number @p SrcValNo from liverange @p Src to live
780	/// range @Dst and use value number @p DstValNo there.
781	static std::pair<bool,bool>
782	addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo, const LiveRange &Src,
783	const VNInfo *SrcValNo) {
784	bool Changed = false;
785	bool MergedWithDead = false;
786	for (const LiveRange::Segment &S : Src.segments) {
787	if (S.valno != SrcValNo)
788	continue;
789	// This is adding a segment from Src that ends in a copy that is about
790	// to be removed. This segment is going to be merged with a pre-existing
791	// segment in Dst. This works, except in cases when the corresponding
792	// segment in Dst is dead. For example: adding [192r,208r:1) from Src
793	// to [208r,208d:1) in Dst would create [192r,208d:1) in Dst.
794	// Recognized such cases, so that the segments can be shrunk.
795	LiveRange::Segment Added = LiveRange::Segment(S.start, S.end, DstValNo);
796	LiveRange::Segment &Merged = *Dst.addSegment(S: Added);
797	if (Merged.end.isDead())
798	MergedWithDead = true;
799	Changed = true;
800	}
801	return std::make_pair(x&: Changed, y&: MergedWithDead);
802	}
803
804	std::pair<bool,bool>
805	RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
806	MachineInstr *CopyMI) {
807	assert(!CP.isPhys());
808
809	LiveInterval &IntA =
810	LIS->getInterval(Reg: CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
811	LiveInterval &IntB =
812	LIS->getInterval(Reg: CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
813
814	// We found a non-trivially-coalescable copy with IntA being the source and
815	// IntB being the dest, thus this defines a value number in IntB. If the
816	// source value number (in IntA) is defined by a commutable instruction and
817	// its other operand is coalesced to the copy dest register, see if we can
818	// transform the copy into a noop by commuting the definition. For example,
819	//
820	// A3 = op A2 killed B0
821	// ...
822	// B1 = A3 <- this copy
823	// ...
824	// = op A3 <- more uses
825	//
826	// ==>
827	//
828	// B2 = op B0 killed A2
829	// ...
830	// B1 = B2 <- now an identity copy
831	// ...
832	// = op B2 <- more uses
833
834	// BValNo is a value number in B that is defined by a copy from A. 'B1' in
835	// the example above.
836	SlotIndex CopyIdx = LIS->getInstructionIndex(Instr: *CopyMI).getRegSlot();
837	VNInfo *BValNo = IntB.getVNInfoAt(Idx: CopyIdx);
838	assert(BValNo != nullptr && BValNo->def == CopyIdx);
839
840	// AValNo is the value number in A that defines the copy, A3 in the example.
841	VNInfo *AValNo = IntA.getVNInfoAt(Idx: CopyIdx.getRegSlot(EC: true));
842	assert(AValNo && !AValNo->isUnused() && "COPY source not live");
843	if (AValNo->isPHIDef())
844	return { false, false };
845	MachineInstr *DefMI = LIS->getInstructionFromIndex(index: AValNo->def);
846	if (!DefMI)
847	return { false, false };
848	if (!DefMI->isCommutable())
849	return { false, false };
850	// If DefMI is a two-address instruction then commuting it will change the
851	// destination register.
852	int DefIdx = DefMI->findRegisterDefOperandIdx(Reg: IntA.reg(), /*TRI=*/nullptr);
853	assert(DefIdx != -1);
854	unsigned UseOpIdx;
855	if (!DefMI->isRegTiedToUseOperand(DefOpIdx: DefIdx, UseOpIdx: &UseOpIdx))
856	return { false, false };
857
858	// FIXME: The code below tries to commute 'UseOpIdx' operand with some other
859	// commutable operand which is expressed by 'CommuteAnyOperandIndex'value
860	// passed to the method. That _other_ operand is chosen by
861	// the findCommutedOpIndices() method.
862	//
863	// That is obviously an area for improvement in case of instructions having
864	// more than 2 operands. For example, if some instruction has 3 commutable
865	// operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3,
866	// op#2<->op#3) of commute transformation should be considered/tried here.
867	unsigned NewDstIdx = TargetInstrInfo::CommuteAnyOperandIndex;
868	if (!TII->findCommutedOpIndices(MI: *DefMI, SrcOpIdx1&: UseOpIdx, SrcOpIdx2&: NewDstIdx))
869	return { false, false };
870
871	MachineOperand &NewDstMO = DefMI->getOperand(i: NewDstIdx);
872	Register NewReg = NewDstMO.getReg();
873	if (NewReg != IntB.reg() || !IntB.Query(Idx: AValNo->def).isKill())
874	return { false, false };
875
876	// Make sure there are no other definitions of IntB that would reach the
877	// uses which the new definition can reach.
878	if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
879	return { false, false };
880
881	// If some of the uses of IntA.reg is already coalesced away, return false.
882	// It's not possible to determine whether it's safe to perform the coalescing.
883	for (MachineOperand &MO : MRI->use_nodbg_operands(Reg: IntA.reg())) {
884	MachineInstr *UseMI = MO.getParent();
885	unsigned OpNo = &MO - &UseMI->getOperand(i: 0);
886	SlotIndex UseIdx = LIS->getInstructionIndex(Instr: *UseMI);
887	LiveInterval::iterator US = IntA.FindSegmentContaining(Idx: UseIdx);
888	if (US == IntA.end() || US->valno != AValNo)
889	continue;
890	// If this use is tied to a def, we can't rewrite the register.
891	if (UseMI->isRegTiedToDefOperand(UseOpIdx: OpNo))
892	return { false, false };
893	}
894
895	LLVM_DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t'
896	<< *DefMI);
897
898	// At this point we have decided that it is legal to do this
899	// transformation. Start by commuting the instruction.
900	MachineBasicBlock *MBB = DefMI->getParent();
901	MachineInstr *NewMI =
902	TII->commuteInstruction(MI&: *DefMI, NewMI: false, OpIdx1: UseOpIdx, OpIdx2: NewDstIdx);
903	if (!NewMI)
904	return { false, false };
905	if (IntA.reg().isVirtual() && IntB.reg().isVirtual() &&
906	!MRI->constrainRegClass(Reg: IntB.reg(), RC: MRI->getRegClass(Reg: IntA.reg())))
907	return { false, false };
908	if (NewMI != DefMI) {
909	LIS->ReplaceMachineInstrInMaps(MI&: *DefMI, NewMI&: *NewMI);
910	MachineBasicBlock::iterator Pos = DefMI;
911	MBB->insert(I: Pos, MI: NewMI);
912	MBB->erase(I: DefMI);
913	}
914
915	// If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
916	// A = or A, B
917	// ...
918	// B = A
919	// ...
920	// C = killed A
921	// ...
922	// = B
923
924	// Update uses of IntA of the specific Val# with IntB.
925	for (MachineOperand &UseMO :
926	llvm::make_early_inc_range(Range: MRI->use_operands(Reg: IntA.reg()))) {
927	if (UseMO.isUndef())
928	continue;
929	MachineInstr *UseMI = UseMO.getParent();
930	if (UseMI->isDebugInstr()) {
931	// FIXME These don't have an instruction index. Not clear we have enough
932	// info to decide whether to do this replacement or not. For now do it.
933	UseMO.setReg(NewReg);
934	continue;
935	}
936	SlotIndex UseIdx = LIS->getInstructionIndex(Instr: *UseMI).getRegSlot(EC: true);
937	LiveInterval::iterator US = IntA.FindSegmentContaining(Idx: UseIdx);
938	assert(US != IntA.end() && "Use must be live");
939	if (US->valno != AValNo)
940	continue;
941	// Kill flags are no longer accurate. They are recomputed after RA.
942	UseMO.setIsKill(false);
943	if (NewReg.isPhysical())
944	UseMO.substPhysReg(Reg: NewReg, *TRI);
945	else
946	UseMO.setReg(NewReg);
947	if (UseMI == CopyMI)
948	continue;
949	if (!UseMI->isCopy())
950	continue;
951	if (UseMI->getOperand(i: 0).getReg() != IntB.reg() ||
952	UseMI->getOperand(i: 0).getSubReg())
953	continue;
954
955	// This copy will become a noop. If it's defining a new val#, merge it into
956	// BValNo.
957	SlotIndex DefIdx = UseIdx.getRegSlot();
958	VNInfo *DVNI = IntB.getVNInfoAt(Idx: DefIdx);
959	if (!DVNI)
960	continue;
961	LLVM_DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI);
962	assert(DVNI->def == DefIdx);
963	BValNo = IntB.MergeValueNumberInto(V1: DVNI, V2: BValNo);
964	for (LiveInterval::SubRange &S : IntB.subranges()) {
965	VNInfo *SubDVNI = S.getVNInfoAt(Idx: DefIdx);
966	if (!SubDVNI)
967	continue;
968	VNInfo *SubBValNo = S.getVNInfoAt(Idx: CopyIdx);
969	assert(SubBValNo->def == CopyIdx);
970	S.MergeValueNumberInto(V1: SubDVNI, V2: SubBValNo);
971	}
972
973	deleteInstr(MI: UseMI);
974	}
975
976	// Extend BValNo by merging in IntA live segments of AValNo. Val# definition
977	// is updated.
978	bool ShrinkB = false;
979	BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
980	if (IntA.hasSubRanges() || IntB.hasSubRanges()) {
981	if (!IntA.hasSubRanges()) {
982	LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(Reg: IntA.reg());
983	IntA.createSubRangeFrom(Allocator, LaneMask: Mask, CopyFrom: IntA);
984	} else if (!IntB.hasSubRanges()) {
985	LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(Reg: IntB.reg());
986	IntB.createSubRangeFrom(Allocator, LaneMask: Mask, CopyFrom: IntB);
987	}
988	SlotIndex AIdx = CopyIdx.getRegSlot(EC: true);
989	LaneBitmask MaskA;
990	const SlotIndexes &Indexes = *LIS->getSlotIndexes();
991	for (LiveInterval::SubRange &SA : IntA.subranges()) {
992	VNInfo *ASubValNo = SA.getVNInfoAt(Idx: AIdx);
993	// Even if we are dealing with a full copy, some lanes can
994	// still be undefined.
995	// E.g.,
996	// undef A.subLow = ...
997	// B = COPY A <== A.subHigh is undefined here and does
998	// not have a value number.
999	if (!ASubValNo)
1000	continue;
1001	MaskA |= SA.LaneMask;
1002
1003	IntB.refineSubRanges(
1004	Allocator, LaneMask: SA.LaneMask,
1005	Apply: [&Allocator, &SA, CopyIdx, ASubValNo,
1006	&ShrinkB](LiveInterval::SubRange &SR) {
1007	VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(Def: CopyIdx, VNInfoAllocator&: Allocator)
1008	: SR.getVNInfoAt(Idx: CopyIdx);
1009	assert(BSubValNo != nullptr);
1010	auto P = addSegmentsWithValNo(Dst&: SR, DstValNo: BSubValNo, Src: SA, SrcValNo: ASubValNo);
1011	ShrinkB |= P.second;
1012	if (P.first)
1013	BSubValNo->def = ASubValNo->def;
1014	},
1015	Indexes, TRI: *TRI);
1016	}
1017	// Go over all subranges of IntB that have not been covered by IntA,
1018	// and delete the segments starting at CopyIdx. This can happen if
1019	// IntA has undef lanes that are defined in IntB.
1020	for (LiveInterval::SubRange &SB : IntB.subranges()) {
1021	if ((SB.LaneMask & MaskA).any())
1022	continue;
1023	if (LiveRange::Segment *S = SB.getSegmentContaining(Idx: CopyIdx))
1024	if (S->start.getBaseIndex() == CopyIdx.getBaseIndex())
1025	SB.removeSegment(S: *S, RemoveDeadValNo: true);
1026	}
1027	}
1028
1029	BValNo->def = AValNo->def;
1030	auto P = addSegmentsWithValNo(Dst&: IntB, DstValNo: BValNo, Src: IntA, SrcValNo: AValNo);
1031	ShrinkB |= P.second;
1032	LLVM_DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
1033
1034	LIS->removeVRegDefAt(LI&: IntA, Pos: AValNo->def);
1035
1036	LLVM_DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n');
1037	++numCommutes;
1038	return { true, ShrinkB };
1039	}
1040
1041	/// For copy B = A in BB2, if A is defined by A = B in BB0 which is a
1042	/// predecessor of BB2, and if B is not redefined on the way from A = B
1043	/// in BB0 to B = A in BB2, B = A in BB2 is partially redundant if the
1044	/// execution goes through the path from BB0 to BB2. We may move B = A
1045	/// to the predecessor without such reversed copy.
1046	/// So we will transform the program from:
1047	/// BB0:
1048	/// A = B; BB1:
1049	/// ... ...
1050	/// / \ /
1051	/// BB2:
1052	/// ...
1053	/// B = A;
1054	///
1055	/// to:
1056	///
1057	/// BB0: BB1:
1058	/// A = B; ...
1059	/// ... B = A;
1060	/// / \ /
1061	/// BB2:
1062	/// ...
1063	///
1064	/// A special case is when BB0 and BB2 are the same BB which is the only
1065	/// BB in a loop:
1066	/// BB1:
1067	/// ...
1068	/// BB0/BB2: ----
1069	/// B = A; |
1070	/// ... |
1071	/// A = B; |
1072	/// |-------
1073	/// |
1074	/// We may hoist B = A from BB0/BB2 to BB1.
1075	///
1076	/// The major preconditions for correctness to remove such partial
1077	/// redundancy include:
1078	/// 1. A in B = A in BB2 is defined by a PHI in BB2, and one operand of
1079	/// the PHI is defined by the reversed copy A = B in BB0.
1080	/// 2. No B is referenced from the start of BB2 to B = A.
1081	/// 3. No B is defined from A = B to the end of BB0.
1082	/// 4. BB1 has only one successor.
1083	///
1084	/// 2 and 4 implicitly ensure B is not live at the end of BB1.
1085	/// 4 guarantees BB2 is hotter than BB1, so we can only move a copy to a
1086	/// colder place, which not only prevent endless loop, but also make sure
1087	/// the movement of copy is beneficial.
1088	bool RegisterCoalescer::removePartialRedundancy(const CoalescerPair &CP,
1089	MachineInstr &CopyMI) {
1090	assert(!CP.isPhys());
1091	if (!CopyMI.isFullCopy())
1092	return false;
1093
1094	MachineBasicBlock &MBB = *CopyMI.getParent();
1095	// If this block is the target of an invoke/inlineasm_br, moving the copy into
1096	// the predecessor is tricker, and we don't handle it.
1097	if (MBB.isEHPad() || MBB.isInlineAsmBrIndirectTarget())
1098	return false;
1099
1100	if (MBB.pred_size() != 2)
1101	return false;
1102
1103	LiveInterval &IntA =
1104	LIS->getInterval(Reg: CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
1105	LiveInterval &IntB =
1106	LIS->getInterval(Reg: CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
1107
1108	// A is defined by PHI at the entry of MBB.
1109	SlotIndex CopyIdx = LIS->getInstructionIndex(Instr: CopyMI).getRegSlot(EC: true);
1110	VNInfo *AValNo = IntA.getVNInfoAt(Idx: CopyIdx);
1111	assert(AValNo && !AValNo->isUnused() && "COPY source not live");
1112	if (!AValNo->isPHIDef())
1113	return false;
1114
1115	// No B is referenced before CopyMI in MBB.
1116	if (IntB.overlaps(Start: LIS->getMBBStartIdx(mbb: &MBB), End: CopyIdx))
1117	return false;
1118
1119	// MBB has two predecessors: one contains A = B so no copy will be inserted
1120	// for it. The other one will have a copy moved from MBB.
1121	bool FoundReverseCopy = false;
1122	MachineBasicBlock *CopyLeftBB = nullptr;
1123	for (MachineBasicBlock *Pred : MBB.predecessors()) {
1124	VNInfo *PVal = IntA.getVNInfoBefore(Idx: LIS->getMBBEndIdx(mbb: Pred));
1125	MachineInstr *DefMI = LIS->getInstructionFromIndex(index: PVal->def);
1126	if (!DefMI || !DefMI->isFullCopy()) {
1127	CopyLeftBB = Pred;
1128	continue;
1129	}
1130	// Check DefMI is a reverse copy and it is in BB Pred.
1131	if (DefMI->getOperand(i: 0).getReg() != IntA.reg() ||
1132	DefMI->getOperand(i: 1).getReg() != IntB.reg() ||
1133	DefMI->getParent() != Pred) {
1134	CopyLeftBB = Pred;
1135	continue;
1136	}
1137	// If there is any other def of B after DefMI and before the end of Pred,
1138	// we need to keep the copy of B = A at the end of Pred if we remove
1139	// B = A from MBB.
1140	bool ValB_Changed = false;
1141	for (auto *VNI : IntB.valnos) {
1142	if (VNI->isUnused())
1143	continue;
1144	if (PVal->def < VNI->def && VNI->def < LIS->getMBBEndIdx(mbb: Pred)) {
1145	ValB_Changed = true;
1146	break;
1147	}
1148	}
1149	if (ValB_Changed) {
1150	CopyLeftBB = Pred;
1151	continue;
1152	}
1153	FoundReverseCopy = true;
1154	}
1155
1156	// If no reverse copy is found in predecessors, nothing to do.
1157	if (!FoundReverseCopy)
1158	return false;
1159
1160	// If CopyLeftBB is nullptr, it means every predecessor of MBB contains
1161	// reverse copy, CopyMI can be removed trivially if only IntA/IntB is updated.
1162	// If CopyLeftBB is not nullptr, move CopyMI from MBB to CopyLeftBB and
1163	// update IntA/IntB.
1164	//
1165	// If CopyLeftBB is not nullptr, ensure CopyLeftBB has a single succ so
1166	// MBB is hotter than CopyLeftBB.
1167	if (CopyLeftBB && CopyLeftBB->succ_size() > 1)
1168	return false;
1169
1170	// Now (almost sure it's) ok to move copy.
1171	if (CopyLeftBB) {
1172	// Position in CopyLeftBB where we should insert new copy.
1173	auto InsPos = CopyLeftBB->getFirstTerminator();
1174
1175	// Make sure that B isn't referenced in the terminators (if any) at the end
1176	// of the predecessor since we're about to insert a new definition of B
1177	// before them.
1178	if (InsPos != CopyLeftBB->end()) {
1179	SlotIndex InsPosIdx = LIS->getInstructionIndex(Instr: *InsPos).getRegSlot(EC: true);
1180	if (IntB.overlaps(Start: InsPosIdx, End: LIS->getMBBEndIdx(mbb: CopyLeftBB)))
1181	return false;
1182	}
1183
1184	LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "
1185	<< printMBBReference(*CopyLeftBB) << '\t' << CopyMI);
1186
1187	// Insert new copy to CopyLeftBB.
1188	MachineInstr *NewCopyMI = BuildMI(BB&: *CopyLeftBB, I: InsPos, MIMD: CopyMI.getDebugLoc(),
1189	MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: IntB.reg())
1190	.addReg(RegNo: IntA.reg());
1191	SlotIndex NewCopyIdx =
1192	LIS->InsertMachineInstrInMaps(MI&: *NewCopyMI).getRegSlot();
1193	IntB.createDeadDef(Def: NewCopyIdx, VNIAlloc&: LIS->getVNInfoAllocator());
1194	for (LiveInterval::SubRange &SR : IntB.subranges())
1195	SR.createDeadDef(Def: NewCopyIdx, VNIAlloc&: LIS->getVNInfoAllocator());
1196
1197	// If the newly created Instruction has an address of an instruction that was
1198	// deleted before (object recycled by the allocator) it needs to be removed from
1199	// the deleted list.
1200	ErasedInstrs.erase(Ptr: NewCopyMI);
1201	} else {
1202	LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Remove the copy from "
1203	<< printMBBReference(MBB) << '\t' << CopyMI);
1204	}
1205
1206	const bool IsUndefCopy = CopyMI.getOperand(i: 1).isUndef();
1207
1208	// Remove CopyMI.
1209	// Note: This is fine to remove the copy before updating the live-ranges.
1210	// While updating the live-ranges, we only look at slot indices and
1211	// never go back to the instruction.
1212	// Mark instructions as deleted.
1213	deleteInstr(MI: &CopyMI);
1214
1215	// Update the liveness.
1216	SmallVector<SlotIndex, 8> EndPoints;
1217	VNInfo *BValNo = IntB.Query(Idx: CopyIdx).valueOutOrDead();
1218	LIS->pruneValue(LR&: *static_cast<LiveRange *>(&IntB), Kill: CopyIdx.getRegSlot(),
1219	EndPoints: &EndPoints);
1220	BValNo->markUnused();
1221
1222	if (IsUndefCopy) {
1223	// We're introducing an undef phi def, and need to set undef on any users of
1224	// the previously local def to avoid artifically extending the lifetime
1225	// through the block.
1226	for (MachineOperand &MO : MRI->use_nodbg_operands(Reg: IntB.reg())) {
1227	const MachineInstr &MI = *MO.getParent();
1228	SlotIndex UseIdx = LIS->getInstructionIndex(Instr: MI);
1229	if (!IntB.liveAt(index: UseIdx))
1230	MO.setIsUndef(true);
1231	}
1232	}
1233
1234	// Extend IntB to the EndPoints of its original live interval.
1235	LIS->extendToIndices(LR&: IntB, Indices: EndPoints);
1236
1237	// Now, do the same for its subranges.
1238	for (LiveInterval::SubRange &SR : IntB.subranges()) {
1239	EndPoints.clear();
1240	VNInfo *BValNo = SR.Query(Idx: CopyIdx).valueOutOrDead();
1241	assert(BValNo && "All sublanes should be live");
1242	LIS->pruneValue(LR&: SR, Kill: CopyIdx.getRegSlot(), EndPoints: &EndPoints);
1243	BValNo->markUnused();
1244	// We can have a situation where the result of the original copy is live,
1245	// but is immediately dead in this subrange, e.g. [336r,336d:0). That makes
1246	// the copy appear as an endpoint from pruneValue(), but we don't want it
1247	// to because the copy has been removed. We can go ahead and remove that
1248	// endpoint; there is no other situation here that there could be a use at
1249	// the same place as we know that the copy is a full copy.
1250	for (unsigned I = 0; I != EndPoints.size(); ) {
1251	if (SlotIndex::isSameInstr(A: EndPoints[I], B: CopyIdx)) {
1252	EndPoints[I] = EndPoints.back();
1253	EndPoints.pop_back();
1254	continue;
1255	}
1256	++I;
1257	}
1258	SmallVector<SlotIndex, 8> Undefs;
1259	IntB.computeSubRangeUndefs(Undefs, LaneMask: SR.LaneMask, MRI: *MRI,
1260	Indexes: *LIS->getSlotIndexes());
1261	LIS->extendToIndices(LR&: SR, Indices: EndPoints, Undefs);
1262	}
1263	// If any dead defs were extended, truncate them.
1264	shrinkToUses(LI: &IntB);
1265
1266	// Finally, update the live-range of IntA.
1267	shrinkToUses(LI: &IntA);
1268	return true;
1269	}
1270
1271	/// Returns true if @p MI defines the full vreg @p Reg, as opposed to just
1272	/// defining a subregister.
1273	static bool definesFullReg(const MachineInstr &MI, Register Reg) {
1274	assert(!Reg.isPhysical() && "This code cannot handle physreg aliasing");
1275
1276	for (const MachineOperand &Op : MI.all_defs()) {
1277	if (Op.getReg() != Reg)
1278	continue;
1279	// Return true if we define the full register or don't care about the value
1280	// inside other subregisters.
1281	if (Op.getSubReg() == 0 || Op.isUndef())
1282	return true;
1283	}
1284	return false;
1285	}
1286
1287	bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP,
1288	MachineInstr *CopyMI,
1289	bool &IsDefCopy) {
1290	IsDefCopy = false;
1291	Register SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();
1292	unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();
1293	Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
1294	unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();
1295	if (SrcReg.isPhysical())
1296	return false;
1297
1298	LiveInterval &SrcInt = LIS->getInterval(Reg: SrcReg);
1299	SlotIndex CopyIdx = LIS->getInstructionIndex(Instr: *CopyMI);
1300	VNInfo *ValNo = SrcInt.Query(Idx: CopyIdx).valueIn();
1301	if (!ValNo)
1302	return false;
1303	if (ValNo->isPHIDef() || ValNo->isUnused())
1304	return false;
1305	MachineInstr *DefMI = LIS->getInstructionFromIndex(index: ValNo->def);
1306	if (!DefMI)
1307	return false;
1308	if (DefMI->isCopyLike()) {
1309	IsDefCopy = true;
1310	return false;
1311	}
1312	if (!TII->isAsCheapAsAMove(MI: *DefMI))
1313	return false;
1314
1315	SmallVector<Register, 8> NewRegs;
1316	LiveRangeEdit Edit(&SrcInt, NewRegs, *MF, *LIS, nullptr, this);
1317	if (!Edit.checkRematerializable(VNI: ValNo, DefMI))
1318	return false;
1319
1320	if (!definesFullReg(MI: *DefMI, Reg: SrcReg))
1321	return false;
1322	bool SawStore = false;
1323	if (!DefMI->isSafeToMove(AA, SawStore))
1324	return false;
1325	const MCInstrDesc &MCID = DefMI->getDesc();
1326	if (MCID.getNumDefs() != 1)
1327	return false;
1328	// Only support subregister destinations when the def is read-undef.
1329	MachineOperand &DstOperand = CopyMI->getOperand(i: 0);
1330	Register CopyDstReg = DstOperand.getReg();
1331	if (DstOperand.getSubReg() && !DstOperand.isUndef())
1332	return false;
1333
1334	// If both SrcIdx and DstIdx are set, correct rematerialization would widen
1335	// the register substantially (beyond both source and dest size). This is bad
1336	// for performance since it can cascade through a function, introducing many
1337	// extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers
1338	// around after a few subreg copies).
1339	if (SrcIdx && DstIdx)
1340	return false;
1341
1342	[[maybe_unused]] const unsigned DefSubIdx = DefMI->getOperand(i: 0).getSubReg();
1343	const TargetRegisterClass *DefRC = TII->getRegClass(MCID, OpNum: 0, TRI, MF: *MF);
1344	if (!DefMI->isImplicitDef()) {
1345	if (DstReg.isPhysical()) {
1346	Register NewDstReg = DstReg;
1347
1348	unsigned NewDstIdx = TRI->composeSubRegIndices(a: CP.getSrcIdx(),
1349	b: DefMI->getOperand(i: 0).getSubReg());
1350	if (NewDstIdx)
1351	NewDstReg = TRI->getSubReg(Reg: DstReg, Idx: NewDstIdx);
1352
1353	// Finally, make sure that the physical subregister that will be
1354	// constructed later is permitted for the instruction.
1355	if (!DefRC->contains(Reg: NewDstReg))
1356	return false;
1357	} else {
1358	// Theoretically, some stack frame reference could exist. Just make sure
1359	// it hasn't actually happened.
1360	assert(DstReg.isVirtual() &&
1361	"Only expect to deal with virtual or physical registers");
1362	}
1363	}
1364
1365	LiveRangeEdit::Remat RM(ValNo);
1366	RM.OrigMI = DefMI;
1367	if (!Edit.canRematerializeAt(RM, OrigVNI: ValNo, UseIdx: CopyIdx, cheapAsAMove: true))
1368	return false;
1369
1370	DebugLoc DL = CopyMI->getDebugLoc();
1371	MachineBasicBlock *MBB = CopyMI->getParent();
1372	MachineBasicBlock::iterator MII =
1373	std::next(x: MachineBasicBlock::iterator(CopyMI));
1374	Edit.rematerializeAt(MBB&: *MBB, MI: MII, DestReg: DstReg, RM, *TRI, Late: false, SubIdx: SrcIdx, ReplaceIndexMI: CopyMI);
1375	MachineInstr &NewMI = *std::prev(x: MII);
1376	NewMI.setDebugLoc(DL);
1377
1378	// In a situation like the following:
1379	// %0:subreg = instr ; DefMI, subreg = DstIdx
1380	// %1 = copy %0:subreg ; CopyMI, SrcIdx = 0
1381	// instead of widening %1 to the register class of %0 simply do:
1382	// %1 = instr
1383	const TargetRegisterClass *NewRC = CP.getNewRC();
1384	if (DstIdx != 0) {
1385	MachineOperand &DefMO = NewMI.getOperand(i: 0);
1386	if (DefMO.getSubReg() == DstIdx) {
1387	assert(SrcIdx == 0 && CP.isFlipped()
1388	&& "Shouldn't have SrcIdx+DstIdx at this point");
1389	const TargetRegisterClass *DstRC = MRI->getRegClass(Reg: DstReg);
1390	const TargetRegisterClass *CommonRC =
1391	TRI->getCommonSubClass(A: DefRC, B: DstRC);
1392	if (CommonRC != nullptr) {
1393	NewRC = CommonRC;
1394
1395	// Instruction might contain "undef %0:subreg" as use operand:
1396	// %0:subreg = instr op_1, ..., op_N, undef %0:subreg, op_N+2, ...
1397	//
1398	// Need to check all operands.
1399	for (MachineOperand &MO : NewMI.operands()) {
1400	if (MO.isReg() && MO.getReg() == DstReg && MO.getSubReg() == DstIdx) {
1401	MO.setSubReg(0);
1402	}
1403	}
1404
1405	DstIdx = 0;
1406	DefMO.setIsUndef(false); // Only subregs can have def+undef.
1407	}
1408	}
1409	}
1410
1411	// CopyMI may have implicit operands, save them so that we can transfer them
1412	// over to the newly materialized instruction after CopyMI is removed.
1413	SmallVector<MachineOperand, 4> ImplicitOps;
1414	ImplicitOps.reserve(N: CopyMI->getNumOperands() -
1415	CopyMI->getDesc().getNumOperands());
1416	for (unsigned I = CopyMI->getDesc().getNumOperands(),
1417	E = CopyMI->getNumOperands();
1418	I != E; ++I) {
1419	MachineOperand &MO = CopyMI->getOperand(i: I);
1420	if (MO.isReg()) {
1421	assert(MO.isImplicit() && "No explicit operands after implicit operands.");
1422	assert((MO.getReg().isPhysical() ||
1423	(MO.getSubReg() == 0 && MO.getReg() == DstOperand.getReg())) &&
1424	"unexpected implicit virtual register def");
1425	ImplicitOps.push_back(Elt: MO);
1426	}
1427	}
1428
1429	CopyMI->eraseFromParent();
1430	ErasedInstrs.insert(Ptr: CopyMI);
1431
1432	// NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).
1433	// We need to remember these so we can add intervals once we insert
1434	// NewMI into SlotIndexes.
1435	//
1436	// We also expect to have tied implicit-defs of super registers originating
1437	// from SUBREG_TO_REG, such as:
1438	// $edi = MOV32r0 implicit-def dead $eflags, implicit-def $rdi
1439	// undef %0.sub_32bit = MOV32r0 implicit-def dead $eflags, implicit-def %0
1440	//
1441	// The implicit-def of the super register may have been reduced to
1442	// subregisters depending on the uses.
1443
1444	bool NewMIDefinesFullReg = false;
1445
1446	SmallVector<MCRegister, 4> NewMIImplDefs;
1447	for (unsigned i = NewMI.getDesc().getNumOperands(),
1448	e = NewMI.getNumOperands();
1449	i != e; ++i) {
1450	MachineOperand &MO = NewMI.getOperand(i);
1451	if (MO.isReg() && MO.isDef()) {
1452	assert(MO.isImplicit());
1453	if (MO.getReg().isPhysical()) {
1454	if (MO.getReg() == DstReg)
1455	NewMIDefinesFullReg = true;
1456
1457	assert(MO.isImplicit() && MO.getReg().isPhysical() &&
1458	(MO.isDead() ||
1459	(DefSubIdx &&
1460	((TRI->getSubReg(MO.getReg(), DefSubIdx) ==
1461	MCRegister((unsigned)NewMI.getOperand(0).getReg())) ||
1462	TRI->isSubRegisterEq(NewMI.getOperand(0).getReg(),
1463	MO.getReg())))));
1464	NewMIImplDefs.push_back(Elt: MO.getReg().asMCReg());
1465	} else {
1466	assert(MO.getReg() == NewMI.getOperand(0).getReg());
1467
1468	// We're only expecting another def of the main output, so the range
1469	// should get updated with the regular output range.
1470	//
1471	// FIXME: The range updating below probably needs updating to look at
1472	// the super register if subranges are tracked.
1473	assert(!MRI->shouldTrackSubRegLiveness(DstReg) &&
1474	"subrange update for implicit-def of super register may not be "
1475	"properly handled");
1476	}
1477	}
1478	}
1479
1480	if (DstReg.isVirtual()) {
1481	unsigned NewIdx = NewMI.getOperand(i: 0).getSubReg();
1482
1483	if (DefRC != nullptr) {
1484	if (NewIdx)
1485	NewRC = TRI->getMatchingSuperRegClass(A: NewRC, B: DefRC, Idx: NewIdx);
1486	else
1487	NewRC = TRI->getCommonSubClass(A: NewRC, B: DefRC);
1488	assert(NewRC && "subreg chosen for remat incompatible with instruction");
1489	}
1490	// Remap subranges to new lanemask and change register class.
1491	LiveInterval &DstInt = LIS->getInterval(Reg: DstReg);
1492	for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1493	SR.LaneMask = TRI->composeSubRegIndexLaneMask(IdxA: DstIdx, Mask: SR.LaneMask);
1494	}
1495	MRI->setRegClass(Reg: DstReg, RC: NewRC);
1496
1497	// Update machine operands and add flags.
1498	updateRegDefsUses(SrcReg: DstReg, DstReg, SubIdx: DstIdx);
1499	NewMI.getOperand(i: 0).setSubReg(NewIdx);
1500	// updateRegDefUses can add an "undef" flag to the definition, since
1501	// it will replace DstReg with DstReg.DstIdx. If NewIdx is 0, make
1502	// sure that "undef" is not set.
1503	if (NewIdx == 0)
1504	NewMI.getOperand(i: 0).setIsUndef(false);
1505	// Add dead subregister definitions if we are defining the whole register
1506	// but only part of it is live.
1507	// This could happen if the rematerialization instruction is rematerializing
1508	// more than actually is used in the register.
1509	// An example would be:
1510	// %1 = LOAD CONSTANTS 5, 8 ; Loading both 5 and 8 in different subregs
1511	// ; Copying only part of the register here, but the rest is undef.
1512	// %2:sub_16bit<def, read-undef> = COPY %1:sub_16bit
1513	// ==>
1514	// ; Materialize all the constants but only using one
1515	// %2 = LOAD_CONSTANTS 5, 8
1516	//
1517	// at this point for the part that wasn't defined before we could have
1518	// subranges missing the definition.
1519	if (NewIdx == 0 && DstInt.hasSubRanges()) {
1520	SlotIndex CurrIdx = LIS->getInstructionIndex(Instr: NewMI);
1521	SlotIndex DefIndex =
1522	CurrIdx.getRegSlot(EC: NewMI.getOperand(i: 0).isEarlyClobber());
1523	LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg: DstReg);
1524	VNInfo::Allocator& Alloc = LIS->getVNInfoAllocator();
1525	for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1526	if (!SR.liveAt(index: DefIndex))
1527	SR.createDeadDef(Def: DefIndex, VNIAlloc&: Alloc);
1528	MaxMask &= ~SR.LaneMask;
1529	}
1530	if (MaxMask.any()) {
1531	LiveInterval::SubRange *SR = DstInt.createSubRange(Allocator&: Alloc, LaneMask: MaxMask);
1532	SR->createDeadDef(Def: DefIndex, VNIAlloc&: Alloc);
1533	}
1534	}
1535
1536	// Make sure that the subrange for resultant undef is removed
1537	// For example:
1538	// %1:sub1<def,read-undef> = LOAD CONSTANT 1
1539	// %2 = COPY %1
1540	// ==>
1541	// %2:sub1<def, read-undef> = LOAD CONSTANT 1
1542	// ; Correct but need to remove the subrange for %2:sub0
1543	// ; as it is now undef
1544	if (NewIdx != 0 && DstInt.hasSubRanges()) {
1545	// The affected subregister segments can be removed.
1546	SlotIndex CurrIdx = LIS->getInstructionIndex(Instr: NewMI);
1547	LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(SubIdx: NewIdx);
1548	bool UpdatedSubRanges = false;
1549	SlotIndex DefIndex =
1550	CurrIdx.getRegSlot(EC: NewMI.getOperand(i: 0).isEarlyClobber());
1551	VNInfo::Allocator &Alloc = LIS->getVNInfoAllocator();
1552	for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1553	if ((SR.LaneMask & DstMask).none()) {
1554	LLVM_DEBUG(dbgs()
1555	<< "Removing undefined SubRange "
1556	<< PrintLaneMask(SR.LaneMask) << " : " << SR << "\n");
1557
1558	if (VNInfo *RmValNo = SR.getVNInfoAt(Idx: CurrIdx.getRegSlot())) {
1559	// VNI is in ValNo - remove any segments in this SubRange that have
1560	// this ValNo
1561	SR.removeValNo(ValNo: RmValNo);
1562	}
1563
1564	// We may not have a defined value at this point, but still need to
1565	// clear out any empty subranges tentatively created by
1566	// updateRegDefUses. The original subrange def may have only undefed
1567	// some lanes.
1568	UpdatedSubRanges = true;
1569	} else {
1570	// We know that this lane is defined by this instruction,
1571	// but at this point it may be empty because it is not used by
1572	// anything. This happens when updateRegDefUses adds the missing
1573	// lanes. Assign that lane a dead def so that the interferences
1574	// are properly modeled.
1575	if (SR.empty())
1576	SR.createDeadDef(Def: DefIndex, VNIAlloc&: Alloc);
1577	}
1578	}
1579	if (UpdatedSubRanges)
1580	DstInt.removeEmptySubRanges();
1581	}
1582	} else if (NewMI.getOperand(i: 0).getReg() != CopyDstReg) {
1583	// The New instruction may be defining a sub-register of what's actually
1584	// been asked for. If so it must implicitly define the whole thing.
1585	assert(DstReg.isPhysical() &&
1586	"Only expect virtual or physical registers in remat");
1587	NewMI.getOperand(i: 0).setIsDead(true);
1588
1589	if (!NewMIDefinesFullReg) {
1590	NewMI.addOperand(Op: MachineOperand::CreateReg(
1591	Reg: CopyDstReg, isDef: true /*IsDef*/, isImp: true /*IsImp*/, isKill: false /*IsKill*/));
1592	}
1593
1594	// Record small dead def live-ranges for all the subregisters
1595	// of the destination register.
1596	// Otherwise, variables that live through may miss some
1597	// interferences, thus creating invalid allocation.
1598	// E.g., i386 code:
1599	// %1 = somedef ; %1 GR8
1600	// %2 = remat ; %2 GR32
1601	// CL = COPY %2.sub_8bit
1602	// = somedef %1 ; %1 GR8
1603	// =>
1604	// %1 = somedef ; %1 GR8
1605	// dead ECX = remat ; implicit-def CL
1606	// = somedef %1 ; %1 GR8
1607	// %1 will see the interferences with CL but not with CH since
1608	// no live-ranges would have been created for ECX.
1609	// Fix that!
1610	SlotIndex NewMIIdx = LIS->getInstructionIndex(Instr: NewMI);
1611	for (MCRegUnit Unit : TRI->regunits(Reg: NewMI.getOperand(i: 0).getReg()))
1612	if (LiveRange *LR = LIS->getCachedRegUnit(Unit))
1613	LR->createDeadDef(Def: NewMIIdx.getRegSlot(), VNIAlloc&: LIS->getVNInfoAllocator());
1614	}
1615
1616	NewMI.setRegisterDefReadUndef(Reg: NewMI.getOperand(i: 0).getReg());
1617
1618	// Transfer over implicit operands to the rematerialized instruction.
1619	for (MachineOperand &MO : ImplicitOps)
1620	NewMI.addOperand(Op: MO);
1621
1622	SlotIndex NewMIIdx = LIS->getInstructionIndex(Instr: NewMI);
1623	for (MCRegister Reg : NewMIImplDefs) {
1624	for (MCRegUnit Unit : TRI->regunits(Reg))
1625	if (LiveRange *LR = LIS->getCachedRegUnit(Unit))
1626	LR->createDeadDef(Def: NewMIIdx.getRegSlot(), VNIAlloc&: LIS->getVNInfoAllocator());
1627	}
1628
1629	LLVM_DEBUG(dbgs() << "Remat: " << NewMI);
1630	++NumReMats;
1631
1632	// If the virtual SrcReg is completely eliminated, update all DBG_VALUEs
1633	// to describe DstReg instead.
1634	if (MRI->use_nodbg_empty(RegNo: SrcReg)) {
1635	for (MachineOperand &UseMO :
1636	llvm::make_early_inc_range(Range: MRI->use_operands(Reg: SrcReg))) {
1637	MachineInstr *UseMI = UseMO.getParent();
1638	if (UseMI->isDebugInstr()) {
1639	if (DstReg.isPhysical())
1640	UseMO.substPhysReg(Reg: DstReg, *TRI);
1641	else
1642	UseMO.setReg(DstReg);
1643	// Move the debug value directly after the def of the rematerialized
1644	// value in DstReg.
1645	MBB->splice(Where: std::next(x: NewMI.getIterator()), Other: UseMI->getParent(), From: UseMI);
1646	LLVM_DEBUG(dbgs() << "\t\tupdated: " << *UseMI);
1647	}
1648	}
1649	}
1650
1651	if (ToBeUpdated.count(V: SrcReg))
1652	return true;
1653
1654	unsigned NumCopyUses = 0;
1655	for (MachineOperand &UseMO : MRI->use_nodbg_operands(Reg: SrcReg)) {
1656	if (UseMO.getParent()->isCopyLike())
1657	NumCopyUses++;
1658	}
1659	if (NumCopyUses < LateRematUpdateThreshold) {
1660	// The source interval can become smaller because we removed a use.
1661	shrinkToUses(LI: &SrcInt, Dead: &DeadDefs);
1662	if (!DeadDefs.empty())
1663	eliminateDeadDefs(Edit: &Edit);
1664	} else {
1665	ToBeUpdated.insert(V: SrcReg);
1666	}
1667	return true;
1668	}
1669
1670	MachineInstr *RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) {
1671	// ProcessImplicitDefs may leave some copies of <undef> values, it only
1672	// removes local variables. When we have a copy like:
1673	//
1674	// %1 = COPY undef %2
1675	//
1676	// We delete the copy and remove the corresponding value number from %1.
1677	// Any uses of that value number are marked as <undef>.
1678
1679	// Note that we do not query CoalescerPair here but redo isMoveInstr as the
1680	// CoalescerPair may have a new register class with adjusted subreg indices
1681	// at this point.
1682	Register SrcReg, DstReg;
1683	unsigned SrcSubIdx = 0, DstSubIdx = 0;
1684	if(!isMoveInstr(tri: *TRI, MI: CopyMI, Src&: SrcReg, Dst&: DstReg, SrcSub&: SrcSubIdx, DstSub&: DstSubIdx))
1685	return nullptr;
1686
1687	SlotIndex Idx = LIS->getInstructionIndex(Instr: *CopyMI);
1688	const LiveInterval &SrcLI = LIS->getInterval(Reg: SrcReg);
1689	// CopyMI is undef iff SrcReg is not live before the instruction.
1690	if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
1691	LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SubIdx: SrcSubIdx);
1692	for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {
1693	if ((SR.LaneMask & SrcMask).none())
1694	continue;
1695	if (SR.liveAt(index: Idx))
1696	return nullptr;
1697	}
1698	} else if (SrcLI.liveAt(index: Idx))
1699	return nullptr;
1700
1701	// If the undef copy defines a live-out value (i.e. an input to a PHI def),
1702	// then replace it with an IMPLICIT_DEF.
1703	LiveInterval &DstLI = LIS->getInterval(Reg: DstReg);
1704	SlotIndex RegIndex = Idx.getRegSlot();
1705	LiveRange::Segment *Seg = DstLI.getSegmentContaining(Idx: RegIndex);
1706	assert(Seg != nullptr && "No segment for defining instruction");
1707	VNInfo *V = DstLI.getVNInfoAt(Idx: Seg->end);
1708
1709	// The source interval may also have been on an undef use, in which case the
1710	// copy introduced a live value.
1711	if (((V && V->isPHIDef()) || (!V && !DstLI.liveAt(index: Idx)))) {
1712	for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {
1713	MachineOperand &MO = CopyMI->getOperand(i: i-1);
1714	if (MO.isReg()) {
1715	if (MO.isUse())
1716	CopyMI->removeOperand(OpNo: i - 1);
1717	} else {
1718	assert(MO.isImm() &&
1719	CopyMI->getOpcode() == TargetOpcode::SUBREG_TO_REG);
1720	CopyMI->removeOperand(OpNo: i-1);
1721	}
1722	}
1723
1724	CopyMI->setDesc(TII->get(Opcode: TargetOpcode::IMPLICIT_DEF));
1725	LLVM_DEBUG(dbgs() << "\tReplaced copy of <undef> value with an "
1726	"implicit def\n");
1727	return CopyMI;
1728	}
1729
1730	// Remove any DstReg segments starting at the instruction.
1731	LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
1732
1733	// Remove value or merge with previous one in case of a subregister def.
1734	if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
1735	VNInfo *VNI = DstLI.getVNInfoAt(Idx: RegIndex);
1736	DstLI.MergeValueNumberInto(V1: VNI, V2: PrevVNI);
1737
1738	// The affected subregister segments can be removed.
1739	LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(SubIdx: DstSubIdx);
1740	for (LiveInterval::SubRange &SR : DstLI.subranges()) {
1741	if ((SR.LaneMask & DstMask).none())
1742	continue;
1743
1744	VNInfo *SVNI = SR.getVNInfoAt(Idx: RegIndex);
1745	assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex));
1746	SR.removeValNo(ValNo: SVNI);
1747	}
1748	DstLI.removeEmptySubRanges();
1749	} else
1750	LIS->removeVRegDefAt(LI&: DstLI, Pos: RegIndex);
1751
1752	// Mark uses as undef.
1753	for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg: DstReg)) {
1754	if (MO.isDef() /*|| MO.isUndef()*/)
1755	continue;
1756	const MachineInstr &MI = *MO.getParent();
1757	SlotIndex UseIdx = LIS->getInstructionIndex(Instr: MI);
1758	LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubIdx: MO.getSubReg());
1759	bool isLive;
1760	if (!UseMask.all() && DstLI.hasSubRanges()) {
1761	isLive = false;
1762	for (const LiveInterval::SubRange &SR : DstLI.subranges()) {
1763	if ((SR.LaneMask & UseMask).none())
1764	continue;
1765	if (SR.liveAt(index: UseIdx)) {
1766	isLive = true;
1767	break;
1768	}
1769	}
1770	} else
1771	isLive = DstLI.liveAt(index: UseIdx);
1772	if (isLive)
1773	continue;
1774	MO.setIsUndef(true);
1775	LLVM_DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI);
1776	}
1777
1778	// A def of a subregister may be a use of the other subregisters, so
1779	// deleting a def of a subregister may also remove uses. Since CopyMI
1780	// is still part of the function (but about to be erased), mark all
1781	// defs of DstReg in it as <undef>, so that shrinkToUses would
1782	// ignore them.
1783	for (MachineOperand &MO : CopyMI->all_defs())
1784	if (MO.getReg() == DstReg)
1785	MO.setIsUndef(true);
1786	LIS->shrinkToUses(li: &DstLI);
1787
1788	return CopyMI;
1789	}
1790
1791	void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
1792	MachineOperand &MO, unsigned SubRegIdx) {
1793	LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubIdx: SubRegIdx);
1794	if (MO.isDef())
1795	Mask = ~Mask;
1796	bool IsUndef = true;
1797	for (const LiveInterval::SubRange &S : Int.subranges()) {
1798	if ((S.LaneMask & Mask).none())
1799	continue;
1800	if (S.liveAt(index: UseIdx)) {
1801	IsUndef = false;
1802	break;
1803	}
1804	}
1805	if (IsUndef) {
1806	MO.setIsUndef(true);
1807	// We found out some subregister use is actually reading an undefined
1808	// value. In some cases the whole vreg has become undefined at this
1809	// point so we have to potentially shrink the main range if the
1810	// use was ending a live segment there.
1811	LiveQueryResult Q = Int.Query(Idx: UseIdx);
1812	if (Q.valueOut() == nullptr)
1813	ShrinkMainRange = true;
1814	}
1815	}
1816
1817	void RegisterCoalescer::updateRegDefsUses(Register SrcReg, Register DstReg,
1818	unsigned SubIdx) {
1819	bool DstIsPhys = DstReg.isPhysical();
1820	LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(Reg: DstReg);
1821
1822	if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
1823	for (MachineOperand &MO : MRI->reg_operands(Reg: DstReg)) {
1824	unsigned SubReg = MO.getSubReg();
1825	if (SubReg == 0 || MO.isUndef())
1826	continue;
1827	MachineInstr &MI = *MO.getParent();
1828	if (MI.isDebugInstr())
1829	continue;
1830	SlotIndex UseIdx = LIS->getInstructionIndex(Instr: MI).getRegSlot(EC: true);
1831	addUndefFlag(Int: *DstInt, UseIdx, MO, SubRegIdx: SubReg);
1832	}
1833	}
1834
1835	SmallPtrSet<MachineInstr*, 8> Visited;
1836	for (MachineRegisterInfo::reg_instr_iterator
1837	I = MRI->reg_instr_begin(RegNo: SrcReg), E = MRI->reg_instr_end();
1838	I != E; ) {
1839	MachineInstr *UseMI = &*(I++);
1840
1841	// Each instruction can only be rewritten once because sub-register
1842	// composition is not always idempotent. When SrcReg != DstReg, rewriting
1843	// the UseMI operands removes them from the SrcReg use-def chain, but when
1844	// SrcReg is DstReg we could encounter UseMI twice if it has multiple
1845	// operands mentioning the virtual register.
1846	if (SrcReg == DstReg && !Visited.insert(Ptr: UseMI).second)
1847	continue;
1848
1849	SmallVector<unsigned,8> Ops;
1850	bool Reads, Writes;
1851	std::tie(args&: Reads, args&: Writes) = UseMI->readsWritesVirtualRegister(Reg: SrcReg, Ops: &Ops);
1852
1853	// If SrcReg wasn't read, it may still be the case that DstReg is live-in
1854	// because SrcReg is a sub-register.
1855	if (DstInt && !Reads && SubIdx && !UseMI->isDebugInstr())
1856	Reads = DstInt->liveAt(index: LIS->getInstructionIndex(Instr: *UseMI));
1857
1858	// Replace SrcReg with DstReg in all UseMI operands.
1859	for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1860	MachineOperand &MO = UseMI->getOperand(i: Ops[i]);
1861
1862	// Adjust <undef> flags in case of sub-register joins. We don't want to
1863	// turn a full def into a read-modify-write sub-register def and vice
1864	// versa.
1865	if (SubIdx && MO.isDef())
1866	MO.setIsUndef(!Reads);
1867
1868	// A subreg use of a partially undef (super) register may be a complete
1869	// undef use now and then has to be marked that way.
1870	if (MO.isUse() && !DstIsPhys) {
1871	unsigned SubUseIdx = TRI->composeSubRegIndices(a: SubIdx, b: MO.getSubReg());
1872	if (SubUseIdx != 0 && MRI->shouldTrackSubRegLiveness(VReg: DstReg)) {
1873	if (!DstInt->hasSubRanges()) {
1874	BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
1875	LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(Reg: DstInt->reg());
1876	LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(SubIdx);
1877	LaneBitmask UnusedLanes = FullMask & ~UsedLanes;
1878	DstInt->createSubRangeFrom(Allocator, LaneMask: UsedLanes, CopyFrom: *DstInt);
1879	// The unused lanes are just empty live-ranges at this point.
1880	// It is the caller responsibility to set the proper
1881	// dead segments if there is an actual dead def of the
1882	// unused lanes. This may happen with rematerialization.
1883	DstInt->createSubRange(Allocator, LaneMask: UnusedLanes);
1884	}
1885	SlotIndex MIIdx = UseMI->isDebugInstr()
1886	? LIS->getSlotIndexes()->getIndexBefore(MI: *UseMI)
1887	: LIS->getInstructionIndex(Instr: *UseMI);
1888	SlotIndex UseIdx = MIIdx.getRegSlot(EC: true);
1889	addUndefFlag(Int: *DstInt, UseIdx, MO, SubRegIdx: SubUseIdx);
1890	}
1891	}
1892
1893	if (DstIsPhys)
1894	MO.substPhysReg(Reg: DstReg, *TRI);
1895	else
1896	MO.substVirtReg(Reg: DstReg, SubIdx, *TRI);
1897	}
1898
1899	LLVM_DEBUG({
1900	dbgs() << "\t\tupdated: ";
1901	if (!UseMI->isDebugInstr())
1902	dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";
1903	dbgs() << *UseMI;
1904	});
1905	}
1906	}
1907
1908	bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
1909	// Always join simple intervals that are defined by a single copy from a
1910	// reserved register. This doesn't increase register pressure, so it is
1911	// always beneficial.
1912	if (!MRI->isReserved(PhysReg: CP.getDstReg())) {
1913	LLVM_DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
1914	return false;
1915	}
1916
1917	LiveInterval &JoinVInt = LIS->getInterval(Reg: CP.getSrcReg());
1918	if (JoinVInt.containsOneValue())
1919	return true;
1920
1921	LLVM_DEBUG(
1922	dbgs() << "\tCannot join complex intervals into reserved register.\n");
1923	return false;
1924	}
1925
1926	bool RegisterCoalescer::copyValueUndefInPredecessors(
1927	LiveRange &S, const MachineBasicBlock *MBB, LiveQueryResult SLRQ) {
1928	for (const MachineBasicBlock *Pred : MBB->predecessors()) {
1929	SlotIndex PredEnd = LIS->getMBBEndIdx(mbb: Pred);
1930	if (VNInfo *V = S.getVNInfoAt(Idx: PredEnd.getPrevSlot())) {
1931	// If this is a self loop, we may be reading the same value.
1932	if (V->id != SLRQ.valueOutOrDead()->id)
1933	return false;
1934	}
1935	}
1936
1937	return true;
1938	}
1939
1940	void RegisterCoalescer::setUndefOnPrunedSubRegUses(LiveInterval &LI,
1941	Register Reg,
1942	LaneBitmask PrunedLanes) {
1943	// If we had other instructions in the segment reading the undef sublane
1944	// value, we need to mark them with undef.
1945	for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
1946	unsigned SubRegIdx = MO.getSubReg();
1947	if (SubRegIdx == 0 || MO.isUndef())
1948	continue;
1949
1950	LaneBitmask SubRegMask = TRI->getSubRegIndexLaneMask(SubIdx: SubRegIdx);
1951	SlotIndex Pos = LIS->getInstructionIndex(Instr: *MO.getParent());
1952	for (LiveInterval::SubRange &S : LI.subranges()) {
1953	if (!S.liveAt(index: Pos) && (PrunedLanes & SubRegMask).any()) {
1954	MO.setIsUndef();
1955	break;
1956	}
1957	}
1958	}
1959
1960	LI.removeEmptySubRanges();
1961
1962	// A def of a subregister may be a use of other register lanes. Replacing
1963	// such a def with a def of a different register will eliminate the use,
1964	// and may cause the recorded live range to be larger than the actual
1965	// liveness in the program IR.
1966	LIS->shrinkToUses(li: &LI);
1967	}
1968
1969	bool RegisterCoalescer::joinCopy(
1970	MachineInstr *CopyMI, bool &Again,
1971	SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs) {
1972	Again = false;
1973	LLVM_DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI);
1974
1975	CoalescerPair CP(*TRI);
1976	if (!CP.setRegisters(CopyMI)) {
1977	LLVM_DEBUG(dbgs() << "\tNot coalescable.\n");
1978	return false;
1979	}
1980
1981	if (CP.getNewRC()) {
1982	auto SrcRC = MRI->getRegClass(Reg: CP.getSrcReg());
1983	auto DstRC = MRI->getRegClass(Reg: CP.getDstReg());
1984	unsigned SrcIdx = CP.getSrcIdx();
1985	unsigned DstIdx = CP.getDstIdx();
1986	if (CP.isFlipped()) {
1987	std::swap(a&: SrcIdx, b&: DstIdx);
1988	std::swap(a&: SrcRC, b&: DstRC);
1989	}
1990	if (!TRI->shouldCoalesce(MI: CopyMI, SrcRC, SubReg: SrcIdx, DstRC, DstSubReg: DstIdx,
1991	NewRC: CP.getNewRC(), LIS&: *LIS)) {
1992	LLVM_DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n");
1993	return false;
1994	}
1995	}
1996
1997	// Dead code elimination. This really should be handled by MachineDCE, but
1998	// sometimes dead copies slip through, and we can't generate invalid live
1999	// ranges.
2000	if (!CP.isPhys() && CopyMI->allDefsAreDead()) {
2001	LLVM_DEBUG(dbgs() << "\tCopy is dead.\n");
2002	DeadDefs.push_back(Elt: CopyMI);
2003	eliminateDeadDefs();
2004	return true;
2005	}
2006
2007	// Eliminate undefs.
2008	if (!CP.isPhys()) {
2009	// If this is an IMPLICIT_DEF, leave it alone, but don't try to coalesce.
2010	if (MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {
2011	if (UndefMI->isImplicitDef())
2012	return false;
2013	deleteInstr(MI: CopyMI);
2014	return false; // Not coalescable.
2015	}
2016	}
2017
2018	// Coalesced copies are normally removed immediately, but transformations
2019	// like removeCopyByCommutingDef() can inadvertently create identity copies.
2020	// When that happens, just join the values and remove the copy.
2021	if (CP.getSrcReg() == CP.getDstReg()) {
2022	LiveInterval &LI = LIS->getInterval(Reg: CP.getSrcReg());
2023	LLVM_DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n');
2024	const SlotIndex CopyIdx = LIS->getInstructionIndex(Instr: *CopyMI);
2025	LiveQueryResult LRQ = LI.Query(Idx: CopyIdx);
2026	if (VNInfo *DefVNI = LRQ.valueDefined()) {
2027	VNInfo *ReadVNI = LRQ.valueIn();
2028	assert(ReadVNI && "No value before copy and no <undef> flag.");
2029	assert(ReadVNI != DefVNI && "Cannot read and define the same value.");
2030
2031	// Track incoming undef lanes we need to eliminate from the subrange.
2032	LaneBitmask PrunedLanes;
2033	MachineBasicBlock *MBB = CopyMI->getParent();
2034
2035	// Process subregister liveranges.
2036	for (LiveInterval::SubRange &S : LI.subranges()) {
2037	LiveQueryResult SLRQ = S.Query(Idx: CopyIdx);
2038	if (VNInfo *SDefVNI = SLRQ.valueDefined()) {
2039	if (VNInfo *SReadVNI = SLRQ.valueIn())
2040	SDefVNI = S.MergeValueNumberInto(V1: SDefVNI, V2: SReadVNI);
2041
2042	// If this copy introduced an undef subrange from an incoming value,
2043	// we need to eliminate the undef live in values from the subrange.
2044	if (copyValueUndefInPredecessors(S, MBB, SLRQ)) {
2045	LLVM_DEBUG(dbgs() << "Incoming sublane value is undef at copy\n");
2046	PrunedLanes |= S.LaneMask;
2047	S.removeValNo(ValNo: SDefVNI);
2048	}
2049	}
2050	}
2051
2052	LI.MergeValueNumberInto(V1: DefVNI, V2: ReadVNI);
2053	if (PrunedLanes.any()) {
2054	LLVM_DEBUG(dbgs() << "Pruning undef incoming lanes: "
2055	<< PrunedLanes << '\n');
2056	setUndefOnPrunedSubRegUses(LI, Reg: CP.getSrcReg(), PrunedLanes);
2057	}
2058
2059	LLVM_DEBUG(dbgs() << "\tMerged values: " << LI << '\n');
2060	}
2061	deleteInstr(MI: CopyMI);
2062	return true;
2063	}
2064
2065	// Enforce policies.
2066	if (CP.isPhys()) {
2067	LLVM_DEBUG(dbgs() << "\tConsidering merging "
2068	<< printReg(CP.getSrcReg(), TRI) << " with "
2069	<< printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n');
2070	if (!canJoinPhys(CP)) {
2071	// Before giving up coalescing, if definition of source is defined by
2072	// trivial computation, try rematerializing it.
2073	bool IsDefCopy = false;
2074	if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2075	return true;
2076	if (IsDefCopy)
2077	Again = true; // May be possible to coalesce later.
2078	return false;
2079	}
2080	} else {
2081	// When possible, let DstReg be the larger interval.
2082	if (!CP.isPartial() && LIS->getInterval(Reg: CP.getSrcReg()).size() >
2083	LIS->getInterval(Reg: CP.getDstReg()).size())
2084	CP.flip();
2085
2086	LLVM_DEBUG({
2087	dbgs() << "\tConsidering merging to "
2088	<< TRI->getRegClassName(CP.getNewRC()) << " with ";
2089	if (CP.getDstIdx() && CP.getSrcIdx())
2090	dbgs() << printReg(CP.getDstReg()) << " in "
2091	<< TRI->getSubRegIndexName(CP.getDstIdx()) << " and "
2092	<< printReg(CP.getSrcReg()) << " in "
2093	<< TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';
2094	else
2095	dbgs() << printReg(CP.getSrcReg(), TRI) << " in "
2096	<< printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';
2097	});
2098	}
2099
2100	ShrinkMask = LaneBitmask::getNone();
2101	ShrinkMainRange = false;
2102
2103	// Okay, attempt to join these two intervals. On failure, this returns false.
2104	// Otherwise, if one of the intervals being joined is a physreg, this method
2105	// always canonicalizes DstInt to be it. The output "SrcInt" will not have
2106	// been modified, so we can use this information below to update aliases.
2107	if (!joinIntervals(CP)) {
2108	// Coalescing failed.
2109
2110	// If definition of source is defined by trivial computation, try
2111	// rematerializing it.
2112	bool IsDefCopy = false;
2113	if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2114	return true;
2115
2116	// If we can eliminate the copy without merging the live segments, do so
2117	// now.
2118	if (!CP.isPartial() && !CP.isPhys()) {
2119	bool Changed = adjustCopiesBackFrom(CP, CopyMI);
2120	bool Shrink = false;
2121	if (!Changed)
2122	std::tie(args&: Changed, args&: Shrink) = removeCopyByCommutingDef(CP, CopyMI);
2123	if (Changed) {
2124	deleteInstr(MI: CopyMI);
2125	if (Shrink) {
2126	Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
2127	LiveInterval &DstLI = LIS->getInterval(Reg: DstReg);
2128	shrinkToUses(LI: &DstLI);
2129	LLVM_DEBUG(dbgs() << "\t\tshrunk: " << DstLI << '\n');
2130	}
2131	LLVM_DEBUG(dbgs() << "\tTrivial!\n");
2132	return true;
2133	}
2134	}
2135
2136	// Try and see if we can partially eliminate the copy by moving the copy to
2137	// its predecessor.
2138	if (!CP.isPartial() && !CP.isPhys())
2139	if (removePartialRedundancy(CP, CopyMI&: *CopyMI))
2140	return true;
2141
2142	// Otherwise, we are unable to join the intervals.
2143	LLVM_DEBUG(dbgs() << "\tInterference!\n");
2144	Again = true; // May be possible to coalesce later.
2145	return false;
2146	}
2147
2148	// Coalescing to a virtual register that is of a sub-register class of the
2149	// other. Make sure the resulting register is set to the right register class.
2150	if (CP.isCrossClass()) {
2151	++numCrossRCs;
2152	MRI->setRegClass(Reg: CP.getDstReg(), RC: CP.getNewRC());
2153	}
2154
2155	// Removing sub-register copies can ease the register class constraints.
2156	// Make sure we attempt to inflate the register class of DstReg.
2157	if (!CP.isPhys() && RegClassInfo.isProperSubClass(RC: CP.getNewRC()))
2158	InflateRegs.push_back(Elt: CP.getDstReg());
2159
2160	// CopyMI has been erased by joinIntervals at this point. Remove it from
2161	// ErasedInstrs since copyCoalesceWorkList() won't add a successful join back
2162	// to the work list. This keeps ErasedInstrs from growing needlessly.
2163	if (ErasedInstrs.erase(Ptr: CopyMI))
2164	// But we may encounter the instruction again in this iteration.
2165	CurrentErasedInstrs.insert(Ptr: CopyMI);
2166
2167	// Rewrite all SrcReg operands to DstReg.
2168	// Also update DstReg operands to include DstIdx if it is set.
2169	if (CP.getDstIdx())
2170	updateRegDefsUses(SrcReg: CP.getDstReg(), DstReg: CP.getDstReg(), SubIdx: CP.getDstIdx());
2171	updateRegDefsUses(SrcReg: CP.getSrcReg(), DstReg: CP.getDstReg(), SubIdx: CP.getSrcIdx());
2172
2173	// Shrink subregister ranges if necessary.
2174	if (ShrinkMask.any()) {
2175	LiveInterval &LI = LIS->getInterval(Reg: CP.getDstReg());
2176	for (LiveInterval::SubRange &S : LI.subranges()) {
2177	if ((S.LaneMask & ShrinkMask).none())
2178	continue;
2179	LLVM_DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask)
2180	<< ")\n");
2181	LIS->shrinkToUses(SR&: S, Reg: LI.reg());
2182	ShrinkMainRange = true;
2183	}
2184	LI.removeEmptySubRanges();
2185	}
2186
2187	// CP.getSrcReg()'s live interval has been merged into CP.getDstReg's live
2188	// interval. Since CP.getSrcReg() is in ToBeUpdated set and its live interval
2189	// is not up-to-date, need to update the merged live interval here.
2190	if (ToBeUpdated.count(V: CP.getSrcReg()))
2191	ShrinkMainRange = true;
2192
2193	if (ShrinkMainRange) {
2194	LiveInterval &LI = LIS->getInterval(Reg: CP.getDstReg());
2195	shrinkToUses(LI: &LI);
2196	}
2197
2198	// SrcReg is guaranteed to be the register whose live interval that is
2199	// being merged.
2200	LIS->removeInterval(Reg: CP.getSrcReg());
2201
2202	// Update regalloc hint.
2203	TRI->updateRegAllocHint(Reg: CP.getSrcReg(), NewReg: CP.getDstReg(), MF&: *MF);
2204
2205	LLVM_DEBUG({
2206	dbgs() << "\tSuccess: " << printReg(CP.getSrcReg(), TRI, CP.getSrcIdx())
2207	<< " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
2208	dbgs() << "\tResult = ";
2209	if (CP.isPhys())
2210	dbgs() << printReg(CP.getDstReg(), TRI);
2211	else
2212	dbgs() << LIS->getInterval(CP.getDstReg());
2213	dbgs() << '\n';
2214	});
2215
2216	++numJoins;
2217	return true;
2218	}
2219
2220	bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
2221	Register DstReg = CP.getDstReg();
2222	Register SrcReg = CP.getSrcReg();
2223	assert(CP.isPhys() && "Must be a physreg copy");
2224	assert(MRI->isReserved(DstReg) && "Not a reserved register");
2225	LiveInterval &RHS = LIS->getInterval(Reg: SrcReg);
2226	LLVM_DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n');
2227
2228	assert(RHS.containsOneValue() && "Invalid join with reserved register");
2229
2230	// Optimization for reserved registers like ESP. We can only merge with a
2231	// reserved physreg if RHS has a single value that is a copy of DstReg.
2232	// The live range of the reserved register will look like a set of dead defs
2233	// - we don't properly track the live range of reserved registers.
2234
2235	// Deny any overlapping intervals. This depends on all the reserved
2236	// register live ranges to look like dead defs.
2237	if (!MRI->isConstantPhysReg(PhysReg: DstReg)) {
2238	for (MCRegUnit Unit : TRI->regunits(Reg: DstReg)) {
2239	// Abort if not all the regunits are reserved.
2240	for (MCRegUnitRootIterator RI(Unit, TRI); RI.isValid(); ++RI) {
2241	if (!MRI->isReserved(PhysReg: *RI))
2242	return false;
2243	}
2244	if (RHS.overlaps(other: LIS->getRegUnit(Unit))) {
2245	LLVM_DEBUG(dbgs() << "\t\tInterference: " << printRegUnit(Unit, TRI)
2246	<< '\n');
2247	return false;
2248	}
2249	}
2250
2251	// We must also check for overlaps with regmask clobbers.
2252	BitVector RegMaskUsable;
2253	if (LIS->checkRegMaskInterference(LI: RHS, UsableRegs&: RegMaskUsable) &&
2254	!RegMaskUsable.test(Idx: DstReg)) {
2255	LLVM_DEBUG(dbgs() << "\t\tRegMask interference\n");
2256	return false;
2257	}
2258	}
2259
2260	// Skip any value computations, we are not adding new values to the
2261	// reserved register. Also skip merging the live ranges, the reserved
2262	// register live range doesn't need to be accurate as long as all the
2263	// defs are there.
2264
2265	// Delete the identity copy.
2266	MachineInstr *CopyMI;
2267	if (CP.isFlipped()) {
2268	// Physreg is copied into vreg
2269	// %y = COPY %physreg_x
2270	// ... //< no other def of %physreg_x here
2271	// use %y
2272	// =>
2273	// ...
2274	// use %physreg_x
2275	CopyMI = MRI->getVRegDef(Reg: SrcReg);
2276	deleteInstr(MI: CopyMI);
2277	} else {
2278	// VReg is copied into physreg:
2279	// %y = def
2280	// ... //< no other def or use of %physreg_x here
2281	// %physreg_x = COPY %y
2282	// =>
2283	// %physreg_x = def
2284	// ...
2285	if (!MRI->hasOneNonDBGUse(RegNo: SrcReg)) {
2286	LLVM_DEBUG(dbgs() << "\t\tMultiple vreg uses!\n");
2287	return false;
2288	}
2289
2290	if (!LIS->intervalIsInOneMBB(LI: RHS)) {
2291	LLVM_DEBUG(dbgs() << "\t\tComplex control flow!\n");
2292	return false;
2293	}
2294
2295	MachineInstr &DestMI = *MRI->getVRegDef(Reg: SrcReg);
2296	CopyMI = &*MRI->use_instr_nodbg_begin(RegNo: SrcReg);
2297	SlotIndex CopyRegIdx = LIS->getInstructionIndex(Instr: *CopyMI).getRegSlot();
2298	SlotIndex DestRegIdx = LIS->getInstructionIndex(Instr: DestMI).getRegSlot();
2299
2300	if (!MRI->isConstantPhysReg(PhysReg: DstReg)) {
2301	// We checked above that there are no interfering defs of the physical
2302	// register. However, for this case, where we intend to move up the def of
2303	// the physical register, we also need to check for interfering uses.
2304	SlotIndexes *Indexes = LIS->getSlotIndexes();
2305	for (SlotIndex SI = Indexes->getNextNonNullIndex(Index: DestRegIdx);
2306	SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(Index: SI)) {
2307	MachineInstr *MI = LIS->getInstructionFromIndex(index: SI);
2308	if (MI->readsRegister(Reg: DstReg, TRI)) {
2309	LLVM_DEBUG(dbgs() << "\t\tInterference (read): " << *MI);
2310	return false;
2311	}
2312	}
2313	}
2314
2315	// We're going to remove the copy which defines a physical reserved
2316	// register, so remove its valno, etc.
2317	LLVM_DEBUG(dbgs() << "\t\tRemoving phys reg def of "
2318	<< printReg(DstReg, TRI) << " at " << CopyRegIdx << "\n");
2319
2320	LIS->removePhysRegDefAt(Reg: DstReg.asMCReg(), Pos: CopyRegIdx);
2321	deleteInstr(MI: CopyMI);
2322
2323	// Create a new dead def at the new def location.
2324	for (MCRegUnit Unit : TRI->regunits(Reg: DstReg)) {
2325	LiveRange &LR = LIS->getRegUnit(Unit);
2326	LR.createDeadDef(Def: DestRegIdx, VNIAlloc&: LIS->getVNInfoAllocator());
2327	}
2328	}
2329
2330	// We don't track kills for reserved registers.
2331	MRI->clearKillFlags(Reg: CP.getSrcReg());
2332
2333	return true;
2334	}
2335
2336	//===----------------------------------------------------------------------===//
2337	// Interference checking and interval joining
2338	//===----------------------------------------------------------------------===//
2339	//
2340	// In the easiest case, the two live ranges being joined are disjoint, and
2341	// there is no interference to consider. It is quite common, though, to have
2342	// overlapping live ranges, and we need to check if the interference can be
2343	// resolved.
2344	//
2345	// The live range of a single SSA value forms a sub-tree of the dominator tree.
2346	// This means that two SSA values overlap if and only if the def of one value
2347	// is contained in the live range of the other value. As a special case, the
2348	// overlapping values can be defined at the same index.
2349	//
2350	// The interference from an overlapping def can be resolved in these cases:
2351	//
2352	// 1. Coalescable copies. The value is defined by a copy that would become an
2353	// identity copy after joining SrcReg and DstReg. The copy instruction will
2354	// be removed, and the value will be merged with the source value.
2355	//
2356	// There can be several copies back and forth, causing many values to be
2357	// merged into one. We compute a list of ultimate values in the joined live
2358	// range as well as a mappings from the old value numbers.
2359	//
2360	// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI
2361	// predecessors have a live out value. It doesn't cause real interference,
2362	// and can be merged into the value it overlaps. Like a coalescable copy, it
2363	// can be erased after joining.
2364	//
2365	// 3. Copy of external value. The overlapping def may be a copy of a value that
2366	// is already in the other register. This is like a coalescable copy, but
2367	// the live range of the source register must be trimmed after erasing the
2368	// copy instruction:
2369	//
2370	// %src = COPY %ext
2371	// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext.
2372	//
2373	// 4. Clobbering undefined lanes. Vector registers are sometimes built by
2374	// defining one lane at a time:
2375	//
2376	// %dst:ssub0<def,read-undef> = FOO
2377	// %src = BAR
2378	// %dst:ssub1 = COPY %src
2379	//
2380	// The live range of %src overlaps the %dst value defined by FOO, but
2381	// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane
2382	// which was undef anyway.
2383	//
2384	// The value mapping is more complicated in this case. The final live range
2385	// will have different value numbers for both FOO and BAR, but there is no
2386	// simple mapping from old to new values. It may even be necessary to add
2387	// new PHI values.
2388	//
2389	// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that
2390	// is live, but never read. This can happen because we don't compute
2391	// individual live ranges per lane.
2392	//
2393	// %dst = FOO
2394	// %src = BAR
2395	// %dst:ssub1 = COPY %src
2396	//
2397	// This kind of interference is only resolved locally. If the clobbered
2398	// lane value escapes the block, the join is aborted.
2399
2400	namespace {
2401
2402	/// Track information about values in a single virtual register about to be
2403	/// joined. Objects of this class are always created in pairs - one for each
2404	/// side of the CoalescerPair (or one for each lane of a side of the coalescer
2405	/// pair)
2406	class JoinVals {
2407	/// Live range we work on.
2408	LiveRange &LR;
2409
2410	/// (Main) register we work on.
2411	const Register Reg;
2412
2413	/// Reg (and therefore the values in this liverange) will end up as
2414	/// subregister SubIdx in the coalesced register. Either CP.DstIdx or
2415	/// CP.SrcIdx.
2416	const unsigned SubIdx;
2417
2418	/// The LaneMask that this liverange will occupy the coalesced register. May
2419	/// be smaller than the lanemask produced by SubIdx when merging subranges.
2420	const LaneBitmask LaneMask;
2421
2422	/// This is true when joining sub register ranges, false when joining main
2423	/// ranges.
2424	const bool SubRangeJoin;
2425
2426	/// Whether the current LiveInterval tracks subregister liveness.
2427	const bool TrackSubRegLiveness;
2428
2429	/// Values that will be present in the final live range.
2430	SmallVectorImpl<VNInfo*> &NewVNInfo;
2431
2432	const CoalescerPair &CP;
2433	LiveIntervals *LIS;
2434	SlotIndexes *Indexes;
2435	const TargetRegisterInfo *TRI;
2436
2437	/// Value number assignments. Maps value numbers in LI to entries in
2438	/// NewVNInfo. This is suitable for passing to LiveInterval::join().
2439	SmallVector<int, 8> Assignments;
2440
2441	public:
2442	/// Conflict resolution for overlapping values.
2443	enum ConflictResolution {
2444	/// No overlap, simply keep this value.
2445	CR_Keep,
2446
2447	/// Merge this value into OtherVNI and erase the defining instruction.
2448	/// Used for IMPLICIT_DEF, coalescable copies, and copies from external
2449	/// values.
2450	CR_Erase,
2451
2452	/// Merge this value into OtherVNI but keep the defining instruction.
2453	/// This is for the special case where OtherVNI is defined by the same
2454	/// instruction.
2455	CR_Merge,
2456
2457	/// Keep this value, and have it replace OtherVNI where possible. This
2458	/// complicates value mapping since OtherVNI maps to two different values
2459	/// before and after this def.
2460	/// Used when clobbering undefined or dead lanes.
2461	CR_Replace,
2462
2463	/// Unresolved conflict. Visit later when all values have been mapped.
2464	CR_Unresolved,
2465
2466	/// Unresolvable conflict. Abort the join.
2467	CR_Impossible
2468	};
2469
2470	private:
2471	/// Per-value info for LI. The lane bit masks are all relative to the final
2472	/// joined register, so they can be compared directly between SrcReg and
2473	/// DstReg.
2474	struct Val {
2475	ConflictResolution Resolution = CR_Keep;
2476
2477	/// Lanes written by this def, 0 for unanalyzed values.
2478	LaneBitmask WriteLanes;
2479
2480	/// Lanes with defined values in this register. Other lanes are undef and
2481	/// safe to clobber.
2482	LaneBitmask ValidLanes;
2483
2484	/// Value in LI being redefined by this def.
2485	VNInfo *RedefVNI = nullptr;
2486
2487	/// Value in the other live range that overlaps this def, if any.
2488	VNInfo *OtherVNI = nullptr;
2489
2490	/// Is this value an IMPLICIT_DEF that can be erased?
2491	///
2492	/// IMPLICIT_DEF values should only exist at the end of a basic block that
2493	/// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
2494	/// safely erased if they are overlapping a live value in the other live
2495	/// interval.
2496	///
2497	/// Weird control flow graphs and incomplete PHI handling in
2498	/// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with
2499	/// longer live ranges. Such IMPLICIT_DEF values should be treated like
2500	/// normal values.
2501	bool ErasableImplicitDef = false;
2502
2503	/// True when the live range of this value will be pruned because of an
2504	/// overlapping CR_Replace value in the other live range.
2505	bool Pruned = false;
2506
2507	/// True once Pruned above has been computed.
2508	bool PrunedComputed = false;
2509
2510	/// True if this value is determined to be identical to OtherVNI
2511	/// (in valuesIdentical). This is used with CR_Erase where the erased
2512	/// copy is redundant, i.e. the source value is already the same as
2513	/// the destination. In such cases the subranges need to be updated
2514	/// properly. See comment at pruneSubRegValues for more info.
2515	bool Identical = false;
2516
2517	Val() = default;
2518
2519	bool isAnalyzed() const { return WriteLanes.any(); }
2520
2521	/// Mark this value as an IMPLICIT_DEF which must be kept as if it were an
2522	/// ordinary value.
2523	void mustKeepImplicitDef(const TargetRegisterInfo &TRI,
2524	const MachineInstr &ImpDef) {
2525	assert(ImpDef.isImplicitDef());
2526	ErasableImplicitDef = false;
2527	ValidLanes = TRI.getSubRegIndexLaneMask(SubIdx: ImpDef.getOperand(i: 0).getSubReg());
2528	}
2529	};
2530
2531	/// One entry per value number in LI.
2532	SmallVector<Val, 8> Vals;
2533
2534	/// Compute the bitmask of lanes actually written by DefMI.
2535	/// Set Redef if there are any partial register definitions that depend on the
2536	/// previous value of the register.
2537	LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
2538
2539	/// Find the ultimate value that VNI was copied from.
2540	std::pair<const VNInfo *, Register> followCopyChain(const VNInfo *VNI) const;
2541
2542	bool valuesIdentical(VNInfo *Value0, VNInfo *Value1, const JoinVals &Other) const;
2543
2544	/// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
2545	/// Return a conflict resolution when possible, but leave the hard cases as
2546	/// CR_Unresolved.
2547	/// Recursively calls computeAssignment() on this and Other, guaranteeing that
2548	/// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
2549	/// The recursion always goes upwards in the dominator tree, making loops
2550	/// impossible.
2551	ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
2552
2553	/// Compute the value assignment for ValNo in RI.
2554	/// This may be called recursively by analyzeValue(), but never for a ValNo on
2555	/// the stack.
2556	void computeAssignment(unsigned ValNo, JoinVals &Other);
2557
2558	/// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute
2559	/// the extent of the tainted lanes in the block.
2560	///
2561	/// Multiple values in Other.LR can be affected since partial redefinitions
2562	/// can preserve previously tainted lanes.
2563	///
2564	/// 1 %dst = VLOAD <-- Define all lanes in %dst
2565	/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0
2566	/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0
2567	/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
2568	///
2569	/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)
2570	/// entry to TaintedVals.
2571	///
2572	/// Returns false if the tainted lanes extend beyond the basic block.
2573	bool
2574	taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2575	SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);
2576
2577	/// Return true if MI uses any of the given Lanes from Reg.
2578	/// This does not include partial redefinitions of Reg.
2579	bool usesLanes(const MachineInstr &MI, Register, unsigned, LaneBitmask) const;
2580
2581	/// Determine if ValNo is a copy of a value number in LR or Other.LR that will
2582	/// be pruned:
2583	///
2584	/// %dst = COPY %src
2585	/// %src = COPY %dst <-- This value to be pruned.
2586	/// %dst = COPY %src <-- This value is a copy of a pruned value.
2587	bool isPrunedValue(unsigned ValNo, JoinVals &Other);
2588
2589	public:
2590	JoinVals(LiveRange &LR, Register Reg, unsigned SubIdx, LaneBitmask LaneMask,
2591	SmallVectorImpl<VNInfo *> &newVNInfo, const CoalescerPair &cp,
2592	LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
2593	bool TrackSubRegLiveness)
2594	: LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2595	SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2596	NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2597	TRI(TRI), Assignments(LR.getNumValNums(), -1),
2598	Vals(LR.getNumValNums()) {}
2599
2600	/// Analyze defs in LR and compute a value mapping in NewVNInfo.
2601	/// Returns false if any conflicts were impossible to resolve.
2602	bool mapValues(JoinVals &Other);
2603
2604	/// Try to resolve conflicts that require all values to be mapped.
2605	/// Returns false if any conflicts were impossible to resolve.
2606	bool resolveConflicts(JoinVals &Other);
2607
2608	/// Prune the live range of values in Other.LR where they would conflict with
2609	/// CR_Replace values in LR. Collect end points for restoring the live range
2610	/// after joining.
2611	void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
2612	bool changeInstrs);
2613
2614	/// Removes subranges starting at copies that get removed. This sometimes
2615	/// happens when undefined subranges are copied around. These ranges contain
2616	/// no useful information and can be removed.
2617	void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
2618
2619	/// Pruning values in subranges can lead to removing segments in these
2620	/// subranges started by IMPLICIT_DEFs. The corresponding segments in
2621	/// the main range also need to be removed. This function will mark
2622	/// the corresponding values in the main range as pruned, so that
2623	/// eraseInstrs can do the final cleanup.
2624	/// The parameter @p LI must be the interval whose main range is the
2625	/// live range LR.
2626	void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);
2627
2628	/// Erase any machine instructions that have been coalesced away.
2629	/// Add erased instructions to ErasedInstrs.
2630	/// Add foreign virtual registers to ShrinkRegs if their live range ended at
2631	/// the erased instrs.
2632	void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2633	SmallVectorImpl<Register> &ShrinkRegs,
2634	LiveInterval *LI = nullptr);
2635
2636	/// Remove liverange defs at places where implicit defs will be removed.
2637	void removeImplicitDefs();
2638
2639	/// Get the value assignments suitable for passing to LiveInterval::join.
2640	const int *getAssignments() const { return Assignments.data(); }
2641
2642	/// Get the conflict resolution for a value number.
2643	ConflictResolution getResolution(unsigned Num) const {
2644	return Vals[Num].Resolution;
2645	}
2646	};
2647
2648	} // end anonymous namespace
2649
2650	LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef)
2651	const {
2652	LaneBitmask L;
2653	for (const MachineOperand &MO : DefMI->all_defs()) {
2654	if (MO.getReg() != Reg)
2655	continue;
2656	L |= TRI->getSubRegIndexLaneMask(
2657	SubIdx: TRI->composeSubRegIndices(a: SubIdx, b: MO.getSubReg()));
2658	if (MO.readsReg())
2659	Redef = true;
2660	}
2661	return L;
2662	}
2663
2664	std::pair<const VNInfo *, Register>
2665	JoinVals::followCopyChain(const VNInfo *VNI) const {
2666	Register TrackReg = Reg;
2667
2668	while (!VNI->isPHIDef()) {
2669	SlotIndex Def = VNI->def;
2670	MachineInstr *MI = Indexes->getInstructionFromIndex(index: Def);
2671	assert(MI && "No defining instruction");
2672	if (!MI->isFullCopy())
2673	return std::make_pair(x&: VNI, y&: TrackReg);
2674	Register SrcReg = MI->getOperand(i: 1).getReg();
2675	if (!SrcReg.isVirtual())
2676	return std::make_pair(x&: VNI, y&: TrackReg);
2677
2678	const LiveInterval &LI = LIS->getInterval(Reg: SrcReg);
2679	const VNInfo *ValueIn;
2680	// No subrange involved.
2681	if (!SubRangeJoin || !LI.hasSubRanges()) {
2682	LiveQueryResult LRQ = LI.Query(Idx: Def);
2683	ValueIn = LRQ.valueIn();
2684	} else {
2685	// Query subranges. Ensure that all matching ones take us to the same def
2686	// (allowing some of them to be undef).
2687	ValueIn = nullptr;
2688	for (const LiveInterval::SubRange &S : LI.subranges()) {
2689	// Transform lanemask to a mask in the joined live interval.
2690	LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(IdxA: SubIdx, Mask: S.LaneMask);
2691	if ((SMask & LaneMask).none())
2692	continue;
2693	LiveQueryResult LRQ = S.Query(Idx: Def);
2694	if (!ValueIn) {
2695	ValueIn = LRQ.valueIn();
2696	continue;
2697	}
2698	if (LRQ.valueIn() && ValueIn != LRQ.valueIn())
2699	return std::make_pair(x&: VNI, y&: TrackReg);
2700	}
2701	}
2702	if (ValueIn == nullptr) {
2703	// Reaching an undefined value is legitimate, for example:
2704	//
2705	// 1 undef %0.sub1 = ... ;; %0.sub0 == undef
2706	// 2 %1 = COPY %0 ;; %1 is defined here.
2707	// 3 %0 = COPY %1 ;; Now %0.sub0 has a definition,
2708	// ;; but it's equivalent to "undef".
2709	return std::make_pair(x: nullptr, y&: SrcReg);
2710	}
2711	VNI = ValueIn;
2712	TrackReg = SrcReg;
2713	}
2714	return std::make_pair(x&: VNI, y&: TrackReg);
2715	}
2716
2717	bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2718	const JoinVals &Other) const {
2719	const VNInfo *Orig0;
2720	Register Reg0;
2721	std::tie(args&: Orig0, args&: Reg0) = followCopyChain(VNI: Value0);
2722	if (Orig0 == Value1 && Reg0 == Other.Reg)
2723	return true;
2724
2725	const VNInfo *Orig1;
2726	Register Reg1;
2727	std::tie(args&: Orig1, args&: Reg1) = Other.followCopyChain(VNI: Value1);
2728	// If both values are undefined, and the source registers are the same
2729	// register, the values are identical. Filter out cases where only one
2730	// value is defined.
2731	if (Orig0 == nullptr || Orig1 == nullptr)
2732	return Orig0 == Orig1 && Reg0 == Reg1;
2733
2734	// The values are equal if they are defined at the same place and use the
2735	// same register. Note that we cannot compare VNInfos directly as some of
2736	// them might be from a copy created in mergeSubRangeInto() while the other
2737	// is from the original LiveInterval.
2738	return Orig0->def == Orig1->def && Reg0 == Reg1;
2739	}
2740
2741	JoinVals::ConflictResolution
2742	JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
2743	Val &V = Vals[ValNo];
2744	assert(!V.isAnalyzed() && "Value has already been analyzed!");
2745	VNInfo *VNI = LR.getValNumInfo(ValNo);
2746	if (VNI->isUnused()) {
2747	V.WriteLanes = LaneBitmask::getAll();
2748	return CR_Keep;
2749	}
2750
2751	// Get the instruction defining this value, compute the lanes written.
2752	const MachineInstr *DefMI = nullptr;
2753	if (VNI->isPHIDef()) {
2754	// Conservatively assume that all lanes in a PHI are valid.
2755	LaneBitmask Lanes = SubRangeJoin ? LaneBitmask::getLane(Lane: 0)
2756	: TRI->getSubRegIndexLaneMask(SubIdx);
2757	V.ValidLanes = V.WriteLanes = Lanes;
2758	} else {
2759	DefMI = Indexes->getInstructionFromIndex(index: VNI->def);
2760	assert(DefMI != nullptr);
2761	if (SubRangeJoin) {
2762	// We don't care about the lanes when joining subregister ranges.
2763	V.WriteLanes = V.ValidLanes = LaneBitmask::getLane(Lane: 0);
2764	if (DefMI->isImplicitDef()) {
2765	V.ValidLanes = LaneBitmask::getNone();
2766	V.ErasableImplicitDef = true;
2767	}
2768	} else {
2769	bool Redef = false;
2770	V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
2771
2772	// If this is a read-modify-write instruction, there may be more valid
2773	// lanes than the ones written by this instruction.
2774	// This only covers partial redef operands. DefMI may have normal use
2775	// operands reading the register. They don't contribute valid lanes.
2776	//
2777	// This adds ssub1 to the set of valid lanes in %src:
2778	//
2779	// %src:ssub1 = FOO
2780	//
2781	// This leaves only ssub1 valid, making any other lanes undef:
2782	//
2783	// %src:ssub1<def,read-undef> = FOO %src:ssub2
2784	//
2785	// The <read-undef> flag on the def operand means that old lane values are
2786	// not important.
2787	if (Redef) {
2788	V.RedefVNI = LR.Query(Idx: VNI->def).valueIn();
2789	assert((TrackSubRegLiveness || V.RedefVNI) &&
2790	"Instruction is reading nonexistent value");
2791	if (V.RedefVNI != nullptr) {
2792	computeAssignment(ValNo: V.RedefVNI->id, Other);
2793	V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
2794	}
2795	}
2796
2797	// An IMPLICIT_DEF writes undef values.
2798	if (DefMI->isImplicitDef()) {
2799	// We normally expect IMPLICIT_DEF values to be live only until the end
2800	// of their block. If the value is really live longer and gets pruned in
2801	// another block, this flag is cleared again.
2802	//
2803	// Clearing the valid lanes is deferred until it is sure this can be
2804	// erased.
2805	V.ErasableImplicitDef = true;
2806	}
2807	}
2808	}
2809
2810	// Find the value in Other that overlaps VNI->def, if any.
2811	LiveQueryResult OtherLRQ = Other.LR.Query(Idx: VNI->def);
2812
2813	// It is possible that both values are defined by the same instruction, or
2814	// the values are PHIs defined in the same block. When that happens, the two
2815	// values should be merged into one, but not into any preceding value.
2816	// The first value defined or visited gets CR_Keep, the other gets CR_Merge.
2817	if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {
2818	assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ");
2819
2820	// One value stays, the other is merged. Keep the earlier one, or the first
2821	// one we see.
2822	if (OtherVNI->def < VNI->def)
2823	Other.computeAssignment(ValNo: OtherVNI->id, Other&: *this);
2824	else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
2825	// This is an early-clobber def overlapping a live-in value in the other
2826	// register. Not mergeable.
2827	V.OtherVNI = OtherLRQ.valueIn();
2828	return CR_Impossible;
2829	}
2830	V.OtherVNI = OtherVNI;
2831	Val &OtherV = Other.Vals[OtherVNI->id];
2832	// Keep this value, check for conflicts when analyzing OtherVNI. Avoid
2833	// revisiting OtherVNI->id in JoinVals::computeAssignment() below before it
2834	// is assigned.
2835	if (!OtherV.isAnalyzed() || Other.Assignments[OtherVNI->id] == -1)
2836	return CR_Keep;
2837	// Both sides have been analyzed now.
2838	// Allow overlapping PHI values. Any real interference would show up in a
2839	// predecessor, the PHI itself can't introduce any conflicts.
2840	if (VNI->isPHIDef())
2841	return CR_Merge;
2842	if ((V.ValidLanes & OtherV.ValidLanes).any())
2843	// Overlapping lanes can't be resolved.
2844	return CR_Impossible;
2845	else
2846	return CR_Merge;
2847	}
2848
2849	// No simultaneous def. Is Other live at the def?
2850	V.OtherVNI = OtherLRQ.valueIn();
2851	if (!V.OtherVNI)
2852	// No overlap, no conflict.
2853	return CR_Keep;
2854
2855	assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ");
2856
2857	// We have overlapping values, or possibly a kill of Other.
2858	// Recursively compute assignments up the dominator tree.
2859	Other.computeAssignment(ValNo: V.OtherVNI->id, Other&: *this);
2860	Val &OtherV = Other.Vals[V.OtherVNI->id];
2861
2862	if (OtherV.ErasableImplicitDef) {
2863	// Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block.
2864	// This shouldn't normally happen, but ProcessImplicitDefs can leave such
2865	// IMPLICIT_DEF instructions behind, and there is nothing wrong with it
2866	// technically.
2867	//
2868	// When it happens, treat that IMPLICIT_DEF as a normal value, and don't try
2869	// to erase the IMPLICIT_DEF instruction.
2870	//
2871	// Additionally we must keep an IMPLICIT_DEF if we're redefining an incoming
2872	// value.
2873
2874	MachineInstr *OtherImpDef =
2875	Indexes->getInstructionFromIndex(index: V.OtherVNI->def);
2876	MachineBasicBlock *OtherMBB = OtherImpDef->getParent();
2877	if (DefMI &&
2878	(DefMI->getParent() != OtherMBB || LIS->isLiveInToMBB(LR, mbb: OtherMBB))) {
2879	LLVM_DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2880	<< " extends into "
2881	<< printMBBReference(*DefMI->getParent())
2882	<< ", keeping it.\n");
2883	OtherV.mustKeepImplicitDef(TRI: *TRI, ImpDef: *OtherImpDef);
2884	} else if (OtherMBB->hasEHPadSuccessor()) {
2885	// If OtherV is defined in a basic block that has EH pad successors then
2886	// we get the same problem not just if OtherV is live beyond its basic
2887	// block, but beyond the last call instruction in its basic block. Handle
2888	// this case conservatively.
2889	LLVM_DEBUG(
2890	dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2891	<< " may be live into EH pad successors, keeping it.\n");
2892	OtherV.mustKeepImplicitDef(TRI: *TRI, ImpDef: *OtherImpDef);
2893	} else {
2894	// We deferred clearing these lanes in case we needed to save them
2895	OtherV.ValidLanes &= ~OtherV.WriteLanes;
2896	}
2897	}
2898
2899	// Allow overlapping PHI values. Any real interference would show up in a
2900	// predecessor, the PHI itself can't introduce any conflicts.
2901	if (VNI->isPHIDef())
2902	return CR_Replace;
2903
2904	// Check for simple erasable conflicts.
2905	if (DefMI->isImplicitDef())
2906	return CR_Erase;
2907
2908	// Include the non-conflict where DefMI is a coalescable copy that kills
2909	// OtherVNI. We still want the copy erased and value numbers merged.
2910	if (CP.isCoalescable(MI: DefMI)) {
2911	// Some of the lanes copied from OtherVNI may be undef, making them undef
2912	// here too.
2913	V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2914	return CR_Erase;
2915	}
2916
2917	// This may not be a real conflict if DefMI simply kills Other and defines
2918	// VNI.
2919	if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
2920	return CR_Keep;
2921
2922	// Handle the case where VNI and OtherVNI can be proven to be identical:
2923	//
2924	// %other = COPY %ext
2925	// %this = COPY %ext <-- Erase this copy
2926	//
2927	if (DefMI->isFullCopy() && !CP.isPartial() &&
2928	valuesIdentical(Value0: VNI, Value1: V.OtherVNI, Other)) {
2929	V.Identical = true;
2930	return CR_Erase;
2931	}
2932
2933	// The remaining checks apply to the lanes, which aren't tracked here. This
2934	// was already decided to be OK via the following CR_Replace condition.
2935	// CR_Replace.
2936	if (SubRangeJoin)
2937	return CR_Replace;
2938
2939	// If the lanes written by this instruction were all undef in OtherVNI, it is
2940	// still safe to join the live ranges. This can't be done with a simple value
2941	// mapping, though - OtherVNI will map to multiple values:
2942	//
2943	// 1 %dst:ssub0 = FOO <-- OtherVNI
2944	// 2 %src = BAR <-- VNI
2945	// 3 %dst:ssub1 = COPY killed %src <-- Eliminate this copy.
2946	// 4 BAZ killed %dst
2947	// 5 QUUX killed %src
2948	//
2949	// Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace
2950	// handles this complex value mapping.
2951	if ((V.WriteLanes & OtherV.ValidLanes).none())
2952	return CR_Replace;
2953
2954	// If the other live range is killed by DefMI and the live ranges are still
2955	// overlapping, it must be because we're looking at an early clobber def:
2956	//
2957	// %dst<def,early-clobber> = ASM killed %src
2958	//
2959	// In this case, it is illegal to merge the two live ranges since the early
2960	// clobber def would clobber %src before it was read.
2961	if (OtherLRQ.isKill()) {
2962	// This case where the def doesn't overlap the kill is handled above.
2963	assert(VNI->def.isEarlyClobber() &&
2964	"Only early clobber defs can overlap a kill");
2965	return CR_Impossible;
2966	}
2967
2968	// VNI is clobbering live lanes in OtherVNI, but there is still the
2969	// possibility that no instructions actually read the clobbered lanes.
2970	// If we're clobbering all the lanes in OtherVNI, at least one must be read.
2971	// Otherwise Other.RI wouldn't be live here.
2972	if ((TRI->getSubRegIndexLaneMask(SubIdx: Other.SubIdx) & ~V.WriteLanes).none())
2973	return CR_Impossible;
2974
2975	if (TrackSubRegLiveness) {
2976	auto &OtherLI = LIS->getInterval(Reg: Other.Reg);
2977	// If OtherVNI does not have subranges, it means all the lanes of OtherVNI
2978	// share the same live range, so we just need to check whether they have
2979	// any conflict bit in their LaneMask.
2980	if (!OtherLI.hasSubRanges()) {
2981	LaneBitmask OtherMask = TRI->getSubRegIndexLaneMask(SubIdx: Other.SubIdx);
2982	return (OtherMask & V.WriteLanes).none() ? CR_Replace : CR_Impossible;
2983	}
2984
2985	// If we are clobbering some active lanes of OtherVNI at VNI->def, it is
2986	// impossible to resolve the conflict. Otherwise, we can just replace
2987	// OtherVNI because of no real conflict.
2988	for (LiveInterval::SubRange &OtherSR : OtherLI.subranges()) {
2989	LaneBitmask OtherMask =
2990	TRI->composeSubRegIndexLaneMask(IdxA: Other.SubIdx, Mask: OtherSR.LaneMask);
2991	if ((OtherMask & V.WriteLanes).none())
2992	continue;
2993
2994	auto OtherSRQ = OtherSR.Query(Idx: VNI->def);
2995	if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->def) {
2996	// VNI is clobbering some lanes of OtherVNI, they have real conflict.
2997	return CR_Impossible;
2998	}
2999	}
3000
3001	// VNI is NOT clobbering any lane of OtherVNI, just replace OtherVNI.
3002	return CR_Replace;
3003	}
3004
3005	// We need to verify that no instructions are reading the clobbered lanes.
3006	// To save compile time, we'll only check that locally. Don't allow the
3007	// tainted value to escape the basic block.
3008	MachineBasicBlock *MBB = Indexes->getMBBFromIndex(index: VNI->def);
3009	if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(mbb: MBB))
3010	return CR_Impossible;
3011
3012	// There are still some things that could go wrong besides clobbered lanes
3013	// being read, for example OtherVNI may be only partially redefined in MBB,
3014	// and some clobbered lanes could escape the block. Save this analysis for
3015	// resolveConflicts() when all values have been mapped. We need to know
3016	// RedefVNI and WriteLanes for any later defs in MBB, and we can't compute
3017	// that now - the recursive analyzeValue() calls must go upwards in the
3018	// dominator tree.
3019	return CR_Unresolved;
3020	}
3021
3022	void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
3023	Val &V = Vals[ValNo];
3024	if (V.isAnalyzed()) {
3025	// Recursion should always move up the dominator tree, so ValNo is not
3026	// supposed to reappear before it has been assigned.
3027	assert(Assignments[ValNo] != -1 && "Bad recursion?");
3028	return;
3029	}
3030	switch ((V.Resolution = analyzeValue(ValNo, Other))) {
3031	case CR_Erase:
3032	case CR_Merge:
3033	// Merge this ValNo into OtherVNI.
3034	assert(V.OtherVNI && "OtherVNI not assigned, can't merge.");
3035	assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");
3036	Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
3037	LLVM_DEBUG(dbgs() << "\t\tmerge " << printReg(Reg) << ':' << ValNo << '@'
3038	<< LR.getValNumInfo(ValNo)->def << " into "
3039	<< printReg(Other.Reg) << ':' << V.OtherVNI->id << '@'
3040	<< V.OtherVNI->def << " --> @"
3041	<< NewVNInfo[Assignments[ValNo]]->def << '\n');
3042	break;
3043	case CR_Replace:
3044	case CR_Unresolved: {
3045	// The other value is going to be pruned if this join is successful.
3046	assert(V.OtherVNI && "OtherVNI not assigned, can't prune");
3047	Val &OtherV = Other.Vals[V.OtherVNI->id];
3048	OtherV.Pruned = true;
3049	[[fallthrough]];
3050	}
3051	default:
3052	// This value number needs to go in the final joined live range.
3053	Assignments[ValNo] = NewVNInfo.size();
3054	NewVNInfo.push_back(Elt: LR.getValNumInfo(ValNo));
3055	break;
3056	}
3057	}
3058
3059	bool JoinVals::mapValues(JoinVals &Other) {
3060	for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3061	computeAssignment(ValNo: i, Other);
3062	if (Vals[i].Resolution == CR_Impossible) {
3063	LLVM_DEBUG(dbgs() << "\t\tinterference at " << printReg(Reg) << ':' << i
3064	<< '@' << LR.getValNumInfo(i)->def << '\n');
3065	return false;
3066	}
3067	}
3068	return true;
3069	}
3070
3071	bool JoinVals::
3072	taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
3073	SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent) {
3074	VNInfo *VNI = LR.getValNumInfo(ValNo);
3075	MachineBasicBlock *MBB = Indexes->getMBBFromIndex(index: VNI->def);
3076	SlotIndex MBBEnd = Indexes->getMBBEndIdx(mbb: MBB);
3077
3078	// Scan Other.LR from VNI.def to MBBEnd.
3079	LiveInterval::iterator OtherI = Other.LR.find(Pos: VNI->def);
3080	assert(OtherI != Other.LR.end() && "No conflict?");
3081	do {
3082	// OtherI is pointing to a tainted value. Abort the join if the tainted
3083	// lanes escape the block.
3084	SlotIndex End = OtherI->end;
3085	if (End >= MBBEnd) {
3086	LLVM_DEBUG(dbgs() << "\t\ttaints global " << printReg(Other.Reg) << ':'
3087	<< OtherI->valno->id << '@' << OtherI->start << '\n');
3088	return false;
3089	}
3090	LLVM_DEBUG(dbgs() << "\t\ttaints local " << printReg(Other.Reg) << ':'
3091	<< OtherI->valno->id << '@' << OtherI->start << " to "
3092	<< End << '\n');
3093	// A dead def is not a problem.
3094	if (End.isDead())
3095	break;
3096	TaintExtent.push_back(Elt: std::make_pair(x&: End, y&: TaintedLanes));
3097
3098	// Check for another def in the MBB.
3099	if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
3100	break;
3101
3102	// Lanes written by the new def are no longer tainted.
3103	const Val &OV = Other.Vals[OtherI->valno->id];
3104	TaintedLanes &= ~OV.WriteLanes;
3105	if (!OV.RedefVNI)
3106	break;
3107	} while (TaintedLanes.any());
3108	return true;
3109	}
3110
3111	bool JoinVals::usesLanes(const MachineInstr &MI, Register Reg, unsigned SubIdx,
3112	LaneBitmask Lanes) const {
3113	if (MI.isDebugOrPseudoInstr())
3114	return false;
3115	for (const MachineOperand &MO : MI.all_uses()) {
3116	if (MO.getReg() != Reg)
3117	continue;
3118	if (!MO.readsReg())
3119	continue;
3120	unsigned S = TRI->composeSubRegIndices(a: SubIdx, b: MO.getSubReg());
3121	if ((Lanes & TRI->getSubRegIndexLaneMask(SubIdx: S)).any())
3122	return true;
3123	}
3124	return false;
3125	}
3126
3127	bool JoinVals::resolveConflicts(JoinVals &Other) {
3128	for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3129	Val &V = Vals[i];
3130	assert(V.Resolution != CR_Impossible && "Unresolvable conflict");
3131	if (V.Resolution != CR_Unresolved)
3132	continue;
3133	LLVM_DEBUG(dbgs() << "\t\tconflict at " << printReg(Reg) << ':' << i << '@'
3134	<< LR.getValNumInfo(i)->def
3135	<< ' ' << PrintLaneMask(LaneMask) << '\n');
3136	if (SubRangeJoin)
3137	return false;
3138
3139	++NumLaneConflicts;
3140	assert(V.OtherVNI && "Inconsistent conflict resolution.");
3141	VNInfo *VNI = LR.getValNumInfo(ValNo: i);
3142	const Val &OtherV = Other.Vals[V.OtherVNI->id];
3143
3144	// VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
3145	// join, those lanes will be tainted with a wrong value. Get the extent of
3146	// the tainted lanes.
3147	LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
3148	SmallVector<std::pair<SlotIndex, LaneBitmask>, 8> TaintExtent;
3149	if (!taintExtent(ValNo: i, TaintedLanes, Other, TaintExtent))
3150	// Tainted lanes would extend beyond the basic block.
3151	return false;
3152
3153	assert(!TaintExtent.empty() && "There should be at least one conflict.");
3154
3155	// Now look at the instructions from VNI->def to TaintExtent (inclusive).
3156	MachineBasicBlock *MBB = Indexes->getMBBFromIndex(index: VNI->def);
3157	MachineBasicBlock::iterator MI = MBB->begin();
3158	if (!VNI->isPHIDef()) {
3159	MI = Indexes->getInstructionFromIndex(index: VNI->def);
3160	if (!VNI->def.isEarlyClobber()) {
3161	// No need to check the instruction defining VNI for reads.
3162	++MI;
3163	}
3164	}
3165	assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&
3166	"Interference ends on VNI->def. Should have been handled earlier");
3167	MachineInstr *LastMI =
3168	Indexes->getInstructionFromIndex(index: TaintExtent.front().first);
3169	assert(LastMI && "Range must end at a proper instruction");
3170	unsigned TaintNum = 0;
3171	while (true) {
3172	assert(MI != MBB->end() && "Bad LastMI");
3173	if (usesLanes(MI: *MI, Reg: Other.Reg, SubIdx: Other.SubIdx, Lanes: TaintedLanes)) {
3174	LLVM_DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI);
3175	return false;
3176	}
3177	// LastMI is the last instruction to use the current value.
3178	if (&*MI == LastMI) {
3179	if (++TaintNum == TaintExtent.size())
3180	break;
3181	LastMI = Indexes->getInstructionFromIndex(index: TaintExtent[TaintNum].first);
3182	assert(LastMI && "Range must end at a proper instruction");
3183	TaintedLanes = TaintExtent[TaintNum].second;
3184	}
3185	++MI;
3186	}
3187
3188	// The tainted lanes are unused.
3189	V.Resolution = CR_Replace;
3190	++NumLaneResolves;
3191	}
3192	return true;
3193	}
3194
3195	bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
3196	Val &V = Vals[ValNo];
3197	if (V.Pruned || V.PrunedComputed)
3198	return V.Pruned;
3199
3200	if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
3201	return V.Pruned;
3202
3203	// Follow copies up the dominator tree and check if any intermediate value
3204	// has been pruned.
3205	V.PrunedComputed = true;
3206	V.Pruned = Other.isPrunedValue(ValNo: V.OtherVNI->id, Other&: *this);
3207	return V.Pruned;
3208	}
3209
3210	void JoinVals::pruneValues(JoinVals &Other,
3211	SmallVectorImpl<SlotIndex> &EndPoints,
3212	bool changeInstrs) {
3213	for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3214	SlotIndex Def = LR.getValNumInfo(ValNo: i)->def;
3215	switch (Vals[i].Resolution) {
3216	case CR_Keep:
3217	break;
3218	case CR_Replace: {
3219	// This value takes precedence over the value in Other.LR.
3220	LIS->pruneValue(LR&: Other.LR, Kill: Def, EndPoints: &EndPoints);
3221	// Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF
3222	// instructions are only inserted to provide a live-out value for PHI
3223	// predecessors, so the instruction should simply go away once its value
3224	// has been replaced.
3225	Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
3226	bool EraseImpDef = OtherV.ErasableImplicitDef &&
3227	OtherV.Resolution == CR_Keep;
3228	if (!Def.isBlock()) {
3229	if (changeInstrs) {
3230	// Remove <def,read-undef> flags. This def is now a partial redef.
3231	// Also remove dead flags since the joined live range will
3232	// continue past this instruction.
3233	for (MachineOperand &MO :
3234	Indexes->getInstructionFromIndex(index: Def)->operands()) {
3235	if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
3236	if (MO.getSubReg() != 0 && MO.isUndef() && !EraseImpDef)
3237	MO.setIsUndef(false);
3238	MO.setIsDead(false);
3239	}
3240	}
3241	}
3242	// This value will reach instructions below, but we need to make sure
3243	// the live range also reaches the instruction at Def.
3244	if (!EraseImpDef)
3245	EndPoints.push_back(Elt: Def);
3246	}
3247	LLVM_DEBUG(dbgs() << "\t\tpruned " << printReg(Other.Reg) << " at " << Def
3248	<< ": " << Other.LR << '\n');
3249	break;
3250	}
3251	case CR_Erase:
3252	case CR_Merge:
3253	if (isPrunedValue(ValNo: i, Other)) {
3254	// This value is ultimately a copy of a pruned value in LR or Other.LR.
3255	// We can no longer trust the value mapping computed by
3256	// computeAssignment(), the value that was originally copied could have
3257	// been replaced.
3258	LIS->pruneValue(LR, Kill: Def, EndPoints: &EndPoints);
3259	LLVM_DEBUG(dbgs() << "\t\tpruned all of " << printReg(Reg) << " at "
3260	<< Def << ": " << LR << '\n');
3261	}
3262	break;
3263	case CR_Unresolved:
3264	case CR_Impossible:
3265	llvm_unreachable("Unresolved conflicts");
3266	}
3267	}
3268	}
3269
3270	// Check if the segment consists of a copied live-through value (i.e. the copy
3271	// in the block only extended the liveness, of an undef value which we may need
3272	// to handle).
3273	static bool isLiveThrough(const LiveQueryResult Q) {
3274	return Q.valueIn() && Q.valueIn()->isPHIDef() && Q.valueIn() == Q.valueOut();
3275	}
3276
3277	/// Consider the following situation when coalescing the copy between
3278	/// %31 and %45 at 800. (The vertical lines represent live range segments.)
3279	///
3280	/// Main range Subrange 0004 (sub2)
3281	/// %31 %45 %31 %45
3282	/// 544 %45 = COPY %28 + +
3283	/// | v1 | v1
3284	/// 560B bb.1: + +
3285	/// 624 = %45.sub2 | v2 | v2
3286	/// 800 %31 = COPY %45 + + + +
3287	/// | v0 | v0
3288	/// 816 %31.sub1 = ... + |
3289	/// 880 %30 = COPY %31 | v1 +
3290	/// 928 %45 = COPY %30 | + +
3291	/// | | v0 | v0 <--+
3292	/// 992B ; backedge -> bb.1 | + + |
3293	/// 1040 = %31.sub0 + |
3294	/// This value must remain
3295	/// live-out!
3296	///
3297	/// Assuming that %31 is coalesced into %45, the copy at 928 becomes
3298	/// redundant, since it copies the value from %45 back into it. The
3299	/// conflict resolution for the main range determines that %45.v0 is
3300	/// to be erased, which is ok since %31.v1 is identical to it.
3301	/// The problem happens with the subrange for sub2: it has to be live
3302	/// on exit from the block, but since 928 was actually a point of
3303	/// definition of %45.sub2, %45.sub2 was not live immediately prior
3304	/// to that definition. As a result, when 928 was erased, the value v0
3305	/// for %45.sub2 was pruned in pruneSubRegValues. Consequently, an
3306	/// IMPLICIT_DEF was inserted as a "backedge" definition for %45.sub2,
3307	/// providing an incorrect value to the use at 624.
3308	///
3309	/// Since the main-range values %31.v1 and %45.v0 were proved to be
3310	/// identical, the corresponding values in subranges must also be the
3311	/// same. A redundant copy is removed because it's not needed, and not
3312	/// because it copied an undefined value, so any liveness that originated
3313	/// from that copy cannot disappear. When pruning a value that started
3314	/// at the removed copy, the corresponding identical value must be
3315	/// extended to replace it.
3316	void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
3317	// Look for values being erased.
3318	bool DidPrune = false;
3319	for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3320	Val &V = Vals[i];
3321	// We should trigger in all cases in which eraseInstrs() does something.
3322	// match what eraseInstrs() is doing, print a message so
3323	if (V.Resolution != CR_Erase &&
3324	(V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned))
3325	continue;
3326
3327	// Check subranges at the point where the copy will be removed.
3328	SlotIndex Def = LR.getValNumInfo(ValNo: i)->def;
3329	SlotIndex OtherDef;
3330	if (V.Identical)
3331	OtherDef = V.OtherVNI->def;
3332
3333	// Print message so mismatches with eraseInstrs() can be diagnosed.
3334	LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def
3335	<< '\n');
3336	for (LiveInterval::SubRange &S : LI.subranges()) {
3337	LiveQueryResult Q = S.Query(Idx: Def);
3338
3339	// If a subrange starts at the copy then an undefined value has been
3340	// copied and we must remove that subrange value as well.
3341	VNInfo *ValueOut = Q.valueOutOrDead();
3342	if (ValueOut != nullptr && (Q.valueIn() == nullptr ||
3343	(V.Identical && V.Resolution == CR_Erase &&
3344	ValueOut->def == Def))) {
3345	LLVM_DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)
3346	<< " at " << Def << "\n");
3347	SmallVector<SlotIndex,8> EndPoints;
3348	LIS->pruneValue(LR&: S, Kill: Def, EndPoints: &EndPoints);
3349	DidPrune = true;
3350	// Mark value number as unused.
3351	ValueOut->markUnused();
3352
3353	if (V.Identical && S.Query(Idx: OtherDef).valueOutOrDead()) {
3354	// If V is identical to V.OtherVNI (and S was live at OtherDef),
3355	// then we can't simply prune V from S. V needs to be replaced
3356	// with V.OtherVNI.
3357	LIS->extendToIndices(LR&: S, Indices: EndPoints);
3358	}
3359
3360	// We may need to eliminate the subrange if the copy introduced a live
3361	// out undef value.
3362	if (ValueOut->isPHIDef())
3363	ShrinkMask |= S.LaneMask;
3364	continue;
3365	}
3366
3367	// If a subrange ends at the copy, then a value was copied but only
3368	// partially used later. Shrink the subregister range appropriately.
3369	//
3370	// Ultimately this calls shrinkToUses, so assuming ShrinkMask is
3371	// conservatively correct.
3372	if ((Q.valueIn() != nullptr && Q.valueOut() == nullptr) ||
3373	(V.Resolution == CR_Erase && isLiveThrough(Q))) {
3374	LLVM_DEBUG(dbgs() << "\t\tDead uses at sublane "
3375	<< PrintLaneMask(S.LaneMask) << " at " << Def
3376	<< "\n");
3377	ShrinkMask |= S.LaneMask;
3378	}
3379	}
3380	}
3381	if (DidPrune)
3382	LI.removeEmptySubRanges();
3383	}
3384
3385	/// Check if any of the subranges of @p LI contain a definition at @p Def.
3386	static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def) {
3387	for (LiveInterval::SubRange &SR : LI.subranges()) {
3388	if (VNInfo *VNI = SR.Query(Idx: Def).valueOutOrDead())
3389	if (VNI->def == Def)
3390	return true;
3391	}
3392	return false;
3393	}
3394
3395	void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {
3396	assert(&static_cast<LiveRange&>(LI) == &LR);
3397
3398	for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3399	if (Vals[i].Resolution != CR_Keep)
3400	continue;
3401	VNInfo *VNI = LR.getValNumInfo(ValNo: i);
3402	if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, Def: VNI->def))
3403	continue;
3404	Vals[i].Pruned = true;
3405	ShrinkMainRange = true;
3406	}
3407	}
3408
3409	void JoinVals::removeImplicitDefs() {
3410	for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3411	Val &V = Vals[i];
3412	if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)
3413	continue;
3414
3415	VNInfo *VNI = LR.getValNumInfo(ValNo: i);
3416	VNI->markUnused();
3417	LR.removeValNo(ValNo: VNI);
3418	}
3419	}
3420
3421	void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
3422	SmallVectorImpl<Register> &ShrinkRegs,
3423	LiveInterval *LI) {
3424	for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3425	// Get the def location before markUnused() below invalidates it.
3426	VNInfo *VNI = LR.getValNumInfo(ValNo: i);
3427	SlotIndex Def = VNI->def;
3428	switch (Vals[i].Resolution) {
3429	case CR_Keep: {
3430	// If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
3431	// longer. The IMPLICIT_DEF instructions are only inserted by
3432	// PHIElimination to guarantee that all PHI predecessors have a value.
3433	if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
3434	break;
3435	// Remove value number i from LR.
3436	// For intervals with subranges, removing a segment from the main range
3437	// may require extending the previous segment: for each definition of
3438	// a subregister, there will be a corresponding def in the main range.
3439	// That def may fall in the middle of a segment from another subrange.
3440	// In such cases, removing this def from the main range must be
3441	// complemented by extending the main range to account for the liveness
3442	// of the other subrange.
3443	// The new end point of the main range segment to be extended.
3444	SlotIndex NewEnd;
3445	if (LI != nullptr) {
3446	LiveRange::iterator I = LR.FindSegmentContaining(Idx: Def);
3447	assert(I != LR.end());
3448	// Do not extend beyond the end of the segment being removed.
3449	// The segment may have been pruned in preparation for joining
3450	// live ranges.
3451	NewEnd = I->end;
3452	}
3453
3454	LR.removeValNo(ValNo: VNI);
3455	// Note that this VNInfo is reused and still referenced in NewVNInfo,
3456	// make it appear like an unused value number.
3457	VNI->markUnused();
3458
3459	if (LI != nullptr && LI->hasSubRanges()) {
3460	assert(static_cast<LiveRange*>(LI) == &LR);
3461	// Determine the end point based on the subrange information:
3462	// minimum of (earliest def of next segment,
3463	// latest end point of containing segment)
3464	SlotIndex ED, LE;
3465	for (LiveInterval::SubRange &SR : LI->subranges()) {
3466	LiveRange::iterator I = SR.find(Pos: Def);
3467	if (I == SR.end())
3468	continue;
3469	if (I->start > Def)
3470	ED = ED.isValid() ? std::min(a: ED, b: I->start) : I->start;
3471	else
3472	LE = LE.isValid() ? std::max(a: LE, b: I->end) : I->end;
3473	}
3474	if (LE.isValid())
3475	NewEnd = std::min(a: NewEnd, b: LE);
3476	if (ED.isValid())
3477	NewEnd = std::min(a: NewEnd, b: ED);
3478
3479	// We only want to do the extension if there was a subrange that
3480	// was live across Def.
3481	if (LE.isValid()) {
3482	LiveRange::iterator S = LR.find(Pos: Def);
3483	if (S != LR.begin())
3484	std::prev(x: S)->end = NewEnd;
3485	}
3486	}
3487	LLVM_DEBUG({
3488	dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n';
3489	if (LI != nullptr)
3490	dbgs() << "\t\t LHS = " << *LI << '\n';
3491	});
3492	[[fallthrough]];
3493	}
3494
3495	case CR_Erase: {
3496	MachineInstr *MI = Indexes->getInstructionFromIndex(index: Def);
3497	assert(MI && "No instruction to erase");
3498	if (MI->isCopy()) {
3499	Register Reg = MI->getOperand(i: 1).getReg();
3500	if (Reg.isVirtual() && Reg != CP.getSrcReg() && Reg != CP.getDstReg())
3501	ShrinkRegs.push_back(Elt: Reg);
3502	}
3503	ErasedInstrs.insert(Ptr: MI);
3504	LLVM_DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);
3505	LIS->RemoveMachineInstrFromMaps(MI&: *MI);
3506	MI->eraseFromParent();
3507	break;
3508	}
3509	default:
3510	break;
3511	}
3512	}
3513	}
3514
3515	void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
3516	LaneBitmask LaneMask,
3517	const CoalescerPair &CP) {
3518	SmallVector<VNInfo*, 16> NewVNInfo;
3519	JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
3520	NewVNInfo, CP, LIS, TRI, true, true);
3521	JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
3522	NewVNInfo, CP, LIS, TRI, true, true);
3523
3524	// Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
3525	// We should be able to resolve all conflicts here as we could successfully do
3526	// it on the mainrange already. There is however a problem when multiple
3527	// ranges get mapped to the "overflow" lane mask bit which creates unexpected
3528	// interferences.
3529	if (!LHSVals.mapValues(Other&: RHSVals) || !RHSVals.mapValues(Other&: LHSVals)) {
3530	// We already determined that it is legal to merge the intervals, so this
3531	// should never fail.
3532	llvm_unreachable("*** Couldn't join subrange!\n");
3533	}
3534	if (!LHSVals.resolveConflicts(Other&: RHSVals) ||
3535	!RHSVals.resolveConflicts(Other&: LHSVals)) {
3536	// We already determined that it is legal to merge the intervals, so this
3537	// should never fail.
3538	llvm_unreachable("*** Couldn't join subrange!\n");
3539	}
3540
3541	// The merging algorithm in LiveInterval::join() can't handle conflicting
3542	// value mappings, so we need to remove any live ranges that overlap a
3543	// CR_Replace resolution. Collect a set of end points that can be used to
3544	// restore the live range after joining.
3545	SmallVector<SlotIndex, 8> EndPoints;
3546	LHSVals.pruneValues(Other&: RHSVals, EndPoints, changeInstrs: false);
3547	RHSVals.pruneValues(Other&: LHSVals, EndPoints, changeInstrs: false);
3548
3549	LHSVals.removeImplicitDefs();
3550	RHSVals.removeImplicitDefs();
3551
3552	LRange.verify();
3553	RRange.verify();
3554
3555	// Join RRange into LHS.
3556	LRange.join(Other&: RRange, ValNoAssignments: LHSVals.getAssignments(), RHSValNoAssignments: RHSVals.getAssignments(),
3557	NewVNInfo);
3558
3559	LLVM_DEBUG(dbgs() << "\t\tjoined lanes: " << PrintLaneMask(LaneMask)
3560	<< ' ' << LRange << "\n");
3561	if (EndPoints.empty())
3562	return;
3563
3564	// Recompute the parts of the live range we had to remove because of
3565	// CR_Replace conflicts.
3566	LLVM_DEBUG({
3567	dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
3568	for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
3569	dbgs() << EndPoints[i];
3570	if (i != n-1)
3571	dbgs() << ',';
3572	}
3573	dbgs() << ": " << LRange << '\n';
3574	});
3575	LIS->extendToIndices(LR&: LRange, Indices: EndPoints);
3576	}
3577
3578	void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
3579	const LiveRange &ToMerge,
3580	LaneBitmask LaneMask,
3581	CoalescerPair &CP,
3582	unsigned ComposeSubRegIdx) {
3583	BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3584	LI.refineSubRanges(
3585	Allocator, LaneMask,
3586	Apply: [this, &Allocator, &ToMerge, &CP](LiveInterval::SubRange &SR) {
3587	if (SR.empty()) {
3588	SR.assign(Other: ToMerge, Allocator);
3589	} else {
3590	// joinSubRegRange() destroys the merged range, so we need a copy.
3591	LiveRange RangeCopy(ToMerge, Allocator);
3592	joinSubRegRanges(LRange&: SR, RRange&: RangeCopy, LaneMask: SR.LaneMask, CP);
3593	}
3594	},
3595	Indexes: *LIS->getSlotIndexes(), TRI: *TRI, ComposeSubRegIdx);
3596	}
3597
3598	bool RegisterCoalescer::isHighCostLiveInterval(LiveInterval &LI) {
3599	if (LI.valnos.size() < LargeIntervalSizeThreshold)
3600	return false;
3601	auto &Counter = LargeLIVisitCounter[LI.reg()];
3602	if (Counter < LargeIntervalFreqThreshold) {
3603	Counter++;
3604	return false;
3605	}
3606	return true;
3607	}
3608
3609	bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
3610	SmallVector<VNInfo*, 16> NewVNInfo;
3611	LiveInterval &RHS = LIS->getInterval(Reg: CP.getSrcReg());
3612	LiveInterval &LHS = LIS->getInterval(Reg: CP.getDstReg());
3613	bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(RC: *CP.getNewRC());
3614	JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), LaneBitmask::getNone(),
3615	NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
3616	JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), LaneBitmask::getNone(),
3617	NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
3618
3619	LLVM_DEBUG(dbgs() << "\t\tRHS = " << RHS << "\n\t\tLHS = " << LHS << '\n');
3620
3621	if (isHighCostLiveInterval(LI&: LHS) || isHighCostLiveInterval(LI&: RHS))
3622	return false;
3623
3624	// First compute NewVNInfo and the simple value mappings.
3625	// Detect impossible conflicts early.
3626	if (!LHSVals.mapValues(Other&: RHSVals) || !RHSVals.mapValues(Other&: LHSVals))
3627	return false;
3628
3629	// Some conflicts can only be resolved after all values have been mapped.
3630	if (!LHSVals.resolveConflicts(Other&: RHSVals) || !RHSVals.resolveConflicts(Other&: LHSVals))
3631	return false;
3632
3633	// All clear, the live ranges can be merged.
3634	if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
3635	BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3636
3637	// Transform lanemasks from the LHS to masks in the coalesced register and
3638	// create initial subranges if necessary.
3639	unsigned DstIdx = CP.getDstIdx();
3640	if (!LHS.hasSubRanges()) {
3641	LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
3642	: TRI->getSubRegIndexLaneMask(SubIdx: DstIdx);
3643	// LHS must support subregs or we wouldn't be in this codepath.
3644	assert(Mask.any());
3645	LHS.createSubRangeFrom(Allocator, LaneMask: Mask, CopyFrom: LHS);
3646	} else if (DstIdx != 0) {
3647	// Transform LHS lanemasks to new register class if necessary.
3648	for (LiveInterval::SubRange &R : LHS.subranges()) {
3649	LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(IdxA: DstIdx, Mask: R.LaneMask);
3650	R.LaneMask = Mask;
3651	}
3652	}
3653	LLVM_DEBUG(dbgs() << "\t\tLHST = " << printReg(CP.getDstReg()) << ' ' << LHS
3654	<< '\n');
3655
3656	// Determine lanemasks of RHS in the coalesced register and merge subranges.
3657	unsigned SrcIdx = CP.getSrcIdx();
3658	if (!RHS.hasSubRanges()) {
3659	LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
3660	: TRI->getSubRegIndexLaneMask(SubIdx: SrcIdx);
3661	mergeSubRangeInto(LI&: LHS, ToMerge: RHS, LaneMask: Mask, CP, ComposeSubRegIdx: DstIdx);
3662	} else {
3663	// Pair up subranges and merge.
3664	for (LiveInterval::SubRange &R : RHS.subranges()) {
3665	LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(IdxA: SrcIdx, Mask: R.LaneMask);
3666	mergeSubRangeInto(LI&: LHS, ToMerge: R, LaneMask: Mask, CP, ComposeSubRegIdx: DstIdx);
3667	}
3668	}
3669	LLVM_DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
3670
3671	// Pruning implicit defs from subranges may result in the main range
3672	// having stale segments.
3673	LHSVals.pruneMainSegments(LI&: LHS, ShrinkMainRange);
3674
3675	LHSVals.pruneSubRegValues(LI&: LHS, ShrinkMask);
3676	RHSVals.pruneSubRegValues(LI&: LHS, ShrinkMask);
3677	}
3678
3679	// The merging algorithm in LiveInterval::join() can't handle conflicting
3680	// value mappings, so we need to remove any live ranges that overlap a
3681	// CR_Replace resolution. Collect a set of end points that can be used to
3682	// restore the live range after joining.
3683	SmallVector<SlotIndex, 8> EndPoints;
3684	LHSVals.pruneValues(Other&: RHSVals, EndPoints, changeInstrs: true);
3685	RHSVals.pruneValues(Other&: LHSVals, EndPoints, changeInstrs: true);
3686
3687	// Erase COPY and IMPLICIT_DEF instructions. This may cause some external
3688	// registers to require trimming.
3689	SmallVector<Register, 8> ShrinkRegs;
3690	LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, LI: &LHS);
3691	RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3692	while (!ShrinkRegs.empty())
3693	shrinkToUses(LI: &LIS->getInterval(Reg: ShrinkRegs.pop_back_val()));
3694
3695	// Scan and mark undef any DBG_VALUEs that would refer to a different value.
3696	checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);
3697
3698	// If the RHS covers any PHI locations that were tracked for debug-info, we
3699	// must update tracking information to reflect the join.
3700	auto RegIt = RegToPHIIdx.find(Val: CP.getSrcReg());
3701	if (RegIt != RegToPHIIdx.end()) {
3702	// Iterate over all the debug instruction numbers assigned this register.
3703	for (unsigned InstID : RegIt->second) {
3704	auto PHIIt = PHIValToPos.find(Val: InstID);
3705	assert(PHIIt != PHIValToPos.end());
3706	const SlotIndex &SI = PHIIt->second.SI;
3707
3708	// Does the RHS cover the position of this PHI?
3709	auto LII = RHS.find(Pos: SI);
3710	if (LII == RHS.end() || LII->start > SI)
3711	continue;
3712
3713	// Accept two kinds of subregister movement:
3714	// * When we merge from one register class into a larger register:
3715	// %1:gr16 = some-inst
3716	// ->
3717	// %2:gr32.sub_16bit = some-inst
3718	// * When the PHI is already in a subregister, and the larger class
3719	// is coalesced:
3720	// %2:gr32.sub_16bit = some-inst
3721	// %3:gr32 = COPY %2
3722	// ->
3723	// %3:gr32.sub_16bit = some-inst
3724	// Test for subregister move:
3725	if (CP.getSrcIdx() != 0 || CP.getDstIdx() != 0)
3726	// If we're moving between different subregisters, ignore this join.
3727	// The PHI will not get a location, dropping variable locations.
3728	if (PHIIt->second.SubReg && PHIIt->second.SubReg != CP.getSrcIdx())
3729	continue;
3730
3731	// Update our tracking of where the PHI is.
3732	PHIIt->second.Reg = CP.getDstReg();
3733
3734	// If we merge into a sub-register of a larger class (test above),
3735	// update SubReg.
3736	if (CP.getSrcIdx() != 0)
3737	PHIIt->second.SubReg = CP.getSrcIdx();
3738	}
3739
3740	// Rebuild the register index in RegToPHIIdx to account for PHIs tracking
3741	// different VRegs now. Copy old collection of debug instruction numbers and
3742	// erase the old one:
3743	auto InstrNums = RegIt->second;
3744	RegToPHIIdx.erase(I: RegIt);
3745
3746	// There might already be PHIs being tracked in the destination VReg. Insert
3747	// into an existing tracking collection, or insert a new one.
3748	RegIt = RegToPHIIdx.find(Val: CP.getDstReg());
3749	if (RegIt != RegToPHIIdx.end())
3750	RegIt->second.insert(I: RegIt->second.end(), From: InstrNums.begin(),
3751	To: InstrNums.end());
3752	else
3753	RegToPHIIdx.insert(KV: {CP.getDstReg(), InstrNums});
3754	}
3755
3756	// Join RHS into LHS.
3757	LHS.join(Other&: RHS, ValNoAssignments: LHSVals.getAssignments(), RHSValNoAssignments: RHSVals.getAssignments(), NewVNInfo);
3758
3759	// Kill flags are going to be wrong if the live ranges were overlapping.
3760	// Eventually, we should simply clear all kill flags when computing live
3761	// ranges. They are reinserted after register allocation.
3762	MRI->clearKillFlags(Reg: LHS.reg());
3763	MRI->clearKillFlags(Reg: RHS.reg());
3764
3765	if (!EndPoints.empty()) {
3766	// Recompute the parts of the live range we had to remove because of
3767	// CR_Replace conflicts.
3768	LLVM_DEBUG({
3769	dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
3770	for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
3771	dbgs() << EndPoints[i];
3772	if (i != n-1)
3773	dbgs() << ',';
3774	}
3775	dbgs() << ": " << LHS << '\n';
3776	});
3777	LIS->extendToIndices(LR&: (LiveRange&)LHS, Indices: EndPoints);
3778	}
3779
3780	return true;
3781	}
3782
3783	bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
3784	return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
3785	}
3786
3787	void RegisterCoalescer::buildVRegToDbgValueMap(MachineFunction &MF)
3788	{
3789	const SlotIndexes &Slots = *LIS->getSlotIndexes();
3790	SmallVector<MachineInstr *, 8> ToInsert;
3791
3792	// After collecting a block of DBG_VALUEs into ToInsert, enter them into the
3793	// vreg => DbgValueLoc map.
3794	auto CloseNewDVRange = [this, &ToInsert](SlotIndex Slot) {
3795	for (auto *X : ToInsert) {
3796	for (const auto &Op : X->debug_operands()) {
3797	if (Op.isReg() && Op.getReg().isVirtual())
3798	DbgVRegToValues[Op.getReg()].push_back(x: {Slot, X});
3799	}
3800	}
3801
3802	ToInsert.clear();
3803	};
3804
3805	// Iterate over all instructions, collecting them into the ToInsert vector.
3806	// Once a non-debug instruction is found, record the slot index of the
3807	// collected DBG_VALUEs.
3808	for (auto &MBB : MF) {
3809	SlotIndex CurrentSlot = Slots.getMBBStartIdx(mbb: &MBB);
3810
3811	for (auto &MI : MBB) {
3812	if (MI.isDebugValue()) {
3813	if (any_of(Range: MI.debug_operands(), P: [](const MachineOperand &MO) {
3814	return MO.isReg() && MO.getReg().isVirtual();
3815	}))
3816	ToInsert.push_back(Elt: &MI);
3817	} else if (!MI.isDebugOrPseudoInstr()) {
3818	CurrentSlot = Slots.getInstructionIndex(MI);
3819	CloseNewDVRange(CurrentSlot);
3820	}
3821	}
3822
3823	// Close range of DBG_VALUEs at the end of blocks.
3824	CloseNewDVRange(Slots.getMBBEndIdx(mbb: &MBB));
3825	}
3826
3827	// Sort all DBG_VALUEs we've seen by slot number.
3828	for (auto &Pair : DbgVRegToValues)
3829	llvm::sort(C&: Pair.second);
3830	}
3831
3832	void RegisterCoalescer::checkMergingChangesDbgValues(CoalescerPair &CP,
3833	LiveRange &LHS,
3834	JoinVals &LHSVals,
3835	LiveRange &RHS,
3836	JoinVals &RHSVals) {
3837	auto ScanForDstReg = [&](Register Reg) {
3838	checkMergingChangesDbgValuesImpl(Reg, OtherRange&: RHS, RegRange&: LHS, Vals2&: LHSVals);
3839	};
3840
3841	auto ScanForSrcReg = [&](Register Reg) {
3842	checkMergingChangesDbgValuesImpl(Reg, OtherRange&: LHS, RegRange&: RHS, Vals2&: RHSVals);
3843	};
3844
3845	// Scan for unsound updates of both the source and destination register.
3846	ScanForSrcReg(CP.getSrcReg());
3847	ScanForDstReg(CP.getDstReg());
3848	}
3849
3850	void RegisterCoalescer::checkMergingChangesDbgValuesImpl(Register Reg,
3851	LiveRange &OtherLR,
3852	LiveRange &RegLR,
3853	JoinVals &RegVals) {
3854	// Are there any DBG_VALUEs to examine?
3855	auto VRegMapIt = DbgVRegToValues.find(Val: Reg);
3856	if (VRegMapIt == DbgVRegToValues.end())
3857	return;
3858
3859	auto &DbgValueSet = VRegMapIt->second;
3860	auto DbgValueSetIt = DbgValueSet.begin();
3861	auto SegmentIt = OtherLR.begin();
3862
3863	bool LastUndefResult = false;
3864	SlotIndex LastUndefIdx;
3865
3866	// If the "Other" register is live at a slot Idx, test whether Reg can
3867	// safely be merged with it, or should be marked undef.
3868	auto ShouldUndef = [&RegVals, &RegLR, &LastUndefResult,
3869	&LastUndefIdx](SlotIndex Idx) -> bool {
3870	// Our worst-case performance typically happens with asan, causing very
3871	// many DBG_VALUEs of the same location. Cache a copy of the most recent
3872	// result for this edge-case.
3873	if (LastUndefIdx == Idx)
3874	return LastUndefResult;
3875
3876	// If the other range was live, and Reg's was not, the register coalescer
3877	// will not have tried to resolve any conflicts. We don't know whether
3878	// the DBG_VALUE will refer to the same value number, so it must be made
3879	// undef.
3880	auto OtherIt = RegLR.find(Pos: Idx);
3881	if (OtherIt == RegLR.end())
3882	return true;
3883
3884	// Both the registers were live: examine the conflict resolution record for
3885	// the value number Reg refers to. CR_Keep meant that this value number
3886	// "won" and the merged register definitely refers to that value. CR_Erase
3887	// means the value number was a redundant copy of the other value, which
3888	// was coalesced and Reg deleted. It's safe to refer to the other register
3889	// (which will be the source of the copy).
3890	auto Resolution = RegVals.getResolution(Num: OtherIt->valno->id);
3891	LastUndefResult = Resolution != JoinVals::CR_Keep &&
3892	Resolution != JoinVals::CR_Erase;
3893	LastUndefIdx = Idx;
3894	return LastUndefResult;
3895	};
3896
3897	// Iterate over both the live-range of the "Other" register, and the set of
3898	// DBG_VALUEs for Reg at the same time. Advance whichever one has the lowest
3899	// slot index. This relies on the DbgValueSet being ordered.
3900	while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.end()) {
3901	if (DbgValueSetIt->first < SegmentIt->end) {
3902	// "Other" is live and there is a DBG_VALUE of Reg: test if we should
3903	// set it undef.
3904	if (DbgValueSetIt->first >= SegmentIt->start) {
3905	bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(Reg);
3906	bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);
3907	if (HasReg && ShouldUndefReg) {
3908	// Mark undef, erase record of this DBG_VALUE to avoid revisiting.
3909	DbgValueSetIt->second->setDebugValueUndef();
3910	continue;
3911	}
3912	}
3913	++DbgValueSetIt;
3914	} else {
3915	++SegmentIt;
3916	}
3917	}
3918	}
3919
3920	namespace {
3921
3922	/// Information concerning MBB coalescing priority.
3923	struct MBBPriorityInfo {
3924	MachineBasicBlock *MBB;
3925	unsigned Depth;
3926	bool IsSplit;
3927
3928	MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)
3929	: MBB(mbb), Depth(depth), IsSplit(issplit) {}
3930	};
3931
3932	} // end anonymous namespace
3933
3934	/// C-style comparator that sorts first based on the loop depth of the basic
3935	/// block (the unsigned), and then on the MBB number.
3936	///
3937	/// EnableGlobalCopies assumes that the primary sort key is loop depth.
3938	static int compareMBBPriority(const MBBPriorityInfo *LHS,
3939	const MBBPriorityInfo *RHS) {
3940	// Deeper loops first
3941	if (LHS->Depth != RHS->Depth)
3942	return LHS->Depth > RHS->Depth ? -1 : 1;
3943
3944	// Try to unsplit critical edges next.
3945	if (LHS->IsSplit != RHS->IsSplit)
3946	return LHS->IsSplit ? -1 : 1;
3947
3948	// Prefer blocks that are more connected in the CFG. This takes care of
3949	// the most difficult copies first while intervals are short.
3950	unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();
3951	unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();
3952	if (cl != cr)
3953	return cl > cr ? -1 : 1;
3954
3955	// As a last resort, sort by block number.
3956	return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;
3957	}
3958
3959	/// \returns true if the given copy uses or defines a local live range.
3960	static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) {
3961	if (!Copy->isCopy())
3962	return false;
3963
3964	if (Copy->getOperand(i: 1).isUndef())
3965	return false;
3966
3967	Register SrcReg = Copy->getOperand(i: 1).getReg();
3968	Register DstReg = Copy->getOperand(i: 0).getReg();
3969	if (SrcReg.isPhysical() || DstReg.isPhysical())
3970	return false;
3971
3972	return LIS->intervalIsInOneMBB(LI: LIS->getInterval(Reg: SrcReg))
3973	|| LIS->intervalIsInOneMBB(LI: LIS->getInterval(Reg: DstReg));
3974	}
3975
3976	void RegisterCoalescer::lateLiveIntervalUpdate() {
3977	for (Register reg : ToBeUpdated) {
3978	if (!LIS->hasInterval(Reg: reg))
3979	continue;
3980	LiveInterval &LI = LIS->getInterval(Reg: reg);
3981	shrinkToUses(LI: &LI, Dead: &DeadDefs);
3982	if (!DeadDefs.empty())
3983	eliminateDeadDefs();
3984	}
3985	ToBeUpdated.clear();
3986	}
3987
3988	bool RegisterCoalescer::
3989	copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) {
3990	bool Progress = false;
3991	SmallPtrSet<MachineInstr *, 4> CurrentErasedInstrs;
3992	for (MachineInstr *&MI : CurrList) {
3993	if (!MI)
3994	continue;
3995	// Skip instruction pointers that have already been erased, for example by
3996	// dead code elimination.
3997	if (ErasedInstrs.count(Ptr: MI) || CurrentErasedInstrs.count(Ptr: MI)) {
3998	MI = nullptr;
3999	continue;
4000	}
4001	bool Again = false;
4002	bool Success = joinCopy(CopyMI: MI, Again, CurrentErasedInstrs);
4003	Progress |= Success;
4004	if (Success || !Again)
4005	MI = nullptr;
4006	}
4007	// Clear instructions not recorded in `ErasedInstrs` but erased.
4008	if (!CurrentErasedInstrs.empty()) {
4009	for (MachineInstr *&MI : CurrList) {
4010	if (MI && CurrentErasedInstrs.count(Ptr: MI))
4011	MI = nullptr;
4012	}
4013	for (MachineInstr *&MI : WorkList) {
4014	if (MI && CurrentErasedInstrs.count(Ptr: MI))
4015	MI = nullptr;
4016	}
4017	}
4018	return Progress;
4019	}
4020
4021	/// Check if DstReg is a terminal node.
4022	/// I.e., it does not have any affinity other than \p Copy.
4023	static bool isTerminalReg(Register DstReg, const MachineInstr &Copy,
4024	const MachineRegisterInfo *MRI) {
4025	assert(Copy.isCopyLike());
4026	// Check if the destination of this copy as any other affinity.
4027	for (const MachineInstr &MI : MRI->reg_nodbg_instructions(Reg: DstReg))
4028	if (&MI != &Copy && MI.isCopyLike())
4029	return false;
4030	return true;
4031	}
4032
4033	bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {
4034	assert(Copy.isCopyLike());
4035	if (!UseTerminalRule)
4036	return false;
4037	Register SrcReg, DstReg;
4038	unsigned SrcSubReg = 0, DstSubReg = 0;
4039	if (!isMoveInstr(tri: *TRI, MI: &Copy, Src&: SrcReg, Dst&: DstReg, SrcSub&: SrcSubReg, DstSub&: DstSubReg))
4040	return false;
4041	// Check if the destination of this copy has any other affinity.
4042	if (DstReg.isPhysical() ||
4043	// If SrcReg is a physical register, the copy won't be coalesced.
4044	// Ignoring it may have other side effect (like missing
4045	// rematerialization). So keep it.
4046	SrcReg.isPhysical() || !isTerminalReg(DstReg, Copy, MRI))
4047	return false;
4048
4049	// DstReg is a terminal node. Check if it interferes with any other
4050	// copy involving SrcReg.
4051	const MachineBasicBlock *OrigBB = Copy.getParent();
4052	const LiveInterval &DstLI = LIS->getInterval(Reg: DstReg);
4053	for (const MachineInstr &MI : MRI->reg_nodbg_instructions(Reg: SrcReg)) {
4054	// Technically we should check if the weight of the new copy is
4055	// interesting compared to the other one and update the weight
4056	// of the copies accordingly. However, this would only work if
4057	// we would gather all the copies first then coalesce, whereas
4058	// right now we interleave both actions.
4059	// For now, just consider the copies that are in the same block.
4060	if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB)
4061	continue;
4062	Register OtherSrcReg, OtherReg;
4063	unsigned OtherSrcSubReg = 0, OtherSubReg = 0;
4064	if (!isMoveInstr(tri: *TRI, MI: &Copy, Src&: OtherSrcReg, Dst&: OtherReg, SrcSub&: OtherSrcSubReg,
4065	DstSub&: OtherSubReg))
4066	return false;
4067	if (OtherReg == SrcReg)
4068	OtherReg = OtherSrcReg;
4069	// Check if OtherReg is a non-terminal.
4070	if (OtherReg.isPhysical() || isTerminalReg(DstReg: OtherReg, Copy: MI, MRI))
4071	continue;
4072	// Check that OtherReg interfere with DstReg.
4073	if (LIS->getInterval(Reg: OtherReg).overlaps(other: DstLI)) {
4074	LLVM_DEBUG(dbgs() << "Apply terminal rule for: " << printReg(DstReg)
4075	<< '\n');
4076	return true;
4077	}
4078	}
4079	return false;
4080	}
4081
4082	void
4083	RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {
4084	LLVM_DEBUG(dbgs() << MBB->getName() << ":\n");
4085
4086	// Collect all copy-like instructions in MBB. Don't start coalescing anything
4087	// yet, it might invalidate the iterator.
4088	const unsigned PrevSize = WorkList.size();
4089	if (JoinGlobalCopies) {
4090	SmallVector<MachineInstr*, 2> LocalTerminals;
4091	SmallVector<MachineInstr*, 2> GlobalTerminals;
4092	// Coalesce copies bottom-up to coalesce local defs before local uses. They
4093	// are not inherently easier to resolve, but slightly preferable until we
4094	// have local live range splitting. In particular this is required by
4095	// cmp+jmp macro fusion.
4096	for (MachineInstr &MI : *MBB) {
4097	if (!MI.isCopyLike())
4098	continue;
4099	bool ApplyTerminalRule = applyTerminalRule(Copy: MI);
4100	if (isLocalCopy(Copy: &MI, LIS)) {
4101	if (ApplyTerminalRule)
4102	LocalTerminals.push_back(Elt: &MI);
4103	else
4104	LocalWorkList.push_back(Elt: &MI);
4105	} else {
4106	if (ApplyTerminalRule)
4107	GlobalTerminals.push_back(Elt: &MI);
4108	else
4109	WorkList.push_back(Elt: &MI);
4110	}
4111	}
4112	// Append the copies evicted by the terminal rule at the end of the list.
4113	LocalWorkList.append(in_start: LocalTerminals.begin(), in_end: LocalTerminals.end());
4114	WorkList.append(in_start: GlobalTerminals.begin(), in_end: GlobalTerminals.end());
4115	}
4116	else {
4117	SmallVector<MachineInstr*, 2> Terminals;
4118	for (MachineInstr &MII : *MBB)
4119	if (MII.isCopyLike()) {
4120	if (applyTerminalRule(Copy: MII))
4121	Terminals.push_back(Elt: &MII);
4122	else
4123	WorkList.push_back(Elt: &MII);
4124	}
4125	// Append the copies evicted by the terminal rule at the end of the list.
4126	WorkList.append(in_start: Terminals.begin(), in_end: Terminals.end());
4127	}
4128	// Try coalescing the collected copies immediately, and remove the nulls.
4129	// This prevents the WorkList from getting too large since most copies are
4130	// joinable on the first attempt.
4131	MutableArrayRef<MachineInstr*>
4132	CurrList(WorkList.begin() + PrevSize, WorkList.end());
4133	if (copyCoalesceWorkList(CurrList))
4134	WorkList.erase(CS: std::remove(first: WorkList.begin() + PrevSize, last: WorkList.end(),
4135	value: nullptr), CE: WorkList.end());
4136	}
4137
4138	void RegisterCoalescer::coalesceLocals() {
4139	copyCoalesceWorkList(CurrList: LocalWorkList);
4140	for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) {
4141	if (LocalWorkList[j])
4142	WorkList.push_back(Elt: LocalWorkList[j]);
4143	}
4144	LocalWorkList.clear();
4145	}
4146
4147	void RegisterCoalescer::joinAllIntervals() {
4148	LLVM_DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
4149	assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around.");
4150
4151	std::vector<MBBPriorityInfo> MBBs;
4152	MBBs.reserve(n: MF->size());
4153	for (MachineBasicBlock &MBB : *MF) {
4154	MBBs.push_back(x: MBBPriorityInfo(&MBB, Loops->getLoopDepth(BB: &MBB),
4155	JoinSplitEdges && isSplitEdge(MBB: &MBB)));
4156	}
4157	array_pod_sort(Start: MBBs.begin(), End: MBBs.end(), Compare: compareMBBPriority);
4158
4159	// Coalesce intervals in MBB priority order.
4160	unsigned CurrDepth = std::numeric_limits<unsigned>::max();
4161	for (MBBPriorityInfo &MBB : MBBs) {
4162	// Try coalescing the collected local copies for deeper loops.
4163	if (JoinGlobalCopies && MBB.Depth < CurrDepth) {
4164	coalesceLocals();
4165	CurrDepth = MBB.Depth;
4166	}
4167	copyCoalesceInMBB(MBB: MBB.MBB);
4168	}
4169	lateLiveIntervalUpdate();
4170	coalesceLocals();
4171
4172	// Joining intervals can allow other intervals to be joined. Iteratively join
4173	// until we make no progress.
4174	while (copyCoalesceWorkList(CurrList: WorkList))
4175	/* empty */ ;
4176	lateLiveIntervalUpdate();
4177	}
4178
4179	void RegisterCoalescer::releaseMemory() {
4180	ErasedInstrs.clear();
4181	WorkList.clear();
4182	DeadDefs.clear();
4183	InflateRegs.clear();
4184	LargeLIVisitCounter.clear();
4185	}
4186
4187	bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) {
4188	LLVM_DEBUG(dbgs() << "********** REGISTER COALESCER **********\n"
4189	<< "********** Function: " << fn.getName() << '\n');
4190
4191	// Variables changed between a setjmp and a longjump can have undefined value
4192	// after the longjmp. This behaviour can be observed if such a variable is
4193	// spilled, so longjmp won't restore the value in the spill slot.
4194	// RegisterCoalescer should not run in functions with a setjmp to avoid
4195	// merging such undefined variables with predictable ones.
4196	//
4197	// TODO: Could specifically disable coalescing registers live across setjmp
4198	// calls
4199	if (fn.exposesReturnsTwice()) {
4200	LLVM_DEBUG(
4201	dbgs() << "* Skipped as it exposes functions that returns twice.\n");
4202	return false;
4203	}
4204
4205	MF = &fn;
4206	MRI = &fn.getRegInfo();
4207	const TargetSubtargetInfo &STI = fn.getSubtarget();
4208	TRI = STI.getRegisterInfo();
4209	TII = STI.getInstrInfo();
4210	LIS = &getAnalysis<LiveIntervals>();
4211	AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4212	Loops = &getAnalysis<MachineLoopInfo>();
4213	if (EnableGlobalCopies == cl::BOU_UNSET)
4214	JoinGlobalCopies = STI.enableJoinGlobalCopies();
4215	else
4216	JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE);
4217
4218	// If there are PHIs tracked by debug-info, they will need updating during
4219	// coalescing. Build an index of those PHIs to ease updating.
4220	SlotIndexes *Slots = LIS->getSlotIndexes();
4221	for (const auto &DebugPHI : MF->DebugPHIPositions) {
4222	MachineBasicBlock *MBB = DebugPHI.second.MBB;
4223	Register Reg = DebugPHI.second.Reg;
4224	unsigned SubReg = DebugPHI.second.SubReg;
4225	SlotIndex SI = Slots->getMBBStartIdx(mbb: MBB);
4226	PHIValPos P = {.SI: SI, .Reg: Reg, .SubReg: SubReg};
4227	PHIValToPos.insert(KV: std::make_pair(x: DebugPHI.first, y&: P));
4228	RegToPHIIdx[Reg].push_back(Elt: DebugPHI.first);
4229	}
4230
4231	// The MachineScheduler does not currently require JoinSplitEdges. This will
4232	// either be enabled unconditionally or replaced by a more general live range
4233	// splitting optimization.
4234	JoinSplitEdges = EnableJoinSplits;
4235
4236	if (VerifyCoalescing)
4237	MF->verify(p: this, Banner: "Before register coalescing");
4238
4239	DbgVRegToValues.clear();
4240	buildVRegToDbgValueMap(MF&: fn);
4241
4242	RegClassInfo.runOnMachineFunction(MF: fn);
4243
4244	// Join (coalesce) intervals if requested.
4245	if (EnableJoining)
4246	joinAllIntervals();
4247
4248	// After deleting a lot of copies, register classes may be less constrained.
4249	// Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->
4250	// DPR inflation.
4251	array_pod_sort(Start: InflateRegs.begin(), End: InflateRegs.end());
4252	InflateRegs.erase(CS: std::unique(first: InflateRegs.begin(), last: InflateRegs.end()),
4253	CE: InflateRegs.end());
4254	LLVM_DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size()
4255	<< " regs.\n");
4256	for (Register Reg : InflateRegs) {
4257	if (MRI->reg_nodbg_empty(RegNo: Reg))
4258	continue;
4259	if (MRI->recomputeRegClass(Reg)) {
4260	LLVM_DEBUG(dbgs() << printReg(Reg) << " inflated to "
4261	<< TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n');
4262	++NumInflated;
4263
4264	LiveInterval &LI = LIS->getInterval(Reg);
4265	if (LI.hasSubRanges()) {
4266	// If the inflated register class does not support subregisters anymore
4267	// remove the subranges.
4268	if (!MRI->shouldTrackSubRegLiveness(VReg: Reg)) {
4269	LI.clearSubRanges();
4270	} else {
4271	#ifndef NDEBUG
4272	LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
4273	// If subranges are still supported, then the same subregs
4274	// should still be supported.
4275	for (LiveInterval::SubRange &S : LI.subranges()) {
4276	assert((S.LaneMask & ~MaxMask).none());
4277	}
4278	#endif
4279	}
4280	}
4281	}
4282	}
4283
4284	// After coalescing, update any PHIs that are being tracked by debug-info
4285	// with their new VReg locations.
4286	for (auto &p : MF->DebugPHIPositions) {
4287	auto it = PHIValToPos.find(Val: p.first);
4288	assert(it != PHIValToPos.end());
4289	p.second.Reg = it->second.Reg;
4290	p.second.SubReg = it->second.SubReg;
4291	}
4292
4293	PHIValToPos.clear();
4294	RegToPHIIdx.clear();
4295
4296	LLVM_DEBUG(dump());
4297	if (VerifyCoalescing)
4298	MF->verify(p: this, Banner: "After register coalescing");
4299	return true;
4300	}
4301
4302	void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
4303	LIS->print(O, m);
4304	}
4305