| 1 | //===- OptimizeSharedMemory.cpp - MLIR NVGPU pass implementation ----------===// |
| 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 implements transforms to optimize accesses to shared memory. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/NVGPU/Transforms/Passes.h" |
| 14 | |
| 15 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 16 | #include "mlir/Dialect/MemRef/IR/MemRef.h" |
| 17 | #include "mlir/Dialect/NVGPU/IR/NVGPUDialect.h" |
| 18 | #include "mlir/Dialect/NVGPU/Transforms/Transforms.h" |
| 19 | #include "mlir/Dialect/NVGPU/Transforms/Utils.h" |
| 20 | #include "mlir/Dialect/Vector/IR/VectorOps.h" |
| 21 | #include "mlir/Interfaces/SideEffectInterfaces.h" |
| 22 | #include "llvm/ADT/STLExtras.h" |
| 23 | #include "llvm/Support/MathExtras.h" |
| 24 | |
| 25 | namespace mlir { |
| 26 | namespace nvgpu { |
| 27 | #define GEN_PASS_DEF_OPTIMIZESHAREDMEMORY |
| 28 | #include "mlir/Dialect/NVGPU/Transforms/Passes.h.inc" |
| 29 | } // namespace nvgpu |
| 30 | } // namespace mlir |
| 31 | |
| 32 | using namespace mlir; |
| 33 | using namespace mlir::nvgpu; |
| 34 | |
| 35 | /// The size of a shared memory line according to NV documentation. |
| 36 | constexpr int64_t kSharedMemoryLineSizeBytes = 128; |
| 37 | /// We optimize for 128bit accesses, but this can be made an argument in the |
| 38 | /// future. |
| 39 | constexpr int64_t kDefaultVectorSizeBits = 128; |
| 40 | |
| 41 | /// Uses `srcIndexValue` to permute `tgtIndexValue` via |
| 42 | /// `result = xor(floordiv(srcIdxVal,permuteEveryN), |
| 43 | /// floordiv(tgtIdxVal,vectorSize))) |
| 44 | /// + tgtIdxVal % vectorSize` |
| 45 | /// This is done using an optimized sequence of `arith` operations. |
| 46 | static Value permuteVectorOffset(OpBuilder &b, Location loc, |
| 47 | ArrayRef<Value> indices, MemRefType memrefTy, |
| 48 | int64_t srcDim, int64_t tgtDim) { |
| 49 | // Adjust the src index to change how often the permutation changes |
| 50 | // if necessary. |
| 51 | Value src = indices[srcDim]; |
| 52 | |
| 53 | // We only want to permute every N iterations of the target dim where N is |
| 54 | // ceil(sharedMemoryLineSizeBytes / dimSizeBytes(tgtDim)). |
| 55 | const int64_t permuteEveryN = std::max<int64_t>( |
| 56 | a: 1, b: kSharedMemoryLineSizeBytes / ((memrefTy.getDimSize(idx: tgtDim) * |
| 57 | memrefTy.getElementTypeBitWidth()) / |
| 58 | 8)); |
| 59 | |
| 60 | // clang-format off |
| 61 | // Index bit representation (b0 = least significant bit) for dim(1) |
| 62 | // of a `memref<?x?xDT>` is as follows: |
| 63 | // N := log2(128/elementSizeBits) |
| 64 | // M := log2(dimSize(1)) |
| 65 | // then |
| 66 | // bits[0:N] = sub-vector element offset |
| 67 | // bits[N:M] = vector index |
| 68 | // clang-format on |
| 69 | int64_t n = |
| 70 | llvm::Log2_64(Value: kDefaultVectorSizeBits / memrefTy.getElementTypeBitWidth()); |
| 71 | int64_t m = llvm::Log2_64(Value: memrefTy.getDimSize(idx: tgtDim)); |
| 72 | |
| 73 | // Capture bits[0:(M-N)] of src by first creating a (M-N) mask. |
| 74 | int64_t mask = (1LL << (m - n)) - 1; |
| 75 | if (permuteEveryN > 1) |
| 76 | mask = mask << llvm::Log2_64(Value: permuteEveryN); |
| 77 | Value srcBits = arith::ConstantIndexOp::create(builder&: b, location: loc, value: mask); |
| 78 | srcBits = arith::AndIOp::create(builder&: b, location: loc, lhs: src, rhs: srcBits); |
| 79 | |
| 80 | // Use the src bits to permute the target bits b[N:M] containing the |
| 81 | // vector offset. |
| 82 | if (permuteEveryN > 1) { |
| 83 | int64_t shlBits = n - llvm::Log2_64(Value: permuteEveryN); |
| 84 | if (shlBits > 0) { |
| 85 | Value finalShiftVal = arith::ConstantIndexOp::create(builder&: b, location: loc, value: shlBits); |
| 86 | srcBits = b.createOrFold<arith::ShLIOp>(location: loc, args&: srcBits, args&: finalShiftVal); |
| 87 | } else if (shlBits < 0) { |
| 88 | Value finalShiftVal = |
| 89 | arith::ConstantIndexOp::create(builder&: b, location: loc, value: -1 * shlBits); |
| 90 | srcBits = b.createOrFold<arith::ShRUIOp>(location: loc, args&: srcBits, args&: finalShiftVal); |
| 91 | } |
| 92 | } else { |
| 93 | Value finalShiftVal = arith::ConstantIndexOp::create(builder&: b, location: loc, value: n); |
| 94 | srcBits = b.createOrFold<arith::ShLIOp>(location: loc, args&: srcBits, args&: finalShiftVal); |
| 95 | } |
| 96 | |
| 97 | Value permutedVectorIdx = |
| 98 | arith::XOrIOp::create(builder&: b, location: loc, lhs: indices[tgtDim], rhs: srcBits); |
| 99 | return permutedVectorIdx; |
| 100 | } |
| 101 | |
| 102 | static void transformIndices(OpBuilder &builder, Location loc, |
| 103 | SmallVector<Value, 4> &indices, |
| 104 | MemRefType memrefTy, int64_t srcDim, |
| 105 | int64_t tgtDim) { |
| 106 | indices[tgtDim] = |
| 107 | permuteVectorOffset(b&: builder, loc, indices, memrefTy, srcDim, tgtDim); |
| 108 | } |
| 109 | |
| 110 | /// Return all operations within `parentOp` that read from or write to |
| 111 | /// `shmMemRef`. |
| 112 | static LogicalResult |
| 113 | getShmReadAndWriteOps(Operation *parentOp, Value shmMemRef, |
| 114 | SmallVector<Operation *, 16> &readOps, |
| 115 | SmallVector<Operation *, 16> &writeOps) { |
| 116 | parentOp->walk(callback: [&](Operation *op) { |
| 117 | MemoryEffectOpInterface iface = dyn_cast<MemoryEffectOpInterface>(Val: op); |
| 118 | if (!iface) |
| 119 | return; |
| 120 | std::optional<MemoryEffects::EffectInstance> effect = |
| 121 | iface.getEffectOnValue<MemoryEffects::Read>(value: shmMemRef); |
| 122 | if (effect) { |
| 123 | readOps.push_back(Elt: op); |
| 124 | return; |
| 125 | } |
| 126 | effect = iface.getEffectOnValue<MemoryEffects::Write>(value: shmMemRef); |
| 127 | if (effect) |
| 128 | writeOps.push_back(Elt: op); |
| 129 | }); |
| 130 | |
| 131 | // Restrict to a supported set of ops. We also require at least 2D access, |
| 132 | // although this could be relaxed. |
| 133 | if (llvm::any_of(Range&: readOps, P: [](Operation *op) { |
| 134 | return !isa<memref::LoadOp, vector::LoadOp, nvgpu::LdMatrixOp>(Val: op) || |
| 135 | getIndices(op).size() < 2; |
| 136 | })) |
| 137 | return failure(); |
| 138 | if (llvm::any_of(Range&: writeOps, P: [](Operation *op) { |
| 139 | return !isa<memref::StoreOp, vector::StoreOp, nvgpu::DeviceAsyncCopyOp>( |
| 140 | Val: op) || |
| 141 | getIndices(op).size() < 2; |
| 142 | })) |
| 143 | return failure(); |
| 144 | |
| 145 | return success(); |
| 146 | } |
| 147 | |
| 148 | bool mlir::nvgpu::canSwizzleSharedMemoryType(MemRefType memRefType) { |
| 149 | // Not support 0D MemRefs. |
| 150 | if (memRefType.getRank() == 0) |
| 151 | return false; |
| 152 | |
| 153 | // Only support memrefs with scalar element types (i.e., int or float). |
| 154 | // Memrefs with vector element types are not supported. |
| 155 | if (!memRefType.getElementType().isIntOrFloat()) |
| 156 | return false; |
| 157 | |
| 158 | // Check if this is necessary given the assumption of 128b accesses: |
| 159 | // If dim[rank-1] is small enough to fit 8 rows in a 128B line. |
| 160 | const int64_t rowSize = memRefType.getDimSize(idx: memRefType.getRank() - 1); |
| 161 | if (ShapedType::isDynamic(dValue: rowSize) || rowSize == 0) |
| 162 | return false; |
| 163 | |
| 164 | const int64_t rowsPerLine = |
| 165 | (8 * kSharedMemoryLineSizeBytes / memRefType.getElementTypeBitWidth()) / |
| 166 | rowSize; |
| 167 | const int64_t threadGroupSize = |
| 168 | 1LL << (7 - llvm::Log2_64(Value: kDefaultVectorSizeBits / 8)); |
| 169 | if (rowsPerLine >= threadGroupSize) |
| 170 | return false; |
| 171 | |
| 172 | // The XOR swizzle stays within a row only if the row size is a power of 2. |
| 173 | // Otherwise it moves some accesses into the next row, where they overwrite |
| 174 | // other elements. |
| 175 | return llvm::isPowerOf2_64(Value: rowSize); |
| 176 | } |
| 177 | |
| 178 | llvm::LogicalResult |
| 179 | mlir::nvgpu::optimizeSharedMemoryReadsAndWrites(Operation *parentOp, |
| 180 | Value memrefValue) { |
| 181 | auto memRefType = dyn_cast<MemRefType>(Val: memrefValue.getType()); |
| 182 | if (!memRefType || !NVGPUDialect::hasSharedMemoryAddressSpace(type: memRefType)) |
| 183 | return failure(); |
| 184 | |
| 185 | if (!canSwizzleSharedMemoryType(memRefType)) |
| 186 | return failure(); |
| 187 | |
| 188 | // Abort if the given value has any sub-views; we do not do any alias |
| 189 | // analysis. |
| 190 | bool hasSubView = false; |
| 191 | parentOp->walk(callback: [&](memref::SubViewOp subView) { hasSubView = true; }); |
| 192 | if (hasSubView) |
| 193 | return failure(); |
| 194 | |
| 195 | // Get sets of operations within the function that read/write to shared |
| 196 | // memory. |
| 197 | SmallVector<Operation *, 16> shmReadOps; |
| 198 | SmallVector<Operation *, 16> shmWriteOps; |
| 199 | if (failed(Result: getShmReadAndWriteOps(parentOp, shmMemRef: memrefValue, readOps&: shmReadOps, |
| 200 | writeOps&: shmWriteOps))) |
| 201 | return failure(); |
| 202 | |
| 203 | if (shmReadOps.empty() || shmWriteOps.empty()) |
| 204 | return failure(); |
| 205 | |
| 206 | OpBuilder builder(parentOp->getContext()); |
| 207 | |
| 208 | int64_t tgtDim = memRefType.getRank() - 1; |
| 209 | int64_t srcDim = memRefType.getRank() - 2; |
| 210 | |
| 211 | // Transform indices for the ops writing to shared memory. |
| 212 | while (!shmWriteOps.empty()) { |
| 213 | Operation *shmWriteOp = shmWriteOps.back(); |
| 214 | shmWriteOps.pop_back(); |
| 215 | builder.setInsertionPoint(shmWriteOp); |
| 216 | |
| 217 | auto indices = getIndices(op: shmWriteOp); |
| 218 | SmallVector<Value, 4> transformedIndices(indices.begin(), indices.end()); |
| 219 | transformIndices(builder, loc: shmWriteOp->getLoc(), indices&: transformedIndices, |
| 220 | memrefTy: memRefType, srcDim, tgtDim); |
| 221 | setIndices(op: shmWriteOp, indices: transformedIndices); |
| 222 | } |
| 223 | |
| 224 | // Transform indices for the ops reading from shared memory. |
| 225 | while (!shmReadOps.empty()) { |
| 226 | Operation *shmReadOp = shmReadOps.back(); |
| 227 | shmReadOps.pop_back(); |
| 228 | builder.setInsertionPoint(shmReadOp); |
| 229 | |
| 230 | auto indices = getIndices(op: shmReadOp); |
| 231 | SmallVector<Value, 4> transformedIndices(indices.begin(), indices.end()); |
| 232 | transformIndices(builder, loc: shmReadOp->getLoc(), indices&: transformedIndices, |
| 233 | memrefTy: memRefType, srcDim, tgtDim); |
| 234 | setIndices(op: shmReadOp, indices: transformedIndices); |
| 235 | } |
| 236 | |
| 237 | return success(); |
| 238 | } |
| 239 | |
| 240 | namespace { |
| 241 | class OptimizeSharedMemoryPass |
| 242 | : public nvgpu::impl::OptimizeSharedMemoryBase<OptimizeSharedMemoryPass> { |
| 243 | public: |
| 244 | OptimizeSharedMemoryPass() = default; |
| 245 | |
| 246 | void runOnOperation() override { |
| 247 | Operation *op = getOperation(); |
| 248 | SmallVector<memref::AllocOp> shmAllocOps; |
| 249 | op->walk(callback: [&](memref::AllocOp allocOp) { |
| 250 | if (!NVGPUDialect::hasSharedMemoryAddressSpace(type: allocOp.getType())) |
| 251 | return; |
| 252 | shmAllocOps.push_back(Elt: allocOp); |
| 253 | }); |
| 254 | for (auto allocOp : shmAllocOps) { |
| 255 | if (failed(Result: optimizeSharedMemoryReadsAndWrites(parentOp: getOperation(), |
| 256 | memrefValue: allocOp.getMemref()))) |
| 257 | return; |
| 258 | } |
| 259 | } |
| 260 | }; |
| 261 | } // namespace |
| 262 | |
| 263 | std::unique_ptr<Pass> mlir::nvgpu::createOptimizeSharedMemoryPass() { |
| 264 | return std::make_unique<OptimizeSharedMemoryPass>(); |
| 265 | } |
| 266 | |