Function sequant::eval::detail::pass_step_cycle_edges

Function Documentation

inline container::vector<std::pair<std::size_t, std::size_t>> sequant::eval::detail::pass_step_cycle_edges(RichSchedule const &rich, OrderedScheduleDepGraph const &g, container::vector<std::optional<ForcedSplitSite>> const &site, ForcedSplitLevels const &levels)

The dependency edges (reader, operand) on cycles among the steps of one pass, for forced_split_levels to bump; empty when every block level of every pass can be ordered.

The steps are those build_ordered_schedule orders. At root: each root value, and one block per nest and pass holding every value site places in that nest. Inside a nest, at each chain depth: the values built there (ForcedSplitSite::build) and one block holding everything produced deeper. An edge between two values of one pass is an edge between the two steps they belong to at the level where those differ; values of different passes are never ordered against each other (an operand of an earlier pass is read from that pass’s block, which has closed). A read of a leaf orders nothing: leaves are fetched, not produced by a step.

Every cycle runs through a block, since the values themselves form a DAG. Inside a nest the level has one block, and the edges returned are those by which the block needs a build that needs the block back, directly or through other builds of the level: bumping those readers leaves the build and what it waits on in the earlier pass. At root, one block of each strongly connected set of steps gives up its edges into the set; which block does is a choice – any of them breaks the cycles through it – and it falls on the block with the fewest such edges.