16 #define DEBUG_TYPE "machine-cse"
31 STATISTIC(NumCoalesces,
"Number of copies coalesced");
32 STATISTIC(NumCSEs,
"Number of common subexpression eliminated");
34 "Number of physreg referencing common subexpr eliminated");
36 "Number of cross-MBB physreg referencing CS eliminated");
37 STATISTIC(NumCommutes,
"Number of copies coalesced after commuting");
63 virtual void releaseMemory() {
69 const unsigned LookAheadLimit;
74 typedef ScopedHTType::ScopeTy ScopeType;
81 bool isPhysDefTriviallyDead(
unsigned Reg,
88 bool &PhysUseDef)
const;
92 bool &NonLocal)
const;
94 bool isProfitableToCSE(
unsigned CSReg,
unsigned Reg,
108 "Machine Common Subexpression Elimination",
false,
false)
116 bool Changed =
false;
117 for (
unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
124 if (!
MRI->hasOneNonDBGUse(Reg))
138 DEBUG(
dbgs() <<
"Coalescing: " << *DefMI);
141 MRI->clearKillFlags(SrcReg);
151 MachineCSE::isPhysDefTriviallyDead(
unsigned Reg,
154 unsigned LookAheadLeft = LookAheadLimit;
155 while (LookAheadLeft) {
157 while (I != E && I->isDebugValue())
164 bool SeenDef =
false;
165 for (
unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
197 bool &PhysUseDef)
const{
203 unsigned Reg = MO.
getReg();
222 unsigned Reg = MO.
getReg();
228 if (PhysRefs.
count(Reg))
233 if (!MO.
isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->
end()))
238 for (
unsigned i = 0, e = PhysDefs.
size(); i != e; ++i)
242 return !PhysRefs.
empty();
248 bool &NonLocal)
const {
255 bool CrossMBB =
false;
260 for (
unsigned i = 0, e = PhysDefs.
size(); i != e; ++i) {
261 if (
MRI->isAllocatable(PhysDefs[i]) ||
MRI->isReserved(PhysDefs[i]))
271 unsigned LookAheadLeft = LookAheadLimit;
272 while (LookAheadLeft) {
274 while (I != E && I != EE && I->isDebugValue())
278 assert(CrossMBB &&
"Reaching end-of-MBB without finding MI?");
290 for (
unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
298 unsigned MOReg = MO.
getReg();
301 if (PhysRefs.
count(MOReg))
341 bool MachineCSE::isProfitableToCSE(
unsigned CSReg,
unsigned Reg,
347 bool MayIncreasePressure =
true;
350 MayIncreasePressure =
false;
353 E =
MRI->use_nodbg_end(); I != E; ++
I) {
358 E =
MRI->use_nodbg_end(); I != E; ++
I) {
360 if (!CSUses.
count(Use)) {
361 MayIncreasePressure =
true;
366 if (!MayIncreasePressure)
return true;
380 bool HasVRegUse =
false;
390 bool HasNonCopyUse =
false;
392 E =
MRI->use_nodbg_end(); I != E; ++
I) {
396 HasNonCopyUse =
true;
409 E =
MRI->use_nodbg_end(); I != E; ++
I) {
411 HasPHI |= Use->
isPHI();
422 ScopeType *Scope =
new ScopeType(VNT);
423 ScopeMap[MBB] = Scope;
429 assert(SI != ScopeMap.end());
435 bool Changed =
false;
443 if (!isCSECandidate(MI))
446 bool FoundCSE = VNT.count(MI);
449 if (PerformTrivialCoalescing(MI, MBB)) {
455 FoundCSE = VNT.count(MI);
460 bool Commuted =
false;
465 FoundCSE = VNT.count(NewMI);
470 }
else if (!FoundCSE)
472 (void)
TII->commuteInstruction(MI);
479 bool CrossMBBPhysDef =
false;
482 bool PhysUseDef =
false;
483 if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs,
484 PhysDefs, PhysUseDef)) {
493 unsigned CSVN = VNT.lookup(MI);
495 if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
501 VNT.insert(MI, CurrVN++);
507 unsigned CSVN = VNT.lookup(MI);
510 DEBUG(
dbgs() <<
"*** Found a common subexpression: " << *CSMI);
517 for (
unsigned i = 0, e = MI->
getNumOperands(); NumDefs && i != e; ++i) {
521 unsigned OldReg = MO.
getReg();
528 if (OldReg == NewReg) {
535 "Do not CSE physical register defs!");
537 if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
538 DEBUG(
dbgs() <<
"*** Not profitable, avoid CSE!\n");
546 if (!
MRI->constrainRegClass(NewReg, OldRC)) {
547 DEBUG(
dbgs() <<
"*** Not the same register class, avoid CSE!\n");
552 CSEPairs.
push_back(std::make_pair(OldReg, NewReg));
558 for (
unsigned i = 0, e = CSEPairs.
size(); i != e; ++i) {
559 MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second);
560 MRI->clearKillFlags(CSEPairs[i].second);
565 for (
unsigned i = 0, e = ImplicitDefsToUpdate.
size(); i != e; ++i)
568 if (CrossMBBPhysDef) {
571 while (!PhysDefs.
empty()) {
581 if (!PhysRefs.
empty())
587 VNT.insert(MI, CurrVN++);
591 ImplicitDefsToUpdate.
clear();
603 if (OpenChildren[Node])
607 ExitScope(Node->getBlock());
611 unsigned Left = --OpenChildren[Parent];
614 ExitScope(Parent->getBlock());
631 const std::vector<MachineDomTreeNode*> &Children = Node->
getChildren();
632 unsigned NumChildren = Children.size();
633 OpenChildren[Node] = NumChildren;
634 for (
unsigned i = 0; i != NumChildren; ++i) {
638 }
while (!WorkList.
empty());
641 bool Changed =
false;
642 for (
unsigned i = 0, e = Scopes.
size(); i != e; ++i) {
646 Changed |= ProcessBlock(MBB);
648 ExitScopeIfDone(Node, OpenChildren);
658 AA = &getAnalysis<AliasAnalysis>();
659 DT = &getAnalysis<MachineDominatorTree>();
660 return PerformCSE(DT->getRootNode());
void push_back(const T &Elt)
const MachineFunction * getParent() const
AnalysisUsage & addPreserved()
static PassRegistry * getPassRegistry()
STATISTIC(NumCoalesces,"Number of copies coalesced")
unsigned getNumImplicitDefs() const
Return the number of implicit defs this instruct has.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions. Register definitions always occur...
void initializeMachineCSEPass(PassRegistry &)
bool mayStore(QueryType Type=AnyInBundle) const
static bool isVirtualRegister(unsigned Reg)
void addLiveIn(unsigned Reg)
const MCInstrDesc & getDesc() const
void setIsDead(bool Val=true)
bool isTerminator(QueryType Type=AnyInBundle) const
DomTreeNodeBase< NodeT > * getIDom() const
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
const HexagonInstrInfo * TII
T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val()
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool mayLoad(QueryType Type=AnyInBundle) const
ID
LLVM Calling Convention Representation.
unsigned getNumOperands() const
char & MachineCSEID
MachineCSE - This pass performs global CSE on machine instructions.
bool count(PtrType Ptr) const
count - Return true if the specified pointer is in the set.
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
AnalysisUsage & addPreservedID(const void *ID)
COFF::MachineTypes Machine
const MachineBasicBlock * getParent() const
bool isDebugValue() const
bool isImplicitDef() const
bundle_iterator< MachineInstr, instr_iterator > iterator
machine Machine Common Subexpression Elimination
const MCRegisterClass & getRegClass(unsigned i) const
Returns the register class associated with the enumeration value. See class MCOperandInfo.
bool isAsCheapAsAMove(QueryType Type=AllInBundle) const
const MachineOperand & getOperand(unsigned i) const
ItTy next(ItTy it, Dist n)
bool hasUnmodeledSideEffects() const
bool isInvariantLoad(AliasAnalysis *AA) const
#define INITIALIZE_AG_DEPENDENCY(depName)
unsigned getSubReg() const
pred_iterator pred_begin()
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
const std::vector< DomTreeNodeBase< NodeT > * > & getChildren() const
machine Machine Common Subexpression false
virtual const TargetInstrInfo * getInstrInfo() const
bool isSuccessor(const MachineBasicBlock *MBB) const
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
StringRef getName() const
bool count(const T &V) const
count - Return true if the element is in the set.
bundle_iterator< const MachineInstr, const_instr_iterator > const_iterator
bool isLiveIn(unsigned Reg) const
MachineRegisterInfo & getRegInfo()
virtual void getAnalysisUsage(AnalysisUsage &AU) const
void setReg(unsigned Reg)
bool isCall(QueryType Type=AnyInBundle) const
const TargetMachine & getTarget() const
virtual const TargetRegisterInfo * getRegisterInfo() const
unsigned getReg() const
getReg - Returns the register number.
bool isCommutable(QueryType Type=IgnoreBundle) const
INITIALIZE_PASS_BEGIN(MachineCSE,"machine-cse","Machine Common Subexpression Elimination", false, false) INITIALIZE_PASS_END(MachineCSE
const MCRegisterInfo & MRI
iterator find(const KeyT &Val)
unsigned pred_size() const