CIRCT  20.0.0git
ModuleInliner.cpp
Go to the documentation of this file.
1 //===- ModuleInliner.cpp - FIRRTL module inlining ---------------*- 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 instance inlining.
10 //
11 //===----------------------------------------------------------------------===//
12 
22 #include "circt/Dialect/HW/HWOps.h"
24 #include "circt/Support/Debug.h"
25 #include "circt/Support/LLVM.h"
26 #include "mlir/IR/IRMapping.h"
27 #include "mlir/Pass/Pass.h"
28 #include "llvm/ADT/BitVector.h"
29 #include "llvm/ADT/SetOperations.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/FormatVariadic.h"
32 
33 #define DEBUG_TYPE "firrtl-inliner"
34 
35 namespace circt {
36 namespace firrtl {
37 #define GEN_PASS_DEF_INLINER
38 #include "circt/Dialect/FIRRTL/Passes.h.inc"
39 } // namespace firrtl
40 } // namespace circt
41 
42 using namespace circt;
43 using namespace firrtl;
44 using namespace chirrtl;
45 
46 using hw::InnerRefAttr;
47 using llvm::BitVector;
48 
49 using InnerRefToNewNameMap = DenseMap<hw::InnerRefAttr, StringAttr>;
50 
51 //===----------------------------------------------------------------------===//
52 // Module Inlining Support
53 //===----------------------------------------------------------------------===//
54 
55 namespace {
56 /// A representation of an NLA that can be mutated. This is intended to be used
57 /// in situations where you want to make a series of modifications to an NLA
58 /// while also being able to query information about it. Finally, the NLA is
59 /// written back to the IR to replace the original NLA.
60 class MutableNLA {
61  // Storage of the NLA this represents.
62  hw::HierPathOp nla;
63 
64  // A namespace that can be used to generate new symbol names if needed.
65  CircuitNamespace *circuitNamespace;
66 
67  /// A mapping of symbol to index in the NLA.
68  DenseMap<Attribute, unsigned> symIdx;
69 
70  /// Records which elements of the path are inlined.
71  BitVector inlinedSymbols;
72 
73  /// The point after which the NLA is flattened. A value of "-1" indicates
74  /// that this was never set.
75  signed flattenPoint = -1;
76 
77  /// Indicates if the _original_ NLA is dead and should be deleted. Updates
78  /// may still need to be written if the newTops vector below is non-empty.
79  bool dead = false;
80 
81  /// Indicates if the NLA is only used to target a module
82  /// (i.e., no ports or operations use this HierPathOp).
83  /// This is needed to help determine when the HierPathOp is dead:
84  /// if we inline/flatten a module, NLA's targeting (only) that module
85  /// are now dead.
86  bool moduleOnly = false;
87 
88  /// Stores new roots for the NLA. If this is non-empty, then it indicates
89  /// that the NLA should be copied and re-topped using the roots stored here.
90  /// This is non-empty when the NLA's root is inlined and the original NLA
91  /// migrates to each instantiator of the original NLA.
92  SmallVector<InnerRefAttr> newTops;
93 
94  /// Cache of roots that this module participates in. This is only valid when
95  /// newTops is non-empty.
96  DenseSet<StringAttr> rootSet;
97 
98  /// Stores the size of the NLA path.
99  unsigned int size;
100 
101  /// A mapping of module name to _new_ inner symbol name. For convenience of
102  /// how this pass works (operations are inlined *into* a new module), the key
103  /// is the NEW module, after inlining/flattening as opposed to on the old
104  /// module.
105  DenseMap<Attribute, StringAttr> renames;
106 
107  /// Lookup a reference and apply any renames to it. This requires both the
108  /// module where the NEW reference lives (to lookup the rename) and the
109  /// original ID of the reference (to fallback to if the reference was not
110  /// renamed).
111  StringAttr lookupRename(Attribute lastMod, unsigned idx = 0) {
112  if (renames.count(lastMod))
113  return renames[lastMod];
114  return nla.refPart(idx);
115  }
116 
117 public:
118  MutableNLA(hw::HierPathOp nla, CircuitNamespace *circuitNamespace)
119  : nla(nla), circuitNamespace(circuitNamespace),
120  inlinedSymbols(BitVector(nla.getNamepath().size(), true)),
121  size(nla.getNamepath().size()) {
122  for (size_t i = 0, e = size; i != e; ++i)
123  symIdx.insert({nla.modPart(i), i});
124  }
125 
126  /// This default, erroring constructor exists because the pass uses
127  /// `DenseMap<Attribute, MutableNLA>`. `DenseMap` requires a default
128  /// constructor for the value type because its `[]` operator (which returns a
129  /// reference) must default construct the value type for a non-existent key.
130  /// This default constructor is never supposed to be used because the pass
131  /// prepopulates a `DenseMap<Attribute, MutableNLA>` before it runs and
132  /// thereby guarantees that `[]` will always hit and never need to use the
133  /// default constructor.
134  MutableNLA() {
135  llvm_unreachable(
136  "the default constructor for MutableNLA should never be used");
137  }
138 
139  /// Set the state of the mutable NLA to indicate that the _original_ NLA
140  /// should be removed when updates are applied.
141  void markDead() { dead = true; }
142 
143  /// Set the state of the mutable NLA to indicate the only target is a module.
144  void markModuleOnly() { moduleOnly = true; }
145 
146  /// Return the original NLA that this was pointing at.
147  hw::HierPathOp getNLA() { return nla; }
148 
149  /// Writeback updates accumulated in this MutableNLA to the IR. This method
150  /// should only ever be called once and, if a writeback occurrs, the
151  /// MutableNLA is NOT updated for further use. Interacting with the
152  /// MutableNLA in any way after calling this method may result in crashes.
153  /// (This is done to save unnecessary state cleanup of a pass-private
154  /// utility.)
155  hw::HierPathOp applyUpdates() {
156  // Delete an NLA which is either dead or has been made local.
157  if (isLocal() || isDead()) {
158  nla.erase();
159  return nullptr;
160  }
161 
162  // The NLA was never updated, just return the NLA and do not writeback
163  // anything.
164  if (inlinedSymbols.all() && newTops.empty() && flattenPoint == -1 &&
165  renames.empty())
166  return nla;
167 
168  // The NLA has updates. Generate a new NLA with the same symbol and delete
169  // the original NLA.
170  OpBuilder b(nla);
171  auto writeBack = [&](StringAttr root, StringAttr sym) -> hw::HierPathOp {
172  SmallVector<Attribute> namepath;
173  StringAttr lastMod;
174 
175  // Root of the namepath.
176  if (!inlinedSymbols.test(1))
177  lastMod = root;
178  else
179  namepath.push_back(InnerRefAttr::get(root, lookupRename(root)));
180 
181  // Everything in the middle of the namepath (excluding the root and leaf).
182  for (signed i = 1, e = inlinedSymbols.size() - 1; i != e; ++i) {
183  if (i == flattenPoint) {
184  lastMod = nla.modPart(i);
185  break;
186  }
187 
188  if (!inlinedSymbols.test(i + 1)) {
189  if (!lastMod)
190  lastMod = nla.modPart(i);
191  continue;
192  }
193 
194  // Update the inner symbol if it has been renamed.
195  auto modPart = lastMod ? lastMod : nla.modPart(i);
196  auto refPart = lookupRename(modPart, i);
197  namepath.push_back(InnerRefAttr::get(modPart, refPart));
198  lastMod = {};
199  }
200 
201  // Leaf of the namepath.
202  auto modPart = lastMod ? lastMod : nla.modPart(size - 1);
203  auto refPart = lookupRename(modPart, size - 1);
204 
205  if (refPart)
206  namepath.push_back(InnerRefAttr::get(modPart, refPart));
207  else
208  namepath.push_back(FlatSymbolRefAttr::get(modPart));
209 
210  auto hp = b.create<hw::HierPathOp>(b.getUnknownLoc(), sym,
211  b.getArrayAttr(namepath));
212  hp.setVisibility(nla.getVisibility());
213  return hp;
214  };
215 
216  hw::HierPathOp last;
217  assert(!dead || !newTops.empty());
218  if (!dead)
219  last = writeBack(nla.root(), nla.getNameAttr());
220  for (auto root : newTops)
221  last = writeBack(root.getModule(), root.getName());
222 
223  nla.erase();
224  return last;
225  }
226 
227  void dump() {
228  llvm::errs() << " - orig: " << nla << "\n"
229  << " new: " << *this << "\n"
230  << " dead: " << dead << "\n"
231  << " isDead: " << isDead() << "\n"
232  << " isModuleOnly: " << isModuleOnly() << "\n"
233  << " isLocal: " << isLocal() << "\n"
234  << " inlinedSymbols: [";
235  llvm::interleaveComma(inlinedSymbols.getData(), llvm::errs(), [](auto a) {
236  llvm::errs() << llvm::formatv("{0:x-}", a);
237  });
238  llvm::errs() << "]\n"
239  << " flattenPoint: " << flattenPoint << "\n"
240  << " renames:\n";
241  for (auto rename : renames)
242  llvm::errs() << " - " << rename.first << " -> " << rename.second
243  << "\n";
244  }
245 
246  /// Write the current state of this MutableNLA to a string using a format that
247  /// looks like the NLA serialization. This is intended to be used for
248  /// debugging purposes.
249  friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, MutableNLA &x) {
250  auto writePathSegment = [&](StringAttr mod, StringAttr sym = {}) {
251  if (sym)
252  os << "#hw.innerNameRef<";
253  os << "@" << mod.getValue();
254  if (sym)
255  os << "::@" << sym.getValue() << ">";
256  };
257 
258  auto writeOne = [&](StringAttr root, StringAttr sym) {
259  os << "firrtl.nla @" << sym.getValue() << " [";
260 
261  StringAttr lastMod;
262  // Root of the namepath.
263  if (!x.inlinedSymbols.test(1))
264  lastMod = root;
265  else
266  writePathSegment(root, x.lookupRename(root));
267 
268  // Everything in the middle of the namepath (excluding the root and leaf).
269  bool needsComma = false;
270  for (signed i = 1, e = x.inlinedSymbols.size() - 1; i != e; ++i) {
271  if (i == x.flattenPoint) {
272  lastMod = x.nla.modPart(i);
273  break;
274  }
275 
276  if (!x.inlinedSymbols.test(i + 1)) {
277  if (!lastMod)
278  lastMod = x.nla.modPart(i);
279  continue;
280  }
281 
282  if (needsComma)
283  os << ", ";
284  auto modPart = lastMod ? lastMod : x.nla.modPart(i);
285  auto refPart = x.nla.refPart(i);
286  if (x.renames.count(modPart))
287  refPart = x.renames[modPart];
288  writePathSegment(modPart, refPart);
289  needsComma = true;
290  lastMod = {};
291  }
292 
293  // Leaf of the namepath.
294  os << ", ";
295  auto modPart = lastMod ? lastMod : x.nla.modPart(x.size - 1);
296  auto refPart = x.nla.refPart(x.size - 1);
297  if (x.renames.count(modPart))
298  refPart = x.renames[modPart];
299  writePathSegment(modPart, refPart);
300  os << "]";
301  };
302 
303  SmallVector<InnerRefAttr> tops;
304  if (!x.dead)
305  tops.push_back(InnerRefAttr::get(x.nla.root(), x.nla.getNameAttr()));
306  tops.append(x.newTops.begin(), x.newTops.end());
307 
308  bool multiary = !x.newTops.empty();
309  if (multiary)
310  os << "[";
311  llvm::interleaveComma(tops, os, [&](InnerRefAttr a) {
312  writeOne(a.getModule(), a.getName());
313  });
314  if (multiary)
315  os << "]";
316 
317  return os;
318  }
319 
320  /// Returns true if this NLA is dead. There are several reasons why this
321  /// could be dead:
322  /// 1. This NLA has no uses and was not re-topped.
323  /// 2. This NLA was flattened and its leaf reference is a Module.
324  bool isDead() { return dead && newTops.empty(); }
325 
326  /// Returns true if this NLA targets only a module.
327  bool isModuleOnly() { return moduleOnly; }
328 
329  /// Returns true if this NLA is local. For this to be local, every module
330  /// after the root (up to the flatten point or the end) must be inlined. The
331  /// root is never truly inlined as inlining the root just sets a new root.
332  bool isLocal() {
333  unsigned end = flattenPoint > -1 ? flattenPoint + 1 : inlinedSymbols.size();
334  return inlinedSymbols.find_first_in(1, end) == -1;
335  }
336 
337  /// Return true if this NLA has a root that originates from a specific module.
338  bool hasRoot(FModuleLike mod) {
339  return (isDead() && nla.root() == mod.getModuleNameAttr()) ||
340  rootSet.contains(mod.getModuleNameAttr());
341  }
342 
343  /// Return true if either this NLA is rooted at modName, or is retoped to it.
344  bool hasRoot(StringAttr modName) {
345  return (nla.root() == modName) || rootSet.contains(modName);
346  }
347 
348  /// Mark a module as inlined. This will remove it from the NLA.
349  void inlineModule(FModuleOp module) {
350  auto sym = module.getNameAttr();
351  assert(sym != nla.root() && "unable to inline the root module");
352  assert(symIdx.count(sym) && "module is not in the symIdx map");
353  auto idx = symIdx[sym];
354  inlinedSymbols.reset(idx);
355  // If we inlined the last module in the path and the NLA targets only that
356  // module, then this NLA is dead.
357  if (idx == size - 1 && moduleOnly)
358  markDead();
359  }
360 
361  /// Mark a module as flattened. This has the effect of inlining all of its
362  /// children. Also mark the NLA as dead if the leaf reference of this NLA is
363  /// a module and the only target is a module.
364  void flattenModule(FModuleOp module) {
365  auto sym = module.getNameAttr();
366  assert(symIdx.count(sym) && "module is not in the symIdx map");
367  auto idx = symIdx[sym] - 1;
368  flattenPoint = idx;
369  // If the NLA only targets a module and we're flattening the NLA,
370  // then the NLA must be dead. Mark it as such.
371  if (moduleOnly)
372  markDead();
373  }
374 
375  StringAttr reTop(FModuleOp module) {
376  StringAttr sym = nla.getSymNameAttr();
377  if (!newTops.empty())
378  sym = StringAttr::get(nla.getContext(),
379  circuitNamespace->newName(sym.getValue()));
380  newTops.push_back(InnerRefAttr::get(module.getNameAttr(), sym));
381  rootSet.insert(module.getNameAttr());
382  symIdx.insert({module.getNameAttr(), 0});
383  markDead();
384  return sym;
385  }
386 
387  ArrayRef<InnerRefAttr> getAdditionalSymbols() { return ArrayRef(newTops); }
388 
389  void setInnerSym(Attribute module, StringAttr innerSym) {
390  assert(symIdx.count(module) && "Mutable NLA did not contain symbol");
391  assert(!renames.count(module) && "Module already renamed");
392  renames.insert({module, innerSym});
393  }
394 };
395 } // namespace
396 
397 /// This function is used after inlining a module, to handle the conversion
398 /// between module ports and instance results. This maps each wire to the
399 /// result of the instance operation. When future operations are cloned from
400 /// the current block, they will use the value of the wire instead of the
401 /// instance results.
402 static void mapResultsToWires(IRMapping &mapper, SmallVectorImpl<Value> &wires,
403  InstanceOp instance) {
404  for (unsigned i = 0, e = instance.getNumResults(); i < e; ++i) {
405  auto result = instance.getResult(i);
406  auto wire = wires[i];
407  mapper.map(result, wire);
408  }
409 }
410 
411 /// Process each operation, updating InnerRefAttr's using the specified map
412 /// and the given name as the containing IST of the mapped-to sym names.
413 static void replaceInnerRefUsers(ArrayRef<Operation *> newOps,
414  const InnerRefToNewNameMap &map,
415  StringAttr istName) {
416  mlir::AttrTypeReplacer replacer;
417  replacer.addReplacement([&](hw::InnerRefAttr innerRef) {
418  auto it = map.find(innerRef);
419  // TODO: what to do with users that aren't local (or not mapped?).
420  assert(it != map.end());
421 
422  return std::pair{hw::InnerRefAttr::get(istName, it->second),
423  WalkResult::skip()};
424  });
425  llvm::for_each(newOps,
426  [&](auto *op) { replacer.recursivelyReplaceElementsIn(op); });
427 }
428 
429 /// Generate and creating map entries for new inner symbol based on old one
430 /// and an appropriate namespace for creating unique names for each.
431 static hw::InnerSymAttr uniqueInNamespace(hw::InnerSymAttr old,
433  hw::InnerSymbolNamespace &ns,
434  StringAttr istName) {
435  if (!old || old.empty())
436  return old;
437 
438  bool anyChanged = false;
439 
440  SmallVector<hw::InnerSymPropertiesAttr> newProps;
441  auto *context = old.getContext();
442  for (auto &prop : old) {
443  auto newSym = ns.newName(prop.getName().strref());
444  if (newSym == prop.getName()) {
445  newProps.push_back(prop);
446  continue;
447  }
448  auto newSymStrAttr = StringAttr::get(context, newSym);
449  auto newProp = hw::InnerSymPropertiesAttr::get(
450  context, newSymStrAttr, prop.getFieldID(), prop.getSymVisibility());
451  anyChanged = true;
452  newProps.push_back(newProp);
453  }
454 
455  auto newSymAttr = anyChanged ? hw::InnerSymAttr::get(context, newProps) : old;
456 
457  for (auto [oldProp, newProp] : llvm::zip(old, newSymAttr)) {
458  assert(oldProp.getFieldID() == newProp.getFieldID());
459  // Map InnerRef to this inner sym -> new inner sym.
460  map[hw::InnerRefAttr::get(istName, oldProp.getName())] = newProp.getName();
461  }
462 
463  return newSymAttr;
464 }
465 
466 //===----------------------------------------------------------------------===//
467 // Inliner
468 //===----------------------------------------------------------------------===//
469 
470 /// Inlines, flattens, and removes dead modules in a circuit.
471 ///
472 /// The inliner works in a top down fashion, starting from the top level module,
473 /// and inlines every possible instance. With this method of recursive top-down
474 /// inlining, each operation will be cloned directly to its final location.
475 ///
476 /// The inliner uses a worklist to track which modules need to be processed.
477 /// When an instance op is not inlined, the referenced module is added to the
478 /// worklist. When the inliner is complete, it deletes every un-processed
479 /// module: either all instances of the module were inlined, or it was not
480 /// reachable from the top level module.
481 ///
482 /// During the inlining process, every cloned operation with a name must be
483 /// prefixed with the instance's name. The top-down process means that we know
484 /// the entire desired prefix when we clone an operation, and can set the name
485 /// attribute once. This means that we will not create any intermediate name
486 /// attributes (which will be interned by the compiler), and helps keep down the
487 /// total memory usage.
488 namespace {
489 class Inliner {
490 public:
491  /// Initialize the inliner to run on this circuit.
492  Inliner(CircuitOp circuit, SymbolTable &symbolTable);
493 
494  /// Run the inliner.
495  LogicalResult run();
496 
497 private:
498  /// Inlining context, one per module being inlined into.
499  /// Cleans up backedges on destruction.
500  struct ModuleInliningContext {
501  ModuleInliningContext(FModuleOp module)
502  : module(module), modNamespace(module), b(module.getContext()) {}
503  /// Top-level module for current inlining task.
504  FModuleOp module;
505  /// Namespace for generating new names in `module`.
506  hw::InnerSymbolNamespace modNamespace;
507  /// Builder, insertion point into module.
508  OpBuilder b;
509  };
510 
511  /// One inlining level, created for each instance inlined or flattened.
512  /// All inner symbols renamed are recorded in relocatedInnerSyms,
513  /// and new operations in newOps. On destruction newOps are fixed up.
514  struct InliningLevel {
515  InliningLevel(ModuleInliningContext &mic, FModuleOp childModule)
516  : mic(mic), childModule(childModule) {}
517 
518  /// Top-level inlining context.
519  ModuleInliningContext &mic;
520  /// Map of inner-refs to the new inner sym.
521  InnerRefToNewNameMap relocatedInnerSyms;
522  /// All operations cloned are tracked here.
523  SmallVector<Operation *> newOps;
524  /// Wires and other values introduced for ports.
525  SmallVector<Value> wires;
526  /// The module being inlined (this "level").
527  FModuleOp childModule;
528  /// The explicit debug scope of the inlined instance.
529  Value debugScope;
530 
531  ~InliningLevel() {
532  replaceInnerRefUsers(newOps, relocatedInnerSyms,
533  mic.module.getNameAttr());
534  }
535  };
536 
537  /// Returns true if the NLA matches the current path. This will only return
538  /// false if there is a mismatch indicating that the NLA definitely is
539  /// referring to some other path.
540  bool doesNLAMatchCurrentPath(hw::HierPathOp nla);
541 
542  /// Rename an operation and unique any symbols it has.
543  /// Returns true iff symbol was changed.
544  bool rename(StringRef prefix, Operation *op, InliningLevel &il);
545 
546  /// Rename an InstanceOp and unique any symbols it has.
547  /// Requires old and new operations to appropriately update the `HierPathOp`'s
548  /// that it participates in.
549  bool renameInstance(StringRef prefix, InliningLevel &il, InstanceOp oldInst,
550  InstanceOp newInst,
551  const DenseMap<Attribute, Attribute> &symbolRenames);
552 
553  /// Clone and rename an operation. Insert the operation into the inlining
554  /// level.
555  void cloneAndRename(StringRef prefix, InliningLevel &il, IRMapping &mapper,
556  Operation &op,
557  const DenseMap<Attribute, Attribute> &symbolRenames,
558  const DenseSet<Attribute> &localSymbols);
559 
560  /// Rewrite the ports of a module as wires. This is similar to
561  /// cloneAndRename, but operating on ports.
562  /// Wires are added to il.wires.
563  void mapPortsToWires(StringRef prefix, InliningLevel &il, IRMapping &mapper,
564  const DenseSet<Attribute> &localSymbols);
565 
566  /// Returns true if the operation is annotated to be flattened.
567  bool shouldFlatten(Operation *op);
568 
569  /// Returns true if the operation is annotated to be inlined.
570  bool shouldInline(Operation *op);
571 
572  /// Check not inlining into anything other than layerblock or module.
573  /// In the future, could check this per-inlined-operation.
574  LogicalResult checkInstanceParents(InstanceOp instance);
575 
576  /// Walk the specified block, invoking `process` for operations visited
577  /// forward+pre-order. Handles cloning supported operations with regions,
578  /// so that `process` is only invoked on regionless operations.
579  LogicalResult
580  inliningWalk(OpBuilder &builder, Block *block, IRMapping &mapper,
581  llvm::function_ref<LogicalResult(Operation *op)> process);
582 
583  /// Flattens a target module into the insertion point of the builder,
584  /// renaming all operations using the prefix. This clones all operations from
585  /// the target, and does not trigger inlining on the target itself.
586  LogicalResult flattenInto(StringRef prefix, InliningLevel &il,
587  IRMapping &mapper,
588  DenseSet<Attribute> localSymbols);
589 
590  /// Inlines a target module into the insertion point of the builder,
591  /// prefixing all operations with prefix. This clones all operations from
592  /// the target, and does not trigger inlining on the target itself.
593  LogicalResult inlineInto(StringRef prefix, InliningLevel &il,
594  IRMapping &mapper,
595  DenseMap<Attribute, Attribute> &symbolRenames);
596 
597  /// Recursively flatten all instances in a module.
598  LogicalResult flattenInstances(FModuleOp module);
599 
600  /// Inline any instances in the module which were marked for inlining.
601  LogicalResult inlineInstances(FModuleOp module);
602 
603  /// Create a debug scope for an inlined instance at the current insertion
604  /// point of the `il.mic` builder.
605  void createDebugScope(InliningLevel &il, InstanceOp instance,
606  Value parentScope = {});
607 
608  /// Identify all module-only NLA's, marking their MutableNLA's accordingly.
609  void identifyNLAsTargetingOnlyModules();
610 
611  /// Populate the activeHierpaths with the HierPaths that are active given the
612  /// current hierarchy. This is the set of HierPaths that were active in the
613  /// parent, and on the current instance. Also HierPaths that are rooted at
614  /// this module are also added to the active set.
615  void setActiveHierPaths(StringAttr moduleName, StringAttr instInnerSym) {
616  auto &instPaths =
617  instOpHierPaths[InnerRefAttr::get(moduleName, instInnerSym)];
618  if (currentPath.empty()) {
619  activeHierpaths.insert(instPaths.begin(), instPaths.end());
620  return;
621  }
622  DenseSet<StringAttr> hPaths(instPaths.begin(), instPaths.end());
623  // Only the hierPaths that this instance participates in, and is active in
624  // the current path must be kept active for the child modules.
625  llvm::set_intersect(activeHierpaths, hPaths);
626  // Also, the nlas, that have current instance as the top must be added to
627  // the active set.
628  for (auto hPath : instPaths)
629  if (nlaMap[hPath].hasRoot(moduleName))
630  activeHierpaths.insert(hPath);
631  }
632 
633  CircuitOp circuit;
634  MLIRContext *context;
635 
636  // A symbol table with references to each module in a circuit.
637  SymbolTable &symbolTable;
638 
639  /// The set of live modules. Anything not recorded in this set will be
640  /// removed by dead code elimination.
641  DenseSet<Operation *> liveModules;
642 
643  /// Worklist of modules to process for inlining or flattening.
644  SmallVector<FModuleOp, 16> worklist;
645 
646  /// A mapping of NLA symbol name to mutable NLA.
647  DenseMap<Attribute, MutableNLA> nlaMap;
648 
649  /// A mapping of module names to NLA symbols that originate from that module.
650  DenseMap<Attribute, SmallVector<Attribute>> rootMap;
651 
652  /// The current instance path. This is a pair<ModuleName, InstanceName>.
653  /// This is used to distinguish if a non-local annotation applies to the
654  /// current instance or not.
655  SmallVector<std::pair<Attribute, Attribute>> currentPath;
656 
657  DenseSet<StringAttr> activeHierpaths;
658 
659  /// Record the HierPathOps that each InstanceOp participates in. This is a map
660  /// from the InnerRefAttr to the list of HierPathOp names. The InnerRefAttr
661  /// corresponds to the InstanceOp.
662  DenseMap<InnerRefAttr, SmallVector<StringAttr>> instOpHierPaths;
663 
664  /// The debug scopes created for inlined instances. Scopes that are unused
665  /// after inlining will be deleted again.
666  SmallVector<debug::ScopeOp> debugScopes;
667 };
668 } // namespace
669 
670 /// Check if the NLA applies to our instance path. This works by verifying the
671 /// instance paths backwards starting from the current module. We drop the back
672 /// element from the NLA because it obviously matches the current operation.
673 bool Inliner::doesNLAMatchCurrentPath(hw::HierPathOp nla) {
674  return (activeHierpaths.find(nla.getSymNameAttr()) != activeHierpaths.end());
675 }
676 
677 /// If this operation or any child operation has a name, add the prefix to that
678 /// operation's name. If the operation has any inner symbols, make sure that
679 /// these are unique in the namespace. Record renamed inner symbols
680 /// in relocatedInnerSyms map for renaming local users.
681 bool Inliner::rename(StringRef prefix, Operation *op, InliningLevel &il) {
682  // Debug operations with implicit module scope now need an explicit scope,
683  // since inlining has destroyed the module whose scope they implicitly used.
684  auto updateDebugScope = [&](auto op) {
685  if (!op.getScope())
686  op.getScopeMutable().assign(il.debugScope);
687  };
688  if (auto varOp = dyn_cast<debug::VariableOp>(op))
689  return updateDebugScope(varOp), false;
690  if (auto scopeOp = dyn_cast<debug::ScopeOp>(op))
691  return updateDebugScope(scopeOp), false;
692 
693  // Add a prefix to things that has a "name" attribute.
694  if (auto nameAttr = op->getAttrOfType<StringAttr>("name"))
695  op->setAttr("name", StringAttr::get(op->getContext(),
696  (prefix + nameAttr.getValue())));
697 
698  // If the operation has an inner symbol, ensure that it is unique. Record
699  // renames for any NLAs that this participates in if the symbol was renamed.
700  auto symOp = dyn_cast<hw::InnerSymbolOpInterface>(op);
701  if (!symOp)
702  return false;
703  auto oldSymAttr = symOp.getInnerSymAttr();
704  auto newSymAttr =
705  uniqueInNamespace(oldSymAttr, il.relocatedInnerSyms, il.mic.modNamespace,
706  il.childModule.getNameAttr());
707 
708  if (!newSymAttr)
709  return false;
710 
711  // If there's a symbol on the root and it changed, do NLA work.
712  if (auto newSymStrAttr = newSymAttr.getSymName();
713  newSymStrAttr && newSymStrAttr != oldSymAttr.getSymName()) {
714  for (Annotation anno : AnnotationSet(op)) {
715  auto sym = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal");
716  if (!sym)
717  continue;
718  // If this is a breadcrumb, we update the annotation path
719  // unconditionally. If this is the leaf of the NLA, we need to make
720  // sure we only update the annotation if the current path matches the
721  // NLA. This matters when the same module is inlined twice and the NLA
722  // only applies to one of them.
723  auto &mnla = nlaMap[sym.getAttr()];
724  if (!doesNLAMatchCurrentPath(mnla.getNLA()))
725  continue;
726  mnla.setInnerSym(il.mic.module.getModuleNameAttr(), newSymStrAttr);
727  }
728  }
729 
730  symOp.setInnerSymbolAttr(newSymAttr);
731 
732  return newSymAttr != oldSymAttr;
733 }
734 
735 bool Inliner::renameInstance(
736  StringRef prefix, InliningLevel &il, InstanceOp oldInst, InstanceOp newInst,
737  const DenseMap<Attribute, Attribute> &symbolRenames) {
738  // TODO: There is currently no good way to annotate an explicit parent scope
739  // on instances. Just emit a note in debug runs until this is resolved.
740  LLVM_DEBUG({
741  if (il.debugScope)
742  llvm::dbgs() << "Discarding parent debug scope for " << oldInst << "\n";
743  });
744 
745  // Add this instance to the activeHierpaths. This ensures that NLAs that this
746  // instance participates in will be updated correctly.
747  auto parentActivePaths = activeHierpaths;
748  assert(oldInst->getParentOfType<FModuleOp>() == il.childModule);
749  if (auto instSym = getInnerSymName(oldInst))
750  setActiveHierPaths(oldInst->getParentOfType<FModuleOp>().getNameAttr(),
751  instSym);
752  // List of HierPathOps that are valid based on the InstanceOp being inlined
753  // and the InstanceOp which is being replaced after inlining. That is the set
754  // of HierPathOps that is common between these two.
755  SmallVector<StringAttr> validHierPaths;
756  auto oldParent = oldInst->getParentOfType<FModuleOp>().getNameAttr();
757  auto oldInstSym = getInnerSymName(oldInst);
758 
759  if (oldInstSym) {
760  // Get the innerRef to the original InstanceOp that is being inlined here.
761  // For all the HierPathOps that the instance being inlined participates
762  // in.
763  auto oldInnerRef = InnerRefAttr::get(oldParent, oldInstSym);
764  for (auto old : instOpHierPaths[oldInnerRef]) {
765  // If this HierPathOp is valid at the inlining context, where the
766  // instance is being inlined at. That is, if it exists in the
767  // activeHierpaths.
768  if (activeHierpaths.find(old) != activeHierpaths.end())
769  validHierPaths.push_back(old);
770  else
771  // The HierPathOp could have been renamed, check for the other retoped
772  // names, if they are active at the inlining context.
773  for (auto additionalSym : nlaMap[old].getAdditionalSymbols())
774  if (activeHierpaths.find(additionalSym.getName()) !=
775  activeHierpaths.end()) {
776  validHierPaths.push_back(old);
777  break;
778  }
779  }
780  }
781 
782  assert(getInnerSymName(newInst) == oldInstSym);
783 
784  // Do the renaming, creating new symbol as needed.
785  auto symbolChanged = rename(prefix, newInst, il);
786 
787  // If the symbol changed, update instOpHierPaths accordingly.
788  auto newSymAttr = getInnerSymName(newInst);
789  if (symbolChanged) {
790  assert(newSymAttr);
791  // The InstanceOp is renamed, so move the HierPathOps to the new
792  // InnerRefAttr.
793  auto newInnerRef = InnerRefAttr::get(
794  newInst->getParentOfType<FModuleOp>().getNameAttr(), newSymAttr);
795  instOpHierPaths[newInnerRef] = validHierPaths;
796  // Update the innerSym for all the affected HierPathOps.
797  for (auto nla : instOpHierPaths[newInnerRef]) {
798  if (!nlaMap.count(nla))
799  continue;
800  auto &mnla = nlaMap[nla];
801  mnla.setInnerSym(newInnerRef.getModule(), newSymAttr);
802  }
803  }
804 
805  if (newSymAttr) {
806  auto innerRef = InnerRefAttr::get(
807  newInst->getParentOfType<FModuleOp>().getNameAttr(), newSymAttr);
808  SmallVector<StringAttr> &nlaList = instOpHierPaths[innerRef];
809  // Now rename the Updated HierPathOps that this InstanceOp participates in.
810  for (const auto &en : llvm::enumerate(nlaList)) {
811  auto oldNLA = en.value();
812  if (auto newSym = symbolRenames.lookup(oldNLA))
813  nlaList[en.index()] = cast<StringAttr>(newSym);
814  }
815  }
816  activeHierpaths = std::move(parentActivePaths);
817  return symbolChanged;
818 }
819 
820 /// This function is used before inlining a module, to handle the conversion
821 /// between module ports and instance results. For every port in the target
822 /// module, create a wire, and assign a mapping from each module port to the
823 /// wire. When the body of the module is cloned, the value of the wire will be
824 /// used instead of the module's ports.
825 void Inliner::mapPortsToWires(StringRef prefix, InliningLevel &il,
826  IRMapping &mapper,
827  const DenseSet<Attribute> &localSymbols) {
828  auto target = il.childModule;
829  auto portInfo = target.getPorts();
830  for (unsigned i = 0, e = target.getNumPorts(); i < e; ++i) {
831  auto arg = target.getArgument(i);
832  // Get the type of the wire.
833  auto type = type_cast<FIRRTLType>(arg.getType());
834 
835  // Compute new symbols if needed.
836  auto oldSymAttr = portInfo[i].sym;
837  auto newSymAttr =
838  uniqueInNamespace(oldSymAttr, il.relocatedInnerSyms,
839  il.mic.modNamespace, target.getNameAttr());
840 
841  StringAttr newRootSymName, oldRootSymName;
842  if (oldSymAttr)
843  oldRootSymName = oldSymAttr.getSymName();
844  if (newSymAttr)
845  newRootSymName = newSymAttr.getSymName();
846 
847  SmallVector<Attribute> newAnnotations;
848  for (auto anno : AnnotationSet::forPort(target, i)) {
849  // If the annotation is not non-local, copy it to the clone.
850  if (auto sym = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal")) {
851  auto &mnla = nlaMap[sym.getAttr()];
852  // If the NLA does not match the path, we don't want to copy it over.
853  if (!doesNLAMatchCurrentPath(mnla.getNLA()))
854  continue;
855  // Update any NLAs with the new symbol name.
856  // This does not handle per-field symbols used in NLA's.
857  if (oldRootSymName != newRootSymName)
858  mnla.setInnerSym(il.mic.module.getModuleNameAttr(), newRootSymName);
859  // If all paths of the NLA have been inlined, make it local.
860  if (mnla.isLocal() || localSymbols.count(sym.getAttr()))
861  anno.removeMember("circt.nonlocal");
862  }
863  newAnnotations.push_back(anno.getAttr());
864  }
865 
866  Value wire =
867  il.mic.b
868  .create<WireOp>(
869  target.getLoc(), type,
870  StringAttr::get(context, (prefix + portInfo[i].getName())),
871  NameKindEnumAttr::get(context, NameKindEnum::DroppableName),
872  ArrayAttr::get(context, newAnnotations), newSymAttr,
873  /*forceable=*/UnitAttr{})
874  .getResult();
875  il.wires.push_back(wire);
876  mapper.map(arg, wire);
877  }
878 }
879 
880 /// Clone an operation, mapping used values and results with the mapper, and
881 /// apply the prefix to the name of the operation. This will clone to the
882 /// insert point of the builder. Insert the operation into the level.
883 void Inliner::cloneAndRename(
884  StringRef prefix, InliningLevel &il, IRMapping &mapper, Operation &op,
885  const DenseMap<Attribute, Attribute> &symbolRenames,
886  const DenseSet<Attribute> &localSymbols) {
887  // Strip any non-local annotations which are local.
888  AnnotationSet oldAnnotations(&op);
889  SmallVector<Annotation> newAnnotations;
890  for (auto anno : oldAnnotations) {
891  // If the annotation is not non-local, it will apply to all inlined
892  // instances of this op. Add it to the cloned op.
893  if (auto sym = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal")) {
894  // Retrieve the corresponding NLA.
895  auto &mnla = nlaMap[sym.getAttr()];
896  // If the NLA does not match the path we don't want to copy it over.
897  if (!doesNLAMatchCurrentPath(mnla.getNLA()))
898  continue;
899  // The NLA has become local, rewrite the annotation to be local.
900  if (mnla.isLocal() || localSymbols.count(sym.getAttr()))
901  anno.removeMember("circt.nonlocal");
902  }
903  // Attach this annotation to the cloned operation.
904  newAnnotations.push_back(anno);
905  }
906 
907  // Clone and rename.
908  assert(op.getNumRegions() == 0 &&
909  "operation with regions should not reach cloneAndRename");
910  auto *newOp = il.mic.b.cloneWithoutRegions(op, mapper);
911 
912  // Rename the new operation.
913  // (add prefix to it, if named, and unique-ify symbol, updating NLA's).
914 
915  // Instances require extra handling to update HierPathOp's if their symbols
916  // change.
917  if (auto oldInst = dyn_cast<InstanceOp>(op))
918  renameInstance(prefix, il, oldInst, cast<InstanceOp>(newOp), symbolRenames);
919  else
920  rename(prefix, newOp, il);
921 
922  // We want to avoid attaching an empty annotation array on to an op that
923  // never had an annotation array in the first place.
924  if (!newAnnotations.empty() || !oldAnnotations.empty())
925  AnnotationSet(newAnnotations, context).applyToOperation(newOp);
926 
927  il.newOps.push_back(newOp);
928 }
929 
930 bool Inliner::shouldFlatten(Operation *op) {
932 }
933 
934 bool Inliner::shouldInline(Operation *op) {
936 }
937 
938 LogicalResult Inliner::inliningWalk(
939  OpBuilder &builder, Block *block, IRMapping &mapper,
940  llvm::function_ref<LogicalResult(Operation *op)> process) {
941  struct IPs {
942  OpBuilder::InsertPoint target;
943  Block::iterator source;
944  };
945  // Invariant: no Block::iterator == end(), can't getBlock().
946  SmallVector<IPs> inliningStack;
947  if (block->empty())
948  return success();
949 
950  inliningStack.push_back(IPs{builder.saveInsertionPoint(), block->begin()});
951  OpBuilder::InsertionGuard guard(builder);
952 
953  while (!inliningStack.empty()) {
954  auto target = inliningStack.back().target;
955  builder.restoreInsertionPoint(target);
956  Operation *source;
957  // Get next source operation.
958  {
959  auto &ips = inliningStack.back();
960  source = &*ips.source;
961  auto end = source->getBlock()->end();
962  if (++ips.source == end)
963  inliningStack.pop_back();
964  }
965 
966  // Does the source have regions? If not, use callback to process.
967  if (source->getNumRegions() == 0) {
968  assert(builder.saveInsertionPoint().getPoint() == target.getPoint());
969  // Clone source into insertion point 'target'.
970  if (failed(process(source)))
971  return failure();
972  assert(builder.saveInsertionPoint().getPoint() == target.getPoint());
973 
974  continue;
975  }
976 
977  // Limited support for region-containing operations.
978  if (!isa<LayerBlockOp, WhenOp, MatchOp>(source))
979  return source->emitError("unsupported operation '")
980  << source->getName() << "' cannot be inlined";
981 
982  // Note: This does not use cloneAndRename for simplicity,
983  // as there are no annotations, symbols to rename, or names
984  // to prefix. This does mean these operations do not appear
985  // in `il.newOps` for inner-ref renaming walk, FWIW.
986  auto *newOp = builder.cloneWithoutRegions(*source, mapper);
987  for (auto [newRegion, oldRegion] : llvm::reverse(
988  llvm::zip_equal(newOp->getRegions(), source->getRegions()))) {
989  // If region has no blocks, skip.
990  if (oldRegion.empty()) {
991  assert(newRegion.empty());
992  continue;
993  }
994  // Otherwise, assert single block. Multiple blocks is trickier.
995  assert(oldRegion.hasOneBlock());
996 
997  // Create new block and add to inlining stack for processing.
998  auto &oldBlock = oldRegion.getBlocks().front();
999  auto &newBlock = newRegion.emplaceBlock();
1000  mapper.map(&oldBlock, &newBlock);
1001 
1002  // Copy block arguments, and add mapping for each.
1003  for (auto arg : oldBlock.getArguments())
1004  mapper.map(arg, newBlock.addArgument(arg.getType(), arg.getLoc()));
1005 
1006  if (oldBlock.empty())
1007  continue;
1008 
1009  inliningStack.push_back(
1010  IPs{OpBuilder::InsertPoint(&newBlock, newBlock.begin()),
1011  oldBlock.begin()});
1012  }
1013  }
1014  return success();
1015 }
1016 
1017 LogicalResult Inliner::checkInstanceParents(InstanceOp instance) {
1018  auto *parent = instance->getParentOp();
1019  while (!isa<FModuleLike>(parent)) {
1020  if (!isa<LayerBlockOp>(parent))
1021  return instance->emitError("cannot inline instance")
1022  .attachNote(parent->getLoc())
1023  << "containing operation '" << parent->getName()
1024  << "' not safe to inline into";
1025  parent = parent->getParentOp();
1026  }
1027  return success();
1028 }
1029 
1030 // NOLINTNEXTLINE(misc-no-recursion)
1031 LogicalResult Inliner::flattenInto(StringRef prefix, InliningLevel &il,
1032  IRMapping &mapper,
1033  DenseSet<Attribute> localSymbols) {
1034  auto target = il.childModule;
1035  auto moduleName = target.getNameAttr();
1036  DenseMap<Attribute, Attribute> symbolRenames;
1037 
1038  LLVM_DEBUG(llvm::dbgs() << "flattening " << target.getModuleName() << " into "
1039  << il.mic.module.getModuleName() << "\n");
1040  auto visit = [&](Operation *op) {
1041  // If it's not an instance op, clone it and continue.
1042  auto instance = dyn_cast<InstanceOp>(op);
1043  if (!instance) {
1044  cloneAndRename(prefix, il, mapper, *op, symbolRenames, localSymbols);
1045  return success();
1046  }
1047 
1048  // If it's not a regular module we can't inline it. Mark it as live.
1049  auto *moduleOp = symbolTable.lookup(instance.getModuleName());
1050  auto childModule = dyn_cast<FModuleOp>(moduleOp);
1051  if (!childModule) {
1052  liveModules.insert(moduleOp);
1053 
1054  cloneAndRename(prefix, il, mapper, *op, symbolRenames, localSymbols);
1055  return success();
1056  }
1057 
1058  if (failed(checkInstanceParents(instance)))
1059  return failure();
1060 
1061  // Add any NLAs which start at this instance to the localSymbols set.
1062  // Anything in this set will be made local during the recursive flattenInto
1063  // walk.
1064  llvm::set_union(localSymbols, rootMap[childModule.getNameAttr()]);
1065  auto instInnerSym = getInnerSymName(instance);
1066  auto parentActivePaths = activeHierpaths;
1067  setActiveHierPaths(moduleName, instInnerSym);
1068  currentPath.emplace_back(moduleName, instInnerSym);
1069 
1070  InliningLevel childIL(il.mic, childModule);
1071  createDebugScope(childIL, instance, il.debugScope);
1072 
1073  // Create the wire mapping for results + ports.
1074  auto nestedPrefix = (prefix + instance.getName() + "_").str();
1075  mapPortsToWires(nestedPrefix, childIL, mapper, localSymbols);
1076  mapResultsToWires(mapper, childIL.wires, instance);
1077 
1078  // Unconditionally flatten all instance operations.
1079  if (failed(flattenInto(nestedPrefix, childIL, mapper, localSymbols)))
1080  return failure();
1081  currentPath.pop_back();
1082  activeHierpaths = parentActivePaths;
1083  return success();
1084  };
1085  return inliningWalk(il.mic.b, target.getBodyBlock(), mapper, visit);
1086 }
1087 
1088 LogicalResult Inliner::flattenInstances(FModuleOp module) {
1089  auto moduleName = module.getNameAttr();
1090  ModuleInliningContext mic(module);
1091 
1092  auto visit = [&](InstanceOp instance) {
1093  // If it's not a regular module we can't inline it. Mark it as live.
1094  auto *targetModule = symbolTable.lookup(instance.getModuleName());
1095  auto target = dyn_cast<FModuleOp>(targetModule);
1096  if (!target) {
1097  liveModules.insert(targetModule);
1098  return WalkResult::advance();
1099  }
1100 
1101  if (failed(checkInstanceParents(instance)))
1102  return WalkResult::interrupt();
1103 
1104  if (auto instSym = getInnerSymName(instance)) {
1105  auto innerRef = InnerRefAttr::get(moduleName, instSym);
1106  // Preorder update of any non-local annotations this instance participates
1107  // in. This needs to happen _before_ visiting modules so that internal
1108  // non-local annotations can be deleted if they are now local.
1109  for (auto targetNLA : instOpHierPaths[innerRef])
1110  nlaMap[targetNLA].flattenModule(target);
1111  }
1112 
1113  // Add any NLAs which start at this instance to the localSymbols set.
1114  // Anything in this set will be made local during the recursive flattenInto
1115  // walk.
1116  DenseSet<Attribute> localSymbols;
1117  llvm::set_union(localSymbols, rootMap[target.getNameAttr()]);
1118  auto instInnerSym = getInnerSymName(instance);
1119  auto parentActivePaths = activeHierpaths;
1120  setActiveHierPaths(moduleName, instInnerSym);
1121  currentPath.emplace_back(moduleName, instInnerSym);
1122 
1123  // Create the wire mapping for results + ports. We RAUW the results instead
1124  // of mapping them.
1125  IRMapping mapper;
1126  mic.b.setInsertionPoint(instance);
1127 
1128  InliningLevel il(mic, target);
1129  createDebugScope(il, instance);
1130 
1131  auto nestedPrefix = (instance.getName() + "_").str();
1132  mapPortsToWires(nestedPrefix, il, mapper, localSymbols);
1133  for (unsigned i = 0, e = instance.getNumResults(); i < e; ++i)
1134  instance.getResult(i).replaceAllUsesWith(il.wires[i]);
1135 
1136  // Recursively flatten the target module.
1137  if (failed(flattenInto(nestedPrefix, il, mapper, localSymbols)))
1138  return WalkResult::interrupt();
1139  currentPath.pop_back();
1140  activeHierpaths = parentActivePaths;
1141 
1142  // Erase the replaced instance.
1143  instance.erase();
1144  return WalkResult::skip();
1145  };
1146  return failure(module.getBodyBlock()
1147  ->walk<mlir::WalkOrder::PreOrder>(visit)
1148  .wasInterrupted());
1149 }
1150 
1151 // NOLINTNEXTLINE(misc-no-recursion)
1152 LogicalResult
1153 Inliner::inlineInto(StringRef prefix, InliningLevel &il, IRMapping &mapper,
1154  DenseMap<Attribute, Attribute> &symbolRenames) {
1155  auto target = il.childModule;
1156  auto inlineToParent = il.mic.module;
1157  auto moduleName = target.getNameAttr();
1158 
1159  LLVM_DEBUG(llvm::dbgs() << "inlining " << target.getModuleName() << " into "
1160  << inlineToParent.getModuleName() << "\n");
1161 
1162  auto visit = [&](Operation *op) {
1163  // If it's not an instance op, clone it and continue.
1164  auto instance = dyn_cast<InstanceOp>(op);
1165  if (!instance) {
1166  cloneAndRename(prefix, il, mapper, *op, symbolRenames, {});
1167  return success();
1168  }
1169 
1170  // If it's not a regular module we can't inline it. Mark it as live.
1171  auto *moduleOp = symbolTable.lookup(instance.getModuleName());
1172  auto childModule = dyn_cast<FModuleOp>(moduleOp);
1173  if (!childModule) {
1174  liveModules.insert(moduleOp);
1175  cloneAndRename(prefix, il, mapper, *op, symbolRenames, {});
1176  return success();
1177  }
1178 
1179  // If we aren't inlining the target, add it to the work list.
1180  if (!shouldInline(childModule)) {
1181  if (liveModules.insert(childModule).second) {
1182  worklist.push_back(childModule);
1183  }
1184  cloneAndRename(prefix, il, mapper, *op, symbolRenames, {});
1185  return success();
1186  }
1187 
1188  if (failed(checkInstanceParents(instance)))
1189  return failure();
1190 
1191  auto toBeFlattened = shouldFlatten(childModule);
1192  if (auto instSym = getInnerSymName(instance)) {
1193  auto innerRef = InnerRefAttr::get(moduleName, instSym);
1194  // Preorder update of any non-local annotations this instance participates
1195  // in. This needs to happen _before_ visiting modules so that internal
1196  // non-local annotations can be deleted if they are now local.
1197  for (auto sym : instOpHierPaths[innerRef]) {
1198  if (toBeFlattened)
1199  nlaMap[sym].flattenModule(childModule);
1200  else
1201  nlaMap[sym].inlineModule(childModule);
1202  }
1203  }
1204 
1205  // The InstanceOp `instance` might not have a symbol, if it does not
1206  // participate in any HierPathOp. But the reTop might add a symbol to it, if
1207  // a HierPathOp is added to this Op. If we're about to inline a module that
1208  // contains a non-local annotation that starts at that module, then we need
1209  // to both update the mutable NLA to indicate that this has a new top and
1210  // add an annotation on the instance saying that this now participates in
1211  // this new NLA.
1212  DenseMap<Attribute, Attribute> symbolRenames;
1213  if (!rootMap[childModule.getNameAttr()].empty()) {
1214  for (auto sym : rootMap[childModule.getNameAttr()]) {
1215  auto &mnla = nlaMap[sym];
1216  // Retop to the new parent, which is the topmost module (and not
1217  // immediate parent) in case of recursive inlining.
1218  sym = mnla.reTop(inlineToParent);
1219  StringAttr instSym = getInnerSymName(instance);
1220  if (!instSym) {
1221  instSym = StringAttr::get(
1222  context, il.mic.modNamespace.newName(instance.getName()));
1223  instance.setInnerSymAttr(hw::InnerSymAttr::get(instSym));
1224  }
1225  instOpHierPaths[InnerRefAttr::get(moduleName, instSym)].push_back(
1226  cast<StringAttr>(sym));
1227  // TODO: Update any symbol renames which need to be used by the next
1228  // call of inlineInto. This will then check each instance and rename
1229  // any symbols appropriately for that instance.
1230  symbolRenames.insert({mnla.getNLA().getNameAttr(), sym});
1231  }
1232  }
1233  auto instInnerSym = getInnerSymName(instance);
1234  auto parentActivePaths = activeHierpaths;
1235  setActiveHierPaths(moduleName, instInnerSym);
1236  // This must be done after the reTop, since it might introduce an innerSym.
1237  currentPath.emplace_back(moduleName, instInnerSym);
1238 
1239  InliningLevel childIL(il.mic, childModule);
1240  createDebugScope(childIL, instance, il.debugScope);
1241 
1242  // Create the wire mapping for results + ports.
1243  auto nestedPrefix = (prefix + instance.getName() + "_").str();
1244  mapPortsToWires(nestedPrefix, childIL, mapper, {});
1245  mapResultsToWires(mapper, childIL.wires, instance);
1246 
1247  // Inline the module, it can be marked as flatten and inline.
1248  if (toBeFlattened) {
1249  if (failed(flattenInto(nestedPrefix, childIL, mapper, {})))
1250  return failure();
1251  } else {
1252  if (failed(inlineInto(nestedPrefix, childIL, mapper, symbolRenames)))
1253  return failure();
1254  }
1255  currentPath.pop_back();
1256  activeHierpaths = parentActivePaths;
1257  return success();
1258  };
1259 
1260  return inliningWalk(il.mic.b, target.getBodyBlock(), mapper, visit);
1261 }
1262 
1263 LogicalResult Inliner::inlineInstances(FModuleOp module) {
1264  // Generate a namespace for this module so that we can safely inline symbols.
1265  auto moduleName = module.getNameAttr();
1266  ModuleInliningContext mic(module);
1267 
1268  auto visit = [&](InstanceOp instance) {
1269  // If it's not a regular module we can't inline it. Mark it as live.
1270  auto *childModule = symbolTable.lookup(instance.getModuleName());
1271  auto target = dyn_cast<FModuleOp>(childModule);
1272  if (!target) {
1273  liveModules.insert(childModule);
1274  return WalkResult::advance();
1275  }
1276 
1277  // If we aren't inlining the target, add it to the work list.
1278  if (!shouldInline(target)) {
1279  if (liveModules.insert(target).second) {
1280  worklist.push_back(target);
1281  }
1282  return WalkResult::advance();
1283  }
1284 
1285  if (failed(checkInstanceParents(instance)))
1286  return WalkResult::interrupt();
1287 
1288  auto toBeFlattened = shouldFlatten(target);
1289  if (auto instSym = getInnerSymName(instance)) {
1290  auto innerRef = InnerRefAttr::get(moduleName, instSym);
1291  // Preorder update of any non-local annotations this instance participates
1292  // in. This needs to happen _before_ visiting modules so that internal
1293  // non-local annotations can be deleted if they are now local.
1294  for (auto sym : instOpHierPaths[innerRef]) {
1295  if (toBeFlattened)
1296  nlaMap[sym].flattenModule(target);
1297  else
1298  nlaMap[sym].inlineModule(target);
1299  }
1300  }
1301 
1302  // The InstanceOp `instance` might not have a symbol, if it does not
1303  // participate in any HierPathOp. But the reTop might add a symbol to it, if
1304  // a HierPathOp is added to this Op.
1305  DenseMap<Attribute, Attribute> symbolRenames;
1306  if (!rootMap[target.getNameAttr()].empty() && !toBeFlattened) {
1307  for (auto sym : rootMap[target.getNameAttr()]) {
1308  auto &mnla = nlaMap[sym];
1309  sym = mnla.reTop(module);
1310  StringAttr instSym = getOrAddInnerSym(
1311  instance, [&](FModuleLike mod) -> hw::InnerSymbolNamespace & {
1312  return mic.modNamespace;
1313  });
1314  instOpHierPaths[InnerRefAttr::get(moduleName, instSym)].push_back(
1315  cast<StringAttr>(sym));
1316  // TODO: Update any symbol renames which need to be used by the next
1317  // call of inlineInto. This will then check each instance and rename
1318  // any symbols appropriately for that instance.
1319  symbolRenames.insert({mnla.getNLA().getNameAttr(), sym});
1320  }
1321  }
1322  auto instInnerSym = getInnerSymName(instance);
1323  auto parentActivePaths = activeHierpaths;
1324  setActiveHierPaths(moduleName, instInnerSym);
1325  // This must be done after the reTop, since it might introduce an innerSym.
1326  currentPath.emplace_back(moduleName, instInnerSym);
1327  // Create the wire mapping for results + ports. We RAUW the results instead
1328  // of mapping them.
1329  IRMapping mapper;
1330  mic.b.setInsertionPoint(instance);
1331  auto nestedPrefix = (instance.getName() + "_").str();
1332 
1333  InliningLevel childIL(mic, target);
1334  createDebugScope(childIL, instance);
1335 
1336  mapPortsToWires(nestedPrefix, childIL, mapper, {});
1337  for (unsigned i = 0, e = instance.getNumResults(); i < e; ++i)
1338  instance.getResult(i).replaceAllUsesWith(childIL.wires[i]);
1339 
1340  // Inline the module, it can be marked as flatten and inline.
1341  if (toBeFlattened) {
1342  if (failed(flattenInto(nestedPrefix, childIL, mapper, {})))
1343  return WalkResult::interrupt();
1344  } else {
1345  // Recursively inline all the child modules under `parent`, that are
1346  // marked to be inlined.
1347  if (failed(inlineInto(nestedPrefix, childIL, mapper, symbolRenames)))
1348  return WalkResult::interrupt();
1349  }
1350  currentPath.pop_back();
1351  activeHierpaths = parentActivePaths;
1352 
1353  // Erase the replaced instance.
1354  instance.erase();
1355  return WalkResult::skip();
1356  };
1357 
1358  return failure(module.getBodyBlock()
1359  ->walk<mlir::WalkOrder::PreOrder>(visit)
1360  .wasInterrupted());
1361 }
1362 
1363 void Inliner::createDebugScope(InliningLevel &il, InstanceOp instance,
1364  Value parentScope) {
1365  auto op = il.mic.b.create<debug::ScopeOp>(
1366  instance.getLoc(), instance.getInstanceNameAttr(),
1367  instance.getModuleNameAttr().getAttr(), parentScope);
1368  debugScopes.push_back(op);
1369  il.debugScope = op;
1370 }
1371 
1372 void Inliner::identifyNLAsTargetingOnlyModules() {
1373  DenseSet<Operation *> nlaTargetedModules;
1374 
1375  // Identify candidate NLA's: those that end in a module
1376  for (auto &[sym, mnla] : nlaMap) {
1377  auto nla = mnla.getNLA();
1378  if (nla.isModule()) {
1379  auto mod = symbolTable.lookup<FModuleLike>(nla.leafMod());
1380  assert(mod &&
1381  "NLA ends in module reference but does not target FModuleLike?");
1382  nlaTargetedModules.insert(mod);
1383  }
1384  }
1385 
1386  // Helper to scan leaf modules for users of NLAs, gathering by symbol names
1387  auto scanForNLARefs = [&](FModuleLike mod) {
1388  DenseSet<StringAttr> referencedNLASyms;
1389  auto scanAnnos = [&](const AnnotationSet &annos) {
1390  for (auto anno : annos)
1391  if (auto sym = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal"))
1392  referencedNLASyms.insert(sym.getAttr());
1393  };
1394  // Scan ports
1395  for (unsigned i = 0, e = mod.getNumPorts(); i != e; ++i)
1396  scanAnnos(AnnotationSet::forPort(mod, i));
1397 
1398  // Scan operations (and not the module itself):
1399  // (Walk includes module for lack of simple/generic way to walk body only)
1400  mod.walk([&](Operation *op) {
1401  if (op == mod.getOperation())
1402  return;
1403  scanAnnos(AnnotationSet(op));
1404 
1405  // Check MemOp and InstanceOp port annotations, special case
1406  TypeSwitch<Operation *>(op).Case<MemOp, InstanceOp>([&](auto op) {
1407  for (auto portAnnoAttr : op.getPortAnnotations())
1408  scanAnnos(AnnotationSet(cast<ArrayAttr>(portAnnoAttr)));
1409  });
1410  });
1411 
1412  return referencedNLASyms;
1413  };
1414 
1415  // Reduction operator
1416  auto mergeSets = [](auto &&a, auto &&b) {
1417  a.insert(b.begin(), b.end());
1418  return std::move(a);
1419  };
1420 
1421  // Walk modules in parallel, scanning for references to NLA's
1422  // Gather set of NLA's referenced by each module's ports/operations.
1423  SmallVector<FModuleLike, 0> mods(nlaTargetedModules.begin(),
1424  nlaTargetedModules.end());
1425  auto nonModOnlyNLAs =
1426  transformReduce(circuit->getContext(), mods, DenseSet<StringAttr>{},
1427  mergeSets, scanForNLARefs);
1428 
1429  // Mark NLA's that were not referenced as module-only
1430  for (auto &[_, mnla] : nlaMap) {
1431  auto nla = mnla.getNLA();
1432  if (nla.isModule() && !nonModOnlyNLAs.count(nla.getSymNameAttr()))
1433  mnla.markModuleOnly();
1434  }
1435 }
1436 
1437 Inliner::Inliner(CircuitOp circuit, SymbolTable &symbolTable)
1438  : circuit(circuit), context(circuit.getContext()),
1439  symbolTable(symbolTable) {}
1440 
1441 LogicalResult Inliner::run() {
1442  CircuitNamespace circuitNamespace(circuit);
1443 
1444  // Gather all NLA's, build information about the instance ops used:
1445  for (auto nla : circuit.getBodyBlock()->getOps<hw::HierPathOp>()) {
1446  auto mnla = MutableNLA(nla, &circuitNamespace);
1447  nlaMap.insert({nla.getSymNameAttr(), mnla});
1448  rootMap[mnla.getNLA().root()].push_back(nla.getSymNameAttr());
1449  for (auto p : nla.getNamepath())
1450  if (auto ref = dyn_cast<InnerRefAttr>(p))
1451  instOpHierPaths[ref].push_back(nla.getSymNameAttr());
1452  }
1453  // Mark 'module-only' the NLA's that only target modules.
1454  // These may be deleted when their module is inlined/flattened.
1455  identifyNLAsTargetingOnlyModules();
1456 
1457  // Mark the top module as live, so it doesn't get deleted.
1458  for (auto module : circuit.getOps<FModuleLike>()) {
1459  if (module.canDiscardOnUseEmpty())
1460  continue;
1461  liveModules.insert(module);
1462  if (isa<FModuleOp>(module))
1463  worklist.push_back(cast<FModuleOp>(module));
1464  }
1465 
1466  // If the module is marked for flattening, flatten it. Otherwise, inline
1467  // every instance marked to be inlined.
1468  while (!worklist.empty()) {
1469  auto moduleOp = worklist.pop_back_val();
1470  if (shouldFlatten(moduleOp)) {
1471  if (failed(flattenInstances(moduleOp)))
1472  return failure();
1473  // Delete the flatten annotation, the transform was performed.
1474  // Even if visited again in our walk (for inlining),
1475  // we've just flattened it and so the annotation is no longer needed.
1476  AnnotationSet::removeAnnotations(moduleOp, flattenAnnoClass);
1477  } else {
1478  if (failed(inlineInstances(moduleOp)))
1479  return failure();
1480  }
1481  }
1482 
1483  // Delete debug scopes that ended up being unused. Erase them in reverse order
1484  // since scopes at the back may have uses on scopes at the front.
1485  for (auto scopeOp : llvm::reverse(debugScopes))
1486  if (scopeOp.use_empty())
1487  scopeOp.erase();
1488  debugScopes.clear();
1489 
1490  // Delete all unreferenced modules. Mark any NLAs that originate from dead
1491  // modules as also dead.
1492  for (auto mod : llvm::make_early_inc_range(
1493  circuit.getBodyBlock()->getOps<FModuleLike>())) {
1494  if (liveModules.count(mod))
1495  continue;
1496  for (auto nla : rootMap[mod.getModuleNameAttr()])
1497  nlaMap[nla].markDead();
1498  mod.erase();
1499  }
1500 
1501  // Remove leftover inline annotations, and check no flatten annotations
1502  // remain as they should have been processed and removed.
1503  for (auto mod : circuit.getBodyBlock()->getOps<FModuleLike>()) {
1504  if (shouldInline(mod)) {
1505  assert(mod.isPublic() &&
1506  "non-public module with inline annotation still present");
1507  AnnotationSet::removeAnnotations(mod, inlineAnnoClass);
1508  }
1509  assert(!shouldFlatten(mod) && "flatten annotation found on live module");
1510  }
1511 
1512  LLVM_DEBUG({
1513  llvm::dbgs() << "NLA modifications:\n";
1514  for (auto nla : circuit.getBodyBlock()->getOps<hw::HierPathOp>()) {
1515  auto &mnla = nlaMap[nla.getNameAttr()];
1516  mnla.dump();
1517  }
1518  });
1519 
1520  // Writeback all NLAs to MLIR.
1521  for (auto &nla : nlaMap)
1522  nla.getSecond().applyUpdates();
1523 
1524  // Garbage collect any annotations which are now dead. Duplicate annotations
1525  // which are now split.
1526  for (auto fmodule : circuit.getBodyBlock()->getOps<FModuleOp>()) {
1527  SmallVector<Attribute> newAnnotations;
1528  auto processNLAs = [&](Annotation anno) -> bool {
1529  if (auto sym = anno.getMember<FlatSymbolRefAttr>("circt.nonlocal")) {
1530  // If the symbol isn't in the NLA map, just skip it. This avoids
1531  // problems where the nlaMap "[]" will try to construct a default
1532  // MutableNLA map (which it should never do).
1533  if (!nlaMap.count(sym.getAttr()))
1534  return false;
1535 
1536  auto mnla = nlaMap[sym.getAttr()];
1537 
1538  // Garbage collect dead NLA references. This cleans up NLAs that go
1539  // through modules which we never visited.
1540  if (mnla.isDead())
1541  return true;
1542 
1543  // Do nothing if there are no additional NLAs to add or if we're
1544  // dealing with a root module. Root modules have already been updated
1545  // earlier in the pass. We only need to update NLA paths which are
1546  // not the root.
1547  auto newTops = mnla.getAdditionalSymbols();
1548  if (newTops.empty() || mnla.hasRoot(fmodule))
1549  return false;
1550 
1551  // Add NLAs to the non-root portion of the NLA. This only needs to
1552  // add symbols for NLAs which are after the first one. We reused the
1553  // old symbol name for the first NLA.
1554  NamedAttrList newAnnotation;
1555  for (auto rootAndSym : newTops.drop_front()) {
1556  for (auto pair : anno.getDict()) {
1557  if (pair.getName().getValue() != "circt.nonlocal") {
1558  newAnnotation.push_back(pair);
1559  continue;
1560  }
1561  newAnnotation.push_back(
1562  {pair.getName(), FlatSymbolRefAttr::get(rootAndSym.getName())});
1563  }
1564  newAnnotations.push_back(DictionaryAttr::get(context, newAnnotation));
1565  }
1566  }
1567  return false;
1568  };
1569  fmodule.walk([&](Operation *op) {
1570  AnnotationSet annotations(op);
1571  // Early exit to avoid adding an empty annotations attribute to operations
1572  // which did not previously have annotations.
1573  if (annotations.empty())
1574  return;
1575 
1576  // Update annotations on the op.
1577  newAnnotations.clear();
1578  annotations.removeAnnotations(processNLAs);
1579  annotations.addAnnotations(newAnnotations);
1580  annotations.applyToOperation(op);
1581  });
1582 
1583  // Update annotations on the ports.
1584  SmallVector<Attribute> newPortAnnotations;
1585  for (auto port : fmodule.getPorts()) {
1586  newAnnotations.clear();
1587  port.annotations.removeAnnotations(processNLAs);
1588  port.annotations.addAnnotations(newAnnotations);
1589  newPortAnnotations.push_back(
1590  ArrayAttr::get(context, port.annotations.getArray()));
1591  }
1592  fmodule->setAttr("portAnnotations",
1593  ArrayAttr::get(context, newPortAnnotations));
1594  }
1595  return success();
1596 }
1597 
1598 //===----------------------------------------------------------------------===//
1599 // Pass Infrastructure
1600 //===----------------------------------------------------------------------===//
1601 
1602 namespace {
1603 class InlinerPass : public circt::firrtl::impl::InlinerBase<InlinerPass> {
1604  void runOnOperation() override {
1605  LLVM_DEBUG(debugPassHeader(this) << "\n");
1606  Inliner inliner(getOperation(), getAnalysis<SymbolTable>());
1607  if (failed(inliner.run()))
1608  signalPassFailure();
1609  LLVM_DEBUG(debugFooter() << "\n");
1610  }
1611 };
1612 } // namespace
1613 
1614 std::unique_ptr<mlir::Pass> circt::firrtl::createInlinerPass() {
1615  return std::make_unique<InlinerPass>();
1616 }
assert(baseType &&"element must be base type")
static void dump(DIModule &module, raw_indented_ostream &os)
DenseMap< hw::InnerRefAttr, StringAttr > InnerRefToNewNameMap
static hw::InnerSymAttr uniqueInNamespace(hw::InnerSymAttr old, InnerRefToNewNameMap &map, hw::InnerSymbolNamespace &ns, StringAttr istName)
Generate and creating map entries for new inner symbol based on old one and an appropriate namespace ...
static void mapResultsToWires(IRMapping &mapper, SmallVectorImpl< Value > &wires, InstanceOp instance)
This function is used after inlining a module, to handle the conversion between module ports and inst...
static void replaceInnerRefUsers(ArrayRef< Operation * > newOps, const InnerRefToNewNameMap &map, StringAttr istName)
Process each operation, updating InnerRefAttr's using the specified map and the given name as the con...
StringRef newName(const Twine &name)
Return a unique name, derived from the input name, and add the new name to the internal namespace.
Definition: Namespace.h:85
This class provides a read-only projection over the MLIR attributes that represent a set of annotatio...
bool applyToOperation(Operation *op) const
Store the annotations in this set in an operation's annotations attribute, overwriting any existing a...
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.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:55
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.
std::unique_ptr< mlir::Pass > createInlinerPass()
static ResultTy transformReduce(MLIRContext *context, IterTy begin, IterTy end, ResultTy init, ReduceFuncTy reduce, TransformFuncTy transform)
Wrapper for llvm::parallelTransformReduce that performs the transform_reduce serially when MLIR multi...
Definition: FIRRTLUtils.h:295
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const InstanceInfo::LatticeValue &value)
constexpr const char * inlineAnnoClass
constexpr const char * flattenAnnoClass
StringAttr getInnerSymName(Operation *op)
Return the StringAttr for the inner_sym name, if it exists.
Definition: FIRRTLOps.h:108
StringAttr getName(ArrayAttr names, size_t idx)
Return the name at the specified index of the ArrayAttr or null if it cannot be determined.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
llvm::raw_ostream & debugPassHeader(const mlir::Pass *pass, int width=80)
Write a boilerplate header for a pass to the debug stream.
Definition: Debug.cpp:31
llvm::raw_ostream & debugFooter(int width=80)
Write a boilerplate footer to the debug stream to indicate that a pass has ended.
Definition: Debug.cpp:35
int run(Type[Generator] generator=CppGenerator, cmdline_args=sys.argv)
Definition: codegen.py:121
The namespace of a CircuitOp, generally inhabited by modules.
Definition: Namespace.h:24