Before this commit, all the nodes created by weaving were dispatcher
switches. This is wrong, because when you weave a switch coming from
original assembly code you lose information if you lower it to a
dispatcher (for example which variable you are switching on).
This commit likely breaks the emitted C code (which was actually broken
anyway in case a code switch was lowered to a dispatcher).
Later commits will propagate this change to the emission of C code to
fix it.
This was broken after the introduction of `SwitchDispatcherNode`,
because
both `SwitchDispatcherNode` and `RegularSwitchNode` used the `isEqual`
method from `SwitchNode`.
Now the `isEqual` method is implemented only for the `ASTNode` base
class, and each leaf of the llvm-RTTI hierarchy of `ASTNode` properly
implements the comparison.
In presence of a switch node, which contains a case made up of
entirely a sequence of empty nodes (simplified by the
`simplifyAtomicSequence` recursive function), enable the removal of the
aforementioned case from the switch node.
The untangle procedure evaluates the cost of Combing, the cost of
performing Untangling on the 'then' side, and the cost of performing the
Untangling on the 'else' side.
To compute the costs related to 'then' and 'else' branches, it uses the
dominance relationships between then/else and the nodes they can reach.
To do so, it builds a set of nodes that are dominated by the 'then'
__edge__, and by the 'else' __edge__.
Notice, __edge__ is important here.
Before this commit, the computation of these two sets was wrong.
To decide if node was dominated by the 'then' __edge__ it checked if the
node was actually dominated by the __target node of the 'then' edge__,
which is not correct. For a case where this is wrong see the following:
A --(else edge)-> B --> C --> D
\ ^
\ /
-----(then edge)----
Here D is not dominated by the (then edge), but it is dominated by C,
which is the target of the (then edge).
A similar example can be devised for the else edge.
This commit fixes the computation of the two sets, using the dominance
w.r.t. the edge instead of the dominance w.r.t. the target node of the
edge.
This fixes some cases where the untangling was taking the wrong
decision.
The other `_ext` graph iterators from LLVM all use `std::set` as default
template parameter used for the set types.
This commit make `ReversePostOrderTraversalExt` behave the same.
The switch node generation now takes care of setting the correct default
case in presence of a `RegularSwitchNode`. We cross check the default
case with the underlying switch instruction in the LLVM IR.
We now emit `RegularSwitch` node type creating the vector containing the
case values by inspecting the actual values of the `ConstantInt` in the
IR.
Due to the introduction of weaving, we can have a cascade of switches,
and in this case the top switch should bring to a certain weaving switch
for multiple values of the case label.
For this reason, switch case are now represented by sets, which are
usually populated by a single value, but in presence of a weaving
switches they can represent the fact that for each value contained in
the set we must take a certain case label.
The backend of the decompiler has been updated to reflect this change,
in order to emit all the values for a certain `CaseSet` in `or` if the
size of the seat is greater than 1.
Isolated the part creating `switch` AST nodes in a dedicated section of
the `generateAST` method.
In addition, the creation of the standard nodes has been refactored with
a `switch` case covering all the possible situations.
Removed the distinction between entry and exit dispatcher nodes since
they are semantically equivalent.
Only the name differentiates them (useful for debugging purpose).
Drop duplicated code in `addPredecessor/addSuccessor` reusing the code
of respectively `hasPredecessor/hasSuccessor`.
Restructure the code of `hasPredecessor/hasSuccessor` with idiomatic use
of `std::find`.
Restructure the core algorithm of the weaving, according to the
following idea:
- Compute the PDT.
- Iterate on the graph in post order.
- For every switch node S, take its immediate post dominator P.
- Let C be the set of cases for S and iterate in reverse post order on
the nodes N between S and P.
- If N post-dominates at least one case in C, but not all of them, it's
a candidate for weaving.
- Waving inserts a common predecessor K to the cases to be weaved. The
weaved cases are removed from C, and K is added to C (C is the set of
case labels for the switch S).
- The PDT is then updated to reflect the addition of K.
Remove an assert used to check that no switch nodes were present in the
graph. These assertions are not useful anymore since we now handle
generic conditional nodes.
Reorganize attribute `Kind` incorporating it into the `Type` attribute,
by lowering its memory footprint.
Modified the constructors, some accessors and helpers accordingly.
Removed some development leftover in the aforementioned method. In the
future we should consider adding some logic to not set as a successor
for each `switch` node the `unexpectedpc`, which causes sub-optimal
performances in the restructuring (and combing, and untangling, and
waeving).
Improve constructors of `SwitchNode`, `RegularSwitchNode` and
`SwitchCheckNode` by adding a new default parameter for the successor
and therefore removing a useless parameter.
Pietro Fezzardi