lib/CodeGen/InstrSched/SchedPriorities.h

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