+ //Return final Order
+ //return FinalNodeOrder;
+}
+
+void ModuloSchedulingPass::computeSchedule() {
+
+ bool success = false;
+
+ while(!success) {
+
+ //Loop over the final node order and process each node
+ for(std::vector<MSchedGraphNode*>::iterator I = FinalNodeOrder.begin(),
+ E = FinalNodeOrder.end(); I != E; ++I) {
+
+ //CalculateEarly and Late start
+ int EarlyStart = -1;
+ int LateStart = 99999; //Set to something higher then we would ever expect (FIXME)
+ bool hasSucc = false;
+ bool hasPred = false;
+ std::set<MSchedGraphNode*> seenNodes;
+
+ for(std::map<unsigned, std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > > >::iterator J = schedule.begin(),
+ JE = schedule.end(); J != JE; ++J) {
+
+ //For each resource with nodes scheduled, loop over the nodes and see if they
+ //are a predecessor or successor of this current node we are trying
+ //to schedule.
+ for(std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > >::iterator schedNodeVec = J->second.begin(), SNE = J->second.end(); schedNodeVec != SNE; ++schedNodeVec) {
+
+ for(std::vector<MSchedGraphNode*>::iterator schedNode = schedNodeVec->second.begin(), schedNodeEnd = schedNodeVec->second.end(); schedNode != schedNodeEnd; ++schedNode) {
+ if((*I)->isPredecessor(*schedNode) && !seenNodes.count(*schedNode)) {
+ if(!ignoreEdge(*schedNode, *I)) {
+ int diff = (*I)->getInEdge(*schedNode).getIteDiff();
+ int ES_Temp = J->first + (*schedNode)->getLatency() - diff * II;
+ DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << J->first << "\n");
+ DEBUG(std::cerr << "Temp EarlyStart: " << ES_Temp << " Prev EarlyStart: " << EarlyStart << "\n");
+ EarlyStart = std::max(EarlyStart, ES_Temp);
+ hasPred = true;
+ }
+ }
+ if((*I)->isSuccessor(*schedNode) && !seenNodes.count(*schedNode)) {
+ if(!ignoreEdge(*I,*schedNode)) {
+ int diff = (*schedNode)->getInEdge(*I).getIteDiff();
+ int LS_Temp = J->first - (*I)->getLatency() + diff * II;
+ DEBUG(std::cerr << "Diff: " << diff << " Cycle: " << J->first << "\n");
+ DEBUG(std::cerr << "Temp LateStart: " << LS_Temp << " Prev LateStart: " << LateStart << "\n");
+ LateStart = std::min(LateStart, LS_Temp);
+ hasSucc = true;
+ }
+ }
+ seenNodes.insert(*schedNode);
+ }
+ }
+ }
+ seenNodes.clear();
+
+ DEBUG(std::cerr << "Has Successors: " << hasSucc << ", Has Pred: " << hasPred << "\n");
+ DEBUG(std::cerr << "EarlyStart: " << EarlyStart << ", LateStart: " << LateStart << "\n");
+
+ //Check if the node has no pred or successors and set Early Start to its ASAP
+ if(!hasSucc && !hasPred)
+ EarlyStart = nodeToAttributesMap.find(*I)->second.ASAP;
+
+ //Now, try to schedule this node depending upon its pred and successor in the schedule
+ //already
+ if(!hasSucc && hasPred)
+ success = scheduleNode(*I, EarlyStart, (EarlyStart + II -1));
+ else if(!hasPred && hasSucc)
+ success = scheduleNode(*I, LateStart, (LateStart - II +1));
+ else if(hasPred && hasSucc)
+ success = scheduleNode(*I, EarlyStart, std::min(LateStart, (EarlyStart + II -1)));
+ else
+ success = scheduleNode(*I, EarlyStart, EarlyStart + II - 1);
+
+ if(!success) {
+ ++II;
+ schedule.clear();
+ break;
+ }
+
+ }
+ }
+}
+
+
+bool ModuloSchedulingPass::scheduleNode(MSchedGraphNode *node,
+ int start, int end) {
+ bool success = false;
+
+ DEBUG(std::cerr << *node << " (Start Cycle: " << start << ", End Cycle: " << end << ")\n");
+
+ /*std::cerr << "CURRENT SCHEDULE\n";
+ //Dump out current schedule
+ for(std::map<unsigned, std::vector<std::pair<unsigned, MSchedGraphNode*> > >::iterator J = schedule.begin(),
+ JE = schedule.end(); J != JE; ++J) {
+ std::cerr << "Cycle " << J->first << ":\n";
+ for(std::vector<std::pair<unsigned, MSchedGraphNode*> >::iterator VI = J->second.begin(), VE = J->second.end(); VI != VE; ++VI)
+ std::cerr << "Resource ID: " << VI->first << " by node " << *(VI->second) << "\n";
+ }
+ std::cerr << "END CURRENT SCHEDULE\n";
+ */
+
+ //Make sure start and end are not negative
+ if(start < 0)
+ start = 0;
+ if(end < 0)
+ end = 0;
+
+ bool forward = true;
+ if(start > end)
+ forward = false;
+
+ const TargetSchedInfo & msi = target.getSchedInfo();
+
+ bool increaseSC = true;
+
+ int cycle = start ;
+
+
+ while(increaseSC) {
+
+ increaseSC = false;
+
+ //Get the resource used by this instruction
+ //Get resource usage for this instruction
+ InstrRUsage rUsage = msi.getInstrRUsage(node->getInst()->getOpcode());
+ std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
+
+ //Loop over each resource and see if we can put it into the schedule
+ for(unsigned r=0; r < resources.size(); ++r) {
+ unsigned intermediateCycle = cycle + r;
+
+ for(unsigned j=0; j < resources[r].size(); ++j) {
+ //Put it into the schedule
+ DEBUG(std::cerr << "Attempting to put resource " << resources[r][j] << " in schedule at cycle: " << intermediateCycle << "\n");
+
+ //Check if resource is free at this cycle
+ std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > > resourceForCycle = schedule[intermediateCycle];
+
+ //Vector of nodes using this resource
+ std::vector<MSchedGraphNode*> *nodesUsingResource;
+
+ for(std::vector<std::pair<unsigned, std::vector<MSchedGraphNode*> > >::iterator I = resourceForCycle.begin(), E= resourceForCycle.end(); I != E; ++I) {
+
+ if(I->first == resources[r][j]) {
+ //Get the number of available for this resource
+ unsigned numResource = CPUResource::getCPUResource(resources[r][j])->maxNumUsers;
+ nodesUsingResource = &(I->second);
+
+ //Check that there are enough of this resource, otherwise
+ //we need to increase/decrease the cycle
+ if(I->second.size() >= numResource) {
+ DEBUG(std::cerr << "No open spot for this resource in this cycle\n");
+ increaseSC = true;
+ }
+ break;
+
+ }
+ //safe to put into schedule
+ }
+
+ if(increaseSC)
+ break;
+
+ else {
+ DEBUG(std::cerr << "Found spot in schedule\n");
+ //Add node to resource vector
+ if(nodesUsingResource == 0) {
+ nodesUsingResource = new std::vector<MSchedGraphNode*>;
+ resourceForCycle.push_back(std::make_pair(resources[r][j], *nodesUsingResource));
+ }
+
+ nodesUsingResource->push_back(node);
+
+ schedule[intermediateCycle] = resourceForCycle;
+ }
+ }
+ if(increaseSC) {
+ /*for(unsigned x = 0; x < r; ++x) {
+ unsigned removeCycle = x + start;
+ for(unsigned j=0; j < resources[x].size(); ++j) {
+ std::vector<std::pair<unsigned, MSchedGraphNode*> > resourceForCycle = schedule[removeCycle];
+ for(std::vector<std::pair<unsigned,MSchedGraphNode*> >::iterator I = resourceForCycle.begin(), E= resourceForCycle.end(); I != E; ++I) {
+ if(I->first == resources[x][j]) {
+ //remove it
+ resourceForCycle.erase(I);
+ }
+ }
+ //Put vector back
+ schedule[removeCycle] = resourceForCycle;
+ }
+ }*/
+
+ break;
+ }
+ }
+ if(!increaseSC)
+ return true;
+
+ //Increment cycle to try again
+ if(forward) {
+ ++cycle;
+ DEBUG(std::cerr << "Increase cycle: " << cycle << "\n");
+ if(cycle > end)
+ return false;
+ }
+ else {
+ --cycle;
+ DEBUG(std::cerr << "Decrease cycle: " << cycle << "\n");
+ if(cycle < end)
+ return false;
+ }
+ }
+ return success;