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 <vector>
  24 #include <utility>
  25 #include <iostream>
  26 #include <fstream>
  27 #include <sstream>
  28
  29 using namespace llvm;
  30
  31 /// Create ModuloSchedulingPass
  32 ///
  33 FunctionPass *llvm::createModuloSchedulingPass(TargetMachine & targ) {
  34   DEBUG(std::cerr << "Created ModuloSchedulingPass\n");
  35   return new ModuloSchedulingPass(targ);
  36 }
  37
  38 template<typename GraphType>
  39 static void WriteGraphToFile(std::ostream &O, const std::string &GraphName,
  40                              const GraphType &GT) {
  41   std::string Filename = GraphName + ".dot";
  42   O << "Writing '" << Filename << "'...";
  43   std::ofstream F(Filename.c_str());
  44
  45   if (F.good())
  46     WriteGraph(F, GT);
  47   else
  48     O << "  error opening file for writing!";
  49   O << "\n";
  50 };
  51
  52 namespace llvm {
  53
  54   template<>
  55   struct DOTGraphTraits<MSchedGraph*> : public DefaultDOTGraphTraits {
  56     static std::string getGraphName(MSchedGraph *F) {
  57       return "Dependence Graph";
  58     }
  59
  60     static std::string getNodeLabel(MSchedGraphNode *Node, MSchedGraph *Graph) {
  61       if (Node->getInst()) {
  62         std::stringstream ss;
  63         ss << *(Node->getInst());
  64         return ss.str(); //((MachineInstr*)Node->getInst());
  65       }
  66       else
  67         return "No Inst";
  68     }
  69     static std::string getEdgeSourceLabel(MSchedGraphNode *Node,
  70                                           MSchedGraphNode::succ_iterator I) {
  71       //Label each edge with the type of dependence
  72       std::string edgelabel = "";
  73       switch (I.getEdge().getDepOrderType()) {
  74
  75       case MSchedGraphEdge::TrueDep:
  76         edgelabel = "True";
  77         break;
  78
  79       case MSchedGraphEdge::AntiDep:
  80         edgelabel =  "Anti";
  81         break;
  82
  83       case MSchedGraphEdge::OutputDep:
  84         edgelabel = "Output";
  85         break;
  86
  87       default:
  88         edgelabel = "Unknown";
  89         break;
  90       }
  91       if(I.getEdge().getIteDiff() > 0)
  92         edgelabel += I.getEdge().getIteDiff();
  93
  94       return edgelabel;
  95   }
  96
  97
  98
  99   };
 100 }
 101
 102 /// ModuloScheduling::runOnFunction - main transformation entry point
 103 bool ModuloSchedulingPass::runOnFunction(Function &F) {
 104   bool Changed = false;
 105
 106   DEBUG(std::cerr << "Creating ModuloSchedGraph for each BasicBlock in" + F.getName() + "\n");
 107
 108   //Get MachineFunction
 109   MachineFunction &MF = MachineFunction::get(&F);
 110
 111   //Iterate over BasicBlocks and do ModuloScheduling if they are valid
 112   for (MachineFunction::const_iterator BI = MF.begin(); BI != MF.end(); ++BI) {
 113     if(MachineBBisValid(BI)) {
 114       MSchedGraph *MSG = new MSchedGraph(BI, target);
 115
 116       //Write Graph out to file
 117       DEBUG(WriteGraphToFile(std::cerr, "dependgraph", MSG));
 118
 119       //Print out BB for debugging
 120       DEBUG(BI->print(std::cerr));
 121
 122       //Calculate Resource II
 123       int ResMII = calculateResMII(BI);
 124
 125       calculateNodeAttributes(MSG, ResMII);
 126
 127     }
 128   }
 129
 130
 131   return Changed;
 132 }
 133
 134
 135 bool ModuloSchedulingPass::MachineBBisValid(const MachineBasicBlock *BI) {
 136
 137   //Valid basic blocks must be loops and can not have if/else statements or calls.
 138   bool isLoop = false;
 139
 140   //Check first if its a valid loop
 141   for(succ_const_iterator I = succ_begin(BI->getBasicBlock()),
 142         E = succ_end(BI->getBasicBlock()); I != E; ++I) {
 143     if (*I == BI->getBasicBlock())    // has single block loop
 144       isLoop = true;
 145   }
 146
 147   if(!isLoop) {
 148     DEBUG(std::cerr << "Basic Block is not a loop\n");
 149     return false;
 150   }
 151   else
 152     DEBUG(std::cerr << "Basic Block is a loop\n");
 153
 154   //Get Target machine instruction info
 155   /*const TargetInstrInfo& TMI = targ.getInstrInfo();
 156
 157   //Check each instruction and look for calls or if/else statements
 158   unsigned count = 0;
 159   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 160   //Get opcode to check instruction type
 161   MachineOpCode OC = I->getOpcode();
 162   if(TMI.isControlFlow(OC) && (count+1 < BI->size()))
 163   return false;
 164   count++;
 165   }*/
 166   return true;
 167
 168 }
 169
 170 //ResMII is calculated by determining the usage count for each resource
 171 //and using the maximum.
 172 //FIXME: In future there should be a way to get alternative resources
 173 //for each instruction
 174 int ModuloSchedulingPass::calculateResMII(const MachineBasicBlock *BI) {
 175
 176   const TargetInstrInfo & mii = target.getInstrInfo();
 177   const TargetSchedInfo & msi = target.getSchedInfo();
 178
 179   int ResMII = 0;
 180
 181   //Map to keep track of usage count of each resource
 182   std::map<unsigned, unsigned> resourceUsageCount;
 183
 184   for(MachineBasicBlock::const_iterator I = BI->begin(), E = BI->end(); I != E; ++I) {
 185
 186     //Get resource usage for this instruction
 187     InstrRUsage rUsage = msi.getInstrRUsage(I->getOpcode());
 188     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
 189
 190     //Loop over resources in each cycle and increments their usage count
 191     for(unsigned i=0; i < resources.size(); ++i)
 192       for(unsigned j=0; j < resources[i].size(); ++j) {
 193         if( resourceUsageCount.find(resources[i][j]) == resourceUsageCount.end()) {
 194           resourceUsageCount[resources[i][j]] = 1;
 195         }
 196         else {
 197           resourceUsageCount[resources[i][j]] =  resourceUsageCount[resources[i][j]] + 1;
 198         }
 199       }
 200   }
 201
 202   //Find maximum usage count
 203
 204   //Get max number of instructions that can be issued at once.
 205   int issueSlots = msi.maxNumIssueTotal;
 206
 207   for(std::map<unsigned,unsigned>::iterator RB = resourceUsageCount.begin(), RE = resourceUsageCount.end(); RB != RE; ++RB) {
 208     //Get the total number of the resources in our cpu
 209     //int resourceNum = msi.getCPUResourceNum(RB->first);
 210
 211     //Get total usage count for this resources
 212     unsigned usageCount = RB->second;
 213
 214     //Divide the usage count by either the max number we can issue or the number of
 215     //resources (whichever is its upper bound)
 216     double finalUsageCount;
 217     //if( resourceNum <= issueSlots)
 218     //finalUsageCount = ceil(1.0 * usageCount / resourceNum);
 219     //else
 220       finalUsageCount = ceil(1.0 * usageCount / issueSlots);
 221
 222
 223     DEBUG(std::cerr << "Resource ID: " << RB->first << " (usage=" << usageCount << ", resourceNum=X" << ", issueSlots=" << issueSlots << ", finalUsage=" << finalUsageCount << ")\n");
 224
 225     //Only keep track of the max
 226     ResMII = std::max( (int) finalUsageCount, ResMII);
 227
 228   }
 229
 230   DEBUG(std::cerr << "Final Resource MII: " << ResMII << "\n");
 231   return ResMII;
 232
 233 }
 234
 235 void ModuloSchedulingPass::calculateNodeAttributes(MSchedGraph *graph, int MII) {
 236
 237   //Loop over the nodes and add them to the map
 238   for(MSchedGraph::iterator I = graph->begin(), E = graph->end(); I != E; ++I) {
 239     //Assert if its already in the map
 240     assert(nodeToAttributesMap.find(I->second) == nodeToAttributesMap.end() && "Node attributes are already in the map");
 241
 242     //Put into the map with default attribute values
 243     nodeToAttributesMap[I->second] = MSNodeAttributes();
 244   }
 245
 246   //Create set to deal with reccurrences
 247   std::set<MSchedGraphNode*> visitedNodes;
 248   std::vector<MSchedGraphNode*> vNodes;
 249   //Now Loop over map and calculate the node attributes
 250   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 251     // calculateASAP(I->first, (I->second), MII, visitedNodes);
 252     findAllReccurrences(I->first, vNodes);
 253     vNodes.clear();
 254     visitedNodes.clear();
 255   }
 256
 257   //Calculate ALAP which depends on ASAP being totally calculated
 258   /*for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 259     calculateALAP(I->first, (I->second), MII, MII, visitedNodes);
 260     visitedNodes.clear();
 261   }*/
 262
 263   //Calculate MOB which depends on ASAP being totally calculated, also do depth and height
 264   /*for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(), E = nodeToAttributesMap.end(); I != E; ++I) {
 265     (I->second).MOB = (I->second).ALAP - (I->second).ASAP;
 266     DEBUG(std::cerr << "MOB: " << (I->second).MOB << " (" << *(I->first) << ")\n");
 267     calculateDepth(I->first, (I->second), visitedNodes);
 268     visitedNodes.clear();
 269     calculateHeight(I->first, (I->second), visitedNodes);
 270     visitedNodes.clear();
 271   }*/
 272
 273
 274 }
 275
 276 void ModuloSchedulingPass::calculateASAP(MSchedGraphNode *node, MSNodeAttributes &attributes,
 277                                          int MII, std::set<MSchedGraphNode*> &visitedNodes) {
 278
 279   DEBUG(std::cerr << "Calculating ASAP for " << *node << "\n");
 280
 281   if(attributes.ASAP != -1 || (visitedNodes.find(node) != visitedNodes.end())) {
 282     visitedNodes.erase(node);
 283     return;
 284   }
 285   if(node->hasPredecessors()) {
 286     int maxPredValue = 0;
 287
 288     //Iterate over all of the predecessors and fine max
 289     for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 290
 291       //Get that nodes ASAP
 292       MSNodeAttributes predAttributes = nodeToAttributesMap.find(*P)->second;
 293       if(predAttributes.ASAP == -1) {
 294         //Put into set before you recurse
 295         visitedNodes.insert(node);
 296         calculateASAP(*P, predAttributes, MII, visitedNodes);
 297         predAttributes = nodeToAttributesMap.find(*P)->second;
 298       }
 299       int iteDiff = node->getInEdge(*P).getIteDiff();
 300
 301       int currentPredValue = predAttributes.ASAP + node->getLatency() - iteDiff * MII;
 302       DEBUG(std::cerr << "Current ASAP pred: " << currentPredValue << "\n");
 303       maxPredValue = std::max(maxPredValue, currentPredValue);
 304     }
 305     visitedNodes.erase(node);
 306     attributes.ASAP = maxPredValue;
 307   }
 308   else {
 309     visitedNodes.erase(node);
 310     attributes.ASAP = 0;
 311   }
 312
 313   DEBUG(std::cerr << "ASAP: " << attributes.ASAP << " (" << *node << ")\n");
 314 }
 315
 316
 317 void ModuloSchedulingPass::calculateALAP(MSchedGraphNode *node, MSNodeAttributes &attributes,
 318                                          int MII, int maxASAP,
 319                                          std::set<MSchedGraphNode*> &visitedNodes) {
 320
 321   DEBUG(std::cerr << "Calculating AlAP for " << *node << "\n");
 322
 323   if(attributes.ALAP != -1|| (visitedNodes.find(node) != visitedNodes.end())) {
 324    visitedNodes.erase(node);
 325    return;
 326   }
 327   if(node->hasSuccessors()) {
 328     int minSuccValue = 0;
 329
 330     //Iterate over all of the predecessors and fine max
 331     for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 332           E = node->succ_end(); P != E; ++P) {
 333
 334       MSNodeAttributes succAttributes = nodeToAttributesMap.find(*P)->second;
 335       if(succAttributes.ASAP == -1) {
 336
 337         //Put into set before recursing
 338         visitedNodes.insert(node);
 339
 340         calculateALAP(*P, succAttributes, MII, maxASAP, visitedNodes);
 341         succAttributes = nodeToAttributesMap.find(*P)->second;
 342         assert(succAttributes.ASAP == -1 && "Successors ALAP should have been caclulated");
 343       }
 344       int iteDiff = P.getEdge().getIteDiff();
 345       int currentSuccValue = succAttributes.ALAP + node->getLatency() + iteDiff * MII;
 346       minSuccValue = std::min(minSuccValue, currentSuccValue);
 347     }
 348     visitedNodes.erase(node);
 349     attributes.ALAP = minSuccValue;
 350   }
 351   else {
 352     visitedNodes.erase(node);
 353     attributes.ALAP = maxASAP;
 354   }
 355   DEBUG(std::cerr << "ALAP: " << attributes.ALAP << " (" << *node << ")\n");
 356 }
 357
 358 int ModuloSchedulingPass::findMaxASAP() {
 359   int maxASAP = 0;
 360
 361   for(std::map<MSchedGraphNode*, MSNodeAttributes>::iterator I = nodeToAttributesMap.begin(),
 362         E = nodeToAttributesMap.end(); I != E; ++I)
 363     maxASAP = std::max(maxASAP, I->second.ASAP);
 364   return maxASAP;
 365 }
 366
 367
 368 void ModuloSchedulingPass::calculateHeight(MSchedGraphNode *node,
 369                                            MSNodeAttributes &attributes,
 370                                            std::set<MSchedGraphNode*> &visitedNodes) {
 371
 372   if(attributes.depth != -1 || (visitedNodes.find(node) != visitedNodes.end())) {
 373     //Remove from map before returning
 374     visitedNodes.erase(node);
 375     return;
 376   }
 377
 378   if(node->hasSuccessors()) {
 379     int maxHeight = 0;
 380
 381     //Iterate over all of the predecessors and fine max
 382     for(MSchedGraphNode::succ_iterator P = node->succ_begin(),
 383           E = node->succ_end(); P != E; ++P) {
 384
 385       MSNodeAttributes succAttributes = nodeToAttributesMap.find(*P)->second;
 386       if(succAttributes.height == -1) {
 387
 388         //Put into map before recursing
 389         visitedNodes.insert(node);
 390
 391         calculateHeight(*P, succAttributes, visitedNodes);
 392         succAttributes = nodeToAttributesMap.find(*P)->second;
 393         assert(succAttributes.height == -1 && "Successors Height should have been caclulated");
 394       }
 395       int currentHeight = succAttributes.height + node->getLatency();
 396       maxHeight = std::max(maxHeight, currentHeight);
 397     }
 398     visitedNodes.erase(node);
 399     attributes.height = maxHeight;
 400   }
 401   else {
 402     visitedNodes.erase(node);
 403     attributes.height = 0;
 404   }
 405
 406     DEBUG(std::cerr << "Height: " << attributes.height << " (" << *node << ")\n");
 407 }
 408
 409
 410 void ModuloSchedulingPass::calculateDepth(MSchedGraphNode *node,
 411                                           MSNodeAttributes &attributes,
 412                                           std::set<MSchedGraphNode*> &visitedNodes) {
 413
 414   if(attributes.depth != -1 || (visitedNodes.find(node) != visitedNodes.end())) {
 415     //Remove from map before returning
 416     visitedNodes.erase(node);
 417     return;
 418   }
 419
 420   if(node->hasPredecessors()) {
 421     int maxDepth = 0;
 422
 423     //Iterate over all of the predecessors and fine max
 424     for(MSchedGraphNode::pred_iterator P = node->pred_begin(), E = node->pred_end(); P != E; ++P) {
 425
 426       //Get that nodes depth
 427       MSNodeAttributes predAttributes = nodeToAttributesMap.find(*P)->second;
 428       if(predAttributes.depth == -1) {
 429
 430         //Put into set before recursing
 431         visitedNodes.insert(node);
 432
 433         calculateDepth(*P, predAttributes, visitedNodes);
 434         predAttributes = nodeToAttributesMap.find(*P)->second;
 435         assert(predAttributes.depth == -1 && "Predecessors ASAP should have been caclulated");
 436       }
 437       int currentDepth = predAttributes.depth + node->getLatency();
 438       maxDepth = std::max(maxDepth, currentDepth);
 439     }
 440
 441     //Remove from map before returning
 442     visitedNodes.erase(node);
 443
 444     attributes.height = maxDepth;
 445   }
 446   else {
 447     //Remove from map before returning
 448     visitedNodes.erase(node);
 449     attributes.depth = 0;
 450   }
 451
 452   DEBUG(std::cerr << "Depth: " << attributes.depth << " (" << *node << "*)\n");
 453
 454 }
 455
 456
 457 void ModuloSchedulingPass::findAllReccurrences(MSchedGraphNode *node,
 458                                                std::vector<MSchedGraphNode*> &visitedNodes) {
 459
 460   if(find(visitedNodes.begin(), visitedNodes.end(), node) != visitedNodes.end()) {
 461     //DUMP out recurrence
 462     DEBUG(std::cerr << "Reccurrence:\n");
 463     bool first = true;
 464     for(std::vector<MSchedGraphNode*>::iterator I = visitedNodes.begin(), E = visitedNodes.end();
 465         I !=E; ++I) {
 466       if(*I == node)
 467         first = false;
 468       if(first)
 469         continue;
 470       DEBUG(std::cerr << **I << "\n");
 471     }
 472      DEBUG(std::cerr << "End Reccurrence:\n");
 473     return;
 474   }
 475
 476   for(MSchedGraphNode::succ_iterator I = node->succ_begin(), E = node->succ_end(); I != E; ++I) {
 477     visitedNodes.push_back(node);
 478     findAllReccurrences(*I, visitedNodes);
 479     visitedNodes.pop_back();
 480   }
 481
 482 }
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492 void ModuloSchedulingPass::orderNodes() {
 493
 494   int BOTTOM_UP = 0;
 495   int TOP_DOWN = 1;
 496
 497   //FIXME: Group nodes into sets and order all the sets based on RecMII
 498   typedef std::vector<MSchedGraphNode*> NodeVector;
 499   typedef std::pair<int, NodeVector> NodeSet;
 500
 501   std::vector<NodeSet> NodeSetsToOrder;
 502
 503   //Order the resulting sets
 504   NodeVector FinalNodeOrder;
 505
 506   //Loop over all the sets and place them in the final node order
 507   for(unsigned i=0; i < NodeSetsToOrder.size(); ++i) {
 508
 509     //Set default order
 510     int order = BOTTOM_UP;
 511
 512     //Get Nodes in Current set
 513     NodeVector CurrentSet = NodeSetsToOrder[i].second;
 514
 515     //Loop through the predecessors for each node in the final order
 516     //and only keeps nodes both in the pred_set and currentset
 517     NodeVector IntersectCurrent;
 518
 519     //Sort CurrentSet so we can use lowerbound
 520     sort(CurrentSet.begin(), CurrentSet.end());
 521
 522     for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 523       for(MSchedGraphNode::pred_iterator P = FinalNodeOrder[j]->pred_begin(),
 524             E = FinalNodeOrder[j]->pred_end(); P != E; ++P) {
 525         if(lower_bound(CurrentSet.begin(),
 526                        CurrentSet.end(), *P) != CurrentSet.end())
 527           IntersectCurrent.push_back(*P);
 528       }
 529     }
 530
 531     //If the intersection of predecessor and current set is not empty
 532     //sort nodes bottom up
 533     if(IntersectCurrent.size() != 0)
 534       order = BOTTOM_UP;
 535
 536     //If empty, use successors
 537     else {
 538
 539       for(unsigned j=0; j < FinalNodeOrder.size(); ++j) {
 540         for(MSchedGraphNode::succ_iterator P = FinalNodeOrder[j]->succ_begin(),
 541               E = FinalNodeOrder[j]->succ_end(); P != E; ++P) {
 542           if(lower_bound(CurrentSet.begin(),
 543                          CurrentSet.end(), *P) != CurrentSet.end())
 544             IntersectCurrent.push_back(*P);
 545         }
 546       }
 547
 548       //sort top-down
 549       if(IntersectCurrent.size() != 0)
 550         order = TOP_DOWN;
 551
 552       else {
 553         //Find node with max ASAP in current Set
 554         MSchedGraphNode *node;
 555         int maxASAP = 0;
 556         for(unsigned j=0; j < CurrentSet.size(); ++j) {
 557           //Get node attributes
 558           MSNodeAttributes nodeAttr= nodeToAttributesMap.find(CurrentSet[j])->second;
 559           //assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!");
 560
 561           if(maxASAP < nodeAttr.ASAP) {
 562             maxASAP = nodeAttr.ASAP;
 563             node = CurrentSet[j];
 564           }
 565         }
 566         order = BOTTOM_UP;
 567       }
 568     }
 569
 570     //Repeat until all nodes are put into the final order from current set
 571     /*while(IntersectCurrent.size() > 0) {
 572
 573       if(order == TOP_DOWN) {
 574         while(IntersectCurrent.size() > 0) {
 575
 576           //FIXME
 577           //Get node attributes
 578           MSNodeAttributes nodeAttr= nodeToAttributesMap.find(IntersectCurrent[0])->second;
 579           assert(nodeAttr != nodeToAttributesMap.end() && "Node not in attributes map!");
 580
 581           //Get node with highest height, if a tie, use one with lowest
 582           //MOB
 583           int MOB = nodeAttr.MBO;
 584           int height = nodeAttr.height;
 585           ModuloSchedGraphNode *V = IntersectCurrent[0];
 586
 587           for(unsigned j=0; j < IntersectCurrent.size(); ++j) {
 588             int temp = IntersectCurrent[j]->getHeight();
 589             if(height < temp) {
 590               V = IntersectCurrent[j];
 591               height = temp;
 592               MOB = V->getMobility();
 593             }
 594             else if(height == temp) {
 595               if(MOB > IntersectCurrent[j]->getMobility()) {
 596                 V = IntersectCurrent[j];
 597                 height = temp;
 598                 MOB = V->getMobility();
 599               }
 600             }
 601           }
 602
 603           //Append V to the NodeOrder
 604           NodeOrder.push_back(V);
 605
 606           //Remove V from IntersectOrder
 607           IntersectCurrent.erase(find(IntersectCurrent.begin(),
 608                                       IntersectCurrent.end(), V));
 609
 610           //Intersect V's successors with CurrentSet
 611           for(mod_succ_iterator P = succ_begin(V),
 612                 E = succ_end(V); P != E; ++P) {
 613             if(lower_bound(CurrentSet.begin(),
 614                            CurrentSet.end(), *P) != CurrentSet.end()) {
 615               //If not already in Intersect, add
 616               if(find(IntersectCurrent.begin(), IntersectCurrent.end(), *P) == IntersectCurrent.end())
 617                 IntersectCurrent.push_back(*P);
 618             }
 619           }
 620         } //End while loop over Intersect Size
 621
 622         //Change direction
 623         order = BOTTOM_UP;
 624
 625         //Reset Intersect to reflect changes in OrderNodes
 626         IntersectCurrent.clear();
 627         for(unsigned j=0; j < NodeOrder.size(); ++j) {
 628           for(mod_pred_iterator P = pred_begin(NodeOrder[j]),
 629                 E = pred_end(NodeOrder[j]); P != E; ++P) {
 630             if(lower_bound(CurrentSet.begin(),
 631                            CurrentSet.end(), *P) != CurrentSet.end())
 632               IntersectCurrent.push_back(*P);
 633           }
 634         }
 635       } //End If TOP_DOWN
 636
 637         //Begin if BOTTOM_UP
 638         else {
 639           while(IntersectCurrent.size() > 0) {
 640             //Get node with highest depth, if a tie, use one with lowest
 641             //MOB
 642             int MOB = IntersectCurrent[0]->getMobility();
 643             int depth = IntersectCurrent[0]->getDepth();
 644             ModuloSchedGraphNode *V = IntersectCurrent[0];
 645
 646             for(unsigned j=0; j < IntersectCurrent.size(); ++j) {
 647               int temp = IntersectCurrent[j]->getDepth();
 648               if(depth < temp) {
 649                 V = IntersectCurrent[j];
 650                 depth = temp;
 651                 MOB = V->getMobility();
 652               }
 653               else if(depth == temp) {
 654                 if(MOB > IntersectCurrent[j]->getMobility()) {
 655                   V = IntersectCurrent[j];
 656                   depth = temp;
 657                   MOB = V->getMobility();
 658                 }
 659               }
 660             }
 661
 662             //Append V to the NodeOrder
 663             NodeOrder.push_back(V);
 664
 665             //Remove V from IntersectOrder
 666             IntersectCurrent.erase(find(IntersectCurrent.begin(),
 667                                         IntersectCurrent.end(),V));
 668
 669             //Intersect V's pred with CurrentSet
 670             for(mod_pred_iterator P = pred_begin(V),
 671                   E = pred_end(V); P != E; ++P) {
 672               if(lower_bound(CurrentSet.begin(),
 673                              CurrentSet.end(), *P) != CurrentSet.end()) {
 674                 //If not already in Intersect, add
 675                 if(find(IntersectCurrent.begin(), IntersectCurrent.end(), *P) == IntersectCurrent.end())
 676                   IntersectCurrent.push_back(*P);
 677               }
 678             }
 679           } //End while loop over Intersect Size
 680
 681           //Change order
 682           order = TOP_DOWN;
 683
 684           //Reset IntersectCurrent to reflect changes in OrderNodes
 685           IntersectCurrent.clear();
 686           for(unsigned j=0; j < NodeOrder.size(); ++j) {
 687             for(mod_succ_iterator P = succ_begin(NodeOrder[j]),
 688                   E = succ_end(NodeOrder[j]); P != E; ++P) {
 689               if(lower_bound(CurrentSet.begin(),
 690                              CurrentSet.end(), *P) != CurrentSet.end())
 691                 IntersectCurrent.push_back(*P);
 692             }
 693
 694           }
 695         } //End if BOTTOM_DOWN
 696
 697         }*/
 698 //End Wrapping while loop
 699
 700     }//End for over all sets of nodes
 701
 702     //Return final Order
 703     //return FinalNodeOrder;
 704 }