1	//===- MachineSink.cpp - Sinking for machine instructions -----------------===//
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 pass moves instructions into successor blocks when possible, so that
10	// they aren't executed on paths where their results aren't needed.
11	//
12	// This pass is not intended to be a replacement or a complete alternative
13	// for an LLVM-IR-level sinking pass. It is only designed to sink simple
14	// constructs that are not exposed before lowering and instruction selection.
15	//
16	//===----------------------------------------------------------------------===//
17
18	#include "llvm/CodeGen/MachineSink.h"
19	#include "llvm/ADT/DenseSet.h"
20	#include "llvm/ADT/DepthFirstIterator.h"
21	#include "llvm/ADT/MapVector.h"
22	#include "llvm/ADT/PointerIntPair.h"
23	#include "llvm/ADT/SetVector.h"
24	#include "llvm/ADT/SmallSet.h"
25	#include "llvm/ADT/SmallVector.h"
26	#include "llvm/ADT/Statistic.h"
27	#include "llvm/Analysis/AliasAnalysis.h"
28	#include "llvm/Analysis/CFG.h"
29	#include "llvm/Analysis/ProfileSummaryInfo.h"
30	#include "llvm/CodeGen/LiveIntervals.h"
31	#include "llvm/CodeGen/LiveVariables.h"
32	#include "llvm/CodeGen/MachineBasicBlock.h"
33	#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
34	#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
35	#include "llvm/CodeGen/MachineCycleAnalysis.h"
36	#include "llvm/CodeGen/MachineDomTreeUpdater.h"
37	#include "llvm/CodeGen/MachineDominators.h"
38	#include "llvm/CodeGen/MachineFunction.h"
39	#include "llvm/CodeGen/MachineFunctionPass.h"
40	#include "llvm/CodeGen/MachineInstr.h"
41	#include "llvm/CodeGen/MachineLoopInfo.h"
42	#include "llvm/CodeGen/MachineOperand.h"
43	#include "llvm/CodeGen/MachinePostDominators.h"
44	#include "llvm/CodeGen/MachineRegisterInfo.h"
45	#include "llvm/CodeGen/MachineSizeOpts.h"
46	#include "llvm/CodeGen/PostRAMachineSink.h"
47	#include "llvm/CodeGen/RegisterClassInfo.h"
48	#include "llvm/CodeGen/RegisterPressure.h"
49	#include "llvm/CodeGen/SlotIndexes.h"
50	#include "llvm/CodeGen/TargetInstrInfo.h"
51	#include "llvm/CodeGen/TargetPassConfig.h"
52	#include "llvm/CodeGen/TargetRegisterInfo.h"
53	#include "llvm/CodeGen/TargetSchedule.h"
54	#include "llvm/CodeGen/TargetSubtargetInfo.h"
55	#include "llvm/IR/BasicBlock.h"
56	#include "llvm/IR/DebugInfoMetadata.h"
57	#include "llvm/IR/LLVMContext.h"
58	#include "llvm/InitializePasses.h"
59	#include "llvm/Pass.h"
60	#include "llvm/Support/BranchProbability.h"
61	#include "llvm/Support/CommandLine.h"
62	#include "llvm/Support/Debug.h"
63	#include "llvm/Support/raw_ostream.h"
64	#include <cassert>
65	#include <cstdint>
66	#include <utility>
67	#include <vector>
68
69	using namespace llvm;
70
71	#define DEBUG_TYPE "machine-sink"
72
73	static cl::opt<bool>
74	SplitEdges("machine-sink-split",
75	cl::desc("Split critical edges during machine sinking"),
76	cl::init(Val: true), cl::Hidden);
77
78	static cl::opt<bool> UseBlockFreqInfo(
79	"machine-sink-bfi",
80	cl::desc("Use block frequency info to find successors to sink"),
81	cl::init(Val: true), cl::Hidden);
82
83	static cl::opt<unsigned> SplitEdgeProbabilityThreshold(
84	"machine-sink-split-probability-threshold",
85	cl::desc(
86	"Percentage threshold for splitting single-instruction critical edge. "
87	"If the branch threshold is higher than this threshold, we allow "
88	"speculative execution of up to 1 instruction to avoid branching to "
89	"splitted critical edge"),
90	cl::init(Val: 40), cl::Hidden);
91
92	static cl::opt<unsigned> SinkLoadInstsPerBlockThreshold(
93	"machine-sink-load-instrs-threshold",
94	cl::desc("Do not try to find alias store for a load if there is a in-path "
95	"block whose instruction number is higher than this threshold."),
96	cl::init(Val: 2000), cl::Hidden);
97
98	static cl::opt<unsigned> SinkLoadBlocksThreshold(
99	"machine-sink-load-blocks-threshold",
100	cl::desc("Do not try to find alias store for a load if the block number in "
101	"the straight line is higher than this threshold."),
102	cl::init(Val: 20), cl::Hidden);
103
104	static cl::opt<bool>
105	SinkInstsIntoCycle("sink-insts-to-avoid-spills",
106	cl::desc("Sink instructions into cycles to avoid "
107	"register spills"),
108	cl::init(Val: false), cl::Hidden);
109
110	static cl::opt<unsigned> SinkIntoCycleLimit(
111	"machine-sink-cycle-limit",
112	cl::desc(
113	"The maximum number of instructions considered for cycle sinking."),
114	cl::init(Val: 50), cl::Hidden);
115
116	STATISTIC(NumSunk, "Number of machine instructions sunk");
117	STATISTIC(NumCycleSunk, "Number of machine instructions sunk into a cycle");
118	STATISTIC(NumSplit, "Number of critical edges split");
119	STATISTIC(NumCoalesces, "Number of copies coalesced");
120	STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
121
122	using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
123
124	namespace {
125
126	class MachineSinking {
127	const TargetSubtargetInfo *STI = nullptr;
128	const TargetInstrInfo *TII = nullptr;
129	const TargetRegisterInfo *TRI = nullptr;
130	MachineRegisterInfo *MRI = nullptr; // Machine register information
131	MachineDominatorTree *DT = nullptr; // Machine dominator tree
132	MachinePostDominatorTree *PDT = nullptr; // Machine post dominator tree
133	MachineCycleInfo *CI = nullptr;
134	ProfileSummaryInfo *PSI = nullptr;
135	MachineBlockFrequencyInfo *MBFI = nullptr;
136	const MachineBranchProbabilityInfo *MBPI = nullptr;
137	AliasAnalysis *AA = nullptr;
138	RegisterClassInfo RegClassInfo;
139	TargetSchedModel SchedModel;
140	// Required for split critical edge
141	LiveIntervals *LIS;
142	SlotIndexes *SI;
143	LiveVariables *LV;
144	MachineLoopInfo *MLI;
145
146	// Remember which edges have been considered for breaking.
147	SmallSet<std::pair<MachineBasicBlock *, MachineBasicBlock *>, 8>
148	CEBCandidates;
149	// Memorize the register that also wanted to sink into the same block along
150	// a different critical edge.
151	// {register to sink, sink-to block} -> the first sink-from block.
152	// We're recording the first sink-from block because that (critical) edge
153	// was deferred until we see another register that's going to sink into the
154	// same block.
155	DenseMap<std::pair<Register, MachineBasicBlock *>, MachineBasicBlock *>
156	CEMergeCandidates;
157	// Remember which edges we are about to split.
158	// This is different from CEBCandidates since those edges
159	// will be split.
160	SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
161
162	DenseSet<Register> RegsToClearKillFlags;
163
164	using AllSuccsCache =
165	SmallDenseMap<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
166
167	/// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
168	/// post-dominated by another DBG_VALUE of the same variable location.
169	/// This is necessary to detect sequences such as:
170	/// %0 = someinst
171	/// DBG_VALUE %0, !123, !DIExpression()
172	/// %1 = anotherinst
173	/// DBG_VALUE %1, !123, !DIExpression()
174	/// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
175	/// would re-order assignments.
176	using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
177
178	using SinkItem = std::pair<MachineInstr *, MachineBasicBlock *>;
179
180	/// Record of DBG_VALUE uses of vregs in a block, so that we can identify
181	/// debug instructions to sink.
182	SmallDenseMap<Register, TinyPtrVector<SeenDbgUser>> SeenDbgUsers;
183
184	/// Record of debug variables that have had their locations set in the
185	/// current block.
186	DenseSet<DebugVariable> SeenDbgVars;
187
188	DenseMap<std::pair<MachineBasicBlock *, MachineBasicBlock *>, bool>
189	HasStoreCache;
190
191	DenseMap<std::pair<MachineBasicBlock *, MachineBasicBlock *>,
192	SmallVector<MachineInstr *>>
193	StoreInstrCache;
194
195	/// Cached BB's register pressure.
196	DenseMap<const MachineBasicBlock *, std::vector<unsigned>>
197	CachedRegisterPressure;
198
199	bool EnableSinkAndFold;
200
201	public:
202	MachineSinking(bool EnableSinkAndFold, MachineDominatorTree *DT,
203	MachinePostDominatorTree *PDT, LiveVariables *LV,
204	MachineLoopInfo *MLI, SlotIndexes *SI, LiveIntervals *LIS,
205	MachineCycleInfo *CI, ProfileSummaryInfo *PSI,
206	MachineBlockFrequencyInfo *MBFI,
207	const MachineBranchProbabilityInfo *MBPI, AliasAnalysis *AA)
208	: DT(DT), PDT(PDT), CI(CI), PSI(PSI), MBFI(MBFI), MBPI(MBPI), AA(AA),
209	LIS(LIS), SI(SI), LV(LV), MLI(MLI),
210	EnableSinkAndFold(EnableSinkAndFold) {}
211
212	bool run(MachineFunction &MF);
213
214	void releaseMemory() {
215	CEBCandidates.clear();
216	CEMergeCandidates.clear();
217	}
218
219	private:
220	bool ProcessBlock(MachineBasicBlock &MBB);
221	void ProcessDbgInst(MachineInstr &MI);
222	bool isLegalToBreakCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
223	MachineBasicBlock *To, bool BreakPHIEdge);
224	bool isWorthBreakingCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
225	MachineBasicBlock *To,
226	MachineBasicBlock *&DeferredFromBlock);
227
228	bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,
229	MachineInstr &MI);
230
231	/// Postpone the splitting of the given critical
232	/// edge (\p From, \p To).
233	///
234	/// We do not split the edges on the fly. Indeed, this invalidates
235	/// the dominance information and thus triggers a lot of updates
236	/// of that information underneath.
237	/// Instead, we postpone all the splits after each iteration of
238	/// the main loop. That way, the information is at least valid
239	/// for the lifetime of an iteration.
240	///
241	/// \return True if the edge is marked as toSplit, false otherwise.
242	/// False can be returned if, for instance, this is not profitable.
243	bool PostponeSplitCriticalEdge(MachineInstr &MI, MachineBasicBlock *From,
244	MachineBasicBlock *To, bool BreakPHIEdge);
245	bool SinkInstruction(MachineInstr &MI, bool &SawStore,
246	AllSuccsCache &AllSuccessors);
247
248	/// If we sink a COPY inst, some debug users of it's destination may no
249	/// longer be dominated by the COPY, and will eventually be dropped.
250	/// This is easily rectified by forwarding the non-dominated debug uses
251	/// to the copy source.
252	void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
253	MachineBasicBlock *TargetBlock);
254	bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
255	MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
256	bool &LocalUse) const;
257	MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
258	bool &BreakPHIEdge,
259	AllSuccsCache &AllSuccessors);
260
261	void FindCycleSinkCandidates(MachineCycle *Cycle, MachineBasicBlock *BB,
262	SmallVectorImpl<MachineInstr *> &Candidates);
263
264	bool
265	aggressivelySinkIntoCycle(MachineCycle *Cycle, MachineInstr &I,
266	DenseMap<SinkItem, MachineInstr *> &SunkInstrs);
267
268	bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
269	MachineBasicBlock *MBB,
270	MachineBasicBlock *SuccToSinkTo,
271	AllSuccsCache &AllSuccessors);
272
273	bool PerformTrivialForwardCoalescing(MachineInstr &MI,
274	MachineBasicBlock *MBB);
275
276	bool PerformSinkAndFold(MachineInstr &MI, MachineBasicBlock *MBB);
277
278	SmallVector<MachineBasicBlock *, 4> &
279	GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
280	AllSuccsCache &AllSuccessors) const;
281
282	std::vector<unsigned> &getBBRegisterPressure(const MachineBasicBlock &MBB,
283	bool UseCache = true);
284
285	bool registerPressureSetExceedsLimit(unsigned NRegs,
286	const TargetRegisterClass *RC,
287	const MachineBasicBlock &MBB);
288
289	bool registerPressureExceedsLimit(const MachineBasicBlock &MBB);
290	};
291
292	class MachineSinkingLegacy : public MachineFunctionPass {
293	public:
294	static char ID;
295
296	MachineSinkingLegacy() : MachineFunctionPass(ID) {
297	initializeMachineSinkingLegacyPass(*PassRegistry::getPassRegistry());
298	}
299
300	bool runOnMachineFunction(MachineFunction &MF) override;
301
302	void getAnalysisUsage(AnalysisUsage &AU) const override {
303	MachineFunctionPass::getAnalysisUsage(AU);
304	AU.addRequired<AAResultsWrapperPass>();
305	AU.addRequired<MachineDominatorTreeWrapperPass>();
306	AU.addRequired<MachinePostDominatorTreeWrapperPass>();
307	AU.addRequired<MachineCycleInfoWrapperPass>();
308	AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
309	AU.addPreserved<MachineCycleInfoWrapperPass>();
310	AU.addPreserved<MachineLoopInfoWrapperPass>();
311	AU.addRequired<ProfileSummaryInfoWrapperPass>();
312	if (UseBlockFreqInfo)
313	AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
314	AU.addRequired<TargetPassConfig>();
315	}
316	};
317
318	} // end anonymous namespace
319
320	char MachineSinkingLegacy::ID = 0;
321
322	char &llvm::MachineSinkingLegacyID = MachineSinkingLegacy::ID;
323
324	INITIALIZE_PASS_BEGIN(MachineSinkingLegacy, DEBUG_TYPE, "Machine code sinking",
325	false, false)
326	INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
327	INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
328	INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
329	INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass)
330	INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
331	INITIALIZE_PASS_END(MachineSinkingLegacy, DEBUG_TYPE, "Machine code sinking",
332	false, false)
333
334	/// Return true if a target defined block prologue instruction interferes
335	/// with a sink candidate.
336	static bool blockPrologueInterferes(const MachineBasicBlock *BB,
337	MachineBasicBlock::const_iterator End,
338	const MachineInstr &MI,
339	const TargetRegisterInfo *TRI,
340	const TargetInstrInfo *TII,
341	const MachineRegisterInfo *MRI) {
342	for (MachineBasicBlock::const_iterator PI = BB->getFirstNonPHI(); PI != End;
343	++PI) {
344	// Only check target defined prologue instructions
345	if (!TII->isBasicBlockPrologue(MI: *PI))
346	continue;
347	for (auto &MO : MI.operands()) {
348	if (!MO.isReg())
349	continue;
350	Register Reg = MO.getReg();
351	if (!Reg)
352	continue;
353	if (MO.isUse()) {
354	if (Reg.isPhysical() &&
355	(TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(PhysReg: Reg))))
356	continue;
357	if (PI->modifiesRegister(Reg, TRI))
358	return true;
359	} else {
360	if (PI->readsRegister(Reg, TRI))
361	return true;
362	// Check for interference with non-dead defs
363	auto *DefOp = PI->findRegisterDefOperand(Reg, TRI, isDead: false, Overlap: true);
364	if (DefOp && !DefOp->isDead())
365	return true;
366	}
367	}
368	}
369
370	return false;
371	}
372
373	bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
374	MachineBasicBlock *MBB) {
375	if (!MI.isCopy())
376	return false;
377
378	Register SrcReg = MI.getOperand(i: 1).getReg();
379	Register DstReg = MI.getOperand(i: 0).getReg();
380	if (!SrcReg.isVirtual() || !DstReg.isVirtual() ||
381	!MRI->hasOneNonDBGUse(RegNo: SrcReg))
382	return false;
383
384	const TargetRegisterClass *SRC = MRI->getRegClass(Reg: SrcReg);
385	const TargetRegisterClass *DRC = MRI->getRegClass(Reg: DstReg);
386	if (SRC != DRC)
387	return false;
388
389	MachineInstr *DefMI = MRI->getVRegDef(Reg: SrcReg);
390	if (DefMI->isCopyLike())
391	return false;
392	LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
393	LLVM_DEBUG(dbgs() << "*** to: " << MI);
394	MRI->replaceRegWith(FromReg: DstReg, ToReg: SrcReg);
395	MI.eraseFromParent();
396
397	// Conservatively, clear any kill flags, since it's possible that they are no
398	// longer correct.
399	MRI->clearKillFlags(Reg: SrcReg);
400
401	++NumCoalesces;
402	return true;
403	}
404
405	bool MachineSinking::PerformSinkAndFold(MachineInstr &MI,
406	MachineBasicBlock *MBB) {
407	if (MI.isCopy() || MI.mayLoadOrStore() ||
408	MI.getOpcode() == TargetOpcode::REG_SEQUENCE)
409	return false;
410
411	// Don't sink instructions that the target prefers not to sink.
412	if (!TII->shouldSink(MI))
413	return false;
414
415	// Check if it's safe to move the instruction.
416	bool SawStore = true;
417	if (!MI.isSafeToMove(SawStore))
418	return false;
419
420	// Convergent operations may not be made control-dependent on additional
421	// values.
422	if (MI.isConvergent())
423	return false;
424
425	// Don't sink defs/uses of hard registers or if the instruction defines more
426	// than one register.
427	// Don't sink more than two register uses - it'll cover most of the cases and
428	// greatly simplifies the register pressure checks.
429	Register DefReg;
430	Register UsedRegA, UsedRegB;
431	for (const MachineOperand &MO : MI.operands()) {
432	if (MO.isImm() || MO.isRegMask() || MO.isRegLiveOut() || MO.isMetadata() ||
433	MO.isMCSymbol() || MO.isDbgInstrRef() || MO.isCFIIndex() ||
434	MO.isIntrinsicID() || MO.isPredicate() || MO.isShuffleMask())
435	continue;
436	if (!MO.isReg())
437	return false;
438
439	Register Reg = MO.getReg();
440	if (Reg == 0)
441	continue;
442
443	if (Reg.isVirtual()) {
444	if (MO.isDef()) {
445	if (DefReg)
446	return false;
447	DefReg = Reg;
448	continue;
449	}
450
451	if (UsedRegA == 0)
452	UsedRegA = Reg;
453	else if (UsedRegB == 0)
454	UsedRegB = Reg;
455	else
456	return false;
457	continue;
458	}
459
460	if (Reg.isPhysical() && MO.isUse() &&
461	(MRI->isConstantPhysReg(PhysReg: Reg) || TII->isIgnorableUse(MO)))
462	continue;
463
464	return false;
465	}
466
467	// Scan uses of the destination register. Every use, except the last, must be
468	// a copy, with a chain of copies terminating with either a copy into a hard
469	// register, or a load/store instruction where the use is part of the
470	// address (*not* the stored value).
471	using SinkInfo = std::pair<MachineInstr *, ExtAddrMode>;
472	SmallVector<SinkInfo> SinkInto;
473	SmallVector<Register> Worklist;
474
475	const TargetRegisterClass *RC = MRI->getRegClass(Reg: DefReg);
476	const TargetRegisterClass *RCA =
477	UsedRegA == 0 ? nullptr : MRI->getRegClass(Reg: UsedRegA);
478	const TargetRegisterClass *RCB =
479	UsedRegB == 0 ? nullptr : MRI->getRegClass(Reg: UsedRegB);
480
481	Worklist.push_back(Elt: DefReg);
482	while (!Worklist.empty()) {
483	Register Reg = Worklist.pop_back_val();
484
485	for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
486	ExtAddrMode MaybeAM;
487	MachineInstr &UseInst = *MO.getParent();
488	if (UseInst.isCopy()) {
489	Register DstReg;
490	if (const MachineOperand &O = UseInst.getOperand(i: 0); O.isReg())
491	DstReg = O.getReg();
492	if (DstReg == 0)
493	return false;
494	if (DstReg.isVirtual()) {
495	Worklist.push_back(Elt: DstReg);
496	continue;
497	}
498	// If we are going to replace a copy, the original instruction must be
499	// as cheap as a copy.
500	if (!TII->isAsCheapAsAMove(MI))
501	return false;
502	// The hard register must be in the register class of the original
503	// instruction's destination register.
504	if (!RC->contains(Reg: DstReg))
505	return false;
506	} else if (UseInst.mayLoadOrStore()) {
507	ExtAddrMode AM;
508	if (!TII->canFoldIntoAddrMode(MemI: UseInst, Reg, AddrI: MI, AM))
509	return false;
510	MaybeAM = AM;
511	} else {
512	return false;
513	}
514
515	if (UseInst.getParent() != MI.getParent()) {
516	// If the register class of the register we are replacing is a superset
517	// of any of the register classes of the operands of the materialized
518	// instruction don't consider that live range extended.
519	const TargetRegisterClass *RCS = MRI->getRegClass(Reg);
520	if (RCA && RCA->hasSuperClassEq(RC: RCS))
521	RCA = nullptr;
522	else if (RCB && RCB->hasSuperClassEq(RC: RCS))
523	RCB = nullptr;
524	if (RCA || RCB) {
525	if (RCA == nullptr) {
526	RCA = RCB;
527	RCB = nullptr;
528	}
529
530	unsigned NRegs = !!RCA + !!RCB;
531	if (RCA == RCB)
532	RCB = nullptr;
533
534	// Check we don't exceed register pressure at the destination.
535	const MachineBasicBlock &MBB = *UseInst.getParent();
536	if (RCB == nullptr) {
537	if (registerPressureSetExceedsLimit(NRegs, RC: RCA, MBB))
538	return false;
539	} else if (registerPressureSetExceedsLimit(NRegs: 1, RC: RCA, MBB) ||
540	registerPressureSetExceedsLimit(NRegs: 1, RC: RCB, MBB)) {
541	return false;
542	}
543	}
544	}
545
546	SinkInto.emplace_back(Args: &UseInst, Args&: MaybeAM);
547	}
548	}
549
550	if (SinkInto.empty())
551	return false;
552
553	// Now we know we can fold the instruction in all its users.
554	for (auto &[SinkDst, MaybeAM] : SinkInto) {
555	MachineInstr *New = nullptr;
556	LLVM_DEBUG(dbgs() << "Sinking copy of"; MI.dump(); dbgs() << "into";
557	SinkDst->dump());
558	if (SinkDst->isCopy()) {
559	// TODO: After performing the sink-and-fold, the original instruction is
560	// deleted. Its value is still available (in a hard register), so if there
561	// are debug instructions which refer to the (now deleted) virtual
562	// register they could be updated to refer to the hard register, in
563	// principle. However, it's not clear how to do that, moreover in some
564	// cases the debug instructions may need to be replicated proportionally
565	// to the number of the COPY instructions replaced and in some extreme
566	// cases we can end up with quadratic increase in the number of debug
567	// instructions.
568
569	// Sink a copy of the instruction, replacing a COPY instruction.
570	MachineBasicBlock::iterator InsertPt = SinkDst->getIterator();
571	Register DstReg = SinkDst->getOperand(i: 0).getReg();
572	TII->reMaterialize(MBB&: *SinkDst->getParent(), MI: InsertPt, DestReg: DstReg, SubIdx: 0, Orig: MI, TRI: *TRI);
573	New = &*std::prev(x: InsertPt);
574	if (!New->getDebugLoc())
575	New->setDebugLoc(SinkDst->getDebugLoc());
576
577	// The operand registers of the "sunk" instruction have their live range
578	// extended and their kill flags may no longer be correct. Conservatively
579	// clear the kill flags.
580	if (UsedRegA)
581	MRI->clearKillFlags(Reg: UsedRegA);
582	if (UsedRegB)
583	MRI->clearKillFlags(Reg: UsedRegB);
584	} else {
585	// Fold instruction into the addressing mode of a memory instruction.
586	New = TII->emitLdStWithAddr(MemI&: *SinkDst, AM: MaybeAM);
587
588	// The registers of the addressing mode may have their live range extended
589	// and their kill flags may no longer be correct. Conservatively clear the
590	// kill flags.
591	if (Register R = MaybeAM.BaseReg; R.isValid() && R.isVirtual())
592	MRI->clearKillFlags(Reg: R);
593	if (Register R = MaybeAM.ScaledReg; R.isValid() && R.isVirtual())
594	MRI->clearKillFlags(Reg: R);
595	}
596	LLVM_DEBUG(dbgs() << "yielding"; New->dump());
597	// Clear the StoreInstrCache, since we may invalidate it by erasing.
598	if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())
599	StoreInstrCache.clear();
600	SinkDst->eraseFromParent();
601	}
602
603	// Collect operands that need to be cleaned up because the registers no longer
604	// exist (in COPYs and debug instructions). We cannot delete instructions or
605	// clear operands while traversing register uses.
606	SmallVector<MachineOperand *> Cleanup;
607	Worklist.push_back(Elt: DefReg);
608	while (!Worklist.empty()) {
609	Register Reg = Worklist.pop_back_val();
610	for (MachineOperand &MO : MRI->use_operands(Reg)) {
611	MachineInstr *U = MO.getParent();
612	assert((U->isCopy() || U->isDebugInstr()) &&
613	"Only debug uses and copies must remain");
614	if (U->isCopy())
615	Worklist.push_back(Elt: U->getOperand(i: 0).getReg());
616	Cleanup.push_back(Elt: &MO);
617	}
618	}
619
620	// Delete the dead COPYs and clear operands in debug instructions
621	for (MachineOperand *MO : Cleanup) {
622	MachineInstr *I = MO->getParent();
623	if (I->isCopy()) {
624	I->eraseFromParent();
625	} else {
626	MO->setReg(0);
627	MO->setSubReg(0);
628	}
629	}
630
631	MI.eraseFromParent();
632	return true;
633	}
634
635	/// AllUsesDominatedByBlock - Return true if all uses of the specified register
636	/// occur in blocks dominated by the specified block. If any use is in the
637	/// definition block, then return false since it is never legal to move def
638	/// after uses.
639	bool MachineSinking::AllUsesDominatedByBlock(Register Reg,
640	MachineBasicBlock *MBB,
641	MachineBasicBlock *DefMBB,
642	bool &BreakPHIEdge,
643	bool &LocalUse) const {
644	assert(Reg.isVirtual() && "Only makes sense for vregs");
645
646	// Ignore debug uses because debug info doesn't affect the code.
647	if (MRI->use_nodbg_empty(RegNo: Reg))
648	return true;
649
650	// BreakPHIEdge is true if all the uses are in the successor MBB being sunken
651	// into and they are all PHI nodes. In this case, machine-sink must break
652	// the critical edge first. e.g.
653	//
654	// %bb.1:
655	// Predecessors according to CFG: %bb.0
656	// ...
657	// %def = DEC64_32r %x, implicit-def dead %eflags
658	// ...
659	// JE_4 <%bb.37>, implicit %eflags
660	// Successors according to CFG: %bb.37 %bb.2
661	//
662	// %bb.2:
663	// %p = PHI %y, %bb.0, %def, %bb.1
664	if (all_of(Range: MRI->use_nodbg_operands(Reg), P: [&](MachineOperand &MO) {
665	MachineInstr *UseInst = MO.getParent();
666	unsigned OpNo = MO.getOperandNo();
667	MachineBasicBlock *UseBlock = UseInst->getParent();
668	return UseBlock == MBB && UseInst->isPHI() &&
669	UseInst->getOperand(i: OpNo + 1).getMBB() == DefMBB;
670	})) {
671	BreakPHIEdge = true;
672	return true;
673	}
674
675	for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
676	// Determine the block of the use.
677	MachineInstr *UseInst = MO.getParent();
678	unsigned OpNo = &MO - &UseInst->getOperand(i: 0);
679	MachineBasicBlock *UseBlock = UseInst->getParent();
680	if (UseInst->isPHI()) {
681	// PHI nodes use the operand in the predecessor block, not the block with
682	// the PHI.
683	UseBlock = UseInst->getOperand(i: OpNo + 1).getMBB();
684	} else if (UseBlock == DefMBB) {
685	LocalUse = true;
686	return false;
687	}
688
689	// Check that it dominates.
690	if (!DT->dominates(A: MBB, B: UseBlock))
691	return false;
692	}
693
694	return true;
695	}
696
697	/// Return true if this machine instruction loads from global offset table or
698	/// constant pool.
699	static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
700	assert(MI.mayLoad() && "Expected MI that loads!");
701
702	// If we lost memory operands, conservatively assume that the instruction
703	// reads from everything..
704	if (MI.memoperands_empty())
705	return true;
706
707	for (MachineMemOperand *MemOp : MI.memoperands())
708	if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
709	if (PSV->isGOT() || PSV->isConstantPool())
710	return true;
711
712	return false;
713	}
714
715	void MachineSinking::FindCycleSinkCandidates(
716	MachineCycle *Cycle, MachineBasicBlock *BB,
717	SmallVectorImpl<MachineInstr *> &Candidates) {
718	for (auto &MI : *BB) {
719	LLVM_DEBUG(dbgs() << "CycleSink: Analysing candidate: " << MI);
720	if (MI.isMetaInstruction()) {
721	LLVM_DEBUG(dbgs() << "CycleSink: not sinking meta instruction\n");
722	continue;
723	}
724	if (!TII->shouldSink(MI)) {
725	LLVM_DEBUG(dbgs() << "CycleSink: Instruction not a candidate for this "
726	"target\n");
727	continue;
728	}
729	if (!isCycleInvariant(Cycle, I&: MI)) {
730	LLVM_DEBUG(dbgs() << "CycleSink: Instruction is not cycle invariant\n");
731	continue;
732	}
733	bool DontMoveAcrossStore = true;
734	if (!MI.isSafeToMove(SawStore&: DontMoveAcrossStore)) {
735	LLVM_DEBUG(dbgs() << "CycleSink: Instruction not safe to move.\n");
736	continue;
737	}
738	if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
739	LLVM_DEBUG(dbgs() << "CycleSink: Dont sink GOT or constant pool loads\n");
740	continue;
741	}
742	if (MI.isConvergent())
743	continue;
744
745	const MachineOperand &MO = MI.getOperand(i: 0);
746	if (!MO.isReg() || !MO.getReg() || !MO.isDef())
747	continue;
748	if (!MRI->hasOneDef(RegNo: MO.getReg()))
749	continue;
750
751	LLVM_DEBUG(dbgs() << "CycleSink: Instruction added as candidate.\n");
752	Candidates.push_back(Elt: &MI);
753	}
754	}
755
756	PreservedAnalyses
757	MachineSinkingPass::run(MachineFunction &MF,
758	MachineFunctionAnalysisManager &MFAM) {
759	auto *DT = &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
760	auto *PDT = &MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
761	auto *CI = &MFAM.getResult<MachineCycleAnalysis>(IR&: MF);
762	auto *PSI = MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
763	.getCachedResult<ProfileSummaryAnalysis>(
764	IR&: *MF.getFunction().getParent());
765	auto *MBFI = UseBlockFreqInfo
766	? &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF)
767	: nullptr;
768	auto *MBPI = &MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF);
769	auto *AA = &MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
770	.getManager()
771	.getResult<AAManager>(IR&: MF.getFunction());
772	auto *LIS = MFAM.getCachedResult<LiveIntervalsAnalysis>(IR&: MF);
773	auto *SI = MFAM.getCachedResult<SlotIndexesAnalysis>(IR&: MF);
774	auto *LV = MFAM.getCachedResult<LiveVariablesAnalysis>(IR&: MF);
775	auto *MLI = MFAM.getCachedResult<MachineLoopAnalysis>(IR&: MF);
776	MachineSinking Impl(EnableSinkAndFold, DT, PDT, LV, MLI, SI, LIS, CI, PSI,
777	MBFI, MBPI, AA);
778	bool Changed = Impl.run(MF);
779	if (!Changed)
780	return PreservedAnalyses::all();
781	auto PA = getMachineFunctionPassPreservedAnalyses();
782	PA.preserve<MachineCycleAnalysis>();
783	PA.preserve<MachineLoopAnalysis>();
784	return PA;
785	}
786
787	void MachineSinkingPass::printPipeline(
788	raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
789	OS << MapClassName2PassName(name()); // ideally machine-sink
790	if (EnableSinkAndFold)
791	OS << "<enable-sink-fold>";
792	}
793
794	bool MachineSinkingLegacy::runOnMachineFunction(MachineFunction &MF) {
795	if (skipFunction(F: MF.getFunction()))
796	return false;
797
798	TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
799	bool EnableSinkAndFold = PassConfig->getEnableSinkAndFold();
800
801	auto *DT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
802	auto *PDT =
803	&getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
804	auto *CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
805	auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
806	auto *MBFI =
807	UseBlockFreqInfo
808	? &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI()
809	: nullptr;
810	auto *MBPI =
811	&getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
812	auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
813	// Get analyses for split critical edge.
814	auto *LISWrapper = getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
815	auto *LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
816	auto *SIWrapper = getAnalysisIfAvailable<SlotIndexesWrapperPass>();
817	auto *SI = SIWrapper ? &SIWrapper->getSI() : nullptr;
818	auto *LVWrapper = getAnalysisIfAvailable<LiveVariablesWrapperPass>();
819	auto *LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
820	auto *MLIWrapper = getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();
821	auto *MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;
822
823	MachineSinking Impl(EnableSinkAndFold, DT, PDT, LV, MLI, SI, LIS, CI, PSI,
824	MBFI, MBPI, AA);
825	return Impl.run(MF);
826	}
827
828	bool MachineSinking::run(MachineFunction &MF) {
829	LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
830
831	STI = &MF.getSubtarget();
832	TII = STI->getInstrInfo();
833	TRI = STI->getRegisterInfo();
834	MRI = &MF.getRegInfo();
835
836	RegClassInfo.runOnMachineFunction(MF);
837
838	bool EverMadeChange = false;
839
840	while (true) {
841	bool MadeChange = false;
842
843	// Process all basic blocks.
844	CEBCandidates.clear();
845	CEMergeCandidates.clear();
846	ToSplit.clear();
847	for (auto &MBB : MF)
848	MadeChange |= ProcessBlock(MBB);
849
850	// If we have anything we marked as toSplit, split it now.
851	MachineDomTreeUpdater MDTU(DT, PDT,
852	MachineDomTreeUpdater::UpdateStrategy::Lazy);
853	for (const auto &Pair : ToSplit) {
854	auto NewSucc = Pair.first->SplitCriticalEdge(
855	Succ: Pair.second, Analyses: {.LIS: LIS, .SI: SI, .LV: LV, .MLI: MLI}, LiveInSets: nullptr, MDTU: &MDTU);
856	if (NewSucc != nullptr) {
857	LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
858	<< printMBBReference(*Pair.first) << " -- "
859	<< printMBBReference(*NewSucc) << " -- "
860	<< printMBBReference(*Pair.second) << '\n');
861	if (MBFI)
862	MBFI->onEdgeSplit(NewPredecessor: *Pair.first, NewSuccessor: *NewSucc, MBPI: *MBPI);
863
864	MadeChange = true;
865	++NumSplit;
866	CI->splitCriticalEdge(Pred: Pair.first, Succ: Pair.second, New: NewSucc);
867	} else
868	LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
869	}
870	// If this iteration over the code changed anything, keep iterating.
871	if (!MadeChange)
872	break;
873	EverMadeChange = true;
874	}
875
876	if (SinkInstsIntoCycle) {
877	SmallVector<MachineCycle *, 8> Cycles(CI->toplevel_cycles());
878	SchedModel.init(TSInfo: STI);
879	bool HasHighPressure;
880
881	DenseMap<SinkItem, MachineInstr *> SunkInstrs;
882
883	enum CycleSinkStage { COPY, LOW_LATENCY, AGGRESSIVE, END };
884	for (unsigned Stage = CycleSinkStage::COPY; Stage != CycleSinkStage::END;
885	++Stage, SunkInstrs.clear()) {
886	HasHighPressure = false;
887
888	for (auto *Cycle : Cycles) {
889	MachineBasicBlock *Preheader = Cycle->getCyclePreheader();
890	if (!Preheader) {
891	LLVM_DEBUG(dbgs() << "CycleSink: Can't find preheader\n");
892	continue;
893	}
894	SmallVector<MachineInstr *, 8> Candidates;
895	FindCycleSinkCandidates(Cycle, BB: Preheader, Candidates);
896
897	unsigned i = 0;
898
899	// Walk the candidates in reverse order so that we start with the use
900	// of a def-use chain, if there is any.
901	// TODO: Sort the candidates using a cost-model.
902	for (MachineInstr *I : llvm::reverse(C&: Candidates)) {
903	// CycleSinkStage::COPY: Sink a limited number of copies
904	if (Stage == CycleSinkStage::COPY) {
905	if (i++ == SinkIntoCycleLimit) {
906	LLVM_DEBUG(dbgs()
907	<< "CycleSink: Limit reached of instructions to "
908	"be analyzed.");
909	break;
910	}
911
912	if (!I->isCopy())
913	continue;
914	}
915
916	// CycleSinkStage::LOW_LATENCY: sink unlimited number of instructions
917	// which the target specifies as low-latency
918	if (Stage == CycleSinkStage::LOW_LATENCY &&
919	!TII->hasLowDefLatency(SchedModel, DefMI: *I, DefIdx: 0))
920	continue;
921
922	if (!aggressivelySinkIntoCycle(Cycle, I&: *I, SunkInstrs))
923	continue;
924	EverMadeChange = true;
925	++NumCycleSunk;
926	}
927
928	// Recalculate the pressure after sinking
929	if (!HasHighPressure)
930	HasHighPressure = registerPressureExceedsLimit(MBB: *Preheader);
931	}
932	if (!HasHighPressure)
933	break;
934	}
935	}
936
937	HasStoreCache.clear();
938	StoreInstrCache.clear();
939
940	// Now clear any kill flags for recorded registers.
941	for (auto I : RegsToClearKillFlags)
942	MRI->clearKillFlags(Reg: I);
943	RegsToClearKillFlags.clear();
944
945	releaseMemory();
946	return EverMadeChange;
947	}
948
949	bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
950	if ((!EnableSinkAndFold && MBB.succ_size() <= 1) || MBB.empty())
951	return false;
952
953	// Don't bother sinking code out of unreachable blocks. In addition to being
954	// unprofitable, it can also lead to infinite looping, because in an
955	// unreachable cycle there may be nowhere to stop.
956	if (!DT->isReachableFromEntry(A: &MBB))
957	return false;
958
959	bool MadeChange = false;
960
961	// Cache all successors, sorted by frequency info and cycle depth.
962	AllSuccsCache AllSuccessors;
963
964	// Walk the basic block bottom-up. Remember if we saw a store.
965	MachineBasicBlock::iterator I = MBB.end();
966	--I;
967	bool ProcessedBegin, SawStore = false;
968	do {
969	MachineInstr &MI = *I; // The instruction to sink.
970
971	// Predecrement I (if it's not begin) so that it isn't invalidated by
972	// sinking.
973	ProcessedBegin = I == MBB.begin();
974	if (!ProcessedBegin)
975	--I;
976
977	if (MI.isDebugOrPseudoInstr() || MI.isFakeUse()) {
978	if (MI.isDebugValue())
979	ProcessDbgInst(MI);
980	continue;
981	}
982
983	if (EnableSinkAndFold && PerformSinkAndFold(MI, MBB: &MBB)) {
984	MadeChange = true;
985	continue;
986	}
987
988	// Can't sink anything out of a block that has less than two successors.
989	if (MBB.succ_size() <= 1)
990	continue;
991
992	if (PerformTrivialForwardCoalescing(MI, MBB: &MBB)) {
993	MadeChange = true;
994	continue;
995	}
996
997	if (SinkInstruction(MI, SawStore, AllSuccessors)) {
998	++NumSunk;
999	MadeChange = true;
1000	}
1001
1002	// If we just processed the first instruction in the block, we're done.
1003	} while (!ProcessedBegin);
1004
1005	SeenDbgUsers.clear();
1006	SeenDbgVars.clear();
1007	// recalculate the bb register pressure after sinking one BB.
1008	CachedRegisterPressure.clear();
1009	return MadeChange;
1010	}
1011
1012	void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
1013	// When we see DBG_VALUEs for registers, record any vreg it reads, so that
1014	// we know what to sink if the vreg def sinks.
1015	assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
1016
1017	DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
1018	MI.getDebugLoc()->getInlinedAt());
1019	bool SeenBefore = SeenDbgVars.contains(V: Var);
1020
1021	for (MachineOperand &MO : MI.debug_operands()) {
1022	if (MO.isReg() && MO.getReg().isVirtual())
1023	SeenDbgUsers[MO.getReg()].push_back(NewVal: SeenDbgUser(&MI, SeenBefore));
1024	}
1025
1026	// Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
1027	SeenDbgVars.insert(V: Var);
1028	}
1029
1030	bool MachineSinking::isWorthBreakingCriticalEdge(
1031	MachineInstr &MI, MachineBasicBlock *From, MachineBasicBlock *To,
1032	MachineBasicBlock *&DeferredFromBlock) {
1033	// FIXME: Need much better heuristics.
1034
1035	// If the pass has already considered breaking this edge (during this pass
1036	// through the function), then let's go ahead and break it. This means
1037	// sinking multiple "cheap" instructions into the same block.
1038	if (!CEBCandidates.insert(V: std::make_pair(x&: From, y&: To)).second)
1039	return true;
1040
1041	if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
1042	return true;
1043
1044	// Check and record the register and the destination block we want to sink
1045	// into. Note that we want to do the following before the next check on branch
1046	// probability. Because we want to record the initial candidate even if it's
1047	// on hot edge, so that other candidates that might not on hot edges can be
1048	// sinked as well.
1049	for (const auto &MO : MI.all_defs()) {
1050	Register Reg = MO.getReg();
1051	if (!Reg)
1052	continue;
1053	Register SrcReg = Reg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: Reg, MRI) : Reg;
1054	auto Key = std::make_pair(x&: SrcReg, y&: To);
1055	auto Res = CEMergeCandidates.try_emplace(Key, Args&: From);
1056	// We wanted to sink the same register into the same block, consider it to
1057	// be profitable.
1058	if (!Res.second) {
1059	// Return the source block that was previously held off.
1060	DeferredFromBlock = Res.first->second;
1061	return true;
1062	}
1063	}
1064
1065	if (From->isSuccessor(MBB: To) &&
1066	MBPI->getEdgeProbability(Src: From, Dst: To) <=
1067	BranchProbability(SplitEdgeProbabilityThreshold, 100))
1068	return true;
1069
1070	// MI is cheap, we probably don't want to break the critical edge for it.
1071	// However, if this would allow some definitions of its source operands
1072	// to be sunk then it's probably worth it.
1073	for (const MachineOperand &MO : MI.all_uses()) {
1074	Register Reg = MO.getReg();
1075	if (Reg == 0)
1076	continue;
1077
1078	// We don't move live definitions of physical registers,
1079	// so sinking their uses won't enable any opportunities.
1080	if (Reg.isPhysical())
1081	continue;
1082
1083	// If this instruction is the only user of a virtual register,
1084	// check if breaking the edge will enable sinking
1085	// both this instruction and the defining instruction.
1086	if (MRI->hasOneNonDBGUse(RegNo: Reg)) {
1087	// If the definition resides in same MBB,
1088	// claim it's likely we can sink these together.
1089	// If definition resides elsewhere, we aren't
1090	// blocking it from being sunk so don't break the edge.
1091	MachineInstr *DefMI = MRI->getVRegDef(Reg);
1092	if (DefMI->getParent() == MI.getParent())
1093	return true;
1094	}
1095	}
1096
1097	// Let the target decide if it's worth breaking this
1098	// critical edge for a "cheap" instruction.
1099	return TII->shouldBreakCriticalEdgeToSink(MI);
1100	}
1101
1102	bool MachineSinking::isLegalToBreakCriticalEdge(MachineInstr &MI,
1103	MachineBasicBlock *FromBB,
1104	MachineBasicBlock *ToBB,
1105	bool BreakPHIEdge) {
1106	// Avoid breaking back edge. From == To means backedge for single BB cycle.
1107	if (!SplitEdges || FromBB == ToBB || !FromBB->isSuccessor(MBB: ToBB))
1108	return false;
1109
1110	MachineCycle *FromCycle = CI->getCycle(Block: FromBB);
1111	MachineCycle *ToCycle = CI->getCycle(Block: ToBB);
1112
1113	// Check for backedges of more "complex" cycles.
1114	if (FromCycle == ToCycle && FromCycle &&
1115	(!FromCycle->isReducible() || FromCycle->getHeader() == ToBB))
1116	return false;
1117
1118	// It's not always legal to break critical edges and sink the computation
1119	// to the edge.
1120	//
1121	// %bb.1:
1122	// v1024
1123	// Beq %bb.3
1124	// <fallthrough>
1125	// %bb.2:
1126	// ... no uses of v1024
1127	// <fallthrough>
1128	// %bb.3:
1129	// ...
1130	// = v1024
1131	//
1132	// If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
1133	//
1134	// %bb.1:
1135	// ...
1136	// Bne %bb.2
1137	// %bb.4:
1138	// v1024 =
1139	// B %bb.3
1140	// %bb.2:
1141	// ... no uses of v1024
1142	// <fallthrough>
1143	// %bb.3:
1144	// ...
1145	// = v1024
1146	//
1147	// This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
1148	// flow. We need to ensure the new basic block where the computation is
1149	// sunk to dominates all the uses.
1150	// It's only legal to break critical edge and sink the computation to the
1151	// new block if all the predecessors of "To", except for "From", are
1152	// not dominated by "From". Given SSA property, this means these
1153	// predecessors are dominated by "To".
1154	//
1155	// There is no need to do this check if all the uses are PHI nodes. PHI
1156	// sources are only defined on the specific predecessor edges.
1157	if (!BreakPHIEdge) {
1158	for (MachineBasicBlock *Pred : ToBB->predecessors())
1159	if (Pred != FromBB && !DT->dominates(A: ToBB, B: Pred))
1160	return false;
1161	}
1162
1163	return true;
1164	}
1165
1166	bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
1167	MachineBasicBlock *FromBB,
1168	MachineBasicBlock *ToBB,
1169	bool BreakPHIEdge) {
1170	bool Status = false;
1171	MachineBasicBlock *DeferredFromBB = nullptr;
1172	if (isWorthBreakingCriticalEdge(MI, From: FromBB, To: ToBB, DeferredFromBlock&: DeferredFromBB)) {
1173	// If there is a DeferredFromBB, we consider FromBB only if _both_
1174	// of them are legal to split.
1175	if ((!DeferredFromBB ||
1176	ToSplit.count(key: std::make_pair(x&: DeferredFromBB, y&: ToBB)) ||
1177	isLegalToBreakCriticalEdge(MI, FromBB: DeferredFromBB, ToBB, BreakPHIEdge)) &&
1178	isLegalToBreakCriticalEdge(MI, FromBB, ToBB, BreakPHIEdge)) {
1179	ToSplit.insert(X: std::make_pair(x&: FromBB, y&: ToBB));
1180	if (DeferredFromBB)
1181	ToSplit.insert(X: std::make_pair(x&: DeferredFromBB, y&: ToBB));
1182	Status = true;
1183	}
1184	}
1185
1186	return Status;
1187	}
1188
1189	std::vector<unsigned> &
1190	MachineSinking::getBBRegisterPressure(const MachineBasicBlock &MBB,
1191	bool UseCache) {
1192	// Currently to save compiling time, MBB's register pressure will not change
1193	// in one ProcessBlock iteration because of CachedRegisterPressure. but MBB's
1194	// register pressure is changed after sinking any instructions into it.
1195	// FIXME: need a accurate and cheap register pressure estiminate model here.
1196
1197	auto RP = CachedRegisterPressure.find(Val: &MBB);
1198	if (UseCache && RP != CachedRegisterPressure.end())
1199	return RP->second;
1200
1201	RegionPressure Pressure;
1202	RegPressureTracker RPTracker(Pressure);
1203
1204	// Initialize the register pressure tracker.
1205	RPTracker.init(mf: MBB.getParent(), rci: &RegClassInfo, lis: nullptr, mbb: &MBB, pos: MBB.end(),
1206	/*TrackLaneMasks*/ false, /*TrackUntiedDefs=*/true);
1207
1208	for (MachineBasicBlock::const_iterator MII = MBB.instr_end(),
1209	MIE = MBB.instr_begin();
1210	MII != MIE; --MII) {
1211	const MachineInstr &MI = *std::prev(x: MII);
1212	if (MI.isDebugInstr() || MI.isPseudoProbe())
1213	continue;
1214	RegisterOperands RegOpers;
1215	RegOpers.collect(MI, TRI: *TRI, MRI: *MRI, TrackLaneMasks: false, IgnoreDead: false);
1216	RPTracker.recedeSkipDebugValues();
1217	assert(&*RPTracker.getPos() == &MI && "RPTracker sync error!");
1218	RPTracker.recede(RegOpers);
1219	}
1220
1221	RPTracker.closeRegion();
1222
1223	if (RP != CachedRegisterPressure.end()) {
1224	CachedRegisterPressure[&MBB] = RPTracker.getPressure().MaxSetPressure;
1225	return CachedRegisterPressure[&MBB];
1226	}
1227
1228	auto It = CachedRegisterPressure.insert(
1229	KV: std::make_pair(x: &MBB, y&: RPTracker.getPressure().MaxSetPressure));
1230	return It.first->second;
1231	}
1232
1233	bool MachineSinking::registerPressureSetExceedsLimit(
1234	unsigned NRegs, const TargetRegisterClass *RC,
1235	const MachineBasicBlock &MBB) {
1236	unsigned Weight = NRegs * TRI->getRegClassWeight(RC).RegWeight;
1237	const int *PS = TRI->getRegClassPressureSets(RC);
1238	std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(MBB);
1239	for (; *PS != -1; PS++)
1240	if (Weight + BBRegisterPressure[*PS] >=
1241	RegClassInfo.getRegPressureSetLimit(Idx: *PS))
1242	return true;
1243	return false;
1244	}
1245
1246	// Recalculate RP and check if any pressure set exceeds the set limit.
1247	bool MachineSinking::registerPressureExceedsLimit(
1248	const MachineBasicBlock &MBB) {
1249	std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(MBB, UseCache: false);
1250
1251	for (unsigned PS = 0; PS < BBRegisterPressure.size(); ++PS) {
1252	if (BBRegisterPressure[PS] >=
1253	TRI->getRegPressureSetLimit(MF: *MBB.getParent(), Idx: PS)) {
1254	return true;
1255	}
1256	}
1257
1258	return false;
1259	}
1260
1261	/// isProfitableToSinkTo - Return true if it is profitable to sink MI.
1262	bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
1263	MachineBasicBlock *MBB,
1264	MachineBasicBlock *SuccToSinkTo,
1265	AllSuccsCache &AllSuccessors) {
1266	assert(SuccToSinkTo && "Invalid SinkTo Candidate BB");
1267
1268	if (MBB == SuccToSinkTo)
1269	return false;
1270
1271	// It is profitable if SuccToSinkTo does not post dominate current block.
1272	if (!PDT->dominates(A: SuccToSinkTo, B: MBB))
1273	return true;
1274
1275	// It is profitable to sink an instruction from a deeper cycle to a shallower
1276	// cycle, even if the latter post-dominates the former (PR21115).
1277	if (CI->getCycleDepth(Block: MBB) > CI->getCycleDepth(Block: SuccToSinkTo))
1278	return true;
1279
1280	// Check if only use in post dominated block is PHI instruction.
1281	bool NonPHIUse = false;
1282	for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
1283	MachineBasicBlock *UseBlock = UseInst.getParent();
1284	if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
1285	NonPHIUse = true;
1286	}
1287	if (!NonPHIUse)
1288	return true;
1289
1290	// If SuccToSinkTo post dominates then also it may be profitable if MI
1291	// can further profitably sinked into another block in next round.
1292	bool BreakPHIEdge = false;
1293	// FIXME - If finding successor is compile time expensive then cache results.
1294	if (MachineBasicBlock *MBB2 =
1295	FindSuccToSinkTo(MI, MBB: SuccToSinkTo, BreakPHIEdge, AllSuccessors))
1296	return isProfitableToSinkTo(Reg, MI, MBB: SuccToSinkTo, SuccToSinkTo: MBB2, AllSuccessors);
1297
1298	MachineCycle *MCycle = CI->getCycle(Block: MBB);
1299
1300	// If the instruction is not inside a cycle, it is not profitable to sink MI
1301	// to a post dominate block SuccToSinkTo.
1302	if (!MCycle)
1303	return false;
1304
1305	// If this instruction is inside a Cycle and sinking this instruction can make
1306	// more registers live range shorten, it is still prifitable.
1307	for (const MachineOperand &MO : MI.operands()) {
1308	// Ignore non-register operands.
1309	if (!MO.isReg())
1310	continue;
1311	Register Reg = MO.getReg();
1312	if (Reg == 0)
1313	continue;
1314
1315	if (Reg.isPhysical()) {
1316	// Don't handle non-constant and non-ignorable physical register uses.
1317	if (MO.isUse() && !MRI->isConstantPhysReg(PhysReg: Reg) &&
1318	!TII->isIgnorableUse(MO))
1319	return false;
1320	continue;
1321	}
1322
1323	// Users for the defs are all dominated by SuccToSinkTo.
1324	if (MO.isDef()) {
1325	// This def register's live range is shortened after sinking.
1326	bool LocalUse = false;
1327	if (!AllUsesDominatedByBlock(Reg, MBB: SuccToSinkTo, DefMBB: MBB, BreakPHIEdge,
1328	LocalUse))
1329	return false;
1330	} else {
1331	MachineInstr *DefMI = MRI->getVRegDef(Reg);
1332	if (!DefMI)
1333	continue;
1334	MachineCycle *Cycle = CI->getCycle(Block: DefMI->getParent());
1335	// DefMI is defined outside of cycle. There should be no live range
1336	// impact for this operand. Defination outside of cycle means:
1337	// 1: defination is outside of cycle.
1338	// 2: defination is in this cycle, but it is a PHI in the cycle header.
1339	if (Cycle != MCycle || (DefMI->isPHI() && Cycle && Cycle->isReducible() &&
1340	Cycle->getHeader() == DefMI->getParent()))
1341	continue;
1342	// The DefMI is defined inside the cycle.
1343	// If sinking this operand makes some register pressure set exceed limit,
1344	// it is not profitable.
1345	if (registerPressureSetExceedsLimit(NRegs: 1, RC: MRI->getRegClass(Reg),
1346	MBB: *SuccToSinkTo)) {
1347	LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
1348	return false;
1349	}
1350	}
1351	}
1352
1353	// If MI is in cycle and all its operands are alive across the whole cycle or
1354	// if no operand sinking make register pressure set exceed limit, it is
1355	// profitable to sink MI.
1356	return true;
1357	}
1358
1359	/// Get the sorted sequence of successors for this MachineBasicBlock, possibly
1360	/// computing it if it was not already cached.
1361	SmallVector<MachineBasicBlock *, 4> &
1362	MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
1363	AllSuccsCache &AllSuccessors) const {
1364	// Do we have the sorted successors in cache ?
1365	auto Succs = AllSuccessors.find(Val: MBB);
1366	if (Succs != AllSuccessors.end())
1367	return Succs->second;
1368
1369	SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->successors());
1370
1371	// Handle cases where sinking can happen but where the sink point isn't a
1372	// successor. For example:
1373	//
1374	// x = computation
1375	// if () {} else {}
1376	// use x
1377	//
1378	for (MachineDomTreeNode *DTChild : DT->getNode(BB: MBB)->children()) {
1379	// DomTree children of MBB that have MBB as immediate dominator are added.
1380	if (DTChild->getIDom()->getBlock() == MI.getParent() &&
1381	// Skip MBBs already added to the AllSuccs vector above.
1382	!MBB->isSuccessor(MBB: DTChild->getBlock()))
1383	AllSuccs.push_back(Elt: DTChild->getBlock());
1384	}
1385
1386	// Sort Successors according to their cycle depth or block frequency info.
1387	llvm::stable_sort(
1388	Range&: AllSuccs, C: [&](const MachineBasicBlock *L, const MachineBasicBlock *R) {
1389	uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(MBB: L).getFrequency() : 0;
1390	uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(MBB: R).getFrequency() : 0;
1391	if (llvm::shouldOptimizeForSize(MBB, PSI, MBFI) ||
1392	(!LHSFreq && !RHSFreq))
1393	return CI->getCycleDepth(Block: L) < CI->getCycleDepth(Block: R);
1394	return LHSFreq < RHSFreq;
1395	});
1396
1397	auto it = AllSuccessors.insert(KV: std::make_pair(x&: MBB, y&: AllSuccs));
1398
1399	return it.first->second;
1400	}
1401
1402	/// FindSuccToSinkTo - Find a successor to sink this instruction to.
1403	MachineBasicBlock *
1404	MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
1405	bool &BreakPHIEdge,
1406	AllSuccsCache &AllSuccessors) {
1407	assert(MBB && "Invalid MachineBasicBlock!");
1408
1409	// loop over all the operands of the specified instruction. If there is
1410	// anything we can't handle, bail out.
1411
1412	// SuccToSinkTo - This is the successor to sink this instruction to, once we
1413	// decide.
1414	MachineBasicBlock *SuccToSinkTo = nullptr;
1415	for (const MachineOperand &MO : MI.operands()) {
1416	if (!MO.isReg())
1417	continue; // Ignore non-register operands.
1418
1419	Register Reg = MO.getReg();
1420	if (Reg == 0)
1421	continue;
1422
1423	if (Reg.isPhysical()) {
1424	if (MO.isUse()) {
1425	// If the physreg has no defs anywhere, it's just an ambient register
1426	// and we can freely move its uses. Alternatively, if it's allocatable,
1427	// it could get allocated to something with a def during allocation.
1428	if (!MRI->isConstantPhysReg(PhysReg: Reg) && !TII->isIgnorableUse(MO))
1429	return nullptr;
1430	} else if (!MO.isDead()) {
1431	// A def that isn't dead. We can't move it.
1432	return nullptr;
1433	}
1434	} else {
1435	// Virtual register uses are always safe to sink.
1436	if (MO.isUse())
1437	continue;
1438
1439	// If it's not safe to move defs of the register class, then abort.
1440	if (!TII->isSafeToMoveRegClassDefs(RC: MRI->getRegClass(Reg)))
1441	return nullptr;
1442
1443	// Virtual register defs can only be sunk if all their uses are in blocks
1444	// dominated by one of the successors.
1445	if (SuccToSinkTo) {
1446	// If a previous operand picked a block to sink to, then this operand
1447	// must be sinkable to the same block.
1448	bool LocalUse = false;
1449	if (!AllUsesDominatedByBlock(Reg, MBB: SuccToSinkTo, DefMBB: MBB, BreakPHIEdge,
1450	LocalUse))
1451	return nullptr;
1452
1453	continue;
1454	}
1455
1456	// Otherwise, we should look at all the successors and decide which one
1457	// we should sink to. If we have reliable block frequency information
1458	// (frequency != 0) available, give successors with smaller frequencies
1459	// higher priority, otherwise prioritize smaller cycle depths.
1460	for (MachineBasicBlock *SuccBlock :
1461	GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
1462	bool LocalUse = false;
1463	if (AllUsesDominatedByBlock(Reg, MBB: SuccBlock, DefMBB: MBB, BreakPHIEdge,
1464	LocalUse)) {
1465	SuccToSinkTo = SuccBlock;
1466	break;
1467	}
1468	if (LocalUse)
1469	// Def is used locally, it's never safe to move this def.
1470	return nullptr;
1471	}
1472
1473	// If we couldn't find a block to sink to, ignore this instruction.
1474	if (!SuccToSinkTo)
1475	return nullptr;
1476	if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
1477	return nullptr;
1478	}
1479	}
1480
1481	// It is not possible to sink an instruction into its own block. This can
1482	// happen with cycles.
1483	if (MBB == SuccToSinkTo)
1484	return nullptr;
1485
1486	// It's not safe to sink instructions to EH landing pad. Control flow into
1487	// landing pad is implicitly defined.
1488	if (SuccToSinkTo && SuccToSinkTo->isEHPad())
1489	return nullptr;
1490
1491	// It ought to be okay to sink instructions into an INLINEASM_BR target, but
1492	// only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in
1493	// the source block (which this code does not yet do). So for now, forbid
1494	// doing so.
1495	if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())
1496	return nullptr;
1497
1498	if (SuccToSinkTo && !TII->isSafeToSink(MI, SuccToSinkTo, CI))
1499	return nullptr;
1500
1501	return SuccToSinkTo;
1502	}
1503
1504	/// Return true if MI is likely to be usable as a memory operation by the
1505	/// implicit null check optimization.
1506	///
1507	/// This is a "best effort" heuristic, and should not be relied upon for
1508	/// correctness. This returning true does not guarantee that the implicit null
1509	/// check optimization is legal over MI, and this returning false does not
1510	/// guarantee MI cannot possibly be used to do a null check.
1511	static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI,
1512	const TargetInstrInfo *TII,
1513	const TargetRegisterInfo *TRI) {
1514	using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
1515
1516	auto *MBB = MI.getParent();
1517	if (MBB->pred_size() != 1)
1518	return false;
1519
1520	auto *PredMBB = *MBB->pred_begin();
1521	auto *PredBB = PredMBB->getBasicBlock();
1522
1523	// Frontends that don't use implicit null checks have no reason to emit
1524	// branches with make.implicit metadata, and this function should always
1525	// return false for them.
1526	if (!PredBB ||
1527	!PredBB->getTerminator()->getMetadata(KindID: LLVMContext::MD_make_implicit))
1528	return false;
1529
1530	const MachineOperand *BaseOp;
1531	int64_t Offset;
1532	bool OffsetIsScalable;
1533	if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
1534	return false;
1535
1536	if (!BaseOp->isReg())
1537	return false;
1538
1539	if (!(MI.mayLoad() && !MI.isPredicable()))
1540	return false;
1541
1542	MachineBranchPredicate MBP;
1543	if (TII->analyzeBranchPredicate(MBB&: *PredMBB, MBP, AllowModify: false))
1544	return false;
1545
1546	return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1547	(MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1548	MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1549	MBP.LHS.getReg() == BaseOp->getReg();
1550	}
1551
1552	/// If the sunk instruction is a copy, try to forward the copy instead of
1553	/// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
1554	/// there's any subregister weirdness involved. Returns true if copy
1555	/// propagation occurred.
1556	static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI,
1557	Register Reg) {
1558	const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
1559	const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
1560
1561	// Copy DBG_VALUE operand and set the original to undef. We then check to
1562	// see whether this is something that can be copy-forwarded. If it isn't,
1563	// continue around the loop.
1564
1565	const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
1566	auto CopyOperands = TII.isCopyInstr(MI: SinkInst);
1567	if (!CopyOperands)
1568	return false;
1569	SrcMO = CopyOperands->Source;
1570	DstMO = CopyOperands->Destination;
1571
1572	// Check validity of forwarding this copy.
1573	bool PostRA = MRI.getNumVirtRegs() == 0;
1574
1575	// Trying to forward between physical and virtual registers is too hard.
1576	if (Reg.isVirtual() != SrcMO->getReg().isVirtual())
1577	return false;
1578
1579	// Only try virtual register copy-forwarding before regalloc, and physical
1580	// register copy-forwarding after regalloc.
1581	bool arePhysRegs = !Reg.isVirtual();
1582	if (arePhysRegs != PostRA)
1583	return false;
1584
1585	// Pre-regalloc, only forward if all subregisters agree (or there are no
1586	// subregs at all). More analysis might recover some forwardable copies.
1587	if (!PostRA)
1588	for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg))
1589	if (DbgMO.getSubReg() != SrcMO->getSubReg() ||
1590	DbgMO.getSubReg() != DstMO->getSubReg())
1591	return false;
1592
1593	// Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
1594	// of this copy. Only forward the copy if the DBG_VALUE operand exactly
1595	// matches the copy destination.
1596	if (PostRA && Reg != DstMO->getReg())
1597	return false;
1598
1599	for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg)) {
1600	DbgMO.setReg(SrcMO->getReg());
1601	DbgMO.setSubReg(SrcMO->getSubReg());
1602	}
1603	return true;
1604	}
1605
1606	using MIRegs = std::pair<MachineInstr *, SmallVector<Register, 2>>;
1607	/// Sink an instruction and its associated debug instructions.
1608	static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
1609	MachineBasicBlock::iterator InsertPos,
1610	ArrayRef<MIRegs> DbgValuesToSink) {
1611	// If we cannot find a location to use (merge with), then we erase the debug
1612	// location to prevent debug-info driven tools from potentially reporting
1613	// wrong location information.
1614	if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
1615	MI.setDebugLoc(DebugLoc::getMergedLocation(LocA: MI.getDebugLoc(),
1616	LocB: InsertPos->getDebugLoc()));
1617	else
1618	MI.setDebugLoc(DebugLoc());
1619
1620	// Move the instruction.
1621	MachineBasicBlock *ParentBlock = MI.getParent();
1622	SuccToSinkTo.splice(Where: InsertPos, Other: ParentBlock, From: MI,
1623	To: ++MachineBasicBlock::iterator(MI));
1624
1625	// Sink a copy of debug users to the insert position. Mark the original
1626	// DBG_VALUE location as 'undef', indicating that any earlier variable
1627	// location should be terminated as we've optimised away the value at this
1628	// point.
1629	for (const auto &DbgValueToSink : DbgValuesToSink) {
1630	MachineInstr *DbgMI = DbgValueToSink.first;
1631	MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(Orig: DbgMI);
1632	SuccToSinkTo.insert(I: InsertPos, MI: NewDbgMI);
1633
1634	bool PropagatedAllSunkOps = true;
1635	for (Register Reg : DbgValueToSink.second) {
1636	if (DbgMI->hasDebugOperandForReg(Reg)) {
1637	if (!attemptDebugCopyProp(SinkInst&: MI, DbgMI&: *DbgMI, Reg)) {
1638	PropagatedAllSunkOps = false;
1639	break;
1640	}
1641	}
1642	}
1643	if (!PropagatedAllSunkOps)
1644	DbgMI->setDebugValueUndef();
1645	}
1646	}
1647
1648	/// hasStoreBetween - check if there is store betweeen straight line blocks From
1649	/// and To.
1650	bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
1651	MachineBasicBlock *To, MachineInstr &MI) {
1652	// Make sure From and To are in straight line which means From dominates To
1653	// and To post dominates From.
1654	if (!DT->dominates(A: From, B: To) || !PDT->dominates(A: To, B: From))
1655	return true;
1656
1657	auto BlockPair = std::make_pair(x&: From, y&: To);
1658
1659	// Does these two blocks pair be queried before and have a definite cached
1660	// result?
1661	if (auto It = HasStoreCache.find(Val: BlockPair); It != HasStoreCache.end())
1662	return It->second;
1663
1664	if (auto It = StoreInstrCache.find(Val: BlockPair); It != StoreInstrCache.end())
1665	return llvm::any_of(Range&: It->second, P: [&](MachineInstr *I) {
1666	return I->mayAlias(AA, Other: MI, UseTBAA: false);
1667	});
1668
1669	bool SawStore = false;
1670	bool HasAliasedStore = false;
1671	DenseSet<MachineBasicBlock *> HandledBlocks;
1672	DenseSet<MachineBasicBlock *> HandledDomBlocks;
1673	// Go through all reachable blocks from From.
1674	for (MachineBasicBlock *BB : depth_first(G: From)) {
1675	// We insert the instruction at the start of block To, so no need to worry
1676	// about stores inside To.
1677	// Store in block From should be already considered when just enter function
1678	// SinkInstruction.
1679	if (BB == To || BB == From)
1680	continue;
1681
1682	// We already handle this BB in previous iteration.
1683	if (HandledBlocks.count(V: BB))
1684	continue;
1685
1686	HandledBlocks.insert(V: BB);
1687	// To post dominates BB, it must be a path from block From.
1688	if (PDT->dominates(A: To, B: BB)) {
1689	if (!HandledDomBlocks.count(V: BB))
1690	HandledDomBlocks.insert(V: BB);
1691
1692	// If this BB is too big or the block number in straight line between From
1693	// and To is too big, stop searching to save compiling time.
1694	if (BB->sizeWithoutDebugLargerThan(Limit: SinkLoadInstsPerBlockThreshold) ||
1695	HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
1696	for (auto *DomBB : HandledDomBlocks) {
1697	if (DomBB != BB && DT->dominates(A: DomBB, B: BB))
1698	HasStoreCache[std::make_pair(x&: DomBB, y&: To)] = true;
1699	else if (DomBB != BB && DT->dominates(A: BB, B: DomBB))
1700	HasStoreCache[std::make_pair(x&: From, y&: DomBB)] = true;
1701	}
1702	HasStoreCache[BlockPair] = true;
1703	return true;
1704	}
1705
1706	for (MachineInstr &I : *BB) {
1707	// Treat as alias conservatively for a call or an ordered memory
1708	// operation.
1709	if (I.isCall() || I.hasOrderedMemoryRef()) {
1710	for (auto *DomBB : HandledDomBlocks) {
1711	if (DomBB != BB && DT->dominates(A: DomBB, B: BB))
1712	HasStoreCache[std::make_pair(x&: DomBB, y&: To)] = true;
1713	else if (DomBB != BB && DT->dominates(A: BB, B: DomBB))
1714	HasStoreCache[std::make_pair(x&: From, y&: DomBB)] = true;
1715	}
1716	HasStoreCache[BlockPair] = true;
1717	return true;
1718	}
1719
1720	if (I.mayStore()) {
1721	SawStore = true;
1722	// We still have chance to sink MI if all stores between are not
1723	// aliased to MI.
1724	// Cache all store instructions, so that we don't need to go through
1725	// all From reachable blocks for next load instruction.
1726	if (I.mayAlias(AA, Other: MI, UseTBAA: false))
1727	HasAliasedStore = true;
1728	StoreInstrCache[BlockPair].push_back(Elt: &I);
1729	}
1730	}
1731	}
1732	}
1733	// If there is no store at all, cache the result.
1734	if (!SawStore)
1735	HasStoreCache[BlockPair] = false;
1736	return HasAliasedStore;
1737	}
1738
1739	/// Aggressively sink instructions into cycles. This will aggressively try to
1740	/// sink all instructions in the top-most preheaders in an attempt to reduce RP.
1741	/// In particular, it will sink into multiple successor blocks without limits
1742	/// based on the amount of sinking, or the type of ops being sunk (so long as
1743	/// they are safe to sink).
1744	bool MachineSinking::aggressivelySinkIntoCycle(
1745	MachineCycle *Cycle, MachineInstr &I,
1746	DenseMap<SinkItem, MachineInstr *> &SunkInstrs) {
1747	// TODO: support instructions with multiple defs
1748	if (I.getNumDefs() > 1)
1749	return false;
1750
1751	LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Finding sink block for: " << I);
1752	assert(Cycle->getCyclePreheader() && "Cycle sink needs a preheader block");
1753	SmallVector<std::pair<RegSubRegPair, MachineInstr *>> Uses;
1754
1755	MachineOperand &DefMO = I.getOperand(i: 0);
1756	for (MachineInstr &MI : MRI->use_instructions(Reg: DefMO.getReg())) {
1757	Uses.push_back(Elt: {{DefMO.getReg(), DefMO.getSubReg()}, &MI});
1758	}
1759
1760	for (std::pair<RegSubRegPair, MachineInstr *> Entry : Uses) {
1761	MachineInstr *MI = Entry.second;
1762	LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Analysing use: " << MI);
1763	if (MI->isPHI()) {
1764	LLVM_DEBUG(
1765	dbgs() << "AggressiveCycleSink: Not attempting to sink for PHI.\n");
1766	continue;
1767	}
1768	// We cannot sink before the prologue
1769	if (MI->isPosition() || TII->isBasicBlockPrologue(MI: *MI)) {
1770	LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Use is BasicBlock prologue, "
1771	"can't sink.\n");
1772	continue;
1773	}
1774	if (!Cycle->contains(Block: MI->getParent())) {
1775	LLVM_DEBUG(
1776	dbgs() << "AggressiveCycleSink: Use not in cycle, can't sink.\n");
1777	continue;
1778	}
1779
1780	MachineBasicBlock *SinkBlock = MI->getParent();
1781	MachineInstr *NewMI = nullptr;
1782	SinkItem MapEntry(&I, SinkBlock);
1783
1784	auto SI = SunkInstrs.find(Val: MapEntry);
1785
1786	// Check for the case in which we have already sunk a copy of this
1787	// instruction into the user block.
1788	if (SI != SunkInstrs.end()) {
1789	LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Already sunk to block: "
1790	<< printMBBReference(*SinkBlock) << "\n");
1791	NewMI = SI->second;
1792	}
1793
1794	// Create a copy of the instruction in the use block.
1795	if (!NewMI) {
1796	LLVM_DEBUG(dbgs() << "AggressiveCycleSink: Sinking instruction to block: "
1797	<< printMBBReference(*SinkBlock) << "\n");
1798
1799	NewMI = I.getMF()->CloneMachineInstr(Orig: &I);
1800	if (DefMO.getReg().isVirtual()) {
1801	const TargetRegisterClass *TRC = MRI->getRegClass(Reg: DefMO.getReg());
1802	Register DestReg = MRI->createVirtualRegister(RegClass: TRC);
1803	NewMI->substituteRegister(FromReg: DefMO.getReg(), ToReg: DestReg, SubIdx: DefMO.getSubReg(),
1804	RegInfo: *TRI);
1805	}
1806	SinkBlock->insert(I: SinkBlock->SkipPHIsAndLabels(I: SinkBlock->begin()),
1807	MI: NewMI);
1808	SunkInstrs.insert(KV: {MapEntry, NewMI});
1809	}
1810
1811	// Conservatively clear any kill flags on uses of sunk instruction
1812	for (MachineOperand &MO : NewMI->all_uses()) {
1813	assert(MO.isReg() && MO.isUse());
1814	RegsToClearKillFlags.insert(V: MO.getReg());
1815	}
1816
1817	// The instruction is moved from its basic block, so do not retain the
1818	// debug information.
1819	assert(!NewMI->isDebugInstr() && "Should not sink debug inst");
1820	NewMI->setDebugLoc(DebugLoc());
1821
1822	// Replace the use with the newly created virtual register.
1823	RegSubRegPair &UseReg = Entry.first;
1824	MI->substituteRegister(FromReg: UseReg.Reg, ToReg: NewMI->getOperand(i: 0).getReg(),
1825	SubIdx: UseReg.SubReg, RegInfo: *TRI);
1826	}
1827	// If we have replaced all uses, then delete the dead instruction
1828	if (I.isDead(MRI: *MRI))
1829	I.eraseFromParent();
1830	return true;
1831	}
1832
1833	/// SinkInstruction - Determine whether it is safe to sink the specified machine
1834	/// instruction out of its current block into a successor.
1835	bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
1836	AllSuccsCache &AllSuccessors) {
1837	// Don't sink instructions that the target prefers not to sink.
1838	if (!TII->shouldSink(MI))
1839	return false;
1840
1841	// Check if it's safe to move the instruction.
1842	if (!MI.isSafeToMove(SawStore))
1843	return false;
1844
1845	// Convergent operations may not be made control-dependent on additional
1846	// values.
1847	if (MI.isConvergent())
1848	return false;
1849
1850	// Don't break implicit null checks. This is a performance heuristic, and not
1851	// required for correctness.
1852	if (SinkingPreventsImplicitNullCheck(MI, TII, TRI))
1853	return false;
1854
1855	// FIXME: This should include support for sinking instructions within the
1856	// block they are currently in to shorten the live ranges. We often get
1857	// instructions sunk into the top of a large block, but it would be better to
1858	// also sink them down before their first use in the block. This xform has to
1859	// be careful not to *increase* register pressure though, e.g. sinking
1860	// "x = y + z" down if it kills y and z would increase the live ranges of y
1861	// and z and only shrink the live range of x.
1862
1863	bool BreakPHIEdge = false;
1864	MachineBasicBlock *ParentBlock = MI.getParent();
1865	MachineBasicBlock *SuccToSinkTo =
1866	FindSuccToSinkTo(MI, MBB: ParentBlock, BreakPHIEdge, AllSuccessors);
1867
1868	// If there are no outputs, it must have side-effects.
1869	if (!SuccToSinkTo)
1870	return false;
1871
1872	// If the instruction to move defines a dead physical register which is live
1873	// when leaving the basic block, don't move it because it could turn into a
1874	// "zombie" define of that preg. E.g., EFLAGS.
1875	for (const MachineOperand &MO : MI.all_defs()) {
1876	Register Reg = MO.getReg();
1877	if (Reg == 0 || !Reg.isPhysical())
1878	continue;
1879	if (SuccToSinkTo->isLiveIn(Reg))
1880	return false;
1881	}
1882
1883	LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
1884
1885	// If the block has multiple predecessors, this is a critical edge.
1886	// Decide if we can sink along it or need to break the edge.
1887	if (SuccToSinkTo->pred_size() > 1) {
1888	// We cannot sink a load across a critical edge - there may be stores in
1889	// other code paths.
1890	bool TryBreak = false;
1891	bool Store =
1892	MI.mayLoad() ? hasStoreBetween(From: ParentBlock, To: SuccToSinkTo, MI) : true;
1893	if (!MI.isSafeToMove(SawStore&: Store)) {
1894	LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
1895	TryBreak = true;
1896	}
1897
1898	// We don't want to sink across a critical edge if we don't dominate the
1899	// successor. We could be introducing calculations to new code paths.
1900	if (!TryBreak && !DT->dominates(A: ParentBlock, B: SuccToSinkTo)) {
1901	LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
1902	TryBreak = true;
1903	}
1904
1905	// Don't sink instructions into a cycle.
1906	if (!TryBreak && CI->getCycle(Block: SuccToSinkTo) &&
1907	(!CI->getCycle(Block: SuccToSinkTo)->isReducible() ||
1908	CI->getCycle(Block: SuccToSinkTo)->getHeader() == SuccToSinkTo)) {
1909	LLVM_DEBUG(dbgs() << " *** NOTE: cycle header found\n");
1910	TryBreak = true;
1911	}
1912
1913	// Otherwise we are OK with sinking along a critical edge.
1914	if (!TryBreak)
1915	LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
1916	else {
1917	// Mark this edge as to be split.
1918	// If the edge can actually be split, the next iteration of the main loop
1919	// will sink MI in the newly created block.
1920	bool Status = PostponeSplitCriticalEdge(MI, FromBB: ParentBlock, ToBB: SuccToSinkTo,
1921	BreakPHIEdge);
1922	if (!Status)
1923	LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1924	"break critical edge\n");
1925	// The instruction will not be sunk this time.
1926	return false;
1927	}
1928	}
1929
1930	if (BreakPHIEdge) {
1931	// BreakPHIEdge is true if all the uses are in the successor MBB being
1932	// sunken into and they are all PHI nodes. In this case, machine-sink must
1933	// break the critical edge first.
1934	bool Status =
1935	PostponeSplitCriticalEdge(MI, FromBB: ParentBlock, ToBB: SuccToSinkTo, BreakPHIEdge);
1936	if (!Status)
1937	LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1938	"break critical edge\n");
1939	// The instruction will not be sunk this time.
1940	return false;
1941	}
1942
1943	// Determine where to insert into. Skip phi nodes.
1944	MachineBasicBlock::iterator InsertPos =
1945	SuccToSinkTo->SkipPHIsAndLabels(I: SuccToSinkTo->begin());
1946	if (blockPrologueInterferes(BB: SuccToSinkTo, End: InsertPos, MI, TRI, TII, MRI)) {
1947	LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
1948	return false;
1949	}
1950
1951	// Collect debug users of any vreg that this inst defines.
1952	SmallVector<MIRegs, 4> DbgUsersToSink;
1953	for (auto &MO : MI.all_defs()) {
1954	if (!MO.getReg().isVirtual())
1955	continue;
1956	auto It = SeenDbgUsers.find(Val: MO.getReg());
1957	if (It == SeenDbgUsers.end())
1958	continue;
1959
1960	// Sink any users that don't pass any other DBG_VALUEs for this variable.
1961	auto &Users = It->second;
1962	for (auto &User : Users) {
1963	MachineInstr *DbgMI = User.getPointer();
1964	if (User.getInt()) {
1965	// This DBG_VALUE would re-order assignments. If we can't copy-propagate
1966	// it, it can't be recovered. Set it undef.
1967	if (!attemptDebugCopyProp(SinkInst&: MI, DbgMI&: *DbgMI, Reg: MO.getReg()))
1968	DbgMI->setDebugValueUndef();
1969	} else {
1970	DbgUsersToSink.push_back(
1971	Elt: {DbgMI, SmallVector<Register, 2>(1, MO.getReg())});
1972	}
1973	}
1974	}
1975
1976	// After sinking, some debug users may not be dominated any more. If possible,
1977	// copy-propagate their operands. As it's expensive, don't do this if there's
1978	// no debuginfo in the program.
1979	if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
1980	SalvageUnsunkDebugUsersOfCopy(MI, TargetBlock: SuccToSinkTo);
1981
1982	performSink(MI, SuccToSinkTo&: *SuccToSinkTo, InsertPos, DbgValuesToSink: DbgUsersToSink);
1983
1984	// Conservatively, clear any kill flags, since it's possible that they are no
1985	// longer correct.
1986	// Note that we have to clear the kill flags for any register this instruction
1987	// uses as we may sink over another instruction which currently kills the
1988	// used registers.
1989	for (MachineOperand &MO : MI.all_uses())
1990	RegsToClearKillFlags.insert(V: MO.getReg()); // Remember to clear kill flags.
1991
1992	return true;
1993	}
1994
1995	void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1996	MachineInstr &MI, MachineBasicBlock *TargetBlock) {
1997	assert(MI.isCopy());
1998	assert(MI.getOperand(1).isReg());
1999
2000	// Enumerate all users of vreg operands that are def'd. Skip those that will
2001	// be sunk. For the rest, if they are not dominated by the block we will sink
2002	// MI into, propagate the copy source to them.
2003	SmallVector<MachineInstr *, 4> DbgDefUsers;
2004	SmallVector<Register, 4> DbgUseRegs;
2005	const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
2006	for (auto &MO : MI.all_defs()) {
2007	if (!MO.getReg().isVirtual())
2008	continue;
2009	DbgUseRegs.push_back(Elt: MO.getReg());
2010	for (auto &User : MRI.use_instructions(Reg: MO.getReg())) {
2011	if (!User.isDebugValue() || DT->dominates(A: TargetBlock, B: User.getParent()))
2012	continue;
2013
2014	// If is in same block, will either sink or be use-before-def.
2015	if (User.getParent() == MI.getParent())
2016	continue;
2017
2018	assert(User.hasDebugOperandForReg(MO.getReg()) &&
2019	"DBG_VALUE user of vreg, but has no operand for it?");
2020	DbgDefUsers.push_back(Elt: &User);
2021	}
2022	}
2023
2024	// Point the users of this copy that are no longer dominated, at the source
2025	// of the copy.
2026	for (auto *User : DbgDefUsers) {
2027	for (auto &Reg : DbgUseRegs) {
2028	for (auto &DbgOp : User->getDebugOperandsForReg(Reg)) {
2029	DbgOp.setReg(MI.getOperand(i: 1).getReg());
2030	DbgOp.setSubReg(MI.getOperand(i: 1).getSubReg());
2031	}
2032	}
2033	}
2034	}
2035
2036	//===----------------------------------------------------------------------===//
2037	// This pass is not intended to be a replacement or a complete alternative
2038	// for the pre-ra machine sink pass. It is only designed to sink COPY
2039	// instructions which should be handled after RA.
2040	//
2041	// This pass sinks COPY instructions into a successor block, if the COPY is not
2042	// used in the current block and the COPY is live-in to a single successor
2043	// (i.e., doesn't require the COPY to be duplicated). This avoids executing the
2044	// copy on paths where their results aren't needed. This also exposes
2045	// additional opportunites for dead copy elimination and shrink wrapping.
2046	//
2047	// These copies were either not handled by or are inserted after the MachineSink
2048	// pass. As an example of the former case, the MachineSink pass cannot sink
2049	// COPY instructions with allocatable source registers; for AArch64 these type
2050	// of copy instructions are frequently used to move function parameters (PhyReg)
2051	// into virtual registers in the entry block.
2052	//
2053	// For the machine IR below, this pass will sink %w19 in the entry into its
2054	// successor (%bb.1) because %w19 is only live-in in %bb.1.
2055	// %bb.0:
2056	// %wzr = SUBSWri %w1, 1
2057	// %w19 = COPY %w0
2058	// Bcc 11, %bb.2
2059	// %bb.1:
2060	// Live Ins: %w19
2061	// BL @fun
2062	// %w0 = ADDWrr %w0, %w19
2063	// RET %w0
2064	// %bb.2:
2065	// %w0 = COPY %wzr
2066	// RET %w0
2067	// As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
2068	// able to see %bb.0 as a candidate.
2069	//===----------------------------------------------------------------------===//
2070	namespace {
2071
2072	class PostRAMachineSinkingImpl {
2073	/// Track which register units have been modified and used.
2074	LiveRegUnits ModifiedRegUnits, UsedRegUnits;
2075
2076	/// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
2077	/// entry in this map for each unit it touches. The DBG_VALUE's entry
2078	/// consists of a pointer to the instruction itself, and a vector of registers
2079	/// referred to by the instruction that overlap the key register unit.
2080	DenseMap<MCRegUnit, SmallVector<MIRegs, 2>> SeenDbgInstrs;
2081
2082	/// Sink Copy instructions unused in the same block close to their uses in
2083	/// successors.
2084	bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
2085	const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
2086
2087	public:
2088	bool run(MachineFunction &MF);
2089	};
2090
2091	class PostRAMachineSinkingLegacy : public MachineFunctionPass {
2092	public:
2093	bool runOnMachineFunction(MachineFunction &MF) override;
2094
2095	static char ID;
2096	PostRAMachineSinkingLegacy() : MachineFunctionPass(ID) {}
2097	StringRef getPassName() const override { return "PostRA Machine Sink"; }
2098
2099	void getAnalysisUsage(AnalysisUsage &AU) const override {
2100	AU.setPreservesCFG();
2101	MachineFunctionPass::getAnalysisUsage(AU);
2102	}
2103
2104	MachineFunctionProperties getRequiredProperties() const override {
2105	return MachineFunctionProperties().set(
2106	MachineFunctionProperties::Property::NoVRegs);
2107	}
2108	};
2109
2110	} // namespace
2111
2112	char PostRAMachineSinkingLegacy::ID = 0;
2113	char &llvm::PostRAMachineSinkingID = PostRAMachineSinkingLegacy::ID;
2114
2115	INITIALIZE_PASS(PostRAMachineSinkingLegacy, "postra-machine-sink",
2116	"PostRA Machine Sink", false, false)
2117
2118	static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, Register Reg,
2119	const TargetRegisterInfo *TRI) {
2120	LiveRegUnits LiveInRegUnits(*TRI);
2121	LiveInRegUnits.addLiveIns(MBB);
2122	return !LiveInRegUnits.available(Reg);
2123	}
2124
2125	static MachineBasicBlock *
2126	getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
2127	const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
2128	Register Reg, const TargetRegisterInfo *TRI) {
2129	// Try to find a single sinkable successor in which Reg is live-in.
2130	MachineBasicBlock *BB = nullptr;
2131	for (auto *SI : SinkableBBs) {
2132	if (aliasWithRegsInLiveIn(MBB&: *SI, Reg, TRI)) {
2133	// If BB is set here, Reg is live-in to at least two sinkable successors,
2134	// so quit.
2135	if (BB)
2136	return nullptr;
2137	BB = SI;
2138	}
2139	}
2140	// Reg is not live-in to any sinkable successors.
2141	if (!BB)
2142	return nullptr;
2143
2144	// Check if any register aliased with Reg is live-in in other successors.
2145	for (auto *SI : CurBB.successors()) {
2146	if (!SinkableBBs.count(Ptr: SI) && aliasWithRegsInLiveIn(MBB&: *SI, Reg, TRI))
2147	return nullptr;
2148	}
2149	return BB;
2150	}
2151
2152	static MachineBasicBlock *
2153	getSingleLiveInSuccBB(MachineBasicBlock &CurBB,
2154	const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
2155	ArrayRef<Register> DefedRegsInCopy,
2156	const TargetRegisterInfo *TRI) {
2157	MachineBasicBlock *SingleBB = nullptr;
2158	for (auto DefReg : DefedRegsInCopy) {
2159	MachineBasicBlock *BB =
2160	getSingleLiveInSuccBB(CurBB, SinkableBBs, Reg: DefReg, TRI);
2161	if (!BB || (SingleBB && SingleBB != BB))
2162	return nullptr;
2163	SingleBB = BB;
2164	}
2165	return SingleBB;
2166	}
2167
2168	static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB,
2169	const SmallVectorImpl<unsigned> &UsedOpsInCopy,
2170	const LiveRegUnits &UsedRegUnits,
2171	const TargetRegisterInfo *TRI) {
2172	for (auto U : UsedOpsInCopy) {
2173	MachineOperand &MO = MI->getOperand(i: U);
2174	Register SrcReg = MO.getReg();
2175	if (!UsedRegUnits.available(Reg: SrcReg)) {
2176	MachineBasicBlock::iterator NI = std::next(x: MI->getIterator());
2177	for (MachineInstr &UI : make_range(x: NI, y: CurBB.end())) {
2178	if (UI.killsRegister(Reg: SrcReg, TRI)) {
2179	UI.clearRegisterKills(Reg: SrcReg, RegInfo: TRI);
2180	MO.setIsKill(true);
2181	break;
2182	}
2183	}
2184	}
2185	}
2186	}
2187
2188	static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB,
2189	const SmallVectorImpl<unsigned> &UsedOpsInCopy,
2190	const SmallVectorImpl<Register> &DefedRegsInCopy) {
2191	MachineFunction &MF = *SuccBB->getParent();
2192	const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2193	for (Register DefReg : DefedRegsInCopy)
2194	for (MCPhysReg S : TRI->subregs_inclusive(Reg: DefReg))
2195	SuccBB->removeLiveIn(Reg: S);
2196	for (auto U : UsedOpsInCopy)
2197	SuccBB->addLiveIn(PhysReg: MI->getOperand(i: U).getReg());
2198	SuccBB->sortUniqueLiveIns();
2199	}
2200
2201	static bool hasRegisterDependency(MachineInstr *MI,
2202	SmallVectorImpl<unsigned> &UsedOpsInCopy,
2203	SmallVectorImpl<Register> &DefedRegsInCopy,
2204	LiveRegUnits &ModifiedRegUnits,
2205	LiveRegUnits &UsedRegUnits) {
2206	bool HasRegDependency = false;
2207	for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
2208	MachineOperand &MO = MI->getOperand(i);
2209	if (!MO.isReg())
2210	continue;
2211	Register Reg = MO.getReg();
2212	if (!Reg)
2213	continue;
2214	if (MO.isDef()) {
2215	if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
2216	HasRegDependency = true;
2217	break;
2218	}
2219	DefedRegsInCopy.push_back(Elt: Reg);
2220
2221	// FIXME: instead of isUse(), readsReg() would be a better fix here,
2222	// For example, we can ignore modifications in reg with undef. However,
2223	// it's not perfectly clear if skipping the internal read is safe in all
2224	// other targets.
2225	} else if (MO.isUse()) {
2226	if (!ModifiedRegUnits.available(Reg)) {
2227	HasRegDependency = true;
2228	break;
2229	}
2230	UsedOpsInCopy.push_back(Elt: i);
2231	}
2232	}
2233	return HasRegDependency;
2234	}
2235
2236	bool PostRAMachineSinkingImpl::tryToSinkCopy(MachineBasicBlock &CurBB,
2237	MachineFunction &MF,
2238	const TargetRegisterInfo *TRI,
2239	const TargetInstrInfo *TII) {
2240	SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
2241	// FIXME: For now, we sink only to a successor which has a single predecessor
2242	// so that we can directly sink COPY instructions to the successor without
2243	// adding any new block or branch instruction.
2244	for (MachineBasicBlock *SI : CurBB.successors())
2245	if (!SI->livein_empty() && SI->pred_size() == 1)
2246	SinkableBBs.insert(Ptr: SI);
2247
2248	if (SinkableBBs.empty())
2249	return false;
2250
2251	bool Changed = false;
2252
2253	// Track which registers have been modified and used between the end of the
2254	// block and the current instruction.
2255	ModifiedRegUnits.clear();
2256	UsedRegUnits.clear();
2257	SeenDbgInstrs.clear();
2258
2259	for (MachineInstr &MI : llvm::make_early_inc_range(Range: llvm::reverse(C&: CurBB))) {
2260	// Track the operand index for use in Copy.
2261	SmallVector<unsigned, 2> UsedOpsInCopy;
2262	// Track the register number defed in Copy.
2263	SmallVector<Register, 2> DefedRegsInCopy;
2264
2265	// We must sink this DBG_VALUE if its operand is sunk. To avoid searching
2266	// for DBG_VALUEs later, record them when they're encountered.
2267	if (MI.isDebugValue() && !MI.isDebugRef()) {
2268	SmallDenseMap<MCRegUnit, SmallVector<Register, 2>, 4> MIUnits;
2269	bool IsValid = true;
2270	for (MachineOperand &MO : MI.debug_operands()) {
2271	if (MO.isReg() && MO.getReg().isPhysical()) {
2272	// Bail if we can already tell the sink would be rejected, rather
2273	// than needlessly accumulating lots of DBG_VALUEs.
2274	if (hasRegisterDependency(MI: &MI, UsedOpsInCopy, DefedRegsInCopy,
2275	ModifiedRegUnits, UsedRegUnits)) {
2276	IsValid = false;
2277	break;
2278	}
2279
2280	// Record debug use of each reg unit.
2281	for (MCRegUnit Unit : TRI->regunits(Reg: MO.getReg()))
2282	MIUnits[Unit].push_back(Elt: MO.getReg());
2283	}
2284	}
2285	if (IsValid) {
2286	for (auto &RegOps : MIUnits)
2287	SeenDbgInstrs[RegOps.first].emplace_back(Args: &MI,
2288	Args: std::move(RegOps.second));
2289	}
2290	continue;
2291	}
2292
2293	if (MI.isDebugOrPseudoInstr())
2294	continue;
2295
2296	// Do not move any instruction across function call.
2297	if (MI.isCall())
2298	return false;
2299
2300	if (!MI.isCopy() || !MI.getOperand(i: 0).isRenamable()) {
2301	LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2302	TRI);
2303	continue;
2304	}
2305
2306	// Don't sink the COPY if it would violate a register dependency.
2307	if (hasRegisterDependency(MI: &MI, UsedOpsInCopy, DefedRegsInCopy,
2308	ModifiedRegUnits, UsedRegUnits)) {
2309	LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2310	TRI);
2311	continue;
2312	}
2313	assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
2314	"Unexpect SrcReg or DefReg");
2315	MachineBasicBlock *SuccBB =
2316	getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
2317	// Don't sink if we cannot find a single sinkable successor in which Reg
2318	// is live-in.
2319	if (!SuccBB) {
2320	LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2321	TRI);
2322	continue;
2323	}
2324	assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
2325	"Unexpected predecessor");
2326
2327	// Collect DBG_VALUEs that must sink with this copy. We've previously
2328	// recorded which reg units that DBG_VALUEs read, if this instruction
2329	// writes any of those units then the corresponding DBG_VALUEs must sink.
2330	MapVector<MachineInstr *, MIRegs::second_type> DbgValsToSinkMap;
2331	for (auto &MO : MI.all_defs()) {
2332	for (MCRegUnit Unit : TRI->regunits(Reg: MO.getReg())) {
2333	for (const auto &MIRegs : SeenDbgInstrs.lookup(Val: Unit)) {
2334	auto &Regs = DbgValsToSinkMap[MIRegs.first];
2335	llvm::append_range(C&: Regs, R: MIRegs.second);
2336	}
2337	}
2338	}
2339	auto DbgValsToSink = DbgValsToSinkMap.takeVector();
2340
2341	LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccBB);
2342
2343	MachineBasicBlock::iterator InsertPos =
2344	SuccBB->SkipPHIsAndLabels(I: SuccBB->begin());
2345	if (blockPrologueInterferes(BB: SuccBB, End: InsertPos, MI, TRI, TII, MRI: nullptr)) {
2346	LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2347	TRI);
2348	LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
2349	continue;
2350	}
2351
2352	// Clear the kill flag if SrcReg is killed between MI and the end of the
2353	// block.
2354	clearKillFlags(MI: &MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
2355	performSink(MI, SuccToSinkTo&: *SuccBB, InsertPos, DbgValuesToSink: DbgValsToSink);
2356	updateLiveIn(MI: &MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
2357
2358	Changed = true;
2359	++NumPostRACopySink;
2360	}
2361	return Changed;
2362	}
2363
2364	bool PostRAMachineSinkingImpl::run(MachineFunction &MF) {
2365	bool Changed = false;
2366	const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2367	const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
2368
2369	ModifiedRegUnits.init(TRI: *TRI);
2370	UsedRegUnits.init(TRI: *TRI);
2371	for (auto &BB : MF)
2372	Changed |= tryToSinkCopy(CurBB&: BB, MF, TRI, TII);
2373
2374	return Changed;
2375	}
2376
2377	bool PostRAMachineSinkingLegacy::runOnMachineFunction(MachineFunction &MF) {
2378	if (skipFunction(F: MF.getFunction()))
2379	return false;
2380
2381	return PostRAMachineSinkingImpl().run(MF);
2382	}
2383
2384	PreservedAnalyses
2385	PostRAMachineSinkingPass::run(MachineFunction &MF,
2386	MachineFunctionAnalysisManager &MFAM) {
2387	MFPropsModifier _(*this, MF);
2388
2389	if (!PostRAMachineSinkingImpl().run(MF))
2390	return PreservedAnalyses::all();
2391
2392	PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
2393	PA.preserveSet<CFGAnalyses>();
2394	return PA;
2395	}
2396