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