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 << "MSehedGraphNode: 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 void MSchedGraph::addNode(const MachineInstr *MI,
  48                           MSchedGraphNode *node) {
  49
  50   //Make sure node does not already exist
  51   assert(GraphMap.find(MI) == GraphMap.end()
  52          && "New MSchedGraphNode already exists for this instruction");
  53
  54   GraphMap[MI] = node;
  55 }
  56
  57 MSchedGraph::MSchedGraph(const MachineBasicBlock *bb, const TargetMachine &targ)
  58   : BB(bb), Target(targ) {
  59
  60   //Make sure BB is not null,
  61   assert(BB != NULL && "Basic Block is null");
  62
  63   DEBUG(std::cerr << "Constructing graph for " << bb << "\n");
  64
  65   //Create nodes and edges for this BB
  66   buildNodesAndEdges();
  67 }
  68
  69 MSchedGraph::~MSchedGraph () {
  70   for(MSchedGraph::iterator I = GraphMap.begin(), E = GraphMap.end(); I != E; ++I)
  71     delete I->second;
  72 }
  73
  74 void MSchedGraph::buildNodesAndEdges() {
  75
  76   //Get Machine target information for calculating latency
  77   const TargetInstrInfo &MTI = Target.getInstrInfo();
  78
  79   std::vector<MSchedGraphNode*> memInstructions;
  80   std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap;
  81   std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap;
  82
  83   //Save PHI instructions to deal with later
  84   std::vector<const MachineInstr*> phiInstrs;
  85
  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
  90     //graph.
  91
  92     MachineOpCode MIopCode = MI->getOpcode();
  93     int delay;
  94
  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);
  99     else
 100       delay = MTI.maxLatency(MIopCode);
 101
 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))
 105       continue;
 106
 107     //Add PHI to phi instruction list to be processed later
 108     if (MIopCode == TargetInstrInfo::PHI)
 109       phiInstrs.push_back(MI);
 110
 111     //Node is created and added to the graph automatically
 112     MSchedGraphNode *node =  new MSchedGraphNode(MI, this, delay);
 113
 114     DEBUG(std::cerr << "Created Node: " << *node << "\n");
 115
 116     //Check OpCode to keep track of memory operations to add memory dependencies later.
 117     MachineOpCode opCode = MI->getOpcode();
 118
 119     if(MTI.isLoad(opCode) || MTI.isStore(opCode))
 120       memInstructions.push_back(node);
 121
 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) {
 126       //Get Operand
 127       const MachineOperand &mOp = MI->getOperand(i);
 128
 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();
 134
 135         //Put into our map
 136         regNumtoNodeMap[regNum].push_back(std::make_pair(i, node));
 137         continue;
 138       }
 139
 140
 141       //Add virtual registers dependencies
 142       //Check if any exist in the value map already and create dependencies
 143       //between them.
 144       if(mOp.getType() == MachineOperand::MO_VirtualRegister ||  mOp.getType() == MachineOperand::MO_CCRegister) {
 145
 146         //Make sure virtual register value is not null
 147         assert((mOp.getVRegValue() != NULL) && "Null value is defined");
 148
 149         //Check if this is a read operation in a phi node, if so DO NOT PROCESS
 150         if(mOp.isUse() && (MIopCode == TargetInstrInfo::PHI))
 151           continue;
 152
 153
 154         if (const Value* srcI = mOp.getVRegValue()) {
 155
 156           //Find value in the map
 157           std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 158             = valuetoNodeMap.find(srcI);
 159
 160           //If there is something in the map already, add edges from
 161           //those instructions
 162           //to this one we are processing
 163           if(V != valuetoNodeMap.end()) {
 164             addValueEdges(V->second, node, mOp.isUse(), mOp.isDef());
 165
 166             //Add to value map
 167             V->second.push_back(std::make_pair(i,node));
 168           }
 169           //Otherwise put it in the map
 170           else
 171             //Put into value map
 172           valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node));
 173         }
 174       }
 175     }
 176   }
 177   addMemEdges(memInstructions);
 178   addMachRegEdges(regNumtoNodeMap);
 179
 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;
 184
 185     //Loop over operands for this instruction and add value edges
 186     for(unsigned i=0; i < (*I)->getNumOperands(); ++i) {
 187       //Get Operand
 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()) {
 192
 193           //Find value in the map
 194           std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 195             = valuetoNodeMap.find(srcI);
 196
 197           //If there is something in the map already, add edges from
 198           //those instructions
 199           //to this one we are processing
 200           if(V != valuetoNodeMap.end()) {
 201             addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 1);
 202           }
 203         }
 204       }
 205     }
 206   }
 207 }
 208
 209 void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
 210                                 MSchedGraphNode *destNode, bool nodeIsUse,
 211                                 bool nodeIsDef, int diff) {
 212
 213   for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(),
 214         E = NodesInMap.end(); I != E; ++I) {
 215
 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);
 219
 220     //Node is a Def, so add output dep.
 221     if(nodeIsDef) {
 222       if(mOp.isUse())
 223         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 224                             MSchedGraphEdge::AntiDep, diff);
 225       if(mOp.isDef())
 226         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 227                             MSchedGraphEdge::OutputDep, diff);
 228
 229     }
 230     if(nodeIsUse) {
 231       if(mOp.isDef())
 232         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 233                             MSchedGraphEdge::TrueDep, diff);
 234     }
 235   }
 236 }
 237
 238
 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;
 246
 247     //Get Vector of nodes that use this register
 248     std::vector<OpIndexNodePair> Nodes = (*I).second;
 249
 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) {
 253
 254       //Get src node operator index that uses this machine register
 255       int srcOpIndex = Nodes[i].first;
 256
 257       //Get the actual src Node
 258       MSchedGraphNode *srcNode = Nodes[i].second;
 259
 260       //Get Operand
 261       const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex);
 262
 263       bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse();
 264       bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef();
 265
 266
 267       //Look at all instructions after this in execution order
 268       for(unsigned j=i+1; j < Nodes.size(); ++j) {
 269
 270         //Sink node is a write
 271         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 272                       //Src only uses the register (read)
 273             if(srcIsUse)
 274               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 275                                   MSchedGraphEdge::AntiDep);
 276
 277             else if(srcIsUseandDef) {
 278               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 279                                   MSchedGraphEdge::AntiDep);
 280
 281               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 282                                   MSchedGraphEdge::OutputDep);
 283             }
 284             else
 285               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 286                                   MSchedGraphEdge::OutputDep);
 287         }
 288         //Dest node is a read
 289         else {
 290           if(!srcIsUse || srcIsUseandDef)
 291             srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 292                                 MSchedGraphEdge::TrueDep);
 293         }
 294
 295       }
 296
 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)
 303             if(srcIsUse)
 304               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 305                                   MSchedGraphEdge::AntiDep, 1);
 306
 307             else if(srcIsUseandDef) {
 308               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 309                                   MSchedGraphEdge::AntiDep, 1);
 310
 311               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 312                                   MSchedGraphEdge::OutputDep, 1);
 313             }
 314             else
 315               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 316                                   MSchedGraphEdge::OutputDep, 1);
 317         }
 318         //Dest node is a read
 319         else {
 320           if(!srcIsUse || srcIsUseandDef)
 321             srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 322                                 MSchedGraphEdge::TrueDep,1 );
 323         }
 324
 325
 326       }
 327
 328     }
 329
 330   }
 331
 332 }
 333
 334 void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) {
 335
 336   //Get Target machine instruction info
 337   const TargetInstrInfo& TMI = Target.getInstrInfo();
 338
 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) {
 342
 343     //Get the machine opCode to determine type of memory instruction
 344     MachineOpCode srcNodeOpCode = memInst[srcIndex]->getInst()->getOpcode();
 345
 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) {
 348
 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);
 355
 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);
 362         else
 363           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 364                               MSchedGraphEdge::MemoryDep,
 365                               MSchedGraphEdge::TrueDep);
 366       }
 367     }
 368
 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);
 382         else
 383           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 384                               MSchedGraphEdge::MemoryDep,
 385                               MSchedGraphEdge::TrueDep, 1);
 386       }
 387
 388     }
 389
 390   }
 391 }