LLVM API Documentation
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