Re: Optimizing Across && And ||

I wrote:
[...]
> if(x && y)
> n++;
> if(x && y)
> n++;


Bill Leonard <Bill.Leonard@mail.csd.harris.com> wrote:
> How likely is this to occur in real code?


I suspect that this sort of thing occurs often in macro expansions.


For example, an implementation of the stdio putc() macro for a
very popular OS expands to a complicated conditional expression
including
((p)->_flag & _IOLBF) && -(p)->cnt < (p)->_bufsiz
which is executed once each time an io buffer is output.
People often write code like
putc(x);
putc(y);
or even
for(i=0; i<100000; i++) {
putc(x[i]);
putc(y[i]);
}
in which case there are some serious opportunities for
optimization here. Of course, you'll now insist that I go find
examples of this sort of putc() usage, in real programs, in
places where it matters... Unfortunately, no one pays me
enough to chase this any further :-).


> > if( x && y || x && z )
> > n++;
> > Compiler 1: Loses a value propagation, but OK.
> > Compiler 2: Tests x twice!
> > Compiler 3: Tests x twice!
> >
> > This last result suggests I must be doing something wrong.
> > Surely value propagation across basic blocks will clean this
> > one up?? Comments?
>
> Value propagation? No. Value propagation generally replaces a variable
> reference with a constant that was *assigned* to the variable previously.


You're right. Sigh. I guess the best answer I know of is some
sort of global CSE.


> In this case, no constant was assigned to x. Now let's analyze the "usual"
> way this code is translated:
> if (x)
> if (y)
> goto incr;
> if (x)
> if (z)
> goto incr;
> goto skipit;
> incr: n++;
> skipit:
> Note that the test of (x && z) is done only if (x && y) is false, but this
> doesn't tell you much about the value of x, so x must be tested again. One
> can only avoid the test of x on the paths where x's value is known. Now
> assuming x, y, and z are free of side-effects, we *can* make the following
> transformation:
[transformation deleted]


How about the following, simpler transformation?
      if (x) {
          if (y)
              goto incr;
          if (z)
              goto incr;
      }
      goto skipit;
      incr: n++;
      skipit:
I think this sort of coalescing really is pretty general --
it's been studied more in the context of loops than simple
conditionals, I believe.


Note that I'm cheating a bit above -- things really need to be
turned back into basic blocks:
      if (!x)
          goto skipit0;
      if (y)
          goto incr;
      if (z)
          goto incr;
      skipit0: goto skipit;
      incr: n++;
      skipit:
followed by the obvious goto chain shortening.


> Notice that this is not really just an elimination of the second test of x,
> because we must also adjust the branches of preceding blocks. I wouldn't
> expect many compilers to do this, though, because of the low likelihood of
> an opportunity for it.


Again, see the putc() case above.


Bart Massey
bart@cs.uoregon.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.