Hi all,
This question came to my mind since I saw Julia and DLVM, they are using SSA for their solutions, and relay is using ANF. what’s consideration when we choose different IR?
Julia https://arxiv.org/pdf/1810.07951.pdf
DLVM https://arxiv.org/pdf/1711.03016.pdf
I have some thoughts over this. First of all, relay IR is not strictly ANF. It is dataflow(graph) with let binding and functional support, while have structured control flow blocks.
In particular, supporting structured control flow and dataflow(graph) makes it easy to do rewriting and automatic differentiation. And a few other computational graph rewriting in the way folks usually understand
The advantage of SSA, on the other hand, is the ability to support low level code generation of arbitrary control flow, so it definitely makes sense for LLVM to do so, and we shall use llvm to generate low level code. Never the less, general SSA might complicate some high level optimizations.
I find the current IR design sufficient for now, but we might consider add SSA support on top of functional basic blocks when we find such need
I see, ANF is more friendly for automatic differentiation and high level optimizations, where can I find some cases so I can understand correctly?
another points i wanna to mention, 1) in MLIR and DLVM, they have the same control flow abstraction in their IR, that is as below, this is important for a principled compiler, 2) in DLVM, with its basic IR DLVM expresses complicated ops. these are important things we should learn.
ANF doesn’t seem to be that much different from SSA. However, too general SSA may introduce some issues analyzing stuff like pointer alias. So why not just use ANF for high level and Halide-like IR for low level which may make your life much easier.
In the context of graph we only have tensor expression, I don’t see any issue of pointer alias which is true in the context of traditional compiler. What I want is some insights rather than general points.
Basically, they are formally equivalent. The topic that compares ANF, CPS and SSA goes on for tens of years, but I personally don’t think there is too much difference.
To be more specific, okay, let’s view a Relay func as a basic block with 0, 1 or 2 outgoing edge. This should make some sense.
