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
27namespace mlir {
28namespace affine {
29#define GEN_PASS_DEF_AFFINELOOPTILING
30#include "mlir/Dialect/Affine/Transforms/Passes.h.inc"
31} // namespace affine
32} // namespace mlir
33
34using namespace mlir;
35using namespace mlir::affine;
36
37#define DEBUG_TYPE "affine-loop-tile"
38
39namespace {
40
41/// A pass to perform loop tiling on all suitable loop nests of a func op.
42struct 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`.
63static void
64getTopLevelTileableBands(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.
78std::unique_ptr<OperationPass<func::FuncOp>>
79mlir::affine::createLoopTilingPass(uint64_t cacheSizeBytes) {
80 return std::make_unique<LoopTiling>(args&: cacheSizeBytes);
81}
82std::unique_ptr<OperationPass<func::FuncOp>>
83mlir::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).
89static 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.
114void 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
192void 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