code review 5190043: 5g, 6g, 8g: fix loop finding bug, squash jmps

5g, 6g, 8g: fix loop finding bug, squash jmps

The loop recognizer uses the standard dominance
frontiers but gets confused by dead code, which
has a (not explicitly set) rpo number of 0, meaning it
looks like the head of the function, so it dominates
everything.  If the loop recognizer encounters dead
code while tracking backward through the graph
it fails to recognize where it started as a loop, and
then the optimizer does not registerize values loaded
inside that loop.  Fix by checking rpo against rpo2r.

Separately, run a quick pass over the generated
code to squash JMPs to JMP instructions, which
are convenient to emit during code generation but
difficult to read when debugging the -S output.
A side effect of this pass is to eliminate dead code,
so the output files may be slightly smaller and the
optimizer may have less work to do.
There is no semantic effect, because the linkers
flatten JMP chains and delete dead instructions
when laying out the final code.  Doing it here too
just makes the -S output easier to read and more
like what the final binary will contain.

The "dead code breaks loop finding" bug is thus
fixed twice over.  It seemed prudent to fix loopit
separately just in case dead code ever sneaks back
in for one reason or another.

[rsc, 2011-10-04 19:06:17]

Hello ken2 (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[rsc, 2011-10-04 19:06:24]

*** Submitted as http://code.google.com/p/go/source/detail?r=de5179577ab4 ***

5g, 6g, 8g: fix loop finding bug, squash jmps

The loop recognizer uses the standard dominance
frontiers but gets confused by dead code, which
has a (not explicitly set) rpo number of 0, meaning it
looks like the head of the function, so it dominates
everything.  If the loop recognizer encounters dead
code while tracking backward through the graph
it fails to recognize where it started as a loop, and
then the optimizer does not registerize values loaded
inside that loop.  Fix by checking rpo against rpo2r.

Separately, run a quick pass over the generated
code to squash JMPs to JMP instructions, which
are convenient to emit during code generation but
difficult to read when debugging the -S output.
A side effect of this pass is to eliminate dead code,
so the output files may be slightly smaller and the
optimizer may have less work to do.
There is no semantic effect, because the linkers
flatten JMP chains and delete dead instructions
when laying out the final code.  Doing it here too
just makes the -S output easier to read and more
like what the final binary will contain.

The "dead code breaks loop finding" bug is thus
fixed twice over.  It seemed prudent to fix loopit
separately just in case dead code ever sneaks back
in for one reason or another.

R=ken2
CC=golang-dev
http://codereview.appspot.com/5190043

[ken3, 2011-10-18 23:34:23]

lgtm