lib/Target/TargetMachine.cpp

   1 //===-- TargetMachine.cpp - General Target Information ---------------------==//
   2 //
   3 // This file describes the general parts of a Target machine.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Target/Machine.h"
   8 #include "llvm/DerivedTypes.h"
   9
  10 // External object describing the machine instructions
  11 // Initialized only when the TargetMachine class is created
  12 // and reset when that class is destroyed.
  13 //
  14 const MachineInstrDescriptor* TargetInstrDescriptors = NULL;
  15
  16 resourceId_t MachineResource::nextId = 0;
  17
  18 static cycles_t ComputeMinGap           (const InstrRUsage& fromRU,
  19                                          const InstrRUsage& toRU);
  20
  21 static bool     RUConflict              (const vector<resourceId_t>& fromRVec,
  22                                          const vector<resourceId_t>& fromRVec);
  23
  24 //---------------------------------------------------------------------------
  25 // class TargetMachine
  26 //
  27 // Purpose:
  28 //   Machine description.
  29 //
  30 //---------------------------------------------------------------------------
  31
  32
  33 // function TargetMachine::findOptimalStorageSize
  34 //
  35 // Purpose:
  36 //   This default implementation assumes that all sub-word data items use
  37 //   space equal to optSizeForSubWordData, and all other primitive data
  38 //   items use space according to the type.
  39 //
  40 unsigned int TargetMachine::findOptimalStorageSize(const Type* ty) const {
  41   switch(ty->getPrimitiveID()) {
  42   case Type::BoolTyID:
  43   case Type::UByteTyID:
  44   case Type::SByteTyID:
  45   case Type::UShortTyID:
  46   case Type::ShortTyID:
  47     return optSizeForSubWordData;
  48
  49   default:
  50     return DataLayout.getTypeSize(ty);
  51   }
  52 }
  53
  54
  55 //---------------------------------------------------------------------------
  56 // class MachineInstructionInfo
  57 //      Interface to description of machine instructions
  58 //---------------------------------------------------------------------------
  59
  60
  61 /*ctor*/
  62 MachineInstrInfo::MachineInstrInfo(const MachineInstrDescriptor* _desc,
  63                                    unsigned int _descSize,
  64                                    unsigned int _numRealOpCodes)
  65   : desc(_desc), descSize(_descSize), numRealOpCodes(_numRealOpCodes)
  66 {
  67   assert(TargetInstrDescriptors == NULL && desc != NULL);
  68   TargetInstrDescriptors = desc;        // initialize global variable
  69 }
  70
  71
  72 /*dtor*/
  73 MachineInstrInfo::~MachineInstrInfo()
  74 {
  75   TargetInstrDescriptors = NULL;        // reset global variable
  76 }
  77
  78
  79 bool
  80 MachineInstrInfo::constantFitsInImmedField(MachineOpCode opCode,
  81                                            int64_t intValue) const
  82 {
  83   // First, check if opCode has an immed field.
  84   bool isSignExtended;
  85   uint64_t maxImmedValue = this->maxImmedConstant(opCode, isSignExtended);
  86   if (maxImmedValue != 0)
  87     {
  88       // Now check if the constant fits
  89       if (intValue <= (int64_t) maxImmedValue &&
  90           intValue >= -((int64_t) maxImmedValue+1))
  91         return true;
  92     }
  93
  94   return false;
  95 }
  96
  97
  98 //---------------------------------------------------------------------------
  99 // class MachineSchedInfo
 100 //      Interface to machine description for instruction scheduling
 101 //---------------------------------------------------------------------------
 102
 103 /*ctor*/
 104 MachineSchedInfo::MachineSchedInfo(int                     _numSchedClasses,
 105                                    const MachineInstrInfo* _mii,
 106                                    const InstrClassRUsage* _classRUsages,
 107                                    const InstrRUsageDelta* _usageDeltas,
 108                                    const InstrIssueDelta*  _issueDeltas,
 109                                    unsigned int            _numUsageDeltas,
 110                                    unsigned int            _numIssueDeltas)
 111   : numSchedClasses(_numSchedClasses),
 112     mii(_mii),
 113     classRUsages(_classRUsages),
 114     usageDeltas(_usageDeltas),
 115     issueDeltas(_issueDeltas),
 116     numUsageDeltas(_numUsageDeltas),
 117     numIssueDeltas(_numIssueDeltas)
 118 {
 119 }
 120
 121 void
 122 MachineSchedInfo::initializeResources()
 123 {
 124   assert(MAX_NUM_SLOTS >= (int) getMaxNumIssueTotal()
 125          && "Insufficient slots for static data! Increase MAX_NUM_SLOTS");
 126
 127   // First, compute common resource usage info for each class because
 128   // most instructions will probably behave the same as their class.
 129   // Cannot allocate a vector of InstrRUsage so new each one.
 130   //
 131   vector<InstrRUsage> instrRUForClasses;
 132   instrRUForClasses.resize(numSchedClasses);
 133   for (InstrSchedClass sc=0; sc < numSchedClasses; sc++)
 134     {
 135       // instrRUForClasses.push_back(new InstrRUsage);
 136       instrRUForClasses[sc].setMaxSlots(getMaxNumIssueTotal());
 137       instrRUForClasses[sc] = classRUsages[sc];
 138     }
 139
 140   computeInstrResources(instrRUForClasses);
 141
 142   computeIssueGaps(instrRUForClasses);
 143 }
 144
 145
 146 void
 147 MachineSchedInfo::computeInstrResources(const vector<InstrRUsage>& instrRUForClasses)
 148 {
 149   int numOpCodes =  mii->getNumRealOpCodes();
 150   instrRUsages.resize(numOpCodes);
 151
 152   // First get the resource usage information from the class resource usages.
 153   for (MachineOpCode op=0; op < numOpCodes; op++)
 154     {
 155       InstrSchedClass sc = getSchedClass(op);
 156       assert(sc >= 0 && sc < numSchedClasses);
 157       instrRUsages[op] = instrRUForClasses[sc];
 158     }
 159
 160   // Now, modify the resource usages as specified in the deltas.
 161   for (unsigned i=0; i < numUsageDeltas; i++)
 162     {
 163       MachineOpCode op = usageDeltas[i].opCode;
 164       assert(op < numOpCodes);
 165       instrRUsages[op].addUsageDelta(usageDeltas[i]);
 166     }
 167
 168   // Then modify the issue restrictions as specified in the deltas.
 169   for (unsigned i=0; i < numIssueDeltas; i++)
 170     {
 171       MachineOpCode op = issueDeltas[i].opCode;
 172       assert(op < numOpCodes);
 173       instrRUsages[issueDeltas[i].opCode].addIssueDelta(issueDeltas[i]);
 174     }
 175 }
 176
 177
 178 void
 179 MachineSchedInfo::computeIssueGaps(const vector<InstrRUsage>& instrRUForClasses)
 180 {
 181   int numOpCodes =  mii->getNumRealOpCodes();
 182   instrRUsages.resize(numOpCodes);
 183
 184   assert(numOpCodes < (1 << MAX_OPCODE_SIZE) - 1
 185          && "numOpCodes invalid for implementation of class OpCodePair!");
 186
 187   // First, compute issue gaps between pairs of classes based on common
 188   // resources usages for each class, because most instruction pairs will
 189   // usually behave the same as their class.
 190   //
 191   int classPairGaps[numSchedClasses][numSchedClasses];
 192   for (InstrSchedClass fromSC=0; fromSC < numSchedClasses; fromSC++)
 193     for (InstrSchedClass toSC=0; toSC < numSchedClasses; toSC++)
 194       {
 195         int classPairGap = ComputeMinGap(instrRUForClasses[fromSC],
 196                                       instrRUForClasses[toSC]);
 197         classPairGaps[fromSC][toSC] = classPairGap;
 198       }
 199
 200   // Now, for each pair of instructions, use the class pair gap if both
 201   // instructions have identical resource usage as their respective classes.
 202   // If not, recompute the gap for the pair from scratch.
 203
 204   longestIssueConflict = 0;
 205
 206   for (MachineOpCode fromOp=0; fromOp < numOpCodes; fromOp++)
 207     for (MachineOpCode toOp=0; toOp < numOpCodes; toOp++)
 208     {
 209       int instrPairGap =
 210         (instrRUsages[fromOp].sameAsClass && instrRUsages[toOp].sameAsClass)
 211         ? classPairGaps[getSchedClass(fromOp)][getSchedClass(toOp)]
 212         : ComputeMinGap(instrRUsages[fromOp], instrRUsages[toOp]);
 213
 214       if (instrPairGap > 0)
 215         {
 216           issueGaps[OpCodePair(fromOp,toOp)] = instrPairGap;
 217           conflictLists[fromOp].push_back(toOp);
 218           longestIssueConflict = max(longestIssueConflict, instrPairGap);
 219         }
 220     }
 221 }
 222
 223
 224 // Check if fromRVec and toRVec have *any* common entries.
 225 // Assume the vectors are sorted in increasing order.
 226 // Algorithm copied from function set_intersection() for sorted ranges (stl_algo.h).
 227 inline static bool
 228 RUConflict(const vector<resourceId_t>& fromRVec,
 229            const vector<resourceId_t>& toRVec)
 230 {
 231   bool commonElementFound = false;
 232
 233   unsigned fN = fromRVec.size(), tN = toRVec.size();
 234   unsigned fi = 0, ti = 0;
 235   while (fi < fN && ti < tN)
 236     if (fromRVec[fi] < toRVec[ti])
 237       ++fi;
 238     else if (toRVec[ti] < fromRVec[fi])
 239       ++ti;
 240     else
 241       {
 242         commonElementFound = true;
 243         break;
 244       }
 245
 246   return commonElementFound;
 247 }
 248
 249
 250 static cycles_t
 251 ComputeMinGap(const InstrRUsage& fromRU, const InstrRUsage& toRU)
 252 {
 253   cycles_t minGap = 0;
 254
 255   if (fromRU.numBubbles > 0)
 256     minGap = fromRU.numBubbles;
 257
 258   if (minGap < fromRU.numCycles)
 259     {
 260       // only need to check from cycle `minGap' onwards
 261       for (cycles_t gap=minGap; gap <= fromRU.numCycles-1; gap++)
 262         {
 263           // check if instr. #2 can start executing `gap' cycles after #1
 264           // by checking for resource conflicts in each overlapping cycle
 265           cycles_t numOverlap = min(fromRU.numCycles - gap, toRU.numCycles);
 266           for (cycles_t c = 0; c <= numOverlap-1; c++)
 267             if (RUConflict(fromRU.resourcesByCycle[gap + c],
 268                            toRU.resourcesByCycle[c]))
 269               {// conflict found so minGap must be more than `gap'
 270                 minGap = gap+1;
 271                 break;
 272               }
 273         }
 274     }
 275
 276   return minGap;
 277 }
 278
 279 //---------------------------------------------------------------------------