Control flow in complex conditions

During my attempts to understand the control flow analysis in dcc, I'm
quite sure that the algorithm to detect IF statements in dcc cannot
work for complex conditions, consisting of more than 2
conditions. E.g.:


if (a && b) || (c && d) ...


In such conditional expressions many labels (BBs) can belong to the
condition evaluation, before the final Then/Else labels are
referenced. Many of these nodes can have the IF as their immediate
dominator, and they can have more preds than the follow (EndIf)
node. So most of the assumptions in dcc, about the structure of
condition evaluation, don't hold :-(


Does anybody know of better working algorithms, to determine the structure of
IF statements and complex conditions?




In my last approach I tried to find the Then node first, by skipping
over all un/conditional jump instructions, until a statement (other
instructions) is found, or some other condition indicates, that the If
statement must end here.


Inside a single complex condition only the following jump targets (successors)
can occur:
- the Then and Else (or EndIf) nodes
- nodes between the If and Then nodes


Having found the Then node, we can work back through the nodes and add
all nodes to the innermost IF, which satisfy the above
restrictions. Regular conditional expressions have further
restrictions, like that the immediate dominator of the Then node must
be the header node of the innermost IF statement.




This is roughly the algorithm, which I used to determine the structure
of nested IF statments, in my old experimental decompiler. Now I would
like to prove, that this algorithm is correct, but my theoretical
background is insufficient :-(


Any contributions are welcome...


DoDi

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