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