1//===- LLVMAggregateOps.cpp - LLVM dialect aggregate ops ------------------===//
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 defines the ops of op partition `Aggregate` of the LLVM dialect.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/LLVMIR/LLVMAggregateOps.h"
14
15#include "IR/LLVMOps.h"
16#include "mlir/IR/Builders.h"
17#include "mlir/IR/DialectImplementation.h"
18#include "mlir/IR/Matchers.h"
19#include "mlir/IR/PatternMatch.h"
20
21using namespace mlir;
22using namespace mlir::LLVM;
23
24//===----------------------------------------------------------------------===//
25// ExtractValueOp
26//===----------------------------------------------------------------------===//
27
28/// Extract the type at `position` in the LLVM IR aggregate type
29/// `containerType`. Each element of `position` is an index into a nested
30/// aggregate type. Return the resulting type or emit an error.
31static Type getInsertExtractValueElementType(
32 function_ref<InFlightDiagnostic(StringRef)> emitError, Type containerType,
33 ArrayRef<int64_t> position) {
34 Type llvmType = containerType;
35 if (!isCompatibleType(type: containerType)) {
36 emitError("expected LLVM IR Dialect type, got ") << containerType;
37 return {};
38 }
39
40 // Infer the element type from the structure type: iteratively step inside the
41 // type by taking the element type, indexed by the position attribute for
42 // structures. Check the position index before accessing, it is supposed to
43 // be in bounds.
44 for (int64_t idx : position) {
45 if (auto arrayType = llvm::dyn_cast<LLVMArrayType>(Val&: llvmType)) {
46 if (idx < 0 || static_cast<unsigned>(idx) >= arrayType.getNumElements()) {
47 emitError("position out of bounds: ") << idx;
48 return {};
49 }
50 llvmType = arrayType.getElementType();
51 } else if (auto structType = llvm::dyn_cast<LLVMStructType>(Val&: llvmType)) {
52 if (idx < 0 ||
53 static_cast<unsigned>(idx) >= structType.getBody().size()) {
54 emitError("position out of bounds: ") << idx;
55 return {};
56 }
57 llvmType = structType.getBody()[idx];
58 } else {
59 emitError("expected LLVM IR structure/array type, got: ") << llvmType;
60 return {};
61 }
62 }
63 return llvmType;
64}
65
66/// Extract the type at `position` in the wrapped LLVM IR aggregate type
67/// `containerType`.
68static Type getInsertExtractValueElementType(Type llvmType,
69 ArrayRef<int64_t> position) {
70 for (int64_t idx : position) {
71 if (auto structType = llvm::dyn_cast<LLVMStructType>(Val&: llvmType))
72 llvmType = structType.getBody()[idx];
73 else
74 llvmType = llvm::cast<LLVMArrayType>(Val&: llvmType).getElementType();
75 }
76 return llvmType;
77}
78
79/// Extracts the element at the given index from an attribute. For
80/// `ElementsAttr`, returns the element at the specified index, or `nullptr` if
81/// the shaped type does not have rank 1. For `ArrayAttr`, returns the element
82/// at the specified index. For `ZeroAttr`, `UndefAttr`, and `PoisonAttr`,
83/// returns the attribute itself unchanged. Returns `nullptr` if the attribute
84/// is not one of these types or if the index is out of bounds.
85static Attribute extractElementAt(Attribute attr, size_t index) {
86 if (auto elementsAttr = dyn_cast<ElementsAttr>(Val&: attr)) {
87 ShapedType shapedType = elementsAttr.getShapedType();
88 if (!shapedType.hasRank() || shapedType.getRank() != 1)
89 return nullptr;
90 if (index < static_cast<size_t>(elementsAttr.getNumElements()))
91 return elementsAttr.getValues<Attribute>()[index];
92 return nullptr;
93 }
94 if (auto arrayAttr = dyn_cast<ArrayAttr>(Val&: attr)) {
95 if (index < arrayAttr.getValue().size())
96 return arrayAttr[index];
97 return nullptr;
98 }
99 if (isa<ZeroAttr, UndefAttr, PoisonAttr>(Val: attr))
100 return attr;
101 return nullptr;
102}
103
104OpFoldResult LLVM::ExtractValueOp::fold(FoldAdaptor adaptor) {
105 if (auto extractValueOp = getContainer().getDefiningOp<ExtractValueOp>()) {
106 SmallVector<int64_t, 4> newPos(extractValueOp.getPosition());
107 newPos.append(in_start: getPosition().begin(), in_end: getPosition().end());
108 setPosition(newPos);
109 getContainerMutable().set(extractValueOp.getContainer());
110 return getResult();
111 }
112
113 Attribute containerAttr;
114 if (matchPattern(value: getContainer(), pattern: m_Constant(bind_value: &containerAttr))) {
115 for (int64_t pos : getPosition()) {
116 containerAttr = extractElementAt(attr: containerAttr, index: pos);
117 if (!containerAttr)
118 return nullptr;
119 }
120 return containerAttr;
121 }
122
123 Value container = getContainer();
124 ArrayRef<int64_t> extractPos = getPosition();
125 while (auto insertValueOp = container.getDefiningOp<InsertValueOp>()) {
126 ArrayRef<int64_t> insertPos = insertValueOp.getPosition();
127 auto extractPosSize = extractPos.size();
128 auto insertPosSize = insertPos.size();
129
130 // Case 1: Exact match of positions.
131 if (extractPos == insertPos)
132 return insertValueOp.getValue();
133
134 // Case 2: Insert position is a prefix of extract position. Continue
135 // traversal with the inserted value. Example:
136 // ```
137 // %0 = llvm.insertvalue %arg1, %undef[0] : !llvm.struct<(i32, i32, i32)>
138 // %1 = llvm.insertvalue %arg2, %0[1] : !llvm.struct<(i32, i32, i32)>
139 // %2 = llvm.insertvalue %arg3, %1[2] : !llvm.struct<(i32, i32, i32)>
140 // %3 = llvm.insertvalue %2, %foo[0]
141 // : !llvm.struct<(struct<(i32, i32, i32)>, i64)>
142 // %4 = llvm.extractvalue %3[0, 0]
143 // : !llvm.struct<(struct<(i32, i32, i32)>, i64)>
144 // ```
145 // In the above example, %4 is folded to %arg1.
146 if (extractPosSize > insertPosSize &&
147 extractPos.take_front(N: insertPosSize) == insertPos) {
148 container = insertValueOp.getValue();
149 extractPos = extractPos.drop_front(N: insertPosSize);
150 continue;
151 }
152
153 // Case 3: Try to continue the traversal with the container value.
154
155 // If extract position is a prefix of insert position, stop propagating back
156 // as it will miss dependencies. For instance, %3 should not fold to %f0 in
157 // the following example:
158 // ```
159 // %1 = llvm.insertvalue %f0, %0[0, 0] :
160 // !llvm.array<4 x !llvm.array<4 x f32>>
161 // %2 = llvm.insertvalue %arr, %1[0] :
162 // !llvm.array<4 x !llvm.array<4 x f32>>
163 // %3 = llvm.extractvalue %2[0, 0] : !llvm.array<4 x !llvm.array<4 x f32>>
164 // ```
165 if (insertPosSize > extractPosSize &&
166 extractPos == insertPos.take_front(N: extractPosSize))
167 break;
168 // If neither a prefix, nor the exact position, we can extract out of the
169 // value being inserted into. Moreover, we can try again if that operand
170 // is itself an insertvalue expression.
171 container = insertValueOp.getContainer();
172 }
173
174 // We failed to resolve past this container either because it is not an
175 // InsertValueOp, or it is an InsertValueOp that partially overlaps with the
176 // value being extracted. Update to read from this container instead.
177 if (container == getContainer())
178 return {};
179 setPosition(extractPos);
180 getContainerMutable().assign(value: container);
181 return getResult();
182}
183
184LogicalResult ExtractValueOp::verify() {
185 auto emitError = [this](StringRef msg) { return emitOpError(message: msg); };
186 Type valueType = getInsertExtractValueElementType(
187 emitError, containerType: getContainer().getType(), position: getPosition());
188 if (!valueType)
189 return failure();
190
191 if (getRes().getType() != valueType)
192 return emitOpError() << "Type mismatch: extracting from "
193 << getContainer().getType() << " should produce "
194 << valueType << " but this op returns "
195 << getRes().getType();
196 return success();
197}
198
199void ExtractValueOp::build(OpBuilder &builder, OperationState &state,
200 Value container, ArrayRef<int64_t> position) {
201 build(odsBuilder&: builder, odsState&: state,
202 res: getInsertExtractValueElementType(llvmType: container.getType(), position),
203 container, position: builder.getAttr<DenseI64ArrayAttr>(args&: position));
204}
205
206//===----------------------------------------------------------------------===//
207// InsertValueOp
208//===----------------------------------------------------------------------===//
209
210namespace {
211/// Update any ExtractValueOps using a given InsertValueOp to instead read from
212/// the closest InsertValueOp in the chain leading up to the current op that
213/// writes to the same member. This traversal could be done entirely in
214/// ExtractValueOp::fold, but doing it here significantly speeds things up
215/// because we can handle several ExtractValueOps with a single traversal.
216/// For instance, in this example:
217/// %i0 = llvm.insertvalue %v0, %undef[0]
218/// %i1 = llvm.insertvalue %v1, %0[1]
219/// ...
220/// %i999 = llvm.insertvalue %v999, %998[999]
221/// %e0 = llvm.extractvalue %i999[0]
222/// %e1 = llvm.extractvalue %i999[1]
223/// ...
224/// %e999 = llvm.extractvalue %i999[999]
225/// Individually running the folder on each extractvalue would require
226/// traversing the insertvalue chain 1000 times, but running this pattern on the
227/// InsertValueOp would allow us to achieve the same result with a single
228/// traversal. The resulting IR after this pattern will then be:
229/// %i0 = llvm.insertvalue %v0, %undef[0]
230/// %i1 = llvm.insertvalue %v1, %0[1]
231/// ...
232/// %i999 = llvm.insertvalue %v999, %998[999]
233/// %e0 = llvm.extractvalue %i0[0]
234/// %e1 = llvm.extractvalue %i1[1]
235/// ...
236/// %e999 = llvm.extractvalue %i999[999]
237struct ResolveExtractValueSource : public OpRewritePattern<InsertValueOp> {
238 using Base::Base;
239
240 LogicalResult matchAndRewrite(InsertValueOp insertOp,
241 PatternRewriter &rewriter) const override {
242 bool changed = false;
243 // Map each position in the top-level struct to the ExtractOps that read
244 // from it. For the example in the doc-comment above this map will be empty
245 // when we visit ops %i0 - %i998. For %i999, it will contain:
246 // 0 -> { %e0 }, 1 -> { %e1 }, ... 999-> { %e999 }
247 DenseMap<int64_t, SmallVector<ExtractValueOp, 4>> posToExtractOps;
248 auto insertBaseIdx = insertOp.getPosition()[0];
249 for (auto &use : insertOp->getUses()) {
250 if (auto extractOp = dyn_cast<ExtractValueOp>(Val: use.getOwner())) {
251 auto baseIdx = extractOp.getPosition()[0];
252 // We can skip reads of the member that insertOp writes to since they
253 // will not be updated.
254 if (baseIdx == insertBaseIdx)
255 continue;
256 posToExtractOps[baseIdx].push_back(Elt: extractOp);
257 }
258 }
259 // Walk up the chain of insertions and try to resolve the remaining
260 // extractions that access the same member.
261 Value nextContainer = insertOp.getContainer();
262 while (!posToExtractOps.empty()) {
263 auto curInsert =
264 dyn_cast_or_null<InsertValueOp>(Val: nextContainer.getDefiningOp());
265 if (!curInsert)
266 break;
267 nextContainer = curInsert.getContainer();
268
269 // Check if any extractions read the member written by this insertion.
270 auto curInsertBaseIdx = curInsert.getPosition()[0];
271 auto it = posToExtractOps.find(Val: curInsertBaseIdx);
272 if (it == posToExtractOps.end())
273 continue;
274
275 // Update the ExtractOps to read from the current insertion.
276 for (auto &extractOp : it->second) {
277 rewriter.modifyOpInPlace(root: extractOp, callable: [&] {
278 extractOp.getContainerMutable().assign(value: curInsert);
279 });
280 }
281 // The entry should never be empty if it exists, so if we are at this
282 // point, set changed to true.
283 assert(!it->second.empty());
284 changed |= true;
285 posToExtractOps.erase(I: it);
286 }
287 // There was no insertion along the chain that wrote the member accessed by
288 // these extracts. So we can update them to use the top of the chain.
289 for (auto &[baseIdx, extracts] : posToExtractOps) {
290 for (auto &extractOp : extracts) {
291 rewriter.modifyOpInPlace(root: extractOp, callable: [&] {
292 extractOp.getContainerMutable().assign(value: nextContainer);
293 });
294 }
295 assert(!extracts.empty() && "Empty list in map");
296 changed = true;
297 }
298 return success(IsSuccess: changed);
299 }
300};
301} // namespace
302
303void InsertValueOp::getCanonicalizationPatterns(RewritePatternSet &patterns,
304 MLIRContext *context) {
305 patterns.add<ResolveExtractValueSource>(arg&: context);
306}
307
308/// Infer the value type from the container type and position.
309ParseResult mlir::LLVM::parseInsertExtractValueElementType(
310 AsmParser &parser, Type &valueType, Type containerType,
311 DenseI64ArrayAttr position) {
312 valueType = getInsertExtractValueElementType(
313 emitError: [&](StringRef msg) {
314 return parser.emitError(loc: parser.getCurrentLocation(), message: msg);
315 },
316 containerType, position: position.asArrayRef());
317 return success(IsSuccess: !!valueType);
318}
319
320/// Nothing to print for an inferred type.
321void mlir::LLVM::printInsertExtractValueElementType(
322 AsmPrinter &printer, Operation *op, Type valueType, Type containerType,
323 DenseI64ArrayAttr position) {}
324
325LogicalResult InsertValueOp::verify() {
326 auto emitError = [this](StringRef msg) { return emitOpError(message: msg); };
327 Type valueType = getInsertExtractValueElementType(
328 emitError, containerType: getContainer().getType(), position: getPosition());
329 if (!valueType)
330 return failure();
331
332 if (getValue().getType() != valueType)
333 return emitOpError() << "Type mismatch: cannot insert "
334 << getValue().getType() << " into "
335 << getContainer().getType();
336
337 return success();
338}
339
340#define GET_OP_CLASSES
341#include "mlir/Dialect/LLVMIR/LLVMAggregateOps.cpp.inc"
342