Before this commit, the method could partly fail in moving the edge
target even in legitimate scenarios, because of a bug in how it fixed up
the Successors link in the edge source.
This commit fixes the bug.
Now CompactCompatibleArrays runs after ArrangeAccessesHierarchically.
Rearranging the accesses hierarchically first allows the following step,
that compacts compatible arrays, to achieve better results, and overall
recover much better looking arrays.
This commit extends the CompactCompatibleArrays DLAStep to also consider
non-strided accesses.
Strided accesses are still always considered first, and they are still
considered the only real source of information on arrays, but after
having tried to compact all the compatible arrays,
CompactCompatibleArrays now also considers non-strided instance edges to
see if they can be compacted with the rest of the inferred array.
This has shown to handle gracefully a number of real-world examples and
reduce unions.
Before this commit, the CompactCompatibleArray DLAStep had that caused
the compaction to be sensible to the order of the pairs of edges that
were compacted, and that also caused the compaction operation to overrun
the end of the containing struct in some corner cases.
This commit fixes both bugs.
Now the compaction routine is not ordering-sensitive anymore.
For each pair of edges <A, B> to compact it tries to compact them in 2
possible ways: by aligning A to B shifting A to lower offsets, and by
aligning B to A shifting B to lower offsets.
If both succeed, it picks the best result among the two, which doesn't
depend on the ordering of A and B.
This fixes the order-sensitiveness.
While reworking this logic, the logic was fixed so that if any of the
two compaction attempts causes to overrun the end of the containing
struct, the attempt is not considered successful anymore, and it's
discarded altogether.
The inter-procedural part of the DLA frontend connects actual arguments
of function calls with formal arguments of the callee functions, with
instance links at offset 0.
This represents the information that the type pointed-to by the actual
argument has an instance of the type pointed-to by the formal argument
at offset 0.
Before this commit, this was done even when the actual argument was an
integer constant leading to various problems:
1. Most of the times, small integer constants passed as actual
cannot represent valid pointers, leading to graphs bigger than
necessary.
2. Even when an integer constant might actually represent a pointer into
valid memory, if it does it should fall into some segment.
If it does, by the time DLA runs, those integer constants should have
already converted into calls to the special SegmentRef opcode, which
is already handled properly.
3. Finally, those constants end up being very connected in the DLA
graph, creating connections between other nodes that are otherwise
unrelated or very far from each other. This pollutes the graph and
rapidly degrades the quality of the results.
This commit properly guards the code so that the instance-at-offset-0
link between actual and formal arguments is never injected if the actual
argument is an integer constant.
Before this commit, DLA's backend often emitted things like:
```c
struct x {
struct y {
int32_t z;
uint8_t padding[4];
} _offset_0;
uint8_t padding[8];
};
```
This is suboptimal, since the fields of y actually can just be inlined
into x, giving:
```c
struct x {
int32_t z;
uint8_t padding[12];
};
```
This behaviour was due to a logic bug carried over from old versions of
the code, and partially extended, but never revisited nor thought
through.
This commit fixes the problem, making the second behaviour the only
thing DLA ever does when updating the model.
Basically, struct fields are copied over field by field, instead of
inserting the bulk struct (y in the example) inside the larger struct to
update (x in the example).
Before this commit the DLA frontend was not ready to handle all the
possible combinations of integer- and pointer-typed arithmetic that was
used to compute SCEVs.
This could cause crashes when dealing with pointer-typed SCEVs.
This commit fixes the issues by converting all pointer-typed expressions
to integers, and resizing integers to the same size before adding them.
This commit adds caching for mutual reachability among children of a
node, in SimplifyInstanceAtOffset0.
This makes the DLAStep 10% to 50% faster on real-world benchmarks we
have measured, such as `updatedb.plocate` and `df` for Ubuntu 22.04
x86_64.
llvm::EquivalenceClasses is an efficient data structure from LLVM, to
compute equivalence classes among objects with Tarjan's union-find.
This commit uses that to avoid an hand-crafted very inefficient
algorithm.
Now extractvalue instruction are replaced by dedicated
OpaqueExtractValue custom opcode, that prevents LLVM from doing strange
things with extractvalues during optimizations (such as e.g. sinking).
This is important since extractvalue instructions and struct-typed
values in general in our LLVM IR are not real first-class citizens, but
only a byproduct of the binary lifting process, and they actually
represent bundles of registers that are returned from isolated
functions.
Pietro Fezzardi