78#define DEBUG_TYPE "machine-cp"
80STATISTIC(NumDeletes,
"Number of dead copies deleted");
81STATISTIC(NumCopyForwards,
"Number of copy uses forwarded");
82STATISTIC(NumCopyBackwardPropagated,
"Number of copy defs backward propagated");
84 "Controls which register COPYs are forwarded");
91static std::optional<DestSourcePair> isCopyInstr(
const MachineInstr &
MI,
95 return TII.isCopyInstr(
MI);
98 return std::optional<DestSourcePair>(
121 auto CI =
Copies.find(*RUI);
123 CI->second.Avail =
false;
135 RegsToInvalidate.
insert(Reg);
140 std::optional<DestSourcePair> CopyOperands =
141 isCopyInstr(*
MI,
TII, UseCopyInstr);
142 assert(CopyOperands &&
"Expect copy");
145 CopyOperands->Destination->getReg().asMCReg());
146 RegsToInvalidate.
insert(CopyOperands->Source->getReg().asMCReg());
148 RegsToInvalidate.
insert(
I->second.DefRegs.begin(),
149 I->second.DefRegs.end());
152 for (
MCRegister InvalidReg : RegsToInvalidate)
165 markRegsUnavailable(
I->second.DefRegs,
TRI);
169 std::optional<DestSourcePair> CopyOperands =
170 isCopyInstr(*
MI,
TII, UseCopyInstr);
171 markRegsUnavailable({CopyOperands->Destination->getReg().asMCReg()},
183 std::optional<DestSourcePair> CopyOperands =
184 isCopyInstr(*
MI,
TII, UseCopyInstr);
185 assert(CopyOperands &&
"Tracking non-copy?");
187 MCRegister Src = CopyOperands->Source->getReg().asMCReg();
188 MCRegister Def = CopyOperands->Destination->getReg().asMCReg();
192 Copies[*RUI] = {
MI, {},
true};
197 auto I =
Copies.insert({*RUI, {
nullptr, {},
false}});
198 auto &
Copy =
I.first->second;
200 Copy.DefRegs.push_back(Def);
204 bool hasAnyCopies() {
210 bool MustBeAvailable =
false) {
211 auto CI =
Copies.find(RegUnit);
214 if (MustBeAvailable && !CI->second.Avail)
216 return CI->second.MI;
221 auto CI =
Copies.find(RegUnit);
224 if (CI->second.DefRegs.size() != 1)
227 return findCopyForUnit(*RUI,
TRI,
true);
240 std::optional<DestSourcePair> CopyOperands =
241 isCopyInstr(*AvailCopy,
TII, UseCopyInstr);
242 Register AvailSrc = CopyOperands->Source->getReg();
243 Register AvailDef = CopyOperands->Destination->getReg();
244 if (!
TRI.isSubRegisterEq(AvailSrc, Reg))
252 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
265 findCopyForUnit(*RUI,
TRI,
true);
270 std::optional<DestSourcePair> CopyOperands =
271 isCopyInstr(*AvailCopy,
TII, UseCopyInstr);
272 Register AvailSrc = CopyOperands->Source->getReg();
273 Register AvailDef = CopyOperands->Destination->getReg();
274 if (!
TRI.isSubRegisterEq(AvailDef, Reg))
283 if (MO.clobbersPhysReg(AvailSrc) || MO.clobbersPhysReg(AvailDef))
305 MachineCopyPropagation(
bool CopyInstr =
false)
319 MachineFunctionProperties::Property::NoVRegs);
323 typedef enum { DebugUse =
false, RegularUse =
true }
DebugType;
331 bool isForwardableRegClassCopy(
const MachineInstr &Copy,
333 bool isBackwardPropagatableRegClassCopy(
const MachineInstr &Copy,
353char MachineCopyPropagation::ID = 0;
358 "Machine Copy Propagation Pass",
false,
false)
367 if (DT == RegularUse) {
368 LLVM_DEBUG(
dbgs() <<
"MCP: Copy is used - not dead: "; Copy->dump());
369 MaybeDeadCopies.remove(Copy);
371 CopyDbgUsers[Copy].insert(&Reader);
387 std::optional<DestSourcePair> CopyOperands =
388 isCopyInstr(PreviousCopy, *
TII, UseCopyInstr);
389 MCRegister PreviousSrc = CopyOperands->Source->getReg().asMCReg();
390 MCRegister PreviousDef = CopyOperands->Destination->getReg().asMCReg();
391 if (Src == PreviousSrc && Def == PreviousDef)
393 if (!
TRI->isSubRegister(PreviousSrc, Src))
395 unsigned SubIdx =
TRI->getSubRegIndex(PreviousSrc, Src);
396 return SubIdx ==
TRI->getSubRegIndex(PreviousDef, Def);
402bool MachineCopyPropagation::eraseIfRedundant(
MachineInstr &Copy,
406 if (
MRI->isReserved(Src) ||
MRI->isReserved(Def))
411 Tracker.findAvailCopy(Copy, Def, *
TRI, *
TII, UseCopyInstr);
415 auto PrevCopyOperands = isCopyInstr(*PrevCopy, *
TII, UseCopyInstr);
417 if (PrevCopyOperands->Destination->isDead())
426 std::optional<DestSourcePair> CopyOperands =
427 isCopyInstr(Copy, *
TII, UseCopyInstr);
430 Register CopyDef = CopyOperands->Destination->getReg();
431 assert(CopyDef == Src || CopyDef == Def);
434 MI.clearRegisterKills(CopyDef,
TRI);
436 Copy.eraseFromParent();
442bool MachineCopyPropagation::isBackwardPropagatableRegClassCopy(
444 std::optional<DestSourcePair> CopyOperands =
445 isCopyInstr(Copy, *
TII, UseCopyInstr);
446 Register Def = CopyOperands->Destination->getReg();
450 return URC->contains(Def);
460bool MachineCopyPropagation::isForwardableRegClassCopy(
const MachineInstr &Copy,
463 std::optional<DestSourcePair> CopyOperands =
464 isCopyInstr(Copy, *
TII, UseCopyInstr);
465 Register CopySrcReg = CopyOperands->Source->getReg();
471 return URC->contains(CopySrcReg);
473 auto UseICopyOperands = isCopyInstr(UseI, *
TII, UseCopyInstr);
474 if (!UseICopyOperands)
497 Register UseDstReg = UseICopyOperands->Destination->getReg();
499 bool IsCrossClass =
false;
501 if (RC->contains(CopySrcReg) && RC->contains(UseDstReg)) {
503 if (
TRI->getCrossCopyRegClass(RC) != RC) {
515 Register CopyDstReg = CopyOperands->Destination->getReg();
517 if (RC->contains(CopySrcReg) && RC->contains(CopyDstReg) &&
518 TRI->getCrossCopyRegClass(RC) != RC)
532bool MachineCopyPropagation::hasImplicitOverlap(
const MachineInstr &
MI,
535 if (&MIUse != &
Use && MIUse.isReg() && MIUse.isImplicit() &&
536 MIUse.isUse() &&
TRI->regsOverlap(
Use.getReg(), MIUse.getReg()))
546bool MachineCopyPropagation::hasOverlappingMultipleDef(
549 if ((&MIDef != &MODef) && MIDef.isReg() &&
550 TRI->regsOverlap(Def, MIDef.getReg()))
560 if (!Tracker.hasAnyCopies())
566 for (
unsigned OpIdx = 0, OpEnd =
MI.getNumOperands(); OpIdx < OpEnd;
588 *
TRI, *
TII, UseCopyInstr);
592 std::optional<DestSourcePair> CopyOperands =
593 isCopyInstr(*Copy, *
TII, UseCopyInstr);
594 Register CopyDstReg = CopyOperands->Destination->getReg();
600 unsigned SubregIdx = 0;
603 if (MOUse.
getReg() != CopyDstReg) {
604 SubregIdx =
TRI->getSubRegIndex(CopyDstReg, MOUse.
getReg());
610 if (
MRI->isReserved(CopySrcReg) && !
MRI->isConstantPhysReg(CopySrcReg))
613 if (!isForwardableRegClassCopy(*Copy,
MI, OpIdx))
616 if (hasImplicitOverlap(
MI, MOUse))
622 if (isCopyInstr(
MI, *
TII, UseCopyInstr) &&
623 MI.modifiesRegister(CopySrcReg,
TRI) &&
624 !
MI.definesRegister(CopySrcReg)) {
630 LLVM_DEBUG(
dbgs() <<
"MCP: Skipping forwarding due to debug counter:\n "
637 <<
"\n in " <<
MI <<
" from " << *Copy);
640 MOUse.
setReg(
TRI->getSubReg(CopySrcReg, SubregIdx));
653 KMI.clearRegisterKills(CopySrcReg,
TRI);
666 std::optional<DestSourcePair> CopyOperands =
667 isCopyInstr(
MI, *
TII, UseCopyInstr);
670 Register RegSrc = CopyOperands->Source->getReg();
671 Register RegDef = CopyOperands->Destination->getReg();
673 if (!
TRI->regsOverlap(RegDef, RegSrc)) {
675 "MachineCopyPropagation should be run after register allocation!");
695 if (eraseIfRedundant(
MI, Def, Src) || eraseIfRedundant(
MI, Src, Def))
701 CopyOperands = isCopyInstr(
MI, *
TII, UseCopyInstr);
702 Src = CopyOperands->Source->getReg().asMCReg();
706 ReadRegister(Src,
MI, RegularUse);
708 if (!MO.isReg() || !MO.readsReg())
713 ReadRegister(Reg,
MI, RegularUse);
719 if (!
MRI->isReserved(Def))
720 MaybeDeadCopies.insert(&
MI);
729 Tracker.clobberRegister(Def, *
TRI, *
TII, UseCopyInstr);
731 if (!MO.isReg() || !MO.isDef())
736 Tracker.clobberRegister(Reg, *
TRI, *
TII, UseCopyInstr);
739 Tracker.trackCopy(&
MI, *
TRI, *
TII, UseCopyInstr);
747 if (MO.isReg() && MO.isEarlyClobber()) {
753 ReadRegister(Reg,
MI, RegularUse);
754 Tracker.clobberRegister(Reg, *
TRI, *
TII, UseCopyInstr);
772 "MachineCopyPropagation should be run after register allocation!");
774 if (MO.isDef() && !MO.isEarlyClobber()) {
777 }
else if (MO.readsReg())
778 ReadRegister(
Reg.asMCReg(),
MI, MO.isDebug() ? DebugUse : RegularUse);
787 MaybeDeadCopies.
begin();
788 DI != MaybeDeadCopies.end();) {
790 std::optional<DestSourcePair> CopyOperands =
791 isCopyInstr(*MaybeDead, *
TII, UseCopyInstr);
792 MCRegister Reg = CopyOperands->Destination->getReg().asMCReg();
800 LLVM_DEBUG(
dbgs() <<
"MCP: Removing copy due to regmask clobbering: ";
805 Tracker.clobberRegister(Reg, *
TRI, *
TII, UseCopyInstr);
809 DI = MaybeDeadCopies.erase(DI);
818 Tracker.clobberRegister(Reg, *
TRI, *
TII, UseCopyInstr);
826 LLVM_DEBUG(
dbgs() <<
"MCP: Removing copy due to no live-out succ: ";
829 std::optional<DestSourcePair> CopyOperands =
830 isCopyInstr(*MaybeDead, *
TII, UseCopyInstr);
833 Register SrcReg = CopyOperands->Source->getReg();
834 Register DestReg = CopyOperands->Destination->getReg();
839 CopyDbgUsers[MaybeDead].
begin(), CopyDbgUsers[MaybeDead].
end());
849 MaybeDeadCopies.clear();
850 CopyDbgUsers.clear();
858 std::optional<DestSourcePair> CopyOperands =
859 isCopyInstr(
MI,
TII, UseCopyInstr);
860 assert(CopyOperands &&
"MI is expected to be a COPY");
862 Register Def = CopyOperands->Destination->getReg();
863 Register Src = CopyOperands->Source->getReg();
868 if (
MRI.isReserved(Def) ||
MRI.isReserved(Src))
871 return CopyOperands->Source->isRenamable() && CopyOperands->Source->isKill();
875 if (!Tracker.hasAnyCopies())
878 for (
unsigned OpIdx = 0, OpEnd =
MI.getNumOperands(); OpIdx != OpEnd;
901 std::optional<DestSourcePair> CopyOperands =
902 isCopyInstr(*Copy, *
TII, UseCopyInstr);
903 Register Def = CopyOperands->Destination->getReg();
904 Register Src = CopyOperands->Source->getReg();
906 if (MODef.
getReg() != Src)
909 if (!isBackwardPropagatableRegClassCopy(*Copy,
MI, OpIdx))
912 if (hasImplicitOverlap(
MI, MODef))
915 if (hasOverlappingMultipleDef(
MI, MODef, Def))
920 <<
MI <<
" from " << *Copy);
926 MaybeDeadCopies.insert(Copy);
928 ++NumCopyBackwardPropagated;
932void MachineCopyPropagation::BackwardCopyPropagateBlock(
939 std::optional<DestSourcePair> CopyOperands =
940 isCopyInstr(
MI, *
TII, UseCopyInstr);
941 if (CopyOperands &&
MI.getNumOperands() == 2) {
942 Register DefReg = CopyOperands->Destination->getReg();
943 Register SrcReg = CopyOperands->Source->getReg();
945 if (!
TRI->regsOverlap(DefReg, SrcReg)) {
952 Tracker.invalidateRegister(Src, *
TRI, *
TII, UseCopyInstr);
953 Tracker.invalidateRegister(Def, *
TRI, *
TII, UseCopyInstr);
954 Tracker.trackCopy(&
MI, *
TRI, *
TII, UseCopyInstr);
962 if (MO.isReg() && MO.isEarlyClobber()) {
966 Tracker.invalidateRegister(Reg, *
TRI, *
TII, UseCopyInstr);
978 Tracker.invalidateRegister(MO.getReg().asMCReg(), *
TRI, *
TII,
988 if (
auto *Copy = Tracker.findCopyDefViaUnit(*RUI, *
TRI)) {
989 CopyDbgUsers[
Copy].insert(&
MI);
993 Tracker.invalidateRegister(MO.getReg().asMCReg(), *
TRI, *
TII,
1000 for (
auto *Copy : MaybeDeadCopies) {
1001 std::optional<DestSourcePair> CopyOperands =
1002 isCopyInstr(*Copy, *
TII, UseCopyInstr);
1003 Register Src = CopyOperands->Source->getReg();
1004 Register Def = CopyOperands->Destination->getReg();
1006 CopyDbgUsers[Copy].
end());
1008 MRI->updateDbgUsersToReg(Src.asMCReg(),
Def.asMCReg(), MaybeDeadDbgUsers);
1009 Copy->eraseFromParent();
1013 MaybeDeadCopies.clear();
1014 CopyDbgUsers.clear();
1018bool MachineCopyPropagation::runOnMachineFunction(
MachineFunction &MF) {
1029 BackwardCopyPropagateBlock(
MBB);
1030 ForwardCopyPropagateBlock(
MBB);
1038 return new MachineCopyPropagation(UseCopyInstr);
unsigned const MachineRegisterInfo * MRI
static void clear(coro::Shape &Shape)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines the DenseMap class.
const HexagonInstrInfo * TII
static bool isNopCopy(const MachineInstr &PreviousCopy, MCRegister Src, MCRegister Def, const TargetRegisterInfo *TRI, const TargetInstrInfo *TII, bool UseCopyInstr)
Return true if PreviousCopy did copy register Src to register Def.
static bool isBackwardPropagatableCopy(MachineInstr &MI, const MachineRegisterInfo &MRI, const TargetInstrInfo &TII, bool UseCopyInstr)
static cl::opt< bool > MCPUseCopyInstr("mcp-use-is-copy-instr", cl::init(false), cl::Hidden)
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
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)
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
static bool shouldExecute(unsigned CounterName)
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Wrapper class representing physical registers. Should be passed by value.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
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.
Representation of each machine instruction.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const TargetRegisterClass * getRegClassConstraint(unsigned OpIdx, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const
Compute the static register class constraint for operand OpIdx.
MachineOperand class - Representation of each machine instruction operand.
void setIsRenamable(bool Val=true)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
bool isRenamable() const
isRenamable - Returns true if this register may be renamed, i.e.
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Wrapper class representing virtual and physical registers.
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
iterator begin()
Get an iterator to the beginning of the SetVector.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
A Use represents the edge between a Value definition and its users.
reverse_self_iterator getReverseIterator()
self_iterator getIterator()
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
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...
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
MachineFunctionPass * createMachineCopyPropagationPass(bool UseCopyInstr)
void initializeMachineCopyPropagationPass(PassRegistry &)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
char & MachineCopyPropagationID
MachineCopyPropagation - This pass performs copy propagation on machine instructions.