CIRCT  19.0.0git
InlineArcs.cpp
Go to the documentation of this file.
1 //===- InlineArcs.cpp -----------------------------------------------------===//
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 
11 #include "circt/Dialect/HW/HWOps.h"
12 #include "mlir/Dialect/Func/IR/FuncOps.h"
13 #include "mlir/IR/IRMapping.h"
14 #include "mlir/Pass/Pass.h"
15 #include "mlir/Transforms/InliningUtils.h"
16 #include "llvm/Support/Debug.h"
17 
18 #define DEBUG_TYPE "arc-inline"
19 
20 namespace circt {
21 namespace arc {
22 #define GEN_PASS_DEF_INLINEARCS
23 #include "circt/Dialect/Arc/ArcPasses.h.inc"
24 } // namespace arc
25 } // namespace circt
26 
27 using namespace circt;
28 using namespace arc;
29 
30 namespace {
31 
32 /// Statistics collected during the pass. The fields should match the statistics
33 /// declared in the pass definition and are just bundled here to conveniently
34 /// pass around a reference to them.
35 struct InlineArcsStatistics {
36  size_t numInlinedArcs = 0;
37  size_t numRemovedArcs = 0;
38  size_t numTrivialArcs = 0;
39  size_t numSingleUseArcs = 0;
40 };
41 
42 /// An analysis that analyses the call graph and can be queried by the inliner
43 /// for inlining decisions on a per-call basis. The inliner should use the
44 /// notification calls to keep the analysis up-to-date.
45 class InlineArcsAnalysis {
46 public:
47  InlineArcsAnalysis(InlineArcsStatistics &statistics,
48  const InlineArcsOptions &options)
49  : statistics(statistics), options(options) {}
50 
51  /// Clears the current analysis state and recomputes it. The first argument
52  /// is a list of regions that can contain calls that should possibly be
53  /// inlined. The second argument is the list of arcs to which calls in the
54  /// regions of the first argument could refer to.
55  void analyze(ArrayRef<Region *> regionsWithCalls,
56  ArrayRef<DefineOp> arcDefinitions);
57 
58  /// Notify the analysis that a call was inlined such that it can adjust
59  /// future inlining decisions accordingly.
60  void notifyInlinedCallInto(mlir::CallOpInterface callOp, Region *region);
61 
62  /// Notify the analysis that an arc was removed.
63  void notifyArcRemoved(DefineOp arc);
64 
65  /// Query the analysis for a decision whether the given call should be
66  /// inlined, taking the pass options into account.
67  bool shouldInline(mlir::CallOpInterface callOp) const;
68 
69  /// Get the arc referred to by the call from the cache.
70  DefineOp getArc(mlir::CallOpInterface callOp) const;
71 
72  /// Get the number of calls within the regions passed as argument to the
73  /// initial `analyze` call that refer to the given arc.
74  size_t getNumArcUses(StringAttr arcName) const;
75 
76 private:
77  DenseMap<StringAttr, SmallVector<StringAttr>> callsInArcBody;
78  DenseMap<StringAttr, size_t> numOpsInArc;
79  DenseMap<StringAttr, size_t> usersPerArc;
80  DenseMap<StringAttr, DefineOp> arcMap;
81 
82  InlineArcsStatistics &statistics;
83  const InlineArcsOptions &options;
84 };
85 
86 /// The actual inliner performing the transformation. Has to be given an
87 /// analysis that it can query for inlining decisions.
88 class ArcInliner {
89 public:
90  explicit ArcInliner(InlineArcsAnalysis &analysis) : analysis(analysis) {}
91 
92  /// Inline calls in the given list of regions according to the analysis. The
93  /// second argument has to contain all arcs that calls could refer to.
94  /// Only pass true as the last argument if it is guarenteed that there cannot
95  /// be any calls to arcs in `arcDefinitions` outside of the passed regions.
96  void inlineCallsInRegion(ArrayRef<Region *> regionsWithCalls,
97  ArrayRef<DefineOp> arcDefinitions,
98  bool removeUnusedArcs = false);
99 
100  /// Remove arcs given by the second argument that that aren't used in the
101  /// given region.
102  void removeUnusedArcs(Region *unusedIn, ArrayRef<DefineOp> arcs);
103 
104 private:
105  void inlineCallsInRegion(Region *region);
106  void removeUnusedArcsInternal(ArrayRef<DefineOp> arcs);
107 
108  InlineArcsAnalysis &analysis;
109 };
110 
111 /// The inliner pass that sets up the analysis and inliner to operate on the
112 /// root builtin module.
113 struct InlineArcsPass : public arc::impl::InlineArcsBase<InlineArcsPass> {
114  using InlineArcsBase::InlineArcsBase;
115 
116  void runOnOperation() override;
117 };
118 
119 } // namespace
120 
121 void ArcInliner::inlineCallsInRegion(Region *region) {
122  for (auto &block : region->getBlocks()) {
123  for (auto iter = block.begin(); iter != block.end(); ++iter) {
124  Operation &op = *iter;
125  if (auto callOp = dyn_cast<mlir::CallOpInterface>(op);
126  callOp && analysis.shouldInline(callOp)) {
127  DefineOp arc = analysis.getArc(callOp);
128  auto args = arc.getBodyBlock().getArguments();
129 
130  IRMapping localMapping;
131  for (auto [arg, operand] : llvm::zip(args, callOp.getArgOperands()))
132  localMapping.map(arg, operand);
133 
134  OpBuilder builder(callOp);
135  builder.setInsertionPointAfter(callOp);
136  for (auto &op : arc.getBodyBlock().without_terminator())
137  builder.clone(op, localMapping);
138 
139  for (auto [returnVal, result] :
140  llvm::zip(arc.getBodyBlock().getTerminator()->getOperands(),
141  callOp->getResults()))
142  result.replaceAllUsesWith(localMapping.lookup(returnVal));
143 
144  analysis.notifyInlinedCallInto(callOp, region);
145  --iter;
146  callOp->erase();
147  continue;
148  }
149 
150  // Note: this is a recursive call where the max depth is the max number of
151  // nested regions. In Arc we don't have deep regions nestings thus this is
152  // fine for now.
153  for (Region &region : op.getRegions())
154  inlineCallsInRegion(&region);
155  }
156  }
157 }
158 
159 void ArcInliner::removeUnusedArcsInternal(ArrayRef<DefineOp> arcs) {
160  for (auto arc : llvm::make_early_inc_range(arcs)) {
161  if (analysis.getNumArcUses(arc.getSymNameAttr()) == 0) {
162  analysis.notifyArcRemoved(arc);
163  arc->erase();
164  }
165  }
166 }
167 
168 void ArcInliner::removeUnusedArcs(Region *unusedIn, ArrayRef<DefineOp> arcs) {
169  analysis.analyze({unusedIn}, arcs);
170  removeUnusedArcsInternal(arcs);
171 }
172 
173 void InlineArcsAnalysis::analyze(ArrayRef<Region *> regionsWithCalls,
174  ArrayRef<DefineOp> arcDefinitions) {
175  callsInArcBody.clear();
176  numOpsInArc.clear();
177  usersPerArc.clear();
178  arcMap.clear();
179 
180  // Count the number of non-trivial ops in the arc. If there are only a few
181  // (determined by the pass option), the arc will be inlined.
182  for (auto arc : arcDefinitions) {
183  auto arcName = arc.getSymNameAttr();
184  arcMap[arcName] = arc;
185  numOpsInArc[arcName] = 0;
186  arc->walk([&](Operation *op) {
187  if (!op->hasTrait<OpTrait::ConstantLike>() && !isa<OutputOp>(op))
188  ++numOpsInArc[arcName];
189  if (isa<mlir::CallOpInterface>(op))
190  // TODO: make safe
191  callsInArcBody[arcName].push_back(cast<mlir::CallOpInterface>(op)
192  .getCallableForCallee()
193  .get<mlir::SymbolRefAttr>()
194  .getLeafReference());
195  });
196  if (numOpsInArc[arcName] <= options.maxNonTrivialOpsInBody)
197  ++statistics.numTrivialArcs;
198 
199  LLVM_DEBUG(llvm::dbgs() << "Arc " << arc.getSymName() << " has "
200  << numOpsInArc[arcName] << " non-trivial ops\n");
201 
202  // Make sure an entry is present such that we don't have to lookup the
203  // symbol below but can just check if we already have an initialized entry
204  // in this map.
205  usersPerArc[arc.getSymNameAttr()] = 0;
206  }
207 
208  for (auto *regionWithCalls : regionsWithCalls) {
209  regionWithCalls->walk([&](mlir::CallOpInterface op) {
210  if (!op.getCallableForCallee().is<SymbolRefAttr>())
211  return;
212 
213  StringAttr arcName =
214  op.getCallableForCallee().get<SymbolRefAttr>().getLeafReference();
215  if (!usersPerArc.contains(arcName))
216  return;
217 
218  ++usersPerArc[arcName];
219  });
220  }
221 
222  // Provide the user with some statistics on how many arcs are only ever used
223  // once.
224  for (auto arc : arcDefinitions)
225  if (usersPerArc[arc.getSymNameAttr()] == 1)
226  ++statistics.numSingleUseArcs;
227 }
228 
229 bool InlineArcsAnalysis::shouldInline(mlir::CallOpInterface callOp) const {
230  // Arcs are always referenced via symbol.
231  if (!callOp.getCallableForCallee().is<SymbolRefAttr>())
232  return false;
233 
234  if (!callOp->getParentOfType<DefineOp>() && options.intoArcsOnly)
235  return false;
236 
237  // The `numOpsInArc` map contains an entry for all arcs considered. If the
238  // callee symbol is not present, it is either not an arc or an arc that we
239  // don't consider and thus don't want to inline.
240  StringAttr arcName =
241  callOp.getCallableForCallee().get<SymbolRefAttr>().getLeafReference();
242  if (!numOpsInArc.contains(arcName))
243  return false;
244 
245  // Query the inliner interface which will always be the one of the Arc dialect
246  // at this point. This is to make sure no StateOps with latency > 1 are
247  // are inlined.
248  auto *inlinerInterface =
249  dyn_cast<mlir::DialectInlinerInterface>(callOp->getDialect());
250  if (!inlinerInterface ||
251  !inlinerInterface->isLegalToInline(callOp, getArc(callOp), true))
252  return false;
253 
254  if (numOpsInArc.at(arcName) <= options.maxNonTrivialOpsInBody)
255  return true;
256 
257  return usersPerArc.at(arcName) == 1;
258 }
259 
260 DefineOp InlineArcsAnalysis::getArc(mlir::CallOpInterface callOp) const {
261  StringAttr arcName =
262  callOp.getCallableForCallee().get<SymbolRefAttr>().getLeafReference();
263  return arcMap.at(arcName);
264 }
265 
266 void ArcInliner::inlineCallsInRegion(ArrayRef<Region *> regionsWithCalls,
267  ArrayRef<DefineOp> arcDefinitions,
268  bool removeUnusedArcs) {
269  analysis.analyze(regionsWithCalls, arcDefinitions);
270  for (auto *regionWithCalls : regionsWithCalls)
271  inlineCallsInRegion(regionWithCalls);
272 
273  if (removeUnusedArcs)
274  removeUnusedArcsInternal(arcDefinitions);
275 }
276 
277 size_t InlineArcsAnalysis::getNumArcUses(StringAttr arcName) const {
278  return usersPerArc.at(arcName);
279 }
280 
281 void InlineArcsAnalysis::notifyInlinedCallInto(mlir::CallOpInterface callOp,
282  Region *region) {
283  StringAttr calledArcName = callOp.getCallableForCallee()
284  .get<mlir::SymbolRefAttr>()
285  .getLeafReference();
286  --usersPerArc[calledArcName];
287  ++statistics.numInlinedArcs;
288 
289  auto arc = dyn_cast<DefineOp>(region->getParentOp());
290  if (!arc)
291  return;
292 
293  StringAttr arcName = arc.getSymNameAttr();
294  // Minus one for the call op that gets removed
295  numOpsInArc[arcName] += numOpsInArc[calledArcName] - 1;
296  auto &calls = callsInArcBody[arcName];
297  auto *iter = llvm::find(calls, calledArcName);
298  if (iter != calls.end())
299  calls.erase(iter);
300 
301  for (auto calleeName : callsInArcBody[calledArcName]) {
302  if (!usersPerArc.contains(calleeName))
303  continue;
304 
305  ++usersPerArc[calleeName];
306  callsInArcBody[arcName].push_back(calleeName);
307  }
308 }
309 
310 void InlineArcsAnalysis::notifyArcRemoved(DefineOp arc) {
311  for (auto calleeName : callsInArcBody[arc.getSymNameAttr()])
312  --usersPerArc[calleeName];
313 
314  callsInArcBody[arc.getSymNameAttr()].clear();
315  ++statistics.numRemovedArcs;
316 }
317 
318 void InlineArcsPass::runOnOperation() {
319  // This is a big ugly, TableGen should add the options as a field of this
320  // struct to the pass to make passing them around easier.
321  InlineArcsOptions options;
322  options.intoArcsOnly = intoArcsOnly;
323  options.maxNonTrivialOpsInBody = maxNonTrivialOpsInBody;
324  InlineArcsStatistics statistics;
325  InlineArcsAnalysis analysis(statistics, options);
326  ArcInliner inliner(analysis);
327 
328  // The order of elements in `regions` determines which calls are inlined first
329  // (region by region). It is thus possible to pre-compute a ordering that
330  // leads to calls being inlined top-down in the call-graph, buttom-up, or
331  // anything inbetween. Currently, we just use the existing order in the IR.
332  SmallVector<DefineOp> arcDefinitions;
333  SmallVector<Region *> regions;
334  for (Operation &op : *getOperation().getBody()) {
335  if (auto arc = dyn_cast<DefineOp>(&op)) {
336  arcDefinitions.emplace_back(arc);
337  regions.push_back(&arc.getBody());
338  }
339  // TODO: instead of hardcoding these ops we might also be able to query the
340  // inliner interface for legality
341  if (isa<hw::HWModuleOp, mlir::func::FuncOp, ModelOp>(&op))
342  regions.push_back(&op.getRegion(0));
343  }
344 
345  // Inline the calls and remove all arcs that don't have any uses. It doesn't
346  // matter if all uses got inlined or if they already had no uses to begin
347  // with.
348  inliner.inlineCallsInRegion(regions, arcDefinitions,
349  /*removeUnusedArcs=*/true);
350 
351  // This is a bit ugly, but TableGen doesn't generate a container for all
352  // statistics to easily pass them around unfortunately.
353  numInlinedArcs = statistics.numInlinedArcs;
354  numRemovedArcs = statistics.numRemovedArcs;
355  numSingleUseArcs = statistics.numSingleUseArcs;
356  numTrivialArcs = statistics.numTrivialArcs;
357 }
358 
359 std::unique_ptr<Pass> arc::createInlineArcsPass() {
360  return std::make_unique<InlineArcsPass>();
361 }
Builder builder
std::unique_ptr< mlir::Pass > createInlineArcsPass()
Definition: InlineArcs.cpp:359
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
mlir::raw_indented_ostream & dbgs()
Definition: Utility.h:28