lib/Target/SparcV9/ModuloScheduling/MSchedGraphSB.cpp

   1 //===-- MSchedGraphSB.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. This graph only contains true, anti, and
  11 // output data dependencies for a given MachineBasicBlock. Dependencies
  12 // across iterations are also computed. Unless data dependence analysis
  13 // is provided, a conservative approach of adding dependencies between all
  14 // loads and stores is taken.
  15 //===----------------------------------------------------------------------===//
  16 #define DEBUG_TYPE "ModuloSchedSB"
  17
  18 #include "MSchedGraphSB.h"
  19 #include "../SparcV9RegisterInfo.h"
  20 #include "../MachineCodeForInstruction.h"
  21 #include "llvm/BasicBlock.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/Type.h"
  25 #include "llvm/CodeGen/MachineBasicBlock.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Support/Debug.h"
  28 #include <cstdlib>
  29 #include <algorithm>
  30 #include <set>
  31 #include "llvm/Target/TargetSchedInfo.h"
  32 #include "../SparcV9Internals.h"
  33
  34 using namespace llvm;
  35
  36 //MSchedGraphSBNode constructor
  37 MSchedGraphSBNode::MSchedGraphSBNode(const MachineInstr* inst,
  38                                  MSchedGraphSB *graph, unsigned idx,
  39                                  unsigned late, bool isBranch)
  40   : Inst(inst), Parent(graph), index(idx), latency(late),
  41     isBranchInstr(isBranch) {
  42
  43   //Add to the graph
  44   graph->addNode(inst, this);
  45 }
  46
  47 //MSchedGraphSBNode constructor
  48 MSchedGraphSBNode::MSchedGraphSBNode(const MachineInstr* inst,
  49                                      std::vector<const MachineInstr*> &other,
  50                                      MSchedGraphSB *graph, unsigned idx,
  51                                      unsigned late, bool isPNode)
  52   : Inst(inst), otherInstrs(other), Parent(graph), index(idx), latency(late), isPredicateNode(isPNode) {
  53
  54
  55   isBranchInstr = false;
  56
  57   //Add to the graph
  58   graph->addNode(inst, this);
  59 }
  60
  61 //MSchedGraphSBNode copy constructor
  62 MSchedGraphSBNode::MSchedGraphSBNode(const MSchedGraphSBNode &N)
  63   : Predecessors(N.Predecessors), Successors(N.Successors) {
  64
  65   Inst = N.Inst;
  66   Parent = N.Parent;
  67   index = N.index;
  68   latency = N.latency;
  69   isBranchInstr = N.isBranchInstr;
  70   otherInstrs = N.otherInstrs;
  71 }
  72
  73 //Print the node (instruction and latency)
  74 void MSchedGraphSBNode::print(std::ostream &os) const {
  75   if(!isPredicate())
  76     os << "MSchedGraphSBNode: Inst=" << *Inst << ", latency= " << latency << "\n";
  77   else
  78     os << "Pred Node\n";
  79 }
  80
  81
  82 //Get the edge from a predecessor to this node
  83 MSchedGraphSBEdge MSchedGraphSBNode::getInEdge(MSchedGraphSBNode *pred) {
  84   //Loop over all the successors of our predecessor
  85   //return the edge the corresponds to this in edge
  86   for (MSchedGraphSBNode::succ_iterator I = pred->succ_begin(),
  87          E = pred->succ_end(); I != E; ++I) {
  88     if (*I == this)
  89       return I.getEdge();
  90   }
  91   assert(0 && "Should have found edge between this node and its predecessor!");
  92   abort();
  93 }
  94
  95 //Get the iteration difference for the edge from this node to its successor
  96 unsigned MSchedGraphSBNode::getIteDiff(MSchedGraphSBNode *succ) {
  97   for(std::vector<MSchedGraphSBEdge>::iterator I = Successors.begin(),
  98         E = Successors.end();
  99       I != E; ++I) {
 100     if(I->getDest() == succ)
 101       return I->getIteDiff();
 102   }
 103   return 0;
 104 }
 105
 106 //Get the index into the vector of edges for the edge from pred to this node
 107 unsigned MSchedGraphSBNode::getInEdgeNum(MSchedGraphSBNode *pred) {
 108   //Loop over all the successors of our predecessor
 109   //return the edge the corresponds to this in edge
 110   int count = 0;
 111   for(MSchedGraphSBNode::succ_iterator I = pred->succ_begin(),
 112         E = pred->succ_end();
 113       I != E; ++I) {
 114     if(*I == this)
 115       return count;
 116     count++;
 117   }
 118   assert(0 && "Should have found edge between this node and its predecessor!");
 119   abort();
 120 }
 121
 122 //Determine if succ is a successor of this node
 123 bool MSchedGraphSBNode::isSuccessor(MSchedGraphSBNode *succ) {
 124   for(succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I)
 125     if(*I == succ)
 126       return true;
 127   return false;
 128 }
 129
 130 //Dtermine if pred is a predecessor of this node
 131 bool MSchedGraphSBNode::isPredecessor(MSchedGraphSBNode *pred) {
 132   if(std::find( Predecessors.begin(),  Predecessors.end(),
 133                 pred) !=   Predecessors.end())
 134     return true;
 135   else
 136     return false;
 137 }
 138
 139 //Add a node to the graph
 140 void MSchedGraphSB::addNode(const MachineInstr* MI,
 141                           MSchedGraphSBNode *node) {
 142
 143   //Make sure node does not already exist
 144   assert(GraphMap.find(MI) == GraphMap.end()
 145          && "New MSchedGraphSBNode already exists for this instruction");
 146
 147   GraphMap[MI] = node;
 148 }
 149
 150 //Delete a node to the graph
 151 void MSchedGraphSB::deleteNode(MSchedGraphSBNode *node) {
 152
 153   //Delete the edge to this node from all predecessors
 154   while(node->pred_size() > 0) {
 155     //DEBUG(std::cerr << "Delete edge from: " << **P << " to " << *node << "\n");
 156     MSchedGraphSBNode *pred = *(node->pred_begin());
 157     pred->deleteSuccessor(node);
 158   }
 159
 160   //Remove this node from the graph
 161   GraphMap.erase(node->getInst());
 162
 163 }
 164
 165
 166 //Create a graph for a machine block. The ignoreInstrs map is so that
 167 //we ignore instructions associated to the index variable since this
 168 //is a special case in Modulo Scheduling.  We only want to deal with
 169 //the body of the loop.
 170 MSchedGraphSB::MSchedGraphSB(std::vector<const MachineBasicBlock*> &bbs,
 171                          const TargetMachine &targ,
 172                          std::map<const MachineInstr*, unsigned> &ignoreInstrs,
 173                          DependenceAnalyzer &DA,
 174                          std::map<MachineInstr*, Instruction*> &machineTollvm)
 175   : BBs(bbs), Target(targ) {
 176
 177   //Make sure there is at least one BB and it is not null,
 178   assert(((bbs.size() >= 1) &&  bbs[1] != NULL) && "Basic Block is null");
 179
 180   std::map<MSchedGraphSBNode*, std::set<MachineInstr*> > liveOutsideTrace;
 181   std::set<const BasicBlock*> llvmBBs;
 182
 183   for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1;
 184       MBB != ME; ++MBB)
 185     llvmBBs.insert((*MBB)->getBasicBlock());
 186
 187   //create predicate nodes
 188   DEBUG(std::cerr << "Create predicate nodes\n");
 189   for(std::vector<const MachineBasicBlock*>::iterator MBB = bbs.begin(), ME = bbs.end()-1;
 190        MBB != ME; ++MBB) {
 191     //Get LLVM basic block
 192     BasicBlock *BB = (BasicBlock*) (*MBB)->getBasicBlock();
 193
 194     //Get Terminator
 195     BranchInst *b = dyn_cast<BranchInst>(BB->getTerminator());
 196
 197     std::vector<const MachineInstr*> otherInstrs;
 198     MachineInstr *instr = 0;
 199
 200     //Get the condition for the branch (we already checked if it was conditional)
 201     if(b->isConditional()) {
 202
 203       Value *cond = b->getCondition();
 204
 205       DEBUG(std::cerr << "Condition: " << *cond << "\n");
 206
 207       assert(cond && "Condition must not be null!");
 208
 209       if(Instruction *I = dyn_cast<Instruction>(cond)) {
 210         MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(I);
 211         if(tempMvec.size() > 0) {
 212           DEBUG(std::cerr << *(tempMvec[tempMvec.size()-1]) << "\n");;
 213           instr = (MachineInstr*) tempMvec[tempMvec.size()-1];
 214         }
 215       }
 216     }
 217
 218     //Get Machine target information for calculating latency
 219     const TargetInstrInfo *MTI = Target.getInstrInfo();
 220
 221     MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(b);
 222     int offset = tempMvec.size();
 223     for (unsigned j = 0; j < tempMvec.size(); j++) {
 224       MachineInstr *mi = tempMvec[j];
 225       if(MTI->isNop(mi->getOpcode()))
 226         continue;
 227
 228       if(!instr) {
 229         instr = mi;
 230         DEBUG(std::cerr << "No Cond MI: " << *mi << "\n");
 231       }
 232       else {
 233         DEBUG(std::cerr << *mi << "\n");;
 234         otherInstrs.push_back(mi);
 235       }
 236     }
 237
 238     //Node is created and added to the graph automatically
 239     MSchedGraphSBNode *node =  new MSchedGraphSBNode(instr, otherInstrs, this, (*MBB)->size()-offset-1, 3, true);
 240
 241     DEBUG(std::cerr << "Created Node: " << *node << "\n");
 242
 243     //Now loop over all instructions and see if their def is live outside the trace
 244     MachineBasicBlock *mb = (MachineBasicBlock*) *MBB;
 245     for(MachineBasicBlock::iterator I = mb->begin(), E = mb->end(); I != E; ++I) {
 246       MachineInstr *instr = I;
 247       if(MTI->isNop(instr->getOpcode()) || MTI->isBranch(instr->getOpcode()))
 248         continue;
 249       if(node->getInst() == instr)
 250         continue;
 251
 252       for(unsigned i=0; i < instr->getNumOperands(); ++i) {
 253         MachineOperand &mOp = instr->getOperand(i);
 254         if(mOp.isDef() && mOp.getType() == MachineOperand::MO_VirtualRegister) {
 255           Value *val = mOp.getVRegValue();
 256           //Check if there is a use not in the trace
 257           for(Value::use_iterator V = val->use_begin(), VE = val->use_end(); V != VE; ++V) {
 258             if (Instruction *Inst = dyn_cast<Instruction>(*V)) {
 259               if(llvmBBs.count(Inst->getParent()))
 260                  liveOutsideTrace[node].insert(instr);
 261             }
 262           }
 263         }
 264       }
 265     }
 266
 267
 268   }
 269
 270   //Create nodes and edges for this BB
 271   buildNodesAndEdges(ignoreInstrs, DA, machineTollvm, liveOutsideTrace);
 272
 273 }
 274
 275
 276 //Copies the graph and keeps a map from old to new nodes
 277 MSchedGraphSB::MSchedGraphSB(const MSchedGraphSB &G,
 278                          std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> &newNodes)
 279   : Target(G.Target) {
 280
 281   BBs = G.BBs;
 282
 283   std::map<MSchedGraphSBNode*, MSchedGraphSBNode*> oldToNew;
 284   //Copy all nodes
 285   for(MSchedGraphSB::const_iterator N = G.GraphMap.begin(),
 286         NE = G.GraphMap.end(); N != NE; ++N) {
 287
 288     MSchedGraphSBNode *newNode = new MSchedGraphSBNode(*(N->second));
 289     oldToNew[&*(N->second)] = newNode;
 290     newNodes[newNode] = &*(N->second);
 291     GraphMap[&*(N->first)] = newNode;
 292   }
 293
 294   //Loop over nodes and update edges to point to new nodes
 295   for(MSchedGraphSB::iterator N = GraphMap.begin(), NE = GraphMap.end();
 296       N != NE; ++N) {
 297
 298     //Get the node we are dealing with
 299     MSchedGraphSBNode *node = &*(N->second);
 300
 301     node->setParent(this);
 302
 303     //Loop over nodes successors and predecessors and update to the new nodes
 304     for(unsigned i = 0; i < node->pred_size(); ++i) {
 305       node->setPredecessor(i, oldToNew[node->getPredecessor(i)]);
 306     }
 307
 308     for(unsigned i = 0; i < node->succ_size(); ++i) {
 309       MSchedGraphSBEdge *edge = node->getSuccessor(i);
 310       MSchedGraphSBNode *oldDest = edge->getDest();
 311       edge->setDest(oldToNew[oldDest]);
 312     }
 313   }
 314 }
 315
 316 //Deconstructor, deletes all nodes in the graph
 317 MSchedGraphSB::~MSchedGraphSB () {
 318   for(MSchedGraphSB::iterator I = GraphMap.begin(), E = GraphMap.end();
 319       I != E; ++I)
 320     delete I->second;
 321 }
 322
 323 //Print out graph
 324 void MSchedGraphSB::print(std::ostream &os) const {
 325   for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end();
 326       N != NE; ++N) {
 327
 328     //Get the node we are dealing with
 329     MSchedGraphSBNode *node = &*(N->second);
 330
 331     os << "Node Start\n";
 332     node->print(os);
 333     os << "Successors:\n";
 334     //print successors
 335     for(unsigned i = 0; i < node->succ_size(); ++i) {
 336       MSchedGraphSBEdge *edge = node->getSuccessor(i);
 337       MSchedGraphSBNode *oldDest = edge->getDest();
 338       oldDest->print(os);
 339     }
 340     os << "Node End\n";
 341   }
 342 }
 343
 344 //Calculate total delay
 345 int MSchedGraphSB::totalDelay() {
 346   int sum = 0;
 347
 348   for(MSchedGraphSB::const_iterator N = GraphMap.begin(), NE = GraphMap.end();
 349       N != NE; ++N) {
 350
 351     //Get the node we are dealing with
 352     MSchedGraphSBNode *node = &*(N->second);
 353     sum += node->getLatency();
 354   }
 355   return sum;
 356 }
 357
 358 bool MSchedGraphSB::instrCauseException(MachineOpCode opCode) {
 359   //Check for integer divide
 360   if(opCode == V9::SDIVXr || opCode == V9::SDIVXi
 361      || opCode == V9::UDIVXr || opCode == V9::UDIVXi)
 362     return true;
 363
 364   //Check for loads or stores
 365   const TargetInstrInfo *MTI = Target.getInstrInfo();
 366   //if( MTI->isLoad(opCode) ||
 367   if(MTI->isStore(opCode))
 368     return true;
 369
 370   //Check for any floating point operation
 371   const TargetSchedInfo *msi = Target.getSchedInfo();
 372   InstrSchedClass sc = msi->getSchedClass(opCode);
 373
 374   //FIXME: Should check for floating point instructions!
 375   //if(sc == SPARC_FGA || sc == SPARC_FGM)
 376   //return true;
 377
 378   return false;
 379 }
 380
 381
 382 //Add edges between the nodes
 383 void MSchedGraphSB::buildNodesAndEdges(std::map<const MachineInstr*, unsigned> &ignoreInstrs,
 384                                      DependenceAnalyzer &DA,
 385                                        std::map<MachineInstr*, Instruction*> &machineTollvm,
 386                                        std::map<MSchedGraphSBNode*, std::set<MachineInstr*> > &liveOutsideTrace) {
 387
 388
 389   //Get Machine target information for calculating latency
 390   const TargetInstrInfo *MTI = Target.getInstrInfo();
 391
 392   std::vector<MSchedGraphSBNode*> memInstructions;
 393   std::map<int, std::vector<OpIndexNodePair> > regNumtoNodeMap;
 394   std::map<const Value*, std::vector<OpIndexNodePair> > valuetoNodeMap;
 395
 396   //Save PHI instructions to deal with later
 397   std::vector<const MachineInstr*> phiInstrs;
 398   unsigned index = 0;
 399
 400   MSchedGraphSBNode *lastPred = 0;
 401
 402
 403   for(std::vector<const MachineBasicBlock*>::iterator B = BBs.begin(),
 404         BE = BBs.end(); B != BE; ++B) {
 405
 406     const MachineBasicBlock *BB = *B;
 407
 408
 409     //Loop over instructions in MBB and add nodes and edges
 410     for (MachineBasicBlock::const_iterator MI = BB->begin(), e = BB->end();
 411          MI != e; ++MI) {
 412
 413       //Ignore indvar instructions
 414       if(ignoreInstrs.count(MI)) {
 415         ++index;
 416         continue;
 417       }
 418
 419       //Get each instruction of machine basic block, get the delay
 420       //using the op code, create a new node for it, and add to the
 421       //graph.
 422
 423       MachineOpCode opCode = MI->getOpcode();
 424       int delay;
 425
 426       //Get delay
 427       delay = MTI->maxLatency(opCode);
 428
 429       //Create new node for this machine instruction and add to the graph.
 430       //Create only if not a nop
 431       if(MTI->isNop(opCode))
 432         continue;
 433
 434       //Sparc BE does not use PHI opcode, so assert on this case
 435       assert(opCode != TargetInstrInfo::PHI && "Did not expect PHI opcode");
 436
 437       bool isBranch = false;
 438
 439       //Skip branches
 440       if(MTI->isBranch(opCode))
 441         continue;
 442
 443       //Node is created and added to the graph automatically
 444       MSchedGraphSBNode *node = 0;
 445       if(!GraphMap.count(MI)){
 446         node =  new MSchedGraphSBNode(MI, this, index, delay);
 447         DEBUG(std::cerr << "Created Node: " << *node << "\n");
 448       }
 449       else {
 450         node = GraphMap[MI];
 451         if(node->isPredicate()) {
 452           //Create edge between this node and last pred, then switch to new pred
 453           if(lastPred) {
 454             lastPred->addOutEdge(node, MSchedGraphSBEdge::PredDep,
 455             MSchedGraphSBEdge::NonDataDep, 0);
 456
 457             if(liveOutsideTrace.count(lastPred)) {
 458               for(std::set<MachineInstr*>::iterator L = liveOutsideTrace[lastPred].begin(), LE = liveOutsideTrace[lastPred].end(); L != LE; ++L)
 459                 lastPred->addOutEdge(GraphMap[*L], MSchedGraphSBEdge::PredDep,
 460                                      MSchedGraphSBEdge::NonDataDep, 1);
 461             }
 462
 463           }
 464
 465           lastPred = node;
 466         }
 467       }
 468
 469       //Add dependencies to instructions that cause exceptions
 470       if(lastPred)
 471         lastPred->print(std::cerr);
 472
 473       if(!node->isPredicate() && instrCauseException(opCode)) {
 474         if(lastPred) {
 475           lastPred->addOutEdge(node, MSchedGraphSBEdge::PredDep,
 476                                MSchedGraphSBEdge::NonDataDep, 0);
 477         }
 478       }
 479
 480
 481       //Check OpCode to keep track of memory operations to add memory
 482       //dependencies later.
 483       if(MTI->isLoad(opCode) || MTI->isStore(opCode))
 484         memInstructions.push_back(node);
 485
 486       //Loop over all operands, and put them into the register number to
 487       //graph node map for determining dependencies
 488       //If an operands is a use/def, we have an anti dependence to itself
 489       for(unsigned i=0; i < MI->getNumOperands(); ++i) {
 490         //Get Operand
 491         const MachineOperand &mOp = MI->getOperand(i);
 492
 493         //Check if it has an allocated register
 494         if(mOp.hasAllocatedReg()) {
 495           int regNum = mOp.getReg();
 496
 497           if(regNum != SparcV9::g0) {
 498             //Put into our map
 499             regNumtoNodeMap[regNum].push_back(std::make_pair(i, node));
 500           }
 501           continue;
 502         }
 503
 504
 505         //Add virtual registers dependencies
 506         //Check if any exist in the value map already and create dependencies
 507         //between them.
 508         if(mOp.getType() == MachineOperand::MO_VirtualRegister
 509            ||  mOp.getType() == MachineOperand::MO_CCRegister) {
 510
 511           //Make sure virtual register value is not null
 512           assert((mOp.getVRegValue() != NULL) && "Null value is defined");
 513
 514           //Check if this is a read operation in a phi node, if so DO NOT PROCESS
 515           if(mOp.isUse() && (opCode == TargetInstrInfo::PHI)) {
 516             DEBUG(std::cerr << "Read Operation in a PHI node\n");
 517             continue;
 518           }
 519
 520           if (const Value* srcI = mOp.getVRegValue()) {
 521
 522             //Find value in the map
 523             std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 524               = valuetoNodeMap.find(srcI);
 525
 526             //If there is something in the map already, add edges from
 527             //those instructions
 528             //to this one we are processing
 529             if(V != valuetoNodeMap.end()) {
 530               addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(), phiInstrs);
 531
 532               //Add to value map
 533               V->second.push_back(std::make_pair(i,node));
 534             }
 535             //Otherwise put it in the map
 536             else
 537               //Put into value map
 538               valuetoNodeMap[mOp.getVRegValue()].push_back(std::make_pair(i, node));
 539           }
 540         }
 541       }
 542       ++index;
 543     }
 544
 545     //Loop over LLVM BB, examine phi instructions, and add them to our
 546     //phiInstr list to process
 547     const BasicBlock *llvm_bb = BB->getBasicBlock();
 548     for(BasicBlock::const_iterator I = llvm_bb->begin(), E = llvm_bb->end();
 549         I != E; ++I) {
 550       if(const PHINode *PN = dyn_cast<PHINode>(I)) {
 551         MachineCodeForInstruction & tempMvec = MachineCodeForInstruction::get(PN);
 552         for (unsigned j = 0; j < tempMvec.size(); j++) {
 553           if(!ignoreInstrs.count(tempMvec[j])) {
 554             DEBUG(std::cerr << "Inserting phi instr into map: " << *tempMvec[j] << "\n");
 555             phiInstrs.push_back((MachineInstr*) tempMvec[j]);
 556           }
 557         }
 558       }
 559
 560     }
 561
 562     addMemEdges(memInstructions, DA, machineTollvm);
 563     addMachRegEdges(regNumtoNodeMap);
 564
 565     //Finally deal with PHI Nodes and Value*
 566     for(std::vector<const MachineInstr*>::iterator I = phiInstrs.begin(),
 567           E = phiInstrs.end(); I != E;  ++I) {
 568
 569       //Get Node for this instruction
 570       std::map<const MachineInstr*, MSchedGraphSBNode*>::iterator X;
 571       X = find(*I);
 572
 573       if(X == GraphMap.end())
 574         continue;
 575
 576       MSchedGraphSBNode *node = X->second;
 577
 578       DEBUG(std::cerr << "Adding ite diff edges for node: " << *node << "\n");
 579
 580       //Loop over operands for this instruction and add value edges
 581       for(unsigned i=0; i < (*I)->getNumOperands(); ++i) {
 582         //Get Operand
 583         const MachineOperand &mOp = (*I)->getOperand(i);
 584         if((mOp.getType() == MachineOperand::MO_VirtualRegister
 585             ||  mOp.getType() == MachineOperand::MO_CCRegister) && mOp.isUse()) {
 586
 587           //find the value in the map
 588           if (const Value* srcI = mOp.getVRegValue()) {
 589
 590             //Find value in the map
 591             std::map<const Value*, std::vector<OpIndexNodePair> >::iterator V
 592               = valuetoNodeMap.find(srcI);
 593
 594             //If there is something in the map already, add edges from
 595             //those instructions
 596             //to this one we are processing
 597             if(V != valuetoNodeMap.end()) {
 598               addValueEdges(V->second, node, mOp.isUse(), mOp.isDef(),
 599                             phiInstrs, 1);
 600             }
 601           }
 602         }
 603       }
 604     }
 605   }
 606 }
 607 //Add dependencies for Value*s
 608 void MSchedGraphSB::addValueEdges(std::vector<OpIndexNodePair> &NodesInMap,
 609                                 MSchedGraphSBNode *destNode, bool nodeIsUse,
 610                                 bool nodeIsDef, std::vector<const MachineInstr*> &phiInstrs, int diff) {
 611
 612   for(std::vector<OpIndexNodePair>::iterator I = NodesInMap.begin(),
 613         E = NodesInMap.end(); I != E; ++I) {
 614
 615     //Get node in vectors machine operand that is the same value as node
 616     MSchedGraphSBNode *srcNode = I->second;
 617     MachineOperand mOp = srcNode->getInst()->getOperand(I->first);
 618
 619     if(diff > 0)
 620       if(std::find(phiInstrs.begin(), phiInstrs.end(), srcNode->getInst()) == phiInstrs.end())
 621         continue;
 622
 623     //Node is a Def, so add output dep.
 624     if(nodeIsDef) {
 625       if(mOp.isUse()) {
 626         DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=anti)\n");
 627         srcNode->addOutEdge(destNode, MSchedGraphSBEdge::ValueDep,
 628                             MSchedGraphSBEdge::AntiDep, diff);
 629       }
 630       if(mOp.isDef()) {
 631         DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=output)\n");
 632         srcNode->addOutEdge(destNode, MSchedGraphSBEdge::ValueDep,
 633                             MSchedGraphSBEdge::OutputDep, diff);
 634       }
 635     }
 636     if(nodeIsUse) {
 637       if(mOp.isDef()) {
 638         DEBUG(std::cerr << "Edge from " << *srcNode << " to " << *destNode << " (itediff=" << diff << ", type=true)\n");
 639         srcNode->addOutEdge(destNode, MSchedGraphSBEdge::ValueDep,
 640                             MSchedGraphSBEdge::TrueDep, diff);
 641       }
 642     }
 643   }
 644 }
 645
 646 //Add dependencies for machine registers across iterations
 647 void MSchedGraphSB::addMachRegEdges(std::map<int, std::vector<OpIndexNodePair> >& regNumtoNodeMap) {
 648   //Loop over all machine registers in the map, and add dependencies
 649   //between the instructions that use it
 650   typedef std::map<int, std::vector<OpIndexNodePair> > regNodeMap;
 651   for(regNodeMap::iterator I = regNumtoNodeMap.begin();
 652       I != regNumtoNodeMap.end(); ++I) {
 653     //Get the register number
 654     int regNum = (*I).first;
 655
 656     //Get Vector of nodes that use this register
 657     std::vector<OpIndexNodePair> Nodes = (*I).second;
 658
 659     //Loop over nodes and determine the dependence between the other
 660     //nodes in the vector
 661     for(unsigned i =0; i < Nodes.size(); ++i) {
 662
 663       //Get src node operator index that uses this machine register
 664       int srcOpIndex = Nodes[i].first;
 665
 666       //Get the actual src Node
 667       MSchedGraphSBNode *srcNode = Nodes[i].second;
 668
 669       //Get Operand
 670       const MachineOperand &srcMOp = srcNode->getInst()->getOperand(srcOpIndex);
 671
 672       bool srcIsUseandDef = srcMOp.isDef() && srcMOp.isUse();
 673       bool srcIsUse = srcMOp.isUse() && !srcMOp.isDef();
 674
 675
 676       //Look at all instructions after this in execution order
 677       for(unsigned j=i+1; j < Nodes.size(); ++j) {
 678
 679         //Sink node is a write
 680         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 681                       //Src only uses the register (read)
 682             if(srcIsUse)
 683               srcNode->addOutEdge(Nodes[j].second,
 684                                   MSchedGraphSBEdge::MachineRegister,
 685                                   MSchedGraphSBEdge::AntiDep);
 686
 687             else if(srcIsUseandDef) {
 688               srcNode->addOutEdge(Nodes[j].second,
 689                                   MSchedGraphSBEdge::MachineRegister,
 690                                   MSchedGraphSBEdge::AntiDep);
 691
 692               srcNode->addOutEdge(Nodes[j].second,
 693                                   MSchedGraphSBEdge::MachineRegister,
 694                                   MSchedGraphSBEdge::OutputDep);
 695             }
 696             else
 697               srcNode->addOutEdge(Nodes[j].second,
 698                                   MSchedGraphSBEdge::MachineRegister,
 699                                   MSchedGraphSBEdge::OutputDep);
 700         }
 701         //Dest node is a read
 702         else {
 703           if(!srcIsUse || srcIsUseandDef)
 704             srcNode->addOutEdge(Nodes[j].second,
 705                                 MSchedGraphSBEdge::MachineRegister,
 706                                 MSchedGraphSBEdge::TrueDep);
 707         }
 708
 709       }
 710
 711       //Look at all the instructions before this one since machine registers
 712       //could live across iterations.
 713       for(unsigned j = 0; j < i; ++j) {
 714                 //Sink node is a write
 715         if(Nodes[j].second->getInst()->getOperand(Nodes[j].first).isDef()) {
 716                       //Src only uses the register (read)
 717             if(srcIsUse)
 718               srcNode->addOutEdge(Nodes[j].second,
 719                                   MSchedGraphSBEdge::MachineRegister,
 720                                   MSchedGraphSBEdge::AntiDep, 1);
 721             else if(srcIsUseandDef) {
 722               srcNode->addOutEdge(Nodes[j].second,
 723                                   MSchedGraphSBEdge::MachineRegister,
 724                                   MSchedGraphSBEdge::AntiDep, 1);
 725
 726               srcNode->addOutEdge(Nodes[j].second,
 727                                   MSchedGraphSBEdge::MachineRegister,
 728                                   MSchedGraphSBEdge::OutputDep, 1);
 729             }
 730             else
 731               srcNode->addOutEdge(Nodes[j].second,
 732                                   MSchedGraphSBEdge::MachineRegister,
 733                                   MSchedGraphSBEdge::OutputDep, 1);
 734         }
 735         //Dest node is a read
 736         else {
 737           if(!srcIsUse || srcIsUseandDef)
 738             srcNode->addOutEdge(Nodes[j].second,
 739                                 MSchedGraphSBEdge::MachineRegister,
 740                                 MSchedGraphSBEdge::TrueDep,1 );
 741         }
 742
 743
 744       }
 745
 746     }
 747
 748   }
 749
 750 }
 751
 752 //Add edges between all loads and stores
 753 //Can be less strict with alias analysis and data dependence analysis.
 754 void MSchedGraphSB::addMemEdges(const std::vector<MSchedGraphSBNode*>& memInst,
 755                       DependenceAnalyzer &DA,
 756                       std::map<MachineInstr*, Instruction*> &machineTollvm) {
 757
 758   //Get Target machine instruction info
 759   const TargetInstrInfo *TMI = Target.getInstrInfo();
 760
 761   //Loop over all memory instructions in the vector
 762   //Knowing that they are in execution, add true, anti, and output dependencies
 763   for (unsigned srcIndex = 0; srcIndex < memInst.size(); ++srcIndex) {
 764
 765     MachineInstr *srcInst = (MachineInstr*) memInst[srcIndex]->getInst();
 766
 767     //Get the machine opCode to determine type of memory instruction
 768     MachineOpCode srcNodeOpCode = srcInst->getOpcode();
 769
 770     //All instructions after this one in execution order have an
 771     //iteration delay of 0
 772     for(unsigned destIndex = 0; destIndex < memInst.size(); ++destIndex) {
 773
 774       //No self loops
 775       if(destIndex == srcIndex)
 776         continue;
 777
 778       MachineInstr *destInst = (MachineInstr*) memInst[destIndex]->getInst();
 779
 780       DEBUG(std::cerr << "MInst1: " << *srcInst << "\n");
 781       DEBUG(std::cerr << "MInst2: " << *destInst << "\n");
 782
 783       //Assuming instructions without corresponding llvm instructions
 784       //are from constant pools.
 785       if (!machineTollvm.count(srcInst) || !machineTollvm.count(destInst))
 786         continue;
 787
 788       bool useDepAnalyzer = true;
 789
 790       //Some machine loads and stores are generated by casts, so be
 791       //conservative and always add deps
 792       Instruction *srcLLVM = machineTollvm[srcInst];
 793       Instruction *destLLVM = machineTollvm[destInst];
 794       if(!isa<LoadInst>(srcLLVM)
 795          && !isa<StoreInst>(srcLLVM)) {
 796         if(isa<BinaryOperator>(srcLLVM)) {
 797           if(isa<ConstantFP>(srcLLVM->getOperand(0)) || isa<ConstantFP>(srcLLVM->getOperand(1)))
 798             continue;
 799         }
 800         useDepAnalyzer = false;
 801       }
 802       if(!isa<LoadInst>(destLLVM)
 803          && !isa<StoreInst>(destLLVM)) {
 804         if(isa<BinaryOperator>(destLLVM)) {
 805           if(isa<ConstantFP>(destLLVM->getOperand(0)) || isa<ConstantFP>(destLLVM->getOperand(1)))
 806             continue;
 807         }
 808         useDepAnalyzer = false;
 809       }
 810
 811       //Use dep analysis when we have corresponding llvm loads/stores
 812       if(useDepAnalyzer) {
 813         bool srcBeforeDest = true;
 814         if(destIndex < srcIndex)
 815           srcBeforeDest = false;
 816
 817         DependenceResult dr = DA.getDependenceInfo(machineTollvm[srcInst],
 818                                                    machineTollvm[destInst],
 819                                                    srcBeforeDest);
 820
 821         for(std::vector<Dependence>::iterator d = dr.dependences.begin(),
 822               de = dr.dependences.end(); d != de; ++d) {
 823           //Add edge from load to store
 824           memInst[srcIndex]->addOutEdge(memInst[destIndex],
 825                                         MSchedGraphSBEdge::MemoryDep,
 826                                         d->getDepType(), d->getIteDiff());
 827
 828         }
 829       }
 830       //Otherwise, we can not do any further analysis and must make a dependence
 831       else {
 832
 833         //Get the machine opCode to determine type of memory instruction
 834         MachineOpCode destNodeOpCode = destInst->getOpcode();
 835
 836         //Get the Value* that we are reading from the load, always the first op
 837         const MachineOperand &mOp = srcInst->getOperand(0);
 838         const MachineOperand &mOp2 = destInst->getOperand(0);
 839
 840         if(mOp.hasAllocatedReg())
 841           if(mOp.getReg() == SparcV9::g0)
 842             continue;
 843         if(mOp2.hasAllocatedReg())
 844           if(mOp2.getReg() == SparcV9::g0)
 845             continue;
 846
 847         DEBUG(std::cerr << "Adding dependence for machine instructions\n");
 848         //Load-Store deps
 849         if(TMI->isLoad(srcNodeOpCode)) {
 850
 851           if(TMI->isStore(destNodeOpCode))
 852             memInst[srcIndex]->addOutEdge(memInst[destIndex],
 853                                           MSchedGraphSBEdge::MemoryDep,
 854                                           MSchedGraphSBEdge::AntiDep, 0);
 855         }
 856         else if(TMI->isStore(srcNodeOpCode)) {
 857           if(TMI->isStore(destNodeOpCode))
 858             memInst[srcIndex]->addOutEdge(memInst[destIndex],
 859                                           MSchedGraphSBEdge::MemoryDep,
 860                                           MSchedGraphSBEdge::OutputDep, 0);
 861
 862           else
 863             memInst[srcIndex]->addOutEdge(memInst[destIndex],
 864                                           MSchedGraphSBEdge::MemoryDep,
 865                                           MSchedGraphSBEdge::TrueDep, 0);
 866         }
 867       }
 868     }
 869   }
 870 }