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