The stack analysis identifies CSV as `CPU+x` where `x` is an index that
uniquely identifies a CSV. We used to compute this index multiple times,
going through the list of global variables.
After we switched from metadata to global variables for strings
representing disassembled instructions, such process became very slow to
the point of being a bottleneck due to the large amount of global
variables.
This commit precomputes, once and for all, the unique identifier of each
CSV and saves it in a `std::set`.
`BinaryFile::readRawValue` scans the segment list to identify which
segment contains a certain address. However, it was failing if the
target address was in `.bss`, i.e., the portion of a segment after
`p_filesz` but `before `p_memsz`.
This commit lets `BinaryFile::readRawValue` return 0 in that situation.
Fix for a situation where the fallthrough basic block of an instruction
calling a helper function is not in an executable segment and therefore
not created.
This commit fixes a huge performance issue due to performing a orphan
basic block cleanup every time `JumpTargetManager::peek` was called
instead of only when actual harvesting was required.
Now using the `root` function of the cloned module as a starting point
for the isolation process.
In this way we can ignore the old module, and in particular we can
drop the `ModuleCloningVMap`, a giant map that was used to keep the
match between old and new global objects and was used in the instruction
cloning phase.
Also changed the creation of the trampoline for the isolated function,
using a new basic block and later purging all the unreachable basic
blocks in the `root` function.
Moved the definition of `OBJ` before its first use.
Moved the definition of `CSV` outside the lifting scope, to avoid
erroneous behaviors when invoking the script with the `-s` option.
This commit uses SET, information about canonical values and labels to
detect if an indirect function call is targeting an external symbol.
The strings used for the name of external symbols are uniqued global
variables. This commit also uses this approach for the disassembly of
original instructions, which used to be metadata.
So far we've been tracking only base-relative relocations in an ad-hoc
fashion. This commit introduces a data structure that can describe the
most common relocations, including those for `.got`, `.got.plt`,
base-relative and `R_*_COPY`.
A label describes a range of the binary. A label can be generated from a
symbol (basically assigning a name to range of the binary) or from a
relocation, describing the content of a certain range.
This commit generates labels from symbols and relocations, including
MIPS implicit relocations.
This commit also introduces canonical values.
A register can have a canonical value, i.e., a value that register will
assume when the analyzed module is being run. This is typically useful
for the value of the global pointer, which is different from one module
to another but, within a module, is stable.
This commit registers the canonical value of `gp` (in MIPS), if
available.
`segments_count` provides a way for the runtime to know how many
executable segments the original program had. This is used to implement
the `is_executable` function.
While the `segment_boundaries` contained only the executable segments,
`segments_count` included non-executable segments too, leading to an
out-of-bound read which sometimes led to a spurious `Unknown PC` error.
While translating the code, it might happen that a basic block needs to
be splitted and the second part to be revisited. In such cases, the
second part is register for being "purged" at the next iteration.
Translation failed if we met such a basic block before purging. This
commit correctly handles such situations.
In certain cases we find more than one instruction storing the return
address to a register. In particular, this happens with a `bltzal`
instruction in MIPS, where the return address is stored both in `ra` and
`btarget`.
For now, do not consider these as actual function calls.
We used to check if the address associated to the `PT_DYNAMIC` program
header matched the one of the `.dynamic` section. However, we were not
recording it, which is required in case sections headers are
missing/corrupt.
In QEMU we should suppress the emission of the debug_insn
pseudo-instruction (which delimits the tiny code instructions
corresponding to an original input instruction) in case of a delay slot.
However, this was not happening due to a wrong `#ifdef`. Since this has
now been fixed in QEMU, this commit updates the results of the tests
accordingly.
`DebugAnnotationWriter` creates debug information for each instruction
in the generated LLVM IR module. Before this commit, it used to clobber
any debug information in any function, which lead to wrong debug
information on helper functions.
This commit ensures that debug information of helper functions are
untouched, so that they can be used while debugging.
Updating to LLVM 7 mainly involved the following steps:
* Upgrade APIs for folding ConstantExpr.
* Upgrade APIs for GraphTraits.
* Upgrade APIs for DominatorTreeBase.
* Upgrade APIs for BinaryFormat to parse ELFs.
* Fix the LLVM Linker to properly link the QEMU helpers.
* Disable the new optnone attribute even with optimization -O0. This is
necessary to allow SROA to do its job properly.
* Upgrade APIs to delete Instructions.
* Properly cleaning up orphaned metadata still referring to Instructions
that have been destroyed. Recent versions of LLVM are more strict in
this respect, and will assert when compiled in debug.
* Avoid using LLVM `getGlobalContext` which has been removed from newer
versions of LLVM.
* Upgrade tests to use the new APIs.
* Upgrade APIs for instruction iterators and reverse iterators.
This commit reimplements the (conditional) reaching definitions passes
as an instance of a monotone framework.
The `ConditionNumberingPass` has also been reworked in the way it
exposes its results, but it's otherwise unchanged.
A proper unit testing framework is also available to ensure everything
works as supposed to.
In a `MonotoneFramework` it is sometimes necessary to change the
information propagated on a branch w.r.t. another branch.
This commit introduces the `handleEdge` function that allows
`MonotoneFramework` implementors to modify the `LatticeElement` produced
by `transfer`.
Through `JumpTargetManager::setCFGForm` the `root` function CFG can be
changed so that the `dispatcher` is minimized, i.e., it jumps only to
those basic blocks that would be otherwise unreachable. This allows us
to perform more accurate and simpler analyses.
To bring the function in this state we used to check if there was at
least a non-dispatcher predecessor, however this did not work with loops
reachable only from the dispatcher, since they had a predecessor, but
that didn't mean it was reachable from the entry.
This commit fixes the problem by navigating the CFG in reverse-post
order, registering all the reachable blocks and then restoring the edge
from the dispatcher to those that are not reachable.
Additionally:
* Basic blocks with no predecessors are now purged before
`JumpTargetManager::harvest`.
* The `CFGForm` enum is now a namespace.
Alessandro Di Federico