CIRCT  19.0.0git
ASAPScheduler.cpp
Go to the documentation of this file.
1 //===- ASAPScheduler.cpp - As-soon-as-possible list scheduler -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Implementation of an as-soon-as-possible list scheduler for acyclic problems.
10 //
11 //===----------------------------------------------------------------------===//
12 
15 
16 using namespace circt;
17 using namespace circt::scheduling;
18 
19 LogicalResult scheduling::scheduleASAP(Problem &prob) {
20  return handleOperationsInTopologicalOrder(prob, [&](Operation *op) {
21  // Operations with no predecessors are scheduled at time step 0
22  if (prob.getDependences(op).empty()) {
23  prob.setStartTime(op, 0);
24  return success();
25  }
26 
27  // op has at least one predecessor. Compute start time as:
28  // max_{p : preds} startTime[p] + latency[linkedOpr[p]]
29  unsigned startTime = 0;
30  for (auto &dep : prob.getDependences(op)) {
31  Operation *pred = dep.getSource();
32  auto predStart = prob.getStartTime(pred);
33  if (!predStart)
34  // pred is not yet scheduled, give up and try again later
35  return failure();
36 
37  // pred is already scheduled
38  auto predOpr = *prob.getLinkedOperatorType(pred);
39  startTime = std::max(startTime, *predStart + *prob.getLatency(predOpr));
40  }
41 
42  prob.setStartTime(op, startTime);
43  return success();
44  });
45 }
This class models the most basic scheduling problem.
Definition: Problems.h:87
void setStartTime(Operation *op, unsigned val)
Definition: Problems.h:221
DependenceRange getDependences(Operation *op)
Return a range object to transparently iterate over op's incoming 1) implicit def-use dependences (ba...
Definition: Problems.cpp:53
LogicalResult handleOperationsInTopologicalOrder(Problem &prob, HandleOpFn fun)
Visit prob's operations in topological order, using an internal worklist.
Definition: Utilities.cpp:21
LogicalResult scheduleASAP(Problem &prob)
This is a simple list scheduler for solving the basic scheduling problem.
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21