This enables us to handle situations where the comparison against the
switch value is performed on the lower 32 bits, but the address
computations uses the full 64 bits.
cmp edi,0x23
ja ...
movsxd rdx,DWORD PTR [rcx+rdi*4]
Note that this does not solve all these situations yet.
This commit also introduces a reference output for the new
switch-jump-table-32-bit-comparison test case.
This commit drops support for running StackAnalysis without ABI
analysis. This has been broken for quite some time and a source of slow
downs in (badly) crafted optimization pipelines.
This commit:
* Drops `KeyTraits::toString`: if needed, use `getNameFromYAMLScalar`.
* Makes many methods in TupleTree.h return `nullptr` or `std::optional`
in order to gracefully handle failures.
* Provides `KeyTraits` specializations for integral types and tuple-like
composed by types providing `KeyTraits`.
* Introduces `CompositeScalar`, which enables tuple-like objects to be
YAML-serializable scalars by joining the YAML-serialization of its
members through a customziable character.
* Implements `PathMatcher`, a very simple "regular expression" mechanism
for paths on tuple trees.
* Introduce testing for the Model.
Before this commit, recursive coroutines did not work properly if they
had out arguments with reference type.
The reason is that `rc_run` was inferring the type of its arguments from
the arguments themselves, not from the prototype of the recursive
coroutine.
Hence, code snippets like the following did not work properly, because
`rc_run` was taking x by value, not by reference.
```
RecursiveCoroutine<void> accumulate_on_i(int &i) {
// ...
}
int f() {
int x = 0;
rc_run(accumulate_on_i, x);
return x;
}
```
This commit fixes the problem. Now the arguments of `rc_run` are
properly forwarded to the recursive coroutine.
These are the elementary steps of the DataLayoutAnalysis (that is still
to be defined), along with a manager to handle them, their dependencies,
their executions and their invalidations.
In principle, this design could have been implemented inheriting from
`llvm::Pass` and `llvm::legacy::PassManager` (or `llvm::PassInfoMixin`
and `llvm::PMDataManager` for the new step manager).
However, LLVM's passes and managers provide far more complex features
than we need for now, so I decided to keep it simple and roll our own
for now.
We could potentially switch to LLVM stuff later if we need their power.
Some examples of features we don't need for now are:
- capability to pass results from a pass to another that depends on it
- capability to dynamically compute pass dependencies
- capability to dynamically invalidate passes
If some of these become necessary in future, it's a sign that it might
be time to switch to an LLVM-based design
The design is structured as follows.
1) Adding `Step`s to the `StepManager`
The `StepManager` owns the `Step`s, that can be added via the `addStep`
method.
Whenever a new `Step` is added, four properties are checked:
- that all its dependencies have already been added before it;
- that non of its dependencies have been invalidated by the insertion of
another step that invalidate them.
- that it does not depend on itself
- that it does not invalidate itself
If any of these conditions fail, the `Step` is not added successfully.
Whenever a new `Step` A is added and it invalidates any `Step` B, the
last instance of B added to the `StepManager` before A (if present) is
marked as invalidated.
If one wants to add a new `Step` C that depends on B, it will be
necessary to explicitly add a new instance of A (say A*) before adding
C.
Otherwise, there will be no guarantee that an instance of A executes
before C without being invalidated.
These conditions on invalidations are restrictive but the allow to
specify the dependencies and invalidations that we need for now.
If it turns out we need more complex dependencies and invalidations we
should explore implementing the LLVM-based design.
2) Executing the added `Step`s
After adding the `Step`s to the `StepManger`, they can be executed all
together with the `dla::StepManger::run()` method.
This method runs all the steps in the order they were added by the user
with calls to `addStep`.
The fact that `addStep` strictly ensures that dependencies and
invalidations are respected, guarantees that the execution always works
in the order of `Step`s specified by the user.
It also means that there is no need to check and propagate invalidations
across dependencies between the execution of the `Step`s, because there
is the guarantee that if a `Step` A invalidates `Step` B, another
instance of B will be executed later if some `Step` C needs it, or if
the user has added it explicitly.
When the `dla::StepManager::run()` method returns, all the `Step`s that
were successfully added to the manager have finished running.
3) Implementing a `Step`
Each `Step` has a virtual `runOnTypeSystem` method, that executes the
`Step` and returns true if some change was made, false otherwise.
`TypeSystem` for now is just a forward declaration and all the
implementations of `runOnTypeSystem` simply return true.
This commit fixes a couple of bugs preventing SortedVector and
MutableSet from being serialized.
Also, it introduces minimal testing for serialization.
These data structures are substitutes for a `std::map<Key, Value>` where
`Key` is embedded in `Value`. Their main goal is to be serializable in a
YAML sequence while preserving the order enforced by the key.
`MutableSet` is implemented using a map.
`SortedVector` is implemented using a sorted vector.
RecursiveCoroutines are a facility intended to be used as-drop in
replacement of recursive functions.
They provide the following features.
- They can be written almost as regular recursive functions,
with 4 caveats.
1. A recursive coroutine that returns a type `T`, needs to be declared
to return a `RecursiveCoroutine<T>`.
2. Inside the body of a recursive coroutine, when recursively calling
another recursive coroutine, the recursive call needs to be
prepended by the new keyword `rc_recur`.
3. Inside the body of a recursive coroutine, the `return` statement
needs to be substituted with `rc_return`.
4. When launching a recursive coroutine `A` from a function that is
not a recursive coroutine, `A` needs to be called with the provided
dedicated template wrapper `rc_run`.
The syntax is the following `rc_run(A, arg0, arg1, ...)`.
This is necessary to enable swapping off recursive coroutine and
fall back to regular recursion for debug.
See below for how to do it.
- Unlike regular recursive functions, they don't use the system stack
for recursion. They use a custom heap-allocated stack to manage
recursion. This makes them more robust for implementing recursive
functions that manipulate user-defined input, because they are much
less likely to trigger stack overflow.
- They can be turned off compiling with
`-DDISABLE_RECURSIVE_COROUTINES`, falling back to regular recursion,
for debug purposes.
- They support both direct and indirect recursion, i.e. a recursive
coroutine A can recursively call itself, or it can recursively call
another recursive coroutine B, which in turns recursively calls A.
Sorting the BasicBlocks on which DisjointRanges works is detrimental for
performance. Using a random order takes less time. This is due to the
fact that the number of BasicBlocks to analyze is significantly smaller
than the whole list of BasicBlocks.
This commit drops the `--isolate-no-safety-checks` flags since we
adopted a new approach later on in the decompilation pipeline, i.e.,
dropping calls to `raise_exception_helper` and running dead code
elimination.
We recently bumped the GCC version used for the x86-64 toolchain. The
newer version makes slightly different choices of instruction breaking
the names of basic blocks.
This commit drops them, since they are not really necessary: checking
the order is already more than enough.
These are necessary for this iterator to be a forward_iterator according
to the standard.
Missing these causes compilation errors in some cases when using
functions from the Standard Template Library with these iterators.
This patch adds a two markers for llvm::GraphTraits:
- NodePairFilteredGraph
- EdgeFilteredGraph
Both these markers allow to specify a static predicate that is used to
filter edges.
This predicate is a boolean function such that:
- for NodePairFilteredGraph, it takes a pair of const NodeRef & that
are used to represent an edge, and it evaluates a given property of
that pair;
- for EdgeFilteredGraph, it takes a const EdgeRef & that represents an
edge, and it evaluates a given property on the edge.
The filtered graph contains only the edges for which the predicate
evaluates true.
Notice that the predicate must have static lifetime, meaning that all
the edge properties must be entirely evaluated on the pair of node (for
NodePairFilteredGraph) or on the edge (for EdgeFilteredGraph).
This means that you cannot pass mutable state to the predicate at
runtime.
The new markers are designed to interoperate well with llvm::Inverse and
to allow you to traverse the marked graphs with llvm::depth_first,
llvm::inverse_depth_first, llvm::breadth_first, and to compute dominator
trees and post-dominator trees on filtered graphs.
Alessandro Di Federico