This commit fixes a bug that lead to be unable to instantiate from a
`Module` `ProgramCounterHandler`. The reason for this was that
`ProgramCounterHandler` was using `Module::getGlobalVariable` which, by
default, ignores variables with internal linkage.
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.
Problem:
1. `ForwardNode::getConstNeighbor` returns a reference to a non-`const`
object, but the referenced pointer is `const`
2. `FowardNode::toNeighborRange` checks if the type of the argument is
const, but since `Successors` is not declared const the resulting
`toNeighborRange(Successors)` is never executed in the const version
Solution:
1. Make `getConstNeighbor()` return a reference to a `const` pointer
2. Explicitly declare a separate `toNeighborRange()` function which
returns a `const_child_iterator` and remove the template parameter
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 introduces the PruneRetSuccessors pass, whose role is to
identify all the indirect jumps whose devirtualized destinations
correspond to return addresses. In fact, they are most likely to be
return instructions and devirtualizing them is always detrimental.
FunctionIsolation used to base its work on calls to the marker function
`function_call`, as opposed to information provided by the StackAnalysis
(i.e., `revng.member.type` along with `func.call`).
This also affected EnforceABI, which took care of finishing the work
left over by FunctionIsolation. This was hackish and inelegant.
This commit makes FunctionIsolation work exclusively employing
information from StackAnalysis and purges away code that is no longer
necessary from EnforceABI.
EnforceABI promotes global variables representing parts of the CPU
states to arguments and return values of isolated functions.
This commit enables the promotion of CSV that are used in isolated
functions only indirectly, through `ConstantExpr`s casts.
This helper function is now able to replace also uses that are inside
`ConstantExpr`s.
Before this commit they were not substituted correctly, causing problems
down the decompilation pipeline.
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.
Rationale: it is a widespread practice, both in revng and in projects
that depend on it, to write verification functions that check specific
properties hold after different transformations on various data
structures.
Often, these verification function are very useful for debugging and
during development, but they can be very costly and we don't want to
always execute them at runtime.
This patch adds a global public Logger, called VerifyLog, that can be
enabled with the --debug-log=verify command line argument.
This Logger is intended to be used in revng and in projects that depend
on it, as a guard for costly calls to verification functions that do not
need to be performed on a typical execution, but only when debugging.
For now the only user is JumpTargetManager, but other uses are already
envisioned.
This commit makes possible to execute the GeneratedCodeBasicInfo (GCBI)
Pass even on LLVM IR where the AnyPC and UnexpectedPC BasicBlocks are
not present.
This makes the GCBI pass more flexible, enabling more other passes to
depend on it and to use it to retrieve informations on the generated
code without architecture-dependent hacks.
As an example, one can now use GCBI to retrieve the CSV representing the
Stack Pointer Register or the Program Counter Register without relying
on the register names (which are architecture-specific), even if some
optimization pass along the decompilation pipeline has removed AnyPC or
UnexpectedPC.
Notice that the contracts of GCBI's methods has not been changed.
Calling anyPC() or unexpectedPC() still asserts that those are not
nullptr.
The contract has just been moved from the execution stage of the pass
(basically runOnModule), to the APIs used to query the results.
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.
Add EdgeRef and ChildEdgeIteratorType to GraphTraits<DotNode *> and to
GraphTraits<const DotNode *>.
This allows iterating on edges of DotGraphs, which will be useful for
some testing on edge properties.
This commits fixes a typo, probably a leftover from copy-paste, that
caused `DotGraph::end()` methods to actually return `begin()`.
Nobody was relying on this, which caused this bug to go unnoticed.
AVI and InstCombine are the bottleneck of the lifting process.
This commit introduces a whitelist of jump targets that are considered
by AVI during harvesting.
The whitelist is initialized by the jump targets that are new with
respect to the last run of AVI. Then, it's expanded with all the jump
targets that can reach the initial set of jump targets through direct
jumps.
When translation of code overflows into an unmapped page, we can get a
SIGSEGV. To avoid this, for each set of contiguous pages, we add "guard
page" containing an architecture-specific pattern that ensure basic
block termination.
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.
Alessandro Di Federico