Value numbering
32 points by asb
32 points by asb
The Pro64 compiler suite used a representation known as hashed static single assignment (HSSA). This named new instructions by hashing the operands and operator and inserting them into a hash table, deduplicating common subexpressions during the initial creation phase.
It’s a neat approach, but it was patented so things like LLVM couldn’t use it. The patent expired over a decade ago though, so I’d recommend reading Fred Chow’s paper describing it.
It's so weird to me how you can patent that sort of stuff. Somebody comes up with a better way to do code generation, and ... nobody can ever use it for decades because this shitty little company with a shitty little compiler nobody uses was inexplicably granted a government-enforced world wide monopoly on the idea.
I wonder if they could have started from Gulwani's work on random interpretation instead (https://people.eecs.berkeley.edu/~necula/Papers/rand_popl04.pdf)
The Pro64 implementation was from 1993, so probably couldn’t build on top of a 2004 paper very easily.
I think they meant "pre-order" toward the end, not "reverse post-order". I didn't know reverse post-order was a thing, but wiki says it is! (It's just post-order with opposite chirality.)