#define DEBUG_TYPE "machine-licm"
#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/MachineConstantPool.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineMemOperand.h"
namespace {
class MachineLICM : public MachineFunctionPass {
+ MachineConstantPool *MCP;
const TargetMachine *TM;
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
// State that is updated as we process loops
bool Changed; // True if a loop is changed.
+ bool FirstInLoop; // True if it's the first LICM in the loop.
MachineLoop *CurLoop; // The current loop we are working on.
MachineBasicBlock *CurPreheader; // The preheader for CurLoop.
- // For each BB and opcode pair, keep a list of hoisted instructions.
- DenseMap<std::pair<unsigned, unsigned>,
- std::vector<const MachineInstr*> > CSEMap;
+ // For each opcode, keep a list of potentail CSE instructions.
+ DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap;
public:
static char ID; // Pass identification, replacement for typeid
MachineLICM() : MachineFunctionPass(&ID) {}
///
void HoistRegion(MachineDomTreeNode *N);
+ /// isLoadFromConstantMemory - Return true if the given instruction is a
+ /// load from constant memory.
+ bool isLoadFromConstantMemory(MachineInstr *MI);
+
/// ExtractHoistableLoad - Unfold a load from the given machineinstr if
/// the load itself could be hoisted. Return the unfolded and hoistable
/// load, or null if the load couldn't be unfolded or if it wouldn't
/// be hoistable.
MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
+ /// LookForDuplicate - Find an instruction amount PrevMIs that is a
+ /// duplicate of MI. Return this instruction if it's found.
+ const MachineInstr *LookForDuplicate(const MachineInstr *MI,
+ std::vector<const MachineInstr*> &PrevMIs);
+
+ /// EliminateCSE - Given a LICM'ed instruction, look for an instruction on
+ /// the preheader that compute the same value. If it's found, do a RAU on
+ /// with the definition of the existing instruction rather than hoisting
+ /// the instruction to the preheader.
+ bool EliminateCSE(MachineInstr *MI,
+ DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI);
+
/// Hoist - When an instruction is found to only use loop invariant operands
/// that is safe to hoist, this instruction is called to do the dirty work.
///
void Hoist(MachineInstr *MI);
+
+ /// InitCSEMap - Initialize the CSE map with instructions that are in the
+ /// current loop preheader that may become duplicates of instructions that
+ /// are hoisted out of the loop.
+ void InitCSEMap(MachineBasicBlock *BB);
};
} // end anonymous namespace
/// loop.
///
bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
- DEBUG(errs() << "******** Machine LICM ********\n");
+ DEBUG(dbgs() << "******** Machine LICM ********\n");
- Changed = false;
+ Changed = FirstInLoop = false;
+ MCP = MF.getConstantPool();
TM = &MF.getTarget();
TII = TM->getInstrInfo();
TRI = TM->getRegisterInfo();
DT = &getAnalysis<MachineDominatorTree>();
AA = &getAnalysis<AliasAnalysis>();
- for (MachineLoopInfo::iterator
- I = LI->begin(), E = LI->end(); I != E; ++I) {
+ for (MachineLoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
CurLoop = *I;
// Only visit outer-most preheader-sporting loops.
if (!CurPreheader)
continue;
+ // CSEMap is initialized for loop header when the first instruction is
+ // being hoisted.
+ FirstInLoop = true;
HoistRegion(DT->getNode(CurLoop->getHeader()));
+ CSEMap.clear();
}
return Changed;
for (MachineBasicBlock::iterator
MII = BB->begin(), E = BB->end(); MII != E; ) {
MachineBasicBlock::iterator NextMII = MII; ++NextMII;
- MachineInstr &MI = *MII;
-
- Hoist(&MI);
-
+ Hoist(&*MII);
MII = NextMII;
}
// to decide whether the loaded value is actually a constant. If so, we can
// actually use it as a load.
if (!I.isInvariantLoad(AA))
- // FIXME: we should be able to sink loads with no other side effects if
- // there is nothing that can change memory from here until the end of
- // block. This is a trivial form of alias analysis.
+ // FIXME: we should be able to hoist loads with no other side effects if
+ // there are no other instructions which can change memory in this loop.
+ // This is a trivial form of alias analysis.
return false;
}
- DEBUG({
- errs() << "--- Checking if we can hoist " << I;
- if (I.getDesc().getImplicitUses()) {
- errs() << " * Instruction has implicit uses:\n";
-
- const TargetRegisterInfo *TRI = TM->getRegisterInfo();
- for (const unsigned *ImpUses = I.getDesc().getImplicitUses();
- *ImpUses; ++ImpUses)
- errs() << " -> " << TRI->getName(*ImpUses) << "\n";
- }
-
- if (I.getDesc().getImplicitDefs()) {
- errs() << " * Instruction has implicit defines:\n";
-
- const TargetRegisterInfo *TRI = TM->getRegisterInfo();
- for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs();
- *ImpDefs; ++ImpDefs)
- errs() << " -> " << TRI->getName(*ImpDefs) << "\n";
- }
- });
-
- if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) {
- DEBUG(errs() << "Cannot hoist with implicit defines or uses\n");
- return false;
- }
-
// The instruction is loop invariant if all of its operands are.
for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
const MachineOperand &MO = I.getOperand(i);
} else if (!MO.isDead()) {
// A def that isn't dead. We can't move it.
return false;
+ } else if (CurLoop->getHeader()->isLiveIn(Reg)) {
+ // If the reg is live into the loop, we can't hoist an instruction
+ // which would clobber it.
+ return false;
}
}
// If the loop contains the definition of an operand, then the instruction
// isn't loop invariant.
- if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent()))
+ if (CurLoop->contains(RegInfo->getVRegDef(Reg)))
return false;
}
for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg),
UE = RegInfo->use_end(); UI != UE; ++UI) {
MachineInstr *UseMI = &*UI;
- if (UseMI->getOpcode() == TargetInstrInfo::PHI)
+ if (UseMI->isPHI())
return true;
}
return false;
}
+/// isLoadFromConstantMemory - Return true if the given instruction is a
+/// load from constant memory. Machine LICM will hoist these even if they are
+/// not re-materializable.
+bool MachineLICM::isLoadFromConstantMemory(MachineInstr *MI) {
+ if (!MI->getDesc().mayLoad()) return false;
+ if (!MI->hasOneMemOperand()) return false;
+ MachineMemOperand *MMO = *MI->memoperands_begin();
+ if (MMO->isVolatile()) return false;
+ if (!MMO->getValue()) return false;
+ const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(MMO->getValue());
+ if (PSV) {
+ MachineFunction &MF = *MI->getParent()->getParent();
+ return PSV->isConstant(MF.getFrameInfo());
+ } else {
+ return AA->pointsToConstantMemory(MMO->getValue());
+ }
+}
+
/// IsProfitableToHoist - Return true if it is potentially profitable to hoist
/// the given loop invariant.
bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
- if (MI.getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
+ if (MI.isImplicitDef())
return false;
// FIXME: For now, only hoist re-materilizable instructions. LICM will
// increase register pressure. We want to make sure it doesn't increase
// spilling.
- if (!TII->isTriviallyReMaterializable(&MI, AA))
- return false;
+ // Also hoist loads from constant memory, e.g. load from stubs, GOT. Hoisting
+ // these tend to help performance in low register pressure situation. The
+ // trade off is it may cause spill in high pressure situation. It will end up
+ // adding a store in the loop preheader. But the reload is no more expensive.
+ // The side benefit is these loads are frequently CSE'ed.
+ if (!TII->isTriviallyReMaterializable(&MI, AA)) {
+ if (!isLoadFromConstantMemory(&MI))
+ return false;
+ }
// If result(s) of this instruction is used by PHIs, then don't hoist it.
// The presence of joins makes it difficult for current register allocator
return true;
}
-static const MachineInstr *LookForDuplicate(const MachineInstr *MI,
- std::vector<const MachineInstr*> &PrevMIs,
- MachineRegisterInfo *RegInfo) {
- unsigned NumOps = MI->getNumOperands();
- for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) {
- const MachineInstr *PrevMI = PrevMIs[i];
- unsigned NumOps2 = PrevMI->getNumOperands();
- if (NumOps != NumOps2)
- continue;
- bool IsSame = true;
- for (unsigned j = 0; j != NumOps; ++j) {
- const MachineOperand &MO = MI->getOperand(j);
- if (MO.isReg() && MO.isDef()) {
- if (RegInfo->getRegClass(MO.getReg()) !=
- RegInfo->getRegClass(PrevMI->getOperand(j).getReg())) {
- IsSame = false;
- break;
- }
- continue;
- }
- if (!MO.isIdenticalTo(PrevMI->getOperand(j))) {
- IsSame = false;
- break;
- }
- }
- if (IsSame)
- return PrevMI;
- }
- return 0;
-}
-
MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) {
// If not, we may be able to unfold a load and hoist that.
// First test whether the instruction is loading from an amenable
// memory location.
- if (!MI->getDesc().mayLoad()) return 0;
- if (!MI->hasOneMemOperand()) return 0;
- MachineMemOperand *MMO = *MI->memoperands_begin();
- if (MMO->isVolatile()) return 0;
- MachineFunction &MF = *MI->getParent()->getParent();
- if (!MMO->getValue()) return 0;
- if (const PseudoSourceValue *PSV =
- dyn_cast<PseudoSourceValue>(MMO->getValue())) {
- if (!PSV->isConstant(MF.getFrameInfo())) return 0;
- } else {
- if (!AA->pointsToConstantMemory(MMO->getValue())) return 0;
- }
+ if (!isLoadFromConstantMemory(MI))
+ return 0;
+
// Next determine the register class for a temporary register.
unsigned LoadRegIndex;
unsigned NewOpc =
const TargetRegisterClass *RC = TID.OpInfo[LoadRegIndex].getRegClass(TRI);
// Ok, we're unfolding. Create a temporary register and do the unfold.
unsigned Reg = RegInfo->createVirtualRegister(RC);
+
+ MachineFunction &MF = *MI->getParent()->getParent();
SmallVector<MachineInstr *, 2> NewMIs;
bool Success =
TII->unfoldMemoryOperand(MF, MI, Reg,
return NewMIs[0];
}
+void MachineLICM::InitCSEMap(MachineBasicBlock *BB) {
+ for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) {
+ const MachineInstr *MI = &*I;
+ // FIXME: For now, only hoist re-materilizable instructions. LICM will
+ // increase register pressure. We want to make sure it doesn't increase
+ // spilling.
+ if (TII->isTriviallyReMaterializable(MI, AA)) {
+ unsigned Opcode = MI->getOpcode();
+ DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator
+ CI = CSEMap.find(Opcode);
+ if (CI != CSEMap.end())
+ CI->second.push_back(MI);
+ else {
+ std::vector<const MachineInstr*> CSEMIs;
+ CSEMIs.push_back(MI);
+ CSEMap.insert(std::make_pair(Opcode, CSEMIs));
+ }
+ }
+ }
+}
+
+const MachineInstr*
+MachineLICM::LookForDuplicate(const MachineInstr *MI,
+ std::vector<const MachineInstr*> &PrevMIs) {
+ for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) {
+ const MachineInstr *PrevMI = PrevMIs[i];
+ if (TII->produceSameValue(MI, PrevMI))
+ return PrevMI;
+ }
+ return 0;
+}
+
+bool MachineLICM::EliminateCSE(MachineInstr *MI,
+ DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) {
+ if (CI == CSEMap.end())
+ return false;
+
+ if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
+ DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
+
+ // Replace virtual registers defined by MI by their counterparts defined
+ // by Dup.
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ const MachineOperand &MO = MI->getOperand(i);
+
+ // Physical registers may not differ here.
+ assert((!MO.isReg() || MO.getReg() == 0 ||
+ !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) ||
+ MO.getReg() == Dup->getOperand(i).getReg()) &&
+ "Instructions with different phys regs are not identical!");
+
+ if (MO.isReg() && MO.isDef() &&
+ !TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
+ RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg());
+ }
+ MI->eraseFromParent();
+ ++NumCSEed;
+ return true;
+ }
+ return false;
+}
+
/// Hoist - When an instruction is found to use only loop invariant operands
/// that are safe to hoist, this instruction is called to do the dirty work.
///
// Now move the instructions to the predecessor, inserting it before any
// terminator instructions.
DEBUG({
- errs() << "Hoisting " << *MI;
+ dbgs() << "Hoisting " << *MI;
if (CurPreheader->getBasicBlock())
- errs() << " to MachineBasicBlock "
- << CurPreheader->getBasicBlock()->getName();
+ dbgs() << " to MachineBasicBlock "
+ << CurPreheader->getName();
if (MI->getParent()->getBasicBlock())
- errs() << " from MachineBasicBlock "
- << MI->getParent()->getBasicBlock()->getName();
- errs() << "\n";
+ dbgs() << " from MachineBasicBlock "
+ << MI->getParent()->getName();
+ dbgs() << "\n";
});
+ // If this is the first instruction being hoisted to the preheader,
+ // initialize the CSE map with potential common expressions.
+ InitCSEMap(CurPreheader);
+
// Look for opportunity to CSE the hoisted instruction.
- std::pair<unsigned, unsigned> BBOpcPair =
- std::make_pair(CurPreheader->getNumber(), MI->getOpcode());
- DenseMap<std::pair<unsigned, unsigned>,
- std::vector<const MachineInstr*> >::iterator CI = CSEMap.find(BBOpcPair);
- bool DoneCSE = false;
- if (CI != CSEMap.end()) {
- const MachineInstr *Dup = LookForDuplicate(MI, CI->second, RegInfo);
- if (Dup) {
- DEBUG(errs() << "CSEing " << *MI << " with " << *Dup);
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- const MachineOperand &MO = MI->getOperand(i);
- if (MO.isReg() && MO.isDef())
- RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg());
- }
- MI->eraseFromParent();
- DoneCSE = true;
- ++NumCSEed;
- }
- }
+ unsigned Opcode = MI->getOpcode();
+ DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator
+ CI = CSEMap.find(Opcode);
+ if (!EliminateCSE(MI, CI)) {
+ // Otherwise, splice the instruction to the preheader.
+ CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI);
- // Otherwise, splice the instruction to the preheader.
- if (!DoneCSE) {
- CurPreheader->splice(CurPreheader->getFirstTerminator(),
- MI->getParent(), MI);
// Add to the CSE map.
if (CI != CSEMap.end())
CI->second.push_back(MI);
else {
std::vector<const MachineInstr*> CSEMIs;
CSEMIs.push_back(MI);
- CSEMap.insert(std::make_pair(BBOpcPair, CSEMIs));
+ CSEMap.insert(std::make_pair(Opcode, CSEMIs));
}
}