Before this commit, it could happen that some duplicated dummy node
(used to mark backedges) could be left lingering in wrong regions when
collapsing a regions, if they were first iteration outlined.
This commit fixes the problem, by collecting them and letting
`updateNodes` take care of them, removing them from the containing
region and all its parents.
Before this commit, many passes in revng-c were skipping over
non-isolated functions.
Now revng-pipeline takes care of removing non-isolated functions so that
check can be omitted everywhere.
Various improvements to the debug graphs for `restructure-cfg` and
`beautify`:
- Normalize casing and syntax of debug graphs.
- Improve the graph folders name and layout.
- Implement `CFGDumper` and `ASTDumper` for when we need a serialization
with incremental indexes.
- Remove old and stale graph serializations.
Introduce the `DispatcherKind` attribute as a field in the
`BasicBlockNode` and `ASTNode` classes, in order to be able to
distinguish entry and exit dispatchers, and the related set nodes.
Improve the logic of the first iteration outline:
1) The cloning of the nodes involved in the first iteration outlining,
is now performed with a series of DFS visits from all the late entry
nodes in the `MetaRegion`, instead of performing a blind clone of all
the nodes and removing those not needed.
2) Restoring the edges between the cloned nodes has been subject to
minor changes.
3) The outline nodes are now assigned to a `MetaRegion` using a new
logic, instead of blindly assigning them to the parent `MetaRegion`.
Remove old broken code that handled `Set` nodes as source of retreatings
when inserting an `entry` dispatcher. This situation should no longer be
the case, because a `Set` node should not be the `source` of a
retreating edge. We assert this situation.
We now explicitly store the retreatings edges, that will eventually be
connected to the `continue` nodes, so that we can explicitly handle
them, without resorting to iterating over the predecessors of the
`EntryNode`, which although correct is a fragile method with respect to
defective situations.
In addition, we check that after the restructuring, all the retreating
edges that we connect to `continue` nodes, do point to the `EntryNode`
before the transformation.
Before this commit, the code was using an old arcane algorithm that was
adding and removing dummy frontier nodes, and relying on the
DominatorTree.
This commit drops the DominatorTree altogether, drops the use of
frontier nodes, and rewrites the algorithm only using successors and
predecessors.
Now a node outside a metaregion M is included in the metaregion only if
all its predecessors are part of the metaregion, and none of them is
already in another metaregion that is a transitive parent of M.
Before this commit, the whole body of each loop was outlined and
duplicated, only to be removed later if not necessary.
Now we only do this if there is more than one entry to the loop, which
is the simplest condition to detect when first iteration outlining is
needed.
Ensure that no backedges are left after the restructuring of all the
metaregions.
This additional assertion should help ensuring that no entries in the
`Backedges` set are left after the restructuring process, in turn making
it easier to spot bugs if backedges references are not handled correctly
during the steps of the restructuring.
Assign a value to cloned and collapsed nodes in terms of shortest path
from entry, which is a criterion we use to elect region entry.
The shortest path is computed at the beginning for the nodes present in
the CFG, but needs to keep updated for additional nodes that we insert
that may become loop entry candidates.
During the creation of the exit dispatcher, take care of removing from
the `Backedges` set the additional backedge that is collapsed in case
two exiting backedges do target the same destination.
When this is not done, a ghost backedge is left inside the set, making
it not coherent with the state of the graph.
In addition, we add an assertion which ensures that during this phase of
the restructuring dummy nodes are present only as source of retreating
edges, and have one and only one successor.
Now that the late stage of the decompilation pipeline is managed with
revng-pipeline, and we have a standalone tool for decompilation, we
have no need to use LLVM passes anymore for those stages.
This commit also renames the directories to avoid the confusing Pass
suffix, not what LLVM passes are gone.
Alessandro Di Federico