* 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.
In OSRA, when producing constraints associated to a `ICmpInst`
associated to a load instruction, consider also all of its reaching
definitions.
Moreover, when propagating constraints due to a `Br` instruction, look
for loads which might be affected by the constraints being propagated,
and, if necessary, update them.
Three new passes have been introduced:
* `ReachingDefinitionsPass`: classical reaching definitions analysis
working on load/stores with the main difference that a load without a
definition behaves similarly to a definition and that we ignore
certain basic blocks (i.e., the dispatcher).
* `ConditionNumberingPass`: goes through all the branch instructions to
check if some of them use an equivalent condition, this is
particularly useful to understand that consecutive ARM instructions
using the same predicate are working on the same condition.
* `ConditionalReachingDefinitionsPass`: identical to
`ReachingDefinitionsPass` but uses information from
`ConditionNumberingPass` to stop certain definitions from reaching
certain loads.
The first and the last analyses have `Reached*` variants which expose
information from the point of view of the definintion instead of from
the point of view of the load.
Constant OSR are now represented through an OSR such as
[0 + 1 * x with x = (*, c, c)]. Since equality doesn't hold any
signedness information we introduce a new signedness type (available
only in `BoundedValue`), `AnySignedness`, which is similar to
`UnknownSignedness` but does not trigger `isUninitialized() == true`.
In `BVMap` we also introduce the concept of "forced" constraint, i.e. a
constraint that is fixed, cannot be changed or update. Constant stores
will produce this type of constraints.
* When generating the code for setting a label or jumping to it, give
sensible names to the new basic blocks.
* Keep track of the last seen PC during translation so it can be used to
obtain a sensible name for the basic block.
* Let `JumpTargetManager::getBlockAt` set a proper name to the basic
block before returning, if it doesn't already have one.
This commit introduces the `getName` function, which, given a
BasicBlock, an Instruction or a Value, outputs a sensible name. In
particular instructions are now identified as [basic block]:[instruction
index].
`getName` is now used in the various `describe` methods in OSRA.
`forceFallthroughAfterHelper` handles the situation where there isn't a
PC-store between a call to an helper and to `exitTB`, in this case, we
force a branch to the fallthrough PC.
This commit also simplifies `InstructionTranslator::translateCall`:
remove jump to the dispatcher after a call to an helper in case the PC
was saved and it has changed. We don't really need to do this, QEMU will
generate a call to `exitTB` has necessary or
`forceFallthroughAfterHelper` will take care of the thing.
* The function now can take a `std::set` of basic blocks to ignore.
* The visitor function has now several options on how to proceed, and
can express them through its return value.
* A serious bug in the implementation was also fixed.
Sometimes QEMU writes to register that are never used afterwards,
typically the `cmp` instruction sets several CPU flags which might be
ignored.
This becomes a problem when comparison are performed since they affect
the signedness of a BoundedValue. With this patch, we ignore their
effect if we can prove it's a dead store.
With this patch we basically handle a load as a sort of phi-node, since
we keep track of all the store/loads reaching a certain load, along with
their OSR, so that we can come up with smarter merging policies and
obtain more precise information.
This commit also introduce a change that leads to consider loads as
stores during propagation. This heavily simplifies the store
propagation logic by considering load instruction as aliasing, and by,
consequently, propagating load (along with stores). This removes
completely the need for the concept of "conflicts".
This pass helps us handling instructions like ARM's `blt` which compute
the result of the comparison by bit-fiddling with the bit sign of the
operands of a subtraction.
The idea is to have a series of known boolean expressions using `a`, `b'
and `c` as variables (e.g. the boolean expression corresponding to
"signed greater than") and compare their truth table against the one
being analyzed. In case of match, the comparison can be simplified.
Introduce the `MemoryAccess` class which represents the source of a
`LoadInst` or the destination of a `StoreInst` for which we want to
propagate an OSR.
This patch handles more elegantly the propagation and introduces support
for propagating OSRs through register + offset memory accesses, in
particular stack pointer- (or base pointer-)relative memory accesses,
which are common in unoptimized code and that led to miss some cases
that we otherwise handle correctly.
`TranslateDirectBranchesPass` now optionally depends on `SETPass`. This
allows us to reuse information obtained by SET and OSRA to pin potential
jump targets we detected to an `exitTB` call. In practice this means
that before a call to `exitTB` a conditional branch or a switch is
present to check if the destination of the jump is one of those we
expected, and if not, go to the dispatcher if the estimated destinations
were marked as approximate, or fail otherwise. Since this feature is
currently WIP, we never fail, we always go the dispatcher instead.
Since the amount of successors might grow during the iterative discovery
process, record the amount of successors as a `exitTB` argument.
* New `exitTB` argument: estimated number of successors.
* Move the code of the old implementation of the pass to the
`pinConstantStore` function.
* Update routine for cleanup of post-exitTB instructions.
* `findNextExitTB`: more reliable implementation of the search for the
next call to `exitTB`.
* Keep a reference to the basic block handling the failure of the
dispatcher's switch, so we can use it to report failure of our jump
target estimation.
* `handleInstructionWithOSRA`: isolate usage of OSRA and increase its
priority in SET.
* Let SET expose, for each store to the PC (i.e. a jump), the
(approximate or exact) list of destination it can have.
* Extend the OperationsStack to explicitly track all the possible values
that can be assumed by the instruction currently being analyzed. Note
that before this patch we were only tracking possible jump targets by
feeding them to JTM. The tracked values can be approximate or not,
depending on the situation, and OperationsStack keeps track of this.
* Clean up some leftovers from the isolation of `SET` from `SETPass`.
The current modeling of constant OSRs prevent their merging on basic
blocks. This was due to the fact they had no `BoundedValue`
associated. This patch fixes this by representing them as:
[120 + 0 * x, with x = (null, ?)]
instead of:
[120 + 0 * x, with x = null]
Alessandro Di Federico