lib/CodeGen/ModuloScheduling/ModuloSchedGraph.cpp

   1 //===- ModuloSchedGraph.cpp - Graph datastructure for Modulo Scheduling ---===//
   2 //
   3 //
   4 //===----------------------------------------------------------------------===//
   5
   6 #include "llvm/CodeGen/InstrSelection.h"
   7 #include "llvm/Function.h"
   8 #include "llvm/Instructions.h"
   9 #include "llvm/Type.h"
  10 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  11 #include "llvm/CodeGen/MachineInstr.h"
  12 #include "llvm/Target/TargetSchedInfo.h"
  13 #include "Support/StringExtras.h"
  14 #include "Support/STLExtras.h"
  15 #include "Support/hash_map"
  16 #include "Support/Statistic.h"
  17 #include "ModuloScheduling.h"
  18 #include "ModuloSchedGraph.h"
  19 #include <algorithm>
  20 #include <ostream>
  21 #include <vector>
  22 #include <math.h>
  23
  24
  25 #define UNIDELAY 1
  26
  27 using std::cerr;
  28 using std::endl;
  29 using std::vector;
  30
  31
  32 /***********member functions for ModuloSchedGraphNode*********/
  33
  34
  35 ModuloSchedGraphNode::ModuloSchedGraphNode(unsigned int in_nodeId,
  36                                            const BasicBlock * in_bb,
  37                                            const Instruction * in_inst,
  38                                            int indexInBB,
  39                                            const TargetMachine & target)
  40   :SchedGraphNodeCommon(in_nodeId, indexInBB), inst(in_inst){
  41
  42   if (inst) {
  43     //FIXME: find the latency
  44     //currently set the latency to zero
  45     latency = 0;
  46   }
  47 }
  48
  49
  50 /***********member functions for ModuloSchedGraph*********/
  51
  52 void
  53 ModuloSchedGraph::addDefUseEdges(const BasicBlock *bb){
  54
  55   //collect def instructions, store them in vector
  56   const TargetInstrInfo & mii = target.getInstrInfo();
  57   vector < ModuloSchedGraphNode * > defVec;
  58
  59
  60   //find those def instructions
  61   for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E; ++I) {
  62     if (I->getType() != Type::VoidTy) {
  63       defVec.push_back(this->getGraphNodeForInst(I));
  64     }
  65   }
  66
  67   for (unsigned int i = 0; i < defVec.size(); i++) {
  68     for (Value::use_const_iterator I = defVec[i]->getInst()->use_begin();
  69          I != defVec[i]->getInst()->use_end(); I++) {
  70       //for each use of a def, add a flow edge from the def instruction to the
  71       //ref instruction
  72
  73       const Instruction *value = defVec[i]->getInst();
  74       Instruction *inst = (Instruction *) (*I);
  75       ModuloSchedGraphNode *node = NULL;
  76
  77       for (BasicBlock::const_iterator ins = bb->begin(), E = bb->end();
  78            ins != E; ++ins)
  79         if ((const Instruction *) ins == inst) {
  80           node = (*this)[inst];
  81           break;
  82         }
  83
  84
  85       if (node == NULL){
  86
  87         //inst is not an instruction in this block
  88         //do nothing
  89
  90       } else {
  91         // Add a flow edge from the def instruction to the ref instruction
  92         // This is a true dependence, so the delay is equal to the
  93         //delay of the preceding node.
  94
  95         int delay = 0;
  96
  97         // self loop will not happen in SSA form
  98         assert(defVec[i] != node && "same node?");
  99
 100         MachineCodeForInstruction & tempMvec =
 101             MachineCodeForInstruction::get(value);
 102         for (unsigned j = 0; j < tempMvec.size(); j++) {
 103           MachineInstr *temp = tempMvec[j];
 104           delay = std::max(delay, mii.minLatency(temp->getOpCode()));
 105         }
 106
 107         SchedGraphEdge *trueEdge =
 108           new SchedGraphEdge(defVec[i], node, value,
 109                                SchedGraphEdge::TrueDep, delay);
 110
 111         // if the ref instruction is before the def instrution
 112         // then the def instruction must be a phi instruction
 113         // add an anti-dependence edge to from the ref instruction to the def
 114         // instruction
 115         if (node->getOrigIndexInBB() < defVec[i]->getOrigIndexInBB()) {
 116           assert(PHINode::classof(inst)
 117                  && "the ref instruction befre def is not PHINode?");
 118           trueEdge->setIteDiff(1);
 119         }
 120
 121       }
 122
 123     }
 124   }
 125 }
 126
 127 void
 128 ModuloSchedGraph::addCDEdges(const BasicBlock * bb) {
 129
 130   // find the last instruction in the basic block
 131   // see if it is an branch instruction.
 132   // If yes, then add an edge from each node expcept the last node
 133   // to the last node
 134
 135   const Instruction *inst = &(bb->back());
 136   ModuloSchedGraphNode *lastNode = (*this)[inst];
 137   if (TerminatorInst::classof(inst))
 138     for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E;
 139          I++) {
 140       if (inst != I) {
 141         ModuloSchedGraphNode *node = (*this)[I];
 142         //use latency of 0
 143         (void) new SchedGraphEdge(node, lastNode, SchedGraphEdge::CtrlDep,
 144                                   SchedGraphEdge::NonDataDep, 0);
 145       }
 146
 147     }
 148 }
 149
 150 static const int SG_LOAD_REF = 0;
 151 static const int SG_STORE_REF = 1;
 152 static const int SG_CALL_REF = 2;
 153
 154 static const unsigned int SG_DepOrderArray[][3] = {
 155   {SchedGraphEdge::NonDataDep,
 156    SchedGraphEdge::AntiDep,
 157    SchedGraphEdge::AntiDep},
 158   {SchedGraphEdge::TrueDep,
 159    SchedGraphEdge::OutputDep,
 160    SchedGraphEdge::TrueDep | SchedGraphEdge::OutputDep},
 161   {SchedGraphEdge::TrueDep,
 162    SchedGraphEdge::AntiDep | SchedGraphEdge::OutputDep,
 163    SchedGraphEdge::TrueDep | SchedGraphEdge::AntiDep
 164    | SchedGraphEdge::OutputDep}
 165 };
 166
 167
 168 // Add a dependence edge between every pair of machine load/store/call
 169 // instructions, where at least one is a store or a call.
 170 // Use latency 1 just to ensure that memory operations are ordered;
 171 // latency does not otherwise matter (true dependences enforce that).
 172 //
 173 void
 174 ModuloSchedGraph::addMemEdges(const BasicBlock * bb) {
 175
 176   vector<ModuloSchedGraphNode*> memNodeVec;
 177
 178   //construct the memNodeVec
 179   for (BasicBlock::const_iterator I = bb->begin(),
 180          E = bb->end(); I != E; ++I) {
 181
 182     if (LoadInst::classof(I) || StoreInst::classof(I)
 183         || CallInst::classof(I)) {
 184
 185       ModuloSchedGraphNode *node = (*this)[(const Instruction *) I];
 186       memNodeVec.push_back(node);
 187
 188     }
 189   }
 190
 191   // Instructions in memNodeVec are in execution order within the
 192   // basic block, so simply look at all pairs
 193   // <memNodeVec[i], memNodeVec[j: j > i]>.
 194
 195   for (unsigned im = 0, NM = memNodeVec.size(); im < NM; im++) {
 196
 197     const Instruction *fromInst,*toInst;
 198     int toType, fromType;
 199
 200     //get the first mem instruction and instruction type
 201     fromInst = memNodeVec[im]->getInst();
 202     fromType = CallInst::classof(fromInst) ? SG_CALL_REF
 203       : LoadInst::classof(fromInst) ? SG_LOAD_REF : SG_STORE_REF;
 204
 205     for (unsigned jm = im + 1; jm < NM; jm++) {
 206
 207       //get the second mem instruction and instruction type
 208       toInst = memNodeVec[jm]->getInst();
 209       toType = CallInst::classof(toInst) ? SG_CALL_REF
 210           : LoadInst::classof(toInst) ? SG_LOAD_REF : SG_STORE_REF;
 211
 212       //add two edges if not both of them are LOAD instructions
 213       if (fromType != SG_LOAD_REF || toType != SG_LOAD_REF) {
 214         (void) new SchedGraphEdge(memNodeVec[im], memNodeVec[jm],
 215                                   SchedGraphEdge::MemoryDep,
 216                                   SG_DepOrderArray[fromType][toType], 1);
 217
 218         SchedGraphEdge *edge =
 219             new SchedGraphEdge(memNodeVec[jm], memNodeVec[im],
 220                                SchedGraphEdge::MemoryDep,
 221                                SG_DepOrderArray[toType][fromType], 1);
 222
 223         //set the iteration difference for this edge to 1.
 224         edge->setIteDiff(1);
 225
 226       }
 227     }
 228   }
 229 }
 230
 231 /*
 232   this function build graph nodes for each instruction
 233   in the basicblock
 234 */
 235
 236 void
 237 ModuloSchedGraph::buildNodesforBB(const TargetMachine &target,
 238                                   const BasicBlock *bb){
 239
 240   int i = 0;
 241   ModuloSchedGraphNode *node;
 242
 243   for (BasicBlock::const_iterator I = bb->begin(), E = bb->end();
 244        I != E; ++I) {
 245
 246     node=new ModuloSchedGraphNode(getNumNodes(), bb, I, i, target);
 247
 248     i++;
 249
 250     this->addHash(I, node);
 251   }
 252
 253 }
 254
 255
 256 /*
 257   determine if this basicblock includes a loop or not
 258 */
 259
 260 bool
 261 ModuloSchedGraph::isLoop(const BasicBlock *bb) {
 262
 263   //only if the last instruction in the basicblock is branch instruction and
 264   //there is at least an option to branch itself
 265
 266   const Instruction *inst = &(bb->back());
 267
 268   if (BranchInst::classof(inst)) {
 269     for (unsigned i = 0; i < ((BranchInst *) inst)->getNumSuccessors();
 270          i++) {
 271       BasicBlock *sb = ((BranchInst *) inst)->getSuccessor(i);
 272       if (sb == bb)
 273         return true;
 274     }
 275   }
 276
 277   return false;
 278
 279 }
 280
 281 /*
 282   compute every node's ASAP
 283
 284 */
 285
 286 //FIXME: now assume the only backward edges come from the edges from other
 287 //nodes to the phi Node so i will ignore all edges to the phi node; after
 288 //this, there shall be no recurrence.
 289
 290 void
 291 ModuloSchedGraph::computeNodeASAP(const BasicBlock *bb) {
 292
 293
 294   unsigned numNodes = bb->size();
 295   for (unsigned i = 2; i < numNodes + 2; i++) {
 296     ModuloSchedGraphNode *node = getNode(i);
 297     node->setPropertyComputed(false);
 298   }
 299
 300   for (unsigned i = 2; i < numNodes + 2; i++) {
 301     ModuloSchedGraphNode *node = getNode(i);
 302     node->ASAP = 0;
 303     if (i == 2 || node->getNumInEdges() == 0) {
 304       node->setPropertyComputed(true);
 305       continue;
 306     }
 307     for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E =
 308          node->endInEdges(); I != E; I++) {
 309       SchedGraphEdge *edge = *I;
 310       ModuloSchedGraphNode *pred =
 311           (ModuloSchedGraphNode *) (edge->getSrc());
 312       assert(pred->getPropertyComputed()
 313              && "pred node property is not computed!");
 314       int temp =
 315           pred->ASAP + edge->getMinDelay() -
 316           edge->getIteDiff() * this->MII;
 317       node->ASAP = std::max(node->ASAP, temp);
 318     }
 319     node->setPropertyComputed(true);
 320   }
 321 }
 322
 323
 324 /*
 325   compute every node's ALAP in the basic block
 326 */
 327
 328 void
 329 ModuloSchedGraph::computeNodeALAP(const BasicBlock *bb) {
 330
 331   unsigned numNodes = bb->size();
 332   int maxASAP = 0;
 333   for (unsigned i = numNodes + 1; i >= 2; i--) {
 334
 335     ModuloSchedGraphNode *node = getNode(i);
 336     node->setPropertyComputed(false);
 337     maxASAP = std::max(maxASAP, node->ASAP);
 338
 339   }
 340
 341   for (unsigned i = numNodes + 1; i >= 2; i--) {
 342     ModuloSchedGraphNode *node = getNode(i);
 343
 344     node->ALAP = maxASAP;
 345
 346     for (ModuloSchedGraphNode::const_iterator I =
 347          node->beginOutEdges(), E = node->endOutEdges(); I != E; I++) {
 348
 349       SchedGraphEdge *edge = *I;
 350       ModuloSchedGraphNode *succ =
 351         (ModuloSchedGraphNode *) (edge->getSink());
 352       if (PHINode::classof(succ->getInst()))
 353         continue;
 354
 355       assert(succ->getPropertyComputed()
 356              && "succ node property is not computed!");
 357
 358       int temp =
 359           succ->ALAP - edge->getMinDelay() +
 360           edge->getIteDiff() * this->MII;
 361
 362       node->ALAP = std::min(node->ALAP, temp);
 363
 364     }
 365     node->setPropertyComputed(true);
 366   }
 367 }
 368
 369 /*
 370   compute every node's mov in this basicblock
 371 */
 372
 373 void
 374 ModuloSchedGraph::computeNodeMov(const BasicBlock *bb){
 375
 376   unsigned numNodes = bb->size();
 377   for (unsigned i = 2; i < numNodes + 2; i++) {
 378
 379     ModuloSchedGraphNode *node = getNode(i);
 380     node->mov = node->ALAP - node->ASAP;
 381     assert(node->mov >= 0
 382            && "move freedom for this node is less than zero? ");
 383
 384   }
 385
 386 }
 387
 388
 389 /*
 390   compute every node's depth in this basicblock
 391 */
 392 void
 393 ModuloSchedGraph::computeNodeDepth(const BasicBlock * bb){
 394
 395   unsigned numNodes = bb->size();
 396
 397   for (unsigned i = 2; i < numNodes + 2; i++) {
 398
 399     ModuloSchedGraphNode *node = getNode(i);
 400     node->setPropertyComputed(false);
 401
 402   }
 403
 404   for (unsigned i = 2; i < numNodes + 2; i++) {
 405
 406     ModuloSchedGraphNode *node = getNode(i);
 407     node->depth = 0;
 408     if (i == 2 || node->getNumInEdges() == 0) {
 409       node->setPropertyComputed(true);
 410       continue;
 411     }
 412
 413     for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E =
 414          node->endInEdges(); I != E; I++) {
 415       SchedGraphEdge *edge = *I;
 416       ModuloSchedGraphNode *pred =
 417           (ModuloSchedGraphNode *) (edge->getSrc());
 418       assert(pred->getPropertyComputed()
 419              && "pred node property is not computed!");
 420       int temp = pred->depth + edge->getMinDelay();
 421       node->depth = std::max(node->depth, temp);
 422     }
 423     node->setPropertyComputed(true);
 424
 425   }
 426
 427 }
 428
 429
 430 /*
 431   compute every node's height in this basic block
 432 */
 433
 434 void
 435 ModuloSchedGraph::computeNodeHeight(const BasicBlock *bb){
 436
 437   unsigned numNodes = bb->size();
 438   for (unsigned i = numNodes + 1; i >= 2; i--) {
 439     ModuloSchedGraphNode *node = getNode(i);
 440     node->setPropertyComputed(false);
 441   }
 442
 443   for (unsigned i = numNodes + 1; i >= 2; i--) {
 444     ModuloSchedGraphNode *node = getNode(i);
 445     node->height = 0;
 446     for (ModuloSchedGraphNode::const_iterator I =
 447            node->beginOutEdges(), E = node->endOutEdges(); I != E; ++I) {
 448       SchedGraphEdge *edge = *I;
 449       ModuloSchedGraphNode *succ =
 450         (ModuloSchedGraphNode *) (edge->getSink());
 451       if (PHINode::classof(succ->getInst()))
 452         continue;
 453       assert(succ->getPropertyComputed()
 454              && "succ node property is not computed!");
 455       node->height = std::max(node->height, succ->height + edge->getMinDelay());
 456
 457     }
 458     node->setPropertyComputed(true);
 459   }
 460
 461 }
 462
 463 /*
 464   compute every node's property in a basicblock
 465 */
 466
 467 void ModuloSchedGraph::computeNodeProperty(const BasicBlock * bb)
 468 {
 469   //FIXME: now assume the only backward edges come from the edges from other
 470   //nodes to the phi Node so i will ignore all edges to the phi node; after
 471   //this, there shall be no recurrence.
 472
 473   this->computeNodeASAP(bb);
 474   this->computeNodeALAP(bb);
 475   this->computeNodeMov(bb);
 476   this->computeNodeDepth(bb);
 477   this->computeNodeHeight(bb);
 478 }
 479
 480
 481 /*
 482   compute the preset of this set without considering the edges
 483   between backEdgeSrc and backEdgeSink
 484 */
 485 std::vector<ModuloSchedGraphNode*>
 486 ModuloSchedGraph::predSet(std::vector<ModuloSchedGraphNode*> set,
 487                           unsigned backEdgeSrc,
 488                           unsigned
 489                           backEdgeSink){
 490
 491   std::vector<ModuloSchedGraphNode*> predS;
 492
 493   for (unsigned i = 0; i < set.size(); i++) {
 494
 495     ModuloSchedGraphNode *node = set[i];
 496     for (ModuloSchedGraphNode::const_iterator I = node->beginInEdges(), E =
 497          node->endInEdges(); I != E; I++) {
 498       SchedGraphEdge *edge = *I;
 499
 500       //if edges between backEdgeSrc and backEdgeSink, omitted
 501       if (edge->getSrc()->getNodeId() == backEdgeSrc
 502           && edge->getSink()->getNodeId() == backEdgeSink)
 503         continue;
 504       ModuloSchedGraphNode *pred =
 505           (ModuloSchedGraphNode *) (edge->getSrc());
 506
 507       //if pred is not in the predSet ....
 508       bool alreadyInset = false;
 509       for (unsigned j = 0; j < predS.size(); ++j)
 510         if (predS[j]->getNodeId() == pred->getNodeId()) {
 511           alreadyInset = true;
 512           break;
 513         }
 514
 515       // and pred is not in the set ....
 516       for (unsigned j = 0; j < set.size(); ++j)
 517         if (set[j]->getNodeId() == pred->getNodeId()) {
 518           alreadyInset = true;
 519           break;
 520         }
 521
 522       //push it into the predS
 523       if (!alreadyInset)
 524         predS.push_back(pred);
 525     }
 526   }
 527   return predS;
 528 }
 529
 530
 531 /*
 532   return pred set to this set
 533 */
 534
 535 ModuloSchedGraph::NodeVec
 536 ModuloSchedGraph::predSet(NodeVec set){
 537
 538   //node number increases from 2,
 539   return predSet(set, 0, 0);
 540 }
 541
 542 /*
 543   return pred set to  _node, ignoring
 544   any edge between backEdgeSrc and backEdgeSink
 545 */
 546 std::vector <ModuloSchedGraphNode*>
 547 ModuloSchedGraph::predSet(ModuloSchedGraphNode *_node,
 548                           unsigned backEdgeSrc, unsigned backEdgeSink){
 549
 550   std::vector<ModuloSchedGraphNode*> set;
 551   set.push_back(_node);
 552   return predSet(set, backEdgeSrc, backEdgeSink);
 553 }
 554
 555
 556 /*
 557   return pred set to  _node, ignoring
 558 */
 559
 560 std::vector <ModuloSchedGraphNode*>
 561 ModuloSchedGraph::predSet(ModuloSchedGraphNode * _node){
 562
 563   return predSet(_node, 0, 0);
 564
 565 }
 566
 567 /*
 568   return successor set to the input set
 569   ignoring any edge between src and sink
 570 */
 571
 572 std::vector<ModuloSchedGraphNode*>
 573 ModuloSchedGraph::succSet(std::vector<ModuloSchedGraphNode*> set,
 574                           unsigned src, unsigned sink){
 575
 576   std::vector<ModuloSchedGraphNode*> succS;
 577
 578   for (unsigned i = 0; i < set.size(); i++) {
 579     ModuloSchedGraphNode *node = set[i];
 580     for (ModuloSchedGraphNode::const_iterator I =
 581          node->beginOutEdges(), E = node->endOutEdges(); I != E; I++) {
 582       SchedGraphEdge *edge = *I;
 583
 584       //if the edge is between src and sink, skip
 585       if (edge->getSrc()->getNodeId() == src
 586           && edge->getSink()->getNodeId() == sink)
 587         continue;
 588       ModuloSchedGraphNode *succ =
 589           (ModuloSchedGraphNode *) (edge->getSink());
 590
 591       //if pred is not in the successor set ....
 592       bool alreadyInset = false;
 593       for (unsigned j = 0; j < succS.size(); j++)
 594         if (succS[j]->getNodeId() == succ->getNodeId()) {
 595           alreadyInset = true;
 596           break;
 597         }
 598
 599       //and not in this set ....
 600       for (unsigned j = 0; j < set.size(); j++)
 601         if (set[j]->getNodeId() == succ->getNodeId()) {
 602           alreadyInset = true;
 603           break;
 604         }
 605
 606       //push it into the successor set
 607       if (!alreadyInset)
 608         succS.push_back(succ);
 609     }
 610   }
 611   return succS;
 612 }
 613
 614 /*
 615   return successor set to the input set
 616 */
 617
 618 ModuloSchedGraph::NodeVec ModuloSchedGraph::succSet(NodeVec set){
 619
 620   return succSet(set, 0, 0);
 621
 622 }
 623
 624 /*
 625   return successor set to the input node
 626   ignoring any edge between src and sink
 627 */
 628
 629 std::vector<ModuloSchedGraphNode*>
 630 ModuloSchedGraph::succSet(ModuloSchedGraphNode *_node,
 631                           unsigned src, unsigned sink){
 632
 633   std::vector<ModuloSchedGraphNode*>set;
 634
 635   set.push_back(_node);
 636
 637   return succSet(set, src, sink);
 638
 639 }
 640
 641 /*
 642   return successor set to the input node
 643 */
 644
 645 std::vector<ModuloSchedGraphNode*>
 646 ModuloSchedGraph::succSet(ModuloSchedGraphNode * _node){
 647
 648   return succSet(_node, 0, 0);
 649
 650 }
 651
 652
 653 /*
 654   find maximum delay between srcId and sinkId
 655 */
 656
 657 SchedGraphEdge*
 658 ModuloSchedGraph::getMaxDelayEdge(unsigned srcId,
 659                                   unsigned sinkId){
 660
 661   ModuloSchedGraphNode *node = getNode(srcId);
 662   SchedGraphEdge *maxDelayEdge = NULL;
 663   int maxDelay = -1;
 664   for (ModuloSchedGraphNode::const_iterator I = node->beginOutEdges(), E =
 665        node->endOutEdges(); I != E; I++) {
 666     SchedGraphEdge *edge = *I;
 667     if (edge->getSink()->getNodeId() == sinkId)
 668       if (edge->getMinDelay() > maxDelay) {
 669         maxDelayEdge = edge;
 670         maxDelay = edge->getMinDelay();
 671       }
 672   }
 673   assert(maxDelayEdge != NULL && "no edge between the srcId and sinkId?");
 674   return maxDelayEdge;
 675
 676 }
 677
 678 /*
 679   dump all circuits found
 680 */
 681
 682 void
 683 ModuloSchedGraph::dumpCircuits(){
 684
 685   DEBUG_PRINT(std::cerr << "dumping circuits for graph:\n");
 686   int j = -1;
 687   while (circuits[++j][0] != 0) {
 688     int k = -1;
 689     while (circuits[j][++k] != 0)
 690       DEBUG_PRINT(std::cerr << circuits[j][k] << "\t");
 691     DEBUG_PRINT(std::cerr << "\n");
 692   }
 693 }
 694
 695 /*
 696   dump all sets found
 697 */
 698
 699 void
 700 ModuloSchedGraph::dumpSet(std::vector < ModuloSchedGraphNode * >set){
 701
 702   for (unsigned i = 0; i < set.size(); i++)
 703     DEBUG_PRINT(std::cerr << set[i]->getNodeId() << "\t");
 704   DEBUG_PRINT(std::cerr << "\n");
 705
 706 }
 707
 708 /*
 709   return union of set1 and set2
 710 */
 711
 712 std::vector<ModuloSchedGraphNode*>
 713 ModuloSchedGraph::vectorUnion(std::vector<ModuloSchedGraphNode*> set1,
 714                               std::vector<ModuloSchedGraphNode*> set2){
 715
 716   std::vector<ModuloSchedGraphNode*> unionVec;
 717   for (unsigned i = 0; i < set1.size(); i++)
 718     unionVec.push_back(set1[i]);
 719   for (unsigned j = 0; j < set2.size(); j++) {
 720     bool inset = false;
 721     for (unsigned i = 0; i < unionVec.size(); i++)
 722       if (set2[j] == unionVec[i])
 723         inset = true;
 724     if (!inset)
 725       unionVec.push_back(set2[j]);
 726   }
 727   return unionVec;
 728 }
 729
 730 /*
 731   return conjuction of set1 and set2
 732 */
 733 std::vector<ModuloSchedGraphNode*>
 734 ModuloSchedGraph::vectorConj(std::vector<ModuloSchedGraphNode*> set1,
 735                              std::vector<ModuloSchedGraphNode*> set2){
 736
 737   std::vector<ModuloSchedGraphNode*> conjVec;
 738   for (unsigned i = 0; i < set1.size(); i++)
 739     for (unsigned j = 0; j < set2.size(); j++)
 740       if (set1[i] == set2[j])
 741         conjVec.push_back(set1[i]);
 742   return conjVec;
 743
 744 }
 745
 746 /*
 747   return the result of subtracting set2 from set1
 748   (set1 -set2)
 749 */
 750 ModuloSchedGraph::NodeVec
 751 ModuloSchedGraph::vectorSub(NodeVec set1,
 752                             NodeVec set2){
 753
 754   NodeVec newVec;
 755   for (NodeVec::iterator I = set1.begin(); I != set1.end(); I++) {
 756
 757     bool inset = false;
 758     for (NodeVec::iterator II = set2.begin(); II != set2.end(); II++)
 759       if ((*I)->getNodeId() == (*II)->getNodeId()) {
 760         inset = true;
 761         break;
 762       }
 763
 764     if (!inset)
 765       newVec.push_back(*I);
 766
 767   }
 768
 769   return newVec;
 770
 771 }
 772
 773 /*
 774   order all nodes in the basicblock
 775   based on the sets information and node property
 776
 777   output: ordered nodes are stored in oNodes
 778 */
 779
 780 void ModuloSchedGraph::orderNodes() {
 781   oNodes.clear();
 782
 783   std::vector < ModuloSchedGraphNode * >set;
 784   unsigned numNodes = bb->size();
 785
 786   // first order all the sets
 787   int j = -1;
 788   int totalDelay = -1;
 789   int preDelay = -1;
 790   while (circuits[++j][0] != 0) {
 791     int k = -1;
 792     preDelay = totalDelay;
 793
 794     while (circuits[j][++k] != 0) {
 795       ModuloSchedGraphNode *node = getNode(circuits[j][k]);
 796       unsigned nextNodeId;
 797       nextNodeId =
 798           circuits[j][k + 1] != 0 ? circuits[j][k + 1] : circuits[j][0];
 799       SchedGraphEdge *edge = getMaxDelayEdge(circuits[j][k], nextNodeId);
 800       totalDelay += edge->getMinDelay();
 801     }
 802     if (preDelay != -1 && totalDelay > preDelay) {
 803       // swap circuits[j][] and cuicuits[j-1][]
 804       unsigned temp[MAXNODE];
 805       for (int k = 0; k < MAXNODE; k++) {
 806         temp[k] = circuits[j - 1][k];
 807         circuits[j - 1][k] = circuits[j][k];
 808         circuits[j][k] = temp[k];
 809       }
 810       //restart
 811       j = -1;
 812     }
 813   }
 814
 815
 816   // build the first set
 817   int backEdgeSrc;
 818   int backEdgeSink;
 819   if (ModuloScheduling::printScheduleProcess())
 820     DEBUG_PRINT(std::cerr << "building the first set" << "\n");
 821   int setSeq = -1;
 822   int k = -1;
 823   setSeq++;
 824   while (circuits[setSeq][++k] != 0)
 825     set.push_back(getNode(circuits[setSeq][k]));
 826   if (circuits[setSeq][0] != 0) {
 827     backEdgeSrc = circuits[setSeq][k - 1];
 828     backEdgeSink = circuits[setSeq][0];
 829   }
 830   if (ModuloScheduling::printScheduleProcess()) {
 831     DEBUG_PRINT(std::cerr << "the first set is:");
 832     dumpSet(set);
 833   }
 834
 835   // implement the ordering algorithm
 836   enum OrderSeq { bottom_up, top_down };
 837   OrderSeq order;
 838   std::vector<ModuloSchedGraphNode*> R;
 839   while (!set.empty()) {
 840     std::vector<ModuloSchedGraphNode*> pset = predSet(oNodes);
 841     std::vector<ModuloSchedGraphNode*> sset = succSet(oNodes);
 842
 843     if (!pset.empty() && !vectorConj(pset, set).empty()) {
 844       R = vectorConj(pset, set);
 845       order = bottom_up;
 846     } else if (!sset.empty() && !vectorConj(sset, set).empty()) {
 847       R = vectorConj(sset, set);
 848       order = top_down;
 849     } else {
 850       int maxASAP = -1;
 851       int position = -1;
 852       for (unsigned i = 0; i < set.size(); i++) {
 853         int temp = set[i]->getASAP();
 854         if (temp > maxASAP) {
 855           maxASAP = temp;
 856           position = i;
 857         }
 858       }
 859       R.push_back(set[position]);
 860       order = bottom_up;
 861     }
 862
 863     while (!R.empty()) {
 864       if (order == top_down) {
 865         if (ModuloScheduling::printScheduleProcess())
 866           DEBUG_PRINT(std::cerr << "in top_down round\n");
 867         while (!R.empty()) {
 868           int maxHeight = -1;
 869           NodeVec::iterator chosenI;
 870           for (NodeVec::iterator I = R.begin(); I != R.end(); I++) {
 871             int temp = (*I)->height;
 872             if ((temp > maxHeight)
 873                 || (temp == maxHeight && (*I)->mov <= (*chosenI)->mov)) {
 874
 875               if ((temp > maxHeight)
 876                   || (temp == maxHeight && (*I)->mov < (*chosenI)->mov)) {
 877                 maxHeight = temp;
 878                 chosenI = I;
 879                 continue;
 880               }
 881
 882               //possible case: instruction A and B has the same height and mov,
 883               //but A has dependence to B e.g B is the branch instruction in the
 884               //end, or A is the phi instruction at the beginning
 885               if ((*I)->mov == (*chosenI)->mov)
 886                 for (ModuloSchedGraphNode::const_iterator oe =
 887                      (*I)->beginOutEdges(), end = (*I)->endOutEdges();
 888                      oe != end; oe++) {
 889                   if ((*oe)->getSink() == (*chosenI)) {
 890                     maxHeight = temp;
 891                     chosenI = I;
 892                     continue;
 893                   }
 894                 }
 895             }
 896           }
 897
 898           ModuloSchedGraphNode *mu = *chosenI;
 899           oNodes.push_back(mu);
 900           R.erase(chosenI);
 901           std::vector<ModuloSchedGraphNode*> succ_mu =
 902             succSet(mu, backEdgeSrc, backEdgeSink);
 903           std::vector<ModuloSchedGraphNode*> comm =
 904             vectorConj(succ_mu, set);
 905           comm = vectorSub(comm, oNodes);
 906           R = vectorUnion(comm, R);
 907         }
 908         order = bottom_up;
 909         R = vectorConj(predSet(oNodes), set);
 910       } else {
 911         if (ModuloScheduling::printScheduleProcess())
 912           DEBUG_PRINT(std::cerr << "in bottom up round\n");
 913         while (!R.empty()) {
 914           int maxDepth = -1;
 915           NodeVec::iterator chosenI;
 916           for (NodeVec::iterator I = R.begin(); I != R.end(); I++) {
 917             int temp = (*I)->depth;
 918             if ((temp > maxDepth)
 919                 || (temp == maxDepth && (*I)->mov < (*chosenI)->mov)) {
 920               maxDepth = temp;
 921               chosenI = I;
 922             }
 923           }
 924           ModuloSchedGraphNode *mu = *chosenI;
 925           oNodes.push_back(mu);
 926           R.erase(chosenI);
 927           std::vector<ModuloSchedGraphNode*> pred_mu =
 928             predSet(mu, backEdgeSrc, backEdgeSink);
 929           std::vector<ModuloSchedGraphNode*> comm =
 930             vectorConj(pred_mu, set);
 931           comm = vectorSub(comm, oNodes);
 932           R = vectorUnion(comm, R);
 933         }
 934         order = top_down;
 935         R = vectorConj(succSet(oNodes), set);
 936       }
 937     }
 938     if (ModuloScheduling::printScheduleProcess()) {
 939       DEBUG_PRINT(std::cerr << "order finished\n");
 940       DEBUG_PRINT(std::cerr << "dumping the ordered nodes:\n");
 941       dumpSet(oNodes);
 942       dumpCircuits();
 943     }
 944
 945     //create a new set
 946     //FIXME: the nodes between onodes and this circuit should also be include in
 947     //this set
 948     if (ModuloScheduling::printScheduleProcess())
 949       DEBUG_PRINT(std::cerr << "building the next set\n");
 950     set.clear();
 951     int k = -1;
 952     setSeq++;
 953     while (circuits[setSeq][++k] != 0)
 954       set.push_back(getNode(circuits[setSeq][k]));
 955     if (circuits[setSeq][0] != 0) {
 956       backEdgeSrc = circuits[setSeq][k - 1];
 957       backEdgeSink = circuits[setSeq][0];
 958     }
 959
 960     if (set.empty()) {
 961       //no circuits any more
 962       //collect all other nodes
 963       if (ModuloScheduling::printScheduleProcess())
 964         DEBUG_PRINT(std::cerr << "no circuits any more, collect the rest nodes\n");
 965       for (unsigned i = 2; i < numNodes + 2; i++) {
 966         bool inset = false;
 967         for (unsigned j = 0; j < oNodes.size(); j++)
 968           if (oNodes[j]->getNodeId() == i) {
 969             inset = true;
 970             break;
 971           }
 972         if (!inset)
 973           set.push_back(getNode(i));
 974       }
 975     }
 976     if (ModuloScheduling::printScheduleProcess()) {
 977       DEBUG_PRINT(std::cerr << "next set is:\n");
 978       dumpSet(set);
 979     }
 980   }
 981
 982 }
 983
 984
 985
 986 /*
 987
 988   build graph for instructions in this basic block
 989
 990 */
 991 void ModuloSchedGraph::buildGraph(const TargetMachine & target)
 992 {
 993
 994   assert(this->bb && "The basicBlock is NULL?");
 995
 996   // Make a dummy root node.  We'll add edges to the real roots later.
 997   graphRoot = new ModuloSchedGraphNode(0, NULL, NULL, -1, target);
 998   graphLeaf = new ModuloSchedGraphNode(1, NULL, NULL, -1, target);
 999
1000   if (ModuloScheduling::printScheduleProcess())
1001     this->dump(bb);
1002
1003   if (isLoop(bb)) {
1004
1005     DEBUG_PRINT(cerr << "building nodes for this BasicBlock\n");
1006     buildNodesforBB(target, bb);
1007
1008     DEBUG_PRINT(cerr << "adding def-use edge to this basic block\n");
1009     this->addDefUseEdges(bb);
1010
1011     DEBUG_PRINT(cerr << "adding CD edges to this basic block\n");
1012     this->addCDEdges(bb);
1013
1014     DEBUG_PRINT(cerr << "adding memory edges to this basicblock\n");
1015     this->addMemEdges(bb);
1016
1017     int ResII = this->computeResII(bb);
1018
1019     if (ModuloScheduling::printScheduleProcess())
1020       DEBUG_PRINT(std::cerr << "ResII is " << ResII << "\n");
1021
1022     int RecII = this->computeRecII(bb);
1023     if (ModuloScheduling::printScheduleProcess())
1024       DEBUG_PRINT(std::cerr << "RecII is " << RecII << "\n");
1025
1026     this->MII = std::max(ResII, RecII);
1027
1028     this->computeNodeProperty(bb);
1029     if (ModuloScheduling::printScheduleProcess())
1030       this->dumpNodeProperty();
1031
1032     this->orderNodes();
1033
1034     if (ModuloScheduling::printScheduleProcess())
1035       this->dump();
1036
1037   }
1038 }
1039
1040 /*
1041   get node with nodeId
1042 */
1043
1044 ModuloSchedGraphNode *
1045 ModuloSchedGraph::getNode(const unsigned nodeId) const{
1046
1047   for (const_iterator I = begin(), E = end(); I != E; I++)
1048     if ((*I).second->getNodeId() == nodeId)
1049       return (ModuloSchedGraphNode *) (*I).second;
1050   return NULL;
1051
1052 }
1053
1054 /*
1055   compute RecurrenceII
1056 */
1057
1058 int
1059 ModuloSchedGraph::computeRecII(const BasicBlock *bb){
1060
1061   int RecII = 0;
1062
1063
1064   //FIXME: only deal with circuits starting at the first node: the phi node
1065   //nodeId=2;
1066
1067   //search all elementary circuits in the dependence graph
1068   //assume maximum number of nodes is MAXNODE
1069
1070   unsigned path[MAXNODE];
1071   unsigned stack[MAXNODE][MAXNODE];
1072
1073   for (int j = 0; j < MAXNODE; j++) {
1074     path[j] = 0;
1075     for (int k = 0; k < MAXNODE; k++)
1076       stack[j][k] = 0;
1077   }
1078
1079   //in our graph, the node number starts at 2
1080   const unsigned numNodes = bb->size();
1081
1082   int i = 0;
1083   path[i] = 2;
1084
1085   ModuloSchedGraphNode *initNode = getNode(path[0]);
1086   unsigned initNodeId = initNode->getNodeId();
1087   ModuloSchedGraphNode *currentNode = initNode;
1088
1089   while (currentNode != NULL) {
1090     unsigned currentNodeId = currentNode->getNodeId();
1091     // DEBUG_PRINT(std::cerr<<"current node is "<<currentNodeId<<"\n");
1092
1093     ModuloSchedGraphNode *nextNode = NULL;
1094     for (ModuloSchedGraphNode::const_iterator I =
1095          currentNode->beginOutEdges(), E = currentNode->endOutEdges();
1096          I != E; I++) {
1097       //DEBUG_PRINT(std::cerr <<" searching in outgoint edges of node
1098       //"<<currentNodeId<<"\n";
1099       unsigned nodeId = ((SchedGraphEdge *) * I)->getSink()->getNodeId();
1100       bool inpath = false, instack = false;
1101       int k;
1102
1103       //DEBUG_PRINT(std::cerr<<"nodeId is "<<nodeId<<"\n");
1104
1105       k = -1;
1106       while (path[++k] != 0)
1107         if (nodeId == path[k]) {
1108           inpath = true;
1109           break;
1110         }
1111
1112       k = -1;
1113       while (stack[i][++k] != 0)
1114         if (nodeId == stack[i][k]) {
1115           instack = true;
1116           break;
1117         }
1118
1119       if (nodeId > currentNodeId && !inpath && !instack) {
1120         nextNode =
1121             (ModuloSchedGraphNode *) ((SchedGraphEdge *) * I)->getSink();
1122         break;
1123       }
1124     }
1125
1126     if (nextNode != NULL) {
1127       //DEBUG_PRINT(std::cerr<<"find the next Node "<<nextNode->getNodeId()<<"\n");
1128
1129       int j = 0;
1130       while (stack[i][j] != 0)
1131         j++;
1132       stack[i][j] = nextNode->getNodeId();
1133
1134       i++;
1135       path[i] = nextNode->getNodeId();
1136       currentNode = nextNode;
1137     } else {
1138       //DEBUG_PRINT(std::cerr<<"no expansion any more"<<"\n");
1139       //confirmCircuit();
1140       for (ModuloSchedGraphNode::const_iterator I =
1141            currentNode->beginOutEdges(), E = currentNode->endOutEdges();
1142            I != E; I++) {
1143         unsigned nodeId = ((SchedGraphEdge *) * I)->getSink()->getNodeId();
1144         if (nodeId == initNodeId) {
1145
1146           int j = -1;
1147           while (circuits[++j][0] != 0);
1148           for (int k = 0; k < MAXNODE; k++)
1149             circuits[j][k] = path[k];
1150
1151         }
1152       }
1153       //remove this node in the path and clear the corresponding entries in the
1154       //stack
1155       path[i] = 0;
1156       int j = 0;
1157       for (j = 0; j < MAXNODE; j++)
1158         stack[i][j] = 0;
1159       i--;
1160       currentNode = getNode(path[i]);
1161     }
1162     if (i == 0) {
1163
1164       if (ModuloScheduling::printScheduleProcess())
1165         DEBUG_PRINT(std::cerr << "circuits found are:\n");
1166       int j = -1;
1167       while (circuits[++j][0] != 0) {
1168         int k = -1;
1169         while (circuits[j][++k] != 0)
1170           if (ModuloScheduling::printScheduleProcess())
1171             DEBUG_PRINT(std::cerr << circuits[j][k] << "\t");
1172         if (ModuloScheduling::printScheduleProcess())
1173           DEBUG_PRINT(std::cerr << "\n");
1174
1175         //for this circuit, compute the sum of all edge delay
1176         int sumDelay = 0;
1177         k = -1;
1178         while (circuits[j][++k] != 0) {
1179           //ModuloSchedGraphNode* node =getNode(circuits[j][k]);
1180           unsigned nextNodeId;
1181           nextNodeId =
1182               circuits[j][k + 1] !=
1183               0 ? circuits[j][k + 1] : circuits[j][0];
1184
1185           sumDelay +=
1186             getMaxDelayEdge(circuits[j][k], nextNodeId)->getMinDelay();
1187
1188         }
1189         //       assume we have distance 1, in this case the sumDelay is RecII
1190         //       this is correct for SSA form only
1191         //
1192         if (ModuloScheduling::printScheduleProcess())
1193           DEBUG_PRINT(std::cerr << "The total Delay in the circuit is " << sumDelay
1194                 << "\n");
1195
1196         RecII = RecII > sumDelay ? RecII : sumDelay;
1197
1198       }
1199       return RecII;
1200     }
1201
1202   }
1203
1204   return -1;
1205 }
1206
1207 /*
1208   update resource usage vector (ruVec)
1209 */
1210 void
1211 ModuloSchedGraph::addResourceUsage(std::vector<std::pair<int,int> > &ruVec,
1212                                    int rid){
1213
1214   bool alreadyExists = false;
1215   for (unsigned i = 0; i < ruVec.size(); i++) {
1216     if (rid == ruVec[i].first) {
1217       ruVec[i].second++;
1218       alreadyExists = true;
1219       break;
1220     }
1221   }
1222   if (!alreadyExists)
1223     ruVec.push_back(std::make_pair(rid, 1));
1224
1225 }
1226
1227 /*
1228   dump the resource usage vector
1229 */
1230
1231 void
1232 ModuloSchedGraph::dumpResourceUsage(std::vector<std::pair<int,int> > &ru){
1233
1234   TargetSchedInfo & msi = (TargetSchedInfo &) target.getSchedInfo();
1235
1236   std::vector<std::pair<int,int> > resourceNumVector = msi.resourceNumVector;
1237   DEBUG_PRINT(std::cerr << "resourceID\t" << "resourceNum\n");
1238   for (unsigned i = 0; i < resourceNumVector.size(); i++)
1239     DEBUG_PRINT(std::cerr << resourceNumVector[i].
1240         first << "\t" << resourceNumVector[i].second << "\n");
1241
1242   DEBUG_PRINT(std::cerr << " maxNumIssueTotal(issue slot in one cycle) = " << msi.
1243         maxNumIssueTotal << "\n");
1244   DEBUG_PRINT(std::cerr << "resourceID\t resourceUsage\t ResourceNum\n");
1245   for (unsigned i = 0; i < ru.size(); i++) {
1246     DEBUG_PRINT(std::cerr << ru[i].first << "\t" << ru[i].second);
1247     const unsigned resNum = msi.getCPUResourceNum(ru[i].first);
1248     DEBUG_PRINT(std::cerr << "\t" << resNum << "\n");
1249
1250   }
1251 }
1252
1253 /*
1254   compute thre resource restriction II
1255 */
1256
1257 int
1258 ModuloSchedGraph::computeResII(const BasicBlock * bb){
1259
1260   const TargetInstrInfo & mii = target.getInstrInfo();
1261   const TargetSchedInfo & msi = target.getSchedInfo();
1262
1263   int ResII;
1264   std::vector<std::pair<int,int> > resourceUsage;
1265
1266   for (BasicBlock::const_iterator I = bb->begin(), E = bb->end(); I != E;
1267        I++) {
1268     if (ModuloScheduling::printScheduleProcess()) {
1269       DEBUG_PRINT(std::cerr << "machine instruction for llvm instruction( node " <<
1270             getGraphNodeForInst(I)->getNodeId() << ")\n");
1271       DEBUG_PRINT(std::cerr << "\t" << *I);
1272     }
1273     MachineCodeForInstruction & tempMvec =
1274         MachineCodeForInstruction::get(I);
1275     if (ModuloScheduling::printScheduleProcess())
1276       DEBUG_PRINT(std::cerr << "size =" << tempMvec.size() << "\n");
1277     for (unsigned i = 0; i < tempMvec.size(); i++) {
1278       MachineInstr *minstr = tempMvec[i];
1279
1280       unsigned minDelay = mii.minLatency(minstr->getOpCode());
1281       InstrRUsage rUsage = msi.getInstrRUsage(minstr->getOpCode());
1282       InstrClassRUsage classRUsage =
1283           msi.getClassRUsage(mii.getSchedClass(minstr->getOpCode()));
1284       unsigned totCycles = classRUsage.totCycles;
1285
1286       std::vector<std::vector<resourceId_t> > resources=rUsage.resourcesByCycle;
1287       assert(totCycles == resources.size());
1288       if (ModuloScheduling::printScheduleProcess())
1289         DEBUG_PRINT(std::cerr << "resources Usage for this Instr(totCycles="
1290               << totCycles << ",mindLatency="
1291               << mii.minLatency(minstr->getOpCode()) << "): " << *minstr
1292               << "\n");
1293       for (unsigned j = 0; j < resources.size(); j++) {
1294         if (ModuloScheduling::printScheduleProcess())
1295           DEBUG_PRINT(std::cerr << "cycle " << j << ": ");
1296         for (unsigned k = 0; k < resources[j].size(); k++) {
1297           if (ModuloScheduling::printScheduleProcess())
1298             DEBUG_PRINT(std::cerr << "\t" << resources[j][k]);
1299           addResourceUsage(resourceUsage, resources[j][k]);
1300         }
1301         if (ModuloScheduling::printScheduleProcess())
1302           DEBUG_PRINT(std::cerr << "\n");
1303       }
1304     }
1305   }
1306   if (ModuloScheduling::printScheduleProcess())
1307     this->dumpResourceUsage(resourceUsage);
1308
1309   //compute ResII
1310   ResII = 0;
1311   int issueSlots = msi.maxNumIssueTotal;
1312   for (unsigned i = 0; i < resourceUsage.size(); i++) {
1313     int resourceNum = msi.getCPUResourceNum(resourceUsage[i].first);
1314     int useNum = resourceUsage[i].second;
1315     double tempII;
1316     if (resourceNum <= issueSlots)
1317       tempII = ceil(1.0 * useNum / resourceNum);
1318     else
1319       tempII = ceil(1.0 * useNum / issueSlots);
1320     ResII = std::max((int) tempII, ResII);
1321   }
1322   return ResII;
1323 }
1324
1325
1326
1327 /*
1328   dump the basicblock
1329 */
1330
1331 void
1332 ModuloSchedGraph::dump(const BasicBlock * bb){
1333
1334   DEBUG_PRINT(std::cerr << "dumping basic block:");
1335   DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
1336               << " (" << bb << ")" << "\n");
1337
1338 }
1339
1340 /*
1341   dump the basicblock to ostream os
1342 */
1343
1344 void
1345 ModuloSchedGraph::dump(const BasicBlock * bb, std::ostream & os){
1346
1347   os << "dumping basic block:";
1348   os << (bb->hasName()? bb->getName() : "block")
1349       << " (" << bb << ")" << "\n";
1350 }
1351
1352 /*
1353   dump the graph
1354 */
1355
1356 void ModuloSchedGraph::dump() const
1357 {
1358   DEBUG_PRINT(std::cerr << " ModuloSchedGraph for basic Blocks:");
1359
1360   DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
1361         << " (" << bb << ")" <<  "");
1362
1363   DEBUG_PRINT(std::cerr << "\n\n    Actual Root nodes : ");
1364   for (unsigned i = 0, N = graphRoot->outEdges.size(); i < N; i++)
1365     DEBUG_PRINT(std::cerr << graphRoot->outEdges[i]->getSink()->getNodeId()
1366           << ((i == N - 1) ? "" : ", "));
1367
1368   DEBUG_PRINT(std::cerr << "\n    Graph Nodes:\n");
1369
1370   unsigned numNodes = bb->size();
1371   for (unsigned i = 2; i < numNodes + 2; i++) {
1372     ModuloSchedGraphNode *node = getNode(i);
1373     DEBUG_PRINT(std::cerr << "\n" << *node);
1374   }
1375
1376   DEBUG_PRINT(std::cerr << "\n");
1377 }
1378
1379
1380 /*
1381   dump all node property
1382 */
1383
1384 void ModuloSchedGraph::dumpNodeProperty() const
1385 {
1386
1387   unsigned numNodes = bb->size();
1388   for (unsigned i = 2; i < numNodes + 2; i++) {
1389     ModuloSchedGraphNode *node = getNode(i);
1390     DEBUG_PRINT(std::cerr << "NodeId " << node->getNodeId() << "\t");
1391     DEBUG_PRINT(std::cerr << "ASAP " << node->getASAP() << "\t");
1392     DEBUG_PRINT(std::cerr << "ALAP " << node->getALAP() << "\t");
1393     DEBUG_PRINT(std::cerr << "mov " << node->getMov() << "\t");
1394     DEBUG_PRINT(std::cerr << "depth " << node->getDepth() << "\t");
1395     DEBUG_PRINT(std::cerr << "height " << node->getHeight() << "\t\n");
1396   }
1397 }
1398
1399
1400
1401
1402 /************member functions for ModuloSchedGraphSet**************/
1403
1404 /*
1405   constructor
1406 */
1407
1408 ModuloSchedGraphSet::ModuloSchedGraphSet(const Function *function,
1409                                          const TargetMachine &target)
1410 :  method(function){
1411
1412   buildGraphsForMethod(method, target);
1413
1414 }
1415
1416 /*
1417   destructor
1418 */
1419
1420
1421 ModuloSchedGraphSet::~ModuloSchedGraphSet(){
1422
1423   //delete all the graphs
1424   for (iterator I = begin(), E = end(); I != E; ++I)
1425     delete *I;
1426 }
1427
1428
1429
1430 /*
1431   build graph for each basicblock in this method
1432 */
1433
1434 void
1435 ModuloSchedGraphSet::buildGraphsForMethod(const Function *F,
1436                                           const TargetMachine &target){
1437
1438   for (Function::const_iterator BI = F->begin(); BI != F->end(); ++BI){
1439     const BasicBlock* local_bb;
1440
1441     local_bb=BI;
1442     addGraph(new ModuloSchedGraph((BasicBlock*)local_bb, target));
1443   }
1444
1445 }
1446
1447 /*
1448   dump the graph set
1449 */
1450
1451 void
1452 ModuloSchedGraphSet::dump() const{
1453
1454   DEBUG_PRINT(std::cerr << " ====== ModuloSched graphs for function `" <<
1455               method->getName() << "' =========\n\n");
1456   for (const_iterator I = begin(); I != end(); ++I)
1457     (*I)->dump();
1458
1459   DEBUG_PRINT(std::cerr << "\n=========End graphs for function `" << method->getName()
1460               << "' ==========\n\n");
1461 }
1462
1463
1464
1465
1466 /********************misc functions***************************/
1467
1468
1469 /*
1470   dump the input basic block
1471 */
1472
1473 static void
1474 dumpBasicBlock(const BasicBlock * bb){
1475
1476   DEBUG_PRINT(std::cerr << "dumping basic block:");
1477   DEBUG_PRINT(std::cerr << (bb->hasName()? bb->getName() : "block")
1478               << " (" << bb << ")" << "\n");
1479 }
1480
1481 /*
1482   dump the input node
1483 */
1484
1485 std::ostream& operator<<(std::ostream &os,
1486                          const ModuloSchedGraphNode &node)
1487 {
1488   os << std::string(8, ' ')
1489       << "Node " << node.nodeId << " : "
1490       << "latency = " << node.latency << "\n" << std::string(12, ' ');
1491
1492   if (node.getInst() == NULL)
1493     os << "(Dummy node)\n";
1494   else {
1495     os << *node.getInst() << "\n" << std::string(12, ' ');
1496     os << node.inEdges.size() << " Incoming Edges:\n";
1497     for (unsigned i = 0, N = node.inEdges.size(); i < N; i++)
1498       os << std::string(16, ' ') << *node.inEdges[i];
1499
1500     os << std::string(12, ' ') << node.outEdges.size()
1501         << " Outgoing Edges:\n";
1502     for (unsigned i = 0, N = node.outEdges.size(); i < N; i++)
1503       os << std::string(16, ' ') << *node.outEdges[i];
1504   }
1505
1506   return os;
1507 }