Re: Optimizing nested if statements?

Saverio Perugini <sperugin@csgrad.cs.vt.edu> schreibt:


>Is there a program-theoretic operation (e.g., partial evaluation) or
>compiler optimization which will perform this (syntax-to-syntax)
>transformation automatically? I want to collapse/consolidate
>consecutive single variable conditional expressions, where possible
>(i.e., when the conditional does not have an else clause; e.g., the if
>(b) clause above).


What exactly do you want to optimize? Amount of text? Or operation
speed?


A textual optimization is a matter of pattern matching and
transformation.


Execution speed is optimized by the compiler, which produces the same
binary code for all equivalent representations of the same conditional
structure.


A sequence of "if (a) if (b) ..." will evaluate (b) only if (a) is
true, otherwise the evaluation of (b) is skipped. This behaviour may
differ from "if (a && b)", when the language doesn't explicitly
specify short-circuit evaluation of boolean expressions.


More topics are side effects during the evaluation of the conditional
expression, where IMO (depending on the language specs) "if (a & b)"
will evaluate both conditions, and allow for side effects, whereas "if
(a) if (b)" is guaranteed to evaluate (b) only if (a) is true.


And finally the order of evaluation of expressions can be important,
even if no side effects can occur. Usually a compiler is allowed to
rearrange the order of evaluation of subexpressions, so that "if ((a
!= NULL) && (a[1]))" can produce runtime errors, when the compiler
decides to evaluate a[1] prior to checking a for NULL.




In the long form, with nested if's with simple conditions, the control
flow is exactly predictable, what's not necessarily true when multiple
conditions are combined into a single if statement.


Your example fails to address situations where an optimization really would
reduce the amount of source code:
    if (a || b && c) X else Y;
The according long(est) form would be:
    if (a) X else { if (b) { if (c) X else Y } else Y };


Here the code for X and Y must be duplicated in the long form, what's
not necessary when all conditions are combined into a single
expression. But optimization of the long form of this example requires
a comparison of all actions (X,Y) in all branches, before conditions
AND actions can be reduced into a more compact form.


DoDi

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