Before this commit, switches were treated as normal conditional nodes.
This was wrong, because treating a switch as a conditional node does not
guarantee that all the parts of the control flow representing each case
are really combed.
This commit removes switch nodes from conditional nodes, and creates a
dummy for each case. All the dummy cases are treated as conditional
nodes inducing duplication separately, instead of the actual switch.
This has the consequence of enabling the combing to proper comb the
switch cases from each other, without altering the combing algorithm.
Each switch case is combed until the combing finds the post-dominator
of the switch, not the post-dominator of the case.
This method was used to sort vector of nodes either in post-order or in
reverse-post-order.
It had 2 problems:
- the boolean argument used to select between POT and RPOT was no longer
used, since all the remaining call sites passed false.
- it was expensive to call, because it took a vector, it created a set
from it, and performed a reverse-post-order-traversal of the whole
graph while pushing the nodes to sort back into a newly allocated
vector. This was particularly problematic because in one of the call
sites a reverse-post-order-traversal was already available, but the
method did calculate a new one nonetheless.
The method is removed in this commit.
All the call sites have been modified to use the
reverse-post-order-traversal object if already available, and they
avoid allocating a new set for the computation and a new vector for the
results. The initialization is now performed directly into a set, and
the sorted results are pushed into a vector. This effectively saves the
allocation of a vector in each call site.
The weaving routine included a check that the candidate node for weaving
was not one of the case blocks of the switch. This check was likely
introduce to mask an old malfunction, caused by a missing update of the
CaseSet data structure, that has since then been removed.
This check was now useless and this commit removes it.
Before this commit, the original llvm BasicBlock was not embedded
properly in the GHAST SwitchNodes. This caused problems and crashes in
decompilation.
This commit SwitchNode constructors so the that the BasicBlock properly
reaches the GHAST and it is printed correctly by the decompiler.
Before this commit, the C statements before an IfNode or a SwitchNode
were not guaranteed to be emitted if they were not involved in the
computation of the branch condition.
This commit fixes this problem.
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.
This commit removes a call to untangle() that was performed before the
whole combing algorithm on the root RegionCFG.
The call was redundant before introducing the weaving, and became
plainly wrong after adding the weaving, because it ended up trying to
untangle the root RegionCFG before weaving (which is supposed to run
first).
Removing the dedicated call fixes the bug, because weaving is performed
first as part of the call to generateAst().
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.
`llvm::removeUnreachableBlocks` doesn't just drop dead basic blocks,
it also turns certain `SwitchInst` into `BranchInst`, which leads to
hard-to-debug issues in parts of the code where we don't assume
unexpected changes such as this.
Function isolation used to mishandle blocks of type
`BlockType::IndirectBranchDispatcherHelperBlock`. This led to have
empty basic blocks instead of the dispatcher for handling indirect
branches.
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.
Pietro Fezzardi