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 "llvm/InstrTypes.h"
16 #include "llvm/Instruction.h"
17 #include "llvm/BasicBlock.h"
18 #include "llvm/Method.h"
19 #include "llvm/CodeGen/SchedGraph.h"
20 #include "llvm/CodeGen/MachineInstr.h"
21 #include "llvm/Target/Machine.h"
22 #include "llvm/Support/StringExtras.h"
25 //************************* Class Implementations **************************/
28 // class SchedGraphEdge
32 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
33 SchedGraphNode* _sink,
34 SchedGraphEdgeDepType _depType,
35 DataDepOrderType _depOrderType,
40 depOrderType(_depOrderType),
42 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
44 src->addOutEdge(this);
45 sink->addInEdge(this);
50 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
51 SchedGraphNode* _sink,
53 DataDepOrderType _depOrderType,
58 depOrderType(_depOrderType),
60 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency())
62 src->addOutEdge(this);
63 sink->addInEdge(this);
68 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
69 SchedGraphNode* _sink,
71 DataDepOrderType _depOrderType,
75 depType(MachineRegister),
76 depOrderType(_depOrderType),
77 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
78 machineRegNum(_regNum)
80 src->addOutEdge(this);
81 sink->addInEdge(this);
86 SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
87 SchedGraphNode* _sink,
88 ResourceId _resourceId,
92 depType(MachineResource),
93 depOrderType(NonDataDep),
94 minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
95 resourceId(_resourceId)
97 src->addOutEdge(this);
98 sink->addInEdge(this);
101 void SchedGraphEdge::dump(int indent=0) const {
102 printIndent(indent); cout << *this;
107 // class SchedGraphNode
111 SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
112 const Instruction* _instr,
113 const MachineInstr* _minstr,
114 const TargetMachine& target)
122 MachineOpCode mopCode = minstr->getOpCode();
123 latency = target.getInstrInfo().hasResultInterlock(mopCode)
124 ? target.getInstrInfo().minLatency(mopCode)
125 : target.getInstrInfo().maxLatency(mopCode);
131 SchedGraphNode::~SchedGraphNode()
133 // a node deletes its outgoing edges only
134 for (unsigned i=0, N=outEdges.size(); i < N; i++)
138 void SchedGraphNode::dump(int indent=0) const {
139 printIndent(indent); cout << *this;
144 SchedGraphNode::addInEdge(SchedGraphEdge* edge)
146 inEdges.push_back(edge);
151 SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
153 outEdges.push_back(edge);
157 SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
159 assert(edge->getSink() == this);
160 for (iterator I = beginInEdges(); I != endInEdges(); ++I)
169 SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
171 assert(edge->getSrc() == this);
172 for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
181 SchedGraphNode::eraseAllEdges()
183 // Disconnect and delete all in-edges and out-edges for the node.
184 // Note that we delete the in-edges too since they have been
185 // disconnected from the source node and will not be deleted there.
186 for (iterator I = beginInEdges(); I != endInEdges(); ++I)
188 (*I)->getSrc()->removeOutEdge(*I);
191 for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
193 (*I)->getSink()->removeInEdge(*I);
207 SchedGraph::SchedGraph(const BasicBlock* bb,
208 const TargetMachine& target)
211 this->buildGraph(target);
216 SchedGraph::~SchedGraph()
218 // delete all the nodes. each node deletes its out-edges.
219 for (iterator I=begin(); I != end(); ++I)
225 SchedGraph::dump() const
227 cout << " Sched Graph for Basic Blocks: ";
228 for (unsigned i=0, N=bbVec.size(); i < N; i++)
230 cout << (bbVec[i]->hasName()? bbVec[i]->getName() : "block")
231 << " (" << bbVec[i] << ")"
232 << ((i == N-1)? "" : ", ");
235 cout << endl << endl << " Actual Root nodes : ";
236 for (unsigned i=0, N=graphRoot->outEdges.size(); i < N; i++)
237 cout << graphRoot->outEdges[i]->getSink()->getNodeId()
238 << ((i == N-1)? "" : ", ");
240 cout << endl << " Graph Nodes:" << endl;
241 for (const_iterator I=begin(); I != end(); ++I)
242 cout << endl << * (*I).second;
249 SchedGraph::addDummyEdges()
251 assert(graphRoot->outEdges.size() == 0);
253 for (const_iterator I=begin(); I != end(); ++I)
255 SchedGraphNode* node = (*I).second;
256 assert(node != graphRoot && node != graphLeaf);
257 if (node->beginInEdges() == node->endInEdges())
258 (void) new SchedGraphEdge(graphRoot, node, SchedGraphEdge::CtrlDep,
259 SchedGraphEdge::NonDataDep, 0);
260 if (node->beginOutEdges() == node->endOutEdges())
261 (void) new SchedGraphEdge(node, graphLeaf, SchedGraphEdge::CtrlDep,
262 SchedGraphEdge::NonDataDep, 0);
268 SchedGraph::addCDEdges(const TerminatorInst* term,
269 const TargetMachine& target)
271 const MachineInstrInfo& mii = target.getInstrInfo();
272 MachineCodeForVMInstr& termMvec = term->getMachineInstrVec();
274 // Find the first branch instr in the sequence of machine instrs for term
277 while (! mii.isBranch(termMvec[first]->getOpCode()))
279 assert(first < termMvec.size() &&
280 "No branch instructions for BR? Ok, but weird! Delete assertion.");
281 if (first == termMvec.size())
284 SchedGraphNode* firstBrNode = this->getGraphNodeForInstr(termMvec[first]);
286 // Add CD edges from each instruction in the sequence to the
287 // *last preceding* branch instr. in the sequence
289 for (int i = (int) termMvec.size()-1; i > (int) first; i--)
291 SchedGraphNode* toNode = this->getGraphNodeForInstr(termMvec[i]);
292 assert(toNode && "No node for instr generated for branch?");
294 for (int j = i-1; j >= 0; j--)
295 if (mii.isBranch(termMvec[j]->getOpCode()))
297 SchedGraphNode* brNode = this->getGraphNodeForInstr(termMvec[j]);
298 assert(brNode && "No node for instr generated for branch?");
299 (void) new SchedGraphEdge(brNode, toNode, SchedGraphEdge::CtrlDep,
300 SchedGraphEdge::NonDataDep, 0);
301 break; // only one incoming edge is enough
305 // Add CD edges from each instruction preceding the first branch
306 // to the first branch
308 for (int i = first-1; i >= 0; i--)
310 SchedGraphNode* fromNode = this->getGraphNodeForInstr(termMvec[i]);
311 assert(fromNode && "No node for instr generated for branch?");
312 (void) new SchedGraphEdge(fromNode, firstBrNode, SchedGraphEdge::CtrlDep,
313 SchedGraphEdge::NonDataDep, 0);
316 // Now add CD edges to the first branch instruction in the sequence
317 // from all preceding instructions in the basic block.
319 const BasicBlock* bb = term->getParent();
320 for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
322 if ((*II) == (const Instruction*) term) // special case, handled above
325 assert(! (*II)->isTerminator() && "Two terminators in basic block?");
327 const MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
328 for (unsigned i=0, N=mvec.size(); i < N; i++)
330 SchedGraphNode* fromNode = this->getGraphNodeForInstr(mvec[i]);
331 if (fromNode == NULL)
332 continue; // dummy instruction, e.g., PHI
334 (void) new SchedGraphEdge(fromNode, firstBrNode,
335 SchedGraphEdge::CtrlDep,
336 SchedGraphEdge::NonDataDep, 0);
338 // If we find any other machine instructions (other than due to
339 // the terminator) that also have delay slots, add an outgoing edge
340 // from the instruction to the instructions in the delay slots.
342 unsigned d = mii.getNumDelaySlots(mvec[i]->getOpCode());
343 assert(i+d < N && "Insufficient delay slots for instruction?");
345 for (unsigned j=1; j <= d; j++)
347 SchedGraphNode* toNode = this->getGraphNodeForInstr(mvec[i+j]);
348 assert(toNode && "No node for machine instr in delay slot?");
349 (void) new SchedGraphEdge(fromNode, toNode,
350 SchedGraphEdge::CtrlDep,
351 SchedGraphEdge::NonDataDep, 0);
359 SchedGraph::addMemEdges(const vector<const Instruction*>& memVec,
360 const TargetMachine& target)
362 const MachineInstrInfo& mii = target.getInstrInfo();
364 for (unsigned im=0, NM=memVec.size(); im < NM; im++)
366 const Instruction* fromInstr = memVec[im];
367 bool fromIsLoad = fromInstr->getOpcode() == Instruction::Load;
369 for (unsigned jm=im+1; jm < NM; jm++)
371 const Instruction* toInstr = memVec[jm];
372 bool toIsLoad = toInstr->getOpcode() == Instruction::Load;
373 SchedGraphEdge::DataDepOrderType depOrderType;
377 if (toIsLoad) continue; // both instructions are loads
378 depOrderType = SchedGraphEdge::AntiDep;
382 depOrderType = (toIsLoad)? SchedGraphEdge::TrueDep
383 : SchedGraphEdge::OutputDep;
386 MachineCodeForVMInstr& fromInstrMvec=fromInstr->getMachineInstrVec();
387 MachineCodeForVMInstr& toInstrMvec = toInstr->getMachineInstrVec();
389 // We have two VM memory instructions, and at least one is a store.
390 // Add edges between all machine load/store instructions.
392 for (unsigned i=0, N=fromInstrMvec.size(); i < N; i++)
394 MachineOpCode fromOpCode = fromInstrMvec[i]->getOpCode();
395 if (mii.isLoad(fromOpCode) || mii.isStore(fromOpCode))
397 SchedGraphNode* fromNode =
398 this->getGraphNodeForInstr(fromInstrMvec[i]);
399 assert(fromNode && "No node for memory instr?");
401 for (unsigned j=0, M=toInstrMvec.size(); j < M; j++)
403 MachineOpCode toOpCode = toInstrMvec[j]->getOpCode();
404 if (mii.isLoad(toOpCode) || mii.isStore(toOpCode))
406 SchedGraphNode* toNode =
407 this->getGraphNodeForInstr(toInstrMvec[j]);
408 assert(toNode && "No node for memory instr?");
410 (void) new SchedGraphEdge(fromNode, toNode,
411 SchedGraphEdge::MemoryDep,
422 typedef vector< pair<SchedGraphNode*, unsigned int> > RegRefVec;
424 // The following needs to be a class, not a typedef, so we can use
425 // an opaque declaration in SchedGraph.h
426 class NodeToRegRefMap: public hash_map<int, RegRefVec> {
427 typedef hash_map<int, RegRefVec>:: iterator iterator;
428 typedef hash_map<int, RegRefVec>::const_iterator const_iterator;
433 SchedGraph::addMachineRegEdges(NodeToRegRefMap& regToRefVecMap,
434 const TargetMachine& target)
436 assert(bbVec.size() == 1 && "Only handling a single basic block here");
438 // This assumes that such hardwired registers are never allocated
439 // to any LLVM value (since register allocation happens later), i.e.,
440 // any uses or defs of this register have been made explicit!
441 // Also assumes that two registers with different numbers are
444 for (NodeToRegRefMap::iterator I = regToRefVecMap.begin();
445 I != regToRefVecMap.end(); ++I)
447 int regNum = (*I).first;
448 RegRefVec& regRefVec = (*I).second;
450 // regRefVec is ordered by control flow order in the basic block
452 for (unsigned i=0; i < regRefVec.size(); ++i)
454 SchedGraphNode* node = regRefVec[i].first;
455 bool isDef = regRefVec[i].second;
458 { // Each def gets an output edge from the last def
460 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum,
461 SchedGraphEdge::OutputDep);
463 // Also, an anti edge from all uses *since* the last def,
464 // But don't add edge from an instruction to itself!
465 for (int u = 1 + lastDefIdx; u < (int) i; u++)
466 if (regRefVec[u].first != node)
467 new SchedGraphEdge(regRefVec[u].first, node, regNum,
468 SchedGraphEdge::AntiDep);
471 { // Each use gets a true edge from the last def
473 new SchedGraphEdge(regRefVec[lastDefIdx].first, node, regNum);
481 SchedGraph::addSSAEdge(SchedGraphNode* node,
483 const TargetMachine& target)
485 if (!val->isInstruction()) return;
487 const Instruction* thisVMInstr = node->getInstr();
488 const Instruction* defVMInstr = (const Instruction*) val;
490 // Phi instructions are the only ones that produce a value but don't get
491 // any non-dummy machine instructions. Return here as an optimization.
493 if (defVMInstr->isPHINode())
496 // Now add the graph edge for the appropriate machine instruction(s).
497 // Note that multiple machine instructions generated for the
498 // def VM instruction may modify the register for the def value.
500 MachineCodeForVMInstr& defMvec = defVMInstr->getMachineInstrVec();
501 const MachineInstrInfo& mii = target.getInstrInfo();
503 for (unsigned i=0, N=defMvec.size(); i < N; i++)
504 for (int o=0, N = mii.getNumOperands(defMvec[i]->getOpCode()); o < N; o++)
506 const MachineOperand& defOp = defMvec[i]->getOperand(o);
509 && (defOp.getOperandType() == MachineOperand::MO_VirtualRegister
510 || defOp.getOperandType() == MachineOperand::MO_CCRegister)
511 && (defOp.getVRegValue() == val))
513 // this instruction does define value `val'.
514 // if there is a node for it in the same graph, add an edge.
515 SchedGraphNode* defNode = this->getGraphNodeForInstr(defMvec[i]);
517 (void) new SchedGraphEdge(defNode, node, val);
524 SchedGraph::addEdgesForInstruction(SchedGraphNode* node,
525 NodeToRegRefMap& regToRefVecMap,
526 const TargetMachine& target)
528 const Instruction& instr = * node->getInstr(); // No dummy nodes here!
529 const MachineInstr& minstr = * node->getMachineInstr();
531 // Add incoming edges for the following:
532 // (1) operands of the machine instruction, including hidden operands
533 // (2) machine register dependences
534 // (3) other resource dependences for the machine instruction, if any
535 // Also, note any uses or defs of machine registers.
537 for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
539 const MachineOperand& mop = minstr.getOperand(i);
541 // if this writes to a machine register other than the hardwired
542 // "zero" register used on many processors, record the reference.
543 if (mop.getOperandType() == MachineOperand::MO_MachineRegister
544 && (! (target.zeroRegNum >= 0
545 && mop.getMachineRegNum()==(unsigned) target.zeroRegNum)))
547 regToRefVecMap[mop.getMachineRegNum()].
548 push_back(make_pair(node, i));
551 // ignore all other def operands
552 if (minstr.operandIsDefined(i))
555 switch(mop.getOperandType())
557 case MachineOperand::MO_VirtualRegister:
558 case MachineOperand::MO_CCRegister:
559 if (mop.getVRegValue())
560 addSSAEdge(node, mop.getVRegValue(), target);
563 case MachineOperand::MO_MachineRegister:
566 case MachineOperand::MO_SignExtendedImmed:
567 case MachineOperand::MO_UnextendedImmed:
568 case MachineOperand::MO_PCRelativeDisp:
569 break; // nothing to do for immediate fields
572 assert(0 && "Unknown machine operand type in SchedGraph builder");
577 // add all true, anti,
578 // and output dependences for this register. but ignore
584 SchedGraph::buildGraph(const TargetMachine& target)
586 const MachineInstrInfo& mii = target.getInstrInfo();
587 const BasicBlock* bb = bbVec[0];
589 assert(bbVec.size() == 1 && "Only handling a single basic block here");
591 // Use this data structures to note all LLVM memory instructions.
592 // We use this to add memory dependence edges without a second full walk.
594 vector<const Instruction*> memVec;
596 // Use this data structures to note any uses or definitions of
597 // machine registers so we can add edges for those later without
598 // extra passes over the nodes.
599 // The vector holds an ordered list of references to the machine reg,
600 // ordered according to control-flow order. This only works for a
601 // single basic block, hence the assertion. Each reference is identified
602 // by the pair: <node, operand-number>.
604 NodeToRegRefMap regToRefVecMap;
606 // Make a dummy root node. We'll add edges to the real roots later.
607 graphRoot = new SchedGraphNode(0, NULL, NULL, target);
608 graphLeaf = new SchedGraphNode(1, NULL, NULL, target);
610 //----------------------------------------------------------------
611 // First add nodes for all the machine instructions in the basic block.
612 // This greatly simplifies identifing which edges to add.
613 // Also, remember the load/store instructions to add memory deps later.
614 //----------------------------------------------------------------
616 for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
618 const Instruction *instr = *II;
619 const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
620 for (unsigned i=0, N=mvec.size(); i < N; i++)
621 if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
623 SchedGraphNode* node = new SchedGraphNode(getNumNodes(),
624 instr, mvec[i], target);
625 this->noteGraphNodeForInstr(mvec[i], node);
628 if (instr->getOpcode() == Instruction::Load ||
629 instr->getOpcode() == Instruction::Store)
630 memVec.push_back(instr);
633 //----------------------------------------------------------------
634 // Now add the edges.
635 //----------------------------------------------------------------
637 // First, add edges to the terminator instruction of the basic block.
638 this->addCDEdges(bb->getTerminator(), target);
640 // Then add memory dep edges: store->load, load->store, and store->store
641 this->addMemEdges(memVec, target);
643 // Then add other edges for all instructions in the block.
644 for (SchedGraph::iterator GI = this->begin(); GI != this->end(); ++GI)
646 SchedGraphNode* node = (*GI).second;
647 addEdgesForInstruction(node, regToRefVecMap, target);
650 // Then add edges for dependences on machine registers
651 this->addMachineRegEdges(regToRefVecMap, target);
653 // Finally, add edges from the dummy root and to dummy leaf
654 this->addDummyEdges();
659 // class SchedGraphSet
663 SchedGraphSet::SchedGraphSet(const Method* _method,
664 const TargetMachine& target) :
667 buildGraphsForMethod(method, target);
672 SchedGraphSet::~SchedGraphSet()
674 // delete all the graphs
675 for (iterator I=begin(); I != end(); ++I)
681 SchedGraphSet::dump() const
683 cout << "======== Sched graphs for method `"
684 << (method->hasName()? method->getName() : "???")
685 << "' ========" << endl << endl;
687 for (const_iterator I=begin(); I != end(); ++I)
690 cout << endl << "====== End graphs for method `"
691 << (method->hasName()? method->getName() : "")
692 << "' ========" << endl << endl;
697 SchedGraphSet::buildGraphsForMethod(const Method *method,
698 const TargetMachine& target)
700 for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI)
702 SchedGraph* graph = new SchedGraph(*BI, target);
703 this->noteGraphForBlock(*BI, graph);
710 operator<<(ostream& os, const SchedGraphEdge& edge)
712 os << "edge [" << edge.src->getNodeId() << "] -> ["
713 << edge.sink->getNodeId() << "] : ";
715 switch(edge.depType) {
716 case SchedGraphEdge::CtrlDep: os<< "Control Dep"; break;
717 case SchedGraphEdge::DefUseDep: os<< "Reg Value " << edge.val; break;
718 case SchedGraphEdge::MemoryDep: os<< "Mem Value " << edge.val; break;
719 case SchedGraphEdge::MachineRegister: os<< "Reg " <<edge.machineRegNum;break;
720 case SchedGraphEdge::MachineResource: os<<"Resource "<<edge.resourceId;break;
721 default: assert(0); break;
724 os << " : delay = " << edge.minDelay << endl;
730 operator<<(ostream& os, const SchedGraphNode& node)
733 os << "Node " << node.nodeId << " : "
734 << "latency = " << node.latency << endl;
738 if (node.getMachineInstr() == NULL)
739 os << "(Dummy node)" << endl;
742 os << *node.getMachineInstr() << endl;
745 os << node.inEdges.size() << " Incoming Edges:" << endl;
746 for (unsigned i=0, N=node.inEdges.size(); i < N; i++)
749 os << * node.inEdges[i];
753 os << node.outEdges.size() << " Outgoing Edges:" << endl;
754 for (unsigned i=0, N=node.outEdges.size(); i < N; i++)
757 os << * node.outEdges[i];