1//===- TileAllocation.cpp - Allocate SME ZA tiles -------------------------===//
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 transform allocates SME tiles at the 'func.func' op level for ArmSME
10// operations. It roughly implements a linear scan register allocator, similar
11// to the one outlined in [1], but with simplifications and assumptions made for
12// our use case. Note that this is a greedy allocator (so it may not always find
13// the most optimal allocation of tiles).
14//
15// The allocator operates at the CF dialect level. It is the responsibility of
16// users to ensure the IR has been lowered to CF before invoking the tile
17// allocator.
18//
19// The 128-bit tiles overlap with other element tiles as follows (see section
20// B2.3.2 of SME spec [2]):
21//
22// Tile Overlaps
23// ---------------------------------------------------------------------------
24// ZA0.B ZA0.Q, ZA1.Q, ZA2.Q, ZA3.Q, ZA4.Q, ZA5.Q, ZA6.Q, ZA7.Q, ZA8.Q,
25// ZA9.Q, ZA10.Q, ZA11.Q, ZA12.Q, ZA13.Q, ZA14.Q, ZA15.Q
26// ZA0.H ZA0.Q, ZA2.Q, ZA4.Q, ZA6.Q, ZA8.Q, ZA10.Q, ZA12.Q, ZA14.Q
27// ZA1.H ZA1.Q, ZA3.Q, ZA5.Q, ZA7.Q, ZA9.Q, ZA11.Q, ZA13.Q, ZA15.Q
28// ZA0.S ZA0.Q, ZA4.Q, ZA8.Q, ZA12.Q
29// ZA1.S ZA1.Q, ZA5.Q, ZA9.Q, ZA13.Q
30// ZA2.S ZA2.Q, ZA6.Q, ZA10.Q, ZA14.Q
31// ZA3.S ZA3.Q, ZA7.Q, ZA11.Q, ZA15.Q
32// ZA0.D ZA0.Q, ZA8.Q
33// ZA1.D ZA1.Q, ZA9.Q
34// ZA2.D ZA2.Q, ZA10.Q
35// ZA3.D ZA3.Q, ZA11.Q
36// ZA4.D ZA4.Q, ZA12.Q
37// ZA5.D ZA5.Q, ZA13.Q
38// ZA6.D ZA6.Q, ZA14.Q
39// ZA7.D ZA7.Q, ZA15.Q
40//
41// [1] "Linear Scan Register Allocation in the Context of SSA Form and Register
42// Constraints" (Hanspeter Mössenböck and Michael Pfeiffer)
43// https://link.springer.com/content/pdf/10.1007/3-540-45937-5_17.pdf
44// [2] https://developer.arm.com/documentation/ddi0616/aa
45//
46//===----------------------------------------------------------------------===//
47
48#include "mlir/Analysis/Liveness.h"
49#include "mlir/Analysis/TopologicalSortUtils.h"
50#include "mlir/Dialect/ArmSME/IR/ArmSME.h"
51#include "mlir/Dialect/ArmSME/Transforms/Passes.h"
52#include "mlir/Dialect/ArmSME/Transforms/Transforms.h"
53#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
54#include "mlir/Dialect/Func/IR/FuncOps.h"
55#include "llvm/ADT/IntervalMap.h"
56#include "llvm/ADT/SmallVectorExtras.h"
57#include "llvm/ADT/TypeSwitch.h"
58
59namespace mlir::arm_sme {
60#define GEN_PASS_DEF_TESTTILEALLOCATION
61#include "mlir/Dialect/ArmSME/Transforms/Passes.h.inc"
62} // namespace mlir::arm_sme
63
64using namespace mlir;
65using namespace mlir::arm_sme;
66
67namespace {
68
69enum class TileMask : unsigned {
70 // clang-format off
71 kZA0B = 0xffff, // 1111 1111 1111 1111
72
73 kZA0H = 0xaaaa, // 1010 1010 1010 1010
74 kZA1H = 0x5555, // 0101 0101 0101 0101
75
76 kZA0S = 0x8888, // 1000 1000 1000 1000
77 kZA1S = 0x4444, // 0100 0100 0100 0100
78 kZA2S = 0x2222, // 0010 0010 0010 0010
79 kZA3S = 0x1111, // 0001 0001 0001 0001
80
81 kZA0D = 0x8080, // 1000 0000 1000 0000
82 kZA1D = 0x4040, // 0100 0000 0100 0000
83 kZA2D = 0x2020, // 0010 0000 0010 0000
84 kZA3D = 0x1010, // 0001 0000 0001 0000
85 kZA4D = 0x808, // 0000 1000 0000 1000
86 kZA5D = 0x404, // 0000 0100 0000 0100
87 kZA6D = 0x202, // 0000 0010 0000 0010
88 kZA7D = 0x101, // 0000 0001 0000 0001
89
90 kZA0Q = 0x8000, // 1000 0000 0000 0000
91 kZA1Q = 0x4000, // 0100 0000 0000 0000
92 kZA2Q = 0x2000, // 0010 0000 0000 0000
93 kZA3Q = 0x1000, // 0001 0000 0000 0000
94 kZA4Q = 0x800, // 0000 1000 0000 0000
95 kZA5Q = 0x400, // 0000 0100 0000 0000
96 kZA6Q = 0x200, // 0000 0010 0000 0000
97 kZA7Q = 0x100, // 0000 0001 0000 0000
98 kZA8Q = 0x80, // 0000 0000 1000 0000
99 kZA9Q = 0x40, // 0000 0000 0100 0000
100 kZA10Q = 0x20, // 0000 0000 0010 0000
101 kZA11Q = 0x10, // 0000 0000 0001 0000
102 kZA12Q = 0x8, // 0000 0000 0000 1000
103 kZA13Q = 0x4, // 0000 0000 0000 0100
104 kZA14Q = 0x2, // 0000 0000 0000 0010
105 kZA15Q = 0x1, // 0000 0000 0000 0001
106
107 kNone = 0x0, // 0000 0000 0000 0000
108 // clang-format on
109
110 LLVM_MARK_AS_BITMASK_ENUM(kZA0B)
111};
112
113/// Returns the set of masks relevant for the given type.
114static ArrayRef<TileMask> getMasks(ArmSMETileType type) {
115 static constexpr std::array ZA_B_MASKS = {TileMask::kZA0B};
116 static constexpr std::array ZA_H_MASKS = {TileMask::kZA0H, TileMask::kZA1H};
117 static constexpr std::array ZA_S_MASKS = {TileMask::kZA0S, TileMask::kZA1S,
118 TileMask::kZA2S, TileMask::kZA3S};
119 static constexpr std::array ZA_D_MASKS = {
120 TileMask::kZA0D, TileMask::kZA1D, TileMask::kZA2D, TileMask::kZA3D,
121 TileMask::kZA4D, TileMask::kZA5D, TileMask::kZA6D, TileMask::kZA7D};
122 static constexpr std::array ZA_Q_MASKS = {
123 TileMask::kZA0Q, TileMask::kZA1Q, TileMask::kZA2Q, TileMask::kZA3Q,
124 TileMask::kZA4Q, TileMask::kZA5Q, TileMask::kZA6Q, TileMask::kZA7Q,
125 TileMask::kZA8Q, TileMask::kZA9Q, TileMask::kZA10Q, TileMask::kZA11Q,
126 TileMask::kZA12Q, TileMask::kZA13Q, TileMask::kZA14Q, TileMask::kZA15Q};
127 switch (type) {
128 case ArmSMETileType::ZAB:
129 return ZA_B_MASKS;
130 case ArmSMETileType::ZAH:
131 return ZA_H_MASKS;
132 case ArmSMETileType::ZAS:
133 return ZA_S_MASKS;
134 case ArmSMETileType::ZAD:
135 return ZA_D_MASKS;
136 case ArmSMETileType::ZAQ:
137 return ZA_Q_MASKS;
138 }
139 llvm_unreachable("unknown type in getMasks");
140}
141
142class TileAllocator {
143public:
144 /// Allocates and returns a tile ID. Fails if there are no tiles left.
145 FailureOr<unsigned> allocateTileId(ArmSMETileType tileType) {
146 auto masks = getMasks(type: tileType);
147 for (auto [tileId, tileMask] : llvm::enumerate(First&: masks)) {
148 if ((tilesInUse & tileMask) == TileMask::kNone) {
149 tilesInUse |= tileMask;
150 return tileId;
151 }
152 }
153 return failure();
154 }
155
156 /// Acquires a specific tile ID. Asserts the tile is initially free.
157 void acquireTileId(ArmSMETileType tileType, unsigned tileId) {
158 TileMask tileMask = getMasks(type: tileType)[tileId];
159 assert((tilesInUse & tileMask) == TileMask::kNone &&
160 "cannot acquire allocated tile!");
161 tilesInUse |= tileMask;
162 }
163
164 /// Releases a previously allocated tile ID.
165 void releaseTileId(ArmSMETileType tileType, unsigned tileId) {
166 TileMask tileMask = getMasks(type: tileType)[tileId];
167 assert((tilesInUse & tileMask) == tileMask &&
168 "cannot release unallocated tile!");
169 tilesInUse ^= tileMask;
170 }
171
172 /// Allocates an in-memory tile ID.
173 unsigned allocateInMemoryTileId() {
174 // Note: We never release in-memory tile IDs. We could, which may allow
175 // reusing an allocation, but as we _never_ want to spill an SME tile this
176 // is not optimized.
177 return nextInMemoryTileId++;
178 }
179
180private:
181 TileMask tilesInUse = TileMask::kNone;
182 unsigned nextInMemoryTileId = kInMemoryTileIdBase;
183};
184
185/// Add new intermediate blocks for the true and false destinations of
186/// `cf.cond_br`s that contain tile operands. This prevents spurious liveness
187/// overlaps due to copies at branches.
188///
189/// BEFORE:
190/// ```mlir
191/// cf.cond_br %cond, ^bb1(%tile: vector<[4]x[4]xf32>), ^bb2
192/// ```
193///
194/// AFTER:
195/// ```mlir
196/// cf.cond_br %cond, ^bb1_copy, ^bb2_copy
197/// ^bb1_copy:
198/// cf.br ^bb1(%tile: vector<[4]x[4]xf32>)
199/// ^bb2_copy:
200/// cf.br ^bb2
201/// ```
202void splitCondBranches(IRRewriter &rewriter, FunctionOpInterface function) {
203 SmallVector<cf::CondBranchOp> worklist;
204 function.walk(callback: [&](cf::CondBranchOp condBranch) {
205 if (llvm::any_of(Range: condBranch->getOperands(), P: [&](Value value) {
206 return isValidSMETileVectorType(type: value.getType());
207 })) {
208 worklist.push_back(Elt: condBranch);
209 }
210 });
211
212 auto insertJump = [&](Location loc, Block *source, Block *dest, auto args) {
213 rewriter.setInsertionPointToEnd(source);
214 cf::BranchOp::create(rewriter, loc, dest, args);
215 };
216
217 for (auto condBranch : worklist) {
218 auto loc = condBranch.getLoc();
219 Block *block = condBranch->getBlock();
220 auto *newTrueBranch = rewriter.splitBlock(block, before: block->end());
221 auto *newFalseBranch = rewriter.splitBlock(block, before: block->end());
222 insertJump(loc, newTrueBranch, condBranch.getTrueDest(),
223 condBranch.getTrueDestOperands());
224 insertJump(loc, newFalseBranch, condBranch.getFalseDest(),
225 condBranch.getFalseDestOperands());
226 rewriter.modifyOpInPlace(root: condBranch, callable: [&] {
227 condBranch.getFalseDestOperandsMutable().clear();
228 condBranch.getTrueDestOperandsMutable().clear();
229 condBranch.setSuccessor(block: newTrueBranch, i: 0);
230 condBranch.setSuccessor(block: newFalseBranch, i: 1);
231 });
232 }
233}
234
235/// Inserts tile copies at `cf.br` operations.
236///
237/// BEFORE:
238/// ```mlir
239/// cf.br ^bb1(%tile: vector<[4]x[4]xf32>)
240/// ```
241///
242/// AFTER:
243/// ```mlir
244/// %copy = arm_sme.copy_tile %tile : vector<[4]x[4]xf32>
245/// cf.br ^bb1(%copy: vector<[4]x[4]xf32>)
246/// ```
247void insertCopiesAtBranches(IRRewriter &rewriter,
248 FunctionOpInterface function) {
249 for (Block &block : function.getBlocks()) {
250 Operation *terminator = block.getTerminator();
251 if (!isa<cf::BranchOp>(Val: terminator))
252 continue;
253 rewriter.setInsertionPoint(terminator);
254 for (OpOperand &operand : terminator->getOpOperands()) {
255 if (isValidSMETileVectorType(type: operand.get().getType())) {
256 auto copy =
257 CopyTileOp::create(builder&: rewriter, location: terminator->getLoc(), tile: operand.get());
258 rewriter.modifyOpInPlace(root: terminator, callable: [&] { operand.assign(value: copy); });
259 }
260 }
261 }
262}
263
264/// Prepares the IR for tile allocation. It does this by first 'splitting'
265/// conditional branches (see `splitCondBranches`), then inserting tile copies
266/// at branch operations. The conditional branches are split to prevent the
267/// copies needed for them overlapping between the true and false paths of the
268/// branch (see `tile-allocation-copies.mlir` and
269/// `tile-allocation-liveness.mlir` for examples). The copies break up live
270/// ranges and ensure when moving out of SSA the semantics of the program are
271/// preserved.
272void preprocessForTileAllocation(IRRewriter &rewriter,
273 FunctionOpInterface function) {
274 splitCondBranches(rewriter, function);
275 insertCopiesAtBranches(rewriter, function);
276}
277
278/// A live range for a (collection of) tile values. A live range is built up of
279/// non-overlapping intervals [start, end) which represent parts of the program
280/// where a value in the range needs to be live (i.e. in an SME virtual tile).
281/// Note that as the intervals are non-overlapping all values within a live
282/// range can be allocated to the same SME virtual tile.
283struct LiveRange {
284 using RangeSet = llvm::IntervalMap<uint64_t, uint8_t, 16,
285 llvm::IntervalMapHalfOpenInfo<unsigned>>;
286 using Allocator = RangeSet::Allocator;
287 // Dummy value for the IntervalMap. Only the keys matter (the intervals).
288 static constexpr uint8_t kValidLiveRange = 0xff;
289
290 LiveRange(Allocator &allocator)
291 : ranges(std::make_unique<RangeSet>(args&: allocator)) {}
292
293 /// Returns true if this range overlaps with `otherRange`.
294 bool overlaps(LiveRange const &otherRange) const {
295 return llvm::IntervalMapOverlaps<RangeSet, RangeSet>(*ranges,
296 *otherRange.ranges)
297 .valid();
298 }
299
300 /// Returns true if this range is active at `point` in the program.
301 bool overlaps(uint64_t point) const {
302 return ranges->lookup(x: point) == kValidLiveRange;
303 }
304
305 /// Unions this live range with `otherRange`, aborts if the ranges overlap.
306 void unionWith(LiveRange const &otherRange) {
307 for (auto it = otherRange.ranges->begin(); it != otherRange.ranges->end();
308 ++it)
309 ranges->insert(a: it.start(), b: it.stop(), y: kValidLiveRange);
310 values.set_union(otherRange.values);
311 }
312
313 /// Inserts an interval [start, end) for `value` into this range.
314 void insert(Value value, unsigned start, unsigned end) {
315 values.insert(X: value);
316 if (start != end)
317 ranges->insert(a: start, b: end, y: kValidLiveRange);
318 }
319
320 bool empty() const { return ranges->empty(); }
321 unsigned start() const { return ranges->start(); }
322 unsigned end() const { return ranges->stop(); }
323 bool operator<(LiveRange const &other) const {
324 return start() < other.start();
325 }
326
327 ArmSMETileType getTileType() const {
328 return *getSMETileType(cast<VectorType>(Val: values[0].getType()));
329 }
330
331 /// The values contained in this live range.
332 SetVector<Value> values;
333
334 /// A set of (non-overlapping) intervals that mark where any value in `values`
335 /// is live.
336 std::unique_ptr<RangeSet> ranges;
337
338 /// The tile ID (or none) assigned to this live range.
339 std::optional<unsigned> tileId;
340};
341
342/// Number operations within a function to allow computing live ranges.
343/// Operations are numbered consecutively wihin blocks, and the blocks are
344/// topologically sorted (using forward edges). This function is only correct if
345/// all ArmSME have been converted to CF (which is asserted).
346FailureOr<DenseMap<Operation *, unsigned>>
347generateOperationNumbering(FunctionOpInterface function) {
348 unsigned index = 0;
349 SetVector<Block *> blocks =
350 getBlocksSortedByDominance(region&: function.getFunctionBody());
351 DenseMap<Operation *, unsigned> operationToIndexMap;
352 for (Block *block : blocks) {
353 index++; // We want block args to have their own number.
354 for (Operation &op : block->getOperations()) {
355 WalkResult walkResult =
356 op.walk(callback: [&](ArmSMETileOpInterface nestedOp) -> WalkResult {
357 if (&op != nestedOp.getOperation())
358 return WalkResult::interrupt();
359 return WalkResult::advance();
360 });
361 if (walkResult.wasInterrupted()) {
362 return op.emitError(message: "ArmSME tile allocation requires flattened control "
363 "flow; run -convert-scf-to-cf before this pass "
364 "(e.g. via convert-arm-sme-to-llvm pipeline)");
365 }
366 operationToIndexMap.try_emplace(Key: &op, Args: index++);
367 }
368 }
369
370 return operationToIndexMap;
371}
372
373/// Gather live ranges for SME tiles from the MLIR liveness analysis. Uses a
374/// `MapVector` (rather than a `DenseMap`) so that iteration order is
375/// deterministic (insertion order).
376MapVector<Value, LiveRange>
377gatherTileLiveRanges(DenseMap<Operation *, unsigned> const &operationToIndexMap,
378 LiveRange::Allocator &liveRangeAllocator,
379 Liveness &liveness, FunctionOpInterface function) {
380 assert(!operationToIndexMap.empty() && "expected operation numbering");
381 MapVector<Value, LiveRange> liveRanges;
382 /// Defines or updates a live range for an SME tile value. Live-ins may update
383 /// an existing live range (rather than define a new one). Note: If
384 /// `liveAtBlockEntry` is true then `firstUseOrDef` is the first operation in
385 /// the block.
386 auto defineOrUpdateValueLiveRange = [&](Value value, Operation *firstUseOrDef,
387 LivenessBlockInfo const &livenessInfo,
388 bool liveAtBlockEntry = false) {
389 if (!isValidSMETileVectorType(type: value.getType()))
390 return;
391 // Find or create a live range for `value`.
392 auto [it, _] = liveRanges.try_emplace(Key: value, Args&: liveRangeAllocator);
393 LiveRange &valueLiveRange = it->second;
394 auto *lastUseInBlock = livenessInfo.getEndOperation(value, startOperation: firstUseOrDef);
395 // Add the interval [firstUseOrDef, lastUseInBlock) to the live range.
396 unsigned startOpIdx =
397 operationToIndexMap.at(Val: firstUseOrDef) + (liveAtBlockEntry ? -1 : 0);
398 unsigned endOpIdx = operationToIndexMap.at(Val: lastUseInBlock);
399 valueLiveRange.insert(value, start: startOpIdx, end: endOpIdx);
400 };
401
402 for (Block &block : function.getBlocks()) {
403 LivenessBlockInfo const *livenessInfo = liveness.getLiveness(block: &block);
404 // Handle block arguments:
405 for (Value argument : block.getArguments())
406 defineOrUpdateValueLiveRange(argument, &block.front(), *livenessInfo,
407 /*liveAtBlockEntry=*/true);
408 // Handle live-ins:
409 for (Value liveIn : livenessInfo->in())
410 defineOrUpdateValueLiveRange(liveIn, &block.front(), *livenessInfo,
411 /*liveAtBlockEntry=*/true);
412 // Handle new definitions:
413 for (Operation &op : block) {
414 for (Value result : op.getResults())
415 defineOrUpdateValueLiveRange(result, &op, *livenessInfo);
416 }
417 }
418
419 return liveRanges;
420}
421
422/// Iterate over all predecessor tile values to a (tile) block argument.
423static void forEachPredecessorTileValue(BlockArgument blockArg,
424 function_ref<void(Value)> callback) {
425 Block *block = blockArg.getOwner();
426 unsigned argNumber = blockArg.getArgNumber();
427 for (Block *pred : block->getPredecessors()) {
428 TypeSwitch<Operation *>(pred->getTerminator())
429 .Case(caseFn: [&](cf::BranchOp branch) {
430 Value predecessorOperand = branch.getDestOperands()[argNumber];
431 callback(predecessorOperand);
432 })
433 .Case(caseFn: [&](cf::CondBranchOp condBranch) {
434 if (condBranch.getFalseDest() == block) {
435 Value predecessorOperand =
436 condBranch.getFalseDestOperands()[argNumber];
437 callback(predecessorOperand);
438 }
439 if (condBranch.getTrueDest() == block) {
440 Value predecessorOperand =
441 condBranch.getTrueDestOperands()[argNumber];
442 callback(predecessorOperand);
443 }
444 });
445 }
446}
447
448/// Coalesce live ranges where it would prevent unnecessary tile moves.
449SmallVector<LiveRange *>
450coalesceTileLiveRanges(MapVector<Value, LiveRange> &initialLiveRanges) {
451 MapVector<Value, LiveRange *> liveRanges;
452 for (auto &[value, liveRange] : initialLiveRanges) {
453 liveRanges.insert(KV: {value, &liveRange});
454 }
455
456 // Merge the live ranges of values `a` and `b` into one (if they do not
457 // overlap). After this, the values `a` and `b` will both point to the same
458 // live range (which will contain multiple values).
459 auto mergeValuesIfNonOverlapping = [&](Value a, Value b) {
460 LiveRange *aLiveRange = liveRanges.at(Key: a);
461 LiveRange *bLiveRange = liveRanges.at(Key: b);
462 if (aLiveRange != bLiveRange && !aLiveRange->overlaps(otherRange: *bLiveRange)) {
463 aLiveRange->unionWith(otherRange: *bLiveRange);
464 for (Value value : bLiveRange->values)
465 liveRanges[value] = aLiveRange;
466 }
467 };
468
469 // Merge the live ranges of new definitions with their tile operands.
470 auto unifyDefinitionsWithOperands = [&](Value value) {
471 auto armSMEOp = value.getDefiningOp<ArmSMETileOpInterface>();
472 if (!armSMEOp)
473 return;
474 for (auto operand : armSMEOp->getOperands()) {
475 if (isValidSMETileVectorType(type: operand.getType()))
476 mergeValuesIfNonOverlapping(value, operand);
477 }
478 };
479
480 // Merge the live ranges of block arguments with their predecessors.
481 auto unifyBlockArgumentsWithPredecessors = [&](Value value) {
482 auto blockArg = dyn_cast<BlockArgument>(Val&: value);
483 if (!blockArg)
484 return;
485 forEachPredecessorTileValue(blockArg, callback: [&](Value predecessorTile) {
486 mergeValuesIfNonOverlapping(blockArg, predecessorTile);
487 });
488 };
489
490 auto applyRule = [&](auto rule) {
491 llvm::for_each(llvm::make_first_range(c&: initialLiveRanges), rule);
492 };
493
494 // Unify as many live ranges as we can. This prevents unnecessary moves.
495 applyRule(unifyBlockArgumentsWithPredecessors);
496 applyRule(unifyDefinitionsWithOperands);
497
498 // Remove duplicate live range entries.
499 SetVector<LiveRange *> uniqueLiveRanges;
500 for (auto [_, liveRange] : liveRanges) {
501 if (!liveRange->empty())
502 uniqueLiveRanges.insert(X: liveRange);
503 }
504
505 // Sort the new live ranges by starting point (ready for tile allocation).
506 auto coalescedLiveRanges = uniqueLiveRanges.takeVector();
507 llvm::sort(C&: coalescedLiveRanges,
508 Comp: [](LiveRange *a, LiveRange *b) { return *a < *b; });
509 return std::move(coalescedLiveRanges);
510}
511
512/// Choose a live range to spill (via some heuristics). This picks either a live
513/// range from `overlappingRanges`, or the new live range `newRange`.
514template <typename OverlappingRangesIterator>
515LiveRange *
516chooseSpillUsingHeuristics(OverlappingRangesIterator overlappingRanges,
517 LiveRange *newRange) {
518 // Heuristic: Spill trivially copyable operations (usually free).
519 auto isTrivialSpill = [&](LiveRange &allocatedRange) {
520 return isTileTypeGreaterOrEqual(typeA: allocatedRange.getTileType(),
521 typeB: newRange->getTileType()) &&
522 allocatedRange.values.size() == 1 &&
523 isTriviallyCloneableTileOp(
524 tileOp: allocatedRange.values[0].getDefiningOp<ArmSMETileOpInterface>());
525 };
526 if (isTrivialSpill(*newRange))
527 return newRange;
528 auto trivialSpill = llvm::find_if(overlappingRanges, isTrivialSpill);
529 if (trivialSpill != overlappingRanges.end())
530 return &*trivialSpill;
531
532 // Heuristic: Spill the range that ends last (with a compatible tile type).
533 auto isSmallerTileTypeOrEndsEarlier = [](LiveRange &a, LiveRange &b) {
534 return !isTileTypeGreaterOrEqual(typeA: a.getTileType(), typeB: b.getTileType()) ||
535 a.end() < b.end();
536 };
537 LiveRange &latestEndingLiveRange =
538 *llvm::max_element(overlappingRanges, isSmallerTileTypeOrEndsEarlier);
539 if (!isSmallerTileTypeOrEndsEarlier(latestEndingLiveRange, *newRange))
540 return &latestEndingLiveRange;
541 return newRange;
542}
543
544/// Greedily allocate tile IDs to live ranges. Spill using simple heuristics.
545void allocateTilesToLiveRanges(
546 ArrayRef<LiveRange *> liveRangesSortedByStartPoint) {
547 TileAllocator tileAllocator;
548 // `activeRanges` = Live ranges that need to be in a tile at the
549 // `currentPoint` in the program.
550 SetVector<LiveRange *> activeRanges;
551 // `inactiveRanges` = Live ranges that _do not_ need to be in a tile
552 // at the `currentPoint` in the program but could become active again later.
553 // An inactive section of a live range can be seen as a 'hole' in the live
554 // range, where it is possible to reuse the live range's tile ID _before_ it
555 // has ended. By identifying 'holes', the allocator can reuse tiles more
556 // often, which helps avoid costly tile spills.
557 SetVector<LiveRange *> inactiveRanges;
558 for (LiveRange *nextRange : liveRangesSortedByStartPoint) {
559 auto currentPoint = nextRange->start();
560 // 1. Update the `activeRanges` at `currentPoint`.
561 activeRanges.remove_if(P: [&](LiveRange *activeRange) {
562 // Check for live ranges that have expired.
563 if (activeRange->end() <= currentPoint) {
564 tileAllocator.releaseTileId(tileType: activeRange->getTileType(),
565 tileId: *activeRange->tileId);
566 return true;
567 }
568 // Check for live ranges that have become inactive.
569 if (!activeRange->overlaps(point: currentPoint)) {
570 tileAllocator.releaseTileId(tileType: activeRange->getTileType(),
571 tileId: *activeRange->tileId);
572 inactiveRanges.insert(X: activeRange);
573 return true;
574 }
575 return false;
576 });
577 // 2. Update the `inactiveRanges` at `currentPoint`.
578 inactiveRanges.remove_if(P: [&](LiveRange *inactiveRange) {
579 // Check for live ranges that have expired.
580 if (inactiveRange->end() <= currentPoint) {
581 return true;
582 }
583 // Check for live ranges that have become active.
584 if (inactiveRange->overlaps(point: currentPoint)) {
585 tileAllocator.acquireTileId(tileType: inactiveRange->getTileType(),
586 tileId: *inactiveRange->tileId);
587 activeRanges.insert(X: inactiveRange);
588 return true;
589 }
590 return false;
591 });
592
593 // 3. Collect inactive live ranges that overlap with the new live range.
594 // Note: The overlap checks in steps 1 and 2 only look at the `currentPoint`
595 // whereas this checks if there is an overlap at any future point too.
596 SmallVector<LiveRange *> overlappingInactiveRanges;
597 for (LiveRange *inactiveRange : inactiveRanges) {
598 if (inactiveRange->overlaps(otherRange: *nextRange)) {
599 // We need to reserve the tile IDs of overlapping inactive ranges to
600 // prevent two (overlapping) live ranges from getting the same tile ID.
601 tileAllocator.acquireTileId(tileType: inactiveRange->getTileType(),
602 tileId: *inactiveRange->tileId);
603 overlappingInactiveRanges.push_back(Elt: inactiveRange);
604 }
605 }
606
607 // 4. Allocate a tile ID to `nextRange`.
608 auto rangeTileType = nextRange->getTileType();
609 auto tileId = tileAllocator.allocateTileId(tileType: rangeTileType);
610 if (succeeded(Result: tileId)) {
611 nextRange->tileId = *tileId;
612 } else {
613 // Create an iterator over all overlapping live ranges.
614 auto allOverlappingRanges = llvm::concat<LiveRange>(
615 Ranges: llvm::make_pointee_range(Range: activeRanges.getArrayRef()),
616 Ranges: llvm::make_pointee_range(Range&: overlappingInactiveRanges));
617 // Choose an overlapping live range to spill.
618 LiveRange *rangeToSpill =
619 chooseSpillUsingHeuristics(overlappingRanges: allOverlappingRanges, newRange: nextRange);
620 if (rangeToSpill != nextRange) {
621 // Spill an (in)active live range (so release its tile ID first).
622 tileAllocator.releaseTileId(tileType: rangeToSpill->getTileType(),
623 tileId: *rangeToSpill->tileId);
624 // This will always succeed after a spill (of an active live range).
625 nextRange->tileId = *tileAllocator.allocateTileId(tileType: rangeTileType);
626 // Remove the live range from the active/inactive sets.
627 if (!activeRanges.remove(X: rangeToSpill)) {
628 bool removed = inactiveRanges.remove(X: rangeToSpill);
629 assert(removed && "expected a range to be removed!");
630 (void)removed;
631 }
632 }
633 rangeToSpill->tileId = tileAllocator.allocateInMemoryTileId();
634 }
635
636 // 5. Insert the live range into the active ranges.
637 if (nextRange->tileId < kInMemoryTileIdBase)
638 activeRanges.insert(X: nextRange);
639
640 // 6. Release tiles reserved for inactive live ranges (in step 3).
641 for (LiveRange *range : overlappingInactiveRanges) {
642 if (*range->tileId < kInMemoryTileIdBase)
643 tileAllocator.releaseTileId(tileType: range->getTileType(), tileId: *range->tileId);
644 }
645 }
646}
647
648/// Assigns a tile ID to an MLIR value.
649void assignTileIdToValue(IRRewriter &rewriter, Value value,
650 IntegerAttr tileIdAttr) {
651 if (auto tileOp = value.getDefiningOp<ArmSMETileOpInterface>())
652 rewriter.modifyOpInPlace(root: tileOp, callable: [&] { tileOp.setTileId(tileIdAttr); });
653 for (Operation *user : value.getUsers()) {
654 if (auto tileOp = dyn_cast<ArmSMETileOpInterface>(Val: user)) {
655 // Ensure ArmSME ops that don't produce a value still get a tile ID.
656 if (!hasTileResult(tileOp))
657 rewriter.modifyOpInPlace(root: tileOp, callable: [&] { tileOp.setTileId(tileIdAttr); });
658 }
659 }
660}
661
662/// Assign tile IDs back to IR and attempt to resolve trivial tile ID conflicts.
663LogicalResult assignTileIdsAndResolveTrivialConflicts(
664 IRRewriter &rewriter, FunctionOpInterface function,
665 ArrayRef<LiveRange *> allocatedLiveRanges) {
666 for (LiveRange const *liveRange : allocatedLiveRanges) {
667 auto tileIdAttr = rewriter.getI32IntegerAttr(value: *liveRange->tileId);
668 auto isAllocatedToSameTile = [&](Value value) {
669 if (auto tileOp = value.getDefiningOp<ArmSMETileOpInterface>();
670 tileOp && tileOp.getTileId() == tileIdAttr)
671 return true;
672 return liveRange->values.contains(key: value);
673 };
674
675 /// Eliminates copies where the operand has the same tile ID.
676 auto foldRedundantCopies = [&](Value value) -> LogicalResult {
677 auto copyOp = value.getDefiningOp<CopyTileOp>();
678 if (!copyOp || !isAllocatedToSameTile(copyOp.getTile()))
679 return failure();
680 rewriter.replaceAllUsesWith(from: copyOp, to: copyOp.getTile());
681 return success();
682 };
683
684 /// Validates each predecessor to a tile block argument has been assigned
685 /// the same tile ID.
686 auto validateBlockArguments = [&](Value value) {
687 auto blockArg = dyn_cast<BlockArgument>(Val&: value);
688 if (!blockArg) {
689 // Not a block argument (nothing to validate).
690 return success();
691 }
692 bool tileMismatch = false;
693 forEachPredecessorTileValue(blockArg, callback: [&](Value predecessorTile) {
694 if (tileMismatch)
695 return;
696 if (!isAllocatedToSameTile(predecessorTile)) {
697 blockArg.getOwner()->getParentOp()->emitOpError(
698 message: "block argument not allocated to the same SME virtial tile as "
699 "predecessors");
700 tileMismatch = true;
701 }
702 });
703 return success(/*isSuccess=*/IsSuccess: !tileMismatch);
704 };
705
706 /// Attempts to resolve (trivial) tile ID conflicts.
707 auto resolveTrivialTileConflicts = [&](Value value) -> LogicalResult {
708 auto tileOp = value.getDefiningOp<ArmSMETileOpInterface>();
709 OpOperand *tileOperand = getTileOpOperand(tileOp);
710 if (!tileOperand || isAllocatedToSameTile(tileOperand->get())) {
711 // Operand already allocated to the correct tile.
712 // No conflict to resolve.
713 return success();
714 }
715 auto operandTileOp =
716 tileOperand->get().getDefiningOp<ArmSMETileOpInterface>();
717 if (!isTriviallyCloneableTileOp(tileOp: operandTileOp)) {
718 auto error =
719 tileOp.emitOpError(message: "tile operand allocated to different SME "
720 "virtial tile (move required)");
721 error.attachNote(noteLoc: tileOperand->get().getLoc())
722 << "tile operand is: " << tileOperand->get();
723 return error;
724 }
725 // Cloning prevents a move/spill (though may require recomputation).
726 rewriter.setInsertionPoint(tileOp);
727 auto clonedOp = operandTileOp.clone();
728 rewriter.modifyOpInPlace(root: clonedOp,
729 callable: [&] { clonedOp.setTileId(tileOp.getTileId()); });
730 rewriter.insert(op: clonedOp);
731 if (isa<CopyTileOp>(Val: tileOp)) {
732 rewriter.replaceAllUsesWith(from: tileOp->getResult(idx: 0),
733 to: clonedOp->getResult(idx: 0));
734 } else {
735 rewriter.modifyOpInPlace(
736 root: tileOp, callable: [&] { tileOperand->assign(value: clonedOp->getResult(idx: 0)); });
737 }
738 return success();
739 };
740
741 for (Value value : liveRange->values) {
742 // 1. Assign the tile ID to the value.
743 assignTileIdToValue(rewriter, value, tileIdAttr);
744
745 // 2. Attempt to eliminate redundant tile copies.
746 if (succeeded(Result: foldRedundantCopies(value)))
747 continue;
748
749 // 3. Validate tile block arguments.
750 if (failed(Result: validateBlockArguments(value)))
751 return failure();
752
753 // 4. Attempt to resolve (trivial) tile ID conflicts.
754 if (failed(Result: resolveTrivialTileConflicts(value)))
755 return failure();
756 }
757 }
758 return success();
759}
760
761/// Prints live ranges alongside operation names for debugging.
762void dumpLiveRanges(DenseMap<Operation *, unsigned> const &operationToIndexMap,
763 ArrayRef<LiveRange const *> liveRanges,
764 FunctionOpInterface function) {
765 llvm::errs() << "SME Tile Liveness: @" << function.getName()
766 << "\nKey:\nS - Start\nE - End\n| - Live\n";
767 for (auto [blockIdx, block] : llvm::enumerate(First&: function.getBlocks())) {
768 llvm::errs() << "^bb" << blockIdx << ":\n";
769 for (Operation &op : block.getOperations()) {
770 unsigned operationIndex = operationToIndexMap.at(Val: &op);
771 for (LiveRange const *range : liveRanges) {
772 char liveness = ' ';
773 for (auto it = range->ranges->begin(); it != range->ranges->end();
774 ++it) {
775 if (it.start() == operationIndex)
776 liveness = (liveness == 'E' ? '|' : 'S');
777 else if (it.stop() == operationIndex)
778 liveness = (liveness == 'S' ? '|' : 'E');
779 else if (operationIndex >= it.start() && operationIndex < it.stop())
780 liveness = '|';
781 }
782 llvm::errs() << liveness;
783 }
784 llvm::errs() << ' ' << op.getName() << '\n';
785 }
786 }
787 llvm::errs() << "==========\n";
788}
789
790struct TestTileAllocationPass
791 : public arm_sme::impl::TestTileAllocationBase<TestTileAllocationPass> {
792 using TestTileAllocationBase::TestTileAllocationBase;
793 void runOnOperation() override {
794 FunctionOpInterface function = getOperation();
795 if (preprocessOnly) {
796 IRRewriter rewriter(function);
797 return preprocessForTileAllocation(rewriter, function);
798 }
799 if (failed(Result: arm_sme::allocateSMETiles(function, dumpRanges: dumpTileLiveRanges)))
800 signalPassFailure();
801 }
802};
803} // namespace
804
805/// Returns true if `function` contains any ArmSME tile ops.
806static bool hasArmSMETileOps(FunctionOpInterface function) {
807 return function
808 .walk(callback: [&](ArmSMETileOpInterface) { return WalkResult::interrupt(); })
809 .wasInterrupted();
810}
811
812LogicalResult mlir::arm_sme::allocateSMETiles(FunctionOpInterface function,
813 bool dumpRanges) {
814 // Bail out early if the function has no ArmSME tile ops: there is nothing
815 // to allocate (a value not produced/consumed by such an op never gets a
816 // tile ID), so this avoids the (non-trivial) preprocessing and liveness
817 // analysis.
818 if (!hasArmSMETileOps(function))
819 return success();
820
821 LiveRange::Allocator liveRangeAllocator;
822 IRRewriter rewriter(function.getContext());
823
824 // 1. Preprocess the IR for tile allocation.
825 preprocessForTileAllocation(rewriter, function);
826
827 // 2. Gather live ranges for each ArmSME tile within the function.
828 Liveness liveness(function);
829 auto maybeOperationToIndexMap = generateOperationNumbering(function);
830 if (failed(Result: maybeOperationToIndexMap))
831 return failure();
832 auto &operationToIndexMap = *maybeOperationToIndexMap;
833 auto initialLiveRanges = gatherTileLiveRanges(
834 operationToIndexMap, liveRangeAllocator, liveness, function);
835 if (initialLiveRanges.empty())
836 return success();
837
838 if (dumpRanges) {
839 // Wrangle initial live ranges into a form suitable for printing.
840 auto nonEmpty = llvm::make_filter_range(
841 Range: llvm::make_second_range(c&: initialLiveRanges),
842 Pred: [&](LiveRange const &liveRange) { return !liveRange.empty(); });
843 auto initialRanges = llvm::map_to_vector(
844 C&: nonEmpty, F: [](LiveRange const &liveRange) { return &liveRange; });
845 llvm::sort(C&: initialRanges,
846 Comp: [](LiveRange const *a, LiveRange const *b) { return *a < *b; });
847 llvm::errs() << "\n========== Initial Live Ranges:\n";
848 dumpLiveRanges(operationToIndexMap, liveRanges: initialRanges, function);
849 }
850
851 // 3. Coalesce (non-overlapping) live ranges where it would be beneficial
852 // for tile allocation. E.g. Unify the result of an operation with its
853 // operands.
854 auto coalescedLiveRanges = coalesceTileLiveRanges(initialLiveRanges);
855
856 if (dumpRanges) {
857 llvm::errs() << "\n========== Coalesced Live Ranges:\n";
858 dumpLiveRanges(operationToIndexMap, liveRanges: coalescedLiveRanges, function);
859 }
860
861 // 4. Allocate tile IDs to live ranges.
862 allocateTilesToLiveRanges(liveRangesSortedByStartPoint: coalescedLiveRanges);
863
864 // 5. Assign the tile IDs back to the ArmSME operations.
865 if (failed(Result: assignTileIdsAndResolveTrivialConflicts(rewriter, function,
866 allocatedLiveRanges: coalescedLiveRanges))) {
867 return failure();
868 }
869
870 // 6. Erase trivially dead tile operations (e.g. a ZeroOp with no
871 // users). This prevents the LLVM conversion needlessly inserting spills.
872 eraseTriviallyDeadTileOps(rewriter, function);
873 return success();
874}
875