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