| 1 | //===- LoopTiling.cpp --- Loop tiling pass ------------------------------*-===// |
| 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 a pass to tile affine loop nests. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/Affine/Transforms/Passes.h" |
| 14 | |
| 15 | #include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h" |
| 16 | #include "mlir/Dialect/Affine/Analysis/AffineStructures.h" |
| 17 | #include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h" |
| 18 | #include "mlir/Dialect/Affine/Analysis/Utils.h" |
| 19 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 20 | #include "mlir/Dialect/Affine/LoopUtils.h" |
| 21 | #include "mlir/Dialect/Affine/Utils.h" |
| 22 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 23 | #include "llvm/Support/CommandLine.h" |
| 24 | #include "llvm/Support/Debug.h" |
| 25 | #include <optional> |
| 26 | |
| 27 | namespace mlir { |
| 28 | namespace affine { |
| 29 | #define GEN_PASS_DEF_AFFINELOOPTILING |
| 30 | #include "mlir/Dialect/Affine/Transforms/Passes.h.inc" |
| 31 | } // namespace affine |
| 32 | } // namespace mlir |
| 33 | |
| 34 | using namespace mlir; |
| 35 | using namespace mlir::affine; |
| 36 | |
| 37 | #define DEBUG_TYPE "affine-loop-tile" |
| 38 | |
| 39 | namespace { |
| 40 | |
| 41 | /// A pass to perform loop tiling on all suitable loop nests of a func op. |
| 42 | struct LoopTiling : public affine::impl::AffineLoopTilingBase<LoopTiling> { |
| 43 | LoopTiling() = default; |
| 44 | explicit LoopTiling(uint64_t cacheSizeBytes, bool avoidMaxMinBounds = true) |
| 45 | : avoidMaxMinBounds(avoidMaxMinBounds) { |
| 46 | this->cacheSizeInKiB = cacheSizeBytes / 1024; |
| 47 | } |
| 48 | |
| 49 | void runOnOperation() override; |
| 50 | void getTileSizes(ArrayRef<AffineForOp> band, |
| 51 | SmallVectorImpl<unsigned> *tileSizes); |
| 52 | |
| 53 | // Default tile size if nothing is provided. |
| 54 | constexpr static unsigned kDefaultTileSize = 4; |
| 55 | |
| 56 | // If true, tile sizes are set to avoid max/min in bounds if possible. |
| 57 | bool avoidMaxMinBounds = true; |
| 58 | }; |
| 59 | |
| 60 | } // namespace |
| 61 | |
| 62 | /// Get bands of loops that are valid to tile from the top-level of `f`. |
| 63 | static void |
| 64 | getTopLevelTileableBands(func::FuncOp f, |
| 65 | std::vector<SmallVector<AffineForOp, 6>> &bands) { |
| 66 | // Get maximal perfect nest of 'affine.for' ops starting from root |
| 67 | // (inclusive). |
| 68 | for (AffineForOp forOp : f.getOps<AffineForOp>()) { |
| 69 | SmallVector<AffineForOp, 6> band; |
| 70 | getPerfectlyNestedLoops(nestedLoops&: band, root: forOp); |
| 71 | if (isTilingValid(loops: band)) |
| 72 | bands.push_back(x: band); |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | /// Creates a pass to perform loop tiling on all suitable loop nests of a |
| 77 | /// Function. |
| 78 | std::unique_ptr<OperationPass<func::FuncOp>> |
| 79 | mlir::affine::createLoopTilingPass(uint64_t cacheSizeBytes) { |
| 80 | return std::make_unique<LoopTiling>(args&: cacheSizeBytes); |
| 81 | } |
| 82 | std::unique_ptr<OperationPass<func::FuncOp>> |
| 83 | mlir::affine::createLoopTilingPass() { |
| 84 | return std::make_unique<LoopTiling>(); |
| 85 | } |
| 86 | |
| 87 | /// Reduces each tile size to the largest divisor of the corresponding trip |
| 88 | /// count (if the trip count is known). |
| 89 | static void adjustToDivisorsOfTripCounts(ArrayRef<AffineForOp> band, |
| 90 | SmallVectorImpl<unsigned> *tileSizes) { |
| 91 | assert(band.size() == tileSizes->size() && "invalid tile size count" ); |
| 92 | for (unsigned i = 0, e = band.size(); i < e; i++) { |
| 93 | unsigned &tSizeAdjusted = (*tileSizes)[i]; |
| 94 | AffineForOp forOp = band[i]; |
| 95 | std::optional<APInt> mayConst = forOp.getStaticTripCount(); |
| 96 | if (!mayConst) |
| 97 | continue; |
| 98 | // Adjust the tile size to largest factor of the trip count less than |
| 99 | // tSize. |
| 100 | uint64_t constTripCount = mayConst->getZExtValue(); |
| 101 | if (constTripCount > 1 && tSizeAdjusted > constTripCount / 2) |
| 102 | tSizeAdjusted = constTripCount / 2; |
| 103 | while (constTripCount % tSizeAdjusted != 0) |
| 104 | tSizeAdjusted--; |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | // Returns tile sizes to use. Checks CL options; if none are specified, sets it |
| 109 | // based on a simple model that looks at the memory footprint and determines |
| 110 | // tile sizes assuming identity accesses / 1:1 tile size proportional footprint |
| 111 | // along each of the dimensions being tiled. |
| 112 | // TODO: evolve this model. Tile size determination is a large area |
| 113 | // to play with in general. |
| 114 | void LoopTiling::getTileSizes(ArrayRef<AffineForOp> band, |
| 115 | SmallVectorImpl<unsigned> *tileSizes) { |
| 116 | if (band.empty()) |
| 117 | return; |
| 118 | |
| 119 | // Use command-line tileSize for all loops if specified. |
| 120 | if (tileSize) { |
| 121 | tileSizes->assign(NumElts: band.size(), Elt: tileSize); |
| 122 | return; |
| 123 | } |
| 124 | |
| 125 | // Use supplied tile sizes and fill them with default tile size if it's short. |
| 126 | if (!this->tileSizes.empty()) { |
| 127 | tileSizes->assign(in_start: this->tileSizes.begin(), in_end: this->tileSizes.end()); |
| 128 | tileSizes->resize(N: band.size(), NV: kDefaultTileSize); |
| 129 | return; |
| 130 | } |
| 131 | tileSizes->resize(N: band.size()); |
| 132 | |
| 133 | // If the cache size is zero, set the minimum valid tile size. No good reason |
| 134 | // to pick another specific size over this. |
| 135 | if (cacheSizeInKiB == 0) { |
| 136 | llvm::fill(Range&: *tileSizes, Value: 1); |
| 137 | return; |
| 138 | } |
| 139 | |
| 140 | // Obtain memory footprint and set tile sizes so that a tile fits in |
| 141 | // the cache size. This is an approximation with the assumption that the |
| 142 | // footprint increases with the tile size linearly in that dimension (i.e., |
| 143 | // assumes one-to-one access function). |
| 144 | std::optional<int64_t> fp = getMemoryFootprintBytes(forOp: band[0], memorySpace: 0); |
| 145 | if (!fp) { |
| 146 | // Fill with default tile sizes if footprint is unknown. |
| 147 | llvm::fill(Range&: *tileSizes, Value: LoopTiling::kDefaultTileSize); |
| 148 | if (avoidMaxMinBounds) |
| 149 | adjustToDivisorsOfTripCounts(band, tileSizes); |
| 150 | // The first loop in the band. |
| 151 | AffineForOp rootForOp = band[0]; |
| 152 | (void)rootForOp; |
| 153 | LLVM_DEBUG( |
| 154 | rootForOp.emitWarning("memory footprint unknown: using default tile " |
| 155 | "sizes adjusted to trip count divisors" )); |
| 156 | return; |
| 157 | } |
| 158 | |
| 159 | // Check how many times larger the cache size is when compared to footprint. |
| 160 | uint64_t cacheSizeBytes = cacheSizeInKiB * 1024; |
| 161 | uint64_t excessFactor = llvm::divideCeil(Numerator: *fp, Denominator: cacheSizeBytes); |
| 162 | if (excessFactor <= 1) { |
| 163 | // No need of any tiling - set tile size to 1. |
| 164 | llvm::fill(Range&: *tileSizes, Value: 1); |
| 165 | return; |
| 166 | } |
| 167 | |
| 168 | // Divide all loops equally in an attempt to reduce footprint. |
| 169 | // TODO: this is approximate. Ideally, obtain reuse factor / |
| 170 | // profitability along each dimension and weight tile sizes based on that as |
| 171 | // one possible approach. Or compute a polynomial in tile sizes and solve for |
| 172 | // it. |
| 173 | |
| 174 | // For an n-d tileable band, compute the n^th root of the excess. |
| 175 | unsigned tSize = |
| 176 | static_cast<unsigned>(floorl(x: std::pow(x: excessFactor, y: 1.0 / band.size()))); |
| 177 | // We'll keep a running product to determine the last tile size better. |
| 178 | unsigned cumulProductOfTileSizes = 1; |
| 179 | for (unsigned i = 0, e = band.size(); i < e; i++) { |
| 180 | if (i < e - 1) |
| 181 | (*tileSizes)[i] = tSize; |
| 182 | else |
| 183 | // Set last tile size to cover the balance. |
| 184 | (*tileSizes)[i] = std::max( |
| 185 | a: 1U, b: static_cast<unsigned>(excessFactor / cumulProductOfTileSizes)); |
| 186 | cumulProductOfTileSizes *= (*tileSizes)[i]; |
| 187 | } |
| 188 | if (avoidMaxMinBounds) |
| 189 | adjustToDivisorsOfTripCounts(band, tileSizes); |
| 190 | } |
| 191 | |
| 192 | void LoopTiling::runOnOperation() { |
| 193 | // Bands of loops to tile. |
| 194 | std::vector<SmallVector<AffineForOp, 6>> bands; |
| 195 | getTopLevelTileableBands(f: getOperation(), bands); |
| 196 | |
| 197 | // Tile each band. |
| 198 | for (auto &band : bands) { |
| 199 | // Set up tile sizes; fill missing tile sizes at the end with default tile |
| 200 | // size or tileSize if one was provided. |
| 201 | SmallVector<unsigned, 6> tileSizes; |
| 202 | getTileSizes(band, tileSizes: &tileSizes); |
| 203 | if (llvm::DebugFlag) { |
| 204 | auto diag = band[0].emitRemark(message: "using tile sizes [" ); |
| 205 | llvm::interleaveComma(c: tileSizes, os&: llvm::dbgs()); |
| 206 | diag << "]\n" ; |
| 207 | } |
| 208 | SmallVector<AffineForOp, 6> tiledNest; |
| 209 | if (failed(Result: tilePerfectlyNested(input: band, tileSizes, tiledNest: &tiledNest))) { |
| 210 | // An empty band always succeeds. |
| 211 | assert(!band.empty() && "guaranteed to succeed on empty bands" ); |
| 212 | LLVM_DEBUG(band.front()->emitRemark("loop tiling failed!\n" )); |
| 213 | continue; |
| 214 | } |
| 215 | |
| 216 | // Separate full and partial tiles. |
| 217 | if (separate) { |
| 218 | auto intraTileLoops = |
| 219 | MutableArrayRef<AffineForOp>(tiledNest).drop_front(N: band.size()); |
| 220 | if (failed(Result: separateFullTiles(nest: intraTileLoops))) { |
| 221 | assert(!intraTileLoops.empty() && |
| 222 | "guaranteed to succeed on empty bands" ); |
| 223 | LLVM_DEBUG(intraTileLoops.front()->emitRemark( |
| 224 | "separation post tiling failed!" )); |
| 225 | } |
| 226 | } |
| 227 | } |
| 228 | } |
| 229 | |