Re: Are C logical operators beging lowered too soon?

cdg@nullstone.com (Christopher Glaeser) writes:


> 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;
> 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?


> [My guess is that nobody bothers to optimize this, because && and || rarely
> occur outside of a truth value context in if, while, or for. -John]


Probably it's lowered too soon.
This looks to me like another example of a missing "canonical form".
(early on the compiler should push things into some canonical form
so that later phases see common cases in easy-to-recognize forms.)


First the compiler should lower everything to it's least common denominator.
Then the compiler uses pattern recognition to raise back up everything that
it lowered, plus anything that matches the pattern. The crucial part is
that it raises back up _everything_ that got lowered. Then the optimizer
goes to town on the raised forms. The backend/code-generator ends up with
the option to lower again if it's appropriate (instead of being forced to
deal with a pre-lowered form). For this case:


Lower "x && y" --> "if(x) { if(y) 1; else 0; } else 0;"
If "y" is side-effect free, compiler pattern matches it back to "!!x & !!y"
(where "!!x" means 0 if x is zero and 1 otherwise).
Optimizer goes to town on either form. Portions of the second form can
be hoisted, CSE'd etc. The first form has control flow, and optimization
is more restricted.


Later the back end is presented with the optimized "x & y" version.
The back end can choose to use conditional assignment, a real boolean AND,
control flow or something else to handle this case.


If the back end is handed "if(x) { if(y) 1; else 0; } else 0;" it's
choices are more restricted: it's handed control flow so it will
generate control flow.


To summarize: replacing control flow with data flow should happen early on,
so that optimization phases benefit and this transformation needs only be
implemented up front. The backend should handle the reverse case (data flow
back to control flow) when it makes sense on an operator-by-operator basis.
If-converting vectorizing compilers need not apply :-)


Cliff
--

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