ScheduleDAG.cpp revision bae5210321e0c3ea28723334841555135a61e915 
1//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===//
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 implements the ScheduleDAG class, which is a base class used by
11// scheduling implementation classes.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "pre-RA-sched"
16#include "llvm/CodeGen/ScheduleDAG.h"
17#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
18#include "llvm/Target/TargetMachine.h"
19#include "llvm/Target/TargetInstrInfo.h"
20#include "llvm/Target/TargetRegisterInfo.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/raw_ostream.h"
23#include <climits>
24using namespace llvm;
25
26ScheduleDAG::ScheduleDAG(MachineFunction &mf)
27  : TM(mf.getTarget()),
28    TII(TM.getInstrInfo()),
29    TRI(TM.getRegisterInfo()),
30    MF(mf), MRI(mf.getRegInfo()),
31    EntrySU(), ExitSU() {
32}
33
34ScheduleDAG::~ScheduleDAG() {}
35
36/// dump - dump the schedule.
37void ScheduleDAG::dumpSchedule() const {
38  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
39    if (SUnit *SU = Sequence[i])
40      SU->dump(this);
41    else
42      dbgs() << "**** NOOP ****\n";
43  }
44}
45
46
47/// Run - perform scheduling.
48///
49void ScheduleDAG::Run(MachineBasicBlock *bb,
50                      MachineBasicBlock::iterator insertPos) {
51  BB = bb;
52  InsertPos = insertPos;
53
54  SUnits.clear();
55  Sequence.clear();
56  EntrySU = SUnit();
57  ExitSU = SUnit();
58
59  Schedule();
60
61  DEBUG({
62      dbgs() << "*** Final schedule ***\n";
63      dumpSchedule();
64      dbgs() << '\n';
65    });
66}
67
68/// addPred - This adds the specified edge as a pred of the current node if
69/// not already.  It also adds the current node as a successor of the
70/// specified node.
71void SUnit::addPred(const SDep &D) {
72  // If this node already has this depenence, don't add a redundant one.
73  for (SmallVector<SDep, 4>::const_iterator I = Preds.begin(), E = Preds.end();
74       I != E; ++I)
75    if (*I == D)
76      return;
77  // Now add a corresponding succ to N.
78  SDep P = D;
79  P.setSUnit(this);
80  SUnit *N = D.getSUnit();
81  // Update the bookkeeping.
82  if (D.getKind() == SDep::Data) {
83    assert(NumPreds < UINT_MAX && "NumPreds will overflow!");
84    assert(N->NumSuccs < UINT_MAX && "NumSuccs will overflow!");
85    ++NumPreds;
86    ++N->NumSuccs;
87  }
88  if (!N->isScheduled) {
89    assert(NumPredsLeft < UINT_MAX && "NumPredsLeft will overflow!");
90    ++NumPredsLeft;
91  }
92  if (!isScheduled) {
93    assert(N->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
94    ++N->NumSuccsLeft;
95  }
96  Preds.push_back(D);
97  N->Succs.push_back(P);
98  if (P.getLatency() != 0) {
99    this->setDepthDirty();
100    N->setHeightDirty();
101  }
102}
103
104/// removePred - This removes the specified edge as a pred of the current
105/// node if it exists.  It also removes the current node as a successor of
106/// the specified node.
107void SUnit::removePred(const SDep &D) {
108  // Find the matching predecessor.
109  for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
110       I != E; ++I)
111    if (*I == D) {
112      bool FoundSucc = false;
113      // Find the corresponding successor in N.
114      SDep P = D;
115      P.setSUnit(this);
116      SUnit *N = D.getSUnit();
117      for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
118             EE = N->Succs.end(); II != EE; ++II)
119        if (*II == P) {
120          FoundSucc = true;
121          N->Succs.erase(II);
122          break;
123        }
124      assert(FoundSucc && "Mismatching preds / succs lists!");
125      Preds.erase(I);
126      // Update the bookkeeping.
127      if (P.getKind() == SDep::Data) {
128        assert(NumPreds > 0 && "NumPreds will underflow!");
129        assert(N->NumSuccs > 0 && "NumSuccs will underflow!");
130        --NumPreds;
131        --N->NumSuccs;
132      }
133      if (!N->isScheduled) {
134        assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!");
135        --NumPredsLeft;
136      }
137      if (!isScheduled) {
138        assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");
139        --N->NumSuccsLeft;
140      }
141      if (P.getLatency() != 0) {
142        this->setDepthDirty();
143        N->setHeightDirty();
144      }
145      return;
146    }
147}
148
149void SUnit::setDepthDirty() {
150  if (!isDepthCurrent) return;
151  SmallVector<SUnit*, 8> WorkList;
152  WorkList.push_back(this);
153  do {
154    SUnit *SU = WorkList.pop_back_val();
155    SU->isDepthCurrent = false;
156    for (SUnit::const_succ_iterator I = SU->Succs.begin(),
157         E = SU->Succs.end(); I != E; ++I) {
158      SUnit *SuccSU = I->getSUnit();
159      if (SuccSU->isDepthCurrent)
160        WorkList.push_back(SuccSU);
161    }
162  } while (!WorkList.empty());
163}
164
165void SUnit::setHeightDirty() {
166  if (!isHeightCurrent) return;
167  SmallVector<SUnit*, 8> WorkList;
168  WorkList.push_back(this);
169  do {
170    SUnit *SU = WorkList.pop_back_val();
171    SU->isHeightCurrent = false;
172    for (SUnit::const_pred_iterator I = SU->Preds.begin(),
173         E = SU->Preds.end(); I != E; ++I) {
174      SUnit *PredSU = I->getSUnit();
175      if (PredSU->isHeightCurrent)
176        WorkList.push_back(PredSU);
177    }
178  } while (!WorkList.empty());
179}
180
181/// setDepthToAtLeast - Update this node's successors to reflect the
182/// fact that this node's depth just increased.
183///
184void SUnit::setDepthToAtLeast(unsigned NewDepth) {
185  if (NewDepth <= getDepth())
186    return;
187  setDepthDirty();
188  Depth = NewDepth;
189  isDepthCurrent = true;
190}
191
192/// setHeightToAtLeast - Update this node's predecessors to reflect the
193/// fact that this node's height just increased.
194///
195void SUnit::setHeightToAtLeast(unsigned NewHeight) {
196  if (NewHeight <= getHeight())
197    return;
198  setHeightDirty();
199  Height = NewHeight;
200  isHeightCurrent = true;
201}
202
203/// ComputeDepth - Calculate the maximal path from the node to the exit.
204///
205void SUnit::ComputeDepth() {
206  SmallVector<SUnit*, 8> WorkList;
207  WorkList.push_back(this);
208  do {
209    SUnit *Cur = WorkList.back();
210
211    bool Done = true;
212    unsigned MaxPredDepth = 0;
213    for (SUnit::const_pred_iterator I = Cur->Preds.begin(),
214         E = Cur->Preds.end(); I != E; ++I) {
215      SUnit *PredSU = I->getSUnit();
216      if (PredSU->isDepthCurrent)
217        MaxPredDepth = std::max(MaxPredDepth,
218                                PredSU->Depth + I->getLatency());
219      else {
220        Done = false;
221        WorkList.push_back(PredSU);
222      }
223    }
224
225    if (Done) {
226      WorkList.pop_back();
227      if (MaxPredDepth != Cur->Depth) {
228        Cur->setDepthDirty();
229        Cur->Depth = MaxPredDepth;
230      }
231      Cur->isDepthCurrent = true;
232    }
233  } while (!WorkList.empty());
234}
235
236/// ComputeHeight - Calculate the maximal path from the node to the entry.
237///
238void SUnit::ComputeHeight() {
239  SmallVector<SUnit*, 8> WorkList;
240  WorkList.push_back(this);
241  do {
242    SUnit *Cur = WorkList.back();
243
244    bool Done = true;
245    unsigned MaxSuccHeight = 0;
246    for (SUnit::const_succ_iterator I = Cur->Succs.begin(),
247         E = Cur->Succs.end(); I != E; ++I) {
248      SUnit *SuccSU = I->getSUnit();
249      if (SuccSU->isHeightCurrent)
250        MaxSuccHeight = std::max(MaxSuccHeight,
251                                 SuccSU->Height + I->getLatency());
252      else {
253        Done = false;
254        WorkList.push_back(SuccSU);
255      }
256    }
257
258    if (Done) {
259      WorkList.pop_back();
260      if (MaxSuccHeight != Cur->Height) {
261        Cur->setHeightDirty();
262        Cur->Height = MaxSuccHeight;
263      }
264      Cur->isHeightCurrent = true;
265    }
266  } while (!WorkList.empty());
267}
268
269/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
270/// a group of nodes flagged together.
271void SUnit::dump(const ScheduleDAG *G) const {
272  dbgs() << "SU(" << NodeNum << "): ";
273  G->dumpNode(this);
274}
275
276void SUnit::dumpAll(const ScheduleDAG *G) const {
277  dump(G);
278
279  dbgs() << "  # preds left       : " << NumPredsLeft << "\n";
280  dbgs() << "  # succs left       : " << NumSuccsLeft << "\n";
281  dbgs() << "  Latency            : " << Latency << "\n";
282  dbgs() << "  Depth              : " << Depth << "\n";
283  dbgs() << "  Height             : " << Height << "\n";
284
285  if (Preds.size() != 0) {
286    dbgs() << "  Predecessors:\n";
287    for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
288         I != E; ++I) {
289      dbgs() << "   ";
290      switch (I->getKind()) {
291      case SDep::Data:        dbgs() << "val "; break;
292      case SDep::Anti:        dbgs() << "anti"; break;
293      case SDep::Output:      dbgs() << "out "; break;
294      case SDep::Order:       dbgs() << "ch  "; break;
295      }
296      dbgs() << "#";
297      dbgs() << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")";
298      if (I->isArtificial())
299        dbgs() << " *";
300      dbgs() << ": Latency=" << I->getLatency();
301      dbgs() << "\n";
302    }
303  }
304  if (Succs.size() != 0) {
305    dbgs() << "  Successors:\n";
306    for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
307         I != E; ++I) {
308      dbgs() << "   ";
309      switch (I->getKind()) {
310      case SDep::Data:        dbgs() << "val "; break;
311      case SDep::Anti:        dbgs() << "anti"; break;
312      case SDep::Output:      dbgs() << "out "; break;
313      case SDep::Order:       dbgs() << "ch  "; break;
314      }
315      dbgs() << "#";
316      dbgs() << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")";
317      if (I->isArtificial())
318        dbgs() << " *";
319      dbgs() << ": Latency=" << I->getLatency();
320      dbgs() << "\n";
321    }
322  }
323  dbgs() << "\n";
324}
325
326#ifndef NDEBUG
327/// VerifySchedule - Verify that all SUnits were scheduled and that
328/// their state is consistent.
329///
330void ScheduleDAG::VerifySchedule(bool isBottomUp) {
331  bool AnyNotSched = false;
332  unsigned DeadNodes = 0;
333  unsigned Noops = 0;
334  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
335    if (!SUnits[i].isScheduled) {
336      if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) {
337        ++DeadNodes;
338        continue;
339      }
340      if (!AnyNotSched)
341        dbgs() << "*** Scheduling failed! ***\n";
342      SUnits[i].dump(this);
343      dbgs() << "has not been scheduled!\n";
344      AnyNotSched = true;
345    }
346    if (SUnits[i].isScheduled &&
347        (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getDepth()) >
348          unsigned(INT_MAX)) {
349      if (!AnyNotSched)
350        dbgs() << "*** Scheduling failed! ***\n";
351      SUnits[i].dump(this);
352      dbgs() << "has an unexpected "
353           << (isBottomUp ? "Height" : "Depth") << " value!\n";
354      AnyNotSched = true;
355    }
356    if (isBottomUp) {
357      if (SUnits[i].NumSuccsLeft != 0) {
358        if (!AnyNotSched)
359          dbgs() << "*** Scheduling failed! ***\n";
360        SUnits[i].dump(this);
361        dbgs() << "has successors left!\n";
362        AnyNotSched = true;
363      }
364    } else {
365      if (SUnits[i].NumPredsLeft != 0) {
366        if (!AnyNotSched)
367          dbgs() << "*** Scheduling failed! ***\n";
368        SUnits[i].dump(this);
369        dbgs() << "has predecessors left!\n";
370        AnyNotSched = true;
371      }
372    }
373  }
374  for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
375    if (!Sequence[i])
376      ++Noops;
377  assert(!AnyNotSched);
378  assert(Sequence.size() + DeadNodes - Noops == SUnits.size() &&
379         "The number of nodes scheduled doesn't match the expected number!");
380}
381#endif
382
383/// InitDAGTopologicalSorting - create the initial topological
384/// ordering from the DAG to be scheduled.
385///
386/// The idea of the algorithm is taken from
387/// "Online algorithms for managing the topological order of
388/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly
389/// This is the MNR algorithm, which was first introduced by
390/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in
391/// "Maintaining a topological order under edge insertions".
392///
393/// Short description of the algorithm:
394///
395/// Topological ordering, ord, of a DAG maps each node to a topological
396/// index so that for all edges X->Y it is the case that ord(X) < ord(Y).
397///
398/// This means that if there is a path from the node X to the node Z,
399/// then ord(X) < ord(Z).
400///
401/// This property can be used to check for reachability of nodes:
402/// if Z is reachable from X, then an insertion of the edge Z->X would
403/// create a cycle.
404///
405/// The algorithm first computes a topological ordering for the DAG by
406/// initializing the Index2Node and Node2Index arrays and then tries to keep
407/// the ordering up-to-date after edge insertions by reordering the DAG.
408///
409/// On insertion of the edge X->Y, the algorithm first marks by calling DFS
410/// the nodes reachable from Y, and then shifts them using Shift to lie
411/// immediately after X in Index2Node.
412void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
413  unsigned DAGSize = SUnits.size();
414  std::vector<SUnit*> WorkList;
415  WorkList.reserve(DAGSize);
416
417  Index2Node.resize(DAGSize);
418  Node2Index.resize(DAGSize);
419
420  // Initialize the data structures.
421  for (unsigned i = 0, e = DAGSize; i != e; ++i) {
422    SUnit *SU = &SUnits[i];
423    int NodeNum = SU->NodeNum;
424    unsigned Degree = SU->Succs.size();
425    // Temporarily use the Node2Index array as scratch space for degree counts.
426    Node2Index[NodeNum] = Degree;
427
428    // Is it a node without dependencies?
429    if (Degree == 0) {
430      assert(SU->Succs.empty() && "SUnit should have no successors");
431      // Collect leaf nodes.
432      WorkList.push_back(SU);
433    }
434  }
435
436  int Id = DAGSize;
437  while (!WorkList.empty()) {
438    SUnit *SU = WorkList.back();
439    WorkList.pop_back();
440    Allocate(SU->NodeNum, --Id);
441    for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
442         I != E; ++I) {
443      SUnit *SU = I->getSUnit();
444      if (!--Node2Index[SU->NodeNum])
445        // If all dependencies of the node are processed already,
446        // then the node can be computed now.
447        WorkList.push_back(SU);
448    }
449  }
450
451  Visited.resize(DAGSize);
452
453#ifndef NDEBUG
454  // Check correctness of the ordering
455  for (unsigned i = 0, e = DAGSize; i != e; ++i) {
456    SUnit *SU = &SUnits[i];
457    for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
458         I != E; ++I) {
459      assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] &&
460      "Wrong topological sorting");
461    }
462  }
463#endif
464}
465
466/// AddPred - Updates the topological ordering to accomodate an edge
467/// to be added from SUnit X to SUnit Y.
468void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {
469  int UpperBound, LowerBound;
470  LowerBound = Node2Index[Y->NodeNum];
471  UpperBound = Node2Index[X->NodeNum];
472  bool HasLoop = false;
473  // Is Ord(X) < Ord(Y) ?
474  if (LowerBound < UpperBound) {
475    // Update the topological order.
476    Visited.reset();
477    DFS(Y, UpperBound, HasLoop);
478    assert(!HasLoop && "Inserted edge creates a loop!");
479    // Recompute topological indexes.
480    Shift(Visited, LowerBound, UpperBound);
481  }
482}
483
484/// RemovePred - Updates the topological ordering to accomodate an
485/// an edge to be removed from the specified node N from the predecessors
486/// of the current node M.
487void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) {
488  // InitDAGTopologicalSorting();
489}
490
491/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark
492/// all nodes affected by the edge insertion. These nodes will later get new
493/// topological indexes by means of the Shift method.
494void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
495                                     bool& HasLoop) {
496  std::vector<const SUnit*> WorkList;
497  WorkList.reserve(SUnits.size());
498
499  WorkList.push_back(SU);
500  do {
501    SU = WorkList.back();
502    WorkList.pop_back();
503    Visited.set(SU->NodeNum);
504    for (int I = SU->Succs.size()-1; I >= 0; --I) {
505      int s = SU->Succs[I].getSUnit()->NodeNum;
506      if (Node2Index[s] == UpperBound) {
507        HasLoop = true;
508        return;
509      }
510      // Visit successors if not already and in affected region.
511      if (!Visited.test(s) && Node2Index[s] < UpperBound) {
512        WorkList.push_back(SU->Succs[I].getSUnit());
513      }
514    }
515  } while (!WorkList.empty());
516}
517
518/// Shift - Renumber the nodes so that the topological ordering is
519/// preserved.
520void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
521                                       int UpperBound) {
522  std::vector<int> L;
523  int shift = 0;
524  int i;
525
526  for (i = LowerBound; i <= UpperBound; ++i) {
527    // w is node at topological index i.
528    int w = Index2Node[i];
529    if (Visited.test(w)) {
530      // Unmark.
531      Visited.reset(w);
532      L.push_back(w);
533      shift = shift + 1;
534    } else {
535      Allocate(w, i - shift);
536    }
537  }
538
539  for (unsigned j = 0; j < L.size(); ++j) {
540    Allocate(L[j], i - shift);
541    i = i + 1;
542  }
543}
544
545
546/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
547/// create a cycle.
548bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
549  if (IsReachable(TargetSU, SU))
550    return true;
551  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
552       I != E; ++I)
553    if (I->isAssignedRegDep() &&
554        IsReachable(TargetSU, I->getSUnit()))
555      return true;
556  return false;
557}
558
559/// IsReachable - Checks if SU is reachable from TargetSU.
560bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
561                                             const SUnit *TargetSU) {
562  // If insertion of the edge SU->TargetSU would create a cycle
563  // then there is a path from TargetSU to SU.
564  int UpperBound, LowerBound;
565  LowerBound = Node2Index[TargetSU->NodeNum];
566  UpperBound = Node2Index[SU->NodeNum];
567  bool HasLoop = false;
568  // Is Ord(TargetSU) < Ord(SU) ?
569  if (LowerBound < UpperBound) {
570    Visited.reset();
571    // There may be a path from TargetSU to SU. Check for it.
572    DFS(TargetSU, UpperBound, HasLoop);
573  }
574  return HasLoop;
575}
576
577/// Allocate - assign the topological index to the node n.
578void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
579  Node2Index[n] = index;
580  Index2Node[index] = n;
581}
582
583ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort(
584                                                     std::vector<SUnit> &sunits)
585 : SUnits(sunits) {}
586
587ScheduleHazardRecognizer::~ScheduleHazardRecognizer() {}
588