Three closely-coupled changes that have to land together to keep
every caller compiling:
- Introduce a per-instance ExtraState recording surface (with a
NoExtraState default) and thread it through applyTransferFunction.
- Replace getMaximalFixedPoint's positional arg list with a single
MFPConfiguration struct, so callers spell out only the fields they
need.
- Replace the EntryLabels pointer with an Entry/All/vector* variant
so callers can ask for the graph entry, every node, or a custom
list without juggling extra arguments.
Update every existing caller for the new signatures and switch
Liveness::GraphType to a plain Function* (with the inverse
GraphTraits selected at call sites).
After we drop legacy mode, the only user of LocalVariableBuilder will be
SegregateStackAccesses. This is possible thanks to the fact that
dropping the legacy mode will demistify local variables and turn them
into plain allocas accessed via loads/stores. This will end the need for
a centralized place to deal with local variable creation, that is caused
by the various ad-hoc manipulations we've been doing for a long time in
legacy mode.
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.
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.
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.
Before this commit, initModelTypes always looked at uses of each
instructions to see if its knowledge of the instruction's model type
could be improved.
This is useful in some cases, but it's detrimental when building model
casts, because this requires to see the exact type computed for an
instruction.
This commit introduces a new function initModeTypesConsideringUses,
which works like old initModelTypes, considering uses.
In this way we can make sure that uses are considered when necessary,
like when computing types to build new local variables, and ignored when
necessary, e.g. when building model casts.
Before this commit, SwitchToStatement, in Legacy mode, was evaluating
the injection of Copy instruction an all uses at the same time, while
it's perfectly feasible, depending on how the surrounding IR is shaped,
that calls to Copy are only necessary on some of the uses.
This commit fixes, that evaluating the emission of a call to Copy on
each Use separately.
This commit changes the prototype of getCopeType, so that it now takes 2
arguments.
1. The llvm::Type returned by the Copy function. This can be any scalar
llvm::Type.
2. The llvm::type of the argument representing the reference to the
value being copied. This should be a pointer-sized integer, where
pointer-sized means with the same size of a pointer in the
architecture in the input binary.
The second argument is not strictly necessary for now, because the whole
decompilation framework expects a binary with a single architecture,
hence a well defined unambiguous pointer size.
This will be used fully only when we start supporting multiple binaries.
Whenever that happens, if we haven't already fully dropped the Copy
helper function we will have to update the associated
OpaqueFunctionsPool to a type pair as key: the return type and the type
of the argument.
Before this commit, the AvailableExpressionAnalysis used by
SwitchToStatements did not take into account the full set of custom
opcodes that allocate local variables.
In particular, if only checked FunctionTags::LocalVariable, and not the
larger set marked with the tag FunctionTags::AllocatesLocalVariable,
which includes revng_stack_frame and revng_call_stack_arguments.
This caused all the reasoning on aliasing that involved the stack to be
broken.
This commit fixes the problem by properly using the
FunctionTags::AllocatesLocalVariable to reason about aliasing.
Before this commit, the InstructionToSerializePicker had a wrong bailout
condition, that caused to never pick for serialization memory reads.
This was wrong and caused semantic bugs, due to the instruction
performing the memory read not being serialized into a new variable.
Alessandro Di Federico