Nested SCEVAddRecs are not guaranteed to have strides that go from
larger to smaller. Both cases are valid and can convey interesting
information to DLA. But DLA assumes that the outermost strides are
always larger than the innermost, because this is the only scenario
allowed by well-nested types.
This commit re-orders the strides (and the associated trip counts) so
that they always go from larger to smaller sizes.
The linkOrderLess comparison function is used for sorting the children
edges of a node.
Before this commit, it could not handle the case of comparing an edge
with itself, yielding wrong results (or assertion failure if assertions
were compiled in).
This commit fixes linkOrderLess to handle that case without asserting,
and adds an early return for it, without requiring to inspect the edges
in depth.
DeduplicateUnionFields does not depend on CollapseSingleChild, but can
break if CollapseSingleChild has not run.
However, we don't want to introduce an explicit dependency between the
two steps, because CollapseSingleChild could soon become obsolete on
its own, superseeded by a more powerful and costly step.
This commit changes DeduplicateUnionFields with an additional
pre-processing that runs CollapseSingleChild on each node at step one,
to ensure the step does not fail if CollapseSingleChild child is not
executed.
This DLAStep was moving edges improperly before this commit.
In particular, edges were detected solely looking at source and target
edge, not looking at the edge itself. This was leading to wrong results
whenever a node N1 had many outgoing edges to a child node N2, at
different offsets, where all the edges were moved instead of just the
correct ones.
In order to fix this, this commit:
- reworks the logic of `moveEdges`, switching to iterator-based logic
- reworks the struct OrderedChild used internally by
DLAComputeNonInterferingComponents, so that it is also iterator-based
- re-uses common code for field size computation
This commit moves the logic for the computation of field sizes to a
separate .cpp file.
At the moment this is only used by DLAComputeUpperMemberAccess, but in
the future it will also be re-used DLAComputeNonInterferingComponents,
which at the moment employs very similar code.
Before this commit the case where the DLA recovered narrower sizes for
stack arguments than what expected on the Model was not handled
properly.
Now the scenario is handled explicitly, in two ways
- if the DLA recovers a stack argument with struct type, the fields are
copied to the model in the type representing the stack argument;
- if the DLA recovers a stack argument with a type T that is non-struct,
then the type in the model representing that stack argument is a
struct with a single field at offset 0 and type T.
Before this commit, if the DLA was detecting stack sizes that were
smaller than expected by the Model, the size of struct recovered by the
DLA was edited in-place, enlarging it an possibly leading to a
malformed Model.
This commit fixes the problem:
- the size of the stack struct recovered by DLA is not changed
- the fields of the stack struct recovered by DLA are copied inside
inside the Model in the struct representing the stack
This commit fixes a use-after-poison bug.
DLADeduplicateUnionFields::runOnTypeSystem iterates over the DLA graph
while mutating it.
Due to iterations on copies of the edges, there were some edges to dead
nodes that were still hanging around and could be accessed.
This commit fixes the problem by not saving copies of the edges, but
saving LayoutTypeSystemNode * and iterating lazily on the edges starting
from the node itself every time.
In this way, if the graph is mutated, we never have outdated edges
pointing to dead nodes, and we don't have use-after-poison.
Before this commit, this method could not move Inheritance edges to
offsets different than 0.
This commit enables this action. Inheritance edges that are moved to
offset different than 0 become Instance edges.
This commit changes a bunch of methods of LayoutTypeSystem that were
dealing with edge removal and editing.
The previous version was using linear search with std::find_if on the
neighbours.
This commit switches to using std::set::lower_bound and
std::set::upper_bound, exploiting the fact that edges are ordered based
on the address of the target node.
This makes the code more concise and more efficient.
Inheritance edges have a specific semantic that must derive directly
from the binary, and are often treated specially by DLA steps.
For this reason is not correct to inject them late in the pipeline.
This DLA Step works iterating in post-order on a graph while mutating
it. The post-order traversal is done with llvm::post_order, which holds
an iterator to the next children to visit.
Before this commit, the mutation of the graph could invalidate this
iterator.
This commit fixes the iteration logic, by computing the post-order ahead
of time, without holding around iterators that could be invalidated.
This is possible thanks to the fact that the mutation applied by the
DLADeduplicateUnionFields step on the graph do not change the post-order
visit, so the order computed beforehand remains valid throughout all the
computation despite the mutations that could take place.
The assertGetLayoutTypePreConditions methods didn't really need to be
exposed as methods in a header. This commit moves them to static
standalone functions in the only place they're used.
This assertion was conceived to check that DLADeduplicateUnionFields was
doing its job, ensuring that we never created a union with only one
field.
However, the assertion is too strict, and there are situation that union
deduplication cannot handle and that still generate a union with one
single field. Here's an example
Node A, with Interfering Children
Instance Edge -> Node B
Offset 12 Edge -> Node C
Node C
Offset 12 Edge -> Node D
Node C: uint32_t
Node D: uint32_t
Hence we need to remove the assertion.
Since in the model a FunctionPrototype can be shared among different
functions or indirect calls, we should take into account this fact when
initializing the DLA.
In particular, if the aforementioned case happens, we want to add
equality edges between the return value(s) and the arguments of all the
functions that have the same prototype. These will then be merged by
later steps in the middle-end, and the resulting information will be
shared among all the merged nodes.
Add `MakeModelTypes` and `UpdateFuncPrototypes` to the DLA backend:
* `MakeModelTypes` adds to the model all the types recovered by the DLA
* `UpdateFuncPrototypes` updates function prototypes in the model that
have generic return values or arguments to use the types recovered by
the DLA
* Changes to the `LayoutTypeSystem` graph
Pointers are identified in the TypeSystem graph as leaf nodes which
have a new type of edge (PointerEdge) that connects them to another
node of the graph. The destination of the edge represents the layout of
the pointed type.
* Changes to the Front-end
Pointer edges, and their destination nodes, are created by the DLA
front-end (`DLACreateIntraProceduralTypes`) whenever an access node has
a size that is compatible with the size of a pointer in the current
Architecture.
Successors might then be added to the newly generated node, if any,
by looking up the llvm::Value it is attached to.
* Changes to the Middle-end
Most of the DLA passes should ignore Pointer Edges, so they are modified
accordingly. Most notably, nodes that represent pointed layouts should
never be merged/pruned-off.
* Changes to the Back-end
The `TypeDeclCreationAction` of the decompiler and the `DLAMakeLayouts`
step of the DLA back-end are modified to take into account the new
information about pointers.
⚠️ There is a known issue with this version of the decompiler,
namely the fact that type loops are not detected and can cause the
emitter to enter an infinite loop.
When deduplicating unions, for each union we compare each successor
with all other successors. However, the same successor node might be
reachable by more than one edge from the parent.
This can cause problems when a node gets merged while the comparison is
still ongoing. In particular, since the comparison is done using a copy
of the successor list, to avoid iterator invalidation, the links in
the worklist are not updated when a node gets merged, causing links to
the merged node to have an invalid destination.
The fix here is to keep a list of **nodes** to visit, and a list of
**edges** that have already been visited, so that, if a node is merged
through one of its links, we are not visiting other links connected to
the same node after the merge.
Pietro Fezzardi