Re: "Documentation by paper"

["Paolo Bonzini" <paolo dot bonzini at polimi dot it>]

> > I assume that everyone knows what dominators and post-dominators are?
> > What about a dominator tree?  Value numbering? SSA form?  How using
> > value numbering on the SSA form during a dominator walk gives us
> > redundancy elimination on an almost-global scale without the need to
> > invalidate values from our hash tables?

I'd expect something like this to suffice [just guessing, this is not about
the actual tree-ssa code]:

"The value numbering pass builds on a simple dominator tree walk.  We go
through every available expression and put it into a hash table ("we give it
a number").  In the dominator tree, blocks higher in the tree must execute
before their children: thus, visiting it pre-order assures that all the
available numbered expressions are already in the hash table.  Using SSA
form, we can avoid building def-use/use-def chains, and find redundant
expressions without invalidating the values into the hash table; we only
remove the expressions from the hash table when we have visited all the
dominated blocks.

Note that the redundancy elimination is not really global because..."

I can presume that SSA form is documented (at least briefly) in the
convert-to-SSA pass.  I would not document the algorithms for convert-to-SSA
though, these are available in compiler texts without substantial flaws.
Value numbering is actually quite trivial, so no paper reference may even be
necessary, but it may be different for SSAPRE or points-to analysis.

> I can't answer for people in general, but I don't know what *any* of those
> things are and I would expect to see at least a definition of any of those
> terms in adequate documentation.  Of course, the documentation can't
> substitute for a good compiler text,

Which you have never read (at least a modern one), if you do not know what a
dominator is.  My first compiler course, which used only part of Appel's
"Modern compiler implementation" (which is nowhere near  in depth with
respect to Muchnick or Morgan) did teach dominators.

I'd love gcc to become a free compiler text, but it is not its purpose.

Paolo