MLIR-AIE 1.4.6.dev
AIEDMAChannelAnalysis.h
Go to the documentation of this file.
1//===- AIEDMAChannelAnalysis.h ----------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2021-2022 Xilinx, Inc.
4// Copyright (C) 2022-2026 Advanced Micro Devices, Inc.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef AIE_DIALECT_AIE_TRANSFORMS_AIEDMACHANNELANALYSIS_H
10#define AIE_DIALECT_AIE_TRANSFORMS_AIEDMACHANNELANALYSIS_H
11
13
14#include "llvm/ADT/BitVector.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/MapVector.h"
17#include "llvm/ADT/STLFunctionalExtras.h"
18#include "llvm/ADT/SmallVector.h"
19
20#include <limits>
21#include <optional>
22
23namespace xilinx::AIE {
24
25/// Which DMA channels of each tile are already spoken for, so that a channel is
26/// handed out at most once across everything that programs one.
28 /// Fully resolved tile aliases name the same hardware resources. Unresolved
29 /// tiles retain their SSA identity until placement establishes co-location.
30 mlir::DenseMap<std::pair<int, int>, mlir::Value> tilesByCoordinate;
31 mlir::Value getTileKey(mlir::Value tile);
32
33 /// Keep the reserving operation so diagnostics retain its MLIR location.
34 mlir::DenseMap<std::tuple<mlir::Value, DMAChannelDir, int>, mlir::Operation *>
35 usedChannels;
36 /// DMA channels an explicit flow routes. First-free assignment skips them;
37 /// a pinned request may still claim one.
38 mlir::DenseMap<std::tuple<mlir::Value, DMAChannelDir, int>, mlir::Operation *>
39 streamedChannels;
40 /// Channels whose claimants all share them. Several packet-switched sources
41 /// coexist on one; a circuit claim is exclusive.
42 mlir::DenseSet<std::tuple<mlir::Value, DMAChannelDir, int>> sharedChannels;
43 mlir::DenseMap<std::tuple<mlir::Value, DMAChannelDir, int>, mlir::Operation *>
44 shareableChannels;
45 /// The first claimant of a core stream port, and whether only packets use
46 /// it; circuit occupancy is exclusive.
47 struct StreamClaim {
48 mlir::Operation *owner;
49 bool packet;
50 };
51 mlir::DenseMap<std::tuple<mlir::Value, DMAChannelDir, int>, StreamClaim>
52 usedStreams;
53
54public:
55 /// A channel claimed by index: by a DMA program start, a runtime task or a
56 /// shim allocation (`owner`), on `tile`.
57 struct ChannelClaim {
58 ChannelClaim(mlir::Value tile, DMAChannelDir dir, int channel,
59 mlir::Operation *owner)
61 mlir::Value tile;
62 DMAChannelDir dir;
64 mlir::Operation *owner;
65 };
66
67private:
68 /// Every claim that took a channel, in the order they were made.
69 llvm::SmallVector<ChannelClaim> claims;
70 void claim(mlir::Value tile, DMAChannelDir dir, int channel,
71 mlir::Operation *owner);
72
73public:
74 DMAChannelAnalysis(DeviceOp &device);
75
76 /// The channels taken by index rather than through a route endpoint, in
77 /// the order the claims were made. A shareable one may appear more than
78 /// once.
79 llvm::ArrayRef<ChannelClaim> getChannelClaims() const { return claims; }
80
81 /// Exclusive upper bound on channel indices eligible for this transfer.
82 static int getDMAChannelLimit(TileLike tile, DMAChannelDir dir,
83 bool requiresAdjacentTileAccessChannels);
84
85 /// Next free channel of `tile` in `dir`, or -1 when the tile has none left.
86 /// A channel an explicit flow routes is not free.
87 /// A channel reaching an adjacent MemTile's memory must come from the
88 /// target's restricted range at every compatible physical position.
89 int getDMAChannelIndex(TileLike tile, DMAChannelDir dir,
90 bool requiresAdjacentTileAccessChannels,
91 mlir::Operation *owner = nullptr);
92
93 /// Whether first-free assignment could hand out `channel`: nothing reserves
94 /// it and no explicit flow routes it.
95 bool isChannelFree(TileLike tile, DMAChannelDir dir, int channel);
96
97 /// Claim `channel` for (`tile`, `dir`) so first-free assignment cannot take
98 /// it. Returns the channel, or -1 when it is out of range or already
99 /// claimed; the caller reports, since it knows which endpoint asked.
100 /// `shareable` claimants join a channel other shareable ones hold.
101 int reservePinnedChannel(TileLike tile, DMAChannelDir dir, int channel,
102 mlir::Operation *owner = nullptr,
103 bool shareable = false);
104
105 /// Operation reserving or routing this channel; null if none.
106 mlir::Operation *getDMAChannelOwner(TileLike tile, DMAChannelDir dir,
107 int channel);
108
109 /// A DMA end of one tile: its direction, the BD ids it takes, the
110 /// exclusive upper bound on the channels it may take, and the channel it
111 /// pins, if any, which every end pinning it shares.
112 struct BDPlanEnd {
113 BDPlanEnd(DMAChannelDir dir, int64_t bds, int limit,
114 std::optional<int> pinned)
115 : dir(dir), bds(bds), limit(limit), pinned(pinned) {}
116 DMAChannelDir dir;
117 int64_t bds;
118 int limit;
119 std::optional<int> pinned;
120 };
121
122 /// Channels among `0..numChannels-1` at (`col`, `row`), grouped by whichever
123 /// BD ids any two in a group share, transitively.
124 struct BDGroup {
125 llvm::BitVector ids;
126 llvm::SmallVector<int> channels;
127 };
128 static llvm::SmallVector<BDGroup> bdGroups(const AIETargetModel &target,
129 int col, int row, int numChannels);
130
131 /// A channel of the tile at (`col`, `row`) for each of `ends`: its pinned
132 /// one, else one `free` leaves that no other end of its direction takes;
133 /// and, for every set of channels sharing BD ids, the ends on them plus the
134 /// ids `spent` on each channel within those ids fit those ids. Nothing when
135 /// no assignment fits.
136 static std::optional<llvm::SmallVector<int>>
137 planBDChannels(const AIETargetModel &target, int col, int row,
138 llvm::ArrayRef<BDPlanEnd> ends,
139 llvm::function_ref<bool(DMAChannelDir, int)> free,
140 llvm::function_ref<int64_t(int)> spent);
141 /// The same, given the tile's bdGroups.
142 static std::optional<llvm::SmallVector<int>>
143 planBDChannels(llvm::ArrayRef<BDGroup> tileGroups,
144 llvm::ArrayRef<BDPlanEnd> ends,
145 llvm::function_ref<bool(DMAChannelDir, int)> free,
146 llvm::function_ref<int64_t(int)> spent);
147
148 /// A pool whose ends a BD plan weighs: how many objects it holds, the bytes
149 /// of one, and whether it can be walked whole, its ends then taking one BD
150 /// id each.
151 struct BDWalkPool {
152 int64_t depth;
153 int64_t objectBytes;
155 };
156 /// walkSetsThatFit's result; `channelShort` when the ends do not fit the
157 /// tile's channels even taking no BD ids, `fits` false when no set does.
158 struct BDWalkSets {
159 llvm::SmallVector<llvm::SmallVector<unsigned>> sets;
160 /// The bytes each set walks whole.
161 llvm::SmallVector<int64_t> bytes;
162 bool channelShort = false;
163 bool fits = true;
164 };
165
166 /// The walkable pool not yet `whole` to walk next: the deepest, then the one
167 /// with the smallest objects, then the one whose ends take the most BD ids;
168 /// `pools` order decides only between pools alike in all three. Nothing
169 /// when none is left.
170 static std::optional<unsigned>
171 nextPoolToWalk(llvm::ArrayRef<BDPlanEnd> ends,
172 llvm::ArrayRef<unsigned> poolOf,
173 llvm::ArrayRef<BDWalkPool> pools, llvm::ArrayRef<bool> whole);
174
175 /// Every set of walkable `pools` whose walk lets planBDChannels fit `ends`
176 /// (`poolOf` gives each end's pool), ordered by the bytes the set walks
177 /// whole, then its size, then its members in nextPoolToWalk's order; at
178 /// most `maxSets` of them, cheapest first (unbounded by default). Empty
179 /// when the ends fit unwalked. At most 12 pools are walkable: each draws a
180 /// channel of its own, and more ends than channels make `channelShort`.
181 /// aie-objectfifo-allocate and the SA placer both walk by this; the SA only
182 /// ever takes the first set, so it should pass `maxSets=1`.
183 static BDWalkSets
184 walkSetsThatFit(const AIETargetModel &target, int col, int row,
185 llvm::ArrayRef<BDPlanEnd> ends,
186 llvm::ArrayRef<unsigned> poolOf,
187 llvm::ArrayRef<BDWalkPool> pools,
188 llvm::function_ref<bool(DMAChannelDir, int)> free,
189 llvm::function_ref<int64_t(int)> spent,
190 unsigned maxSets = std::numeric_limits<unsigned>::max());
191
192 /// One walkSetsThatFit set per mem tile of a spill component
193 /// (memTileSpillComponents), by index; `placed` when its buffers place,
194 /// `stopped` when the search gave up at `maxTries` tries.
195 struct WalkChoice {
196 llvm::SmallVector<unsigned> sets;
197 bool placed = false;
198 bool stopped = false;
199 };
200 /// Tries the choices of one set per tile, `bytes[tile]` giving each of its
201 /// sets' bytes walked whole, in order of total bytes walked, then the
202 /// tiles' set indices in turn, until `places` (the caller's buffer search
203 /// over the component) accepts one; the first choice when none does.
204 static WalkChoice
205 searchWalkProduct(llvm::ArrayRef<llvm::SmallVector<int64_t>> bytes,
206 llvm::function_ref<bool(llvm::ArrayRef<unsigned>)> places,
207 unsigned maxTries);
208 static constexpr unsigned kMaxWalkPlacements = 1024;
209
210 /// Blocks of the BD chain `start` begins, following next_bd.
211 static llvm::SmallVector<mlir::Block *> chainOf(DMAStartOp start);
212 static int64_t countBDs(DMAStartOp start);
213
214 /// The BD ids tiles' own programs hold before objectFIFOs take theirs: the
215 /// chains DMA programs start by index, on their channels, and each id a
216 /// runtime sequence pins (AIEX::forEachRuntimePinnedBdId), once per tile, on
217 /// the lowest channel up to its own reaching it (aie-reserve-runtime-bd-ids
218 /// keeps static BDs off those).
219 class TakenBDs {
220 public:
221 TakenBDs() = default;
222 explicit TakenBDs(DeviceOp device);
223 /// By channel, the ids held at (`col`, `row`) by `tiles` and by every
224 /// tile with those coordinates.
225 llvm::DenseMap<int, int64_t>
226 at(const AIETargetModel &target, int col, int row,
227 llvm::ArrayRef<mlir::Operation *> tiles = {}) const;
228 /// Coordinates of the placed tiles that hold BD ids.
229 llvm::SmallVector<std::pair<int, int>> positions() const;
230
231 private:
232 struct Pin {
233 unsigned order;
234 std::optional<int> channel;
235 };
236 llvm::MapVector<mlir::Operation *, llvm::DenseMap<int, int64_t>> fixed;
237 llvm::MapVector<mlir::Operation *, llvm::DenseMap<int32_t, Pin>> pinned;
238 };
239
240 /// Claim a raw stream port for `user`, reporting on it when the port is
241 /// taken; packet users may share it with other packets.
242 mlir::LogicalResult checkAIEStreamIndex(TileLike tile, DMAChannel chan,
243 mlir::Operation *user,
244 bool packet = false);
245};
246
247} // namespace xilinx::AIE
248
249#endif // AIE_DIALECT_AIE_TRANSFORMS_AIEDMACHANNELANALYSIS_H
llvm::DenseMap< int, int64_t > at(const AIETargetModel &target, int col, int row, llvm::ArrayRef< mlir::Operation * > tiles={}) const
By channel, the ids held at (col, row) by tiles and by every tile with those coordinates.
llvm::SmallVector< std::pair< int, int > > positions() const
Coordinates of the placed tiles that hold BD ids.
int getDMAChannelIndex(TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels, mlir::Operation *owner=nullptr)
Next free channel of tile in dir, or -1 when the tile has none left.
static std::optional< unsigned > nextPoolToWalk(llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::ArrayRef< bool > whole)
The walkable pool not yet whole to walk next: the deepest, then the one with the smallest objects,...
mlir::Operation * getDMAChannelOwner(TileLike tile, DMAChannelDir dir, int channel)
Operation reserving or routing this channel; null if none.
bool isChannelFree(TileLike tile, DMAChannelDir dir, int channel)
Whether first-free assignment could hand out channel: nothing reserves it and no explicit flow routes...
static std::optional< llvm::SmallVector< int > > planBDChannels(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent)
A channel of the tile at (col, row) for each of ends: its pinned one, else one free leaves that no ot...
static constexpr unsigned kMaxWalkPlacements
static int64_t countBDs(DMAStartOp start)
static llvm::SmallVector< BDGroup > bdGroups(const AIETargetModel &target, int col, int row, int numChannels)
static WalkChoice searchWalkProduct(llvm::ArrayRef< llvm::SmallVector< int64_t > > bytes, llvm::function_ref< bool(llvm::ArrayRef< unsigned >)> places, unsigned maxTries)
Tries the choices of one set per tile, bytes[tile] giving each of its sets' bytes walked whole,...
static llvm::SmallVector< mlir::Block * > chainOf(DMAStartOp start)
Blocks of the BD chain start begins, following next_bd.
static std::optional< llvm::SmallVector< int > > planBDChannels(llvm::ArrayRef< BDGroup > tileGroups, llvm::ArrayRef< BDPlanEnd > ends, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent)
The same, given the tile's bdGroups.
static BDWalkSets walkSetsThatFit(const AIETargetModel &target, int col, int row, llvm::ArrayRef< BDPlanEnd > ends, llvm::ArrayRef< unsigned > poolOf, llvm::ArrayRef< BDWalkPool > pools, llvm::function_ref< bool(DMAChannelDir, int)> free, llvm::function_ref< int64_t(int)> spent, unsigned maxSets=std::numeric_limits< unsigned >::max())
Every set of walkable pools whose walk lets planBDChannels fit ends (poolOf gives each end's pool),...
static int getDMAChannelLimit(TileLike tile, DMAChannelDir dir, bool requiresAdjacentTileAccessChannels)
Exclusive upper bound on channel indices eligible for this transfer.
mlir::LogicalResult checkAIEStreamIndex(TileLike tile, DMAChannel chan, mlir::Operation *user, bool packet=false)
Claim a raw stream port for user, reporting on it when the port is taken; packet users may share it w...
int reservePinnedChannel(TileLike tile, DMAChannelDir dir, int channel, mlir::Operation *owner=nullptr, bool shareable=false)
Claim channel for (tile, dir) so first-free assignment cannot take it.
llvm::ArrayRef< ChannelClaim > getChannelClaims() const
The channels taken by index rather than through a route endpoint, in the order the claims were made.
struct DMAChannel { DMAChannelDir direction; int channel; bool operator==(const DMAChannel &rhs) const { return std::tie(direction, channel)==std::tie(rhs.direction, rhs.channel); } } DMAChannel
Definition AIEDialect.h:314
Channels among 0..numChannels-1 at (col, row), grouped by whichever BD ids any two in a group share,...
BDPlanEnd(DMAChannelDir dir, int64_t bds, int limit, std::optional< int > pinned)
A pool whose ends a BD plan weighs: how many objects it holds, the bytes of one, and whether it can b...
walkSetsThatFit's result; channelShort when the ends do not fit the tile's channels even taking no BD...
llvm::SmallVector< int64_t > bytes
The bytes each set walks whole.
llvm::SmallVector< llvm::SmallVector< unsigned > > sets
ChannelClaim(mlir::Value tile, DMAChannelDir dir, int channel, mlir::Operation *owner)
One walkSetsThatFit set per mem tile of a spill component (memTileSpillComponents),...