diff options
Diffstat (limited to 'lib/CodeGen/InstrSched/SchedGraph.cpp')
| -rw-r--r-- | lib/CodeGen/InstrSched/SchedGraph.cpp | 458 |
1 files changed, 226 insertions, 232 deletions
diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp index 58fbb93c09..fa7920309f 100644 --- a/lib/CodeGen/InstrSched/SchedGraph.cpp +++ b/lib/CodeGen/InstrSched/SchedGraph.cpp @@ -249,20 +249,21 @@ SchedGraph::eraseIncomingEdges(SchedGraphNode* node, bool addDummyEdges) // Delete and disconnect all in-edges for the node for (SchedGraphNode::iterator I = node->beginInEdges(); I != node->endInEdges(); ++I) - { - SchedGraphNode* srcNode = (*I)->getSrc(); - srcNode->removeOutEdge(*I); - delete *I; + { + SchedGraphNode* srcNode = (*I)->getSrc(); + srcNode->removeOutEdge(*I); + delete *I; - if (addDummyEdges && - srcNode != getRoot() && - srcNode->beginOutEdges() == srcNode->endOutEdges()) - { // srcNode has no more out edges, so add an edge to dummy EXIT node - assert(node != getLeaf() && "Adding edge that was just removed?"); - (void) new SchedGraphEdge(srcNode, getLeaf(), - SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0); - } + if (addDummyEdges && + srcNode != getRoot() && + srcNode->beginOutEdges() == srcNode->endOutEdges()) + { + // srcNode has no more out edges, so add an edge to dummy EXIT node + assert(node != getLeaf() && "Adding edge that was just removed?"); + (void) new SchedGraphEdge(srcNode, getLeaf(), + SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0); } + } node->inEdges.clear(); } @@ -273,20 +274,20 @@ SchedGraph::eraseOutgoingEdges(SchedGraphNode* node, bool addDummyEdges) // Delete and disconnect all out-edges for the node for (SchedGraphNode::iterator I = node->beginOutEdges(); I != node->endOutEdges(); ++I) - { - SchedGraphNode* sinkNode = (*I)->getSink(); - sinkNode->removeInEdge(*I); - delete *I; + { + SchedGraphNode* sinkNode = (*I)->getSink(); + sinkNode->removeInEdge(*I); + delete *I; - if (addDummyEdges && - sinkNode != getLeaf() && - sinkNode->beginInEdges() == sinkNode->endInEdges()) - { //sinkNode has no more in edges, so add an edge from dummy ENTRY node - assert(node != getRoot() && "Adding edge that was just removed?"); - (void) new SchedGraphEdge(getRoot(), sinkNode, - SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0); - } + if (addDummyEdges && + sinkNode != getLeaf() && + sinkNode->beginInEdges() == sinkNode->endInEdges()) + { //sinkNode has no more in edges, so add an edge from dummy ENTRY node + assert(node != getRoot() && "Adding edge that was just removed?"); + (void) new SchedGraphEdge(getRoot(), sinkNode, + SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0); } + } node->outEdges.clear(); } @@ -305,16 +306,16 @@ 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); - } + { + 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); + } } @@ -343,65 +344,65 @@ SchedGraph::addCDEdges(const TerminatorInst* term, // 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?"); + { + 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 - } - } + 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); - } + { + 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 (unsigned i=0, N=MBB.size(); i < N; i++) - { - if (MBB[i] == termMvec[first]) // reached the first branch - break; + { + if (MBB[i] == termMvec[first]) // reached the first branch + break; - SchedGraphNode* fromNode = this->getGraphNodeForInstr(MBB[i]); - if (fromNode == NULL) - continue; // dummy instruction, e.g., PHI + SchedGraphNode* fromNode = this->getGraphNodeForInstr(MBB[i]); + if (fromNode == NULL) + continue; // dummy instruction, e.g., PHI - (void) new SchedGraphEdge(fromNode, firstBrNode, - SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); + (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(MBB[i]->getOpCode()); - assert(i+d < N && "Insufficient delay slots for instruction?"); + // 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(MBB[i]->getOpCode()); + assert(i+d < N && "Insufficient delay slots for instruction?"); - for (unsigned j=1; j <= d; j++) - { - SchedGraphNode* toNode = this->getGraphNodeForInstr(MBB[i+j]); - assert(toNode && "No node for machine instr in delay slot?"); - (void) new SchedGraphEdge(fromNode, toNode, - SchedGraphEdge::CtrlDep, - SchedGraphEdge::NonDataDep, 0); - } + for (unsigned j=1; j <= d; j++) + { + SchedGraphNode* toNode = this->getGraphNodeForInstr(MBB[i+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; @@ -437,24 +438,24 @@ SchedGraph::addMemEdges(const std::vector<SchedGraphNode*>& memNodeVec, // 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 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; + 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); - } + 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. @@ -484,24 +485,23 @@ SchedGraph::addCallCCEdges(const std::vector<SchedGraphNode*>& memNodeVec, 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); - } + { + ++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); + } } @@ -517,47 +517,43 @@ SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap, // for (RegToRefVecMap::iterator I = regToRefVecMap.begin(); I != regToRefVecMap.end(); ++I) - { - int regNum = (*I).first; - RefVec& regRefVec = (*I).second; + { + 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; - bool isDef = node->getMachineInstr()->operandIsDefined(opNum); - bool isDefAndUse = - node->getMachineInstr()->operandIsDefinedAndUsed(opNum); + // 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; + bool isDef = node->getMachineInstr()->operandIsDefined(opNum); + bool isDefAndUse = + node->getMachineInstr()->operandIsDefinedAndUsed(opNum); - for (unsigned p=0; p < i; ++p) - { - SchedGraphNode* prevNode = regRefVec[p].first; - if (prevNode != node) - { - unsigned int prevOpNum = regRefVec[p].second; - bool prevIsDef = - prevNode->getMachineInstr()->operandIsDefined(prevOpNum); - bool prevIsDefAndUse = - prevNode->getMachineInstr()->operandIsDefinedAndUsed(prevOpNum); - if (isDef) - { - if (prevIsDef) - new SchedGraphEdge(prevNode, node, regNum, - SchedGraphEdge::OutputDep); - if (!prevIsDef || prevIsDefAndUse) - new SchedGraphEdge(prevNode, node, regNum, - SchedGraphEdge::AntiDep); - } + for (unsigned p=0; p < i; ++p) { + SchedGraphNode* prevNode = regRefVec[p].first; + if (prevNode != node) { + unsigned int prevOpNum = regRefVec[p].second; + bool prevIsDef = + prevNode->getMachineInstr()->operandIsDefined(prevOpNum); + bool prevIsDefAndUse = + prevNode->getMachineInstr()->operandIsDefinedAndUsed(prevOpNum); + 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); - } - } + if (prevIsDef) + if (!isDef || isDefAndUse) + new SchedGraphEdge(prevNode, node, regNum, + SchedGraphEdge::TrueDep); } + } } + } } @@ -578,29 +574,28 @@ SchedGraph::addEdgesForValue(SchedGraphNode* refNode, // 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 == refNode) + continue; // Dont add any self-loops - if ((*I).first->getOrigIndexInBB() < refNode->getOrigIndexInBB()) - { // (*).first is before refNode - if (refNodeIsDef) - (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) - (void) new SchedGraphEdge(refNode, (*I).first, defValue, - SchedGraphEdge::OutputDep); - if (refNodeIsUse) - (void) new SchedGraphEdge(refNode, (*I).first, defValue, - SchedGraphEdge::AntiDep); - } + if ((*I).first->getOrigIndexInBB() < refNode->getOrigIndexInBB()) { + // (*).first is before refNode + if (refNodeIsDef) + (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) + (void) new SchedGraphEdge(refNode, (*I).first, defValue, + SchedGraphEdge::OutputDep); + if (refNodeIsUse) + (void) new SchedGraphEdge(refNode, (*I).first, defValue, + SchedGraphEdge::AntiDep); } + } } @@ -616,35 +611,35 @@ SchedGraph::addEdgesForInstruction(const MachineInstr& MI, // Add edges for all operands of the machine instruction. // for (unsigned i = 0, numOps = MI.getNumOperands(); i != numOps; ++i) + { + switch (MI.getOperandType(i)) { - switch (MI.getOperandType(i)) - { - case MachineOperand::MO_VirtualRegister: - case MachineOperand::MO_CCRegister: - if (const Instruction* srcI = - dyn_cast_or_null<Instruction>(MI.getOperand(i).getVRegValue())) - { - ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); - if (I != valueToDefVecMap.end()) - addEdgesForValue(node, I->second, srcI, - MI.operandIsDefined(i), - MI.operandIsDefinedAndUsed(i), target); - } - break; + case MachineOperand::MO_VirtualRegister: + case MachineOperand::MO_CCRegister: + if (const Instruction* srcI = + dyn_cast_or_null<Instruction>(MI.getOperand(i).getVRegValue())) + { + ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); + if (I != valueToDefVecMap.end()) + addEdgesForValue(node, I->second, srcI, + MI.operandIsDefined(i), + MI.operandIsDefinedAndUsed(i), target); + } + break; - case MachineOperand::MO_MachineRegister: - 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 + 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; - } + 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 @@ -655,13 +650,13 @@ SchedGraph::addEdgesForInstruction(const MachineInstr& MI, MI.implicitRefIsDefinedAndUsed(i)) if (const Instruction *srcI = dyn_cast_or_null<Instruction>(MI.getImplicitRef(i))) - { - ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); - if (I != valueToDefVecMap.end()) - addEdgesForValue(node, I->second, srcI, - MI.implicitRefIsDefined(i), - MI.implicitRefIsDefinedAndUsed(i), target); - } + { + ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI); + if (I != valueToDefVecMap.end()) + addEdgesForValue(node, I->second, srcI, + MI.implicitRefIsDefined(i), + MI.implicitRefIsDefinedAndUsed(i), target); + } } @@ -683,32 +678,32 @@ SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target, // const MachineInstr& minstr = *node->getMachineInstr(); for (int i=0, numOps = (int) minstr.getNumOperands(); i < numOps; i++) - { - const MachineOperand& mop = minstr.getOperand(i); + { + const MachineOperand& mop = minstr.getOperand(i); - // if this references a register other than the hardwired - // "zero" register, record the reference. - if (mop.getType() == MachineOperand::MO_MachineRegister) - { - int regNum = mop.getMachineRegNum(); - if (regNum != target.getRegInfo().getZeroRegNum()) - regToRefVecMap[mop.getMachineRegNum()].push_back( - std::make_pair(node, i)); - continue; // nothing more to do - } + // if this references a register other than the hardwired + // "zero" register, record the reference. + if (mop.getType() == MachineOperand::MO_MachineRegister) + { + int regNum = mop.getMachineRegNum(); + if (regNum != target.getRegInfo().getZeroRegNum()) + regToRefVecMap[mop.getMachineRegNum()] + .push_back(std::make_pair(node, i)); + continue; // nothing more to do + } - // ignore all other non-def operands - if (! minstr.operandIsDefined(i)) - continue; + // ignore all other non-def operands + if (! minstr.operandIsDefined(i)) + 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!"); + // 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!"); - const Instruction* defInstr = cast<Instruction>(mop.getVRegValue()); - valueToDefVecMap[defInstr].push_back(std::make_pair(node, i)); - } + const Instruction* defInstr = cast<Instruction>(mop.getVRegValue()); + valueToDefVecMap[defInstr].push_back(std::make_pair(node, i)); + } // // Collect value defs. for implicit operands. The interface to extract @@ -903,18 +898,17 @@ std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node) if (node.getMachineInstr() == NULL) os << "(Dummy node)\n"; - else - { - os << *node.getMachineInstr() << "\n" << std::string(12, ' '); - os << node.inEdges.size() << " Incoming Edges:\n"; - for (unsigned i=0, N=node.inEdges.size(); i < N; i++) - os << std::string(16, ' ') << *node.inEdges[i]; - - os << std::string(12, ' ') << node.outEdges.size() - << " Outgoing Edges:\n"; - for (unsigned i=0, N=node.outEdges.size(); i < N; i++) - os << std::string(16, ' ') << *node.outEdges[i]; - } + else { + os << *node.getMachineInstr() << "\n" << std::string(12, ' '); + os << node.inEdges.size() << " Incoming Edges:\n"; + for (unsigned i=0, N=node.inEdges.size(); i < N; i++) + os << std::string(16, ' ') << *node.inEdges[i]; + + os << std::string(12, ' ') << node.outEdges.size() + << " Outgoing Edges:\n"; + for (unsigned i=0, N=node.outEdges.size(); i < N; i++) + os << std::string(16, ' ') << *node.outEdges[i]; + } return os; } |