This commit enables ArrangeAccessesHierachically to push down pointer
edges when rearranging accesses hierarchically.
In particular, if an edge N is being pushed down another edge M, and M
is at offset 0, and N reaches a pointer edge PE that points to a
grandparent G of M at offset 0, then we want to push down the pointer
edge PE so that it points to the target of M, unless there is another
edge M' different from M, such that M' has the same properties of M but
target(M) != target(M').
Before this commit, ArrangeAccesseHierachically was removing nodes from
the graph, instead of merging them.
This degraded the information collected on the graph useful for debug.
This commit drops the use of removeNode method, and switches to using
mergeNodes, that preserves the useful debug information when merging.
Before this commit postProcessMerge was making some strong assumptions
about dla::CollapseSingleChild::collapseSingle that no longer hold.
Namely the (now) wrong assumption is that collapseSingle would not break
post_order iteration, which is now false because collapseSingle can
change the incoming edges of the node it's called on, and those incoming
edges are on the visit stack of the post_order iteration itself.
This required making a copy of the post order, and resulted in dropping
the postProcessMerge function alltogether.
Before this commit we were using int64_t for Offset, Strides, and
TripCounts.
Originally, this choice was intended because for some time we envisioned
actually having a use for negative values, but in the end we decided
there's no use for those.
This commit switches all to unsigned integers, allowing to remove some
static_cast across the codebase, and overall easing typicall computation
we have to perform on those fields.
A logic bug caused the wrong detection of nodes with many fields.
As a result, the field deduplication was only executed on a subset of
the real candidates.
This caused the following two problems.
- Degradation of the quality of the results, i.e. unions that could be
deduplicated were not deduplicated.
- Failing assertions in rare cases.
The algorithm assumes that if it's looking at the children
(C1, ..., Cn) of node A to be deduplicated, then all (C1, ..., Cn)
have beed already visited, hence they don't have children that should
be duplicated because they would have been deduplicated already, when
looking at (C1, ..., Cn). The bug possibly caused to miss the
deduplication of children of Ci (for some i) causing assertions to
fail when looking at A to deduplicate (C1, ..., Cn).
Before this commit, the dla::Step depended on InterferingInfo, but this
was superfluous.
This commit drops the dependency and enables the Step to run before
ComputeNonInterferingComponents.
This also avoids the need to run ComputeNonInterferingComponents twice
(one before and one after DeduplicateUnionFields), so it can only run
once.
Before this commit, CollapseSingleChild Step was thinkering around
with InterferingInfo.
Now CollapseSingleChild does not care about InterferingInfo anymore, so
the code handling it can just be dropped.
The step now collapse parents with their single child if they are
indistinguishable, i.e. if the parent has only that single child, at
offset zero, and their size is the same.
This pass was never implemented and we don't have plans to do it soon.
This commit just drops it to reduce the noise.
Whenever we decide to implement something similar we'll do it from
scratch.
Change company name to "rev.ng Labs Srl" in all license headers
to reflect changed company name and legal status
Add missing license headers to files that didn't have one
Before this commit, each dla::Step handled the printing of its own .dot
files for debug.
This commit moves the logic for dumping the .dot files into the main
loop of dla::StepManager, guarding it with a single Logger.
Before this commit, the dla::Step RemoveInvalidStrideEdges was not
taking into account that dropping edges could change the size of the
node where the edges originated from.
This commit fixes the problem, a) recomputing the size automatically
when needed, and b) adding proper dependencies in the dla middleend
pipeline, so that these changes are properly propagated updwards and
don't break any pre-conditions of following dla::Steps.
This step removes redundant instance-at-offset-0, collapsing the child
into the parent, whenever this operation does not induce instance-loops
on the graph.
This is intended to reduce the number of shallow wrapper structs and
unions.
Before this commit there was a single pass removing equality SCC and
inheritance SCC.
This commit splits the removal of each kind of SCC in a separate
DLAStep, and adds handling of instance-at-offset-0 SCCs that were not
considered before.
The linkOrderLess comparison function is used for sorting the children
edges of a node.
Before this commit, it could not handle the case of comparing an edge
with itself, yielding wrong results (or assertion failure if assertions
were compiled in).
This commit fixes linkOrderLess to handle that case without asserting,
and adds an early return for it, without requiring to inspect the edges
in depth.
DeduplicateUnionFields does not depend on CollapseSingleChild, but can
break if CollapseSingleChild has not run.
However, we don't want to introduce an explicit dependency between the
two steps, because CollapseSingleChild could soon become obsolete on
its own, superseeded by a more powerful and costly step.
This commit changes DeduplicateUnionFields with an additional
pre-processing that runs CollapseSingleChild on each node at step one,
to ensure the step does not fail if CollapseSingleChild child is not
executed.
This DLAStep was moving edges improperly before this commit.
In particular, edges were detected solely looking at source and target
edge, not looking at the edge itself. This was leading to wrong results
whenever a node N1 had many outgoing edges to a child node N2, at
different offsets, where all the edges were moved instead of just the
correct ones.
In order to fix this, this commit:
- reworks the logic of `moveEdges`, switching to iterator-based logic
- reworks the struct OrderedChild used internally by
DLAComputeNonInterferingComponents, so that it is also iterator-based
- re-uses common code for field size computation
This commit moves the logic for the computation of field sizes to a
separate .cpp file.
At the moment this is only used by DLAComputeUpperMemberAccess, but in
the future it will also be re-used DLAComputeNonInterferingComponents,
which at the moment employs very similar code.
This commit fixes a use-after-poison bug.
DLADeduplicateUnionFields::runOnTypeSystem iterates over the DLA graph
while mutating it.
Due to iterations on copies of the edges, there were some edges to dead
nodes that were still hanging around and could be accessed.
This commit fixes the problem by not saving copies of the edges, but
saving LayoutTypeSystemNode * and iterating lazily on the edges starting
from the node itself every time.
In this way, if the graph is mutated, we never have outdated edges
pointing to dead nodes, and we don't have use-after-poison.
Inheritance edges have a specific semantic that must derive directly
from the binary, and are often treated specially by DLA steps.
For this reason is not correct to inject them late in the pipeline.
This DLA Step works iterating in post-order on a graph while mutating
it. The post-order traversal is done with llvm::post_order, which holds
an iterator to the next children to visit.
Before this commit, the mutation of the graph could invalidate this
iterator.
This commit fixes the iteration logic, by computing the post-order ahead
of time, without holding around iterators that could be invalidated.
This is possible thanks to the fact that the mutation applied by the
DLADeduplicateUnionFields step on the graph do not change the post-order
visit, so the order computed beforehand remains valid throughout all the
computation despite the mutations that could take place.
Pietro Fezzardi