LLVM API Documentation
00001 //===-- MSScheduleSB.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 "ModuloSchedSB" 00014 00015 #include "MSScheduleSB.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(MSchedGraphSBNode*, 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 MSScheduleSB::insert(MSchedGraphSBNode *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<MSchedGraphSBNode*> 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 MSScheduleSB::addToSchedule(int cycle, MSchedGraphSBNode *node) { 00060 std::vector<MSchedGraphSBNode*> nodesAtCycle = schedule[cycle]; 00061 00062 std::map<unsigned, MSchedGraphSBNode*> 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<MSchedGraphSBNode*> nodes; 00070 for(std::map<unsigned, MSchedGraphSBNode*>::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 MSScheduleSB::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 MSScheduleSB::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 MSScheduleSB::resourcesFree(MSchedGraphSBNode *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 MSScheduleSB::constructKernel(int II, std::vector<MSchedGraphSBNode*> &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<MSchedGraphSBNode*, 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<MSchedGraphSBNode*>::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<MSchedGraphSBNode*, 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 if(I->first->isPredicate()) { 00247 //assert(I->second == 0 && "Predicate node must be from current iteration\n"); 00248 std::vector<const MachineInstr*> otherInstrs = I->first->getOtherInstrs(); 00249 for(std::vector<const MachineInstr*>::iterator O = otherInstrs.begin(), OE = otherInstrs.end(); O != OE; ++O) { 00250 kernel.push_back(std::make_pair((MachineInstr*) *O, I->second)); 00251 } 00252 } 00253 00254 } 00255 00256 std::map<unsigned, MachineInstr*> tmpMap; 00257 00258 //Add remaining invar instructions 00259 for(std::map<const MachineInstr*, unsigned>::iterator N = indVar.begin(), NE = indVar.end(); N != NE; ++N) { 00260 tmpMap[N->second] = (MachineInstr*) N->first; 00261 } 00262 00263 //Add to kernel, and delete from indVar 00264 for(std::map<unsigned, MachineInstr*>::iterator N = tmpMap.begin(), NE = tmpMap.end(); N != NE; ++N) { 00265 kernel.push_back(std::make_pair(N->second, 0)); 00266 indVar.erase(N->second); 00267 } 00268 00269 00270 maxStage = maxSN; 00271 00272 00273 return true; 00274 } 00275 00276 bool MSScheduleSB::defPreviousStage(Value *def, int stage) { 00277 00278 //Loop over kernel and determine if value is being defined in previous stage 00279 for(std::vector<std::pair<MachineInstr*, int> >::iterator P = kernel.begin(), PE = kernel.end(); P != PE; ++P) { 00280 MachineInstr* inst = P->first; 00281 00282 //Loop over Machine Operands 00283 for(unsigned i=0; i < inst->getNumOperands(); ++i) { 00284 //get machine operand 00285 const MachineOperand &mOp = inst->getOperand(i); 00286 if(mOp.getType() == MachineOperand::MO_VirtualRegister && mOp.isDef()) { 00287 if(def == mOp.getVRegValue()) { 00288 if(P->second >= stage) 00289 return false; 00290 else 00291 return true; 00292 } 00293 } 00294 } 00295 } 00296 00297 assert(0 && "We should always have found the def in our kernel\n"); 00298 abort(); 00299 } 00300 00301 00302 void MSScheduleSB::print(std::ostream &os) const { 00303 os << "Schedule:\n"; 00304 00305 for(schedule_const_iterator I = schedule.begin(), E = schedule.end(); I != E; ++I) { 00306 os << "Cycle: " << I->first << "\n"; 00307 for(std::vector<MSchedGraphSBNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node) 00308 os << **node << "\n"; 00309 } 00310 00311 os << "Kernel:\n"; 00312 for(std::vector<std::pair<MachineInstr*, int> >::const_iterator I = kernel.begin(), 00313 E = kernel.end(); I != E; ++I) 00314 os << "Node: " << *(I->first) << " Stage: " << I->second << "\n"; 00315 } 00316 00317 void MSScheduleSB::printSchedule(std::ostream &os) const { 00318 os << "Schedule:\n"; 00319 00320 for(schedule_const_iterator I = schedule.begin(), E = schedule.end(); I != E; ++I) { 00321 os << "Cycle: " << I->first << "\n"; 00322 for(std::vector<MSchedGraphSBNode*>::const_iterator node = I->second.begin(), nodeEnd = I->second.end(); node != nodeEnd; ++node) 00323 os << **node << "\n"; 00324 } 00325 }