CIRCT  19.0.0git
IsolateClocks.cpp
Go to the documentation of this file.
1 //===- IsolateClocks.cpp --------------------------------------------------===//
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 
11 #include "circt/Dialect/HW/HWOps.h"
12 #include "mlir/Pass/Pass.h"
13 #include "llvm/ADT/TypeSwitch.h"
14 #include "llvm/Support/Debug.h"
15 
16 #define DEBUG_TYPE "arc-isolate-clocks"
17 
18 namespace circt {
19 namespace arc {
20 #define GEN_PASS_DEF_ISOLATECLOCKS
21 #include "circt/Dialect/Arc/ArcPasses.h.inc"
22 } // namespace arc
23 } // namespace circt
24 
25 using namespace circt;
26 using namespace arc;
27 
28 //===----------------------------------------------------------------------===//
29 // Datastructures
30 //===----------------------------------------------------------------------===//
31 
32 namespace {
33 /// Represents a not-yet materialized clock-domain.
34 class ClockDomain {
35 public:
36  ClockDomain(Value clock, MLIRContext *context)
37  : clock(clock), domainBlock(std::make_unique<Block>()),
38  builder(OpBuilder(context)) {
39  builder.setInsertionPointToStart(domainBlock.get());
40  }
41 
42  /// Moves an operation into the clock domain if it is not already in there.
43  /// Returns true if the operation was moved.
44  bool moveToDomain(Operation *op);
45  /// Moves all non-clocked fan-in operations that are not also used outside the
46  /// clock domain into the clock domain.
47  void sinkFanIn(SmallVectorImpl<Value> &);
48  /// Computes all values used from outside this clock domain and all values
49  /// defined in this clock domain that are used outside.
50  void computeCrossingValues(SmallVectorImpl<Value> &inputs,
51  SmallVectorImpl<Value> &outputs);
52  /// Add the terminator, materialize the clock-domain and return the
53  /// operation. After calling this function, the other member functions and
54  /// fields should not be used anymore.
55  ClockDomainOp materialize(OpBuilder &materializeBuilder, Location loc);
56 
57 private:
58  Value clock;
59  std::unique_ptr<Block> domainBlock;
60  OpBuilder builder;
61 };
62 } // namespace
63 
64 bool ClockDomain::moveToDomain(Operation *op) {
65  assert(op != nullptr);
66  // Do not move if already in the block.
67  if (op->getBlock() == domainBlock.get())
68  return false;
69 
70  builder.setInsertionPointToStart(domainBlock.get());
71 
72  // Perform the move
73  op->remove();
74  builder.insert(op);
75 
76  return true;
77 }
78 
79 void ClockDomain::sinkFanIn(SmallVectorImpl<Value> &worklist) {
80  while (!worklist.empty()) {
81  auto *op = worklist.pop_back_val().getDefiningOp();
82  // Ignore block arguments
83  if (!op)
84  continue;
85  // TODO: if we find a clock domain with the same clock we should merge it.
86  // Otherwise ignore it.
87  if (isa<ClockDomainOp>(op))
88  continue;
89  if (auto clockedOp = dyn_cast<ClockedOpInterface>(op);
90  clockedOp && clockedOp.isClocked())
91  continue;
92  // Don't pull in operations that have other users outside this domain. We
93  // don't want do duplicate ops to keep binary size as small as possible and
94  // avoid computing the same thing multiple times. This is also important
95  // because we want every path from domain input to domain output to have at
96  // least one cycle latency, ideally every output is directly from a state op
97  // with greater than 0 latency such that we don't have to insert additional
98  // storage slots later on.
99  if (llvm::any_of(op->getUsers(), [&](auto *user) {
100  return user->getBlock() != domainBlock.get();
101  }))
102  continue;
103 
104  if (moveToDomain(op))
105  worklist.append(op->getOperands().begin(), op->getOperands().end());
106  }
107 }
108 
109 ClockDomainOp ClockDomain::materialize(OpBuilder &materializeBuilder,
110  Location loc) {
111  builder.setInsertionPointToEnd(domainBlock.get());
112  SmallVector<Value> inputs, outputs;
113  computeCrossingValues(inputs, outputs);
114 
115  // Add the terminator and clock domain outputs and rewire the SSA value uses
116  auto outputOp = builder.create<arc::OutputOp>(loc, outputs);
117  auto clockDomainOp = materializeBuilder.create<ClockDomainOp>(
118  loc, ValueRange(outputs).getTypes(), inputs, clock);
119  for (auto [domainOutput, val] :
120  llvm::zip(clockDomainOp.getOutputs(), outputOp->getOperands())) {
121  val.replaceUsesWithIf(domainOutput, [&](OpOperand &operand) {
122  return operand.getOwner()->getBlock() != domainBlock.get();
123  });
124  }
125 
126  // Add arguments and inputs to the clock domain operation and rewire the SSA
127  // value uses.
128  domainBlock->addArguments(ValueRange(inputs).getTypes(),
129  SmallVector<Location>(inputs.size(), loc));
130  for (auto [domainArg, val] :
131  llvm::zip(domainBlock->getArguments(), clockDomainOp.getInputs())) {
132  val.replaceUsesWithIf(domainArg, [&](OpOperand &operand) {
133  return operand.getOwner()->getBlock() == domainBlock.get();
134  });
135  }
136  clockDomainOp->getRegion(0).push_back(domainBlock.release());
137 
138  return clockDomainOp;
139 }
140 
141 void ClockDomain::computeCrossingValues(SmallVectorImpl<Value> &inputs,
142  SmallVectorImpl<Value> &outputs) {
143  DenseSet<Value> inputSet, outputSet;
144  for (auto &op : *domainBlock) {
145  for (auto operand : op.getOperands()) {
146  auto *defOp = operand.getDefiningOp();
147  if (!defOp || defOp->getBlock() != domainBlock.get()) {
148  if (inputSet.insert(operand).second)
149  inputs.push_back(operand);
150  }
151  }
152  for (auto result : op.getResults()) {
153  if (llvm::any_of(result.getUsers(), [&](auto *user) {
154  return user->getBlock() != domainBlock.get();
155  })) {
156  if (outputSet.insert(result).second)
157  outputs.push_back(result);
158  }
159  }
160  }
161 }
162 
163 //===----------------------------------------------------------------------===//
164 // Pass Infrastructure
165 //===----------------------------------------------------------------------===//
166 
167 namespace {
168 struct IsolateClocksPass
169  : public arc::impl::IsolateClocksBase<IsolateClocksPass> {
170  void runOnOperation() override;
171  LogicalResult runOnModule(hw::HWModuleOp module);
172 };
173 } // namespace
174 
175 void IsolateClocksPass::runOnOperation() {
176  for (auto module : getOperation().getOps<hw::HWModuleOp>())
177  if (failed(runOnModule(module)))
178  return signalPassFailure();
179 }
180 
181 LogicalResult IsolateClocksPass::runOnModule(hw::HWModuleOp module) {
182  llvm::MapVector<Value, SmallVector<ClockedOpInterface>> clocks;
183 
184  // Check preconditions and collect clocked operations
185  for (auto &op : *module.getBodyBlock()) {
186  // Nested regions not supported for now. Since different regions have
187  // different semantics we need to special case all region operations we
188  // want to support. An interesting one might be scf::IfOp or similar, but
189  // when it contains clocked operations with different clocks, it needs to
190  // be split up, etc.
191  if (op.getNumRegions() != 0 && !isa<ClockDomainOp>(&op))
192  return op.emitOpError("operations with regions not supported yet!");
193 
194  if (auto clockedOp = dyn_cast<ClockedOpInterface>(&op);
195  clockedOp && clockedOp.isClocked())
196  clocks[clockedOp.getClock()].push_back(clockedOp);
197  }
198 
199  SmallVector<Value> worklist;
200  // Construct the domains clock by clock. This makes handling of
201  // inter-clock-domain connections considerably easier.
202  for (auto [clock, clockedOps] : clocks) {
203  ClockDomain domain(clock, module.getContext());
204 
205  // Move all the clocked operations into the domain, op by op, and pull in
206  // their fan-in immediately after to have a nice op ordering inside the
207  // domain.
208  for (auto op : clockedOps) {
209  worklist.clear();
210  if (domain.moveToDomain(op)) {
211  op.eraseClock();
212  worklist.append(op->getOperands().begin(), op->getOperands().end());
213  domain.sinkFanIn(worklist);
214  }
215  }
216 
217  // Materialize the actual clock domain operation.
218  OpBuilder builder(module.getBodyBlock()->getTerminator());
219  domain.materialize(builder, module.getLoc());
220  }
221 
222  return success();
223 }
224 
225 std::unique_ptr<Pass> arc::createIsolateClocksPass() {
226  return std::make_unique<IsolateClocksPass>();
227 }
assert(baseType &&"element must be base type")
llvm::SmallVector< StringAttr > inputs
llvm::SmallVector< StringAttr > outputs
Builder builder
std::unique_ptr< mlir::Pass > createIsolateClocksPass()
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21