MLIR-AIE 1.4.6.dev
AIEChannelTurns.cpp
Go to the documentation of this file.
1//===- AIEChannelTurns.cpp --------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
10
11#include "mlir/Dialect/SCF/IR/SCF.h"
12#include "mlir/Dialect/Utils/StaticValueUtils.h"
13#include "mlir/IR/Matchers.h"
14#include "mlir/Interfaces/LoopLikeInterface.h"
15#include "mlir/Interfaces/SideEffectInterfaces.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/MathExtras.h"
19
20#include <map>
21#include <set>
22
23#define DEBUG_TYPE "aie-channel-turns"
24
25using namespace mlir;
26using namespace xilinx;
27using namespace xilinx::AIE;
28
29namespace {
30/// Events past this many in a period are not worth one chain.
31constexpr size_t maxPeriodEvents = 4096;
32/// Periods simulated before giving up on a steady state.
33constexpr int maxPeriods = 256;
34} // namespace
35
36LogicalResult CoreTurns::read(ArrayRef<ObjectFifoCoreEndpointOp> ends,
37 std::string &reason) {
38 assert(!ends.empty() && "turns between no endpoints");
39 ObjectFifoCoreEndpointOp first = ends.front();
40 Value tile = first.getTile();
41 if (llvm::any_of(ends, [&](ObjectFifoCoreEndpointOp end) {
42 return end.drains() != first.drains() || end.getTile() != tile;
43 })) {
44 reason = "the endpoints are not all one core's, one way";
45 return failure();
46 }
47 CoreOp core;
48 for (Operation *user : tile.getUsers())
49 if (auto candidate = dyn_cast<CoreOp>(user))
50 core = candidate;
51 if (!core) {
52 reason = "no core works through them";
53 return failure();
54 }
55 SmallVector<StringAttr> names;
56 for (ObjectFifoCoreEndpointOp end : ends)
57 names.push_back(end.getSymNameAttr());
58 return read(core, names, first.drains(), reason);
59}
60
61LogicalResult CoreTurns::read(CoreOp core, ArrayRef<StringAttr> names,
62 bool coreDrains, std::string &reason) {
63 this->coreDrains = coreDrains;
64 ends = names.size();
65 loop = nullptr;
66 idle = false;
67 wholeRun.clear();
68 DenseMap<StringAttr, unsigned> index;
69 for (auto [i, name] : llvm::enumerate(names))
70 index[name] = i;
71 // An objectFIFO's acquires name its port; an endpoint's are one way.
72 ObjectFifoPort port =
73 coreDrains ? ObjectFifoPort::Consume : ObjectFifoPort::Produce;
74 auto endOf = [&](Operation *op) -> std::optional<unsigned> {
75 FlatSymbolRefAttr name;
76 std::optional<ObjectFifoPort> used;
77 if (auto acquire = dyn_cast<ObjectFifoAcquireOp>(op)) {
78 name = acquire.getObjFifoNameAttr();
79 used = acquire.getPort();
80 } else if (auto release = dyn_cast<ObjectFifoReleaseOp>(op)) {
81 name = release.getObjFifoNameAttr();
82 used = release.getPort();
83 }
84 if (!name || (used && *used != port))
85 return std::nullopt;
86 auto it = index.find(name.getAttr());
87 if (it == index.end())
88 return std::nullopt;
89 return it->second;
90 };
91
92 // A draining core's release outside every loop, with no acquire after it,
93 // only gives objects back; the channel's order counts acquires, so it does
94 // not decide the period.
95 auto onceAfterLoops = [&](Operation *op) {
96 if (!coreDrains || !isa<ObjectFifoReleaseOp>(op) ||
97 op->getParentOfType<LoopLikeOpInterface>())
98 return false;
99 return llvm::none_of(
100 llvm::make_range(std::next(op->getIterator()), op->getBlock()->end()),
101 [&](Operation &later) {
102 return later
103 .walk([&](ObjectFifoAcquireOp acquire) {
104 return endOf(acquire) ? WalkResult::interrupt()
105 : WalkResult::advance();
106 })
107 .wasInterrupted();
108 });
109 };
110 SmallVector<Operation *> uses, tails;
111 core.walk([&](Operation *op) {
112 if (endOf(op))
113 (onceAfterLoops(op) ? tails : uses).push_back(op);
114 });
115 if (uses.empty()) {
116 reason = "the core never acquires them";
117 return failure();
118 }
119 // The period: the innermost loop around every use.
120 auto loopsAround = [&](Operation *op) {
121 SmallVector<Operation *> loops;
122 for (Operation *parent = op->getParentOp(); parent != core;
123 parent = parent->getParentOp())
124 if (isa<LoopLikeOpInterface>(parent))
125 loops.push_back(parent);
126 return loops;
127 };
128 SmallVector<Operation *> candidates;
129 for (Operation *candidate : loopsAround(uses.front()))
130 if (llvm::all_of(uses, [&](Operation *use) {
131 return candidate->isProperAncestor(use);
132 }))
133 candidates.push_back(candidate);
134 if (candidates.empty()) {
135 reason = "no loop repeats the core's use of them";
136 return failure();
137 }
138
139 // The counters of the unrolled loops, so that branches on them fold.
140 DenseMap<Value, Attribute> counters;
141 std::function<Attribute(Value)> evaluate = [&](Value value) -> Attribute {
142 Attribute attr = counters.lookup(value);
143 Operation *def = value.getDefiningOp();
144 if (attr || !def || matchPattern(value, m_Constant(&attr)))
145 return attr;
146 if (!isPure(def) || def->getNumResults() != 1)
147 return {};
148 SmallVector<Attribute> operands;
149 for (Value operand : def->getOperands())
150 if (!operands.emplace_back(evaluate(operand)))
151 return {};
152 SmallVector<OpFoldResult> folded;
153 if (failed(def->fold(operands, folded)) || folded.size() != 1)
154 return {};
155 if (auto result = dyn_cast<Attribute>(folded.front()))
156 return result;
157 return evaluate(cast<Value>(folded.front()));
158 };
159
160 std::function<LogicalResult(Block &)> unroll = [&](Block &block) {
161 for (Operation &op : block) {
162 if (std::optional<unsigned> end = endOf(&op)) {
163 if (auto acquire = dyn_cast<ObjectFifoAcquireOp>(op))
164 period.push_back({*end, acquire.acqNumber(), true, &op});
165 else
166 period.push_back(
167 {*end, cast<ObjectFifoReleaseOp>(op).relNumber(), false, &op});
168 if (period.size() > maxPeriodEvents) {
169 reason = "the core's period uses them too many times";
170 return failure();
171 }
172 continue;
173 }
174 if (!llvm::any_of(
175 uses, [&](Operation *use) { return op.isProperAncestor(use); }))
176 continue;
177 if (auto ifOp = dyn_cast<scf::IfOp>(op)) {
178 if (auto taken =
179 dyn_cast_or_null<BoolAttr>(evaluate(ifOp.getCondition()))) {
180 for (Block &branch :
181 taken.getValue() ? ifOp.getThenRegion() : ifOp.getElseRegion())
182 if (failed(unroll(branch)))
183 return failure();
184 continue;
185 }
186 }
187 auto forOp = dyn_cast<scf::ForOp>(op);
188 std::optional<APInt> trips =
189 forOp ? forOp.getStaticTripCount() : std::nullopt;
190 if (!trips) {
191 reason = "the core uses them under control flow that depends on data";
192 return failure();
193 }
194 if (trips->getSExtValue() > static_cast<int64_t>(maxPeriodEvents)) {
195 reason = "the core's period uses them too many times";
196 return failure();
197 }
198 std::optional<int64_t> lower = getConstantIntValue(forOp.getLowerBound());
199 std::optional<int64_t> step = getConstantIntValue(forOp.getStep());
200 for (int64_t trip = 0; trip < trips->getSExtValue(); trip++) {
201 if (lower && step)
202 counters[forOp.getInductionVar()] = IntegerAttr::get(
203 forOp.getInductionVar().getType(), *lower + trip * *step);
204 if (failed(unroll(*forOp.getBody())))
205 return failure();
206 }
207 }
208 return success();
209 };
210 // The innermost loop whose body unrolls, branches folded, is the period. An
211 // scf.while's condition region holds no uses.
212 for (Operation *candidate : candidates) {
213 period.clear();
214 counters.clear();
215 if (llvm::all_of(cast<LoopLikeOpInterface>(candidate).getLoopRegions(),
216 [&](Region *region) {
217 return llvm::all_of(*region, [&](Block &block) {
218 return succeeded(unroll(block));
219 });
220 })) {
221 loop = candidate;
222 reason.clear();
223 break;
224 }
225 }
226 if (!loop)
227 return failure();
228 LLVM_DEBUG({
229 llvm::dbgs() << "period of " << names.size() << " ends in "
230 << loop->getName() << " at " << loop->getLoc() << ": "
231 << period.size() << " events:";
232 for (const Event &event : period)
233 llvm::dbgs() << " " << (event.acquire ? "a" : "r") << event.end << "x"
234 << event.count;
235 llvm::dbgs() << "\n";
236 });
237
238 // Objects the channel moves in a period: those each acquire takes beyond the
239 // ones held, where the channel fills; those released, where it drains. The
240 // first periods may differ while the core builds up what it holds, so the
241 // order is that of the first period starting from a state seen before.
242 SmallVector<int64_t> held(ends, 0);
243 std::map<SmallVector<int64_t>, int> seen;
244 for (int round = 0; round < maxPeriods; round++) {
245 order.clear();
246 SmallVector<int64_t> start = held;
247 for (const Event &event : period) {
248 int64_t &h = held[event.end];
249 if (event.acquire) {
250 if (coreDrains)
251 order.append(std::max<int64_t>(0, event.count - h), event.end);
252 h = std::max(h, event.count);
253 } else {
254 if (event.count > h) {
255 reason = "the core releases objects it does not hold";
256 return failure();
257 }
258 h -= event.count;
259 if (!coreDrains)
260 order.append(event.count, event.end);
261 }
262 }
263 if (!seen.emplace(start, round).second) {
264 if (order.empty()) {
265 idle = true;
266 reason = "the core's period moves none of their objects";
267 return failure();
268 }
269 if (tails.empty())
270 return success();
271 SmallVector<std::pair<ObjectFifoReleaseOp, unsigned>> releases;
272 for (Operation *op : llvm::concat<Operation *const>(uses, tails))
273 if (auto release = dyn_cast<ObjectFifoReleaseOp>(op))
274 if (std::optional<unsigned> end = endOf(op))
275 releases.push_back({release, *end});
276 return readWholeRun(core, releases, reason);
277 }
278 }
279 reason = "the core never settles into a steady order";
280 return failure();
281}
282
283LogicalResult CoreTurns::readWholeRun(
284 CoreOp core, ArrayRef<std::pair<ObjectFifoReleaseOp, unsigned>> releases,
285 std::string &reason) {
286 // A tail release behind a loop that runs forever is never reached.
287 for (Operation *op = loop; op != core; op = op->getParentOp()) {
288 auto whileOp = dyn_cast<scf::WhileOp>(op);
289 if (whileOp && isForeverLoop(whileOp))
290 return success();
291 }
292
293 SmallVector<int64_t> moved(ends, 0);
294 for (auto [release, end] : releases) {
295 int64_t runs = release.relNumber();
296 for (Operation *parent = release->getParentOp(); parent != core;
297 parent = parent->getParentOp()) {
298 auto forOp = dyn_cast<scf::ForOp>(parent);
299 std::optional<APInt> trips =
300 forOp ? forOp.getStaticTripCount() : std::nullopt;
301 if (!trips || llvm::MulOverflow(runs, trips->getSExtValue(), runs)) {
302 reason = "the core's whole run does not move a static count of them";
303 return failure();
304 }
305 }
306 moved[end] += runs;
307 }
308 wholeRun = std::move(moved);
309 return success();
310}
311
312bool CoreTurns::wholeRunFits(ArrayRef<int64_t> counts) const {
313 // The channel keeps taking its turns from one run of the core to the next,
314 // so a finite core must move each pool's objects a whole number of turns'
315 // worth over its run; otherwise a later run starts out of step with the
316 // turns, and the channel can wait on a full pool while the core waits on
317 // another.
318 if (wholeRun.empty())
319 return true;
320 std::optional<int64_t> whole;
321 for (size_t i = 0; i < ends; i++) {
322 if (!counts[i]) {
323 if (wholeRun[i])
324 return false;
325 continue;
326 }
327 if (wholeRun[i] % counts[i] || (whole && *whole != wholeRun[i] / counts[i]))
328 return false;
329 whole = wholeRun[i] / counts[i];
330 }
331 return true;
332}
333
334bool CoreTurns::keepsUp(ArrayRef<int64_t> depths) {
335 assert(depths.size() == ends && "one depth per endpoint");
336 // The shortest run of the period's order, in the same proportions, that the
337 // channel can repeat, as a loop's steps do; the core's first and last steps
338 // may move them in another order, which the pools' depths then absorb.
339 SmallVector<int64_t> counts(ends, 0);
340 for (unsigned end : order)
341 counts[end]++;
342 for (size_t length = 1; length < order.size(); length++) {
343 if (order.size() % length)
344 continue;
345 size_t repeats = order.size() / length;
346 if (llvm::any_of(counts, [&](int64_t c) { return c % repeats; }))
347 continue;
348 SmallVector<int64_t> perRun(counts);
349 for (int64_t &count : perRun)
350 count /= static_cast<int64_t>(repeats);
351 if (!wholeRunFits(perRun))
352 continue;
353 std::set<SmallVector<unsigned>> tried;
354 // Counts for the window order[start, start + length), maintained
355 // incrementally across start (one element leaves, one enters per step)
356 // instead of recomputed from scratch, so the cheap proportionality
357 // filter below runs before a window is ever materialized, deduped or
358 // simulated, not after.
359 SmallVector<int64_t> runCounts(ends, 0);
360 for (size_t i = 0; i < length; i++)
361 runCounts[order[i]]++;
362 for (size_t start = 0; start + length <= order.size(); start++) {
363 if (start > 0) {
364 runCounts[order[start - 1]]--;
365 runCounts[order[start + length - 1]]++;
366 }
367 bool proportional = true;
368 for (size_t i = 0; i < ends; i++)
369 proportional &=
370 runCounts[i] * static_cast<int64_t>(repeats) == counts[i];
371 if (!proportional)
372 continue;
373 SmallVector<unsigned> run(order.begin() + start,
374 order.begin() + start + length);
375 if (!tried.insert(run).second || !keepsUp(run, depths))
376 continue;
377 order = run;
378 return true;
379 }
380 }
381 return wholeRunFits(counts) && keepsUp(order, depths);
382}
383
384Operation *CoreTurns::periodAcquire() const {
385 for (const Event &event : period)
386 if (event.acquire)
387 return event.op;
388 return nullptr;
389}
390
391bool CoreTurns::keepsUp(ArrayRef<unsigned> order,
392 ArrayRef<int64_t> depths) const {
393 // Objects ready for the core (full where it drains, free where it fills)
394 // and for the channel (the other kind); the core holds what it acquired.
395 SmallVector<int64_t> forCore(ends, 0), forChannel(ends, 0), held(ends, 0);
396 for (size_t i = 0; i < ends; i++)
397 (coreDrains ? forChannel : forCore)[i] = depths[i];
398 size_t turn = 0, event = 0;
399 std::map<SmallVector<int64_t>, int> seen;
400 for (int round = 0; round < maxPeriods * 4;) {
401 bool moved = false;
402 while (forChannel[order[turn]] > 0) {
403 forChannel[order[turn]]--;
404 forCore[order[turn]]++;
405 turn = (turn + 1) % order.size();
406 moved = true;
407 }
408 while (true) {
409 const Event &e = period[event];
410 if (e.acquire) {
411 int64_t take = std::max<int64_t>(0, e.count - held[e.end]);
412 if (forCore[e.end] < take)
413 break;
414 forCore[e.end] -= take;
415 held[e.end] = std::max(held[e.end], e.count);
416 } else {
417 held[e.end] -= e.count;
418 forChannel[e.end] += e.count;
419 }
420 moved = true;
421 if (++event == period.size()) {
422 event = 0;
423 round++;
424 SmallVector<int64_t> state{static_cast<int64_t>(turn)};
425 llvm::append_range(state, forCore);
426 llvm::append_range(state, forChannel);
427 llvm::append_range(state, held);
428 if (!seen.emplace(state, round).second)
429 return true;
430 }
431 }
432 if (!moved)
433 return false;
434 }
435 return false;
436}
mlir::LogicalResult read(llvm::ArrayRef< ObjectFifoCoreEndpointOp > ends, std::string &reason)
Reads the order off the program of the core working through ends, all draining (the channel fills the...
bool keepsUp(llvm::ArrayRef< int64_t > depths)
Whether a channel moving objects in turns() order forever, through pools of depths,...
mlir::Operation * periodAcquire() const
The first acquire the period runs, with its branches folded; null when it runs none.
bool isForeverLoop(mlir::scf::WhileOp whileOp)
Whether whileOp repeats forever: its condition is a constant true, and its condition region does noth...