This commit changes the `TupleTree::deserialize` method to return an
`llvm::ErrorOr<TupleTree>`, enabling users to choose their policies on
error reporting.
callOnPathSteps was using linear scan search in KeyedObjectContainer.
This commit fixes it for using binary search, dramatically improving
performance in workloads that do lots of lookups.
This commit introduces the type system of the model along with several
various other improvements to the model and its users.
* Introduce the type system.
* Introduce possibility to tag certain fields in the model as to be
optional during YAML serialization.
* All the `Name` fields have been replaced in favor of `CustomName` plus
a `name` method that will use `CustomName` if available, or an
automatically generated name otherwise.
* Make TupleTreeReferences behavior more robust: now you either need to
have a valid pointer to `Root` and a `Path` or be default constructed
(`nullptr` for `Root` and an empty `Path`). Any other configuration is
invalid.
* The type system introduces `RawFunctionType`: this superseds the
previous way in which we were specifying arguments and return
values. Users of such information have been updated accordingly.
This commit drops the KeyTraits in favor of a std::any-like solution.
Basically, we type erase any key the user wants to employ, just exposing
a virtual version of the destructor, a comparison operator and a clone
primitive.
Before this commit, the execution logic of RecursiveCoroutine used an
underlying std::stack allocated on the heap to hold all the
coroutine_handles. It also manually managed passing return values from
callees to callers.
This commit drops this unnecessary auxiliary stack.
When a RecursiveCoroutine co_awaits another one, the handle of the
awaiter is injected into the awaitee, so that when the awaitee is done
it can directly execute the remaining part of the awaiter as a
continuation.
This commit greatly improves the performance by ensuring that, when
computing the set of nodes we want to consider for AVI, we do not
traverse the dispatcher.
Doing so, means including *a lot* of irrelevant nodes and wasting a lot
of computation, since the CFG usually is not influenced by stuff
happening before an indirect jump.
In at least a situation the speedup is in the order of 20x, however this
depends on the size of the binary, since traversing the dispatcher means
including all the binary in the computations (as opposed to just the set
of blocks involved in the dataflow to compute a certain expression).
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.
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.
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.
Unlike the previous iteration of `MetaAddress`, which tried to stuff all
the parts of `MetaAddress` within the existing `PC` CSV, this
implementation adds a set of new CSVs (or marks some existing ones as) to
represent the four portions of the current PC's `MetaAddress`.
* Introduce `ProgramCounterHandler`: a class responsible to maintain the
PC-related CSVs. This class is also used to manipulate the new
dispatcher.
* `AdvancedValueInfo`: update for new MetaAddress.
* External jump handler: do not clobber registers.
When introducing support for dynamic binaries, we didn't realize that
in x86-64 we were clobbering `r11`. To avoid this, we have to jump to
an address stored in memory. However, due to the new `MetaAddress`,
obtaining a *jumpable* address from the PC-related CSVs might require
some computations (and it does in ARM). Therefore, we introduce a new
global variable, `jumpablepc`, whose only role is to contain the
jumpable version of the program counter and then be the target of the
memory-indirect jump instruction.
* Labels care only about absolute addresses.
* CSAA: mark call site, even if no accesses.
* Drop unused argument names from function prototypes
* Make `static` some methods
* Disable some copy constructors
* Fix casing of Doxygen `\file` directives
* Add some casts to make the compiler happy
* Initialize `hasRelocationAddend` for AArch64
* Use references in range-for where possible
* Drop default for `switch` statements covering all the entries of an `enum`
* Make some global variables `static`
* Drop dead functions
Alessandro Di Federico