48 #define DEBUG_TYPE "machine-cse" 50 STATISTIC(NumCoalesces,
"Number of copies coalesced");
51 STATISTIC(NumCSEs,
"Number of common subexpression eliminated");
53 "Number of physreg referencing common subexpr eliminated");
55 "Number of cross-MBB physreg referencing CS eliminated");
56 STATISTIC(NumCommutes,
"Number of copies coalesced after commuting");
85 void releaseMemory()
override {
96 using ScopeType = ScopedHTType::ScopeTy;
98 unsigned LookAheadLimit = 0;
104 bool PerformTrivialCopyPropagation(MachineInstr *
MI,
106 bool isPhysDefTriviallyDead(
unsigned Reg,
109 bool hasLivePhysRegDefUses(
const MachineInstr *
MI,
113 bool &PhysUseDef)
const;
114 bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *
MI,
117 bool &NonLocal)
const;
118 bool isCSECandidate(MachineInstr *
MI);
119 bool isProfitableToCSE(
unsigned CSReg,
unsigned Reg,
120 MachineInstr *CSMI, MachineInstr *
MI);
136 "Machine Common Subexpression Elimination",
false,
false)
148 bool Changed =
false;
150 if (!MO.isReg() || !MO.isUse())
152 unsigned Reg = MO.getReg();
201 MachineCSE::isPhysDefTriviallyDead(
unsigned Reg,
204 unsigned LookAheadLeft = LookAheadLimit;
205 while (LookAheadLeft) {
213 bool SeenDef =
false;
215 if (MO.isRegMask() && MO.clobbersPhysReg(Reg))
217 if (!MO.isReg() || !MO.getReg())
260 bool &PhysUseDef)
const{
263 if (!MO.isReg() || MO.isDef())
265 unsigned Reg = MO.getReg();
281 if (!MO.isReg() || !MO.isDef())
283 unsigned Reg = MO.getReg();
289 if (PhysRefs.
count(Reg))
294 if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->
end()))
299 for (
unsigned i = 0, e = PhysDefs.
size(); i != e; ++i)
303 return !PhysRefs.
empty();
309 bool &NonLocal)
const {
316 bool CrossMBB =
false;
321 for (
unsigned i = 0, e = PhysDefs.
size(); i != e; ++i) {
332 unsigned LookAheadLeft = LookAheadLimit;
333 while (LookAheadLeft) {
335 while (I != E && I != EE && I->isDebugInstr())
339 assert(CrossMBB &&
"Reaching end-of-MBB without finding MI?");
356 if (!MO.isReg() || !MO.isDef())
358 unsigned MOReg = MO.getReg();
361 if (PhysRefs.
count(MOReg))
399 if (MI->
getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
407 bool MachineCSE::isProfitableToCSE(
unsigned CSReg,
unsigned Reg,
413 bool MayIncreasePressure =
true;
416 MayIncreasePressure =
false;
422 if (!CSUses.
count(&MI)) {
423 MayIncreasePressure =
true;
428 if (!MayIncreasePressure)
return true;
442 bool HasVRegUse =
false;
444 if (MO.isReg() && MO.isUse() &&
451 bool HasNonCopyUse =
false;
455 HasNonCopyUse =
true;
467 HasPHI |=
UseMI.isPHI();
477 ScopeType *Scope =
new ScopeType(VNT);
478 ScopeMap[MBB] = Scope;
484 assert(SI != ScopeMap.end());
490 bool Changed =
false;
499 if (!isCSECandidate(MI))
502 bool FoundCSE = VNT.count(MI);
505 if (PerformTrivialCopyPropagation(MI, MBB)) {
513 FoundCSE = VNT.count(MI);
518 bool Commuted =
false;
522 FoundCSE = VNT.count(NewMI);
525 NewMI->eraseFromParent();
527 }
else if (!FoundCSE)
536 bool CrossMBBPhysDef =
false;
539 bool PhysUseDef =
false;
540 if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs,
541 PhysDefs, PhysUseDef)) {
550 unsigned CSVN = VNT.lookup(MI);
552 if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
558 VNT.insert(MI, CurrVN++);
564 unsigned CSVN = VNT.lookup(MI);
567 LLVM_DEBUG(
dbgs() <<
"*** Found a common subexpression: " << *CSMI);
573 for (
unsigned i = 0, e = MI->
getNumOperands(); NumDefs && i != e; ++i) {
577 unsigned OldReg = MO.
getReg();
590 if (OldReg == NewReg) {
597 "Do not CSE physical register defs!");
599 if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
610 dbgs() <<
"*** Not the same register constraints, avoid CSE!\n");
615 CSEPairs.
push_back(std::make_pair(OldReg, NewReg));
621 for (std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
622 unsigned OldReg = CSEPair.first;
623 unsigned NewReg = CSEPair.second;
626 assert(Def !=
nullptr &&
"CSEd register has no unique definition?");
635 for (
unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
650 for (
auto ImplicitDef : ImplicitDefs)
652 ImplicitDef,
true, TRI))
653 MO->setIsKill(
false);
657 for (
auto ImplicitDef : ImplicitDefs)
661 if (CrossMBBPhysDef) {
664 while (!PhysDefs.
empty()) {
674 if (!PhysRefs.
empty())
680 VNT.insert(MI, CurrVN++);
684 ImplicitDefsToUpdate.
clear();
685 ImplicitDefs.
clear();
697 if (OpenChildren[Node])
701 ExitScope(Node->getBlock());
705 unsigned Left = --OpenChildren[Parent];
708 ExitScope(Parent->getBlock());
725 const std::vector<MachineDomTreeNode*> &Children = Node->
getChildren();
726 OpenChildren[Node] = Children.
size();
729 }
while (!WorkList.
empty());
732 bool Changed =
false;
738 ExitScopeIfDone(Node, OpenChildren);
751 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
752 DT = &getAnalysis<MachineDominatorTree>();
Machine Common Subexpression Elimination
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool isCall(QueryType Type=AnyInBundle) const
bool isAllocatable(unsigned PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
This class represents lattice values for constants.
INITIALIZE_PASS_BEGIN(MachineCSE, DEBUG_TYPE, "Machine Common Subexpression Elimination", false, false) INITIALIZE_PASS_END(MachineCSE
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void push_back(const T &Elt)
void initializeMachineCSEPass(PassRegistry &)
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
MachineInstr * commuteInstruction(MachineInstr &MI, bool NewMI=false, unsigned OpIdx1=CommuteAnyOperandIndex, unsigned OpIdx2=CommuteAnyOperandIndex) const
This method commutes the operands of the given machine instruction MI.
unsigned getSubReg() const
bool constrainRegAttrs(unsigned Reg, unsigned ConstrainingReg, unsigned MinNumRegs=0)
Constrain the register class or the register bank of the virtual register Reg (and low-level type) to...
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
void setIsDead(bool Val=true)
bool reservedRegsFrozen() const
reservedRegsFrozen - Returns true after freezeReservedRegs() was called to ensure the set of reserved...
iterator_range< mop_iterator > operands()
bool isCopyLike() const
Return true if the instruction behaves like a copy.
Special DenseMapInfo traits to compare MachineInstr* by value of the instruction rather than by point...
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
virtual unsigned getMachineCSELookAheadLimit() const
Return the value to use for the MachineCSE's LookAheadLimit, which is a heuristic used for CSE'ing ph...
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
LLVM_NODISCARD bool empty() const
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
char & MachineCSEID
MachineCSE - This pass performs global CSE on machine instructions.
void clearKillFlags(unsigned Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
void changeDebugValuesDefReg(unsigned Reg)
Find all DBG_VALUEs immediately following this instruction that point to a register def in this instr...
Base class for the actual dominator tree node.
const std::vector< DomTreeNodeBase * > & getChildren() const
AnalysisUsage & addPreservedID(const void *ID)
COFF::MachineTypes Machine
virtual const TargetInstrInfo * getInstrInfo() const
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
bool isDereferenceableInvariantLoad(AliasAnalysis *AA) const
Return true if this load instruction never traps and points to a memory location whose value doesn't ...
TargetInstrInfo - Interface to description of machine instruction set.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void clearRegisterDeads(unsigned Reg)
Clear all dead flags on operands defining register Reg.
MachineInstrBuilder & UseMI
DomTreeNodeBase * getIDom() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
bool isImplicitDef() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
pred_iterator pred_begin()
bool isDebugInstr() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool isConstantPhysReg(unsigned PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
virtual bool isAsCheapAsAMove(const MachineInstr &MI) const
Return true if the instruction is as cheap as a move instruction.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
bool regsOverlap(unsigned regA, unsigned regB) const
Returns true if the two registers are equal or alias each other.
MachineDomTreeNode * getRootNode() const
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
MachineInstrBuilder MachineInstrBuilder & DefMI
LLVM_NODISCARD T pop_back_val()
void setPreservesCFG()
This function should be called by the pass, iff they do not:
unsigned pred_size() const
MachineInstr * getUniqueVRegDef(unsigned Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
IterT skipDebugInstructionsForward(IterT It, IterT End)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator...
const MachineBasicBlock * getParent() const
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
unsigned getNumDefs() const
Returns the total number of definitions.
virtual bool isCallerPreservedPhysReg(unsigned PhysReg, const MachineFunction &MF) const
Physical registers that may be modified within a function but are guaranteed to be restored before an...
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug instruction using the specified regis...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
static bool isCallerPreservedOrConstPhysReg(unsigned Reg, const MachineFunction &MF, const TargetRegisterInfo &TRI)
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
const MachineOperand & getOperand(unsigned i) const
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool isCommutable(QueryType Type=IgnoreBundle) const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z, ..."), which produces the same result if Y and Z are exchanged.
bool isReserved(unsigned PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.