MLIR-AIE 1.4.6.dev
BFP16MatMulOperands.cpp
Go to the documentation of this file.
1//===- BFP16MatMulOperands.cpp - Operands of bfp16 matmuls --------------===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7//
8// Patterns that let AIE2P bfp16 matmuls load their operands as bfp16ebs8
9// blocks (72 bytes: per row, an exponent byte then 8 mantissa bytes) instead
10// of converting bf16 tiles before every multiply.
11//
12//===----------------------------------------------------------------------===//
13
14#include "BFP16MatMulOperands.h"
15
18#include "mlir/Analysis/AliasAnalysis/LocalAliasAnalysis.h"
19#include "mlir/Dialect/Affine/IR/AffineOps.h"
20#include "mlir/Dialect/Arith/IR/Arith.h"
21#include "mlir/Dialect/LLVMIR/LLVMTypes.h"
22#include "mlir/Dialect/MemRef/IR/MemRef.h"
23#include "mlir/Dialect/SCF/IR/SCF.h"
24#include "mlir/Dialect/Utils/StaticValueUtils.h"
25#include "mlir/Dialect/Vector/IR/VectorOps.h"
26#include "mlir/IR/IRMapping.h"
27#include "mlir/IR/PatternMatch.h"
28#include "mlir/Interfaces/SideEffectInterfaces.h"
29
30#include <numeric>
31
32using namespace mlir;
33using namespace xilinx;
34using namespace xilinx::aievec;
35
36namespace {
37
38/// The type of a FIFO stream's address. Loops carry it as a pointer, not as
39/// an integer converted at every access.
40Type fifoAddrType(MLIRContext *ctx) { return LLVM::LLVMPointerType::get(ctx); }
41
42constexpr int64_t kTile = 64; // Values in an 8x8 tile.
43constexpr int64_t kExpBytes = 8; // Exponent bytes in a block.
44// Upper bound used for divisors, also standing for "divisible by anything".
45constexpr int64_t kMaxDiv = 1 << 30;
46
47/// Returns the aie.buffer that `v` is, or that `v` reshapes as a whole, or
48/// null.
49static AIE::BufferOp rootBuffer(Value v) {
50 while (Operation *d = v.getDefiningOp()) {
51 if (auto b = dyn_cast<AIE::BufferOp>(d))
52 return b;
53 if (!isa<memref::CollapseShapeOp, memref::ExpandShapeOp, memref::CastOp>(d))
54 return {};
55 v = d->getOperand(0);
56 }
57 return {};
58}
59
60static int64_t mulCapped(int64_t a, int64_t b) {
61 return (a >= kMaxDiv / std::max<int64_t>(b, 1)) ? kMaxDiv : a * b;
62}
63
64static int64_t knownDivisor(Value v, int depth = 0);
65
66/// Returns a known divisor of the affine expression `e`, whose dims and
67/// symbols are `operands`.
68static int64_t exprDivisor(AffineExpr e, ValueRange operands, unsigned nDims,
69 int depth) {
70 if (auto c = dyn_cast<AffineConstantExpr>(e))
71 return c.getValue() ? std::abs(c.getValue()) : kMaxDiv;
72 if (auto d = dyn_cast<AffineDimExpr>(e))
73 return knownDivisor(operands[d.getPosition()], depth + 1);
74 if (auto s = dyn_cast<AffineSymbolExpr>(e))
75 return knownDivisor(operands[nDims + s.getPosition()], depth + 1);
76 auto bin = cast<AffineBinaryOpExpr>(e);
77 int64_t l = exprDivisor(bin.getLHS(), operands, nDims, depth);
78 int64_t r = exprDivisor(bin.getRHS(), operands, nDims, depth);
79 switch (bin.getKind()) {
80 case AffineExprKind::Add:
81 return std::gcd(l, r);
82 case AffineExprKind::Mul:
83 return mulCapped(l, r);
84 case AffineExprKind::Mod:
85 // x mod c = x - c * (x floordiv c)
86 if (auto c = dyn_cast<AffineConstantExpr>(bin.getRHS()))
87 return std::gcd(l, std::abs(c.getValue()));
88 return 1;
89 default:
90 return 1;
91 }
92}
93
94/// Returns a divisor of the index `v` that follows from how it is computed,
95/// or 1.
96static int64_t knownDivisor(Value v, int depth) {
97 if (depth > 16)
98 return 1;
99 if (std::optional<int64_t> c = getConstantIntValue(v))
100 return *c ? std::abs(*c) : kMaxDiv;
101 if (auto arg = dyn_cast<BlockArgument>(v)) {
102 auto loop = dyn_cast<scf::ForOp>(arg.getOwner()->getParentOp());
103 if (!loop)
104 return 1;
105 if (arg == loop.getInductionVar())
106 return std::gcd(knownDivisor(loop.getLowerBound(), depth + 1),
107 knownDivisor(loop.getStep(), depth + 1));
108 // An iter_arg incremented by the same value every iteration, such as a
109 // pointer the loop advances.
110 OpOperand *init = loop.getTiedLoopInit(arg);
111 Value next = loop.getTiedLoopYieldedValue(arg)->get();
112 auto add = next.getDefiningOp<arith::AddIOp>();
113 if (!init || !add || (add.getLhs() != arg && add.getRhs() != arg))
114 return 1;
115 Value step = add.getLhs() == arg ? add.getRhs() : add.getLhs();
116 return std::gcd(knownDivisor(init->get(), depth + 1),
117 knownDivisor(step, depth + 1));
118 }
119 Operation *d = v.getDefiningOp();
120 if (isa<arith::AddIOp, arith::SubIOp>(d))
121 return std::gcd(knownDivisor(d->getOperand(0), depth + 1),
122 knownDivisor(d->getOperand(1), depth + 1));
123 if (isa<arith::MulIOp>(d))
124 return mulCapped(knownDivisor(d->getOperand(0), depth + 1),
125 knownDivisor(d->getOperand(1), depth + 1));
126 if (isa<arith::IndexCastOp, arith::IndexCastUIOp>(d))
127 return knownDivisor(d->getOperand(0), depth + 1);
128 if (auto ap = dyn_cast<affine::AffineApplyOp>(d))
129 return exprDivisor(ap.getAffineMap().getResult(0), ap.getMapOperands(),
130 ap.getAffineMap().getNumDims(), depth);
131 return 1;
132}
133
134/// Returns the trip count of `loop` if it is static.
135static std::optional<int64_t> staticTrips(scf::ForOp loop) {
136 std::optional<APInt> n = loop.getStaticTripCount();
137 return n ? std::optional<int64_t>(n->getSExtValue()) : std::nullopt;
138}
139
140/// Returns the trip count of `loop` if it is static, otherwise 2: a loop
141/// whose trip count is only known at run time is assumed to repeat.
142static int64_t tripsOrTwo(scf::ForOp loop) {
143 return staticTrips(loop).value_or(2);
144}
145
146/// A read of a whole tile from an aie.buffer.
147struct TileRead {
148 vector::TransferReadOp read;
149 AIE::BufferOp buf;
150};
151
152/// Returns the read that `conv` converts if it reads a contiguous,
153/// tile-aligned 8x8 tile of an identity-layout aie.buffer.
154static std::optional<TileRead> getTileRead(ToBFP16Op conv) {
155 VectorType srcTy = conv.getSource().getType();
156 if (srcTy.getNumElements() != kTile)
157 return std::nullopt;
158 Value src = conv.getSource();
159 while (auto sc = src.getDefiningOp<vector::ShapeCastOp>())
160 src = sc.getSource();
161 auto read = src.getDefiningOp<vector::TransferReadOp>();
162 if (!read || read.getMask() || !read.getPermutationMap().isMinorIdentity())
163 return std::nullopt;
164 if (llvm::any_of(read.getInBoundsValues(), [](bool b) { return !b; }))
165 return std::nullopt;
166 auto memTy = dyn_cast<MemRefType>(read.getBase().getType());
167 VectorType vecTy = read.getVectorType();
168 if (!memTy || !memTy.hasStaticShape() || !memTy.getLayout().isIdentity() ||
169 vecTy.getNumElements() != kTile)
170 return std::nullopt;
171 // Contiguous: all vector dims but the outermost cover the corresponding
172 // memref dims entirely.
173 int64_t vr = vecTy.getRank(), mr = memTy.getRank();
174 if (vr > mr)
175 return std::nullopt;
176 for (int64_t i = 1; i < vr; ++i)
177 if (vecTy.getDimSize(i) != memTy.getDimSize(mr - vr + i))
178 return std::nullopt;
179 AIE::BufferOp buf = rootBuffer(read.getBase());
180 if (!buf)
181 return std::nullopt;
182 auto bufTy = cast<MemRefType>(buf.getType());
183 if (!bufTy.getLayout().isIdentity() || !bufTy.getElementType().isBF16() ||
184 bufTy.getNumElements() % kTile)
185 return std::nullopt;
186 // Tile-aligned: the element offset is a multiple of the tile size.
187 ArrayRef<int64_t> shape = memTy.getShape();
188 int64_t stride = 1, div = kMaxDiv;
189 for (int64_t i = mr - 1; i >= 0; --i) {
190 div = std::gcd(div, mulCapped(knownDivisor(read.getIndices()[i]), stride));
191 stride *= shape[i];
192 }
193 if (div % kTile)
194 return std::nullopt;
195 return TileRead{read, buf};
196}
197
198/// Builds the element offset of `read` in its identity-layout memref.
199static Value linearOffset(OpBuilder &b, Location loc,
200 vector::TransferReadOp read) {
201 auto memTy = cast<MemRefType>(read.getBase().getType());
202 Value off = arith::ConstantIndexOp::create(b, loc, 0);
203 int64_t stride = 1;
204 for (int64_t i = memTy.getRank() - 1; i >= 0; --i) {
205 Value s = arith::ConstantIndexOp::create(b, loc, stride);
206 off = arith::AddIOp::create(
207 b, loc, off,
208 arith::MulIOp::create(b, loc, read.getIndices()[i], s).getResult());
209 stride *= memTy.getDimSize(i);
210 }
211 return off;
212}
213
214/// The locks that guard a buffer: for each DMA buffer descriptor that moves
215/// it, the lock acquired last before it and the lock released first after
216/// it, along the descriptor chain (blocks joined by aie.next_bd). If another
217/// core uses the buffer, any lock may guard it.
218struct BufferLocks {
219 DenseSet<Value> locks;
220 bool any = false;
221
222 bool contains(Value lock) const { return any || locks.contains(lock); }
223};
224
225static BufferLocks bufferLocks(AIE::BufferOp buf, Operation *core) {
226 BufferLocks bl;
227 SmallVector<Value> work = {buf.getBuffer()};
228 while (!work.empty()) {
229 Value v = work.pop_back_val();
230 for (Operation *user : v.getUsers()) {
231 if (isa<ViewLikeOpInterface>(user))
232 work.push_back(user->getResult(0));
233 else if (auto c = user->getParentOfType<AIE::CoreOp>(); c && c != core)
234 bl.any = true;
235 }
236 }
237 auto dev = buf->getParentOfType<AIE::DeviceOp>();
238 if (!dev)
239 return bl;
240 // The chain's next and previous descriptor blocks.
241 auto next = [](Block *b) -> Block * {
242 auto n = dyn_cast<AIE::NextBDOp>(b->getTerminator());
243 return n ? n.getDest() : nullptr;
244 };
245 auto prev = [&](Block *b) -> Block * {
246 for (Block *p : b->getPredecessors())
247 if (next(p) == b)
248 return p;
249 return nullptr;
250 };
251 // The first lock op that `want` accepts from `bd` on, backward or forward
252 // along the chain.
253 auto scan = [&](AIE::DMABDOp bd, bool forward,
254 function_ref<bool(AIE::UseLockOp)> want) -> Value {
255 Block *blk = bd->getBlock();
256 Operation *op = forward ? bd->getNextNode() : bd->getPrevNode();
257 for (unsigned n = 0; blk && n < 64; ++n) {
258 for (; op; op = forward ? op->getNextNode() : op->getPrevNode())
259 if (auto ul = dyn_cast<AIE::UseLockOp>(op); ul && want(ul))
260 return ul.getLock();
261 blk = forward ? next(blk) : prev(blk);
262 if (blk)
263 op = forward ? &blk->front() : &blk->back();
264 }
265 return Value();
266 };
267 dev.walk([&](AIE::DMABDOp bd) {
268 if (rootBuffer(bd.getBuffer()) != buf)
269 return;
270 for (Value lock : {scan(bd, /*forward=*/false,
271 [](AIE::UseLockOp ul) {
272 return ul.acquire() || ul.acquireGE();
273 }),
274 scan(bd, /*forward=*/true,
275 [](AIE::UseLockOp ul) { return ul.release(); })})
276 if (lock)
277 bl.locks.insert(lock);
278 });
279 return bl;
280}
281
282/// MLIR's local alias analysis, which also knows that aie.buffer ops (which
283/// declare no allocation effect) are distinct memory: from each other and
284/// from allocations.
285class BufferAliasAnalysis : public LocalAliasAnalysis {
286protected:
287 AliasResult aliasImpl(Value lhs, Value rhs) override {
288 AliasResult r = LocalAliasAnalysis::aliasImpl(lhs, rhs);
289 if (!r.isMay())
290 return r;
291 auto root = [](Value v) {
292 while (auto view = v.getDefiningOp<ViewLikeOpInterface>())
293 v = view.getViewSource();
294 return v;
295 };
296 Operation *a = root(lhs).getDefiningOp(), *b = root(rhs).getDefiningOp();
297 auto isBuffer = [](Operation *op) {
298 return isa_and_nonnull<AIE::BufferOp>(op);
299 };
300 auto isMemory = [](Operation *op) {
301 return isa_and_nonnull<AIE::BufferOp, memref::AllocOp, memref::AllocaOp,
302 memref::GetGlobalOp>(op);
303 };
304 if (a != b && (isBuffer(a) || isBuffer(b)) && isMemory(a) && isMemory(b))
305 return AliasResult::NoAlias;
306 return r;
307 }
308};
309
310/// Returns true if `op` itself may write or free memory that `mem` views
311/// (the ops inside it are checked on their own).
312static bool mayWrite(Operation *op, Value mem) {
313 if (op->hasTrait<OpTrait::HasRecursiveMemoryEffects>())
314 return false;
315 return BufferAliasAnalysis().getModRef(op, mem).isMod();
316}
317
318/// Returns true if `op` may modify `buf`: it writes memory that may alias it,
319/// has unknown effects, or acquires a lock of a DMA that fills `buf`.
320static bool mayChange(Operation *op, Value mem, const BufferLocks &locks) {
321 if (auto ul = dyn_cast<AIE::UseLockOp>(op))
322 return (ul.acquire() || ul.acquireGE()) && locks.contains(ul.getLock());
323 return mayWrite(op, mem);
324}
325
326static bool loopMayChange(scf::ForOp loop, Value mem,
327 const BufferLocks &locks) {
328 return loop.getBody()
329 ->walk([&](Operation *op) {
330 return mayChange(op, mem, locks) ? WalkResult::interrupt()
331 : WalkResult::advance();
332 })
333 .wasInterrupted();
334}
335
336/// Returns how often one execution of `loop` executes `op`.
337static int64_t runsPerExecution(Operation *op, scf::ForOp loop) {
338 int64_t n = 1;
339 for (auto l = op->getParentOfType<scf::ForOp>(); l;
340 l = l->getParentOfType<scf::ForOp>()) {
341 n = mulCapped(n, tripsOrTwo(l));
342 if (l == loop)
343 break;
344 }
345 return n;
346}
347
348/// Returns true if the tile's buffers, its core's stack and `extra` more
349/// bytes fit in the tile's local memory.
350static bool fitsInCoreMemory(AIE::BufferOp buf, int64_t extra) {
351 auto dev = buf->getParentOfType<AIE::DeviceOp>();
352 auto tile = buf.getTile().getDefiningOp<AIE::TileOp>();
353 if (!dev || !tile)
354 return false;
355 int64_t bytes = extra;
356 dev.walk([&](AIE::BufferOp b) {
357 if (b.getTile() == buf.getTile())
358 bytes += b.getAllocationSize();
359 });
360 dev.walk([&](AIE::CoreOp core) {
361 if (core.getTile() == buf.getTile())
362 bytes += core.getEffectiveStackSize();
363 });
364 return bytes <= int64_t(dev.getTargetModel().getLocalMemorySize());
365}
366
367/// Returns the index `v` as an affine expression whose symbols are the values
368/// in `syms`. Values that are not affine in others become new symbols.
369static AffineExpr toExpr(Value v, SmallVectorImpl<Value> &syms, int depth = 0) {
370 MLIRContext *ctx = v.getContext();
371 if (std::optional<int64_t> c = getConstantIntValue(v))
372 return getAffineConstantExpr(*c, ctx);
373 if (depth < 12) {
374 if (auto ap = v.getDefiningOp<affine::AffineApplyOp>()) {
375 AffineMap m = ap.getAffineMap();
376 ValueRange ops = ap.getMapOperands();
377 SmallVector<AffineExpr> dims, symbols;
378 for (unsigned i = 0; i < m.getNumDims(); ++i)
379 dims.push_back(toExpr(ops[i], syms, depth + 1));
380 for (unsigned i = 0; i < m.getNumSymbols(); ++i)
381 symbols.push_back(toExpr(ops[m.getNumDims() + i], syms, depth + 1));
382 return m.getResult(0).replaceDimsAndSymbols(dims, symbols);
383 }
384 if (auto add = v.getDefiningOp<arith::AddIOp>())
385 return toExpr(add.getLhs(), syms, depth + 1) +
386 toExpr(add.getRhs(), syms, depth + 1);
387 if (auto mul = v.getDefiningOp<arith::MulIOp>()) {
388 if (std::optional<int64_t> c = getConstantIntValue(mul.getRhs()))
389 return toExpr(mul.getLhs(), syms, depth + 1) * *c;
390 if (std::optional<int64_t> c = getConstantIntValue(mul.getLhs()))
391 return toExpr(mul.getRhs(), syms, depth + 1) * *c;
392 }
393 }
394 auto it = llvm::find(syms, v);
395 if (it == syms.end()) {
396 syms.push_back(v);
397 it = std::prev(syms.end());
398 }
399 return getAffineSymbolExpr(it - syms.begin(), ctx);
400}
401
402/// Splits `v` into a value plus a constant.
403static std::pair<Value, int64_t> splitConstant(Value v) {
404 int64_t c = 0;
405 while (auto add = v.getDefiningOp<arith::AddIOp>()) {
406 if (std::optional<int64_t> x = getConstantIntValue(add.getRhs())) {
407 c += *x;
408 v = add.getLhs();
409 } else if (std::optional<int64_t> x = getConstantIntValue(add.getLhs())) {
410 c += *x;
411 v = add.getRhs();
412 } else {
413 break;
414 }
415 }
416 return {v, c};
417}
418
419/// Evaluates `exprs` for every combination of values of `syms`, which must all
420/// be induction variables of loops with static bounds. Returns nullopt if
421/// that is not the case or if there are too many combinations.
422static std::optional<SmallVector<SmallVector<int64_t>>>
423valuesOver(ArrayRef<AffineExpr> exprs, ArrayRef<Value> syms) {
424 SmallVector<SmallVector<int64_t>> ranges;
425 int64_t total = 1;
426 for (Value v : syms) {
427 auto arg = dyn_cast<BlockArgument>(v);
428 auto loop =
429 arg ? dyn_cast<scf::ForOp>(arg.getOwner()->getParentOp()) : nullptr;
430 if (!loop || loop.getInductionVar() != arg)
431 return std::nullopt;
432 std::optional<int64_t> lb = getConstantIntValue(loop.getLowerBound());
433 std::optional<int64_t> st = getConstantIntValue(loop.getStep());
434 std::optional<int64_t> n = staticTrips(loop);
435 if (!lb || !st || !n || *n <= 0 || *n > 4096 / total)
436 return std::nullopt;
437 total *= *n;
438 SmallVector<int64_t> r;
439 for (int64_t i = 0; i < *n; ++i)
440 r.push_back(*lb + i * *st);
441 ranges.push_back(std::move(r));
442 }
443 SmallVector<SmallVector<int64_t>> out;
444 SmallVector<size_t> at(syms.size(), 0);
445 for (int64_t n = 0; n < total; ++n) {
446 SmallVector<AffineExpr> vals;
447 for (size_t i = 0; i < syms.size(); ++i)
448 vals.push_back(
449 getAffineConstantExpr(ranges[i][at[i]], syms[i].getContext()));
450 SmallVector<int64_t> row;
451 for (AffineExpr e : exprs) {
452 auto c = dyn_cast<AffineConstantExpr>(
453 simplifyAffineExpr(e.replaceSymbols(vals), 0, 0));
454 if (!c)
455 return std::nullopt;
456 row.push_back(c.getValue());
457 }
458 out.push_back(std::move(row));
459 for (size_t i = 0; i < syms.size(); ++i) {
460 if (++at[i] < ranges[i].size())
461 break;
462 at[i] = 0;
463 }
464 }
465 return out;
466}
467
468/// The order of the T blocks in a bfp16 copy. A loop of K iterations that
469/// reads r tiles per iteration, d tiles apart, and advances s tiles per
470/// iteration, reads tile t = s*k + d*i + rest as block rest*r*K + r*k + i, so
471/// it reads the blocks in order. With s = 0, tile t is block t.
472struct Layout {
473 int64_t s = 0, K = 1, d = 1, r = 1, T = 0;
474
475 bool operator==(const Layout &o) const {
476 return s == o.s && K == o.K && d == o.d && r == o.r && T == o.T;
477 }
478 bool identity() const { return s == 0; }
479
480 /// Returns the (stride, extent) of the lower and the higher of the two
481 /// digits of t that the loop walks.
482 std::pair<std::pair<int64_t, int64_t>, std::pair<int64_t, int64_t>>
483 digits() const {
484 std::pair<int64_t, int64_t> k = {s, K}, i = {d, r};
485 return s < d ? std::pair(k, i) : std::pair(i, k);
486 }
487
488 static std::optional<Layout> make(int64_t s, int64_t K, int64_t d, int64_t r,
489 int64_t T) {
490 Layout l{s, K, d, r, T};
491 if (s <= 0 || K <= 0 || d <= 0 || r <= 0 || T <= 0)
492 return std::nullopt;
493 auto [lo, hi] = l.digits();
494 if (hi.first % (lo.first * lo.second) || T % (hi.first * hi.second))
495 return std::nullopt;
496 return l;
497 }
498
499 /// Builds the block index of tile `t`.
500 Value block(OpBuilder &b, Location loc, Value t) const {
501 if (identity())
502 return t;
503 auto c = [&](int64_t v) -> Value {
504 return arith::ConstantIndexOp::create(b, loc, v);
505 };
506 auto div = [&](Value x, int64_t v) -> Value {
507 return v == 1 ? x : arith::DivUIOp::create(b, loc, x, c(v)).getResult();
508 };
509 auto rem = [&](Value x, int64_t v) -> Value {
510 return arith::RemUIOp::create(b, loc, x, c(v));
511 };
512 auto mul = [&](Value x, int64_t v) -> Value {
513 return v == 1 ? x : arith::MulIOp::create(b, loc, x, c(v)).getResult();
514 };
515 auto add = [&](Value x, Value y) -> Value {
516 return arith::AddIOp::create(b, loc, x, y);
517 };
518 auto [lo, hi] = digits();
519 int64_t m = hi.first / (lo.first * lo.second);
520 Value k = rem(div(t, s), K), i = rem(div(t, d), r);
521 Value rest =
522 add(rem(t, lo.first), mul(add(rem(div(t, lo.first * lo.second), m),
523 mul(div(t, hi.first * hi.second), m)),
524 lo.first));
525 return add(mul(rest, r * K), add(mul(k, r), i));
526 }
527};
528
529/// A tile read at an iter_arg index that starts at `init` and advances by
530/// `step` tiles every iteration of `loop`.
531struct SteppedRead {
532 scf::ForOp loop;
533 Value init;
534 int64_t step;
535 int64_t trips;
536};
537
538static std::optional<SteppedRead> steppedRead(vector::TransferReadOp rd) {
539 auto loop = dyn_cast<scf::ForOp>(rd->getParentOp());
540 if (!loop || rd.getIndices().size() != 1)
541 return std::nullopt;
542 auto arg = dyn_cast<BlockArgument>(rd.getIndices()[0]);
543 if (!arg || arg.getOwner() != loop.getBody() || arg.getArgNumber() == 0)
544 return std::nullopt;
545 auto [base, c] = splitConstant(loop.getTiedLoopYieldedValue(arg)->get());
546 std::optional<int64_t> trips = staticTrips(loop);
547 if (base != arg || c <= 0 || c % kTile || !trips || *trips <= 0)
548 return std::nullopt;
549 return SteppedRead{loop, loop.getTiedLoopInit(arg)->get(), c / kTile, *trips};
550}
551
552/// Reads of one buffer in one loop that can share a load stream. Each read is
553/// paired with its position among the r blocks of an iteration.
554struct Stream {
555 scf::ForOp loop;
556 SmallVector<std::pair<vector::TransferReadOp, int64_t>> reads;
557 Value init; // Element index of the first tile.
558};
559
560/// Picks the block order for a copy of T tiles so that a loop advancing
561/// through `reads` reads consecutive blocks, and returns the streams this
562/// enables.
563static std::pair<Layout, SmallVector<Stream>>
564chooseLayout(ArrayRef<vector::TransferReadOp> reads, int64_t T) {
565 llvm::MapVector<Operation *, SmallVector<vector::TransferReadOp>> byLoop;
566 for (vector::TransferReadOp rd : reads)
567 if (std::optional<SteppedRead> sr = steppedRead(rd))
568 byLoop[sr->loop].push_back(rd);
569 std::optional<Layout> chosen;
570 SmallVector<Stream> streams;
571 for (auto &[loopOp, rds] : byLoop) {
572 SteppedRead first = *steppedRead(rds.front());
573 SmallVector<Value> syms;
574 SmallVector<AffineExpr> exprs;
575 bool ok = true;
576 for (vector::TransferReadOp rd : rds) {
577 SteppedRead sr = *steppedRead(rd);
578 ok &= sr.step == first.step;
579 exprs.push_back(toExpr(sr.init, syms));
580 }
581 if (!ok)
582 continue;
583 std::optional<SmallVector<SmallVector<int64_t>>> vals =
584 valuesOver(exprs, syms);
585 if (!vals)
586 continue;
587 // Each read must be at a fixed tile offset from the first one.
588 SmallVector<int64_t> off;
589 for (size_t j = 0; j < rds.size(); ++j) {
590 int64_t o = (*vals)[0][j] - (*vals)[0][0];
591 for (auto &row : *vals)
592 ok &= row[j] - row[0] == o && row[j] % kTile == 0;
593 off.push_back(o / kTile);
594 }
595 int64_t lo = *llvm::min_element(off);
596 SmallVector<int64_t> distinct;
597 for (int64_t &o : off) {
598 o -= lo;
599 if (!llvm::is_contained(distinct, o))
600 distinct.push_back(o);
601 }
602 llvm::sort(distinct);
603 int64_t r = distinct.size(), d = r > 1 ? distinct[1] : 1;
604 for (int64_t j = 0; j < r; ++j)
605 ok &= distinct[j] == j * d;
606 if (!ok || r > 4)
607 continue;
608 std::optional<Layout> layout =
609 Layout::make(first.step, first.trips, d, r, T);
610 if (!layout || (chosen && !(*chosen == *layout)))
611 continue;
612 // Every entry into the loop must start at the first block of a group.
613 int64_t lowest = 0;
614 for (size_t j = 0; j < rds.size(); ++j)
615 if (off[j] == 0)
616 lowest = j;
617 for (auto &row : *vals) {
618 int64_t t = row[lowest] / kTile;
619 ok &= t >= 0 && t < T && (t / layout->s) % layout->K == 0 &&
620 (t / layout->d) % layout->r == 0;
621 }
622 if (!ok)
623 continue;
624 chosen = layout;
625 Stream st{cast<scf::ForOp>(loopOp), {}, steppedRead(rds[lowest])->init};
626 for (size_t j = 0; j < rds.size(); ++j)
627 st.reads.push_back({rds[j], off[j] / d});
628 streams.push_back(std::move(st));
629 }
630 if (!chosen)
631 return {Layout{0, 1, 1, 1, T}, {}};
632 return {*chosen, std::move(streams)};
633}
634
635/// Returns the number of load streams already carried by `loop`.
636static int64_t loadStreams(scf::ForOp loop) {
637 int64_t n = 0;
638 for (Operation &op : *loop.getBody())
639 if (auto pop = dyn_cast<FifoLdPopBFP16Op>(op))
640 if (auto arg = dyn_cast<BlockArgument>(pop.getAddr()))
641 n += arg.getOwner() == loop.getBody();
642 return n;
643}
644
645struct HoistBFP16ConversionPattern : public OpRewritePattern<ToBFP16Op> {
646 using OpRewritePattern::OpRewritePattern;
647
648 LogicalResult matchAndRewrite(ToBFP16Op conv,
649 PatternRewriter &rewriter) const override {
650 std::optional<TileRead> tr = getTileRead(conv);
651 if (!tr)
652 return rewriter.notifyMatchFailure(conv, "not a tile read of a buffer");
653 AIE::BufferOp buf = tr->buf;
654 auto core = conv->getParentOfType<AIE::CoreOp>();
655 if (!core)
656 return rewriter.notifyMatchFailure(conv, "not in a core");
657
658 // Find the outermost loop around the conversion that does not modify
659 // the buffer.
660 BufferLocks locks = bufferLocks(buf, core);
661 scf::ForOp loop;
662 for (auto l = conv->getParentOfType<scf::ForOp>();
663 l && core->isProperAncestor(l); l = l->getParentOfType<scf::ForOp>()) {
664 if (loopMayChange(l, buf.getBuffer(), locks))
665 break;
666 loop = l;
667 }
668 if (!loop)
669 return rewriter.notifyMatchFailure(conv, "no loop keeps the buffer");
670
671 // Collect the conversions of the buffer's tiles in that loop. Only
672 // operands of matmuls whose other operand is already loaded as bfp16
673 // blocks are considered, so that the matmul needs no conversion at all.
674 auto partnered = [](ToBFP16Op c) {
675 return !c->use_empty() && llvm::all_of(c->getUses(), [&](OpOperand &u) {
676 auto mm = dyn_cast<MatMulBFP16Op_AIE2P>(u.getOwner());
677 if (!mm)
678 return false;
679 Value other = u.getOperandNumber() < 2 ? mm.getRhsMantissas()
680 : mm.getLhsMantissas();
681 return isa_and_nonnull<LoadBFP16Op, FifoLdPopBFP16Op>(
682 other.getDefiningOp());
683 });
684 };
685 if (!partnered(conv))
686 return rewriter.notifyMatchFailure(conv, "the other operand converted");
687 SmallVector<std::pair<ToBFP16Op, vector::TransferReadOp>> group;
688 int64_t runs = 0;
689 loop.getBody()->walk([&](ToBFP16Op c) {
690 if (c.getTranspose() != conv.getTranspose() || !partnered(c))
691 return;
692 std::optional<TileRead> t = getTileRead(c);
693 if (!t || t->buf != buf || !loop->isAncestor(t->read))
694 return;
695 group.push_back({c, t->read});
696 runs = std::min(kMaxDiv, runs + runsPerExecution(c, loop));
697 });
698 // The copy is built each time the loop starts, at about the cost of one
699 // conversion per tile, so require at least two conversions per tile in
700 // one execution of the loop.
701 auto bufTy = cast<MemRefType>(buf.getType());
702 int64_t tiles = bufTy.getNumElements() / kTile;
703 if (runs < 2 * tiles)
704 return rewriter.notifyMatchFailure(conv, "too few conversions per tile");
705 if (!fitsInCoreMemory(buf, tiles * (kTile + kExpBytes)))
706 return rewriter.notifyMatchFailure(conv, "no room for the bfp16 copy");
707
708 // The copy holds one bfp16 block per tile, in the order the loops read
709 // them.
710 Location loc = conv.getLoc();
711 Attribute space = bufTy.getMemorySpace();
712 Type i8 = rewriter.getI8Type(), i32 = rewriter.getI32Type();
713 Type addrTy = fifoAddrType(rewriter.getContext());
714 auto stateTy = VectorType::get({32}, i32);
715 auto mantTy = VectorType::get({kTile}, i8);
716 auto expTy = VectorType::get({kExpBytes}, i8);
717 AIE::BufferOp copy;
718 {
719 OpBuilder::InsertionGuard g(rewriter);
720 rewriter.setInsertionPointAfter(buf);
721 std::string base =
722 (buf.getSymName() ? buf.getSymName()->str() : std::string("buf")) +
723 "_bfp16";
724 DenseSet<StringRef> taken;
725 if (auto dev = buf->getParentOfType<AIE::DeviceOp>())
726 dev.walk([&](Operation *op) {
727 if (auto sym = op->getAttrOfType<StringAttr>(
728 SymbolTable::getSymbolAttrName()))
729 taken.insert(sym.getValue());
730 });
731 std::string name = base;
732 for (int i = 0; taken.contains(name); ++i)
733 name = base + "_" + std::to_string(i);
734 copy = AIE::BufferOp::create(
735 rewriter, buf.getLoc(),
736 MemRefType::get({tiles * (kTile + kExpBytes)}, i8, nullptr, space),
737 buf.getTile(), rewriter.getStringAttr(name));
738 }
739 SmallVector<vector::TransferReadOp> reads;
740 for (auto &[c, rd] : group)
741 if (!llvm::is_contained(reads, rd))
742 reads.push_back(rd);
743 auto [layout, streams] = chooseLayout(reads, tiles);
744 auto cIdx = [&](OpBuilder &b, Location l, int64_t v) -> Value {
745 return arith::ConstantIndexOp::create(b, l, v);
746 };
747 auto blockOffset = [&](OpBuilder &b, Location l, Value t) -> Value {
748 return arith::MulIOp::create(b, l, layout.block(b, l, t),
749 cIdx(b, l, kTile + kExpBytes));
750 };
751
752 // Before the loop, convert every tile and write the blocks in order
753 // through a store stream. The loop nest follows the layout's digits so
754 // that tile indices are affine in the induction variables.
755 rewriter.setInsertionPoint(loop);
756 SmallVector<ReassociationIndices> all(1);
757 for (int64_t i = 0; i < bufTy.getRank(); ++i)
758 all[0].push_back(i);
759 Value flat = bufTy.getRank() == 1 ? Value(buf.getBuffer())
760 : memref::CollapseShapeOp::create(
761 rewriter, loc, buf.getBuffer(), all)
762 .getResult();
763 SmallVector<std::pair<int64_t, int64_t>> nest; // (extent, tile stride)
764 if (layout.identity()) {
765 nest.push_back({tiles, 1});
766 } else {
767 auto [lo, hi] = layout.digits();
768 int64_t m = hi.first / (lo.first * lo.second);
769 nest.push_back({tiles / (hi.first * hi.second), hi.first * hi.second});
770 nest.push_back({m, lo.first * lo.second});
771 nest.push_back({lo.first, 1});
772 nest.push_back({layout.K, layout.s});
773 nest.push_back({layout.r, layout.d});
774 }
775 // Handle U tiles per innermost iteration and read them all before the
776 // first store; later reads are not moved above the stores.
777 while (nest.size() > 1 && nest.back().first == 1)
778 nest.pop_back();
779 int64_t inner = nest.back().first;
780 int64_t U = inner % 4 == 0 ? 4 : inner % 2 == 0 ? 2 : 1;
781 Value bfZero = arith::ConstantOp::create(
782 rewriter, loc, rewriter.getZeroAttr(rewriter.getBF16Type()));
783 auto tileTy = VectorType::get({kTile}, rewriter.getBF16Type());
784 VectorType convTy = conv.getSource().getType();
785 UnitAttr transpose = conv.getTransposeAttr();
786 std::function<SmallVector<Value>(OpBuilder &, Location, unsigned, Value,
787 ValueRange)>
788 build = [&](OpBuilder &b, Location l, unsigned level, Value t,
789 ValueRange st) -> SmallVector<Value> {
790 if (level == nest.size()) {
791 int64_t stride = nest.back().second;
792 SmallVector<Value> tileVals;
793 for (int64_t u = 0; u < U; ++u) {
794 Value tu = arith::AddIOp::create(b, l, t, cIdx(b, l, u * stride));
795 Value at = arith::MulIOp::create(b, l, tu, cIdx(b, l, kTile));
796 tileVals.push_back(
797 vector::TransferReadOp::create(b, l, tileTy, flat, ValueRange{at},
798 bfZero, ArrayRef<bool>{true}));
799 }
800 SmallVector<Value> cur(st.begin(), st.end());
801 for (Value v : tileVals) {
802 auto c = ToBFP16Op::create(
803 b, l, mantTy, expTy, vector::ShapeCastOp::create(b, l, convTy, v),
804 transpose);
805 auto push = FifoStPushBFP16Op::create(
806 b, l, addrTy, stateTy, i32, cur[0], cur[1], cur[2],
807 c.getMantissas(), c.getExponents());
808 cur = SmallVector<Value>(push->getResults());
809 }
810 return cur;
811 }
812 auto [extent, stride] = nest[level];
813 bool last = level + 1 == nest.size();
814 int64_t trips = last ? extent / U : extent;
815 int64_t step = last ? stride * U : stride;
816 if (trips == 1)
817 return build(b, l, level + 1, t, st);
818 auto nloop = scf::ForOp::create(
819 b, l, cIdx(b, l, 0), cIdx(b, l, trips), cIdx(b, l, 1), st,
820 [&](OpBuilder &ib, Location il, Value iv, ValueRange ist) {
821 Value ti = arith::AddIOp::create(
822 ib, il, t,
823 arith::MulIOp::create(ib, il, iv, cIdx(ib, il, step)));
824 scf::YieldOp::create(ib, il, build(ib, il, level + 1, ti, ist));
825 });
826 return SmallVector<Value>(nloop.getResults());
827 };
828 auto start = FifoStartOp::create(rewriter, loc, addrTy, stateTy, i32,
829 copy.getBuffer(), cIdx(rewriter, loc, 0));
830 (void)build(rewriter, loc, 0, cIdx(rewriter, loc, 0),
831 ValueRange(start->getResults()));
832
833 // Replaces the conversions of `rd` with the block (m, e).
834 auto setBFP16 = [&](vector::TransferReadOp rd, Value m, Value e) {
835 for (auto &[c, r] : group)
836 if (r == rd) {
837 c.getMantissas().replaceAllUsesWith(m);
838 c.getExponents().replaceAllUsesWith(e);
839 }
840 };
841 // Read through load streams where possible, at most two per loop (one per
842 // load FIFO). The pops of an iteration are emitted together; a fill
843 // provides enough data for the next 8 pops.
844 SmallPtrSet<Operation *, 16> streamed;
845 for (Stream &st : streams) {
846 if (loadStreams(st.loop) >= 2)
847 continue;
848 rewriter.setInsertionPoint(st.loop);
849 Location l = st.loop.getLoc();
850 Value t0 = arith::DivUIOp::create(rewriter, l, st.init,
851 cIdx(rewriter, l, kTile));
852 auto begin =
853 FifoStartOp::create(rewriter, l, addrTy, stateTy, i32,
854 copy.getBuffer(), blockOffset(rewriter, l, t0));
855 int64_t r = layout.r;
856 (void)st.loop.replaceWithAdditionalYields(
857 rewriter, begin->getResults(), /*replaceInitOperandUsesInLoop=*/false,
858 [&](OpBuilder &b, Location, ArrayRef<BlockArgument> args) {
859 Operation *first = st.reads.front().first;
860 for (auto &[rd, _] : st.reads)
861 if (rd->isBeforeInBlock(first))
862 first = rd;
863 OpBuilder::InsertionGuard g(b);
864 b.setInsertionPoint(first);
865 Value addr = args[0], state = args[1], count = args[2];
866 for (int64_t i = 0; i < r; ++i) {
867 auto pop = FifoLdPopBFP16Op::create(
868 b, first->getLoc(), addrTy, stateTy, i32, mantTy, expTy, addr,
869 state, count,
870 r % 8 == 0 && i % 8 ? b.getUnitAttr() : UnitAttr());
871 for (auto &[rd, place] : st.reads)
872 if (place == i)
873 setBFP16(rd, pop.getMantissas(), pop.getExponents());
874 addr = pop.getNext();
875 state = pop.getStateOut();
876 count = pop.getCountOut();
877 }
878 return SmallVector<Value>{addr, state, count};
879 });
880 for (auto &[rd, _] : st.reads)
881 streamed.insert(rd);
882 }
883 // Load the remaining blocks individually.
884 for (vector::TransferReadOp rd : reads) {
885 if (streamed.contains(rd))
886 continue;
887 rewriter.setInsertionPoint(rd);
888 Location l = rd.getLoc();
889 Value t = arith::DivUIOp::create(
890 rewriter, l, linearOffset(rewriter, l, rd), cIdx(rewriter, l, kTile));
891 auto ld =
892 LoadBFP16Op::create(rewriter, l, mantTy, expTy, copy.getBuffer(),
893 blockOffset(rewriter, l, t));
894 setBFP16(rd, ld.getMantissas(), ld.getExponents());
895 }
896 for (auto &[c, rd] : group)
897 rewriter.eraseOp(c);
898 return success();
899 }
900};
901
902/// Returns the loop whose induction variable is `v` if it runs from 0 to `n`
903/// with step 1.
904static scf::ForOp loopOver(Value v, int64_t n) {
905 auto arg = dyn_cast<BlockArgument>(v);
906 auto loop =
907 arg ? dyn_cast<scf::ForOp>(arg.getOwner()->getParentOp()) : nullptr;
908 if (!loop || loop.getInductionVar() != arg ||
909 getConstantIntValue(loop.getLowerBound()) != 0 ||
910 getConstantIntValue(loop.getStep()) != 1 ||
911 getConstantIntValue(loop.getUpperBound()) != n)
912 return nullptr;
913 return loop;
914}
915
916/// A loop nest that decodes the bfp16ebs8 blocks in `bytes` ([..., 8, 9]) into
917/// the bf16 tiles of `tiles` ([..., 8, 8]):
918/// tiles[i..., r, c] = bf16(sitofp(bytes[p(i...), r, c + 1]) *
919/// bitcast<f32>((zext(bytes[p(i...), r, 0]) - 6) <<
920/// 23))
921/// for all elements of `tiles`. `bytes` may have extra unit dims, indexed
922/// with 0. Dim j of the block grid is dim perm[j] of the tile grid.
923struct Decode {
924 AIE::BufferOp bytes, tiles;
925 scf::ForOp nest;
926 SmallVector<unsigned> perm;
927 SmallVector<int64_t> blocks;
928};
929
930static std::optional<Decode> matchDecode(memref::StoreOp st) {
931 auto trunc = st.getValueToStore().getDefiningOp<arith::TruncFOp>();
932 auto mul = trunc ? trunc.getIn().getDefiningOp<arith::MulFOp>() : nullptr;
933 if (!mul || !trunc.getType().isBF16())
934 return std::nullopt;
935 arith::SIToFPOp man;
936 arith::BitcastOp scale;
937 for (auto [x, y] : {std::pair(mul.getLhs(), mul.getRhs()),
938 std::pair(mul.getRhs(), mul.getLhs())})
939 if (x.getDefiningOp<arith::SIToFPOp>() &&
940 y.getDefiningOp<arith::BitcastOp>()) {
941 man = x.getDefiningOp<arith::SIToFPOp>();
942 scale = y.getDefiningOp<arith::BitcastOp>();
943 }
944 if (!man)
945 return std::nullopt;
946 auto shl = scale.getIn().getDefiningOp<arith::ShLIOp>();
947 auto sub = shl ? shl.getLhs().getDefiningOp<arith::SubIOp>() : nullptr;
948 auto ext = sub ? sub.getLhs().getDefiningOp<arith::ExtUIOp>() : nullptr;
949 auto expLd = ext ? ext.getIn().getDefiningOp<memref::LoadOp>() : nullptr;
950 auto manLd = man.getIn().getDefiningOp<memref::LoadOp>();
951 if (!expLd || !manLd || getConstantIntValue(shl.getRhs()) != 23 ||
952 getConstantIntValue(sub.getRhs()) != 6 || !scale.getType().isF32() ||
953 !man.getType().isF32() || expLd.getMemref() != manLd.getMemref())
954 return std::nullopt;
955 auto bBuf = expLd.getMemref().getDefiningOp<AIE::BufferOp>();
956 auto xBuf = st.getMemref().getDefiningOp<AIE::BufferOp>();
957 if (!bBuf || !xBuf)
958 return std::nullopt;
959 auto bt = cast<MemRefType>(bBuf.getType());
960 auto xt = cast<MemRefType>(xBuf.getType());
961 int64_t n = xt.getRank(), nb = bt.getRank();
962 if (!bt.hasStaticShape() || !xt.hasStaticShape() ||
963 !bt.getLayout().isIdentity() || !xt.getLayout().isIdentity() || nb < n ||
964 n < 3 || !bt.getElementType().isInteger(8) ||
965 !xt.getElementType().isBF16() || bt.getDimSize(nb - 2) != 8 ||
966 bt.getDimSize(nb - 1) != 9 || xt.getDimSize(n - 2) != 8 ||
967 xt.getDimSize(n - 1) != 8)
968 return std::nullopt;
969 // Each store index must be the induction variable of a loop over the whole
970 // corresponding dim.
971 SmallVector<scf::ForOp> loops;
972 for (int64_t i = 0; i < n; ++i) {
973 scf::ForOp l = loopOver(st.getIndices()[i], xt.getDimSize(i));
974 if (!l || llvm::is_contained(loops, l))
975 return std::nullopt;
976 loops.push_back(l);
977 }
978 scf::ForOp nest = loops.front();
979 for (scf::ForOp l : loops)
980 if (l->isProperAncestor(nest))
981 nest = l;
982 // The nest is removed, so nothing may use what it returns.
983 if (!nest->use_empty())
984 return std::nullopt;
985 // Both loads read the same block and row: the exponent at column 0 and the
986 // mantissa at column c + 1.
987 Decode d{bBuf, xBuf, nest, {}, {}};
988 ValueRange tileIdx = st.getIndices().take_front(n - 2);
989 for (int64_t j = 0; j < nb - 2; ++j) {
990 Value v = manLd.getIndices()[j];
991 if (expLd.getIndices()[j] != v)
992 return std::nullopt;
993 if (bt.getDimSize(j) == 1 && getConstantIntValue(v) == 0)
994 continue;
995 auto it = llvm::find(tileIdx, v);
996 if (it == tileIdx.end() ||
997 llvm::is_contained(d.perm, unsigned(it - tileIdx.begin())))
998 return std::nullopt;
999 d.perm.push_back(it - tileIdx.begin());
1000 d.blocks.push_back(bt.getDimSize(j));
1001 }
1002 if (d.perm.size() != size_t(n - 2) ||
1003 manLd.getIndices()[nb - 2] != st.getIndices()[n - 2] ||
1004 expLd.getIndices()[nb - 2] != st.getIndices()[n - 2] ||
1005 getConstantIntValue(expLd.getIndices()[nb - 1]) != 0)
1006 return std::nullopt;
1007 SmallVector<Value> syms;
1008 AffineExpr off = toExpr(manLd.getIndices()[nb - 1], syms) -
1009 toExpr(st.getIndices()[n - 1], syms);
1010 auto c =
1011 dyn_cast<AffineConstantExpr>(simplifyAffineExpr(off, 0, syms.size()));
1012 if (!c || c.getValue() != 1)
1013 return std::nullopt;
1014 // Nothing else in the nest may access memory.
1015 WalkResult clean = nest->walk([&](Operation *op) {
1016 if (op == st || op == manLd || op == expLd || isPure(op) ||
1017 isa<scf::ForOp, scf::YieldOp>(op))
1018 return WalkResult::advance();
1019 return WalkResult::interrupt();
1020 });
1021 if (clean.wasInterrupted())
1022 return std::nullopt;
1023 return d;
1024}
1025
1026/// Builds the index of the block in `d.bytes` that holds tile `t`.
1027static Value blockOf(OpBuilder &b, Location loc, Decode &d, Value t) {
1028 auto xt = cast<MemRefType>(d.tiles.getType());
1029 auto c = [&](int64_t v) -> Value {
1030 return arith::ConstantIndexOp::create(b, loc, v);
1031 };
1032 int64_t n = xt.getRank() - 2;
1033 SmallVector<Value> dig(n);
1034 for (int64_t i = n - 1; i >= 0; --i) {
1035 dig[i] =
1036 i == 0 ? t : arith::RemUIOp::create(b, loc, t, c(xt.getDimSize(i)));
1037 if (i)
1038 t = arith::DivUIOp::create(b, loc, t, c(xt.getDimSize(i)));
1039 }
1040 Value blk;
1041 for (size_t j = 0; j < d.blocks.size(); ++j)
1042 blk = blk ? arith::AddIOp::create(
1043 b, loc, arith::MulIOp::create(b, loc, blk, c(d.blocks[j])),
1044 dig[d.perm[j]])
1045 .getResult()
1046 : dig[d.perm[j]];
1047 return blk;
1048}
1049
1050/// Makes matmuls load the bfp16 blocks that a core would otherwise decode into
1051/// bf16 tiles, when the tiles are only read whole by untransposed
1052/// conversions. The decode loop and the tile buffer are removed, and the
1053/// release of the block buffer's lock moves after the last read.
1054struct ReadDecodedBFP16Pattern : public OpRewritePattern<memref::StoreOp> {
1055 using OpRewritePattern::OpRewritePattern;
1056
1057 LogicalResult matchAndRewrite(memref::StoreOp st,
1058 PatternRewriter &rewriter) const override {
1059 std::optional<Decode> d = matchDecode(st);
1060 if (!d)
1061 return rewriter.notifyMatchFailure(st, "not a bfp16 decode");
1062 auto core = st->getParentOfType<AIE::CoreOp>();
1063 BufferLocks bytesLocks = bufferLocks(d->bytes, core);
1064 BufferLocks tileLocks = bufferLocks(d->tiles, core);
1065 if (bytesLocks.any || bytesLocks.locks.empty() || tileLocks.any ||
1066 !tileLocks.locks.empty() || d->tiles.getInitialValue())
1067 return rewriter.notifyMatchFailure(st, "not DMA bytes into core tiles");
1068
1069 // Every other use of the tiles must be a whole-tile read, after the
1070 // decode, that only untransposed conversions use.
1071 SmallVector<Operation *> views;
1072 SmallVector<std::pair<ToBFP16Op, vector::TransferReadOp>> convs;
1073 SmallVector<Value> work = {d->tiles.getBuffer()};
1074 Block *blk = d->nest->getBlock();
1075 Operation *last = d->nest;
1076 while (!work.empty()) {
1077 Value v = work.pop_back_val();
1078 for (Operation *user : v.getUsers()) {
1079 if (user == st.getOperation())
1080 continue;
1081 if (isa<memref::CollapseShapeOp, memref::ExpandShapeOp, memref::CastOp>(
1082 user)) {
1083 views.push_back(user);
1084 work.push_back(user->getResult(0));
1085 continue;
1086 }
1087 auto rd = dyn_cast<vector::TransferReadOp>(user);
1088 Operation *anc = rd ? blk->findAncestorOpInBlock(*rd) : nullptr;
1089 if (!anc || !d->nest->isBeforeInBlock(anc))
1090 return rewriter.notifyMatchFailure(st, "another use of the tiles");
1091 for (Operation *u : rd->getUsers()) {
1092 while (isa<vector::ShapeCastOp>(u) && u->hasOneUse())
1093 u = *u->getUsers().begin();
1094 auto conv = dyn_cast<ToBFP16Op>(u);
1095 std::optional<TileRead> tr = conv ? getTileRead(conv) : std::nullopt;
1096 if (!conv || conv.getTranspose() || !tr || tr->read != rd)
1097 return rewriter.notifyMatchFailure(st, "a tile read not converted");
1098 convs.push_back({conv, rd});
1099 }
1100 if (last->isBeforeInBlock(anc))
1101 last = anc;
1102 }
1103 }
1104 if (convs.empty())
1105 return rewriter.notifyMatchFailure(st, "no conversions");
1106
1107 // Find the release of the block buffer after the decode. It has to move
1108 // after the last read, so no other use of its locks may come between.
1109 AIE::UseLockOp release;
1110 for (Operation *op = d->nest->getNextNode(); op; op = op->getNextNode()) {
1111 bool usesLock = op->walk([&](AIE::UseLockOp ul) {
1112 return bytesLocks.contains(ul.getLock())
1113 ? WalkResult::interrupt()
1114 : WalkResult::advance();
1115 }).wasInterrupted();
1116 auto ul = dyn_cast<AIE::UseLockOp>(op);
1117 if (ul && ul.release() && bytesLocks.contains(ul.getLock()) && !release)
1118 release = ul;
1119 else if (usesLock)
1120 return rewriter.notifyMatchFailure(st, "the bytes' lock in between");
1121 bool writes = op->walk([&](Operation *o) {
1122 return mayChange(o, d->bytes.getBuffer(), {})
1123 ? WalkResult::interrupt()
1124 : WalkResult::advance();
1125 }).wasInterrupted();
1126 if (writes)
1127 return rewriter.notifyMatchFailure(st, "the bytes may change");
1128 if (op == last)
1129 break;
1130 }
1131
1132 // Load the blocks from a flat view of the block buffer.
1133 rewriter.setInsertionPoint(d->nest);
1134 Location loc = st.getLoc();
1135 auto bt = cast<MemRefType>(d->bytes.getType());
1136 SmallVector<ReassociationIndices> all(1);
1137 for (int64_t i = 0; i < bt.getRank(); ++i)
1138 all[0].push_back(i);
1139 Value flat = memref::CollapseShapeOp::create(rewriter, loc,
1140 d->bytes.getBuffer(), all);
1141 // One load per tile read, where the read is, which all its conversions
1142 // use.
1143 DenseMap<Operation *, LoadBFP16Op> loads;
1144 for (auto [conv, rd] : convs) {
1145 LoadBFP16Op &ld = loads[rd];
1146 if (!ld) {
1147 rewriter.setInsertionPointAfter(rd);
1148 Location l = rd.getLoc();
1149 Value t = arith::DivUIOp::create(
1150 rewriter, l, linearOffset(rewriter, l, rd),
1151 arith::ConstantIndexOp::create(rewriter, l, kTile));
1152 Value off = arith::MulIOp::create(
1153 rewriter, l, blockOf(rewriter, l, *d, t),
1154 arith::ConstantIndexOp::create(rewriter, l, kTile + kExpBytes));
1155 ld = LoadBFP16Op::create(rewriter, l, conv.getMantissas().getType(),
1156 conv.getExponents().getType(), flat, off);
1157 }
1158 rewriter.replaceOp(conv, ld.getResults());
1159 }
1160 if (release && release->isBeforeInBlock(last))
1161 rewriter.moveOpAfter(release, last);
1162 rewriter.eraseOp(d->nest);
1163 // Erase the reads and their shape casts, the views and the tile buffer
1164 // once they are unused.
1165 for (auto &[rd, ld] : loads) {
1166 for (Operation *u : llvm::make_early_inc_range(rd->getUsers()))
1167 if (u->use_empty())
1168 rewriter.eraseOp(u);
1169 if (rd->use_empty())
1170 rewriter.eraseOp(rd);
1171 }
1172 for (Operation *v : llvm::reverse(views))
1173 if (v->use_empty())
1174 rewriter.eraseOp(v);
1175 if (d->tiles->use_empty())
1176 rewriter.eraseOp(d->tiles);
1177 return success();
1178 }
1179};
1180
1181/// Evaluates index computations in `scope`, given the values in `env` for
1182/// induction variables and iter_args. Supports constants, integer arithmetic
1183/// and affine.apply; anything else is unknown.
1184struct TripEvaluator {
1185 Operation *scope;
1186 DenseMap<Value, int64_t> env;
1187
1188 std::optional<int64_t> eval(Value v, int depth = 0) {
1189 if (auto it = env.find(v); it != env.end())
1190 return it->second;
1191 if (std::optional<int64_t> c = getConstantIntValue(v))
1192 return c;
1193 Operation *d = v.getDefiningOp();
1194 if (!d || depth > 32 || !scope->isAncestor(d))
1195 return std::nullopt;
1196 auto bin = [&](auto f) -> std::optional<int64_t> {
1197 std::optional<int64_t> a = eval(d->getOperand(0), depth + 1);
1198 std::optional<int64_t> b = eval(d->getOperand(1), depth + 1);
1199 if (!a || !b)
1200 return std::nullopt;
1201 return f(*a, *b);
1202 };
1203 if (isa<arith::AddIOp>(d))
1204 return bin(
1205 [](int64_t a, int64_t b) -> std::optional<int64_t> { return a + b; });
1206 if (isa<arith::SubIOp>(d))
1207 return bin(
1208 [](int64_t a, int64_t b) -> std::optional<int64_t> { return a - b; });
1209 if (isa<arith::MulIOp>(d))
1210 return bin(
1211 [](int64_t a, int64_t b) -> std::optional<int64_t> { return a * b; });
1212 if (isa<arith::DivUIOp, arith::DivSIOp>(d))
1213 return bin([](int64_t a, int64_t b) -> std::optional<int64_t> {
1214 return b > 0 && a >= 0 ? std::optional<int64_t>(a / b) : std::nullopt;
1215 });
1216 if (isa<arith::RemUIOp, arith::RemSIOp>(d))
1217 return bin([](int64_t a, int64_t b) -> std::optional<int64_t> {
1218 return b > 0 && a >= 0 ? std::optional<int64_t>(a % b) : std::nullopt;
1219 });
1220 if (isa<arith::IndexCastOp, arith::IndexCastUIOp>(d))
1221 return eval(d->getOperand(0), depth + 1);
1222 if (auto ap = dyn_cast<affine::AffineApplyOp>(d)) {
1223 SmallVector<int64_t> vals;
1224 for (Value o : ap.getMapOperands()) {
1225 std::optional<int64_t> x = eval(o, depth + 1);
1226 if (!x)
1227 return std::nullopt;
1228 vals.push_back(*x);
1229 }
1230 AffineMap m = ap.getAffineMap();
1231 SmallVector<AffineExpr> dims, syms;
1232 MLIRContext *ctx = ap.getContext();
1233 for (unsigned i = 0; i < m.getNumDims(); ++i)
1234 dims.push_back(getAffineConstantExpr(vals[i], ctx));
1235 for (unsigned i = 0; i < m.getNumSymbols(); ++i)
1236 syms.push_back(getAffineConstantExpr(vals[m.getNumDims() + i], ctx));
1237 auto c = dyn_cast<AffineConstantExpr>(
1238 m.getResult(0).replaceDimsAndSymbols(dims, syms));
1239 return c ? std::optional<int64_t>(c.getValue()) : std::nullopt;
1240 }
1241 return std::nullopt;
1242 }
1243};
1244
1245/// Returns the values from outside `loop` that the loop body's `vals` depend
1246/// on, directly or through the values the loop carries.
1247static SmallVector<Value> valuesFromOutside(scf::ForOp loop, ValueRange vals) {
1248 auto yield = cast<scf::YieldOp>(loop.getBody()->getTerminator());
1249 SmallVector<Value> outside, work(vals.begin(), vals.end());
1250 DenseSet<Value> seen;
1251 while (!work.empty()) {
1252 Value v = work.pop_back_val();
1253 if (!seen.insert(v).second)
1254 continue;
1255 auto arg = dyn_cast<BlockArgument>(v);
1256 if (arg && arg.getOwner() == loop.getBody()) {
1257 if (OpOperand *init = loop.getTiedLoopInit(arg)) {
1258 outside.push_back(init->get());
1259 work.push_back(
1260 yield.getOperand(arg.getArgNumber() - loop.getNumInductionVars()));
1261 }
1262 } else if (Operation *d = v.getDefiningOp(); d && loop->isAncestor(d)) {
1263 work.append(d->getOperands().begin(), d->getOperands().end());
1264 } else {
1265 outside.push_back(v);
1266 }
1267 }
1268 return outside;
1269}
1270
1271/// Returns the induction variables of the loops around `loop` that `vals`
1272/// depend on, or nullopt if they depend on other block arguments.
1273static std::optional<SmallVector<Value>> outerIVs(scf::ForOp loop,
1274 ArrayRef<Value> vals) {
1275 SmallVector<Value> ivs, work(vals.begin(), vals.end());
1276 DenseSet<Value> seen;
1277 while (!work.empty()) {
1278 Value v = work.pop_back_val();
1279 if (!seen.insert(v).second)
1280 continue;
1281 if (auto arg = dyn_cast<BlockArgument>(v)) {
1282 auto l = dyn_cast<scf::ForOp>(arg.getOwner()->getParentOp());
1283 if (!l || l.getInductionVar() != arg || !l->isProperAncestor(loop))
1284 return std::nullopt;
1285 ivs.push_back(v);
1286 } else if (Operation *d = v.getDefiningOp()) {
1287 work.append(d->getOperands().begin(), d->getOperands().end());
1288 }
1289 }
1290 return ivs;
1291}
1292
1293/// Turns the r loads of one buffer in a loop body into one load stream when
1294/// iteration k loads blocks n + r*k ... n + r*k + r - 1 in program order. n
1295/// may depend on the induction variables of loops with static bounds around
1296/// the loop; the order is checked for each of their values.
1297/// The stream starts empty before the loop; its first pop fills it.
1298struct BFP16LoadStreamPattern : public OpRewritePattern<scf::ForOp> {
1299 using OpRewritePattern::OpRewritePattern;
1300
1301 LogicalResult matchAndRewrite(scf::ForOp loop,
1302 PatternRewriter &rewriter) const override {
1303 std::optional<int64_t> lb = getConstantIntValue(loop.getLowerBound());
1304 std::optional<int64_t> st = getConstantIntValue(loop.getStep());
1305 std::optional<int64_t> n = staticTrips(loop);
1306 if (!lb || !st || !n || *n <= 0)
1307 return rewriter.notifyMatchFailure(loop, "trips not known");
1308 int64_t trips = *n;
1309 // Group the loads in the body by buffer. Loads or streams in nested
1310 // regions are not handled.
1311 llvm::MapVector<Value, SmallVector<LoadBFP16Op>> byBase;
1312 for (Operation &op : *loop.getBody())
1313 if (auto ld = dyn_cast<LoadBFP16Op>(op))
1314 byBase[ld.getBase()].push_back(ld);
1315 bool nested = false;
1316 loop.getBody()->walk([&](Operation *op) {
1317 if (op->getParentOp() != loop &&
1318 isa<LoadBFP16Op, FifoStartOp, FifoLdPopBFP16Op>(op))
1319 nested = true;
1320 });
1321 if (byBase.empty() || nested)
1322 return rewriter.notifyMatchFailure(loop, "no loads to stream");
1323
1324 // Evaluate each load's offset in every iteration to check the order, for
1325 // each value of the outer induction variables the offsets depend on.
1326 Operation *scope = loop->getParentOfType<AIE::CoreOp>();
1327 if (!scope)
1328 scope = loop->getParentOp();
1329 SmallVector<Value> offsets;
1330 for (auto &[base, loads] : byBase)
1331 for (LoadBFP16Op ld : loads)
1332 offsets.push_back(ld.getOffset());
1333 std::optional<SmallVector<Value>> ivs =
1334 outerIVs(loop, valuesFromOutside(loop, offsets));
1335 std::optional<SmallVector<SmallVector<int64_t>>> combos;
1336 if (ivs) {
1337 SmallVector<AffineExpr> syms;
1338 for (unsigned i = 0; i < ivs->size(); ++i)
1339 syms.push_back(getAffineSymbolExpr(i, loop.getContext()));
1340 combos = valuesOver(syms, *ivs);
1341 }
1342 // Each offset is evaluated once per trip and outer combination.
1343 constexpr int64_t kMaxEvals = 1 << 16;
1344 if (combos && (int64_t(offsets.size()) * trips > kMaxEvals ||
1345 int64_t(combos->size()) >
1346 kMaxEvals / (int64_t(offsets.size()) * trips)))
1347 combos.reset();
1348 SmallVector<std::pair<Value, SmallVector<LoadBFP16Op>>> streams;
1349 for (auto &[base, loads] : byBase) {
1350 // The pops read ahead of the loads they replace, so the loop must not
1351 // change the buffer.
1352 AIE::BufferOp root = rootBuffer(base);
1353 BufferLocks locks;
1354 locks.any = true;
1355 if (root)
1356 locks = bufferLocks(root, loop->getParentOfType<AIE::CoreOp>());
1357 bool changes =
1358 loop.getBody()
1359 ->walk([&](Operation *op) {
1360 auto ul = dyn_cast<AIE::UseLockOp>(op);
1361 bool c = ul ? (ul.acquire() || ul.acquireGE()) &&
1362 locks.contains(ul.getLock())
1363 : mayWrite(op, base);
1364 return c ? WalkResult::interrupt() : WalkResult::advance();
1365 })
1366 .wasInterrupted();
1367 if (!loop.isDefinedOutsideOfLoop(base) || !combos || changes)
1368 continue;
1369 int64_t r = loads.size();
1370 bool ok = true;
1371 for (ArrayRef<int64_t> combo : *combos) {
1372 DenseMap<Value, int64_t> outer;
1373 for (auto [iv, x] : llvm::zip(*ivs, combo))
1374 outer[iv] = x;
1375 TripEvaluator ev{scope, outer};
1376 // Track the iter_arg values from one iteration to the next.
1377 SmallVector<std::optional<int64_t>> carried;
1378 for (Value init : loop.getInitArgs())
1379 carried.push_back(ev.eval(init));
1380 std::optional<int64_t> start;
1381 for (int64_t k = 0; k < trips && ok; ++k) {
1382 ev.env = outer;
1383 ev.env[loop.getInductionVar()] = *lb + k * *st;
1384 for (auto [arg, val] : llvm::zip(loop.getRegionIterArgs(), carried))
1385 if (val)
1386 ev.env[arg] = *val;
1387 for (int64_t j = 0; j < r && ok; ++j) {
1388 std::optional<int64_t> off = ev.eval(loads[j].getOffset());
1389 if (!off || *off % (kTile + kExpBytes)) {
1390 ok = false;
1391 break;
1392 }
1393 if (!start)
1394 start = *off;
1395 ok = *off == *start + (kTile + kExpBytes) * (r * k + j);
1396 }
1397 auto yield = cast<scf::YieldOp>(loop.getBody()->getTerminator());
1398 for (auto [i, y] : llvm::enumerate(yield.getOperands()))
1399 carried[i] = ev.eval(y);
1400 }
1401 if (!ok || !start) {
1402 ok = false;
1403 break;
1404 }
1405 }
1406 if (ok)
1407 streams.push_back({base, loads});
1408 }
1409 // A core has two load FIFOs.
1410 if (streams.empty() || int64_t(streams.size()) + loadStreams(loop) > 2)
1411 return rewriter.notifyMatchFailure(loop, "no streams, or too many");
1412
1413 Location loc = loop.getLoc();
1414 rewriter.setInsertionPoint(loop);
1415 SmallVector<Value> inits;
1416 for (auto &[base, loads] : streams) {
1417 // The first offset, computed before the loop as in its first iteration.
1418 IRMapping first;
1419 first.map(loop.getInductionVar(), loop.getLowerBound());
1420 first.map(loop.getRegionIterArgs(), loop.getInitArgs());
1421 std::function<Value(Value)> before = [&](Value v) -> Value {
1422 if (Value m = first.lookupOrNull(v))
1423 return m;
1424 Operation *d = v.getDefiningOp();
1425 if (!d || !loop->isAncestor(d))
1426 return v;
1427 for (Value o : d->getOperands())
1428 before(o);
1429 return rewriter.clone(*d, first)->getResult(
1430 cast<OpResult>(v).getResultNumber());
1431 };
1432 auto begin = FifoStartOp::create(
1433 rewriter, loc, fifoAddrType(rewriter.getContext()),
1434 VectorType::get({32}, rewriter.getI32Type()), rewriter.getI32Type(),
1435 base, before(loads.front().getOffset()));
1436 inits.append(begin->getResults().begin(), begin->getResults().end());
1437 }
1438 (void)loop.replaceWithAdditionalYields(
1439 rewriter, inits, /*replaceInitOperandUsesInLoop=*/false,
1440 [&](OpBuilder &b, Location l, ArrayRef<BlockArgument> args) {
1441 SmallVector<Value> yields;
1442 for (auto [s, entry] : llvm::enumerate(streams)) {
1443 Value addr = args[3 * s], state = args[3 * s + 1],
1444 count = args[3 * s + 2];
1445 // Emit the pops of an iteration together. A fill provides enough
1446 // data for the next 8 pops, so with a multiple of 8 blocks per
1447 // iteration only every eighth pop fills; otherwise every pop
1448 // fills.
1449 int64_t r = entry.second.size();
1450 Operation *first = entry.second.front();
1451 for (LoadBFP16Op ld : entry.second)
1452 if (ld->isBeforeInBlock(first))
1453 first = ld;
1454 OpBuilder::InsertionGuard g(b);
1455 b.setInsertionPoint(first);
1456 for (auto [j, ld] : llvm::enumerate(entry.second)) {
1457 auto pop = FifoLdPopBFP16Op::create(
1458 b, ld.getLoc(), fifoAddrType(b.getContext()), state.getType(),
1459 b.getI32Type(), ld.getMantissas().getType(),
1460 ld.getExponents().getType(), addr, state, count,
1461 r % 8 == 0 && j % 8 ? b.getUnitAttr() : UnitAttr());
1462 addr = pop.getNext();
1463 state = pop.getStateOut();
1464 count = pop.getCountOut();
1465 ld.getMantissas().replaceAllUsesWith(pop.getMantissas());
1466 ld.getExponents().replaceAllUsesWith(pop.getExponents());
1467 }
1468 yields.append({addr, state, count});
1469 }
1470 return yields;
1471 });
1472 for (auto &[base, loads] : streams)
1473 for (LoadBFP16Op ld : loads)
1474 rewriter.eraseOp(ld);
1475 return success();
1476 }
1477};
1478
1479} // namespace
1480
1482 RewritePatternSet &patterns) {
1483 patterns.add<ReadDecodedBFP16Pattern>(patterns.getContext());
1484}
1485
1487 RewritePatternSet &patterns) {
1488 patterns.add<HoistBFP16ConversionPattern>(patterns.getContext());
1489}
1490
1492 RewritePatternSet &patterns) {
1493 patterns.add<BFP16LoadStreamPattern>(patterns.getContext());
1494}
void populateHoistBFP16ConversionPatterns(mlir::RewritePatternSet &patterns)
void populateBFP16LoadStreamPatterns(mlir::RewritePatternSet &patterns)
void populateReadDecodedBFP16Patterns(mlir::RewritePatternSet &patterns)