556 bool warnUnsafeBdReuse, EffectFn effectOf) {
559 static_cast<AIE::DMAChannelDir
>(k[2]));
565 bool operator==(
const PathState &other)
const {
566 return queue == other.queue && completion == other.completion;
569 using States = llvm::SmallVector<PathState, 8>;
570 llvm::DenseMap<mlir::Value, unsigned> taskIndices;
571 auto track = [&](mlir::Value value) {
572 if (value && value.getType().isIndex())
573 taskIndices.try_emplace(value, taskIndices.size());
575 std::set<DmaQueueModel::ChannelKey> keys;
576 for (
const auto &[key, channel] : queue.
state())
577 if (depthOf(key) != 0)
579 llvm::DenseMap<mlir::Operation *, QueueEffect> effects;
580 body.walk([&](mlir::Operation *op) {
581 if (warnUnsafeBdReuse) {
582 for (mlir::Value value : op->getOperands())
584 for (mlir::Value value : op->getResults())
586 for (mlir::Region ®ion : op->getRegions())
587 for (mlir::Block &block : region)
588 for (mlir::Value arg : block.getArguments())
592 if (!warnUnsafeBdReuse) {
606 std::map<uint32_t, DmaQueueModel::ChannelKey> keyByStatus;
607 for (
const auto &key : keys)
609 key[0], key[1], key[3],
static_cast<AIE::DMAChannelDir
>(key[2])))
610 keyByStatus[*status] = key;
611 std::map<DmaQueueModel::ChannelKey, ChannelVisits> visits;
615 body.walk<mlir::WalkOrder::PreOrder>([&](mlir::Operation *op) {
616 if (warnUnsafeBdReuse && mlir::isa<mlir::scf::ForOp, mlir::scf::IfOp>(op))
617 for (
const auto &key : keys)
619 if (
auto it = effects.find(op); it != effects.end()) {
620 visit(op, it->second.key);
621 }
else if (
auto poll = mlir::dyn_cast<NpuMaskPollOp>(op)) {
622 if (
auto address = poll.getAbsoluteAddress())
623 if (
auto it = keyByStatus.find(*address); it != keyByStatus.end())
624 visit(op, it->second);
630 for (
const auto &key : keys) {
631 uint32_t depth = depthOf(key);
633 auto channelEffectOf = [&](mlir::Operation *op) {
634 auto it = effects.find(op);
635 return it != effects.end() && it->second.key == key ? it->second
638 llvm::SetVector<mlir::Operation *> overflowing;
639 llvm::SetVector<mlir::Operation *> unsafeFrees;
640 std::map<mlir::Operation *, DmaQueueModel::ChannelState> witnesses;
641 bool trackCompletion = warnUnsafeBdReuse;
642 auto warnUnsafeFree = [&](mlir::Operation *op) {
643 if (warnUnsafeBdReuse && unsafeFrees.insert(op)) {
645 op, key[0], key[1],
static_cast<AIE::DMAChannelDir
>(key[2]),
647 if (!trackCompletion)
648 diag.attachNote() <<
"task ownership analysis budget exhausted; "
649 "completion is conservatively unproven";
652 size_t completionWork = 0;
653 auto equivalent = [&](
const PathState &a,
const PathState &b) {
654 return a.queue == b.queue &&
655 (!trackCompletion || a.completion == b.completion);
657 auto contains = [&](
const States &states,
const PathState &state) {
658 return llvm::any_of(states, [&](
const PathState &other) {
659 return equivalent(state, other);
662 auto compact = [&](States &states) {
664 for (
const auto &state : states)
665 if (!contains(unique, state))
666 unique.push_back(state);
667 states = std::move(unique);
671 auto append = [&](States &to,
const States &from) {
672 if (warnUnsafeBdReuse && !trackCompletion)
674 for (
const auto &state : from)
675 if (!contains(to, state)) {
676 if (trackCompletion && to.size() >= 256) {
677 trackCompletion =
false;
679 if (contains(to, state))
685 auto dedupe = [&](States &states) {
687 for (
auto &state : states)
688 state.completion.normalize();
689 if (states.size() < 2)
692 append(unique, states);
693 states = std::move(unique);
695 auto transfer = [&](States &states, mlir::ValueRange from,
696 mlir::ValueRange to) {
697 if (!trackCompletion)
699 for (
auto &state : states) {
700 auto previous = state.completion.tasks;
701 for (
auto [source, dest] : llvm::zip_equal(from, to)) {
702 auto src = taskIndices.find(source), dst = taskIndices.find(dest);
703 if (src != taskIndices.end() && dst != taskIndices.end())
704 state.completion.tasks[dst->second] = previous[src->second];
709 auto forgetScope = [&](States &states, mlir::Region ®ion,
710 bool keepArguments =
false) {
711 if (!trackCompletion)
713 for (
auto [value, index] : taskIndices) {
714 mlir::Region *parent = value.getParentRegion();
715 if (parent != ®ion && !region.isAncestor(parent))
718 if (
auto arg = mlir::dyn_cast<mlir::BlockArgument>(value))
719 if (arg.getOwner() == ®ion.front())
721 for (
auto &state : states)
722 state.completion.tasks[index] = 0;
729 static_cast<AIE::DMAChannelDir
>(key[2]), depth)
734 enum class PollEffect { Ignore, Space, Idle };
735 auto pollEffectOf = [&](NpuMaskPollOp poll) {
736 auto address = poll.getAbsoluteAddress();
739 if (!address || !mask || !value)
740 return PollEffect::Ignore;
742 key[0], key[1], key[3],
static_cast<AIE::DMAChannelDir
>(key[2]));
743 if (status != address)
744 return PollEffect::Ignore;
746 if (idleMask && (*mask & idleMask) == idleMask &&
747 (*value & idleMask) == 0)
748 return PollEffect::Idle;
750 if (!fieldMask || (depth & (depth - 1)) != 0)
751 return PollEffect::Ignore;
752 uint32_t depthBit = depth << llvm::countr_zero(fieldMask);
753 return depthBit && (depthBit & fieldMask) == depthBit &&
754 (*mask & depthBit) == depthBit && (*value & depthBit) == 0
756 : PollEffect::Ignore;
761 auto unknownRegion = [&](mlir::Region ®ion, States states) {
762 region.walk([&](mlir::Operation *op) {
768 for (
auto &state : states) {
769 state.queue.pushes.assign(depth,
false);
770 state.queue.unknownTokens =
true;
771 if (trackCompletion) {
772 state.completion.unknownTokens =
true;
773 state.completion.mayHaveDroppedPushes |= !canPoll;
774 for (
unsigned owner : state.completion.tasks)
776 state.completion.forgottenOwners.insert(owner);
778 state.completion.pushes.push_back(
780 state.completion.bound(depth + 1,
false);
782 if (overflowing.insert(op))
783 witnesses[op] = state.queue;
790 std::function<States(mlir::Region &, States)> analyze;
791 analyze = [&](mlir::Region ®ion, States states) -> States {
792 if (!region.hasOneBlock())
793 return unknownRegion(region, std::move(states));
794 auto blockVisits = channelVisits.find(®ion.front());
795 if (blockVisits == channelVisits.end())
797 for (mlir::Operation *visited : blockVisits->second) {
798 if (trackCompletion) {
799 completionWork += states.size();
800 if (completionWork > 16384) {
801 trackCompletion =
false;
805 mlir::Operation &op = *visited;
806 if (
auto loop = mlir::dyn_cast<mlir::scf::ForOp>(&op)) {
807 auto lb = mlir::getConstantIntValue(loop.getLowerBound());
808 auto ub = mlir::getConstantIntValue(loop.getUpperBound());
809 if (lb && ub && *lb >= *ub &&
810 (!loop->hasAttr(
"unsignedCmp") || (*lb >= 0 && *ub >= 0))) {
811 transfer(states, loop.getInitArgs(), loop.getResults());
817 transfer(states, loop.getInitArgs(), loop.getRegionIterArgs());
818 States reachable = states;
819 for (
size_t i = 0; i < reachable.size();) {
820 bool wasTrackingCompletion = trackCompletion;
821 States next = analyze(loop.getRegion(), States{reachable[i]});
822 transfer(next, loop.getYieldedValues(), loop.getRegionIterArgs());
823 forgetScope(next, loop.getRegion(),
true);
824 append(reachable, next);
825 if (wasTrackingCompletion && !trackCompletion) {
833 transfer(reachable, loop.getRegionIterArgs(), loop.getResults());
834 forgetScope(reachable, loop.getRegion());
835 states = std::move(reachable);
838 if (
auto branch = mlir::dyn_cast<mlir::scf::IfOp>(&op)) {
839 States alternatives = analyze(branch.getThenRegion(), states);
840 States otherwise = analyze(branch.getElseRegion(), states);
841 if (branch.getNumResults()) {
842 transfer(alternatives, branch.thenYield().getResults(),
843 branch.getResults());
844 transfer(otherwise, branch.elseYield().getResults(),
845 branch.getResults());
847 forgetScope(alternatives, branch.getThenRegion());
848 forgetScope(otherwise, branch.getElseRegion());
849 append(alternatives, otherwise);
850 states = std::move(alternatives);
853 for (mlir::Region &nested : op.getRegions())
854 states = unknownRegion(nested, std::move(states));
856 if (
auto poll = mlir::dyn_cast<NpuMaskPollOp>(&op))
857 if (
auto effect = pollEffectOf(poll); effect != PollEffect::Ignore) {
858 for (
auto &state : states) {
860 if (trackCompletion) {
861 if (effect == PollEffect::Idle)
862 state.completion.noteIdle();
864 state.completion.bound(depth,
true);
874 if (warnUnsafeBdReuse)
875 for (
const auto &state : states)
876 if (!trackCompletion ||
877 !state.completion.isProvenComplete(
878 state.completion.tasks[taskIndices.lookup(e.
task)]))
882 for (
auto &state : states) {
885 state.completion.tasks[taskIndices.lookup(e.
task)] =
886 taskIndices.size() + 1;
892 state.completion.awaitToken();
896 if (overflowing.insert(&op))
897 witnesses[&op] = state.queue;
899 if (trackCompletion && canPoll)
900 state.completion.bound(depth,
true);
901 else if (trackCompletion)
902 state.completion.mayHaveDroppedPushes =
true;
905 if (trackCompletion) {
907 e.
task ? state.completion.tasks[taskIndices.lookup(e.
task)] : 0;
908 state.completion.pushes.push_back({e.
issuesToken, owner});
909 state.completion.bound(depth + 1,
false);
918 if (
auto it = entry.find(key); it != entry.end())
919 channelEntry = it->second;
920 PathState initial{channelEntry, {}};
921 initial.completion.tasks.resize(taskIndices.size());
922 States exits = analyze(body, States{initial});
923 for (mlir::Operation *push : overflowing) {
924 queue.
setState({{key, witnesses[push]}});
932 for (
const auto &state : exits)
933 if (!(channelExit == state.queue)) {
934 channelExit.
pushes.assign(
935 std::max(channelExit.
pushes.size(), state.queue.pushes.size()),
939 merged[key] = channelExit;
959 const std::set<DmaQueueModel::ChannelKey> &awaited,
960 llvm::ArrayRef<SyncCover> mayAwait, EffectFn effectOf) {
961 mlir::Region &body = sequence.getBody();
962 auto covered = [](llvm::ArrayRef<SyncCover> covers,
964 return llvm::any_of(covers,
967 llvm::SmallVector<SyncCover> ownInexact;
968 body.walk([&](NpuSyncOp sync) {
974 llvm::DenseMap<mlir::Operation *, QueueEffect> effects;
975 std::map<DmaQueueModel::ChannelKey, ChannelVisits> visits;
976 body.walk<mlir::WalkOrder::PreOrder>([&](mlir::Operation *op) {
980 (!awaited.count(e.
key) && !covered(mayAwait, e.
key)) ||
981 covered(ownInexact, e.
key))
987 auto describe = [](mlir::InFlightDiagnostic &diag,
989 diag <<
" on tile (" << key[0] <<
"," << key[1] <<
") "
990 << AIE::stringifyDMAChannelDir(
static_cast<AIE::DMAChannelDir
>(key[2]))
991 <<
" channel " << key[3];
994 constexpr int64_t maxFollowedTrips = 64;
995 bool consumed =
true;
996 for (
const auto &channel : visits) {
999 using Counts = std::set<int64_t>;
1000 bool unknown =
false;
1001 std::function<Counts(mlir::Region &, Counts)> analyze;
1002 analyze = [&](mlir::Region ®ion, Counts counts) -> Counts {
1005 if (!region.hasOneBlock()) {
1009 auto visited = blocks.find(®ion.front());
1010 if (visited == blocks.end())
1012 for (mlir::Operation *at : visited->second) {
1013 mlir::Operation &op = *at;
1016 if (
auto it = effects.find(&op); it != effects.end()) {
1018 for (int64_t count : counts)
1020 ? count + it->second.issuesToken
1021 : std::max<int64_t>(count - 1, 0));
1022 counts = std::move(next);
1025 if (
auto loop = mlir::dyn_cast<mlir::scf::ForOp>(&op)) {
1026 auto lb = mlir::getConstantIntValue(loop.getLowerBound());
1027 auto ub = mlir::getConstantIntValue(loop.getUpperBound());
1028 auto step = mlir::getConstantIntValue(loop.getStep());
1029 if (lb && ub && step && *step > 0 && !loop->hasAttr(
"unsignedCmp")) {
1030 int64_t trips = *ub > *lb ? llvm::divideCeil(*ub - *lb, *step) : 0;
1031 if (trips <= maxFollowedTrips) {
1032 for (int64_t i = 0; i < trips && !unknown; i++)
1033 counts = analyze(loop.getRegion(), counts);
1037 for (int64_t count : counts) {
1038 Counts after = analyze(loop.getRegion(), Counts{count});
1041 if (after == Counts{count})
1043 auto diag = loop.emitOpError(
"changes how many task-completion "
1044 "tokens are outstanding");
1045 describe(diag, key);
1046 diag <<
" in each pass, so how many it leaves depends on its trip "
1047 "count; await as many tokens in each pass as it issues";
1054 if (
auto branch = mlir::dyn_cast<mlir::scf::IfOp>(&op)) {
1055 Counts taken = analyze(branch.getThenRegion(), counts);
1056 Counts otherwise = analyze(branch.getElseRegion(), counts);
1057 taken.insert(otherwise.begin(), otherwise.end());
1058 counts = std::move(taken);
1066 Counts exits = analyze(body, Counts{0});
1067 if (unknown || *exits.rbegin() == 0)
1069 int64_t left = *exits.rbegin();
1071 auto diag = mlir::emitError(sequence.getLoc())
1072 <<
"ends with " << left <<
" task-completion token"
1073 << (left > 1 ?
"s" :
"") <<
" no await consumes";
1074 describe(diag, key);
1075 diag <<
"; the next command's await on that channel would return for "
1076 "this sequence's transfer instead of its own. Await every "
1077 "token-issuing transfer before the sequence ends, or start it "
1078 "without issue_token";
1081 return mlir::success(consumed);