1 //===-- MSchedGraph.h - Scheduling Graph ------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // A graph class for dependencies
12 //===----------------------------------------------------------------------===//
13 #define DEBUG_TYPE "ModuloSched"
15 #include "MSchedGraph.h"
16 #include "llvm/CodeGen/MachineBasicBlock.h"
17 #include "llvm/Target/TargetInstrInfo.h"
18 #include "Support/Debug.h"
22 MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst,
25 : Inst(inst), Parent(graph), latency(late) {
28 graph->addNode(inst, this);
31 void MSchedGraphNode::print(std::ostream &os) const {
32 os << "MSehedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n";
35 MSchedGraphEdge MSchedGraphNode::getInEdge(MSchedGraphNode *pred) {
36 //Loop over all the successors of our predecessor
37 //return the edge the corresponds to this in edge
38 for(MSchedGraphNode::succ_iterator I = pred->succ_begin(), E = pred->succ_end();
43 assert(0 && "Should have found edge between this node and its predecessor!");
47 void MSchedGraph::addNode(const MachineInstr *MI,
48 MSchedGraphNode *node) {
50 //Make sure node does not already exist
51 assert(GraphMap.find(MI) == GraphMap.end()
52 && "New MSchedGraphNode already exists for this instruction");
57 MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ)
58 : BB(bb), Target(targ) {
60 //Make sure BB is not null,
61 assert(BB != NULL && "Basic Block is null");
63 DEBUG(std::cerr << "Constructing graph for " << bb << "\n");
65 //Create nodes and edges for this BB
69 MSchedGraph::~MSchedGraph () {
70 for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I)
74 void MSchedGraph::buildNodesAndEdges() {
76 //Get Machine target information for calculating latency
77 const TargetInstrInfo &MTI = Target.getInstrInfo();
79 std::vector<MSchedGraphNode*> memInstructions;
80 std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap;
81 std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap;
83 //Save PHI instructions to deal with later
84 std::vector<const MachineInstr*> phiInstrs;
86 //Loop over instructions in MBB and add nodes and edges
87 for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); MI != e; ++MI) {
88 //Get each instruction of machine basic block, get the delay
89 //using the op code, create a new node for it, and add to the
92 MachineOpCode MIopCode = MI->getOpcode();
95 //Check if subsequent instructions can be issued before
96 //the result is ready, if so use min delay.
97 if(MTI.hasResultInterlock(MIopCode))
98 delay = MTI.minLatency(MIopCode);
100 delay = MTI.maxLatency(MIopCode);
102 //Create new node for this machine instruction and add to the graph.
103 //Create only if not a nop
104 if(MTI.isNop(MIopCode))
107 //Add PHI to phi instruction list to be processed later
108 if (MIopCode == TargetInstrInfo::PHI)
109 phiInstrs.push_back(MI);
111 //Node is created and added to the graph automatically
112 MSchedGraphNode *node = new MSchedGraphNode(MI, this, delay);
114 DEBUG(std::cerr << "Created Node: " << *node << "\n");
116 //Check OpCode to keep track of memory operations to add memory dependencies later.
117 MachineOpCode opCode = MI->getOpcode();
119 if(MTI.isLoad(opCode) || MTI.isStore(opCode))
120 memInstructions.push_back(node);
122 //Loop over all operands, and put them into the register number to
123 //graph node map for determining dependencies
124 //If an operands is a use/def, we have an anti dependence to itself
125 for(unsigned i=0; i < MI->getNumOperands(); ++i) {
127 const MachineOperand &mOp = MI->getOperand(i);
129 //Check if it has an allocated register (Note: this means it
130 //is greater then zero because zero is a special register for
131 //Sparc that holds the constant zero
132 if(mOp.hasAllocatedReg()) {
133 int regNum = mOp.getReg();
136 regNumtoNodeMap[regNum].push_back(std::make_pair(i, node));
141 //Add virtual registers dependencies
142 //Check if any exist in the value map already and create dependencies
144 if(mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) {
146 //Make sure virtual register value is not null
147 assert((mOp.getVRegValue() != NULL) && "Null value is defined");
149 //Check if this is a read operation in a phi node, if so DO NOT PROCESS
150 if(mOp.isUse() && (MIopCode == TargetInstrInfo::PHI))
154 if (const Value* srcI = mOp.getVRegValue()) {
156 //Find value in the map
157 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
158 = valuetoNodeMap.find(srcI);
160 //If there is something in the map already, add edges from
162 //to this one we are processing
163 if(V != valuetoNodeMap.end()) {
164 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef());
167 V->second.push_back(std::make_pair(i,node));
169 //Otherwise put it in the map
172 valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node));
177 addMemEdges(memInstructions);
178 addMachRegEdges(regNumtoNodeMap);
180 //Finally deal with PHI Nodes and Value*
181 for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), E = phiInstrs.end(); I != E; ++I) {
182 //Get Node for this instruction
183 MSchedGraphNode *node = find(*I)->second;
185 //Loop over operands for this instruction and add value edges
186 for(unsigned i=0; i < (*I)->getNumOperands(); ++i) {
188 const MachineOperand &mOp = (*I)->getOperand(i);
189 if((mOp.getType() == MachineOperand::MO_VirtualRegister || mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) {
190 //find the value in the map
191 if (const Value* srcI = mOp.getVRegValue()) {
193 //Find value in the map
194 std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
195 = valuetoNodeMap.find(srcI);
197 //If there is something in the map already, add edges from
199 //to this one we are processing
200 if(V != valuetoNodeMap.end()) {
201 addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 1);
209 void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
210 MSchedGraphNode *destNode, bool nodeIsUse,
211 bool nodeIsDef, int diff) {
213 for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(),
214 E = NodesInMap.end(); I != E; ++I) {
216 //Get node in vectors machine operand that is the same value as node
217 MSchedGraphNode *srcNode = I->second;
218 MachineOperand mOp = srcNode->getInst()->getOperand(I->first);
220 //Node is a Def, so add output dep.
223 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
224 MSchedGraphEdge::AntiDep, diff);
226 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
227 MSchedGraphEdge::OutputDep, diff);
232 srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
233 MSchedGraphEdge::TrueDep, diff);
239 void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) {
240 //Loop over all machine registers in the map, and add dependencies
241 //between the instructions that use it
242 typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap;
243 for(regNodeMap::iterator I = regNumtoNodeMap.begin(); I != regNumtoNodeMap.end(); ++I) {
244 //Get the register number
245 int regNum = (*I).first;
247 //Get Vector of nodes that use this register
248 std::vector<OpIndexNodePair> Nodes = (*I).second;
250 //Loop over nodes and determine the dependence between the other
251 //nodes in the vector
252 for(unsigned i =0; i < Nodes.size(); ++i) {
254 //Get src node operator index that uses this machine register
255 int srcOpIndex = Nodes[i].first;
257 //Get the actual src Node
258 MSchedGraphNode *srcNode = Nodes[i].second;
261 const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex);
263 bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse();
264 bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef();
267 //Look at all instructions after this in execution order
268 for(unsigned j=i+1; j < Nodes.size(); ++j) {
270 //Sink node is a write
271 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
272 //Src only uses the register (read)
274 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
275 MSchedGraphEdge::AntiDep);
277 else if(srcIsUseandDef) {
278 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
279 MSchedGraphEdge::AntiDep);
281 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
282 MSchedGraphEdge::OutputDep);
285 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
286 MSchedGraphEdge::OutputDep);
288 //Dest node is a read
290 if(!srcIsUse || srcIsUseandDef)
291 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
292 MSchedGraphEdge::TrueDep);
297 //Look at all the instructions before this one since machine registers
298 //could live across iterations.
299 for(unsigned j = 0; j < i; ++j) {
300 //Sink node is a write
301 if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
302 //Src only uses the register (read)
304 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
305 MSchedGraphEdge::AntiDep, 1);
307 else if(srcIsUseandDef) {
308 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
309 MSchedGraphEdge::AntiDep, 1);
311 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
312 MSchedGraphEdge::OutputDep, 1);
315 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
316 MSchedGraphEdge::OutputDep, 1);
318 //Dest node is a read
320 if(!srcIsUse || srcIsUseandDef)
321 srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
322 MSchedGraphEdge::TrueDep,1 );
334 void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) {
336 //Get Target machine instruction info
337 const TargetInstrInfo& TMI = Target.getInstrInfo();
339 //Loop over all memory instructions in the vector
340 //Knowing that they are in execution, add true, anti, and output dependencies
341 for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) {
343 //Get the machine opCode to determine type of memory instruction
344 MachineOpCode srcNodeOpCode = memInst[srcIndex]->getInst()->getOpcode();
346 //All instructions after this one in execution order have an iteration delay of 0
347 for(unsigned destIndex = srcIndex + 1; destIndex < memInst.size(); ++destIndex) {
349 //source is a Load, so add anti-dependencies (store after load)
350 if(TMI.isLoad(srcNodeOpCode))
351 if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
352 memInst[srcIndex]->addOutEdge(memInst[destIndex],
353 MSchedGraphEdge::MemoryDep,
354 MSchedGraphEdge::AntiDep);
356 //If source is a store, add output and true dependencies
357 if(TMI.isStore(srcNodeOpCode)) {
358 if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
359 memInst[srcIndex]->addOutEdge(memInst[destIndex],
360 MSchedGraphEdge::MemoryDep,
361 MSchedGraphEdge::OutputDep);
363 memInst[srcIndex]->addOutEdge(memInst[destIndex],
364 MSchedGraphEdge::MemoryDep,
365 MSchedGraphEdge::TrueDep);
369 //All instructions before the src in execution order have an iteration delay of 1
370 for(unsigned destIndex = 0; destIndex < srcIndex; ++destIndex) {
371 //source is a Load, so add anti-dependencies (store after load)
372 if(TMI.isLoad(srcNodeOpCode))
373 if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
374 memInst[srcIndex]->addOutEdge(memInst[destIndex],
375 MSchedGraphEdge::MemoryDep,
376 MSchedGraphEdge::AntiDep, 1);
377 if(TMI.isStore(srcNodeOpCode)) {
378 if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
379 memInst[srcIndex]->addOutEdge(memInst[destIndex],
380 MSchedGraphEdge::MemoryDep,
381 MSchedGraphEdge::OutputDep, 1);
383 memInst[srcIndex]->addOutEdge(memInst[destIndex],
384 MSchedGraphEdge::MemoryDep,
385 MSchedGraphEdge::TrueDep, 1);