Hello,
I was wondering if there is a utility to produce a unique topological sorting of a given MLIR graph regardless of initial dominance. Put another way, given two MLIR graphs “A” and “B”, with identical use-def chains, have the same inputs and produce the same outputs (with the same inputs), is there a utility to generate a unique ordering of the IR such that “A” == “B” wrt. the SSA values?
1 Like
We have mlir/include/mlir/Transforms/TopologicalSortUtils.h, but it won’t do what you need right now.
Here is what I’d sketch if I had to implement it right now:
- Get all the operation that can be emitted next (that is: the one where the SSA operands have been already emitted).
- If none, that means we have a cycle to break, consider all the remaining ops eligible and apply the algorithm below.
- Amongst all the eligible ops:
- sort them per operation name
- for tie-breaking, sort them by the textual representation of their properties, discardable attributes, types, and location.
- for more tie-breaking, sort them according to their use-list order (which one is first in the use of the first operand)
- for further tie-breaking, sort them according to the “value number” of their operand (see below).
- If they don’t have any operand, I’m not sure how to tie break
; the order still does matter somehow if they have results: it impacts the numbering of their result which will impact their users ordering (but is this observable? I can’t construct an example right now when we keep the “value number of the operands” as last possible tie-break above). - After sorting the next eligible ops: emit all of them (except if we’re breaking a cycle, then emit a single operation) and number their SSA results in order.
- repeat until all the ops are emitted
Could probably use location too somewhere along the way.
For results one could also consider use-list order.
Many of these would also be useful for mlir-canon open project
1 Like