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