Introduce a consistency check for loops having an empty body and not
being `DoWhile`s (the only type of empty loops admitted) before they
reach the serialization backend.
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.
We now reduce the number of cases in which we restart the collection of
the `DivergenceDescriptor`s after a IDS modification on the `ScopeGraph`
is performed.
We previously restarted the collection after each IDS transformation.
Now, restart is only performed after IDS is applied on a `Conditional`
node whose all successors are divergent exits which are `goto` exits.
After such `Conditional` is processed, it may happen that a new `goto`
exit becomes divergent for another `Conditional` upwards in the
`ScopeGraph`.
Therefore, if we do not restart, it may happen that a non-`goto` exit is
processed before a `goto` exit, which may lead to suboptimal situations
in the emitted number of `goto`s, due to how IDS interacts with
`MaterializeTrivialGotos`.
When performing the IDS procedure for a divergence which is entered
through multiple `Successor`s of the `Conditional`, we insert a `Head`
header which collects the entry to the scope, in order to maintain
decidedness if there is a common post-dominator to all the `Successor`s
(similar to what weaving did).
Perform the IDS transformation, by taking into account possible multiple
divergent scopes for a certain conditional node at the same time.
This reduces the run times, since it reduces the number of time IDS is
called on a conditional, but mostly proceduce a more _compact_
`ScopeGraph`, where all the divergent scopes for a certain conditional
node rejoing the path toward the one true exit in a single point,
instead of having a chain of IDS resulting regions.
Make IDS unit tests compliant with the new multiple divergence
implementation.
Perform the IDS operation for the exit nodes corresponding to `goto`
blocks afterwards the other _standard_ exits have been processed.
In addition, order the `GotoBlock`s according to the `post_order` of the
target blocks of the `goto` themselves. This should maximize the
opportunities for later runs of `MaterializeTrivialGoto`.
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`.
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.
Andrea Gussoni