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