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