1//===- InlinerInterfaceImpl.cpp - Inlining for LLVM the dialect -----------===//
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// Logic for inlining LLVM functions and the definition of the
10// LLVMInliningInterface.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/LLVMIR/Transforms/InlinerInterfaceImpl.h"
15#include "mlir/Analysis/SliceWalk.h"
16#include "mlir/Dialect/LLVMIR/LLVMCallOps.h"
17#include "mlir/Dialect/LLVMIR/LLVMCodeGenIntrinsicOps.h"
18#include "mlir/Dialect/LLVMIR/LLVMConstantOps.h"
19#include "mlir/Dialect/LLVMIR/LLVMConversionOps.h"
20#include "mlir/Dialect/LLVMIR/LLVMGeneralIntrinsicOps.h"
21#include "mlir/Dialect/LLVMIR/LLVMInterfaces.h"
22#include "mlir/Dialect/LLVMIR/LLVMMemoryIntrinsicOps.h"
23#include "mlir/Dialect/LLVMIR/LLVMMemoryOps.h"
24#include "mlir/Dialect/LLVMIR/LLVMModuleOps.h"
25#include "mlir/Dialect/LLVMIR/LLVMTerminatorOps.h"
26#include "mlir/Dialect/LLVMIR/LLVMVarArgOps.h"
27#include "mlir/IR/Matchers.h"
28#include "mlir/Interfaces/DataLayoutInterfaces.h"
29#include "mlir/Interfaces/ViewLikeInterface.h"
30#include "mlir/Transforms/InliningUtils.h"
31#include "llvm/ADT/ScopeExit.h"
32#include "llvm/Support/Debug.h"
33
34#include "llvm/Support/DebugLog.h"
35
36#define DEBUG_TYPE "llvm-inliner"
37
38using namespace mlir;
39
40/// Check whether the given alloca is an input to a lifetime intrinsic,
41/// optionally passing through one or more casts on the way. This is not
42/// transitive through block arguments.
43static bool hasLifetimeMarkers(LLVM::AllocaOp allocaOp) {
44 SmallVector<Operation *> stack(allocaOp->getUsers().begin(),
45 allocaOp->getUsers().end());
46 while (!stack.empty()) {
47 Operation *op = stack.pop_back_val();
48 if (isa<LLVM::LifetimeStartOp, LLVM::LifetimeEndOp>(Val: op))
49 return true;
50 if (isa<LLVM::BitcastOp>(Val: op))
51 stack.append(in_start: op->getUsers().begin(), in_end: op->getUsers().end());
52 }
53 return false;
54}
55
56/// Handles alloca operations in the inlined blocks:
57/// - Moves all alloca operations with a constant size in the former entry block
58/// of the callee into the entry block of the caller, so they become part of
59/// the function prologue/epilogue during code generation.
60/// - Inserts lifetime intrinsics that limit the scope of inlined static allocas
61/// to the inlined blocks.
62/// - Inserts StackSave and StackRestore operations if dynamic allocas were
63/// inlined.
64static void
65handleInlinedAllocas(Operation *call,
66 iterator_range<Region::iterator> inlinedBlocks) {
67 // Locate the entry block of the closest callsite ancestor that has either the
68 // IsolatedFromAbove or AutomaticAllocationScope trait. In pure LLVM dialect
69 // programs, this is the LLVMFuncOp containing the call site. However, in
70 // mixed-dialect programs, the callsite might be nested in another operation
71 // that carries one of these traits. In such scenarios, this traversal stops
72 // at the closest ancestor with either trait, ensuring visibility post
73 // relocation and respecting allocation scopes.
74 Block *callerEntryBlock = nullptr;
75 Operation *currentOp = call;
76 while (Operation *parentOp = currentOp->getParentOp()) {
77 if (parentOp->mightHaveTrait<OpTrait::IsIsolatedFromAbove>() ||
78 parentOp->mightHaveTrait<OpTrait::AutomaticAllocationScope>()) {
79 callerEntryBlock = &currentOp->getParentRegion()->front();
80 break;
81 }
82 currentOp = parentOp;
83 }
84
85 // Avoid relocating the alloca operations if the call has been inlined into
86 // the entry block already, which is typically the encompassing
87 // LLVM function, or if the relevant entry block cannot be identified.
88 Block *calleeEntryBlock = &(*inlinedBlocks.begin());
89 if (!callerEntryBlock || callerEntryBlock == calleeEntryBlock)
90 return;
91
92 SmallVector<std::tuple<LLVM::AllocaOp, IntegerAttr, bool>> allocasToMove;
93 bool shouldInsertLifetimes = false;
94 bool hasDynamicAlloca = false;
95 // Conservatively only move static alloca operations that are part of the
96 // entry block and do not inspect nested regions, since they may execute
97 // conditionally or have other unknown semantics.
98 for (auto allocaOp : calleeEntryBlock->getOps<LLVM::AllocaOp>()) {
99 IntegerAttr arraySize;
100 if (!matchPattern(value: allocaOp.getArraySize(), pattern: m_Constant(bind_value: &arraySize))) {
101 hasDynamicAlloca = true;
102 continue;
103 }
104 bool shouldInsertLifetime =
105 arraySize.getValue() != 0 && !hasLifetimeMarkers(allocaOp);
106 shouldInsertLifetimes |= shouldInsertLifetime;
107 allocasToMove.emplace_back(Args&: allocaOp, Args&: arraySize, Args&: shouldInsertLifetime);
108 }
109 // Check the remaining inlined blocks for dynamic allocas as well.
110 for (Block &block : llvm::drop_begin(RangeOrContainer&: inlinedBlocks)) {
111 if (hasDynamicAlloca)
112 break;
113 hasDynamicAlloca =
114 llvm::any_of(Range: block.getOps<LLVM::AllocaOp>(), P: [](auto allocaOp) {
115 return !matchPattern(allocaOp.getArraySize(), m_Constant());
116 });
117 }
118 if (allocasToMove.empty() && !hasDynamicAlloca)
119 return;
120 OpBuilder builder(calleeEntryBlock, calleeEntryBlock->begin());
121 Value stackPtr;
122 if (hasDynamicAlloca) {
123 // This may result in multiple stacksave/stackrestore intrinsics in the same
124 // scope if some are already present in the body of the caller. This is not
125 // invalid IR, but LLVM cleans these up in InstCombineCalls.cpp, along with
126 // other cases where the stacksave/stackrestore is redundant.
127 stackPtr = LLVM::StackSaveOp::create(
128 builder, location: call->getLoc(),
129 res: LLVM::LLVMPointerType::get(context: call->getContext()));
130 }
131 builder.setInsertionPointToStart(callerEntryBlock);
132 for (auto &[allocaOp, arraySize, shouldInsertLifetime] : allocasToMove) {
133 auto newConstant =
134 LLVM::ConstantOp::create(builder, location: allocaOp->getLoc(),
135 res: allocaOp.getArraySize().getType(), value: arraySize);
136 // Insert a lifetime start intrinsic where the alloca was before moving it.
137 if (shouldInsertLifetime) {
138 OpBuilder::InsertionGuard insertionGuard(builder);
139 builder.setInsertionPoint(allocaOp);
140 LLVM::LifetimeStartOp::create(builder, location: allocaOp.getLoc(),
141 ptr: allocaOp.getResult());
142 }
143 allocaOp->moveAfter(existingOp: newConstant);
144 allocaOp.getArraySizeMutable().assign(value: newConstant.getResult());
145 }
146 if (!shouldInsertLifetimes && !hasDynamicAlloca)
147 return;
148 // Insert a lifetime end intrinsic before each return in the callee function.
149 for (Block &block : inlinedBlocks) {
150 if (!block.getTerminator()->hasTrait<OpTrait::ReturnLike>())
151 continue;
152 builder.setInsertionPoint(block.getTerminator());
153 if (hasDynamicAlloca)
154 LLVM::StackRestoreOp::create(builder, location: call->getLoc(), ptr: stackPtr);
155 for (auto &[allocaOp, arraySize, shouldInsertLifetime] : allocasToMove) {
156 if (shouldInsertLifetime)
157 LLVM::LifetimeEndOp::create(builder, location: allocaOp.getLoc(),
158 ptr: allocaOp.getResult());
159 }
160 }
161}
162
163/// Maps all alias scopes in the inlined operations to deep clones of the scopes
164/// and domain. This is required for code such as `foo(a, b); foo(a2, b2);` to
165/// not incorrectly return `noalias` for e.g. operations on `a` and `a2`.
166static void
167deepCloneAliasScopes(iterator_range<Region::iterator> inlinedBlocks) {
168 DenseMap<Attribute, Attribute> mapping;
169
170 // Register handles in the walker to create the deep clones.
171 // The walker ensures that an attribute is only ever walked once and does a
172 // post-order walk, ensuring the domain is visited prior to the scope.
173 AttrTypeWalker walker;
174
175 // Perform the deep clones while visiting. Builders create a distinct
176 // attribute to make sure that new instances are always created by the
177 // uniquer.
178 walker.addWalk(callback: [&](LLVM::AliasScopeDomainAttr domainAttr) {
179 mapping[domainAttr] = LLVM::AliasScopeDomainAttr::get(
180 context: domainAttr.getContext(), description: domainAttr.getDescription());
181 });
182
183 walker.addWalk(callback: [&](LLVM::AliasScopeAttr scopeAttr) {
184 mapping[scopeAttr] = LLVM::AliasScopeAttr::get(
185 domain: cast<LLVM::AliasScopeDomainAttr>(Val: mapping.lookup(Val: scopeAttr.getDomain())),
186 description: scopeAttr.getDescription());
187 });
188
189 // Map an array of scopes to an array of deep clones.
190 auto convertScopeList = [&](ArrayAttr arrayAttr) -> ArrayAttr {
191 if (!arrayAttr)
192 return nullptr;
193
194 // Create the deep clones if necessary.
195 walker.walk(element: arrayAttr);
196
197 return ArrayAttr::get(context: arrayAttr.getContext(),
198 value: llvm::map_to_vector(C&: arrayAttr, F: [&](Attribute attr) {
199 return mapping.lookup(Val: attr);
200 }));
201 };
202
203 for (Block &block : inlinedBlocks) {
204 block.walk(callback: [&](Operation *op) {
205 if (auto aliasInterface = dyn_cast<LLVM::AliasAnalysisOpInterface>(Val: op)) {
206 aliasInterface.setAliasScopes(
207 convertScopeList(aliasInterface.getAliasScopesOrNull()));
208 aliasInterface.setNoAliasScopes(
209 convertScopeList(aliasInterface.getNoAliasScopesOrNull()));
210 }
211
212 if (auto noAliasScope = dyn_cast<LLVM::NoAliasScopeDeclOp>(Val: op)) {
213 // Create the deep clones if necessary.
214 walker.walk(element: noAliasScope.getScopeAttr());
215
216 noAliasScope.setScopeAttr(cast<LLVM::AliasScopeAttr>(
217 Val: mapping.lookup(Val: noAliasScope.getScopeAttr())));
218 }
219 });
220 }
221}
222
223/// Creates a new ArrayAttr by concatenating `lhs` with `rhs`.
224/// Returns null if both parameters are null. If only one attribute is null,
225/// return the other.
226static ArrayAttr concatArrayAttr(ArrayAttr lhs, ArrayAttr rhs) {
227 if (!lhs)
228 return rhs;
229 if (!rhs)
230 return lhs;
231
232 SmallVector<Attribute> result;
233 llvm::append_range(C&: result, R&: lhs);
234 llvm::append_range(C&: result, R&: rhs);
235 return ArrayAttr::get(context: lhs.getContext(), value: result);
236}
237
238/// Attempts to return the set of all underlying pointer values that
239/// `pointerValue` is based on. This function traverses through select
240/// operations and block arguments.
241static FailureOr<SmallVector<Value>>
242getUnderlyingObjectSet(Value pointerValue) {
243 SmallVector<Value> result;
244 WalkContinuation walkResult = walkSlice(rootValues: pointerValue, walkCallback: [&](Value val) {
245 // Attempt to advance to the source of the underlying view-like operation.
246 // Examples of view-like operations include GEPOp and AddrSpaceCastOp.
247 if (auto viewOp = val.getDefiningOp<ViewLikeOpInterface>()) {
248 if (val == viewOp.getViewDest())
249 return WalkContinuation::advanceTo(nextValues: viewOp.getViewSource());
250 }
251
252 // Attempt to advance to control flow predecessors.
253 std::optional<SmallVector<Value>> controlFlowPredecessors =
254 getControlFlowPredecessors(value: val);
255 if (controlFlowPredecessors)
256 return WalkContinuation::advanceTo(nextValues: *controlFlowPredecessors);
257
258 // For all non-control flow results, consider `val` an underlying object.
259 if (isa<OpResult>(Val: val)) {
260 result.push_back(Elt: val);
261 return WalkContinuation::skip();
262 }
263
264 // If this place is reached, `val` is a block argument that is not
265 // understood. Therefore, we conservatively interrupt.
266 // Note: Dealing with function arguments is not necessary, as the slice
267 // would have to go through an SSACopyOp first.
268 return WalkContinuation::interrupt();
269 });
270
271 if (walkResult.wasInterrupted())
272 return failure();
273
274 return result;
275}
276
277/// Creates a new AliasScopeAttr for every noalias parameter and attaches it to
278/// the appropriate inlined memory operations in an attempt to preserve the
279/// original semantics of the parameter attribute.
280static void createNewAliasScopesFromNoAliasParameter(
281 Operation *call, iterator_range<Region::iterator> inlinedBlocks) {
282
283 // First, collect all ssa copy operations, which correspond to function
284 // parameters, and additionally store the noalias parameters. All parameters
285 // have been marked by the `handleArgument` implementation by using the
286 // `ssa.copy` intrinsic. Additionally, noalias parameters have an attached
287 // `noalias` attribute to the intrinsics. These intrinsics are only meant to
288 // be temporary and should therefore be deleted after we're done using them
289 // here.
290 SetVector<LLVM::SSACopyOp> ssaCopies;
291 SetVector<LLVM::SSACopyOp> noAliasParams;
292 for (Value argument : cast<LLVM::CallOp>(Val: call).getArgOperands()) {
293 for (auto ssaCopy :
294 llvm::make_isa_range<LLVM::SSACopyOp>(Range: argument.getUsers())) {
295 ssaCopies.insert(X: ssaCopy);
296
297 if (!ssaCopy->hasDiscardableAttr(name: LLVM::LLVMDialect::getNoAliasAttrName()))
298 continue;
299 noAliasParams.insert(X: ssaCopy);
300 }
301 }
302
303 // Scope exit block to make it impossible to forget to get rid of the
304 // intrinsics.
305 llvm::scope_exit exit([&] {
306 for (LLVM::SSACopyOp ssaCopyOp : ssaCopies) {
307 ssaCopyOp.replaceAllUsesWith(newValue: ssaCopyOp.getOperand());
308 ssaCopyOp->erase();
309 }
310 });
311
312 // If there were no noalias parameters, we have nothing to do here.
313 if (noAliasParams.empty())
314 return;
315
316 // Create a new domain for this specific inlining and a new scope for every
317 // noalias parameter.
318 auto functionDomain = LLVM::AliasScopeDomainAttr::get(
319 context: call->getContext(), description: cast<LLVM::CallOp>(Val: call).getCalleeAttr().getAttr());
320 DenseMap<Value, LLVM::AliasScopeAttr> pointerScopes;
321 for (LLVM::SSACopyOp copyOp : noAliasParams) {
322 auto scope = LLVM::AliasScopeAttr::get(domain: functionDomain);
323 pointerScopes[copyOp] = scope;
324
325 auto builder = OpBuilder(call);
326 LLVM::NoAliasScopeDeclOp::create(builder, location: call->getLoc(), scope);
327 }
328
329 // Go through every instruction and attempt to find which noalias parameters
330 // it is definitely based on and definitely not based on.
331 for (Block &inlinedBlock : inlinedBlocks) {
332 inlinedBlock.walk(callback: [&](LLVM::AliasAnalysisOpInterface aliasInterface) {
333 // Collect the pointer arguments affected by the alias scopes.
334 SmallVector<Value> pointerArgs = aliasInterface.getAccessedOperands();
335
336 // Find the set of underlying pointers that this pointer is based on.
337 SmallPtrSet<Value, 4> basedOnPointers;
338 for (Value pointer : pointerArgs) {
339 FailureOr<SmallVector<Value>> underlyingObjectSet =
340 getUnderlyingObjectSet(pointerValue: pointer);
341 if (failed(Result: underlyingObjectSet))
342 return;
343 llvm::copy(Range&: *underlyingObjectSet,
344 Out: std::inserter(x&: basedOnPointers, i: basedOnPointers.begin()));
345 }
346
347 bool aliasesOtherKnownObject = false;
348 // Go through the based on pointers and check that they are either:
349 // * Constants that can be ignored (undef, poison, null pointer).
350 // * Based on a pointer parameter.
351 // * Other pointers that we know can't alias with our noalias parameter.
352 //
353 // Any other value might be a pointer based on any noalias parameter that
354 // hasn't been identified. In that case conservatively don't add any
355 // scopes to this operation indicating either aliasing or not aliasing
356 // with any parameter.
357 if (llvm::any_of(Range&: basedOnPointers, P: [&](Value object) {
358 if (matchPattern(value: object, pattern: m_Constant()))
359 return false;
360
361 if (auto ssaCopy = object.getDefiningOp<LLVM::SSACopyOp>()) {
362 // If that value is based on a noalias parameter, it is guaranteed
363 // to not alias with any other object.
364 aliasesOtherKnownObject |= !noAliasParams.contains(key: ssaCopy);
365 return false;
366 }
367
368 if (isa_and_nonnull<LLVM::AllocaOp, LLVM::AddressOfOp>(
369 Val: object.getDefiningOp())) {
370 aliasesOtherKnownObject = true;
371 return false;
372 }
373 return true;
374 }))
375 return;
376
377 // Add all noalias parameter scopes to the noalias scope list that we are
378 // not based on.
379 SmallVector<Attribute> noAliasScopes;
380 for (LLVM::SSACopyOp noAlias : noAliasParams) {
381 if (basedOnPointers.contains(Ptr: noAlias))
382 continue;
383
384 noAliasScopes.push_back(Elt: pointerScopes[noAlias]);
385 }
386
387 if (!noAliasScopes.empty())
388 aliasInterface.setNoAliasScopes(
389 concatArrayAttr(lhs: aliasInterface.getNoAliasScopesOrNull(),
390 rhs: ArrayAttr::get(context: call->getContext(), value: noAliasScopes)));
391
392 // Don't add alias scopes to call operations or operations that might
393 // operate on pointers not based on any noalias parameter.
394 // Since we add all scopes to an operation's noalias list that it
395 // definitely doesn't alias, we mustn't do the same for the alias.scope
396 // list if other objects are involved.
397 //
398 // Consider the following case:
399 // %0 = llvm.alloca
400 // %1 = select %magic, %0, %noalias_param
401 // store 5, %1 (1) noalias=[scope(...)]
402 // ...
403 // store 3, %0 (2) noalias=[scope(noalias_param), scope(...)]
404 //
405 // We can add the scopes of any noalias parameters that aren't
406 // noalias_param's scope to (1) and add all of them to (2). We mustn't add
407 // the scope of noalias_param to the alias.scope list of (1) since
408 // that would mean (2) cannot alias with (1) which is wrong since both may
409 // store to %0.
410 //
411 // In conclusion, only add scopes to the alias.scope list if all pointers
412 // have a corresponding scope.
413 // Call operations are included in this list since we do not know whether
414 // the callee accesses any memory besides the ones passed as its
415 // arguments.
416 if (aliasesOtherKnownObject ||
417 isa<LLVM::CallOp>(Val: aliasInterface.getOperation()))
418 return;
419
420 SmallVector<Attribute> aliasScopes;
421 for (LLVM::SSACopyOp noAlias : noAliasParams)
422 if (basedOnPointers.contains(Ptr: noAlias))
423 aliasScopes.push_back(Elt: pointerScopes[noAlias]);
424
425 if (!aliasScopes.empty())
426 aliasInterface.setAliasScopes(
427 concatArrayAttr(lhs: aliasInterface.getAliasScopesOrNull(),
428 rhs: ArrayAttr::get(context: call->getContext(), value: aliasScopes)));
429 });
430 }
431}
432
433/// Appends any alias scopes of the call operation to any inlined memory
434/// operation.
435static void
436appendCallOpAliasScopes(Operation *call,
437 iterator_range<Region::iterator> inlinedBlocks) {
438 auto callAliasInterface = dyn_cast<LLVM::AliasAnalysisOpInterface>(Val: call);
439 if (!callAliasInterface)
440 return;
441
442 ArrayAttr aliasScopes = callAliasInterface.getAliasScopesOrNull();
443 ArrayAttr noAliasScopes = callAliasInterface.getNoAliasScopesOrNull();
444 // If the call has neither alias scopes or noalias scopes we have nothing to
445 // do here.
446 if (!aliasScopes && !noAliasScopes)
447 return;
448
449 // Simply append the call op's alias and noalias scopes to any operation
450 // implementing AliasAnalysisOpInterface.
451 for (Block &block : inlinedBlocks) {
452 block.walk(callback: [&](LLVM::AliasAnalysisOpInterface aliasInterface) {
453 if (aliasScopes)
454 aliasInterface.setAliasScopes(concatArrayAttr(
455 lhs: aliasInterface.getAliasScopesOrNull(), rhs: aliasScopes));
456
457 if (noAliasScopes)
458 aliasInterface.setNoAliasScopes(concatArrayAttr(
459 lhs: aliasInterface.getNoAliasScopesOrNull(), rhs: noAliasScopes));
460 });
461 }
462}
463
464/// Handles all interactions with alias scopes during inlining.
465static void handleAliasScopes(Operation *call,
466 iterator_range<Region::iterator> inlinedBlocks) {
467 deepCloneAliasScopes(inlinedBlocks);
468 createNewAliasScopesFromNoAliasParameter(call, inlinedBlocks);
469 appendCallOpAliasScopes(call, inlinedBlocks);
470}
471
472/// Appends any access groups of the call operation to any inlined memory
473/// operation.
474static void handleAccessGroups(Operation *call,
475 iterator_range<Region::iterator> inlinedBlocks) {
476 auto callAccessGroupInterface = dyn_cast<LLVM::AccessGroupOpInterface>(Val: call);
477 if (!callAccessGroupInterface)
478 return;
479
480 auto accessGroups = callAccessGroupInterface.getAccessGroupsOrNull();
481 if (!accessGroups)
482 return;
483
484 // Simply append the call op's access groups to any operation implementing
485 // AccessGroupOpInterface.
486 for (Block &block : inlinedBlocks)
487 for (auto accessGroupOpInterface :
488 block.getOps<LLVM::AccessGroupOpInterface>())
489 accessGroupOpInterface.setAccessGroups(concatArrayAttr(
490 lhs: accessGroupOpInterface.getAccessGroupsOrNull(), rhs: accessGroups));
491}
492
493/// Whether the two call stacks agree up to the shorter length, matching
494/// LLVM's haveCommonPrefix: a MemProf context matches the new inlined
495/// callsite context when they share a prefix, even if the callsite stack
496/// is longer than the MemProf stack.
497static bool haveCommonPrefix(ArrayRef<int64_t> mibStack,
498 ArrayRef<int64_t> callsiteStack) {
499 size_t len = std::min(a: mibStack.size(), b: callsiteStack.size());
500 return mibStack.take_front(N: len) == callsiteStack.take_front(N: len);
501}
502
503/// Updates MemProf metadata on calls inlined into `call`, matching LLVM's
504/// propagateMemProfMetadata. Each cloned call's `llvm.callsite` stack is
505/// concatenated with the inlined callsite's stack, and its `llvm.memprof`
506/// MIBs are filtered to the ones whose call stack shares a prefix with the
507/// new callsite stack; the kept MIBs are unchanged. If the inlined call
508/// has no callsite metadata, or no MIB matches, both attributes are removed
509/// from the cloned call. A cloned call with `llvm.memprof` but no
510/// `llvm.callsite` cannot have its context extended, so its `llvm.memprof`
511/// attribute is removed.
512///
513/// Known gap: unlike LLVM, which rebuilds a filtered subset through a
514/// call-stack trie (trimming contexts, and replacing the metadata with a
515/// function attribute when a single allocation type is left), this keeps
516/// the raw subset. There is no MLIR way to carry that function attribute.
517static void
518handleMemProfMetadata(Operation *call,
519 iterator_range<Region::iterator> inlinedBlocks) {
520 MLIRContext *context = call->getContext();
521 StringRef callsiteName = LLVM::LLVMDialect::getCallsiteAttrName();
522 StringRef memprofName = LLVM::LLVMDialect::getMemProfAttrName();
523 DenseI64ArrayAttr inlinedCallsite =
524 call->getDiscardableAttrOfType<DenseI64ArrayAttr>(name: callsiteName);
525 ArrayRef<int64_t> inlinedStack =
526 inlinedCallsite ? inlinedCallsite.asArrayRef() : ArrayRef<int64_t>{};
527
528 // Any op carrying these attributes lowers to a call, so act on every
529 // carrier, including calls nested in region ops and intrinsic calls that
530 // are not CallOpInterface, matching the set translation can produce.
531 for (Block &block : inlinedBlocks) {
532 block.walk(callback: [&](Operation *op) {
533 DenseI64ArrayAttr origCallsite =
534 op->getDiscardableAttrOfType<DenseI64ArrayAttr>(name: callsiteName);
535 ArrayAttr memprof = op->getDiscardableAttrOfType<ArrayAttr>(name: memprofName);
536 if (!origCallsite && !memprof)
537 return;
538 if (!origCallsite) {
539 // No callsite context to extend from: drop the memprof attribute
540 // when the clone carries one. LLVM asserts this case cannot happen;
541 // dropping is the conservative equivalent.
542 op->removeDiscardableAttr(name: memprofName);
543 return;
544 }
545 if (inlinedStack.empty()) {
546 // The inlined call carries no callsite context: the cloned call is
547 // not part of any profiled context.
548 op->removeDiscardableAttr(name: memprofName);
549 op->removeDiscardableAttr(name: callsiteName);
550 return;
551 }
552 SmallVector<int64_t> newStack(origCallsite.asArrayRef());
553 newStack.append(in_start: inlinedStack.begin(), in_end: inlinedStack.end());
554 op->setDiscardableAttr(name: callsiteName,
555 value: DenseI64ArrayAttr::get(context, content: newStack));
556 if (!memprof)
557 return;
558 SmallVector<Attribute> keptMIBs;
559 bool malformed = false;
560 for (Attribute mibAttr : memprof) {
561 auto mib = dyn_cast<LLVM::MemProfMIBAttr>(Val&: mibAttr);
562 if (!mib) {
563 malformed = true;
564 break;
565 }
566 if (haveCommonPrefix(mibStack: mib.getCallStack().asArrayRef(), callsiteStack: newStack))
567 keptMIBs.push_back(Elt: mibAttr);
568 }
569 if (malformed || keptMIBs.empty()) {
570 op->removeDiscardableAttr(name: memprofName);
571 op->removeDiscardableAttr(name: callsiteName);
572 } else if (keptMIBs.size() != memprof.size()) {
573 op->setDiscardableAttr(name: memprofName, value: ArrayAttr::get(context, value: keptMIBs));
574 }
575 });
576 }
577}
578
579/// Updates locations inside loop annotations to reflect that they were inlined.
580static void
581handleLoopAnnotations(Operation *call,
582 iterator_range<Region::iterator> inlinedBlocks) {
583 // Attempt to extract a DISubprogram from the callee.
584 auto func = call->getParentOfType<FunctionOpInterface>();
585 if (!func)
586 return;
587 LocationAttr funcLoc = func->getLoc();
588 auto fusedLoc = dyn_cast_if_present<FusedLoc>(Val&: funcLoc);
589 if (!fusedLoc)
590 return;
591 auto scope =
592 dyn_cast_if_present<LLVM::DISubprogramAttr>(Val: fusedLoc.getMetadata());
593 if (!scope)
594 return;
595
596 // Helper to build a new fused location that reflects the inlining of the loop
597 // annotation.
598 auto updateLoc = [&](FusedLoc loc) -> FusedLoc {
599 if (!loc)
600 return {};
601 Location callSiteLoc = CallSiteLoc::get(callee: loc, caller: call->getLoc());
602 return FusedLoc::get(context: loc.getContext(), locations: callSiteLoc, metadata: scope);
603 };
604
605 AttrTypeReplacer replacer;
606 replacer.addReplacement(callback: [&](LLVM::LoopAnnotationAttr loopAnnotation)
607 -> std::pair<Attribute, WalkResult> {
608 FusedLoc newStartLoc = updateLoc(loopAnnotation.getStartLoc());
609 FusedLoc newEndLoc = updateLoc(loopAnnotation.getEndLoc());
610 if (!newStartLoc && !newEndLoc)
611 return {loopAnnotation, WalkResult::advance()};
612 auto newLoopAnnotation = LLVM::LoopAnnotationAttr::get(
613 context: loopAnnotation.getContext(), id: loopAnnotation.getId(),
614 disableNonforced: loopAnnotation.getDisableNonforced(), vectorize: loopAnnotation.getVectorize(),
615 interleave: loopAnnotation.getInterleave(), unroll: loopAnnotation.getUnroll(),
616 unrollAndJam: loopAnnotation.getUnrollAndJam(), licm: loopAnnotation.getLicm(),
617 distribute: loopAnnotation.getDistribute(), pipeline: loopAnnotation.getPipeline(),
618 peeled: loopAnnotation.getPeeled(), unswitch: loopAnnotation.getUnswitch(),
619 mustProgress: loopAnnotation.getMustProgress(), isVectorized: loopAnnotation.getIsVectorized(),
620 align: loopAnnotation.getAlign(), startLoc: newStartLoc, endLoc: newEndLoc,
621 parallelAccesses: loopAnnotation.getParallelAccesses());
622 // Needs to advance, as loop annotations can be nested.
623 return {newLoopAnnotation, WalkResult::advance()};
624 });
625
626 for (Block &block : inlinedBlocks)
627 for (Operation &op : block)
628 replacer.recursivelyReplaceElementsIn(op: &op);
629}
630
631/// If `requestedAlignment` is higher than the alignment specified on `alloca`,
632/// realigns `alloca` if this does not exceed the natural stack alignment.
633/// Returns the post-alignment of `alloca`, whether it was realigned or not.
634static uint64_t tryToEnforceAllocaAlignment(LLVM::AllocaOp alloca,
635 uint64_t requestedAlignment,
636 DataLayout const &dataLayout) {
637 uint64_t allocaAlignment = alloca.getAlignment().value_or(u: 1);
638 if (requestedAlignment <= allocaAlignment)
639 // No realignment necessary.
640 return allocaAlignment;
641 uint64_t naturalStackAlignmentBits = dataLayout.getStackAlignment();
642 // If the natural stack alignment is not specified, the data layout returns
643 // zero. Optimistically allow realignment in this case.
644 if (naturalStackAlignmentBits == 0 ||
645 // If the requested alignment exceeds the natural stack alignment, this
646 // will trigger a dynamic stack realignment, so we prefer to copy...
647 8 * requestedAlignment <= naturalStackAlignmentBits ||
648 // ...unless the alloca already triggers dynamic stack realignment. Then
649 // we might as well further increase the alignment to avoid a copy.
650 8 * allocaAlignment > naturalStackAlignmentBits) {
651 alloca.setAlignment(requestedAlignment);
652 allocaAlignment = requestedAlignment;
653 }
654 return allocaAlignment;
655}
656
657/// Tries to find and return the alignment of the pointer `value` by looking for
658/// an alignment attribute on the defining allocation op or function argument.
659/// If the found alignment is lower than `requestedAlignment`, tries to realign
660/// the pointer, then returns the resulting post-alignment, regardless of
661/// whether it was realigned or not. If no existing alignment attribute is
662/// found, returns 1 (i.e., assume that no alignment is guaranteed).
663static uint64_t tryToEnforceAlignment(Value value, uint64_t requestedAlignment,
664 DataLayout const &dataLayout) {
665 if (Operation *definingOp = value.getDefiningOp()) {
666 if (auto alloca = dyn_cast<LLVM::AllocaOp>(Val: definingOp))
667 return tryToEnforceAllocaAlignment(alloca, requestedAlignment,
668 dataLayout);
669 if (auto addressOf = dyn_cast<LLVM::AddressOfOp>(Val: definingOp))
670 if (auto global = SymbolTable::lookupNearestSymbolFrom<LLVM::GlobalOp>(
671 from: definingOp, symbol: addressOf.getGlobalNameAttr()))
672 return global.getAlignment().value_or(u: 1);
673 // We don't currently handle this operation; assume no alignment.
674 return 1;
675 }
676 // Since there is no defining op, this is a block argument. Probably this
677 // comes directly from a function argument, so check that this is the case.
678 Operation *parentOp = value.getParentBlock()->getParentOp();
679 if (auto func = dyn_cast<LLVM::LLVMFuncOp>(Val: parentOp)) {
680 // Use the alignment attribute set for this argument in the parent function
681 // if it has been set.
682 auto blockArg = llvm::cast<BlockArgument>(Val&: value);
683 if (Attribute alignAttr = func.getArgAttr(
684 index: blockArg.getArgNumber(), name: LLVM::LLVMDialect::getAlignAttrName()))
685 return cast<IntegerAttr>(Val&: alignAttr).getValue().getLimitedValue();
686 }
687 // We didn't find anything useful; assume no alignment.
688 return 1;
689}
690
691/// Introduces a new alloca and copies the memory pointed to by `argument` to
692/// the address of the new alloca, then returns the value of the new alloca.
693static Value handleByValArgumentInit(OpBuilder &builder, Location loc,
694 Value argument, Type elementType,
695 uint64_t elementTypeSize,
696 uint64_t targetAlignment) {
697 // Allocate the new value on the stack.
698 Value allocaOp;
699 {
700 // Walk up from the call site to find the innermost AutomaticAllocationScope
701 // (e.g. an llvm.func or scf.forall). Placing the alloca at the entry block
702 // of that scope keeps it inside parallel regions rather than hoisting it
703 // out, while still landing at the function entry block for the common
704 // non-parallel case.
705 OpBuilder::InsertionGuard insertionGuard(builder);
706 Operation *scope = builder.getInsertionBlock()->getParentOp();
707 if (!scope->mightHaveTrait<OpTrait::AutomaticAllocationScope>())
708 scope = scope->getParentWithTrait<OpTrait::AutomaticAllocationScope>();
709 Block *entryBlock = &scope->getRegion(index: 0).front();
710 builder.setInsertionPointToStart(entryBlock);
711 Value one = LLVM::ConstantOp::create(builder, location: loc, res: builder.getI64Type(),
712 value: builder.getI64IntegerAttr(value: 1));
713 allocaOp = LLVM::AllocaOp::create(builder, location: loc, resultType: argument.getType(),
714 elementType, arraySize: one, alignment: targetAlignment);
715 }
716 // Copy the pointee to the newly allocated value.
717 Value copySize =
718 LLVM::ConstantOp::create(builder, location: loc, res: builder.getI64Type(),
719 value: builder.getI64IntegerAttr(value: elementTypeSize));
720 // Preserve the alignment of the destination (alloca) in the memcpy's
721 // arg_attrs.
722 NamedAttribute dstAlignAttr =
723 builder.getNamedAttr(name: LLVM::LLVMDialect::getAlignAttrName(),
724 val: builder.getI64IntegerAttr(value: targetAlignment));
725 ArrayAttr argAttrs =
726 builder.getArrayAttr(value: {builder.getDictionaryAttr(value: {dstAlignAttr})});
727 LLVM::MemcpyOp::create(builder, location: loc, dst: allocaOp, src: argument, len: copySize,
728 /*isVolatile=*/false,
729 /*tbaa_struct=*/nullptr,
730 /*access_groups=*/nullptr, /*alias_scopes=*/nullptr,
731 /*noalias_scopes=*/nullptr, /*tbaa=*/nullptr, arg_attrs: argAttrs,
732 /*res_attrs=*/nullptr);
733 return allocaOp;
734}
735
736/// Handles a function argument marked with the byval attribute by introducing a
737/// memcpy or realigning the defining operation, if required either due to the
738/// pointee being writeable in the callee, and/or due to an alignment mismatch.
739/// `requestedAlignment` specifies the alignment set in the "align" argument
740/// attribute (or 1 if no align attribute was set).
741static Value handleByValArgument(OpBuilder &builder, Operation *callable,
742 Value argument, Type elementType,
743 uint64_t requestedAlignment) {
744 auto func = cast<LLVM::LLVMFuncOp>(Val: callable);
745 LLVM::MemoryEffectsAttr memoryEffects = func.getMemoryEffectsAttr();
746 // If there is no memory effects attribute, assume that the function is
747 // not read-only.
748 bool isReadOnly = memoryEffects &&
749 memoryEffects.getArgMem() != LLVM::ModRefInfo::ModRef &&
750 memoryEffects.getArgMem() != LLVM::ModRefInfo::Mod;
751 // Check if there's an alignment mismatch requiring us to copy.
752 DataLayout dataLayout = DataLayout::closest(op: callable);
753 uint64_t minimumAlignment = dataLayout.getTypeABIAlignment(t: elementType);
754 if (isReadOnly) {
755 if (requestedAlignment <= minimumAlignment)
756 return argument;
757 uint64_t currentAlignment =
758 tryToEnforceAlignment(value: argument, requestedAlignment, dataLayout);
759 if (currentAlignment >= requestedAlignment)
760 return argument;
761 }
762 uint64_t targetAlignment = std::max(a: requestedAlignment, b: minimumAlignment);
763 return handleByValArgumentInit(
764 builder, loc: argument.getLoc(), argument, elementType,
765 elementTypeSize: dataLayout.getTypeSize(t: elementType), targetAlignment);
766}
767
768namespace {
769struct LLVMInlinerInterface : public DialectInlinerInterface {
770 using DialectInlinerInterface::DialectInlinerInterface;
771
772 LLVMInlinerInterface(Dialect *dialect)
773 : DialectInlinerInterface(dialect),
774 // Cache set of StringAttrs for fast lookup in `isLegalToInline`.
775 disallowedFunctionAttrs({
776 StringAttr::get(context: dialect->getContext(), bytes: "noduplicate"),
777 StringAttr::get(context: dialect->getContext(), bytes: "presplitcoroutine"),
778 StringAttr::get(context: dialect->getContext(), bytes: "returns_twice"),
779 StringAttr::get(context: dialect->getContext(), bytes: "strictfp"),
780 }) {}
781
782 bool isLegalToInline(Operation *call, Operation *callable,
783 bool wouldBeCloned) const final {
784 auto callOp = dyn_cast<LLVM::CallOp>(Val: call);
785 if (!callOp) {
786 LDBG() << "Cannot inline: call is not an '"
787 << LLVM::CallOp::getOperationName() << "' op";
788 return false;
789 }
790 if (callOp.getNoInline()) {
791 LDBG() << "Cannot inline: call is marked no_inline";
792 return false;
793 }
794 auto funcOp = dyn_cast<LLVM::LLVMFuncOp>(Val: callable);
795 if (!funcOp) {
796 LDBG() << "Cannot inline: callable is not an '"
797 << LLVM::LLVMFuncOp::getOperationName() << "' op";
798 return false;
799 }
800 if (funcOp.isNoInline()) {
801 LDBG() << "Cannot inline: function is marked no_inline";
802 return false;
803 }
804 if (funcOp.isVarArg()) {
805 LDBG() << "Cannot inline: callable is variadic";
806 return false;
807 }
808 // TODO: Generate aliasing metadata from noalias result attributes.
809 if (auto attrs = funcOp.getArgAttrs()) {
810 for (DictionaryAttr attrDict : attrs->getAsRange<DictionaryAttr>()) {
811 if (attrDict.contains(name: LLVM::LLVMDialect::getInAllocaAttrName())) {
812 LDBG() << "Cannot inline " << funcOp.getSymName()
813 << ": inalloca arguments not supported";
814 return false;
815 }
816 }
817 }
818 // TODO: Handle exceptions.
819 if (funcOp.getPersonality()) {
820 LDBG() << "Cannot inline " << funcOp.getSymName()
821 << ": unhandled function personality";
822 return false;
823 }
824 if (funcOp.getPassthrough()) {
825 // TODO: Used attributes should not be passthrough.
826 if (llvm::any_of(Range: *funcOp.getPassthrough(), P: [&](Attribute attr) {
827 auto stringAttr = dyn_cast<StringAttr>(Val&: attr);
828 if (!stringAttr)
829 return false;
830 if (disallowedFunctionAttrs.contains(V: stringAttr)) {
831 LDBG() << "Cannot inline " << funcOp.getSymName()
832 << ": found disallowed function attribute " << stringAttr;
833 return true;
834 }
835 return false;
836 }))
837 return false;
838 }
839 // Refuse to inline if any block in the callee ends with an op that does
840 // not have the terminator trait. The MLIR verifier conservatively accepts
841 // unregistered ops as potential terminators (via mightHaveTrait), but
842 // handleTerminator uses cast<LLVM::ReturnOp> in the single-block path and
843 // would crash on such ops. Registered terminators from other dialects
844 // (e.g. cf.br) are safe: the multi-block path uses dyn_cast and skips
845 // non-llvm.return ops gracefully.
846 for (Block &block : funcOp.getBody()) {
847 if (!block.empty() && !block.back().hasTrait<OpTrait::IsTerminator>()) {
848 LDBG() << "Cannot inline " << funcOp.getSymName()
849 << ": block ends with non-terminator op";
850 return false;
851 }
852 }
853 return true;
854 }
855
856 bool isLegalToInline(Region *, Region *, bool, IRMapping &) const final {
857 return true;
858 }
859
860 bool isLegalToInline(Operation *op, Region *, bool, IRMapping &) const final {
861 // The inliner cannot handle variadic function arguments and blocktag
862 // operations prevent inlining since they the blockaddress operations
863 // reference them via the callee symbol.
864 return !(isa<LLVM::VaStartOp>(Val: op) || isa<LLVM::BlockTagOp>(Val: op));
865 }
866
867 /// Handle the given inlined return by replacing it with a branch. This
868 /// overload is called when the inlined region has more than one block.
869 void handleTerminator(Operation *op, Block *newDest) const final {
870 // Only return needs to be handled here.
871 auto returnOp = dyn_cast<LLVM::ReturnOp>(Val: op);
872 if (!returnOp)
873 return;
874
875 // Replace the return with a branch to the dest.
876 OpBuilder builder(op);
877 LLVM::BrOp::create(builder, location: op->getLoc(), operands: returnOp.getOperands(), dest: newDest);
878 op->erase();
879 }
880
881 bool allowSingleBlockOptimization(Block *inlinedBlock) const final {
882 return !isa<LLVM::UnreachableOp>(Val: inlinedBlock->getTerminator());
883 }
884
885 /// Handle the given inlined return by replacing the uses of the call with the
886 /// operands of the return. This overload is called when the inlined region
887 /// only contains one block.
888 void handleTerminator(Operation *op, ValueRange valuesToRepl) const final {
889 // Return will be the only terminator present.
890 auto returnOp = cast<LLVM::ReturnOp>(Val: op);
891
892 // Replace the values directly with the return operands.
893 assert(returnOp.getNumOperands() == valuesToRepl.size());
894 for (auto [dst, src] : llvm::zip(t&: valuesToRepl, u: returnOp.getOperands()))
895 dst.replaceAllUsesWith(newValue: src);
896 }
897
898 Value handleArgument(OpBuilder &builder, Operation *call, Operation *callable,
899 Value argument,
900 DictionaryAttr argumentAttrs) const final {
901 if (std::optional<NamedAttribute> attr =
902 argumentAttrs.getNamed(name: LLVM::LLVMDialect::getByValAttrName())) {
903 Type elementType = cast<TypeAttr>(Val: attr->getValue()).getValue();
904 uint64_t requestedAlignment = 1;
905 if (std::optional<NamedAttribute> alignAttr =
906 argumentAttrs.getNamed(name: LLVM::LLVMDialect::getAlignAttrName())) {
907 requestedAlignment = cast<IntegerAttr>(Val: alignAttr->getValue())
908 .getValue()
909 .getLimitedValue();
910 }
911 return handleByValArgument(builder, callable, argument, elementType,
912 requestedAlignment);
913 }
914
915 // This code is essentially a workaround for deficiencies in the inliner
916 // interface: We need to transform operations *after* inlined based on the
917 // argument attributes of the parameters *before* inlining. This method runs
918 // prior to actual inlining and thus cannot transform the post-inlining
919 // code, while `processInlinedCallBlocks` does not have access to
920 // pre-inlining function arguments. Additionally, it is required to
921 // distinguish which parameter an SSA value originally came from. As a
922 // workaround until this is changed: Create an ssa.copy intrinsic with the
923 // noalias attribute (when it was present before) that can easily be found,
924 // and is extremely unlikely to exist in the code prior to inlining, using
925 // this to communicate between this method and `processInlinedCallBlocks`.
926 // TODO: Fix this by refactoring the inliner interface.
927 auto copyOp = LLVM::SSACopyOp::create(builder, location: call->getLoc(), operand: argument);
928 if (argumentAttrs.contains(name: LLVM::LLVMDialect::getNoAliasAttrName()))
929 copyOp->setDiscardableAttr(
930 name: builder.getStringAttr(bytes: LLVM::LLVMDialect::getNoAliasAttrName()),
931 value: builder.getUnitAttr());
932 return copyOp;
933 }
934
935 void processInlinedCallBlocks(
936 Operation *call,
937 iterator_range<Region::iterator> inlinedBlocks) const override {
938 handleInlinedAllocas(call, inlinedBlocks);
939 handleAliasScopes(call, inlinedBlocks);
940 handleAccessGroups(call, inlinedBlocks);
941 handleMemProfMetadata(call, inlinedBlocks);
942 handleLoopAnnotations(call, inlinedBlocks);
943 }
944
945 // Keeping this (immutable) state on the interface allows us to look up
946 // StringAttrs instead of looking up strings, since StringAttrs are bound to
947 // the current context and thus cannot be initialized as static fields.
948 const DenseSet<StringAttr> disallowedFunctionAttrs;
949};
950
951} // end anonymous namespace
952
953void mlir::LLVM::registerInlinerInterface(DialectRegistry &registry) {
954 registry.addExtension(extensionFn: +[](MLIRContext *ctx, LLVM::LLVMDialect *dialect) {
955 dialect->addInterfaces<LLVMInlinerInterface>();
956 });
957}
958