MLIR-AIE 1.4.6.dev
AIELockPlan.h
Go to the documentation of this file.
1//===- AIELockPlan.h --------------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
8#ifndef AIE_DIALECT_AIE_TRANSFORMS_AIELOCKPLAN_H
9#define AIE_DIALECT_AIE_TRANSFORMS_AIELOCKPLAN_H
10
13
14#include "llvm/ADT/ArrayRef.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
18
19#include <optional>
20#include <vector>
21
22namespace mlir {
23class Operation;
24} // namespace mlir
25
26namespace xilinx::AIE {
27
28class ObjectFifoPoolOp;
29
30/// Lock placement shared by aie-objectfifo-allocate and the SA placer, on
31/// plain records.
32class LockPlan {
33public:
34 /// A tile's candidate positions, and the one placement chose, once it has.
35 struct Tile {
36 llvm::SmallVector<TileID, 1> positions;
37 std::optional<TileID> at;
38 };
39 /// A tile using the locks, `localOnly` when only its own (dmaLocalOnly).
40 struct User {
41 unsigned tile;
43 };
44 struct Group {
45 int count;
46 llvm::SmallVector<unsigned> candidates;
47 llvm::SmallVector<User> users;
48 };
49 struct Placed {
50 std::optional<unsigned> tile;
51 /// Some candidate every user reaches.
52 bool reachable = false;
53 /// The last such candidate, when all were full.
54 std::optional<unsigned> full;
55 };
56
57private:
58 enum class Packing { Found, None, Stopped };
59
60 /// A packing found, keyed on what pack() reads. A packing found records
61 /// each group's tile as an offset into its eligible tiles.
62 struct Outcome {
63 Packing packing;
64 llvm::SmallVector<unsigned> blocked;
65 llvm::SmallVector<unsigned> offsets;
66 };
67
68public:
69 /// Packings by what pack() reads, the least recently used dropped first
70 /// beyond its capacity.
72
73 explicit LockPlan(const AIETargetModel &target) : target(target) {}
74
75 /// The lock groups `owners` lock owners of a pool of `depth` objects take,
76 /// by count. With semaphore locks each owner is a segment taking a pair,
77 /// one lock counting free objects and one full ones; otherwise the one
78 /// owner is the pool, taking a binary lock per object.
79 static llvm::SmallVector<int> groupCounts(const AIETargetModel &target,
80 int64_t depth, int owners) {
81 if (target.hasProperty(AIETargetModel::UsesSemaphoreLocks))
82 return llvm::SmallVector<int>(owners, 2);
83 if (!owners)
84 return {};
85 return {static_cast<int>(depth)};
86 }
87
88 /// Whether a DMA on a tile of `type` uses only its own tile's locks: every
89 /// DMA does but a mem tile's.
90 static bool dmaLocalOnly(AIETileType type) {
91 return type != AIETileType::MemTile;
92 }
93
94 /// The ops whose locks allocation and the SA each make for `pool`: with
95 /// semaphore locks, each segment without its own pair; otherwise the pool,
96 /// when it has none.
97 static llvm::SmallVector<mlir::Operation *>
98 lockOwners(const AIETargetModel &target, ObjectFifoPoolOp pool);
99
100 unsigned addTile(Tile tile) {
101 tiles.push_back(std::move(tile));
102 return tiles.size() - 1;
103 }
104
105 /// Takes `count` locks on `tile`, or returns false when it has too few
106 /// left. A tile not yet placed is not counted.
107 bool reserve(unsigned tile, int count) {
108 if (!tiles[tile].at)
109 return true;
110 TileID at = *tiles[tile].at;
111 int &taken = used[at];
112 if (taken + count > static_cast<int>(target.getNumLocks(at.col, at.row)))
113 return false;
114 taken += count;
115 return true;
116 }
117
118 /// Whether a tile at one of `user` reaches memory at one of `memory`; with
119 /// `localOnly`, only at its own position.
120 static bool reaches(const AIETargetModel &target, llvm::ArrayRef<TileID> user,
121 llvm::ArrayRef<TileID> memory, bool localOnly) {
122 for (TileID u : user)
123 for (TileID m : memory) {
124 if (localOnly && u != m)
125 continue;
126 auto shared = target.getSharedMemory(u, m);
129 return true;
130 }
131 return false;
132 }
133 bool reaches(const User &user, unsigned tile) const {
134 return user.tile == tile || reaches(target, tiles[user.tile].positions,
135 tiles[tile].positions, user.localOnly);
136 }
137
138 /// A group of `count` locks a pool's objects are counted by: on `home`,
139 /// else, unless the pool must stay `local`, on a tile holding its buffers,
140 /// one of its users' tiles, then any tile in `ranked` order.
141 static Group group(int count, unsigned home, bool local,
142 llvm::ArrayRef<unsigned> buffers,
143 llvm::ArrayRef<User> users,
144 llvm::ArrayRef<unsigned> ranked) {
145 Group group{count, {home}, llvm::to_vector(users)};
146 if (!local) {
147 llvm::append_range(group.candidates, buffers);
148 for (const User &user : users)
149 group.candidates.push_back(user.tile);
150 llvm::append_range(group.candidates, ranked);
151 }
152 return group;
153 }
154
156 Placed placed;
157 for (unsigned tile : group.candidates) {
158 if (!llvm::all_of(group.users,
159 [&](const User &user) { return reaches(user, tile); }))
160 continue;
161 placed.reachable = true;
162 if (reserve(tile, group.count)) {
163 placed.tile = tile;
164 placed.full.reset();
165 return placed;
166 }
167 placed.full = tile;
168 }
169 return placed;
170 }
171
172 struct Assignment {
173 llvm::SmallVector<std::optional<unsigned>> tiles;
174 /// The first group no assignment finds room for: first fit's miss, or,
175 /// after packing or matching run, the first one still left over.
176 std::optional<size_t> failed;
178 /// How many groups no assignment finds room for.
179 size_t unassigned = 0;
180 /// The exact packing ran out of kPackBudget steps before it decided.
181 bool stopped = false;
182 };
183
184 /// Places `groups` first fit: with `callerOrder`, in order on each one's
185 /// candidates, then in canonical order (canonicalFirstFit); without, in
186 /// canonical order only. On a miss: exact bipartite matching when every
187 /// group takes one count, else exact packing, which leaves the first-fit
188 /// placement standing if no packing exists or the search runs out of
189 /// kPackBudget steps. The SA places in canonical order only, so it fits
190 /// only where allocation's own-order-first pass fits too.
191 Assignment assign(llvm::ArrayRef<Group> groups, Memo *memo = nullptr,
192 bool callerOrder = true);
193
194 /// Steps the exact packing of groups of different counts may take on each
195 /// connected component.
196 static constexpr int64_t kPackBudget = 1000000;
197
198private:
199 /// Places each group, larger counts first, then by the positions it may
200 /// take, on the first of `eligible` with room: a tile not yet placed, then
201 /// placed ones by position. The order comes from the groups' counts and
202 /// positions alone, and groups alike in both are interchangeable, so every
203 /// caller listing the same groups gets the same verdict. Returns each
204 /// group's index and placement, in the order placed.
205 llvm::SmallVector<std::pair<size_t, Placed>>
206 canonicalFirstFit(llvm::ArrayRef<Group> groups,
207 llvm::ArrayRef<llvm::SmallVector<unsigned>> eligible);
208
209 /// Puts each group in `chosen` on a tile in `eligible` with room for it,
210 /// from the room left `before` any group; a group that may use a tile not
211 /// yet placed takes it. The rest is solved one connected component of
212 /// positions at a time by bin completion: the open position with the fewest
213 /// groups to choose from takes every subset of them wasting no more room
214 /// than the component can spare, then closes. A state whose groups do not
215 /// fit even when split is cut off, as is one whose open positions must waste
216 /// more than it can spare. Groups alike in count and positions are
217 /// interchangeable, so a subset takes how many of each. Each component may
218 /// take kPackBudget steps; one that does not decide leaves the packing
219 /// Stopped unless another has none, whose groups `blocked` then holds.
220 Packing pack(llvm::ArrayRef<Group> groups,
221 llvm::ArrayRef<llvm::SmallVector<unsigned>> eligible,
222 const llvm::DenseMap<TileID, int> &before,
223 llvm::SmallVectorImpl<std::optional<unsigned>> &chosen,
224 llvm::SmallVectorImpl<unsigned> &blocked) const;
225
226 const AIETargetModel &target;
227 llvm::SmallVector<Tile> tiles;
228 llvm::DenseMap<TileID, int> used;
229};
230
231} // namespace xilinx::AIE
232
233#endif // AIE_DIALECT_AIE_TRANSFORMS_AIELOCKPLAN_H
@ Second
Only the second tile's module.
A memo that keeps its capacity most recently used results, each key stored once.
Placed place(const Group &group)
static llvm::SmallVector< mlir::Operation * > lockOwners(const AIETargetModel &target, ObjectFifoPoolOp pool)
The ops whose locks allocation and the SA each make for pool: with semaphore locks,...
static llvm::SmallVector< int > groupCounts(const AIETargetModel &target, int64_t depth, int owners)
The lock groups owners lock owners of a pool of depth objects take, by count.
Definition AIELockPlan.h:79
bool reaches(const User &user, unsigned tile) const
static constexpr int64_t kPackBudget
Steps the exact packing of groups of different counts may take on each connected component.
unsigned addTile(Tile tile)
Assignment assign(llvm::ArrayRef< Group > groups, Memo *memo=nullptr, bool callerOrder=true)
Places groups first fit: with callerOrder, in order on each one's candidates, then in canonical order...
static bool dmaLocalOnly(AIETileType type)
Whether a DMA on a tile of type uses only its own tile's locks: every DMA does but a mem tile's.
Definition AIELockPlan.h:90
bool reserve(unsigned tile, int count)
Takes count locks on tile, or returns false when it has too few left.
LockPlan(const AIETargetModel &target)
Definition AIELockPlan.h:73
BoundedMemo< std::vector< int64_t >, Outcome > Memo
Packings by what pack() reads, the least recently used dropped first beyond its capacity.
Definition AIELockPlan.h:71
static bool reaches(const AIETargetModel &target, llvm::ArrayRef< TileID > user, llvm::ArrayRef< TileID > memory, bool localOnly)
Whether a tile at one of user reaches memory at one of memory; with localOnly, only at its own positi...
static Group group(int count, unsigned home, bool local, llvm::ArrayRef< unsigned > buffers, llvm::ArrayRef< User > users, llvm::ArrayRef< unsigned > ranked)
A group of count locks a pool's objects are counted by: on home, else, unless the pool must stay loca...
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
std::optional< size_t > failed
The first group no assignment finds room for: first fit's miss, or, after packing or matching run,...
size_t unassigned
How many groups no assignment finds room for.
llvm::SmallVector< std::optional< unsigned > > tiles
bool stopped
The exact packing ran out of kPackBudget steps before it decided.
llvm::SmallVector< User > users
Definition AIELockPlan.h:47
llvm::SmallVector< unsigned > candidates
Definition AIELockPlan.h:46
std::optional< unsigned > tile
Definition AIELockPlan.h:50
bool reachable
Some candidate every user reaches.
Definition AIELockPlan.h:52
std::optional< unsigned > full
The last such candidate, when all were full.
Definition AIELockPlan.h:54
A tile's candidate positions, and the one placement chose, once it has.
Definition AIELockPlan.h:35
llvm::SmallVector< TileID, 1 > positions
Definition AIELockPlan.h:36
std::optional< TileID > at
Definition AIELockPlan.h:37
A tile using the locks, localOnly when only its own (dmaLocalOnly).
Definition AIELockPlan.h:40