Re: Are C logical operators beging lowered too soon? (Bill Leonard)
Sun, 19 Feb 1995 19:35:03 GMT

          From comp.compilers

Related articles
Are C logical operators beging lowered too soon? (1995-02-13)
Re: Are C logical operators beging lowered too soon? (1995-02-14)
Re: Are C logical operators beging lowered too soon? (1995-02-19)
| 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
Date: Sun, 19 Feb 1995 19:35:03 GMT (Christopher Glaeser) writes:
> The logical operators && and || are relatively common in C programs.
> However, analysis shows that many compilers fail to optimize
> expressions that contain logical operators.
> In other words, many compilers fail to optimize code fragments of
> the form:
> i1 = x && y;
> i2 = x && y;
> and replace it with:
> reg = x && y;
> i1 = reg;
> i2 = reg;
> This is not only true for CSE Elimination, but many other optimizations
> as well. For example, some compilers can hoist (x + y) in:
> for (i = ...) a[i] = x + y;
> but these compilers fail to hoist (x && y) in:
> for (i = ...) a[i] = x && y;
> Of course, (x && y) is quite different from many other operators due
> to the sequence point, which, in general, requires a branch. However,
> is it possible that compilers are lowering && and || to if-then-else
> too early in the compiler, and thus making it much more difficult
> to perform optimizations which would otherwise be easier to support?

"Too early" is a matter of opinion, but it certainly is true in our
compilers that we "lower" && and || to if-then-else before doing CSE
analysis. But there is a reason for this.

Most CSE algorithms (and algorithms for other kinds of expression analysis)
assume that the operands of an operator will both be evaluated. These
algorithms would be much more complicated if they had to contend with
"conditional evaluation" of operands, as is necessary for && and ||. If
they are *not* so modified, then they can perform invalid optimizations.

For instance, suppose I have the following C code fragment:

        for (...) {
              a = <some expression>;
              b = (a > 0) && (x + y) > 5;

If && is not converted to if-then-else, and the CSE algorithms are not
taught that the second operand is not always executed, then the expression
(x + y) might be hoisted out of the loop. But this is incorrect, because
(x + y) is not always executed! Not only could this cause sub-optimal
code, it could also produce incorrect code if (x + y) can cause an

The CSE analysis would be much harder if one tried to take conditional
evaluation into account, because the primary mechanism for indicating
conditional execution in these algorithms is the flow graph of basic
blocks. By definition, all of the code in a basic block is executed once
the block is entered, and most of the analysis algorithms I've dealt with
depend on this fact.

One *could* do two passes of CSE analysis, one before lowering && and ||
and one after, but the first pass would still have to treat the operands
specially. As our moderator pointed out, the likelihood of finding a CSE
opportunity for && or || is so low that this complication is just not worth

Motto: Just because you *can* optimize something doesn't mean you *should*.

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.