We now set the postdominator (meaning the point where the combing stop
the exploration for dominated nodes) for the case nodes using the
postdominator of the switch node corresponding to the case.
Workaround that resort to looking for the original switch node in the IR
to force the creation of a switch node even if we have < 4 nodes under
our domination.
First implementation sketch of the waveing pass.
The implementation operates by going through the postdominator tree, and
by adding preposterous switch nodes in case we have a topology that we
cannot emit using standard switches.
In this way, we build a tree of nested switch costructs.
Added a new constructor for the dispatcher nodes which will be emitted
as `switch` nodes by the decompiler.
These nodes are introduced during the restructuring phase as loop
dispatchers.
Improved the creation of `Regular` and `Check` switch nodes types during
the preliminary AST creation phase performed on the `RegionCFG`.
In particular, we now handle the dispatchers creating the right AST node
type.
Create directly regular switch nodes in the AST build starting from the
`RegionCFG`.
As of now, a switch node is built only if we find a node that
immediately dominates more than 3 nodes.
In the future, we will need to refine this criterion.
During the RegionCFG creation from the LLVM IR handle the creation of
nodes with possibly more than two successors.
In this way we do not have to disassemble the switch nodes in nested if
trees.
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.
`MetaAddress` replaces all the `uint64_t` used to represent a virtual
address. Its main features are:
* It has a non-zero representation of invalid addresses.
* It supports tags to represent code that has different interpretations but
resides at the same address in memory (namely ARM vs Thumb).
* Arithmetic operations cannot overflow.
* It supports epochs, a way we intend to employ to handle self-modifying code
(i.e., different code at the same address at different times).
* It supports "address spaces", which enable handling architectures with
multiple address spaces.
* It fits in two 64-bit registers.
Andrea Gussoni