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.
* 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.
Alessandro Di Federico