[Restructuring] Resolve unresolved reaching conditions

[ebehner]

Proposal

During the restructuring, when we restructure a region, each node gets a reaching condition. Using these reaching conditions we try to find if-else and switch constructs. Nevertheless, not all reaching conditions are resolved by these algorithms, i.e., at the end of the restructuring, there may be still some nodes whose reaching condition is not true. Thus, these reaching conditions have to be transformed into if-constructs.

Currently, we simply add a condition node before a node with a reaching condition that has as condition the reaching condition of the node. But sometimes, this does not lead to the best possible output.

Here are some examples where another approach would be better:

1. If we have two nodes with reaching conditions (!x1 & x2) and (!x1 & !x2), then we first restructure the if-else with the condition x2, resulting in the following AST (nodes 6, 7, 8):
   
   After resolving the unresolved reaching conditions it results in the following AST:
   
   A better solution would be to add the condition before node 6:
   

This example belongs to test15 in test_condition.zip

2. If we have already a condition node with the condition x1 and we have a node with reaching condition x1 & cond that we want to resolve, we do not add this node to the existing condition node (if it is possible due to reachability), where cond is an arbitrary condition that could also be true.

Consider, for example, the following AST, where we have a condition node with the condition x1 and a node with reaching condition !x1 & !x2.

When resolving the reaching condition for code node 6, we get the following AST:

However, we could also add this node to the false-branch of the condition node, i.e., we would like to have the following AST:

This example belongs to test16 in test_condition.zip

Approach

No response

[ebehner]

/cib

[github-actions]

Branch issue-28-_Restructuring_Resolve_unresolved_reaching_conditions created!