Make cannotBePointer recurse through an Add when both of its
operands cannot be pointers. This lets canDisambiguatePointerOperand
identify the only viable base pointer of an outer Add even when the
offset side is itself an Add (or a deeper tree of Adds) whose leaves
are all clearly-non-pointer values, e.g.
%offset = add i64 (%a*%b), (%c*%d)
%result = add i64 %arg, %offset
Two unit tests cover the simple two-mul case and a deeper
four-mul binary-tree variant.
The ModuleSlotTracker is owned by a new function-level
ModuleSlotTrackerAnalysis whose Result holds the MST through a
unique_ptr (MST is neither copyable nor movable, but the FAM
cache requires a movable Result). Its run method calls
incorporateFunction on the function.
AvailableExpressionsAnalysis and InstructionToSerializePicker
fetch the MST via FAM.getResult<ModuleSlotTrackerAnalysis>(F) and
forward it down to AvailableExpressionsResult and the monotone
framework, so all dumpToString calls on the logging path share
the same slot-numbering cache.
Drop the workaround that skipped recursion into a Use whose User
was a CallInst with that Use as an arg operand. The original
motivation no longer holds with the rest of the recent changes,
and the workaround was suppressing valid serialisation
opportunities at call sites.
Remove the workaround that suppressed the redundant
self-assignment that the pass now occasionally introduces in
non-legacy mode.
The remaining self-assignments are not bugs but sub-optimal C
generation, so we just disable the -Wself-assign warning in the
tests.
The sub-optimal code generation comes from passes that emit local
variables (allocas) before conversion to Clift, e.g. STS and
ExitSSA (with more planned). Each of these passes generates local
variables independently and they don't know about each other; the
order between them might also be swapped in the future. The only
clean fix is to unify them into a single transformation pass that
takes the results of multiple analyses (in the LLVM sense) and
emits local variables once. We have plans to do that, and when
it's done the warning can be re-enabled.
Hoist the "use already picked in a previous iteration" early-out
to the very start of the per-use loop in
pickInstructionForMemoryRead, so that the rest of the body never
runs for uses that are going to be replaced anyway. The check
itself is unchanged.
Introduce a new canonicalisation pass that forces a small set of
exponential-dataflow-prone instructions (SelectInst plus the FShl
and FShr intrinsic patterns) to be stored into a dedicated local
variable. Without this, expanding their value into C expressions
during decompilation can blow up into exponential path enumeration
on real binaries.
This is a temporary workaround. A more principled split of
pathological dataflows is planned and will replace this pass.
If an instruction picked for serialisation has zero uses, skip
emitting an alloca/copy pair for it. The Clifter recognises a
zero-use instruction as a statement and turns it into an
ExpressionStatement in place, preserving the ordering as if the
local variable had been emitted, but without the cost of a real
local variable. The legacy mode keeps the previous behaviour.
When a use of `I` is going to be replaced by a copy from
SelectedAssign and `User` does not write memory, there is no need
to recur on uses of `User`: those uses will be reading from
SelectedAssign's location, so the original memory read no longer
flows through them.
This avoids a class of redundant explorations and the spurious
serialisations they used to cause.
The "skip over the Assign operand" workaround is only needed in
legacy mode, where assignments are calls to opaque functions that
the rest of the pass cannot reason about. Gate it on `IsLegacy`
so that the non-legacy code path treats the pointer operand of a
StoreInst as a regular use, which is semantic-preserving and
unblocks downstream simplifications.
Add a canonicalisation pass that rewrites extractvalue from a
pointer-returning struct as an i8 GEP plus a load. Together with
ArithmeticToGEP this lets later passes consume the result through
the same GEP-based interface they use for ordinary memory accesses.
Introduce the ArithmeticToGEP canonicalisation pass. It detects
pointers (LLVM-typed pointer values, model pointers flagged by the
"revng.pointers" metadata, and pointer-tagged extract values) and
rewrites integer arithmetic computed on top of them as i8 GEPs,
followed by a ptrtoint when the original use needs an integer.
For each obvious pointer the pass also walks backwards through Add
chains and disambiguates the pointer operand of each Add when the
other operand cannot be a pointer, so the rewrite extends to integer
arithmetic that only later flows into a pointer use.
Drop the special case in serializeToLocalVariable that, for
struct-typed values, allocated `[N x i8]` of the struct's data-layout
size instead of an alloca of the struct type itself. The Clifter now
handles arbitrary alloca element types directly, so we can just use
the value's LLVM type.
In non-legacy mode, replace the hand-written aliasing checks in
AEMFP::mayClobber with the answer of LLVM's AAManager, queried
through an AliasAnalysis * threaded into the framework. Legacy mode
keeps its previous logic, since it operates on calls to opaque
copy/assign functions that LLVM AA cannot reason about.
The pass now registers and consumes AAManager via the
FunctionAnalysisManager, with the usual GlobalsAA / module-proxy
cross-registration so that local AA can fall back to GlobalsAA
without crashing.
Make AEMFP::mayClobber and AEMFP::applyTransferFunctionImpl proper
members instead of free functions taking the framework state as a
parameter. This removes a fair amount of boilerplate around passing
the AliasAnalysis pointer along, and keeps all the logic that
operates on the lattice in one place.
No behavioural change.
Convert SwitchToStatements to a new-PassManager FunctionPass and
introduce two function-level analyses,
AvailableExpressionsAnalysis and InstructionToSerializePicker,
backed by AnalysisInfoMixin. The non-legacy production entry point
now sets up an FAM, registers GlobalsAA proxies and runs the pass
through a FunctionPassManager; the legacy entry point keeps using
the legacy FunctionPass wrapper.
The pass also exposes a registerCallbacks hook so the upcoming unit
tests can load it from `revng opt -passes=switch-to-statements-test`
without dragging the model along.
Replace the loose ResultMap typedef with the
MFP::MFIResultMap<AEMFP<IsLegacy>> alias and keep the maximal fixed
point result inside AvailableExpressionsResult, so callers of
AEResult can fetch availability-at-a-point without reaching into a
separate map.
This is a structural step toward turning available-expressions
discovery into a real new-PassManager analysis.
Rename the AvailableExpressionsAnalysis class to
AvailableExpressionsMonotoneFramework (with the AEMFP alias)
because it does not satisfy the LLVM AnalysisInfoMixin contract;
keeping the "Analysis" name would clash with the actual
new-PassManager analysis introduced in a follow-up commit.
Replace the home-grown hasSideEffects, mayHaveSideEffects,
mayWriteToMemory and mayReadMemory helpers (in
DecompilationHelpers.h) with the equivalent predicates from
llvm::Instruction. The legacy code paths still need a few extra
checks, so the templated wrappers in SwitchToStatements.cpp
specialise on IsLegacy and fall back to the LLVM predicates in
non-legacy mode.
This removes the now-unused helpers from DecompilationHelpers.h.
Add a set of templated helpers for getting the pointer/value
operands and operand-uses of copy and assign instructions. The
helpers exist because the legacy mode represents copies and
assignments as calls to opaque functions while the non-legacy mode
uses LoadInst and StoreInst directly: with these helpers the rest
of the pass can be written once and parameterised on IsLegacy.
The helpers are pure additions; nothing uses them yet.
Rename the legacy FunctionPass wrapper class from
SwitchToStatements to SwitchToStatementsPass to free the
SwitchToStatements name for the upcoming new-PassManager pass that
will replace it.
Reorganise LocalVariableBuilder so that the legacy and non-legacy
code paths are separated into two specialisations, and so that the
non-legacy specialisation does not need a model::Binary to operate.
This is a prerequisite for using LocalVariableBuilder from passes
that do not know about the model, e.g. unit tests for the new-PM
SwitchToStatements and the upcoming non-legacy decompilation
pipeline.
Before this commit, the insertion point for load instructions was being
set before a PHINode, causing the IR to temporarily fail verification.
The effect of this logic bug did not propagate outside the pass, because
all PHINodes are removed at the end of the pass, but it made debugging
harder.
This commit fixes the problem by always setting the insert point after
all the PHINodes.
This commit drops libptc in favor of its new form libtcg.
It brings several improvements, among which:
* The QEMU version we work on has been upgraded.
* CPUStateAccessAnalysis has been reimplemented in a way that makes it
easier to debug and solves some limitations (e.g., tracking leaking
pointers).
* Identification of pieces of the CPU state that are read by each helper
and fixing access to the CPU state is now performed at build-time.
* We no longer mmap the code we need to translate, dropping all the
issues related to code that needed to be mapped where something is
already present.
* We now have two distinct flavors of helper modules: the full one and
the "slim" one. The latter contains the definition only of functions
we intend to inline. It is used in most of the pipeline, a good thing
since we spend less time optimizing code we don't really care about.
The full module is only used on the re-compilation branch of the
pipeline.
* We no longer split the `cpu_loop` function.
* We change MetaAddress to rely on architectures from `model::` as
opposed to the LLVM ones.
* We no longer attach debug info to LLVM IR containing the original
assembly.
* We now verify that the lifted code only contains code we expect.
This forces all such instructions to get their value stored into a local
variable in SwitchToStatements.
The reason for doing this is that they often contribute to the formation
of pathological dataflows, causing exponential path explosion when
expanded into C expressions during decompilation.
Serializing their value into a dedicated local variable breaks such an
exponential path explosion.
This is a temporary workaround, that we've already put in place for
SelectInst too, and that will be replaced in the future by a more
principled approach for splitting pathological dataflows that lead to
exponential path esplosion.
* Make the following private headers public:
* Lift/CPUStateAccessAnalysisPass.h
* Lift/CSVOffsets.h
* Lift/PTCDump.h
* Lift/VariableManager.h
* Move from revngSupport to revngLift:
* IRAnnotators.{h,cpp}
* SelfReferencingDbgAnnotationWriter.{h,cpp}
* Move from revngSupport to revngModel:
* FunctionTags.{h,cpp}
* ProgramCounterHandler.{h,cpp}
* Move from revngSupport to revngRecompile:
* OriginalAssemblyAnnotationWriter.{h,cpp}
This commit fixes a bug in the `noAlias` function, that failed to detect
two aliasing accesses when the second was writeOnly (so it did not read
memory).
That causes the transfer function of the Available Expression analysis
in SwitchToStatements to wrongly see some expressions as available,
because of the undetected aliasing write that would otherwise overwrite
the available expression.
Lauri Vasama