Make realization order invariant to unique_name suffixes #8124
Conversation
|
Overnight test is good, ready to land (failure is irrelevant and will be fixed when llvm/llvm-project#83151 lands) |
|
There's one issue I'd like to raise before I hit merge: The goal for this PR is for the topological order of Funcs to be invariant to unique_name nonsense so that machine-generated pipelines are more likely to remain valid, and so that stmts don't arbitrarily change the order in which things get realized based across a multi-target build. This PR does that by sorting by name and then definition time. Name is so that we're as similar as possible to existing behavior, rather than being a good idea a priori. Let's assume for now that someone doesn't name their Funcs, so the entire responsibility falls on the secondary key. Definition time is good because it's resistant to changes to the RHS of Funcs. But it's not resistant to refactorings with no actual changes to any definitions that move around when different subpipelines are created, and it's not resistant to helper Funcs that are defined once and then reused in multiple pipelines (e.g. in a multi-target build). An alternative for the second sorting key would be the order in which Funcs are encountered in an IRVisitor traversal of the entire Pipeline starting from the output. This would be resistant to the problems above, but not resistant to things like commuting an addition in the RHS of a Func. I think I might prefer this, because multi-target with reused helper Funcs would be fine, and refactorings with no functional changes intended would be fine. If you tweak the RHS of a Func you may want to reschedule anyway. Thoughts? |
|
I changed the secondary sorting key to the order in which Funcs are visited during a traversal, rather than the order in which Funcs are given definitions. |
|
Worth mentioning in the release notes, because as @vksnk found, it may change the realization order in existing pipelines, which can affect peak memory usage, possibly causing stack overflows in pipelines that were close to the limit before. |
Currently the realization order is alphabetical in the case of ties, which may depend on suffixes introduced by unique_name, which will not have a consistent alphabetical order if you define the same pipeline multiple times, e.g. in a multi-target compilation scenario (because numeric order isn't alphabetical order if you don't have leading zeros).
This is a problem for machine-generated schedules, because they depend on topological order of the pipeline. So in a multi-target compilation, a machine-generated schedule that was checked in may be valid for the first few targets, but as soon as your unique_name counters start exceed 10, the ordering may no longer be correct.
This PR makes the realization order invariant to any unique_name suffixes. It works by stripping any potential suffixes, and then sorting primarily by any prefix that remains (for maximum consistency with existing machine-generated schedules), and secondarily by the order in which Funcs were given definitions (which is now tracked).