This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Disable CSE skip-blocks
On 10/29/06, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> With just cse-follow-jumps, CSE works on extended basic blocks, which
> is really as simple as we should go I think. Doing CSE only locally
> requires more work (like fwprop) to catch some simple things.
CSE already worked on extended basic blocks before cse-follow-jumps
because it would go through the jump in the fallthrough direction.
What that switch does is to make it go in BOTH directions.
That depends on your definition of an extended basic block. It seems
to me that you're confusing extended basic blocks and traces (paths).
In my previous example, AB and AC are paths, but they are both in the
extended basic block ABC. (For the definition of "extended basic
block" see e.g. http://plg.uwaterloo.ca/~olhotak/cs744/slides/2dfa.pdf
or the Dragon book.)
What you mean is that without -fcse-follow-jumps, CSE would (again for
my example CFG) only be able to follow either AB _or_ AC, depending on
which one is on the fallthrough path. With -fcse-follow-jumps, CSE can
follow the non-fallthrough path also. In my definition of "extended
basic blocks" this means CSE can work on the whole extended basic
block with -fcse-follow-jumps, and only on a trace without that flag.
And that's
the very expensive pass.
That's actually not true in general. Every compiler I know of has some
form of extended basic block value numbering. The only difference with
GCC is that GCC's implementation is just stupid. If you remember the
state of the value and equivalence tables at the end of each basic
block, extended basic block CSE is linear. GCC just rescans from the
first instruction, and *that* is why it is slow.
Removing skip-blocks makes it *much* easier to re-implement GCC's CSE
pass to work on extended basic blocks in linear time.
> So again, that is *not* my intent. If someone wants to investigate
> this, I can only encourage that, but I'm not going to do it.
Sorry, I was talking about understand just what we miss with disabling
-fcse-skip-blocks, at least at this time.
This has been discussed so many times before that it's not funny, but oh well...
My remarks about both were
meant to be very general. I'm all in favor of disabling and then
removing -fcse-skip-blocks, but I think that before we do so (and
hence while we still can) we should analyze what we miss that it's
catching since that should be the empty set.
We miss some very basic constant propagations across the boundaries of
extended basic blocks (my definition ;-). We miss basically no common
sub-expressions.
The missed constant propagations are later caught in gcse's CPROP,
except a few acros critical edges. For that, I need to make CPROP
work in cfglayout mode, so that I can cheaply pre-split all critical
edges. Doing that allows gcse jump-bypassing to work better also, to
the point that rtl jump threading becomes a NOP. The only things we
really miss are addressing modes optimizations that follow from
forward propagation of non-constant expressions. But for loops this
is entirely remedied by TARGET_MEM_REF at the tree level, and for
straight-line code the number of missed optimizations is very, *very*
small. They would be caught by fwprop, if that pass is ever approved.
Gr.
Steven