`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.
Reduce the amount of "\n" and do not print again the original
instruction unless the last instruction that had a decoration, if any,
was associated with a different instruction.
Now `CodeGenerator::translate`, `CodeGenerator::translateCall` and
`CodeGenerator::newInstruction` all return
`CodeGenerator::TranslationResult` which covers all the possible results
that the caller needs to handle such abort, stop translation, force a
new basic block or simply proceed.
This patch also prevents reading a PTC temporary that has never been
written (typically due to a mistranslation) by emitting an abort.
* Import OSRA
* Improve the SET (aka `JumpTargetFromConstants`) by introducing the
`OperationsStack` class.
* Review `harvest` logic
* Allow to disable OSRA (along with the sumjump heuristic)
* Take the core of `getNextPC` out of it and move it to `getPC`, a
function returning both the current and the next PC. Also, fix a bug
when reaching the beginning of a basic block.
* Detect "reliable" jump targets: a "reliable" jump target is a jump
target obtained from a store to a PC but it's not a fallthrough jump.
`unknownPC` is an extern function we expect to be linked to the output
which is called when we have to crash due to an unexpected jump target.
* Remove unused references to register variables, now only need the
stack pointer
* Fix bug in how the auxiliary values were pushed on the stack.
* Push 0 HW_CAPs
* Implement some glib's functions
Since one of our requirements is to have all the accesses to the CPU
state explicit, we used to modify the helper functions depending on the
parameters used to call them. This was fine when we were supporting a
reduced set of helpers, but now this is not acceptable since the calling
code can call helpers in different ways. We circumvent the problem by
creating a distinct function specialization for call.
This patch implements `VariableManager::storeToCPUStateOffset` and
`VariableManager::loadFromCPUStateOffset`, which handle in a single
point all the accesses by offset to the CPU state.
* `getTypeAtOffset`: introduce a feature to easily debug how we compute
which field is at a specified offset in the CPU state (`--debug
type-at-offset`).
* Let `getTypeAtOffset` and its wrappers return the offset inside a
field of the CPU state (useful when accessing the third byte of an
integer).
* Use a dedicated class for the `CorrectCPUStateUsage` worklist
Alessandro Di Federico