Unlike the previous iteration of `MetaAddress`, which tried to stuff all
the parts of `MetaAddress` within the existing `PC` CSV, this
implementation adds a set of new CSVs (or marks some existing ones as) to
represent the four portions of the current PC's `MetaAddress`.
* Introduce `ProgramCounterHandler`: a class responsible to maintain the
PC-related CSVs. This class is also used to manipulate the new
dispatcher.
* `AdvancedValueInfo`: update for new MetaAddress.
* External jump handler: do not clobber registers.
When introducing support for dynamic binaries, we didn't realize that
in x86-64 we were clobbering `r11`. To avoid this, we have to jump to
an address stored in memory. However, due to the new `MetaAddress`,
obtaining a *jumpable* address from the PC-related CSVs might require
some computations (and it does in ARM). Therefore, we introduce a new
global variable, `jumpablepc`, whose only role is to contain the
jumpable version of the program counter and then be the target of the
memory-indirect jump instruction.
* Labels care only about absolute addresses.
* CSAA: mark call site, even if no accesses.
`MetaAddress` replaces all the `uint64_t` used to represent a virtual
address. Its main features are:
* It has a non-zero representation of invalid addresses.
* It supports tags to represent code that has different interpretations but
resides at the same address in memory (namely ARM vs Thumb).
* Arithmetic operations cannot overflow.
* It supports epochs, a way we intend to employ to handle self-modifying code
(i.e., different code at the same address at different times).
* It supports "address spaces", which enable handling architectures with
multiple address spaces.
* It fits in two 64-bit registers.
* Drop unused argument names from function prototypes
* Make `static` some methods
* Disable some copy constructors
* Fix casing of Doxygen `\file` directives
* Add some casts to make the compiler happy
* Initialize `hasRelocationAddend` for AArch64
* Use references in range-for where possible
* Drop default for `switch` statements covering all the entries of an `enum`
* Make some global variables `static`
* Drop dead functions
LLVM 9 drops the `TerminatorInst` class. This commit replaces it with
`Instruction` where possible and asserts
`Instruction::isTerminator()`. It also switches from
`TerminatorInst::successors` to `successors(TerminatorInst *)`.
* Introduce `ShrinkInstructionOperandsPass`: a transformation shrinking
operands and the results of instructions if they are
zero/sign-extended immediately before and after the instruction.
* Introduce `ConstantRangeSet`: similar to `ConstantRange` but allows
disjoint ranges.
* Introduce `MaterializedValue`: a class that can represent a constant
value or a symbol plus offset pair.
* Introduce `DropHelperCallsPass`: a transformation removing calls to
helpers and replacing them with a function call reading the CSVs that
the helper reads and writing the CSVs that the helper writes
(according to CSAA).
* Introduce `DropRangeMetadataPass`: a transformation dropping the
`range` metadata, which, in certain situations, lowers the quality of
the results provided by `LazyValueInfo`.
* Introduce `AdvancedValueInfo`: an analysis exploiting results of
`LazyValueInfo` but collecting them as `ConstantRangeSet` with a
monotone framework. It produces `MaterializedValue`.
* Anticipate linking of helpers: `AVI` requires `CSAA`, which requires
helper functions to be linked in.
* Drop `--no-link`.
* Force x86-64 `DataLayout`.
* Reorganize harvesting to either collect simple literals or go with
(incremental) `AVI`.
* Drop `SET`, `OSRA`, the reaching definition analysis, the
`SimplifyComparisonsPass` and all the sumjump-related code: e now
clone `root`, optimize it and analyze it with `AVI`.
* Temporarily drop the `NoReturnAnalysis`.
* Link `libLLVMInstCombine`, `libLLVMCodeGen` and `libLLVMPasses`.
* Introduce tests for `AdvancedValueInfo`,
`ShrinkInstructionOperandsPass` and `ConstantRangeSet`.
* Fix test results.
* Add `llvm.bswap.i64` and `@pc` to the LLVM template module for unit
tests.
Any stack pointer value greater than or equal to the original one used
to be OK for stack analysis to recognize an instruction as a
return. This commit changes this policy by collecting the value of the
stack pointer on all the return points and, at the end, elect a final
stack pointer value. All non-compliant returns are marked a
`BranchType::BrokenReturn`. The function is now considered fake only if
all the return instructions agree on a specific value of the stack
pointer, and it's lower than the original one.
* Drop `BranchType::IndirectTail`.
* `s/BranchType::FunctionSummary/BranchType::RegularFunction/`.
A series of algorithms working on `llvm::GraphTraits`.
* `nodesBetween` computes the set of nodes on all the paths from a node
A to B.
* Factor out code to iterate over infinite loops into
`exitless_scc_range`.
* Introduce unit tests.
* Introduce `KeyContainer::compare` and drop the `getKey` method.
* Let users of ZipMapIterator specify a trait class instead of using the
default one.
* `GeneratedCodeBasicInfo::getCSVUsedByHelperCall` and
`GeneratedCodeBasicInfo::extractCSVs`: make the call argument an
`Instruction`.
* Introduce `blockByName`
* Introduce `getUniqueUser`.
* Fix linking issues.
Register marked as explicitly callee saved in a function used to be
marked as No both for the current function and all of its function
calls. However, the latter action is not accurate.
In certain locations we were using a `std::vector`, taking a reference
to it, adding elements and ending up in a reference invalidation issue.
This commit replaces those `std::vectors` with `std::deque` which do not
present this issue.
The ABI analysis used to ignore actions happening in CFG-level infinite
loops due to the fact that they had no exists. This commits detects
infinite loops and marks certain nodes as exits.
This commit introduces the `enforce-abi` pass, which consumes the
information provided by the ABI analysis and enforces them in the
isolated functions adding actual arguments.
This commit also rewrites the logic of `ResultsPool::finalize` and
changes the semantic of `Yes` statements on arguments to `YesOrDead`.
`ZipMapIterator` allows you to iterate in parallel over two
`std::map`-like containers.
In the ABI analysis, this allows us to be much more efficient. In
practice, if we have two maps with M and N elements, we pass from
performing N*log(N) + M*log(M) queries to the size of the union of the
set of keys of the two maps.
In the stack analysis, we used to consider helper functions as indirect
calls. However, the `CPUStateAccessAnalysis` provides us accurate
information about what an helper function does.
This commit transforms calls to helper functions in a series of ABI IR
instructions reading all the input registers of the helper functions and
a series of instructions writing the output registers.
Note that, while this is a serious improvement over considering them
indirect function calls, it's still suboptimal since
`CPUStateAccessAnalysis` doesn't provide us information as fine-grained
as the ABI analysis.
We used to save the type of a block in the `revng.block.type` metadata
as a number. This commit serializes it as a string.
In order to do this, the `BlockType` enum has been promoted to a
namespace with the usual `getName` and `fromName` functions.
In the intraprocedural analysis of the stack analysis we implemented the
transfer function of the `Trunc` instruction as the identity function
(just as `PtrToInt` or `ZExt`). However this is not safe since `Trunc`
loses information. This lead to incorrect results in the ABI analysis.
All the definitions of `greaterThan` were `!lowerThanOrEqual`, and all
the uses were implicitly assuming this semantic.
However, this was confusing because in a Lattice the ordering is not
total, hence `!lowerThanOrEqual` is not equivalent to `greaterThan`.
This commit drops the `greaterThan` method altogether to avoid
confusion.
In most cases, a user of MonotoneFramework does not need a
interprocedural analysis, nor an analysis whose results on
terminal labels have to be aggregated in a FinalResults.
DefaultInterrupt<LatticeElement> is designed exactly for those
cases, and is hence used as default template parameter for
MonotoneFramework.
The MonotoneFrameworkSet class had two sets of methods, one for handling
set operations on it, the other handling lattice ordering.
It also silently assumed that the lattice combine operation was the set
union, which is not true in general.
This commit decouples the set operations from the lattice operations.
This allows to provide two separate implementations of
IntersectionMonotoneSet (for which the compbine operation is the set
intersection) and UnionMonotoneSet (for which the combine operation is
the set union).
This commit drops the old FunctionBoundariesDetectionPass and introduces
a new one based on the results provided by the StackAnalysis. A very
similar pass, the ABIDetectionPass, is now available to offer the
results of the ABI analysis too.
These two new passes are a thin shim depending on the appropriate
version of the StackAnalysis (with or withour ABI anlysis) and simply
call `serializeMetadata`, which decorates the LLVM IR with the requested
information.
In addition to drop the old analysis, this commit also isolates the
function boundaries detection pass from `revamb` making it available as
a library only.
This commit does the following:
* It drops `revamb-dump` and transforms all the passes it featured in
passes that can be used directly from `opt`.
* It rename `revamb` to `revng-lift`.
* It introduces a script called `revng` which acts as a driver for the
whole rev.ng project. It replaces `translate`, `revcc`,
`csv-to-ld-options` and `revamb-dump`, since it offers an `opt`
subcommand which allows to easily invoke all the analysis passes.
* It makes the project a CMake package that can be easily used
externally.
* It allows to easily create libraries of analysis to use through
`revng-opt`.
This commit lets the reaching definitions analysis employ results from
the stack analysis to propagate definitions across functions
calls. Specifically, the stack analysis provides a list of registers
that might be clobbered by the callee: definitions concerning those are
not propagated, all the others are propagated.
This change is key to detect jump tables whose address has been
materialized *before* a function call. A test for such situation has
been introduced.
To make this work, the RDA now works over the CFG provided by the
function identification analysis.
Alessandro Di Federico