Three closely-coupled changes that have to land together to keep
every caller compiling:
- Introduce a per-instance ExtraState recording surface (with a
NoExtraState default) and thread it through applyTransferFunction.
- Replace getMaximalFixedPoint's positional arg list with a single
MFPConfiguration struct, so callers spell out only the fields they
need.
- Replace the EntryLabels pointer with an Entry/All/vector* variant
so callers can ask for the graph entry, every node, or a custom
list without juggling extra arguments.
Update every existing caller for the new signatures and switch
Liveness::GraphType to a plain Function* (with the inverse
GraphTraits selected at call sites).
The implementation of `simplifyTerminator` is very specific to the
operations of IDS, can be easily misused, and is not currently used
anywhere else in the codebase.
* Make the following private headers public:
* Lift/CPUStateAccessAnalysisPass.h
* Lift/CSVOffsets.h
* Lift/PTCDump.h
* Lift/VariableManager.h
* Move from revngSupport to revngLift:
* IRAnnotators.{h,cpp}
* SelfReferencingDbgAnnotationWriter.{h,cpp}
* Move from revngSupport to revngModel:
* FunctionTags.{h,cpp}
* ProgramCounterHandler.{h,cpp}
* Move from revngSupport to revngRecompile:
* OriginalAssemblyAnnotationWriter.{h,cpp}
Drop the `MaterializeLoopScopes` pass after the re-design the loop
matching stage to work entirely on `clift`, without the need to insert a
`scope_closer` edge to guide the emission.
Simultaneously, drop the DAGify `Head` metadata insertion, since it will
not be checked anymore during the `MaterializeLoopScopes` pass.
The `MaterializeLoopScopes` is a scope-inducing transformation, with the
goal of inserting a `scope_closer` edge targeting the immediate post
dominator, outside each `GenericRegion`, in order to materialize the
scope representing the body of each `GenericRegion` on the `ScopeGraph`.
When attempting to simplify away a dummy that simply connects a
Predecessor and a Successor, fail if Predecessor and Successor are
already connected.
In order to handle such failure, we need to decorate a lot of function
on the stack trace in order to be able to propagate the failure code.
The MaterializeTrivialGoto pass, tries to remove superfluous `goto` from
the `ScopeGraph`, by verifying that the resulting `ScopeGraph` does not
become cyclic or undecided.
In that case, it rolls back the changes.
Introduce the `inline-divergent-scopes` pass. This pass in is charge of
reducing the exit nodes in a `ScopeGraph`, applying the _Inline
Divergent Scopes_ transformation, which is able, in presence of
divergent exits nodes, wrt. to a conditional, to remove the exit node
and to transform the `ScopeGraph` in a form where semantics is
preserved.
Introduce the `select-scope` pass. This pass is in charge of enforcing
the relative decidedness property for all the nodes in the `ScopeGraph`,
wrt. to all the conditional nodes. It does this by applying the
relative decidedness definition, electing one scope for each conditional
node in the graph, and by transforming all the edges that would violate
the property into goto edges.
Introduce the `makeGotoEdge` helper to the `ScopeGraphBuilder` class,
that can be used to handle the transformation of a solid edge into a
`goto` edge, taking care of the creation of the `goto` block and the
redirection of the edges.
Implement the DAGify pass. This pass, using the results exposed by the
`GenericRegionInfo` analysis, transforms all the retreating edges of
each identified `GenericRegion`, processed in a bottom-up fashion, into
a `goto` edge on the `ScopeGraph`.
Do not assert if the marker function is not present in the input IR, the
`Builder` instantiation takes care of its on-the-fly declaration
instantiation.
Delete the `Scope(const GraphType &&)` constructor, in order to avoid
potential bugs due to the storage of a temporary reference in the `const
GraphType &Graph` member.
Implement the `Inverse<Scope<...>>` `GraphTraits`. This are needed in
order to support the computation of the `PostDominatorTree` on a
`ScopeGraph`.
Add some `FileCheck` tests to test the dominator and postdominator trees
on the `ScopeGraph`.
Introduce the `EagerMaterializationRangeIterator`, which substitutes the
`GeneratorIterator`, and is used to materialize the successors of a
node in the `ScopeGraph`.
In addition, remove the `GeneratorIterator`.
Introduce the Enforce Single Exit pass, whose task is to normalize a
generic `ScopeGraph`, which may have multiple exit blocks (and/or
infinite loop regions), in order to have a single `sink_block` as exit
block.
This is done by adding a new entry block, a `sink_block`, and some
`scope_closer` edges (which are visible only on the `ScopeGraph`) that
enforce the property.
This is done taking inspiration from how the internally the
`PostDominatorTree` pass construct the temporary graph on which the post
dominance information is computed on.
Some unit tests are added in order to verify that the pass works as
expected.
Introduce the `ScopeCloser` and `GotoTarget` annotations in the IR, and
the relative necessary machinery, needed to handle scope closer and goto
edges for the new backend.
A specialization of the `llvm::GraphTraits`, called `ScopeGraph`, that
is able to handle both the above mentioned annotations is provided.
For the `llvm::GraphTraits` implementation, we introduce the
`GeneratorIterator` class, which uses a coroutine to store the status of
the iteration.
A debug logger pass is added, so that we are able to test the
functionality with `FileCheck`.
Alessandro Di Federico