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