Re: Optimizing Across && And || (Barton C. Massey)
Thu, 23 Feb 1995 00:47:56 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)
Re: Optimizing Across && And || (1995-02-28)
Re: Optimizing Across && And || (1995-03-03)
Re: Optimizing Across && And || (1995-03-07)
[16 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Barton C. Massey)
Keywords: C, optimize
Organization: University of Oregon Computer and Information Sciences Dept.
References: 95-02-110 95-02-148
Date: Thu, 23 Feb 1995 00:47:56 GMT

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

Bill Leonard <> 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
((p)->_flag & _IOLBF) && -(p)->cnt < (p)->_bufsiz
which is executed once each time an io buffer is output.
People often write code like
or even
for(i=0; i<100000; 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++;
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++;
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

Post a followup to this message

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