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