LLVM 18.0.0git
MachineSink.cpp
Go to the documentation of this file.
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/ADT/DenseSet.h"
20#include "llvm/ADT/MapVector.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/SmallSet.h"
26#include "llvm/ADT/Statistic.h"
28#include "llvm/Analysis/CFG.h"
47#include "llvm/IR/BasicBlock.h"
49#include "llvm/IR/LLVMContext.h"
52#include "llvm/Pass.h"
55#include "llvm/Support/Debug.h"
57#include <algorithm>
58#include <cassert>
59#include <cstdint>
60#include <utility>
61#include <vector>
62
63using namespace llvm;
64
65#define DEBUG_TYPE "machine-sink"
66
67static cl::opt<bool>
68SplitEdges("machine-sink-split",
69 cl::desc("Split critical edges during machine sinking"),
70 cl::init(true), cl::Hidden);
71
72static cl::opt<bool>
73UseBlockFreqInfo("machine-sink-bfi",
74 cl::desc("Use block frequency info to find successors to sink"),
75 cl::init(true), cl::Hidden);
76
78 "machine-sink-split-probability-threshold",
80 "Percentage threshold for splitting single-instruction critical edge. "
81 "If the branch threshold is higher than this threshold, we allow "
82 "speculative execution of up to 1 instruction to avoid branching to "
83 "splitted critical edge"),
84 cl::init(40), cl::Hidden);
85
87 "machine-sink-load-instrs-threshold",
88 cl::desc("Do not try to find alias store for a load if there is a in-path "
89 "block whose instruction number is higher than this threshold."),
90 cl::init(2000), cl::Hidden);
91
93 "machine-sink-load-blocks-threshold",
94 cl::desc("Do not try to find alias store for a load if the block number in "
95 "the straight line is higher than this threshold."),
96 cl::init(20), cl::Hidden);
97
98static cl::opt<bool>
99 SinkInstsIntoCycle("sink-insts-to-avoid-spills",
100 cl::desc("Sink instructions into cycles to avoid "
101 "register spills"),
102 cl::init(false), cl::Hidden);
103
105 "machine-sink-cycle-limit",
106 cl::desc("The maximum number of instructions considered for cycle sinking."),
107 cl::init(50), cl::Hidden);
108
109STATISTIC(NumSunk, "Number of machine instructions sunk");
110STATISTIC(NumCycleSunk, "Number of machine instructions sunk into a cycle");
111STATISTIC(NumSplit, "Number of critical edges split");
112STATISTIC(NumCoalesces, "Number of copies coalesced");
113STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
114
115namespace {
116
117 class MachineSinking : public MachineFunctionPass {
118 const TargetSubtargetInfo *STI = nullptr;
119 const TargetInstrInfo *TII = nullptr;
120 const TargetRegisterInfo *TRI = nullptr;
121 MachineRegisterInfo *MRI = nullptr; // Machine register information
122 MachineDominatorTree *DT = nullptr; // Machine dominator tree
123 MachinePostDominatorTree *PDT = nullptr; // Machine post dominator tree
124 MachineCycleInfo *CI = nullptr;
125 MachineBlockFrequencyInfo *MBFI = nullptr;
126 const MachineBranchProbabilityInfo *MBPI = nullptr;
127 AliasAnalysis *AA = nullptr;
128 RegisterClassInfo RegClassInfo;
129
130 // Remember which edges have been considered for breaking.
132 CEBCandidates;
133 // Remember which edges we are about to split.
134 // This is different from CEBCandidates since those edges
135 // will be split.
137
138 DenseSet<Register> RegsToClearKillFlags;
139
140 using AllSuccsCache =
142
143 /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
144 /// post-dominated by another DBG_VALUE of the same variable location.
145 /// This is necessary to detect sequences such as:
146 /// %0 = someinst
147 /// DBG_VALUE %0, !123, !DIExpression()
148 /// %1 = anotherinst
149 /// DBG_VALUE %1, !123, !DIExpression()
150 /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
151 /// would re-order assignments.
152 using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
153
154 /// Record of DBG_VALUE uses of vregs in a block, so that we can identify
155 /// debug instructions to sink.
157
158 /// Record of debug variables that have had their locations set in the
159 /// current block.
160 DenseSet<DebugVariable> SeenDbgVars;
161
163 HasStoreCache;
164
167 StoreInstrCache;
168
169 /// Cached BB's register pressure.
171 CachedRegisterPressure;
172
173 bool EnableSinkAndFold;
174
175 public:
176 static char ID; // Pass identification
177
178 MachineSinking() : MachineFunctionPass(ID) {
180 }
181
182 bool runOnMachineFunction(MachineFunction &MF) override;
183
184 void getAnalysisUsage(AnalysisUsage &AU) const override {
196 }
197
198 void releaseMemory() override {
199 CEBCandidates.clear();
200 }
201
202 private:
204 void ProcessDbgInst(MachineInstr &MI);
205 bool isWorthBreakingCriticalEdge(MachineInstr &MI,
208
209 bool hasStoreBetween(MachineBasicBlock *From, MachineBasicBlock *To,
211
212 /// Postpone the splitting of the given critical
213 /// edge (\p From, \p To).
214 ///
215 /// We do not split the edges on the fly. Indeed, this invalidates
216 /// the dominance information and thus triggers a lot of updates
217 /// of that information underneath.
218 /// Instead, we postpone all the splits after each iteration of
219 /// the main loop. That way, the information is at least valid
220 /// for the lifetime of an iteration.
221 ///
222 /// \return True if the edge is marked as toSplit, false otherwise.
223 /// False can be returned if, for instance, this is not profitable.
224 bool PostponeSplitCriticalEdge(MachineInstr &MI,
227 bool BreakPHIEdge);
228 bool SinkInstruction(MachineInstr &MI, bool &SawStore,
229 AllSuccsCache &AllSuccessors);
230
231 /// If we sink a COPY inst, some debug users of it's destination may no
232 /// longer be dominated by the COPY, and will eventually be dropped.
233 /// This is easily rectified by forwarding the non-dominated debug uses
234 /// to the copy source.
235 void SalvageUnsunkDebugUsersOfCopy(MachineInstr &,
236 MachineBasicBlock *TargetBlock);
237 bool AllUsesDominatedByBlock(Register Reg, MachineBasicBlock *MBB,
238 MachineBasicBlock *DefMBB, bool &BreakPHIEdge,
239 bool &LocalUse) const;
241 bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
242
243 void FindCycleSinkCandidates(MachineCycle *Cycle, MachineBasicBlock *BB,
245 bool SinkIntoCycle(MachineCycle *Cycle, MachineInstr &I);
246
247 bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
249 MachineBasicBlock *SuccToSinkTo,
250 AllSuccsCache &AllSuccessors);
251
252 bool PerformTrivialForwardCoalescing(MachineInstr &MI,
254
255 bool PerformSinkAndFold(MachineInstr &MI, MachineBasicBlock *MBB);
256
258 GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
259 AllSuccsCache &AllSuccessors) const;
260
261 std::vector<unsigned> &getBBRegisterPressure(const MachineBasicBlock &MBB);
262
263 bool registerPressureSetExceedsLimit(unsigned NRegs,
264 const TargetRegisterClass *RC,
265 const MachineBasicBlock &MBB);
266 };
267
268} // end anonymous namespace
269
270char MachineSinking::ID = 0;
271
272char &llvm::MachineSinkingID = MachineSinking::ID;
273
275 "Machine code sinking", false, false)
281 "Machine code sinking", false, false)
282
283/// Return true if a target defined block prologue instruction interferes
284/// with a sink candidate.
291 for (MachineBasicBlock::const_iterator PI = BB->getFirstNonPHI(); PI != End;
292 ++PI) {
293 // Only check target defined prologue instructions
294 if (!TII->isBasicBlockPrologue(*PI))
295 continue;
296 for (auto &MO : MI.operands()) {
297 if (!MO.isReg())
298 continue;
299 Register Reg = MO.getReg();
300 if (!Reg)
301 continue;
302 if (MO.isUse()) {
303 if (Reg.isPhysical() &&
304 (TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(Reg))))
305 continue;
306 if (PI->modifiesRegister(Reg, TRI))
307 return true;
308 } else {
309 if (PI->readsRegister(Reg, TRI))
310 return true;
311 // Check for interference with non-dead defs
312 auto *DefOp = PI->findRegisterDefOperand(Reg, false, true, TRI);
313 if (DefOp && !DefOp->isDead())
314 return true;
315 }
316 }
317 }
318
319 return false;
320}
321
322bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
324 if (!MI.isCopy())
325 return false;
326
327 Register SrcReg = MI.getOperand(1).getReg();
328 Register DstReg = MI.getOperand(0).getReg();
329 if (!SrcReg.isVirtual() || !DstReg.isVirtual() ||
330 !MRI->hasOneNonDBGUse(SrcReg))
331 return false;
332
333 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
334 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg);
335 if (SRC != DRC)
336 return false;
337
338 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
339 if (DefMI->isCopyLike())
340 return false;
341 LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
342 LLVM_DEBUG(dbgs() << "*** to: " << MI);
343 MRI->replaceRegWith(DstReg, SrcReg);
344 MI.eraseFromParent();
345
346 // Conservatively, clear any kill flags, since it's possible that they are no
347 // longer correct.
348 MRI->clearKillFlags(SrcReg);
349
350 ++NumCoalesces;
351 return true;
352}
353
354bool MachineSinking::PerformSinkAndFold(MachineInstr &MI,
356 if (MI.isCopy() || MI.mayLoadOrStore() ||
357 MI.getOpcode() == TargetOpcode::REG_SEQUENCE)
358 return false;
359
360 // Don't sink instructions that the target prefers not to sink.
361 if (!TII->shouldSink(MI))
362 return false;
363
364 // Check if it's safe to move the instruction.
365 bool SawStore = true;
366 if (!MI.isSafeToMove(AA, SawStore))
367 return false;
368
369 // Convergent operations may not be made control-dependent on additional
370 // values.
371 if (MI.isConvergent())
372 return false;
373
374 // Don't sink defs/uses of hard registers or if the instruction defines more
375 // than one register.
376 // Don't sink more than two register uses - it'll cover most of the cases and
377 // greatly simplifies the register pressure checks.
378 Register DefReg;
379 Register UsedRegA, UsedRegB;
380 for (const MachineOperand &MO : MI.operands()) {
381 if (MO.isImm() || MO.isRegMask() || MO.isRegLiveOut() || MO.isMetadata() ||
382 MO.isMCSymbol() || MO.isDbgInstrRef() || MO.isCFIIndex() ||
383 MO.isIntrinsicID() || MO.isPredicate() || MO.isShuffleMask())
384 continue;
385 if (!MO.isReg())
386 return false;
387
388 Register Reg = MO.getReg();
389 if (Reg == 0)
390 continue;
391
392 if (Reg.isVirtual()) {
393 if (MO.isDef()) {
394 if (DefReg)
395 return false;
396 DefReg = Reg;
397 continue;
398 }
399
400 if (UsedRegA == 0)
401 UsedRegA = Reg;
402 else if (UsedRegB == 0)
403 UsedRegB = Reg;
404 else
405 return false;
406 continue;
407 }
408
409 if (Reg.isPhysical() &&
410 (MRI->isConstantPhysReg(Reg) || TII->isIgnorableUse(MO)))
411 continue;
412
413 return false;
414 }
415
416 // Scan uses of the destination register. Every use, except the last, must be
417 // a copy, with a chain of copies terminating with either a copy into a hard
418 // register, or a load/store instruction where the use is part of the
419 // address (*not* the stored value).
420 using SinkInfo = std::pair<MachineInstr *, ExtAddrMode>;
421 SmallVector<SinkInfo> SinkInto;
422 SmallVector<Register> Worklist;
423
424 const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
425 const TargetRegisterClass *RCA =
426 UsedRegA == 0 ? nullptr : MRI->getRegClass(UsedRegA);
427 const TargetRegisterClass *RCB =
428 UsedRegB == 0 ? nullptr : MRI->getRegClass(UsedRegB);
429
430 Worklist.push_back(DefReg);
431 while (!Worklist.empty()) {
432 Register Reg = Worklist.pop_back_val();
433
434 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
435 ExtAddrMode MaybeAM;
436 MachineInstr &UseInst = *MO.getParent();
437 if (UseInst.isCopy()) {
438 Register DstReg;
439 if (const MachineOperand &O = UseInst.getOperand(0); O.isReg())
440 DstReg = O.getReg();
441 if (DstReg == 0)
442 return false;
443 if (DstReg.isVirtual()) {
444 Worklist.push_back(DstReg);
445 continue;
446 }
447 // If we are going to replace a copy, the original instruction must be
448 // as cheap as a copy.
449 if (!TII->isAsCheapAsAMove(MI))
450 return false;
451 // The hard register must be in the register class of the original
452 // instruction's destination register.
453 if (!RC->contains(DstReg))
454 return false;
455 } else if (UseInst.mayLoadOrStore()) {
456 ExtAddrMode AM;
457 if (!TII->canFoldIntoAddrMode(UseInst, Reg, MI, AM))
458 return false;
459 MaybeAM = AM;
460 } else {
461 return false;
462 }
463
464 if (UseInst.getParent() != MI.getParent()) {
465 // If the register class of the register we are replacing is a superset
466 // of any of the register classes of the operands of the materialized
467 // instruction don't consider that live range extended.
468 const TargetRegisterClass *RCS = MRI->getRegClass(Reg);
469 if (RCA && RCA->hasSuperClassEq(RCS))
470 RCA = nullptr;
471 else if (RCB && RCB->hasSuperClassEq(RCS))
472 RCB = nullptr;
473 if (RCA || RCB) {
474 if (RCA == nullptr) {
475 RCA = RCB;
476 RCB = nullptr;
477 }
478
479 unsigned NRegs = !!RCA + !!RCB;
480 if (RCA == RCB)
481 RCB = nullptr;
482
483 // Check we don't exceed register pressure at the destination.
484 const MachineBasicBlock &MBB = *UseInst.getParent();
485 if (RCB == nullptr) {
486 if (registerPressureSetExceedsLimit(NRegs, RCA, MBB))
487 return false;
488 } else if (registerPressureSetExceedsLimit(1, RCA, MBB) ||
489 registerPressureSetExceedsLimit(1, RCB, MBB)) {
490 return false;
491 }
492 }
493 }
494
495 SinkInto.emplace_back(&UseInst, MaybeAM);
496 }
497 }
498
499 if (SinkInto.empty())
500 return false;
501
502 // Now we know we can fold the instruction in all its users.
503 if (UsedRegA)
504 MRI->clearKillFlags(UsedRegA);
505 if (UsedRegB)
506 MRI->clearKillFlags(UsedRegB);
507
508 for (auto &[SinkDst, MaybeAM] : SinkInto) {
509 MachineInstr *New = nullptr;
510 LLVM_DEBUG(dbgs() << "Sinking copy of"; MI.dump(); dbgs() << "into";
511 SinkDst->dump());
512 if (SinkDst->isCopy()) {
513 // TODO: After performing the sink-and-fold, the original instruction is
514 // deleted. Its value is still available (in a hard register), so if there
515 // are debug instructions which refer to the (now deleted) virtual
516 // register they could be updated to refer to the hard register, in
517 // principle. However, it's not clear how to do that, moreover in some
518 // cases the debug instructions may need to be replicated proportionally
519 // to the number of the COPY instructions replaced and in some extreme
520 // cases we can end up with quadratic increase in the number of debug
521 // instructions.
522
523 // Sink a copy of the instruction, replacing a COPY instruction.
524 MachineBasicBlock::iterator InsertPt = SinkDst->getIterator();
525 Register DstReg = SinkDst->getOperand(0).getReg();
526 TII->reMaterialize(*SinkDst->getParent(), InsertPt, DstReg, 0, MI, *TRI);
527 New = &*std::prev(InsertPt);
528 if (!New->getDebugLoc())
529 New->setDebugLoc(SinkDst->getDebugLoc());
530 } else {
531 // Fold instruction into the addressing mode of a memory instruction.
532 New = TII->emitLdStWithAddr(*SinkDst, MaybeAM);
533 }
534 LLVM_DEBUG(dbgs() << "yielding"; New->dump());
535 // Clear the StoreInstrCache, since we may invalidate it by erasing.
536 if (SinkDst->mayStore() && !SinkDst->hasOrderedMemoryRef())
537 StoreInstrCache.clear();
538 SinkDst->eraseFromParent();
539 }
540
541 // Collect operands that need to be cleaned up because the registers no longer
542 // exist (in COPYs and debug instructions). We cannot delete instructions or
543 // clear operands while traversing register uses.
545 Worklist.push_back(DefReg);
546 while (!Worklist.empty()) {
547 Register Reg = Worklist.pop_back_val();
548 for (MachineOperand &MO : MRI->use_operands(Reg)) {
549 MachineInstr *U = MO.getParent();
550 assert((U->isCopy() || U->isDebugInstr()) &&
551 "Only debug uses and copies must remain");
552 if (U->isCopy())
553 Worklist.push_back(U->getOperand(0).getReg());
554 Cleanup.push_back(&MO);
555 }
556 }
557
558 // Delete the dead COPYs and clear operands in debug instructions
559 for (MachineOperand *MO : Cleanup) {
560 MachineInstr *I = MO->getParent();
561 if (I->isCopy()) {
562 I->eraseFromParent();
563 } else {
564 MO->setReg(0);
565 MO->setSubReg(0);
566 }
567 }
568
569 MI.eraseFromParent();
570 return true;
571}
572
573/// AllUsesDominatedByBlock - Return true if all uses of the specified register
574/// occur in blocks dominated by the specified block. If any use is in the
575/// definition block, then return false since it is never legal to move def
576/// after uses.
577bool MachineSinking::AllUsesDominatedByBlock(Register Reg,
579 MachineBasicBlock *DefMBB,
580 bool &BreakPHIEdge,
581 bool &LocalUse) const {
582 assert(Reg.isVirtual() && "Only makes sense for vregs");
583
584 // Ignore debug uses because debug info doesn't affect the code.
585 if (MRI->use_nodbg_empty(Reg))
586 return true;
587
588 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken
589 // into and they are all PHI nodes. In this case, machine-sink must break
590 // the critical edge first. e.g.
591 //
592 // %bb.1:
593 // Predecessors according to CFG: %bb.0
594 // ...
595 // %def = DEC64_32r %x, implicit-def dead %eflags
596 // ...
597 // JE_4 <%bb.37>, implicit %eflags
598 // Successors according to CFG: %bb.37 %bb.2
599 //
600 // %bb.2:
601 // %p = PHI %y, %bb.0, %def, %bb.1
602 if (all_of(MRI->use_nodbg_operands(Reg), [&](MachineOperand &MO) {
603 MachineInstr *UseInst = MO.getParent();
604 unsigned OpNo = MO.getOperandNo();
605 MachineBasicBlock *UseBlock = UseInst->getParent();
606 return UseBlock == MBB && UseInst->isPHI() &&
607 UseInst->getOperand(OpNo + 1).getMBB() == DefMBB;
608 })) {
609 BreakPHIEdge = true;
610 return true;
611 }
612
613 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
614 // Determine the block of the use.
615 MachineInstr *UseInst = MO.getParent();
616 unsigned OpNo = &MO - &UseInst->getOperand(0);
617 MachineBasicBlock *UseBlock = UseInst->getParent();
618 if (UseInst->isPHI()) {
619 // PHI nodes use the operand in the predecessor block, not the block with
620 // the PHI.
621 UseBlock = UseInst->getOperand(OpNo+1).getMBB();
622 } else if (UseBlock == DefMBB) {
623 LocalUse = true;
624 return false;
625 }
626
627 // Check that it dominates.
628 if (!DT->dominates(MBB, UseBlock))
629 return false;
630 }
631
632 return true;
633}
634
635/// Return true if this machine instruction loads from global offset table or
636/// constant pool.
638 assert(MI.mayLoad() && "Expected MI that loads!");
639
640 // If we lost memory operands, conservatively assume that the instruction
641 // reads from everything..
642 if (MI.memoperands_empty())
643 return true;
644
645 for (MachineMemOperand *MemOp : MI.memoperands())
646 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())
647 if (PSV->isGOT() || PSV->isConstantPool())
648 return true;
649
650 return false;
651}
652
653void MachineSinking::FindCycleSinkCandidates(
656 for (auto &MI : *BB) {
657 LLVM_DEBUG(dbgs() << "CycleSink: Analysing candidate: " << MI);
658 if (!TII->shouldSink(MI)) {
659 LLVM_DEBUG(dbgs() << "CycleSink: Instruction not a candidate for this "
660 "target\n");
661 continue;
662 }
663 if (!isCycleInvariant(Cycle, MI)) {
664 LLVM_DEBUG(dbgs() << "CycleSink: Instruction is not cycle invariant\n");
665 continue;
666 }
667 bool DontMoveAcrossStore = true;
668 if (!MI.isSafeToMove(AA, DontMoveAcrossStore)) {
669 LLVM_DEBUG(dbgs() << "CycleSink: Instruction not safe to move.\n");
670 continue;
671 }
672 if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
673 LLVM_DEBUG(dbgs() << "CycleSink: Dont sink GOT or constant pool loads\n");
674 continue;
675 }
676 if (MI.isConvergent())
677 continue;
678
679 const MachineOperand &MO = MI.getOperand(0);
680 if (!MO.isReg() || !MO.getReg() || !MO.isDef())
681 continue;
682 if (!MRI->hasOneDef(MO.getReg()))
683 continue;
684
685 LLVM_DEBUG(dbgs() << "CycleSink: Instruction added as candidate.\n");
686 Candidates.push_back(&MI);
687 }
688}
689
690bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
691 if (skipFunction(MF.getFunction()))
692 return false;
693
694 LLVM_DEBUG(dbgs() << "******** Machine Sinking ********\n");
695
696 STI = &MF.getSubtarget();
697 TII = STI->getInstrInfo();
698 TRI = STI->getRegisterInfo();
699 MRI = &MF.getRegInfo();
700 DT = &getAnalysis<MachineDominatorTree>();
701 PDT = &getAnalysis<MachinePostDominatorTree>();
702 CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
703 MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
704 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
705 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
706 RegClassInfo.runOnMachineFunction(MF);
707 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
708 EnableSinkAndFold = PassConfig->getEnableSinkAndFold();
709
710 bool EverMadeChange = false;
711
712 while (true) {
713 bool MadeChange = false;
714
715 // Process all basic blocks.
716 CEBCandidates.clear();
717 ToSplit.clear();
718 for (auto &MBB: MF)
719 MadeChange |= ProcessBlock(MBB);
720
721 // If we have anything we marked as toSplit, split it now.
722 for (const auto &Pair : ToSplit) {
723 auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);
724 if (NewSucc != nullptr) {
725 LLVM_DEBUG(dbgs() << " *** Splitting critical edge: "
726 << printMBBReference(*Pair.first) << " -- "
727 << printMBBReference(*NewSucc) << " -- "
728 << printMBBReference(*Pair.second) << '\n');
729 if (MBFI)
730 MBFI->onEdgeSplit(*Pair.first, *NewSucc, *MBPI);
731
732 MadeChange = true;
733 ++NumSplit;
734 CI->splitCriticalEdge(Pair.first, Pair.second, NewSucc);
735 } else
736 LLVM_DEBUG(dbgs() << " *** Not legal to break critical edge\n");
737 }
738 // If this iteration over the code changed anything, keep iterating.
739 if (!MadeChange) break;
740 EverMadeChange = true;
741 }
742
743 if (SinkInstsIntoCycle) {
745 CI->toplevel_end());
746 for (auto *Cycle : Cycles) {
748 if (!Preheader) {
749 LLVM_DEBUG(dbgs() << "CycleSink: Can't find preheader\n");
750 continue;
751 }
753 FindCycleSinkCandidates(Cycle, Preheader, Candidates);
754
755 // Walk the candidates in reverse order so that we start with the use
756 // of a def-use chain, if there is any.
757 // TODO: Sort the candidates using a cost-model.
758 unsigned i = 0;
759 for (MachineInstr *I : llvm::reverse(Candidates)) {
760 if (i++ == SinkIntoCycleLimit) {
761 LLVM_DEBUG(dbgs() << "CycleSink: Limit reached of instructions to "
762 "be analysed.");
763 break;
764 }
765
766 if (!SinkIntoCycle(Cycle, *I))
767 break;
768 EverMadeChange = true;
769 ++NumCycleSunk;
770 }
771 }
772 }
773
774 HasStoreCache.clear();
775 StoreInstrCache.clear();
776
777 // Now clear any kill flags for recorded registers.
778 for (auto I : RegsToClearKillFlags)
779 MRI->clearKillFlags(I);
780 RegsToClearKillFlags.clear();
781
782 return EverMadeChange;
783}
784
785bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
786 if ((!EnableSinkAndFold && MBB.succ_size() <= 1) || MBB.empty())
787 return false;
788
789 // Don't bother sinking code out of unreachable blocks. In addition to being
790 // unprofitable, it can also lead to infinite looping, because in an
791 // unreachable cycle there may be nowhere to stop.
792 if (!DT->isReachableFromEntry(&MBB)) return false;
793
794 bool MadeChange = false;
795
796 // Cache all successors, sorted by frequency info and cycle depth.
797 AllSuccsCache AllSuccessors;
798
799 // Walk the basic block bottom-up. Remember if we saw a store.
801 --I;
802 bool ProcessedBegin, SawStore = false;
803 do {
804 MachineInstr &MI = *I; // The instruction to sink.
805
806 // Predecrement I (if it's not begin) so that it isn't invalidated by
807 // sinking.
808 ProcessedBegin = I == MBB.begin();
809 if (!ProcessedBegin)
810 --I;
811
812 if (MI.isDebugOrPseudoInstr()) {
813 if (MI.isDebugValue())
814 ProcessDbgInst(MI);
815 continue;
816 }
817
818 if (EnableSinkAndFold && PerformSinkAndFold(MI, &MBB)) {
819 MadeChange = true;
820 continue;
821 }
822
823 // Can't sink anything out of a block that has less than two successors.
824 if (MBB.succ_size() <= 1)
825 continue;
826
827 if (PerformTrivialForwardCoalescing(MI, &MBB)) {
828 MadeChange = true;
829 continue;
830 }
831
832 if (SinkInstruction(MI, SawStore, AllSuccessors)) {
833 ++NumSunk;
834 MadeChange = true;
835 }
836
837 // If we just processed the first instruction in the block, we're done.
838 } while (!ProcessedBegin);
839
840 SeenDbgUsers.clear();
841 SeenDbgVars.clear();
842 // recalculate the bb register pressure after sinking one BB.
843 CachedRegisterPressure.clear();
844 return MadeChange;
845}
846
847void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
848 // When we see DBG_VALUEs for registers, record any vreg it reads, so that
849 // we know what to sink if the vreg def sinks.
850 assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
851
852 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
853 MI.getDebugLoc()->getInlinedAt());
854 bool SeenBefore = SeenDbgVars.contains(Var);
855
856 for (MachineOperand &MO : MI.debug_operands()) {
857 if (MO.isReg() && MO.getReg().isVirtual())
858 SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore));
859 }
860
861 // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
862 SeenDbgVars.insert(Var);
863}
864
865bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
867 MachineBasicBlock *To) {
868 // FIXME: Need much better heuristics.
869
870 // If the pass has already considered breaking this edge (during this pass
871 // through the function), then let's go ahead and break it. This means
872 // sinking multiple "cheap" instructions into the same block.
873 if (!CEBCandidates.insert(std::make_pair(From, To)).second)
874 return true;
875
876 if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
877 return true;
878
879 if (From->isSuccessor(To) && MBPI->getEdgeProbability(From, To) <=
881 return true;
882
883 // MI is cheap, we probably don't want to break the critical edge for it.
884 // However, if this would allow some definitions of its source operands
885 // to be sunk then it's probably worth it.
886 for (const MachineOperand &MO : MI.all_uses()) {
887 Register Reg = MO.getReg();
888 if (Reg == 0)
889 continue;
890
891 // We don't move live definitions of physical registers,
892 // so sinking their uses won't enable any opportunities.
893 if (Reg.isPhysical())
894 continue;
895
896 // If this instruction is the only user of a virtual register,
897 // check if breaking the edge will enable sinking
898 // both this instruction and the defining instruction.
899 if (MRI->hasOneNonDBGUse(Reg)) {
900 // If the definition resides in same MBB,
901 // claim it's likely we can sink these together.
902 // If definition resides elsewhere, we aren't
903 // blocking it from being sunk so don't break the edge.
904 MachineInstr *DefMI = MRI->getVRegDef(Reg);
905 if (DefMI->getParent() == MI.getParent())
906 return true;
907 }
908 }
909
910 return false;
911}
912
913bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
914 MachineBasicBlock *FromBB,
915 MachineBasicBlock *ToBB,
916 bool BreakPHIEdge) {
917 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
918 return false;
919
920 // Avoid breaking back edge. From == To means backedge for single BB cycle.
921 if (!SplitEdges || FromBB == ToBB)
922 return false;
923
924 MachineCycle *FromCycle = CI->getCycle(FromBB);
925 MachineCycle *ToCycle = CI->getCycle(ToBB);
926
927 // Check for backedges of more "complex" cycles.
928 if (FromCycle == ToCycle && FromCycle &&
929 (!FromCycle->isReducible() || FromCycle->getHeader() == ToBB))
930 return false;
931
932 // It's not always legal to break critical edges and sink the computation
933 // to the edge.
934 //
935 // %bb.1:
936 // v1024
937 // Beq %bb.3
938 // <fallthrough>
939 // %bb.2:
940 // ... no uses of v1024
941 // <fallthrough>
942 // %bb.3:
943 // ...
944 // = v1024
945 //
946 // If %bb.1 -> %bb.3 edge is broken and computation of v1024 is inserted:
947 //
948 // %bb.1:
949 // ...
950 // Bne %bb.2
951 // %bb.4:
952 // v1024 =
953 // B %bb.3
954 // %bb.2:
955 // ... no uses of v1024
956 // <fallthrough>
957 // %bb.3:
958 // ...
959 // = v1024
960 //
961 // This is incorrect since v1024 is not computed along the %bb.1->%bb.2->%bb.3
962 // flow. We need to ensure the new basic block where the computation is
963 // sunk to dominates all the uses.
964 // It's only legal to break critical edge and sink the computation to the
965 // new block if all the predecessors of "To", except for "From", are
966 // not dominated by "From". Given SSA property, this means these
967 // predecessors are dominated by "To".
968 //
969 // There is no need to do this check if all the uses are PHI nodes. PHI
970 // sources are only defined on the specific predecessor edges.
971 if (!BreakPHIEdge) {
972 for (MachineBasicBlock *Pred : ToBB->predecessors())
973 if (Pred != FromBB && !DT->dominates(ToBB, Pred))
974 return false;
975 }
976
977 ToSplit.insert(std::make_pair(FromBB, ToBB));
978
979 return true;
980}
981
982std::vector<unsigned> &
983MachineSinking::getBBRegisterPressure(const MachineBasicBlock &MBB) {
984 // Currently to save compiling time, MBB's register pressure will not change
985 // in one ProcessBlock iteration because of CachedRegisterPressure. but MBB's
986 // register pressure is changed after sinking any instructions into it.
987 // FIXME: need a accurate and cheap register pressure estiminate model here.
988 auto RP = CachedRegisterPressure.find(&MBB);
989 if (RP != CachedRegisterPressure.end())
990 return RP->second;
991
992 RegionPressure Pressure;
993 RegPressureTracker RPTracker(Pressure);
994
995 // Initialize the register pressure tracker.
996 RPTracker.init(MBB.getParent(), &RegClassInfo, nullptr, &MBB, MBB.end(),
997 /*TrackLaneMasks*/ false, /*TrackUntiedDefs=*/true);
998
1000 MIE = MBB.instr_begin();
1001 MII != MIE; --MII) {
1002 const MachineInstr &MI = *std::prev(MII);
1003 if (MI.isDebugInstr() || MI.isPseudoProbe())
1004 continue;
1005 RegisterOperands RegOpers;
1006 RegOpers.collect(MI, *TRI, *MRI, false, false);
1007 RPTracker.recedeSkipDebugValues();
1008 assert(&*RPTracker.getPos() == &MI && "RPTracker sync error!");
1009 RPTracker.recede(RegOpers);
1010 }
1011
1012 RPTracker.closeRegion();
1013 auto It = CachedRegisterPressure.insert(
1014 std::make_pair(&MBB, RPTracker.getPressure().MaxSetPressure));
1015 return It.first->second;
1016}
1017
1018bool MachineSinking::registerPressureSetExceedsLimit(
1019 unsigned NRegs, const TargetRegisterClass *RC,
1020 const MachineBasicBlock &MBB) {
1021 unsigned Weight = NRegs * TRI->getRegClassWeight(RC).RegWeight;
1022 const int *PS = TRI->getRegClassPressureSets(RC);
1023 std::vector<unsigned> BBRegisterPressure = getBBRegisterPressure(MBB);
1024 for (; *PS != -1; PS++)
1025 if (Weight + BBRegisterPressure[*PS] >=
1026 TRI->getRegPressureSetLimit(*MBB.getParent(), *PS))
1027 return true;
1028 return false;
1029}
1030
1031/// isProfitableToSinkTo - Return true if it is profitable to sink MI.
1032bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
1034 MachineBasicBlock *SuccToSinkTo,
1035 AllSuccsCache &AllSuccessors) {
1036 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
1037
1038 if (MBB == SuccToSinkTo)
1039 return false;
1040
1041 // It is profitable if SuccToSinkTo does not post dominate current block.
1042 if (!PDT->dominates(SuccToSinkTo, MBB))
1043 return true;
1044
1045 // It is profitable to sink an instruction from a deeper cycle to a shallower
1046 // cycle, even if the latter post-dominates the former (PR21115).
1047 if (CI->getCycleDepth(MBB) > CI->getCycleDepth(SuccToSinkTo))
1048 return true;
1049
1050 // Check if only use in post dominated block is PHI instruction.
1051 bool NonPHIUse = false;
1052 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) {
1053 MachineBasicBlock *UseBlock = UseInst.getParent();
1054 if (UseBlock == SuccToSinkTo && !UseInst.isPHI())
1055 NonPHIUse = true;
1056 }
1057 if (!NonPHIUse)
1058 return true;
1059
1060 // If SuccToSinkTo post dominates then also it may be profitable if MI
1061 // can further profitably sinked into another block in next round.
1062 bool BreakPHIEdge = false;
1063 // FIXME - If finding successor is compile time expensive then cache results.
1064 if (MachineBasicBlock *MBB2 =
1065 FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
1066 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
1067
1068 MachineCycle *MCycle = CI->getCycle(MBB);
1069
1070 // If the instruction is not inside a cycle, it is not profitable to sink MI to
1071 // a post dominate block SuccToSinkTo.
1072 if (!MCycle)
1073 return false;
1074
1075 // If this instruction is inside a Cycle and sinking this instruction can make
1076 // more registers live range shorten, it is still prifitable.
1077 for (const MachineOperand &MO : MI.operands()) {
1078 // Ignore non-register operands.
1079 if (!MO.isReg())
1080 continue;
1081 Register Reg = MO.getReg();
1082 if (Reg == 0)
1083 continue;
1084
1085 if (Reg.isPhysical()) {
1086 // Don't handle non-constant and non-ignorable physical register uses.
1087 if (MO.isUse() && !MRI->isConstantPhysReg(Reg) && !TII->isIgnorableUse(MO))
1088 return false;
1089 continue;
1090 }
1091
1092 // Users for the defs are all dominated by SuccToSinkTo.
1093 if (MO.isDef()) {
1094 // This def register's live range is shortened after sinking.
1095 bool LocalUse = false;
1096 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge,
1097 LocalUse))
1098 return false;
1099 } else {
1100 MachineInstr *DefMI = MRI->getVRegDef(Reg);
1101 if (!DefMI)
1102 continue;
1104 // DefMI is defined outside of cycle. There should be no live range
1105 // impact for this operand. Defination outside of cycle means:
1106 // 1: defination is outside of cycle.
1107 // 2: defination is in this cycle, but it is a PHI in the cycle header.
1108 if (Cycle != MCycle || (DefMI->isPHI() && Cycle && Cycle->isReducible() &&
1109 Cycle->getHeader() == DefMI->getParent()))
1110 continue;
1111 // The DefMI is defined inside the cycle.
1112 // If sinking this operand makes some register pressure set exceed limit,
1113 // it is not profitable.
1114 if (registerPressureSetExceedsLimit(1, MRI->getRegClass(Reg),
1115 *SuccToSinkTo)) {
1116 LLVM_DEBUG(dbgs() << "register pressure exceed limit, not profitable.");
1117 return false;
1118 }
1119 }
1120 }
1121
1122 // If MI is in cycle and all its operands are alive across the whole cycle or
1123 // if no operand sinking make register pressure set exceed limit, it is
1124 // profitable to sink MI.
1125 return true;
1126}
1127
1128/// Get the sorted sequence of successors for this MachineBasicBlock, possibly
1129/// computing it if it was not already cached.
1131MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
1132 AllSuccsCache &AllSuccessors) const {
1133 // Do we have the sorted successors in cache ?
1134 auto Succs = AllSuccessors.find(MBB);
1135 if (Succs != AllSuccessors.end())
1136 return Succs->second;
1137
1139
1140 // Handle cases where sinking can happen but where the sink point isn't a
1141 // successor. For example:
1142 //
1143 // x = computation
1144 // if () {} else {}
1145 // use x
1146 //
1147 for (MachineDomTreeNode *DTChild : DT->getNode(MBB)->children()) {
1148 // DomTree children of MBB that have MBB as immediate dominator are added.
1149 if (DTChild->getIDom()->getBlock() == MI.getParent() &&
1150 // Skip MBBs already added to the AllSuccs vector above.
1151 !MBB->isSuccessor(DTChild->getBlock()))
1152 AllSuccs.push_back(DTChild->getBlock());
1153 }
1154
1155 // Sort Successors according to their cycle depth or block frequency info.
1157 AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
1158 uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
1159 uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
1160 bool HasBlockFreq = LHSFreq != 0 || RHSFreq != 0;
1161 return HasBlockFreq ? LHSFreq < RHSFreq
1162 : CI->getCycleDepth(L) < CI->getCycleDepth(R);
1163 });
1164
1165 auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
1166
1167 return it.first->second;
1168}
1169
1170/// FindSuccToSinkTo - Find a successor to sink this instruction to.
1172MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
1173 bool &BreakPHIEdge,
1174 AllSuccsCache &AllSuccessors) {
1175 assert (MBB && "Invalid MachineBasicBlock!");
1176
1177 // loop over all the operands of the specified instruction. If there is
1178 // anything we can't handle, bail out.
1179
1180 // SuccToSinkTo - This is the successor to sink this instruction to, once we
1181 // decide.
1182 MachineBasicBlock *SuccToSinkTo = nullptr;
1183 for (const MachineOperand &MO : MI.operands()) {
1184 if (!MO.isReg()) continue; // Ignore non-register operands.
1185
1186 Register Reg = MO.getReg();
1187 if (Reg == 0) continue;
1188
1189 if (Reg.isPhysical()) {
1190 if (MO.isUse()) {
1191 // If the physreg has no defs anywhere, it's just an ambient register
1192 // and we can freely move its uses. Alternatively, if it's allocatable,
1193 // it could get allocated to something with a def during allocation.
1194 if (!MRI->isConstantPhysReg(Reg) && !TII->isIgnorableUse(MO))
1195 return nullptr;
1196 } else if (!MO.isDead()) {
1197 // A def that isn't dead. We can't move it.
1198 return nullptr;
1199 }
1200 } else {
1201 // Virtual register uses are always safe to sink.
1202 if (MO.isUse()) continue;
1203
1204 // If it's not safe to move defs of the register class, then abort.
1205 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
1206 return nullptr;
1207
1208 // Virtual register defs can only be sunk if all their uses are in blocks
1209 // dominated by one of the successors.
1210 if (SuccToSinkTo) {
1211 // If a previous operand picked a block to sink to, then this operand
1212 // must be sinkable to the same block.
1213 bool LocalUse = false;
1214 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB,
1215 BreakPHIEdge, LocalUse))
1216 return nullptr;
1217
1218 continue;
1219 }
1220
1221 // Otherwise, we should look at all the successors and decide which one
1222 // we should sink to. If we have reliable block frequency information
1223 // (frequency != 0) available, give successors with smaller frequencies
1224 // higher priority, otherwise prioritize smaller cycle depths.
1225 for (MachineBasicBlock *SuccBlock :
1226 GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
1227 bool LocalUse = false;
1228 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
1229 BreakPHIEdge, LocalUse)) {
1230 SuccToSinkTo = SuccBlock;
1231 break;
1232 }
1233 if (LocalUse)
1234 // Def is used locally, it's never safe to move this def.
1235 return nullptr;
1236 }
1237
1238 // If we couldn't find a block to sink to, ignore this instruction.
1239 if (!SuccToSinkTo)
1240 return nullptr;
1241 if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
1242 return nullptr;
1243 }
1244 }
1245
1246 // It is not possible to sink an instruction into its own block. This can
1247 // happen with cycles.
1248 if (MBB == SuccToSinkTo)
1249 return nullptr;
1250
1251 // It's not safe to sink instructions to EH landing pad. Control flow into
1252 // landing pad is implicitly defined.
1253 if (SuccToSinkTo && SuccToSinkTo->isEHPad())
1254 return nullptr;
1255
1256 // It ought to be okay to sink instructions into an INLINEASM_BR target, but
1257 // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in
1258 // the source block (which this code does not yet do). So for now, forbid
1259 // doing so.
1260 if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())
1261 return nullptr;
1262
1263 if (SuccToSinkTo && !TII->isSafeToSink(MI, SuccToSinkTo, CI))
1264 return nullptr;
1265
1266 return SuccToSinkTo;
1267}
1268
1269/// Return true if MI is likely to be usable as a memory operation by the
1270/// implicit null check optimization.
1271///
1272/// This is a "best effort" heuristic, and should not be relied upon for
1273/// correctness. This returning true does not guarantee that the implicit null
1274/// check optimization is legal over MI, and this returning false does not
1275/// guarantee MI cannot possibly be used to do a null check.
1277 const TargetInstrInfo *TII,
1278 const TargetRegisterInfo *TRI) {
1279 using MachineBranchPredicate = TargetInstrInfo::MachineBranchPredicate;
1280
1281 auto *MBB = MI.getParent();
1282 if (MBB->pred_size() != 1)
1283 return false;
1284
1285 auto *PredMBB = *MBB->pred_begin();
1286 auto *PredBB = PredMBB->getBasicBlock();
1287
1288 // Frontends that don't use implicit null checks have no reason to emit
1289 // branches with make.implicit metadata, and this function should always
1290 // return false for them.
1291 if (!PredBB ||
1292 !PredBB->getTerminator()->getMetadata(LLVMContext::MD_make_implicit))
1293 return false;
1294
1295 const MachineOperand *BaseOp;
1296 int64_t Offset;
1297 bool OffsetIsScalable;
1298 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
1299 return false;
1300
1301 if (!BaseOp->isReg())
1302 return false;
1303
1304 if (!(MI.mayLoad() && !MI.isPredicable()))
1305 return false;
1306
1307 MachineBranchPredicate MBP;
1308 if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
1309 return false;
1310
1311 return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
1312 (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
1313 MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
1314 MBP.LHS.getReg() == BaseOp->getReg();
1315}
1316
1317/// If the sunk instruction is a copy, try to forward the copy instead of
1318/// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
1319/// there's any subregister weirdness involved. Returns true if copy
1320/// propagation occurred.
1321static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI,
1322 Register Reg) {
1323 const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
1324 const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
1325
1326 // Copy DBG_VALUE operand and set the original to undef. We then check to
1327 // see whether this is something that can be copy-forwarded. If it isn't,
1328 // continue around the loop.
1329
1330 const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
1331 auto CopyOperands = TII.isCopyInstr(SinkInst);
1332 if (!CopyOperands)
1333 return false;
1334 SrcMO = CopyOperands->Source;
1335 DstMO = CopyOperands->Destination;
1336
1337 // Check validity of forwarding this copy.
1338 bool PostRA = MRI.getNumVirtRegs() == 0;
1339
1340 // Trying to forward between physical and virtual registers is too hard.
1341 if (Reg.isVirtual() != SrcMO->getReg().isVirtual())
1342 return false;
1343
1344 // Only try virtual register copy-forwarding before regalloc, and physical
1345 // register copy-forwarding after regalloc.
1346 bool arePhysRegs = !Reg.isVirtual();
1347 if (arePhysRegs != PostRA)
1348 return false;
1349
1350 // Pre-regalloc, only forward if all subregisters agree (or there are no
1351 // subregs at all). More analysis might recover some forwardable copies.
1352 if (!PostRA)
1353 for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg))
1354 if (DbgMO.getSubReg() != SrcMO->getSubReg() ||
1355 DbgMO.getSubReg() != DstMO->getSubReg())
1356 return false;
1357
1358 // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
1359 // of this copy. Only forward the copy if the DBG_VALUE operand exactly
1360 // matches the copy destination.
1361 if (PostRA && Reg != DstMO->getReg())
1362 return false;
1363
1364 for (auto &DbgMO : DbgMI.getDebugOperandsForReg(Reg)) {
1365 DbgMO.setReg(SrcMO->getReg());
1366 DbgMO.setSubReg(SrcMO->getSubReg());
1367 }
1368 return true;
1369}
1370
1371using MIRegs = std::pair<MachineInstr *, SmallVector<unsigned, 2>>;
1372/// Sink an instruction and its associated debug instructions.
1373static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
1375 ArrayRef<MIRegs> DbgValuesToSink) {
1376 // If we cannot find a location to use (merge with), then we erase the debug
1377 // location to prevent debug-info driven tools from potentially reporting
1378 // wrong location information.
1379 if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
1380 MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
1381 InsertPos->getDebugLoc()));
1382 else
1383 MI.setDebugLoc(DebugLoc());
1384
1385 // Move the instruction.
1386 MachineBasicBlock *ParentBlock = MI.getParent();
1387 SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
1389
1390 // Sink a copy of debug users to the insert position. Mark the original
1391 // DBG_VALUE location as 'undef', indicating that any earlier variable
1392 // location should be terminated as we've optimised away the value at this
1393 // point.
1394 for (const auto &DbgValueToSink : DbgValuesToSink) {
1395 MachineInstr *DbgMI = DbgValueToSink.first;
1396 MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(DbgMI);
1397 SuccToSinkTo.insert(InsertPos, NewDbgMI);
1398
1399 bool PropagatedAllSunkOps = true;
1400 for (unsigned Reg : DbgValueToSink.second) {
1401 if (DbgMI->hasDebugOperandForReg(Reg)) {
1402 if (!attemptDebugCopyProp(MI, *DbgMI, Reg)) {
1403 PropagatedAllSunkOps = false;
1404 break;
1405 }
1406 }
1407 }
1408 if (!PropagatedAllSunkOps)
1409 DbgMI->setDebugValueUndef();
1410 }
1411}
1412
1413/// hasStoreBetween - check if there is store betweeen straight line blocks From
1414/// and To.
1415bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
1417 // Make sure From and To are in straight line which means From dominates To
1418 // and To post dominates From.
1419 if (!DT->dominates(From, To) || !PDT->dominates(To, From))
1420 return true;
1421
1422 auto BlockPair = std::make_pair(From, To);
1423
1424 // Does these two blocks pair be queried before and have a definite cached
1425 // result?
1426 if (auto It = HasStoreCache.find(BlockPair); It != HasStoreCache.end())
1427 return It->second;
1428
1429 if (auto It = StoreInstrCache.find(BlockPair); It != StoreInstrCache.end())
1430 return llvm::any_of(It->second, [&](MachineInstr *I) {
1431 return I->mayAlias(AA, MI, false);
1432 });
1433
1434 bool SawStore = false;
1435 bool HasAliasedStore = false;
1436 DenseSet<MachineBasicBlock *> HandledBlocks;
1437 DenseSet<MachineBasicBlock *> HandledDomBlocks;
1438 // Go through all reachable blocks from From.
1439 for (MachineBasicBlock *BB : depth_first(From)) {
1440 // We insert the instruction at the start of block To, so no need to worry
1441 // about stores inside To.
1442 // Store in block From should be already considered when just enter function
1443 // SinkInstruction.
1444 if (BB == To || BB == From)
1445 continue;
1446
1447 // We already handle this BB in previous iteration.
1448 if (HandledBlocks.count(BB))
1449 continue;
1450
1451 HandledBlocks.insert(BB);
1452 // To post dominates BB, it must be a path from block From.
1453 if (PDT->dominates(To, BB)) {
1454 if (!HandledDomBlocks.count(BB))
1455 HandledDomBlocks.insert(BB);
1456
1457 // If this BB is too big or the block number in straight line between From
1458 // and To is too big, stop searching to save compiling time.
1459 if (BB->sizeWithoutDebugLargerThan(SinkLoadInstsPerBlockThreshold) ||
1460 HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
1461 for (auto *DomBB : HandledDomBlocks) {
1462 if (DomBB != BB && DT->dominates(DomBB, BB))
1463 HasStoreCache[std::make_pair(DomBB, To)] = true;
1464 else if(DomBB != BB && DT->dominates(BB, DomBB))
1465 HasStoreCache[std::make_pair(From, DomBB)] = true;
1466 }
1467 HasStoreCache[BlockPair] = true;
1468 return true;
1469 }
1470
1471 for (MachineInstr &I : *BB) {
1472 // Treat as alias conservatively for a call or an ordered memory
1473 // operation.
1474 if (I.isCall() || I.hasOrderedMemoryRef()) {
1475 for (auto *DomBB : HandledDomBlocks) {
1476 if (DomBB != BB && DT->dominates(DomBB, BB))
1477 HasStoreCache[std::make_pair(DomBB, To)] = true;
1478 else if(DomBB != BB && DT->dominates(BB, DomBB))
1479 HasStoreCache[std::make_pair(From, DomBB)] = true;
1480 }
1481 HasStoreCache[BlockPair] = true;
1482 return true;
1483 }
1484
1485 if (I.mayStore()) {
1486 SawStore = true;
1487 // We still have chance to sink MI if all stores between are not
1488 // aliased to MI.
1489 // Cache all store instructions, so that we don't need to go through
1490 // all From reachable blocks for next load instruction.
1491 if (I.mayAlias(AA, MI, false))
1492 HasAliasedStore = true;
1493 StoreInstrCache[BlockPair].push_back(&I);
1494 }
1495 }
1496 }
1497 }
1498 // If there is no store at all, cache the result.
1499 if (!SawStore)
1500 HasStoreCache[BlockPair] = false;
1501 return HasAliasedStore;
1502}
1503
1504/// Sink instructions into cycles if profitable. This especially tries to
1505/// prevent register spills caused by register pressure if there is little to no
1506/// overhead moving instructions into cycles.
1507bool MachineSinking::SinkIntoCycle(MachineCycle *Cycle, MachineInstr &I) {
1508 LLVM_DEBUG(dbgs() << "CycleSink: Finding sink block for: " << I);
1510 assert(Preheader && "Cycle sink needs a preheader block");
1511 MachineBasicBlock *SinkBlock = nullptr;
1512 bool CanSink = true;
1513 const MachineOperand &MO = I.getOperand(0);
1514
1515 for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
1516 LLVM_DEBUG(dbgs() << "CycleSink: Analysing use: " << MI);
1517 if (!Cycle->contains(MI.getParent())) {
1518 LLVM_DEBUG(dbgs() << "CycleSink: Use not in cycle, can't sink.\n");
1519 CanSink = false;
1520 break;
1521 }
1522
1523 // FIXME: Come up with a proper cost model that estimates whether sinking
1524 // the instruction (and thus possibly executing it on every cycle
1525 // iteration) is more expensive than a register.
1526 // For now assumes that copies are cheap and thus almost always worth it.
1527 if (!MI.isCopy()) {
1528 LLVM_DEBUG(dbgs() << "CycleSink: Use is not a copy\n");
1529 CanSink = false;
1530 break;
1531 }
1532 if (!SinkBlock) {
1533 SinkBlock = MI.getParent();
1534 LLVM_DEBUG(dbgs() << "CycleSink: Setting sink block to: "
1535 << printMBBReference(*SinkBlock) << "\n");
1536 continue;
1537 }
1538 SinkBlock = DT->findNearestCommonDominator(SinkBlock, MI.getParent());
1539 if (!SinkBlock) {
1540 LLVM_DEBUG(dbgs() << "CycleSink: Can't find nearest dominator\n");
1541 CanSink = false;
1542 break;
1543 }
1544 LLVM_DEBUG(dbgs() << "CycleSink: Setting nearest common dom block: " <<
1545 printMBBReference(*SinkBlock) << "\n");
1546 }
1547
1548 if (!CanSink) {
1549 LLVM_DEBUG(dbgs() << "CycleSink: Can't sink instruction.\n");
1550 return false;
1551 }
1552 if (!SinkBlock) {
1553 LLVM_DEBUG(dbgs() << "CycleSink: Not sinking, can't find sink block.\n");
1554 return false;
1555 }
1556 if (SinkBlock == Preheader) {
1557 LLVM_DEBUG(
1558 dbgs() << "CycleSink: Not sinking, sink block is the preheader\n");
1559 return false;
1560 }
1562 LLVM_DEBUG(
1563 dbgs() << "CycleSink: Not Sinking, block too large to analyse.\n");
1564 return false;
1565 }
1566
1567 LLVM_DEBUG(dbgs() << "CycleSink: Sinking instruction!\n");
1568 SinkBlock->splice(SinkBlock->SkipPHIsAndLabels(SinkBlock->begin()), Preheader,
1569 I);
1570
1571 // Conservatively clear any kill flags on uses of sunk instruction
1572 for (MachineOperand &MO : I.operands()) {
1573 if (MO.isReg() && MO.readsReg())
1574 RegsToClearKillFlags.insert(MO.getReg());
1575 }
1576
1577 // The instruction is moved from its basic block, so do not retain the
1578 // debug information.
1579 assert(!I.isDebugInstr() && "Should not sink debug inst");
1580 I.setDebugLoc(DebugLoc());
1581 return true;
1582}
1583
1584/// SinkInstruction - Determine whether it is safe to sink the specified machine
1585/// instruction out of its current block into a successor.
1586bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
1587 AllSuccsCache &AllSuccessors) {
1588 // Don't sink instructions that the target prefers not to sink.
1589 if (!TII->shouldSink(MI))
1590 return false;
1591
1592 // Check if it's safe to move the instruction.
1593 if (!MI.isSafeToMove(AA, SawStore))
1594 return false;
1595
1596 // Convergent operations may not be made control-dependent on additional
1597 // values.
1598 if (MI.isConvergent())
1599 return false;
1600
1601 // Don't break implicit null checks. This is a performance heuristic, and not
1602 // required for correctness.
1604 return false;
1605
1606 // FIXME: This should include support for sinking instructions within the
1607 // block they are currently in to shorten the live ranges. We often get
1608 // instructions sunk into the top of a large block, but it would be better to
1609 // also sink them down before their first use in the block. This xform has to
1610 // be careful not to *increase* register pressure though, e.g. sinking
1611 // "x = y + z" down if it kills y and z would increase the live ranges of y
1612 // and z and only shrink the live range of x.
1613
1614 bool BreakPHIEdge = false;
1615 MachineBasicBlock *ParentBlock = MI.getParent();
1616 MachineBasicBlock *SuccToSinkTo =
1617 FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
1618
1619 // If there are no outputs, it must have side-effects.
1620 if (!SuccToSinkTo)
1621 return false;
1622
1623 // If the instruction to move defines a dead physical register which is live
1624 // when leaving the basic block, don't move it because it could turn into a
1625 // "zombie" define of that preg. E.g., EFLAGS.
1626 for (const MachineOperand &MO : MI.all_defs()) {
1627 Register Reg = MO.getReg();
1628 if (Reg == 0 || !Reg.isPhysical())
1629 continue;
1630 if (SuccToSinkTo->isLiveIn(Reg))
1631 return false;
1632 }
1633
1634 LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccToSinkTo);
1635
1636 // If the block has multiple predecessors, this is a critical edge.
1637 // Decide if we can sink along it or need to break the edge.
1638 if (SuccToSinkTo->pred_size() > 1) {
1639 // We cannot sink a load across a critical edge - there may be stores in
1640 // other code paths.
1641 bool TryBreak = false;
1642 bool Store =
1643 MI.mayLoad() ? hasStoreBetween(ParentBlock, SuccToSinkTo, MI) : true;
1644 if (!MI.isSafeToMove(AA, Store)) {
1645 LLVM_DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
1646 TryBreak = true;
1647 }
1648
1649 // We don't want to sink across a critical edge if we don't dominate the
1650 // successor. We could be introducing calculations to new code paths.
1651 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
1652 LLVM_DEBUG(dbgs() << " *** NOTE: Critical edge found\n");
1653 TryBreak = true;
1654 }
1655
1656 // Don't sink instructions into a cycle.
1657 if (!TryBreak && CI->getCycle(SuccToSinkTo) &&
1658 (!CI->getCycle(SuccToSinkTo)->isReducible() ||
1659 CI->getCycle(SuccToSinkTo)->getHeader() == SuccToSinkTo)) {
1660 LLVM_DEBUG(dbgs() << " *** NOTE: cycle header found\n");
1661 TryBreak = true;
1662 }
1663
1664 // Otherwise we are OK with sinking along a critical edge.
1665 if (!TryBreak)
1666 LLVM_DEBUG(dbgs() << "Sinking along critical edge.\n");
1667 else {
1668 // Mark this edge as to be split.
1669 // If the edge can actually be split, the next iteration of the main loop
1670 // will sink MI in the newly created block.
1671 bool Status =
1672 PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
1673 if (!Status)
1674 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1675 "break critical edge\n");
1676 // The instruction will not be sunk this time.
1677 return false;
1678 }
1679 }
1680
1681 if (BreakPHIEdge) {
1682 // BreakPHIEdge is true if all the uses are in the successor MBB being
1683 // sunken into and they are all PHI nodes. In this case, machine-sink must
1684 // break the critical edge first.
1685 bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
1686 SuccToSinkTo, BreakPHIEdge);
1687 if (!Status)
1688 LLVM_DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
1689 "break critical edge\n");
1690 // The instruction will not be sunk this time.
1691 return false;
1692 }
1693
1694 // Determine where to insert into. Skip phi nodes.
1695 MachineBasicBlock::iterator InsertPos =
1696 SuccToSinkTo->SkipPHIsAndLabels(SuccToSinkTo->begin());
1697 if (blockPrologueInterferes(SuccToSinkTo, InsertPos, MI, TRI, TII, MRI)) {
1698 LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
1699 return false;
1700 }
1701
1702 // Collect debug users of any vreg that this inst defines.
1703 SmallVector<MIRegs, 4> DbgUsersToSink;
1704 for (auto &MO : MI.all_defs()) {
1705 if (!MO.getReg().isVirtual())
1706 continue;
1707 if (!SeenDbgUsers.count(MO.getReg()))
1708 continue;
1709
1710 // Sink any users that don't pass any other DBG_VALUEs for this variable.
1711 auto &Users = SeenDbgUsers[MO.getReg()];
1712 for (auto &User : Users) {
1713 MachineInstr *DbgMI = User.getPointer();
1714 if (User.getInt()) {
1715 // This DBG_VALUE would re-order assignments. If we can't copy-propagate
1716 // it, it can't be recovered. Set it undef.
1717 if (!attemptDebugCopyProp(MI, *DbgMI, MO.getReg()))
1718 DbgMI->setDebugValueUndef();
1719 } else {
1720 DbgUsersToSink.push_back(
1721 {DbgMI, SmallVector<unsigned, 2>(1, MO.getReg())});
1722 }
1723 }
1724 }
1725
1726 // After sinking, some debug users may not be dominated any more. If possible,
1727 // copy-propagate their operands. As it's expensive, don't do this if there's
1728 // no debuginfo in the program.
1729 if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
1730 SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);
1731
1732 performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);
1733
1734 // Conservatively, clear any kill flags, since it's possible that they are no
1735 // longer correct.
1736 // Note that we have to clear the kill flags for any register this instruction
1737 // uses as we may sink over another instruction which currently kills the
1738 // used registers.
1739 for (MachineOperand &MO : MI.all_uses())
1740 RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.
1741
1742 return true;
1743}
1744
1745void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
1746 MachineInstr &MI, MachineBasicBlock *TargetBlock) {
1747 assert(MI.isCopy());
1748 assert(MI.getOperand(1).isReg());
1749
1750 // Enumerate all users of vreg operands that are def'd. Skip those that will
1751 // be sunk. For the rest, if they are not dominated by the block we will sink
1752 // MI into, propagate the copy source to them.
1754 SmallVector<Register, 4> DbgUseRegs;
1755 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
1756 for (auto &MO : MI.all_defs()) {
1757 if (!MO.getReg().isVirtual())
1758 continue;
1759 DbgUseRegs.push_back(MO.getReg());
1760 for (auto &User : MRI.use_instructions(MO.getReg())) {
1761 if (!User.isDebugValue() || DT->dominates(TargetBlock, User.getParent()))
1762 continue;
1763
1764 // If is in same block, will either sink or be use-before-def.
1765 if (User.getParent() == MI.getParent())
1766 continue;
1767
1768 assert(User.hasDebugOperandForReg(MO.getReg()) &&
1769 "DBG_VALUE user of vreg, but has no operand for it?");
1770 DbgDefUsers.push_back(&User);
1771 }
1772 }
1773
1774 // Point the users of this copy that are no longer dominated, at the source
1775 // of the copy.
1776 for (auto *User : DbgDefUsers) {
1777 for (auto &Reg : DbgUseRegs) {
1778 for (auto &DbgOp : User->getDebugOperandsForReg(Reg)) {
1779 DbgOp.setReg(MI.getOperand(1).getReg());
1780 DbgOp.setSubReg(MI.getOperand(1).getSubReg());
1781 }
1782 }
1783 }
1784}
1785
1786//===----------------------------------------------------------------------===//
1787// This pass is not intended to be a replacement or a complete alternative
1788// for the pre-ra machine sink pass. It is only designed to sink COPY
1789// instructions which should be handled after RA.
1790//
1791// This pass sinks COPY instructions into a successor block, if the COPY is not
1792// used in the current block and the COPY is live-in to a single successor
1793// (i.e., doesn't require the COPY to be duplicated). This avoids executing the
1794// copy on paths where their results aren't needed. This also exposes
1795// additional opportunites for dead copy elimination and shrink wrapping.
1796//
1797// These copies were either not handled by or are inserted after the MachineSink
1798// pass. As an example of the former case, the MachineSink pass cannot sink
1799// COPY instructions with allocatable source registers; for AArch64 these type
1800// of copy instructions are frequently used to move function parameters (PhyReg)
1801// into virtual registers in the entry block.
1802//
1803// For the machine IR below, this pass will sink %w19 in the entry into its
1804// successor (%bb.1) because %w19 is only live-in in %bb.1.
1805// %bb.0:
1806// %wzr = SUBSWri %w1, 1
1807// %w19 = COPY %w0
1808// Bcc 11, %bb.2
1809// %bb.1:
1810// Live Ins: %w19
1811// BL @fun
1812// %w0 = ADDWrr %w0, %w19
1813// RET %w0
1814// %bb.2:
1815// %w0 = COPY %wzr
1816// RET %w0
1817// As we sink %w19 (CSR in AArch64) into %bb.1, the shrink-wrapping pass will be
1818// able to see %bb.0 as a candidate.
1819//===----------------------------------------------------------------------===//
1820namespace {
1821
1822class PostRAMachineSinking : public MachineFunctionPass {
1823public:
1824 bool runOnMachineFunction(MachineFunction &MF) override;
1825
1826 static char ID;
1827 PostRAMachineSinking() : MachineFunctionPass(ID) {}
1828 StringRef getPassName() const override { return "PostRA Machine Sink"; }
1829
1830 void getAnalysisUsage(AnalysisUsage &AU) const override {
1831 AU.setPreservesCFG();
1833 }
1834
1837 MachineFunctionProperties::Property::NoVRegs);
1838 }
1839
1840private:
1841 /// Track which register units have been modified and used.
1842 LiveRegUnits ModifiedRegUnits, UsedRegUnits;
1843
1844 /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
1845 /// entry in this map for each unit it touches. The DBG_VALUE's entry
1846 /// consists of a pointer to the instruction itself, and a vector of registers
1847 /// referred to by the instruction that overlap the key register unit.
1849
1850 /// Sink Copy instructions unused in the same block close to their uses in
1851 /// successors.
1852 bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
1853 const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
1854};
1855} // namespace
1856
1857char PostRAMachineSinking::ID = 0;
1858char &llvm::PostRAMachineSinkingID = PostRAMachineSinking::ID;
1859
1860INITIALIZE_PASS(PostRAMachineSinking, "postra-machine-sink",
1861 "PostRA Machine Sink", false, false)
1862
1863static bool aliasWithRegsInLiveIn(MachineBasicBlock &MBB, unsigned Reg,
1865 LiveRegUnits LiveInRegUnits(*TRI);
1866 LiveInRegUnits.addLiveIns(MBB);
1867 return !LiveInRegUnits.available(Reg);
1868}
1869
1870static MachineBasicBlock *
1872 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1873 unsigned Reg, const TargetRegisterInfo *TRI) {
1874 // Try to find a single sinkable successor in which Reg is live-in.
1875 MachineBasicBlock *BB = nullptr;
1876 for (auto *SI : SinkableBBs) {
1877 if (aliasWithRegsInLiveIn(*SI, Reg, TRI)) {
1878 // If BB is set here, Reg is live-in to at least two sinkable successors,
1879 // so quit.
1880 if (BB)
1881 return nullptr;
1882 BB = SI;
1883 }
1884 }
1885 // Reg is not live-in to any sinkable successors.
1886 if (!BB)
1887 return nullptr;
1888
1889 // Check if any register aliased with Reg is live-in in other successors.
1890 for (auto *SI : CurBB.successors()) {
1891 if (!SinkableBBs.count(SI) && aliasWithRegsInLiveIn(*SI, Reg, TRI))
1892 return nullptr;
1893 }
1894 return BB;
1895}
1896
1897static MachineBasicBlock *
1899 const SmallPtrSetImpl<MachineBasicBlock *> &SinkableBBs,
1900 ArrayRef<unsigned> DefedRegsInCopy,
1901 const TargetRegisterInfo *TRI) {
1902 MachineBasicBlock *SingleBB = nullptr;
1903 for (auto DefReg : DefedRegsInCopy) {
1904 MachineBasicBlock *BB =
1905 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefReg, TRI);
1906 if (!BB || (SingleBB && SingleBB != BB))
1907 return nullptr;
1908 SingleBB = BB;
1909 }
1910 return SingleBB;
1911}
1912
1914 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1915 LiveRegUnits &UsedRegUnits,
1916 const TargetRegisterInfo *TRI) {
1917 for (auto U : UsedOpsInCopy) {
1918 MachineOperand &MO = MI->getOperand(U);
1919 Register SrcReg = MO.getReg();
1920 if (!UsedRegUnits.available(SrcReg)) {
1921 MachineBasicBlock::iterator NI = std::next(MI->getIterator());
1922 for (MachineInstr &UI : make_range(NI, CurBB.end())) {
1923 if (UI.killsRegister(SrcReg, TRI)) {
1924 UI.clearRegisterKills(SrcReg, TRI);
1925 MO.setIsKill(true);
1926 break;
1927 }
1928 }
1929 }
1930 }
1931}
1932
1934 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1935 SmallVectorImpl<unsigned> &DefedRegsInCopy) {
1936 MachineFunction &MF = *SuccBB->getParent();
1938 for (unsigned DefReg : DefedRegsInCopy)
1939 for (MCPhysReg S : TRI->subregs_inclusive(DefReg))
1940 SuccBB->removeLiveIn(S);
1941 for (auto U : UsedOpsInCopy) {
1942 Register SrcReg = MI->getOperand(U).getReg();
1943 LaneBitmask Mask;
1944 for (MCRegUnitMaskIterator S(SrcReg, TRI); S.isValid(); ++S)
1945 Mask |= (*S).second;
1946 SuccBB->addLiveIn(SrcReg, Mask);
1947 }
1948 SuccBB->sortUniqueLiveIns();
1949}
1950
1952 SmallVectorImpl<unsigned> &UsedOpsInCopy,
1953 SmallVectorImpl<unsigned> &DefedRegsInCopy,
1954 LiveRegUnits &ModifiedRegUnits,
1955 LiveRegUnits &UsedRegUnits) {
1956 bool HasRegDependency = false;
1957 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1958 MachineOperand &MO = MI->getOperand(i);
1959 if (!MO.isReg())
1960 continue;
1961 Register Reg = MO.getReg();
1962 if (!Reg)
1963 continue;
1964 if (MO.isDef()) {
1965 if (!ModifiedRegUnits.available(Reg) || !UsedRegUnits.available(Reg)) {
1966 HasRegDependency = true;
1967 break;
1968 }
1969 DefedRegsInCopy.push_back(Reg);
1970
1971 // FIXME: instead of isUse(), readsReg() would be a better fix here,
1972 // For example, we can ignore modifications in reg with undef. However,
1973 // it's not perfectly clear if skipping the internal read is safe in all
1974 // other targets.
1975 } else if (MO.isUse()) {
1976 if (!ModifiedRegUnits.available(Reg)) {
1977 HasRegDependency = true;
1978 break;
1979 }
1980 UsedOpsInCopy.push_back(i);
1981 }
1982 }
1983 return HasRegDependency;
1984}
1985
1986bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
1987 MachineFunction &MF,
1988 const TargetRegisterInfo *TRI,
1989 const TargetInstrInfo *TII) {
1991 // FIXME: For now, we sink only to a successor which has a single predecessor
1992 // so that we can directly sink COPY instructions to the successor without
1993 // adding any new block or branch instruction.
1994 for (MachineBasicBlock *SI : CurBB.successors())
1995 if (!SI->livein_empty() && SI->pred_size() == 1)
1996 SinkableBBs.insert(SI);
1997
1998 if (SinkableBBs.empty())
1999 return false;
2000
2001 bool Changed = false;
2002
2003 // Track which registers have been modified and used between the end of the
2004 // block and the current instruction.
2005 ModifiedRegUnits.clear();
2006 UsedRegUnits.clear();
2007 SeenDbgInstrs.clear();
2008
2010 // Track the operand index for use in Copy.
2011 SmallVector<unsigned, 2> UsedOpsInCopy;
2012 // Track the register number defed in Copy.
2013 SmallVector<unsigned, 2> DefedRegsInCopy;
2014
2015 // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
2016 // for DBG_VALUEs later, record them when they're encountered.
2017 if (MI.isDebugValue() && !MI.isDebugRef()) {
2019 bool IsValid = true;
2020 for (MachineOperand &MO : MI.debug_operands()) {
2021 if (MO.isReg() && MO.getReg().isPhysical()) {
2022 // Bail if we can already tell the sink would be rejected, rather
2023 // than needlessly accumulating lots of DBG_VALUEs.
2024 if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,
2025 ModifiedRegUnits, UsedRegUnits)) {
2026 IsValid = false;
2027 break;
2028 }
2029
2030 // Record debug use of each reg unit.
2031 for (MCRegUnit Unit : TRI->regunits(MO.getReg()))
2032 MIUnits[Unit].push_back(MO.getReg());
2033 }
2034 }
2035 if (IsValid) {
2036 for (auto &RegOps : MIUnits)
2037 SeenDbgInstrs[RegOps.first].emplace_back(&MI,
2038 std::move(RegOps.second));
2039 }
2040 continue;
2041 }
2042
2043 if (MI.isDebugOrPseudoInstr())
2044 continue;
2045
2046 // Do not move any instruction across function call.
2047 if (MI.isCall())
2048 return false;
2049
2050 if (!MI.isCopy() || !MI.getOperand(0).isRenamable()) {
2051 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2052 TRI);
2053 continue;
2054 }
2055
2056 // Don't sink the COPY if it would violate a register dependency.
2057 if (hasRegisterDependency(&MI, UsedOpsInCopy, DefedRegsInCopy,
2058 ModifiedRegUnits, UsedRegUnits)) {
2059 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2060 TRI);
2061 continue;
2062 }
2063 assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
2064 "Unexpect SrcReg or DefReg");
2065 MachineBasicBlock *SuccBB =
2066 getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
2067 // Don't sink if we cannot find a single sinkable successor in which Reg
2068 // is live-in.
2069 if (!SuccBB) {
2070 LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
2071 TRI);
2072 continue;
2073 }
2074 assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
2075 "Unexpected predecessor");
2076
2077 // Collect DBG_VALUEs that must sink with this copy. We've previously
2078 // recorded which reg units that DBG_VALUEs read, if this instruction
2079 // writes any of those units then the corresponding DBG_VALUEs must sink.
2081 for (auto &MO : MI.all_defs()) {
2082 for (MCRegUnit Unit : TRI->regunits(MO.getReg())) {
2083 for (const auto &MIRegs : SeenDbgInstrs.lookup(Unit)) {
2084 auto &Regs = DbgValsToSinkMap[MIRegs.first];
2085 for (unsigned Reg : MIRegs.second)
2086 Regs.push_back(Reg);
2087 }
2088 }
2089 }
2090 auto DbgValsToSink = DbgValsToSinkMap.takeVector();
2091
2092 LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccBB);
2093
2094 MachineBasicBlock::iterator InsertPos =
2095 SuccBB->SkipPHIsAndLabels(SuccBB->begin());
2096 if (blockPrologueInterferes(SuccBB, InsertPos, MI, TRI, TII, nullptr)) {
2097 LLVM_DEBUG(
2098 dbgs() << " *** Not sinking: prologue interference\n");
2099 continue;
2100 }
2101
2102 // Clear the kill flag if SrcReg is killed between MI and the end of the
2103 // block.
2104 clearKillFlags(&MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
2105 performSink(MI, *SuccBB, InsertPos, DbgValsToSink);
2106 updateLiveIn(&MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
2107
2108 Changed = true;
2109 ++NumPostRACopySink;
2110 }
2111 return Changed;
2112}
2113
2114bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
2115 if (skipFunction(MF.getFunction()))
2116 return false;
2117
2118 bool Changed = false;
2121
2122 ModifiedRegUnits.init(*TRI);
2123 UsedRegUnits.init(*TRI);
2124 for (auto &BB : MF)
2125 Changed |= tryToSinkCopy(BB, MF, TRI, TII);
2126
2127 return Changed;
2128}
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder MachineInstrBuilder & DefMI
aarch64 promote const
MachineBasicBlock & MBB
basic Basic Alias true
BlockVerifier::State From
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
bool End
Definition: ELF_riscv.cpp:478
static const HTTPClientCleanup Cleanup
Definition: HTTPClient.cpp:42
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
iv Induction Variable Users
Definition: IVUsers.cpp:48
#define I(x, y, z)
Definition: MD5.cpp:58
static cl::opt< unsigned > SinkLoadInstsPerBlockThreshold("machine-sink-load-instrs-threshold", cl::desc("Do not try to find alias store for a load if there is a in-path " "block whose instruction number is higher than this threshold."), cl::init(2000), cl::Hidden)
static void clearKillFlags(MachineInstr *MI, MachineBasicBlock &CurBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI)
unsigned const TargetRegisterInfo * TRI
static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo, MachineBasicBlock::iterator InsertPos, ArrayRef< MIRegs > DbgValuesToSink)
Sink an instruction and its associated debug instructions.
static cl::opt< bool > SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), cl::init(true), cl::Hidden)
static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI)
Return true if this machine instruction loads from global offset table or constant pool.
static bool SinkingPreventsImplicitNullCheck(MachineInstr &MI, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
Return true if MI is likely to be usable as a memory operation by the implicit null check optimizatio...
static cl::opt< bool > SinkInstsIntoCycle("sink-insts-to-avoid-spills", cl::desc("Sink instructions into cycles to avoid " "register spills"), cl::init(false), cl::Hidden)
static cl::opt< unsigned > SinkLoadBlocksThreshold("machine-sink-load-blocks-threshold", cl::desc("Do not try to find alias store for a load if the block number in " "the straight line is higher than this threshold."), cl::init(20), cl::Hidden)
unsigned Reg
Machine code sinking
static bool hasRegisterDependency(MachineInstr *MI, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits)
static void updateLiveIn(MachineInstr *MI, MachineBasicBlock *SuccBB, SmallVectorImpl< unsigned > &UsedOpsInCopy, SmallVectorImpl< unsigned > &DefedRegsInCopy)
Machine code static false bool blockPrologueInterferes(const MachineBasicBlock *BB, MachineBasicBlock::const_iterator End, const MachineInstr &MI, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, const MachineRegisterInfo *MRI)
Return true if a target defined block prologue instruction interferes with a sink candidate.
static cl::opt< unsigned > SplitEdgeProbabilityThreshold("machine-sink-split-probability-threshold", cl::desc("Percentage threshold for splitting single-instruction critical edge. " "If the branch threshold is higher than this threshold, we allow " "speculative execution of up to 1 instruction to avoid branching to " "splitted critical edge"), cl::init(40), cl::Hidden)
static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI, Register Reg)
If the sunk instruction is a copy, try to forward the copy instead of leaving an 'undef' DBG_VALUE in...
static MachineBasicBlock * getSingleLiveInSuccBB(MachineBasicBlock &CurBB, const SmallPtrSetImpl< MachineBasicBlock * > &SinkableBBs, unsigned Reg, const TargetRegisterInfo *TRI)
static cl::opt< unsigned > SinkIntoCycleLimit("machine-sink-cycle-limit", cl::desc("The maximum number of instructions considered for cycle sinking."), cl::init(50), cl::Hidden)
#define DEBUG_TYPE
Definition: MachineSink.cpp:65
static cl::opt< bool > UseBlockFreqInfo("machine-sink-bfi", cl::desc("Use block frequency info to find successors to sink"), cl::init(true), cl::Hidden)
std::pair< MachineInstr *, SmallVector< unsigned, 2 > > MIRegs
This file implements a map that provides insertion order iteration.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This file defines the PointerIntPair class.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:175
static bool SinkInstruction(Instruction *Inst, SmallPtrSetImpl< Instruction * > &Stores, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
SinkInstruction - Determine whether it is safe to sink the specified machine instruction out of its c...
Definition: Sink.cpp:102
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Target-Independent Code Generator Pass Configuration Options pass.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
A debug info location.
Definition: DebugLoc.h:33
Identifies a unique instance of a variable.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Base class for the actual dominator tree node.
iterator_range< iterator > children()
const_toplevel_iterator toplevel_end() const
void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New)
unsigned getCycleDepth(const BlockT *Block) const
get the depth for the cycle which containing a given block.
const_toplevel_iterator toplevel_begin() const
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
A possibly irreducible generalization of a Loop.
BlockT * getHeader() const
bool isReducible() const
Whether the cycle is a natural loop.
BlockT * getCyclePreheader() const
Return the preheader block for this cycle.
bool contains(const BlockT *Block) const
Return whether Block is contained in the cycle.
bool isAsCheapAsAMove(const MachineInstr &MI) const override
bool shouldSink(const MachineInstr &MI) const override
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
static void accumulateUsedDefed(const MachineInstr &MI, LiveRegUnits &ModifiedRegUnits, LiveRegUnits &UsedRegUnits, const TargetRegisterInfo *TRI)
For a machine instruction MI, adds all register units used in UsedRegUnits and defined or clobbered i...
Definition: LiveRegUnits.h:47
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:116
void addLiveIns(const MachineBasicBlock &MBB)
Adds registers living into block MBB.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
instr_iterator instr_begin()
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
unsigned succ_size() const
void sortUniqueLiveIns()
Sorts and uniques the LiveIns vector.
instr_iterator instr_end()
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
bool sizeWithoutDebugLargerThan(unsigned Limit) const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
void onEdgeSplit(const MachineBasicBlock &NewPredecessor, const MachineBasicBlock &NewSuccessor, const MachineBranchProbabilityInfo &MBPI)
incrementally calculate block frequencies when we split edges, to avoid full CFG traversal.
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Legacy analysis pass which computes a MachineCycleInfo.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
bool isReachableFromEntry(const MachineBasicBlock *A)
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Representation of each machine instruction.
Definition: MachineInstr.h:68
static iterator_range< filter_iterator< Operand *, std::function< bool(Operand &Op)> > > getDebugOperandsForReg(Instruction *MI, Register Reg)
Returns a range of all of the operands that correspond to a debug use of Reg.
Definition: MachineInstr.h:584
bool hasDebugOperandForReg(Register Reg) const
Returns whether this debug value has at least one debug operand with the register Reg.
Definition: MachineInstr.h:573
void setDebugValueUndef()
Sets all register debug operands in this debug value instruction to be undef.
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
bool isCopy() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:326
bool isCopyLike() const
Return true if the instruction behaves like a copy.
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:553
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
void setIsKill(bool Val=true)
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Register getReg() const
getReg - Returns the register number.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
VectorType takeVector()
Clear the MapVector and return the underlying vector.
Definition: MapVector.h:55
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void dump() const
Definition: Pass.cpp:136
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
virtual void releaseMemory()
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: Pass.cpp:102
PointerIntPair - This class implements a pair of a pointer and small integer.
Special value supplied for machine level alias analysis.
Track the current register pressure at some position in the instruction stream, and remember the high...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
List of registers defined and used by a machine instruction.
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:95
A vector that has set insertion semantics.
Definition: SetVector.h:57
void clear()
Completely clear the SetVector.
Definition: SetVector.h:273
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
void clear()
Definition: SmallSet.h:218
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
Target-Independent Code Generator Pass Configuration Options.
bool getEnableSinkAndFold() const
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
bool hasSuperClassEq(const TargetRegisterClass *RC) const
Returns true if RC is a super-class of or equal to this class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type size() const
Definition: DenseSet.h:81
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
void stable_sort(R &&Range)
Definition: STLExtras.h:1970
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1726
bool isCycleInvariant(const MachineCycle *Cycle, MachineInstr &I)
char & MachineSinkingID
MachineSinking - This pass performs sinking on machine instructions.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1733
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
char & PostRAMachineSinkingID
This pass perform post-ra machine sink for COPY instructions.
void initializeMachineSinkingPass(PassRegistry &)
iterator_range< df_iterator< T > > depth_first(const T &G)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
TODO: Might pack better if we changed this to a Struct of Arrays, since MachineOperand is width 32,...
Used to describe addressing mode similar to ExtAddrMode in CodeGenPrepare.
RegisterPressure computed within a region of instructions delimited by TopPos and BottomPos.
Represents a predicate at the MachineFunction level.