CIRCT  20.0.0git
Dedup.cpp
Go to the documentation of this file.
1 //===- Dedup.cpp - FIRRTL module deduping -----------------------*- 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 implements FIRRTL module deduplication.
10 //
11 //===----------------------------------------------------------------------===//
12 
23 #include "circt/Support/LLVM.h"
24 #include "mlir/IR/IRMapping.h"
25 #include "mlir/IR/ImplicitLocOpBuilder.h"
26 #include "mlir/IR/Threading.h"
27 #include "mlir/Pass/Pass.h"
28 #include "mlir/Support/LogicalResult.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/DenseMapInfo.h"
31 #include "llvm/ADT/DepthFirstIterator.h"
32 #include "llvm/ADT/PostOrderIterator.h"
33 #include "llvm/ADT/SmallPtrSet.h"
34 #include "llvm/ADT/TypeSwitch.h"
35 #include "llvm/Support/Format.h"
36 #include "llvm/Support/SHA256.h"
37 
38 namespace circt {
39 namespace firrtl {
40 #define GEN_PASS_DEF_DEDUP
41 #include "circt/Dialect/FIRRTL/Passes.h.inc"
42 } // namespace firrtl
43 } // namespace circt
44 
45 using namespace circt;
46 using namespace firrtl;
47 using hw::InnerRefAttr;
48 
49 //===----------------------------------------------------------------------===//
50 // Utility function for classifying a Symbol's dedup-ability.
51 //===----------------------------------------------------------------------===//
52 
53 static bool checkVisibility(mlir::SymbolOpInterface symbol) {
54  // If module has symbol (name) that must be preserved even if unused,
55  // skip it. All symbol uses must be supported, which is not true if
56  // non-private.
57  // Special handling for class-like's and if symbol reports cannot be
58  // discarded.
59  return symbol.isPrivate() &&
60  (symbol.canDiscardOnUseEmpty() || isa<ClassLike>(*symbol));
61 }
62 
63 //===----------------------------------------------------------------------===//
64 // Hashing
65 //===----------------------------------------------------------------------===//
66 
67 llvm::raw_ostream &printHex(llvm::raw_ostream &stream,
68  ArrayRef<uint8_t> bytes) {
69  // Print the hash on a single line.
70  return stream << format_bytes(bytes, std::nullopt, 32) << "\n";
71 }
72 
73 llvm::raw_ostream &printHash(llvm::raw_ostream &stream, llvm::SHA256 &data) {
74  return printHex(stream, data.result());
75 }
76 
77 llvm::raw_ostream &printHash(llvm::raw_ostream &stream, std::string data) {
78  ArrayRef<uint8_t> bytes(reinterpret_cast<const uint8_t *>(data.c_str()),
79  data.length());
80  return printHex(stream, bytes);
81 }
82 
83 // This struct contains information to determine module module uniqueness. A
84 // first element is a structural hash of the module, and the second element is
85 // an array which tracks module names encountered in the walk. Since module
86 // names could be replaced during dedup, it's necessary to keep names up-to-date
87 // before actually combining them into structural hashes.
88 struct ModuleInfo {
89  // SHA256 hash.
90  std::array<uint8_t, 32> structuralHash;
91  // Module names referred by instance op in the module.
92  mlir::ArrayAttr referredModuleNames;
93 };
94 
95 /// Unique identifier for a value. All value sources are numbered by apperance,
96 /// and values are identified using this numbering (`index`) and an `offset`.
97 /// For BlockArgument's, this is the argument number.
98 /// For OpResult's, this is the result number.
99 struct ValueId {
100  uint64_t index;
101  uint64_t offset;
102 };
103 
104 struct SymbolTarget {
106  uint64_t fieldID;
107 };
108 
109 /// This struct contains constant string attributes shared across different
110 /// threads.
112  explicit StructuralHasherSharedConstants(MLIRContext *context) {
113  portTypesAttr = StringAttr::get(context, "portTypes");
114  moduleNameAttr = StringAttr::get(context, "moduleName");
115  innerSymAttr = StringAttr::get(context, "inner_sym");
116  portSymsAttr = StringAttr::get(context, "portSyms");
117  portNamesAttr = StringAttr::get(context, "portNames");
118  nonessentialAttributes.insert(StringAttr::get(context, "annotations"));
119  nonessentialAttributes.insert(StringAttr::get(context, "name"));
120  nonessentialAttributes.insert(StringAttr::get(context, "portAnnotations"));
121  nonessentialAttributes.insert(StringAttr::get(context, "portNames"));
122  nonessentialAttributes.insert(StringAttr::get(context, "portLocations"));
123  nonessentialAttributes.insert(StringAttr::get(context, "sym_name"));
124  };
125 
126  // This is a cached "portTypes" string attr.
127  StringAttr portTypesAttr;
128 
129  // This is a cached "moduleName" string attr.
130  StringAttr moduleNameAttr;
131 
132  // This is a cached "inner_sym" string attr.
133  StringAttr innerSymAttr;
134 
135  // This is a cached "portSyms" string attr.
136  StringAttr portSymsAttr;
137 
138  // This is a cached "portNames" string attr.
139  StringAttr portNamesAttr;
140 
141  // This is a set of every attribute we should ignore.
142  DenseSet<Attribute> nonessentialAttributes;
143 };
144 
147  : constants(constants){};
148 
149  std::pair<std::array<uint8_t, 32>, SmallVector<StringAttr>>
150  getHashAndModuleNames(FModuleLike module) {
151  update(&(*module));
152  auto hash = sha.final();
153  return {hash, referredModuleNames};
154  }
155 
156 private:
157  void update(const void *pointer) {
158  auto *addr = reinterpret_cast<const uint8_t *>(&pointer);
159  sha.update(ArrayRef<uint8_t>(addr, sizeof pointer));
160  }
161 
162  void update(size_t value) {
163  auto *addr = reinterpret_cast<const uint8_t *>(&value);
164  sha.update(ArrayRef<uint8_t>(addr, sizeof value));
165  }
166 
167  void update(TypeID typeID) { update(typeID.getAsOpaquePointer()); }
168 
169  // NOLINTNEXTLINE(misc-no-recursion)
170  void update(BundleType type) {
171  update(type.getTypeID());
172  for (auto &element : type.getElements()) {
173  update(element.isFlip);
174  update(element.type);
175  }
176  }
177 
178  // NOLINTNEXTLINE(misc-no-recursion)
179  void update(Type type) {
180  if (auto bundle = type_dyn_cast<BundleType>(type))
181  return update(bundle);
182  update(type.getAsOpaquePointer());
183  }
184 
185  void record(void *address) {
186  auto size = indices.size();
187  assert(!indices.contains(address));
188  indices[address] = size;
189  }
190 
191  /// Get the unique id for the specified value.
192  ValueId getId(Value val) {
193  if (auto arg = dyn_cast<BlockArgument>(val))
194  return {indices.at(arg.getOwner()), arg.getArgNumber()};
195  auto result = cast<OpResult>(val);
196  return {indices.at(result.getOwner()), result.getResultNumber()};
197  }
198 
199  void update(OpResult result) {
200  // Like instance ops, don't use object ops' result types since they might be
201  // replaced by dedup. Record the class names and lazily combine their hashes
202  // using the same mechanism as instances and modules.
203  if (auto objectOp = dyn_cast<ObjectOp>(result.getOwner())) {
204  referredModuleNames.push_back(objectOp.getType().getNameAttr().getAttr());
205  return;
206  }
207 
208  update(result.getType());
209  }
210 
211  void update(ValueId index) {
212  update(index.index);
213  update(index.offset);
214  }
215 
216  void update(OpOperand &operand) { update(getId(operand.get())); }
217 
218  void update(Operation *op, hw::InnerSymAttr attr) {
219  for (auto props : attr)
220  innerSymTargets[props.getName()] =
221  SymbolTarget{{indices.at(op), 0}, props.getFieldID()};
222  }
223 
224  void update(Value value, hw::InnerSymAttr attr) {
225  for (auto props : attr)
226  innerSymTargets[props.getName()] =
227  SymbolTarget{getId(value), props.getFieldID()};
228  }
229 
230  void update(const SymbolTarget &target) {
231  update(target.index);
232  update(target.fieldID);
233  }
234 
235  void update(InnerRefAttr attr) {
236  // We hash the value's index as it apears in the block.
237  auto it = innerSymTargets.find(attr.getName());
238  assert(it != innerSymTargets.end() &&
239  "inner symbol should have been previously hashed");
240  update(attr.getTypeID());
241  update(it->second);
242  }
243 
244  /// Hash the top level attribute dictionary of the operation. This function
245  /// has special handling for inner symbols, ports, and referenced modules.
246  void update(Operation *op, DictionaryAttr dict) {
247  for (auto namedAttr : dict) {
248  auto name = namedAttr.getName();
249  auto value = namedAttr.getValue();
250  // Skip names and annotations, except in certain cases.
251  // Names of ports are load bearing for classes, so we do hash those.
252  bool isClassPortNames =
253  isa<ClassLike>(op) && name == constants.portNamesAttr;
254  if (constants.nonessentialAttributes.contains(name) && !isClassPortNames)
255  continue;
256 
257  // Hash the port types.
258  if (name == constants.portTypesAttr) {
259  auto portTypes = cast<ArrayAttr>(value).getAsValueRange<TypeAttr>();
260  for (auto type : portTypes)
261  update(type);
262  continue;
263  }
264 
265  // Special case the InnerSymbols to ignore the symbol names.
266  if (name == constants.portSymsAttr) {
267  if (op->getNumRegions() != 1)
268  continue;
269  auto &region = op->getRegion(0);
270  if (region.getBlocks().empty())
271  continue;
272  auto *block = &region.front();
273  auto syms = cast<ArrayAttr>(value).getAsRange<hw::InnerSymAttr>();
274  if (syms.empty())
275  continue;
276  for (auto [arg, sym] : llvm::zip_equal(block->getArguments(), syms))
277  update(arg, sym);
278  continue;
279  }
280  if (name == constants.innerSymAttr) {
281  auto innerSym = cast<hw::InnerSymAttr>(value);
282  update(op, innerSym);
283  continue;
284  }
285 
286  // For instance op, don't use `moduleName` attributes since they might be
287  // replaced by dedup. Record the names and lazily combine their hashes.
288  // It is assumed that module names are hashed only through instance ops;
289  // it could cause suboptimal results if there was other operation that
290  // refers to module names through essential attributes.
291  if (isa<InstanceOp>(op) && name == constants.moduleNameAttr) {
292  referredModuleNames.push_back(cast<FlatSymbolRefAttr>(value).getAttr());
293  continue;
294  }
295 
296  // Hash the interned pointer.
297  update(name.getAsOpaquePointer());
298 
299  // TODO: properly handle DistinctAttr, including its use in paths.
300  // See https://github.com/llvm/circt/issues/6583.
301  if (isa<DistinctAttr>(value))
302  continue;
303 
304  // If this is an symbol reference, we need to perform name erasure.
305  if (auto innerRef = dyn_cast<hw::InnerRefAttr>(value))
306  update(innerRef);
307  else
308  update(value.getAsOpaquePointer());
309  }
310  }
311 
312  void update(mlir::OperationName name) {
313  // Operation names are interned.
314  update(name.getAsOpaquePointer());
315  }
316 
317  // NOLINTNEXTLINE(misc-no-recursion)
318  void update(Operation *op) {
319  record(op);
320  update(op->getName());
321 
322  // Hash the operands.
323  for (auto &operand : op->getOpOperands())
324  update(operand);
325 
326  // Number the block pointers, for use numbering their arguments.
327  for (auto &region : op->getRegions())
328  for (auto &block : region.getBlocks())
329  record(&block);
330 
331  // This happens after the numbering above, as it uses blockarg numbering
332  // for inner symbols.
333  update(op, op->getAttrDictionary());
334 
335  // Hash the regions. We need to make sure an empty region doesn't hash the
336  // same as no region, so we include the number of regions.
337  update(op->getNumRegions());
338  for (auto &region : op->getRegions()) {
339  update(region.getBlocks().size());
340  for (auto &block : region.getBlocks()) {
341  update(indices.at(&block));
342  for (auto argType : block.getArgumentTypes())
343  update(argType);
344  for (auto &op : block)
345  update(&op);
346  }
347  }
348 
349  // Record any op results (types).
350  for (auto result : op->getResults())
351  update(result);
352  }
353 
354  // Every operation and block is assigned a unique id based on their order of
355  // appearance. All values are uniquely identified using these.
356  DenseMap<void *, unsigned> indices;
357 
358  // Track inner symbol name -> target's unique identification.
359  DenseMap<StringAttr, SymbolTarget> innerSymTargets;
360 
361  // This keeps track of module names in the order of the appearance.
362  SmallVector<mlir::StringAttr> referredModuleNames;
363 
364  // String constants.
366 
367  // This is the actual running hash calculation. This is a stateful element
368  // that should be reinitialized after each hash is produced.
369  llvm::SHA256 sha;
370 };
371 
372 //===----------------------------------------------------------------------===//
373 // Equivalence
374 //===----------------------------------------------------------------------===//
375 
376 /// This class is for reporting differences between two modules which should
377 /// have been deduplicated.
378 struct Equivalence {
379  Equivalence(MLIRContext *context, InstanceGraph &instanceGraph)
380  : instanceGraph(instanceGraph) {
381  noDedupClass = StringAttr::get(context, noDedupAnnoClass);
382  dedupGroupAttrName = StringAttr::get(context, "firrtl.dedup_group");
383  portDirectionsAttr = StringAttr::get(context, "portDirections");
384  nonessentialAttributes.insert(StringAttr::get(context, "annotations"));
385  nonessentialAttributes.insert(StringAttr::get(context, "name"));
386  nonessentialAttributes.insert(StringAttr::get(context, "portAnnotations"));
387  nonessentialAttributes.insert(StringAttr::get(context, "portNames"));
388  nonessentialAttributes.insert(StringAttr::get(context, "portTypes"));
389  nonessentialAttributes.insert(StringAttr::get(context, "portSyms"));
390  nonessentialAttributes.insert(StringAttr::get(context, "portLocations"));
391  nonessentialAttributes.insert(StringAttr::get(context, "sym_name"));
392  nonessentialAttributes.insert(StringAttr::get(context, "inner_sym"));
393  }
394 
395  struct ModuleData {
396  ModuleData(const hw::InnerSymbolTable &a, const hw::InnerSymbolTable &b)
397  : a(a), b(b) {}
398  IRMapping map;
399  const hw::InnerSymbolTable &a;
400  const hw::InnerSymbolTable &b;
401  };
402 
403  std::string prettyPrint(Attribute attr) {
404  SmallString<64> buffer;
405  llvm::raw_svector_ostream os(buffer);
406  if (auto integerAttr = dyn_cast<IntegerAttr>(attr)) {
407  os << "0x";
408  if (integerAttr.getType().isSignlessInteger())
409  integerAttr.getValue().toStringUnsigned(buffer, /*radix=*/16);
410  else
411  integerAttr.getAPSInt().toString(buffer, /*radix=*/16);
412 
413  } else
414  os << attr;
415  return std::string(buffer);
416  }
417 
418  // NOLINTNEXTLINE(misc-no-recursion)
419  LogicalResult check(InFlightDiagnostic &diag, const Twine &message,
420  Operation *a, BundleType aType, Operation *b,
421  BundleType bType) {
422  if (aType.getNumElements() != bType.getNumElements()) {
423  diag.attachNote(a->getLoc())
424  << message << " bundle type has different number of elements";
425  diag.attachNote(b->getLoc()) << "second operation here";
426  return failure();
427  }
428 
429  for (auto elementPair :
430  llvm::zip(aType.getElements(), bType.getElements())) {
431  auto aElement = std::get<0>(elementPair);
432  auto bElement = std::get<1>(elementPair);
433  if (aElement.isFlip != bElement.isFlip) {
434  diag.attachNote(a->getLoc()) << message << " bundle element "
435  << aElement.name << " flip does not match";
436  diag.attachNote(b->getLoc()) << "second operation here";
437  return failure();
438  }
439 
440  if (failed(check(diag,
441  "bundle element \'" + aElement.name.getValue() + "'", a,
442  aElement.type, b, bElement.type)))
443  return failure();
444  }
445  return success();
446  }
447 
448  LogicalResult check(InFlightDiagnostic &diag, const Twine &message,
449  Operation *a, Type aType, Operation *b, Type bType) {
450  if (aType == bType)
451  return success();
452  if (auto aBundleType = type_dyn_cast<BundleType>(aType))
453  if (auto bBundleType = type_dyn_cast<BundleType>(bType))
454  return check(diag, message, a, aBundleType, b, bBundleType);
455  if (type_isa<RefType>(aType) && type_isa<RefType>(bType) &&
456  aType != bType) {
457  diag.attachNote(a->getLoc())
458  << message << ", has a RefType with a different base type "
459  << type_cast<RefType>(aType).getType()
460  << " in the same position of the two modules marked as 'must dedup'. "
461  "(This may be due to Grand Central Taps or Views being different "
462  "between the two modules.)";
463  diag.attachNote(b->getLoc())
464  << "the second module has a different base type "
465  << type_cast<RefType>(bType).getType();
466  return failure();
467  }
468  diag.attachNote(a->getLoc())
469  << message << " types don't match, first type is " << aType;
470  diag.attachNote(b->getLoc()) << "second type is " << bType;
471  return failure();
472  }
473 
474  LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a,
475  Block &aBlock, Operation *b, Block &bBlock) {
476 
477  // Block argument types.
478  auto portNames = a->getAttrOfType<ArrayAttr>("portNames");
479  auto portNo = 0;
480  auto emitMissingPort = [&](Value existsVal, Operation *opExists,
481  Operation *opDoesNotExist) {
482  StringRef portName;
483  auto portNames = opExists->getAttrOfType<ArrayAttr>("portNames");
484  if (portNames)
485  if (auto portNameAttr = dyn_cast<StringAttr>(portNames[portNo]))
486  portName = portNameAttr.getValue();
487  if (type_isa<RefType>(existsVal.getType())) {
488  diag.attachNote(opExists->getLoc())
489  << " contains a RefType port named '" + portName +
490  "' that only exists in one of the modules (can be due to "
491  "difference in Grand Central Tap or View of two modules "
492  "marked with must dedup)";
493  diag.attachNote(opDoesNotExist->getLoc())
494  << "second module to be deduped that does not have the RefType "
495  "port";
496  } else {
497  diag.attachNote(opExists->getLoc())
498  << "port '" + portName + "' only exists in one of the modules";
499  diag.attachNote(opDoesNotExist->getLoc())
500  << "second module to be deduped that does not have the port";
501  }
502  return failure();
503  };
504 
505  for (auto argPair :
506  llvm::zip_longest(aBlock.getArguments(), bBlock.getArguments())) {
507  auto &aArg = std::get<0>(argPair);
508  auto &bArg = std::get<1>(argPair);
509  if (aArg.has_value() && bArg.has_value()) {
510  // TODO: we should print the port number if there are no port names, but
511  // there are always port names ;).
512  StringRef portName;
513  if (portNames) {
514  if (auto portNameAttr = dyn_cast<StringAttr>(portNames[portNo]))
515  portName = portNameAttr.getValue();
516  }
517  // Assumption here that block arguments correspond to ports.
518  if (failed(check(diag, "module port '" + portName + "'", a,
519  aArg->getType(), b, bArg->getType())))
520  return failure();
521  data.map.map(aArg.value(), bArg.value());
522  portNo++;
523  continue;
524  }
525  if (!aArg.has_value())
526  std::swap(a, b);
527  return emitMissingPort(aArg.has_value() ? aArg.value() : bArg.value(), a,
528  b);
529  }
530 
531  // Blocks operations.
532  auto aIt = aBlock.begin();
533  auto aEnd = aBlock.end();
534  auto bIt = bBlock.begin();
535  auto bEnd = bBlock.end();
536  while (aIt != aEnd && bIt != bEnd)
537  if (failed(check(diag, data, &*aIt++, &*bIt++)))
538  return failure();
539  if (aIt != aEnd) {
540  diag.attachNote(aIt->getLoc()) << "first block has more operations";
541  diag.attachNote(b->getLoc()) << "second block here";
542  return failure();
543  }
544  if (bIt != bEnd) {
545  diag.attachNote(bIt->getLoc()) << "second block has more operations";
546  diag.attachNote(a->getLoc()) << "first block here";
547  return failure();
548  }
549  return success();
550  }
551 
552  LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a,
553  Region &aRegion, Operation *b, Region &bRegion) {
554  auto aIt = aRegion.begin();
555  auto aEnd = aRegion.end();
556  auto bIt = bRegion.begin();
557  auto bEnd = bRegion.end();
558 
559  // Region blocks.
560  while (aIt != aEnd && bIt != bEnd)
561  if (failed(check(diag, data, a, *aIt++, b, *bIt++)))
562  return failure();
563  if (aIt != aEnd || bIt != bEnd) {
564  diag.attachNote(a->getLoc())
565  << "operation regions have different number of blocks";
566  diag.attachNote(b->getLoc()) << "second operation here";
567  return failure();
568  }
569  return success();
570  }
571 
572  LogicalResult check(InFlightDiagnostic &diag, Operation *a,
573  mlir::DenseBoolArrayAttr aAttr, Operation *b,
574  mlir::DenseBoolArrayAttr bAttr) {
575  if (aAttr == bAttr)
576  return success();
577  auto portNames = a->getAttrOfType<ArrayAttr>("portNames");
578  for (unsigned i = 0, e = aAttr.size(); i < e; ++i) {
579  auto aDirection = aAttr[i];
580  auto bDirection = bAttr[i];
581  if (aDirection != bDirection) {
582  auto &note = diag.attachNote(a->getLoc()) << "module port ";
583  if (portNames)
584  note << "'" << cast<StringAttr>(portNames[i]).getValue() << "'";
585  else
586  note << i;
587  note << " directions don't match, first direction is '"
588  << direction::toString(aDirection) << "'";
589  diag.attachNote(b->getLoc()) << "second direction is '"
590  << direction::toString(bDirection) << "'";
591  return failure();
592  }
593  }
594  return success();
595  }
596 
597  LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a,
598  DictionaryAttr aDict, Operation *b,
599  DictionaryAttr bDict) {
600  // Fast path.
601  if (aDict == bDict)
602  return success();
603 
604  DenseSet<Attribute> seenAttrs;
605  for (auto namedAttr : aDict) {
606  auto attrName = namedAttr.getName();
607  if (nonessentialAttributes.contains(attrName))
608  continue;
609 
610  auto aAttr = namedAttr.getValue();
611  auto bAttr = bDict.get(attrName);
612  if (!bAttr) {
613  diag.attachNote(a->getLoc())
614  << "second operation is missing attribute " << attrName;
615  diag.attachNote(b->getLoc()) << "second operation here";
616  return diag;
617  }
618 
619  if (isa<hw::InnerRefAttr>(aAttr) && isa<hw::InnerRefAttr>(bAttr)) {
620  auto bRef = cast<hw::InnerRefAttr>(bAttr);
621  auto aRef = cast<hw::InnerRefAttr>(aAttr);
622  // See if they are pointing at the same operation or port.
623  auto aTarget = data.a.lookup(aRef.getName());
624  auto bTarget = data.b.lookup(bRef.getName());
625  if (!aTarget || !bTarget)
626  diag.attachNote(a->getLoc())
627  << "malformed ir, possibly violating use-before-def";
628  auto error = [&]() {
629  diag.attachNote(a->getLoc())
630  << "operations have different targets, first operation has "
631  << aTarget;
632  diag.attachNote(b->getLoc()) << "second operation has " << bTarget;
633  return failure();
634  };
635  if (aTarget.isPort()) {
636  // If they are targeting ports, make sure its the same port number.
637  if (!bTarget.isPort() || aTarget.getPort() != bTarget.getPort())
638  return error();
639  } else {
640  // Otherwise make sure that they are targeting the same operation.
641  if (!bTarget.isOpOnly() ||
642  aTarget.getOp() != data.map.lookup(bTarget.getOp()))
643  return error();
644  }
645  if (aTarget.getField() != bTarget.getField())
646  return error();
647  } else if (attrName == portDirectionsAttr) {
648  // Special handling for the port directions attribute for better
649  // error messages.
650  if (failed(check(diag, a, cast<mlir::DenseBoolArrayAttr>(aAttr), b,
651  cast<mlir::DenseBoolArrayAttr>(bAttr))))
652  return failure();
653  } else if (isa<DistinctAttr>(aAttr) && isa<DistinctAttr>(bAttr)) {
654  // TODO: properly handle DistinctAttr, including its use in paths.
655  // See https://github.com/llvm/circt/issues/6583
656  } else if (aAttr != bAttr) {
657  diag.attachNote(a->getLoc())
658  << "first operation has attribute '" << attrName.getValue()
659  << "' with value " << prettyPrint(aAttr);
660  diag.attachNote(b->getLoc())
661  << "second operation has value " << prettyPrint(bAttr);
662  return failure();
663  }
664  seenAttrs.insert(attrName);
665  }
666  if (aDict.getValue().size() != bDict.getValue().size()) {
667  for (auto namedAttr : bDict) {
668  auto attrName = namedAttr.getName();
669  // Skip the attribute if we don't care about this particular one or it
670  // is one that is known to be in both dictionaries.
671  if (nonessentialAttributes.contains(attrName) ||
672  seenAttrs.contains(attrName))
673  continue;
674  // We have found an attribute that is only in the second operation.
675  diag.attachNote(a->getLoc())
676  << "first operation is missing attribute " << attrName;
677  diag.attachNote(b->getLoc()) << "second operation here";
678  return failure();
679  }
680  }
681  return success();
682  }
683 
684  // NOLINTNEXTLINE(misc-no-recursion)
685  LogicalResult check(InFlightDiagnostic &diag, FInstanceLike a,
686  FInstanceLike b) {
687  auto aName = a.getReferencedModuleNameAttr();
688  auto bName = b.getReferencedModuleNameAttr();
689  if (aName == bName)
690  return success();
691 
692  // If the modules instantiate are different we will want to know why the
693  // sub module did not dedupliate. This code recursively checks the child
694  // module.
695  auto aModule = instanceGraph.lookup(aName)->getModule();
696  auto bModule = instanceGraph.lookup(bName)->getModule();
697  // Create a new error for the submodule.
698  diag.attachNote(std::nullopt)
699  << "in instance " << a.getInstanceNameAttr() << " of " << aName
700  << ", and instance " << b.getInstanceNameAttr() << " of " << bName;
701  check(diag, aModule, bModule);
702  return failure();
703  }
704 
705  // NOLINTNEXTLINE(misc-no-recursion)
706  LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a,
707  Operation *b) {
708  // Operation name.
709  if (a->getName() != b->getName()) {
710  diag.attachNote(a->getLoc()) << "first operation is a " << a->getName();
711  diag.attachNote(b->getLoc()) << "second operation is a " << b->getName();
712  return failure();
713  }
714 
715  // If its an instance operaiton, perform some checking and possibly
716  // recurse.
717  if (auto aInst = dyn_cast<FInstanceLike>(a)) {
718  auto bInst = cast<FInstanceLike>(b);
719  if (failed(check(diag, aInst, bInst)))
720  return failure();
721  }
722 
723  // Operation results.
724  if (a->getNumResults() != b->getNumResults()) {
725  diag.attachNote(a->getLoc())
726  << "operations have different number of results";
727  diag.attachNote(b->getLoc()) << "second operation here";
728  return failure();
729  }
730  for (auto resultPair : llvm::zip(a->getResults(), b->getResults())) {
731  auto &aValue = std::get<0>(resultPair);
732  auto &bValue = std::get<1>(resultPair);
733  if (failed(check(diag, "operation result", a, aValue.getType(), b,
734  bValue.getType())))
735  return failure();
736  data.map.map(aValue, bValue);
737  }
738 
739  // Operations operands.
740  if (a->getNumOperands() != b->getNumOperands()) {
741  diag.attachNote(a->getLoc())
742  << "operations have different number of operands";
743  diag.attachNote(b->getLoc()) << "second operation here";
744  return failure();
745  }
746  for (auto operandPair : llvm::zip(a->getOperands(), b->getOperands())) {
747  auto &aValue = std::get<0>(operandPair);
748  auto &bValue = std::get<1>(operandPair);
749  if (bValue != data.map.lookup(aValue)) {
750  diag.attachNote(a->getLoc())
751  << "operations use different operands, first operand is '"
752  << getFieldName(
753  getFieldRefFromValue(aValue, /*lookThroughCasts=*/true))
754  .first
755  << "'";
756  diag.attachNote(b->getLoc())
757  << "second operand is '"
758  << getFieldName(
759  getFieldRefFromValue(bValue, /*lookThroughCasts=*/true))
760  .first
761  << "', but should have been '"
762  << getFieldName(getFieldRefFromValue(data.map.lookup(aValue),
763  /*lookThroughCasts=*/true))
764  .first
765  << "'";
766  return failure();
767  }
768  }
769  data.map.map(a, b);
770 
771  // Operation regions.
772  if (a->getNumRegions() != b->getNumRegions()) {
773  diag.attachNote(a->getLoc())
774  << "operations have different number of regions";
775  diag.attachNote(b->getLoc()) << "second operation here";
776  return failure();
777  }
778  for (auto regionPair : llvm::zip(a->getRegions(), b->getRegions())) {
779  auto &aRegion = std::get<0>(regionPair);
780  auto &bRegion = std::get<1>(regionPair);
781  if (failed(check(diag, data, a, aRegion, b, bRegion)))
782  return failure();
783  }
784 
785  // Operation attributes.
786  if (failed(check(diag, data, a, a->getAttrDictionary(), b,
787  b->getAttrDictionary())))
788  return failure();
789  return success();
790  }
791 
792  // NOLINTNEXTLINE(misc-no-recursion)
793  void check(InFlightDiagnostic &diag, Operation *a, Operation *b) {
794  hw::InnerSymbolTable aTable(a);
795  hw::InnerSymbolTable bTable(b);
796  ModuleData data(aTable, bTable);
797  if (AnnotationSet::hasAnnotation(a, noDedupClass)) {
798  diag.attachNote(a->getLoc()) << "module marked NoDedup";
799  return;
800  }
801  if (AnnotationSet::hasAnnotation(b, noDedupClass)) {
802  diag.attachNote(b->getLoc()) << "module marked NoDedup";
803  return;
804  }
805  auto aSymbol = cast<mlir::SymbolOpInterface>(a);
806  auto bSymbol = cast<mlir::SymbolOpInterface>(b);
807  if (!checkVisibility(aSymbol)) {
808  diag.attachNote(a->getLoc())
809  << "module is "
810  << (aSymbol.isPrivate() ? "private but not discardable" : "public");
811  return;
812  }
813  if (!checkVisibility(bSymbol)) {
814  diag.attachNote(b->getLoc())
815  << "module is "
816  << (bSymbol.isPrivate() ? "private but not discardable" : "public");
817  return;
818  }
819  auto aGroup =
820  dyn_cast_or_null<StringAttr>(a->getDiscardableAttr(dedupGroupAttrName));
821  auto bGroup = dyn_cast_or_null<StringAttr>(
822  b->getAttrOfType<StringAttr>(dedupGroupAttrName));
823  if (aGroup != bGroup) {
824  if (bGroup) {
825  diag.attachNote(b->getLoc())
826  << "module is in dedup group '" << bGroup.str() << "'";
827  } else {
828  diag.attachNote(b->getLoc()) << "module is not part of a dedup group";
829  }
830  if (aGroup) {
831  diag.attachNote(a->getLoc())
832  << "module is in dedup group '" << aGroup.str() << "'";
833  } else {
834  diag.attachNote(a->getLoc()) << "module is not part of a dedup group";
835  }
836  return;
837  }
838  if (failed(check(diag, data, a, b)))
839  return;
840  diag.attachNote(a->getLoc()) << "first module here";
841  diag.attachNote(b->getLoc()) << "second module here";
842  }
843 
844  // This is a cached "portDirections" string attr.
845  StringAttr portDirectionsAttr;
846  // This is a cached "NoDedup" annotation class string attr.
847  StringAttr noDedupClass;
848  // This is a cached string attr for the dedup group attribute.
849  StringAttr dedupGroupAttrName;
850 
851  // This is a set of every attribute we should ignore.
852  DenseSet<Attribute> nonessentialAttributes;
854 };
855 
856 //===----------------------------------------------------------------------===//
857 // Deduplication
858 //===----------------------------------------------------------------------===//
859 
860 // Custom location merging. This only keeps track of 8 annotations from ".fir"
861 // files, and however many annotations come from "real" sources. When
862 // deduplicating, modules tend not to have scala source locators, so we wind
863 // up fusing source locators for a module from every copy being deduped. There
864 // is little value in this (all the modules are identical by definition).
865 static Location mergeLoc(MLIRContext *context, Location to, Location from) {
866  // Unique the set of locations to be fused.
867  llvm::SmallSetVector<Location, 4> decomposedLocs;
868  // only track 8 "fir" locations
869  unsigned seenFIR = 0;
870  for (auto loc : {to, from}) {
871  // If the location is a fused location we decompose it if it has no
872  // metadata or the metadata is the same as the top level metadata.
873  if (auto fusedLoc = dyn_cast<FusedLoc>(loc)) {
874  // UnknownLoc's have already been removed from FusedLocs so we can
875  // simply add all of the internal locations.
876  for (auto loc : fusedLoc.getLocations()) {
877  if (FileLineColLoc fileLoc = dyn_cast<FileLineColLoc>(loc)) {
878  if (fileLoc.getFilename().strref().ends_with(".fir")) {
879  ++seenFIR;
880  if (seenFIR > 8)
881  continue;
882  }
883  }
884  decomposedLocs.insert(loc);
885  }
886  continue;
887  }
888 
889  // Might need to skip this fir.
890  if (FileLineColLoc fileLoc = dyn_cast<FileLineColLoc>(loc)) {
891  if (fileLoc.getFilename().strref().ends_with(".fir")) {
892  ++seenFIR;
893  if (seenFIR > 8)
894  continue;
895  }
896  }
897  // Otherwise, only add known locations to the set.
898  if (!isa<UnknownLoc>(loc))
899  decomposedLocs.insert(loc);
900  }
901 
902  auto locs = decomposedLocs.getArrayRef();
903 
904  // Handle the simple cases of less than two locations. Ensure the metadata (if
905  // provided) is not dropped.
906  if (locs.empty())
907  return UnknownLoc::get(context);
908  if (locs.size() == 1)
909  return locs.front();
910 
911  return FusedLoc::get(context, locs);
912 }
913 
914 struct Deduper {
915 
916  using RenameMap = DenseMap<StringAttr, StringAttr>;
917 
918  Deduper(InstanceGraph &instanceGraph, SymbolTable &symbolTable,
919  NLATable *nlaTable, CircuitOp circuit)
920  : context(circuit->getContext()), instanceGraph(instanceGraph),
921  symbolTable(symbolTable), nlaTable(nlaTable),
922  nlaBlock(circuit.getBodyBlock()),
923  nonLocalString(StringAttr::get(context, "circt.nonlocal")),
924  classString(StringAttr::get(context, "class")) {
925  // Populate the NLA cache.
926  for (auto nla : circuit.getOps<hw::HierPathOp>())
927  nlaCache[nla.getNamepathAttr()] = nla.getSymNameAttr();
928  }
929 
930  /// Remove the "fromModule", and replace all references to it with the
931  /// "toModule". Modules should be deduplicated in a bottom-up order. Any
932  /// module which is not deduplicated needs to be recorded with the `record`
933  /// call.
934  void dedup(FModuleLike toModule, FModuleLike fromModule) {
935  // A map of operation (e.g. wires, nodes) names which are changed, which is
936  // used to update NLAs that reference the "fromModule".
937  RenameMap renameMap;
938 
939  // Merge the port locations.
940  SmallVector<Attribute> newLocs;
941  for (auto [toLoc, fromLoc] : llvm::zip(toModule.getPortLocations(),
942  fromModule.getPortLocations())) {
943  if (toLoc == fromLoc)
944  newLocs.push_back(toLoc);
945  else
946  newLocs.push_back(mergeLoc(context, cast<LocationAttr>(toLoc),
947  cast<LocationAttr>(fromLoc)));
948  }
949  toModule->setAttr("portLocations", ArrayAttr::get(context, newLocs));
950 
951  // Merge the two modules.
952  mergeOps(renameMap, toModule, toModule, fromModule, fromModule);
953 
954  // Rewrite NLAs pathing through these modules to refer to the to module. It
955  // is safe to do this at this point because NLAs cannot be one element long.
956  // This means that all NLAs which require more context cannot be targetting
957  // something in the module it self.
958  if (auto to = dyn_cast<FModuleOp>(*toModule))
959  rewriteModuleNLAs(renameMap, to, cast<FModuleOp>(*fromModule));
960  else
961  rewriteExtModuleNLAs(renameMap, toModule.getModuleNameAttr(),
962  fromModule.getModuleNameAttr());
963 
964  replaceInstances(toModule, fromModule);
965  }
966 
967  /// Record the usages of any NLA's in this module, so that we may update the
968  /// annotation if the parent module is deduped with another module.
969  void record(FModuleLike module) {
970  // Record any annotations on the module.
971  recordAnnotations(module);
972  // Record port annotations.
973  for (unsigned i = 0, e = getNumPorts(module); i < e; ++i)
974  recordAnnotations(PortAnnoTarget(module, i));
975  // Record any annotations in the module body.
976  module->walk([&](Operation *op) { recordAnnotations(op); });
977  }
978 
979 private:
980  /// Get a cached namespace for a module.
981  hw::InnerSymbolNamespace &getNamespace(Operation *module) {
982  return moduleNamespaces.try_emplace(module, cast<FModuleLike>(module))
983  .first->second;
984  }
985 
986  /// For a specific annotation target, record all the unique NLAs which
987  /// target it in the `targetMap`.
989  for (auto anno : target.getAnnotations())
990  if (auto nlaRef = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal"))
991  targetMap[nlaRef.getAttr()].insert(target);
992  }
993 
994  /// Record all targets which use an NLA.
995  void recordAnnotations(Operation *op) {
996  // Record annotations.
997  recordAnnotations(OpAnnoTarget(op));
998 
999  // Record port annotations only if this is a mem operation.
1000  auto mem = dyn_cast<MemOp>(op);
1001  if (!mem)
1002  return;
1003 
1004  // Record port annotations.
1005  for (unsigned i = 0, e = mem->getNumResults(); i < e; ++i)
1006  recordAnnotations(PortAnnoTarget(mem, i));
1007  }
1008 
1009  /// This deletes and replaces all instances of the "fromModule" with instances
1010  /// of the "toModule".
1011  void replaceInstances(FModuleLike toModule, Operation *fromModule) {
1012  // Replace all instances of the other module.
1013  auto *fromNode =
1014  instanceGraph[::cast<igraph::ModuleOpInterface>(fromModule)];
1015  auto *toNode = instanceGraph[toModule];
1016  auto toModuleRef = FlatSymbolRefAttr::get(toModule.getModuleNameAttr());
1017  for (auto *oldInstRec : llvm::make_early_inc_range(fromNode->uses())) {
1018  auto inst = oldInstRec->getInstance();
1019  if (auto instOp = dyn_cast<InstanceOp>(*inst)) {
1020  instOp.setModuleNameAttr(toModuleRef);
1021  instOp.setPortNamesAttr(toModule.getPortNamesAttr());
1022  } else if (auto objectOp = dyn_cast<ObjectOp>(*inst)) {
1023  auto classLike = cast<ClassLike>(*toNode->getModule());
1024  ClassType classType = detail::getInstanceTypeForClassLike(classLike);
1025  objectOp.getResult().setType(classType);
1026  }
1027  oldInstRec->getParent()->addInstance(inst, toNode);
1028  oldInstRec->erase();
1029  }
1030  instanceGraph.erase(fromNode);
1031  fromModule->erase();
1032  }
1033 
1034  /// Look up the instantiations of the `from` module and create an NLA for each
1035  /// one, appending the baseNamepath to each NLA. This is used to add more
1036  /// context to an already existing NLA. The `fromModule` is used to indicate
1037  /// which module the annotation is coming from before the merge, and will be
1038  /// used to create the namepaths.
1039  SmallVector<FlatSymbolRefAttr>
1040  createNLAs(Operation *fromModule, ArrayRef<Attribute> baseNamepath,
1041  SymbolTable::Visibility vis = SymbolTable::Visibility::Private) {
1042  // Create an attribute array with a placeholder in the first element, where
1043  // the root refence of the NLA will be inserted.
1044  SmallVector<Attribute> namepath = {nullptr};
1045  namepath.append(baseNamepath.begin(), baseNamepath.end());
1046 
1047  auto loc = fromModule->getLoc();
1048  auto *fromNode = instanceGraph[cast<igraph::ModuleOpInterface>(fromModule)];
1049  SmallVector<FlatSymbolRefAttr> nlas;
1050  for (auto *instanceRecord : fromNode->uses()) {
1051  auto parent = cast<FModuleOp>(*instanceRecord->getParent()->getModule());
1052  auto inst = instanceRecord->getInstance();
1053  namepath[0] = OpAnnoTarget(inst).getNLAReference(getNamespace(parent));
1054  auto arrayAttr = ArrayAttr::get(context, namepath);
1055  // Check the NLA cache to see if we already have this NLA.
1056  auto &cacheEntry = nlaCache[arrayAttr];
1057  if (!cacheEntry) {
1058  auto nla = OpBuilder::atBlockBegin(nlaBlock).create<hw::HierPathOp>(
1059  loc, "nla", arrayAttr);
1060  // Insert it into the symbol table to get a unique name.
1061  symbolTable.insert(nla);
1062  // Store it in the cache.
1063  cacheEntry = nla.getNameAttr();
1064  nla.setVisibility(vis);
1065  nlaTable->addNLA(nla);
1066  }
1067  auto nlaRef = FlatSymbolRefAttr::get(cast<StringAttr>(cacheEntry));
1068  nlas.push_back(nlaRef);
1069  }
1070  return nlas;
1071  }
1072 
1073  /// Look up the instantiations of this module and create an NLA for each one.
1074  /// This returns an array of symbol references which can be used to reference
1075  /// the NLAs.
1076  SmallVector<FlatSymbolRefAttr>
1077  createNLAs(StringAttr toModuleName, FModuleLike fromModule,
1078  SymbolTable::Visibility vis = SymbolTable::Visibility::Private) {
1079  return createNLAs(fromModule, FlatSymbolRefAttr::get(toModuleName), vis);
1080  }
1081 
1082  /// Clone the annotation for each NLA in a list. The attribute list should
1083  /// have a placeholder for the "circt.nonlocal" field, and `nonLocalIndex`
1084  /// should be the index of this field.
1085  void cloneAnnotation(SmallVectorImpl<FlatSymbolRefAttr> &nlas,
1086  Annotation anno, ArrayRef<NamedAttribute> attributes,
1087  unsigned nonLocalIndex,
1088  SmallVectorImpl<Annotation> &newAnnotations) {
1089  SmallVector<NamedAttribute> mutableAttributes(attributes.begin(),
1090  attributes.end());
1091  for (auto &nla : nlas) {
1092  // Add the new annotation.
1093  mutableAttributes[nonLocalIndex].setValue(nla);
1094  auto dict = DictionaryAttr::getWithSorted(context, mutableAttributes);
1095  // The original annotation records if its a subannotation.
1096  anno.setDict(dict);
1097  newAnnotations.push_back(anno);
1098  }
1099  }
1100 
1101  /// This erases the NLA op, and removes the NLA from every module's NLA map,
1102  /// but it does not delete the NLA reference from the target operation's
1103  /// annotations.
1104  void eraseNLA(hw::HierPathOp nla) {
1105  // Erase the NLA from the leaf module's nlaMap.
1106  targetMap.erase(nla.getNameAttr());
1107  nlaTable->erase(nla);
1108  nlaCache.erase(nla.getNamepathAttr());
1109  symbolTable.erase(nla);
1110  }
1111 
1112  /// Process all NLAs referencing the "from" module to point to the "to"
1113  /// module. This is used after merging two modules together.
1114  void addAnnotationContext(RenameMap &renameMap, FModuleOp toModule,
1115  FModuleOp fromModule) {
1116  auto toName = toModule.getNameAttr();
1117  auto fromName = fromModule.getNameAttr();
1118  // Create a copy of the current NLAs. We will be pushing and removing
1119  // NLAs from this op as we go.
1120  auto moduleNLAs = nlaTable->lookup(fromModule.getNameAttr()).vec();
1121  // Change the NLA to target the toModule.
1122  nlaTable->renameModuleAndInnerRef(toName, fromName, renameMap);
1123  // Now we walk the NLA searching for ones that require more context to be
1124  // added.
1125  for (auto nla : moduleNLAs) {
1126  auto elements = nla.getNamepath().getValue();
1127  // If we don't need to add more context, we're done here.
1128  if (nla.root() != toName)
1129  continue;
1130  // Create the replacement NLAs.
1131  SmallVector<Attribute> namepath(elements.begin(), elements.end());
1132  auto nlaRefs = createNLAs(fromModule, namepath, nla.getVisibility());
1133  // Copy out the targets, because we will be updating the map.
1134  auto &set = targetMap[nla.getSymNameAttr()];
1135  SmallVector<AnnoTarget> targets(set.begin(), set.end());
1136  // Replace the uses of the old NLA with the new NLAs.
1137  for (auto target : targets) {
1138  // We have to clone any annotation which uses the old NLA for each new
1139  // NLA. This array collects the new set of annotations.
1140  SmallVector<Annotation> newAnnotations;
1141  for (auto anno : target.getAnnotations()) {
1142  // Find the non-local field of the annotation.
1143  auto [it, found] = mlir::impl::findAttrSorted(
1144  anno.begin(), anno.end(), nonLocalString);
1145  // If this annotation doesn't use the target NLA, copy it with no
1146  // changes.
1147  if (!found || cast<FlatSymbolRefAttr>(it->getValue()).getAttr() !=
1148  nla.getSymNameAttr()) {
1149  newAnnotations.push_back(anno);
1150  continue;
1151  }
1152  auto nonLocalIndex = std::distance(anno.begin(), it);
1153  // Clone the annotation and add it to the list of new annotations.
1154  cloneAnnotation(nlaRefs, anno,
1155  ArrayRef<NamedAttribute>(anno.begin(), anno.end()),
1156  nonLocalIndex, newAnnotations);
1157  }
1158 
1159  // Apply the new annotations to the operation.
1160  AnnotationSet annotations(newAnnotations, context);
1161  target.setAnnotations(annotations);
1162  // Record that target uses the NLA.
1163  for (auto nla : nlaRefs)
1164  targetMap[nla.getAttr()].insert(target);
1165  }
1166 
1167  // Erase the old NLA and remove it from all breadcrumbs.
1168  eraseNLA(nla);
1169  }
1170  }
1171 
1172  /// Process all the NLAs that the two modules participate in, replacing
1173  /// references to the "from" module with references to the "to" module, and
1174  /// adding more context if necessary.
1175  void rewriteModuleNLAs(RenameMap &renameMap, FModuleOp toModule,
1176  FModuleOp fromModule) {
1177  addAnnotationContext(renameMap, toModule, toModule);
1178  addAnnotationContext(renameMap, toModule, fromModule);
1179  }
1180 
1181  // Update all NLAs which the "from" external module participates in to the
1182  // "toName".
1183  void rewriteExtModuleNLAs(RenameMap &renameMap, StringAttr toName,
1184  StringAttr fromName) {
1185  nlaTable->renameModuleAndInnerRef(toName, fromName, renameMap);
1186  }
1187 
1188  /// Take an annotation, and update it to be a non-local annotation. If the
1189  /// annotation is already non-local and has enough context, it will be skipped
1190  /// for now. Return true if the annotation was made non-local.
1191  bool makeAnnotationNonLocal(StringAttr toModuleName, AnnoTarget to,
1192  FModuleLike fromModule, Annotation anno,
1193  SmallVectorImpl<Annotation> &newAnnotations) {
1194  // Start constructing a new annotation, pushing a "circt.nonLocal" field
1195  // into the correct spot if its not already a non-local annotation.
1196  SmallVector<NamedAttribute> attributes;
1197  int nonLocalIndex = -1;
1198  for (const auto &val : llvm::enumerate(anno)) {
1199  auto attr = val.value();
1200  // Is this field "circt.nonlocal"?
1201  auto compare = attr.getName().compare(nonLocalString);
1202  assert(compare != 0 && "should not pass non-local annotations here");
1203  if (compare == 1) {
1204  // This annotation definitely does not have "circt.nonlocal" field. Push
1205  // an empty place holder for the non-local annotation.
1206  nonLocalIndex = val.index();
1207  attributes.push_back(NamedAttribute(nonLocalString, nonLocalString));
1208  break;
1209  }
1210  // Otherwise push the current attribute and keep searching for the
1211  // "circt.nonlocal" field.
1212  attributes.push_back(attr);
1213  }
1214  if (nonLocalIndex == -1) {
1215  // Push an empty "circt.nonlocal" field to the last slot.
1216  nonLocalIndex = attributes.size();
1217  attributes.push_back(NamedAttribute(nonLocalString, nonLocalString));
1218  } else {
1219  // Copy the remaining annotation fields in.
1220  attributes.append(anno.begin() + nonLocalIndex, anno.end());
1221  }
1222 
1223  // Construct the NLAs if we don't have any yet.
1224  auto nlaRefs = createNLAs(toModuleName, fromModule);
1225  for (auto nla : nlaRefs)
1226  targetMap[nla.getAttr()].insert(to);
1227 
1228  // Clone the annotation for each new NLA.
1229  cloneAnnotation(nlaRefs, anno, attributes, nonLocalIndex, newAnnotations);
1230  return true;
1231  }
1232 
1233  void copyAnnotations(FModuleLike toModule, AnnoTarget to,
1234  FModuleLike fromModule, AnnotationSet annos,
1235  SmallVectorImpl<Annotation> &newAnnotations,
1236  SmallPtrSetImpl<Attribute> &dontTouches) {
1237  for (auto anno : annos) {
1238  if (anno.isClass(dontTouchAnnoClass)) {
1239  // Remove the nonlocal field of the annotation if it has one, since this
1240  // is a sticky annotation.
1241  anno.removeMember("circt.nonlocal");
1242  auto [it, inserted] = dontTouches.insert(anno.getAttr());
1243  if (inserted)
1244  newAnnotations.push_back(anno);
1245  continue;
1246  }
1247  // If the annotation is already non-local, we add it as is. It is already
1248  // added to the target map.
1249  if (auto nla = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal")) {
1250  newAnnotations.push_back(anno);
1251  targetMap[nla.getAttr()].insert(to);
1252  continue;
1253  }
1254  // Otherwise make the annotation non-local and add it to the set.
1255  makeAnnotationNonLocal(toModule.getModuleNameAttr(), to, fromModule, anno,
1256  newAnnotations);
1257  }
1258  }
1259 
1260  /// Merge the annotations of a specific target, either a operation or a port
1261  /// on an operation.
1262  void mergeAnnotations(FModuleLike toModule, AnnoTarget to,
1263  AnnotationSet toAnnos, FModuleLike fromModule,
1264  AnnoTarget from, AnnotationSet fromAnnos) {
1265  // This is a list of all the annotations which will be added to `to`.
1266  SmallVector<Annotation> newAnnotations;
1267 
1268  // We have special case handling of DontTouch to prevent it from being
1269  // turned into a non-local annotation, and to remove duplicates.
1270  llvm::SmallPtrSet<Attribute, 4> dontTouches;
1271 
1272  // Iterate the annotations, transforming most annotations into non-local
1273  // ones.
1274  copyAnnotations(toModule, to, toModule, toAnnos, newAnnotations,
1275  dontTouches);
1276  copyAnnotations(toModule, to, fromModule, fromAnnos, newAnnotations,
1277  dontTouches);
1278 
1279  // Copy over all the new annotations.
1280  if (!newAnnotations.empty())
1281  to.setAnnotations(AnnotationSet(newAnnotations, context));
1282  }
1283 
1284  /// Merge all annotations and port annotations on two operations.
1285  void mergeAnnotations(FModuleLike toModule, Operation *to,
1286  FModuleLike fromModule, Operation *from) {
1287  // Merge op annotations.
1288  mergeAnnotations(toModule, OpAnnoTarget(to), AnnotationSet(to), fromModule,
1289  OpAnnoTarget(from), AnnotationSet(from));
1290 
1291  // Merge port annotations.
1292  if (toModule == to) {
1293  // Merge module port annotations.
1294  for (unsigned i = 0, e = getNumPorts(toModule); i < e; ++i)
1295  mergeAnnotations(toModule, PortAnnoTarget(toModule, i),
1296  AnnotationSet::forPort(toModule, i), fromModule,
1297  PortAnnoTarget(fromModule, i),
1298  AnnotationSet::forPort(fromModule, i));
1299  } else if (auto toMem = dyn_cast<MemOp>(to)) {
1300  // Merge memory port annotations.
1301  auto fromMem = cast<MemOp>(from);
1302  for (unsigned i = 0, e = toMem.getNumResults(); i < e; ++i)
1303  mergeAnnotations(toModule, PortAnnoTarget(toMem, i),
1304  AnnotationSet::forPort(toMem, i), fromModule,
1305  PortAnnoTarget(fromMem, i),
1306  AnnotationSet::forPort(fromMem, i));
1307  }
1308  }
1309 
1310  // Record the symbol name change of the operation or any of its ports when
1311  // merging two operations. The renamed symbols are used to update the
1312  // target of any NLAs. This will add symbols to the "to" operation if needed.
1313  void recordSymRenames(RenameMap &renameMap, FModuleLike toModule,
1314  Operation *to, FModuleLike fromModule,
1315  Operation *from) {
1316  // If the "from" operation has an inner_sym, we need to make sure the
1317  // "to" operation also has an `inner_sym` and then record the renaming.
1318  if (auto fromSym = getInnerSymName(from)) {
1319  auto toSym =
1320  getOrAddInnerSym(to, [&](auto _) -> hw::InnerSymbolNamespace & {
1321  return getNamespace(toModule);
1322  });
1323  renameMap[fromSym] = toSym;
1324  }
1325 
1326  // If there are no port symbols on the "from" operation, we are done here.
1327  auto fromPortSyms = from->getAttrOfType<ArrayAttr>("portSyms");
1328  if (!fromPortSyms || fromPortSyms.empty())
1329  return;
1330  // We have to map each "fromPort" to each "toPort".
1331  auto &moduleNamespace = getNamespace(toModule);
1332  auto portCount = fromPortSyms.size();
1333  auto portNames = to->getAttrOfType<ArrayAttr>("portNames");
1334  auto toPortSyms = to->getAttrOfType<ArrayAttr>("portSyms");
1335 
1336  // Create an array of new port symbols for the "to" operation, copy in the
1337  // old symbols if it has any, create an empty symbol array if it doesn't.
1338  SmallVector<Attribute> newPortSyms;
1339  if (toPortSyms.empty())
1340  newPortSyms.assign(portCount, hw::InnerSymAttr());
1341  else
1342  newPortSyms.assign(toPortSyms.begin(), toPortSyms.end());
1343 
1344  for (unsigned portNo = 0; portNo < portCount; ++portNo) {
1345  // If this fromPort doesn't have a symbol, move on to the next one.
1346  if (!fromPortSyms[portNo])
1347  continue;
1348  auto fromSym = cast<hw::InnerSymAttr>(fromPortSyms[portNo]);
1349 
1350  // If this toPort doesn't have a symbol, assign one.
1351  hw::InnerSymAttr toSym;
1352  if (!newPortSyms[portNo]) {
1353  // Get a reasonable base name for the port.
1354  StringRef symName = "inner_sym";
1355  if (portNames)
1356  symName = cast<StringAttr>(portNames[portNo]).getValue();
1357  // Create the symbol and store it into the array.
1358  toSym = hw::InnerSymAttr::get(
1359  StringAttr::get(context, moduleNamespace.newName(symName)));
1360  newPortSyms[portNo] = toSym;
1361  } else
1362  toSym = cast<hw::InnerSymAttr>(newPortSyms[portNo]);
1363 
1364  // Record the renaming.
1365  renameMap[fromSym.getSymName()] = toSym.getSymName();
1366  }
1367 
1368  // Commit the new symbol attribute.
1369  cast<FModuleLike>(to).setPortSymbols(newPortSyms);
1370  }
1371 
1372  /// Recursively merge two operations.
1373  // NOLINTNEXTLINE(misc-no-recursion)
1374  void mergeOps(RenameMap &renameMap, FModuleLike toModule, Operation *to,
1375  FModuleLike fromModule, Operation *from) {
1376  // Merge the operation locations.
1377  if (to->getLoc() != from->getLoc())
1378  to->setLoc(mergeLoc(context, to->getLoc(), from->getLoc()));
1379 
1380  // Recurse into any regions.
1381  for (auto regions : llvm::zip(to->getRegions(), from->getRegions()))
1382  mergeRegions(renameMap, toModule, std::get<0>(regions), fromModule,
1383  std::get<1>(regions));
1384 
1385  // Record any inner_sym renamings that happened.
1386  recordSymRenames(renameMap, toModule, to, fromModule, from);
1387 
1388  // Merge the annotations.
1389  mergeAnnotations(toModule, to, fromModule, from);
1390  }
1391 
1392  /// Recursively merge two blocks.
1393  void mergeBlocks(RenameMap &renameMap, FModuleLike toModule, Block &toBlock,
1394  FModuleLike fromModule, Block &fromBlock) {
1395  // Merge the block locations.
1396  for (auto [toArg, fromArg] :
1397  llvm::zip(toBlock.getArguments(), fromBlock.getArguments()))
1398  if (toArg.getLoc() != fromArg.getLoc())
1399  toArg.setLoc(mergeLoc(context, toArg.getLoc(), fromArg.getLoc()));
1400 
1401  for (auto ops : llvm::zip(toBlock, fromBlock))
1402  mergeOps(renameMap, toModule, &std::get<0>(ops), fromModule,
1403  &std::get<1>(ops));
1404  }
1405 
1406  // Recursively merge two regions.
1407  void mergeRegions(RenameMap &renameMap, FModuleLike toModule,
1408  Region &toRegion, FModuleLike fromModule,
1409  Region &fromRegion) {
1410  for (auto blocks : llvm::zip(toRegion, fromRegion))
1411  mergeBlocks(renameMap, toModule, std::get<0>(blocks), fromModule,
1412  std::get<1>(blocks));
1413  }
1414 
1415  MLIRContext *context;
1417  SymbolTable &symbolTable;
1418 
1419  /// Cached nla table analysis.
1420  NLATable *nlaTable = nullptr;
1421 
1422  /// We insert all NLAs to the beginning of this block.
1423  Block *nlaBlock;
1424 
1425  // This maps an NLA to the operations and ports that uses it.
1426  DenseMap<Attribute, llvm::SmallDenseSet<AnnoTarget>> targetMap;
1427 
1428  // This is a cache to avoid creating duplicate NLAs. This maps the ArrayAtr
1429  // of the NLA's path to the name of the NLA which contains it.
1430  DenseMap<Attribute, Attribute> nlaCache;
1431 
1432  // Cached attributes for faster comparisons and attribute building.
1433  StringAttr nonLocalString;
1434  StringAttr classString;
1435 
1436  /// A module namespace cache.
1437  DenseMap<Operation *, hw::InnerSymbolNamespace> moduleNamespaces;
1438 };
1439 
1440 //===----------------------------------------------------------------------===//
1441 // Fixup
1442 //===----------------------------------------------------------------------===//
1443 
1444 /// This fixes up ClassLikes with ClassType ports, when the classes have
1445 /// deduped. For each ClassType port, if the object reference being assigned is
1446 /// a different type, update the port type. Returns true if the ClassOp was
1447 /// updated and the associated ObjectOps should be updated.
1448 bool fixupClassOp(ClassOp classOp) {
1449  // New port type attributes, if necessary.
1450  SmallVector<Attribute> newPortTypes;
1451  bool anyDifferences = false;
1452 
1453  // Check each port.
1454  for (size_t i = 0, e = classOp.getNumPorts(); i < e; ++i) {
1455  // Check if this port is a ClassType. If not, save the original type
1456  // attribute in case we need to update port types.
1457  auto portClassType = dyn_cast<ClassType>(classOp.getPortType(i));
1458  if (!portClassType) {
1459  newPortTypes.push_back(classOp.getPortTypeAttr(i));
1460  continue;
1461  }
1462 
1463  // Check if this port is assigned a reference of a different ClassType.
1464  Type newPortClassType;
1465  BlockArgument portArg = classOp.getArgument(i);
1466  for (auto &use : portArg.getUses()) {
1467  if (auto propassign = dyn_cast<PropAssignOp>(use.getOwner())) {
1468  Type sourceType = propassign.getSrc().getType();
1469  if (propassign.getDest() == use.get() && sourceType != portClassType) {
1470  // Double check that all references are the same new type.
1471  if (newPortClassType) {
1472  assert(newPortClassType == sourceType &&
1473  "expected all references to be of the same type");
1474  continue;
1475  }
1476 
1477  newPortClassType = sourceType;
1478  }
1479  }
1480  }
1481 
1482  // If there was no difference, save the original type attribute in case we
1483  // need to update port types and move along.
1484  if (!newPortClassType) {
1485  newPortTypes.push_back(classOp.getPortTypeAttr(i));
1486  continue;
1487  }
1488 
1489  // The port type changed, so update the block argument, save the new port
1490  // type attribute, and indicate there was a difference.
1491  classOp.getArgument(i).setType(newPortClassType);
1492  newPortTypes.push_back(TypeAttr::get(newPortClassType));
1493  anyDifferences = true;
1494  }
1495 
1496  // If necessary, update port types.
1497  if (anyDifferences)
1498  classOp.setPortTypes(newPortTypes);
1499 
1500  return anyDifferences;
1501 }
1502 
1503 /// This fixes up ObjectOps when the signature of their ClassOp changes. This
1504 /// amounts to updating the ObjectOp result type to match the newly updated
1505 /// ClassOp type.
1506 void fixupObjectOp(ObjectOp objectOp, ClassType newClassType) {
1507  objectOp.getResult().setType(newClassType);
1508 }
1509 
1510 /// This fixes up connects when the field names of a bundle type changes. It
1511 /// finds all fields which were previously bulk connected and legalizes it
1512 /// into a connect for each field.
1513 void fixupConnect(ImplicitLocOpBuilder &builder, Value dst, Value src) {
1514  // If the types already match we can emit a connect.
1515  auto dstType = dst.getType();
1516  auto srcType = src.getType();
1517  if (dstType == srcType) {
1518  emitConnect(builder, dst, src);
1519  return;
1520  }
1521  // It must be a bundle type and the field name has changed. We have to
1522  // manually decompose the bulk connect into a connect for each field.
1523  auto dstBundle = type_cast<BundleType>(dstType);
1524  auto srcBundle = type_cast<BundleType>(srcType);
1525  for (unsigned i = 0; i < dstBundle.getNumElements(); ++i) {
1526  auto dstField = builder.create<SubfieldOp>(dst, i);
1527  auto srcField = builder.create<SubfieldOp>(src, i);
1528  if (dstBundle.getElement(i).isFlip) {
1529  std::swap(srcBundle, dstBundle);
1530  std::swap(srcField, dstField);
1531  }
1532  fixupConnect(builder, dstField, srcField);
1533  }
1534 }
1535 
1536 /// This is the root method to fixup module references when a module changes.
1537 /// It matches all the results of "to" module with the results of the "from"
1538 /// module.
1539 void fixupAllModules(InstanceGraph &instanceGraph) {
1540  for (auto *node : instanceGraph) {
1541  auto module = cast<FModuleLike>(*node->getModule());
1542 
1543  // Handle class declarations here.
1544  bool shouldFixupObjects = false;
1545  auto classOp = dyn_cast<ClassOp>(module.getOperation());
1546  if (classOp)
1547  shouldFixupObjects = fixupClassOp(classOp);
1548 
1549  for (auto *instRec : node->uses()) {
1550  // Handle object instantiations here.
1551  if (classOp) {
1552  if (shouldFixupObjects) {
1553  fixupObjectOp(instRec->getInstance<ObjectOp>(),
1554  classOp.getInstanceType());
1555  }
1556  continue;
1557  }
1558 
1559  auto inst = instRec->getInstance<InstanceOp>();
1560  // Only handle module instantiations here.
1561  if (!inst)
1562  continue;
1563  ImplicitLocOpBuilder builder(inst.getLoc(), inst->getContext());
1564  builder.setInsertionPointAfter(inst);
1565  for (size_t i = 0, e = getNumPorts(module); i < e; ++i) {
1566  auto result = inst.getResult(i);
1567  auto newType = module.getPortType(i);
1568  auto oldType = result.getType();
1569  // If the type has not changed, we don't have to fix up anything.
1570  if (newType == oldType)
1571  continue;
1572  // If the type changed we transform it back to the old type with an
1573  // intermediate wire.
1574  auto wire =
1575  builder.create<WireOp>(oldType, inst.getPortName(i)).getResult();
1576  result.replaceAllUsesWith(wire);
1577  result.setType(newType);
1578  if (inst.getPortDirection(i) == Direction::Out)
1579  fixupConnect(builder, wire, result);
1580  else
1581  fixupConnect(builder, result, wire);
1582  }
1583  }
1584  }
1585 }
1586 
1587 namespace llvm {
1588 /// A DenseMapInfo implementation for `ModuleInfo` that is a pair of
1589 /// llvm::SHA256 hashes, which are represented as std::array<uint8_t, 32>, and
1590 /// an array of string attributes. This allows us to create a DenseMap with
1591 /// `ModuleInfo` as keys.
1592 template <>
1593 struct DenseMapInfo<ModuleInfo> {
1594  static inline ModuleInfo getEmptyKey() {
1595  std::array<uint8_t, 32> key;
1596  std::fill(key.begin(), key.end(), ~0);
1597  return {key, DenseMapInfo<mlir::ArrayAttr>::getEmptyKey()};
1598  }
1599 
1600  static inline ModuleInfo getTombstoneKey() {
1601  std::array<uint8_t, 32> key;
1602  std::fill(key.begin(), key.end(), ~0 - 1);
1603  return {key, DenseMapInfo<mlir::ArrayAttr>::getTombstoneKey()};
1604  }
1605 
1606  static unsigned getHashValue(const ModuleInfo &val) {
1607  // We assume SHA256 is already a good hash and just truncate down to the
1608  // number of bytes we need for DenseMap.
1609  unsigned hash;
1610  std::memcpy(&hash, val.structuralHash.data(), sizeof(unsigned));
1611 
1612  // Combine module names.
1613  return llvm::hash_combine(hash, val.referredModuleNames);
1614  }
1615 
1616  static bool isEqual(const ModuleInfo &lhs, const ModuleInfo &rhs) {
1617  return lhs.structuralHash == rhs.structuralHash &&
1618  lhs.referredModuleNames == rhs.referredModuleNames;
1619  }
1620 };
1621 } // namespace llvm
1622 
1623 //===----------------------------------------------------------------------===//
1624 // DedupPass
1625 //===----------------------------------------------------------------------===//
1626 
1627 namespace {
1628 class DedupPass : public circt::firrtl::impl::DedupBase<DedupPass> {
1629  void runOnOperation() override {
1630  auto *context = &getContext();
1631  auto circuit = getOperation();
1632  auto &instanceGraph = getAnalysis<InstanceGraph>();
1633  auto *nlaTable = &getAnalysis<NLATable>();
1634  auto &symbolTable = getAnalysis<SymbolTable>();
1635  Deduper deduper(instanceGraph, symbolTable, nlaTable, circuit);
1636  Equivalence equiv(context, instanceGraph);
1637  auto anythingChanged = false;
1638 
1639  // Modules annotated with this should not be considered for deduplication.
1640  auto noDedupClass = StringAttr::get(context, noDedupAnnoClass);
1641 
1642  // Only modules within the same group may be deduplicated.
1643  auto dedupGroupClass = StringAttr::get(context, dedupGroupAnnoClass);
1644 
1645  // A map of all the module moduleInfo that we have calculated so far.
1646  llvm::DenseMap<ModuleInfo, Operation *> moduleInfoToModule;
1647 
1648  // We track the name of the module that each module is deduped into, so that
1649  // we can make sure all modules which are marked "must dedup" with each
1650  // other were all deduped to the same module.
1651  DenseMap<Attribute, StringAttr> dedupMap;
1652 
1653  // We must iterate the modules from the bottom up so that we can properly
1654  // deduplicate the modules. We copy the list of modules into a vector first
1655  // to avoid iterator invalidation while we mutate the instance graph.
1656  SmallVector<FModuleLike, 0> modules(
1657  llvm::map_range(llvm::post_order(&instanceGraph), [](auto *node) {
1658  return cast<FModuleLike>(*node->getModule());
1659  }));
1660 
1661  SmallVector<std::optional<
1662  std::pair<std::array<uint8_t, 32>, SmallVector<StringAttr>>>>
1663  hashesAndModuleNames(modules.size());
1664  StructuralHasherSharedConstants hasherConstants(&getContext());
1665 
1666  // Attribute name used to store dedup_group for this pass.
1667  auto dedupGroupAttrName = StringAttr::get(context, "firrtl.dedup_group");
1668 
1669  // Move dedup group annotations to attributes on the module.
1670  // This results in the desired behavior (included in hash),
1671  // and avoids unnecessary processing of these as annotations
1672  // that need to be tracked, made non-local, so on.
1673  for (auto module : modules) {
1674  llvm::SmallSetVector<StringAttr, 1> groups;
1676  module, [&groups, dedupGroupClass](Annotation annotation) {
1677  if (annotation.getClassAttr() != dedupGroupClass)
1678  return false;
1679  groups.insert(annotation.getMember<StringAttr>("group"));
1680  return true;
1681  });
1682  if (groups.size() > 1) {
1683  module.emitError("module belongs to multiple dedup groups: ") << groups;
1684  return signalPassFailure();
1685  }
1686  assert(!module->hasAttr(dedupGroupAttrName) &&
1687  "unexpected existing use of temporary dedup group attribute");
1688  if (!groups.empty())
1689  module->setDiscardableAttr(dedupGroupAttrName, groups.front());
1690  }
1691 
1692  // Calculate module information parallelly.
1693  auto result = mlir::failableParallelForEach(
1694  context, llvm::seq(modules.size()), [&](unsigned idx) {
1695  auto module = modules[idx];
1696  // If the module is marked with NoDedup, just skip it.
1697  if (AnnotationSet::hasAnnotation(module, noDedupClass))
1698  return success();
1699 
1700  // Only dedup extmodule's with defname.
1701  if (auto ext = dyn_cast<FExtModuleOp>(*module);
1702  ext && !ext.getDefname().has_value())
1703  return success();
1704 
1705  if (!checkVisibility(module))
1706  return success();
1707 
1708  StructuralHasher hasher(hasherConstants);
1709  // Calculate the hash of the module and referred module names.
1710  hashesAndModuleNames[idx] = hasher.getHashAndModuleNames(module);
1711  return success();
1712  });
1713 
1714  if (result.failed())
1715  return signalPassFailure();
1716 
1717  for (auto [i, module] : llvm::enumerate(modules)) {
1718  auto moduleName = module.getModuleNameAttr();
1719  auto &hashAndModuleNamesOpt = hashesAndModuleNames[i];
1720  // If the hash was not calculated, we need to skip it.
1721  if (!hashAndModuleNamesOpt) {
1722  // We record it in the dedup map to help detect errors when the user
1723  // marks the module as both NoDedup and MustDedup. We do not record this
1724  // module in the hasher to make sure no other module dedups "into" this
1725  // one.
1726  dedupMap[moduleName] = moduleName;
1727  continue;
1728  }
1729 
1730  // Replace module names referred in the module with new names.
1731  SmallVector<mlir::Attribute> names;
1732  for (auto oldModuleName : hashAndModuleNamesOpt->second) {
1733  auto newModuleName = dedupMap[oldModuleName];
1734  names.push_back(newModuleName);
1735  }
1736 
1737  // Create a module info to use it as a key.
1738  ModuleInfo moduleInfo{hashAndModuleNamesOpt->first,
1739  mlir::ArrayAttr::get(module.getContext(), names)};
1740 
1741  // Check if there a module with the same hash.
1742  auto it = moduleInfoToModule.find(moduleInfo);
1743  if (it != moduleInfoToModule.end()) {
1744  auto original = cast<FModuleLike>(it->second);
1745  // Record the group ID of the other module.
1746  dedupMap[moduleName] = original.getModuleNameAttr();
1747  deduper.dedup(original, module);
1748  ++erasedModules;
1749  anythingChanged = true;
1750  continue;
1751  }
1752  // Any module not deduplicated must be recorded.
1753  deduper.record(module);
1754  // Add the module to a new dedup group.
1755  dedupMap[moduleName] = moduleName;
1756  // Record the module info.
1757  moduleInfoToModule[moduleInfo] = module;
1758  }
1759 
1760  // This part verifies that all modules marked by "MustDedup" have been
1761  // properly deduped with each other. For this check to succeed, all modules
1762  // have to been deduped to the same module. It is possible that a module was
1763  // deduped with the wrong thing.
1764 
1765  auto failed = false;
1766  // This parses the module name out of a target string.
1767  auto parseModule = [&](Attribute path) -> StringAttr {
1768  // Each module is listed as a target "~Circuit|Module" which we have to
1769  // parse.
1770  auto [_, rhs] = cast<StringAttr>(path).getValue().split('|');
1771  return StringAttr::get(context, rhs);
1772  };
1773  // This gets the name of the module which the current module was deduped
1774  // with. If the named module isn't in the map, then we didn't encounter it
1775  // in the circuit.
1776  auto getLead = [&](StringAttr module) -> StringAttr {
1777  auto it = dedupMap.find(module);
1778  if (it == dedupMap.end()) {
1779  auto diag = emitError(circuit.getLoc(),
1780  "MustDeduplicateAnnotation references module ")
1781  << module << " which does not exist";
1782  failed = true;
1783  return nullptr;
1784  }
1785  return it->second;
1786  };
1787 
1788  AnnotationSet::removeAnnotations(circuit, [&](Annotation annotation) {
1789  if (!annotation.isClass(mustDedupAnnoClass))
1790  return false;
1791  auto modules = annotation.getMember<ArrayAttr>("modules");
1792  if (!modules) {
1793  emitError(circuit.getLoc(),
1794  "MustDeduplicateAnnotation missing \"modules\" member");
1795  failed = true;
1796  return false;
1797  }
1798  // Empty module list has nothing to process.
1799  if (modules.empty())
1800  return true;
1801  // Get the first element.
1802  auto firstModule = parseModule(modules[0]);
1803  auto firstLead = getLead(firstModule);
1804  if (!firstLead)
1805  return false;
1806  // Verify that the remaining elements are all the same as the first.
1807  for (auto attr : modules.getValue().drop_front()) {
1808  auto nextModule = parseModule(attr);
1809  auto nextLead = getLead(nextModule);
1810  if (!nextLead)
1811  return false;
1812  if (firstLead != nextLead) {
1813  auto diag = emitError(circuit.getLoc(), "module ")
1814  << nextModule << " not deduplicated with " << firstModule;
1815  auto a = instanceGraph.lookup(firstLead)->getModule();
1816  auto b = instanceGraph.lookup(nextLead)->getModule();
1817  equiv.check(diag, a, b);
1818  failed = true;
1819  return false;
1820  }
1821  }
1822  return true;
1823  });
1824  if (failed)
1825  return signalPassFailure();
1826 
1827  // Remove all dedup group attributes, they only exist during this pass.
1828  for (auto module : circuit.getOps<FModuleLike>())
1829  module->removeDiscardableAttr(dedupGroupAttrName);
1830 
1831  // Walk all the modules and fixup the instance operation to return the
1832  // correct type. We delay this fixup until the end because doing it early
1833  // can block the deduplication of the parent modules.
1834  fixupAllModules(instanceGraph);
1835 
1836  markAnalysesPreserved<NLATable>();
1837  if (!anythingChanged)
1838  markAllAnalysesPreserved();
1839  }
1840 };
1841 } // end anonymous namespace
1842 
1843 std::unique_ptr<mlir::Pass> circt::firrtl::createDedupPass() {
1844  return std::make_unique<DedupPass>();
1845 }
assert(baseType &&"element must be base type")
static Attribute getAttr(ArrayRef< NamedAttribute > attrs, StringRef name)
Get an attribute by name from a list of named attributes.
Definition: FIRRTLOps.cpp:3962
static Location mergeLoc(MLIRContext *context, Location to, Location from)
Definition: Dedup.cpp:865
void fixupObjectOp(ObjectOp objectOp, ClassType newClassType)
This fixes up ObjectOps when the signature of their ClassOp changes.
Definition: Dedup.cpp:1506
llvm::raw_ostream & printHex(llvm::raw_ostream &stream, ArrayRef< uint8_t > bytes)
Definition: Dedup.cpp:67
static bool checkVisibility(mlir::SymbolOpInterface symbol)
Definition: Dedup.cpp:53
void fixupConnect(ImplicitLocOpBuilder &builder, Value dst, Value src)
This fixes up connects when the field names of a bundle type changes.
Definition: Dedup.cpp:1513
llvm::raw_ostream & printHash(llvm::raw_ostream &stream, llvm::SHA256 &data)
Definition: Dedup.cpp:73
void fixupAllModules(InstanceGraph &instanceGraph)
This is the root method to fixup module references when a module changes.
Definition: Dedup.cpp:1539
bool fixupClassOp(ClassOp classOp)
This fixes up ClassLikes with ClassType ports, when the classes have deduped.
Definition: Dedup.cpp:1448
static void mergeRegions(Region *region1, Region *region2)
Definition: HWCleanup.cpp:77
static Block * getBodyBlock(FModuleLike mod)
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.
bool hasAnnotation(StringRef className) const
Return true if we have an annotation with the specified class name.
static AnnotationSet forPort(FModuleLike op, size_t portNo)
Get an annotation set for the specified port.
This class provides a read-only projection of an annotation.
void setDict(DictionaryAttr dict)
Set the data dictionary of this attribute.
AttrClass getMember(StringAttr name) const
Return a member of the annotation.
StringAttr getClassAttr() const
Return the 'class' that this annotation is representing.
bool isClass(Args... names) const
Return true if this annotation matches any of the specified class names.
This graph tracks modules and where they are instantiated.
This table tracks nlas and what modules participate in them.
Definition: NLATable.h:29
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:55
ClassType getInstanceTypeForClassLike(ClassLike classOp)
Definition: FIRRTLOps.cpp:1813
static StringRef toString(Direction direction)
FieldRef getFieldRefFromValue(Value value, bool lookThroughCasts=false)
Get the FieldRef from a value.
constexpr const char * mustDedupAnnoClass
std::pair< hw::InnerSymAttr, StringAttr > getOrAddInnerSym(MLIRContext *context, hw::InnerSymAttr attr, uint64_t fieldID, llvm::function_ref< hw::InnerSymbolNamespace &()> getNamespace)
Ensure that the the InnerSymAttr has a symbol on the field specified.
constexpr const char * noDedupAnnoClass
size_t getNumPorts(Operation *op)
Return the number of ports in a module-like thing (modules, memories, etc)
Definition: FIRRTLOps.cpp:300
constexpr const char * dedupGroupAnnoClass
std::unique_ptr< mlir::Pass > createDedupPass()
Definition: Dedup.cpp:1843
std::pair< std::string, bool > getFieldName(const FieldRef &fieldRef, bool nameSafe=false)
Get a string identifier representing the FieldRef.
constexpr const char * dontTouchAnnoClass
void emitConnect(OpBuilder &builder, Location loc, Value lhs, Value rhs)
Emit a connect between two values.
Definition: FIRRTLUtils.cpp:25
StringAttr getInnerSymName(Operation *op)
Return the StringAttr for the inner_sym name, if it exists.
Definition: FIRRTLOps.h:108
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
size_t hash_combine(size_t h1, size_t h2)
C++'s stdlib doesn't have a hash_combine function. This is a simple one.
Definition: Utils.h:32
MLIRContext * context
Definition: Dedup.cpp:1415
Block * nlaBlock
We insert all NLAs to the beginning of this block.
Definition: Dedup.cpp:1423
void recordAnnotations(Operation *op)
Record all targets which use an NLA.
Definition: Dedup.cpp:995
void eraseNLA(hw::HierPathOp nla)
This erases the NLA op, and removes the NLA from every module's NLA map, but it does not delete the N...
Definition: Dedup.cpp:1104
void mergeAnnotations(FModuleLike toModule, Operation *to, FModuleLike fromModule, Operation *from)
Merge all annotations and port annotations on two operations.
Definition: Dedup.cpp:1285
void replaceInstances(FModuleLike toModule, Operation *fromModule)
This deletes and replaces all instances of the "fromModule" with instances of the "toModule".
Definition: Dedup.cpp:1011
SmallVector< FlatSymbolRefAttr > createNLAs(StringAttr toModuleName, FModuleLike fromModule, SymbolTable::Visibility vis=SymbolTable::Visibility::Private)
Look up the instantiations of this module and create an NLA for each one.
Definition: Dedup.cpp:1077
void record(FModuleLike module)
Record the usages of any NLA's in this module, so that we may update the annotation if the parent mod...
Definition: Dedup.cpp:969
void rewriteExtModuleNLAs(RenameMap &renameMap, StringAttr toName, StringAttr fromName)
Definition: Dedup.cpp:1183
void mergeRegions(RenameMap &renameMap, FModuleLike toModule, Region &toRegion, FModuleLike fromModule, Region &fromRegion)
Definition: Dedup.cpp:1407
void dedup(FModuleLike toModule, FModuleLike fromModule)
Remove the "fromModule", and replace all references to it with the "toModule".
Definition: Dedup.cpp:934
void rewriteModuleNLAs(RenameMap &renameMap, FModuleOp toModule, FModuleOp fromModule)
Process all the NLAs that the two modules participate in, replacing references to the "from" module w...
Definition: Dedup.cpp:1175
void recordAnnotations(AnnoTarget target)
For a specific annotation target, record all the unique NLAs which target it in the targetMap.
Definition: Dedup.cpp:988
void cloneAnnotation(SmallVectorImpl< FlatSymbolRefAttr > &nlas, Annotation anno, ArrayRef< NamedAttribute > attributes, unsigned nonLocalIndex, SmallVectorImpl< Annotation > &newAnnotations)
Clone the annotation for each NLA in a list.
Definition: Dedup.cpp:1085
void recordSymRenames(RenameMap &renameMap, FModuleLike toModule, Operation *to, FModuleLike fromModule, Operation *from)
Definition: Dedup.cpp:1313
void mergeAnnotations(FModuleLike toModule, AnnoTarget to, AnnotationSet toAnnos, FModuleLike fromModule, AnnoTarget from, AnnotationSet fromAnnos)
Merge the annotations of a specific target, either a operation or a port on an operation.
Definition: Dedup.cpp:1262
StringAttr nonLocalString
Definition: Dedup.cpp:1433
SymbolTable & symbolTable
Definition: Dedup.cpp:1417
SmallVector< FlatSymbolRefAttr > createNLAs(Operation *fromModule, ArrayRef< Attribute > baseNamepath, SymbolTable::Visibility vis=SymbolTable::Visibility::Private)
Look up the instantiations of the from module and create an NLA for each one, appending the baseNamep...
Definition: Dedup.cpp:1040
void mergeOps(RenameMap &renameMap, FModuleLike toModule, Operation *to, FModuleLike fromModule, Operation *from)
Recursively merge two operations.
Definition: Dedup.cpp:1374
hw::InnerSymbolNamespace & getNamespace(Operation *module)
Get a cached namespace for a module.
Definition: Dedup.cpp:981
DenseMap< Operation *, hw::InnerSymbolNamespace > moduleNamespaces
A module namespace cache.
Definition: Dedup.cpp:1437
bool makeAnnotationNonLocal(StringAttr toModuleName, AnnoTarget to, FModuleLike fromModule, Annotation anno, SmallVectorImpl< Annotation > &newAnnotations)
Take an annotation, and update it to be a non-local annotation.
Definition: Dedup.cpp:1191
InstanceGraph & instanceGraph
Definition: Dedup.cpp:1416
void mergeBlocks(RenameMap &renameMap, FModuleLike toModule, Block &toBlock, FModuleLike fromModule, Block &fromBlock)
Recursively merge two blocks.
Definition: Dedup.cpp:1393
DenseMap< Attribute, llvm::SmallDenseSet< AnnoTarget > > targetMap
Definition: Dedup.cpp:1426
StringAttr classString
Definition: Dedup.cpp:1434
void copyAnnotations(FModuleLike toModule, AnnoTarget to, FModuleLike fromModule, AnnotationSet annos, SmallVectorImpl< Annotation > &newAnnotations, SmallPtrSetImpl< Attribute > &dontTouches)
Definition: Dedup.cpp:1233
Deduper(InstanceGraph &instanceGraph, SymbolTable &symbolTable, NLATable *nlaTable, CircuitOp circuit)
Definition: Dedup.cpp:918
void addAnnotationContext(RenameMap &renameMap, FModuleOp toModule, FModuleOp fromModule)
Process all NLAs referencing the "from" module to point to the "to" module.
Definition: Dedup.cpp:1114
DenseMap< StringAttr, StringAttr > RenameMap
Definition: Dedup.cpp:916
DenseMap< Attribute, Attribute > nlaCache
Definition: Dedup.cpp:1430
const hw::InnerSymbolTable & a
Definition: Dedup.cpp:399
ModuleData(const hw::InnerSymbolTable &a, const hw::InnerSymbolTable &b)
Definition: Dedup.cpp:396
const hw::InnerSymbolTable & b
Definition: Dedup.cpp:400
This class is for reporting differences between two modules which should have been deduplicated.
Definition: Dedup.cpp:378
DenseSet< Attribute > nonessentialAttributes
Definition: Dedup.cpp:852
std::string prettyPrint(Attribute attr)
Definition: Dedup.cpp:403
LogicalResult check(InFlightDiagnostic &diag, FInstanceLike a, FInstanceLike b)
Definition: Dedup.cpp:685
LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a, Block &aBlock, Operation *b, Block &bBlock)
Definition: Dedup.cpp:474
LogicalResult check(InFlightDiagnostic &diag, const Twine &message, Operation *a, Type aType, Operation *b, Type bType)
Definition: Dedup.cpp:448
StringAttr noDedupClass
Definition: Dedup.cpp:847
StringAttr dedupGroupAttrName
Definition: Dedup.cpp:849
LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a, DictionaryAttr aDict, Operation *b, DictionaryAttr bDict)
Definition: Dedup.cpp:597
LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a, Region &aRegion, Operation *b, Region &bRegion)
Definition: Dedup.cpp:552
StringAttr portDirectionsAttr
Definition: Dedup.cpp:845
LogicalResult check(InFlightDiagnostic &diag, const Twine &message, Operation *a, BundleType aType, Operation *b, BundleType bType)
Definition: Dedup.cpp:419
LogicalResult check(InFlightDiagnostic &diag, ModuleData &data, Operation *a, Operation *b)
Definition: Dedup.cpp:706
Equivalence(MLIRContext *context, InstanceGraph &instanceGraph)
Definition: Dedup.cpp:379
LogicalResult check(InFlightDiagnostic &diag, Operation *a, mlir::DenseBoolArrayAttr aAttr, Operation *b, mlir::DenseBoolArrayAttr bAttr)
Definition: Dedup.cpp:572
InstanceGraph & instanceGraph
Definition: Dedup.cpp:853
void check(InFlightDiagnostic &diag, Operation *a, Operation *b)
Definition: Dedup.cpp:793
std::array< uint8_t, 32 > structuralHash
Definition: Dedup.cpp:90
mlir::ArrayAttr referredModuleNames
Definition: Dedup.cpp:92
This struct contains constant string attributes shared across different threads.
Definition: Dedup.cpp:111
DenseSet< Attribute > nonessentialAttributes
Definition: Dedup.cpp:142
StructuralHasherSharedConstants(MLIRContext *context)
Definition: Dedup.cpp:112
void update(Operation *op, DictionaryAttr dict)
Hash the top level attribute dictionary of the operation.
Definition: Dedup.cpp:246
ValueId getId(Value val)
Get the unique id for the specified value.
Definition: Dedup.cpp:192
void update(Type type)
Definition: Dedup.cpp:179
void update(const void *pointer)
Definition: Dedup.cpp:157
void update(InnerRefAttr attr)
Definition: Dedup.cpp:235
void update(Operation *op)
Definition: Dedup.cpp:318
void record(void *address)
Definition: Dedup.cpp:185
void update(const SymbolTarget &target)
Definition: Dedup.cpp:230
std::pair< std::array< uint8_t, 32 >, SmallVector< StringAttr > > getHashAndModuleNames(FModuleLike module)
Definition: Dedup.cpp:150
llvm::SHA256 sha
Definition: Dedup.cpp:369
void update(Operation *op, hw::InnerSymAttr attr)
Definition: Dedup.cpp:218
DenseMap< StringAttr, SymbolTarget > innerSymTargets
Definition: Dedup.cpp:359
void update(size_t value)
Definition: Dedup.cpp:162
SmallVector< mlir::StringAttr > referredModuleNames
Definition: Dedup.cpp:362
void update(BundleType type)
Definition: Dedup.cpp:170
void update(OpResult result)
Definition: Dedup.cpp:199
void update(OpOperand &operand)
Definition: Dedup.cpp:216
StructuralHasher(const StructuralHasherSharedConstants &constants)
Definition: Dedup.cpp:146
void update(ValueId index)
Definition: Dedup.cpp:211
void update(TypeID typeID)
Definition: Dedup.cpp:167
const StructuralHasherSharedConstants & constants
Definition: Dedup.cpp:365
void update(Value value, hw::InnerSymAttr attr)
Definition: Dedup.cpp:224
DenseMap< void *, unsigned > indices
Definition: Dedup.cpp:356
void update(mlir::OperationName name)
Definition: Dedup.cpp:312
ValueId index
Definition: Dedup.cpp:105
uint64_t fieldID
Definition: Dedup.cpp:106
Unique identifier for a value.
Definition: Dedup.cpp:99
uint64_t index
Definition: Dedup.cpp:100
uint64_t offset
Definition: Dedup.cpp:101
An annotation target is used to keep track of something that is targeted by an Annotation.
AnnotationSet getAnnotations() const
Get the annotations associated with the target.
void setAnnotations(AnnotationSet annotations) const
Set the annotations associated with the target.
This represents an annotation targeting a specific operation.
Attribute getNLAReference(hw::InnerSymbolNamespace &moduleNamespace) const
This represents an annotation targeting a specific port of a module, memory, or instance.
static ModuleInfo getEmptyKey()
Definition: Dedup.cpp:1594
static ModuleInfo getTombstoneKey()
Definition: Dedup.cpp:1600
static unsigned getHashValue(const ModuleInfo &val)
Definition: Dedup.cpp:1606
static bool isEqual(const ModuleInfo &lhs, const ModuleInfo &rhs)
Definition: Dedup.cpp:1616