// This pass performs loop invariant code motion on machine instructions. We
// attempt to remove as much code from the body of a loop as possible.
//
+// This pass does not attempt to throttle itself to limit register pressure.
+// The register allocation phases are expected to perform rematerialization
+// to recover when register pressure is high.
+//
+// This pass is not intended to be a replacement or a complete alternative
+// for the LLVM-IR-level LICM pass. It is only designed to hoist simple
+// constructs that are not exposed before lowering and instruction selection.
+//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "machine-licm"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
using namespace llvm;
STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
+STATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed");
namespace {
class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass {
// State that is updated as we process loops
bool Changed; // True if a loop is changed.
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;
public:
static char ID; // Pass identification, replacement for typeid
MachineLICM() : MachineFunctionPass(&ID) {}
AU.addPreserved<MachineDominatorTree>();
MachineFunctionPass::getAnalysisUsage(AU);
}
- private:
- /// VisitAllLoops - Visit all of the loops in depth first order and try to
- /// hoist invariant instructions from them.
- ///
- void VisitAllLoops(MachineLoop *L) {
- const std::vector<MachineLoop*> &SubLoops = L->getSubLoops();
- for (MachineLoop::iterator
- I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) {
- MachineLoop *ML = *I;
-
- // Traverse the body of the loop in depth first order on the dominator
- // tree so that we are guaranteed to see definitions before we see uses.
- VisitAllLoops(ML);
- HoistRegion(DT->getNode(ML->getHeader()));
- }
-
- HoistRegion(DT->getNode(L->getHeader()));
- }
-
- /// IsInSubLoop - A little predicate that returns true if the specified
- /// basic block is in a subloop of the current one, not the current one
- /// itself.
- ///
- bool IsInSubLoop(MachineBasicBlock *BB) {
- assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
- return LI->getLoopFor(BB) != CurLoop;
+ virtual void releaseMemory() {
+ CSEMap.clear();
}
+ private:
/// IsLoopInvariantInst - Returns true if the instruction is loop
/// invariant. I.e., all virtual register operands are defined outside of
/// the loop, physical registers aren't accessed (explicitly or implicitly),
///
bool IsLoopInvariantInst(MachineInstr &I);
- /// FindPredecessors - Get all of the predecessors of the loop that are not
- /// back-edges.
- ///
- void FindPredecessors(std::vector<MachineBasicBlock*> &Preds) {
- const MachineBasicBlock *Header = CurLoop->getHeader();
-
- for (MachineBasicBlock::const_pred_iterator
- I = Header->pred_begin(), E = Header->pred_end(); I != E; ++I)
- if (!CurLoop->contains(*I))
- Preds.push_back(*I);
- }
-
- /// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of
- /// the predecessor basic block (but before the terminator instructions).
- ///
- void MoveInstToEndOfBlock(MachineBasicBlock *ToMBB,
- MachineBasicBlock *FromMBB,
- MachineInstr *MI);
+ /// IsProfitableToHoist - Return true if it is potentially profitable to
+ /// hoist the given loop invariant.
+ bool IsProfitableToHoist(MachineInstr &MI);
/// HoistRegion - Walk the specified region of the CFG (defined by all
/// blocks dominated by the specified block, and that are in the current
FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); }
+/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most
+/// loop that has a preheader.
+static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) {
+ for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop())
+ if (L->getLoopPreheader())
+ return false;
+ return true;
+}
+
/// Hoist expressions out of the specified loop. Note, alias info for inner loop
/// is not preserved so it is not a good idea to run LICM multiple times on one
/// loop.
///
bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
+ const Function *F = MF.getFunction();
+ if (F->hasFnAttr(Attribute::OptimizeForSize))
+ return false;
+
DOUT << "******** Machine LICM ********\n";
Changed = false;
I = LI->begin(), E = LI->end(); I != E; ++I) {
CurLoop = *I;
- // Visit all of the instructions of the loop. We want to visit the subloops
- // first, though, so that we can hoist their invariants first into their
- // containing loop before we process that loop.
- VisitAllLoops(CurLoop);
+ // Only visit outer-most preheader-sporting loops.
+ if (!LoopIsOuterMostWithPreheader(CurLoop))
+ continue;
+
+ // Determine the block to which to hoist instructions. If we can't find a
+ // suitable loop preheader, we can't do any hoisting.
+ //
+ // FIXME: We are only hoisting if the basic block coming into this loop
+ // has only one successor. This isn't the case in general because we haven't
+ // broken critical edges or added preheaders.
+ CurPreheader = CurLoop->getLoopPreheader();
+ if (!CurPreheader)
+ continue;
+
+ HoistRegion(DT->getNode(CurLoop->getHeader()));
}
return Changed;
// If this subregion is not in the top level loop at all, exit.
if (!CurLoop->contains(BB)) return;
- // Only need to process the contents of this block if it is not part of a
- // subloop (which would already have been processed).
- if (!IsInSubLoop(BB))
- for (MachineBasicBlock::iterator
- I = BB->begin(), E = BB->end(); I != E; ) {
- MachineInstr &MI = *I++;
-
- // Try hoisting the instruction out of the loop. We can only do this if
- // all of the operands of the instruction are loop invariant and if it is
- // safe to hoist the instruction.
- Hoist(MI);
- }
+ for (MachineBasicBlock::iterator
+ MII = BB->begin(), E = BB->end(); MII != E; ) {
+ MachineBasicBlock::iterator NextMII = MII; ++NextMII;
+ MachineInstr &MI = *MII;
+
+ Hoist(MI);
+
+ MII = NextMII;
+ }
const std::vector<MachineDomTreeNode*> &Children = N->getChildren();
if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
TID.hasUnmodeledSideEffects())
return false;
-
+
if (TID.mayLoad()) {
// Okay, this instruction does a load. As a refinement, we allow the target
// to decide whether the loaded value is actually a constant. If so, we can
if (!MO.isReg())
continue;
- if (MO.isDef() && TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
- // Don't hoist an instruction that defines a physical register.
- return false;
-
- if (!MO.isUse())
- continue;
-
unsigned Reg = MO.getReg();
if (Reg == 0) continue;
- // Don't hoist instructions that access physical registers.
+ // Don't hoist an instruction that uses or defines a physical register.
if (TargetRegisterInfo::isPhysicalRegister(Reg))
return false;
+ if (!MO.isUse())
+ continue;
+
assert(RegInfo->getVRegDef(Reg) &&
"Machine instr not mapped for this vreg?!");
return true;
}
-/// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of the
-/// predecessor basic block (but before the terminator instructions).
-///
-void MachineLICM::MoveInstToEndOfBlock(MachineBasicBlock *ToMBB,
- MachineBasicBlock *FromMBB,
- MachineInstr *MI) {
- DEBUG({
- DOUT << "Hoisting " << *MI;
- if (ToMBB->getBasicBlock())
- DOUT << " to MachineBasicBlock "
- << ToMBB->getBasicBlock()->getName();
- if (FromMBB->getBasicBlock())
- DOUT << " from MachineBasicBlock "
- << FromMBB->getBasicBlock()->getName();
- DOUT << "\n";
- });
- MachineBasicBlock::iterator WhereIter = ToMBB->getFirstTerminator();
- MachineBasicBlock::iterator To, From = FromMBB->begin();
+/// HasPHIUses - Return true if the specified register has any PHI use.
+static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) {
+ for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg),
+ UE = RegInfo->use_end(); UI != UE; ++UI) {
+ MachineInstr *UseMI = &*UI;
+ if (UseMI->getOpcode() == TargetInstrInfo::PHI)
+ return true;
+ }
+ return false;
+}
- while (&*From != MI)
- ++From;
+/// IsProfitableToHoist - Return true if it is potentially profitable to hoist
+/// the given loop invariant.
+bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
+ const TargetInstrDesc &TID = MI.getDesc();
- assert(From != FromMBB->end() && "Didn't find instr in BB!");
+ // FIXME: For now, only hoist re-materilizable instructions. LICM will
+ // increase register pressure. We want to make sure it doesn't increase
+ // spilling.
+ if (!TID.mayLoad() && (!TID.isRematerializable() ||
+ !TII->isTriviallyReMaterializable(&MI)))
+ return false;
- To = From;
- ToMBB->splice(WhereIter, FromMBB, From, ++To);
- ++NumHoisted;
+ // 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
+ // implementation to perform remat.
+ for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
+ const MachineOperand &MO = MI.getOperand(i);
+ if (!MO.isReg() || !MO.isDef())
+ continue;
+ if (HasPHIUses(MO.getReg(), RegInfo))
+ return false;
+ }
+
+ return true;
+}
+
+static const MachineInstr *LookForDuplicate(const MachineInstr *MI,
+ std::vector<const MachineInstr*> &PrevMIs) {
+ 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())
+ continue;
+ if (!MO.isIdenticalTo(PrevMI->getOperand(j))) {
+ IsSame = false;
+ break;
+ }
+ }
+ if (IsSame)
+ return PrevMI;
+ }
+ return 0;
}
/// Hoist - When an instruction is found to use only loop invariant operands
///
void MachineLICM::Hoist(MachineInstr &MI) {
if (!IsLoopInvariantInst(MI)) return;
+ if (!IsProfitableToHoist(MI)) return;
- std::vector<MachineBasicBlock*> Preds;
-
- // Non-back-edge predecessors.
- FindPredecessors(Preds);
-
- // Either we don't have any predecessors(?!) or we have more than one, which
- // is forbidden.
- if (Preds.empty() || Preds.size() != 1) return;
+ // Now move the instructions to the predecessor, inserting it before any
+ // terminator instructions.
+ DEBUG({
+ DOUT << "Hoisting " << MI;
+ if (CurPreheader->getBasicBlock())
+ DOUT << " to MachineBasicBlock "
+ << CurPreheader->getBasicBlock()->getName();
+ if (MI.getParent()->getBasicBlock())
+ DOUT << " from MachineBasicBlock "
+ << MI.getParent()->getBasicBlock()->getName();
+ DOUT << "\n";
+ });
- // Check that the predecessor is qualified to take the hoisted instruction.
- // I.e., there is only one edge from the predecessor, and it's to the loop
- // header.
- MachineBasicBlock *MBB = Preds.front();
+ // 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);
+ if (Dup) {
+ DOUT << "CSEing " << MI;
+ DOUT << " 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;
+ }
+ }
- // FIXME: We are assuming at first that the basic block coming into this loop
- // has only one successor. This isn't the case in general because we haven't
- // broken critical edges or added preheaders.
- if (MBB->succ_size() != 1) return;
- assert(*MBB->succ_begin() == CurLoop->getHeader() &&
- "The predecessor doesn't feed directly into the loop header!");
+ // 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));
+ }
+ }
- // Now move the instructions to the predecessor.
- MoveInstToEndOfBlock(MBB, MI.getParent(), &MI);
+ ++NumHoisted;
Changed = true;
}
projects / oota-llvm.git / blobdiff