MLIR-AIE 1.4.6.dev
AIEObjectFifoVerify.cpp
Go to the documentation of this file.
1//===- AIEObjectFifoVerify.cpp ----------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2026 Advanced Micro Devices, Inc.
4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5//
6//===----------------------------------------------------------------------===//
7
15
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/Dialect/MemRef/IR/MemRef.h"
18#include "mlir/Dialect/SCF/IR/SCF.h"
19#include "mlir/Dialect/Utils/StaticValueUtils.h"
20#include "mlir/IR/Matchers.h"
21#include "mlir/Interfaces/DataLayoutInterfaces.h"
22#include "mlir/Pass/Pass.h"
23#include "llvm/ADT/MapVector.h"
24#include "llvm/ADT/SetVector.h"
25#include "llvm/ADT/TypeSwitch.h"
26#include "llvm/Support/CheckedArithmetic.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/MathExtras.h"
29
30#include <algorithm>
31#include <functional>
32#include <memory>
33#include <numeric>
34#include <optional>
35
36using namespace mlir;
37using namespace xilinx;
38using namespace xilinx::AIE;
39
40#define DEBUG_TYPE "aie-objectfifo-verify"
41
42namespace xilinx::AIE {
43#define GEN_PASS_DEF_AIEOBJECTFIFOVERIFY
44#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
45} // namespace xilinx::AIE
46
47namespace {
48
49struct SegmentActors {
50 SmallVector<Operation *> fillers;
51 SmallVector<Operation *> drainers;
52};
53
54/// A DMA endpoint with an iteration count moves this many objects through its
55/// pool, then stops.
56struct TransferBudget {
57 ObjectFifoDmaEndpointOp endpoint;
58 int32_t iterations;
59 int64_t objects;
60};
61
62static std::optional<int64_t> getStaticTripCount(scf::ForOp forOp) {
63 if (forOp.getSingleLowerBound() && forOp.getSingleUpperBound() &&
64 forOp.getSingleStep()) {
65 if (std::optional<llvm::APInt> tc = forOp.getStaticTripCount()) {
66 return tc->getSExtValue();
67 }
68 }
69 return std::nullopt;
70}
71
72/// Whether `op` is a loop that runs forever: an `scf.while` on a constant true
73/// condition. An `scf.for` runs its trip count, however large.
74static bool runsForever(Operation *op) {
75 auto whileOp = dyn_cast<scf::WhileOp>(op);
76 return whileOp && isForeverLoop(whileOp);
77}
78
79/// Objects of the fifo `name` still held after `block` runs, entered holding
80/// `held`: an acquire holds at least its count, a release gives its count
81/// back. Unknown when an access sits under anything but a static loop, or a
82/// loop's count has not settled after two passes.
83static std::optional<int64_t> heldAfter(Block &block, StringRef name,
84 int64_t held) {
85 for (Operation &op : block) {
86 if (auto acquire = dyn_cast<ObjectFifoAcquireOp>(op)) {
87 if (acquire.getObjFifoName() == name)
88 held = std::max<int64_t>(held, acquire.acqNumber());
89 continue;
90 }
91 if (auto release = dyn_cast<ObjectFifoReleaseOp>(op)) {
92 if (release.getObjFifoName() == name)
93 held -= release.relNumber();
94 if (held < 0)
95 return std::nullopt;
96 continue;
97 }
98 bool touches = op.getNumRegions() != 0 &&
99 op.walk([&](Operation *inner) {
100 auto acquire = dyn_cast<ObjectFifoAcquireOp>(inner);
101 auto release = dyn_cast<ObjectFifoReleaseOp>(inner);
102 if ((acquire && acquire.getObjFifoName() == name) ||
103 (release && release.getObjFifoName() == name))
104 return WalkResult::interrupt();
105 return WalkResult::advance();
106 }).wasInterrupted();
107 if (!touches)
108 continue;
109 auto forOp = dyn_cast<scf::ForOp>(op);
110 std::optional<int64_t> trip =
111 forOp ? getStaticTripCount(forOp) : std::nullopt;
112 if (!trip)
113 return std::nullopt;
114 if (*trip == 0)
115 continue;
116 std::optional<int64_t> once = heldAfter(*forOp.getBody(), name, held);
117 if (!once)
118 return std::nullopt;
119 if (*trip > 1 && heldAfter(*forOp.getBody(), name, *once) != once)
120 return std::nullopt;
121 held = *once;
122 }
123 return held;
124}
125
126/// The trip count of `forOp`: static, or an upper bound the host writes as
127/// one constant for every dispatch. That is a word of an `aie.buffer` of
128/// 32-bit words the cores only load, which every runtime sequence of the
129/// device writes with the same constant (`aiex.npu.rtp_write`), directly in
130/// its body, before it sets a lock (`aiex.set_lock`) the core waits on ahead
131/// of the load. The lock starts at 0 and each release gives back no more
132/// than the acquire just before it took, so every load follows a write.
133static std::optional<int64_t> tripCount(scf::ForOp forOp, DeviceOp device) {
134 if (std::optional<int64_t> trip = getStaticTripCount(forOp))
135 return trip;
136 std::optional<int64_t> lower = getConstantIntValue(forOp.getLowerBound());
137 std::optional<int64_t> step = getConstantIntValue(forOp.getStep());
138 Value bound = forOp.getUpperBound();
139 if (auto cast = bound.getDefiningOp<arith::IndexCastOp>())
140 bound = cast.getIn();
141 auto load = bound.getDefiningOp<memref::LoadOp>();
142 if (!lower || !step || *step <= 0 || !load || load.getIndices().size() != 1)
143 return std::nullopt;
144 std::optional<int64_t> index = getConstantIntValue(load.getIndices().front());
145 auto buffer = load.getMemRef().getDefiningOp<BufferOp>();
146 // An RTP write's index counts 32-bit words, so only in a buffer of them is
147 // that the element the load reads.
148 auto type = buffer ? dyn_cast<MemRefType>(buffer.getType()) : MemRefType();
149 if (!index || !type || !type.getElementType().isInteger(32) ||
150 !type.getLayout().isIdentity() || !buffer.getSymName() ||
151 buffer.getInitialValue() ||
152 llvm::any_of(buffer->getUsers(),
153 [](Operation *user) { return !isa<memref::LoadOp>(user); }))
154 return std::nullopt;
155
156 UseLockOp wait;
157 for (Operation *prev = load->getPrevNode(); prev && !wait;
158 prev = prev->getPrevNode())
159 if (auto use = dyn_cast<UseLockOp>(prev); use && !use.release())
160 wait = use;
161 std::optional<int64_t> waitsFor =
162 wait ? getConstantIntValue(wait.getValue()) : std::nullopt;
163 LockOp lock = wait ? wait.getLock().getDefiningOp<LockOp>() : LockOp();
164 if (!lock || !wait.acquireGE() || !waitsFor || *waitsFor < 1 ||
165 !wait.getAcqEn() ||
166 wait.getBlocking().value_or(LockBlocking::Blocking) !=
167 LockBlocking::Blocking ||
168 lock.getInit().value_or(0) != 0)
169 return std::nullopt;
170 for (Operation *user : lock->getUsers()) {
171 if (isa<AIEX::SetLockOp>(user))
172 continue;
173 auto use = dyn_cast<UseLockOp>(user);
174 if (!use)
175 return std::nullopt;
176 if (!use.release())
177 continue;
178 std::optional<int64_t> given = getConstantIntValue(use.getValue());
179 UseLockOp before;
180 for (Operation *prev = use->getPrevNode(); prev && !before;
181 prev = prev->getPrevNode())
182 if (auto other = dyn_cast<UseLockOp>(prev);
183 other && other.getLock() == use.getLock())
184 before = other;
185 std::optional<int64_t> taken = before && !before.release()
186 ? getConstantIntValue(before.getValue())
187 : std::nullopt;
188 if (!given || !taken || *given > *taken)
189 return std::nullopt;
190 }
191
192 TileOp tile = buffer.getTileOp();
193 const AIETargetModel &tm = device.getTargetModel();
194 auto reachesTile = [&](FlatSymbolRefAttr named, std::optional<int32_t> col,
195 std::optional<int32_t> row,
196 std::optional<int64_t> address) {
197 if (named)
198 return named.getValue() == *buffer.getSymName();
199 if (!col || !row) {
200 if (!address)
201 return true;
202 col = *address >> tm.getColumnShift();
203 row = (*address >> tm.getRowShift()) &
204 ((1 << (tm.getColumnShift() - tm.getRowShift())) - 1);
205 }
206 return *col == tile.getCol() && *row == tile.getRow();
207 };
208
209 std::optional<int64_t> value;
210 for (auto sequence : device.getOps<RuntimeSequenceOp>()) {
211 bool written = false;
212 WalkResult walk = sequence.walk([&](Operation *op) {
213 bool rawWrite =
214 llvm::TypeSwitch<Operation *, bool>(op)
215 .Case<AIEX::NpuWrite32Op, AIEX::NpuMaskWrite32Op>([&](auto w) {
216 return reachesTile(w.getBufferAttr(), w.getColumn(), w.getRow(),
217 getConstantIntValue(w.getAddress()));
218 })
219 .Case([&](AIEX::NpuBlockWriteOp w) {
220 return reachesTile(w.getBufferAttr(), w.getColumn(), w.getRow(),
221 w.getAddress());
222 })
223 .Case([&](AIEX::NpuPushQueueOp push) {
224 return reachesTile({}, push.getColumn(), push.getRow(), {});
225 })
226 .Default(false);
227 if (rawWrite)
228 return WalkResult::interrupt();
229 if (auto write = dyn_cast<AIEX::NpuWriteRTPOp>(op)) {
230 if (write.getBuffer() != *buffer.getSymName() ||
231 write.getIndex() != *index)
232 return WalkResult::advance();
233 // A write under a branch or a loop may never run.
234 std::optional<int64_t> word = getConstantIntValue(write.getValue());
235 if (write->getParentOp() != sequence || !word ||
236 (value && *value != *word))
237 return WalkResult::interrupt();
238 value = word;
239 written = true;
240 return WalkResult::advance();
241 }
242 auto set = dyn_cast<AIEX::SetLockOp>(op);
243 if (set && set.getLock() == lock.getResult() && !written)
244 return WalkResult::interrupt();
245 return WalkResult::advance();
246 });
247 if (walk.wasInterrupted())
248 return std::nullopt;
249 }
250 if (!value)
251 return std::nullopt;
252 return *value > *lower ? (*value - *lower + *step - 1) / *step : 0;
253}
254
255/// The ratio (in, out) such that a core, once it has released r objects of
256/// `out`, has taken at least r * in / out objects of `in`, at every point.
257///
258/// Each region of the core is summarized by two sets of (taken, released)
259/// pairs: for a ratio k, the smallest taken - k * released over `end` bounds
260/// that value where the region ends, and over `low` at every point inside it,
261/// on every path. A branch may take either arm and a loop whose trip count
262/// `tripCount` cannot tell may run any number of times, so the ratio holds
263/// whatever decides them. Unknown when a branch's arms, or the passes of a
264/// loop whose count is unknown, leave different objects held, or when `in` or
265/// `out` is used under any other region.
266class TakeRatio {
267public:
268 TakeRatio(DeviceOp device, StringRef in, StringRef out)
269 : device(device), in(in), out(out) {}
270
271 std::optional<std::pair<int64_t, int64_t>> of(CoreOp core) {
272 core.walk([&](Operation *op) {
273 if (fifoOf(op) != in && fifoOf(op) != out)
274 return;
275 for (Operation *parent = op->getParentOp(); parent != core;
276 parent = parent->getParentOp())
277 onUsePath.insert(parent);
278 used = true;
279 });
280 Region &body = core.getBody();
281 if (!used || !body.hasOneBlock())
282 return std::nullopt;
283 Held held;
284 std::optional<Effect> effect = analyze(body.front(), held);
285 if (!effect)
286 return std::nullopt;
287 std::optional<Pair> least;
288 for (const Pair &pair : llvm::concat<const Pair>(effect->low, bounds))
289 if (pair.released > 0 && (!least || pair.taken * least->released <
290 least->taken * pair.released))
291 least = pair;
292 if (!least || least->taken == 0)
293 return std::nullopt;
294 int64_t common = std::gcd(least->taken, least->released);
295 return std::make_pair(least->taken / common, least->released / common);
296 }
297
298private:
299 struct Pair {
300 int64_t taken, released;
301 };
302 struct Effect {
303 SmallVector<Pair> end = {{0, 0}}, low = {{0, 0}};
304 };
305 struct Held {
306 int64_t in = 0, out = 0;
307 bool operator==(const Held &other) const {
308 return in == other.in && out == other.out;
309 }
310 };
311 static constexpr size_t maxPairs = 64;
312 static constexpr int64_t maxPeeledPasses = 4096;
313
314 static StringRef fifoOf(Operation *op) {
315 if (auto acquire = dyn_cast<ObjectFifoAcquireOp>(op))
316 return acquire.getObjFifoName();
317 if (auto release = dyn_cast<ObjectFifoReleaseOp>(op))
318 return release.getObjFifoName();
319 return {};
320 }
321
322 // Keeps the pairs no other bounds from below: one with no more taken and no
323 // fewer released gives a smaller taken - k * released for every k >= 0.
324 std::optional<SmallVector<Pair>> prune(ArrayRef<Pair> pairs) {
325 SmallVector<Pair> kept;
326 for (auto [index, pair] : llvm::enumerate(pairs)) {
327 bool dominated = false;
328 for (auto [other, by] : llvm::enumerate(pairs))
329 dominated |= other != index && by.taken <= pair.taken &&
330 by.released >= pair.released &&
331 (by.taken != pair.taken || by.released != pair.released ||
332 other < index);
333 if (!dominated)
334 kept.push_back(pair);
335 }
336 if (kept.size() > maxPairs)
337 return std::nullopt;
338 return kept;
339 }
340
341 std::optional<SmallVector<Pair>> sum(ArrayRef<Pair> a, ArrayRef<Pair> b) {
342 SmallVector<Pair> sums;
343 for (const Pair &x : a)
344 for (const Pair &y : b) {
345 Pair both;
346 if (llvm::AddOverflow(x.taken, y.taken, both.taken) ||
347 llvm::AddOverflow(x.released, y.released, both.released))
348 return std::nullopt;
349 sums.push_back(both);
350 }
351 return prune(sums);
352 }
353
354 std::optional<SmallVector<Pair>> scale(ArrayRef<Pair> pairs, int64_t n) {
355 SmallVector<Pair> scaled;
356 for (const Pair &pair : pairs) {
357 Pair times;
358 if (llvm::MulOverflow(pair.taken, n, times.taken) ||
359 llvm::MulOverflow(pair.released, n, times.released))
360 return std::nullopt;
361 scaled.push_back(times);
362 }
363 return scaled;
364 }
365
366 std::optional<Effect> then(const Effect &first, const Effect &second) {
367 std::optional<SmallVector<Pair>> end = sum(first.end, second.end);
368 std::optional<SmallVector<Pair>> late = sum(first.end, second.low);
369 if (!end || !late)
370 return std::nullopt;
371 std::optional<SmallVector<Pair>> low =
372 prune(llvm::to_vector(llvm::concat<const Pair>(first.low, *late)));
373 if (!low)
374 return std::nullopt;
375 return Effect{*end, *low};
376 }
377
378 std::optional<Effect> either(const Effect &a, const Effect &b) {
379 std::optional<SmallVector<Pair>> end =
380 prune(llvm::to_vector(llvm::concat<const Pair>(a.end, b.end)));
381 std::optional<SmallVector<Pair>> low =
382 prune(llvm::to_vector(llvm::concat<const Pair>(a.low, b.low)));
383 if (!end || !low)
384 return std::nullopt;
385 return Effect{*end, *low};
386 }
387
388 // `n` >= 1 passes of `pass`, each starting with the objects it ends with
389 // held: the value at a point of pass j is j times a pass's end plus a point
390 // of one pass, smallest at j = 0 or j = n - 1.
391 std::optional<Effect> repeat(const Effect &pass, int64_t n) {
392 std::optional<SmallVector<Pair>> end = scale(pass.end, n);
393 std::optional<SmallVector<Pair>> before = scale(pass.end, n - 1);
394 std::optional<SmallVector<Pair>> late =
395 before ? sum(*before, pass.low) : std::nullopt;
396 if (!end || !late)
397 return std::nullopt;
398 std::optional<SmallVector<Pair>> low =
399 prune(llvm::to_vector(llvm::concat<const Pair>(pass.low, *late)));
400 std::optional<SmallVector<Pair>> ends = prune(*end);
401 if (!low || !ends)
402 return std::nullopt;
403 return Effect{*ends, *low};
404 }
405
406 // Any number of passes: the ratio must keep each pass's end at or above
407 // its start, recorded in `bounds`; then a point of pass j is no lower than
408 // a point of one pass, and the end no lower than the start.
409 Effect anyRepeat(const Effect &pass) {
410 llvm::append_range(bounds, pass.end);
411 Effect any;
412 llvm::append_range(any.low, pass.low);
413 return any;
414 }
415
416 std::optional<Effect> analyze(Block &block, Held &held) {
417 Effect effect;
418 for (Operation &op : block) {
419 std::optional<Effect> step = analyzeOp(op, held);
420 if (!step)
421 return std::nullopt;
422 std::optional<Effect> next = then(effect, *step);
423 if (!next)
424 return std::nullopt;
425 effect = *next;
426 }
427 return effect;
428 }
429
430 std::optional<Effect> analyzeOp(Operation &op, Held &held) {
431 StringRef fifo = fifoOf(&op);
432 if (fifo == in || fifo == out) {
433 int64_t &count = fifo == in ? held.in : held.out;
434 Effect effect;
435 if (auto acquire = dyn_cast<ObjectFifoAcquireOp>(op)) {
436 int64_t wanted = acquire.acqNumber();
437 if (fifo == in)
438 effect.end = {{std::max<int64_t>(0, wanted - count), 0}};
439 count = std::max(count, wanted);
440 return effect;
441 }
442 int64_t released = cast<ObjectFifoReleaseOp>(op).relNumber();
443 if (released > count)
444 return std::nullopt;
445 count -= released;
446 if (fifo == out) {
447 effect.end = {{0, released}};
448 effect.low.push_back({0, released});
449 }
450 return effect;
451 }
452 if (!onUsePath.contains(&op))
453 return Effect();
454 if (auto forOp = dyn_cast<scf::ForOp>(op)) {
455 std::optional<int64_t> trip = tripCount(forOp, device);
456 Held entry = held;
457 if (!trip) {
458 std::optional<Effect> pass = analyze(*forOp.getBody(), held);
459 if (!pass || !(held == entry))
460 return std::nullopt;
461 return anyRepeat(*pass);
462 }
463 Effect total;
464 for (int64_t done = 0; done < *trip; ++done) {
465 Held before = held;
466 std::optional<Effect> pass = analyze(*forOp.getBody(), held);
467 std::optional<Effect> rest = pass;
468 // Any number of passes covers this many, where counting overflows.
469 if (pass && held == before) {
470 rest = repeat(*pass, *trip - done);
471 if (!rest)
472 rest = anyRepeat(*pass);
473 }
474 std::optional<Effect> next = rest ? then(total, *rest) : std::nullopt;
475 if (!next || (!(held == before) && done >= maxPeeledPasses))
476 return std::nullopt;
477 total = *next;
478 if (held == before)
479 break;
480 }
481 return total;
482 }
483 if (auto ifOp = dyn_cast<scf::IfOp>(op)) {
484 Held otherwise = held;
485 std::optional<Effect> taken = analyze(ifOp.getThenRegion().front(), held);
486 std::optional<Effect> skipped =
487 ifOp.getElseRegion().empty()
488 ? Effect()
489 : analyze(ifOp.getElseRegion().front(), otherwise);
490 if (!taken || !skipped || !(held == otherwise))
491 return std::nullopt;
492 return either(*taken, *skipped);
493 }
494 if (auto whileOp = dyn_cast<scf::WhileOp>(op)) {
495 Held entry = held;
496 std::optional<Effect> check = analyze(*whileOp.getBeforeBody(), held);
497 Held afterCheck = held;
498 std::optional<Effect> body =
499 check ? analyze(*whileOp.getAfterBody(), held) : std::nullopt;
500 if (!body || !(held == entry))
501 return std::nullopt;
502 held = afterCheck;
503 std::optional<Effect> pass = then(*body, *check);
504 return pass ? then(*check, anyRepeat(*pass)) : std::nullopt;
505 }
506 return std::nullopt;
507 }
508
509 DeviceOp device;
510 StringRef in, out;
511 llvm::SmallPtrSet<Operation *, 16> onUsePath;
512 bool used = false;
513 // Pass ends of loops that may run any number of times.
514 SmallVector<Pair> bounds;
515};
516
517struct AIEObjectFifoVerifyPass
518 : public xilinx::AIE::impl::AIEObjectFifoVerifyBase<
519 AIEObjectFifoVerifyPass> {
520
521 /// Which pools get locks. Without locks nothing waits on a release, and
522 /// nothing a core holds stays taken.
523 std::shared_ptr<PoolLocks> poolLocks;
524
525 /// Every segment needs an actor at each end, so that what one writes another
526 /// reads. A segment may go unfilled when the pool's objects start full, and
527 /// may name no endpoint at an end its `manualFill` or `manualDrain` hands to
528 /// a DMA program the author writes.
529 LogicalResult verifyActors(ObjectFifoPoolOp pool,
530 ArrayRef<SegmentActors> actors) {
531 bool external = llvm::any_of(pool.getBufferOps(), [](BufferLike buffer) {
532 return isa<ExternalBufferOp>(buffer.getOperation());
533 });
534 std::vector<ObjectFifoSegmentOp> segmentOps = pool.getSegmentOps();
535 for (auto [index, segment] : llvm::enumerate(actors)) {
536 ObjectFifoSegmentOp segmentOp = segmentOps[index];
537 bool manualFill = segmentOp.getManualFill();
538 bool manualDrain = segmentOp.getManualDrain();
539 if (segment.fillers.size() > 1 ||
540 (manualFill && !segment.fillers.empty())) {
541 return pool.emitOpError("segment ")
542 << index << " is filled by more than one endpoint";
543 }
544 if (segment.drainers.size() > 1 ||
545 (manualDrain && !segment.drainers.empty())) {
546 return pool.emitOpError("segment ")
547 << index << " is drained by more than one endpoint";
548 }
549 // The host works an external pool's buffers, so it stands in for the end
550 // this device does not program.
551 bool hostDrains = external && !segment.fillers.empty();
552 bool hostFills = external && !segment.drainers.empty();
553 if (segment.drainers.empty() && !hostDrains && !manualDrain) {
554 return pool.emitOpError("segment ") << index << " has no drainer";
555 }
556 if (segment.fillers.empty() && !pool.getInitValues() && !hostFills &&
557 !manualFill) {
558 return pool.emitOpError("segment ") << index << " has no filler";
559 }
560 }
561 return success();
562 }
563
564 /// An endpoint that is not connected carries data nowhere.
565 LogicalResult verifyFlows(DeviceOp device,
566 SymbolTableCollection &symbolTables) {
567 DenseMap<StringRef, int> appearances;
568 for (auto flow : device.getOps<RouteOp>()) {
569 for (StringRef source : flow.getSourceNames()) {
570 appearances[source]++;
571 }
572 for (StringRef dest : flow.getDestinationNames()) {
573 appearances[dest]++;
574 }
575 }
576
577 for (auto endpoint : device.getOps<RouteEndpoint>()) {
578 int count =
579 appearances.lookup(cast<SymbolOpInterface>(*endpoint).getName());
580 if (count == 0) {
581 return endpoint->emitOpError("is not connected by any flow");
582 }
583 if (auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(*endpoint);
584 dma && dma.getDispatch()) {
585 if (failed(verifyDispatch(device, dma, symbolTables)))
586 return failure();
587 continue;
588 }
589 // An aie.route_endpoint's own verifier says which flows may share it.
590 if (count > 1 && !isa<RouteEndpointOp>(endpoint.getOperation())) {
591 return endpoint->emitOpError(
592 "drives one channel, so at most one flow may name it, but "
593 "it is named ")
594 << count << " times";
595 }
596 }
597 return success();
598 }
599
600 /// A dispatching endpoint is the one source of one packet-switched route per
601 /// destination it takes turns between, and of nothing else. A second route to
602 /// the same destination is refused there, by the count every endpoint gets.
603 LogicalResult verifyDispatch(DeviceOp device,
604 ObjectFifoDmaEndpointOp endpoint,
605 SymbolTableCollection &symbolTables) {
606 StringRef name = endpoint.getSymName();
607 llvm::SmallSetVector<StringRef, 4> turns;
608 for (StringRef dest :
609 endpoint.getDispatchAttr().getAsValueRange<FlatSymbolRefAttr>())
610 turns.insert(dest);
611 llvm::SmallDenseSet<StringRef, 4> reached;
612 for (auto flow : device.getOps<RouteOp>()) {
613 if (flow.namesAsDestination(name))
614 return flow.emitOpError("names dispatching endpoint @")
615 << name << " as a destination";
616 if (!flow.namesAsSource(name))
617 continue;
618 if (flow.getSources().size() != 1 || flow.getDestinations().size() != 1)
619 return flow.emitOpError("leaves dispatching endpoint @")
620 << name
621 << " for one destination, so it has one source and "
622 "one destination";
623 if (!flow.getPacket())
624 return flow.emitOpError("leaves dispatching endpoint @")
625 << name << " and needs a packet header to tell its turns apart";
626 StringRef dest = *flow.getDestinationNames().begin();
627 if (!turns.contains(dest))
628 return flow.emitOpError("reaches @")
629 << dest << ", which dispatching endpoint @" << name
630 << " never takes a turn for";
631 reached.insert(dest);
632 }
633 for (StringRef dest : turns)
634 if (!reached.contains(dest))
635 return endpoint.emitOpError("dispatches to @")
636 << dest << ", but no route from it reaches there";
637
638 // Every turn moves the same chain through the dispatching endpoint, one
639 // object per turn, so each turn's destination must move as many elements
640 // as the dispatching endpoint itself does.
641 int64_t elements = transferElements(endpoint);
642 for (StringRef dest : turns) {
643 auto destEndpoint = symbolTables.lookupSymbolIn<ObjectFifoDmaEndpointOp>(
644 device, StringAttr::get(device.getContext(), dest));
645 if (!destEndpoint)
646 continue;
647 int64_t destElements = transferElements(destEndpoint);
648 if (destElements != elements)
649 return endpoint.emitOpError("dispatches, so every turn moves ")
650 << elements << " elements, but @" << dest << " moves "
651 << destElements;
652 }
653 return success();
654 }
655
656 /// The elements one pass of an endpoint's chain moves: each selected segment
657 /// once, through its transform where it has one.
658 static int64_t transferElements(ObjectFifoDmaEndpointOp endpoint) {
659 int64_t elements = 0;
660 std::optional<ArrayRef<BDDimLayoutArrayAttr>> dimensions =
661 endpoint.getDimensions();
662 for (auto [index, segment] :
663 llvm::enumerate(endpoint.getSelectedSegments())) {
664 BDDimLayoutArrayAttr dims;
665 if (dimensions && index < dimensions->size()) {
666 dims = (*dimensions)[index];
667 }
668 if (dims && !dims.empty()) {
669 int64_t product = 1;
670 for (BDDimLayoutAttr dim : dims) {
671 product *= dim.getSize();
672 }
673 elements += product;
674 } else {
675 elements += segment.getSize();
676 }
677 }
678 return elements;
679 }
680
681 /// A fan-in's destination fills its next object with whatever packet
682 /// arrives, and a packet is one pass of its sender's chain, so every end has
683 /// to move the same number of elements or two senders share an object. A
684 /// route endpoint's transfers are the runtime's and are not checked here.
685 LogicalResult verifyFanIn(DeviceOp device,
686 SymbolTableCollection &symbolTables) {
687 for (auto flow : device.getOps<RouteOp>()) {
688 if (!flow.isFanIn()) {
689 continue;
690 }
691 std::optional<std::pair<StringRef, int64_t>> first;
692 auto check = [&](StringRef name) -> LogicalResult {
693 auto endpoint = symbolTables.lookupSymbolIn<ObjectFifoDmaEndpointOp>(
694 device, StringAttr::get(device.getContext(), name));
695 if (!endpoint) {
696 return success();
697 }
698 int64_t elements = transferElements(endpoint);
699 if (!first) {
700 first = {name, elements};
701 return success();
702 }
703 if (elements != first->second) {
704 return flow.emitOpError("fans in, so every end moves one object of "
705 "the same size, but @")
706 << first->first << " moves " << first->second
707 << " elements and @" << name << " moves " << elements;
708 }
709 return success();
710 };
711 for (StringRef name : flow.getSourceNames()) {
712 if (failed(check(name))) {
713 return failure();
714 }
715 }
716 for (StringRef name : flow.getDestinationNames()) {
717 if (failed(check(name))) {
718 return failure();
719 }
720 }
721 }
722 return success();
723 }
724
725 /// A loop body that releases more than it acquires underflows the held count
726 /// as it repeats, whatever the trip count. Accesses split across nesting
727 /// levels are excluded: balancing them needs the inner trip counts. This runs
728 /// before lowering because afterwards the imbalance survives only as
729 /// loop-carried lock values, which no scan can decide.
730 LogicalResult verifyOverRelease(DeviceOp device) {
731 for (auto coreOp : device.getOps<CoreOp>()) {
732 WalkResult result = coreOp.walk([&](Operation *loop) {
733 if (!isObjectFifoLoop(loop)) {
734 return WalkResult::advance();
735 }
736 auto directlyIn = [&](Operation *op) {
737 return getObjectFifoLoopParent(op) == loop;
738 };
739 DenseMap<StringRef, int64_t> acquired;
740 DenseMap<StringRef, int64_t> released;
741 DenseMap<StringRef, Operation *> blame;
742 DenseSet<StringRef> spansNestedLoop;
743
744 loop->walk([&](ObjectFifoAcquireOp a) {
745 StringRef key = a.getObjFifoName();
746 if (!directlyIn(a)) {
747 spansNestedLoop.insert(key);
748 } else {
749 acquired[key] += a.acqNumber();
750 blame.try_emplace(key, a);
751 }
752 });
753 loop->walk([&](ObjectFifoReleaseOp r) {
754 StringRef key = r.getObjFifoName();
755 if (!directlyIn(r)) {
756 spansNestedLoop.insert(key);
757 } else {
758 released[key] += r.relNumber();
759 blame.try_emplace(key, r);
760 }
761 });
762
763 for (auto &[key, count] : released) {
764 if (spansNestedLoop.contains(key) || count <= acquired.lookup(key)) {
765 continue;
766 }
767 blame.lookup(key)->emitOpError(
768 "cannot release more elements than are already acquired");
769 return WalkResult::interrupt();
770 }
771 return WalkResult::advance();
772 });
773 if (result.wasInterrupted()) {
774 return failure();
775 }
776 }
777 return success();
778 }
779
780 /// A DMA endpoint with an iteration count stops after `iterCount * depth`
781 /// objects, so a core that must release more through the same pool waits
782 /// forever for the rest, or leaves objects it filled unsent. Only
783 /// releases static loop bounds force are counted, so what is reported is
784 /// certain; a conditional release, or one in an `scf.while` such as a loop
785 /// that runs forever, is left out, since such a core stalling once the data
786 /// stops is how those designs end. An `scf.for` counts its trip count,
787 /// however large. When all of a core's releases are counted, the DMA endpoint
788 /// is bounded too: it cannot drain more than the core hands over, nor fill
789 /// more than the pool's depth plus what the core releases.
790 LogicalResult verifyTransferBudgets(DeviceOp device) {
791 DenseMap<Operation *, TransferBudget> budgets;
792 for (auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>()) {
793 std::optional<int32_t> iterations = endpoint.getIterCount();
794 ObjectFifoPoolOp pool = endpoint.getPoolOp();
795 if (!iterations || !pool) {
796 continue;
797 }
798 budgets[pool] = {endpoint, *iterations,
799 int64_t{*iterations} * pool.getDepth()};
800 }
801 if (budgets.empty()) {
802 return success();
803 }
804
805 DenseMap<StringRef, int64_t> released;
806 DenseMap<StringRef, ObjectFifoReleaseOp> blame;
807 DenseSet<StringRef> uncounted;
808 device.walk([&](ObjectFifoReleaseOp release) {
809 StringRef key = release.getObjFifoName();
810 std::optional<int64_t> runs = AIEX::staticExecutions(release);
811 if (!runs) {
812 uncounted.insert(key);
813 return;
814 }
815 released[key] += *runs * release.relNumber();
816 blame.try_emplace(key, release);
817 });
818 DenseSet<StringRef> acquired;
819 device.walk([&](ObjectFifoAcquireOp acquire) {
820 acquired.insert(acquire.getObjFifoName());
821 });
822
823 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>()) {
824 // A segment-selecting endpoint sees a share of the pool, not the whole.
825 auto budget = budgets.find(endpoint.getPoolOp());
826 if (budget == budgets.end() || endpoint.getSegments()) {
827 continue;
828 }
829 StringRef name = endpoint.getSymName();
830 int64_t count = released.lookup(name);
831 ObjectFifoDmaEndpointOp dma = budget->second.endpoint;
832 ObjectFifoPoolOp pool = endpoint.getPoolOp();
833 int64_t depth = pool.getDepth();
834 if (count > budget->second.objects) {
835 InFlightDiagnostic diag =
836 blame.lookup(name).emitOpError("releases ")
837 << count << " objects through @" << name
838 << " over the run, but the pool's DMA endpoint stops after "
839 << budget->second.objects << " (iterCount "
840 << budget->second.iterations << " x depth " << depth << ")";
841 // A producer finishes while the pool still has free objects to fill.
842 if (!endpoint.drains() && count <= budget->second.objects + depth)
843 diag << ", leaving " << count - budget->second.objects
844 << " in the pool unsent";
845 else
846 diag << ", so the core would wait forever for the rest";
847 diag.attachNote(dma.getLoc()) << "the DMA endpoint is here";
848 return failure();
849 }
850
851 if (!acquired.contains(name) || uncounted.contains(name) ||
852 dma.getSegments() || pool.getInitValues() ||
853 dma.drains() == endpoint.drains() || !poolLocks->needsLocks(pool)) {
854 continue;
855 }
856 int64_t reachable = endpoint.drains() ? count + depth : count;
857 if (budget->second.objects <= reachable) {
858 continue;
859 }
860 InFlightDiagnostic diag =
861 dma.emitOpError(dma.drains() ? "drains " : "fills ")
862 << budget->second.objects << " objects (iterCount "
863 << budget->second.iterations << " x depth " << depth
864 << ") before it stops, but the core releases exactly " << count
865 << " through @" << name;
866 if (endpoint.drains())
867 diag << ", leaving room for only " << reachable;
868 diag << ", so the DMA endpoint would wait forever for the rest";
869 diag.attachNote(endpoint.getLoc()) << "the core endpoint is here";
870 return failure();
871 }
872 return success();
873 }
874
875 /// A core that reaches its end still holding objects never gives their locks
876 /// back, and locks keep their counts until a PDI load, so the next run of
877 /// the configuration finds those objects taken. Only cores certain to end
878 /// are checked: one block, and no `scf.while`. A fifo an
879 /// `aiex.dma_channel_reset_for` re-arms in every runtime sequence that moves
880 /// data through it gets its locks back each launch.
881 LogicalResult verifyHeldAtEnd(DeviceOp device,
882 SymbolTableCollection &symbolTables) {
883 // The sequences that fill or drain a fifo by name must each re-arm it;
884 // where none names it (a link fills it), every sequence must. Every
885 // fifo needs this at most once across however many cores hold it.
886 llvm::DenseMap<StringRef, SmallVector<RuntimeSequenceOp>> launchesByFifo;
887 std::optional<SmallVector<RuntimeSequenceOp>> allLaunches;
888 auto launchesOf = [&](std::optional<StringRef> fifo)
889 -> const SmallVector<RuntimeSequenceOp> & {
890 if (!fifo) {
891 if (!allLaunches)
892 allLaunches.emplace(
893 llvm::to_vector(device.getOps<RuntimeSequenceOp>()));
894 return *allLaunches;
895 }
896 auto [it, inserted] = launchesByFifo.try_emplace(*fifo);
897 if (inserted) {
898 for (auto seq : device.getOps<RuntimeSequenceOp>())
899 if (AIEX::namesFifo(seq, *fifo, symbolTables))
900 it->second.push_back(seq);
901 if (it->second.empty())
902 llvm::append_range(it->second, device.getOps<RuntimeSequenceOp>());
903 }
904 return it->second;
905 };
906 for (auto core : device.getOps<CoreOp>()) {
907 Region &body = core.getBody();
908 if (!body.hasOneBlock())
909 continue;
910 bool mayNotEnd =
911 core.walk([](scf::WhileOp) { return WalkResult::interrupt(); })
912 .wasInterrupted();
913 if (mayNotEnd)
914 continue;
915 llvm::MapVector<StringRef, ObjectFifoAcquireOp> firstAcquire;
916 core.walk([&](ObjectFifoAcquireOp acquire) {
917 firstAcquire.insert({acquire.getObjFifoName(), acquire});
918 });
919 for (auto &[name, acquire] : firstAcquire) {
920 std::optional<int64_t> held = heldAfter(body.front(), name, 0);
921 if (!held || *held == 0)
922 continue;
923 auto endpoint =
924 symbolTables.lookupNearestSymbolFrom<ObjectFifoCoreEndpointOp>(
925 device, acquire.getObjFifoNameAttr());
926 ObjectFifoPoolOp pool = endpoint ? endpoint.getPoolOp() : nullptr;
927 std::optional<StringRef> fifo =
928 pool ? pool.getFifoName() : std::nullopt;
929 auto rearms =
930 fifo ? poolLocks->rearms().find(*fifo) : poolLocks->rearms().end();
931 bool rearmedEveryLaunch =
932 rearms != poolLocks->rearms().end() &&
933 llvm::all_of(launchesOf(fifo), [&](RuntimeSequenceOp seq) {
934 return llvm::any_of(rearms->second, [&](auto reset) {
935 return reset->getParentOp() == seq;
936 });
937 });
938 if (pool && (!poolLocks->needsLocks(pool) || rearmedEveryLaunch))
939 continue;
940 InFlightDiagnostic diag =
941 core.emitOpError("ends with ")
942 << *held << " acquired from @" << name
943 << " never released, so their locks stay taken into the next run "
944 "of this configuration";
945 diag.attachNote(acquire.getLoc()) << "acquired here";
946 return failure();
947 }
948 }
949 return success();
950 }
951
952 /// A core whose loop repeats forever, and whose every repetition acquires
953 /// objects of a pool but releases none, keeps the same objects for good. The
954 /// end opposite it then stops once the pool is full, if it does not stop by
955 /// itself first: checked where that end is a DMA endpoint without an
956 /// iteration count, or a core that moves objects each time its own loop
957 /// repeats forever. A core holding an object acquired before its loop, for
958 /// the whole configuration, is left alone, as is a loop the core may never
959 /// reach.
960 LogicalResult verifyAdvances(DeviceOp device) {
961 // Whether `loop` runs, and repeats forever: it or a loop around it runs
962 // forever, and nothing on the way from the core may skip it.
963 auto repeatsForever = [](Operation *loop) {
964 bool forever = false;
965 for (Operation *op = loop; !isa<CoreOp>(op); op = op->getParentOp()) {
966 Block *block = op->getBlock();
967 if (block != &op->getParentRegion()->front() ||
968 llvm::any_of(
969 llvm::make_range(block->begin(), op->getIterator()),
970 [&](Operation &before) { return runsForever(&before); }))
971 return false;
972 auto forOp = dyn_cast<scf::ForOp>(op);
973 auto whileOp = dyn_cast<scf::WhileOp>(op);
974 std::optional<int64_t> trip =
975 forOp ? getStaticTripCount(forOp) : std::nullopt;
976 if ((forOp && (!trip || *trip == 0)) ||
977 (whileOp && !isForeverLoop(whileOp)))
978 return false;
979 forever |= runsForever(op);
980 Operation *parent = op->getParentOp();
981 if (auto ifOp = dyn_cast<scf::IfOp>(parent)) {
982 bool inThen = op->getParentRegion() == &ifOp.getThenRegion();
983 if (!matchPattern(ifOp.getCondition(), inThen ? m_One() : m_Zero()))
984 return false;
985 } else if (auto parentWhile = dyn_cast<scf::WhileOp>(parent)) {
986 if (op->getParentRegion() != &parentWhile.getAfter())
987 return false;
988 } else if (!isa<scf::ForOp, CoreOp>(parent)) {
989 return false;
990 }
991 }
992 return forever;
993 };
994
995 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>()) {
996 ObjectFifoPoolOp pool = endpoint.getPoolOp();
997 if (!pool || pool.getInitValues() || endpoint.getSegments() ||
998 !poolLocks->needsLocks(pool))
999 continue;
1000 Operation *keepsMoving = nullptr;
1001 for (auto dma : device.getOps<ObjectFifoDmaEndpointOp>())
1002 if (dma.getPoolOp() == pool && dma.drains() != endpoint.drains() &&
1003 !dma.getIterCount() && !dma.getSegments())
1004 keepsMoving = dma;
1005 for (auto other : device.getOps<ObjectFifoCoreEndpointOp>()) {
1006 if (keepsMoving || other.getPoolOp() != pool ||
1007 other.drains() == endpoint.drains() || other.getSegments())
1008 continue;
1009 CoreTurns otherTurns;
1010 std::string otherReason;
1011 if (succeeded(otherTurns.read({other}, otherReason)) &&
1012 repeatsForever(otherTurns.periodLoop()))
1013 keepsMoving = other;
1014 }
1015 if (!keepsMoving)
1016 continue;
1017
1018 CoreTurns turns;
1019 std::string reason;
1020 if (succeeded(turns.read({endpoint}, reason)) || !turns.movesNone() ||
1021 !repeatsForever(turns.periodLoop()))
1022 continue;
1023 auto acquire =
1024 dyn_cast_or_null<ObjectFifoAcquireOp>(turns.periodAcquire());
1025 if (!acquire)
1026 continue;
1027 InFlightDiagnostic diag =
1028 acquire.emitOpError("takes from @")
1029 << endpoint.getSymName()
1030 << " each time its loop repeats, but the loop releases none of "
1031 "them, so ";
1032 if (endpoint.drains())
1033 diag << "the core keeps the same objects forever and the end "
1034 "filling the pool stops once it is full";
1035 else
1036 diag << "nothing the core writes there is ever sent";
1037 diag.attachNote(keepsMoving->getLoc()) << "the other end is here";
1038 return failure();
1039 }
1040 return success();
1041 }
1042
1043 /// Bytes one run of `sequence` moves through the shim endpoint `name`, when
1044 /// every use of it is a DMA task whose starts, repeats and lengths are
1045 /// static.
1046 static std::optional<int64_t> hostBytes(RuntimeSequenceOp sequence,
1047 StringAttr name) {
1048 std::optional<SymbolTable::UseRange> uses =
1049 SymbolTable::getSymbolUses(name, &sequence.getBody());
1050 if (!uses)
1051 return std::nullopt;
1052 std::optional<int64_t> bytes = 0;
1053 for (const SymbolTable::SymbolUse &use : *uses) {
1054 auto task = dyn_cast<AIEX::DMAConfigureTaskForOp>(use.getUser());
1055 std::optional<int64_t> runs =
1056 task ? AIEX::staticExecutions(task) : std::nullopt;
1057 std::optional<int64_t> streamed =
1058 runs ? task.getStaticBytesStreamed() : std::nullopt;
1059 if (!streamed)
1060 return std::nullopt;
1061 std::optional<int64_t> moved = llvm::checkedMul(*runs, *streamed);
1062 bytes = moved ? llvm::checkedAdd(*bytes, *moved) : std::nullopt;
1063 if (!bytes)
1064 return std::nullopt;
1065 }
1066 return bytes;
1067 }
1068
1069 /// Bytes one object of `endpoint` carries over its channel, its elements
1070 /// sized as a buffer descriptor's length counts them.
1071 static int64_t objectBytes(ObjectFifoDmaEndpointOp endpoint) {
1072 auto type = cast<MemRefType>(endpoint.getPoolOp().getElemType());
1073 return transferElements(endpoint) *
1074 static_cast<int64_t>(DataLayout::closest(endpoint).getTypeSize(
1075 type.getElementType()));
1076 }
1077
1078 /// Objects the DMA endpoint `endpoint` moves in one run of `sequence`, traced
1079 /// to the shim directly or through one pool with one DMA endpoint toward the
1080 /// shim.
1081 std::optional<int64_t> hostObjects(DeviceOp device,
1082 RuntimeSequenceOp sequence,
1083 ObjectFifoDmaEndpointOp endpoint,
1084 bool throughPool) {
1085 if (endpoint.getIterCount() || endpoint.getDispatch())
1086 return std::nullopt;
1087 StringRef name = endpoint.getSymName();
1088 SmallVector<StringRef> peers;
1089 for (auto route : device.getOps<RouteOp>()) {
1090 if (endpoint.drains() ? route.namesAsSource(name)
1091 : route.namesAsDestination(name)) {
1092 auto names = endpoint.drains() ? route.getDestinationNames()
1093 : route.getSourceNames();
1094 peers.append(names.begin(), names.end());
1095 }
1096 }
1097 if (peers.size() != 1)
1098 return std::nullopt;
1099 Operation *peer = SymbolTable::lookupNearestSymbolFrom(
1100 device, StringAttr::get(device.getContext(), peers.front()));
1101 // A draining endpoint sends each object `getRepeat` times.
1102 int64_t sent = objectBytes(endpoint) * endpoint.getRepeat();
1103 int64_t perObject = endpoint.drains() ? sent : objectBytes(endpoint);
1104
1105 int64_t bytes;
1106 if (auto shim = dyn_cast_or_null<RouteEndpointOp>(peer)) {
1107 std::optional<int64_t> host = hostBytes(sequence, shim.getSymNameAttr());
1108 if (!host)
1109 return std::nullopt;
1110 bytes = *host;
1111 } else if (auto other = dyn_cast_or_null<ObjectFifoDmaEndpointOp>(peer);
1112 other && throughPool && other.drains() != endpoint.drains()) {
1113 ObjectFifoDmaEndpointOp toward;
1114 for (auto candidate : device.getOps<ObjectFifoDmaEndpointOp>()) {
1115 if (candidate == other || candidate.getPoolOp() != other.getPoolOp() ||
1116 candidate.drains() == other.drains())
1117 continue;
1118 if (toward)
1119 return std::nullopt;
1120 toward = candidate;
1121 }
1122 if (!toward)
1123 return std::nullopt;
1124 std::optional<int64_t> objects =
1125 hostObjects(device, sequence, toward, false);
1126 if (!objects)
1127 return std::nullopt;
1128 bytes =
1129 *objects * (other.drains() ? objectBytes(other) * other.getRepeat()
1130 : objectBytes(other));
1131 } else {
1132 return std::nullopt;
1133 }
1134 if (perObject == 0 || bytes % perObject)
1135 return std::nullopt;
1136 return bytes / perObject;
1137 }
1138
1139 /// A Worker whose forever loop waits once for each dispatch's parameters
1140 /// runs one pass of that loop per dispatch, so the objects one pass moves
1141 /// through a fifo must be the objects one run of the runtime sequence moves
1142 /// through it, or the core drifts out of step with the dispatches. A pass
1143 /// runs the fifo's period, an inner loop where that is the innermost loop
1144 /// around its accesses, as often as the static loops between them repeat.
1145 /// Checked when one runtime sequence syncs the parameters, so every
1146 /// dispatch runs it, and its transfers on the fifo are static. A sync sets
1147 /// the core's lock rather than adding to it, so where a run syncs twice the
1148 /// core may take only one, and nothing is checked.
1149 LogicalResult verifyDispatchVolumes(DeviceOp device) {
1150 RuntimeSequenceOp sequence;
1151 for (auto candidate : device.getOps<RuntimeSequenceOp>()) {
1152 auto ops = candidate.getBody()
1153 .getOps<AIEX::SyncScratchpadParametersFromHostOp>();
1154 int64_t count = std::distance(ops.begin(), ops.end());
1155 // With a core waiting, --aie-lower-scratchpad-parameters syncs once in a
1156 // sequence that has no sync of its own, unless the sequence opts out.
1157 if (count == 0) {
1158 BoolAttr preamble = candidate.getEmitParameterSyncPreambleAttr();
1159 count = !preamble || preamble.getValue();
1160 }
1161 if (count == 0)
1162 continue;
1163 if (sequence || count > 1)
1164 return success();
1165 sequence = candidate;
1166 }
1167 if (!sequence)
1168 return success();
1169
1170 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>()) {
1171 ObjectFifoPoolOp pool = endpoint.getPoolOp();
1172 if (!pool || pool.getInitValues() || endpoint.getSegments() ||
1173 !poolLocks->needsLocks(pool))
1174 continue;
1175 ObjectFifoDmaEndpointOp dma;
1176 bool single = true;
1177 for (auto candidate : device.getOps<ObjectFifoDmaEndpointOp>()) {
1178 if (candidate.getPoolOp() != pool ||
1179 candidate.drains() == endpoint.drains())
1180 continue;
1181 single = !dma;
1182 dma = candidate;
1183 }
1184 if (!dma || !single || dma.getSegments())
1185 continue;
1186
1187 CoreTurns turns;
1188 std::string reason;
1189 if (failed(turns.read({endpoint}, reason)))
1190 continue;
1191 Operation *loop = turns.periodLoop();
1192 std::optional<int64_t> periods = 1;
1193 for (; periods && !isa<CoreOp>(loop) && !runsForever(loop);
1194 loop = loop->getParentOp()) {
1195 auto forOp = dyn_cast<scf::ForOp>(loop);
1196 std::optional<int64_t> trip =
1197 forOp ? getStaticTripCount(forOp) : std::nullopt;
1198 periods = trip && loop->getBlock() == &loop->getParentRegion()->front()
1199 ? llvm::checkedMul(*periods, *trip)
1200 : std::nullopt;
1201 }
1202 if (!periods || isa<CoreOp>(loop))
1203 continue;
1204 // Two waits a pass serve two dispatches, and a wait under a branch or an
1205 // inner loop may serve none or several.
1206 auto whileLoop = dyn_cast<scf::WhileOp>(loop);
1207 Block *body = whileLoop ? whileLoop.getAfterBody()
1208 : cast<scf::ForOp>(loop).getBody();
1209 int64_t waits = 0;
1210 loop->walk([&](AIEX::WaitScratchpadParametersOp) { waits++; });
1211 if (waits != 1 ||
1212 body->getOps<AIEX::WaitScratchpadParametersOp>().empty())
1213 continue;
1214 std::optional<int64_t> perDispatch = llvm::checkedMul(
1215 *periods, static_cast<int64_t>(turns.turns().size()));
1216 if (!perDispatch)
1217 continue;
1218 std::optional<int64_t> objects = hostObjects(device, sequence, dma, true);
1219 LLVM_DEBUG(llvm::dbgs()
1220 << "dispatch volume of @" << endpoint.getSymName()
1221 << ": the core moves " << *perDispatch << ", @"
1222 << sequence.getSymName() << " moves "
1223 << (objects ? std::to_string(*objects) : "an unknown count")
1224 << "\n");
1225 if (!objects || *objects == *perDispatch)
1226 continue;
1227
1228 ObjectFifoAcquireOp acquire;
1229 loop->walk([&](ObjectFifoAcquireOp op) {
1230 if (!acquire && op.getObjFifoName() == endpoint.getSymName())
1231 acquire = op;
1232 });
1233 if (!acquire)
1234 continue;
1235 InFlightDiagnostic diag =
1236 acquire.emitOpError()
1237 << (endpoint.drains() ? "takes " : "hands over ") << *perDispatch
1238 << " objects through @" << endpoint.getSymName()
1239 << " for each dispatch, one pass of a loop that waits for each "
1240 "dispatch's parameters, but each run of runtime sequence @"
1241 << sequence.getSymName() << " moves " << *objects
1242 << ", so the core drifts out of step with the dispatches";
1243 diag.attachNote(sequence.getLoc()) << "the runtime sequence is here";
1244 return failure();
1245 }
1246 return success();
1247 }
1248
1249 using PoolActors = DenseMap<Operation *, SmallVector<SegmentActors>>;
1250
1251 /// A place the bytes some endpoint sends reach: once `far` has taken some
1252 /// of them, the endpoint has sent at least `inBytes` for every `outBytes`
1253 /// taken. With a nonzero `lagObject`, they pass a later segment of a join
1254 /// on the way, whose drainer takes `lagObject` bytes an object and has taken
1255 /// at least `lagIn` for every `lagOut` `far` took: that holds in whole
1256 /// objects of the join only (see recordConsumption's granule).
1257 struct Reach {
1258 Operation *far;
1259 int64_t inBytes, outBytes;
1260 int64_t lagObject = 0, lagIn = 0, lagOut = 0;
1261 };
1262
1263 static int64_t segmentBytes(ObjectFifoPoolOp pool,
1264 ArrayRef<ObjectFifoSegmentOp> segments) {
1265 int64_t elements = 0;
1266 for (ObjectFifoSegmentOp segment : segments)
1267 elements += segment.getSize();
1268 auto type = cast<MemRefType>(pool.getElemType());
1269 return elements *
1270 static_cast<int64_t>(
1271 DataLayout::closest(pool).getTypeSize(type.getElementType()));
1272 }
1273
1274 /// Whether `dma` moves each object's bytes once, neither padding, repeating
1275 /// nor dispatching them.
1276 static bool passesOn(ObjectFifoDmaEndpointOp dma) {
1277 return !dma.getPadDimensions() && !dma.getDispatch() &&
1278 dma.getRepeat() == 1;
1279 }
1280
1281 /// Where the bytes the endpoint `from` sends end up, scaled by `scale`: a
1282 /// shim's route endpoint, or a core endpoint draining a pool on the way.
1283 /// Every destination of a route is reached. A pool is entered through a
1284 /// fill that alone fills its segments and left through each drainer of the
1285 /// same segments, of the fill's last segment alone (a split), or of all
1286 /// segments when the fill fills the first (a join): segments release once
1287 /// written, so only those drainers' progress bounds the whole of the fill's.
1288 /// Bytes pass only through DMAs that neither pad, repeat nor dispatch them,
1289 /// counted as each DMA's transform moves them, and only to a destination no
1290 /// other route merges into, with no packet header kept in its bytes.
1291 void carries(DeviceOp device, StringAttr from, const PoolActors &actors,
1292 Reach scale, llvm::SmallPtrSetImpl<Operation *> &onPath,
1293 SmallVectorImpl<Reach> &reaches) {
1294 RouteOp route;
1295 for (auto candidate : device.getOps<RouteOp>()) {
1296 if (!candidate.namesAsSource(from.getValue()))
1297 continue;
1298 if (route)
1299 return;
1300 route = candidate;
1301 }
1302 if (!route || route.getSources().size() != 1 || route.getKeepPktHeader())
1303 return;
1304 for (StringRef name : route.getDestinationNames()) {
1305 if (llvm::any_of(device.getOps<RouteOp>(), [&](RouteOp other) {
1306 return other != route && other.namesAsDestination(name);
1307 }))
1308 continue;
1309 Operation *dest = SymbolTable::lookupNearestSymbolFrom(
1310 device, StringAttr::get(device.getContext(), name));
1311 if (auto shim = dyn_cast_or_null<RouteEndpointOp>(dest)) {
1312 Reach at = scale;
1313 at.far = shim;
1314 if (shim.getBundle() == WireBundle::DMA &&
1315 shim.getTileLike().isShimTile())
1316 reaches.push_back(at);
1317 continue;
1318 }
1319 auto fill = dyn_cast_or_null<ObjectFifoDmaEndpointOp>(dest);
1320 if (!fill || fill.drains() || !passesOn(fill))
1321 continue;
1322 ObjectFifoPoolOp pool = fill.getPoolOp();
1323 if (!pool || pool.getInitValues() || pool.getContiguous() ||
1324 !poolLocks->needsLocks(pool) || onPath.contains(pool))
1325 continue;
1326 auto it = actors.find(pool);
1327 if (it == actors.end())
1328 continue;
1329 std::vector<ObjectFifoSegmentOp> all = pool.getSegmentOps();
1330 std::vector<ObjectFifoSegmentOp> filled = fill.getSelectedSegments();
1331 auto indexOf = [&](ObjectFifoSegmentOp segment) {
1332 return llvm::find(all, segment) - all.begin();
1333 };
1334 if (filled.empty() || llvm::any_of(filled, [&](auto segment) {
1335 return it->second[indexOf(segment)].fillers.size() != 1;
1336 }))
1337 continue;
1338 llvm::SetVector<Operation *> drainers;
1339 for (const SegmentActors &segment : it->second)
1340 drainers.insert(segment.drainers.begin(), segment.drainers.end());
1341 onPath.insert(pool);
1342 for (Operation *drainer : drainers) {
1343 auto core = dyn_cast<ObjectFifoCoreEndpointOp>(drainer);
1344 auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(drainer);
1345 if (dma && !passesOn(dma))
1346 continue;
1347 std::vector<ObjectFifoSegmentOp> drained =
1348 core ? core.getSelectedSegments() : dma.getSelectedSegments();
1349 if (drained.empty())
1350 continue;
1351 bool split = drained.size() == 1 && drained.front() == filled.back();
1352 bool join = filled.size() == 1 && filled.front() == drained.front();
1353 // A later segment of a join is taken only after those ahead of it in
1354 // each object (a join's drainer reads its segments in order, any
1355 // transform staying within each), so its progress shows in whole
1356 // objects alone; one such segment per path.
1357 bool laterJoin = dma && filled.size() == 1 && !join &&
1358 llvm::is_contained(drained, filled.front());
1359 if ((drained != filled && !split && !join && !laterJoin) ||
1360 (laterJoin && scale.lagObject))
1361 continue;
1362 int64_t in = objectBytes(fill);
1363 int64_t out = core ? segmentBytes(pool, drained) : objectBytes(dma);
1364 Reach next = scale;
1365 next.far = drainer;
1366 if (in <= 0 || out <= 0 ||
1367 llvm::MulOverflow(scale.inBytes, in, next.inBytes) ||
1368 llvm::MulOverflow(scale.outBytes, out, next.outBytes) ||
1369 (scale.lagObject &&
1370 (llvm::MulOverflow(scale.lagIn, in, next.lagIn) ||
1371 llvm::MulOverflow(scale.lagOut, out, next.lagOut))))
1372 continue;
1373 int64_t common = std::gcd(next.inBytes, next.outBytes);
1374 next.inBytes /= common;
1375 next.outBytes /= common;
1376 if (laterJoin)
1377 next = {next.far, next.inBytes, next.outBytes, out, 1, 1};
1378 if (next.lagObject) {
1379 int64_t lagCommon = std::gcd(next.lagIn, next.lagOut);
1380 next.lagIn /= lagCommon;
1381 next.lagOut /= lagCommon;
1382 }
1383 if (core)
1384 reaches.push_back(next);
1385 else
1386 carries(device, dma.getSymNameAttr(), actors, next, onPath, reaches);
1387 }
1388 onPath.erase(pool);
1389 }
1390 }
1391
1392 /// Records on each shim input the shim outputs whose progress proves it
1393 /// consumed (#aie.consumed_by). Its bytes reach such an output; or they
1394 /// reach a core that, on every path through its program (TakeRatio), takes
1395 /// its share of them before each release into a fifo whose bytes reach the
1396 /// output, or another such core. A shim input sends a byte before anything
1397 /// downstream can take it, and the host receives a byte only after the
1398 /// cores released it, so once the output has received R bytes the input's
1399 /// first R * in / out have been sent; with a granule (see carries), R
1400 /// rounded down to a multiple of it.
1401 void recordConsumption(DeviceOp device, const PoolActors &actors) {
1402 MLIRContext *ctx = device.getContext();
1403 struct Share {
1404 int64_t in, out, granule;
1405 };
1406 // Proofs are listed by their outputs' structural rank, found once and
1407 // only for an input with several.
1408 std::optional<DenseMap<Operation *, unsigned>> rank;
1409 for (auto input : device.getOps<RouteEndpointOp>()) {
1410 if (input.getBundle() != WireBundle::DMA ||
1411 !input.getTileLike().isShimTile())
1412 continue;
1413 // Per output, one proof: one without a granule where there is one, else
1414 // the most bytes for every `out` received, then the smallest granule.
1415 llvm::MapVector<Operation *, Share> proofs;
1416 auto prove = [&](RouteEndpointOp output, const Reach &reach) {
1417 Share share{reach.inBytes, reach.outBytes, 0};
1418 if (reach.lagObject) {
1419 // The smallest R with R * lagIn a multiple of lagOut * lagObject.
1420 int64_t whole;
1421 if (llvm::MulOverflow(reach.lagOut, reach.lagObject, whole))
1422 return;
1423 share.granule = whole / std::gcd(whole, reach.lagIn);
1424 }
1425 auto [it, inserted] = proofs.try_emplace(output, share);
1426 const Share &old = it->second;
1427 int64_t lhs, rhs;
1428 if (inserted || llvm::MulOverflow(share.in, old.out, lhs) ||
1429 llvm::MulOverflow(old.in, share.out, rhs))
1430 return;
1431 if ((old.granule && !share.granule) ||
1432 (!old.granule == !share.granule &&
1433 (lhs > rhs || (lhs == rhs && share.granule < old.granule))))
1434 it->second = share;
1435 };
1436 SmallVector<Reach> reaches;
1437 llvm::SmallPtrSet<Operation *, 8> onPath;
1438 carries(device, input.getSymNameAttr(), actors, {nullptr, 1, 1}, onPath,
1439 reaches);
1440 // A core passes the input on through each fifo it fills, perhaps to
1441 // another core, and so on, a few hops deep.
1442 constexpr int maxCoreHops = 4;
1443 SmallVector<std::pair<Reach, int>> work;
1444 for (const Reach &reach : reaches)
1445 work.push_back({reach, 0});
1446 while (!work.empty()) {
1447 auto [reach, hops] = work.pop_back_val();
1448 if (auto output = dyn_cast<RouteEndpointOp>(reach.far)) {
1449 prove(output, reach);
1450 continue;
1451 }
1452 if (hops == maxCoreHops)
1453 continue;
1454 auto consumer = cast<ObjectFifoCoreEndpointOp>(reach.far);
1455 CoreOp core;
1456 for (Operation *user : consumer.getTile().getUsers())
1457 if (auto candidate = dyn_cast<CoreOp>(user))
1458 core = candidate;
1459 if (!core)
1460 continue;
1461 int64_t takenBytes =
1462 segmentBytes(consumer.getPoolOp(), consumer.getSelectedSegments());
1463 for (auto producer : device.getOps<ObjectFifoCoreEndpointOp>()) {
1464 ObjectFifoPoolOp pool = producer.getPoolOp();
1465 if (producer.drains() || producer.getSegments() ||
1466 producer.getTile() != consumer.getTile() || !pool ||
1467 pool.getInitValues() || !poolLocks->needsLocks(pool))
1468 continue;
1469 auto it = actors.find(pool);
1470 if (it == actors.end() || it->second.size() != 1 ||
1471 it->second.front().fillers.size() != 1 ||
1472 it->second.front().drainers.size() != 1)
1473 continue;
1474 Operation *drainer = it->second.front().drainers.front();
1475 std::optional<std::pair<int64_t, int64_t>> ratio =
1476 TakeRatio(device, consumer.getSymName(), producer.getSymName())
1477 .of(core);
1478 if (!ratio)
1479 continue;
1480 // Once the next place has taken X bytes, the drainer sent X *
1481 // next.inBytes / next.outBytes, the core released at least that
1482 // much of the producer and so took `taken` bytes of the consumer
1483 // for every `released`, of which the input sent reach's share.
1484 // `released` counts what the drainer moves of each object.
1485 auto dma = dyn_cast<ObjectFifoDmaEndpointOp>(drainer);
1486 int64_t taken, released;
1487 if ((dma && !passesOn(dma)) ||
1488 llvm::MulOverflow(ratio->first, takenBytes, taken) ||
1489 llvm::MulOverflow(
1490 ratio->second,
1491 dma ? objectBytes(dma)
1492 : segmentBytes(pool, producer.getSelectedSegments()),
1493 released) ||
1494 released <= 0)
1495 continue;
1496 // A core sharing the pool's memory takes what this one released.
1497 SmallVector<Reach> nexts;
1498 if (!dma) {
1499 nexts.push_back({drainer, 1, 1, 0, 0, 0});
1500 } else {
1501 llvm::SmallPtrSet<Operation *, 8> outPath;
1502 carries(device, dma.getSymNameAttr(), actors, {nullptr, 1, 1},
1503 outPath, nexts);
1504 }
1505 for (const Reach &next : nexts) {
1506 if (reach.lagObject && next.lagObject)
1507 continue;
1508 Reach composed = next;
1509 if (llvm::MulOverflow(next.inBytes, taken, composed.inBytes) ||
1510 llvm::MulOverflow(composed.inBytes, reach.inBytes,
1511 composed.inBytes) ||
1512 llvm::MulOverflow(next.outBytes, released, composed.outBytes) ||
1513 llvm::MulOverflow(composed.outBytes, reach.outBytes,
1514 composed.outBytes))
1515 continue;
1516 int64_t common = std::gcd(composed.inBytes, composed.outBytes);
1517 composed.inBytes /= common;
1518 composed.outBytes /= common;
1519 // A join before the core: its drainer took at least what the
1520 // core took, scaled on to the next place as the input's share is.
1521 if (reach.lagObject) {
1522 composed.lagObject = reach.lagObject;
1523 if (llvm::MulOverflow(reach.lagIn, taken, composed.lagIn) ||
1524 llvm::MulOverflow(composed.lagIn, next.inBytes,
1525 composed.lagIn) ||
1526 llvm::MulOverflow(reach.lagOut, released, composed.lagOut) ||
1527 llvm::MulOverflow(composed.lagOut, next.outBytes,
1528 composed.lagOut))
1529 continue;
1530 int64_t lagCommon = std::gcd(composed.lagIn, composed.lagOut);
1531 composed.lagIn /= lagCommon;
1532 composed.lagOut /= lagCommon;
1533 }
1534 work.push_back({composed, hops + 1});
1535 }
1536 }
1537 }
1538 if (proofs.empty()) {
1539 input.removeConsumedByAttr();
1540 continue;
1541 }
1542 auto ordered = proofs.takeVector();
1543 if (ordered.size() > 1) {
1544 if (!rank)
1545 rank = StructuralGraph::of(device).rank();
1546 llvm::stable_sort(ordered, [&](const auto &a, const auto &b) {
1547 return rank->lookup(a.first) < rank->lookup(b.first);
1548 });
1549 }
1550 SmallVector<Attribute> attrs;
1551 for (auto [output, share] : ordered) {
1552 int64_t common = std::gcd(share.in, share.out);
1553 attrs.push_back(ConsumedByAttr::get(
1554 ctx,
1555 FlatSymbolRefAttr::get(
1556 cast<RouteEndpointOp>(output).getSymNameAttr()),
1557 share.in / common, share.out / common, share.granule,
1558 /*device=*/FlatSymbolRefAttr()));
1559 }
1560 input.setConsumedByAttr(ArrayAttr::get(ctx, attrs));
1561 }
1562 }
1563
1564 /// An out-of-order sender names the buffer each object lands in, and one BD
1565 /// carries one such name, so the ends have to hold the same buffers in the
1566 /// same order. Naming a slice of a larger buffer would need the sender split
1567 /// into one descriptor per slice, which nothing does yet.
1568 LogicalResult verifyOutOfOrderPools(DeviceOp device) {
1569 auto lookup = [&](FlatSymbolRefAttr name) {
1570 return dyn_cast_or_null<ObjectFifoDmaEndpointOp>(
1571 SymbolTable::lookupNearestSymbolFrom(device, name.getAttr()));
1572 };
1573 auto objectBytes = [](ObjectFifoPoolOp pool) -> int64_t {
1574 auto type = dyn_cast<MemRefType>(pool.getElemType());
1575 if (!type)
1576 return 0;
1577 return (type.getNumElements() * type.getElementTypeBitWidth() + 7) / 8;
1578 };
1579 for (auto flow : device.getOps<RouteOp>()) {
1580 if (flow.getSources().size() != 1)
1581 continue;
1582 ObjectFifoDmaEndpointOp src =
1583 lookup(cast<FlatSymbolRefAttr>(flow.getSources()[0]));
1584 ObjectFifoDmaEndpointOp firstReceiver;
1585 for (auto destName :
1586 flow.getDestinations().getAsRange<FlatSymbolRefAttr>()) {
1587 ObjectFifoDmaEndpointOp dst = lookup(destName);
1588 if (!dst || !dst.getOutOfOrder())
1589 continue;
1590 if (!firstReceiver)
1591 firstReceiver = dst;
1592 if (firstReceiver.getNumDescriptors() != dst.getNumDescriptors() ||
1593 objectBytes(firstReceiver.getPoolOp()) !=
1594 objectBytes(dst.getPoolOp()))
1595 return flow.emitOpError(
1596 "out-of-order broadcast destinations require matching buffer "
1597 "counts and object sizes");
1598 if (!src || !src.getOutOfOrder())
1599 continue;
1600 ObjectFifoPoolOp from = src.getPoolOp(), to = dst.getPoolOp();
1601 if (!from || !to)
1602 continue;
1603 if (src.getNumDescriptors() != dst.getNumDescriptors() ||
1604 objectBytes(from) != objectBytes(to))
1605 return src.emitOpError("sends out of order from ")
1606 << src.getNumDescriptors() << " buffers of "
1607 << objectBytes(from) << " bytes into "
1608 << dst.getNumDescriptors() << " of " << objectBytes(to)
1609 << "; an out-of-order fifo needs the same buffers at both "
1610 "ends, because one descriptor names one whole buffer";
1611 }
1612 }
1613 return success();
1614 }
1615
1616 void runOnOperation() override {
1617 DeviceOp device = getOperation();
1618 poolLocks = std::make_shared<PoolLocks>(device);
1619
1620 DenseMap<Operation *, SmallVector<SegmentActors>> actorsPerPool;
1621 for (auto pool : device.getOps<ObjectFifoPoolOp>()) {
1622 actorsPerPool[pool].resize(pool.getSegmentOps().size());
1623 }
1624
1625 auto record = [&](auto endpoint) {
1626 ObjectFifoPoolOp pool = endpoint.getPoolOp();
1627 if (!pool) {
1628 return;
1629 }
1630 auto &actors = actorsPerPool[pool];
1631 std::vector<ObjectFifoSegmentOp> all = pool.getSegmentOps();
1632 for (ObjectFifoSegmentOp segment : endpoint.getSelectedSegments()) {
1633 size_t index = llvm::find(all, segment) - all.begin();
1634 (endpoint.drains() ? actors[index].drainers : actors[index].fillers)
1635 .push_back(endpoint);
1636 }
1637 };
1638
1639 for (auto endpoint : device.getOps<ObjectFifoCoreEndpointOp>()) {
1640 record(endpoint);
1641 }
1642 for (auto endpoint : device.getOps<ObjectFifoDmaEndpointOp>()) {
1643 record(endpoint);
1644 }
1645
1646 for (auto pool : device.getOps<ObjectFifoPoolOp>()) {
1647 if (failed(verifyActors(pool, actorsPerPool[pool]))) {
1648 return signalPassFailure();
1649 }
1650 }
1651
1652 SymbolTableCollection symbolTables;
1653 if (failed(verifyFlows(device, symbolTables)) ||
1654 failed(verifyFanIn(device, symbolTables)) ||
1655 failed(verifyOverRelease(device)) ||
1656 failed(verifyTransferBudgets(device)) ||
1657 failed(verifyHeldAtEnd(device, symbolTables)) ||
1658 failed(verifyAdvances(device)) ||
1659 failed(verifyDispatchVolumes(device)) ||
1660 failed(verifyOutOfOrderPools(device))) {
1661 return signalPassFailure();
1662 }
1663 recordConsumption(device, actorsPerPool);
1664 }
1665};
1666
1667} // namespace
1668
1669std::unique_ptr<OperationPass<DeviceOp>>
1671 return std::make_unique<AIEObjectFifoVerifyPass>();
1672}
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 movesNone() const
Whether read found a steady state in which the period moves none of the objects: the core keeps what ...
mlir::Operation * periodAcquire() const
The first acquire the period runs, with its branches folded; null when it runs none.
llvm::ArrayRef< unsigned > turns() const
Indices into ends, one per object the channel moves in a period of the core's steady state.
mlir::Operation * periodLoop() const
The loop read took as the core's period, once it found one.
bool namesFifo(Operation *op, StringRef fifo, SymbolTableCollection &symbols)
Definition AIEUtils.cpp:386
std::optional< int64_t > staticExecutions(Operation *op)
Definition AIEUtils.cpp:329
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEObjectFifoVerifyPass()
bool isForeverLoop(mlir::scf::WhileOp whileOp)
Whether whileOp repeats forever: its condition is a constant true, and its condition region does noth...
mlir::Operation * getObjectFifoLoopParent(mlir::Operation *op)
The innermost loop around op that isObjectFifoLoop accepts, or null.
bool isObjectFifoLoop(mlir::Operation *op)
Whether op is a loop that objectFifo lowering unrolls by the rotation period of the objectFifos acces...
llvm::DenseMap< mlir::Operation *, unsigned > rank() const
Rank the nodes by their features and then, a round at a time until no class splits,...
static StructuralGraph of(DeviceOp device)
The ops directly in device but its runtime sequences, each with the ops nested in it,...