So far the only tests we had were end to end tests to assess the
functionality of simple programs and, in particular, certain helper
functions. In the perspective of being able to test individual features,
and in particular check that we have no regressions in our analyses, we
isolated these end to end tests in the Runtime directory. We kept in the
root test directory the mechanism to compile a binary for a certain
architecture so that all the test types can use it.
This commit introduces the following feature in
`ConditionalReachingDefintionPass`:
* Propagation of conditions associated to branch instructions across
basic blocks, unless a basic block defines them or the condition is
being propagated by theh current branch.
* Before propagating a definition, sopress in it all the conditions
defined in the target basic block.
* Before propagating a definition, force the condition being propagated
by the current branch to be active in it and its opposite do be
inactive.
`ConditionNumberingPass` now also keeps track of which basic blocks
define the value of a certain condition. This helps the conditional
reaching definition analysis to reset all the definitions associated to
that condition when they are propagated to a basic block which defines
that condition.
Fix a bug which lead to enforce that the left-hand side operand of an
unsigned greater than or greater than or equal comparison was <= 0. This
was the result of some intimate desire for symmetry in my mind which
does not actually exist.
When in `NoFunctionCallsCFG` form it's easy to identify small infinite
loops (i.e., loops without exiting basic blocks), which are often used
to implement the last chance behavior of `abort` or `exit`
functions. Therefore, we include all the involved basic blocks as killer
BBs, which will participate in the computation of the final killer set.
The `purgeBranch` function used to delete the target basic block of the
branch in case no predecessors survived, but this is not correct, in
particular if we already populated it, since we are risking to delete a
basic block already registered as a jump target.
This is probably only a partial solution, since we should check against
JTM if the basic block is registered, but this requires to move the
function in JTM.
This commit improves the `NoreturnAnalysis` by inflating the set of
killer basic blocks using the set of basic blocks post-dominated by the
set of killer basic blocks. To do so, we temporarily replace the
successor of all the killer basic blocks with a single basic block (the
"sink") and then computed the set of basic blocks it post-dominates.
To improve the precision of our analysis we work on the CFG in
`NoFunctionCallsCFG` form, so we don't "infect" functions called by kill
basic blocks. However, since we work in this CFG form, we need to
manually collect the list of basic blocks calling a killer function and
compute the set of basic blocks they post-dominate.
`NoFunctionCallsCFG` is a form of the CFG where all the function call
edges are replaced with jumps to the return address. This is beneficial
in certain analysis to pretend we're working on a function-level.
To implement such a form of CFG we now emit right before the terminator
of each caller basic block a call to the "function_call" function
passing as the first parameter the callee basic block and as the second
one the return basic block. Using this function calls, switching to
`NoFunctionCallsCFG` and back becomes straightforward.
This commit introduces `JumpTargetManager::setCFGForm` which allows to
choose which type of CFG the user currently wants. The default and final
form should be `SemanticPreservingCFG`, which is the most conservative
one. However for certain analysis might be beneficial to have a reduced
CFG with almost no dispatcher (in particular for OSRA and SET).
This new function handles the switching between the two currently
available forms of CFG by changing the behavior of the `anyPC` and
`unexpectedPC` basic blocks and rebuilding the dispatcher as
appropriate.
Every time we don't know where an indirect jump can go, we used to emit
a jump to the dispatcher, however this complicates our analyses, in
particular the computed dominator tree provides less useful information
than it could.
This commit transforms all the jumps to the dispatcher into jumps to a
"anypc" basic block which during analysis just contains an unreachable
instruction, but during finalization this instruction is replaced with a
jump to the dispatcher. A similar (temporary) situation is for the
"unexpectepc" case.
This commit also makes the `visit(Sucessors|Predecessors)` functions
more idiomatic by employing a trait for black lists.
`revamb-dump` is a tool to extract various information from the LLVM IR
generated by `revamb` and output them in a more human-friendly format,
typically CSV. The main source of information are the various metadata.
Currently `revamb-dump` can collect the CFG, function boundaries and
`noreturn` functions.
Create a MDNode for each identified function and associate to the
terminator instruction of each basic block a list containing a reference
to the MDNodes identifying the functions it belongs to.
`JumpTargetManager::readRawValue` used to take into account the
endianess information from `DataLayout`, i.e., the output endianess,
while the input endianess should be take into account.
The commit also checks that during final basic block finalization we
have no empty basic blocks.
This commit removes all the ELF-specific code from the `CodeGenerator`
class by creating a new class, `BinaryFile` which contains all the
information about the program that might be needed in an image format
independent way. However, `BinaryFile` has some fields which are
specific to ELF, we might want to address this when additional file
formats are supported.
A key benefit of isolating this code is that we can anticipate the
parsing of the input file, so that we have its architecture available
earlier than when `CodeGenerator` is instantiated, therefore we can drop
the `--architecture` parameter.
This commit introduces the usage of symbols, if they are available. We
employ them to produce meaningful names for basic block names.
* Collect the symbols from `.symtab`/`.dynsym`
* Box the `Segments` into a new data structure (`BinaryInfo`) which also
handles symbols.
* `JumpTargetManager::nameForAddress`: produce a meaningful name using
symbols, if possible.
* Spread some `const`-ness
* Use "$ORIGIN/../lib/" as RPATH when linking the installed binary
* Install also support material such as "support.c"
* Import the `translate` script for easy end-to-end translation
* Disable PIE if enabled by default
* Link librt.so to compiled binaries (sometimes the QEMU runtime needs
it)
* Replace `strtonum` with `int` in `awk` script
* Specify the compiler, not the triple
This commit handles two cases related to function calls where we want to
limit the propagation of reaching definitions. In the first case down
through function calls, in the second case back up through return
instructions.
For the call instructions, we choose to stop the propagation of reaching
definitions to the callee, since we assume each function should check
its arguments if they affect the control-flow. In particular, this
allows a larger coverage of the function body in case, being able to
enumerate all the calls, we consider dead code those parts that, in the
current program would nevere be executed. Right now we do it in all
cases, it would be more appropriate to do this only if the address of
the function is taken. Also, we should expand this also for tail calls.
For what concerns return instructions, a function called from a lot of
different locations in the code receives a huge number of reaching
definitions. If its close to a no-op, it will also propagate most of
them through the return path. This is an hack to limit how such
definitions spread around the code.
A proper solution, requires to detect the calling convention and allow
to propagate along return paths only return values.
This commit introduces the `noreturn` analysis, whose aim is to detect
all the basic blocks the are doomed to lead to a `noreturn` syscall such
as `execve` or `exit`.
* Implement `NoreturnAnalysis`.
* Include and initialize in the `Architecture` data structure all the
necessary information to detect `noreturn` syscalls. Specifically, the
name of the QEMU helper for syscalls, the name of the register holding
the syscall number and the syscall numbers representing `noreturn`
syscalls.
* `ReachingDefinitionsPass`: make reaching definitions available both in
reaching definitions mode and reached loads mode. This part needs
further cleanup. We also might be willing to implement this with a
`Boost.Bimap`.
* Use `SET` to collect information useful for the
`NoreturnAnalysis`. Also restructure how the `OperationsStack` works
to be more streamlined and keep track of multiple information about
the instruction currently being tracked.
An unsigned comparison such as `x - 3 < 5` carries two information: the
first is the obvious one (`x < 8`), but the other one is even more
interesting. In fact any unsigned comparison implies that the LHS is not
negative, therefore we also can state that `x >= 3`. This commit
implements the usage of this information.
Alessandro Di Federico