* 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.
* When creating a new `BoundedValue`, check if the value associated to
it is a `ConstantInt` and if so, initialize the boundaries and the the
signedness as appropriate.
* Add various checks for the presence of the signedness information
before using functions that might require it.
* Clear all the data that's not part of the analysis results at the end
of the `runOnFunction` method
* Clear all the data that's part of the analysis results when the
`PassManager` tells us so (`Pass::releaseMemory`)
* Do not use the `clear()` method, since it doesn't release memory
* Add some debugging information
Record amount of reaching definitions for each load, even in
`ReachedLoads` mode, so that we can run the `pathSensitiveMerge` only
when we're sure we've collected all of them.
In `ConditionalReachingDefinitionsPass` switch from a `std::vector` of
pairs to an `std::unordered_map` of `llvm::SmallVector`. This is a
non-negligible impact on performances.
An instruction can now subscribe for the change of the list of reachers
of a certain load. This is particularly useful in the case of `ICmp`
instructions, which might hold constraints about the reachers of a
certain load without actually being a its user.
This patch removes the `JumpTargetManager::isInterestingPC` function
which used to prevent to register a jump target if it already
was. However this also prevents from marking that jump target as seen by
SET.
This patch introduces in `JumpTargetManager` a pair of `begin` and `end`
methods which allow to iterate over all the registered jump targets, and
obtain the reason that lead to register them (through the `JumpTarget`
class).
`OnceQueue` is a queue which not only keeps track of what's already in
the queue and prevents it from being re-inserted, but also keeps track
of what has ever been in the queue, and prevents it from returning to
the queue.
`OnceQueue` is implemented by adding a new template parameter to what
was once `UniquedQueue`.
This commit registers for each jump target how we met it, as a flag. It
also keeps track of which pointers in global data have been involved in
materialization performed by SET: those who are not are of special
interest for us, since they are likely function pointers, and are
therefore marked with a specific flag.
Before this commit, loads with multiple definitions were handled by
simply checking if all the definitions agreed. Now we also implement
some logic to put constraints on the new OSR, in case they don't agree.
To do this we implement a path-sensitive algorithm to collect
constraints about the reaching definitions.
This commit also introduce a set of methods to, if possible, apply an
OSR to a BoundedValue, e.g. [1 + 1 * x] will produce a new BoundedValue
whose bounds are shifted of 1 unit.
In OSRA, when producing constraints associated to a `ICmpInst`
associated to a load instruction, consider also all of its reaching
definitions.
Moreover, when propagating constraints due to a `Br` instruction, look
for loads which might be affected by the constraints being propagated,
and, if necessary, update them.
Three new passes have been introduced:
* `ReachingDefinitionsPass`: classical reaching definitions analysis
working on load/stores with the main difference that a load without a
definition behaves similarly to a definition and that we ignore
certain basic blocks (i.e., the dispatcher).
* `ConditionNumberingPass`: goes through all the branch instructions to
check if some of them use an equivalent condition, this is
particularly useful to understand that consecutive ARM instructions
using the same predicate are working on the same condition.
* `ConditionalReachingDefinitionsPass`: identical to
`ReachingDefinitionsPass` but uses information from
`ConditionNumberingPass` to stop certain definitions from reaching
certain loads.
The first and the last analyses have `Reached*` variants which expose
information from the point of view of the definintion instead of from
the point of view of the load.
Constant OSR are now represented through an OSR such as
[0 + 1 * x with x = (*, c, c)]. Since equality doesn't hold any
signedness information we introduce a new signedness type (available
only in `BoundedValue`), `AnySignedness`, which is similar to
`UnknownSignedness` but does not trigger `isUninitialized() == true`.
In `BVMap` we also introduce the concept of "forced" constraint, i.e. a
constraint that is fixed, cannot be changed or update. Constant stores
will produce this type of constraints.
* When generating the code for setting a label or jumping to it, give
sensible names to the new basic blocks.
* Keep track of the last seen PC during translation so it can be used to
obtain a sensible name for the basic block.
* Let `JumpTargetManager::getBlockAt` set a proper name to the basic
block before returning, if it doesn't already have one.
This commit introduces the `getName` function, which, given a
BasicBlock, an Instruction or a Value, outputs a sensible name. In
particular instructions are now identified as [basic block]:[instruction
index].
`getName` is now used in the various `describe` methods in OSRA.
Alessandro Di Federico