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`.
Add the needed support for running `GenericRegionInfo` on the
`ScopeGraph`.
This needs a new ad-hoc `getGenericCycleInfo` helper in order to unwrap
the `Graph` object (pointing to the underlying `Function *`) from the
`Scope` wrapper object.
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`.
We implement the `GenericRegionInfo` analysis.
The analysis accepts a template parameter which enables to run it on
every graph which exposes `llvm::GraphTraits`.
The `GenericRegionPass` is responsible for instantiating and running the
analysis on a `llvm::Function`.
The `GenericRegionInfo` analysis uses, and takes insipiration from the
`GenericCycleInfo` LLVM analysis.
The analysis exposes a tree of well nested `GenericRegion`s, which are
constructed starting from the well nested tree of `GenericCycle`s.
In addition, we perform the election of the `Head` of each
`GenericRegion`, and the election of the retreating edges.
We introduce the `CycleEquivalence` analysis.
This is an analysis which implements the _Cycle Equivalence_ computation
algorithm, and provides as result the _cycle equivalence classes_
Specifically, we introduce:
- The `CycleEquivalenceClass`, which is the unitary element computed by
the analysis.
- The `CycleEquivalenceAnalysis`, which contains the algorithm to
compute the cycle equivalence.
- The `CycleEquivalencePass`, a `FunctionPass` that can be used to
perform the analysis on a `llvm::Function`.
The algorithm is composed by various stages:
- We construct a new `GenericGraph` object, replicating the input CFG,
with the addition of the `exit`->`entry` edge.
- Taking advantage of `llvm::GraphTraits<Undirected<>>`, we can now
implement the algorithm working on an undirected version of the input.
- We perform the `CycleEquivalence` computation, returning a
`llvm::SmallVector` of `CycleEquivalenceClass` objects.
In addition to using the `llvm::GraphTraits<Undirected<>>` traits to
walk on the equivalent undirected graph, we also need to:
- Perform a preliminary DFS, in order to:
- Assign the DFS number to each node in the graph.
- Compute the spanning tree, and use this information to distinguish
tree edges and back edges when running the algorithm.
The internal graph used by the analysis also normalizes the graph in
order to have a sinle exit node (called sink), which is a requirement
for the `CycleEquivalence` algorithm.
We also implement the `llvm::DOTGraphTraits` for the
`CycleEquivalenceAnalysis<llvm::Function *>` specialization. In this
way, we can have a graphical representation of the undirected graph used
internally in the `CycleEquivalenceAnalysis` core implementation.
We add some `FileCheck` tests on some well-known graph topologies.
We introduce a "dead code" optimization like pass on the AST.
The goal is to simplify away, in a `SequenceNode`, everything that
follows a node with sports a `nofallthrough behavior.
A `SwitchBreak` node should not have a specific associated
`FallThroughScopeType`, since its semantics represent the fact of a
`case` of the `switch` with no associated statements, and thus can be
represented with the `FallThrough` behavior.
Change the analysis in order to lift the assumption that a dispatcher
`switch` always coveris all the values of the variable state. This is
not true after the `simplifySwitchBreak` and `inlineDispatcherSwitch`
beautify passes, which can remove some of the `case`s.
The `FallThroughScope` associated to a `ScsNode` should represent the
fact that we have fallthrough from a loop.
Without any more advanced semantical analysis, we cannot conclude that
we do not have fallthrough.
Do not inline loop related `break` and `continue` statements.
Indeed, inlining them would mean moving from the scope of a cycle, to an
inner one, non-local control flow statements, and this would break the
semantics.
Delay the `SwitchBreaksFixer` beautify pass run.
Specifically, we run it last, as this pass computes information used
only by the backend, and the information it depends upon may be
invalidated by some passes that transform `switch`es (as the
`simplifyDualSwitch` pass).
Delay as much as possible the loop promotion passes, in order to catch
more opportunities.
Specifically, we now perform the loop promotion after the dual case
`switch` promotion pass.
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.
Implement a new beautify pass which simplifies away `SwitchBreakNode`s
that constitute the entire body of `case`s in `switch`es, that do not,
have a `default` case. In such situations indeed, the semantics is,
preserved by removing the `SwitchBreakNode`s.
We drop the assumption that each weaved `switch` must be nested inside
its related main `switch`, as a consequence of having generalized the
tiling algorithm in order to be able to emit a weaved `switch` as a AST
successors of the related main `switch`.
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.
Ivan Krysak