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 #include "llvm/CodeGen/MachineInstr.h" 00020 #include <iostream> 00021 using namespace llvm; 00022 00023 //Check if all resources are free 00024 bool resourcesFree(MSchedGraphNode*, int, 00025 std::map<int, std::map<int, int> > &resourceNumPerCycle); 00026 00027 //Returns a boolean indicating if the start cycle needs to be increased/decreased 00028 bool MSSchedule::insert(MSchedGraphNode *node, int cycle, int II) { 00029 00030 //First, check if the cycle has a spot free to start 00031 if(schedule.find(cycle) != schedule.end()) { 00032 //Check if we have a free issue slot at this cycle 00033 if (schedule[cycle].size() < numIssue) { 00034 //Now check if all the resources in their respective cycles are available 00035 if(resourcesFree(node, cycle, II)) { 00036 //Insert to preserve dependencies 00037 addToSchedule(cycle,node); 00038 DEBUG(std::cerr << "Found spot in map, and there is an issue slot\n"); 00039 return false; 00040 } 00041 } 00042 } 00043 //Not in the map yet so put it in 00044 else { 00045 if(resourcesFree(node,cycle,II)) { 00046 std::vector<MSchedGraphNode*> nodes; 00047 nodes.push_back(node); 00048 schedule[cycle] = nodes; 00049 DEBUG(std::cerr << "Nothing in map yet so taking an issue slot\n"); 00050 return false; 00051 } 00052 } 00053 00054 DEBUG(std::cerr << "All issue slots taken\n"); 00055 return true; 00056 00057 } 00058 00059 void MSSchedule::addToSchedule(int cycle, MSchedGraphNode *node) { 00060 std::vector<MSchedGraphNode*> nodesAtCycle = schedule[cycle]; 00061 00062 std::map<unsigned, MSchedGraphNode*> indexMap; 00063 for(unsigned i=0; i < nodesAtCycle.size(); ++i) { 00064 indexMap[nodesAtCycle[i]->getIndex()] = nodesAtCycle[i]; 00065 } 00066 00067 indexMap[node->getIndex()] = node; 00068 00069 std::vector<MSchedGraphNode*> nodes; 00070 for(std::map<unsigned, MSchedGraphNode*>::iterator I = indexMap.begin(), E = indexMap.end(); I != E; ++I) 00071 nodes.push_back(I->second); 00072 00073 schedule[cycle] = nodes; 00074 } 00075 00076 bool MSSchedule::resourceAvailable(int resourceNum, int cycle) { 00077 bool isFree = true; 00078 00079 //Get Map for this cycle 00080 if(resourceNumPerCycle.count(cycle)) { 00081 if(resourceNumPerCycle[cycle].count(resourceNum)) { 00082 int maxRes = CPUResource::getCPUResource(resourceNum)->maxNumUsers; 00083 if(resourceNumPerCycle[cycle][resourceNum] >= maxRes) 00084 isFree = false; 00085 } 00086 } 00087 00088 return isFree; 00089 } 00090 00091 void MSSchedule::useResource(int resourceNum, int cycle) { 00092 00093 //Get Map for this cycle 00094 if(resourceNumPerCycle.count(cycle)) { 00095 if(resourceNumPerCycle[cycle].count(resourceNum)) { 00096 resourceNumPerCycle[cycle][resourceNum]++; 00097 } 00098 else { 00099 resourceNumPerCycle[cycle][resourceNum] = 1; 00100 } 00101 } 00102 //If no map, create one! 00103 else { 00104 std::map<int, int> resourceUse; 00105 resourceUse[resourceNum] = 1; 00106 resourceNumPerCycle[cycle] = resourceUse; 00107 } 00108 00109 } 00110 00111 bool MSSchedule::resourcesFree(MSchedGraphNode *node, int cycle, int II) { 00112 00113 //Get Resource usage for this instruction 00114 const TargetSchedInfo *msi = node->getParent()->getTarget()->getSchedInfo(); 00115 int currentCycle = cycle; 00116 bool success = true; 00117 00118 //Create vector of starting cycles 00119 std::vector<int> cyclesMayConflict; 00120 cyclesMayConflict.push_back(cycle); 00121 00122 if(resourceNumPerCycle.size() > 0) { 00123 for(int i = cycle-II; i >= (resourceNumPerCycle.begin()->first); i-=II) 00124 cyclesMayConflict.push_back(i); 00125 for(int i = cycle+II; i <= resourceNumPerCycle.end()->first; i+=II) 00126 cyclesMayConflict.push_back(i); 00127 } 00128 00129 //Now check all cycles for conflicts 00130 for(int index = 0; index < (int) cyclesMayConflict.size(); ++index) { 00131 currentCycle = cyclesMayConflict[index]; 00132 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 for(unsigned j=0; j < resources[i].size(); ++j) { 00140 00141 //Get Resource to check its availability 00142 int resourceNum = resources[i][j]; 00143 00144 DEBUG(std::cerr << "Attempting to schedule Resource Num: " << resourceNum << " in cycle: " << currentCycle << "\n"); 00145 00146 success = resourceAvailable(resourceNum, currentCycle); 00147 00148 if(!success) 00149 break; 00150 00151 } 00152 00153 if(!success) 00154 break; 00155 00156 //Increase cycle 00157 currentCycle++; 00158 } 00159 00160 if(!success) 00161 return false; 00162 } 00163 00164 //Actually put resources into the map 00165 if(success) { 00166 00167 int currentCycle = cycle; 00168 //Get resource usage for this instruction 00169 InstrRUsage rUsage = msi->getInstrRUsage(node->getInst()->getOpcode()); 00170 std::vector<std::vector<resourceId_t> > resources = rUsage.resourcesByCycle; 00171 00172 //Loop over resources in each cycle and increments their usage count 00173 for(unsigned i=0; i < resources.size(); ++i) { 00174 for(unsigned j=0; j < resources[i].size(); ++j) { 00175 int resourceNum = resources[i][j]; 00176 useResource(resourceNum, currentCycle); 00177 } 00178 currentCycle++; 00179 } 00180 } 00181 00182 00183 return true; 00184 00185 } 00186 00187 bool MSSchedule::constructKernel(int II, std::vector<MSchedGraphNode*> &branches, std::map<const MachineInstr*, unsigned> &indVar) { 00188 00189 //Our schedule is allowed to have negative numbers, so lets calculate this offset 00190 int offset = schedule.begin()->first; 00191 if(offset > 0) 00192 offset = 0; 00193 00194 DEBUG(std::cerr << "Offset: " << offset << "\n"); 00195 00196 //Using the schedule, fold up into kernel and check resource conflicts as we go 00197 std::vector<std::pair<MSchedGraphNode*, int> > tempKernel; 00198 00199 int stageNum = ((schedule.rbegin()->first-offset)+1)/ II; 00200 int maxSN = 0; 00201 00202 DEBUG(std::cerr << "Number of Stages: " << stageNum << "\n"); 00203 00204 for(int index = offset; index < (II+offset); ++index) { 00205 int count = 0; 00206 for(int i = index; i <= (schedule.rbegin()->first); i+=II) { 00207 if(schedule.count(i)) { 00208 for(std::vector<MSchedGraphNode*>::iterator I = schedule[i].begin(), 00209 E = schedule[i].end(); I != E; ++I) { 00210 //Check if its a branch 00211 assert(!(*I)->isBranch() && "Branch should not be schedule!"); 00212 00213 tempKernel.push_back(std::make_pair(*I, count)); 00214 maxSN = std::max(maxSN, count); 00215 00216 } 00217 } 00218 ++count; 00219 } 00220 } 00221 00222 00223 //Add in induction var code 00224 for(std::vector<std::pair<MSchedGraphNode*, int> >::iterator I = tempKernel.begin(), IE = tempKernel.end(); 00225 I != IE; ++I) { 00226 //Add indVar instructions before this one for the current iteration 00227 if(I->second == 0) { 00228 std::map<unsigned, MachineInstr*> tmpMap; 00229 00230 //Loop over induction variable instructions in the map that come before this instr 00231 for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { 00232 00233 00234 if(N->second < I->first->getIndex()) 00235 tmpMap[N->second] = (MachineInstr*) N->first; 00236 } 00237 00238 //Add to kernel, and delete from indVar 00239 for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) { 00240 kernel.push_back(std::make_pair(N->second, 0)); 00241 indVar.erase(N->second); 00242 } 00243 } 00244 00245 kernel.push_back(std::make_pair((MachineInstr*) I->first->getInst(), I->second)); 00246 00247 } 00248 00249 std::map<unsigned, MachineInstr*> tmpMap; 00250 00251 //Add remaining invar instructions 00252 for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { 00253 tmpMap[N->second] = (MachineInstr*) N->first; 00254 } 00255 00256 //Add to kernel, and delete from indVar 00257 for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) { 00258 kernel.push_back(std::make_pair(N->second, 0)); 00259 indVar.erase(N->second); 00260 } 00261 00262 00263 maxStage = maxSN; 00264 00265 00266 return true; 00267 } 00268 00269 bool MSSchedule::defPreviousStage(Value *def, int stage) { 00270 00271 //Loop over kernel and determine if value is being defined in previous stage 00272 for(std::vector<std::pair<MachineInstr*, int> >::iterator P = kernel.begin(), PE = kernel.end(); P != PE; ++P) { 00273 MachineInstr* inst = P->first; 00274 00275 //Loop over Machine Operands 00276 for(unsigned i=0; i < inst->getNumOperands(); ++i) { 00277 //get machine operand 00278 const MachineOperand &mOp = inst->getOperand(i); 00279 if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { 00280 if(def == mOp.getVRegValue()) { 00281 if(P->second >= stage) 00282 return false; 00283 else 00284 return true; 00285 } 00286 } 00287 } 00288 } 00289 00290 assert(0 && "We should always have found the def in our kernel\n"); 00291 abort(); 00292 } 00293 00294 00295 void MSSchedule::print(std::ostream &os) const { 00296 os << "Schedule:\n"; 00297 00298 for(schedule_const_iterator I = schedule.begin(), E = schedule.end(); I != E; ++I) { 00299 os << "Cycle: " << I->first << "\n"; 00300 for(std::vector<MSchedGraphNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node) 00301 os << **node << "\n"; 00302 } 00303 00304 os << "Kernel:\n"; 00305 for(std::vector<std::pair<MachineInstr*, int> >::const_iterator I = kernel.begin(), 00306 E = kernel.end(); I != E; ++I) 00307 os << "Node: " << *(I->first) << " Stage: " << I->second << "\n"; 00308 } 00309