include/llvm/Target/TargetSchedInfo.h

   1 //===-- llvm/Target/SchedInfo.h - Target Instruction Sched Info --*- C++ -*-==//
   2 //
   3 // This file describes the target machine to the instruction scheduler.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #ifndef LLVM_TARGET_MACHINESCHEDINFO_H
   8 #define LLVM_TARGET_MACHINESCHEDINFO_H
   9
  10 #include "llvm/Target/MachineInstrInfo.h"
  11 #include <ext/hash_map>
  12
  13 typedef long long cycles_t;
  14 const cycles_t HUGE_LATENCY = ~((long long) 1 << (sizeof(cycles_t)-2));
  15 const cycles_t INVALID_LATENCY = -HUGE_LATENCY;
  16 static const unsigned MAX_OPCODE_SIZE = 16;
  17
  18 class OpCodePair {
  19 public:
  20   long val;                     // make long by concatenating two opcodes
  21   OpCodePair(MachineOpCode op1, MachineOpCode op2)
  22     : val((op1 < 0 || op2 < 0)?
  23         -1 : (long)((((unsigned) op1) << MAX_OPCODE_SIZE) | (unsigned) op2)) {}
  24   bool operator==(const OpCodePair& op) const {
  25     return val == op.val;
  26   }
  27 private:
  28   OpCodePair();                 // disable for now
  29 };
  30
  31 namespace std {
  32 template <> struct hash<OpCodePair> {
  33   size_t operator()(const OpCodePair& pair) const {
  34     return hash<long>()(pair.val);
  35   }
  36 };
  37 }
  38
  39 //---------------------------------------------------------------------------
  40 // class MachineResource
  41 // class CPUResource
  42 //
  43 // Purpose:
  44 //   Representation of a single machine resource used in specifying
  45 //   resource usages of machine instructions for scheduling.
  46 //---------------------------------------------------------------------------
  47
  48
  49 typedef unsigned int resourceId_t;
  50
  51 class MachineResource {
  52 public:
  53   const std::string rname;
  54   resourceId_t rid;
  55
  56   /*ctor*/      MachineResource(const std::string& resourceName)
  57                         : rname(resourceName), rid(nextId++) {}
  58
  59 private:
  60   static resourceId_t nextId;
  61   MachineResource();                    // disable
  62 };
  63
  64
  65 class CPUResource : public MachineResource {
  66 public:
  67   int           maxNumUsers;            // MAXINT if no restriction
  68
  69   /*ctor*/      CPUResource(const std::string& rname, int maxUsers)
  70                         : MachineResource(rname), maxNumUsers(maxUsers) {}
  71 };
  72
  73
  74 //---------------------------------------------------------------------------
  75 // struct InstrClassRUsage
  76 // struct InstrRUsageDelta
  77 // struct InstrIssueDelta
  78 // struct InstrRUsage
  79 //
  80 // Purpose:
  81 //   The first three are structures used to specify machine resource
  82 //   usages for each instruction in a machine description file:
  83 //    InstrClassRUsage : resource usages common to all instrs. in a class
  84 //    InstrRUsageDelta : add/delete resource usage for individual instrs.
  85 //    InstrIssueDelta  : add/delete instr. issue info for individual instrs
  86 //
  87 //   The last one (InstrRUsage) is the internal representation of
  88 //   instruction resource usage constructed from the above three.
  89 //---------------------------------------------------------------------------
  90
  91 const int MAX_NUM_SLOTS  = 32;
  92 const int MAX_NUM_CYCLES = 32;
  93
  94 struct InstrClassRUsage {
  95   InstrSchedClass schedClass;
  96   int           totCycles;
  97
  98   // Issue restrictions common to instructions in this class
  99   unsigned int  maxNumIssue;
 100   bool          isSingleIssue;
 101   bool          breaksGroup;
 102   cycles_t      numBubbles;
 103
 104   // Feasible slots to use for instructions in this class.
 105   // The size of vector S[] is `numSlots'.
 106   unsigned int  numSlots;
 107   unsigned int  feasibleSlots[MAX_NUM_SLOTS];
 108
 109   // Resource usages common to instructions in this class.
 110   // The size of vector V[] is `numRUEntries'.
 111   unsigned int  numRUEntries;
 112   struct {
 113     resourceId_t resourceId;
 114     unsigned int startCycle;
 115     int          numCycles;
 116   }             V[MAX_NUM_CYCLES];
 117 };
 118
 119 struct InstrRUsageDelta {
 120   MachineOpCode opCode;
 121   resourceId_t  resourceId;
 122   unsigned int  startCycle;
 123   int           numCycles;
 124 };
 125
 126 // Specify instruction issue restrictions for individual instructions
 127 // that differ from the common rules for the class.
 128 //
 129 struct InstrIssueDelta {
 130   MachineOpCode opCode;
 131   bool          isSingleIssue;
 132   bool          breaksGroup;
 133   cycles_t      numBubbles;
 134 };
 135
 136
 137 struct InstrRUsage {
 138   /*ctor*/      InstrRUsage     () {}
 139   /*ctor*/      InstrRUsage     (const InstrRUsage& instrRU);
 140   InstrRUsage&  operator=       (const InstrRUsage& instrRU);
 141
 142   bool          sameAsClass;
 143
 144   // Issue restrictions for this instruction
 145   bool          isSingleIssue;
 146   bool          breaksGroup;
 147   cycles_t      numBubbles;
 148
 149   // Feasible slots to use for this instruction.
 150   std::vector<bool> feasibleSlots;
 151
 152   // Resource usages for this instruction, with one resource vector per cycle.
 153   cycles_t      numCycles;
 154   std::vector<std::vector<resourceId_t> > resourcesByCycle;
 155
 156 private:
 157   // Conveniences for initializing this structure
 158   InstrRUsage&  operator=       (const InstrClassRUsage& classRU);
 159   void          addIssueDelta   (const InstrIssueDelta& delta);
 160   void          addUsageDelta   (const InstrRUsageDelta& delta);
 161   void          setMaxSlots     (int maxNumSlots);
 162
 163   friend class MachineSchedInfo;        // give access to these functions
 164 };
 165
 166
 167 inline void
 168 InstrRUsage::setMaxSlots(int maxNumSlots)
 169 {
 170   feasibleSlots.resize(maxNumSlots);
 171 }
 172
 173 inline InstrRUsage&
 174 InstrRUsage::operator=(const InstrRUsage& instrRU)
 175 {
 176   sameAsClass      = instrRU.sameAsClass;
 177   isSingleIssue    = instrRU.isSingleIssue;
 178   breaksGroup      = instrRU.breaksGroup;
 179   numBubbles       = instrRU.numBubbles;
 180   feasibleSlots    = instrRU.feasibleSlots;
 181   numCycles        = instrRU.numCycles;
 182   resourcesByCycle = instrRU.resourcesByCycle;
 183   return *this;
 184 }
 185
 186 inline /*ctor*/
 187 InstrRUsage::InstrRUsage(const InstrRUsage& instrRU)
 188 {
 189   *this = instrRU;
 190 }
 191
 192 inline InstrRUsage&
 193 InstrRUsage::operator=(const InstrClassRUsage& classRU)
 194 {
 195   sameAsClass   = true;
 196   isSingleIssue = classRU.isSingleIssue;
 197   breaksGroup   = classRU.breaksGroup;
 198   numBubbles    = classRU.numBubbles;
 199
 200   for (unsigned i=0; i < classRU.numSlots; i++)
 201     {
 202       unsigned slot = classRU.feasibleSlots[i];
 203       assert(slot < feasibleSlots.size() && "Invalid slot specified!");
 204       this->feasibleSlots[slot] = true;
 205     }
 206
 207   this->numCycles   = classRU.totCycles;
 208   this->resourcesByCycle.resize(this->numCycles);
 209
 210   for (unsigned i=0; i < classRU.numRUEntries; i++)
 211     for (unsigned c=classRU.V[i].startCycle, NC = c + classRU.V[i].numCycles;
 212          c < NC; c++)
 213       this->resourcesByCycle[c].push_back(classRU.V[i].resourceId);
 214
 215   // Sort each resource usage vector by resourceId_t to speed up conflict checking
 216   for (unsigned i=0; i < this->resourcesByCycle.size(); i++)
 217     sort(resourcesByCycle[i].begin(), resourcesByCycle[i].end());
 218
 219   return *this;
 220 }
 221
 222
 223 inline void
 224 InstrRUsage::addIssueDelta(const InstrIssueDelta&  delta)
 225 {
 226   sameAsClass = false;
 227   isSingleIssue = delta.isSingleIssue;
 228   breaksGroup = delta.breaksGroup;
 229   numBubbles = delta.numBubbles;
 230 }
 231
 232
 233 // Add the extra resource usage requirements specified in the delta.
 234 // Note that a negative value of `numCycles' means one entry for that
 235 // resource should be deleted for each cycle.
 236 //
 237 inline void
 238 InstrRUsage::addUsageDelta(const InstrRUsageDelta& delta)
 239 {
 240   int NC = delta.numCycles;
 241
 242   this->sameAsClass = false;
 243
 244   // resize the resources vector if more cycles are specified
 245   unsigned maxCycles = this->numCycles;
 246   maxCycles = std::max(maxCycles, delta.startCycle + abs(NC) - 1);
 247   if (maxCycles > this->numCycles)
 248     {
 249       this->resourcesByCycle.resize(maxCycles);
 250       this->numCycles = maxCycles;
 251     }
 252
 253   if (NC >= 0)
 254     for (unsigned c=delta.startCycle, last=c+NC-1; c <= last; c++)
 255       this->resourcesByCycle[c].push_back(delta.resourceId);
 256   else
 257     // Remove the resource from all NC cycles.
 258     for (unsigned c=delta.startCycle, last=(c-NC)-1; c <= last; c++)
 259       {
 260         // Look for the resource backwards so we remove the last entry
 261         // for that resource in each cycle.
 262         std::vector<resourceId_t>& rvec = this->resourcesByCycle[c];
 263         int r;
 264         for (r = (int) rvec.size(); r >= 0; r--)
 265           if (rvec[r] == delta.resourceId)
 266             {// found last entry for the resource
 267               rvec.erase(rvec.begin() + r);
 268               break;
 269             }
 270         assert(r >= 0 && "Resource to remove was unused in cycle c!");
 271       }
 272 }
 273
 274 //---------------------------------------------------------------------------
 275 // class MachineSchedInfo
 276 //
 277 // Purpose:
 278 //   Common interface to machine information for instruction scheduling
 279 //---------------------------------------------------------------------------
 280
 281 class MachineSchedInfo : public NonCopyableV {
 282 public:
 283   const TargetMachine& target;
 284
 285   unsigned int  maxNumIssueTotal;
 286   int   longestIssueConflict;
 287
 288   int   branchMispredictPenalty;        // 4 for SPARC IIi
 289   int   branchTargetUnknownPenalty;     // 2 for SPARC IIi
 290   int   l1DCacheMissPenalty;            // 7 or 9 for SPARC IIi
 291   int   l1ICacheMissPenalty;            // ? for SPARC IIi
 292
 293   bool  inOrderLoads;                   // true for SPARC IIi
 294   bool  inOrderIssue;                   // true for SPARC IIi
 295   bool  inOrderExec;                    // false for most architectures
 296   bool  inOrderRetire;                  // true for most architectures
 297
 298 protected:
 299   inline const InstrRUsage& getInstrRUsage(MachineOpCode opCode) const {
 300     assert(opCode >= 0 && opCode < (int) instrRUsages.size());
 301     return instrRUsages[opCode];
 302   }
 303   inline const InstrClassRUsage&
 304                         getClassRUsage(const InstrSchedClass& sc) const {
 305     assert(sc >= 0 && sc < numSchedClasses);
 306     return classRUsages[sc];
 307   }
 308
 309 public:
 310   /*ctor*/         MachineSchedInfo     (const TargetMachine& tgt,
 311                                          int                  _numSchedClasses,
 312                                          const InstrClassRUsage* _classRUsages,
 313                                          const InstrRUsageDelta* _usageDeltas,
 314                                          const InstrIssueDelta*  _issueDeltas,
 315                                          unsigned int _numUsageDeltas,
 316                                          unsigned int _numIssueDeltas);
 317   /*dtor*/ virtual ~MachineSchedInfo    () {}
 318
 319   inline const MachineInstrInfo& getInstrInfo() const {
 320     return *mii;
 321   }
 322
 323   inline int            getNumSchedClasses()  const {
 324     return numSchedClasses;
 325   }
 326
 327   inline  unsigned int  getMaxNumIssueTotal() const {
 328     return maxNumIssueTotal;
 329   }
 330
 331   inline  unsigned int  getMaxIssueForClass(const InstrSchedClass& sc) const {
 332     assert(sc >= 0 && sc < numSchedClasses);
 333     return classRUsages[sc].maxNumIssue;
 334   }
 335
 336   inline InstrSchedClass getSchedClass  (MachineOpCode opCode) const {
 337     return getInstrInfo().getSchedClass(opCode);
 338   }
 339
 340   inline  bool  instrCanUseSlot         (MachineOpCode opCode,
 341                                          unsigned s) const {
 342     assert(s < getInstrRUsage(opCode).feasibleSlots.size() && "Invalid slot!");
 343     return getInstrRUsage(opCode).feasibleSlots[s];
 344   }
 345
 346   inline int    getLongestIssueConflict () const {
 347     return longestIssueConflict;
 348   }
 349
 350   inline  int   getMinIssueGap          (MachineOpCode fromOp,
 351                                          MachineOpCode toOp)   const {
 352     std::hash_map<OpCodePair,int>::const_iterator
 353       I = issueGaps.find(OpCodePair(fromOp, toOp));
 354     return (I == issueGaps.end())? 0 : (*I).second;
 355   }
 356
 357   inline const std::vector<MachineOpCode>*
 358                 getConflictList(MachineOpCode opCode) const {
 359     std::hash_map<MachineOpCode, std::vector<MachineOpCode> >::const_iterator
 360       I = conflictLists.find(opCode);
 361     return (I == conflictLists.end())? NULL : & (*I).second;
 362   }
 363
 364   inline  bool  isSingleIssue           (MachineOpCode opCode) const {
 365     return getInstrRUsage(opCode).isSingleIssue;
 366   }
 367
 368   inline  bool  breaksIssueGroup        (MachineOpCode opCode) const {
 369     return getInstrRUsage(opCode).breaksGroup;
 370   }
 371
 372   inline  unsigned int  numBubblesAfter (MachineOpCode opCode) const {
 373     return getInstrRUsage(opCode).numBubbles;
 374   }
 375
 376 protected:
 377   virtual void  initializeResources     ();
 378
 379 private:
 380   void computeInstrResources(const std::vector<InstrRUsage>& instrRUForClasses);
 381   void computeIssueGaps(const std::vector<InstrRUsage>& instrRUForClasses);
 382
 383 protected:
 384   int                      numSchedClasses;
 385   const MachineInstrInfo*  mii;
 386   const InstrClassRUsage*  classRUsages;        // raw array by sclass
 387   const InstrRUsageDelta*  usageDeltas;         // raw array [1:numUsageDeltas]
 388   const InstrIssueDelta*   issueDeltas;         // raw array [1:numIssueDeltas]
 389   unsigned int             numUsageDeltas;
 390   unsigned int             numIssueDeltas;
 391
 392   std::vector<InstrRUsage>      instrRUsages;   // indexed by opcode
 393   std::hash_map<OpCodePair,int> issueGaps;      // indexed by opcode pair
 394   std::hash_map<MachineOpCode, std::vector<MachineOpCode> >
 395                            conflictLists;       // indexed by opcode
 396 };
 397
 398 #endif