lib/CodeGen/InstrSched/SchedPriorities.cpp

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