2 //***************************************************************************
7 // Scheduling graph based on SSA graph plus extra dependence edges
8 // capturing dependences due to machine resources (machine registers,
9 // CC registers, and any others).
12 // 7/20/01 - Vikram Adve - Created
13 //**************************************************************************/
15 #include "SchedGraph.h"
16 #include "llvm/InstrTypes.h"
17 #include "llvm/Instruction.h"
18 #include "llvm/BasicBlock.h"
19 #include "llvm/Method.h"
20 #include "llvm/CodeGen/MachineInstr.h"
21 #include "llvm/Target/MachineInstrInfo.h"
22 #include "llvm/Target/MachineRegInfo.h"
23 #include "llvm/Support/StringExtras.h"
27 // class SchedGraphEdge
31 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
32 SchedGraphNode* _sink,
33 SchedGraphEdgeDepType _depType,
34 DataDepOrderType _depOrderType,
39 depOrderType(_depOrderType),
41 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
43 src->addOutEdge(this);
44 sink->addInEdge(this);
49 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
50 SchedGraphNode* _sink,
52 DataDepOrderType _depOrderType,
57 depOrderType(_depOrderType),
59 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
61 src->addOutEdge(this);
62 sink->addInEdge(this);
67 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
68 SchedGraphNode* _sink,
70 DataDepOrderType _depOrderType,
74 depType(MachineRegister),
75 depOrderType(_depOrderType),
76 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
77 machineRegNum(_regNum)
79 src->addOutEdge(this);
80 sink->addInEdge(this);
85 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
86 SchedGraphNode* _sink,
87 ResourceId _resourceId,
91 depType(MachineResource),
92 depOrderType(NonDataDep),
93 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
94 resourceId(_resourceId)
96 src->addOutEdge(this);
97 sink->addInEdge(this);
101 SchedGraphEdge::~SchedGraphEdge()
105 void SchedGraphEdge::dump(int indent=0) const {
106 printIndent(indent); cout << *this;
111 // class SchedGraphNode
115 SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
116 const Instruction* _instr,
117 const MachineInstr* _minstr,
118 const TargetMachine& target)
126 MachineOpCode mopCode = minstr->getOpCode();
127 latency = target.getInstrInfo().hasResultInterlock(mopCode)
128 ? target.getInstrInfo().minLatency(mopCode)
129 : target.getInstrInfo().maxLatency(mopCode);
135 SchedGraphNode::~SchedGraphNode()
139 void SchedGraphNode::dump(int indent=0) const {
140 printIndent(indent); cout << *this;
145 SchedGraphNode::addInEdge(SchedGraphEdge* edge)
147 inEdges.push_back(edge);
152 SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
154 outEdges.push_back(edge);
158 SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
160 assert(edge->getSink() == this);
162 for (iterator I = beginInEdges(); I != endInEdges(); ++I)
171 SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
173 assert(edge->getSrc() == this);
175 for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
190 SchedGraph::SchedGraph(const BasicBlock* bb,
191 const TargetMachine& target)
194 this->buildGraph(target);
199 SchedGraph::~SchedGraph()
201 for (iterator I=begin(); I != end(); ++I)
203 SchedGraphNode* node = (*I).second;
205 // for each node, delete its out-edges
206 for (SchedGraphNode::iterator I = node->beginOutEdges();
207 I != node->endOutEdges(); ++I)
210 // then delete the node itself.
217 SchedGraph::dump() const
219 cout << " Sched Graph for Basic Blocks: ";
220 for (unsigned i=0, N=bbVec.size(); i < N; i++)
222 cout << (bbVec[i]->hasName()? bbVec[i]->getName() : "block")
223 << " (" << bbVec[i] << ")"
224 << ((i == N-1)? "" : ", ");
227 cout << endl << endl << " Actual Root nodes : ";
228 for (unsigned i=0, N=graphRoot->outEdges.size(); i < N; i++)
229 cout << graphRoot->outEdges[i]->getSink()->getNodeId()
230 << ((i == N-1)? "" : ", ");
232 cout << endl << " Graph Nodes:" << endl;
233 for (const_iterator I=begin(); I != end(); ++I)
234 cout << endl << * (*I).second;
241 SchedGraph::eraseIncomingEdges(SchedGraphNode* node, bool addDummyEdges)
243 // Delete and disconnect all in-edges for the node
244 for (SchedGraphNode::iterator I = node->beginInEdges();
245 I != node->endInEdges(); ++I)
247 SchedGraphNode* srcNode = (*I)->getSrc();
248 srcNode->removeOutEdge(*I);
252 srcNode != getRoot() &&
253 srcNode->beginOutEdges() == srcNode->endOutEdges())
254 { // srcNode has no more out edges, so add an edge to dummy EXIT node
255 assert(node != getLeaf() && "Adding edge that was just removed?");
256 (void) new SchedGraphEdge(srcNode, getLeaf(),
257 SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
261 node->inEdges.clear();
265 SchedGraph::eraseOutgoingEdges(SchedGraphNode* node, bool addDummyEdges)
267 // Delete and disconnect all out-edges for the node
268 for (SchedGraphNode::iterator I = node->beginOutEdges();
269 I != node->endOutEdges(); ++I)
271 SchedGraphNode* sinkNode = (*I)->getSink();
272 sinkNode->removeInEdge(*I);
276 sinkNode != getLeaf() &&
277 sinkNode->beginInEdges() == sinkNode->endInEdges())
278 { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
279 assert(node != getRoot() && "Adding edge that was just removed?");
280 (void) new SchedGraphEdge(getRoot(), sinkNode,
281 SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
285 node->outEdges.clear();
289 SchedGraph::eraseIncidentEdges(SchedGraphNode* node, bool addDummyEdges)
291 this->eraseIncomingEdges(node, addDummyEdges);
292 this->eraseOutgoingEdges(node, addDummyEdges);
297 SchedGraph::addDummyEdges()
299 assert(graphRoot->outEdges.size() == 0);
301 for (const_iterator I=begin(); I != end(); ++I)
303 SchedGraphNode* node = (*I).second;
304 assert(node != graphRoot && node != graphLeaf);
305 if (node->beginInEdges() == node->endInEdges())
306 (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep,
307 SchedGraphEdge::NonDataDep, 0);
308 if (node->beginOutEdges() == node->endOutEdges())
309 (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep,
310 SchedGraphEdge::NonDataDep, 0);
316 SchedGraph::addCDEdges(const TerminatorInst* term,
317 const TargetMachine& target)
319 const MachineInstrInfo& mii = target.getInstrInfo();
320 MachineCodeForVMInstr& termMvec = term->getMachineInstrVec();
322 // Find the first branch instr in the sequence of machine instrs for term
325 while (! mii.isBranch(termMvec[first]->getOpCode()))
327 assert(first < termMvec.size() &&
328 "No branch instructions for BR? Ok, but weird! Delete assertion.");
329 if (first == termMvec.size())
332 SchedGraphNode* firstBrNode = this->getGraphNodeForInstr(termMvec[first]);
334 // Add CD edges from each instruction in the sequence to the
335 // *last preceding* branch instr. in the sequence
337 for (int i = (int) termMvec.size()-1; i > (int) first; i--)
339 SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]);
340 assert(toNode && "No node for instr generated for branch?");
342 for (int j = i-1; j >= 0; j--)
343 if (mii.isBranch(termMvec[j]->getOpCode()))
345 SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]);
346 assert(brNode && "No node for instr generated for branch?");
347 (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep,
348 SchedGraphEdge::NonDataDep, 0);
349 break; // only one incoming edge is enough
353 // Add CD edges from each instruction preceding the first branch
354 // to the first branch
356 for (int i = first-1; i >= 0; i--)
358 SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]);
359 assert(fromNode && "No node for instr generated for branch?");
360 (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep,
361 SchedGraphEdge::NonDataDep, 0);
364 // Now add CD edges to the first branch instruction in the sequence
365 // from all preceding instructions in the basic block.
367 const BasicBlock* bb = term->getParent();
368 for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
370 if ((*II) == (const Instruction*) term) // special case, handled above
373 assert(! (*II)->isTerminator() && "Two terminators in basic block?");
375 const MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
376 for (unsigned i=0, N=mvec.size(); i < N; i++)
378 SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]);
379 if (fromNode == NULL)
380 continue; // dummy instruction, e.g., PHI
382 (void) new SchedGraphEdge(fromNode, firstBrNode,
383 SchedGraphEdge::CtrlDep,
384 SchedGraphEdge::NonDataDep, 0);
386 // If we find any other machine instructions (other than due to
387 // the terminator) that also have delay slots, add an outgoing edge
388 // from the instruction to the instructions in the delay slots.
390 unsigned d = mii.getNumDelaySlots(mvec[i]->getOpCode());
391 assert(i+d < N && "Insufficient delay slots for instruction?");
393 for (unsigned j=1; j <= d; j++)
395 SchedGraphNode* toNode = this->getGraphNodeForInstr(mvec[i+j]);
396 assert(toNode && "No node for machine instr in delay slot?");
397 (void) new SchedGraphEdge(fromNode, toNode,
398 SchedGraphEdge::CtrlDep,
399 SchedGraphEdge::NonDataDep, 0);
407 SchedGraph::addMemEdges(const vector<const Instruction*>& memVec,
408 const TargetMachine& target)
410 const MachineInstrInfo& mii = target.getInstrInfo();
412 for (unsigned im=0, NM=memVec.size(); im < NM; im++)
414 const Instruction* fromInstr = memVec[im];
415 bool fromIsLoad = fromInstr->getOpcode() == Instruction::Load;
417 for (unsigned jm=im+1; jm < NM; jm++)
419 const Instruction* toInstr = memVec[jm];
420 bool toIsLoad = toInstr->getOpcode() == Instruction::Load;
421 SchedGraphEdge::DataDepOrderType depOrderType;
425 if (toIsLoad) continue; // both instructions are loads
426 depOrderType = SchedGraphEdge::AntiDep;
430 depOrderType = (toIsLoad)? SchedGraphEdge::TrueDep
431 : SchedGraphEdge::OutputDep;
434 MachineCodeForVMInstr& fromInstrMvec=fromInstr->getMachineInstrVec();
435 MachineCodeForVMInstr& toInstrMvec = toInstr->getMachineInstrVec();
437 // We have two VM memory instructions, and at least one is a store.
438 // Add edges between all machine load/store instructions.
440 for (unsigned i=0, N=fromInstrMvec.size(); i < N; i++)
442 MachineOpCode fromOpCode = fromInstrMvec[i]->getOpCode();
443 if (mii.isLoad(fromOpCode) || mii.isStore(fromOpCode))
445 SchedGraphNode* fromNode =
446 this->getGraphNodeForInstr(fromInstrMvec[i]);
447 assert(fromNode && "No node for memory instr?");
449 for (unsigned j=0, M=toInstrMvec.size(); j < M; j++)
451 MachineOpCode toOpCode = toInstrMvec[j]->getOpCode();
452 if (mii.isLoad(toOpCode) || mii.isStore(toOpCode))
454 SchedGraphNode* toNode =
455 this->getGraphNodeForInstr(toInstrMvec[j]);
456 assert(toNode && "No node for memory instr?");
458 (void) new SchedGraphEdge(fromNode, toNode,
459 SchedGraphEdge::MemoryDep,
470 typedef vector< pair<SchedGraphNode*, unsigned int> > RegRefVec;
472 // The following needs to be a class, not a typedef, so we can use
473 // an opaque declaration in SchedGraph.h
474 class NodeToRegRefMap: public hash_map<int, RegRefVec> {
475 typedef hash_map<int, RegRefVec>:: iterator iterator;
476 typedef hash_map<int, RegRefVec>::const_iterator const_iterator;
481 SchedGraph::addMachineRegEdges(NodeToRegRefMap& regToRefVecMap,
482 const TargetMachine& target)
484 assert(bbVec.size() == 1 && "Only handling a single basic block here");
486 // This assumes that such hardwired registers are never allocated
487 // to any LLVM value (since register allocation happens later), i.e.,
488 // any uses or defs of this register have been made explicit!
489 // Also assumes that two registers with different numbers are
492 for (NodeToRegRefMap::iterator I = regToRefVecMap.begin();
493 I != regToRefVecMap.end(); ++I)
495 int regNum = (*I).first;
496 RegRefVec& regRefVec = (*I).second;
498 // regRefVec is ordered by control flow order in the basic block
500 for (unsigned i=0; i < regRefVec.size(); ++i)
502 SchedGraphNode* node = regRefVec[i].first;
503 bool isDef = regRefVec[i].second;
506 { // Each def gets an output edge from the last def
508 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum,
509 SchedGraphEdge::OutputDep);
511 // Also, an anti edge from all uses *since* the last def,
512 // But don't add edge from an instruction to itself!
513 for (int u = 1 + lastDefIdx; u < (int) i; u++)
514 if (regRefVec[u].first != node)
515 new SchedGraphEdge(regRefVec[u].first, node, regNum,
516 SchedGraphEdge::AntiDep);
519 { // Each use gets a true edge from the last def
521 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum);
529 SchedGraph::addSSAEdge(SchedGraphNode* node,
531 const TargetMachine& target)
533 if (!val->isInstruction()) return;
535 const Instruction* thisVMInstr = node->getInstr();
536 const Instruction* defVMInstr = val->castInstructionAsserting();
538 // Phi instructions are the only ones that produce a value but don't get
539 // any non-dummy machine instructions. Return here as an optimization.
541 if (defVMInstr->isPHINode())
544 // Now add the graph edge for the appropriate machine instruction(s).
545 // Note that multiple machine instructions generated for the
546 // def VM instruction may modify the register for the def value.
548 MachineCodeForVMInstr& defMvec = defVMInstr->getMachineInstrVec();
549 const MachineInstrInfo& mii = target.getInstrInfo();
551 for (unsigned i=0, N=defMvec.size(); i < N; i++)
552 for (int o=0, N = mii.getNumOperands(defMvec[i]->getOpCode()); o < N; o++)
554 const MachineOperand& defOp = defMvec[i]->getOperand(o);
557 && (defOp.getOperandType() == MachineOperand::MO_VirtualRegister
558 || defOp.getOperandType() == MachineOperand::MO_CCRegister)
559 && (defOp.getVRegValue() == val))
561 // this instruction does define value `val'.
562 // if there is a node for it in the same graph, add an edge.
563 SchedGraphNode* defNode = this->getGraphNodeForInstr(defMvec[i]);
564 if (defNode != NULL && defNode != node)
565 (void) new SchedGraphEdge(defNode, node, val);
572 SchedGraph::addEdgesForInstruction(SchedGraphNode* node,
573 NodeToRegRefMap& regToRefVecMap,
574 const TargetMachine& target)
576 const Instruction& instr = * node->getInstr(); // No dummy nodes here!
577 const MachineInstr& minstr = * node->getMachineInstr();
579 // Add incoming edges for the following:
580 // (1) operands of the machine instruction, including hidden operands
581 // (2) machine register dependences
582 // (3) other resource dependences for the machine instruction, if any
583 // Also, note any uses or defs of machine registers.
585 for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
587 const MachineOperand& mop = minstr.getOperand(i);
589 // if this writes to a machine register other than the hardwired
590 // "zero" register used on many processors, record the reference.
591 if (mop.getOperandType() == MachineOperand::MO_MachineRegister
592 && (mop.getMachineRegNum()
593 == (unsigned) target.getRegInfo().getZeroRegNum()))
595 regToRefVecMap[mop.getMachineRegNum()].
596 push_back(make_pair(node, i));
599 // ignore all other def operands
600 if (minstr.operandIsDefined(i))
603 switch(mop.getOperandType())
605 case MachineOperand::MO_VirtualRegister:
606 case MachineOperand::MO_CCRegister:
607 if (mop.getVRegValue())
608 addSSAEdge(node, mop.getVRegValue(), target);
611 case MachineOperand::MO_MachineRegister:
614 case MachineOperand::MO_SignExtendedImmed:
615 case MachineOperand::MO_UnextendedImmed:
616 case MachineOperand::MO_PCRelativeDisp:
617 break; // nothing to do for immediate fields
620 assert(0 && "Unknown machine operand type in SchedGraph builder");
625 // add all true, anti,
626 // and output dependences for this register. but ignore
632 SchedGraph::buildGraph(const TargetMachine& target)
634 const MachineInstrInfo& mii = target.getInstrInfo();
635 const BasicBlock* bb = bbVec[0];
637 assert(bbVec.size() == 1 && "Only handling a single basic block here");
639 // Use this data structures to note all LLVM memory instructions.
640 // We use this to add memory dependence edges without a second full walk.
642 vector<const Instruction*> memVec;
644 // Use this data structures to note any uses or definitions of
645 // machine registers so we can add edges for those later without
646 // extra passes over the nodes.
647 // The vector holds an ordered list of references to the machine reg,
648 // ordered according to control-flow order. This only works for a
649 // single basic block, hence the assertion. Each reference is identified
650 // by the pair: <node, operand-number>.
652 NodeToRegRefMap regToRefVecMap;
654 // Make a dummy root node. We'll add edges to the real roots later.
655 graphRoot = new SchedGraphNode(0, NULL, NULL, target);
656 graphLeaf = new SchedGraphNode(1, NULL, NULL, target);
658 //----------------------------------------------------------------
659 // First add nodes for all the machine instructions in the basic block.
660 // This greatly simplifies identifing which edges to add.
661 // Also, remember the load/store instructions to add memory deps later.
662 //----------------------------------------------------------------
664 for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
666 const Instruction *instr = *II;
667 const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
668 for (unsigned i=0, N=mvec.size(); i < N; i++)
669 if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
671 SchedGraphNode* node = new SchedGraphNode(getNumNodes(),
672 instr, mvec[i], target);
673 this->noteGraphNodeForInstr(mvec[i], node);
676 if (instr->getOpcode() == Instruction::Load ||
677 instr->getOpcode() == Instruction::Store)
678 memVec.push_back(instr);
681 //----------------------------------------------------------------
682 // Now add the edges.
683 //----------------------------------------------------------------
685 // First, add edges to the terminator instruction of the basic block.
686 this->addCDEdges(bb->getTerminator(), target);
688 // Then add memory dep edges: store->load, load->store, and store->store
689 this->addMemEdges(memVec, target);
691 // Then add other edges for all instructions in the block.
692 for (SchedGraph::iterator GI = this->begin(); GI != this->end(); ++GI)
694 SchedGraphNode* node = (*GI).second;
695 addEdgesForInstruction(node, regToRefVecMap, target);
698 // Then add edges for dependences on machine registers
699 this->addMachineRegEdges(regToRefVecMap, target);
701 // Finally, add edges from the dummy root and to dummy leaf
702 this->addDummyEdges();
707 // class SchedGraphSet
711 SchedGraphSet::SchedGraphSet(const Method* _method,
712 const TargetMachine& target) :
715 buildGraphsForMethod(method, target);
720 SchedGraphSet::~SchedGraphSet()
722 // delete all the graphs
723 for (iterator I=begin(); I != end(); ++I)
729 SchedGraphSet::dump() const
731 cout << "======== Sched graphs for method `"
732 << (method->hasName()? method->getName() : "???")
733 << "' ========" << endl << endl;
735 for (const_iterator I=begin(); I != end(); ++I)
738 cout << endl << "====== End graphs for method `"
739 << (method->hasName()? method->getName() : "")
740 << "' ========" << endl << endl;
745 SchedGraphSet::buildGraphsForMethod(const Method *method,
746 const TargetMachine& target)
748 for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI)
750 SchedGraph* graph = new SchedGraph(*BI, target);
751 this->noteGraphForBlock(*BI, graph);
758 operator<<(ostream& os, const SchedGraphEdge& edge)
760 os << "edge [" << edge.src->getNodeId() << "] -> ["
761 << edge.sink->getNodeId() << "] : ";
763 switch(edge.depType) {
764 case SchedGraphEdge::CtrlDep: os<< "Control Dep"; break;
765 case SchedGraphEdge::DefUseDep: os<< "Reg Value " << edge.val; break;
766 case SchedGraphEdge::MemoryDep: os<< "Mem Value " << edge.val; break;
767 case SchedGraphEdge::MachineRegister: os<< "Reg " <<edge.machineRegNum;break;
768 case SchedGraphEdge::MachineResource: os<<"Resource "<<edge.resourceId;break;
769 default: assert(0); break;
772 os << " : delay = " << edge.minDelay << endl;
778 operator<<(ostream& os, const SchedGraphNode& node)
781 os << "Node " << node.nodeId << " : "
782 << "latency = " << node.latency << endl;
786 if (node.getMachineInstr() == NULL)
787 os << "(Dummy node)" << endl;
790 os << *node.getMachineInstr() << endl;
793 os << node.inEdges.size() << " Incoming Edges:" << endl;
794 for (unsigned i=0, N=node.inEdges.size(); i < N; i++)
797 os << * node.inEdges[i];
801 os << node.outEdges.size() << " Outgoing Edges:" << endl;
802 for (unsigned i=0, N=node.outEdges.size(); i < N; i++)
805 os << * node.outEdges[i];