lib/CodeGen/InstrSched/SchedPriorities.cpp

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