Unique Topological Sort Utility

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 :slight_smile: ; 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 :slight_smile:

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 :slight_smile:

1 Like