When we compare StackAnalysis test results, the order in which things
appear in the JSON is relevant. However, the output was
non-deterministic due to a `std::map` using a pointer as key.
This commit improves the situation by sorting the elements by name
before dumping them in JSON.
This commit drops support for running StackAnalysis without ABI
analysis. This has been broken for quite some time and a source of slow
downs in (badly) crafted optimization pipelines.
We used to mark call to noreturn functions as killers, but this is not
correct.
Note that this is a temporary solution, we need to explicitly handle
such situations.
Generated code now either jumps to `anypc` or `unexpectedpc`. The latter
one is to be considered a safety measure and will be populated with an
unreachable instruction on the decompilation pipeline.
Changes include:
- `getFunctionCall` has been moved in IRHelpers.h
- `getFallthrough` and `getFunctionCallCallee`
have been simplified and added in IRHelpers.h (their old versions
have been removed respectively from FCI.h and revng.h)
- `FCI::getCall` and `FCI::isCall` have been removed
due to redundancy with `getFunctionCall`.
After combining two AS objects, removing an ASOContent in the cleanup
phase may lead to a mismatch in the CSVs promoted to function argument,
with some registers actually being used. In most cases, this results in
promoting only one or few alive registers as function argument.
We used to accidentaly call `resetCacheMustHit` on the just popped
element of the set, resulting in an out-of-bounds access within the
container.
This bug has been spotted thanks to AddressSanitizer.
We used to detect callee-saved registers only by checking if their final
value was identical to the initial one. However, the need for a more
precise heuristic emerged: we now also check if at least on of the stack
slots contains that same value.
This commit fixes a subtle bug that was preventing us from correctly
considering the effects of function calls during ABI analysis.
Specifically, when merging information from the call site to the caller,
in case the caller did not provide any information about a certain
slots, we used the `DefaultMap::Default` field, which is the correct
thing to do, except for the fact that, in two methods, the `Default`
field was being updated to early.
This basically had the effect of not considering arguments of function
calls as used, e.g., in URAOF.
Under certain conditions, we ended up having code in the ABI IR which
was not reachable. This was due to the fact that a certain instruction
was initially detected as an indirect call, triggering inclusion in the
function of the fallthrough code, and then as a return, which has no
successors within the function.
This commit simply prunes the ABI IR in the finalization method.
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.
Alessandro Di Federico