This commit fixes a situation where CollapseSingleChild could introduce
infinite loops composed entirely of pointer edges, which would end up in
making the DLA backend go out-of-memory.
This happened when collapsing a Child at offset 0 into a Parent node,
when Child had a pointer edge going to Parent.
The pointer edge needed not to be at step one, but it could possibly be
a pointer-to-pointer to Parent, at any depth.
After merging Child into Parent this would lead to a node pointing to
itself, which is a forbidden pointer loop in the graph.
This commit catches the pattern and prevents it to merge Child into
Parent.
This commit adds handling for a corner case of
MergePointeesOfPointerUnion, that wasn't handled before.
Said corner case happens when one of the scalars that gets merged as
part of the DLAStep operations is also itself a pointer to another
scalar that gets merged.
This wasn't accounted for before this commit, but it's actually a valid
scenario that can happen on some inputs.
Before this commit, the DLAStep DeduplicateFields was using
NotMergedNode (a reference) in an assertion, in a place where it was
already invalidated by a preceding call to
CollapseSingleChild::collapseSingle that can mutate the graph.
This caused the assertion to trigger erroneously in some situations.
This commit moves the assertion earlier, in a place where the reference
is guaranteed to always be valid.
The old version was unnecessarily convoluted, and had a bug that caused
invalid iterators to be dereferenced in some corner cases.
This commit reworks the DFS and makes it cleaner and easier to follow,
while fixing the iterator dereference bug.
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.
Before this commit the code was wrong in 2 ways:
- if failed to iterate on children, because it iterated a range that was
effectively [begin, begin) instead of [begin, end)
- the update of the ARootNext iterator in the loop was broken, but it
was impossible to realize that since the loop was never taken
This commit fixes both these intertwined problems.
Before this commit, the DLAStep MergePointeesOfPointerUnion wasn't
really equipped for dealing with LayoutTypeSystemNodes representing
types imported from Model.
There was some code that tried to deal with them but it was mostly an
afterthought and it wasn't robust.
This commit fixes that, and is able to handle a strict superset of the
scenarios envisioned before, while preserving the property that nodes
representing types imported from Model should be preserved (in
particular their size).
This commit extends the CompactCompatibleArrays DLAStep to also consider
non-strided accesses.
Strided accesses are still always considered first, and they are still
considered the only real source of information on arrays, but after
having tried to compact all the compatible arrays,
CompactCompatibleArrays now also considers non-strided instance edges to
see if they can be compacted with the rest of the inferred array.
This has shown to handle gracefully a number of real-world examples and
reduce unions.
Before this commit, the CompactCompatibleArray DLAStep had that caused
the compaction to be sensible to the order of the pairs of edges that
were compacted, and that also caused the compaction operation to overrun
the end of the containing struct in some corner cases.
This commit fixes both bugs.
Now the compaction routine is not ordering-sensitive anymore.
For each pair of edges <A, B> to compact it tries to compact them in 2
possible ways: by aligning A to B shifting A to lower offsets, and by
aligning B to A shifting B to lower offsets.
If both succeed, it picks the best result among the two, which doesn't
depend on the ordering of A and B.
This fixes the order-sensitiveness.
While reworking this logic, the logic was fixed so that if any of the
two compaction attempts causes to overrun the end of the containing
struct, the attempt is not considered successful anymore, and it's
discarded altogether.
This commit adds caching for mutual reachability among children of a
node, in SimplifyInstanceAtOffset0.
This makes the DLAStep 10% to 50% faster on real-world benchmarks we
have measured, such as `updatedb.plocate` and `df` for Ubuntu 22.04
x86_64.
llvm::EquivalenceClasses is an efficient data structure from LLVM, to
compute equivalence classes among objects with Tarjan's union-find.
This commit uses that to avoid an hand-crafted very inefficient
algorithm.
Before this commit, the dla::Step CompactCompatibleArrays was
occasionally generating artificial nodes that were larger than the inner
data, forcing their size to Stride - AvailableSlack.
This commit fixes the problem keeping track of the actual size that is
consumed in the array element, and forcing the size of the artificial
nodes to that.
The dla::Step ArrangeAccessesHierarchically looks throught the DLA graph
and for each node with many outgoing instance edges tries to see if some
of them are hierachically contained within each other.
In order to do this, before this commit, we were building an auxiliary
graph representing this hierarchy, and in order to build it we had to
perform a number of comparisons between edges that was quadratic with
the number of edges.
Moreover, once all the comparisons were done, we had a deep graph
representing inclusion between edges, but we only cared about the
top-level of this graph, i.e. only the edges that contained other edges
hierarchically, but were not contained in other edges (we'll call them
the root edges).
So we were doing a quadratic number of comparisons but possibly many of
them were useless.
Finally, all the edges that were included in root edges, were pushed
down, but only for a single layer, because they needed to be re-compared
later with the children of the root edges they were being pushed
through. This latter part was responsible for a lot of wasted
computation that just needed to be done over and over at all the layers.
Overall this algorithm was doing a lot of wasted computation.
This commit replaces this logic with a new algorithm.
Now we keep track only of the root edges, and we compare only root edges
with other root edges.
Initially all edges are root edges.
Then we start comparing them.
If a root edge A is included in another one B, then A is not a root edge
anymore, and all the edges that were previously found to be included in
A are not included in B.
This algorithm still does a worst case of quadratic number of
comparisons, but drastically reduces the amount of useless computation
that is redone later. In particular:
- in cases where there are a lot of root edges (meaning that only a few,
or no edge can be included in others) we do a number of comparison
close to quadratic, but we're only pushing non-root edges down, so
we'll never have to redo comparisons in deeper layers
- in cases where there is only a small number of root edges, we're doing
a number of comparisons close to linear, and we never compare non-root
edges with each other, so we're saving a lot of computation that would
be wasted (because it would need to be redone in deeper layers).
Before this commit we were manually building a topological ordering,
that resulted in worse overall performance in some scenarios.
This commit changes the dla::Step to temporarily introduce a fake root
node, and computes a RPOT from there, which overall yields better
results.
Before this commit, a logic mistake made the AvailableSlack too large
for arrays that started near the beginning of their parent.
This in turn allowed a compacted array to "underflow" on lower addresses
w.r.t. the parent.
This commit fixes the problem by properly computing the AvailableSlack,
restraining it in cases where the array under analysis is close to the
beginning of the parent.
Pietro Fezzardi