18 Apr 1997 01:04:00 -0400

Related articles |
---|

Reconstructing short circuited expressions Jason_Shirk@ccm.sc.intel.com (Jason Shirk) (1997-04-16) |

Re: Reconstructing short circuited expressions torbenm@diku.dk (1997-04-18) |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 18 Apr 1997 01:04:00 -0400 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 97-04-081 |

Keywords: | optimize |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.