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.
Before this commit, CollapseSingleChild Step was thinkering around
with InterferingInfo.
Now CollapseSingleChild does not care about InterferingInfo anymore, so
the code handling it can just be dropped.
The step now collapse parents with their single child if they are
indistinguishable, i.e. if the parent has only that single child, at
offset zero, and their size is the same.
Change company name to "rev.ng Labs Srl" in all license headers
to reflect changed company name and legal status
Add missing license headers to files that didn't have one
Before this commit, each dla::Step handled the printing of its own .dot
files for debug.
This commit moves the logic for dumping the .dot files into the main
loop of dla::StepManager, guarding it with a single Logger.
* 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.
Add a step that recognizes if two subtrees of a union node are
topologically equivalent and merges them. This corresponds to removing
duplicate fields in unions.
This deduplication was prevously done while emitting layouts.
A check is inserted into DLAMakeLayouts to assert that, after
constructing unions, no union has only one child, which could be the
case if we didn't deduplicate union fields in the graph.
Since the reasoning behind single child collapsing can be reused in
other points of the DLA pipeline, move the logic that acts on a single
node in a static function out of the CollapseSingleChild step.
* Inheritance straight lines are now collapsed by CollapseSingleChild
* Don't collapse if parent has more than one parent or if the child has
more than one parent
* Allow the possibility to construct single-member struct: if this
struct is inherited by many other structs, "flattening" the struct is not
the most sensible thing to do, since inheritance information is something
we want to preserve in these cases.
Pietro Fezzardi