Introduce the `Undirected` GraphTraits, which treats a `MutableEdgeNode`
`GenericGraph` as an undirected graph.
The trait uses the newly introduced `UndirectedChildIterator`, which is
a special custom iterator to get successors and predecessors
concatenated together.
Add some unit tests for `UndirectedChildIterator`.
We introduce the `CycleEquivalence` analysis.
This is an analysis which implements the _Cycle Equivalence_ computation
algorithm, and provides as result the _cycle equivalence classes_
Specifically, we introduce:
- The `CycleEquivalenceClass`, which is the unitary element computed by
the analysis.
- The `CycleEquivalenceAnalysis`, which contains the algorithm to
compute the cycle equivalence.
- The `CycleEquivalencePass`, a `FunctionPass` that can be used to
perform the analysis on a `llvm::Function`.
The algorithm is composed by various stages:
- We construct a new `GenericGraph` object, replicating the input CFG,
with the addition of the `exit`->`entry` edge.
- Taking advantage of `llvm::GraphTraits<Undirected<>>`, we can now
implement the algorithm working on an undirected version of the input.
- We perform the `CycleEquivalence` computation, returning a
`llvm::SmallVector` of `CycleEquivalenceClass` objects.
In addition to using the `llvm::GraphTraits<Undirected<>>` traits to
walk on the equivalent undirected graph, we also need to:
- Perform a preliminary DFS, in order to:
- Assign the DFS number to each node in the graph.
- Compute the spanning tree, and use this information to distinguish
tree edges and back edges when running the algorithm.
The internal graph used by the analysis also normalizes the graph in
order to have a sinle exit node (called sink), which is a requirement
for the `CycleEquivalence` algorithm.
We also implement the `llvm::DOTGraphTraits` for the
`CycleEquivalenceAnalysis<llvm::Function *>` specialization. In this
way, we can have a graphical representation of the undirected graph used
internally in the `CycleEquivalenceAnalysis` core implementation.
We add some `FileCheck` tests on some well-known graph topologies.
The DLAStep SimplifyInstanceAtOffset0 now only triggers if the parent
node has the child-at-offset-0 node as its only successor, or when the
child-at-offset-0 doesn't have other predecessors.
Doing this guarantees that it's impossible for another predecessor of
the child-at-offset-0 to start seeing memory accesses that were
initially relative to the parent.
This condition is slightly more restrictive than the previous one, but
it takes into consideration some far reaching consequences.
If SimplifyInstanceAtOffset0 aggressively like we did before, DLA can
end up inferring types in some memory locations, like executable
segments, for which there aren't clues in the binary.
This isn't bad per se, but if DLA does that, the newly recovered type is
identified as non-executable data, causing misdecompilation because
rev.ng doesn't decompile memory regions that it understands as non
executable.
This commit, making SimplifyInstanceAtOffset0 less aggressive, makes it
play better with the rest of the assumptions of the decompilation
pipeline.
It also relaxes a decompilation test that was previously working by
chance and that was effectively beyond the current expressive power of
reasoning for DLA at the moment.
Before this commit the breadth-first traversal was more convoluted and
it used a broken criterion for bailing out, resulting sometimes in
considering a pointer edge as if it was an instance edge.
This in turn caused bugs to the point of the DLA Graph failing
verification.
This commit rewrites and simplifies the main traversal and comparisons
in DeduplicateField to make them robust against these bugs.
End-to-end tests were disabled due to a bug in ModelToHeader that caused
the decompiled C header with the types not to be recompilable in some
cases.
However, the commit that disabled the tests was too aggressive, because
the only part that needed to be disabled was the part of the tests that
actually recompiled the C code.
This commit re-enables the end-to-end tests except for the recompilation
part, that will be re-enabled after the bug in ModelToHeader is fixed.
Alessandro Di Federico