Re: Common Subexpression Elimination Opportunity not being exploited

["Richard Guenther" <richard dot guenther at gmail dot com>]

On Mon, May 5, 2008 at 7:42 PM, Jim Wilson <wilson@tuliptree.org> wrote:
> Pranav Bhandarkar wrote:
>
> > GCC 4.3 does fine here except when the operator is "logical and" (see
> > attached. test.c uses logical and and test1.c uses plus)
> >
>
>  Logical and generates control-flow instructions, i.e. compares, branches,
> and labels.  This makes optimizing it a very different problem than
> optimizing for plus.
>
>  Try compiling with -fdump-tree-all and notice that the "gimple" dump file
> already contains all of the control-flow expressed in the IL, which means
> optimizing this is going to be very difficult.
>
>  We could perhaps add a new high level gimple that contains the C language
> && as an operator, run a CSE pass, and then later lower it to expose the
> control flow, but that will be a lot of work, and probably won't give enough
> benefit to justify it.

There are a couple of things that can be done.  One thing is building a
canonical representation for && and || and their control-flow variants and
doing optimizations on them.  Another thing is to expose the actual
conditions of the COND_EXPRs to the value-numberer, which means
converting

  if (a > b)

to

  cond_1 = a > b;
  if (cond_1)

this way (partial) redundancies can be detected and optimized.  Of course
this may pessimize code in as many cases as it improves it.

Richard.

>  It is simpler to rewrite the code.  For instance if you change this
>   a[0] = ione && itwo && ithree && ifour && ifive;
>  to
>   a[0] = !!ione & !!itwo & !!ithree & !!ifour & !!ifive;
>  then you get the same effect (assuming none of the subexpressions have
> side-effects), and gcc is able to perform the optimization.  You also get
> code without branches which is likely to be faster on modern workstation
> cpus.