Re:A Simple Graph-Based Intermediate Representation (1995) [...
by eholk on Monday February 03, 2020 @11:43AM
(#22225863)
> - IRs need to be intuitive to the people who work on the compiler. Sea of nodes is more challenging to think about than SSA over CFG.
I worked on V8 for awhile, which uses a sea of nodes representation. This point really resonates with me. I and many of my teammates never completely developed an intuition for the different edges in the graph. There was a lot of trial and error involved.
I remember reading this paper and thinking "wow! this is the solution to all the problems I never knew I had." The generality and simplicity of a single graph that does everything is appealing. But in practice, I think you'd most often be better with SSA over CFG.
Re:A Simple Graph-Based Intermediate Representation (1995) [...
by throwaway17_17 on Monday February 03, 2020 @10:59AM
(#22225294)
I don’t completely disagree with you, but I would point out the paper ‘A Higher-Order Graph-Based Intermediate Representation’ by Roland LeBia, et al from the U of Saarland Compiler Lab. That paper, which describes the groups Thorin IR, does show some advantage to the sea of nodes based approach (although the representation may not be classified as purely SoN). The advantages seem particularly compelling for mixed functional/imperative source languages, which was essentially their goal.
Re:A Simple Graph-Based Intermediate Representation (1995) [...
by hwj on Monday February 03, 2020 @11:22AM
(#22225587)
The name of the author is "Leißa". (The fourth letter is a sharp s).
Re:A Simple Graph-Based Intermediate Representation (1995) [...
by throwaway17_17 on Monday February 03, 2020 @12:13PM
(#22226250)
Apologies, I was aware, but am posting from iOS and couldn’t find the character.
Re:A Simple Graph-Based Intermediate Representation (1995) [...
by gugagore on Monday February 03, 2020 @01:46PM
(#22227468)
fyi, if you long-press the "s" on your keyboard, it should come up as an option!
However, I don’t recommend using this IR style (aka sea of nodes) because:
- The original CFG and the original ordering of operations contains useful data. You want an IR that preserves that at least up to the point where some pass proves that a better order exists.
- Lots of optimizations can be made cheaper to run by using basic blocks, so it’s good to have an IR in which control flow nodes are basic blocks. Load elimination is an example.
- IRs need to be intuitive to the people who work on the compiler. Sea of nodes is more challenging to think about than SSA over CFG.
- There does not exist a program transform or analysis that is uniquely enabled by sea of nodes. Those program transforms that are made easier by sea of nodes are pretty easy to write in SSA over CFG as well.