//First, check if the cycle has a spot free to start
if(schedule.find(cycle) != schedule.end()) {
+ //Check if we have a free issue slot at this cycle
if (schedule[cycle].size() < numIssue) {
+ //Now check if all the resources in their respective cycles are available
if(resourcesFree(node, cycle)) {
schedule[cycle].push_back(node);
DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n");
DEBUG(std::cerr << "All issue slots taken\n");
return true;
-
+
}
bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle) {
-
+
//Get Resource usage for this instruction
const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo();
int currentCycle = cycle;
bool success = true;
-
- //map for easy backtracking, resource num at a certain cycle
- //std::map<int, int> backtrackMap;
-
- //Get resource usage for this instruction
- InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
- std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
-
- //Loop over resources in each cycle and increments their usage count
- for(unsigned i=0; i < resources.size(); ++i) {
- for(unsigned j=0; j < resources[i].size(); ++j) {
- int resourceNum = resources[i][j];
-
- DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
-
+
+ //Get resource usage for this instruction
+ InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
+ std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
+
+ //Loop over resources in each cycle and increments their usage count
+ for(unsigned i=0; i < resources.size(); ++i) {
+ for(unsigned j=0; j < resources[i].size(); ++j) {
+
+ //Get Resource to check its availability
+ int resourceNum = resources[i][j];
+
+ DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
+
//Check if this resource is available for this cycle
std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(currentCycle);
- //First check map of resources for this cycle
+ //First check if map exists for this cycle
if(resourcesForCycle != resourceNumPerCycle.end()) {
//A map exists for this cycle, so lets check for the resource
std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
if(resourceUse != resourcesForCycle->second.end()) {
//Check if there are enough of this resource and if so, increase count and move on
- if(resourceUse->second < CPUResource::getCPUResource(resourceNum)->maxNumUsers) {
+ if(resourceUse->second < CPUResource::getCPUResource(resourceNum)->maxNumUsers)
++resourceUse->second;
- //Document that we increased the usage count for this resource at this cycle
- }
else {
+ DEBUG(std::cerr << "No resource num " << resourceNum << " available for cycle " << currentCycle << "\n");
success = false;
}
}
std::map<int, int> resourceMap;
resourceMap[resourceNum] = 1;
resourceNumPerCycle[currentCycle] = resourceMap;
-
}
if(!success)
break;
}
if(!success)
break;
- //Increase cycle
- currentCycle++;
- }
-
- if(!success) {
- int oldCycle = cycle;
- DEBUG(std::cerr << "Backtrack\n");
- //Get resource usage for this instruction
- InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
- std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
+
- //Loop over resources in each cycle and increments their usage count
- for(unsigned i=0; i < resources.size(); ++i) {
- if(oldCycle < currentCycle) {
-
- //Check if this resource is available for this cycle
- std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(oldCycle);
- if(resourcesForCycle != resourceNumPerCycle.end()) {
- for(unsigned j=0; j < resources[i].size(); ++j) {
- int resourceNum = resources[i][j];
- //remove from map
- std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
- //assert if not in the map.. since it should be!
- //assert(resourceUse != resourcesForCycle.end() && "Resource should be in map!");
- --resourceUse->second;
- }
+ //Increase cycle
+ currentCycle++;
+ }
+
+ if(!success) {
+ int oldCycle = cycle;
+ DEBUG(std::cerr << "Backtrack\n");
+ //Get resource usage for this instruction
+ InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
+ std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
+
+ //Loop over resources in each cycle and increments their usage count
+ for(unsigned i=0; i < resources.size(); ++i) {
+ if(oldCycle < currentCycle) {
+
+ //Check if this resource is available for this cycle
+ std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(oldCycle);
+ if(resourcesForCycle != resourceNumPerCycle.end()) {
+ for(unsigned j=0; j < resources[i].size(); ++j) {
+ int resourceNum = resources[i][j];
+ //remove from map
+ std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
+ //assert if not in the map.. since it should be!
+ //assert(resourceUse != resourcesForCycle.end() && "Resource should be in map!");
+ --resourceUse->second;
}
}
- else
- break;
- oldCycle++;
}
- return false;
-
+ else
+ break;
+ oldCycle++;
}
+ return false;
+
+ }
- return true;
+ return true;
}
void ModuloSchedulingPass::computePartialOrder() {
-
+
+ //Only push BA branches onto the final node order, we put other branches after it
+ //FIXME: Should we really be pushing branches on it a specific order instead of relying
+ //on BA being there?
+ std::vector<MSchedGraphNode*> otherBranch;
//Loop over all recurrences and add to our partial order
//be sure to remove nodes that are already in the partial order in
found = true;
}
if(!found) {
- new_recurrence.insert(*N);
-
+ if((*N)->isBranch()) {
+ if((*N)->getInst()->getOpcode() == V9::BA)
+ FinalNodeOrder.push_back(*N);
+ else
+ otherBranch.push_back(*N);
+ }
+ else
+ new_recurrence.insert(*N);
+ }
if(partialOrder.size() == 0)
//For each predecessors, add it to this recurrence ONLY if it is not already in it
for(MSchedGraphNode::pred_iterator P = (*N)->pred_begin(),
}
if(!predFound)
- if(!new_recurrence.count(*P))
- new_recurrence.insert(*P);
-
+ if(!new_recurrence.count(*P)) {
+ if((*P)->isBranch()) {
+ if((*P)->getInst()->getOpcode() == V9::BA)
+ FinalNodeOrder.push_back(*P);
+ else
+ otherBranch.push_back(*P);
+ }
+ else
+ new_recurrence.insert(*P);
+
+ }
}
}
- }
}
-
-
+
if(new_recurrence.size() > 0)
partialOrder.push_back(new_recurrence);
}
if(PO->count(I->first))
found = true;
}
- if(!found)
- lastNodes.insert(I->first);
+ if(!found) {
+ if(I->first->isBranch()) {
+ if(std::find(FinalNodeOrder.begin(), FinalNodeOrder.end(), I->first) == FinalNodeOrder.end())
+ if((I->first)->getInst()->getOpcode() == V9::BA)
+ FinalNodeOrder.push_back(I->first);
+ else
+ otherBranch.push_back(I->first);
+ }
+ else
+ lastNodes.insert(I->first);
+ }
}
//Break up remaining nodes that are not in the partial order
//if(lastNodes.size() > 0)
//partialOrder.push_back(lastNodes);
+ //Clean up branches by putting them in final order
+ for(std::vector<MSchedGraphNode*>::iterator I = otherBranch.begin(), E = otherBranch.end(); I != E; ++I)
+ FinalNodeOrder.push_back(*I);
+
}
void ModuloSchedulingPass::connectedComponentSet(MSchedGraphNode *node, std::set<MSchedGraphNode*> &ccSet, std::set<MSchedGraphNode*> &lastNodes) {
- //Add to final set
- if( !ccSet.count(node) && lastNodes.count(node)) {
+//Add to final set
+if( !ccSet.count(node) && lastNodes.count(node)) {
lastNodes.erase(node);
- ccSet.insert(node);
+if(node->isBranch())
+ FinalNodeOrder.push_back(node);
+ else
+ ccSet.insert(node);
}
else
return;
//Set default order
int order = BOTTOM_UP;
-
+
//Loop over all the sets and place them in the final node order
for(std::vector<std::set<MSchedGraphNode*> >::iterator CurrentSet = partialOrder.begin(), E= partialOrder.end(); CurrentSet != E; ++CurrentSet) {
int capII = 30;
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) {
LateStart = II-1;
}
else {
- EarlyStart = II-1;
- LateStart = II-1;
+ EarlyStart = II-2;
+ LateStart = 0;
assert( (EarlyStart >= 0) && (LateStart >=0) && "EarlyStart and LateStart must be greater then 0");
}
hasPred = 1;
projects / oota-llvm.git / commitdiff