| 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 | |
| 21 | using namespace mlir; |
| 22 | using 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. |
| 31 | static Type ( |
| 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`. |
| 68 | static Type (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. |
| 85 | static Attribute (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 | |
| 104 | OpFoldResult LLVM::ExtractValueOp::(FoldAdaptor adaptor) { |
| 105 | if (auto = 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> = getPosition(); |
| 125 | while (auto insertValueOp = container.getDefiningOp<InsertValueOp>()) { |
| 126 | ArrayRef<int64_t> insertPos = insertValueOp.getPosition(); |
| 127 | auto = 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 | |
| 184 | LogicalResult ExtractValueOp::() { |
| 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 | |
| 199 | void ExtractValueOp::(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 | |
| 210 | namespace { |
| 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] |
| 237 | struct : 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>> ; |
| 248 | auto insertBaseIdx = insertOp.getPosition()[0]; |
| 249 | for (auto &use : insertOp->getUses()) { |
| 250 | if (auto = 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 & : 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 & : 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 | |
| 303 | void 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. |
| 309 | ParseResult mlir::LLVM::( |
| 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. |
| 321 | void mlir::LLVM::( |
| 322 | AsmPrinter &printer, Operation *op, Type valueType, Type containerType, |
| 323 | DenseI64ArrayAttr position) {} |
| 324 | |
| 325 | LogicalResult 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 | |