This commit greatly improves the performance by ensuring that, when
computing the set of nodes we want to consider for AVI, we do not
traverse the dispatcher.
Doing so, means including *a lot* of irrelevant nodes and wasting a lot
of computation, since the CFG usually is not influenced by stuff
happening before an indirect jump.
In at least a situation the speedup is in the order of 20x, however this
depends on the size of the binary, since traversing the dispatcher means
including all the binary in the computations (as opposed to just the set
of blocks involved in the dataflow to compute a certain expression).
Sorting the BasicBlocks on which DisjointRanges works is detrimental for
performance. Using a random order takes less time. This is due to the
fact that the number of BasicBlocks to analyze is significantly smaller
than the whole list of BasicBlocks.
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.
* 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
Handle `ConstantPointerNull` explicitly in Advanced Value Info, instead
of trying to obtain the analysis result for its operand (which is by
design a `nullptr`).
* 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.
Alessandro Di Federico