Go to the documentation of this file.
51 #define DEBUG_TYPE "machine-cse"
53 STATISTIC(NumCoalesces,
"Number of copies coalesced");
54 STATISTIC(NumCSEs,
"Number of common subexpression eliminated");
55 STATISTIC(NumPREs,
"Number of partial redundant expression"
56 " transformed to fully redundant");
58 "Number of physreg referencing common subexpr eliminated");
60 "Number of cross-MBB physreg referencing CS eliminated");
61 STATISTIC(NumCommutes,
"Number of copies coalesced after commuting");
98 void releaseMemory()
override {
110 using ScopeType = ScopedHTType::ScopeTy;
113 unsigned LookAheadLimit = 0;
129 PhysDefVector &PhysDefs,
bool &PhysUseDef)
const;
132 PhysDefVector &PhysDefs,
bool &NonLocal)
const;
160 "Machine Common Subexpression Elimination",
false,
false)
172 bool Changed =
false;
174 if (!MO.isReg() || !MO.isUse())
226 bool MachineCSE::isPhysDefTriviallyDead(
229 unsigned LookAheadLeft = LookAheadLimit;
230 while (LookAheadLeft) {
238 bool SeenDef =
false;
240 if (MO.isRegMask() && MO.clobbersPhysReg(
Reg))
242 if (!MO.isReg() || !MO.getReg())
284 PhysDefVector &PhysDefs,
285 bool &PhysUseDef)
const {
288 if (!MO.isReg() || MO.isDef())
321 PhysDefs.push_back(std::make_pair(MOP.index(),
Reg));
325 for (
unsigned i = 0,
e = PhysDefs.size();
i !=
e; ++
i)
330 return !PhysRefs.
empty();
335 PhysDefVector &PhysDefs,
336 bool &NonLocal)
const {
343 bool CrossMBB =
false;
348 for (
unsigned i = 0,
e = PhysDefs.size();
i !=
e; ++
i) {
360 unsigned LookAheadLeft = LookAheadLimit;
361 while (LookAheadLeft) {
363 while (
I !=
E &&
I != EE &&
I->isDebugInstr())
367 assert(CrossMBB &&
"Reaching end-of-MBB without finding MI?");
401 if (
MI->isPosition() ||
MI->isPHI() ||
MI->isImplicitDef() ||
MI->isKill() ||
402 MI->isInlineAsm() ||
MI->isDebugInstr())
406 if (
MI->isCopyLike())
410 if (
MI->mayStore() ||
MI->isCall() ||
MI->isTerminator() ||
411 MI->mayRaiseFPException() ||
MI->hasUnmodeledSideEffects())
418 if (!
MI->isDereferenceableInvariantLoad(
AA))
427 if (
MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
442 bool MayIncreasePressure =
true;
444 MayIncreasePressure =
false;
451 MayIncreasePressure =
true;
456 if (!MayIncreasePressure)
return true;
469 bool HasVRegUse =
false;
477 bool HasNonCopyUse =
false;
480 if (!
MI.isCopyLike()) {
481 HasNonCopyUse =
true;
493 HasPHI |=
UseMI.isPHI();
494 if (
UseMI.getParent() ==
MI->getParent())
503 ScopeType *
Scope =
new ScopeType(VNT);
516 bool Changed =
false;
522 if (!isCSECandidate(&
MI))
525 bool FoundCSE = VNT.count(&
MI);
528 if (PerformTrivialCopyPropagation(&
MI,
MBB)) {
536 FoundCSE = VNT.count(&
MI);
541 bool Commuted =
false;
542 if (!FoundCSE &&
MI.isCommutable()) {
545 FoundCSE = VNT.count(NewMI);
548 NewMI->eraseFromParent();
550 }
else if (!FoundCSE)
552 (void)
TII->commuteInstruction(
MI);
559 bool CrossMBBPhysDef =
false;
561 PhysDefVector PhysDefs;
562 bool PhysUseDef =
false;
564 hasLivePhysRegDefUses(&
MI,
MBB, PhysRefs, PhysDefs, PhysUseDef)) {
573 unsigned CSVN = VNT.lookup(&
MI);
575 if (PhysRegDefsReach(CSMI, &
MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
581 VNT.insert(&
MI, CurrVN++);
587 unsigned CSVN = VNT.lookup(&
MI);
590 LLVM_DEBUG(
dbgs() <<
"*** Found a common subexpression: " << *CSMI);
601 if (
MI.isConvergent() &&
MI.getParent() != CSMI->
getParent()) {
602 LLVM_DEBUG(
dbgs() <<
"*** Convergent MI and subexpression exist in "
603 "different BBs, avoid CSE!\n");
604 VNT.insert(&
MI, CurrVN++);
611 unsigned NumDefs =
MI.getNumDefs();
613 for (
unsigned i = 0,
e =
MI.getNumOperands(); NumDefs &&
i !=
e; ++
i) {
623 ImplicitDefsToUpdate.push_back(
i);
628 ImplicitDefs.push_back(OldReg);
630 if (OldReg == NewReg) {
637 "Do not CSE physical register defs!");
639 if (!isProfitableToCSE(NewReg, OldReg, CSMI->
getParent(), &
MI)) {
650 dbgs() <<
"*** Not the same register constraints, avoid CSE!\n");
655 CSEPairs.push_back(std::make_pair(OldReg, NewReg));
661 for (
const std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
662 unsigned OldReg = CSEPair.first;
663 unsigned NewReg = CSEPair.second;
666 assert(
Def !=
nullptr &&
"CSEd register has no unique definition?");
667 Def->clearRegisterDeads(NewReg);
675 for (
unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
677 for (
const auto &PhysDef : PhysDefs)
678 if (!
MI.getOperand(PhysDef.first).isDead())
693 for (
auto ImplicitDef : ImplicitDefs)
695 ImplicitDef,
true,
TRI))
700 for (
auto ImplicitDef : ImplicitDefs)
704 if (CrossMBBPhysDef) {
707 while (!PhysDefs.empty()) {
708 auto LiveIn = PhysDefs.pop_back_val();
715 MI.eraseFromParent();
717 if (!PhysRefs.
empty())
723 VNT.insert(&
MI, CurrVN++);
727 ImplicitDefsToUpdate.clear();
728 ImplicitDefs.clear();
740 if (OpenChildren[Node])
744 ExitScope(Node->getBlock());
748 unsigned Left = --OpenChildren[Parent];
751 ExitScope(Parent->getBlock());
764 WorkList.push_back(Node);
767 Scopes.push_back(Node);
768 OpenChildren[Node] = Node->getNumChildren();
770 }
while (!WorkList.empty());
773 bool Changed =
false;
777 Changed |= ProcessBlockCSE(
MBB);
779 ExitScopeIfDone(Node, OpenChildren);
789 if (!isCSECandidate(
MI) ||
790 MI->isNotDuplicable() ||
792 MI->isAsCheapAsAMove() ||
793 MI->getNumDefs() != 1 ||
794 MI->getNumExplicitDefs() != 1)
797 for (
const auto &def :
MI->defs())
801 for (
const auto &
use :
MI->uses())
810 bool Changed =
false;
812 if (!isPRECandidate(&
MI))
815 if (!PREMap.count(&
MI)) {
820 auto MBB1 = PREMap[&
MI];
823 "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
825 if (!CMBB->isLegalToHoistInto())
828 if (!isProfitableToHoistInto(CMBB,
MBB, MBB1))
835 if (
BB !=
nullptr && BB1 !=
nullptr &&
845 if (
MI.isConvergent() && CMBB !=
MBB)
849 "First operand of instr with one explicit def must be this def");
852 if (!isProfitableToCSE(NewReg, VReg, CMBB, &
MI))
855 TII->duplicate(*CMBB, CMBB->getFirstTerminator(),
MI);
883 bool Changed =
false;
890 Changed |= ProcessBlockPRE(DT,
MBB);
892 }
while (!BBs.empty());
904 "CandidateBB should dominate MBB1");
916 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
917 DT = &getAnalysis<MachineDominatorTree>();
918 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
919 LookAheadLimit =
TII->getMachineCSELookAheadLimit();
920 bool ChangedPRE, ChangedCSE;
921 ChangedPRE = PerformSimplePRE(DT);
923 return ChangedPRE || ChangedCSE;
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
Move duplicate certain instructions close to their use
pred_iterator pred_begin()
This is an optimization pass for GlobalISel generic memory operations.
bool constrainRegAttrs(Register Reg, Register ConstrainingReg, unsigned MinNumRegs=0)
Constrain the register class or the register bank of the virtual register Reg (and low-level type) to...
MachineInstrBuilder & UseMI
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual const TargetInstrInfo * getInstrInfo() const
void setIsKill(bool Val=true)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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 ...
Reg
All possible values of the reg field in the ModR/M byte.
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
MachineDomTreeNode * getRootNode() const
Properties which a MachineFunction may have at a given point in time.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
LLVM_NODISCARD T pop_back_val()
unsigned const TargetRegisterInfo * TRI
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isAsCheapAsAMove(const MachineInstr &MI) const override
unsigned pred_size() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
TargetInstrInfo - Interface to description of machine instruction set.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const MachineOperand & getOperand(unsigned i) const
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Represent the analysis usage information of a pass.
const HexagonInstrInfo * TII
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...
MachineOperand class - Representation of each machine instruction operand.
MachineFunctionProperties & set(Property P)
STATISTIC(NumFunctions, "Total number of functions")
bool reservedRegsFrozen() const
reservedRegsFrozen - Returns true after freezeReservedRegs() was called to ensure the set of reserved...
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
void initializeMachineCSEPass(PassRegistry &)
virtual bool isCallerPreservedPhysReg(MCRegister PhysReg, const MachineFunction &MF) const
Physical registers that may be modified within a function but are guaranteed to be restored before an...
Special DenseMapInfo traits to compare MachineInstr* by value of the instruction rather than by point...
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
void clearKillFlags(Register Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
void setIsDead(bool Val=true)
bool regsOverlap(Register RegA, Register RegB) const
Returns true if the two registers are equal or alias each other.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Machine Common Subexpression Elimination
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...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
char & MachineCSEID
MachineCSE - This pass performs global CSE on machine instructions.
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Register getReg() const
getReg - Returns the register number.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Scope
Defines the scope in which this symbol should be visible: Default – Visible in the public interface o...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
AnalysisUsage & addPreservedID(const void *ID)
bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
INITIALIZE_PASS_BEGIN(MachineCSE, DEBUG_TYPE, "Machine Common Subexpression Elimination", false, false) INITIALIZE_PASS_END(MachineCSE
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
const MachineBasicBlock * getParent() const
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Base class for the actual dominator tree node.
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
unsigned getSubReg() const
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
Function & getFunction()
Return the LLVM function that this machine code represents.
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
COFF::MachineTypes Machine
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 setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstrBuilder MachineInstrBuilder & DefMI
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
static bool isCallerPreservedOrConstPhysReg(MCRegister Reg, const MachineFunction &MF, const TargetRegisterInfo &TRI)
LLVM_NODISCARD bool empty() const
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
MCRegAliasIterator enumerates all registers aliasing Reg.
Wrapper class representing physical registers. Should be passed by value.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void changeDebugValuesDefReg(Register Reg)
Find all DBG_VALUEs that point to the register def in this instruction and point them to Reg instead.