lib/CodeGen/LatencyPriorityQueue.cpp

   1 //===---- LatencyPriorityQueue.cpp - A latency-oriented priority queue ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LatencyPriorityQueue class, which is a
  11 // SchedulingPriorityQueue that schedules using latency information to
  12 // reduce the length of the critical path through the basic block.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "scheduler"
  17 #include "llvm/CodeGen/LatencyPriorityQueue.h"
  18 #include "llvm/Support/Debug.h"
  19 using namespace llvm;
  20
  21 bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
  22   unsigned LHSNum = LHS->NodeNum;
  23   unsigned RHSNum = RHS->NodeNum;
  24
  25   // The most important heuristic is scheduling the critical path.
  26   unsigned LHSLatency = PQ->getLatency(LHSNum);
  27   unsigned RHSLatency = PQ->getLatency(RHSNum);
  28   if (LHSLatency < RHSLatency) return true;
  29   if (LHSLatency > RHSLatency) return false;
  30
  31   // After that, if two nodes have identical latencies, look to see if one will
  32   // unblock more other nodes than the other.
  33   unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
  34   unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
  35   if (LHSBlocked < RHSBlocked) return true;
  36   if (LHSBlocked > RHSBlocked) return false;
  37
  38   // Finally, just to provide a stable ordering, use the node number as a
  39   // deciding factor.
  40   return LHSNum < RHSNum;
  41 }
  42
  43
  44 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
  45 /// of SU, return it, otherwise return null.
  46 SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
  47   SUnit *OnlyAvailablePred = 0;
  48   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
  49        I != E; ++I) {
  50     SUnit &Pred = *I->getSUnit();
  51     if (!Pred.isScheduled) {
  52       // We found an available, but not scheduled, predecessor.  If it's the
  53       // only one we have found, keep track of it... otherwise give up.
  54       if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
  55         return 0;
  56       OnlyAvailablePred = &Pred;
  57     }
  58   }
  59
  60   return OnlyAvailablePred;
  61 }
  62
  63 void LatencyPriorityQueue::push_impl(SUnit *SU) {
  64   // Look at all of the successors of this node.  Count the number of nodes that
  65   // this node is the sole unscheduled node for.
  66   unsigned NumNodesBlocking = 0;
  67   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
  68        I != E; ++I)
  69     if (getSingleUnscheduledPred(I->getSUnit()) == SU)
  70       ++NumNodesBlocking;
  71   NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
  72
  73   Queue.push(SU);
  74 }
  75
  76
  77 // ScheduledNode - As nodes are scheduled, we look to see if there are any
  78 // successor nodes that have a single unscheduled predecessor.  If so, that
  79 // single predecessor has a higher priority, since scheduling it will make
  80 // the node available.
  81 void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
  82   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
  83        I != E; ++I)
  84     AdjustPriorityOfUnscheduledPreds(I->getSUnit());
  85 }
  86
  87 /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
  88 /// scheduled.  If SU is not itself available, then there is at least one
  89 /// predecessor node that has not been scheduled yet.  If SU has exactly ONE
  90 /// unscheduled predecessor, we want to increase its priority: it getting
  91 /// scheduled will make this node available, so it is better than some other
  92 /// node of the same priority that will not make a node available.
  93 void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
  94   if (SU->isAvailable) return;  // All preds scheduled.
  95
  96   SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
  97   if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return;
  98
  99   // Okay, we found a single predecessor that is available, but not scheduled.
 100   // Since it is available, it must be in the priority queue.  First remove it.
 101   remove(OnlyAvailablePred);
 102
 103   // Reinsert the node into the priority queue, which recomputes its
 104   // NumNodesSolelyBlocking value.
 105   push(OnlyAvailablePred);
 106 }