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