3 ms·

The issue is mostly the need for phi nodes everywhere for "true" SSA. Might get away with something like- and I cite Rust here because I know it well, but thes

The issue is mostly the need for phi nodes everywhere for "true" SSA. Might get away with something like- and I cite Rust here because I know it well, but these features are probably from ML- > let x = if foo { 1 } else { 2 }; Loops are trickier- maybe you could write them as "unfolds"- where the loop body is effectively a fn foo(T) -> T, where T is a struct containing all the variables "modified" by the loop. Then evaluate iteratively, starting from the live values on entry. On exit, the live values are the result of the final invocation

chubot 8y ago
Yeah now I remember from reading this paper a few weeks ago: An important point is that SSA is not executable!!! The Phi nodes need to be removed I suppose. I will have to read this paper about Appel to see how that comes into play. SSA form cannot be directly interpreted in order to generate code. Therefore it must be destructed before compilation can continue. This involves using an algorithm that converts phi-functions into appropriately-placed copy instructions. Intermediate representations in imperative compilers: A survey https://scholar.google.com/scholar?cluster=15761365096026414559&hl=en&as_sdt=0,5&as_vis=1 https://scholar.google.com/scholar?cluster=15761365096026414...
- nickpsecurity 8y ago
  Like with parallel DFS, I always look for anything people say is not possible. Here's my first hit on Google with a super-quick skim indicating it runs with phi instructions: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.9046&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.... May or may not be what you're looking for. Probably interesting nonetheless.
  - chubot 8y ago
    Thanks, that does look interesting. The fact that interpreting SSA requires a paper means it's nontrivial, which lends credence to the original statement :) In the abstract it says they present a variant of SSA. I will take a look.
zozbot123 8y ago
Phi functions are a syntactical hack which can be avoided by allowing a basic block that would contain a "phi function" to instead take parameters (similar to the ANF representation). It's a lot more principled than the "phi" hack, but still quite simple and intuitive.
- abecedarius 8y ago
  I saw somewhere a short paper presenting a syntax to write programs in essentially SSA directly, which I think was sort of like that, but it's not coming up in a quick search. I'd thought it was by Anton Ertl. FWIW, I used this idea (extended basic blocks are functions with m arguments and n results) in https://github.com/darius/idel https://github.com/darius/idel with a Forth-like syntax back in 2001.

chubot 8y ago

Yeah now I remember from reading this paper a few weeks ago: An important point is that SSA is not executable!!! The Phi nodes need to be removed I suppose. I will have to read this paper about Appel to see how that comes into play. SSA form cannot be directly interpreted in order to generate code. Therefore it must be destructed before compilation can continue. This involves using an algorithm that converts phi-functions into appropriately-placed copy instructions. Intermediate representations in imperative compilers: A survey https://scholar.google.com/scholar?cluster=15761365096026414559&hl=en&as_sdt=0,5&as_vis=1 https://scholar.google.com/scholar?cluster=15761365096026414...

nickpsecurity 8y ago
Like with parallel DFS, I always look for anything people say is not possible. Here's my first hit on Google with a super-quick skim indicating it runs with phi instructions: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.9046&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.... May or may not be what you're looking for. Probably interesting nonetheless.
- chubot 8y ago
  Thanks, that does look interesting. The fact that interpreting SSA requires a paper means it's nontrivial, which lends credence to the original statement :) In the abstract it says they present a variant of SSA. I will take a look.

zozbot123 8y ago

Phi functions are a syntactical hack which can be avoided by allowing a basic block that would contain a "phi function" to instead take parameters (similar to the ANF representation). It's a lot more principled than the "phi" hack, but still quite simple and intuitive.

abecedarius 8y ago
I saw somewhere a short paper presenting a syntax to write programs in essentially SSA directly, which I think was sort of like that, but it's not coming up in a quick search. I'd thought it was by Anton Ertl. FWIW, I used this idea (extended basic blocks are functions with m arguments and n results) in https://github.com/darius/idel https://github.com/darius/idel with a Forth-like syntax back in 2001.