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