1	//===- TwoAddressInstructionPass.cpp - Two-Address instruction pass -------===//
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 TwoAddress instruction pass which is used
10	// by most register allocators. Two-Address instructions are rewritten
11	// from:
12	//
13	// A = B op C
14	//
15	// to:
16	//
17	// A = B
18	// A op= C
19	//
20	// Note that if a register allocator chooses to use this pass, that it
21	// has to be capable of handling the non-SSA nature of these rewritten
22	// virtual registers.
23	//
24	// It is also worth noting that the duplicate operand of the two
25	// address instruction is removed.
26	//
27	//===----------------------------------------------------------------------===//
28
29	#include "llvm/ADT/DenseMap.h"
30	#include "llvm/ADT/SmallPtrSet.h"
31	#include "llvm/ADT/SmallVector.h"
32	#include "llvm/ADT/Statistic.h"
33	#include "llvm/ADT/iterator_range.h"
34	#include "llvm/Analysis/AliasAnalysis.h"
35	#include "llvm/CodeGen/LiveInterval.h"
36	#include "llvm/CodeGen/LiveIntervals.h"
37	#include "llvm/CodeGen/LiveVariables.h"
38	#include "llvm/CodeGen/MachineBasicBlock.h"
39	#include "llvm/CodeGen/MachineFunction.h"
40	#include "llvm/CodeGen/MachineFunctionPass.h"
41	#include "llvm/CodeGen/MachineInstr.h"
42	#include "llvm/CodeGen/MachineInstrBuilder.h"
43	#include "llvm/CodeGen/MachineOperand.h"
44	#include "llvm/CodeGen/MachineRegisterInfo.h"
45	#include "llvm/CodeGen/Passes.h"
46	#include "llvm/CodeGen/SlotIndexes.h"
47	#include "llvm/CodeGen/TargetInstrInfo.h"
48	#include "llvm/CodeGen/TargetOpcodes.h"
49	#include "llvm/CodeGen/TargetRegisterInfo.h"
50	#include "llvm/CodeGen/TargetSubtargetInfo.h"
51	#include "llvm/MC/MCInstrDesc.h"
52	#include "llvm/Pass.h"
53	#include "llvm/Support/CodeGen.h"
54	#include "llvm/Support/CommandLine.h"
55	#include "llvm/Support/Debug.h"
56	#include "llvm/Support/ErrorHandling.h"
57	#include "llvm/Support/raw_ostream.h"
58	#include "llvm/Target/TargetMachine.h"
59	#include <cassert>
60	#include <iterator>
61	#include <utility>
62
63	using namespace llvm;
64
65	#define DEBUG_TYPE "twoaddressinstruction"
66
67	STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
68	STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
69	STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
70	STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
71	STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up");
72	STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down");
73
74	// Temporary flag to disable rescheduling.
75	static cl::opt<bool>
76	EnableRescheduling("twoaddr-reschedule",
77	cl::desc("Coalesce copies by rescheduling (default=true)"),
78	cl::init(Val: true), cl::Hidden);
79
80	// Limit the number of dataflow edges to traverse when evaluating the benefit
81	// of commuting operands.
82	static cl::opt<unsigned> MaxDataFlowEdge(
83	"dataflow-edge-limit", cl::Hidden, cl::init(Val: 3),
84	cl::desc("Maximum number of dataflow edges to traverse when evaluating "
85	"the benefit of commuting operands"));
86
87	namespace {
88
89	class TwoAddressInstructionPass : public MachineFunctionPass {
90	MachineFunction *MF = nullptr;
91	const TargetInstrInfo *TII = nullptr;
92	const TargetRegisterInfo *TRI = nullptr;
93	const InstrItineraryData *InstrItins = nullptr;
94	MachineRegisterInfo *MRI = nullptr;
95	LiveVariables *LV = nullptr;
96	LiveIntervals *LIS = nullptr;
97	AliasAnalysis *AA = nullptr;
98	CodeGenOptLevel OptLevel = CodeGenOptLevel::None;
99
100	// The current basic block being processed.
101	MachineBasicBlock *MBB = nullptr;
102
103	// Keep track the distance of a MI from the start of the current basic block.
104	DenseMap<MachineInstr*, unsigned> DistanceMap;
105
106	// Set of already processed instructions in the current block.
107	SmallPtrSet<MachineInstr*, 8> Processed;
108
109	// A map from virtual registers to physical registers which are likely targets
110	// to be coalesced to due to copies from physical registers to virtual
111	// registers. e.g. v1024 = move r0.
112	DenseMap<Register, Register> SrcRegMap;
113
114	// A map from virtual registers to physical registers which are likely targets
115	// to be coalesced to due to copies to physical registers from virtual
116	// registers. e.g. r1 = move v1024.
117	DenseMap<Register, Register> DstRegMap;
118
119	MachineInstr *getSingleDef(Register Reg, MachineBasicBlock *BB) const;
120
121	bool isRevCopyChain(Register FromReg, Register ToReg, int Maxlen);
122
123	bool noUseAfterLastDef(Register Reg, unsigned Dist, unsigned &LastDef);
124
125	bool isCopyToReg(MachineInstr &MI, Register &SrcReg, Register &DstReg,
126	bool &IsSrcPhys, bool &IsDstPhys) const;
127
128	bool isPlainlyKilled(const MachineInstr *MI, LiveRange &LR) const;
129	bool isPlainlyKilled(const MachineInstr *MI, Register Reg) const;
130	bool isPlainlyKilled(const MachineOperand &MO) const;
131
132	bool isKilled(MachineInstr &MI, Register Reg, bool allowFalsePositives) const;
133
134	MachineInstr *findOnlyInterestingUse(Register Reg, MachineBasicBlock *MBB,
135	bool &IsCopy, Register &DstReg,
136	bool &IsDstPhys) const;
137
138	bool regsAreCompatible(Register RegA, Register RegB) const;
139
140	void removeMapRegEntry(const MachineOperand &MO,
141	DenseMap<Register, Register> &RegMap) const;
142
143	void removeClobberedSrcRegMap(MachineInstr *MI);
144
145	bool regOverlapsSet(const SmallVectorImpl<Register> &Set, Register Reg) const;
146
147	bool isProfitableToCommute(Register RegA, Register RegB, Register RegC,
148	MachineInstr *MI, unsigned Dist);
149
150	bool commuteInstruction(MachineInstr *MI, unsigned DstIdx,
151	unsigned RegBIdx, unsigned RegCIdx, unsigned Dist);
152
153	bool isProfitableToConv3Addr(Register RegA, Register RegB);
154
155	bool convertInstTo3Addr(MachineBasicBlock::iterator &mi,
156	MachineBasicBlock::iterator &nmi, Register RegA,
157	Register RegB, unsigned &Dist);
158
159	bool isDefTooClose(Register Reg, unsigned Dist, MachineInstr *MI);
160
161	bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
162	MachineBasicBlock::iterator &nmi, Register Reg);
163	bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
164	MachineBasicBlock::iterator &nmi, Register Reg);
165
166	bool tryInstructionTransform(MachineBasicBlock::iterator &mi,
167	MachineBasicBlock::iterator &nmi,
168	unsigned SrcIdx, unsigned DstIdx,
169	unsigned &Dist, bool shouldOnlyCommute);
170
171	bool tryInstructionCommute(MachineInstr *MI,
172	unsigned DstOpIdx,
173	unsigned BaseOpIdx,
174	bool BaseOpKilled,
175	unsigned Dist);
176	void scanUses(Register DstReg);
177
178	void processCopy(MachineInstr *MI);
179
180	using TiedPairList = SmallVector<std::pair<unsigned, unsigned>, 4>;
181	using TiedOperandMap = SmallDenseMap<unsigned, TiedPairList>;
182
183	bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&);
184	void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist);
185	void eliminateRegSequence(MachineBasicBlock::iterator&);
186	bool processStatepoint(MachineInstr *MI, TiedOperandMap &TiedOperands);
187
188	public:
189	static char ID; // Pass identification, replacement for typeid
190
191	TwoAddressInstructionPass() : MachineFunctionPass(ID) {
192	initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry());
193	}
194
195	void getAnalysisUsage(AnalysisUsage &AU) const override {
196	AU.setPreservesCFG();
197	AU.addUsedIfAvailable<AAResultsWrapperPass>();
198	AU.addUsedIfAvailable<LiveVariables>();
199	AU.addPreserved<LiveVariables>();
200	AU.addPreserved<SlotIndexes>();
201	AU.addPreserved<LiveIntervals>();
202	AU.addPreservedID(ID&: MachineLoopInfoID);
203	AU.addPreservedID(ID&: MachineDominatorsID);
204	MachineFunctionPass::getAnalysisUsage(AU);
205	}
206
207	/// Pass entry point.
208	bool runOnMachineFunction(MachineFunction&) override;
209	};
210
211	} // end anonymous namespace
212
213	char TwoAddressInstructionPass::ID = 0;
214
215	char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID;
216
217	INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, DEBUG_TYPE,
218	"Two-Address instruction pass", false, false)
219	INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
220	INITIALIZE_PASS_END(TwoAddressInstructionPass, DEBUG_TYPE,
221	"Two-Address instruction pass", false, false)
222
223	/// Return the MachineInstr* if it is the single def of the Reg in current BB.
224	MachineInstr *
225	TwoAddressInstructionPass::getSingleDef(Register Reg,
226	MachineBasicBlock *BB) const {
227	MachineInstr *Ret = nullptr;
228	for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
229	if (DefMI.getParent() != BB || DefMI.isDebugValue())
230	continue;
231	if (!Ret)
232	Ret = &DefMI;
233	else if (Ret != &DefMI)
234	return nullptr;
235	}
236	return Ret;
237	}
238
239	/// Check if there is a reversed copy chain from FromReg to ToReg:
240	/// %Tmp1 = copy %Tmp2;
241	/// %FromReg = copy %Tmp1;
242	/// %ToReg = add %FromReg ...
243	/// %Tmp2 = copy %ToReg;
244	/// MaxLen specifies the maximum length of the copy chain the func
245	/// can walk through.
246	bool TwoAddressInstructionPass::isRevCopyChain(Register FromReg, Register ToReg,
247	int Maxlen) {
248	Register TmpReg = FromReg;
249	for (int i = 0; i < Maxlen; i++) {
250	MachineInstr *Def = getSingleDef(Reg: TmpReg, BB: MBB);
251	if (!Def || !Def->isCopy())
252	return false;
253
254	TmpReg = Def->getOperand(i: 1).getReg();
255
256	if (TmpReg == ToReg)
257	return true;
258	}
259	return false;
260	}
261
262	/// Return true if there are no intervening uses between the last instruction
263	/// in the MBB that defines the specified register and the two-address
264	/// instruction which is being processed. It also returns the last def location
265	/// by reference.
266	bool TwoAddressInstructionPass::noUseAfterLastDef(Register Reg, unsigned Dist,
267	unsigned &LastDef) {
268	LastDef = 0;
269	unsigned LastUse = Dist;
270	for (MachineOperand &MO : MRI->reg_operands(Reg)) {
271	MachineInstr *MI = MO.getParent();
272	if (MI->getParent() != MBB || MI->isDebugValue())
273	continue;
274	DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(Val: MI);
275	if (DI == DistanceMap.end())
276	continue;
277	if (MO.isUse() && DI->second < LastUse)
278	LastUse = DI->second;
279	if (MO.isDef() && DI->second > LastDef)
280	LastDef = DI->second;
281	}
282
283	return !(LastUse > LastDef && LastUse < Dist);
284	}
285
286	/// Return true if the specified MI is a copy instruction or an extract_subreg
287	/// instruction. It also returns the source and destination registers and
288	/// whether they are physical registers by reference.
289	bool TwoAddressInstructionPass::isCopyToReg(MachineInstr &MI, Register &SrcReg,
290	Register &DstReg, bool &IsSrcPhys,
291	bool &IsDstPhys) const {
292	SrcReg = 0;
293	DstReg = 0;
294	if (MI.isCopy()) {
295	DstReg = MI.getOperand(i: 0).getReg();
296	SrcReg = MI.getOperand(i: 1).getReg();
297	} else if (MI.isInsertSubreg() || MI.isSubregToReg()) {
298	DstReg = MI.getOperand(i: 0).getReg();
299	SrcReg = MI.getOperand(i: 2).getReg();
300	} else {
301	return false;
302	}
303
304	IsSrcPhys = SrcReg.isPhysical();
305	IsDstPhys = DstReg.isPhysical();
306	return true;
307	}
308
309	bool TwoAddressInstructionPass::isPlainlyKilled(const MachineInstr *MI,
310	LiveRange &LR) const {
311	// This is to match the kill flag version where undefs don't have kill flags.
312	if (!LR.hasAtLeastOneValue())
313	return false;
314
315	SlotIndex useIdx = LIS->getInstructionIndex(Instr: *MI);
316	LiveInterval::const_iterator I = LR.find(Pos: useIdx);
317	assert(I != LR.end() && "Reg must be live-in to use.");
318	return !I->end.isBlock() && SlotIndex::isSameInstr(A: I->end, B: useIdx);
319	}
320
321	/// Test if the given register value, which is used by the
322	/// given instruction, is killed by the given instruction.
323	bool TwoAddressInstructionPass::isPlainlyKilled(const MachineInstr *MI,
324	Register Reg) const {
325	// FIXME: Sometimes tryInstructionTransform() will add instructions and
326	// test whether they can be folded before keeping them. In this case it
327	// sets a kill before recursively calling tryInstructionTransform() again.
328	// If there is no interval available, we assume that this instruction is
329	// one of those. A kill flag is manually inserted on the operand so the
330	// check below will handle it.
331	if (LIS && !LIS->isNotInMIMap(Instr: *MI)) {
332	if (Reg.isVirtual())
333	return isPlainlyKilled(MI, LR&: LIS->getInterval(Reg));
334	// Reserved registers are considered always live.
335	if (MRI->isReserved(PhysReg: Reg))
336	return false;
337	return all_of(Range: TRI->regunits(Reg), P: [&](MCRegUnit U) {
338	return isPlainlyKilled(MI, LR&: LIS->getRegUnit(Unit: U));
339	});
340	}
341
342	return MI->killsRegister(Reg, /*TRI=*/nullptr);
343	}
344
345	/// Test if the register used by the given operand is killed by the operand's
346	/// instruction.
347	bool TwoAddressInstructionPass::isPlainlyKilled(
348	const MachineOperand &MO) const {
349	return MO.isKill() || isPlainlyKilled(MI: MO.getParent(), Reg: MO.getReg());
350	}
351
352	/// Test if the given register value, which is used by the given
353	/// instruction, is killed by the given instruction. This looks through
354	/// coalescable copies to see if the original value is potentially not killed.
355	///
356	/// For example, in this code:
357	///
358	/// %reg1034 = copy %reg1024
359	/// %reg1035 = copy killed %reg1025
360	/// %reg1036 = add killed %reg1034, killed %reg1035
361	///
362	/// %reg1034 is not considered to be killed, since it is copied from a
363	/// register which is not killed. Treating it as not killed lets the
364	/// normal heuristics commute the (two-address) add, which lets
365	/// coalescing eliminate the extra copy.
366	///
367	/// If allowFalsePositives is true then likely kills are treated as kills even
368	/// if it can't be proven that they are kills.
369	bool TwoAddressInstructionPass::isKilled(MachineInstr &MI, Register Reg,
370	bool allowFalsePositives) const {
371	MachineInstr *DefMI = &MI;
372	while (true) {
373	// All uses of physical registers are likely to be kills.
374	if (Reg.isPhysical() && (allowFalsePositives || MRI->hasOneUse(RegNo: Reg)))
375	return true;
376	if (!isPlainlyKilled(MI: DefMI, Reg))
377	return false;
378	if (Reg.isPhysical())
379	return true;
380	MachineRegisterInfo::def_iterator Begin = MRI->def_begin(RegNo: Reg);
381	// If there are multiple defs, we can't do a simple analysis, so just
382	// go with what the kill flag says.
383	if (std::next(x: Begin) != MRI->def_end())
384	return true;
385	DefMI = Begin->getParent();
386	bool IsSrcPhys, IsDstPhys;
387	Register SrcReg, DstReg;
388	// If the def is something other than a copy, then it isn't going to
389	// be coalesced, so follow the kill flag.
390	if (!isCopyToReg(MI&: *DefMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
391	return true;
392	Reg = SrcReg;
393	}
394	}
395
396	/// Return true if the specified MI uses the specified register as a two-address
397	/// use. If so, return the destination register by reference.
398	static bool isTwoAddrUse(MachineInstr &MI, Register Reg, Register &DstReg) {
399	for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) {
400	const MachineOperand &MO = MI.getOperand(i);
401	if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
402	continue;
403	unsigned ti;
404	if (MI.isRegTiedToDefOperand(UseOpIdx: i, DefOpIdx: &ti)) {
405	DstReg = MI.getOperand(i: ti).getReg();
406	return true;
407	}
408	}
409	return false;
410	}
411
412	/// Given a register, if all its uses are in the same basic block, return the
413	/// last use instruction if it's a copy or a two-address use.
414	MachineInstr *TwoAddressInstructionPass::findOnlyInterestingUse(
415	Register Reg, MachineBasicBlock *MBB, bool &IsCopy, Register &DstReg,
416	bool &IsDstPhys) const {
417	MachineOperand *UseOp = nullptr;
418	for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
419	MachineInstr *MI = MO.getParent();
420	if (MI->getParent() != MBB)
421	return nullptr;
422	if (isPlainlyKilled(MI, Reg))
423	UseOp = &MO;
424	}
425	if (!UseOp)
426	return nullptr;
427	MachineInstr &UseMI = *UseOp->getParent();
428
429	Register SrcReg;
430	bool IsSrcPhys;
431	if (isCopyToReg(MI&: UseMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
432	IsCopy = true;
433	return &UseMI;
434	}
435	IsDstPhys = false;
436	if (isTwoAddrUse(MI&: UseMI, Reg, DstReg)) {
437	IsDstPhys = DstReg.isPhysical();
438	return &UseMI;
439	}
440	if (UseMI.isCommutable()) {
441	unsigned Src1 = TargetInstrInfo::CommuteAnyOperandIndex;
442	unsigned Src2 = UseOp->getOperandNo();
443	if (TII->findCommutedOpIndices(MI: UseMI, SrcOpIdx1&: Src1, SrcOpIdx2&: Src2)) {
444	MachineOperand &MO = UseMI.getOperand(i: Src1);
445	if (MO.isReg() && MO.isUse() &&
446	isTwoAddrUse(MI&: UseMI, Reg: MO.getReg(), DstReg)) {
447	IsDstPhys = DstReg.isPhysical();
448	return &UseMI;
449	}
450	}
451	}
452	return nullptr;
453	}
454
455	/// Return the physical register the specified virtual register might be mapped
456	/// to.
457	static MCRegister getMappedReg(Register Reg,
458	DenseMap<Register, Register> &RegMap) {
459	while (Reg.isVirtual()) {
460	DenseMap<Register, Register>::iterator SI = RegMap.find(Val: Reg);
461	if (SI == RegMap.end())
462	return 0;
463	Reg = SI->second;
464	}
465	if (Reg.isPhysical())
466	return Reg;
467	return 0;
468	}
469
470	/// Return true if the two registers are equal or aliased.
471	bool TwoAddressInstructionPass::regsAreCompatible(Register RegA,
472	Register RegB) const {
473	if (RegA == RegB)
474	return true;
475	if (!RegA || !RegB)
476	return false;
477	return TRI->regsOverlap(RegA, RegB);
478	}
479
480	/// From RegMap remove entries mapped to a physical register which overlaps MO.
481	void TwoAddressInstructionPass::removeMapRegEntry(
482	const MachineOperand &MO, DenseMap<Register, Register> &RegMap) const {
483	assert(
484	(MO.isReg() || MO.isRegMask()) &&
485	"removeMapRegEntry must be called with a register or regmask operand.");
486
487	SmallVector<Register, 2> Srcs;
488	for (auto SI : RegMap) {
489	Register ToReg = SI.second;
490	if (ToReg.isVirtual())
491	continue;
492
493	if (MO.isReg()) {
494	Register Reg = MO.getReg();
495	if (TRI->regsOverlap(RegA: ToReg, RegB: Reg))
496	Srcs.push_back(Elt: SI.first);
497	} else if (MO.clobbersPhysReg(PhysReg: ToReg))
498	Srcs.push_back(Elt: SI.first);
499	}
500
501	for (auto SrcReg : Srcs)
502	RegMap.erase(Val: SrcReg);
503	}
504
505	/// If a physical register is clobbered, old entries mapped to it should be
506	/// deleted. For example
507	///
508	/// %2:gr64 = COPY killed $rdx
509	/// MUL64r %3:gr64, implicit-def $rax, implicit-def $rdx
510	///
511	/// After the MUL instruction, $rdx contains different value than in the COPY
512	/// instruction. So %2 should not map to $rdx after MUL.
513	void TwoAddressInstructionPass::removeClobberedSrcRegMap(MachineInstr *MI) {
514	if (MI->isCopy()) {
515	// If a virtual register is copied to its mapped physical register, it
516	// doesn't change the potential coalescing between them, so we don't remove
517	// entries mapped to the physical register. For example
518	//
519	// %100 = COPY $r8
520	// ...
521	// $r8 = COPY %100
522	//
523	// The first copy constructs SrcRegMap[%100] = $r8, the second copy doesn't
524	// destroy the content of $r8, and should not impact SrcRegMap.
525	Register Dst = MI->getOperand(i: 0).getReg();
526	if (!Dst || Dst.isVirtual())
527	return;
528
529	Register Src = MI->getOperand(i: 1).getReg();
530	if (regsAreCompatible(RegA: Dst, RegB: getMappedReg(Reg: Src, RegMap&: SrcRegMap)))
531	return;
532	}
533
534	for (const MachineOperand &MO : MI->operands()) {
535	if (MO.isRegMask()) {
536	removeMapRegEntry(MO, RegMap&: SrcRegMap);
537	continue;
538	}
539	if (!MO.isReg() || !MO.isDef())
540	continue;
541	Register Reg = MO.getReg();
542	if (!Reg || Reg.isVirtual())
543	continue;
544	removeMapRegEntry(MO, RegMap&: SrcRegMap);
545	}
546	}
547
548	// Returns true if Reg is equal or aliased to at least one register in Set.
549	bool TwoAddressInstructionPass::regOverlapsSet(
550	const SmallVectorImpl<Register> &Set, Register Reg) const {
551	for (unsigned R : Set)
552	if (TRI->regsOverlap(RegA: R, RegB: Reg))
553	return true;
554
555	return false;
556	}
557
558	/// Return true if it's potentially profitable to commute the two-address
559	/// instruction that's being processed.
560	bool TwoAddressInstructionPass::isProfitableToCommute(Register RegA,
561	Register RegB,
562	Register RegC,
563	MachineInstr *MI,
564	unsigned Dist) {
565	if (OptLevel == CodeGenOptLevel::None)
566	return false;
567
568	// Determine if it's profitable to commute this two address instruction. In
569	// general, we want no uses between this instruction and the definition of
570	// the two-address register.
571	// e.g.
572	// %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
573	// %reg1029 = COPY %reg1028
574	// %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
575	// insert => %reg1030 = COPY %reg1028
576	// %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
577	// In this case, it might not be possible to coalesce the second COPY
578	// instruction if the first one is coalesced. So it would be profitable to
579	// commute it:
580	// %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
581	// %reg1029 = COPY %reg1028
582	// %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
583	// insert => %reg1030 = COPY %reg1029
584	// %reg1030 = ADD8rr killed %reg1029, killed %reg1028, implicit dead %eflags
585
586	if (!isPlainlyKilled(MI, Reg: RegC))
587	return false;
588
589	// Ok, we have something like:
590	// %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
591	// let's see if it's worth commuting it.
592
593	// Look for situations like this:
594	// %reg1024 = MOV r1
595	// %reg1025 = MOV r0
596	// %reg1026 = ADD %reg1024, %reg1025
597	// r0 = MOV %reg1026
598	// Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
599	MCRegister ToRegA = getMappedReg(Reg: RegA, RegMap&: DstRegMap);
600	if (ToRegA) {
601	MCRegister FromRegB = getMappedReg(Reg: RegB, RegMap&: SrcRegMap);
602	MCRegister FromRegC = getMappedReg(Reg: RegC, RegMap&: SrcRegMap);
603	bool CompB = FromRegB && regsAreCompatible(RegA: FromRegB, RegB: ToRegA);
604	bool CompC = FromRegC && regsAreCompatible(RegA: FromRegC, RegB: ToRegA);
605
606	// Compute if any of the following are true:
607	// -RegB is not tied to a register and RegC is compatible with RegA.
608	// -RegB is tied to the wrong physical register, but RegC is.
609	// -RegB is tied to the wrong physical register, and RegC isn't tied.
610	if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC)))
611	return true;
612	// Don't compute if any of the following are true:
613	// -RegC is not tied to a register and RegB is compatible with RegA.
614	// -RegC is tied to the wrong physical register, but RegB is.
615	// -RegC is tied to the wrong physical register, and RegB isn't tied.
616	if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB)))
617	return false;
618	}
619
620	// If there is a use of RegC between its last def (could be livein) and this
621	// instruction, then bail.
622	unsigned LastDefC = 0;
623	if (!noUseAfterLastDef(Reg: RegC, Dist, LastDef&: LastDefC))
624	return false;
625
626	// If there is a use of RegB between its last def (could be livein) and this
627	// instruction, then go ahead and make this transformation.
628	unsigned LastDefB = 0;
629	if (!noUseAfterLastDef(Reg: RegB, Dist, LastDef&: LastDefB))
630	return true;
631
632	// Look for situation like this:
633	// %reg101 = MOV %reg100
634	// %reg102 = ...
635	// %reg103 = ADD %reg102, %reg101
636	// ... = %reg103 ...
637	// %reg100 = MOV %reg103
638	// If there is a reversed copy chain from reg101 to reg103, commute the ADD
639	// to eliminate an otherwise unavoidable copy.
640	// FIXME:
641	// We can extend the logic further: If an pair of operands in an insn has
642	// been merged, the insn could be regarded as a virtual copy, and the virtual
643	// copy could also be used to construct a copy chain.
644	// To more generally minimize register copies, ideally the logic of two addr
645	// instruction pass should be integrated with register allocation pass where
646	// interference graph is available.
647	if (isRevCopyChain(FromReg: RegC, ToReg: RegA, Maxlen: MaxDataFlowEdge))
648	return true;
649
650	if (isRevCopyChain(FromReg: RegB, ToReg: RegA, Maxlen: MaxDataFlowEdge))
651	return false;
652
653	// Look for other target specific commute preference.
654	bool Commute;
655	if (TII->hasCommutePreference(MI&: *MI, Commute))
656	return Commute;
657
658	// Since there are no intervening uses for both registers, then commute
659	// if the def of RegC is closer. Its live interval is shorter.
660	return LastDefB && LastDefC && LastDefC > LastDefB;
661	}
662
663	/// Commute a two-address instruction and update the basic block, distance map,
664	/// and live variables if needed. Return true if it is successful.
665	bool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI,
666	unsigned DstIdx,
667	unsigned RegBIdx,
668	unsigned RegCIdx,
669	unsigned Dist) {
670	Register RegC = MI->getOperand(i: RegCIdx).getReg();
671	LLVM_DEBUG(dbgs() << "2addr: COMMUTING : " << *MI);
672	MachineInstr *NewMI = TII->commuteInstruction(MI&: *MI, NewMI: false, OpIdx1: RegBIdx, OpIdx2: RegCIdx);
673
674	if (NewMI == nullptr) {
675	LLVM_DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
676	return false;
677	}
678
679	LLVM_DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
680	assert(NewMI == MI &&
681	"TargetInstrInfo::commuteInstruction() should not return a new "
682	"instruction unless it was requested.");
683
684	// Update source register map.
685	MCRegister FromRegC = getMappedReg(Reg: RegC, RegMap&: SrcRegMap);
686	if (FromRegC) {
687	Register RegA = MI->getOperand(i: DstIdx).getReg();
688	SrcRegMap[RegA] = FromRegC;
689	}
690
691	return true;
692	}
693
694	/// Return true if it is profitable to convert the given 2-address instruction
695	/// to a 3-address one.
696	bool TwoAddressInstructionPass::isProfitableToConv3Addr(Register RegA,
697	Register RegB) {
698	// Look for situations like this:
699	// %reg1024 = MOV r1
700	// %reg1025 = MOV r0
701	// %reg1026 = ADD %reg1024, %reg1025
702	// r2 = MOV %reg1026
703	// Turn ADD into a 3-address instruction to avoid a copy.
704	MCRegister FromRegB = getMappedReg(Reg: RegB, RegMap&: SrcRegMap);
705	if (!FromRegB)
706	return false;
707	MCRegister ToRegA = getMappedReg(Reg: RegA, RegMap&: DstRegMap);
708	return (ToRegA && !regsAreCompatible(RegA: FromRegB, RegB: ToRegA));
709	}
710
711	/// Convert the specified two-address instruction into a three address one.
712	/// Return true if this transformation was successful.
713	bool TwoAddressInstructionPass::convertInstTo3Addr(
714	MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi,
715	Register RegA, Register RegB, unsigned &Dist) {
716	MachineInstrSpan MIS(mi, MBB);
717	MachineInstr *NewMI = TII->convertToThreeAddress(MI&: *mi, LV, LIS);
718	if (!NewMI)
719	return false;
720
721	LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
722	LLVM_DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI);
723
724	// If the old instruction is debug value tracked, an update is required.
725	if (auto OldInstrNum = mi->peekDebugInstrNum()) {
726	assert(mi->getNumExplicitDefs() == 1);
727	assert(NewMI->getNumExplicitDefs() == 1);
728
729	// Find the old and new def location.
730	unsigned OldIdx = mi->defs().begin()->getOperandNo();
731	unsigned NewIdx = NewMI->defs().begin()->getOperandNo();
732
733	// Record that one def has been replaced by the other.
734	unsigned NewInstrNum = NewMI->getDebugInstrNum();
735	MF->makeDebugValueSubstitution(std::make_pair(x&: OldInstrNum, y&: OldIdx),
736	std::make_pair(x&: NewInstrNum, y&: NewIdx));
737	}
738
739	MBB->erase(I: mi); // Nuke the old inst.
740
741	for (MachineInstr &MI : MIS)
742	DistanceMap.insert(KV: std::make_pair(x: &MI, y: Dist++));
743	Dist--;
744	mi = NewMI;
745	nmi = std::next(x: mi);
746
747	// Update source and destination register maps.
748	SrcRegMap.erase(Val: RegA);
749	DstRegMap.erase(Val: RegB);
750	return true;
751	}
752
753	/// Scan forward recursively for only uses, update maps if the use is a copy or
754	/// a two-address instruction.
755	void TwoAddressInstructionPass::scanUses(Register DstReg) {
756	SmallVector<Register, 4> VirtRegPairs;
757	bool IsDstPhys;
758	bool IsCopy = false;
759	Register NewReg;
760	Register Reg = DstReg;
761	while (MachineInstr *UseMI =
762	findOnlyInterestingUse(Reg, MBB, IsCopy, DstReg&: NewReg, IsDstPhys)) {
763	if (IsCopy && !Processed.insert(Ptr: UseMI).second)
764	break;
765
766	DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(Val: UseMI);
767	if (DI != DistanceMap.end())
768	// Earlier in the same MBB.Reached via a back edge.
769	break;
770
771	if (IsDstPhys) {
772	VirtRegPairs.push_back(Elt: NewReg);
773	break;
774	}
775	SrcRegMap[NewReg] = Reg;
776	VirtRegPairs.push_back(Elt: NewReg);
777	Reg = NewReg;
778	}
779
780	if (!VirtRegPairs.empty()) {
781	unsigned ToReg = VirtRegPairs.back();
782	VirtRegPairs.pop_back();
783	while (!VirtRegPairs.empty()) {
784	unsigned FromReg = VirtRegPairs.pop_back_val();
785	bool isNew = DstRegMap.insert(KV: std::make_pair(x&: FromReg, y&: ToReg)).second;
786	if (!isNew)
787	assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
788	ToReg = FromReg;
789	}
790	bool isNew = DstRegMap.insert(KV: std::make_pair(x&: DstReg, y&: ToReg)).second;
791	if (!isNew)
792	assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
793	}
794	}
795
796	/// If the specified instruction is not yet processed, process it if it's a
797	/// copy. For a copy instruction, we find the physical registers the
798	/// source and destination registers might be mapped to. These are kept in
799	/// point-to maps used to determine future optimizations. e.g.
800	/// v1024 = mov r0
801	/// v1025 = mov r1
802	/// v1026 = add v1024, v1025
803	/// r1 = mov r1026
804	/// If 'add' is a two-address instruction, v1024, v1026 are both potentially
805	/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
806	/// potentially joined with r1 on the output side. It's worthwhile to commute
807	/// 'add' to eliminate a copy.
808	void TwoAddressInstructionPass::processCopy(MachineInstr *MI) {
809	if (Processed.count(Ptr: MI))
810	return;
811
812	bool IsSrcPhys, IsDstPhys;
813	Register SrcReg, DstReg;
814	if (!isCopyToReg(MI&: *MI, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
815	return;
816
817	if (IsDstPhys && !IsSrcPhys) {
818	DstRegMap.insert(KV: std::make_pair(x&: SrcReg, y&: DstReg));
819	} else if (!IsDstPhys && IsSrcPhys) {
820	bool isNew = SrcRegMap.insert(KV: std::make_pair(x&: DstReg, y&: SrcReg)).second;
821	if (!isNew)
822	assert(SrcRegMap[DstReg] == SrcReg &&
823	"Can't map to two src physical registers!");
824
825	scanUses(DstReg);
826	}
827
828	Processed.insert(Ptr: MI);
829	}
830
831	/// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
832	/// consider moving the instruction below the kill instruction in order to
833	/// eliminate the need for the copy.
834	bool TwoAddressInstructionPass::rescheduleMIBelowKill(
835	MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi,
836	Register Reg) {
837	// Bail immediately if we don't have LV or LIS available. We use them to find
838	// kills efficiently.
839	if (!LV && !LIS)
840	return false;
841
842	MachineInstr *MI = &*mi;
843	DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(Val: MI);
844	if (DI == DistanceMap.end())
845	// Must be created from unfolded load. Don't waste time trying this.
846	return false;
847
848	MachineInstr *KillMI = nullptr;
849	if (LIS) {
850	LiveInterval &LI = LIS->getInterval(Reg);
851	assert(LI.end() != LI.begin() &&
852	"Reg should not have empty live interval.");
853
854	SlotIndex MBBEndIdx = LIS->getMBBEndIdx(mbb: MBB).getPrevSlot();
855	LiveInterval::const_iterator I = LI.find(Pos: MBBEndIdx);
856	if (I != LI.end() && I->start < MBBEndIdx)
857	return false;
858
859	--I;
860	KillMI = LIS->getInstructionFromIndex(index: I->end);
861	} else {
862	KillMI = LV->getVarInfo(Reg).findKill(MBB);
863	}
864	if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
865	// Don't mess with copies, they may be coalesced later.
866	return false;
867
868	if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
869	KillMI->isBranch() || KillMI->isTerminator())
870	// Don't move pass calls, etc.
871	return false;
872
873	Register DstReg;
874	if (isTwoAddrUse(MI&: *KillMI, Reg, DstReg))
875	return false;
876
877	bool SeenStore = true;
878	if (!MI->isSafeToMove(AA, SawStore&: SeenStore))
879	return false;
880
881	if (TII->getInstrLatency(ItinData: InstrItins, MI: *MI) > 1)
882	// FIXME: Needs more sophisticated heuristics.
883	return false;
884
885	SmallVector<Register, 2> Uses;
886	SmallVector<Register, 2> Kills;
887	SmallVector<Register, 2> Defs;
888	for (const MachineOperand &MO : MI->operands()) {
889	if (!MO.isReg())
890	continue;
891	Register MOReg = MO.getReg();
892	if (!MOReg)
893	continue;
894	if (MO.isDef())
895	Defs.push_back(Elt: MOReg);
896	else {
897	Uses.push_back(Elt: MOReg);
898	if (MOReg != Reg && isPlainlyKilled(MO))
899	Kills.push_back(Elt: MOReg);
900	}
901	}
902
903	// Move the copies connected to MI down as well.
904	MachineBasicBlock::iterator Begin = MI;
905	MachineBasicBlock::iterator AfterMI = std::next(x: Begin);
906	MachineBasicBlock::iterator End = AfterMI;
907	while (End != MBB->end()) {
908	End = skipDebugInstructionsForward(It: End, End: MBB->end());
909	if (End->isCopy() && regOverlapsSet(Set: Defs, Reg: End->getOperand(i: 1).getReg()))
910	Defs.push_back(Elt: End->getOperand(i: 0).getReg());
911	else
912	break;
913	++End;
914	}
915
916	// Check if the reschedule will not break dependencies.
917	unsigned NumVisited = 0;
918	MachineBasicBlock::iterator KillPos = KillMI;
919	++KillPos;
920	for (MachineInstr &OtherMI : make_range(x: End, y: KillPos)) {
921	// Debug or pseudo instructions cannot be counted against the limit.
922	if (OtherMI.isDebugOrPseudoInstr())
923	continue;
924	if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
925	return false;
926	++NumVisited;
927	if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
928	OtherMI.isBranch() || OtherMI.isTerminator())
929	// Don't move pass calls, etc.
930	return false;
931	for (const MachineOperand &MO : OtherMI.operands()) {
932	if (!MO.isReg())
933	continue;
934	Register MOReg = MO.getReg();
935	if (!MOReg)
936	continue;
937	if (MO.isDef()) {
938	if (regOverlapsSet(Set: Uses, Reg: MOReg))
939	// Physical register use would be clobbered.
940	return false;
941	if (!MO.isDead() && regOverlapsSet(Set: Defs, Reg: MOReg))
942	// May clobber a physical register def.
943	// FIXME: This may be too conservative. It's ok if the instruction
944	// is sunken completely below the use.
945	return false;
946	} else {
947	if (regOverlapsSet(Set: Defs, Reg: MOReg))
948	return false;
949	bool isKill = isPlainlyKilled(MO);
950	if (MOReg != Reg && ((isKill && regOverlapsSet(Set: Uses, Reg: MOReg)) ||
951	regOverlapsSet(Set: Kills, Reg: MOReg)))
952	// Don't want to extend other live ranges and update kills.
953	return false;
954	if (MOReg == Reg && !isKill)
955	// We can't schedule across a use of the register in question.
956	return false;
957	// Ensure that if this is register in question, its the kill we expect.
958	assert((MOReg != Reg || &OtherMI == KillMI) &&
959	"Found multiple kills of a register in a basic block");
960	}
961	}
962	}
963
964	// Move debug info as well.
965	while (Begin != MBB->begin() && std::prev(x: Begin)->isDebugInstr())
966	--Begin;
967
968	nmi = End;
969	MachineBasicBlock::iterator InsertPos = KillPos;
970	if (LIS) {
971	// We have to move the copies (and any interleaved debug instructions)
972	// first so that the MBB is still well-formed when calling handleMove().
973	for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) {
974	auto CopyMI = MBBI++;
975	MBB->splice(Where: InsertPos, Other: MBB, From: CopyMI);
976	if (!CopyMI->isDebugOrPseudoInstr())
977	LIS->handleMove(MI&: *CopyMI);
978	InsertPos = CopyMI;
979	}
980	End = std::next(x: MachineBasicBlock::iterator(MI));
981	}
982
983	// Copies following MI may have been moved as well.
984	MBB->splice(Where: InsertPos, Other: MBB, From: Begin, To: End);
985	DistanceMap.erase(I: DI);
986
987	// Update live variables
988	if (LIS) {
989	LIS->handleMove(MI&: *MI);
990	} else {
991	LV->removeVirtualRegisterKilled(Reg, MI&: *KillMI);
992	LV->addVirtualRegisterKilled(IncomingReg: Reg, MI&: *MI);
993	}
994
995	LLVM_DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI);
996	return true;
997	}
998
999	/// Return true if the re-scheduling will put the given instruction too close
1000	/// to the defs of its register dependencies.
1001	bool TwoAddressInstructionPass::isDefTooClose(Register Reg, unsigned Dist,
1002	MachineInstr *MI) {
1003	for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
1004	if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike())
1005	continue;
1006	if (&DefMI == MI)
1007	return true; // MI is defining something KillMI uses
1008	DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(Val: &DefMI);
1009	if (DDI == DistanceMap.end())
1010	return true; // Below MI
1011	unsigned DefDist = DDI->second;
1012	assert(Dist > DefDist && "Visited def already?");
1013	if (TII->getInstrLatency(ItinData: InstrItins, MI: DefMI) > (Dist - DefDist))
1014	return true;
1015	}
1016	return false;
1017	}
1018
1019	/// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
1020	/// consider moving the kill instruction above the current two-address
1021	/// instruction in order to eliminate the need for the copy.
1022	bool TwoAddressInstructionPass::rescheduleKillAboveMI(
1023	MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi,
1024	Register Reg) {
1025	// Bail immediately if we don't have LV or LIS available. We use them to find
1026	// kills efficiently.
1027	if (!LV && !LIS)
1028	return false;
1029
1030	MachineInstr *MI = &*mi;
1031	DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(Val: MI);
1032	if (DI == DistanceMap.end())
1033	// Must be created from unfolded load. Don't waste time trying this.
1034	return false;
1035
1036	MachineInstr *KillMI = nullptr;
1037	if (LIS) {
1038	LiveInterval &LI = LIS->getInterval(Reg);
1039	assert(LI.end() != LI.begin() &&
1040	"Reg should not have empty live interval.");
1041
1042	SlotIndex MBBEndIdx = LIS->getMBBEndIdx(mbb: MBB).getPrevSlot();
1043	LiveInterval::const_iterator I = LI.find(Pos: MBBEndIdx);
1044	if (I != LI.end() && I->start < MBBEndIdx)
1045	return false;
1046
1047	--I;
1048	KillMI = LIS->getInstructionFromIndex(index: I->end);
1049	} else {
1050	KillMI = LV->getVarInfo(Reg).findKill(MBB);
1051	}
1052	if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
1053	// Don't mess with copies, they may be coalesced later.
1054	return false;
1055
1056	Register DstReg;
1057	if (isTwoAddrUse(MI&: *KillMI, Reg, DstReg))
1058	return false;
1059
1060	bool SeenStore = true;
1061	if (!KillMI->isSafeToMove(AA, SawStore&: SeenStore))
1062	return false;
1063
1064	SmallVector<Register, 2> Uses;
1065	SmallVector<Register, 2> Kills;
1066	SmallVector<Register, 2> Defs;
1067	SmallVector<Register, 2> LiveDefs;
1068	for (const MachineOperand &MO : KillMI->operands()) {
1069	if (!MO.isReg())
1070	continue;
1071	Register MOReg = MO.getReg();
1072	if (MO.isUse()) {
1073	if (!MOReg)
1074	continue;
1075	if (isDefTooClose(Reg: MOReg, Dist: DI->second, MI))
1076	return false;
1077	bool isKill = isPlainlyKilled(MO);
1078	if (MOReg == Reg && !isKill)
1079	return false;
1080	Uses.push_back(Elt: MOReg);
1081	if (isKill && MOReg != Reg)
1082	Kills.push_back(Elt: MOReg);
1083	} else if (MOReg.isPhysical()) {
1084	Defs.push_back(Elt: MOReg);
1085	if (!MO.isDead())
1086	LiveDefs.push_back(Elt: MOReg);
1087	}
1088	}
1089
1090	// Check if the reschedule will not break depedencies.
1091	unsigned NumVisited = 0;
1092	for (MachineInstr &OtherMI :
1093	make_range(x: mi, y: MachineBasicBlock::iterator(KillMI))) {
1094	// Debug or pseudo instructions cannot be counted against the limit.
1095	if (OtherMI.isDebugOrPseudoInstr())
1096	continue;
1097	if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
1098	return false;
1099	++NumVisited;
1100	if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
1101	OtherMI.isBranch() || OtherMI.isTerminator())
1102	// Don't move pass calls, etc.
1103	return false;
1104	SmallVector<Register, 2> OtherDefs;
1105	for (const MachineOperand &MO : OtherMI.operands()) {
1106	if (!MO.isReg())
1107	continue;
1108	Register MOReg = MO.getReg();
1109	if (!MOReg)
1110	continue;
1111	if (MO.isUse()) {
1112	if (regOverlapsSet(Set: Defs, Reg: MOReg))
1113	// Moving KillMI can clobber the physical register if the def has
1114	// not been seen.
1115	return false;
1116	if (regOverlapsSet(Set: Kills, Reg: MOReg))
1117	// Don't want to extend other live ranges and update kills.
1118	return false;
1119	if (&OtherMI != MI && MOReg == Reg && !isPlainlyKilled(MO))
1120	// We can't schedule across a use of the register in question.
1121	return false;
1122	} else {
1123	OtherDefs.push_back(Elt: MOReg);
1124	}
1125	}
1126
1127	for (Register MOReg : OtherDefs) {
1128	if (regOverlapsSet(Set: Uses, Reg: MOReg))
1129	return false;
1130	if (MOReg.isPhysical() && regOverlapsSet(Set: LiveDefs, Reg: MOReg))
1131	return false;
1132	// Physical register def is seen.
1133	llvm::erase(C&: Defs, V: MOReg);
1134	}
1135	}
1136
1137	// Move the old kill above MI, don't forget to move debug info as well.
1138	MachineBasicBlock::iterator InsertPos = mi;
1139	while (InsertPos != MBB->begin() && std::prev(x: InsertPos)->isDebugInstr())
1140	--InsertPos;
1141	MachineBasicBlock::iterator From = KillMI;
1142	MachineBasicBlock::iterator To = std::next(x: From);
1143	while (std::prev(x: From)->isDebugInstr())
1144	--From;
1145	MBB->splice(Where: InsertPos, Other: MBB, From, To);
1146
1147	nmi = std::prev(x: InsertPos); // Backtrack so we process the moved instr.
1148	DistanceMap.erase(I: DI);
1149
1150	// Update live variables
1151	if (LIS) {
1152	LIS->handleMove(MI&: *KillMI);
1153	} else {
1154	LV->removeVirtualRegisterKilled(Reg, MI&: *KillMI);
1155	LV->addVirtualRegisterKilled(IncomingReg: Reg, MI&: *MI);
1156	}
1157
1158	LLVM_DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1159	return true;
1160	}
1161
1162	/// Tries to commute the operand 'BaseOpIdx' and some other operand in the
1163	/// given machine instruction to improve opportunities for coalescing and
1164	/// elimination of a register to register copy.
1165	///
1166	/// 'DstOpIdx' specifies the index of MI def operand.
1167	/// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx'
1168	/// operand is killed by the given instruction.
1169	/// The 'Dist' arguments provides the distance of MI from the start of the
1170	/// current basic block and it is used to determine if it is profitable
1171	/// to commute operands in the instruction.
1172	///
1173	/// Returns true if the transformation happened. Otherwise, returns false.
1174	bool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI,
1175	unsigned DstOpIdx,
1176	unsigned BaseOpIdx,
1177	bool BaseOpKilled,
1178	unsigned Dist) {
1179	if (!MI->isCommutable())
1180	return false;
1181
1182	bool MadeChange = false;
1183	Register DstOpReg = MI->getOperand(i: DstOpIdx).getReg();
1184	Register BaseOpReg = MI->getOperand(i: BaseOpIdx).getReg();
1185	unsigned OpsNum = MI->getDesc().getNumOperands();
1186	unsigned OtherOpIdx = MI->getDesc().getNumDefs();
1187	for (; OtherOpIdx < OpsNum; OtherOpIdx++) {
1188	// The call of findCommutedOpIndices below only checks if BaseOpIdx
1189	// and OtherOpIdx are commutable, it does not really search for
1190	// other commutable operands and does not change the values of passed
1191	// variables.
1192	if (OtherOpIdx == BaseOpIdx || !MI->getOperand(i: OtherOpIdx).isReg() ||
1193	!TII->findCommutedOpIndices(MI: *MI, SrcOpIdx1&: BaseOpIdx, SrcOpIdx2&: OtherOpIdx))
1194	continue;
1195
1196	Register OtherOpReg = MI->getOperand(i: OtherOpIdx).getReg();
1197	bool AggressiveCommute = false;
1198
1199	// If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp
1200	// operands. This makes the live ranges of DstOp and OtherOp joinable.
1201	bool OtherOpKilled = isKilled(MI&: *MI, Reg: OtherOpReg, allowFalsePositives: false);
1202	bool DoCommute = !BaseOpKilled && OtherOpKilled;
1203
1204	if (!DoCommute &&
1205	isProfitableToCommute(RegA: DstOpReg, RegB: BaseOpReg, RegC: OtherOpReg, MI, Dist)) {
1206	DoCommute = true;
1207	AggressiveCommute = true;
1208	}
1209
1210	// If it's profitable to commute, try to do so.
1211	if (DoCommute && commuteInstruction(MI, DstIdx: DstOpIdx, RegBIdx: BaseOpIdx, RegCIdx: OtherOpIdx,
1212	Dist)) {
1213	MadeChange = true;
1214	++NumCommuted;
1215	if (AggressiveCommute)
1216	++NumAggrCommuted;
1217
1218	// There might be more than two commutable operands, update BaseOp and
1219	// continue scanning.
1220	// FIXME: This assumes that the new instruction's operands are in the
1221	// same positions and were simply swapped.
1222	BaseOpReg = OtherOpReg;
1223	BaseOpKilled = OtherOpKilled;
1224	// Resamples OpsNum in case the number of operands was reduced. This
1225	// happens with X86.
1226	OpsNum = MI->getDesc().getNumOperands();
1227	}
1228	}
1229	return MadeChange;
1230	}
1231
1232	/// For the case where an instruction has a single pair of tied register
1233	/// operands, attempt some transformations that may either eliminate the tied
1234	/// operands or improve the opportunities for coalescing away the register copy.
1235	/// Returns true if no copy needs to be inserted to untie mi's operands
1236	/// (either because they were untied, or because mi was rescheduled, and will
1237	/// be visited again later). If the shouldOnlyCommute flag is true, only
1238	/// instruction commutation is attempted.
1239	bool TwoAddressInstructionPass::
1240	tryInstructionTransform(MachineBasicBlock::iterator &mi,
1241	MachineBasicBlock::iterator &nmi,
1242	unsigned SrcIdx, unsigned DstIdx,
1243	unsigned &Dist, bool shouldOnlyCommute) {
1244	if (OptLevel == CodeGenOptLevel::None)
1245	return false;
1246
1247	MachineInstr &MI = *mi;
1248	Register regA = MI.getOperand(i: DstIdx).getReg();
1249	Register regB = MI.getOperand(i: SrcIdx).getReg();
1250
1251	assert(regB.isVirtual() && "cannot make instruction into two-address form");
1252	bool regBKilled = isKilled(MI, Reg: regB, allowFalsePositives: true);
1253
1254	if (regA.isVirtual())
1255	scanUses(DstReg: regA);
1256
1257	bool Commuted = tryInstructionCommute(MI: &MI, DstOpIdx: DstIdx, BaseOpIdx: SrcIdx, BaseOpKilled: regBKilled, Dist);
1258
1259	// If the instruction is convertible to 3 Addr, instead
1260	// of returning try 3 Addr transformation aggressively and
1261	// use this variable to check later. Because it might be better.
1262	// For example, we can just use `leal (%rsi,%rdi), %eax` and `ret`
1263	// instead of the following code.
1264	// addl %esi, %edi
1265	// movl %edi, %eax
1266	// ret
1267	if (Commuted && !MI.isConvertibleTo3Addr())
1268	return false;
1269
1270	if (shouldOnlyCommute)
1271	return false;
1272
1273	// If there is one more use of regB later in the same MBB, consider
1274	// re-schedule this MI below it.
1275	if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, Reg: regB)) {
1276	++NumReSchedDowns;
1277	return true;
1278	}
1279
1280	// If we commuted, regB may have changed so we should re-sample it to avoid
1281	// confusing the three address conversion below.
1282	if (Commuted) {
1283	regB = MI.getOperand(i: SrcIdx).getReg();
1284	regBKilled = isKilled(MI, Reg: regB, allowFalsePositives: true);
1285	}
1286
1287	if (MI.isConvertibleTo3Addr()) {
1288	// This instruction is potentially convertible to a true
1289	// three-address instruction. Check if it is profitable.
1290	if (!regBKilled || isProfitableToConv3Addr(RegA: regA, RegB: regB)) {
1291	// Try to convert it.
1292	if (convertInstTo3Addr(mi, nmi, RegA: regA, RegB: regB, Dist)) {
1293	++NumConvertedTo3Addr;
1294	return true; // Done with this instruction.
1295	}
1296	}
1297	}
1298
1299	// Return if it is commuted but 3 addr conversion is failed.
1300	if (Commuted)
1301	return false;
1302
1303	// If there is one more use of regB later in the same MBB, consider
1304	// re-schedule it before this MI if it's legal.
1305	if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, Reg: regB)) {
1306	++NumReSchedUps;
1307	return true;
1308	}
1309
1310	// If this is an instruction with a load folded into it, try unfolding
1311	// the load, e.g. avoid this:
1312	// movq %rdx, %rcx
1313	// addq (%rax), %rcx
1314	// in favor of this:
1315	// movq (%rax), %rcx
1316	// addq %rdx, %rcx
1317	// because it's preferable to schedule a load than a register copy.
1318	if (MI.mayLoad() && !regBKilled) {
1319	// Determine if a load can be unfolded.
1320	unsigned LoadRegIndex;
1321	unsigned NewOpc =
1322	TII->getOpcodeAfterMemoryUnfold(Opc: MI.getOpcode(),
1323	/*UnfoldLoad=*/true,
1324	/*UnfoldStore=*/false,
1325	LoadRegIndex: &LoadRegIndex);
1326	if (NewOpc != 0) {
1327	const MCInstrDesc &UnfoldMCID = TII->get(Opcode: NewOpc);
1328	if (UnfoldMCID.getNumDefs() == 1) {
1329	// Unfold the load.
1330	LLVM_DEBUG(dbgs() << "2addr: UNFOLDING: " << MI);
1331	const TargetRegisterClass *RC =
1332	TRI->getAllocatableClass(
1333	RC: TII->getRegClass(MCID: UnfoldMCID, OpNum: LoadRegIndex, TRI, MF: *MF));
1334	Register Reg = MRI->createVirtualRegister(RegClass: RC);
1335	SmallVector<MachineInstr *, 2> NewMIs;
1336	if (!TII->unfoldMemoryOperand(MF&: *MF, MI, Reg,
1337	/*UnfoldLoad=*/true,
1338	/*UnfoldStore=*/false, NewMIs)) {
1339	LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1340	return false;
1341	}
1342	assert(NewMIs.size() == 2 &&
1343	"Unfolded a load into multiple instructions!");
1344	// The load was previously folded, so this is the only use.
1345	NewMIs[1]->addRegisterKilled(IncomingReg: Reg, RegInfo: TRI);
1346
1347	// Tentatively insert the instructions into the block so that they
1348	// look "normal" to the transformation logic.
1349	MBB->insert(I: mi, MI: NewMIs[0]);
1350	MBB->insert(I: mi, MI: NewMIs[1]);
1351	DistanceMap.insert(KV: std::make_pair(x&: NewMIs[0], y: Dist++));
1352	DistanceMap.insert(KV: std::make_pair(x&: NewMIs[1], y&: Dist));
1353
1354	LLVM_DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0]
1355	<< "2addr: NEW INST: " << *NewMIs[1]);
1356
1357	// Transform the instruction, now that it no longer has a load.
1358	unsigned NewDstIdx =
1359	NewMIs[1]->findRegisterDefOperandIdx(Reg: regA, /*TRI=*/nullptr);
1360	unsigned NewSrcIdx =
1361	NewMIs[1]->findRegisterUseOperandIdx(Reg: regB, /*TRI=*/nullptr);
1362	MachineBasicBlock::iterator NewMI = NewMIs[1];
1363	bool TransformResult =
1364	tryInstructionTransform(mi&: NewMI, nmi&: mi, SrcIdx: NewSrcIdx, DstIdx: NewDstIdx, Dist, shouldOnlyCommute: true);
1365	(void)TransformResult;
1366	assert(!TransformResult &&
1367	"tryInstructionTransform() should return false.");
1368	if (NewMIs[1]->getOperand(i: NewSrcIdx).isKill()) {
1369	// Success, or at least we made an improvement. Keep the unfolded
1370	// instructions and discard the original.
1371	if (LV) {
1372	for (const MachineOperand &MO : MI.operands()) {
1373	if (MO.isReg() && MO.getReg().isVirtual()) {
1374	if (MO.isUse()) {
1375	if (MO.isKill()) {
1376	if (NewMIs[0]->killsRegister(Reg: MO.getReg(), /*TRI=*/nullptr))
1377	LV->replaceKillInstruction(Reg: MO.getReg(), OldMI&: MI, NewMI&: *NewMIs[0]);
1378	else {
1379	assert(NewMIs[1]->killsRegister(MO.getReg(),
1380	/*TRI=*/nullptr) &&
1381	"Kill missing after load unfold!");
1382	LV->replaceKillInstruction(Reg: MO.getReg(), OldMI&: MI, NewMI&: *NewMIs[1]);
1383	}
1384	}
1385	} else if (LV->removeVirtualRegisterDead(Reg: MO.getReg(), MI)) {
1386	if (NewMIs[1]->registerDefIsDead(Reg: MO.getReg(),
1387	/*TRI=*/nullptr))
1388	LV->addVirtualRegisterDead(IncomingReg: MO.getReg(), MI&: *NewMIs[1]);
1389	else {
1390	assert(NewMIs[0]->registerDefIsDead(MO.getReg(),
1391	/*TRI=*/nullptr) &&
1392	"Dead flag missing after load unfold!");
1393	LV->addVirtualRegisterDead(IncomingReg: MO.getReg(), MI&: *NewMIs[0]);
1394	}
1395	}
1396	}
1397	}
1398	LV->addVirtualRegisterKilled(IncomingReg: Reg, MI&: *NewMIs[1]);
1399	}
1400
1401	SmallVector<Register, 4> OrigRegs;
1402	if (LIS) {
1403	for (const MachineOperand &MO : MI.operands()) {
1404	if (MO.isReg())
1405	OrigRegs.push_back(Elt: MO.getReg());
1406	}
1407
1408	LIS->RemoveMachineInstrFromMaps(MI);
1409	}
1410
1411	MI.eraseFromParent();
1412	DistanceMap.erase(Val: &MI);
1413
1414	// Update LiveIntervals.
1415	if (LIS) {
1416	MachineBasicBlock::iterator Begin(NewMIs[0]);
1417	MachineBasicBlock::iterator End(NewMIs[1]);
1418	LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1419	}
1420
1421	mi = NewMIs[1];
1422	} else {
1423	// Transforming didn't eliminate the tie and didn't lead to an
1424	// improvement. Clean up the unfolded instructions and keep the
1425	// original.
1426	LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1427	NewMIs[0]->eraseFromParent();
1428	NewMIs[1]->eraseFromParent();
1429	DistanceMap.erase(Val: NewMIs[0]);
1430	DistanceMap.erase(Val: NewMIs[1]);
1431	Dist--;
1432	}
1433	}
1434	}
1435	}
1436
1437	return false;
1438	}
1439
1440	// Collect tied operands of MI that need to be handled.
1441	// Rewrite trivial cases immediately.
1442	// Return true if any tied operands where found, including the trivial ones.
1443	bool TwoAddressInstructionPass::
1444	collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
1445	bool AnyOps = false;
1446	unsigned NumOps = MI->getNumOperands();
1447
1448	for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1449	unsigned DstIdx = 0;
1450	if (!MI->isRegTiedToDefOperand(UseOpIdx: SrcIdx, DefOpIdx: &DstIdx))
1451	continue;
1452	AnyOps = true;
1453	MachineOperand &SrcMO = MI->getOperand(i: SrcIdx);
1454	MachineOperand &DstMO = MI->getOperand(i: DstIdx);
1455	Register SrcReg = SrcMO.getReg();
1456	Register DstReg = DstMO.getReg();
1457	// Tied constraint already satisfied?
1458	if (SrcReg == DstReg)
1459	continue;
1460
1461	assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1462
1463	// Deal with undef uses immediately - simply rewrite the src operand.
1464	if (SrcMO.isUndef() && !DstMO.getSubReg()) {
1465	// Constrain the DstReg register class if required.
1466	if (DstReg.isVirtual()) {
1467	const TargetRegisterClass *RC = MRI->getRegClass(Reg: SrcReg);
1468	MRI->constrainRegClass(Reg: DstReg, RC);
1469	}
1470	SrcMO.setReg(DstReg);
1471	SrcMO.setSubReg(0);
1472	LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1473	continue;
1474	}
1475	TiedOperands[SrcReg].push_back(Elt: std::make_pair(x&: SrcIdx, y&: DstIdx));
1476	}
1477	return AnyOps;
1478	}
1479
1480	// Process a list of tied MI operands that all use the same source register.
1481	// The tied pairs are of the form (SrcIdx, DstIdx).
1482	void
1483	TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
1484	TiedPairList &TiedPairs,
1485	unsigned &Dist) {
1486	bool IsEarlyClobber = llvm::any_of(Range&: TiedPairs, P: [MI](auto const &TP) {
1487	return MI->getOperand(TP.second).isEarlyClobber();
1488	});
1489
1490	bool RemovedKillFlag = false;
1491	bool AllUsesCopied = true;
1492	unsigned LastCopiedReg = 0;
1493	SlotIndex LastCopyIdx;
1494	Register RegB = 0;
1495	unsigned SubRegB = 0;
1496	for (auto &TP : TiedPairs) {
1497	unsigned SrcIdx = TP.first;
1498	unsigned DstIdx = TP.second;
1499
1500	const MachineOperand &DstMO = MI->getOperand(i: DstIdx);
1501	Register RegA = DstMO.getReg();
1502
1503	// Grab RegB from the instruction because it may have changed if the
1504	// instruction was commuted.
1505	RegB = MI->getOperand(i: SrcIdx).getReg();
1506	SubRegB = MI->getOperand(i: SrcIdx).getSubReg();
1507
1508	if (RegA == RegB) {
1509	// The register is tied to multiple destinations (or else we would
1510	// not have continued this far), but this use of the register
1511	// already matches the tied destination. Leave it.
1512	AllUsesCopied = false;
1513	continue;
1514	}
1515	LastCopiedReg = RegA;
1516
1517	assert(RegB.isVirtual() && "cannot make instruction into two-address form");
1518
1519	#ifndef NDEBUG
1520	// First, verify that we don't have a use of "a" in the instruction
1521	// (a = b + a for example) because our transformation will not
1522	// work. This should never occur because we are in SSA form.
1523	for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1524	assert(i == DstIdx ||
1525	!MI->getOperand(i).isReg() ||
1526	MI->getOperand(i).getReg() != RegA);
1527	#endif
1528
1529	// Emit a copy.
1530	MachineInstrBuilder MIB = BuildMI(BB&: *MI->getParent(), I: MI, MIMD: MI->getDebugLoc(),
1531	MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: RegA);
1532	// If this operand is folding a truncation, the truncation now moves to the
1533	// copy so that the register classes remain valid for the operands.
1534	MIB.addReg(RegNo: RegB, flags: 0, SubReg: SubRegB);
1535	const TargetRegisterClass *RC = MRI->getRegClass(Reg: RegB);
1536	if (SubRegB) {
1537	if (RegA.isVirtual()) {
1538	assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA),
1539	SubRegB) &&
1540	"tied subregister must be a truncation");
1541	// The superreg class will not be used to constrain the subreg class.
1542	RC = nullptr;
1543	} else {
1544	assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB))
1545	&& "tied subregister must be a truncation");
1546	}
1547	}
1548
1549	// Update DistanceMap.
1550	MachineBasicBlock::iterator PrevMI = MI;
1551	--PrevMI;
1552	DistanceMap.insert(KV: std::make_pair(x: &*PrevMI, y&: Dist));
1553	DistanceMap[MI] = ++Dist;
1554
1555	if (LIS) {
1556	LastCopyIdx = LIS->InsertMachineInstrInMaps(MI&: *PrevMI).getRegSlot();
1557
1558	SlotIndex endIdx =
1559	LIS->getInstructionIndex(Instr: *MI).getRegSlot(EC: IsEarlyClobber);
1560	if (RegA.isVirtual()) {
1561	LiveInterval &LI = LIS->getInterval(Reg: RegA);
1562	VNInfo *VNI = LI.getNextValue(Def: LastCopyIdx, VNInfoAllocator&: LIS->getVNInfoAllocator());
1563	LI.addSegment(S: LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1564	for (auto &S : LI.subranges()) {
1565	VNI = S.getNextValue(Def: LastCopyIdx, VNInfoAllocator&: LIS->getVNInfoAllocator());
1566	S.addSegment(S: LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1567	}
1568	} else {
1569	for (MCRegUnit Unit : TRI->regunits(Reg: RegA)) {
1570	if (LiveRange *LR = LIS->getCachedRegUnit(Unit)) {
1571	VNInfo *VNI =
1572	LR->getNextValue(Def: LastCopyIdx, VNInfoAllocator&: LIS->getVNInfoAllocator());
1573	LR->addSegment(S: LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1574	}
1575	}
1576	}
1577	}
1578
1579	LLVM_DEBUG(dbgs() << "\t\tprepend:\t" << *MIB);
1580
1581	MachineOperand &MO = MI->getOperand(i: SrcIdx);
1582	assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1583	"inconsistent operand info for 2-reg pass");
1584	if (isPlainlyKilled(MO)) {
1585	MO.setIsKill(false);
1586	RemovedKillFlag = true;
1587	}
1588
1589	// Make sure regA is a legal regclass for the SrcIdx operand.
1590	if (RegA.isVirtual() && RegB.isVirtual())
1591	MRI->constrainRegClass(Reg: RegA, RC);
1592	MO.setReg(RegA);
1593	// The getMatchingSuper asserts guarantee that the register class projected
1594	// by SubRegB is compatible with RegA with no subregister. So regardless of
1595	// whether the dest oper writes a subreg, the source oper should not.
1596	MO.setSubReg(0);
1597	}
1598
1599	if (AllUsesCopied) {
1600	LaneBitmask RemainingUses = LaneBitmask::getNone();
1601	// Replace other (un-tied) uses of regB with LastCopiedReg.
1602	for (MachineOperand &MO : MI->all_uses()) {
1603	if (MO.getReg() == RegB) {
1604	if (MO.getSubReg() == SubRegB && !IsEarlyClobber) {
1605	if (isPlainlyKilled(MO)) {
1606	MO.setIsKill(false);
1607	RemovedKillFlag = true;
1608	}
1609	MO.setReg(LastCopiedReg);
1610	MO.setSubReg(0);
1611	} else {
1612	RemainingUses |= TRI->getSubRegIndexLaneMask(SubIdx: MO.getSubReg());
1613	}
1614	}
1615	}
1616
1617	// Update live variables for regB.
1618	if (RemovedKillFlag && RemainingUses.none() && LV &&
1619	LV->getVarInfo(Reg: RegB).removeKill(MI&: *MI)) {
1620	MachineBasicBlock::iterator PrevMI = MI;
1621	--PrevMI;
1622	LV->addVirtualRegisterKilled(IncomingReg: RegB, MI&: *PrevMI);
1623	}
1624
1625	if (RemovedKillFlag && RemainingUses.none())
1626	SrcRegMap[LastCopiedReg] = RegB;
1627
1628	// Update LiveIntervals.
1629	if (LIS) {
1630	SlotIndex UseIdx = LIS->getInstructionIndex(Instr: *MI);
1631	auto Shrink = [=](LiveRange &LR, LaneBitmask LaneMask) {
1632	LiveRange::Segment *S = LR.getSegmentContaining(Idx: LastCopyIdx);
1633	if (!S)
1634	return true;
1635	if ((LaneMask & RemainingUses).any())
1636	return false;
1637	if (S->end.getBaseIndex() != UseIdx)
1638	return false;
1639	S->end = LastCopyIdx;
1640	return true;
1641	};
1642
1643	LiveInterval &LI = LIS->getInterval(Reg: RegB);
1644	bool ShrinkLI = true;
1645	for (auto &S : LI.subranges())
1646	ShrinkLI &= Shrink(S, S.LaneMask);
1647	if (ShrinkLI)
1648	Shrink(LI, LaneBitmask::getAll());
1649	}
1650	} else if (RemovedKillFlag) {
1651	// Some tied uses of regB matched their destination registers, so
1652	// regB is still used in this instruction, but a kill flag was
1653	// removed from a different tied use of regB, so now we need to add
1654	// a kill flag to one of the remaining uses of regB.
1655	for (MachineOperand &MO : MI->all_uses()) {
1656	if (MO.getReg() == RegB) {
1657	MO.setIsKill(true);
1658	break;
1659	}
1660	}
1661	}
1662	}
1663
1664	// For every tied operand pair this function transforms statepoint from
1665	// RegA = STATEPOINT ... RegB(tied-def N)
1666	// to
1667	// RegB = STATEPOINT ... RegB(tied-def N)
1668	// and replaces all uses of RegA with RegB.
1669	// No extra COPY instruction is necessary because tied use is killed at
1670	// STATEPOINT.
1671	bool TwoAddressInstructionPass::processStatepoint(
1672	MachineInstr *MI, TiedOperandMap &TiedOperands) {
1673
1674	bool NeedCopy = false;
1675	for (auto &TO : TiedOperands) {
1676	Register RegB = TO.first;
1677	if (TO.second.size() != 1) {
1678	NeedCopy = true;
1679	continue;
1680	}
1681
1682	unsigned SrcIdx = TO.second[0].first;
1683	unsigned DstIdx = TO.second[0].second;
1684
1685	MachineOperand &DstMO = MI->getOperand(i: DstIdx);
1686	Register RegA = DstMO.getReg();
1687
1688	assert(RegB == MI->getOperand(SrcIdx).getReg());
1689
1690	if (RegA == RegB)
1691	continue;
1692
1693	// CodeGenPrepare can sink pointer compare past statepoint, which
1694	// breaks assumption that statepoint kills tied-use register when
1695	// in SSA form (see note in IR/SafepointIRVerifier.cpp). Fall back
1696	// to generic tied register handling to avoid assertion failures.
1697	// TODO: Recompute LIS/LV information for new range here.
1698	if (LIS) {
1699	const auto &UseLI = LIS->getInterval(Reg: RegB);
1700	const auto &DefLI = LIS->getInterval(Reg: RegA);
1701	if (DefLI.overlaps(other: UseLI)) {
1702	LLVM_DEBUG(dbgs() << "LIS: " << printReg(RegB, TRI, 0)
1703	<< " UseLI overlaps with DefLI\n");
1704	NeedCopy = true;
1705	continue;
1706	}
1707	} else if (LV && LV->getVarInfo(Reg: RegB).findKill(MBB: MI->getParent()) != MI) {
1708	// Note that MachineOperand::isKill does not work here, because it
1709	// is set only on first register use in instruction and for statepoint
1710	// tied-use register will usually be found in preceeding deopt bundle.
1711	LLVM_DEBUG(dbgs() << "LV: " << printReg(RegB, TRI, 0)
1712	<< " not killed by statepoint\n");
1713	NeedCopy = true;
1714	continue;
1715	}
1716
1717	if (!MRI->constrainRegClass(Reg: RegB, RC: MRI->getRegClass(Reg: RegA))) {
1718	LLVM_DEBUG(dbgs() << "MRI: couldn't constrain" << printReg(RegB, TRI, 0)
1719	<< " to register class of " << printReg(RegA, TRI, 0)
1720	<< '\n');
1721	NeedCopy = true;
1722	continue;
1723	}
1724	MRI->replaceRegWith(FromReg: RegA, ToReg: RegB);
1725
1726	if (LIS) {
1727	VNInfo::Allocator &A = LIS->getVNInfoAllocator();
1728	LiveInterval &LI = LIS->getInterval(Reg: RegB);
1729	LiveInterval &Other = LIS->getInterval(Reg: RegA);
1730	SmallVector<VNInfo *> NewVNIs;
1731	for (const VNInfo *VNI : Other.valnos) {
1732	assert(VNI->id == NewVNIs.size() && "assumed");
1733	NewVNIs.push_back(Elt: LI.createValueCopy(orig: VNI, VNInfoAllocator&: A));
1734	}
1735	for (auto &S : Other) {
1736	VNInfo *VNI = NewVNIs[S.valno->id];
1737	LiveRange::Segment NewSeg(S.start, S.end, VNI);
1738	LI.addSegment(S: NewSeg);
1739	}
1740	LIS->removeInterval(Reg: RegA);
1741	}
1742
1743	if (LV) {
1744	if (MI->getOperand(i: SrcIdx).isKill())
1745	LV->removeVirtualRegisterKilled(Reg: RegB, MI&: *MI);
1746	LiveVariables::VarInfo &SrcInfo = LV->getVarInfo(Reg: RegB);
1747	LiveVariables::VarInfo &DstInfo = LV->getVarInfo(Reg: RegA);
1748	SrcInfo.AliveBlocks |= DstInfo.AliveBlocks;
1749	DstInfo.AliveBlocks.clear();
1750	for (auto *KillMI : DstInfo.Kills)
1751	LV->addVirtualRegisterKilled(IncomingReg: RegB, MI&: *KillMI, AddIfNotFound: false);
1752	}
1753	}
1754	return !NeedCopy;
1755	}
1756
1757	/// Reduce two-address instructions to two operands.
1758	bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
1759	MF = &Func;
1760	const TargetMachine &TM = MF->getTarget();
1761	MRI = &MF->getRegInfo();
1762	TII = MF->getSubtarget().getInstrInfo();
1763	TRI = MF->getSubtarget().getRegisterInfo();
1764	InstrItins = MF->getSubtarget().getInstrItineraryData();
1765	LV = getAnalysisIfAvailable<LiveVariables>();
1766	LIS = getAnalysisIfAvailable<LiveIntervals>();
1767	if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>())
1768	AA = &AAPass->getAAResults();
1769	else
1770	AA = nullptr;
1771	OptLevel = TM.getOptLevel();
1772	// Disable optimizations if requested. We cannot skip the whole pass as some
1773	// fixups are necessary for correctness.
1774	if (skipFunction(F: Func.getFunction()))
1775	OptLevel = CodeGenOptLevel::None;
1776
1777	bool MadeChange = false;
1778
1779	LLVM_DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1780	LLVM_DEBUG(dbgs() << "********** Function: " << MF->getName() << '\n');
1781
1782	// This pass takes the function out of SSA form.
1783	MRI->leaveSSA();
1784
1785	// This pass will rewrite the tied-def to meet the RegConstraint.
1786	MF->getProperties()
1787	.set(MachineFunctionProperties::Property::TiedOpsRewritten);
1788
1789	TiedOperandMap TiedOperands;
1790	for (MachineBasicBlock &MBBI : *MF) {
1791	MBB = &MBBI;
1792	unsigned Dist = 0;
1793	DistanceMap.clear();
1794	SrcRegMap.clear();
1795	DstRegMap.clear();
1796	Processed.clear();
1797	for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1798	mi != me; ) {
1799	MachineBasicBlock::iterator nmi = std::next(x: mi);
1800	// Skip debug instructions.
1801	if (mi->isDebugInstr()) {
1802	mi = nmi;
1803	continue;
1804	}
1805
1806	// Expand REG_SEQUENCE instructions. This will position mi at the first
1807	// expanded instruction.
1808	if (mi->isRegSequence())
1809	eliminateRegSequence(mi);
1810
1811	DistanceMap.insert(KV: std::make_pair(x: &*mi, y&: ++Dist));
1812
1813	processCopy(MI: &*mi);
1814
1815	// First scan through all the tied register uses in this instruction
1816	// and record a list of pairs of tied operands for each register.
1817	if (!collectTiedOperands(MI: &*mi, TiedOperands)) {
1818	removeClobberedSrcRegMap(MI: &*mi);
1819	mi = nmi;
1820	continue;
1821	}
1822
1823	++NumTwoAddressInstrs;
1824	MadeChange = true;
1825	LLVM_DEBUG(dbgs() << '\t' << *mi);
1826
1827	// If the instruction has a single pair of tied operands, try some
1828	// transformations that may either eliminate the tied operands or
1829	// improve the opportunities for coalescing away the register copy.
1830	if (TiedOperands.size() == 1) {
1831	SmallVectorImpl<std::pair<unsigned, unsigned>> &TiedPairs
1832	= TiedOperands.begin()->second;
1833	if (TiedPairs.size() == 1) {
1834	unsigned SrcIdx = TiedPairs[0].first;
1835	unsigned DstIdx = TiedPairs[0].second;
1836	Register SrcReg = mi->getOperand(i: SrcIdx).getReg();
1837	Register DstReg = mi->getOperand(i: DstIdx).getReg();
1838	if (SrcReg != DstReg &&
1839	tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, shouldOnlyCommute: false)) {
1840	// The tied operands have been eliminated or shifted further down
1841	// the block to ease elimination. Continue processing with 'nmi'.
1842	TiedOperands.clear();
1843	removeClobberedSrcRegMap(MI: &*mi);
1844	mi = nmi;
1845	continue;
1846	}
1847	}
1848	}
1849
1850	if (mi->getOpcode() == TargetOpcode::STATEPOINT &&
1851	processStatepoint(MI: &*mi, TiedOperands)) {
1852	TiedOperands.clear();
1853	LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1854	mi = nmi;
1855	continue;
1856	}
1857
1858	// Now iterate over the information collected above.
1859	for (auto &TO : TiedOperands) {
1860	processTiedPairs(MI: &*mi, TiedPairs&: TO.second, Dist);
1861	LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1862	}
1863
1864	// Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1865	if (mi->isInsertSubreg()) {
1866	// From %reg = INSERT_SUBREG %reg, %subreg, subidx
1867	// To %reg:subidx = COPY %subreg
1868	unsigned SubIdx = mi->getOperand(i: 3).getImm();
1869	mi->removeOperand(OpNo: 3);
1870	assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1871	mi->getOperand(i: 0).setSubReg(SubIdx);
1872	mi->getOperand(i: 0).setIsUndef(mi->getOperand(i: 1).isUndef());
1873	mi->removeOperand(OpNo: 1);
1874	mi->setDesc(TII->get(Opcode: TargetOpcode::COPY));
1875	LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1876
1877	// Update LiveIntervals.
1878	if (LIS) {
1879	Register Reg = mi->getOperand(i: 0).getReg();
1880	LiveInterval &LI = LIS->getInterval(Reg);
1881	if (LI.hasSubRanges()) {
1882	// The COPY no longer defines subregs of %reg except for
1883	// %reg.subidx.
1884	LaneBitmask LaneMask =
1885	TRI->getSubRegIndexLaneMask(SubIdx: mi->getOperand(i: 0).getSubReg());
1886	SlotIndex Idx = LIS->getInstructionIndex(Instr: *mi).getRegSlot();
1887	for (auto &S : LI.subranges()) {
1888	if ((S.LaneMask & LaneMask).none()) {
1889	LiveRange::iterator DefSeg = S.FindSegmentContaining(Idx);
1890	if (mi->getOperand(i: 0).isUndef()) {
1891	S.removeValNo(ValNo: DefSeg->valno);
1892	} else {
1893	LiveRange::iterator UseSeg = std::prev(x: DefSeg);
1894	S.MergeValueNumberInto(V1: DefSeg->valno, V2: UseSeg->valno);
1895	}
1896	}
1897	}
1898
1899	// The COPY no longer has a use of %reg.
1900	LIS->shrinkToUses(li: &LI);
1901	} else {
1902	// The live interval for Reg did not have subranges but now it needs
1903	// them because we have introduced a subreg def. Recompute it.
1904	LIS->removeInterval(Reg);
1905	LIS->createAndComputeVirtRegInterval(Reg);
1906	}
1907	}
1908	}
1909
1910	// Clear TiedOperands here instead of at the top of the loop
1911	// since most instructions do not have tied operands.
1912	TiedOperands.clear();
1913	removeClobberedSrcRegMap(MI: &*mi);
1914	mi = nmi;
1915	}
1916	}
1917
1918	return MadeChange;
1919	}
1920
1921	/// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1922	///
1923	/// The instruction is turned into a sequence of sub-register copies:
1924	///
1925	/// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1926	///
1927	/// Becomes:
1928	///
1929	/// undef %dst:ssub0 = COPY %v1
1930	/// %dst:ssub1 = COPY %v2
1931	void TwoAddressInstructionPass::
1932	eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1933	MachineInstr &MI = *MBBI;
1934	Register DstReg = MI.getOperand(i: 0).getReg();
1935
1936	SmallVector<Register, 4> OrigRegs;
1937	VNInfo *DefVN = nullptr;
1938	if (LIS) {
1939	OrigRegs.push_back(Elt: MI.getOperand(i: 0).getReg());
1940	for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2)
1941	OrigRegs.push_back(Elt: MI.getOperand(i).getReg());
1942	if (LIS->hasInterval(Reg: DstReg)) {
1943	DefVN = LIS->getInterval(Reg: DstReg)
1944	.Query(Idx: LIS->getInstructionIndex(Instr: MI))
1945	.valueOut();
1946	}
1947	}
1948
1949	LaneBitmask UndefLanes = LaneBitmask::getNone();
1950	bool DefEmitted = false;
1951	for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
1952	MachineOperand &UseMO = MI.getOperand(i);
1953	Register SrcReg = UseMO.getReg();
1954	unsigned SubIdx = MI.getOperand(i: i+1).getImm();
1955	// Nothing needs to be inserted for undef operands.
1956	if (UseMO.isUndef()) {
1957	UndefLanes |= TRI->getSubRegIndexLaneMask(SubIdx);
1958	continue;
1959	}
1960
1961	// Defer any kill flag to the last operand using SrcReg. Otherwise, we
1962	// might insert a COPY that uses SrcReg after is was killed.
1963	bool isKill = UseMO.isKill();
1964	if (isKill)
1965	for (unsigned j = i + 2; j < e; j += 2)
1966	if (MI.getOperand(i: j).getReg() == SrcReg) {
1967	MI.getOperand(i: j).setIsKill();
1968	UseMO.setIsKill(false);
1969	isKill = false;
1970	break;
1971	}
1972
1973	// Insert the sub-register copy.
1974	MachineInstr *CopyMI = BuildMI(BB&: *MI.getParent(), I&: MI, MIMD: MI.getDebugLoc(),
1975	MCID: TII->get(Opcode: TargetOpcode::COPY))
1976	.addReg(RegNo: DstReg, flags: RegState::Define, SubReg: SubIdx)
1977	.add(MO: UseMO);
1978
1979	// The first def needs an undef flag because there is no live register
1980	// before it.
1981	if (!DefEmitted) {
1982	CopyMI->getOperand(i: 0).setIsUndef(true);
1983	// Return an iterator pointing to the first inserted instr.
1984	MBBI = CopyMI;
1985	}
1986	DefEmitted = true;
1987
1988	// Update LiveVariables' kill info.
1989	if (LV && isKill && !SrcReg.isPhysical())
1990	LV->replaceKillInstruction(Reg: SrcReg, OldMI&: MI, NewMI&: *CopyMI);
1991
1992	LLVM_DEBUG(dbgs() << "Inserted: " << *CopyMI);
1993	}
1994
1995	MachineBasicBlock::iterator EndMBBI =
1996	std::next(x: MachineBasicBlock::iterator(MI));
1997
1998	if (!DefEmitted) {
1999	LLVM_DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF");
2000	MI.setDesc(TII->get(Opcode: TargetOpcode::IMPLICIT_DEF));
2001	for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j)
2002	MI.removeOperand(OpNo: j);
2003	} else {
2004	if (LIS) {
2005	// Force live interval recomputation if we moved to a partial definition
2006	// of the register. Undef flags must be propagate to uses of undefined
2007	// subregister for accurate interval computation.
2008	if (UndefLanes.any() && DefVN && MRI->shouldTrackSubRegLiveness(VReg: DstReg)) {
2009	auto &LI = LIS->getInterval(Reg: DstReg);
2010	for (MachineOperand &UseOp : MRI->use_operands(Reg: DstReg)) {
2011	unsigned SubReg = UseOp.getSubReg();
2012	if (UseOp.isUndef() || !SubReg)
2013	continue;
2014	auto *VN =
2015	LI.getVNInfoAt(Idx: LIS->getInstructionIndex(Instr: *UseOp.getParent()));
2016	if (DefVN != VN)
2017	continue;
2018	LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubIdx: SubReg);
2019	if ((UndefLanes & LaneMask).any())
2020	UseOp.setIsUndef(true);
2021	}
2022	LIS->removeInterval(Reg: DstReg);
2023	}
2024	LIS->RemoveMachineInstrFromMaps(MI);
2025	}
2026
2027	LLVM_DEBUG(dbgs() << "Eliminated: " << MI);
2028	MI.eraseFromParent();
2029	}
2030
2031	// Udpate LiveIntervals.
2032	if (LIS)
2033	LIS->repairIntervalsInRange(MBB, Begin: MBBI, End: EndMBBI, OrigRegs);
2034	}
2035