X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FInstrSched%2FSchedGraph.cpp;h=00b48d537d3eee8089fb54d58f2dd5fd1ee442b6;hb=551ccae044b0ff658fe629dd67edd5ffe75d10e8;hp=3c819f6bc7d3322c69e93ab873e0cdfd92336a5b;hpb=b26bcc5087029ffe8037ed9036ff74430c6054cf;p=oota-llvm.git diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp index 3c819f6bc7d..00b48d537d3 100644 --- a/lib/CodeGen/InstrSched/SchedGraph.cpp +++ b/lib/CodeGen/InstrSched/SchedGraph.cpp @@ -1,599 +1,594 @@ -/* - **************************************************************************** - * File: - * SchedGraph.cpp - * - * Purpose: - * Scheduling graph based on SSA graph plus extra dependence edges - * capturing dependences due to machine resources (machine registers, - * CC registers, and any others). - * - * History: - * 7/20/01 - Vikram Adve - Created - ***************************************************************************/ - -#include "llvm/InstrTypes.h" -#include "llvm/Instruction.h" -#include "llvm/BasicBlock.h" -#include "llvm/Method.h" -#include "llvm/CodeGen/SchedGraph.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/Target/Machine.h" -#include "llvm/Support/StringExtras.h" -#include - -//************************* Class Implementations **************************/ - +//===- SchedGraph.cpp - Scheduling Graph Implementation -------------------===// // -// class SchedGraphEdge +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. // +//===----------------------------------------------------------------------===// +// +// Scheduling graph based on SSA graph plus extra dependence edges capturing +// dependences due to machine resources (machine registers, CC registers, and +// any others). +// +//===----------------------------------------------------------------------===// + +#include "SchedGraph.h" +#include "llvm/Function.h" +#include "llvm/Instructions.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "../../Target/SparcV9/MachineCodeForInstruction.h" +#include "../../Target/SparcV9/SparcV9RegInfo.h" +#include "../../Target/SparcV9/SparcV9InstrInfo.h" +#include "llvm/ADT/STLExtras.h" +#include + +namespace llvm { + +//*********************** Internal Data Structures *************************/ + +// The following two types need to be classes, not typedefs, so we can use +// opaque declarations in SchedGraph.h +// +struct RefVec: public std::vector > { + typedef std::vector >::iterator iterator; + typedef + std::vector >::const_iterator const_iterator; +}; -/*ctor*/ -SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - SchedGraphEdgeDepType _depType, - DataDepOrderType _depOrderType, - int _minDelay) - : src(_src), - sink(_sink), - depType(_depType), - depOrderType(_depOrderType), - val(NULL), - minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()) -{ - src->addOutEdge(this); - sink->addInEdge(this); -} - - -/*ctor*/ -SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - Value* _val, - DataDepOrderType _depOrderType, - int _minDelay) - : src(_src), - sink(_sink), - depType(DefUseDep), - depOrderType(_depOrderType), - val(_val), - minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()) -{ - src->addOutEdge(this); - sink->addInEdge(this); -} - - -/*ctor*/ -SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - unsigned int _regNum, - DataDepOrderType _depOrderType, - int _minDelay) - : src(_src), - sink(_sink), - depType(MachineRegister), - depOrderType(_depOrderType), - minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), - machineRegNum(_regNum) -{ - src->addOutEdge(this); - sink->addInEdge(this); -} - - -/*ctor*/ -SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src, - SchedGraphNode* _sink, - ResourceId _resourceId, - int _minDelay) - : src(_src), - sink(_sink), - depType(MachineResource), - depOrderType(NonDataDep), - minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()), - resourceId(_resourceId) -{ - src->addOutEdge(this); - sink->addInEdge(this); -} +struct RegToRefVecMap: public hash_map { + typedef hash_map:: iterator iterator; + typedef hash_map::const_iterator const_iterator; +}; -void SchedGraphEdge::dump(int indent=0) const { - printIndent(indent); cout << *this; -} +struct ValueToDefVecMap: public hash_map { + typedef hash_map:: iterator iterator; + typedef hash_map::const_iterator const_iterator; +}; // // class SchedGraphNode // -/*ctor*/ -SchedGraphNode::SchedGraphNode(unsigned int _nodeId, - const Instruction* _instr, - const MachineInstr* _minstr, - const TargetMachine& target) - : nodeId(_nodeId), - instr(_instr), - minstr(_minstr), - latency(0) -{ - if (minstr) - { - MachineOpCode mopCode = minstr->getOpCode(); - latency = target.getInstrInfo().hasResultInterlock(mopCode) - ? target.getInstrInfo().minLatency(mopCode) - : target.getInstrInfo().maxLatency(mopCode); - } -} - - -/*dtor*/ -SchedGraphNode::~SchedGraphNode() -{ - // a node deletes its outgoing edges only - for (unsigned i=0, N=outEdges.size(); i < N; i++) - delete outEdges[i]; -} - -void SchedGraphNode::dump(int indent=0) const { - printIndent(indent); cout << *this; -} - - -inline void -SchedGraphNode::addInEdge(SchedGraphEdge* edge) -{ - inEdges.push_back(edge); -} - - -inline void -SchedGraphNode::addOutEdge(SchedGraphEdge* edge) -{ - outEdges.push_back(edge); -} - -inline void -SchedGraphNode::removeInEdge(const SchedGraphEdge* edge) -{ - assert(edge->getSink() == this); - for (iterator I = beginInEdges(); I != endInEdges(); ++I) - if ((*I) == edge) - { - inEdges.erase(I); - break; - } -} - -inline void -SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge) -{ - assert(edge->getSrc() == this); - for (iterator I = beginOutEdges(); I != endOutEdges(); ++I) - if ((*I) == edge) - { - outEdges.erase(I); - break; - } +SchedGraphNode::SchedGraphNode(unsigned NID, MachineBasicBlock *mbb, + int indexInBB, const TargetMachine& Target) + : SchedGraphNodeCommon(NID,indexInBB), MBB(mbb), MI(0) { + if (mbb) { + MachineBasicBlock::iterator I = MBB->begin(); + std::advance(I, indexInBB); + MI = I; + + MachineOpCode mopCode = MI->getOpcode(); + latency = Target.getInstrInfo()->hasResultInterlock(mopCode) + ? Target.getInstrInfo()->minLatency(mopCode) + : Target.getInstrInfo()->maxLatency(mopCode); + } } -void -SchedGraphNode::eraseAllEdges() -{ - // Disconnect and delete all in-edges and out-edges for the node. - // Note that we delete the in-edges too since they have been - // disconnected from the source node and will not be deleted there. - for (iterator I = beginInEdges(); I != endInEdges(); ++I) - { - (*I)->getSrc()->removeOutEdge(*I); - delete *I; - } - for (iterator I = beginOutEdges(); I != endOutEdges(); ++I) - { - (*I)->getSink()->removeInEdge(*I); - delete *I; - } - inEdges.clear(); - outEdges.clear(); +// +// Method: SchedGraphNode Destructor +// +// Description: +// Free memory allocated by the SchedGraphNode object. +// +// Notes: +// Do not delete the edges here. The base class will take care of that. +// Only handle subclass specific stuff here (where currently there is +// none). +// +SchedGraphNode::~SchedGraphNode() { } - // // class SchedGraph // - - -/*ctor*/ -SchedGraph::SchedGraph(const BasicBlock* bb, - const TargetMachine& target) -{ - bbVec.push_back(bb); - this->buildGraph(target); +SchedGraph::SchedGraph(MachineBasicBlock &mbb, const TargetMachine& target) + : MBB(mbb) { + buildGraph(target); } - -/*dtor*/ -SchedGraph::~SchedGraph() -{ - // delete all the nodes. each node deletes its out-edges. - for (iterator I=begin(); I != end(); ++I) - delete (*I).second; +// +// Method: SchedGraph Destructor +// +// Description: +// This method deletes memory allocated by the SchedGraph object. +// +// Notes: +// Do not delete the graphRoot or graphLeaf here. The base class handles +// that bit of work. +// +SchedGraph::~SchedGraph() { + for (const_iterator I = begin(); I != end(); ++I) + delete I->second; } - -void -SchedGraph::dump() const -{ - cout << " Sched Graph for Basic Blocks: "; - for (unsigned i=0, N=bbVec.size(); i < N; i++) - { - cout << (bbVec[i]->hasName()? bbVec[i]->getName() : "block") - << " (" << bbVec[i] << ")" - << ((i == N-1)? "" : ", "); - } - - cout << endl << endl << " Actual Root nodes : "; - for (unsigned i=0, N=graphRoot->outEdges.size(); i < N; i++) - cout << graphRoot->outEdges[i]->getSink()->getNodeId() - << ((i == N-1)? "" : ", "); - - cout << endl << " Graph Nodes:" << endl; - for (const_iterator I=begin(); I != end(); ++I) - cout << endl << * (*I).second; - - cout << endl; +void SchedGraph::dump() const { + std::cerr << " Sched Graph for Basic Block: " + << MBB.getBasicBlock()->getName() + << " (" << *MBB.getBasicBlock() << ")" + << "\n\n Actual Root nodes: "; + for (SchedGraphNodeCommon::const_iterator I = graphRoot->beginOutEdges(), + E = graphRoot->endOutEdges(); + I != E; ++I) { + std::cerr << (*I)->getSink ()->getNodeId (); + if (I + 1 != E) { std::cerr << ", "; } + } + std::cerr << "\n Graph Nodes:\n"; + for (const_iterator I = begin(), E = end(); I != E; ++I) + std::cerr << "\n" << *I->second; + std::cerr << "\n"; } - -void -SchedGraph::addDummyEdges() -{ - assert(graphRoot->outEdges.size() == 0); - - for (const_iterator I=begin(); I != end(); ++I) - { - SchedGraphNode* node = (*I).second; - assert(node != graphRoot && node != graphLeaf); - if (node->beginInEdges() == node->endInEdges()) - (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - if (node->beginOutEdges() == node->endOutEdges()) - (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - } +void SchedGraph::addDummyEdges() { + assert(graphRoot->getNumOutEdges() == 0); + + for (const_iterator I=begin(); I != end(); ++I) { + SchedGraphNode* node = (*I).second; + assert(node != graphRoot && node != graphLeaf); + if (node->beginInEdges() == node->endInEdges()) + (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep, + SchedGraphEdge::NonDataDep, 0); + if (node->beginOutEdges() == node->endOutEdges()) + (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep, + SchedGraphEdge::NonDataDep, 0); + } } -void -SchedGraph::addCDEdges(const TerminatorInst* term, - const TargetMachine& target) -{ - const MachineInstrInfo& mii = target.getInstrInfo(); - MachineCodeForVMInstr& termMvec = term->getMachineInstrVec(); +void SchedGraph::addCDEdges(const TerminatorInst* term, + const TargetMachine& target) { + const TargetInstrInfo& mii = *target.getInstrInfo(); + MachineCodeForInstruction &termMvec = MachineCodeForInstruction::get(term); // Find the first branch instr in the sequence of machine instrs for term // unsigned first = 0; - while (! mii.isBranch(termMvec[first]->getOpCode())) + while (! mii.isBranch(termMvec[first]->getOpcode()) && + ! mii.isReturn(termMvec[first]->getOpcode())) ++first; assert(first < termMvec.size() && - "No branch instructions for BR? Ok, but weird! Delete assertion."); + "No branch instructions for terminator? Ok, but weird!"); if (first == termMvec.size()) return; - SchedGraphNode* firstBrNode = this->getGraphNodeForInstr(termMvec[first]); + SchedGraphNode* firstBrNode = getGraphNodeForInstr(termMvec[first]); // Add CD edges from each instruction in the sequence to the // *last preceding* branch instr. in the sequence + // Use a latency of 0 because we only need to prevent out-of-order issue. // - for (int i = (int) termMvec.size()-1; i > (int) first; i--) - { - SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]); - assert(toNode && "No node for instr generated for branch?"); - - for (int j = i-1; j >= 0; j--) - if (mii.isBranch(termMvec[j]->getOpCode())) - { - SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]); - assert(brNode && "No node for instr generated for branch?"); - (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - break; // only one incoming edge is enough - } - } + for (unsigned i = termMvec.size(); i > first+1; --i) { + SchedGraphNode* toNode = getGraphNodeForInstr(termMvec[i-1]); + assert(toNode && "No node for instr generated for branch/ret?"); + + for (unsigned j = i-1; j != 0; --j) + if (mii.isBranch(termMvec[j-1]->getOpcode()) || + mii.isReturn(termMvec[j-1]->getOpcode())) { + SchedGraphNode* brNode = getGraphNodeForInstr(termMvec[j-1]); + assert(brNode && "No node for instr generated for branch/ret?"); + (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep, + SchedGraphEdge::NonDataDep, 0); + break; // only one incoming edge is enough + } + } // Add CD edges from each instruction preceding the first branch - // to the first branch + // to the first branch. Use a latency of 0 as above. // - for (int i = first-1; i >= 0; i--) - { - SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]); - assert(fromNode && "No node for instr generated for branch?"); - (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - } + for (unsigned i = first; i != 0; --i) { + SchedGraphNode* fromNode = getGraphNodeForInstr(termMvec[i-1]); + assert(fromNode && "No node for instr generated for branch?"); + (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep, + SchedGraphEdge::NonDataDep, 0); + } - // Now add CD edges to the first branch instruction in the sequence - // from all preceding instructions in the basic block. + // Now add CD edges to the first branch instruction in the sequence from + // all preceding instructions in the basic block. Use 0 latency again. // - const BasicBlock* bb = term->getParent(); - for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II) - { - if ((*II) == (const Instruction*) term) // special case, handled above - continue; - - assert(! (*II)->isTerminator() && "Two terminators in basic block?"); + for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ++I){ + if (&*I == termMvec[first]) // reached the first branch + break; + + SchedGraphNode* fromNode = getGraphNodeForInstr(I); + if (fromNode == NULL) + continue; // dummy instruction, e.g., PHI + + (void) new SchedGraphEdge(fromNode, firstBrNode, + SchedGraphEdge::CtrlDep, + SchedGraphEdge::NonDataDep, 0); - const MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec(); - for (unsigned i=0, N=mvec.size(); i < N; i++) - { - SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]); - if (fromNode == NULL) - continue; // dummy instruction, e.g., PHI - - (void) new SchedGraphEdge(fromNode, firstBrNode, - SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - - // If we find any other machine instructions (other than due to - // the terminator) that also have delay slots, add an outgoing edge - // from the instruction to the instructions in the delay slots. - // - unsigned d = mii.getNumDelaySlots(mvec[i]->getOpCode()); - assert(i+d < N && "Insufficient delay slots for instruction?"); - - for (unsigned j=1; j <= d; j++) - { - SchedGraphNode* toNode = this->getGraphNodeForInstr(mvec[i+j]); - assert(toNode && "No node for machine instr in delay slot?"); - (void) new SchedGraphEdge(fromNode, toNode, - SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - } - } + // If we find any other machine instructions (other than due to + // the terminator) that also have delay slots, add an outgoing edge + // from the instruction to the instructions in the delay slots. + // + unsigned d = mii.getNumDelaySlots(I->getOpcode()); + + MachineBasicBlock::iterator J = I; ++J; + for (unsigned j=1; j <= d; j++, ++J) { + SchedGraphNode* toNode = this->getGraphNodeForInstr(J); + assert(toNode && "No node for machine instr in delay slot?"); + (void) new SchedGraphEdge(fromNode, toNode, + SchedGraphEdge::CtrlDep, + SchedGraphEdge::NonDataDep, 0); } + } } +static const int SG_LOAD_REF = 0; +static const int SG_STORE_REF = 1; +static const int SG_CALL_REF = 2; + +static const unsigned int SG_DepOrderArray[][3] = { + { SchedGraphEdge::NonDataDep, + SchedGraphEdge::AntiDep, + SchedGraphEdge::AntiDep }, + { SchedGraphEdge::TrueDep, + SchedGraphEdge::OutputDep, + SchedGraphEdge::TrueDep | SchedGraphEdge::OutputDep }, + { SchedGraphEdge::TrueDep, + SchedGraphEdge::AntiDep | SchedGraphEdge::OutputDep, + SchedGraphEdge::TrueDep | SchedGraphEdge::AntiDep + | SchedGraphEdge::OutputDep } +}; + -void -SchedGraph::addMemEdges(const vector& memVec, - const TargetMachine& target) -{ - const MachineInstrInfo& mii = target.getInstrInfo(); +// Add a dependence edge between every pair of machine load/store/call +// instructions, where at least one is a store or a call. +// Use latency 1 just to ensure that memory operations are ordered; +// latency does not otherwise matter (true dependences enforce that). +// +void SchedGraph::addMemEdges(const std::vector& memNodeVec, + const TargetMachine& target) { + const TargetInstrInfo& mii = *target.getInstrInfo(); - for (unsigned im=0, NM=memVec.size(); im < NM; im++) - { - const Instruction* fromInstr = memVec[im]; - bool fromIsLoad = fromInstr->getOpcode() == Instruction::Load; + // Instructions in memNodeVec are in execution order within the basic block, + // so simply look at all pairs i]>. + // + for (unsigned im=0, NM=memNodeVec.size(); im < NM; im++) { + MachineOpCode fromOpCode = memNodeVec[im]->getOpcode(); + int fromType = (mii.isCall(fromOpCode)? SG_CALL_REF + : (mii.isLoad(fromOpCode)? SG_LOAD_REF + : SG_STORE_REF)); + for (unsigned jm=im+1; jm < NM; jm++) { + MachineOpCode toOpCode = memNodeVec[jm]->getOpcode(); + int toType = (mii.isCall(toOpCode)? SG_CALL_REF + : (mii.isLoad(toOpCode)? SG_LOAD_REF + : SG_STORE_REF)); - for (unsigned jm=im+1; jm < NM; jm++) - { - const Instruction* toInstr = memVec[jm]; - bool toIsLoad = toInstr->getOpcode() == Instruction::Load; - SchedGraphEdge::DataDepOrderType depOrderType; - - if (fromIsLoad) - { - if (toIsLoad) continue; // both instructions are loads - depOrderType = SchedGraphEdge::AntiDep; - } - else - { - depOrderType = (toIsLoad)? SchedGraphEdge::TrueDep - : SchedGraphEdge::OutputDep; - } - - MachineCodeForVMInstr& fromInstrMvec=fromInstr->getMachineInstrVec(); - MachineCodeForVMInstr& toInstrMvec = toInstr->getMachineInstrVec(); - - // We have two VM memory instructions, and at least one is a store. - // Add edges between all machine load/store instructions. - // - for (unsigned i=0, N=fromInstrMvec.size(); i < N; i++) - { - MachineOpCode fromOpCode = fromInstrMvec[i]->getOpCode(); - if (mii.isLoad(fromOpCode) || mii.isStore(fromOpCode)) - { - SchedGraphNode* fromNode = - this->getGraphNodeForInstr(fromInstrMvec[i]); - assert(fromNode && "No node for memory instr?"); - - for (unsigned j=0, M=toInstrMvec.size(); j < M; j++) - { - MachineOpCode toOpCode = toInstrMvec[j]->getOpCode(); - if (mii.isLoad(toOpCode) || mii.isStore(toOpCode)) - { - SchedGraphNode* toNode = - this->getGraphNodeForInstr(toInstrMvec[j]); - assert(toNode && "No node for memory instr?"); - - (void) new SchedGraphEdge(fromNode, toNode, - SchedGraphEdge::MemoryDep, - depOrderType, 1); - } - } - } - } - } + if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF) + (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm], + SchedGraphEdge::MemoryDep, + SG_DepOrderArray[fromType][toType], 1); } -} - - -typedef vector< pair > RegRefVec; + } +} -// The following needs to be a class, not a typedef, so we can use -// an opaque declaration in SchedGraph.h -class NodeToRegRefMap: public hash_map { - typedef hash_map:: iterator iterator; - typedef hash_map::const_iterator const_iterator; -}; +// Add edges from/to CC reg instrs to/from call instrs. +// Essentially this prevents anything that sets or uses a CC reg from being +// reordered w.r.t. a call. +// Use a latency of 0 because we only need to prevent out-of-order issue, +// like with control dependences. +// +void SchedGraph::addCallDepEdges(const std::vector& callDepNodeVec, + const TargetMachine& target) { + const TargetInstrInfo& mii = *target.getInstrInfo(); + + // Instructions in memNodeVec are in execution order within the basic block, + // so simply look at all pairs i]>. + // + for (unsigned ic=0, NC=callDepNodeVec.size(); ic < NC; ic++) + if (mii.isCall(callDepNodeVec[ic]->getOpcode())) { + // Add SG_CALL_REF edges from all preds to this instruction. + for (unsigned jc=0; jc < ic; jc++) + (void) new SchedGraphEdge(callDepNodeVec[jc], callDepNodeVec[ic], + SchedGraphEdge::MachineRegister, + MachineIntRegsRID, 0); + + // And do the same from this instruction to all successors. + for (unsigned jc=ic+1; jc < NC; jc++) + (void) new SchedGraphEdge(callDepNodeVec[ic], callDepNodeVec[jc], + SchedGraphEdge::MachineRegister, + MachineIntRegsRID, 0); + } + +#ifdef CALL_DEP_NODE_VEC_CANNOT_WORK + // Find the call instruction nodes and put them in a vector. + std::vector callNodeVec; + for (unsigned im=0, NM=memNodeVec.size(); im < NM; im++) + if (mii.isCall(memNodeVec[im]->getOpcode())) + callNodeVec.push_back(memNodeVec[im]); + + // Now walk the entire basic block, looking for CC instructions *and* + // call instructions, and keep track of the order of the instructions. + // Use the call node vec to quickly find earlier and later call nodes + // relative to the current CC instruction. + // + int lastCallNodeIdx = -1; + for (unsigned i=0, N=bbMvec.size(); i < N; i++) + if (mii.isCall(bbMvec[i]->getOpcode())) { + ++lastCallNodeIdx; + for ( ; lastCallNodeIdx < (int)callNodeVec.size(); ++lastCallNodeIdx) + if (callNodeVec[lastCallNodeIdx]->getMachineInstr() == bbMvec[i]) + break; + assert(lastCallNodeIdx < (int)callNodeVec.size() && "Missed Call?"); + } + else if (mii.isCCInstr(bbMvec[i]->getOpcode())) { + // Add incoming/outgoing edges from/to preceding/later calls + SchedGraphNode* ccNode = this->getGraphNodeForInstr(bbMvec[i]); + int j=0; + for ( ; j <= lastCallNodeIdx; j++) + (void) new SchedGraphEdge(callNodeVec[j], ccNode, + MachineCCRegsRID, 0); + for ( ; j < (int) callNodeVec.size(); j++) + (void) new SchedGraphEdge(ccNode, callNodeVec[j], + MachineCCRegsRID, 0); + } +#endif +} -void -SchedGraph::addMachineRegEdges(NodeToRegRefMap& regToRefVecMap, - const TargetMachine& target) -{ - assert(bbVec.size() == 1 && "Only handling a single basic block here"); - - // This assumes that such hardwired registers are never allocated - // to any LLVM value (since register allocation happens later), i.e., - // any uses or defs of this register have been made explicit! - // Also assumes that two registers with different numbers are +void SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap, + const TargetMachine& target) { + // This code assumes that two registers with different numbers are // not aliased! // - for (NodeToRegRefMap::iterator I = regToRefVecMap.begin(); - I != regToRefVecMap.end(); ++I) - { - int regNum = (*I).first; - RegRefVec& regRefVec = (*I).second; - - // regRefVec is ordered by control flow order in the basic block - int lastDefIdx = -1; - for (unsigned i=0; i < regRefVec.size(); ++i) - { - SchedGraphNode* node = regRefVec[i].first; - bool isDef = regRefVec[i].second; + for (RegToRefVecMap::iterator I = regToRefVecMap.begin(); + I != regToRefVecMap.end(); ++I) { + int regNum = (*I).first; + RefVec& regRefVec = (*I).second; + + // regRefVec is ordered by control flow order in the basic block + for (unsigned i=0; i < regRefVec.size(); ++i) { + SchedGraphNode* node = regRefVec[i].first; + unsigned int opNum = regRefVec[i].second; + const MachineOperand& mop = + node->getMachineInstr()->getExplOrImplOperand(opNum); + bool isDef = mop.isDef() && !mop.isUse(); + bool isDefAndUse = mop.isDef() && mop.isUse(); + + for (unsigned p=0; p < i; ++p) { + SchedGraphNode* prevNode = regRefVec[p].first; + if (prevNode != node) { + unsigned int prevOpNum = regRefVec[p].second; + const MachineOperand& prevMop = + prevNode->getMachineInstr()->getExplOrImplOperand(prevOpNum); + bool prevIsDef = prevMop.isDef() && !prevMop.isUse(); + bool prevIsDefAndUse = prevMop.isDef() && prevMop.isUse(); + if (isDef) { + if (prevIsDef) + new SchedGraphEdge(prevNode, node, regNum, + SchedGraphEdge::OutputDep); + if (!prevIsDef || prevIsDefAndUse) + new SchedGraphEdge(prevNode, node, regNum, + SchedGraphEdge::AntiDep); + } - if (isDef) - { // Each def gets an output edge from the last def - if (lastDefIdx > 0) - new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum, - SchedGraphEdge::OutputDep); - - // Also, an anti edge from all uses *since* the last def, - // But don't add edge from an instruction to itself! - for (int u = 1 + lastDefIdx; u < (int) i; u++) - if (regRefVec[u].first != node) - new SchedGraphEdge(regRefVec[u].first, node, regNum, - SchedGraphEdge::AntiDep); - } - else - { // Each use gets a true edge from the last def - if (lastDefIdx > 0) - new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum); - } - } + if (prevIsDef) + if (!isDef || isDefAndUse) + new SchedGraphEdge(prevNode, node, regNum, + SchedGraphEdge::TrueDep); + } + } } + } } -void -SchedGraph::addSSAEdge(SchedGraphNode* node, - Value* val, - const TargetMachine& target) -{ - if (!val->isInstruction()) return; +// Adds dependences to/from refNode from/to all other defs +// in the basic block. refNode may be a use, a def, or both. +// We do not consider other uses because we are not building use-use deps. +// +void SchedGraph::addEdgesForValue(SchedGraphNode* refNode, + const RefVec& defVec, + const Value* defValue, + bool refNodeIsDef, + bool refNodeIsUse, + const TargetMachine& target) { + // Add true or output dep edges from all def nodes before refNode in BB. + // Add anti or output dep edges to all def nodes after refNode. + for (RefVec::const_iterator I=defVec.begin(), E=defVec.end(); I != E; ++I) { + if ((*I).first == refNode) + continue; // Dont add any self-loops + + if ((*I).first->getOrigIndexInBB() < refNode->getOrigIndexInBB()) { + // (*).first is before refNode + if (refNodeIsDef && !refNodeIsUse) + (void) new SchedGraphEdge((*I).first, refNode, defValue, + SchedGraphEdge::OutputDep); + if (refNodeIsUse) + (void) new SchedGraphEdge((*I).first, refNode, defValue, + SchedGraphEdge::TrueDep); + } else { + // (*).first is after refNode + if (refNodeIsDef && !refNodeIsUse) + (void) new SchedGraphEdge(refNode, (*I).first, defValue, + SchedGraphEdge::OutputDep); + if (refNodeIsUse) + (void) new SchedGraphEdge(refNode, (*I).first, defValue, + SchedGraphEdge::AntiDep); + } + } +} + - const Instruction* thisVMInstr = node->getInstr(); - const Instruction* defVMInstr = (const Instruction*) val; - - // Phi instructions are the only ones that produce a value but don't get - // any non-dummy machine instructions. Return here as an optimization. - // - if (defVMInstr->isPHINode()) +void SchedGraph::addEdgesForInstruction(const MachineInstr& MI, + const ValueToDefVecMap& valueToDefVecMap, + const TargetMachine& target) { + SchedGraphNode* node = getGraphNodeForInstr(&MI); + if (node == NULL) return; - // Now add the graph edge for the appropriate machine instruction(s). - // Note that multiple machine instructions generated for the - // def VM instruction may modify the register for the def value. + // Add edges for all operands of the machine instruction. // - MachineCodeForVMInstr& defMvec = defVMInstr->getMachineInstrVec(); - const MachineInstrInfo& mii = target.getInstrInfo(); + for (unsigned i = 0, numOps = MI.getNumOperands(); i != numOps; ++i) { + switch (MI.getOperand(i).getType()) { + case MachineOperand::MO_VirtualRegister: + case MachineOperand::MO_CCRegister: + if (const Value* srcI = MI.getOperand(i).getVRegValue()) { + ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); + if (I != valueToDefVecMap.end()) + addEdgesForValue(node, I->second, srcI, + MI.getOperand(i).isDef(), MI.getOperand(i).isUse(), + target); + } + break; + + case MachineOperand::MO_MachineRegister: + break; + + case MachineOperand::MO_SignExtendedImmed: + case MachineOperand::MO_UnextendedImmed: + case MachineOperand::MO_PCRelativeDisp: + case MachineOperand::MO_ConstantPoolIndex: + break; // nothing to do for immediate fields + + default: + assert(0 && "Unknown machine operand type in SchedGraph builder"); + break; + } + } - for (unsigned i=0, N=defMvec.size(); i < N; i++) - for (int o=0, N = mii.getNumOperands(defMvec[i]->getOpCode()); o < N; o++) - { - const MachineOperand& defOp = defMvec[i]->getOperand(o); - - if (defOp.opIsDef() - && (defOp.getOperandType() == MachineOperand::MO_VirtualRegister - || defOp.getOperandType() == MachineOperand::MO_CCRegister) - && (defOp.getVRegValue() == val)) - { - // this instruction does define value `val'. - // if there is a node for it in the same graph, add an edge. - SchedGraphNode* defNode = this->getGraphNodeForInstr(defMvec[i]); - if (defNode != NULL) - (void) new SchedGraphEdge(defNode, node, val); - } + // Add edges for values implicitly used by the machine instruction. + // Examples include function arguments to a Call instructions or the return + // value of a Ret instruction. + // + for (unsigned i=0, N=MI.getNumImplicitRefs(); i < N; ++i) + if (MI.getImplicitOp(i).isUse()) + if (const Value* srcI = MI.getImplicitRef(i)) { + ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); + if (I != valueToDefVecMap.end()) + addEdgesForValue(node, I->second, srcI, + MI.getImplicitOp(i).isDef(), + MI.getImplicitOp(i).isUse(), target); } } -void -SchedGraph::addEdgesForInstruction(SchedGraphNode* node, - NodeToRegRefMap& regToRefVecMap, - const TargetMachine& target) -{ - const Instruction& instr = * node->getInstr(); // No dummy nodes here! - const MachineInstr& minstr = * node->getMachineInstr(); +void SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target, + SchedGraphNode* node, + std::vector& memNodeVec, + std::vector& callDepNodeVec, + RegToRefVecMap& regToRefVecMap, + ValueToDefVecMap& valueToDefVecMap) { + const TargetInstrInfo& mii = *target.getInstrInfo(); - // Add incoming edges for the following: - // (1) operands of the machine instruction, including hidden operands - // (2) machine register dependences - // (3) other resource dependences for the machine instruction, if any - // Also, note any uses or defs of machine registers. + MachineOpCode opCode = node->getOpcode(); + + if (mii.isCall(opCode) || mii.isCCInstr(opCode)) + callDepNodeVec.push_back(node); + + if (mii.isLoad(opCode) || mii.isStore(opCode) || mii.isCall(opCode)) + memNodeVec.push_back(node); + + // Collect the register references and value defs. for explicit operands // - for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++) - { - const MachineOperand& mop = minstr.getOperand(i); - - // if this writes to a machine register other than the hardwired - // "zero" register used on many processors, record the reference. - if (mop.getOperandType() == MachineOperand::MO_MachineRegister - && (! (target.zeroRegNum >= 0 - && mop.getMachineRegNum()==(unsigned) target.zeroRegNum))) - { - regToRefVecMap[mop.getMachineRegNum()]. - push_back(make_pair(node, i)); - } + const MachineInstr& MI = *node->getMachineInstr(); + for (int i=0, numOps = (int) MI.getNumOperands(); i < numOps; i++) { + const MachineOperand& mop = MI.getOperand(i); + + // if this references a register other than the hardwired + // "zero" register, record the reference. + if (mop.hasAllocatedReg()) { + unsigned regNum = mop.getReg(); - // ignore all other def operands - if (minstr.operandIsDefined(i)) - continue; - - switch(mop.getOperandType()) - { - case MachineOperand::MO_VirtualRegister: - case MachineOperand::MO_CCRegister: - if (mop.getVRegValue()) - addSSAEdge(node, mop.getVRegValue(), target); - break; - - case MachineOperand::MO_MachineRegister: - break; - - case MachineOperand::MO_SignExtendedImmed: - case MachineOperand::MO_UnextendedImmed: - case MachineOperand::MO_PCRelativeDisp: - break; // nothing to do for immediate fields - - default: - assert(0 && "Unknown machine operand type in SchedGraph builder"); - break; - } + // If this is not a dummy zero register, record the reference in order + if (regNum != target.getRegInfo()->getZeroRegNum()) + regToRefVecMap[mop.getReg()] + .push_back(std::make_pair(node, i)); + + // If this is a volatile register, add the instruction to callDepVec + // (only if the node is not already on the callDepVec!) + if (callDepNodeVec.size() == 0 || callDepNodeVec.back() != node) + { + unsigned rcid; + int regInClass = target.getRegInfo()->getClassRegNum(regNum, rcid); + if (target.getRegInfo()->getMachineRegClass(rcid) + ->isRegVolatile(regInClass)) + callDepNodeVec.push_back(node); + } + + continue; // nothing more to do } + + // ignore all other non-def operands + if (!MI.getOperand(i).isDef()) + continue; + + // We must be defining a value. + assert((mop.getType() == MachineOperand::MO_VirtualRegister || + mop.getType() == MachineOperand::MO_CCRegister) + && "Do not expect any other kind of operand to be defined!"); + assert(mop.getVRegValue() != NULL && "Null value being defined?"); + + valueToDefVecMap[mop.getVRegValue()].push_back(std::make_pair(node, i)); + } - // add all true, anti, - // and output dependences for this register. but ignore + // + // Collect value defs. for implicit operands. They may have allocated + // physical registers also. + // + for (unsigned i=0, N = MI.getNumImplicitRefs(); i != N; ++i) { + const MachineOperand& mop = MI.getImplicitOp(i); + if (mop.hasAllocatedReg()) { + unsigned regNum = mop.getReg(); + if (regNum != target.getRegInfo()->getZeroRegNum()) + regToRefVecMap[mop.getReg()] + .push_back(std::make_pair(node, i + MI.getNumOperands())); + continue; // nothing more to do + } + if (mop.isDef()) { + assert(MI.getImplicitRef(i) != NULL && "Null value being defined?"); + valueToDefVecMap[MI.getImplicitRef(i)].push_back( + std::make_pair(node, -i)); + } + } } -void -SchedGraph::buildGraph(const TargetMachine& target) -{ - const MachineInstrInfo& mii = target.getInstrInfo(); - const BasicBlock* bb = bbVec[0]; - - assert(bbVec.size() == 1 && "Only handling a single basic block here"); +void SchedGraph::buildNodesForBB(const TargetMachine& target, + MachineBasicBlock& MBB, + std::vector& memNodeVec, + std::vector& callDepNodeVec, + RegToRefVecMap& regToRefVecMap, + ValueToDefVecMap& valueToDefVecMap) { + const TargetInstrInfo& mii = *target.getInstrInfo(); + + // Build graph nodes for each VM instruction and gather def/use info. + // Do both those together in a single pass over all machine instructions. + unsigned i = 0; + for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; + ++I, ++i) + if (I->getOpcode() != V9::PHI) { + SchedGraphNode* node = new SchedGraphNode(getNumNodes(), &MBB, i, target); + noteGraphNodeForInstr(I, node); + + // Remember all register references and value defs + findDefUseInfoAtInstr(target, node, memNodeVec, callDepNodeVec, + regToRefVecMap, valueToDefVecMap); + } +} + + +void SchedGraph::buildGraph(const TargetMachine& target) { + // Use this data structure to note all machine operands that compute + // ordinary LLVM values. These must be computed defs (i.e., instructions). + // Note that there may be multiple machine instructions that define + // each Value. + ValueToDefVecMap valueToDefVecMap; - // Use this data structures to note all LLVM memory instructions. + // Use this data structure to note all memory instructions. // We use this to add memory dependence edges without a second full walk. - // - vector memVec; + std::vector memNodeVec; + + // Use this data structure to note all instructions that access physical + // registers that can be modified by a call (including call instructions) + std::vector callDepNodeVec; - // Use this data structures to note any uses or definitions of + // Use this data structure to note any uses or definitions of // machine registers so we can add edges for those later without // extra passes over the nodes. // The vector holds an ordered list of references to the machine reg, @@ -601,55 +596,55 @@ SchedGraph::buildGraph(const TargetMachine& target) // single basic block, hence the assertion. Each reference is identified // by the pair: . // - NodeToRegRefMap regToRefVecMap; + RegToRefVecMap regToRefVecMap; // Make a dummy root node. We'll add edges to the real roots later. - graphRoot = new SchedGraphNode(0, NULL, NULL, target); - graphLeaf = new SchedGraphNode(1, NULL, NULL, target); + graphRoot = new SchedGraphNode(0, NULL, -1, target); + graphLeaf = new SchedGraphNode(1, NULL, -1, target); //---------------------------------------------------------------- - // First add nodes for all the machine instructions in the basic block. - // This greatly simplifies identifing which edges to add. + // First add nodes for all the machine instructions in the basic block + // because this greatly simplifies identifying which edges to add. + // Do this one VM instruction at a time since the SchedGraphNode needs that. // Also, remember the load/store instructions to add memory deps later. //---------------------------------------------------------------- - - for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II) - { - const Instruction *instr = *II; - const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec(); - for (unsigned i=0, N=mvec.size(); i < N; i++) - if (! mii.isDummyPhiInstr(mvec[i]->getOpCode())) - { - SchedGraphNode* node = new SchedGraphNode(getNumNodes(), - instr, mvec[i], target); - this->noteGraphNodeForInstr(mvec[i], node); - } - - if (instr->getOpcode() == Instruction::Load || - instr->getOpcode() == Instruction::Store) - memVec.push_back(instr); - } + + buildNodesForBB(target, MBB, memNodeVec, callDepNodeVec, + regToRefVecMap, valueToDefVecMap); //---------------------------------------------------------------- - // Now add the edges. + // Now add edges for the following (all are incoming edges except (4)): + // (1) operands of the machine instruction, including hidden operands + // (2) machine register dependences + // (3) memory load/store dependences + // (3) other resource dependences for the machine instruction, if any + // (4) output dependences when multiple machine instructions define the + // same value; all must have been generated from a single VM instrn + // (5) control dependences to branch instructions generated for the + // terminator instruction of the BB. Because of delay slots and + // 2-way conditional branches, multiple CD edges are needed + // (see addCDEdges for details). + // Also, note any uses or defs of machine registers. + // //---------------------------------------------------------------- // First, add edges to the terminator instruction of the basic block. - this->addCDEdges(bb->getTerminator(), target); + this->addCDEdges(MBB.getBasicBlock()->getTerminator(), target); - // Then add memory dep edges: store->load, load->store, and store->store - this->addMemEdges(memVec, target); - - // Then add other edges for all instructions in the block. - for (SchedGraph::iterator GI = this->begin(); GI != this->end(); ++GI) - { - SchedGraphNode* node = (*GI).second; - addEdgesForInstruction(node, regToRefVecMap, target); - } + // Then add memory dep edges: store->load, load->store, and store->store. + // Call instructions are treated as both load and store. + this->addMemEdges(memNodeVec, target); + + // Then add edges between call instructions and CC set/use instructions + this->addCallDepEdges(callDepNodeVec, target); + // Then add incoming def-use (SSA) edges for each machine instruction. + for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ++I) + addEdgesForInstruction(*I, valueToDefVecMap, target); + // Then add edges for dependences on machine registers this->addMachineRegEdges(regToRefVecMap, target); - + // Finally, add edges from the dummy root and to dummy leaf this->addDummyEdges(); } @@ -658,105 +653,85 @@ SchedGraph::buildGraph(const TargetMachine& target) // // class SchedGraphSet // - -/*ctor*/ -SchedGraphSet::SchedGraphSet(const Method* _method, +SchedGraphSet::SchedGraphSet(const Function* _function, const TargetMachine& target) : - method(_method) -{ - buildGraphsForMethod(method, target); + function(_function) { + buildGraphsForMethod(function, target); } - -/*dtor*/ -SchedGraphSet::~SchedGraphSet() -{ +SchedGraphSet::~SchedGraphSet() { // delete all the graphs - for (iterator I=begin(); I != end(); ++I) - delete (*I).second; + for(iterator I = begin(), E = end(); I != E; ++I) + delete *I; // destructor is a friend } -void -SchedGraphSet::dump() const -{ - cout << "======== Sched graphs for method `" - << (method->hasName()? method->getName() : "???") - << "' ========" << endl << endl; +void SchedGraphSet::dump() const { + std::cerr << "======== Sched graphs for function `" << function->getName() + << "' ========\n\n"; for (const_iterator I=begin(); I != end(); ++I) - (*I).second->dump(); + (*I)->dump(); - cout << endl << "====== End graphs for method `" - << (method->hasName()? method->getName() : "") - << "' ========" << endl << endl; + std::cerr << "\n====== End graphs for function `" << function->getName() + << "' ========\n\n"; } -void -SchedGraphSet::buildGraphsForMethod(const Method *method, - const TargetMachine& target) -{ - for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI) - { - SchedGraph* graph = new SchedGraph(*BI, target); - this->noteGraphForBlock(*BI, graph); - } +void SchedGraphSet::buildGraphsForMethod(const Function *F, + const TargetMachine& target) { + MachineFunction &MF = MachineFunction::get(F); + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) + addGraph(new SchedGraph(*I, target)); } - -ostream& -operator<<(ostream& os, const SchedGraphEdge& edge) -{ - os << "edge [" << edge.src->getNodeId() << "] -> [" - << edge.sink->getNodeId() << "] : "; - - switch(edge.depType) { - case SchedGraphEdge::CtrlDep: os<< "Control Dep"; break; - case SchedGraphEdge::DefUseDep: os<< "Reg Value " << edge.val; break; - case SchedGraphEdge::MemoryDep: os<< "Mem Value " << edge.val; break; - case SchedGraphEdge::MachineRegister: os<< "Reg " <getNodeId() << "] -> [" + << sink->getNodeId() << "] : "; + + switch(depType) { + case SchedGraphEdge::CtrlDep: + os<< "Control Dep"; + break; + case SchedGraphEdge::ValueDep: + os<< "Reg Value " << *val; + break; + case SchedGraphEdge::MemoryDep: + os<< "Memory Dep"; + break; + case SchedGraphEdge::MachineRegister: + os<< "Reg " << machineRegNum; + break; + case SchedGraphEdge::MachineResource: + os<<"Resource "<< resourceId; + break; + default: + assert(0); + break; } - os << " : delay = " << edge.minDelay << endl; - - return os; + os << " : delay = " << minDelay << "\n"; } -ostream& -operator<<(ostream& os, const SchedGraphNode& node) -{ - printIndent(4, os); - os << "Node " << node.nodeId << " : " - << "latency = " << node.latency << endl; - - printIndent(6, os); - - if (node.getMachineInstr() == NULL) - os << "(Dummy node)" << endl; - else - { - os << *node.getMachineInstr() << endl; - - printIndent(6, os); - os << node.inEdges.size() << " Incoming Edges:" << endl; - for (unsigned i=0, N=node.inEdges.size(); i < N; i++) - { - printIndent(8, os); - os << * node.inEdges[i]; - } - - printIndent(6, os); - os << node.outEdges.size() << " Outgoing Edges:" << endl; - for (unsigned i=0, N=node.outEdges.size(); i < N; i++) - { - printIndent(8, os); - os << * node.outEdges[i]; - } - } - - return os; +void SchedGraphNode::print(std::ostream &os) const { + os << std::string(8, ' ') + << "Node " << ID << " : " + << "latency = " << latency << "\n" << std::string(12, ' '); + + if (getMachineInstr() == NULL) + os << "(Dummy node)\n"; + else { + os << *getMachineInstr() << "\n" << std::string(12, ' '); + os << inEdges.size() << " Incoming Edges:\n"; + for (unsigned i=0, N = inEdges.size(); i < N; i++) + os << std::string(16, ' ') << *inEdges[i]; + + os << std::string(12, ' ') << outEdges.size() + << " Outgoing Edges:\n"; + for (unsigned i=0, N= outEdges.size(); i < N; i++) + os << std::string(16, ' ') << *outEdges[i]; + } } + +} // End llvm namespace