Making jlm (more) deterministic

[haved]

Making the output of a compiler deterministic seems common, and provides some benefits:

• Easier to reproduce bugs, across Debug/Release builds, between clang/g++, in gdb, in Valgrind, on CI servers/locally.
• Bisections can determine which commits caused changes

Some of the reasons Jlm is currently not deterministic include:

• Iteration over sets and maps of pointers to heap allocated objects. When iteration order affects the results, this introduces non-determinism, as heap addresses should be considered unpredictable.
  • For example: The RVSDG traverser classes make use of sets of unique pointers to keep track of state, which means iteration order is non-deterministic even when traversing the same in-memory graph multiple times.
• The LLVM output uses addresses as identifiers in the IR.

One way of removing non-determinism is to make iteration over hash sets and maps use insertion order. Languages like Python do this by default, so I don't think the performance/memory implications are terrible, but I still think it might be even better to never rely on the iteration order of hash sets, and use different approaches when iteration order matters.

The traverser classes can be made independent of addresses by using the ordered list of nodes stored within each region as a deterministic tie-breaker. There are some extra details surrounding the traversers that make them work even while the graph is being modified, so this behavior needs to be maintained in a potential rewrite.

Once the compiler output is deterministic, a part of the CI test suite can check it, e.g. check that jlm compiled with clang and gcc give identical results.

@phate @caleridas any other considerations relevant to this topic?

[phate]

The LLVM output uses addresses as identifiers in the IR.

What exactly do you mean with this point? Do you refer to the basic blocks having addresses instead of numbers? Anything else I do not remember?

by using the ordered list of nodes stored within each region as a deterministic tie-breaker.

The list of nodes in the region is unordered. There is no topological sorting associated with required for the traversing.

[haved]

It might only be the basic blocks that have labels based on addresses, but otherwise yes that is what I mean.

It is fine that the list of nodes doesn't have a particular order, as long as the order is deterministic. It is a linked list, and not a hash set, so that should be enough.

However, after thinking about it some more, it is also possible to deterministically create a topological order without using the list. Inputs and results are ordered, and can only have one origin, which makes a unique "left to right top-down traversal" possible. If the graph has dead nodes they will not be included in this traversal, however. Deterministically ordering dead nodes requires using the list, but I assume dead nodes can be ignored in most traversals, while dead node removal can be done in any order.