Re: Optimizing Across && And || (Bill Leonard)
Sun, 19 Feb 1995 20:10:27 GMT

          From comp.compilers

Related articles
Are C logical operators beging lowered too soon? (1995-02-13)
Optimizing Across && And || (1995-02-15)
Re: Optimizing Across && And || (1995-02-18)
Re: Optimizing Across && And || (1995-02-19)
Re: Optimizing Across && And || (1995-02-21)
Re: Optimizing Across && And || (David Whalley) (1995-02-22)
Re: Optimizing Across && And || (1995-02-23)
Re: Optimizing Across && And || (1995-02-24)
Re: Optimizing Across && And || (1995-02-27)
Re: Optimizing Across && And || (1995-02-28)
[10 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Bill Leonard)
Keywords: C, optimize
Organization: Harris Computer Systems, Ft. Lauderdale FL
References: 95-02-110 95-02-123
Date: Sun, 19 Feb 1995 20:10:27 GMT (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++;

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

      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;
      if (z) {

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

Post a followup to this message

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