CIRCT  18.0.0git
WireDFT.cpp
Go to the documentation of this file.
1 //===- WireDFT.cpp - Create DFT module ports --------------------*- C++ -*-===//
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 // This file defines the WireDFT pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "PassDetails.h"
21 #include "mlir/IR/ImplicitLocOpBuilder.h"
22 #include "llvm/ADT/DepthFirstIterator.h"
23 #include "llvm/ADT/SetVector.h"
24 
25 using namespace circt;
26 using namespace firrtl;
27 
28 /// This calculates the lowest common ancestor of the instance operations. It
29 /// supports finding the LCA of an arbitrary number of nodes (instead of the
30 /// usual 2 at a time), and incremental target node discovery.
31 static InstanceGraphNode *
33  llvm::function_ref<bool(InstanceRecord *)> predicate) {
34  struct StackElement {
35  StackElement(InstanceGraphNode *node)
36  : node(node), it(node->begin()), count(0) {}
37  // The node itself.
38  InstanceGraphNode *node;
39  // The current iterator of this node's children.
41  // The number of interesting nodes under this one.
42  unsigned count;
43  };
44 
45  // Since we support incremental discovery of the interesting modules, we keep
46  // track of node which has the most children under it so far.
47  InstanceGraphNode *currentLCA = nullptr;
48  unsigned currentCount = 0;
49 
50  // This is used to pass the count of a child back to its parent.
51  unsigned childCount = 0;
52 
53  // The workstack for a depth-first walk.
54  SmallVector<StackElement> stack;
55  stack.emplace_back(top);
56  while (!stack.empty()) {
57  auto &element = stack.back();
58  auto &node = element.node;
59  auto &it = element.it;
60 
61  // Add the count of the just-processed child node. If we are coming from
62  // the parent node, childCount will be 0.
63  element.count += childCount;
64 
65  // Check if we're done processing this nodes children.
66  if (it == node->end()) {
67  // Store the current count in the childCount, so that we may return the
68  // count to this node's parent op.
69  childCount = element.count;
70 
71  // If this node has more children than any other node, it is the best LCA
72  // of all the nodes we have found *so far*.
73  if (childCount > currentCount) {
74  currentLCA = node;
75  currentCount = element.count;
76  }
77 
78  // Pop back to the parent op.
79  stack.pop_back();
80  continue;
81  }
82 
83  // If the current node is interesting, increase this node's count.
84  auto *instanceNode = *it++;
85  if (predicate(instanceNode))
86  ++element.count;
87 
88  // Set up to iterate the child node.
89  stack.emplace_back(instanceNode->getTarget());
90  childCount = 0;
91  }
92  return currentLCA;
93 }
94 
95 namespace {
96 class WireDFTPass : public WireDFTBase<WireDFTPass> {
97  void runOnOperation() override;
98 };
99 } // namespace
100 
101 void WireDFTPass::runOnOperation() {
102  auto circuit = getOperation();
103 
104  // This is the module marked as the device under test.
105  FModuleOp dut = nullptr;
106 
107  // This is the signal marked as the DFT enable, a 1-bit signal to be wired to
108  // the EICG modules.
109  Value enableSignal;
110  FModuleOp enableModule;
111 
112  // Optional extra signal: clockDivBypassSignal.
113  Value clockDivBypassSignal;
114  FModuleOp clockDivBypassModule;
115 
116  // Walk all modules looking for the DUT module and the annotated enable
117  // signal.
118  for (auto &op : *circuit.getBodyBlock()) {
119  auto module = dyn_cast<FModuleOp>(op);
120 
121  // If this isn't a regular module, continue.
122  if (!module)
123  continue;
124 
125  // Check if this module is the DUT.
126  AnnotationSet annos(module);
127  if (annos.hasAnnotation(dutAnnoClass)) {
128  // Check if we already found the DUT.
129  if (dut) {
130  auto diag = module->emitError("more than one module marked DUT");
131  diag.attachNote(dut->getLoc()) << "first module here";
132  signalPassFailure();
133  return;
134  }
135  dut = module;
136  }
137  bool error = false;
138 
139  auto handleAnnotation = [&](Value value, Annotation anno,
140  StringRef annoName, Value &signal,
141  auto &signalModule) {
142  // Exit if already found error.
143  if (error)
144  return false;
145  if (anno.isClass(annoName)) {
146  if (signal) {
147  auto diag =
148  emitError(value.getLoc(), "more than one thing marked as ")
149  << annoName;
150  diag.attachNote(signal.getLoc()) << "first thing defined here";
151  error = true;
152  return false;
153  }
154 
155  // Grab the enable value and remove the annotation.
156  auto builder = ImplicitLocOpBuilder::atBlockEnd(value.getLoc(),
157  value.getParentBlock());
158  builder.setInsertionPointAfterValue(value);
159  signal = getValueByFieldID(builder, value, anno.getFieldID());
160  signalModule = module;
161  return true;
162  }
163  return false;
164  };
165  auto handleAnnotationChecks = [&](Value value, Annotation anno) {
166  return handleAnnotation(value, anno, dftTestModeEnableAnnoClass,
167  enableSignal, enableModule) ||
168  handleAnnotation(value, anno, dftClockDividerBypassAnnoClass,
169  clockDivBypassSignal, clockDivBypassModule);
170  };
171 
172  // See if this module has any port marked as the DFT enable.
174  module, [&](unsigned i, Annotation anno) {
175  return handleAnnotationChecks(module.getArgument(i), anno);
176  });
177  if (error)
178  return signalPassFailure();
179 
180  // Walk the module body looking for any operation marked as the
181  // DFT enable.
182  auto walkResult = module->walk([&](Operation *op) {
183  // Skip operations with no results.
184  if (op->getNumResults() == 0)
185  return WalkResult::advance();
186 
188  return handleAnnotationChecks(op->getResult(0), anno);
189  });
190  if (error)
191  return WalkResult::interrupt();
192  return WalkResult::advance();
193  });
194  if (walkResult.wasInterrupted())
195  return signalPassFailure();
196  }
197 
198  // No enable signal means we have no work to do.
199  if (!enableSignal) {
200  // Error if bypass is specified without enable.
201  if (clockDivBypassSignal) {
202  mlir::emitError(clockDivBypassSignal.getLoc(),
203  "bypass signal specified without enable signal");
204  return signalPassFailure();
205  }
206  return markAllAnalysesPreserved();
207  }
208 
209  // This pass requires a DUT.
210  if (!dut) {
211  circuit->emitError("no DUT module found.");
212  return signalPassFailure();
213  }
214 
215  auto &instanceGraph = getAnalysis<InstanceGraph>();
216 
217  // Find the LowestCommonAncestor node of all the nodes to be wired together,
218  // and collect all the ClockGate modules. Search under DUT.
219  llvm::SetVector<InstanceRecord *> clockGates;
220  llvm::SetVector<InstanceRecord *> clockGatesWithBypass;
221  auto *lca = lowestCommonAncestor(
222  instanceGraph.lookup(dut), [&](InstanceRecord *node) {
223  auto module = node->getTarget()->getModule();
224  // If this is a clock gate, record the module and return true.
225  if (module.getModuleName().startswith("EICG_wrapper")) {
226  clockGates.insert(node);
227  return true;
228  }
229  // Return true if this is the module with the enable signal or the
230  // bypass signal.
231  return node->getParent()->getModule() == enableModule ||
232  node->getParent()->getModule() == clockDivBypassModule;
233  });
234 
235  // If there are no clock gates under the DUT, we can stop now.
236  if (clockGates.empty())
237  return;
238 
239  // Stash UInt<1> type for use throughout.
240  auto uint1Type = type_cast<FIRRTLType>(enableSignal.getType());
241 
242  // Hard coded port result number; the clock gate test_en port is 1.
243  // Language below reflects this as well.
244  const unsigned testEnPortNo = 1;
245 
246  const unsigned clockDivBypassPortNo = 3;
247 
248  // Name used for wiring enable signal.
249  StringRef testEnPortName = "test_en";
250 
251  // Magic name for optional bypass signal, port on gate must match.
252  StringRef requiredClockDivBypassPortName = "dft_clk_div_bypass";
253 
254  // Scan gathered clock gates and check for basic compatibility.
255  // Detect clock gates with bypass port while visiting each.
256  for (auto *cgnode : clockGates) {
257  auto module = cgnode->getTarget()->getModule();
258  auto genErr = [&]() { return module.emitError("clock gate module "); };
259  FExtModuleOp ext = dyn_cast<FExtModuleOp>(module.getOperation());
260  if (!ext) {
261  genErr() << "must be an extmodule";
262  return signalPassFailure();
263  }
264  static_assert(testEnPortNo == 1, "update this code");
265  if (ext.getNumPorts() <= testEnPortNo) {
266  genErr() << "must have at least two ports";
267  return signalPassFailure();
268  }
269  if (ext.getPortType(testEnPortNo) != uint1Type) {
270  genErr()
271  .append("must have second port with type UInt<1>")
272  .attachNote() // Use port location once available.
273  .append("Second port (\"")
274  .append(ext.getPortName(testEnPortNo))
275  .append("\") has type ")
276  .append(ext.getPortType(testEnPortNo))
277  .append(", expected ")
278  .append(uint1Type);
279  return signalPassFailure();
280  }
281  if (ext.getPortDirection(testEnPortNo) != Direction::In) {
282  genErr() << "must have second port with input direction";
283  return signalPassFailure();
284  }
285 
286  // If find expected port name + direction + type, this needs clock div
287  // bypass wiring. Check name against magic as well for now.
288  if (clockDivBypassSignal && ext.getNumPorts() > clockDivBypassPortNo) {
289  if (ext.getPortDirection(clockDivBypassPortNo) == Direction::In &&
290  ext.getPortType(clockDivBypassPortNo) == uint1Type) {
291  if (ext.getPortName(clockDivBypassPortNo) ==
292  requiredClockDivBypassPortName)
293  clockGatesWithBypass.insert(cgnode);
294  else
295  mlir::emitWarning(
296  ext.getPortLocation(clockDivBypassPortNo),
297  "compatible port in bypass position has wrong name, skipping");
298  }
299  }
300  }
301 
302  // Handle enable signal (only) outside DUT.
303  if (!instanceGraph.isAncestor(enableModule, lca->getModule())) {
304  // Current LCA covers the clock gates we care about.
305  // Compute new LCA from enable to that node.
306  lca = lowestCommonAncestor(
307  instanceGraph.getTopLevelNode(), [&](InstanceRecord *node) {
308  return node->getTarget() == lca ||
309  node->getParent()->getModule() == enableModule;
310  });
311  // Handle unreachable case.
312  if (!lca) {
313  auto diag =
314  circuit.emitError("unable to connect enable signal and DUT, may not "
315  "be reachable from top-level module");
316  diag.attachNote(enableSignal.getLoc()) << "enable signal here";
317  diag.attachNote(dut.getLoc()) << "DUT here";
318  diag.attachNote(instanceGraph.getTopLevelModule().getLoc())
319  << "top-level module here";
320 
321  return signalPassFailure();
322  }
323  }
324 
325  bool needsClockDivBypassWiring = !clockGatesWithBypass.empty();
326 
327  // Handle bypass signal outside DUT (or the DUT+enable LCA).
328  // Compute separately for more specific diagnostic if unreachable,
329  // and use same LCA for wiring all signals.
330  if (needsClockDivBypassWiring &&
331  !instanceGraph.isAncestor(clockDivBypassModule, lca->getModule())) {
332  // Current LCA covers the clock gates we care about.
333  // Compute new LCA from bypass to that node.
334  lca = lowestCommonAncestor(
335  instanceGraph.getTopLevelNode(), [&](InstanceRecord *node) {
336  return node->getTarget() == lca ||
337  node->getParent()->getModule() == clockDivBypassModule;
338  });
339  // Handle unreachable case.
340  if (!lca) {
341  auto diag = circuit.emitError(
342  "unable to connect bypass signal and DUT (and enable), may not "
343  "be reachable from top-level module");
344  diag.attachNote(clockDivBypassSignal.getLoc()) << "bypass signal here";
345  diag.attachNote(enableSignal.getLoc()) << "enable signal here";
346  diag.attachNote(dut.getLoc()) << "DUT here";
347  diag.attachNote(instanceGraph.getTopLevelModule().getLoc())
348  << "top-level module here";
349 
350  return signalPassFailure();
351  }
352  }
353 
354  // Check all gates we're wiring are only within the DUT.
355  if (!allUnder(clockGates.getArrayRef(), instanceGraph.lookup(dut))) {
356  dut->emitError()
357  << "clock gates within DUT must not be instantiated outside the DUT";
358  return signalPassFailure();
359  }
360 
361  // Stash some useful things.
362  auto loc = lca->getModule().getLoc();
363 
364  // Helper to insert a port into an instance op. We have to replace the whole
365  // op and then keep the instance graph updated.
366  auto insertPortIntoInstance =
367  [&](InstanceRecord *instanceNode,
368  std::pair<unsigned, PortInfo> port) -> InstanceOp {
369  auto instance = cast<InstanceOp>(*instanceNode->getInstance());
370  auto clone = instance.cloneAndInsertPorts({port});
371  instanceGraph.replaceInstance(instance, clone);
372  instance->replaceAllUsesWith(clone.getResults().drop_back());
373  instance->erase();
374  return clone;
375  };
376 
377  // At this point we have found the enable and bypass signals, all important
378  // clock gates, and the ancestor of these. From here we need wire the
379  // enable/bypass signals upward to the LCA, and then wire those signals down
380  // to all clock gates.
381 
382  auto wireUp = [&](Value startSignal, FModuleOp signalModule,
383  StringAttr portName, StringRef portNameFriendly,
384  unsigned targetPortNo, auto &targets) -> LogicalResult {
385  // This maps each module to its signal.
386  DenseMap<InstanceGraphNode *, Value> signals;
387 
388  // This first part wires the signal upward to the LCA module.
389  auto *node = instanceGraph.lookup(signalModule);
390  Value signal = startSignal;
391  PortInfo portInfo = {portName, uint1Type, Direction::Out, {}, loc};
392  while (node != lca) {
393  // If there is more than one parent the we are in trouble. We can't handle
394  // more than one enable signal to wire everywhere else.
395  if (!node->hasOneUse()) {
396  auto diag = emitError(startSignal.getLoc(),
397  "multiple instantiations of the DFT ")
398  << portNameFriendly << " signal";
399  auto it = node->usesBegin();
400  diag.attachNote((*it++)->getInstance()->getLoc())
401  << "first instance here";
402  diag.attachNote((*it)->getInstance()->getLoc())
403  << "second instance here";
404  return diag;
405  }
406 
407  // Record the signal for this module.
408  signals[node] = signal;
409 
410  // Create an output port to this module.
411  auto module = cast<FModuleOp>(*node->getModule());
412  unsigned portNo = module.getNumPorts();
413  module.insertPorts({{portNo, portInfo}});
414  auto builder = ImplicitLocOpBuilder::atBlockEnd(module.getLoc(),
415  module.getBodyBlock());
416  emitConnect(builder, module.getArgument(portNo), signal);
417 
418  // Add an output port to the instance of this module.
419  auto *instanceNode = (*node->usesBegin());
420  auto clone = insertPortIntoInstance(instanceNode, {portNo, portInfo});
421 
422  // Set up for the next iteration.
423  signal = clone.getResult(portNo);
424  node = instanceNode->getParent();
425  }
426 
427  // Record the signal in the LCA.
428  signals[node] = signal;
429 
430  // Drill the enable signal to each of the leaf clock gates. We do this
431  // searching upward in the hiearchy until we find a module with the signal.
432  // This is a recursive function due to lazyness.
433  portInfo = {portName, uint1Type, Direction::In, {}, loc};
434  std::function<Value(InstanceGraphNode *)> getSignal =
435  [&](InstanceGraphNode *node) -> Value {
436  // Mutable signal reference.
437  auto &signal = signals[node];
438 
439  // Early break if this module has already been wired.
440  if (signal)
441  return signal;
442 
443  // Add an input signal to this module.
444  auto module = cast<FModuleOp>(*node->getModule());
445  unsigned portNo = module.getNumPorts();
446  module.insertPorts({{portNo, portInfo}});
447  auto arg = module.getArgument(portNo);
448 
449  // Record the new signal.
450  signal = arg;
451 
452  // Attach the input signal to each instance of this module.
453  for (auto *instanceNode : node->uses()) {
454  // Add an input signal to this instance op.
455  auto clone = insertPortIntoInstance(instanceNode, {portNo, portInfo});
456 
457  // Wire the parent signal to the instance op.
458  auto *parent = instanceNode->getParent();
459  auto module = cast<FModuleOp>(*parent->getModule());
460  auto signal = getSignal(parent);
461  auto builder = ImplicitLocOpBuilder::atBlockEnd(module->getLoc(),
462  module.getBodyBlock());
463  emitConnect(builder, clone.getResult(portNo), signal);
464  }
465 
466  return arg;
467  };
468 
469  // Wire the signal to each clock gate using the helper above.
470  for (auto *instance : targets) {
471  auto *parent = instance->getParent();
472  auto module = cast<FModuleOp>(*parent->getModule());
473  auto builder = ImplicitLocOpBuilder::atBlockEnd(module->getLoc(),
474  module.getBodyBlock());
475  emitConnect(
476  builder,
477  cast<InstanceOp>(*instance->getInstance()).getResult(targetPortNo),
478  getSignal(parent));
479  }
480  return success();
481  };
482 
483  auto enablePortName = StringAttr::get(&getContext(), testEnPortName);
484  auto bypassPortName =
485  StringAttr::get(&getContext(), requiredClockDivBypassPortName);
486  if (failed(wireUp(enableSignal, enableModule, enablePortName, "enable",
487  testEnPortNo, clockGates)))
488  return signalPassFailure();
489  if (needsClockDivBypassWiring &&
490  failed(wireUp(clockDivBypassSignal, clockDivBypassModule, bypassPortName,
491  "clock divider bypass", clockDivBypassPortNo,
492  clockGatesWithBypass)))
493  return signalPassFailure();
494 
495  // And we're done!
496  markAnalysesPreserved<InstanceGraph>();
497 }
498 
499 std::unique_ptr<mlir::Pass> circt::firrtl::createWireDFTPass() {
500  return std::make_unique<WireDFTPass>();
501 }
lowerAnnotationsNoRefTypePorts FirtoolPreserveValuesMode value
Definition: Firtool.cpp:95
Builder builder
static InstanceGraphNode * lowestCommonAncestor(InstanceGraphNode *top, llvm::function_ref< bool(InstanceRecord *)> predicate)
This calculates the lowest common ancestor of the instance operations.
Definition: WireDFT.cpp:32
This class provides a read-only projection over the MLIR attributes that represent a set of annotatio...
bool removeAnnotations(llvm::function_ref< bool(Annotation)> predicate)
Remove all annotations from this annotation set for which predicate returns true.
static bool removePortAnnotations(Operation *module, llvm::function_ref< bool(unsigned, Annotation)> predicate)
Remove all port annotations from a module or extmodule for which predicate returns true.
This class provides a read-only projection of an annotation.
This is a Node in the InstanceGraph.
auto getModule()
Get the module that this node is tracking.
This is an edge in the InstanceGraph.
Definition: InstanceGraph.h:55
auto getInstance()
Get the instance-like op that this is tracking.
Definition: InstanceGraph.h:59
InstanceGraphNode * getParent() const
Get the module where the instantiation lives.
Definition: InstanceGraph.h:66
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:53
constexpr const char * dftTestModeEnableAnnoClass
constexpr const char * dftClockDividerBypassAnnoClass
constexpr const char * dutAnnoClass
Value getValueByFieldID(ImplicitLocOpBuilder builder, Value value, unsigned fieldID)
This gets the value targeted by a field id.
std::unique_ptr< mlir::Pass > createWireDFTPass()
Definition: WireDFT.cpp:499
bool allUnder(ArrayRef< InstanceRecord * > nodes, InstanceGraphNode *top)
void emitConnect(OpBuilder &builder, Location loc, Value lhs, Value rhs)
Emit a connect between two values.
Definition: FIRRTLUtils.cpp:23
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
This holds the name and type that describes the module's ports.
This just maps a iterator of references to an iterator of addresses.
Definition: InstanceGraph.h:35