lib/CodeGen/ModuloScheduling/MSchedGraph.cpp

   1 //===-- MSchedGraph.cpp - 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 "../../Target/SparcV9/SparcV9RegisterInfo.h"
  17 #include "llvm/CodeGen/MachineBasicBlock.h"
  18 #include "llvm/Target/TargetInstrInfo.h"
  19 #include "Support/Debug.h"
  20 using namespace llvm;
  21
  22 MSchedGraphNode::MSchedGraphNode(const MachineInstr* inst,
  23                                  MSchedGraph *graph,
  24                                  unsigned late, bool isBranch)
  25   : Inst(inst), Parent(graph), latency(late), isBranchInstr(isBranch) {
  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 opCode = 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       //Get delay
 132       delay = MTI->maxLatency(opCode);
 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(opCode))
 137       continue;
 138
 139     //Add PHI to phi instruction list to be processed later
 140     if (opCode == TargetInstrInfo::PHI)
 141       phiInstrs.push_back(MI);
 142
 143     bool isBranch = false;
 144
 145     //We want to flag the branch node to treat it special
 146     if(MTI->isBranch(opCode))
 147       isBranch = true;
 148
 149     //Node is created and added to the graph automatically
 150     MSchedGraphNode *node =  new MSchedGraphNode(MI, this, delay, isBranch);
 151
 152     DEBUG(std::cerr << "Created Node: " << *node << "\n");
 153
 154     //Check OpCode to keep track of memory operations to add memory dependencies later.
 155     if(MTI->isLoad(opCode) || MTI->isStore(opCode))
 156       memInstructions.push_back(node);
 157
 158     //Loop over all operands, and put them into the register number to
 159     //graph node map for determining dependencies
 160     //If an operands is a use/def, we have an anti dependence to itself
 161     for(unsigned i=0; i < MI->getNumOperands(); ++i) {
 162       //Get Operand
 163       const MachineOperand &mOp = MI->getOperand(i);
 164
 165       //Check if it has an allocated register
 166       if(mOp.hasAllocatedReg()) {
 167         int regNum = mOp.getReg();
 168
 169         if(regNum != SparcV9::g0) {
 170         //Put into our map
 171         regNumtoNodeMap[regNum].push_back(std::make_pair(i, node));
 172         }
 173         continue;
 174       }
 175
 176
 177       //Add virtual registers dependencies
 178       //Check if any exist in the value map already and create dependencies
 179       //between them.
 180       if(mOp.getType() == MachineOperand::MO_VirtualRegister ||  mOp.getType() == MachineOperand::MO_CCRegister) {
 181
 182         //Make sure virtual register value is not null
 183         assert((mOp.getVRegValue() != NULL) && "Null value is defined");
 184
 185         //Check if this is a read operation in a phi node, if so DO NOT PROCESS
 186         if(mOp.isUse() && (opCode == TargetInstrInfo::PHI))
 187           continue;
 188
 189
 190         if (const Value* srcI = mOp.getVRegValue()) {
 191
 192           //Find value in the map
 193           std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 194             = valuetoNodeMap.find(srcI);
 195
 196           //If there is something in the map already, add edges from
 197           //those instructions
 198           //to this one we are processing
 199           if(V != valuetoNodeMap.end()) {
 200             addValueEdges(V->second, node, mOp.isUse(), mOp.isDef());
 201
 202             //Add to value map
 203             V->second.push_back(std::make_pair(i,node));
 204           }
 205           //Otherwise put it in the map
 206           else
 207             //Put into value map
 208           valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node));
 209         }
 210       }
 211     }
 212   }
 213   addMemEdges(memInstructions);
 214   addMachRegEdges(regNumtoNodeMap);
 215
 216   //Finally deal with PHI Nodes and Value*
 217   for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(), E = phiInstrs.end(); I != E;  ++I) {
 218     //Get Node for this instruction
 219     MSchedGraphNode *node = find(*I)->second;
 220
 221     //Loop over operands for this instruction and add value edges
 222     for(unsigned i=0; i < (*I)->getNumOperands(); ++i) {
 223       //Get Operand
 224       const MachineOperand &mOp = (*I)->getOperand(i);
 225       if((mOp.getType() == MachineOperand::MO_VirtualRegister ||  mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) {
 226         //find the value in the map
 227         if (const Value* srcI = mOp.getVRegValue()) {
 228
 229           //Find value in the map
 230           std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 231             = valuetoNodeMap.find(srcI);
 232
 233           //If there is something in the map already, add edges from
 234           //those instructions
 235           //to this one we are processing
 236           if(V != valuetoNodeMap.end()) {
 237             addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), 1);
 238           }
 239         }
 240       }
 241     }
 242   }
 243 }
 244
 245 void MSchedGraph::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
 246                                 MSchedGraphNode *destNode, bool nodeIsUse,
 247                                 bool nodeIsDef, int diff) {
 248
 249   for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(),
 250         E = NodesInMap.end(); I != E; ++I) {
 251
 252     //Get node in vectors machine operand that is the same value as node
 253     MSchedGraphNode *srcNode = I->second;
 254     MachineOperand mOp = srcNode->getInst()->getOperand(I->first);
 255
 256     //Node is a Def, so add output dep.
 257     if(nodeIsDef) {
 258       if(mOp.isUse())
 259         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 260                             MSchedGraphEdge::AntiDep, diff);
 261       if(mOp.isDef())
 262         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 263                             MSchedGraphEdge::OutputDep, diff);
 264
 265     }
 266     if(nodeIsUse) {
 267       if(mOp.isDef())
 268         srcNode->addOutEdge(destNode, MSchedGraphEdge::ValueDep,
 269                             MSchedGraphEdge::TrueDep, diff);
 270     }
 271   }
 272 }
 273
 274
 275 void MSchedGraph::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) {
 276   //Loop over all machine registers in the map, and add dependencies
 277   //between the instructions that use it
 278   typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap;
 279   for(regNodeMap::iterator I = regNumtoNodeMap.begin(); I != regNumtoNodeMap.end(); ++I) {
 280     //Get the register number
 281     int regNum = (*I).first;
 282
 283     //Get Vector of nodes that use this register
 284     std::vector<OpIndexNodePair> Nodes = (*I).second;
 285
 286     //Loop over nodes and determine the dependence between the other
 287     //nodes in the vector
 288     for(unsigned i =0; i < Nodes.size(); ++i) {
 289
 290       //Get src node operator index that uses this machine register
 291       int srcOpIndex = Nodes[i].first;
 292
 293       //Get the actual src Node
 294       MSchedGraphNode *srcNode = Nodes[i].second;
 295
 296       //Get Operand
 297       const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex);
 298
 299       bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse();
 300       bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef();
 301
 302
 303       //Look at all instructions after this in execution order
 304       for(unsigned j=i+1; j < Nodes.size(); ++j) {
 305
 306         //Sink node is a write
 307         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 308                       //Src only uses the register (read)
 309             if(srcIsUse)
 310               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 311                                   MSchedGraphEdge::AntiDep);
 312
 313             else if(srcIsUseandDef) {
 314               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 315                                   MSchedGraphEdge::AntiDep);
 316
 317               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 318                                   MSchedGraphEdge::OutputDep);
 319             }
 320             else
 321               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 322                                   MSchedGraphEdge::OutputDep);
 323         }
 324         //Dest node is a read
 325         else {
 326           if(!srcIsUse || srcIsUseandDef)
 327             srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 328                                 MSchedGraphEdge::TrueDep);
 329         }
 330
 331       }
 332
 333       //Look at all the instructions before this one since machine registers
 334       //could live across iterations.
 335       for(unsigned j = 0; j < i; ++j) {
 336                 //Sink node is a write
 337         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 338                       //Src only uses the register (read)
 339             if(srcIsUse)
 340               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 341                           MSchedGraphEdge::AntiDep, 1);
 342
 343             else if(srcIsUseandDef) {
 344               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 345                           MSchedGraphEdge::AntiDep, 1);
 346
 347               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 348                           MSchedGraphEdge::OutputDep, 1);
 349             }
 350             else
 351               srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 352                           MSchedGraphEdge::OutputDep, 1);
 353         }
 354         //Dest node is a read
 355         else {
 356           if(!srcIsUse || srcIsUseandDef)
 357             srcNode->addOutEdge(Nodes[j].second, MSchedGraphEdge::MachineRegister,
 358                         MSchedGraphEdge::TrueDep,1 );
 359         }
 360
 361
 362       }
 363
 364     }
 365
 366   }
 367
 368 }
 369
 370 void MSchedGraph::addMemEdges(const std::vector<MSchedGraphNode*>& memInst) {
 371
 372   //Get Target machine instruction info
 373   const TargetInstrInfo *TMI = Target.getInstrInfo();
 374
 375   //Loop over all memory instructions in the vector
 376   //Knowing that they are in execution, add true, anti, and output dependencies
 377   for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) {
 378
 379     //Get the machine opCode to determine type of memory instruction
 380     MachineOpCode srcNodeOpCode = memInst[srcIndex]->getInst()->getOpcode();
 381
 382     //All instructions after this one in execution order have an iteration delay of 0
 383     for(unsigned destIndex = srcIndex + 1; destIndex < memInst.size(); ++destIndex) {
 384
 385       //source is a Load, so add anti-dependencies (store after load)
 386       if(TMI->isLoad(srcNodeOpCode))
 387         if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
 388           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 389                               MSchedGraphEdge::MemoryDep,
 390                               MSchedGraphEdge::AntiDep);
 391
 392       //If source is a store, add output and true dependencies
 393       if(TMI->isStore(srcNodeOpCode)) {
 394         if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
 395            memInst[srcIndex]->addOutEdge(memInst[destIndex],
 396                               MSchedGraphEdge::MemoryDep,
 397                               MSchedGraphEdge::OutputDep);
 398         else
 399           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 400                               MSchedGraphEdge::MemoryDep,
 401                               MSchedGraphEdge::TrueDep);
 402       }
 403     }
 404
 405     //All instructions before the src in execution order have an iteration delay of 1
 406     for(unsigned destIndex = 0; destIndex < srcIndex; ++destIndex) {
 407       //source is a Load, so add anti-dependencies (store after load)
 408       if(TMI->isLoad(srcNodeOpCode))
 409         if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
 410           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 411                               MSchedGraphEdge::MemoryDep,
 412                               MSchedGraphEdge::AntiDep, 1);
 413       if(TMI->isStore(srcNodeOpCode)) {
 414         if(TMI->isStore(memInst[destIndex]->getInst()->getOpcode()))
 415           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 416                               MSchedGraphEdge::MemoryDep,
 417                               MSchedGraphEdge::OutputDep, 1);
 418         else
 419           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 420                               MSchedGraphEdge::MemoryDep,
 421                               MSchedGraphEdge::TrueDep, 1);
 422       }
 423
 424     }
 425
 426   }
 427 }