lib/Target/SparcV9/InstrSched/SchedPriorities.h

   1 // -*-C++-*-
   2 //***************************************************************************
   3 // File:
   4 //      SchedPriorities.h
   5 //
   6 // Purpose:
   7 //      Encapsulate heuristics for instruction scheduling.
   8 //
   9 // Strategy:
  10 //    Priority ordering rules:
  11 //    (1) Max delay, which is the order of the heap S.candsAsHeap.
  12 //    (2) Instruction that frees up a register.
  13 //    (3) Instruction that has the maximum number of dependent instructions.
  14 //    Note that rules 2 and 3 are only used if issue conflicts prevent
  15 //    choosing a higher priority instruction by rule 1.
  16 //
  17 // History:
  18 //      7/30/01  -  Vikram Adve  -  Created
  19 //**************************************************************************/
  20
  21 #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
  22 #define LLVM_CODEGEN_SCHEDPRIORITIES_H
  23
  24 #include "SchedGraph.h"
  25 #include "llvm/CodeGen/InstrScheduling.h"
  26 #include "llvm/Target/MachineSchedInfo.h"
  27 #include "Support/CommandLine.h"
  28 #include <list>
  29 #include <hash_set>
  30 class Method;
  31 class MachineInstr;
  32 class SchedulingManager;
  33 class MethodLiveVarInfo;
  34
  35 //---------------------------------------------------------------------------
  36 // Debug option levels for instruction scheduling
  37
  38 enum SchedDebugLevel_t {
  39   Sched_NoDebugInfo,
  40   Sched_PrintMachineCode,
  41   Sched_PrintSchedTrace,
  42   Sched_PrintSchedGraphs,
  43 };
  44
  45 extern cl::Enum<SchedDebugLevel_t> SchedDebugLevel;
  46
  47 //---------------------------------------------------------------------------
  48 // Function: instrIsFeasible
  49 //
  50 // Purpose:
  51 //   Used by the priority analysis to filter out instructions
  52 //   that are not feasible to issue in the current cycle.
  53 //   Should only be used during schedule construction..
  54 //---------------------------------------------------------------------------
  55
  56 bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
  57
  58
  59
  60 struct NodeDelayPair {
  61   const SchedGraphNode* node;
  62   cycles_t delay;
  63   NodeDelayPair(const SchedGraphNode* n, cycles_t d) :  node(n), delay(d) {}
  64   inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
  65 };
  66
  67 inline bool
  68 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
  69 {
  70   return np1->delay < np2->delay;
  71 }
  72
  73 class NodeHeap: public std::list<NodeDelayPair*>, public NonCopyable {
  74 public:
  75   typedef std::list<NodeDelayPair*>::iterator iterator;
  76   typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
  77
  78 public:
  79   NodeHeap() : _size(0) {}
  80
  81   inline unsigned       size() const { return _size; }
  82
  83   const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
  84   cycles_t              getDelay(const_iterator i) const { return (*i)->delay;}
  85
  86   inline void           makeHeap() {
  87     // make_heap(begin(), end(), NDPLessThan);
  88   }
  89
  90   inline iterator       findNode(const SchedGraphNode* node) {
  91     for (iterator I=begin(); I != end(); ++I)
  92       if (getNode(I) == node)
  93         return I;
  94     return end();
  95   }
  96
  97   inline void     removeNode    (const SchedGraphNode* node) {
  98     iterator ndpPtr = findNode(node);
  99     if (ndpPtr != end())
 100       {
 101         delete *ndpPtr;
 102         erase(ndpPtr);
 103         --_size;
 104       }
 105   };
 106
 107   void            insert(const SchedGraphNode* node, cycles_t delay) {
 108     NodeDelayPair* ndp = new NodeDelayPair(node, delay);
 109     if (_size == 0 || front()->delay < delay)
 110       push_front(ndp);
 111     else
 112       {
 113         iterator I=begin();
 114         for ( ; I != end() && getDelay(I) >= delay; ++I)
 115           ;
 116         std::list<NodeDelayPair*>::insert(I, ndp);
 117       }
 118     _size++;
 119   }
 120 private:
 121   unsigned int _size;
 122 };
 123
 124
 125 class SchedPriorities: public NonCopyable {
 126 public:
 127   SchedPriorities(const Method *M, const SchedGraph *G, MethodLiveVarInfo &LVI);
 128
 129
 130   // This must be called before scheduling begins.
 131   void          initialize              ();
 132
 133   cycles_t      getTime                 () const { return curTime; }
 134   cycles_t      getEarliestReadyTime    () const { return earliestReadyTime; }
 135   unsigned      getNumReady             () const { return candsAsHeap.size(); }
 136   bool          nodeIsReady             (const SchedGraphNode* node) const {
 137     return (candsAsSet.find(node) != candsAsSet.end());
 138   }
 139
 140   void          issuedReadyNodeAt       (cycles_t curTime,
 141                                          const SchedGraphNode* node);
 142
 143   void          insertReady             (const SchedGraphNode* node);
 144
 145   void          updateTime              (cycles_t /*unused*/);
 146
 147   const SchedGraphNode* getNextHighest  (const SchedulingManager& S,
 148                                          cycles_t curTime);
 149                                         // choose next highest priority instr
 150
 151 private:
 152   typedef NodeHeap::iterator candIndex;
 153
 154 private:
 155   cycles_t curTime;
 156   const SchedGraph* graph;
 157   MethodLiveVarInfo &methodLiveVarInfo;
 158   std::hash_map<const MachineInstr*, bool> lastUseMap;
 159   std::vector<cycles_t> nodeDelayVec;
 160   std::vector<cycles_t> earliestForNode;
 161   cycles_t earliestReadyTime;
 162   NodeHeap candsAsHeap;                         // candidate nodes, ready to go
 163   std::hash_set<const SchedGraphNode*> candsAsSet;//same entries as candsAsHeap,
 164                                                 //   but as set for fast lookup
 165   std::vector<candIndex> mcands;                // holds pointers into cands
 166   candIndex nextToTry;                          // next cand after the last
 167                                                 //   one tried in this cycle
 168
 169   int           chooseByRule1           (std::vector<candIndex>& mcands);
 170   int           chooseByRule2           (std::vector<candIndex>& mcands);
 171   int           chooseByRule3           (std::vector<candIndex>& mcands);
 172
 173   void          findSetWithMaxDelay     (std::vector<candIndex>& mcands,
 174                                          const SchedulingManager& S);
 175
 176   void          computeDelays           (const SchedGraph* graph);
 177
 178   void          initializeReadyHeap     (const SchedGraph* graph);
 179
 180   bool          instructionHasLastUse   (MethodLiveVarInfo& methodLiveVarInfo,
 181                                          const SchedGraphNode* graphNode);
 182
 183   // NOTE: The next two return references to the actual vector entries.
 184   //       Use with care.
 185   cycles_t&     getNodeDelayRef         (const SchedGraphNode* node) {
 186     assert(node->getNodeId() < nodeDelayVec.size());
 187     return nodeDelayVec[node->getNodeId()];
 188   }
 189   cycles_t&     getEarliestForNodeRef   (const SchedGraphNode* node) {
 190     assert(node->getNodeId() < earliestForNode.size());
 191     return earliestForNode[node->getNodeId()];
 192   }
 193 };
 194
 195
 196 inline void SchedPriorities::updateTime(cycles_t c) {
 197   curTime = c;
 198   nextToTry = candsAsHeap.begin();
 199   mcands.clear();
 200 }
 201
 202 inline std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd) {
 203   return os << "Delay for node " << nd->node->getNodeId()
 204             << " = " << (long)nd->delay << "\n";
 205 }
 206
 207 #endif