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