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]
The iteartive basic block discovery process has been reorganized to
minimize the amount of passes we run (in particular SROA, constant
propagation and early CSE) and to proceed until we don't "pin" any new
branch instruction, and not only until we're not able to discover any
new basic block.
The logging output has also been reworked to be more informative.
* Isolate the SET algorithm from the SETPass
* Isolate the processing of an instruction in a function to be able to
use returns to easily signal if we were able to handle the instruction
or if we gave up
* Add some documentation
SET needs to create clones of instructions, which are not inserted in
any basic block, therefore we have to manually handle their
lifetime. This patch delegates this role to the `OperationsStack`: when
an element is being popped from the stack the OS checks if it belongs to
a basic block and if it doesn't, it deletes it.
Checking if a range of addresses belong to a segment should be
implemented by checking if the start and end address belong to the
address, the `Start <= Address && Address + Size < End` approach leads
to subtle errors when `Address` is close to the maximum representable
value due to an overflow.
Alessandro Di Federico