Re: Are C logical operators beging lowered too soon?

cdg@nullstone.com (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
exception.


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
it.


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
Bill.Leonard@mail.hcsc.com
--

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