lib/CodeGen/InstrSched/SchedPriorities.cpp

   1 // $Id$ -*-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 #include "SchedPriorities.h"
  22 #include "llvm/Support/PostOrderIterator.h"
  23
  24
  25 SchedPriorities::SchedPriorities(const Method* method,
  26                                  const SchedGraph* _graph)
  27   : curTime(0),
  28     graph(_graph),
  29     methodLiveVarInfo(method),                           // expensive!
  30     lastUseMap(),
  31     nodeDelayVec(_graph->getNumNodes(),INVALID_LATENCY), //make errors obvious
  32     earliestForNode(_graph->getNumNodes(), 0),
  33     earliestReadyTime(0),
  34     candsAsHeap(),
  35     candsAsSet(),
  36     mcands(),
  37     nextToTry(candsAsHeap.begin())
  38 {
  39   methodLiveVarInfo.analyze();
  40   computeDelays(graph);
  41 }
  42
  43
  44 void
  45 SchedPriorities::initialize()
  46 {
  47   initializeReadyHeap(graph);
  48 }
  49
  50
  51 void
  52 SchedPriorities::computeDelays(const SchedGraph* graph)
  53 {
  54   po_iterator<const SchedGraph*> poIter = po_begin(graph), poEnd =po_end(graph);
  55   for ( ; poIter != poEnd; ++poIter)
  56     {
  57       const SchedGraphNode* node = *poIter;
  58       cycles_t nodeDelay;
  59       if (node->beginOutEdges() == node->endOutEdges())
  60         nodeDelay = node->getLatency();
  61       else
  62         {
  63           // Iterate over the out-edges of the node to compute delay
  64           nodeDelay = 0;
  65           for (SchedGraphNode::const_iterator E=node->beginOutEdges();
  66                E != node->endOutEdges(); ++E)
  67             {
  68               cycles_t sinkDelay = getNodeDelayRef((*E)->getSink());
  69               nodeDelay = max(nodeDelay, sinkDelay + (*E)->getMinDelay());
  70             }
  71         }
  72       getNodeDelayRef(node) = nodeDelay;
  73     }
  74 }
  75
  76
  77 void
  78 SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
  79 {
  80   const SchedGraphNode* graphRoot = graph->getRoot();
  81   assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
  82
  83   // Insert immediate successors of dummy root, which are the actual roots
  84   sg_succ_const_iterator SEnd = succ_end(graphRoot);
  85   for (sg_succ_const_iterator S = succ_begin(graphRoot); S != SEnd; ++S)
  86     this->insertReady(*S);
  87
  88 #undef TEST_HEAP_CONVERSION
  89 #ifdef TEST_HEAP_CONVERSION
  90   cout << "Before heap conversion:" << endl;
  91   copy(candsAsHeap.begin(), candsAsHeap.end(),
  92        ostream_iterator<NodeDelayPair*>(cout,"\n"));
  93 #endif
  94
  95   candsAsHeap.makeHeap();
  96
  97 #ifdef TEST_HEAP_CONVERSION
  98   cout << "After heap conversion:" << endl;
  99   copy(candsAsHeap.begin(), candsAsHeap.end(),
 100        ostream_iterator<NodeDelayPair*>(cout,"\n"));
 101 #endif
 102 }
 103
 104
 105 void
 106 SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
 107                                    const SchedGraphNode* node)
 108 {
 109   candsAsHeap.removeNode(node);
 110   candsAsSet.erase(node);
 111   mcands.clear(); // ensure reset choices is called before any more choices
 112
 113   if (earliestReadyTime == getEarliestForNodeRef(node))
 114     {// earliestReadyTime may have been due to this node, so recompute it
 115       earliestReadyTime = HUGE_LATENCY;
 116       for (NodeHeap::const_iterator I=candsAsHeap.begin();
 117            I != candsAsHeap.end(); ++I)
 118         if (candsAsHeap.getNode(I))
 119           earliestReadyTime = min(earliestReadyTime,
 120                                 getEarliestForNodeRef(candsAsHeap.getNode(I)));
 121     }
 122
 123   // Now update ready times for successors
 124   for (SchedGraphNode::const_iterator E=node->beginOutEdges();
 125        E != node->endOutEdges(); ++E)
 126     {
 127       cycles_t& etime = getEarliestForNodeRef((*E)->getSink());
 128       etime = max(etime, curTime + (*E)->getMinDelay());
 129     }
 130 }
 131
 132
 133 //----------------------------------------------------------------------
 134 // Priority ordering rules:
 135 // (1) Max delay, which is the order of the heap S.candsAsHeap.
 136 // (2) Instruction that frees up a register.
 137 // (3) Instruction that has the maximum number of dependent instructions.
 138 // Note that rules 2 and 3 are only used if issue conflicts prevent
 139 // choosing a higher priority instruction by rule 1.
 140 //----------------------------------------------------------------------
 141
 142 inline int
 143 SchedPriorities::chooseByRule1(vector<candIndex>& mcands)
 144 {
 145   return (mcands.size() == 1)? 0        // only one choice exists so take it
 146                              : -1;      // -1 indicates multiple choices
 147 }
 148
 149 inline int
 150 SchedPriorities::chooseByRule2(vector<candIndex>& mcands)
 151 {
 152   assert(mcands.size() >= 1 && "Should have at least one candidate here.");
 153   for (unsigned i=0, N = mcands.size(); i < N; i++)
 154     if (instructionHasLastUse(methodLiveVarInfo,
 155                               candsAsHeap.getNode(mcands[i])))
 156       return i;
 157   return -1;
 158 }
 159
 160 inline int
 161 SchedPriorities::chooseByRule3(vector<candIndex>& mcands)
 162 {
 163   assert(mcands.size() >= 1 && "Should have at least one candidate here.");
 164   int maxUses = candsAsHeap.getNode(mcands[0])->getNumOutEdges();
 165   int indexWithMaxUses = 0;
 166   for (unsigned i=1, N = mcands.size(); i < N; i++)
 167     {
 168       int numUses = candsAsHeap.getNode(mcands[i])->getNumOutEdges();
 169       if (numUses > maxUses)
 170         {
 171           maxUses = numUses;
 172           indexWithMaxUses = i;
 173         }
 174     }
 175   return indexWithMaxUses;
 176 }
 177
 178 const SchedGraphNode*
 179 SchedPriorities::getNextHighest(const SchedulingManager& S,
 180                                 cycles_t curTime)
 181 {
 182   int nextIdx = -1;
 183   const SchedGraphNode* nextChoice = NULL;
 184
 185   if (mcands.size() == 0)
 186     findSetWithMaxDelay(mcands, S);
 187
 188   while (nextIdx < 0 && mcands.size() > 0)
 189     {
 190       nextIdx = chooseByRule1(mcands);   // rule 1
 191
 192       if (nextIdx == -1)
 193         nextIdx = chooseByRule2(mcands); // rule 2
 194
 195       if (nextIdx == -1)
 196         nextIdx = chooseByRule3(mcands); // rule 3
 197
 198       if (nextIdx == -1)
 199         nextIdx = 0;                     // default to first choice by delays
 200
 201       // We have found the next best candidate.  Check if it ready in
 202       // the current cycle, and if it is feasible.
 203       // If not, remove it from mcands and continue.  Refill mcands if
 204       // it becomes empty.
 205       nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
 206       if (getEarliestForNodeRef(nextChoice) > curTime
 207           || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
 208         {
 209           mcands.erase(mcands.begin() + nextIdx);
 210           nextIdx = -1;
 211           if (mcands.size() == 0)
 212             findSetWithMaxDelay(mcands, S);
 213         }
 214     }
 215
 216   if (nextIdx >= 0)
 217     {
 218       mcands.erase(mcands.begin() + nextIdx);
 219       return nextChoice;
 220     }
 221   else
 222     return NULL;
 223 }
 224
 225
 226 void
 227 SchedPriorities::findSetWithMaxDelay(vector<candIndex>& mcands,
 228                                      const SchedulingManager& S)
 229 {
 230   if (mcands.size() == 0 && nextToTry != candsAsHeap.end())
 231     { // out of choices at current maximum delay;
 232       // put nodes with next highest delay in mcands
 233       candIndex next = nextToTry;
 234       cycles_t maxDelay = candsAsHeap.getDelay(next);
 235       for (; next != candsAsHeap.end()
 236              && candsAsHeap.getDelay(next) == maxDelay; ++next)
 237         mcands.push_back(next);
 238
 239       nextToTry = next;
 240
 241       if (SchedDebugLevel >= Sched_PrintSchedTrace)
 242         {
 243           cout << "    Cycle " << this->getTime() << ": "
 244                << "Next highest delay = " << maxDelay << " : "
 245                << mcands.size() << " Nodes with this delay: ";
 246           for (unsigned i=0; i < mcands.size(); i++)
 247             cout << candsAsHeap.getNode(mcands[i])->getNodeId() << ", ";
 248           cout << endl;
 249         }
 250     }
 251 }
 252
 253
 254 bool
 255 SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo,
 256                                        const SchedGraphNode* graphNode)
 257 {
 258   const MachineInstr* minstr = graphNode->getMachineInstr();
 259
 260   hash_map<const MachineInstr*, bool>::const_iterator
 261     ui = lastUseMap.find(minstr);
 262   if (ui != lastUseMap.end())
 263     return (*ui).second;
 264
 265   // else check if instruction is a last use and save it in the hash_map
 266   bool hasLastUse = false;
 267   const BasicBlock* bb = graphNode->getBB();
 268   const LiveVarSet* liveVars =
 269     methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb);
 270
 271   for (MachineInstr::val_op_const_iterator vo(minstr); ! vo.done(); ++vo)
 272     if (liveVars->find(*vo) == liveVars->end())
 273       {
 274         hasLastUse = true;
 275         break;
 276       }
 277
 278   lastUseMap[minstr] = hasLastUse;
 279   return hasLastUse;
 280 }
 281