50 #define DEBUG_TYPE "machine-cse" 52 STATISTIC(NumCoalesces,
"Number of copies coalesced");
53 STATISTIC(NumCSEs,
"Number of common subexpression eliminated");
54 STATISTIC(NumPREs,
"Number of partial redundant expression" 55 " transformed to fully redundant");
57 "Number of physreg referencing common subexpr eliminated");
59 "Number of cross-MBB physreg referencing CS eliminated");
60 STATISTIC(NumCommutes,
"Number of copies coalesced after commuting");
92 void releaseMemory()
override {
104 using ScopeType = ScopedHTType::ScopeTy;
107 unsigned LookAheadLimit = 0;
115 bool PerformTrivialCopyPropagation(MachineInstr *
MI,
117 bool isPhysDefTriviallyDead(
unsigned Reg,
120 bool hasLivePhysRegDefUses(
const MachineInstr *
MI,
123 PhysDefVector &PhysDefs,
bool &PhysUseDef)
const;
124 bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *
MI,
126 PhysDefVector &PhysDefs,
bool &NonLocal)
const;
127 bool isCSECandidate(MachineInstr *
MI);
128 bool isProfitableToCSE(
unsigned CSReg,
unsigned Reg,
137 bool isPRECandidate(MachineInstr *
MI);
154 "Machine Common Subexpression Elimination",
false,
false)
166 bool Changed =
false;
168 if (!MO.isReg() || !MO.isUse())
221 MachineCSE::isPhysDefTriviallyDead(
unsigned Reg,
224 unsigned LookAheadLeft = LookAheadLimit;
225 while (LookAheadLeft) {
233 bool SeenDef =
false;
235 if (MO.isRegMask() && MO.clobbersPhysReg(Reg))
237 if (!MO.isReg() || !MO.getReg())
279 PhysDefVector &PhysDefs,
280 bool &PhysUseDef)
const {
283 if (!MO.isReg() || MO.isDef())
310 if (PhysRefs.
count(Reg))
315 if (!MO.
isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->
end()))
316 PhysDefs.push_back(std::make_pair(MOP.index(),
Reg));
320 for (
unsigned i = 0,
e = PhysDefs.size(); i !=
e; ++i)
325 return !PhysRefs.
empty();
330 PhysDefVector &PhysDefs,
331 bool &NonLocal)
const {
338 bool CrossMBB =
false;
343 for (
unsigned i = 0,
e = PhysDefs.size(); i !=
e; ++i) {
355 unsigned LookAheadLeft = LookAheadLimit;
356 while (LookAheadLeft) {
358 while (I != E && I != EE && I->isDebugInstr())
362 assert(CrossMBB &&
"Reaching end-of-MBB without finding MI?");
379 if (!MO.isReg() || !MO.isDef())
384 if (PhysRefs.
count(MOReg))
422 if (MI->
getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
431 bool MachineCSE::isProfitableToCSE(
unsigned CSReg,
unsigned Reg,
437 bool MayIncreasePressure =
true;
439 MayIncreasePressure =
false;
445 if (!CSUses.
count(&MI)) {
446 MayIncreasePressure =
true;
451 if (!MayIncreasePressure)
return true;
464 bool HasVRegUse =
false;
472 bool HasNonCopyUse =
false;
476 HasNonCopyUse =
true;
488 HasPHI |=
UseMI.isPHI();
498 ScopeType *
Scope =
new ScopeType(VNT);
499 ScopeMap[MBB] =
Scope;
505 assert(SI != ScopeMap.end());
511 bool Changed =
false;
520 if (!isCSECandidate(MI))
523 bool FoundCSE = VNT.count(MI);
526 if (PerformTrivialCopyPropagation(MI, MBB)) {
534 FoundCSE = VNT.count(MI);
539 bool Commuted =
false;
543 FoundCSE = VNT.count(NewMI);
546 NewMI->eraseFromParent();
548 }
else if (!FoundCSE)
557 bool CrossMBBPhysDef =
false;
559 PhysDefVector PhysDefs;
560 bool PhysUseDef =
false;
561 if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs,
562 PhysDefs, PhysUseDef)) {
571 unsigned CSVN = VNT.lookup(MI);
573 if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
579 VNT.insert(MI, CurrVN++);
585 unsigned CSVN = VNT.lookup(MI);
588 LLVM_DEBUG(
dbgs() <<
"*** Found a common subexpression: " << *CSMI);
611 if (OldReg == NewReg) {
618 "Do not CSE physical register defs!");
620 if (!isProfitableToCSE(NewReg, OldReg, CSMI->
getParent(),
MI)) {
631 dbgs() <<
"*** Not the same register constraints, avoid CSE!\n");
636 CSEPairs.
push_back(std::make_pair(OldReg, NewReg));
642 for (std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
643 unsigned OldReg = CSEPair.first;
644 unsigned NewReg = CSEPair.second;
647 assert(Def !=
nullptr &&
"CSEd register has no unique definition?");
656 for (
unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
658 for (
auto PhysDef : PhysDefs)
674 for (
auto ImplicitDef : ImplicitDefs)
676 ImplicitDef,
true, TRI))
677 MO->setIsKill(
false);
681 for (
auto ImplicitDef : ImplicitDefs)
685 if (CrossMBBPhysDef) {
688 while (!PhysDefs.empty()) {
689 auto LiveIn = PhysDefs.pop_back_val();
698 if (!PhysRefs.
empty())
704 VNT.insert(MI, CurrVN++);
708 ImplicitDefsToUpdate.
clear();
709 ImplicitDefs.
clear();
721 if (OpenChildren[Node])
725 ExitScope(Node->getBlock());
729 unsigned Left = --OpenChildren[Parent];
732 ExitScope(Parent->getBlock());
749 const std::vector<MachineDomTreeNode*> &Children = Node->
getChildren();
750 OpenChildren[Node] = Children.
size();
753 }
while (!WorkList.
empty());
756 bool Changed =
false;
760 Changed |= ProcessBlockCSE(MBB);
762 ExitScopeIfDone(Node, OpenChildren);
772 if (!isCSECandidate(MI) ||
780 for (
auto def : MI->
defs())
793 bool Changed =
false;
798 if (!isPRECandidate(MI))
801 if (!PREMap.count(MI)) {
806 auto MBB1 = PREMap[
MI];
809 "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
811 if (!CMBB->isLegalToHoistInto())
814 if (!isProfitableToHoistInto(CMBB, MBB, MBB1))
821 if (BB !=
nullptr && BB1 !=
nullptr &&
826 "First operand of instr with one explicit def must be this def");
829 if (!isProfitableToCSE(NewReg, VReg, CMBB, MI))
832 TII->
duplicate(*CMBB, CMBB->getFirstTerminator(), *
MI);
853 bool Changed =
false;
857 const std::vector<MachineDomTreeNode *> &Children = Node->
getChildren();
862 Changed |= ProcessBlockPRE(DT, MBB);
864 }
while (!BBs.
empty());
874 assert(DT->
dominates(CandidateBB, MBB) &&
"CandidateBB should dominate MBB");
876 "CandidateBB should dominate MBB1");
888 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
889 DT = &getAnalysis<MachineDominatorTree>();
890 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
892 bool ChangedPRE, ChangedCSE;
893 ChangedPRE = PerformSimplePRE(DT);
895 return ChangedPRE || ChangedCSE;
Scope
Defines the scope in which this symbol should be visible: Default – Visible in the public interface ...
Machine Common Subexpression Elimination
void changeDebugValuesDefReg(Register Reg)
Find all DBG_VALUEs that point to the register def in this instruction and point them to Reg instead...
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 isReserved(Register PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
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.
iterator_range< mop_iterator > uses()
Returns a range that includes all operands that are register uses.
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock *> *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
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 &)
virtual MachineInstr & duplicate(MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, const MachineInstr &Orig) const
Clones instruction or the whole instruction bundle Orig and insert into MBB before InsertBefore...
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...
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
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.
void clearRegisterDeads(Register Reg)
Clear all dead flags on operands defining register Reg.
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 ...
bool regsOverlap(Register regA, Register regB) const
Returns true if the two registers are equal or alias each other.
char & MachineCSEID
MachineCSE - This pass performs global CSE on machine instructions.
bool mayRaiseFPException() const
Return true if this instruction could possibly raise a floating-point exception.
void clearKillFlags(unsigned Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
Base class for the actual dominator tree node.
const std::vector< DomTreeNodeBase * > & getChildren() const
AnalysisUsage & addPreservedID(const void *ID)
COFF::MachineTypes Machine
void setReg(Register Reg)
Change the register this operand corresponds to.
virtual const TargetInstrInfo * getInstrInfo() const
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
TargetInstrInfo - Interface to description of machine instruction set.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
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.
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Move duplicate certain instructions close to their use
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.
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.
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
MCRegAliasIterator enumerates all registers aliasing Reg.
Represent the analysis usage information of a pass.
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
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 isDereferenceableInvariantLoad(AAResults *AA) const
Return true if this load instruction never traps and points to a memory location whose value doesn't ...
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...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineInstrBuilder MachineInstrBuilder & DefMI
LLVM_NODISCARD T pop_back_val()
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Register cloneVirtualRegister(Register VReg, StringRef Name="")
Create and return a new virtual register in the function with the same attributes as the given regist...
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.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
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 use of the specified register...
unsigned getNumExplicitDefs() const
Returns the number of non-implicit definitions.
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())
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
Register getReg() const
getReg - Returns the register number.
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 isAsCheapAsAMove(QueryType Type=AllInBundle) const
Returns true if this instruction has the same cost (or less) than a move instruction.
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.
Wrapper class representing virtual and physical registers.
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
bool isNotDuplicable(QueryType Type=AnyInBundle) const
Return true if this instruction cannot be safely duplicated.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.