diff options
Diffstat (limited to 'lib/CodeGen/InstrSched/SchedGraph.cpp')
| -rw-r--r-- | lib/CodeGen/InstrSched/SchedGraph.cpp | 737 |
1 files changed, 0 insertions, 737 deletions
diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp deleted file mode 100644 index 00b48d537d..0000000000 --- a/lib/CodeGen/InstrSched/SchedGraph.cpp +++ /dev/null @@ -1,737 +0,0 @@ -//===- SchedGraph.cpp - Scheduling Graph Implementation -------------------===// -// -// 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 <iostream> - -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<std::pair<SchedGraphNode*, int> > { - typedef std::vector<std::pair<SchedGraphNode*,int> >::iterator iterator; - typedef - std::vector<std::pair<SchedGraphNode*,int> >::const_iterator const_iterator; -}; - -struct RegToRefVecMap: public hash_map<int, RefVec> { - typedef hash_map<int, RefVec>:: iterator iterator; - typedef hash_map<int, RefVec>::const_iterator const_iterator; -}; - -struct ValueToDefVecMap: public hash_map<const Value*, RefVec> { - typedef hash_map<const Value*, RefVec>:: iterator iterator; - typedef hash_map<const Value*, RefVec>::const_iterator const_iterator; -}; - - -// -// class SchedGraphNode -// - -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); - } -} - -// -// 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 -// -SchedGraph::SchedGraph(MachineBasicBlock &mbb, const TargetMachine& target) - : MBB(mbb) { - buildGraph(target); -} - -// -// 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 { - 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->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 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()) && - ! mii.isReturn(termMvec[first]->getOpcode())) - ++first; - assert(first < termMvec.size() && - "No branch instructions for terminator? Ok, but weird!"); - if (first == termMvec.size()) - return; - - 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 (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. Use a latency of 0 as above. - // - 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. Use 0 latency again. - // - 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); - - // 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 } -}; - - -// 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<SchedGraphNode*>& memNodeVec, - 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 <memNodeVec[i], memNodeVec[j: j > 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)); - - if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF) - (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm], - SchedGraphEdge::MemoryDep, - SG_DepOrderArray[fromType][toType], 1); - } - } -} - -// 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<SchedGraphNode*>& 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 <memNodeVec[i], memNodeVec[j: j > 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<SchedGraphNode*> 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(RegToRefVecMap& regToRefVecMap, - const TargetMachine& target) { - // This code assumes that two registers with different numbers are - // not aliased! - // - 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 (prevIsDef) - if (!isDef || isDefAndUse) - new SchedGraphEdge(prevNode, node, regNum, - SchedGraphEdge::TrueDep); - } - } - } - } -} - - -// 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); - } - } -} - - -void SchedGraph::addEdgesForInstruction(const MachineInstr& MI, - const ValueToDefVecMap& valueToDefVecMap, - const TargetMachine& target) { - SchedGraphNode* node = getGraphNodeForInstr(&MI); - if (node == NULL) - return; - - // Add edges for all operands of the machine instruction. - // - 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; - } - } - - // 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::findDefUseInfoAtInstr(const TargetMachine& target, - SchedGraphNode* node, - std::vector<SchedGraphNode*>& memNodeVec, - std::vector<SchedGraphNode*>& callDepNodeVec, - RegToRefVecMap& regToRefVecMap, - ValueToDefVecMap& valueToDefVecMap) { - const TargetInstrInfo& mii = *target.getInstrInfo(); - - 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 - // - 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(); - - // 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)); - } - - // - // 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::buildNodesForBB(const TargetMachine& target, - MachineBasicBlock& MBB, - std::vector<SchedGraphNode*>& memNodeVec, - std::vector<SchedGraphNode*>& 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 structure to note all memory instructions. - // We use this to add memory dependence edges without a second full walk. - std::vector<SchedGraphNode*> 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<SchedGraphNode*> callDepNodeVec; - - // 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, - // ordered according to control-flow order. This only works for a - // single basic block, hence the assertion. Each reference is identified - // by the pair: <node, operand-number>. - // - RegToRefVecMap regToRefVecMap; - - // Make a dummy root node. We'll add edges to the real roots later. - 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 - // 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. - //---------------------------------------------------------------- - - buildNodesForBB(target, MBB, memNodeVec, callDepNodeVec, - regToRefVecMap, valueToDefVecMap); - - //---------------------------------------------------------------- - // 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(MBB.getBasicBlock()->getTerminator(), 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(); -} - - -// -// class SchedGraphSet -// -SchedGraphSet::SchedGraphSet(const Function* _function, - const TargetMachine& target) : - function(_function) { - buildGraphsForMethod(function, target); -} - -SchedGraphSet::~SchedGraphSet() { - // delete all the graphs - for(iterator I = begin(), E = end(); I != E; ++I) - delete *I; // destructor is a friend -} - - -void SchedGraphSet::dump() const { - std::cerr << "======== Sched graphs for function `" << function->getName() - << "' ========\n\n"; - - for (const_iterator I=begin(); I != end(); ++I) - (*I)->dump(); - - std::cerr << "\n====== End graphs for function `" << function->getName() - << "' ========\n\n"; -} - - -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)); -} - - -void SchedGraphEdge::print(std::ostream &os) const { - os << "edge [" << src->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 = " << minDelay << "\n"; -} - -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 |