Re: Reconstructing short circuited expressions

Jason Shirk <Jason_Shirk@ccm.sc.intel.com> writes:


>I am looking for an algorithm to reconstruct a conditional expression
>that has been short circuited. I can easily build a dag representing
>the control flow of the condition. I just want to reconstruct an
>expression logically equivalent to what the user wrote.


A problem is that it may be hard to isolate the short-circuited
expression code from the code corresponding to statements. But,
assuming that you have isolated the code for the expression, you can
do the following:


  1) Construct a DAG for the expression. This will consist of basic
        blocks, There will be two terminal nodes: one corresponding to a
        true condition and one to a false.


  2) Assuming that boolean values are only created by comparisons and
        hence manipulated by AND, OR and NOT, all basic blocks (except
        for the terminal nodes) will consist of code for evaluating two
        values, a comparison and a conditional jump with two alternative
        destinations.


  3) Now assign the expression TRUE to the terminal node for a true
        condition and FALSE for the terminal node for the false
        condition.


  4) For any node in the DAG such that both its successors have been
        assigned expressions and the node itself hasn't, do the following:


i) Construct the expression Eb for the body of the basic block.


ii) Given Et and Ef are the expressions assigned to the true
and false branches of the conditional branch of the node,
assign the expession (Eb AND Et OR NOT Eb AND Ef) to the
node.


  5) Repeat step 4 until all nodes have been assigned expressions. The
        expression at the root node of the DAG is the desired expression.


The order in which to visit nodes in step 4 can be chosen by first
doing a topsort of the DAG. In step 4, it is a good idea to reduce the
constructed expression using the laws:


  1 NOT TRUE = FALSE
  2 NOT FALSE = TRUE
  3 e AND TRUE = e
  4 e AND FALSE = FALSE
  5 e OR TRUE = TRUE
  6 e OR FALSE = e
  7 e AND (e' OR e'') = e AND e' OR e AND e''
  8 e AND e' OR NOT e = e' OR NOT e
  9 e OR NOT e AND e' = e OR e'
10 e AND e' OR NOT e AND e' = e'


plus the associative and commutative laws. You will normally be able
to remove one of the two occurrences of Eb this way.


Example: The expression a<b AND b<c OR NOT(c<d AND d<e) generates the
shortcircuit code


l0: if a<b goto l1 else l2
l1: if b<c then lT else l2
l2: if c<d then l3 else lT
l3: if d<e then lF else lT
lT: <true branch>
lF: <false branch>


We now assign expressions and reduce


lT -> TRUE
lF -> FALSE
l3 -> d<e AND FALSE OR NOT d<e AND TRUE
        = FALSE OR NOT d<e
        = NOT d<e
l2 -> c<d AND NOT d<e OR NOT c<d AND TRUE
        = c<d AND NOT d<e OR NOT c<d
        = NOT d<e OR NOT c<d
l1 -> b<c AND TRUE OR NOT b<c AND (NOT d<e OR NOT c<d)
        = b<c OR NOT b<c AND (NOT d<e OR NOT c<d)
        = b<c OR (NOT d<e OR NOT c<d)
l0 -> a<b AND (b<c OR (NOT d<e OR NOT c<d)) OR NOT a<b AND (NOT d<e OR NOT c<d)
        = a<b AND b<c OR a<b AND NOT d<e OR a<b AND NOT c<d
            OR NOT a<b AND NOT d<e OR NOT a<b AND NOT c<d
        = a<b AND b<c OR a<b AND NOT d<e OR NOT a<b AND NOT d<e
            OR a<b AND NOT c<d OR NOT a<b AND NOT c<d
        = a<b AND b<c OR NOT d<e OR NOT c<d




which is equivalent to the original expression. You can't expect to
get exactly the same expression back, only one equivalent to it.
Basically, the laws keep the expression in disjunctive (?) normal form
throughout the process and use a standard set of reduction rules for
normal form expressions.


Normal form expressions are often non-minimal, though. A guideline
could be that there should be _no_ duplication of atomic expressions
(e.g. a<b). Duplication can occur either due to the explicit
duplication of Eb in the construction or by duplicate use of the same
label (l2 is used both by l0 and l1). The first case is probably
handled by rules 1-6 and 8-10. Additionally, rule 7 and associativity
and commutativity is used for l0, to eliminate the double use of the
expression for l2. It is not certain that these rules will eliminate
all duplication, though. In particular, rule 7 will duplicate an
expession and should only be used from left to right if one or both
occurrences can be eliminated afterwards.


I hope this is helpful.


Torben Mogensen (torbenm@diku.dk)
--

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