lib/Target/SparcV9/ModuloScheduling/ModuloScheduling.cpp

   1 //===-- ModuloScheduling.cpp - ModuloScheduling  ----------------*- 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 //
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "ModuloSched"
  15
  16 #include "ModuloScheduling.h"
  17 #include "llvm/CodeGen/MachineFunction.h"
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/Support/CFG.h"
  20 #include "llvm/Target/TargetSchedInfo.h"
  21 #include "Support/Debug.h"
  22 #include "Support/GraphWriter.h"
  23 #include "Support/StringExtras.h"
  24 #include <vector>
  25 #include <utility>
  26 #include <iostream>
  27 #include <fstream>
  28 #include <sstream>
  29
  30
  31 using namespace llvm;
  32
  33 /// Create ModuloSchedulingPass
  34 ///
  35 FunctionPass *llvm::createModuloSchedulingPass(TargetMachine & targ) {
  36   DEBUG(std::cerr << "Created ModuloSchedulingPass\n");
  37   return new ModuloSchedulingPass(targ);
  38 }
  39
  40 template<typename GraphType>
  41 static void WriteGraphToFile(std::ostream &O, const std::string &GraphName,
  42                              const GraphType &GT) {
  43   std::string Filename = GraphName + ".dot";
  44   O << "Writing '" << Filename << "'...";
  45   std::ofstream F(Filename.c_str());
  46
  47   if (F.good())
  48     WriteGraph(F, GT);
  49   else
  50     O << "  error opening file for writing!";
  51   O << "\n";
  52 };
  53
  54 namespace llvm {
  55
  56   template<>
  57   struct DOTGraphTraits<MSchedGraph*> : public DefaultDOTGraphTraits {
  58     static std::string getGraphName(MSchedGraph *F) {
  59       return "Dependence Graph";
  60     }
  61
  62     static std::string getNodeLabel(MSchedGraphNode *Node, MSchedGraph *Graph) {
  63       if (Node->getInst()) {
  64         std::stringstream ss;
  65         ss << *(Node->getInst());
  66         return ss.str(); //((MachineInstr*)Node->getInst());
  67       }
  68       else
  69         return "No Inst";
  70     }
  71     static std::string getEdgeSourceLabel(MSchedGraphNode *Node,
  72                                           MSchedGraphNode::succ_iterator I) {
  73       //Label each edge with the type of dependence
  74       std::string edgelabel = "";
  75       switch (I.getEdge().getDepOrderType()) {
  76
  77       case MSchedGraphEdge::TrueDep:
  78         edgelabel = "True";
  79         break;
  80
  81       case MSchedGraphEdge::AntiDep:
  82         edgelabel =  "Anti";
  83         break;
  84
  85       case MSchedGraphEdge::OutputDep:
  86         edgelabel = "Output";
  87         break;
  88
  89       default:
  90         edgelabel = "Unknown";
  91         break;
  92       }
  93
  94       //FIXME
  95       int iteDiff = I.getEdge().getIteDiff();
  96       std::string intStr = "(IteDiff: ";
  97       intStr += itostr(iteDiff);
  98
  99       intStr += ")";
 100       edgelabel += intStr;
 101
 102       return edgelabel;
 103     }
 104
 105
 106
 107   };
 108 }
 109
 110 /// ModuloScheduling::runOnFunction - main transformation entry point
 111 bool ModuloSchedulingPass::runOnFunction(Function &F) {
 112   bool Changed = false;
 113
 114   DEBUG(std::cerr << "Creating ModuloSchedGraph for each BasicBlock in" + F.getName() + "\n");
 115
 116   //Get MachineFunction
 117   MachineFunction &MF = MachineFunction::get(&F);
 118
 119   //Iterate over BasicBlocks and do ModuloScheduling if they are valid
 120   for (MachineFunction::const_iterator BI = MF.begin(); BI != MF.end(); ++BI) {
 121     if(MachineBBisValid(BI)) {
 122       MSchedGraph *MSG = new MSchedGraph(BI, target);
 123
 124       //Write Graph out to file
 125       DEBUG(WriteGraphToFile(std::cerr, F.getName(), MSG));
 126
 127       //Print out BB for debugging
 128       DEBUG(BI->print(std::cerr));
 129
 130       //Calculate Resource II
 131       int ResMII = calculateResMII(BI);
 132
 133       //Calculate Recurrence II
 134       int RecMII = calculateRecMII(MSG, ResMII);
 135
 136       II = std::max(RecMII, ResMII);
 137
 138       DEBUG(std::cerr << "II starts out as " << II << "\n");
 139
 140       //Calculate Node Properties
 141       calculateNodeAttributes(MSG, ResMII);
 142
 143       //Dump node properties if in debug mode
 144       for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I =  nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I !=E; ++I) {
 145         DEBUG(std::cerr << "Node: " << *(I->first) << " ASAP: " << I->second.ASAP << " ALAP: " << I->second.ALAP << " MOB: " << I->second.MOB << " Depth: " << I->second.depth << " Height: " << I->second.height << "\n");
 146       }
 147
 148       //Put nodes in order to schedule them
 149       computePartialOrder();
 150
 151       //Dump out partial order
 152       for(std::vector<std::vector<MSchedGraphNode*> >::iterator I = partialOrder.begin(), E = partialOrder.end(); I !=E; ++I) {
 153         DEBUG(std::cerr << "Start set in PO\n");
 154         for(std::vector<MSchedGraphNode*>::iterator J = I->begin(), JE = I->end(); J != JE; ++J)
 155           DEBUG(std::cerr << "PO:" << **J << "\n");
 156       }
 157
 158       orderNodes();
 159
 160       //Dump out order of nodes
 161       for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(), E = FinalNodeOrder.end(); I != E; ++I)
 162         DEBUG(std::cerr << "FO:" << **I << "\n");
 163
 164
 165       //Finally schedule nodes
 166       computeSchedule();
 167
 168
 169       //Dump out final schedule
 170       //std::cerr << "FINALSCHEDULE\n";
 171   //Dump out current schedule
 172   /*for(std::map<unsigned, std::vector<std::pair<unsigned, MSchedGraphNode*> > >::iterator J = schedule.begin(),
 173         JE = schedule.end(); J != JE; ++J) {
 174     std::cerr << "Cycle " << J->first << ":\n";
 175     for(std::vector<std::pair<unsigned, MSchedGraphNode*> >::iterator VI = J->second.begin(), VE = J->second.end(); VI != VE; ++VI)
 176       std::cerr << "Resource ID: " << VI->first << " by node " << *(VI->second) << "\n";
 177   }
 178   std::cerr << "END FINAL SCHEDULE\n";
 179
 180       DEBUG(std::cerr << "II ends up as " << II << "\n");
 181   */
 182
 183
 184       nodeToAttributesMap.clear();
 185       partialOrder.clear();
 186       recurrenceList.clear();
 187       FinalNodeOrder.clear();
 188       schedule.clear();
 189       }
 190
 191   }
 192
 193
 194   return Changed;
 195 }
 196
 197
 198 bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) {
 199
 200   //Valid basic blocks must be loops and can not have if/else statements or calls.
 201   bool isLoop = false;
 202
 203   //Check first if its a valid loop
 204   for(succ_const_iterator I = succ_begin(BI->getBasicBlock()),
 205         E = succ_end(BI->getBasicBlock()); I != E; ++I) {
 206     if (*I == BI->getBasicBlock())    // has single block loop
 207       isLoop = true;
 208   }
 209
 210   if(!isLoop) {
 211     DEBUG(std::cerr << "Basic Block is not a loop\n");
 212     return false;
 213   }
 214   else
 215     DEBUG(std::cerr << "Basic Block is a loop\n");
 216
 217   //Get Target machine instruction info
 218   /*const TargetInstrInfo& TMI = targ.getInstrInfo();
 219
 220   //Check each instruction and look for calls or if/else statements
 221   unsigned count = 0;
 222   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 223   //Get opcode to check instruction type
 224   MachineOpCode OC = I->getOpcode();
 225   if(TMI.isControlFlow(OC) && (count+1 < BI->size()))
 226   return false;
 227   count++;
 228   }*/
 229   return true;
 230
 231 }
 232
 233 //ResMII is calculated by determining the usage count for each resource
 234 //and using the maximum.
 235 //FIXME: In future there should be a way to get alternative resources
 236 //for each instruction
 237 int ModuloSchedulingPass::calculateResMII(const MachineBasicBlock *BI) {
 238
 239   const TargetInstrInfo & mii = target.getInstrInfo();
 240   const TargetSchedInfo & msi = target.getSchedInfo();
 241
 242   int ResMII = 0;
 243
 244   //Map to keep track of usage count of each resource
 245   std::map<unsigned, unsigned> resourceUsageCount;
 246
 247   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 248
 249     //Get resource usage for this instruction
 250     InstrRUsage rUsage = msi.getInstrRUsage(I->getOpcode());
 251     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
 252
 253     //Loop over resources in each cycle and increments their usage count
 254     for(unsigned i=0; i < resources.size(); ++i)
 255       for(unsigned j=0; j < resources[i].size(); ++j) {
 256         if( resourceUsageCount.find(resources[i][j]) == resourceUsageCount.end()) {
 257           resourceUsageCount[resources[i][j]] = 1;
 258         }
 259         else {
 260           resourceUsageCount[resources[i][j]] =  resourceUsageCount[resources[i][j]] + 1;
 261         }
 262       }
 263   }
 264
 265   //Find maximum usage count
 266
 267   //Get max number of instructions that can be issued at once. (FIXME)
 268   int issueSlots = 1; // msi.maxNumIssueTotal;
 269
 270   for(std::map<unsigned,unsigned>::iterator RB = resourceUsageCount.begin(), RE = resourceUsageCount.end(); RB != RE; ++RB) {
 271     //Get the total number of the resources in our cpu
 272     //int resourceNum = msi.getCPUResourceNum(RB->first);
 273
 274     //Get total usage count for this resources
 275     unsigned usageCount = RB->second;
 276
 277     //Divide the usage count by either the max number we can issue or the number of
 278     //resources (whichever is its upper bound)
 279     double finalUsageCount;
 280     //if( resourceNum <= issueSlots)
 281     //finalUsageCount = ceil(1.0 * usageCount / resourceNum);
 282     //else
 283       finalUsageCount = ceil(1.0 * usageCount / issueSlots);
 284
 285
 286     DEBUG(std::cerr << "Resource ID: " << RB->first << " (usage=" << usageCount << ", resourceNum=X" << ", issueSlots=" << issueSlots << ", finalUsage=" << finalUsageCount << ")\n");
 287
 288     //Only keep track of the max
 289     ResMII = std::max( (int) finalUsageCount, ResMII);
 290
 291   }
 292
 293   DEBUG(std::cerr << "Final Resource MII: " << ResMII << "\n");
 294
 295   return ResMII;
 296
 297 }
 298
 299 int ModuloSchedulingPass::calculateRecMII(MSchedGraph *graph, int MII) {
 300   std::vector<MSchedGraphNode*> vNodes;
 301   //Loop over all nodes in the graph
 302   for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
 303     findAllReccurrences(I->second, vNodes, MII);
 304     vNodes.clear();
 305   }
 306
 307   int RecMII = 0;
 308
 309   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator I = recurrenceList.begin(), E=recurrenceList.end(); I !=E; ++I) {
 310     std::cerr << "Recurrence: \n";
 311     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 312       std::cerr << **N << "\n";
 313     }
 314     RecMII = std::max(RecMII, I->first);
 315     std::cerr << "End Recurrence with RecMII: " << I->first << "\n";
 316     }
 317   DEBUG(std::cerr << "RecMII: " << RecMII << "\n");
 318
 319   return MII;
 320 }
 321
 322 void ModuloSchedulingPass::calculateNodeAttributes(MSchedGraph *graph, int MII) {
 323
 324   //Loop over the nodes and add them to the map
 325   for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
 326     //Assert if its already in the map
 327     assert(nodeToAttributesMap.find(I->second) == nodeToAttributesMap.end() && "Node attributes are already in the map");
 328
 329     //Put into the map with default attribute values
 330     nodeToAttributesMap[I->second] = MSNodeAttributes();
 331   }
 332
 333   //Create set to deal with reccurrences
 334   std::set<MSchedGraphNode*> visitedNodes;
 335
 336   //Now Loop over map and calculate the node attributes
 337   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 338     calculateASAP(I->first, MII, (MSchedGraphNode*) 0);
 339     visitedNodes.clear();
 340   }
 341
 342   int maxASAP = findMaxASAP();
 343   //Calculate ALAP which depends on ASAP being totally calculated
 344   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 345     calculateALAP(I->first, MII, maxASAP, (MSchedGraphNode*) 0);
 346     visitedNodes.clear();
 347   }
 348
 349   //Calculate MOB which depends on ASAP being totally calculated, also do depth and height
 350   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 351     (I->second).MOB = std::max(0,(I->second).ALAP - (I->second).ASAP);
 352
 353     DEBUG(std::cerr << "MOB: " << (I->second).MOB << " (" << *(I->first) << ")\n");
 354     calculateDepth(I->first, (MSchedGraphNode*) 0);
 355     calculateHeight(I->first, (MSchedGraphNode*) 0);
 356   }
 357
 358
 359 }
 360
 361 bool ModuloSchedulingPass::ignoreEdge(MSchedGraphNode *srcNode, MSchedGraphNode *destNode) {
 362   if(destNode == 0 || srcNode ==0)
 363     return false;
 364
 365   bool findEdge = edgesToIgnore.count(std::make_pair(srcNode, destNode->getInEdgeNum(srcNode)));
 366   DEBUG(std::cerr << "Ignore Edge from " << *srcNode << " to " << *destNode << "? " << findEdge << "\n");
 367   return findEdge;
 368 }
 369
 370 int  ModuloSchedulingPass::calculateASAP(MSchedGraphNode *node, int MII, MSchedGraphNode *destNode) {
 371
 372   DEBUG(std::cerr << "Calculating ASAP for " << *node << "\n");
 373
 374   //Get current node attributes
 375   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 376
 377   if(attributes.ASAP != -1)
 378     return attributes.ASAP;
 379
 380   int maxPredValue = 0;
 381
 382   //Iterate over all of the predecessors and find max
 383   for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 384
 385     //Only process if we are not ignoring the edge
 386     if(!ignoreEdge(*P, node)) {
 387       int predASAP = -1;
 388       predASAP = calculateASAP(*P, MII, node);
 389
 390       assert(predASAP != -1 && "ASAP has not been calculated");
 391       int iteDiff = node->getInEdge(*P).getIteDiff();
 392
 393       int currentPredValue = predASAP + (*P)->getLatency() - (iteDiff * MII);
 394       DEBUG(std::cerr << "pred ASAP: " << predASAP << ", iteDiff: " << iteDiff << ", PredLatency: " << (*P)->getLatency() << ", Current ASAP pred: " << currentPredValue << "\n");
 395       maxPredValue = std::max(maxPredValue, currentPredValue);
 396     }
 397   }
 398
 399   attributes.ASAP = maxPredValue;
 400
 401   DEBUG(std::cerr << "ASAP: " << attributes.ASAP << " (" << *node << ")\n");
 402
 403   return maxPredValue;
 404 }
 405
 406
 407 int ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, int MII,
 408                                         int maxASAP, MSchedGraphNode *srcNode) {
 409
 410   DEBUG(std::cerr << "Calculating ALAP for " << *node << "\n");
 411
 412   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 413
 414   if(attributes.ALAP != -1)
 415     return attributes.ALAP;
 416
 417   if(node->hasSuccessors()) {
 418
 419     //Trying to deal with the issue where the node has successors, but
 420     //we are ignoring all of the edges to them. So this is my hack for
 421     //now.. there is probably a more elegant way of doing this (FIXME)
 422     bool processedOneEdge = false;
 423
 424     //FIXME, set to something high to start
 425     int minSuccValue = 9999999;
 426
 427     //Iterate over all of the predecessors and fine max
 428     for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 429           E = node->succ_end(); P != E; ++P) {
 430
 431       //Only process if we are not ignoring the edge
 432       if(!ignoreEdge(node, *P)) {
 433         processedOneEdge = true;
 434         int succALAP = -1;
 435         succALAP = calculateALAP(*P, MII, maxASAP, node);
 436
 437         assert(succALAP != -1 && "Successors ALAP should have been caclulated");
 438
 439         int iteDiff = P.getEdge().getIteDiff();
 440
 441         int currentSuccValue = succALAP - node->getLatency() + iteDiff * MII;
 442
 443         DEBUG(std::cerr << "succ ALAP: " << succALAP << ", iteDiff: " << iteDiff << ", SuccLatency: " << (*P)->getLatency() << ", Current ALAP succ: " << currentSuccValue << "\n");
 444
 445         minSuccValue = std::min(minSuccValue, currentSuccValue);
 446       }
 447     }
 448
 449     if(processedOneEdge)
 450         attributes.ALAP = minSuccValue;
 451
 452     else
 453       attributes.ALAP = maxASAP;
 454   }
 455   else
 456     attributes.ALAP = maxASAP;
 457
 458   DEBUG(std::cerr << "ALAP: " << attributes.ALAP << " (" << *node << ")\n");
 459
 460   if(attributes.ALAP < 0)
 461     attributes.ALAP = 0;
 462
 463   return attributes.ALAP;
 464 }
 465
 466 int ModuloSchedulingPass::findMaxASAP() {
 467   int maxASAP = 0;
 468
 469   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(),
 470         E = nodeToAttributesMap.end(); I != E; ++I)
 471     maxASAP = std::max(maxASAP, I->second.ASAP);
 472   return maxASAP;
 473 }
 474
 475
 476 int ModuloSchedulingPass::calculateHeight(MSchedGraphNode *node,MSchedGraphNode *srcNode) {
 477
 478   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 479
 480   if(attributes.height != -1)
 481     return attributes.height;
 482
 483   int maxHeight = 0;
 484
 485   //Iterate over all of the predecessors and find max
 486   for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 487         E = node->succ_end(); P != E; ++P) {
 488
 489
 490     if(!ignoreEdge(node, *P)) {
 491       int succHeight = calculateHeight(*P, node);
 492
 493       assert(succHeight != -1 && "Successors Height should have been caclulated");
 494
 495       int currentHeight = succHeight + node->getLatency();
 496       maxHeight = std::max(maxHeight, currentHeight);
 497     }
 498   }
 499   attributes.height = maxHeight;
 500   DEBUG(std::cerr << "Height: " << attributes.height << " (" << *node << ")\n");
 501   return maxHeight;
 502 }
 503
 504
 505 int ModuloSchedulingPass::calculateDepth(MSchedGraphNode *node,
 506                                           MSchedGraphNode *destNode) {
 507
 508   MSNodeAttributes &attributes = nodeToAttributesMap.find(node)->second;
 509
 510   if(attributes.depth != -1)
 511     return attributes.depth;
 512
 513   int maxDepth = 0;
 514
 515   //Iterate over all of the predecessors and fine max
 516   for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 517
 518     if(!ignoreEdge(*P, node)) {
 519       int predDepth = -1;
 520       predDepth = calculateDepth(*P, node);
 521
 522       assert(predDepth != -1 && "Predecessors ASAP should have been caclulated");
 523
 524       int currentDepth = predDepth + (*P)->getLatency();
 525       maxDepth = std::max(maxDepth, currentDepth);
 526     }
 527   }
 528   attributes.depth = maxDepth;
 529
 530   DEBUG(std::cerr << "Depth: " << attributes.depth << " (" << *node << "*)\n");
 531   return maxDepth;
 532 }
 533
 534
 535
 536 void ModuloSchedulingPass::addReccurrence(std::vector<MSchedGraphNode*> &recurrence, int II, MSchedGraphNode *srcBENode, MSchedGraphNode *destBENode) {
 537   //Check to make sure that this recurrence is unique
 538   bool same = false;
 539
 540
 541   //Loop over all recurrences already in our list
 542   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::iterator R = recurrenceList.begin(), RE = recurrenceList.end(); R != RE; ++R) {
 543
 544     bool all_same = true;
 545      //First compare size
 546     if(R->second.size() == recurrence.size()) {
 547
 548       for(std::vector<MSchedGraphNode*>::const_iterator node = R->second.begin(), end = R->second.end(); node != end; ++node) {
 549         if(find(recurrence.begin(), recurrence.end(), *node) == recurrence.end()) {
 550           all_same = all_same && false;
 551           break;
 552         }
 553         else
 554           all_same = all_same && true;
 555       }
 556       if(all_same) {
 557         same = true;
 558         break;
 559       }
 560     }
 561   }
 562
 563   if(!same) {
 564     //if(srcBENode == 0 || destBENode == 0) {
 565       srcBENode = recurrence.back();
 566       destBENode = recurrence.front();
 567       //}
 568     DEBUG(std::cerr << "Back Edge to Remove: " << *srcBENode << " to " << *destBENode << "\n");
 569     edgesToIgnore.insert(std::make_pair(srcBENode, destBENode->getInEdgeNum(srcBENode)));
 570     recurrenceList.insert(std::make_pair(II, recurrence));
 571   }
 572
 573 }
 574
 575 void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node,
 576                                                std::vector<MSchedGraphNode*> &visitedNodes,
 577                                                int II) {
 578
 579   if(find(visitedNodes.begin(), visitedNodes.end(), node) != visitedNodes.end()) {
 580     std::vector<MSchedGraphNode*> recurrence;
 581     bool first = true;
 582     int delay = 0;
 583     int distance = 0;
 584     int RecMII = II; //Starting value
 585     MSchedGraphNode *last = node;
 586     MSchedGraphNode *srcBackEdge;
 587     MSchedGraphNode *destBackEdge;
 588
 589
 590
 591     for(std::vector<MSchedGraphNode*>::iterator I = visitedNodes.begin(), E = visitedNodes.end();
 592         I !=E; ++I) {
 593
 594       if(*I == node)
 595         first = false;
 596       if(first)
 597         continue;
 598
 599       delay = delay + (*I)->getLatency();
 600
 601       if(*I != node) {
 602         int diff = (*I)->getInEdge(last).getIteDiff();
 603         distance += diff;
 604         if(diff > 0) {
 605           srcBackEdge = last;
 606           destBackEdge = *I;
 607         }
 608       }
 609
 610       recurrence.push_back(*I);
 611       last = *I;
 612     }
 613
 614
 615
 616     //Get final distance calc
 617     distance += node->getInEdge(last).getIteDiff();
 618
 619
 620     //Adjust II until we get close to the inequality delay - II*distance <= 0
 621
 622     int value = delay-(RecMII * distance);
 623     int lastII = II;
 624     while(value <= 0) {
 625
 626       lastII = RecMII;
 627       RecMII--;
 628       value = delay-(RecMII * distance);
 629     }
 630
 631
 632     DEBUG(std::cerr << "Final II for this recurrence: " << lastII << "\n");
 633     addReccurrence(recurrence, lastII, srcBackEdge, destBackEdge);
 634     assert(distance != 0 && "Recurrence distance should not be zero");
 635     return;
 636   }
 637
 638   for(MSchedGraphNode::succ_iterator I = node->succ_begin(), E = node->succ_end(); I != E; ++I) {
 639     visitedNodes.push_back(node);
 640     findAllReccurrences(*I, visitedNodes, II);
 641     visitedNodes.pop_back();
 642   }
 643 }
 644
 645
 646
 647
 648
 649 void ModuloSchedulingPass::computePartialOrder() {
 650
 651
 652   //Loop over all recurrences and add to our partial order
 653   //be sure to remove nodes that are already in the partial order in
 654   //a different recurrence and don't add empty recurrences.
 655   for(std::set<std::pair<int, std::vector<MSchedGraphNode*> > >::reverse_iterator I = recurrenceList.rbegin(), E=recurrenceList.rend(); I !=E; ++I) {
 656
 657     //Add nodes that connect this recurrence to the previous recurrence
 658
 659     //If this is the first recurrence in the partial order, add all predecessors
 660     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 661
 662     }
 663
 664
 665     std::vector<MSchedGraphNode*> new_recurrence;
 666     //Loop through recurrence and remove any nodes already in the partial order
 667     for(std::vector<MSchedGraphNode*>::const_iterator N = I->second.begin(), NE = I->second.end(); N != NE; ++N) {
 668       bool found = false;
 669       for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
 670         if(find(PO->begin(), PO->end(), *N) != PO->end())
 671           found = true;
 672       }
 673       if(!found) {
 674         new_recurrence.push_back(*N);
 675
 676         if(partialOrder.size() == 0)
 677           //For each predecessors, add it to this recurrence ONLY if it is not already in it
 678           for(MSchedGraphNode::pred_iterator P = (*N)->pred_begin(),
 679                 PE = (*N)->pred_end(); P != PE; ++P) {
 680
 681             //Check if we are supposed to ignore this edge or not
 682             if(!ignoreEdge(*P, *N))
 683               //Check if already in this recurrence
 684               if(find(I->second.begin(), I->second.end(), *P) == I->second.end()) {
 685                 //Also need to check if in partial order
 686                 bool predFound = false;
 687                 for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PEND = partialOrder.end(); PO != PEND; ++PO) {
 688                   if(find(PO->begin(), PO->end(), *P) != PO->end())
 689                     predFound = true;
 690                 }
 691
 692                 if(!predFound)
 693                   if(find(new_recurrence.begin(), new_recurrence.end(), *P) == new_recurrence.end())
 694                      new_recurrence.push_back(*P);
 695
 696               }
 697           }
 698       }
 699     }
 700
 701
 702     if(new_recurrence.size() > 0)
 703       partialOrder.push_back(new_recurrence);
 704   }
 705
 706   //Add any nodes that are not already in the partial order
 707   std::vector<MSchedGraphNode*> lastNodes;
 708   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 709     bool found = false;
 710     //Check if its already in our partial order, if not add it to the final vector
 711     for(std::vector<std::vector<MSchedGraphNode*> >::iterator PO = partialOrder.begin(), PE = partialOrder.end(); PO != PE; ++PO) {
 712       if(find(PO->begin(), PO->end(), I->first) != PO->end())
 713         found = true;
 714     }
 715     if(!found)
 716       lastNodes.push_back(I->first);
 717   }
 718
 719   if(lastNodes.size() > 0)
 720     partialOrder.push_back(lastNodes);
 721
 722 }
 723
 724
 725 void ModuloSchedulingPass::predIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
 726
 727   //Sort CurrentSet so we can use lowerbound
 728   sort(CurrentSet.begin(), CurrentSet.end());
 729
 730   for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 731     for(MSchedGraphNode::pred_iterator P = FinalNodeOrder[j]->pred_begin(),
 732           E = FinalNodeOrder[j]->pred_end(); P != E; ++P) {
 733
 734       //Check if we are supposed to ignore this edge or not
 735       if(ignoreEdge(*P,FinalNodeOrder[j]))
 736         continue;
 737
 738       if(find(CurrentSet.begin(),
 739                      CurrentSet.end(), *P) != CurrentSet.end())
 740         if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
 741           IntersectResult.push_back(*P);
 742     }
 743   }
 744 }
 745
 746 void ModuloSchedulingPass::succIntersect(std::vector<MSchedGraphNode*> &CurrentSet, std::vector<MSchedGraphNode*> &IntersectResult) {
 747
 748   //Sort CurrentSet so we can use lowerbound
 749   sort(CurrentSet.begin(), CurrentSet.end());
 750
 751   for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 752     for(MSchedGraphNode::succ_iterator P = FinalNodeOrder[j]->succ_begin(),
 753           E = FinalNodeOrder[j]->succ_end(); P != E; ++P) {
 754
 755       //Check if we are supposed to ignore this edge or not
 756       if(ignoreEdge(FinalNodeOrder[j],*P))
 757         continue;
 758
 759       if(find(CurrentSet.begin(),
 760                      CurrentSet.end(), *P) != CurrentSet.end())
 761         if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), *P) == FinalNodeOrder.end())
 762           IntersectResult.push_back(*P);
 763     }
 764   }
 765 }
 766
 767 void dumpIntersection(std::vector<MSchedGraphNode*> &IntersectCurrent) {
 768   std::cerr << "Intersection (";
 769   for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(), E = IntersectCurrent.end(); I != E; ++I)
 770     std::cerr << **I << ", ";
 771   std::cerr << ")\n";
 772 }
 773
 774
 775
 776 void ModuloSchedulingPass::orderNodes() {
 777
 778   int BOTTOM_UP = 0;
 779   int TOP_DOWN = 1;
 780
 781   //Set default order
 782   int order = BOTTOM_UP;
 783
 784
 785   //Loop over all the sets and place them in the final node order
 786   for(std::vector<std::vector<MSchedGraphNode*> >::iterator CurrentSet = partialOrder.begin(), E= partialOrder.end(); CurrentSet != E; ++CurrentSet) {
 787
 788     DEBUG(std::cerr << "Processing set in S\n");
 789     dumpIntersection(*CurrentSet);
 790     //Result of intersection
 791     std::vector<MSchedGraphNode*> IntersectCurrent;
 792
 793     predIntersect(*CurrentSet, IntersectCurrent);
 794
 795     //If the intersection of predecessor and current set is not empty
 796     //sort nodes bottom up
 797     if(IntersectCurrent.size() != 0) {
 798       DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is NOT empty\n");
 799       order = BOTTOM_UP;
 800     }
 801     //If empty, use successors
 802     else {
 803       DEBUG(std::cerr << "Final Node Order Predecessors and Current Set interesection is empty\n");
 804
 805       succIntersect(*CurrentSet, IntersectCurrent);
 806
 807       //sort top-down
 808       if(IntersectCurrent.size() != 0) {
 809          DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is NOT empty\n");
 810         order = TOP_DOWN;
 811       }
 812       else {
 813         DEBUG(std::cerr << "Final Node Order Successors and Current Set interesection is empty\n");
 814         //Find node with max ASAP in current Set
 815         MSchedGraphNode *node;
 816         int maxASAP = 0;
 817         DEBUG(std::cerr << "Using current set of size " << CurrentSet->size() << "to find max ASAP\n");
 818         for(unsigned j=0; j < CurrentSet->size(); ++j) {
 819           //Get node attributes
 820           MSNodeAttributes nodeAttr= nodeToAttributesMap.find((*CurrentSet)[j])->second;
 821           //assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!");
 822           DEBUG(std::cerr << "CurrentSet index " << j << "has ASAP: " << nodeAttr.ASAP << "\n");
 823           if(maxASAP < nodeAttr.ASAP) {
 824             maxASAP = nodeAttr.ASAP;
 825             node = (*CurrentSet)[j];
 826           }
 827         }
 828         assert(node != 0 && "In node ordering node should not be null");
 829         IntersectCurrent.push_back(node);
 830         order = BOTTOM_UP;
 831       }
 832     }
 833
 834     //Repeat until all nodes are put into the final order from current set
 835     while(IntersectCurrent.size() > 0) {
 836
 837       if(order == TOP_DOWN) {
 838         DEBUG(std::cerr << "Order is TOP DOWN\n");
 839
 840         while(IntersectCurrent.size() > 0) {
 841           DEBUG(std::cerr << "Intersection is not empty, so find heighest height\n");
 842
 843           int MOB = 0;
 844           int height = 0;
 845           MSchedGraphNode *highestHeightNode = IntersectCurrent[0];
 846
 847           //Find node in intersection with highest heigh and lowest MOB
 848           for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
 849                 E = IntersectCurrent.end(); I != E; ++I) {
 850
 851             //Get current nodes properties
 852             MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
 853
 854             if(height < nodeAttr.height) {
 855               highestHeightNode = *I;
 856               height = nodeAttr.height;
 857               MOB = nodeAttr.MOB;
 858             }
 859             else if(height ==  nodeAttr.height) {
 860               if(MOB > nodeAttr.height) {
 861                 highestHeightNode = *I;
 862                 height =  nodeAttr.height;
 863                 MOB = nodeAttr.MOB;
 864               }
 865             }
 866           }
 867
 868           //Append our node with greatest height to the NodeOrder
 869           if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestHeightNode) == FinalNodeOrder.end()) {
 870             DEBUG(std::cerr << "Adding node to Final Order: " << *highestHeightNode << "\n");
 871             FinalNodeOrder.push_back(highestHeightNode);
 872           }
 873
 874           //Remove V from IntersectOrder
 875           IntersectCurrent.erase(find(IntersectCurrent.begin(),
 876                                       IntersectCurrent.end(), highestHeightNode));
 877
 878
 879           //Intersect V's successors with CurrentSet
 880           for(MSchedGraphNode::succ_iterator P = highestHeightNode->succ_begin(),
 881                 E = highestHeightNode->succ_end(); P != E; ++P) {
 882             //if(lower_bound(CurrentSet->begin(),
 883             //     CurrentSet->end(), *P) != CurrentSet->end()) {
 884             if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
 885               if(ignoreEdge(highestHeightNode, *P))
 886                 continue;
 887               //If not already in Intersect, add
 888               if(find(IntersectCurrent.begin(), IntersectCurrent.end(), *P) == IntersectCurrent.end())
 889                 IntersectCurrent.push_back(*P);
 890             }
 891           }
 892         } //End while loop over Intersect Size
 893
 894         //Change direction
 895         order = BOTTOM_UP;
 896
 897         //Reset Intersect to reflect changes in OrderNodes
 898         IntersectCurrent.clear();
 899         predIntersect(*CurrentSet, IntersectCurrent);
 900
 901       } //End If TOP_DOWN
 902
 903         //Begin if BOTTOM_UP
 904       else {
 905         DEBUG(std::cerr << "Order is BOTTOM UP\n");
 906         while(IntersectCurrent.size() > 0) {
 907           DEBUG(std::cerr << "Intersection of size " << IntersectCurrent.size() << ", finding highest depth\n");
 908
 909           //dump intersection
 910           DEBUG(dumpIntersection(IntersectCurrent));
 911           //Get node with highest depth, if a tie, use one with lowest
 912           //MOB
 913           int MOB = 0;
 914           int depth = 0;
 915           MSchedGraphNode *highestDepthNode = IntersectCurrent[0];
 916
 917           for(std::vector<MSchedGraphNode*>::iterator I = IntersectCurrent.begin(),
 918                 E = IntersectCurrent.end(); I != E; ++I) {
 919             //Find node attribute in graph
 920             MSNodeAttributes nodeAttr= nodeToAttributesMap.find(*I)->second;
 921
 922             if(depth < nodeAttr.depth) {
 923               highestDepthNode = *I;
 924               depth = nodeAttr.depth;
 925               MOB = nodeAttr.MOB;
 926             }
 927             else if(depth == nodeAttr.depth) {
 928               if(MOB > nodeAttr.MOB) {
 929                 highestDepthNode = *I;
 930                 depth = nodeAttr.depth;
 931                 MOB = nodeAttr.MOB;
 932               }
 933             }
 934           }
 935
 936
 937
 938           //Append highest depth node to the NodeOrder
 939            if(find(FinalNodeOrder.begin(), FinalNodeOrder.end(), highestDepthNode) == FinalNodeOrder.end()) {
 940              DEBUG(std::cerr << "Adding node to Final Order: " << *highestDepthNode << "\n");
 941              FinalNodeOrder.push_back(highestDepthNode);
 942            }
 943           //Remove heightestDepthNode from IntersectOrder
 944           IntersectCurrent.erase(find(IntersectCurrent.begin(),
 945                                       IntersectCurrent.end(),highestDepthNode));
 946
 947
 948           //Intersect heightDepthNode's pred with CurrentSet
 949           for(MSchedGraphNode::pred_iterator P = highestDepthNode->pred_begin(),
 950                 E = highestDepthNode->pred_end(); P != E; ++P) {
 951             //if(lower_bound(CurrentSet->begin(),
 952             //     CurrentSet->end(), *P) != CurrentSet->end()) {
 953             if(find(CurrentSet->begin(), CurrentSet->end(), *P) != CurrentSet->end()) {
 954
 955               if(ignoreEdge(*P, highestDepthNode))
 956                 continue;
 957
 958             //If not already in Intersect, add
 959             if(find(IntersectCurrent.begin(),
 960                       IntersectCurrent.end(), *P) == IntersectCurrent.end())
 961                 IntersectCurrent.push_back(*P);
 962             }
 963           }
 964
 965         } //End while loop over Intersect Size
 966
 967           //Change order
 968         order = TOP_DOWN;
 969
 970         //Reset IntersectCurrent to reflect changes in OrderNodes
 971         IntersectCurrent.clear();
 972         succIntersect(*CurrentSet, IntersectCurrent);
 973         } //End if BOTTOM_DOWN
 974
 975     }
 976     //End Wrapping while loop
 977
 978   }//End for over all sets of nodes
 979
 980   //Return final Order
 981   //return FinalNodeOrder;
 982 }
 983
 984 void ModuloSchedulingPass::computeSchedule() {
 985
 986   bool success = false;
 987
 988   while(!success) {
 989
 990     //Loop over the final node order and process each node
 991     for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(),
 992           E = FinalNodeOrder.end(); I != E; ++I) {
 993
 994       //CalculateEarly and Late start
 995       int EarlyStart = -1;
 996       int LateStart = 99999; //Set to something higher then we would ever expect (FIXME)
 997       bool hasSucc = false;
 998       bool hasPred = false;
 999       std::set<MSchedGraphNode*> seenNodes;
1000
1001       for(std::map<unsigned, std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > > >::iterator J = schedule.begin(),
1002             JE = schedule.end(); J != JE; ++J) {
1003
1004         //For each resource with nodes scheduled, loop over the nodes and see if they
1005         //are a predecessor or successor of this current node we are trying
1006         //to schedule.
1007         for(std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > >::iterator schedNodeVec = J->second.begin(), SNE = J->second.end(); schedNodeVec != SNE; ++schedNodeVec) {
1008
1009           for(std::vector<MSchedGraphNode*>::iterator schedNode = schedNodeVec->second.begin(), schedNodeEnd = schedNodeVec->second.end(); schedNode != schedNodeEnd; ++schedNode) {
1010             if((*I)->isPredecessor(*schedNode) && !seenNodes.count(*schedNode)) {
1011               if(!ignoreEdge(*schedNode, *I)) {
1012                 int diff = (*I)->getInEdge(*schedNode).getIteDiff();
1013                 int ES_Temp = J->first + (*schedNode)->getLatency() - diff * II;
1014                 DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << J->first << "\n");
1015                 DEBUG(std::cerr << "Temp EarlyStart: " << ES_Temp << " Prev EarlyStart: " << EarlyStart << "\n");
1016                 EarlyStart = std::max(EarlyStart, ES_Temp);
1017                 hasPred = true;
1018               }
1019             }
1020             if((*I)->isSuccessor(*schedNode) && !seenNodes.count(*schedNode)) {
1021               if(!ignoreEdge(*I,*schedNode)) {
1022                 int diff = (*schedNode)->getInEdge(*I).getIteDiff();
1023                 int LS_Temp = J->first - (*I)->getLatency() + diff * II;
1024                 DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << J->first << "\n");
1025                 DEBUG(std::cerr << "Temp LateStart: " << LS_Temp << " Prev LateStart: " << LateStart << "\n");
1026                 LateStart = std::min(LateStart, LS_Temp);
1027                 hasSucc = true;
1028               }
1029             }
1030             seenNodes.insert(*schedNode);
1031           }
1032         }
1033       }
1034       seenNodes.clear();
1035
1036       DEBUG(std::cerr << "Has Successors: " << hasSucc << ", Has Pred: " << hasPred << "\n");
1037       DEBUG(std::cerr << "EarlyStart: " << EarlyStart << ", LateStart: " << LateStart << "\n");
1038
1039       //Check if the node has no pred or successors and set Early Start to its ASAP
1040       if(!hasSucc && !hasPred)
1041         EarlyStart = nodeToAttributesMap.find(*I)->second.ASAP;
1042
1043       //Now, try to schedule this node depending upon its pred and successor in the schedule
1044       //already
1045       if(!hasSucc && hasPred)
1046         success = scheduleNode(*I, EarlyStart, (EarlyStart + II -1));
1047       else if(!hasPred && hasSucc)
1048         success = scheduleNode(*I, LateStart, (LateStart - II +1));
1049       else if(hasPred && hasSucc)
1050         success = scheduleNode(*I, EarlyStart, std::min(LateStart, (EarlyStart + II -1)));
1051       else
1052         success = scheduleNode(*I, EarlyStart, EarlyStart + II - 1);
1053
1054       if(!success) {
1055         ++II;
1056         schedule.clear();
1057         break;
1058       }
1059
1060     }
1061   }
1062 }
1063
1064
1065 bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node,
1066                                       int start, int end) {
1067   bool success = false;
1068
1069   DEBUG(std::cerr << *node << " (Start Cycle: " << start << ", End Cycle: " << end << ")\n");
1070
1071   /*std::cerr << "CURRENT SCHEDULE\n";
1072   //Dump out current schedule
1073   for(std::map<unsigned, std::vector<std::pair<unsigned, MSchedGraphNode*> > >::iterator J = schedule.begin(),
1074         JE = schedule.end(); J != JE; ++J) {
1075     std::cerr << "Cycle " << J->first << ":\n";
1076     for(std::vector<std::pair<unsigned, MSchedGraphNode*> >::iterator VI = J->second.begin(), VE = J->second.end(); VI != VE; ++VI)
1077       std::cerr << "Resource ID: " << VI->first << " by node " << *(VI->second) << "\n";
1078   }
1079   std::cerr << "END CURRENT SCHEDULE\n";
1080   */
1081
1082   //Make sure start and end are not negative
1083   if(start < 0)
1084     start = 0;
1085   if(end < 0)
1086     end = 0;
1087
1088   bool forward = true;
1089   if(start > end)
1090     forward = false;
1091
1092   const TargetSchedInfo & msi = target.getSchedInfo();
1093
1094   bool increaseSC = true;
1095
1096   int cycle = start ;
1097
1098
1099   while(increaseSC) {
1100
1101     increaseSC = false;
1102
1103     //Get the resource used by this instruction
1104     //Get resource usage for this instruction
1105     InstrRUsage rUsage = msi.getInstrRUsage(node->getInst()->getOpcode());
1106     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
1107
1108     //Loop over each resource and see if we can put it into the schedule
1109     for(unsigned r=0; r < resources.size(); ++r) {
1110       unsigned intermediateCycle = cycle + r;
1111
1112       for(unsigned j=0; j < resources[r].size(); ++j) {
1113         //Put it into the schedule
1114         DEBUG(std::cerr << "Attempting to put resource " << resources[r][j] << " in schedule at cycle: " << intermediateCycle << "\n");
1115
1116         //Check if resource is free at this cycle
1117         std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > > resourceForCycle = schedule[intermediateCycle];
1118
1119         //Vector of nodes using this resource
1120         std::vector<MSchedGraphNode*> *nodesUsingResource;
1121
1122         for(std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > >::iterator I = resourceForCycle.begin(), E= resourceForCycle.end(); I != E; ++I) {
1123
1124           if(I->first == resources[r][j]) {
1125             //Get the number of available for this resource
1126             unsigned numResource = CPUResource::getCPUResource(resources[r][j])->maxNumUsers;
1127             nodesUsingResource = &(I->second);
1128
1129             //Check that there are enough of this resource, otherwise
1130             //we need to increase/decrease the cycle
1131             if(I->second.size() >= numResource) {
1132               DEBUG(std::cerr << "No open spot for this resource in this cycle\n");
1133               increaseSC = true;
1134             }
1135             break;
1136
1137           }
1138           //safe to put into schedule
1139         }
1140
1141         if(increaseSC)
1142           break;
1143
1144         else {
1145           DEBUG(std::cerr << "Found spot in schedule\n");
1146           //Add node to resource vector
1147           if(nodesUsingResource == 0) {
1148             nodesUsingResource = new std::vector<MSchedGraphNode*>;
1149             resourceForCycle.push_back(std::make_pair(resources[r][j], *nodesUsingResource));
1150           }
1151
1152           nodesUsingResource->push_back(node);
1153
1154           schedule[intermediateCycle] = resourceForCycle;
1155         }
1156       }
1157       if(increaseSC) {
1158         /*for(unsigned x = 0; x < r; ++x) {
1159           unsigned removeCycle = x + start;
1160           for(unsigned j=0; j < resources[x].size(); ++j) {
1161             std::vector<std::pair<unsigned, MSchedGraphNode*> > resourceForCycle = schedule[removeCycle];
1162             for(std::vector<std::pair<unsigned,MSchedGraphNode*> >::iterator I = resourceForCycle.begin(), E= resourceForCycle.end(); I != E; ++I) {
1163               if(I->first == resources[x][j]) {
1164                 //remove it
1165                 resourceForCycle.erase(I);
1166               }
1167             }
1168             //Put vector back
1169             schedule[removeCycle] = resourceForCycle;
1170           }
1171           }*/
1172
1173         break;
1174       }
1175     }
1176     if(!increaseSC)
1177       return true;
1178
1179     //Increment cycle to try again
1180     if(forward) {
1181       ++cycle;
1182       DEBUG(std::cerr << "Increase cycle: " << cycle << "\n");
1183       if(cycle > end)
1184         return false;
1185     }
1186     else {
1187       --cycle;
1188       DEBUG(std::cerr << "Decrease cycle: " << cycle << "\n");
1189       if(cycle < end)
1190         return false;
1191     }
1192   }
1193   return success;
1194 }