lib/CodeGen/ModuloScheduling/MSchedGraph.cpp

   1 //===-- MSchedGraph.h - Scheduling Graph ------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // A graph class for dependencies
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #define DEBUG_TYPE "ModuloSched"
  14
  15 #include "MSchedGraph.h"
  16 #include "llvm/CodeGen/MachineBasicBlock.h"
  17 #include "llvm/Target/TargetInstrInfo.h"
  18 #include "Support/Debug.h"
  19 #include <iostream>
  20 using namespace llvm;
  21
  22 MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst,
  23                                  MSchedGraph *graph,
  24                                  unsigned late)
  25   : Inst(inst), Parent(graph), latency(late) {
  26
  27   //Add to the graph
  28   graph->addNode(inst, this);
  29 }
  30
  31 void MSchedGraphNode::print(std::ostream &os) const {
  32   os << "MSchedGraphNode: Inst=" << *Inst << ", latency= " << latency << "\n";
  33 }
  34
  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();
  39       I != E; ++I) {
  40     if(*I == this)
  41       return I.getEdge();
  42   }
  43   assert(0 && "Should have found edge between this node and its predecessor!");
  44
  45 }
  46
  47 unsigned MSchedGraphNode::getInEdgeNum(MSchedGraphNode *pred) {
  48   //Loop over all the successors of our predecessor
  49   //return the edge the corresponds to this in edge
  50   int count = 0;
  51   for(MSchedGraphNode::succ_iterator I = pred->succ_begin(), E = pred->succ_end();
  52       I != E; ++I) {
  53     if(*I == this)
  54       return count;
  55     count++;
  56   }
  57   assert(0 && "Should have found edge between this node and its predecessor!");
  58   abort();
  59 }
  60 bool MSchedGraphNode::isSuccessor(MSchedGraphNode *succ) {
  61   for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
  62     if(*I == succ)
  63       return true;
  64   return false;
  65 }
  66
  67
  68 bool MSchedGraphNode::isPredecessor(MSchedGraphNode *pred) {
  69   if(find( Predecessors.begin(),  Predecessors.end(), pred) !=   Predecessors.end())
  70     return true;
  71   else
  72     return false;
  73 }
  74
  75
  76 void MSchedGraph::addNode(const MachineInstr *MI,
  77                           MSchedGraphNode *node) {
  78
  79   //Make sure node does not already exist
  80   assert(GraphMap.find(MI) == GraphMap.end()
  81          && "New MSchedGraphNode already exists for this instruction");
  82
  83   GraphMap[MI] = node;
  84 }
  85
  86 MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ)
  87   : BB(bb), Target(targ) {
  88
  89   //Make sure BB is not null,
  90   assert(BB != NULL && "Basic Block is null");
  91
  92   DEBUG(std::cerr << "Constructing graph for " << bb << "\n");
  93
  94   //Create nodes and edges for this BB
  95   buildNodesAndEdges();
  96 }
  97
  98 MSchedGraph::~MSchedGraph () {
  99   for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I)
 100     delete I->second;
 101 }
 102
 103 void MSchedGraph::buildNodesAndEdges() {
 104
 105   //Get Machine target information for calculating latency
 106   const TargetInstrInfo &MTI = Target.getInstrInfo();
 107
 108   std::vector<MSchedGraphNode*> memInstructions;
 109   std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap;
 110   std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap;
 111
 112   //Save PHI instructions to deal with later
 113   std::vector<const MachineInstr*> phiInstrs;
 114
 115   //Loop over instructions in MBB and add nodes and edges
 116   for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end(); MI != e; ++MI) {
 117     //Get each instruction of machine basic block, get the delay
 118     //using the op code, create a new node for it, and add to the
 119     //graph.
 120
 121     MachineOpCode MIopCode = MI->getOpcode();
 122     int delay;
 123
 124 #if 0  // FIXME: LOOK INTO THIS
 125     //Check if subsequent instructions can be issued before
 126     //the result is ready, if so use min delay.
 127     if(MTI.hasResultInterlock(MIopCode))
 128       delay = MTI.minLatency(MIopCode);
 129     else
 130 #endif
 131       /// FIxME: get this from the sched class.
 132       delay = 7; //MTI.maxLatency(MIopCode);
 133
 134     //Create new node for this machine instruction and add to the graph.
 135     //Create only if not a nop
 136     if(MTI.isNop(MIopCode))
 137       continue;
 138
 139     //Add PHI to phi instruction list to be processed later
 140     if (MIopCode == TargetInstrInfo::PHI)
 141       phiInstrs.push_back(MI);
 142
 143     //Node is created and added to the graph automatically
 144     MSchedGraphNode *node =  new MSchedGraphNode(MI, this, delay);
 145
 146     DEBUG(std::cerr << "Created Node: " << *node << "\n");
 147
 148     //Check OpCode to keep track of memory operations to add memory dependencies later.
 149     MachineOpCode opCode = MI->getOpcode();
 150
 151     if(MTI.isLoad(opCode) || MTI.isStore(opCode))
 152       memInstructions.push_back(node);
 153
 154     //Loop over all operands, and put them into the register number to
 155     //graph node map for determining dependencies
 156     //If an operands is a use/def, we have an anti dependence to itself
 157     for(unsigned i=0; i < MI->getNumOperands(); ++i) {
 158       //Get Operand
 159       const MachineOperand &mOp = MI->getOperand(i);
 160
 161       //Check if it has an allocated register (Note: this means it
 162       //is greater then zero because zero is a special register for
 163       //Sparc that holds the constant zero
 164       if(mOp.hasAllocatedReg()) {
 165         int regNum = mOp.getReg();
 166
 167         //Put into our map
 168         regNumtoNodeMap[regNum].push_back(std::make_pair(i, node));
 169         continue;
 170       }
 171
 172
 173       //Add virtual registers dependencies
 174       //Check if any exist in the value map already and create dependencies
 175       //between them.
 176       if(mOp.getType() == MachineOperand::MO_VirtualRegister ||  mOp.getType() == MachineOperand::MO_CCRegister) {
 177
 178         //Make sure virtual register value is not null
 179         assert((mOp.getVRegValue() != NULL) && "Null value is defined");
 180
 181         //Check if this is a read operation in a phi node, if so DO NOT PROCESS
 182         if(mOp.isUse() && (MIopCode == TargetInstrInfo::PHI))
 183           continue;
 184
 185
 186         if (const Value* srcI = mOp.getVRegValue()) {
 187
 188           //Find value in the map
 189           std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 190             = valuetoNodeMap.find(srcI);
 191
 192           //If there is something in the map already, add edges from
 193           //those instructions
 194           //to this one we are processing
 195           if(V != valuetoNodeMap.end()) {
 196             addValueEdges(V->second, node, mOp.isUse(), mOp.isDef());
 197
 198             //Add to value map
 199             V->second.push_back(std::make_pair(i,node));
 200           }
 201           //Otherwise put it in the map
 202           else
 203             //Put into value map
 204           valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node));
 205         }
 206       }
 207     }
 208   }
 209   addMemEdges(memInstructions);
 210   addMachRegEdges(regNumtoNodeMap);
 211
 212   //Finally deal with PHI Nodes and Value*
 213   for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), E = phiInstrs.end(); I != E;  ++I) {
 214     //Get Node for this instruction
 215     MSchedGraphNode *node = find(*I)->second;
 216
 217     //Loop over operands for this instruction and add value edges
 218     for(unsigned i=0; i < (*I)->getNumOperands(); ++i) {
 219       //Get Operand
 220       const MachineOperand &mOp = (*I)->getOperand(i);
 221       if((mOp.getType() == MachineOperand::MO_VirtualRegister ||  mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) {
 222         //find the value in the map
 223         if (const Value* srcI = mOp.getVRegValue()) {
 224
 225           //Find value in the map
 226           std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 227             = valuetoNodeMap.find(srcI);
 228
 229           //If there is something in the map already, add edges from
 230           //those instructions
 231           //to this one we are processing
 232           if(V != valuetoNodeMap.end()) {
 233             addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 1);
 234           }
 235         }
 236       }
 237     }
 238   }
 239 }
 240
 241 void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
 242                                 MSchedGraphNode *destNode, bool nodeIsUse,
 243                                 bool nodeIsDef, int diff) {
 244
 245   for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(),
 246         E = NodesInMap.end(); I != E; ++I) {
 247
 248     //Get node in vectors machine operand that is the same value as node
 249     MSchedGraphNode *srcNode = I->second;
 250     MachineOperand mOp = srcNode->getInst()->getOperand(I->first);
 251
 252     //Node is a Def, so add output dep.
 253     if(nodeIsDef) {
 254       if(mOp.isUse())
 255         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 256                             MSchedGraphEdge::AntiDep, diff);
 257       if(mOp.isDef())
 258         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 259                             MSchedGraphEdge::OutputDep, diff);
 260
 261     }
 262     if(nodeIsUse) {
 263       if(mOp.isDef())
 264         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 265                             MSchedGraphEdge::TrueDep, diff);
 266     }
 267   }
 268 }
 269
 270
 271 void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) {
 272   //Loop over all machine registers in the map, and add dependencies
 273   //between the instructions that use it
 274   typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap;
 275   for(regNodeMap::iterator I = regNumtoNodeMap.begin(); I != regNumtoNodeMap.end(); ++I) {
 276     //Get the register number
 277     int regNum = (*I).first;
 278
 279     //Get Vector of nodes that use this register
 280     std::vector<OpIndexNodePair> Nodes = (*I).second;
 281
 282     //Loop over nodes and determine the dependence between the other
 283     //nodes in the vector
 284     for(unsigned i =0; i < Nodes.size(); ++i) {
 285
 286       //Get src node operator index that uses this machine register
 287       int srcOpIndex = Nodes[i].first;
 288
 289       //Get the actual src Node
 290       MSchedGraphNode *srcNode = Nodes[i].second;
 291
 292       //Get Operand
 293       const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex);
 294
 295       bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse();
 296       bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef();
 297
 298
 299       //Look at all instructions after this in execution order
 300       for(unsigned j=i+1; j < Nodes.size(); ++j) {
 301
 302         //Sink node is a write
 303         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 304                       //Src only uses the register (read)
 305             if(srcIsUse)
 306               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 307                                   MSchedGraphEdge::AntiDep);
 308
 309             else if(srcIsUseandDef) {
 310               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 311                                   MSchedGraphEdge::AntiDep);
 312
 313               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 314                                   MSchedGraphEdge::OutputDep);
 315             }
 316             else
 317               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 318                                   MSchedGraphEdge::OutputDep);
 319         }
 320         //Dest node is a read
 321         else {
 322           if(!srcIsUse || srcIsUseandDef)
 323             srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 324                                 MSchedGraphEdge::TrueDep);
 325         }
 326
 327       }
 328
 329       //Look at all the instructions before this one since machine registers
 330       //could live across iterations.
 331       for(unsigned j = 0; j < i; ++j) {
 332                 //Sink node is a write
 333         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 334                       //Src only uses the register (read)
 335             if(srcIsUse)
 336               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 337                                   MSchedGraphEdge::AntiDep, 1);
 338
 339             else if(srcIsUseandDef) {
 340               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 341                                   MSchedGraphEdge::AntiDep, 1);
 342
 343               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 344                                   MSchedGraphEdge::OutputDep, 1);
 345             }
 346             else
 347               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 348                                   MSchedGraphEdge::OutputDep, 1);
 349         }
 350         //Dest node is a read
 351         else {
 352           if(!srcIsUse || srcIsUseandDef)
 353             srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 354                                 MSchedGraphEdge::TrueDep,1 );
 355         }
 356
 357
 358       }
 359
 360     }
 361
 362   }
 363
 364 }
 365
 366 void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) {
 367
 368   //Get Target machine instruction info
 369   const TargetInstrInfo& TMI = Target.getInstrInfo();
 370
 371   //Loop over all memory instructions in the vector
 372   //Knowing that they are in execution, add true, anti, and output dependencies
 373   for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) {
 374
 375     //Get the machine opCode to determine type of memory instruction
 376     MachineOpCode srcNodeOpCode = memInst[srcIndex]->getInst()->getOpcode();
 377
 378     //All instructions after this one in execution order have an iteration delay of 0
 379     for(unsigned destIndex = srcIndex + 1; destIndex < memInst.size(); ++destIndex) {
 380
 381       //source is a Load, so add anti-dependencies (store after load)
 382       if(TMI.isLoad(srcNodeOpCode))
 383         if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
 384           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 385                               MSchedGraphEdge::MemoryDep,
 386                               MSchedGraphEdge::AntiDep);
 387
 388       //If source is a store, add output and true dependencies
 389       if(TMI.isStore(srcNodeOpCode)) {
 390         if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
 391            memInst[srcIndex]->addOutEdge(memInst[destIndex],
 392                               MSchedGraphEdge::MemoryDep,
 393                               MSchedGraphEdge::OutputDep);
 394         else
 395           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 396                               MSchedGraphEdge::MemoryDep,
 397                               MSchedGraphEdge::TrueDep);
 398       }
 399     }
 400
 401     //All instructions before the src in execution order have an iteration delay of 1
 402     for(unsigned destIndex = 0; destIndex < srcIndex; ++destIndex) {
 403       //source is a Load, so add anti-dependencies (store after load)
 404       if(TMI.isLoad(srcNodeOpCode))
 405         if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
 406           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 407                               MSchedGraphEdge::MemoryDep,
 408                               MSchedGraphEdge::AntiDep, 1);
 409       if(TMI.isStore(srcNodeOpCode)) {
 410         if(TMI.isStore(memInst[destIndex]->getInst()->getOpcode()))
 411           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 412                               MSchedGraphEdge::MemoryDep,
 413                               MSchedGraphEdge::OutputDep, 1);
 414         else
 415           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 416                               MSchedGraphEdge::MemoryDep,
 417                               MSchedGraphEdge::TrueDep, 1);
 418       }
 419
 420     }
 421
 422   }
 423 }