include/llvm/Target/TargetSchedInfo.h

   1 //===- Target/MachineSchedInfo.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 <ext/hash_map>
  11 #include "llvm/Target/MachineInstrInfo.h"
  12
  13 typedef long long cycles_t;
  14 static const cycles_t HUGE_LATENCY = ~((long long) 1 << (sizeof(cycles_t)-2));
  15 static 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 resourceId_t;
  50
  51 struct MachineResource {
  52   const std::string rname;
  53   resourceId_t rid;
  54
  55   MachineResource(const std::string &resourceName)
  56     : rname(resourceName), rid(nextId++) {}
  57
  58 private:
  59   static resourceId_t nextId;
  60   MachineResource();                    // disable
  61 };
  62
  63
  64 struct CPUResource : public MachineResource {
  65   int maxNumUsers;   // MAXINT if no restriction
  66
  67   CPUResource(const std::string& rname, int maxUsers)
  68     : MachineResource(rname), maxNumUsers(maxUsers) {}
  69 };
  70
  71
  72 //---------------------------------------------------------------------------
  73 // struct InstrClassRUsage
  74 // struct InstrRUsageDelta
  75 // struct InstrIssueDelta
  76 // struct InstrRUsage
  77 //
  78 // Purpose:
  79 //   The first three are structures used to specify machine resource
  80 //   usages for each instruction in a machine description file:
  81 //    InstrClassRUsage : resource usages common to all instrs. in a class
  82 //    InstrRUsageDelta : add/delete resource usage for individual instrs.
  83 //    InstrIssueDelta  : add/delete instr. issue info for individual instrs
  84 //
  85 //   The last one (InstrRUsage) is the internal representation of
  86 //   instruction resource usage constructed from the above three.
  87 //---------------------------------------------------------------------------
  88
  89 const int MAX_NUM_SLOTS  = 32;
  90 const int MAX_NUM_CYCLES = 32;
  91
  92 struct InstrClassRUsage {
  93   InstrSchedClass schedClass;
  94   int           totCycles;
  95
  96   // Issue restrictions common to instructions in this class
  97   unsigned      maxNumIssue;
  98   bool          isSingleIssue;
  99   bool          breaksGroup;
 100   cycles_t      numBubbles;
 101
 102   // Feasible slots to use for instructions in this class.
 103   // The size of vector S[] is `numSlots'.
 104   unsigned      numSlots;
 105   unsigned      feasibleSlots[MAX_NUM_SLOTS];
 106
 107   // Resource usages common to instructions in this class.
 108   // The size of vector V[] is `numRUEntries'.
 109   unsigned      numRUEntries;
 110   struct {
 111     resourceId_t resourceId;
 112     unsigned    startCycle;
 113     int         numCycles;
 114   } V[MAX_NUM_CYCLES];
 115 };
 116
 117 struct InstrRUsageDelta {
 118   MachineOpCode opCode;
 119   resourceId_t  resourceId;
 120   unsigned      startCycle;
 121   int           numCycles;
 122 };
 123
 124 // Specify instruction issue restrictions for individual instructions
 125 // that differ from the common rules for the class.
 126 //
 127 struct InstrIssueDelta {
 128   MachineOpCode opCode;
 129   bool          isSingleIssue;
 130   bool          breaksGroup;
 131   cycles_t      numBubbles;
 132 };
 133
 134
 135 struct InstrRUsage {
 136   bool          sameAsClass;
 137
 138   // Issue restrictions for this instruction
 139   bool          isSingleIssue;
 140   bool          breaksGroup;
 141   cycles_t      numBubbles;
 142
 143   // Feasible slots to use for this instruction.
 144   std::vector<bool> feasibleSlots;
 145
 146   // Resource usages for this instruction, with one resource vector per cycle.
 147   cycles_t      numCycles;
 148   std::vector<std::vector<resourceId_t> > resourcesByCycle;
 149
 150 private:
 151   // Conveniences for initializing this structure
 152   void setTo(const InstrClassRUsage& classRU);
 153
 154   void addIssueDelta(const InstrIssueDelta& delta) {
 155     sameAsClass = false;
 156     isSingleIssue = delta.isSingleIssue;
 157     breaksGroup = delta.breaksGroup;
 158     numBubbles = delta.numBubbles;
 159   }
 160
 161   void addUsageDelta    (const InstrRUsageDelta& delta);
 162   void setMaxSlots      (int maxNumSlots) {
 163     feasibleSlots.resize(maxNumSlots);
 164   }
 165
 166   friend class MachineSchedInfo;        // give access to these functions
 167 };
 168
 169
 170 //---------------------------------------------------------------------------
 171 // class MachineSchedInfo
 172 //
 173 // Purpose:
 174 //   Common interface to machine information for instruction scheduling
 175 //---------------------------------------------------------------------------
 176
 177 class MachineSchedInfo : public NonCopyableV {
 178 public:
 179   const TargetMachine& target;
 180
 181   unsigned maxNumIssueTotal;
 182   int   longestIssueConflict;
 183
 184   int   branchMispredictPenalty;        // 4 for SPARC IIi
 185   int   branchTargetUnknownPenalty;     // 2 for SPARC IIi
 186   int   l1DCacheMissPenalty;            // 7 or 9 for SPARC IIi
 187   int   l1ICacheMissPenalty;            // ? for SPARC IIi
 188
 189   bool  inOrderLoads;                   // true for SPARC IIi
 190   bool  inOrderIssue;                   // true for SPARC IIi
 191   bool  inOrderExec;                    // false for most architectures
 192   bool  inOrderRetire;                  // true for most architectures
 193
 194 protected:
 195   inline const InstrRUsage& getInstrRUsage(MachineOpCode opCode) const {
 196     assert(opCode >= 0 && opCode < (int) instrRUsages.size());
 197     return instrRUsages[opCode];
 198   }
 199   inline const InstrClassRUsage&
 200                         getClassRUsage(const InstrSchedClass& sc) const {
 201     assert(sc >= 0 && sc < numSchedClasses);
 202     return classRUsages[sc];
 203   }
 204
 205 public:
 206   /*ctor*/         MachineSchedInfo     (const TargetMachine& tgt,
 207                                          int                  _numSchedClasses,
 208                                          const InstrClassRUsage* _classRUsages,
 209                                          const InstrRUsageDelta* _usageDeltas,
 210                                          const InstrIssueDelta*  _issueDeltas,
 211                                          unsigned _numUsageDeltas,
 212                                          unsigned _numIssueDeltas);
 213   /*dtor*/ virtual ~MachineSchedInfo    () {}
 214
 215   inline const MachineInstrInfo& getInstrInfo() const {
 216     return *mii;
 217   }
 218
 219   inline int            getNumSchedClasses()  const {
 220     return numSchedClasses;
 221   }
 222
 223   inline  unsigned getMaxNumIssueTotal() const {
 224     return maxNumIssueTotal;
 225   }
 226
 227   inline  unsigned getMaxIssueForClass(const InstrSchedClass& sc) const {
 228     assert(sc >= 0 && sc < numSchedClasses);
 229     return classRUsages[sc].maxNumIssue;
 230   }
 231
 232   inline InstrSchedClass getSchedClass  (MachineOpCode opCode) const {
 233     return getInstrInfo().getSchedClass(opCode);
 234   }
 235
 236   inline  bool  instrCanUseSlot         (MachineOpCode opCode,
 237                                          unsigned s) const {
 238     assert(s < getInstrRUsage(opCode).feasibleSlots.size() && "Invalid slot!");
 239     return getInstrRUsage(opCode).feasibleSlots[s];
 240   }
 241
 242   inline int    getLongestIssueConflict () const {
 243     return longestIssueConflict;
 244   }
 245
 246   inline  int   getMinIssueGap          (MachineOpCode fromOp,
 247                                          MachineOpCode toOp)   const {
 248     std::hash_map<OpCodePair,int>::const_iterator
 249       I = issueGaps.find(OpCodePair(fromOp, toOp));
 250     return (I == issueGaps.end())? 0 : (*I).second;
 251   }
 252
 253   inline const std::vector<MachineOpCode>*
 254                 getConflictList(MachineOpCode opCode) const {
 255     std::hash_map<MachineOpCode, std::vector<MachineOpCode> >::const_iterator
 256       I = conflictLists.find(opCode);
 257     return (I == conflictLists.end())? NULL : & (*I).second;
 258   }
 259
 260   inline  bool  isSingleIssue           (MachineOpCode opCode) const {
 261     return getInstrRUsage(opCode).isSingleIssue;
 262   }
 263
 264   inline  bool  breaksIssueGroup        (MachineOpCode opCode) const {
 265     return getInstrRUsage(opCode).breaksGroup;
 266   }
 267
 268   inline  unsigned numBubblesAfter      (MachineOpCode opCode) const {
 269     return getInstrRUsage(opCode).numBubbles;
 270   }
 271
 272 protected:
 273   virtual void  initializeResources     ();
 274
 275 private:
 276   void computeInstrResources(const std::vector<InstrRUsage>& instrRUForClasses);
 277   void computeIssueGaps(const std::vector<InstrRUsage>& instrRUForClasses);
 278
 279 protected:
 280   int                      numSchedClasses;
 281   const MachineInstrInfo*  mii;
 282   const InstrClassRUsage*  classRUsages;        // raw array by sclass
 283   const InstrRUsageDelta*  usageDeltas;         // raw array [1:numUsageDeltas]
 284   const InstrIssueDelta*   issueDeltas;         // raw array [1:numIssueDeltas]
 285   unsigned                 numUsageDeltas;
 286   unsigned                 numIssueDeltas;
 287
 288   std::vector<InstrRUsage>      instrRUsages;   // indexed by opcode
 289   std::hash_map<OpCodePair,int> issueGaps;      // indexed by opcode pair
 290   std::hash_map<MachineOpCode, std::vector<MachineOpCode> >
 291                            conflictLists;       // indexed by opcode
 292 };
 293
 294 #endif