Go to the documentation of this file.
52 #define DEBUG_TYPE "machine-cse"
54 STATISTIC(NumCoalesces,
"Number of copies coalesced");
55 STATISTIC(NumCSEs,
"Number of common subexpression eliminated");
56 STATISTIC(NumPREs,
"Number of partial redundant expression"
57 " transformed to fully redundant");
59 "Number of physreg referencing common subexpr eliminated");
61 "Number of cross-MBB physreg referencing CS eliminated");
62 STATISTIC(NumCommutes,
"Number of copies coalesced after commuting");
94 void releaseMemory()
override {
106 using ScopeType = ScopedHTType::ScopeTy;
109 unsigned LookAheadLimit = 0;
125 PhysDefVector &PhysDefs,
bool &PhysUseDef)
const;
128 PhysDefVector &PhysDefs,
bool &NonLocal)
const;
156 "Machine Common Subexpression Elimination",
false,
false)
168 bool Changed =
false;
170 if (!MO.isReg() || !MO.isUse())
222 bool MachineCSE::isPhysDefTriviallyDead(
225 unsigned LookAheadLeft = LookAheadLimit;
226 while (LookAheadLeft) {
234 bool SeenDef =
false;
236 if (MO.isRegMask() && MO.clobbersPhysReg(
Reg))
238 if (!MO.isReg() || !MO.getReg())
280 PhysDefVector &PhysDefs,
281 bool &PhysUseDef)
const {
284 if (!MO.isReg() || MO.isDef())
317 PhysDefs.push_back(std::make_pair(MOP.index(),
Reg));
321 for (
unsigned i = 0,
e = PhysDefs.size();
i !=
e; ++
i)
326 return !PhysRefs.
empty();
331 PhysDefVector &PhysDefs,
332 bool &NonLocal)
const {
339 bool CrossMBB =
false;
344 for (
unsigned i = 0,
e = PhysDefs.size();
i !=
e; ++
i) {
356 unsigned LookAheadLeft = LookAheadLimit;
357 while (LookAheadLeft) {
359 while (
I !=
E &&
I != EE &&
I->isDebugInstr())
363 assert(CrossMBB &&
"Reaching end-of-MBB without finding MI?");
397 if (
MI->isPosition() ||
MI->isPHI() ||
MI->isImplicitDef() ||
MI->isKill() ||
398 MI->isInlineAsm() ||
MI->isDebugInstr())
402 if (
MI->isCopyLike())
406 if (
MI->mayStore() ||
MI->isCall() ||
MI->isTerminator() ||
407 MI->mayRaiseFPException() ||
MI->hasUnmodeledSideEffects())
414 if (!
MI->isDereferenceableInvariantLoad(AA))
423 if (
MI->getOpcode() == TargetOpcode::LOAD_STACK_GUARD)
438 bool MayIncreasePressure =
true;
440 MayIncreasePressure =
false;
447 MayIncreasePressure =
true;
452 if (!MayIncreasePressure)
return true;
457 if (
TII->isAsCheapAsAMove(*
MI)) {
465 bool HasVRegUse =
false;
473 bool HasNonCopyUse =
false;
476 if (!
MI.isCopyLike()) {
477 HasNonCopyUse =
true;
489 HasPHI |=
UseMI.isPHI();
490 if (
UseMI.getParent() ==
MI->getParent())
499 ScopeType *
Scope =
new ScopeType(VNT);
512 bool Changed =
false;
521 if (!isCSECandidate(
MI))
524 bool FoundCSE = VNT.count(
MI);
527 if (PerformTrivialCopyPropagation(
MI,
MBB)) {
531 if (
MI->isCopyLike())
535 FoundCSE = VNT.count(
MI);
540 bool Commuted =
false;
541 if (!FoundCSE &&
MI->isCommutable()) {
544 FoundCSE = VNT.count(NewMI);
547 NewMI->eraseFromParent();
549 }
else if (!FoundCSE)
551 (void)
TII->commuteInstruction(*
MI);
558 bool CrossMBBPhysDef =
false;
560 PhysDefVector PhysDefs;
561 bool PhysUseDef =
false;
562 if (FoundCSE && hasLivePhysRegDefUses(
MI,
MBB, PhysRefs,
563 PhysDefs, PhysUseDef)) {
572 unsigned CSVN = VNT.lookup(
MI);
574 if (PhysRegDefsReach(CSMI,
MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
580 VNT.insert(
MI, CurrVN++);
586 unsigned CSVN = VNT.lookup(
MI);
589 LLVM_DEBUG(
dbgs() <<
"*** Found a common subexpression: " << *CSMI);
593 unsigned NumDefs =
MI->getNumDefs();
595 for (
unsigned i = 0,
e =
MI->getNumOperands(); NumDefs &&
i !=
e; ++
i) {
605 ImplicitDefsToUpdate.push_back(
i);
610 ImplicitDefs.push_back(OldReg);
612 if (OldReg == NewReg) {
619 "Do not CSE physical register defs!");
621 if (!isProfitableToCSE(NewReg, OldReg, CSMI->
getParent(),
MI)) {
632 dbgs() <<
"*** Not the same register constraints, avoid CSE!\n");
637 CSEPairs.push_back(std::make_pair(OldReg, NewReg));
643 for (
const std::pair<unsigned, unsigned> &CSEPair : CSEPairs) {
644 unsigned OldReg = CSEPair.first;
645 unsigned NewReg = CSEPair.second;
648 assert(
Def !=
nullptr &&
"CSEd register has no unique definition?");
649 Def->clearRegisterDeads(NewReg);
657 for (
unsigned ImplicitDefToUpdate : ImplicitDefsToUpdate)
659 for (
const auto &PhysDef : PhysDefs)
660 if (!
MI->getOperand(PhysDef.first).isDead())
675 for (
auto ImplicitDef : ImplicitDefs)
677 ImplicitDef,
true,
TRI))
682 for (
auto ImplicitDef : ImplicitDefs)
686 if (CrossMBBPhysDef) {
689 while (!PhysDefs.empty()) {
690 auto LiveIn = PhysDefs.pop_back_val();
697 MI->eraseFromParent();
699 if (!PhysRefs.
empty())
705 VNT.insert(
MI, CurrVN++);
709 ImplicitDefsToUpdate.clear();
710 ImplicitDefs.clear();
722 if (OpenChildren[Node])
726 ExitScope(Node->getBlock());
730 unsigned Left = --OpenChildren[Parent];
733 ExitScope(Parent->getBlock());
746 WorkList.push_back(Node);
749 Scopes.push_back(Node);
750 OpenChildren[Node] = Node->getNumChildren();
752 }
while (!WorkList.empty());
755 bool Changed =
false;
759 Changed |= ProcessBlockCSE(
MBB);
761 ExitScopeIfDone(Node, OpenChildren);
771 if (!isCSECandidate(
MI) ||
772 MI->isNotDuplicable() ||
774 MI->isAsCheapAsAMove() ||
775 MI->getNumDefs() != 1 ||
776 MI->getNumExplicitDefs() != 1)
779 for (
const auto &def :
MI->defs())
783 for (
const auto &
use :
MI->uses())
792 bool Changed =
false;
797 if (!isPRECandidate(
MI))
800 if (!PREMap.count(
MI)) {
805 auto MBB1 = PREMap[
MI];
808 "MBB cannot properly dominate MBB1 while DFS through dominators tree!");
810 if (!CMBB->isLegalToHoistInto())
813 if (!isProfitableToHoistInto(CMBB,
MBB, MBB1))
820 if (
BB !=
nullptr && BB1 !=
nullptr &&
825 "First operand of instr with one explicit def must be this def");
828 if (!isProfitableToCSE(NewReg, VReg, CMBB,
MI))
831 TII->duplicate(*CMBB, CMBB->getFirstTerminator(), *
MI);
859 bool Changed =
false;
866 Changed |= ProcessBlockPRE(DT,
MBB);
868 }
while (!BBs.empty());
880 "CandidateBB should dominate MBB1");
892 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
893 DT = &getAnalysis<MachineDominatorTree>();
894 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
895 LookAheadLimit =
TII->getMachineCSELookAheadLimit();
896 bool ChangedPRE, ChangedCSE;
897 ChangedPRE = PerformSimplePRE(DT);
899 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()
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 ...
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
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.
void setDebugLoc(DebugLoc dl)
Replace current source information with new such.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
LLVM_NODISCARD T pop_back_val()
unsigned const TargetRegisterInfo * TRI
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
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.
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.
STATISTIC(NumFunctions, "Total number of functions")
bool regsOverlap(Register regA, Register regB) const
Returns true if the two registers are equal or alias each other.
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...
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 isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=false)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
Machine Common Subexpression Elimination
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())
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.
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.
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.