Instead of rebuilding the dominator and postdominator at each iteration
of the inflate procedure, use the utilities introduced in LLVM 7.0 to
keep the data structures updated after each change to the RegionCFG.
Now, during the simplification of short-circuits the so called
`de-optimization` is also applied to the corresponding `RegionCFGTree`.
This allows us to avoid loss of information during the iterative
refinement phase, which basically divides for ever the existencies of
two nodes that have been cloned starting from a single original one.
We now perform the AST serialization directly on file, without using
stderr. In this way we can follow the evolution of simplifications and
changes to the AST tree.
After short-circuit simplification, we can have that a conditional node
corresponds to more than one `BasicBlockNode`.
This change reflects this fact, and takes care of merging blocks during
short-circuit simplification, and of representing this change in the
serialization.
Improved the `dumpOnDotFile` function to take as a parameter also a
sub-folder name.
Modified the `inflate` function to dump on file the graphs after each
modification.
Now the `isEqual` operator does what we call a `deep` comparison,
meaning for every type of `ASTNode` it recursively check if the
structures of the AST tree originating in that node can be considered
equivalent (e.g., two sequence nodes are considered equal if every node
they contain is in turn equal).
This operator gives more space to the short-circuit simplification,
which relies heavily on the `isEqual` operator.
First concept of short-circuit simplification.
The `isEqual` operator between ASTNodes is very limited (it does only
check if two nodes originate from the same `BasicBlock` in the original
IR.
Added a new pass that simply purge all the functions in a module from
the useless basic blocks that simply do the `pc` serialization.
Without this until we have available the optimization/comb iterative
refinement, we would not be able to test the short-circuit
simplification.
This commit drops the old FunctionBoundariesDetectionPass and introduces
a new one based on the results provided by the StackAnalysis. A very
similar pass, the ABIDetectionPass, is now available to offer the
results of the ABI analysis too.
These two new passes are a thin shim depending on the appropriate
version of the StackAnalysis (with or withour ABI anlysis) and simply
call `serializeMetadata`, which decorates the LLVM IR with the requested
information.
In addition to drop the old analysis, this commit also isolates the
function boundaries detection pass from `revamb` making it available as
a library only.
This commit does the following:
* It drops `revamb-dump` and transforms all the passes it featured in
passes that can be used directly from `opt`.
* It rename `revamb` to `revng-lift`.
* It introduces a script called `revng` which acts as a driver for the
whole rev.ng project. It replaces `translate`, `revcc`,
`csv-to-ld-options` and `revamb-dump`, since it offers an `opt`
subcommand which allows to easily invoke all the analysis passes.
* It makes the project a CMake package that can be easily used
externally.
* It allows to easily create libraries of analysis to use through
`revng-opt`.
This commit lets the reaching definitions analysis employ results from
the stack analysis to propagate definitions across functions
calls. Specifically, the stack analysis provides a list of registers
that might be clobbered by the callee: definitions concerning those are
not propagated, all the others are propagated.
This change is key to detect jump tables whose address has been
materialized *before* a function call. A test for such situation has
been introduced.
To make this work, the RDA now works over the CFG provided by the
function identification analysis.
The `FunctionCallIdentification` analysis now provides a custom view on
the CFG where 1) dispatcher-related basic blocks are absent, 2) nodes
performing functions calls have an edge to their return address and 3)
nodes ending with a return instruction have no successor.
This CFG is now employed by the reaching definitions analysis and OSRA.
Additionally, the implementation of the `visitSuccessors` and
`visitPredecessors` method has been reviewed. It now consists in a class
that needs to be inherited and for which two methods should be
implemented, one to perform the visit of a block and another one to
enumerate the successors.
In addition, all the users of `visitSuccessors`/`visitPredecessors` have
been updated, a simple set of tests has been introduced and
`GeneratedCodeBasicInfo::visitPredecessors` has been dropped.
This commit fixes a problem that led to use SET to discover very very
simple jump targets: the return addresses of functions call.
Since in this situation, for each call, we needed to run SET, this
commit leads to a *huge* improvements in terms of translation
performance.
This commit also enforces renaming of the translated basic blocks after
they get split and update the ground truth for several analysis tests.
The Reaching Definitions Analysis used to ignore all the memory access
that were not relative to a CSV or an `alloca`. In certain situations,
in particular in x86 which makes heavy use of the stack, this led to
miss certain links that were vital for a correct identification of
certain jump targets.
As an example consider the following example:
cmp DWORD PTR [rbx+0x8],0x5
ja 4bc5c8 <uw_update_context_1+0x148>
mov eax,DWORD PTR [rbx+0x8]
movsxd rax,DWORD PTR [r12+rax*4]
add rax,r12
jmp rax
The constaint on `rbx+0x8` is not propagated to the use after the jump,
due to a missing link.
This commit fixes this by tracking all the memory accesses within the
expressive power of the `MemoryAccess` class, in particular those
expressed as register plus offset.
Additionally, this commit also makes RDA consider as reaching
definitions for a `load` only those definitions that match exactly the
load address, while previously we were considering all the `mayAlias`
definitions. This situation, in combination with the previous change,
led to have paths with multiple reaching definitions, which was
problematic for the path sensitive merge.
Finally, we consider a definition to be clobbered only if there's an
exact store to the esame address, instead of a store on an aliasing
address.
In function isolation, every time we met a jump to an unexpected basic
block (i.e., a basic block that is not part of the current function), we
used to throw an exception. However this is unnecessary since oftentimes
it is sufficient to call the `function_dispatcher` or even perform a
regular function call.
The most obvious example is the case of a direct tail call. In this
situation performing a function call to the corresponding isolated
function is the most appopriate thing to do.
`getType` didn't have a `BlockType` to represent the entry basic block
of the `root` function. Therefore, such basic block was erroneously
identified as a translated basic block.
This commit uses SET, information about canonical values and labels to
detect if an indirect function call is targeting an external symbol.
The strings used for the name of external symbols are uniqued global
variables. This commit also uses this approach for the disassembly of
original instructions, which used to be metadata.
So far we've been tracking only base-relative relocations in an ad-hoc
fashion. This commit introduces a data structure that can describe the
most common relocations, including those for `.got`, `.got.plt`,
base-relative and `R_*_COPY`.
A label describes a range of the binary. A label can be generated from a
symbol (basically assigning a name to range of the binary) or from a
relocation, describing the content of a certain range.
This commit generates labels from symbols and relocations, including
MIPS implicit relocations.
This commit also introduces canonical values.
A register can have a canonical value, i.e., a value that register will
assume when the analyzed module is being run. This is typically useful
for the value of the global pointer, which is different from one module
to another but, within a module, is stable.
This commit registers the canonical value of `gp` (in MIPS), if
available.
Updating to LLVM 7 mainly involved the following steps:
* Upgrade APIs for folding ConstantExpr.
* Upgrade APIs for GraphTraits.
* Upgrade APIs for DominatorTreeBase.
* Upgrade APIs for BinaryFormat to parse ELFs.
* Fix the LLVM Linker to properly link the QEMU helpers.
* Disable the new optnone attribute even with optimization -O0. This is
necessary to allow SROA to do its job properly.
* Upgrade APIs to delete Instructions.
* Properly cleaning up orphaned metadata still referring to Instructions
that have been destroyed. Recent versions of LLVM are more strict in
this respect, and will assert when compiled in debug.
* Avoid using LLVM `getGlobalContext` which has been removed from newer
versions of LLVM.
* Upgrade tests to use the new APIs.
* Upgrade APIs for instruction iterators and reverse iterators.
Andrea Gussoni