lib/Target/TargetSchedInfo.cpp

   1 //===-- SchedInfo.cpp - Generic code to support target schedulers ----------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the generic part of a Scheduler description for a
  11 // target.  This functionality is defined in the llvm/Target/SchedInfo.h file.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Target/TargetSchedInfo.h"
  16 #include "llvm/Target/TargetMachine.h"
  17
  18 resourceId_t MachineResource::nextId = 0;
  19
  20 // Check if fromRVec and toRVec have *any* common entries.
  21 // Assume the vectors are sorted in increasing order.
  22 // Algorithm copied from function set_intersection() for sorted ranges
  23 // (stl_algo.h).
  24 //
  25 inline static bool
  26 RUConflict(const std::vector<resourceId_t>& fromRVec,
  27            const std::vector<resourceId_t>& toRVec)
  28 {
  29
  30   unsigned fN = fromRVec.size(), tN = toRVec.size();
  31   unsigned fi = 0, ti = 0;
  32
  33   while (fi < fN && ti < tN) {
  34     if (fromRVec[fi] < toRVec[ti])
  35       ++fi;
  36     else if (toRVec[ti] < fromRVec[fi])
  37       ++ti;
  38     else
  39       return true;
  40   }
  41   return false;
  42 }
  43
  44
  45 static cycles_t
  46 ComputeMinGap(const InstrRUsage &fromRU,
  47               const InstrRUsage &toRU)
  48 {
  49   cycles_t minGap = 0;
  50
  51   if (fromRU.numBubbles > 0)
  52     minGap = fromRU.numBubbles;
  53
  54   if (minGap < fromRU.numCycles) {
  55     // only need to check from cycle `minGap' onwards
  56     for (cycles_t gap=minGap; gap <= fromRU.numCycles-1; gap++) {
  57       // check if instr. #2 can start executing `gap' cycles after #1
  58       // by checking for resource conflicts in each overlapping cycle
  59       cycles_t numOverlap =std::min(fromRU.numCycles - gap, toRU.numCycles);
  60       for (cycles_t c = 0; c <= numOverlap-1; c++)
  61         if (RUConflict(fromRU.resourcesByCycle[gap + c],
  62                        toRU.resourcesByCycle[c])) {
  63           // conflict found so minGap must be more than `gap'
  64           minGap = gap+1;
  65           break;
  66         }
  67     }
  68   }
  69
  70   return minGap;
  71 }
  72
  73
  74 //---------------------------------------------------------------------------
  75 // class TargetSchedInfo
  76 //      Interface to machine description for instruction scheduling
  77 //---------------------------------------------------------------------------
  78
  79 TargetSchedInfo::TargetSchedInfo(const TargetMachine&    tgt,
  80                                  int                     NumSchedClasses,
  81                                  const InstrClassRUsage* ClassRUsages,
  82                                  const InstrRUsageDelta* UsageDeltas,
  83                                  const InstrIssueDelta*  IssueDeltas,
  84                                  unsigned NumUsageDeltas,
  85                                  unsigned NumIssueDeltas)
  86   : target(tgt),
  87     numSchedClasses(NumSchedClasses), mii(& tgt.getInstrInfo()),
  88     classRUsages(ClassRUsages), usageDeltas(UsageDeltas),
  89     issueDeltas(IssueDeltas), numUsageDeltas(NumUsageDeltas),
  90     numIssueDeltas(NumIssueDeltas)
  91 {}
  92
  93 void
  94 TargetSchedInfo::initializeResources()
  95 {
  96   assert(MAX_NUM_SLOTS >= (int)getMaxNumIssueTotal()
  97          && "Insufficient slots for static data! Increase MAX_NUM_SLOTS");
  98
  99   // First, compute common resource usage info for each class because
 100   // most instructions will probably behave the same as their class.
 101   // Cannot allocate a vector of InstrRUsage so new each one.
 102   //
 103   std::vector<InstrRUsage> instrRUForClasses;
 104   instrRUForClasses.resize(numSchedClasses);
 105   for (InstrSchedClass sc = 0; sc < numSchedClasses; sc++) {
 106     // instrRUForClasses.push_back(new InstrRUsage);
 107     instrRUForClasses[sc].setMaxSlots(getMaxNumIssueTotal());
 108     instrRUForClasses[sc].setTo(classRUsages[sc]);
 109   }
 110
 111   computeInstrResources(instrRUForClasses);
 112   computeIssueGaps(instrRUForClasses);
 113 }
 114
 115
 116 void
 117 TargetSchedInfo::computeInstrResources(const std::vector<InstrRUsage>&
 118                                         instrRUForClasses)
 119 {
 120   int numOpCodes =  mii->getNumRealOpCodes();
 121   instrRUsages.resize(numOpCodes);
 122
 123   // First get the resource usage information from the class resource usages.
 124   for (MachineOpCode op = 0; op < numOpCodes; ++op) {
 125     InstrSchedClass sc = getSchedClass(op);
 126     assert(sc < numSchedClasses);
 127     instrRUsages[op] = instrRUForClasses[sc];
 128   }
 129
 130   // Now, modify the resource usages as specified in the deltas.
 131   for (unsigned i = 0; i < numUsageDeltas; ++i) {
 132     MachineOpCode op = usageDeltas[i].opCode;
 133     assert(op < numOpCodes);
 134     instrRUsages[op].addUsageDelta(usageDeltas[i]);
 135   }
 136
 137   // Then modify the issue restrictions as specified in the deltas.
 138   for (unsigned i = 0; i < numIssueDeltas; ++i) {
 139     MachineOpCode op = issueDeltas[i].opCode;
 140     assert(op < numOpCodes);
 141     instrRUsages[issueDeltas[i].opCode].addIssueDelta(issueDeltas[i]);
 142   }
 143 }
 144
 145
 146 void
 147 TargetSchedInfo::computeIssueGaps(const std::vector<InstrRUsage>&
 148                                    instrRUForClasses)
 149 {
 150   int numOpCodes =  mii->getNumRealOpCodes();
 151   issueGaps.resize(numOpCodes);
 152   conflictLists.resize(numOpCodes);
 153
 154   assert(numOpCodes < (1 << MAX_OPCODE_SIZE) - 1
 155          && "numOpCodes invalid for implementation of class OpCodePair!");
 156
 157   // First, compute issue gaps between pairs of classes based on common
 158   // resources usages for each class, because most instruction pairs will
 159   // usually behave the same as their class.
 160   //
 161   int classPairGaps[numSchedClasses][numSchedClasses];
 162   for (InstrSchedClass fromSC=0; fromSC < numSchedClasses; fromSC++)
 163     for (InstrSchedClass toSC=0; toSC < numSchedClasses; toSC++) {
 164       int classPairGap = ComputeMinGap(instrRUForClasses[fromSC],
 165                                        instrRUForClasses[toSC]);
 166       classPairGaps[fromSC][toSC] = classPairGap;
 167     }
 168
 169   // Now, for each pair of instructions, use the class pair gap if both
 170   // instructions have identical resource usage as their respective classes.
 171   // If not, recompute the gap for the pair from scratch.
 172
 173   longestIssueConflict = 0;
 174
 175   for (MachineOpCode fromOp=0; fromOp < numOpCodes; fromOp++)
 176     for (MachineOpCode toOp=0; toOp < numOpCodes; toOp++) {
 177       int instrPairGap =
 178         (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass)
 179         ? classPairGaps[getSchedClass(fromOp)][getSchedClass(toOp)]
 180         : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]);
 181
 182       if (instrPairGap > 0) {
 183         this->setGap(instrPairGap, fromOp, toOp);
 184         conflictLists[fromOp].push_back(toOp);
 185         longestIssueConflict=std::max(longestIssueConflict, instrPairGap);
 186       }
 187     }
 188 }
 189
 190
 191 void InstrRUsage::setTo(const InstrClassRUsage& classRU) {
 192   sameAsClass   = true;
 193   isSingleIssue = classRU.isSingleIssue;
 194   breaksGroup   = classRU.breaksGroup;
 195   numBubbles    = classRU.numBubbles;
 196
 197   for (unsigned i=0; i < classRU.numSlots; i++) {
 198     unsigned slot = classRU.feasibleSlots[i];
 199     assert(slot < feasibleSlots.size() && "Invalid slot specified!");
 200     this->feasibleSlots[slot] = true;
 201   }
 202
 203   numCycles   = classRU.totCycles;
 204   resourcesByCycle.resize(this->numCycles);
 205
 206   for (unsigned i=0; i < classRU.numRUEntries; i++)
 207     for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles;
 208          c < NC; c++)
 209       this->resourcesByCycle[c].push_back(classRU.V[i].resourceId);
 210
 211   // Sort each resource usage vector by resourceId_t to speed up conflict
 212   // checking
 213   for (unsigned i=0; i < this->resourcesByCycle.size(); i++)
 214     sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end());
 215 }
 216
 217 // Add the extra resource usage requirements specified in the delta.
 218 // Note that a negative value of `numCycles' means one entry for that
 219 // resource should be deleted for each cycle.
 220 //
 221 void InstrRUsage::addUsageDelta(const InstrRUsageDelta &delta) {
 222   int NC = delta.numCycles;
 223   sameAsClass = false;
 224
 225   // resize the resources vector if more cycles are specified
 226   unsigned maxCycles = this->numCycles;
 227   maxCycles = std::max(maxCycles, delta.startCycle + abs(NC) - 1);
 228   if (maxCycles > this->numCycles) {
 229     this->resourcesByCycle.resize(maxCycles);
 230     this->numCycles = maxCycles;
 231   }
 232
 233   if (NC >= 0)
 234     for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++)
 235       this->resourcesByCycle[c].push_back(delta.resourceId);
 236   else
 237     // Remove the resource from all NC cycles.
 238     for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++) {
 239       // Look for the resource backwards so we remove the last entry
 240       // for that resource in each cycle.
 241       std::vector<resourceId_t>& rvec = this->resourcesByCycle[c];
 242       int r;
 243       for (r = rvec.size() - 1; r >= 0; r--)
 244         if (rvec[r] == delta.resourceId) {
 245           // found last entry for the resource
 246           rvec.erase(rvec.begin() + r);
 247           break;
 248         }
 249       assert(r >= 0 && "Resource to remove was unused in cycle c!");
 250     }
 251 }