The previous logic for detection of incompatible PHINodes was broken in
various different ways.
1. `return true` and `return false` were flipped, so it effectively did
the opposite of what it was expected to do
2. `std::numeri_limits<Value *>::max()` yielded 0, breaking the lookup.
This commit fixes the condition for incompatible PHINodes and adds a lot
of logging.
Before this commit, the code never put in the same group two PHINodes if
one of them had a non-phi User. This condition was wrong and was
unnecessarily preventing valig PHINodes to be put in the same group.
This caused the generation of a lot more local variables than necessary.
Before this commit we were replacing all uses of a PHI that were not
used by other PHIs with llvm::UndefValue. That was wrong. The
replacement is valid only if the use is used by a PHINode that is in the
same group. This commit fixes the condition for such a replacement to
take place.
This commit introduces `FixPointerSize`, a pipe changing the
`DataLayout` of module in order to have a pointer size identical to the
one of `targetABI()`.
The pipe also performs safety checks to ensure this does not corrupt
semantics.
Several components in both pipeline YAMLs are slated for removal.
Prepend a legacy prefix to their names, and to the matching c++ code, so
they are clearly distinguished from the new Clift-based pipeline until
they are dropped.
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).
Replace the hoist-struct-phis pass with a split-struct-phis pass that
breaks struct PHI nodes into per-field PHIs instead of moving them
out, and update both pipelines to use the new name.
Replace the stable_sort that ordered (block, value) entries by raw
BasicBlock* address in getIncomingUsesOfValuesFromBlocks with a
MapVector that groups entries by block in first-encountered
insertion order, and add a per-block stable_sort by use count
(descending). Same-block contiguity is now structural rather than
enforced by a sort, and the order in which the split basic blocks
are created and appended to the function no longer depends on
pointer values that vary across runs. The within-block ordering,
the use-count tie-breaking, and the rest of the edge-splitting
algorithm are preserved.
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.
* Discover deferrable allocas in a separate pass before applying changes
in order to avoid double work.
* Defer allocas to just before the first user or the terminator, if no
user exists in the target block.
* Move allocas when the target block is the same as the original block.
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.
Pietro Fezzardi