-// $Id$
-//***************************************************************************
-// File:
-// InstrScheduling.cpp
-//
-// Purpose:
-//
-// History:
-// 7/23/01 - Vikram Adve - Created
-//**************************************************************************/
+//===- InstrScheduling.cpp - Generic Instruction Scheduling support -------===//
+//
+// This file implements the llvm/CodeGen/InstrScheduling.h interface, along with
+// generic support routines for instruction scheduling.
+//
+//===----------------------------------------------------------------------===//
-
-#include "llvm/CodeGen/InstrScheduling.h"
+#include "SchedPriorities.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineCodeForMethod.h"
-#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" // FIXME: Remove when AnalysisUsage sets can be symbolic!
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better
#include "llvm/Target/TargetMachine.h"
#include "llvm/BasicBlock.h"
-#include "SchedPriorities.h"
-#include <ext/hash_set>
+#include "Support/CommandLine.h"
#include <algorithm>
-#include <iterator>
-#include <iostream>
using std::cerr;
using std::vector;
-//************************* External Data Types *****************************/
+SchedDebugLevel_t SchedDebugLevel;
-cl::Enum<enum SchedDebugLevel_t> SchedDebugLevel("dsched", cl::NoFlags,
- "enable instruction scheduling debugging information",
- clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
- clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
- clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
- clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"), 0);
+static cl::opt<SchedDebugLevel_t, true>
+SDL_opt("dsched", cl::Hidden, cl::location(SchedDebugLevel),
+ cl::desc("enable instruction scheduling debugging information"),
+ cl::values(
+ clEnumValN(Sched_NoDebugInfo, "n", "disable debug output"),
+ clEnumValN(Sched_PrintMachineCode, "y", "print machine code after scheduling"),
+ clEnumValN(Sched_PrintSchedTrace, "t", "print trace of scheduling actions"),
+ clEnumValN(Sched_PrintSchedGraphs, "g", "print scheduling graphs"),
+ 0));
//************************* Internal Data Types *****************************/
class InstrSchedule;
class SchedulingManager;
-class DelaySlotInfo;
//----------------------------------------------------------------------
//----------------------------------------------------------------------
template<class _NodeType>
-class ScheduleIterator: public std::forward_iterator<_NodeType, ptrdiff_t> {
+class ScheduleIterator : public forward_iterator<_NodeType, ptrdiff_t> {
private:
unsigned cycleNum;
unsigned slotNum;
}
inline InstrGroup* getIGroup (cycles_t c) {
- if (c >= groups.size())
+ if ((unsigned)c >= groups.size())
groups.resize(c+1);
if (groups[c] == NULL)
groups[c] = new InstrGroup(nslots);
}
inline const InstrGroup* getIGroup (cycles_t c) const {
- assert(c < groups.size());
+ assert((unsigned)c < groups.size());
return groups[c];
}
class SchedulingManager: public NonCopyable {
public: // publicly accessible data members
- const unsigned int nslots;
- const MachineSchedInfo& schedInfo;
+ const unsigned nslots;
+ const TargetSchedInfo& schedInfo;
SchedPriorities& schedPrio;
InstrSchedule isched;
unsigned int totalInstrCount;
cycles_t curTime;
cycles_t nextEarliestIssueTime; // next cycle we can issue
- vector<std::hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
+ vector<hash_set<const SchedGraphNode*> > choicesForSlot; // indexed by slot#
vector<const SchedGraphNode*> choiceVec; // indexed by node ptr
vector<int> numInClass; // indexed by sched class
vector<cycles_t> nextEarliestStartTime; // indexed by opCode
- std::hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
+ hash_map<const SchedGraphNode*, DelaySlotInfo*> delaySlotInfoForBranches;
// indexed by branch node ptr
public:
- /*ctor*/ SchedulingManager (const TargetMachine& _target,
- const SchedGraph* graph,
- SchedPriorities& schedPrio);
- /*dtor*/ ~SchedulingManager () {}
+ SchedulingManager(const TargetMachine& _target, const SchedGraph* graph,
+ SchedPriorities& schedPrio);
+ ~SchedulingManager() {
+ for (hash_map<const SchedGraphNode*,
+ DelaySlotInfo*>::iterator I = delaySlotInfoForBranches.begin(),
+ E = delaySlotInfoForBranches.end(); I != E; ++I)
+ delete I->second;
+ }
//----------------------------------------------------------------------
// Simplify access to the machine instruction info
//----------------------------------------------------------------------
- inline const MachineInstrInfo& getInstrInfo () const {
+ inline const TargetInstrInfo& getInstrInfo () const {
return schedInfo.getInstrInfo();
}
}
inline unsigned getNumChoicesInClass (const InstrSchedClass& sc) const {
- assert(sc < (int) numInClass.size() && "Invalid op code or sched class!");
+ assert(sc < numInClass.size() && "Invalid op code or sched class!");
return numInClass[sc];
}
return choiceVec[i];
}
- inline std::hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
+ inline hash_set<const SchedGraphNode*>& getChoicesForSlot(unsigned slotNum) {
assert(slotNum < nslots);
return choicesForSlot[slotNum];
}
// Increment numInClass[c] for the sched class to which the instr belongs.
choiceVec.push_back(node);
const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
- assert(sc < (int) numInClass.size());
+ assert(sc < numInClass.size());
numInClass[sc]++;
}
// and decrement the instr count for the sched class to which it belongs
const InstrSchedClass& sc = schedInfo.getSchedClass(node->getOpCode());
- assert(sc < (int) numInClass.size());
+ assert(sc < numInClass.size());
numInClass[sc]--;
}
inline DelaySlotInfo* getDelaySlotInfoForInstr(const SchedGraphNode* bn,
bool createIfMissing=false)
{
- DelaySlotInfo* dinfo;
- std::hash_map<const SchedGraphNode*, DelaySlotInfo* >::const_iterator
+ hash_map<const SchedGraphNode*, DelaySlotInfo*>::const_iterator
I = delaySlotInfoForBranches.find(bn);
- if (I == delaySlotInfoForBranches.end())
- {
- if (createIfMissing)
- {
- dinfo = new DelaySlotInfo(bn,
- getInstrInfo().getNumDelaySlots(bn->getOpCode()));
- delaySlotInfoForBranches[bn] = dinfo;
- }
- else
- dinfo = NULL;
- }
- else
- dinfo = (*I).second;
-
- return dinfo;
+ if (I != delaySlotInfoForBranches.end())
+ return I->second;
+
+ if (!createIfMissing) return 0;
+
+ DelaySlotInfo *dinfo =
+ new DelaySlotInfo(bn, getInstrInfo().getNumDelaySlots(bn->getOpCode()));
+ return delaySlotInfoForBranches[bn] = dinfo;
}
private:
- /*ctor*/ SchedulingManager (); // Disable: DO NOT IMPLEMENT.
- void updateEarliestStartTimes(const SchedGraphNode* node,
- cycles_t schedTime);
+ SchedulingManager(); // DISABLED: DO NOT IMPLEMENT
+ void updateEarliestStartTimes(const SchedGraphNode* node, cycles_t schedTime);
};
curTime + 1 + schedInfo.numBubblesAfter(node->getOpCode()));
}
- const vector<MachineOpCode>*
+ const std::vector<MachineOpCode>&
conflictVec = schedInfo.getConflictList(node->getOpCode());
- if (conflictVec != NULL)
- for (unsigned i=0; i < conflictVec->size(); i++)
- {
- MachineOpCode toOp = (*conflictVec)[i];
- cycles_t est = schedTime + schedInfo.getMinIssueGap(node->getOpCode(),
- toOp);
- assert(toOp < (int) nextEarliestStartTime.size());
- if (nextEarliestStartTime[toOp] < est)
- nextEarliestStartTime[toOp] = est;
- }
+ for (unsigned i=0; i < conflictVec.size(); i++)
+ {
+ MachineOpCode toOp = conflictVec[i];
+ cycles_t est=schedTime + schedInfo.getMinIssueGap(node->getOpCode(),toOp);
+ assert(toOp < (int) nextEarliestStartTime.size());
+ if (nextEarliestStartTime[toOp] < est)
+ nextEarliestStartTime[toOp] = est;
+ }
}
//************************* Internal Functions *****************************/
// of the basic block, since they are not part of the schedule.
//
static void
-RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
+RecordSchedule(MachineBasicBlock &MBB, const SchedulingManager& S)
{
- MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
- const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
+ const TargetInstrInfo& mii = S.schedInfo.getInstrInfo();
#ifndef NDEBUG
// Lets make sure we didn't lose any instructions, except possibly
// some NOPs from delay slots. Also, PHIs are not included in the schedule.
unsigned numInstr = 0;
- for (MachineCodeForBasicBlock::iterator I=mvec.begin(); I != mvec.end(); ++I)
+ for (MachineBasicBlock::iterator I=MBB.begin(); I != MBB.end(); ++I)
if (! mii.isNop((*I)->getOpCode()) &&
! mii.isDummyPhiInstr((*I)->getOpCode()))
++numInstr;
return; // empty basic block!
// First find the dummy instructions at the start of the basic block
- MachineCodeForBasicBlock::iterator I = mvec.begin();
- for ( ; I != mvec.end(); ++I)
+ MachineBasicBlock::iterator I = MBB.begin();
+ for ( ; I != MBB.end(); ++I)
if (! mii.isDummyPhiInstr((*I)->getOpCode()))
break;
- // Erase all except the dummy PHI instructions from mvec, and
+ // Erase all except the dummy PHI instructions from MBB, and
// pre-allocate create space for the ones we will put back in.
- mvec.erase(I, mvec.end());
- mvec.reserve(mvec.size() + S.isched.getNumInstructions());
+ MBB.erase(I, MBB.end());
InstrSchedule::const_iterator NIend = S.isched.end();
for (InstrSchedule::const_iterator NI = S.isched.begin(); NI != NIend; ++NI)
- mvec.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
+ MBB.push_back(const_cast<MachineInstr*>((*NI)->getMachineInstr()));
}
return false;
// don't put a load-use dependence in the delay slot of a branch
- const MachineInstrInfo& mii = S.getInstrInfo();
+ const TargetInstrInfo& mii = S.getInstrInfo();
for (SchedGraphNode::const_iterator EI = node->beginInEdges();
EI != node->endInEdges(); ++EI)
SchedGraphNode* brNode,
vector<SchedGraphNode*>& sdelayNodeVec)
{
- const MachineInstrInfo& mii = S.getInstrInfo();
+ const TargetInstrInfo& mii = S.getInstrInfo();
unsigned ndelays =
mii.getNumDelaySlots(brNode->getOpCode());
// If not enough useful instructions were found, mark the NOPs to be used
// for filling delay slots, otherwise, otherwise just discard them.
//
-void
-ReplaceNopsWithUsefulInstr(SchedulingManager& S,
- SchedGraphNode* node,
- vector<SchedGraphNode*> sdelayNodeVec,
- SchedGraph* graph)
+static void ReplaceNopsWithUsefulInstr(SchedulingManager& S,
+ SchedGraphNode* node,
+ vector<SchedGraphNode*> sdelayNodeVec,
+ SchedGraph* graph)
{
vector<SchedGraphNode*> nopNodeVec; // this will hold unused NOPs
- const MachineInstrInfo& mii = S.getInstrInfo();
+ const TargetInstrInfo& mii = S.getInstrInfo();
const MachineInstr* brInstr = node->getMachineInstr();
unsigned ndelays= mii.getNumDelaySlots(brInstr->getOpCode());
assert(ndelays > 0 && "Unnecessary call to replace NOPs");
// fill delay slots, otherwise, just discard them.
//
unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
- MachineCodeForBasicBlock& bbMvec = node->getBB()->getMachineInstrVec();
- assert(bbMvec[firstDelaySlotIdx - 1] == brInstr &&
+ MachineBasicBlock& MBB = node->getMachineBasicBlock();
+ assert(MBB[firstDelaySlotIdx - 1] == brInstr &&
"Incorrect instr. index in basic block for brInstr");
// First find all useful instructions already in the delay slots
// and USE THEM. We'll throw away the unused alternatives below
//
for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
- if (! mii.isNop(bbMvec[i]->getOpCode()))
+ if (! mii.isNop(MBB[i]->getOpCode()))
sdelayNodeVec.insert(sdelayNodeVec.begin(),
- graph->getGraphNodeForInstr(bbMvec[i]));
+ graph->getGraphNodeForInstr(MBB[i]));
// Then find the NOPs and keep only as many as are needed.
// Put the rest in nopNodeVec to be deleted.
for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
- if (mii.isNop(bbMvec[i]->getOpCode()))
+ if (mii.isNop(MBB[i]->getOpCode()))
if (sdelayNodeVec.size() < ndelays)
- sdelayNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
+ sdelayNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
else
- nopNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
-
+ {
+ nopNodeVec.push_back(graph->getGraphNodeForInstr(MBB[i]));
+
+ //remove the MI from the Machine Code For Instruction
+ TerminatorInst *TI = MBB.getBasicBlock()->getTerminator();
+ MachineCodeForInstruction& llvmMvec =
+ MachineCodeForInstruction::get((Instruction *)TI);
+
+ for(MachineCodeForInstruction::iterator mciI=llvmMvec.begin(),
+ mciE=llvmMvec.end(); mciI!=mciE; ++mciI){
+ if (*mciI==MBB[i])
+ llvmMvec.erase(mciI);
+ }
+ }
+
assert(sdelayNodeVec.size() >= ndelays);
// If some delay slots were already filled, throw away that many new choices
// regalloc.
//
static void
-ChooseInstructionsForDelaySlots(SchedulingManager& S,
- const BasicBlock *bb,
+ChooseInstructionsForDelaySlots(SchedulingManager& S, MachineBasicBlock &MBB,
SchedGraph *graph)
{
- const MachineInstrInfo& mii = S.getInstrInfo();
- const TerminatorInst *termInstr = bb->getTerminator();
+ const TargetInstrInfo& mii = S.getInstrInfo();
+
+ Instruction *termInstr = (Instruction*)MBB.getBasicBlock()->getTerminator();
MachineCodeForInstruction &termMvec=MachineCodeForInstruction::get(termInstr);
vector<SchedGraphNode*> delayNodeVec;
const MachineInstr* brInstr = NULL;
- assert(termInstr->getOpcode() != Instruction::Call
- && "Call used as terminator?");
-
if (termInstr->getOpcode() != Instruction::Ret)
{
// To find instructions that need delay slots without searching the full
// Simply passing in an empty delayNodeVec will have this effect.
//
delayNodeVec.clear();
- const MachineCodeForBasicBlock& bbMvec = bb->getMachineInstrVec();
- for (unsigned i=0; i < bbMvec.size(); i++)
- if (bbMvec[i] != brInstr &&
- mii.getNumDelaySlots(bbMvec[i]->getOpCode()) > 0)
+ for (unsigned i=0; i < MBB.size(); ++i)
+ if (MBB[i] != brInstr &&
+ mii.getNumDelaySlots(MBB[i]->getOpCode()) > 0)
{
- SchedGraphNode* node = graph->getGraphNodeForInstr(bbMvec[i]);
+ SchedGraphNode* node = graph->getGraphNodeForInstr(MBB[i]);
ReplaceNopsWithUsefulInstr(S, node, delayNodeVec, graph);
}
}
//---------------------------------------------------------------------------
namespace {
- class InstructionSchedulingWithSSA : public MethodPass {
- const TargetMachine &Target;
+ class InstructionSchedulingWithSSA : public FunctionPass {
+ const TargetMachine ⌖
public:
- inline InstructionSchedulingWithSSA(const TargetMachine &T) : Target(T) {}
+ inline InstructionSchedulingWithSSA(const TargetMachine &T) : target(T) {}
- // getAnalysisUsageInfo - We use LiveVarInfo...
- virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
- Pass::AnalysisSet &Destroyed,
- Pass::AnalysisSet &Provided) {
- Requires.push_back(MethodLiveVarInfo::ID);
+ const char *getPassName() const { return "Instruction Scheduling"; }
+
+ // getAnalysisUsage - We use LiveVarInfo...
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<FunctionLiveVarInfo>();
+ AU.setPreservesCFG();
}
+
+ bool runOnFunction(Function &F);
+ };
+} // end anonymous namespace
- bool runOnMethod(Method *M) {
- cerr << "Instr scheduling failed for method " << ((Value*)M)->getName()
- << "\n\n";
- SchedGraphSet graphSet(M, Target);
+
+bool InstructionSchedulingWithSSA::runOnFunction(Function &F)
+{
+ SchedGraphSet graphSet(&F, target);
- if (SchedDebugLevel >= Sched_PrintSchedGraphs) {
- cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
- graphSet.dump();
- }
+ if (SchedDebugLevel >= Sched_PrintSchedGraphs)
+ {
+ cerr << "\n*** SCHEDULING GRAPHS FOR INSTRUCTION SCHEDULING\n";
+ graphSet.dump();
+ }
- for (SchedGraphSet::const_iterator GI=graphSet.begin();
- GI != graphSet.end(); ++GI) {
- SchedGraph* graph = GI->second;
- const vector<const BasicBlock*> &bbvec = graph->getBasicBlocks();
- assert(bbvec.size() == 1 && "Cannot schedule multiple basic blocks");
- const BasicBlock* bb = bbvec[0];
+ for (SchedGraphSet::const_iterator GI=graphSet.begin(), GE=graphSet.end();
+ GI != GE; ++GI)
+ {
+ SchedGraph* graph = (*GI);
+ MachineBasicBlock &MBB = graph->getBasicBlock();
- if (SchedDebugLevel >= Sched_PrintSchedTrace)
- cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
+ if (SchedDebugLevel >= Sched_PrintSchedTrace)
+ cerr << "\n*** TRACE OF INSTRUCTION SCHEDULING OPERATIONS\n\n";
- // expensive!
- SchedPriorities schedPrio(M, graph, getAnalysis<MethodLiveVarInfo>());
- SchedulingManager S(Target, graph, schedPrio);
-
- ChooseInstructionsForDelaySlots(S, bb, graph); // modifies graph
-
- ForwardListSchedule(S); // computes schedule in S
-
- RecordSchedule(GI->first, S); // records schedule in BB
- }
-
- if (SchedDebugLevel >= Sched_PrintMachineCode) {
- cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
- MachineCodeForMethod::get(M).dump();
- }
+ // expensive!
+ SchedPriorities schedPrio(&F, graph,getAnalysis<FunctionLiveVarInfo>());
+ SchedulingManager S(target, graph, schedPrio);
+
+ ChooseInstructionsForDelaySlots(S, MBB, graph); // modifies graph
+ ForwardListSchedule(S); // computes schedule in S
+ RecordSchedule(MBB, S); // records schedule in BB
+ }
- return false;
+ if (SchedDebugLevel >= Sched_PrintMachineCode)
+ {
+ cerr << "\n*** Machine instructions after INSTRUCTION SCHEDULING\n";
+ MachineFunction::get(&F).dump();
}
- };
-} // end anonymous namespace
+
+ return false;
+}
+
-MethodPass *createInstructionSchedulingWithSSAPass(const TargetMachine &T) {
- return new InstructionSchedulingWithSSA(T);
+Pass *createInstructionSchedulingWithSSAPass(const TargetMachine &tgt) {
+ return new InstructionSchedulingWithSSA(tgt);
}
projects / oota-llvm.git / blobdiff