//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Bill Wendling and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/MRegisterInfo.h"
+#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
using namespace llvm;
namespace {
class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass {
- MachineFunction *CurMF;// Current MachineFunction
+ const TargetMachine *TM;
+ const TargetInstrInfo *TII;
+ MachineFunction *CurMF; // Current MachineFunction
// Various analyses that we use...
MachineLoopInfo *LI; // Current MachineLoopInfo
MachineDominatorTree *DT; // Machine dominator tree for the current Loop
-
- const TargetInstrInfo *TII;
+ MachineRegisterInfo *RegInfo; // Machine register information
// State that is updated as we process loops
bool Changed; // True if a loop is changed.
return LI->getLoopFor(BB) != CurLoop;
}
- /// CanHoistInst - Checks that this instructions is one that can be hoisted
- /// out of the loop. I.e., it has no side effects, isn't a control flow
- /// instr, etc.
- ///
- bool CanHoistInst(MachineInstr &I) const {
- const TargetInstrDescriptor *TID = I.getInstrDescriptor();
-
- // Don't hoist if this instruction implicitly reads physical registers.
- if (TID->ImplicitUses) return false;
-
- MachineOpCode Opcode = TID->Opcode;
- return TII->isTriviallyReMaterializable(&I) &&
- // FIXME: Below necessary?
- !(TII->isReturn(Opcode) ||
- TII->isTerminatorInstr(Opcode) ||
- TII->isBranch(Opcode) ||
- TII->isIndirectBranch(Opcode) ||
- TII->isBarrier(Opcode) ||
- TII->isCall(Opcode) ||
- TII->isLoad(Opcode) || // TODO: Do loads and stores.
- TII->isStore(Opcode));
- }
-
/// 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),
/// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of
/// the predecessor basic block (but before the terminator instructions).
///
- void MoveInstToEndOfBlock(MachineBasicBlock *MBB, MachineInstr *MI) {
- MachineBasicBlock::iterator Iter = MBB->getFirstTerminator();
- MBB->insert(Iter, MI);
+ void MoveInstToEndOfBlock(MachineBasicBlock *ToMBB,
+ MachineBasicBlock *FromMBB,
+ MachineInstr *MI) {
+ DEBUG({
+ DOUT << "Hoisting " << *MI;
+ if (ToMBB->getBasicBlock())
+ DOUT << " to MachineBasicBlock "
+ << ToMBB->getBasicBlock()->getName();
+ DOUT << "\n";
+ });
+
+ MachineBasicBlock::iterator WhereIter = ToMBB->getFirstTerminator();
+ MachineBasicBlock::iterator To, From = FromMBB->begin();
+
+ while (&*From != MI)
+ ++From;
+
+ assert(From != FromMBB->end() && "Didn't find instr in BB!");
+
+ To = From;
+ ToMBB->splice(WhereIter, FromMBB, From, ++To);
++NumHoisted;
}
Changed = false;
CurMF = &MF;
- TII = CurMF->getTarget().getInstrInfo();
+ TM = &CurMF->getTarget();
+ TII = TM->getInstrInfo();
+ RegInfo = new MachineRegisterInfo(*TM->getRegisterInfo());
// Get our Loop information...
LI = &getAnalysis<MachineLoopInfo>();
VisitAllLoops(CurLoop);
}
+ delete RegInfo;
return Changed;
}
const MachineOperand &MO = MI.getOperand(i);
if (MO.isRegister() && MO.isDef() &&
- MRegisterInfo::isVirtualRegister(MO.getReg()))
+ MRegisterInfo::isVirtualRegister(MO.getReg())) {
+ VRegDefs.grow(MO.getReg());
VRegDefs[MO.getReg()] = &MI;
+ }
}
}
}
/// 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), and the
-/// instruction is hoistable.
+/// loop, physical registers aren't accessed explicitly, and there are no side
+/// effects that aren't captured by the operands or other flags.
///
bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
- if (!CanHoistInst(I)) return false;
+ DEBUG({
+ DOUT << "--- Checking if we can hoist " << I;
+ if (I.getInstrDescriptor()->ImplicitUses) {
+ DOUT << " * Instruction has implicit uses:\n";
+
+ const MRegisterInfo *MRI = TM->getRegisterInfo();
+ const unsigned *ImpUses = I.getInstrDescriptor()->ImplicitUses;
+
+ for (; *ImpUses; ++ImpUses)
+ DOUT << " -> " << MRI->getName(*ImpUses) << "\n";
+ }
+
+ if (I.getInstrDescriptor()->ImplicitDefs) {
+ DOUT << " * Instruction has implicit defines:\n";
+
+ const MRegisterInfo *MRI = TM->getRegisterInfo();
+ const unsigned *ImpDefs = I.getInstrDescriptor()->ImplicitDefs;
+
+ for (; *ImpDefs; ++ImpDefs)
+ DOUT << " -> " << MRI->getName(*ImpDefs) << "\n";
+ }
+
+ if (TII->hasUnmodelledSideEffects(&I))
+ DOUT << " * Instruction has side effects.\n";
+ });
// The instruction is loop invariant if all of its operands are loop-invariant
for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
const MachineOperand &MO = I.getOperand(i);
- if (!MO.isRegister() || !MO.isUse())
+ if (!(MO.isRegister() && MO.getReg() && MO.isUse()))
continue;
unsigned Reg = MO.getReg();
if (!MRegisterInfo::isVirtualRegister(Reg))
return false;
- assert(VRegDefs[Reg] && "Machine instr not mapped for this vreg?");
+ assert(RegInfo->getVRegDef(Reg)&&"Machine instr not mapped for this vreg?");
// If the loop contains the definition of an operand, then the instruction
// isn't loop invariant.
- if (CurLoop->contains(VRegDefs[Reg]->getParent()))
+ if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent()))
return false;
}
+ // Don't hoist something that has unmodelled side effects.
+ if (TII->hasUnmodelledSideEffects(&I)) return false;
+
// If we got this far, the instruction is loop invariant!
return true;
}
"The predecessor doesn't feed directly into the loop header!");
// Now move the instructions to the predecessor.
- MachineInstr *NewMI = MI.clone();
- MoveInstToEndOfBlock(MBB, NewMI);
-
- // Update VRegDefs.
- for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
- const MachineOperand &MO = NewMI->getOperand(i);
-
- if (MO.isRegister() && MO.isDef() &&
- MRegisterInfo::isVirtualRegister(MO.getReg()))
- VRegDefs[MO.getReg()] = NewMI;
- }
-
- // Hoisting was successful! Remove bothersome instruction now.
- MI.getParent()->remove(&MI);
+ MoveInstToEndOfBlock(MBB, MI.getParent(), &MI);
Changed = true;
}