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"
23#define DEBUG_TYPE "aie-channel-turns"
31constexpr size_t maxPeriodEvents = 4096;
33constexpr int maxPeriods = 256;
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;
44 reason =
"the endpoints are not all one core's, one way";
48 for (Operation *user : tile.getUsers())
49 if (
auto candidate = dyn_cast<CoreOp>(user))
52 reason =
"no core works through them";
55 SmallVector<StringAttr> names;
56 for (ObjectFifoCoreEndpointOp end : ends)
57 names.push_back(end.getSymNameAttr());
58 return read(core, names, first.drains(), reason);
62 bool coreDrains, std::string &reason) {
63 this->coreDrains = coreDrains;
68 DenseMap<StringAttr, unsigned> index;
69 for (
auto [i, name] : llvm::enumerate(names))
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();
84 if (!name || (used && *used != port))
86 auto it = index.find(name.getAttr());
87 if (it == index.end())
95 auto onceAfterLoops = [&](Operation *op) {
96 if (!coreDrains || !isa<ObjectFifoReleaseOp>(op) ||
97 op->getParentOfType<LoopLikeOpInterface>())
100 llvm::make_range(std::next(op->getIterator()), op->getBlock()->end()),
101 [&](Operation &later) {
103 .walk([&](ObjectFifoAcquireOp acquire) {
104 return endOf(acquire) ? WalkResult::interrupt()
105 : WalkResult::advance();
110 SmallVector<Operation *> uses, tails;
111 core.walk([&](Operation *op) {
113 (onceAfterLoops(op) ? tails : uses).push_back(op);
116 reason =
"the core never acquires them";
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);
128 SmallVector<Operation *> candidates;
129 for (Operation *candidate : loopsAround(uses.front()))
130 if (llvm::all_of(uses, [&](Operation *use) {
131 return candidate->isProperAncestor(use);
133 candidates.push_back(candidate);
134 if (candidates.empty()) {
135 reason =
"no loop repeats the core's use of them";
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)))
146 if (!isPure(def) || def->getNumResults() != 1)
148 SmallVector<Attribute> operands;
149 for (Value operand : def->getOperands())
150 if (!operands.emplace_back(evaluate(operand)))
152 SmallVector<OpFoldResult> folded;
153 if (failed(def->fold(operands, folded)) || folded.size() != 1)
155 if (
auto result = dyn_cast<Attribute>(folded.front()))
157 return evaluate(cast<Value>(folded.front()));
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});
167 {*end, cast<ObjectFifoReleaseOp>(op).relNumber(),
false, &op});
168 if (period.size() > maxPeriodEvents) {
169 reason =
"the core's period uses them too many times";
175 uses, [&](Operation *use) {
return op.isProperAncestor(use); }))
177 if (
auto ifOp = dyn_cast<scf::IfOp>(op)) {
179 dyn_cast_or_null<BoolAttr>(evaluate(ifOp.getCondition()))) {
181 taken.getValue() ? ifOp.getThenRegion() : ifOp.getElseRegion())
182 if (failed(unroll(branch)))
187 auto forOp = dyn_cast<scf::ForOp>(op);
188 std::optional<APInt> trips =
189 forOp ? forOp.getStaticTripCount() : std::nullopt;
191 reason =
"the core uses them under control flow that depends on data";
194 if (trips->getSExtValue() >
static_cast<int64_t
>(maxPeriodEvents)) {
195 reason =
"the core's period uses them too many times";
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++) {
202 counters[forOp.getInductionVar()] = IntegerAttr::get(
203 forOp.getInductionVar().getType(), *lower + trip * *step);
204 if (failed(unroll(*forOp.getBody())))
212 for (Operation *candidate : candidates) {
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));
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"
235 llvm::dbgs() <<
"\n";
242 SmallVector<int64_t> held(ends, 0);
243 std::map<SmallVector<int64_t>,
int> seen;
244 for (
int round = 0; round < maxPeriods; round++) {
246 SmallVector<int64_t> start = held;
247 for (
const Event &event : period) {
248 int64_t &h = held[
event.end];
251 order.append(std::max<int64_t>(0, event.count - h), event.end);
252 h = std::max(h, event.count);
254 if (event.count > h) {
255 reason =
"the core releases objects it does not hold";
260 order.append(event.count, event.end);
263 if (!seen.emplace(start, round).second) {
266 reason =
"the core's period moves none of their objects";
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);
279 reason =
"the core never settles into a steady order";
283LogicalResult CoreTurns::readWholeRun(
284 CoreOp core, ArrayRef<std::pair<ObjectFifoReleaseOp, unsigned>> releases,
285 std::string &reason) {
287 for (Operation *op = loop; op != core; op = op->getParentOp()) {
288 auto whileOp = dyn_cast<scf::WhileOp>(op);
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";
308 wholeRun = std::move(moved);
312bool CoreTurns::wholeRunFits(ArrayRef<int64_t> counts)
const {
318 if (wholeRun.empty())
320 std::optional<int64_t> whole;
321 for (
size_t i = 0; i < ends; i++) {
327 if (wholeRun[i] % counts[i] || (whole && *whole != wholeRun[i] / counts[i]))
329 whole = wholeRun[i] / counts[i];
335 assert(depths.size() == ends &&
"one depth per endpoint");
339 SmallVector<int64_t> counts(ends, 0);
340 for (
unsigned end : order)
342 for (
size_t length = 1; length < order.size(); length++) {
343 if (order.size() % length)
345 size_t repeats = order.size() / length;
346 if (llvm::any_of(counts, [&](int64_t c) {
return c % repeats; }))
348 SmallVector<int64_t> perRun(counts);
349 for (int64_t &count : perRun)
350 count /=
static_cast<int64_t
>(repeats);
351 if (!wholeRunFits(perRun))
353 std::set<SmallVector<unsigned>> tried;
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++) {
364 runCounts[order[start - 1]]--;
365 runCounts[order[start + length - 1]]++;
367 bool proportional =
true;
368 for (
size_t i = 0; i < ends; i++)
370 runCounts[i] *
static_cast<int64_t
>(repeats) == counts[i];
373 SmallVector<unsigned> run(order.begin() + start,
374 order.begin() + start + length);
375 if (!tried.insert(run).second || !
keepsUp(run, depths))
381 return wholeRunFits(counts) &&
keepsUp(order, depths);
385 for (
const Event &event : period)
392 ArrayRef<int64_t> depths)
const {
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;) {
402 while (forChannel[order[turn]] > 0) {
403 forChannel[order[turn]]--;
404 forCore[order[turn]]++;
405 turn = (turn + 1) % order.size();
409 const Event &e = period[event];
411 int64_t take = std::max<int64_t>(0, e.count - held[e.end]);
412 if (forCore[e.end] < take)
414 forCore[e.end] -= take;
415 held[e.end] = std::max(held[e.end], e.count);
417 held[e.end] -= e.count;
418 forChannel[e.end] += e.count;
421 if (++event == period.size()) {
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)
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...