When performing a comparison, we try to attach its signedness to the
base OSR it's working on. However, this is not always
effective. Typically, even after this, the OSR remains with an unknown
signedness due to the fact that we don't have information about its
bounded value from all the predecessors, and therefore it goes to top.
`support.c` used to have a basic tracing system which would print on `stderr`
all the program counters. This commit reorganizes this system so that it has a
buffer, whose size can be specified through the `REVAMB_TRACE_BUFFER_SIZE`
environment variable, and it's possible to specify the output file
`REVAMB_TRACE_PATH`. The new tracing system also supports flushing the buffers
in case of clean exit of crash.
We also cleaned up `support.c`.
`support.c` used to be compiled using the system compiler and then
linked to the module generated by `revamb` as a separate translation
unit. This commit introduces a change that lets `clang` compile
`support.c`. This will allow us to make the CSV static, which should
enable more aggressive optimizations.
* Change the signature of the `root` function so that it accepts an
argument: the initial value of the stack pointer, which the main is
supposed to set up. QEMU now provides us with the offset of the stack
pointer.
* Let the build system compile `support.c` for each supported
architecture, both in normal and "tracing" mode.
* Remove the `--tracing` option, this is now handled by `support.c`, in
particular depending on which version of `support.c` you link, you can
have tracing enabled or not.
* In `support.c` drop global variables representing the stack pointer,
we no longer need them.
* In `support.c` fix some warnings while handling the stack on 32-bit
architectures.
* Extende the `translate` script to handle the new way we link the final
binary and the tracing mechanism.
We used to jump directly to the program entry point (typically
`_start`), without initializing the program counter. We now initialize
the program counter and the let the program start with the dispatcher,
since it seems a safer solution.
This commit handles the situation where we have a function call with
more than one successor. This might be the case if there's an indirect
call but we're able to enumerate the possible targets statically.
This commit simply avoids an assertion, in the future we will register
all the possible destinations in the `function_call` marker.
We used to have a normalized address space formed only functions,
skipping all the holes. This was employed to identify "skipping
jumps". However, this method was ineffective, and we changed the
definition of skipping jump as a jump skipping over CFEPs that are
highly likely to be actual functions.
This commit removes the leftovers of the normalized address space
computation, which was also the cause of a bug in function detection.
This commit fixes a bug triggered by specifying the `--entry` switch:
the entry point would not be registered as a jump target, instead the
code would try to get the basic block associated to that address,
resulting in an assertion.
The manually specified entry point is now registered as a jump target
coming from global data.
Introduce an option to prevent `revamb` from linking in all the QEMU
helpers. This is useful if the output doesn't need to be compiled, but
just analyzed.
Currently we're identifying basic blocks that are a jump target by
adding metadata on the terminator instruction. This is a problem in many
cases, therefore we now use the third parameter of `newpc` calls to
understand if a basic block is a jump target.
The third argument was set only at the very end of all our analysis,
before producing the output. We anticipate this so that is done before
each jump target harvesting, so that this information is available
through `GeneratedCodeBasicInfo`.
This commit fixes a couple of bugs in function call
identification.
* Adopt a new version of `visitPredecessors` more similar to
`visitSuccessors`.
* If we meet a call to `newpc` which has an unexpected address (i.e.,
it's not the previous with respect to the last we saw) give up.
* Ensure we went through the required amount of instructions before
finding the return address (in case the architecture has delay slots).
* When counting the number of successors of a function call to check if
there's a single one, ignore the dispatcher-related basic blocks.
This commit reduces the amount of constraint we propagate. We do this in
two ways. First, by computing the set of all the instruction that will
ever be affected by the current instruction (recursively). Second, by
preventing propagation on constraints across function calls.
In quick test on `ls` compiled for MIPS we reduce the execution time by
55% of the peak memory usage by 68%. This makes me quite happy.
This commit introduces two new passes:
* `GeneratedCodeBasicInfo`: recovers from the IR some basic information
like the size of delay slots in the input architecture, the name of
the program counter and so on. It can also identify the type of a
basic block (e.g., dispatcher, jump target...). *
* `FunctionCallIdentification`: identifies function calls and injects a
marker before the associated terminator instruction.
The idea of these two passes is to try to progressively move information
we used to keep in `JumpTargetManager` into the IR, so that it is more
easily accessible and passes do not need a reference to `JTM`.
In particular by having markers for function calls available during jump
target discovery we don't have to have duplicated and suboptimal
implementation of `isCall`.
This commit also introduce some additional helper functions and an
helper class to quickly.
So far we only had end-to-end functionality testing. This commit
introduces a new part of the testsuite which allows to verify quickly if
the results that a certain analysis should give are changed or not. This
is vital to be able to make larger changes.
So far the test suite is composed by the most difficult case we support
(the uClibc ARM memset) and the typical lowering of switch statements
for ARM, MIPS and x86-64.
I'm so happy now.
Let functions such as `JumpTargetManager::readRawValue` take a parameter
specifying if the value should be read from the segment using the
endianess of the original architecture or of the target architecture.
This commit fixes a bug with big endian architectures (i.e., MIPS) since
when materializing a value on the operation stack of SET, the endianess
was changed twice, once in `readRawValue` and the second time while
applying the `bswap` instruction which is registered on the stack.
This commit reworks quite heavily the `ConditionNumberingPass` and the
`ConditionalReachingDefinitionPass`.
* Increase debugging information for both passes.
* `ConditionNumberingPass`: rename the concept basic blocks "defining" a
condition to the concept of basic blocks "resetting" a condition.
* `ConditionNumberingPass`: add to the list of basic blocks resetting a
condition also the basic block post-dominating all the branches
associated to that condition. In this way,
`ConditionalReachingDefinitionPass` will not propagate the condition
after them.
* `ConditionalBasicBlockInfo::mergeDefinition`: merge policy for
condition bits is now simply or-merging them.
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.
Alessandro Di Federico