LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

MSSchedule.cpp

Go to the documentation of this file.
00001 //===-- MSSchedule.cpp Schedule ---------------------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // 
00011 //
00012 //===----------------------------------------------------------------------===//
00013 #define DEBUG_TYPE "ModuloSched"
00014 
00015 #include "MSSchedule.h"
00016 #include "llvm/Support/Debug.h"
00017 #include "llvm/Target/TargetSchedInfo.h"
00018 #include "../SparcV9Internals.h"
00019 
00020 using namespace llvm;
00021 
00022 bool MSSchedule::insert(MSchedGraphNode *node, int cycle) {
00023   
00024   //First, check if the cycle has a spot free to start
00025   if(schedule.find(cycle) != schedule.end()) {
00026     //Check if we have a free issue slot at this cycle
00027     if (schedule[cycle].size() < numIssue) {
00028       //Now check if all the resources in their respective cycles are available
00029       if(resourcesFree(node, cycle)) {
00030   //Insert to preserve dependencies
00031   addToSchedule(cycle,node);
00032   DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n");
00033   return false;
00034       }
00035     }
00036   }
00037   //Not in the map yet so put it in
00038   else {
00039     if(resourcesFree(node,cycle)) {
00040       std::vector<MSchedGraphNode*> nodes;
00041       nodes.push_back(node);
00042       schedule[cycle] = nodes;
00043       DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n");
00044       return false;
00045     }
00046   }
00047 
00048   DEBUG(std::cerr << "All issue slots taken\n");
00049   return true;
00050   
00051 }
00052 
00053 void MSSchedule::addToSchedule(int cycle, MSchedGraphNode *node) {
00054   std::vector<MSchedGraphNode*> nodesAtCycle = schedule[cycle];
00055 
00056   std::map<unsigned, MSchedGraphNode*> indexMap;
00057   for(unsigned i=0; i < nodesAtCycle.size(); ++i) {
00058     indexMap[nodesAtCycle[i]->getIndex()] = nodesAtCycle[i];
00059   }
00060 
00061   indexMap[node->getIndex()] = node;
00062 
00063   std::vector<MSchedGraphNode*> nodes;
00064   for(std::map<unsigned, MSchedGraphNode*>::iterator I = indexMap.begin(), E = indexMap.end(); I != E; ++I)
00065     nodes.push_back(I->second);
00066   
00067   schedule[cycle] =  nodes;
00068 }
00069 
00070 
00071 bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle) {
00072   
00073   //Get Resource usage for this instruction
00074   const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo();
00075   int currentCycle = cycle;
00076   bool success = true;
00077   
00078   //Get resource usage for this instruction
00079   InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
00080   std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
00081   
00082   //Loop over resources in each cycle and increments their usage count
00083   for(unsigned i=0; i < resources.size(); ++i) {
00084     for(unsigned j=0; j < resources[i].size(); ++j) {
00085       
00086       //Get Resource to check its availability
00087       int resourceNum = resources[i][j];
00088       
00089       DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n");
00090       
00091   //Check if this resource is available for this cycle
00092   std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(currentCycle);
00093 
00094   //First check if map exists for this cycle
00095   if(resourcesForCycle != resourceNumPerCycle.end()) {
00096     //A map exists for this cycle, so lets check for the resource
00097     std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
00098     if(resourceUse != resourcesForCycle->second.end()) {
00099       //Check if there are enough of this resource and if so, increase count and move on
00100       if(resourceUse->second < CPUResource::getCPUResource(resourceNum)->maxNumUsers)
00101         ++resourceUse->second;
00102       
00103       else {
00104         DEBUG(std::cerr << "No resource num " << resourceNum << " available for cycle " << currentCycle << "\n");
00105         success = false;
00106       }
00107     }
00108     //Not in the map yet, so put it
00109     else
00110       resourcesForCycle->second[resourceNum] = 1;
00111   
00112   }
00113   else {
00114     //Create a new map and put in our resource
00115     std::map<int, int> resourceMap;
00116     resourceMap[resourceNum] = 1;
00117     resourceNumPerCycle[currentCycle] = resourceMap;
00118   }
00119   if(!success)
00120     break;
00121       }
00122       if(!success)
00123   break;
00124   
00125       
00126       //Increase cycle
00127       currentCycle++;
00128   }
00129   
00130   if(!success) {
00131     int oldCycle = cycle;
00132     DEBUG(std::cerr << "Backtrack\n");
00133     //Get resource usage for this instruction
00134     InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode());
00135     std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle;
00136     
00137     //Loop over resources in each cycle and increments their usage count
00138     for(unsigned i=0; i < resources.size(); ++i) {
00139       if(oldCycle < currentCycle) {
00140   
00141   //Check if this resource is available for this cycle
00142   std::map<int, std::map<int,int> >::iterator resourcesForCycle = resourceNumPerCycle.find(oldCycle);
00143   if(resourcesForCycle != resourceNumPerCycle.end()) {
00144     for(unsigned j=0; j < resources[i].size(); ++j) {
00145       int resourceNum = resources[i][j];
00146       //remove from map
00147       std::map<int, int>::iterator resourceUse = resourcesForCycle->second.find(resourceNum);
00148       //assert if not in the map.. since it should be!
00149       //assert(resourceUse != resourcesForCycle.end() && "Resource should be in map!");
00150       --resourceUse->second;
00151     }
00152   }
00153       }
00154       else
00155   break;
00156       oldCycle++;
00157     }
00158     return false;
00159     
00160   }
00161 
00162   return true;
00163 
00164 }
00165 
00166 bool MSSchedule::constructKernel(int II) {
00167  
00168   int stageNum = (schedule.rbegin()->first)/ II;
00169   DEBUG(std::cerr << "Number of Stages: " << stageNum << "\n");
00170   
00171   for(int index = 0; index < II; ++index) {
00172     int count = 0;
00173     for(int i = index; i <= (schedule.rbegin()->first); i+=II) {  
00174       if(schedule.count(i)) {
00175   for(std::vector<MSchedGraphNode*>::iterator I = schedule[i].begin(), 
00176         E = schedule[i].end(); I != E; ++I) {
00177     //Check if its a branch
00178     if((*I)->isBranch()) {
00179       assert(count == 0 && "Branch can not be from a previous iteration");
00180       kernel.push_back(std::make_pair(*I, count));
00181     }
00182     else
00183     //FIXME: Check if the instructions in the earlier stage conflict
00184     kernel.push_back(std::make_pair(*I, count));
00185   }
00186       }
00187       ++count;
00188     }
00189   }
00190   
00191   if(stageNum > 0)
00192     maxStage = stageNum;
00193   else
00194     maxStage = 0;
00195 
00196   return true;
00197 }
00198 
00199 
00200 void MSSchedule::print(std::ostream &os) const {
00201   os << "Schedule:\n";
00202   
00203   for(schedule_const_iterator I =  schedule.begin(), E = schedule.end(); I != E; ++I) {
00204     os << "Cycle: " << I->first << "\n";
00205     for(std::vector<MSchedGraphNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node)
00206     os << **node << "\n";
00207   }
00208 
00209   os << "Kernel:\n";
00210   for(std::vector<std::pair<MSchedGraphNode*, int> >::const_iterator I = kernel.begin(),
00211   E = kernel.end(); I != E; ++I)
00212     os << "Node: " << *(I->first) << " Stage: " << I->second << "\n";
00213 }
00214