X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FMachineCSE.cpp;h=87aaaa0834cf5186306b1fe1e70330c7dda6884d;hp=76ab7dcb6a3a07f8ce0e6c75c92cf8967db39f35;hb=93204d28b863e1ca28c99188c92bf8658da82736;hpb=bf63022492e54c8abe7c8d8c8448661342294f46 diff --git a/lib/CodeGen/MachineCSE.cpp b/lib/CodeGen/MachineCSE.cpp index 76ab7dcb6a3..87aaaa0834c 100644 --- a/lib/CodeGen/MachineCSE.cpp +++ b/lib/CodeGen/MachineCSE.cpp @@ -13,7 +13,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "machine-cse" #include "llvm/CodeGen/Passes.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ScopedHashTable.h" @@ -25,9 +24,13 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/Debug.h" #include "llvm/Support/RecyclingAllocator.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; +#define DEBUG_TYPE "machine-cse" + STATISTIC(NumCoalesces, "Number of copies coalesced"); STATISTIC(NumCSEs, "Number of common subexpression eliminated"); STATISTIC(NumPhysCSEs, @@ -45,7 +48,7 @@ namespace { MachineRegisterInfo *MRI; public: static char ID; // Pass identification - MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) { + MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(0), CurrVN(0) { initializeMachineCSEPass(*PassRegistry::getPassRegistry()); } @@ -66,7 +69,7 @@ namespace { } private: - const unsigned LookAheadLimit; + unsigned LookAheadLimit; typedef RecyclingAllocator > AllocatorTy; typedef ScopedHashTable Exps; unsigned CurrVN; - bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); + bool PerformTrivialCopyPropagation(MachineInstr *MI, + MachineBasicBlock *MBB); bool isPhysDefTriviallyDead(unsigned Reg, MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator E) const; @@ -111,8 +115,12 @@ INITIALIZE_AG_DEPENDENCY(AliasAnalysis) INITIALIZE_PASS_END(MachineCSE, "machine-cse", "Machine Common Subexpression Elimination", false, false) -bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, - MachineBasicBlock *MBB) { +/// The source register of a COPY machine instruction can be propagated to all +/// its users, and this propagation could increase the probability of finding +/// common subexpressions. If the COPY has only one user, the COPY itself can +/// be removed. +bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI, + MachineBasicBlock *MBB) { bool Changed = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); @@ -121,10 +129,7 @@ bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, unsigned Reg = MO.getReg(); if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; - if (!MRI->hasOneNonDBGUse(Reg)) - // Only coalesce single use copies. This ensure the copy will be - // deleted. - continue; + bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg); MachineInstr *DefMI = MRI->getVRegDef(Reg); if (!DefMI->isCopy()) continue; @@ -152,10 +157,14 @@ bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, continue; DEBUG(dbgs() << "Coalescing: " << *DefMI); DEBUG(dbgs() << "*** to: " << *MI); + // Propagate SrcReg of copies to MI. MO.setReg(SrcReg); MRI->clearKillFlags(SrcReg); - DefMI->eraseFromParent(); - ++NumCoalesces; + // Coalesce single use copies. + if (OnlyOneUse) { + DefMI->eraseFromParent(); + ++NumCoalesces; + } Changed = true; } @@ -364,15 +373,11 @@ bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, TargetRegisterInfo::isVirtualRegister(Reg)) { MayIncreasePressure = false; SmallPtrSet CSUses; - for (MachineRegisterInfo::use_instr_nodbg_iterator - I = MRI->use_instr_nodbg_begin(CSReg), E = MRI->use_instr_nodbg_end(); - I != E; ++I) { - CSUses.insert(&*I); + for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { + CSUses.insert(&MI); } - for (MachineRegisterInfo::use_instr_nodbg_iterator - I = MRI->use_instr_nodbg_begin(Reg), E = MRI->use_instr_nodbg_end(); - I != E; ++I) { - if (!CSUses.count(&*I)) { + for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { + if (!CSUses.count(&MI)) { MayIncreasePressure = true; break; } @@ -383,7 +388,7 @@ bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in // an immediate predecessor. We don't want to increase register pressure and // end up causing other computation to be spilled. - if (MI->isAsCheapAsAMove()) { + if (TII->isAsCheapAsAMove(MI)) { MachineBasicBlock *CSBB = CSMI->getParent(); MachineBasicBlock *BB = MI->getParent(); if (CSBB != BB && !CSBB->isSuccessor(BB)) @@ -403,11 +408,9 @@ bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, } if (!HasVRegUse) { bool HasNonCopyUse = false; - for (MachineRegisterInfo::use_instr_nodbg_iterator - I = MRI->use_instr_nodbg_begin(Reg), E = MRI->use_instr_nodbg_end(); - I != E; ++I) { + for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { // Ignore copies. - if (!I->isCopyLike()) { + if (!MI.isCopyLike()) { HasNonCopyUse = true; break; } @@ -420,11 +423,9 @@ bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, // it unless the defined value is already used in the BB of the new use. bool HasPHI = false; SmallPtrSet CSBBs; - for (MachineRegisterInfo::use_instr_nodbg_iterator - I = MRI->use_instr_nodbg_begin(CSReg), E = MRI->use_instr_nodbg_end(); - I != E; ++I) { - HasPHI |= I->isPHI(); - CSBBs.insert(I->getParent()); + for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { + HasPHI |= MI.isPHI(); + CSBBs.insert(MI.getParent()); } if (!HasPHI) @@ -451,6 +452,7 @@ bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { SmallVector, 8> CSEPairs; SmallVector ImplicitDefsToUpdate; + SmallVector ImplicitDefs; for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { MachineInstr *MI = &*I; ++I; @@ -460,13 +462,15 @@ bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { bool FoundCSE = VNT.count(MI); if (!FoundCSE) { - // Look for trivial copy coalescing opportunities. - if (PerformTrivialCoalescing(MI, MBB)) { + // Using trivial copy propagation to find more CSE opportunities. + if (PerformTrivialCopyPropagation(MI, MBB)) { Changed = true; // After coalescing MI itself may become a copy. if (MI->isCopyLike()) continue; + + // Try again to see if CSE is possible. FoundCSE = VNT.count(MI); } } @@ -540,6 +544,12 @@ bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { // we should make sure it is not dead at CSMI. if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead()) ImplicitDefsToUpdate.push_back(i); + + // Keep track of implicit defs of CSMI and MI, to clear possibly + // made-redundant kill flags. + if (MO.isImplicit() && !MO.isDead() && OldReg == NewReg) + ImplicitDefs.push_back(OldReg); + if (OldReg == NewReg) { --NumDefs; continue; @@ -571,8 +581,15 @@ bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { // Actually perform the elimination. if (DoCSE) { for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { - MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); - MRI->clearKillFlags(CSEPairs[i].second); + unsigned OldReg = CSEPairs[i].first; + unsigned NewReg = CSEPairs[i].second; + // OldReg may have been unused but is used now, clear the Dead flag + MachineInstr *Def = MRI->getUniqueVRegDef(NewReg); + assert(Def != nullptr && "CSEd register has no unique definition?"); + Def->clearRegisterDeads(NewReg); + // Replace with NewReg and clear kill flags which may be wrong now. + MRI->replaceRegWith(OldReg, NewReg); + MRI->clearKillFlags(NewReg); } // Go through implicit defs of CSMI and MI, if a def is not dead at MI, @@ -580,6 +597,29 @@ bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { for (unsigned i = 0, e = ImplicitDefsToUpdate.size(); i != e; ++i) CSMI->getOperand(ImplicitDefsToUpdate[i]).setIsDead(false); + // Go through implicit defs of CSMI and MI, and clear the kill flags on + // their uses in all the instructions between CSMI and MI. + // We might have made some of the kill flags redundant, consider: + // subs ... %NZCV <- CSMI + // csinc ... %NZCV <- this kill flag isn't valid anymore + // subs ... %NZCV <- MI, to be eliminated + // csinc ... %NZCV + // Since we eliminated MI, and reused a register imp-def'd by CSMI + // (here %NZCV), that register, if it was killed before MI, should have + // that kill flag removed, because it's lifetime was extended. + if (CSMI->getParent() == MI->getParent()) { + for (MachineBasicBlock::iterator II = CSMI, IE = MI; II != IE; ++II) + for (auto ImplicitDef : ImplicitDefs) + if (MachineOperand *MO = II->findRegisterUseOperand( + ImplicitDef, /*isKill=*/true, TRI)) + MO->setIsKill(false); + } else { + // If the instructions aren't in the same BB, bail out and clear the + // kill flag on all uses of the imp-def'd register. + for (auto ImplicitDef : ImplicitDefs) + MRI->clearKillFlags(ImplicitDef); + } + if (CrossMBBPhysDef) { // Add physical register defs now coming in from a predecessor to MBB // livein list. @@ -604,6 +644,7 @@ bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { } CSEPairs.clear(); ImplicitDefsToUpdate.clear(); + ImplicitDefs.clear(); } return Changed; @@ -667,10 +708,14 @@ bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { } bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { - TII = MF.getTarget().getInstrInfo(); - TRI = MF.getTarget().getRegisterInfo(); + if (skipOptnoneFunction(*MF.getFunction())) + return false; + + TII = MF.getSubtarget().getInstrInfo(); + TRI = MF.getSubtarget().getRegisterInfo(); MRI = &MF.getRegInfo(); AA = &getAnalysis(); DT = &getAnalysis(); + LookAheadLimit = TII->getMachineCSELookAheadLimit(); return PerformCSE(DT->getRootNode()); }