| 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 | |
| 59 | namespace mlir::arm_sme { |
| 60 | #define GEN_PASS_DEF_TESTTILEALLOCATION |
| 61 | #include "mlir/Dialect/ArmSME/Transforms/Passes.h.inc" |
| 62 | } // namespace mlir::arm_sme |
| 63 | |
| 64 | using namespace mlir; |
| 65 | using namespace mlir::arm_sme; |
| 66 | |
| 67 | namespace { |
| 68 | |
| 69 | enum 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. |
| 114 | static 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 | |
| 142 | class TileAllocator { |
| 143 | public: |
| 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 | |
| 180 | private: |
| 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 | /// ``` |
| 202 | void 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 | /// ``` |
| 247 | void 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. |
| 272 | void 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. |
| 283 | struct 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). |
| 346 | FailureOr<DenseMap<Operation *, unsigned>> |
| 347 | generateOperationNumbering(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). |
| 376 | MapVector<Value, LiveRange> |
| 377 | gatherTileLiveRanges(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. |
| 423 | static 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. |
| 449 | SmallVector<LiveRange *> |
| 450 | coalesceTileLiveRanges(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`. |
| 514 | template <typename OverlappingRangesIterator> |
| 515 | LiveRange * |
| 516 | chooseSpillUsingHeuristics(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. |
| 545 | void 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 * : 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. |
| 649 | void 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. |
| 663 | LogicalResult 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. |
| 762 | void 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 | |
| 790 | struct 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. |
| 806 | static bool hasArmSMETileOps(FunctionOpInterface function) { |
| 807 | return function |
| 808 | .walk(callback: [&](ArmSMETileOpInterface) { return WalkResult::interrupt(); }) |
| 809 | .wasInterrupted(); |
| 810 | } |
| 811 | |
| 812 | LogicalResult 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 | |