CIRCT  20.0.0git
ChainingSupport.cpp
Go to the documentation of this file.
1 //===- ChainingSupport.cpp - Utilities for chaining-aware schedulers ------===//
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 // Helpers to add chaining support to existing algorithms via chain-breaking
10 // auxiliary dependences, i.e. edges whose endpoints must be separated by at
11 // least one time steps.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 
17 #include "mlir/IR/Operation.h"
18 
19 using namespace circt;
20 using namespace circt::scheduling;
21 
23 
25  ChainingProblem &prob, float cycleTime,
26  SmallVectorImpl<Dependence> &result) {
27  // Sanity check: This approach treats the given `cycleTime` as a hard
28  // constraint, so all individual delays must be shorter.
29  for (auto opr : prob.getOperatorTypes())
30  if (*prob.getIncomingDelay(opr) > cycleTime ||
31  *prob.getOutgoingDelay(opr) > cycleTime)
32  return prob.getContainingOp()->emitError()
33  << "Delays of operator type '" << opr.getValue()
34  << "' exceed maximum cycle time: " << cycleTime;
35 
36  // chains[v][u] denotes the accumulated delay incoming at `v`, of the longest
37  // combinational chain originating from `u`.
38  DenseMap<Operation *, SmallDenseMap<Operation *, float>> chains;
39 
40  // Do a simple DFA-style pass over the dependence graph to determine
41  // combinational chains and their respective accumulated delays.
42  return handleOperationsInTopologicalOrder(prob, [&](Operation *op) {
43  // Mark `op` to be the origin of its own chain.
44  chains[op][op] = 0.0f;
45 
46  for (auto dep : prob.getDependences(op)) {
47  // Skip auxiliary deps, as these don't carry values.
48  if (dep.isAuxiliary())
49  continue;
50 
51  Operation *pred = dep.getSource();
52  if (!chains.count(pred))
53  return failure(); // Predecessor hasn't been handled yet.
54 
55  auto predOpr = *prob.getLinkedOperatorType(pred);
56  if (*prob.getLatency(predOpr) > 0) {
57  // `pred` is not combinational, so none of its incoming chains are
58  // extended. Hence, it only contributes its outgoing delay to `op`'s
59  // incoming delay.
60  chains[op][pred] = *prob.getOutgoingDelay(predOpr);
61  continue;
62  }
63 
64  // Otherwise, `pred` is combinational. This means that all of its incoming
65  // chains, extended by `pred`, are incoming chains for `op`.
66  for (auto incomingChain : chains[pred]) {
67  Operation *origin = incomingChain.first;
68  float delay = incomingChain.second;
69  chains[op][origin] = std::max(delay + *prob.getOutgoingDelay(predOpr),
70  chains[op][origin]);
71  }
72  }
73 
74  // All chains/accumulated delays incoming at `op` are now known.
75  auto opr = *prob.getLinkedOperatorType(op);
76  for (auto incomingChain : chains[op]) {
77  Operation *origin = incomingChain.first;
78  float delay = incomingChain.second;
79  // Check whether `op` could be appended to the incoming chain without
80  // violating the cycle time constraint.
81  if (delay + *prob.getIncomingDelay(opr) > cycleTime) {
82  // If not, add a chain-breaking auxiliary dep ...
83  result.emplace_back(origin, op);
84  // ... and end the chain here.
85  chains[op].erase(origin);
86  }
87  }
88 
89  return success();
90  });
91 }
92 
94  prob.clearStartTimeInCycle();
95  return handleOperationsInTopologicalOrder(prob, [&](Operation *op) {
96  // `op` will start within its abstract time step as soon as all operand
97  // values have reached it.
98  unsigned startTime = *prob.getStartTime(op);
99  float startTimeInCycle = 0.0f;
100 
101  for (auto dep : prob.getDependences(op)) {
102  // Skip auxiliary deps, as these don't carry values.
103  if (dep.isAuxiliary())
104  continue;
105 
106  Operation *pred = dep.getSource();
107  auto predStartTimeInCycle = prob.getStartTimeInCycle(pred);
108  if (!predStartTimeInCycle)
109  return failure(); // Predecessor hasn't been handled yet.
110 
111  auto predOpr = *prob.getLinkedOperatorType(pred);
112  unsigned predStartTime = *prob.getStartTime(pred);
113  unsigned predEndTime = predStartTime + *prob.getLatency(predOpr);
114 
115  if (predEndTime < startTime)
116  // Incoming value is completely registered/available with the beginning
117  // of the cycle.
118  continue;
119 
120  // So, `pred` ends in the same cycle as `op` starts.
121  assert(predEndTime == startTime);
122  // If `pred` uses a multi-cycle operator, only its outgoing delay counts.
123  float predEndTimeInCycle =
124  (predStartTime == predEndTime ? *predStartTimeInCycle : 0.0f) +
125  *prob.getOutgoingDelay(predOpr);
126  startTimeInCycle = std::max(predEndTimeInCycle, startTimeInCycle);
127  }
128 
129  prob.setStartTimeInCycle(op, startTimeInCycle);
130  return success();
131  });
132 }
This class models the accumulation of physical propagation delays on combinational paths along SSA de...
Definition: Problems.h:339
void setStartTimeInCycle(Operation *op, float time)
Definition: Problems.h:377
std::optional< float > getIncomingDelay(OperatorType opr)
The incoming delay denotes the propagation time from the operand inputs to either the result outputs ...
Definition: Problems.h:355
std::optional< float > getOutgoingDelay(OperatorType opr)
The outgoing delay denotes the propagation time from either the operand inputs (combinational operato...
Definition: Problems.h:365
std::optional< OperatorType > getLinkedOperatorType(Operation *op)
The linked operator type provides the runtime characteristics for op.
Definition: Problems.h:196
const OperatorTypeSet & getOperatorTypes()
Return the set of operator types.
Definition: Problems.h:189
std::optional< unsigned > getStartTime(Operation *op)
Return the start time for op, as computed by the scheduler.
Definition: Problems.h:212
detail::Dependence Dependence
A thin wrapper to allow a uniform handling of def-use and auxiliary dependences.
Definition: Problems.h:95
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
Operation * getContainingOp()
Return the operation containing this problem, e.g. to emit diagnostics.
Definition: Problems.h:165
A wrapper class to uniformly handle def-use and auxiliary dependence edges.
LogicalResult handleOperationsInTopologicalOrder(Problem &prob, HandleOpFn fun)
Visit prob's operations in topological order, using an internal worklist.
Definition: Utilities.cpp:21
LogicalResult computeChainBreakingDependences(ChainingProblem &prob, float cycleTime, SmallVectorImpl< Problem::Dependence > &result)
Analyse combinational chains in prob's dependence graph and determine pairs of operations that must b...
LogicalResult computeStartTimesInCycle(ChainingProblem &prob)
Assuming prob is scheduled and contains (integer) start times, this method fills in the start times i...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21