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.
The dla::Step ArrangeAccessesHierarchically looks throught the DLA graph
and for each node with many outgoing instance edges tries to see if some
of them are hierachically contained within each other.
In order to do this, before this commit, we were building an auxiliary
graph representing this hierarchy, and in order to build it we had to
perform a number of comparisons between edges that was quadratic with
the number of edges.
Moreover, once all the comparisons were done, we had a deep graph
representing inclusion between edges, but we only cared about the
top-level of this graph, i.e. only the edges that contained other edges
hierarchically, but were not contained in other edges (we'll call them
the root edges).
So we were doing a quadratic number of comparisons but possibly many of
them were useless.
Finally, all the edges that were included in root edges, were pushed
down, but only for a single layer, because they needed to be re-compared
later with the children of the root edges they were being pushed
through. This latter part was responsible for a lot of wasted
computation that just needed to be done over and over at all the layers.
Overall this algorithm was doing a lot of wasted computation.
This commit replaces this logic with a new algorithm.
Now we keep track only of the root edges, and we compare only root edges
with other root edges.
Initially all edges are root edges.
Then we start comparing them.
If a root edge A is included in another one B, then A is not a root edge
anymore, and all the edges that were previously found to be included in
A are not included in B.
This algorithm still does a worst case of quadratic number of
comparisons, but drastically reduces the amount of useless computation
that is redone later. In particular:
- in cases where there are a lot of root edges (meaning that only a few,
or no edge can be included in others) we do a number of comparison
close to quadratic, but we're only pushing non-root edges down, so
we'll never have to redo comparisons in deeper layers
- in cases where there is only a small number of root edges, we're doing
a number of comparisons close to linear, and we never compare non-root
edges with each other, so we're saving a lot of computation that would
be wasted (because it would need to be redone in deeper layers).
Before this commit we were manually building a topological ordering,
that resulted in worse overall performance in some scenarios.
This commit changes the dla::Step to temporarily introduce a fake root
node, and computes a RPOT from there, which overall yields better
results.
InstCombine was disabled in favor of some more basic constant
propagation, but it turns that under certain circumstances this leads to
direct branches appearing as indirect branches until we run InstCombine
during finalization, which triggers an assertion, since we do not expect
any direct jump there.
If this, affects translation performance, we can think to run it less
often.
We always emit a variable for calls to QEMU helpers. For this reason,
for what concerns operator precedence, calls to QEMU helpers should be
considered as references to variables. Hence, they should never be
parenthesized.
Before this commit, calls were marked to push ALAP in the wrong order,
resulting in preventing to actually push them ALAP.
This commit fixes the ordering, reactivating the code motion.
This commit does various things oriented at reducing the number of local
variables emitted in C:
- MarkAssignments now know that @Copy and @Assign involving
@LocalVariable only have side effects that affect the local variable
itself; this enables to reduce the number of times we're forced to
emit a local variable due to interfering side effects
- Drop the @AssignmentMarker FunctionTag; AddAssignmentMarkerPass now
doesn't emit @AssignmentMarker anymore; instead it emits groups of
@LocalVariable, @Copy, and @Assign, which benefit from the previous
point
- Drop 2 MarkAssignments::Reasons: HasManyUses and HasUsesOutsideOfBB;
both these have now been aggregated into the AlwaysAssign reason for
simplicity, representing all reasons non involving side effects
- Update BeautifyGHAST and how it reasons about side effects when
beautifying; before this commit it used @AssignmentMarker, now it
looks at @Assign
- Simplify ExitSSA; before this commit it was trying hard to be smart on
where it emitted the store instructions representing the incoming
values of the PHI that was being destroyed; this seemed smart when we
originally did it but it generated C code that was not really better
to read, so this useless complexity is finally gone
`TupleTreeReference`s use the Root type as a pointer only so they can
operate with forward declarations. Before this commit there were static
asserts that prevented this use case, and thus required the headers
defining the root type to be included before this one to work correctly.
We drop those `static_assert`s to make sure that all headers are parsable
on their own.
This change introduces some duplication but ensures an important
property of `tuple_tree_generate`d: data structures: all the leaves are
scalars. Previously, yield::Function was using efa::BasicBlock, making
things more difficult under certain conditions.
Specifically, we can rely on the fact that, when generating a visit to
the TupleTree, we know everything about all non-scalars.
Alessandro Di Federico