Re: Optimizing Across && And ||

bart@cs.uoregon.edu (Barton C. Massey) writes:
> I was curious: unfortunately, even in a truth-value context
> inside an if(), the compilers I just tried mostly lose. I put
> together a sequence of simple benchmarks that I expected the
> compilers would all optimize perfectly, as a starting point to
> see how bad the problem was. I'll publish something more
> formal if there's interest, but here's a sketch of my (very)
> preliminary results. (Compiler 1 is a popular free C compiler
> running on a popular RISC architecture, compilers 2 and 3 are
> vendor's proprietary compilers for two RISC architectures. All
> were run with the best optimization flags I could figure out
> without extensive meditation.)
>
> benchmark:
> if(x && y)
> n++;
> if(x && y)
> n++;


How likely is this to occur in real code? I could always construct some
benchmark that tests for a particular (perhaps obscure) optimization that
would show lots of compilers to be "deficient", but unless that benchmark
represents a real application, it a completely artificial measure of a
compiler's effectiveness. However, you can be sure that if such a
benchmark becomes widely used to measure compilers, lots of compilers will
start implementing that optimization, regardless of whether it does any
users any real good or not. :-)


> benchmark:
> if( x && y || x && z )
> n++;
> result:
> 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.


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:


      if (x) {
            if (y) goto incr;
            goto testz; /* x is known to be non-zero here */
      } else {
            /* x is known to be zero here. No need to test z. */
            goto skipit;
      }
      testz:
      if (z) {
            incr:
            n++;
      }
      skipit:


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.


--
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.hcsc.com
--

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