`OSRA:handleComparison` was too big and complex, it has been mostly
rewritten.
* Create `OSRA::identifyComparisonOperands` which expands the argument
of the comparison in a list of possible values (constants or
OSRs). The new way in which we handle possible operands also fixes a
bug showing up in case a constant OSR was being compared with an LLVM
constant, which was checked for being a tautology/contradiction,
preventing the reaching definitions of the operand to be considered
too.
* Squeeze more information from uge/ugt. Unsigned comparisons lead to
two pieces information: the result of the comparison itself, and the
fact the left-hand side is greather than or equal 0. This secondo
information is precious, but we were not able to exploit it in the
case the original comparison is already "greater than" or "greater
than or equal". In fact, `x - 4 > 10` gives us `x >= 4` and `x > 14`,
which boils down to `x > 14`. This commit introduces a change that
handles this case as `NOT x - 4 <= 10` leading to the negation of `x
>= 4` and `x < 14` which is way more informative.
* Improve `OSRA::mergePredicate` and `OSRA::applyConstraints`
interfaces.
* In case a comparison instructions leads to multiple constraints on the
same `Value`, these constraints are now first or-merged together and
then propagated. This change improves the quality of the analysis in
certain situations.
This commit introduces radically changes the implementation of
`BoundedValue`: it no longer represents a single, contiguous range, but
an arbitrary number of ranges.
The bounds are now represented through a
`llvm::SmallVector<std::pair<uint64_t, uint64_t>, 3>`.
* Introduce the `BoundedValue::bounds()` method, which allows to iterate
over all the ranges that a `BoundedValue` represents. The `bounds`
method returns a `Bounds` object, which can be used as a range
composed by `BoundsIterator`.
* All the methods dealing with the `BoundedValue`'s bounds have been
rewritten.
* New debugging information: "bv-merge". Print all the computations
performed by `BoundedValue::mergeImpl`.
* Drop dead code: `BoundedValue::setBound` and `isPositive`
* Introduce `BoundedValue::isRightOpen` and drop
`BoundedValue::isSingleRange`
Some subtle bugs have been fixed in `OSRA::pathSensitiveMerge`:
* Do not alter the current `BoundedValue` if merging a component would
lead to bottom.
* Do not deactivate a reacher in case an incoherent condition is met.
In our reaching definition analysis we used to consider all the loads
not reached by any store as definitions. However we forgot to actually
register them as such, with the result that two consecutive loads from
the same CSV would end up being two free loads.
In `ConditionNumberingPass` we used to consider as resetting the last
basic block possibly interested in a certain numbered
condition. However, what we really meant, was that its successors were
resetting basic blocks. This commit fixes this issue.
`OSR::constant()` used to forward the result of
`BoundedValue::constant()`, but this is wrong, since the factor and the
base value have to be considered too.
Constraints associated to a memory instruction are propagated to
reached loads. However, if a constraint on the same `Value` is already
present, the new constraint should be and-merged, not or-merged.
* Introduce some additional helpers
* Spread some `const`ness
* Improve documentation
* New debugging information: "osr-bv". Prints every update operation
performed in `BVMap::update`.
* Remove dead code
* Whitespace fixes
* Some new TODOs
* Fix some typos in comments
This commit drops the original handcrafted implementation of
`BoundedValue` merging, in favor of an implementation based on Boost
intervals. The old implementation was the source of intermittend bugs,
using Boost should be a more reliable solution. Moreover, this commit
enables moves us towards supporting multiple ranges in `BoundedValues`.
In OSRA we used to track `GlobalVariable`s and `AllocaInst` only,
despite the `MemoryAccess` infrastructure supported memory accesses of
the type register + constant. Enabling this, we're able to handle the
following x86-64 snippet found in the `omnetpp` SPEC benchmark:
cmp DWORD PTR [rbx+0x8],0x5
ja elsewhere
mov eax,DWORD PTR [rbx+0x8]
SET, when getting data from OSRA, used to check that the first and last
materialized address were within a certain range, under the assumption
that the last value would be greater that the first one. Turns out that
this is not always the case when in the operation stack we have a load
instruction. This commit improve the way such a situation is handled.
This commit changes the way instruction and basic block are purged when
re-translation is necessary. Specifically, the purge is now performed
through a post-order visit, which should prevent the removal of any
instructions still holding users.
This commit also introduces the `SubGraph` class, which is useful to be
able to navigate portions of a graph (e.g., a `Function`) in post-order
easily.
The main goal of this patch is to reduce the size of
`OSRAPass::runOnFunction()`. To do this we created the `OSRA` class
which handles everything `runOnFunction` was taking care of but without
the ugly lambdas nor being an endless function. Each class of
instruction is now handled by a dedicated function.
This also has the side effect of heavily reducing the amount of clutter
exposed by `OSRAPass` to its users.
Fix of another bug showing up only with LLVM in debug mode: splitting a
malformed basic block is not allowed, and we had a function call after a
`ret` instruction.
This commit should fix some bugs due to the fact that when we're
splitting a basic block we don't retranslate the basic block at the
split point but preserve the existing code. This lead to problems, in
particular in x86-64 where certain QEMU local variables were not
available. This change should fix it.
Basically, every time we split a basic block in
`JumpTargetManager::registerJT` we note down that the new basic block
must be purged, and in `JumpTargetManager::harvest` we perform the
purge. `harvest` has been chosen since it's a particularly quiet moment,
i.e., there should be no pending references/iterator to code we have to
delete.
This commit fixes a bug that appears only with debug builds of LLVM: in
RDA we were erasing a temporary common predecessor basic block before
removing the references to it in a `switch` statement.
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.
Alessandro Di Federico