[RFC] Preserve use-list orders in MLIR bytecode

Hi all,

in an effort to help reaching bytecode stability i am planning to add a feature to MLIR that allows to retain a use-list order for all op results when doing a rountrip of the IR to bytecode. The idea is similar to what described here in the context of LLVM (LLVM Language Reference Manual — LLVM 17.0.0git documentation) but the implementation I have in mind does not really define the a semantic to represent those use-list directives.

Since the bytecode printers and readers rely on a reference numbering for the encoding of the IR to bytecode, that is, the operation ordering, this can be considered as the reference order - any ordering changes can be defined as a map of the use-list with respect to this reference order.

To retain the use-list order after a bytecode rountrip, the idea i have is to store the list of indices representing this mapping for every operation result. I would propose to encode those as part of the op mask for every op result that is not already ordered, so that it will integrate seamlessly with the existing bytecode format. Other ways of encoding this are possible, but the advantage of this kind of encoding is that it does not to rely of any global value ID numbering - the proximity to the value owner allows to store pretty much only the result number as defining ID for the value with custom use-list order, which most likely will fit in a single byte, and can be optionally printed on operations that have multiple results.

At the end of parsing, when all the values in the scope are defined and the use-lists are already assembled according to the reference operation order, one can process all the values with custom uselist order and shuffle the uselist according to the indices.

I’ll be posting a patch soon, but looking forward to hear any comments or concern in the meantime.


1 Like

Here the first patch:

I am still working on testing the approach more thoroughly (I just tested with a couple of repro cases locally). Also the current implementation does not yet include the use-list order of the block arguments - those will be coming as well as part of the patch update.