CIRCT 20.0.0git
Loading...
Searching...
No Matches
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
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
20namespace circt {
21namespace arc {
22#define GEN_PASS_DEF_INLINEARCS
23#include "circt/Dialect/Arc/ArcPasses.h.inc"
24} // namespace arc
25} // namespace circt
26
27using namespace circt;
28using namespace arc;
29
30namespace {
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.
35struct 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.
45class InlineArcsAnalysis {
46public:
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
76private:
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.
88class ArcInliner {
89public:
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
104private:
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.
113struct InlineArcsPass : public arc::impl::InlineArcsBase<InlineArcsPass> {
114 using InlineArcsBase::InlineArcsBase;
115
116 void runOnOperation() override;
117};
118
119} // namespace
120
121void 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
159void 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
168void ArcInliner::removeUnusedArcs(Region *unusedIn, ArrayRef<DefineOp> arcs) {
169 analysis.analyze({unusedIn}, arcs);
170 removeUnusedArcsInternal(arcs);
171}
172
173void 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(
192 cast<mlir::SymbolRefAttr>(
193 cast<mlir::CallOpInterface>(op).getCallableForCallee())
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 (!isa<SymbolRefAttr>(op.getCallableForCallee()))
211 return;
212
213 StringAttr arcName =
214 cast<SymbolRefAttr>(op.getCallableForCallee()).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
229bool InlineArcsAnalysis::shouldInline(mlir::CallOpInterface callOp) const {
230 // Arcs are always referenced via symbol.
231 if (!isa<SymbolRefAttr>(callOp.getCallableForCallee()))
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 = llvm::cast<SymbolRefAttr>(callOp.getCallableForCallee())
241 .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
260DefineOp InlineArcsAnalysis::getArc(mlir::CallOpInterface callOp) const {
261 StringAttr arcName =
262 cast<SymbolRefAttr>(callOp.getCallableForCallee()).getLeafReference();
263 return arcMap.at(arcName);
264}
265
266void 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
277size_t InlineArcsAnalysis::getNumArcUses(StringAttr arcName) const {
278 return usersPerArc.at(arcName);
279}
280
281void InlineArcsAnalysis::notifyInlinedCallInto(mlir::CallOpInterface callOp,
282 Region *region) {
283 StringAttr calledArcName =
284 cast<mlir::SymbolRefAttr>(callOp.getCallableForCallee())
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
310void 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
318void 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
359std::unique_ptr<Pass> arc::createInlineArcsPass() {
360 return std::make_unique<InlineArcsPass>();
361}
static Block * getBodyBlock(FModuleLike mod)
std::unique_ptr< mlir::Pass > createInlineArcsPass()
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.