LLVM API Documentation
00001 //===-- SchedInfo.cpp - Generic code to support target schedulers ----------==// 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 // This file implements the generic part of a Scheduler description for a 00011 // target. This functionality is defined in the llvm/Target/SchedInfo.h file. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Config/alloca.h" 00016 #include "llvm/Target/TargetSchedInfo.h" 00017 #include "llvm/Target/TargetMachine.h" 00018 #include <algorithm> 00019 #include <iostream> 00020 using namespace llvm; 00021 00022 resourceId_t llvm::CPUResource::nextId = 0; 00023 static std::vector<CPUResource*> *CPUResourceMap = 0; 00024 00025 CPUResource::CPUResource(const std::string& resourceName, int maxUsers) 00026 : rname(resourceName), rid(nextId++), maxNumUsers(maxUsers) { 00027 if(!CPUResourceMap) 00028 CPUResourceMap = new std::vector<CPUResource*>; 00029 00030 //Put Resource in the map 00031 CPUResourceMap->push_back(this); 00032 } 00033 00034 ///Get CPUResource if you only have the resource ID 00035 CPUResource* CPUResource::getCPUResource(resourceId_t id) { 00036 return (*CPUResourceMap)[id]; 00037 } 00038 00039 // Check if fromRVec and toRVec have *any* common entries. 00040 // Assume the vectors are sorted in increasing order. 00041 // Algorithm copied from function set_intersection() for sorted ranges 00042 // (stl_algo.h). 00043 // 00044 inline static bool 00045 RUConflict(const std::vector<resourceId_t>& fromRVec, 00046 const std::vector<resourceId_t>& toRVec) 00047 { 00048 00049 unsigned fN = fromRVec.size(), tN = toRVec.size(); 00050 unsigned fi = 0, ti = 0; 00051 00052 while (fi < fN && ti < tN) { 00053 if (fromRVec[fi] < toRVec[ti]) 00054 ++fi; 00055 else if (toRVec[ti] < fromRVec[fi]) 00056 ++ti; 00057 else 00058 return true; 00059 } 00060 return false; 00061 } 00062 00063 00064 static cycles_t 00065 ComputeMinGap(const InstrRUsage &fromRU, 00066 const InstrRUsage &toRU) 00067 { 00068 cycles_t minGap = 0; 00069 00070 if (fromRU.numBubbles > 0) 00071 minGap = fromRU.numBubbles; 00072 00073 if (minGap < fromRU.numCycles) { 00074 // only need to check from cycle `minGap' onwards 00075 for (cycles_t gap=minGap; gap <= fromRU.numCycles-1; gap++) { 00076 // check if instr. #2 can start executing `gap' cycles after #1 00077 // by checking for resource conflicts in each overlapping cycle 00078 cycles_t numOverlap =std::min(fromRU.numCycles - gap, toRU.numCycles); 00079 for (cycles_t c = 0; c <= numOverlap-1; c++) 00080 if (RUConflict(fromRU.resourcesByCycle[gap + c], 00081 toRU.resourcesByCycle[c])) { 00082 // conflict found so minGap must be more than `gap' 00083 minGap = gap+1; 00084 break; 00085 } 00086 } 00087 } 00088 00089 return minGap; 00090 } 00091 00092 00093 //--------------------------------------------------------------------------- 00094 // class TargetSchedInfo 00095 // Interface to machine description for instruction scheduling 00096 //--------------------------------------------------------------------------- 00097 00098 TargetSchedInfo::TargetSchedInfo(const TargetMachine& tgt, 00099 int NumSchedClasses, 00100 const InstrClassRUsage* ClassRUsages, 00101 const InstrRUsageDelta* UsageDeltas, 00102 const InstrIssueDelta* IssueDeltas, 00103 unsigned NumUsageDeltas, 00104 unsigned NumIssueDeltas) 00105 : target(tgt), 00106 numSchedClasses(NumSchedClasses), mii(tgt.getInstrInfo()), 00107 classRUsages(ClassRUsages), usageDeltas(UsageDeltas), 00108 issueDeltas(IssueDeltas), numUsageDeltas(NumUsageDeltas), 00109 numIssueDeltas(NumIssueDeltas) 00110 {} 00111 00112 void 00113 TargetSchedInfo::initializeResources() 00114 { 00115 assert(MAX_NUM_SLOTS >= (int)getMaxNumIssueTotal() 00116 && "Insufficient slots for static data! Increase MAX_NUM_SLOTS"); 00117 00118 // First, compute common resource usage info for each class because 00119 // most instructions will probably behave the same as their class. 00120 // Cannot allocate a vector of InstrRUsage so new each one. 00121 // 00122 std::vector<InstrRUsage> instrRUForClasses; 00123 instrRUForClasses.resize(numSchedClasses); 00124 for (InstrSchedClass sc = 0; sc < numSchedClasses; sc++) { 00125 // instrRUForClasses.push_back(new InstrRUsage); 00126 instrRUForClasses[sc].setMaxSlots(getMaxNumIssueTotal()); 00127 instrRUForClasses[sc].setTo(classRUsages[sc]); 00128 } 00129 00130 computeInstrResources(instrRUForClasses); 00131 computeIssueGaps(instrRUForClasses); 00132 } 00133 00134 00135 void 00136 TargetSchedInfo::computeInstrResources(const std::vector<InstrRUsage>& 00137 instrRUForClasses) 00138 { 00139 int numOpCodes = mii->getNumOpcodes(); 00140 instrRUsages.resize(numOpCodes); 00141 00142 // First get the resource usage information from the class resource usages. 00143 for (MachineOpCode op = 0; op < numOpCodes; ++op) { 00144 InstrSchedClass sc = getSchedClass(op); 00145 assert(sc < numSchedClasses); 00146 instrRUsages[op] = instrRUForClasses[sc]; 00147 } 00148 00149 // Now, modify the resource usages as specified in the deltas. 00150 for (unsigned i = 0; i < numUsageDeltas; ++i) { 00151 MachineOpCode op = usageDeltas[i].opCode; 00152 assert(op < numOpCodes); 00153 instrRUsages[op].addUsageDelta(usageDeltas[i]); 00154 } 00155 00156 // Then modify the issue restrictions as specified in the deltas. 00157 for (unsigned i = 0; i < numIssueDeltas; ++i) { 00158 MachineOpCode op = issueDeltas[i].opCode; 00159 assert(op < numOpCodes); 00160 instrRUsages[issueDeltas[i].opCode].addIssueDelta(issueDeltas[i]); 00161 } 00162 } 00163 00164 00165 void 00166 TargetSchedInfo::computeIssueGaps(const std::vector<InstrRUsage>& 00167 instrRUForClasses) 00168 { 00169 int numOpCodes = mii->getNumOpcodes(); 00170 issueGaps.resize(numOpCodes); 00171 conflictLists.resize(numOpCodes); 00172 00173 // First, compute issue gaps between pairs of classes based on common 00174 // resources usages for each class, because most instruction pairs will 00175 // usually behave the same as their class. 00176 // 00177 int* classPairGaps = 00178 static_cast<int*>(alloca(sizeof(int) * numSchedClasses * numSchedClasses)); 00179 for (InstrSchedClass fromSC=0; fromSC < numSchedClasses; fromSC++) 00180 for (InstrSchedClass toSC=0; toSC < numSchedClasses; toSC++) { 00181 int classPairGap = ComputeMinGap(instrRUForClasses[fromSC], 00182 instrRUForClasses[toSC]); 00183 classPairGaps[fromSC*numSchedClasses + toSC] = classPairGap; 00184 } 00185 00186 // Now, for each pair of instructions, use the class pair gap if both 00187 // instructions have identical resource usage as their respective classes. 00188 // If not, recompute the gap for the pair from scratch. 00189 00190 longestIssueConflict = 0; 00191 00192 for (MachineOpCode fromOp=0; fromOp < numOpCodes; fromOp++) 00193 for (MachineOpCode toOp=0; toOp < numOpCodes; toOp++) { 00194 int instrPairGap = 00195 (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass) 00196 ? classPairGaps[getSchedClass(fromOp)*numSchedClasses + getSchedClass(toOp)] 00197 : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]); 00198 00199 if (instrPairGap > 0) { 00200 this->setGap(instrPairGap, fromOp, toOp); 00201 conflictLists[fromOp].push_back(toOp); 00202 longestIssueConflict=std::max(longestIssueConflict, instrPairGap); 00203 } 00204 } 00205 } 00206 00207 00208 void InstrRUsage::setTo(const InstrClassRUsage& classRU) { 00209 sameAsClass = true; 00210 isSingleIssue = classRU.isSingleIssue; 00211 breaksGroup = classRU.breaksGroup; 00212 numBubbles = classRU.numBubbles; 00213 00214 for (unsigned i=0; i < classRU.numSlots; i++) { 00215 unsigned slot = classRU.feasibleSlots[i]; 00216 assert(slot < feasibleSlots.size() && "Invalid slot specified!"); 00217 this->feasibleSlots[slot] = true; 00218 } 00219 00220 numCycles = classRU.totCycles; 00221 resourcesByCycle.resize(this->numCycles); 00222 00223 for (unsigned i=0; i < classRU.numRUEntries; i++) 00224 for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles; 00225 c < NC; c++) 00226 this->resourcesByCycle[c].push_back(classRU.V[i].resourceId); 00227 00228 // Sort each resource usage vector by resourceId_t to speed up conflict 00229 // checking 00230 for (unsigned i=0; i < this->resourcesByCycle.size(); i++) 00231 std::sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end()); 00232 } 00233 00234 // Add the extra resource usage requirements specified in the delta. 00235 // Note that a negative value of `numCycles' means one entry for that 00236 // resource should be deleted for each cycle. 00237 // 00238 void InstrRUsage::addUsageDelta(const InstrRUsageDelta &delta) { 00239 int NC = delta.numCycles; 00240 sameAsClass = false; 00241 00242 // resize the resources vector if more cycles are specified 00243 unsigned maxCycles = this->numCycles; 00244 maxCycles = std::max(maxCycles, delta.startCycle + abs(NC) - 1); 00245 if (maxCycles > this->numCycles) { 00246 this->resourcesByCycle.resize(maxCycles); 00247 this->numCycles = maxCycles; 00248 } 00249 00250 if (NC >= 0) 00251 for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++) 00252 this->resourcesByCycle[c].push_back(delta.resourceId); 00253 else 00254 // Remove the resource from all NC cycles. 00255 for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++) { 00256 // Look for the resource backwards so we remove the last entry 00257 // for that resource in each cycle. 00258 std::vector<resourceId_t>& rvec = this->resourcesByCycle[c]; 00259 int r; 00260 for (r = rvec.size() - 1; r >= 0; r--) 00261 if (rvec[r] == delta.resourceId) { 00262 // found last entry for the resource 00263 rvec.erase(rvec.begin() + r); 00264 break; 00265 } 00266 assert(r >= 0 && "Resource to remove was unused in cycle c!"); 00267 } 00268 }