Add three more unit tests that mirror the previous "with_alloca"
variants but where the store of the extra argument %val into the
pre-existing alloca happens BEFORE the call instead of after it. The
expected number of NEW allocas after the pass is the same as in the
corresponding store-after-call variant: the position of the store
relative to the call does not change the picker's decision.
Add three more unit tests, one for each of the three call patterns
introduced in the previous commit. Each test takes an extra i64
argument %val, has an alloca pre-existing in the entry block, stores
%val into the alloca right after the call, and at least one branch
returns by loading from the alloca.
The pre-existing alloca/store/load pattern does not write to memory
the call could read (the alloca is local and the call's pointer
argument is unrelated) and the call cannot write to the alloca, so
the picker should reach the same conclusion as in the simpler
counterpart tests: the variant of @call_rw_one_use generates no new
alloca, @call_rw_two_uses generates one new alloca alongside the
pre-existing one, and @call_ro_two_uses generates none.
Cover three representative cases for how the picker should treat
function calls in non-legacy mode:
- A call to a read+write function with a single use (an icmp that
feeds a conditional branch). The call has only one use, so the
picker does not pick it and no new alloca is created.
- The same shape, but with two uses of the call (the icmp and a
return). Because the function may read+write memory and the call
has more than one use, the picker picks the call: a new alloca is
created at the top of entry, the result of the call is stored into
it, and every user of the call uses a load from the alloca.
- The same shape as the second case but with a function that only
reads memory (and is also nounwind willreturn so that
Instruction::mayHaveSideEffects returns false). The picker does
not pick the call and no new alloca is created.
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.
Cover several scenarios where a single base pointer is reachable
only after the discovery walk in ArithmeticToGEPPass propagates
through many layers of Add instructions, each of which has
ambiguous pointer operands and must be disambiguated separately:
- A chain of 8 chained adds with a varied set of clearly-non-pointer
offset opcodes (mul, ashr, shl, and, or, xor, sdiv, srem), with
discovery seeded from the !revng.pointers metadata on the return.
- A chain seeded from a pointer argument (forward propagation).
- A chain feeding the integer argument of a call whose argument is
a pointer (backwards discovery from the call site).
- A chain where the pointer side alternates between operand 0 and
operand 1 of each add.
- A chain whose offset side is hidden behind freeze instructions,
so the cannotBePointer recursion through transparent casts is
exercised.
- A chain where every add reuses the same multiplication as offset,
exercising independent disambiguation per-add over a shared
sub-expression.
- A chain interrupted by ptrtoint/inttoptr round-trips between adds.
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.
Add an llvm-lit test suite for the new-PassManager
SwitchToStatements pass, exercised via
`revng opt -passes=switch-to-statements-test` (registered by the
pass's registerCallbacks hook). The tests cover load/store
serialisation, side-effecting calls and a few representative
patterns where an instruction must be picked for serialisation
because its memory read is no longer available at one of its uses.
The `Head` election now works in a bottom-up fashion (child regions are
processed before the parent ones), and ensures that the `Head` election
process is coherent across multiple nested regions.
This means that:
1) The late entries are coherent between the nested regions. If a node
is selected as a late entry for a region, the parent region must
follow this decision too.
2) If a node which is a `Head` candidate for a parent region, is
selected as the `Head` for a child region, the same choice must be
performed for the parent region too.
Drop the `MaterializeLoopScopes` pass after the re-design the loop
matching stage to work entirely on `clift`, without the need to insert a
`scope_closer` edge to guide the emission.
Simultaneously, drop the DAGify `Head` metadata insertion, since it will
not be checked anymore during the `MaterializeLoopScopes` pass.
During the `Head` election phase, we now introduce the following
additional criterion:
When processing a `GenericRegion` nested into an outer one (its
`ParentRegion`), if the inner `Region` contains the block that has been
elected as `Head` of the `ParentRegion`, we also force that block to be
the `Head` of the inner `GenericRegion`.
We add a unit test to check this behavior.
The `check-conventions` script inadvertently ignored checking the
license header in `CMakeLists.txt`. Change the script so that those are
checked. Also add the missing headers to the reported files.
Perform the abnormal (late) entries normalization in the DAGify pass.
In this way, we are exploiting the information computed by
`GenericRegionInfo` as close as possible to where it is computed the
first time (in DAGify).
Actualize the unit tests to reflect these changes.
Perform the IDS transformation, by taking into account possible multiple
divergent scopes for a certain conditional node at the same time.
This reduces the run times, since it reduces the number of time IDS is
called on a conditional, but mostly proceduce a more _compact_
`ScopeGraph`, where all the divergent scopes for a certain conditional
node rejoing the path toward the one true exit in a single point,
instead of having a chain of IDS resulting regions.
Make IDS unit tests compliant with the new multiple divergence
implementation.
Implement the DAGify pass. This pass, using the results exposed by the
`GenericRegionInfo` analysis, transforms all the retreating edges of
each identified `GenericRegion`, processed in a bottom-up fashion, into
a `goto` edge on the `ScopeGraph`.
Implement the `Inverse<Scope<...>>` `GraphTraits`. This are needed in
order to support the computation of the `PostDominatorTree` on a
`ScopeGraph`.
Add some `FileCheck` tests to test the dominator and postdominator trees
on the `ScopeGraph`.
Introduce the Enforce Single Exit pass, whose task is to normalize a
generic `ScopeGraph`, which may have multiple exit blocks (and/or
infinite loop regions), in order to have a single `sink_block` as exit
block.
This is done by adding a new entry block, a `sink_block`, and some
`scope_closer` edges (which are visible only on the `ScopeGraph`) that
enforce the property.
This is done taking inspiration from how the internally the
`PostDominatorTree` pass construct the temporary graph on which the post
dominance information is computed on.
Some unit tests are added in order to verify that the pass works as
expected.
Introduce the `ScopeCloser` and `GotoTarget` annotations in the IR, and
the relative necessary machinery, needed to handle scope closer and goto
edges for the new backend.
A specialization of the `llvm::GraphTraits`, called `ScopeGraph`, that
is able to handle both the above mentioned annotations is provided.
For the `llvm::GraphTraits` implementation, we introduce the
`GeneratorIterator` class, which uses a coroutine to store the status of
the iteration.
A debug logger pass is added, so that we are able to test the
functionality with `FileCheck`.
We implement the `GenericRegionInfo` analysis.
The analysis accepts a template parameter which enables to run it on
every graph which exposes `llvm::GraphTraits`.
The `GenericRegionPass` is responsible for instantiating and running the
analysis on a `llvm::Function`.
The `GenericRegionInfo` analysis uses, and takes insipiration from the
`GenericCycleInfo` LLVM analysis.
The analysis exposes a tree of well nested `GenericRegion`s, which are
constructed starting from the well nested tree of `GenericCycle`s.
In addition, we perform the election of the `Head` of each
`GenericRegion`, and the election of the retreating edges.
We introduce the `CycleEquivalence` analysis.
This is an analysis which implements the _Cycle Equivalence_ computation
algorithm, and provides as result the _cycle equivalence classes_
Specifically, we introduce:
- The `CycleEquivalenceClass`, which is the unitary element computed by
the analysis.
- The `CycleEquivalenceAnalysis`, which contains the algorithm to
compute the cycle equivalence.
- The `CycleEquivalencePass`, a `FunctionPass` that can be used to
perform the analysis on a `llvm::Function`.
The algorithm is composed by various stages:
- We construct a new `GenericGraph` object, replicating the input CFG,
with the addition of the `exit`->`entry` edge.
- Taking advantage of `llvm::GraphTraits<Undirected<>>`, we can now
implement the algorithm working on an undirected version of the input.
- We perform the `CycleEquivalence` computation, returning a
`llvm::SmallVector` of `CycleEquivalenceClass` objects.
In addition to using the `llvm::GraphTraits<Undirected<>>` traits to
walk on the equivalent undirected graph, we also need to:
- Perform a preliminary DFS, in order to:
- Assign the DFS number to each node in the graph.
- Compute the spanning tree, and use this information to distinguish
tree edges and back edges when running the algorithm.
The internal graph used by the analysis also normalizes the graph in
order to have a sinle exit node (called sink), which is a requirement
for the `CycleEquivalence` algorithm.
We also implement the `llvm::DOTGraphTraits` for the
`CycleEquivalenceAnalysis<llvm::Function *>` specialization. In this
way, we can have a graphical representation of the undirected graph used
internally in the `CycleEquivalenceAnalysis` core implementation.
We add some `FileCheck` tests on some well-known graph topologies.
This bug caused the expression x + (-2) < -3 to be rewritten as
(x > 2) || (x < -1), instead of (x > 2) && (x < -1).
We had tests for a very similar case, but this specific example was
triggered by having the two constant terms in the inequality with a
difference of only one.
This commit rewrites and unifies the logic for handling inequalities,
and adapts the test for checking this specific additional corner case.
Many old unit tests were too rigid, using the model and the LLVM IR.
This commit drops them, and replaces them with decompilation tests based
on revng-qa, relying on `revng model compare` to test model properties,
and on `FileCheck` to test that we emit specific constructs in C.
The new tests cover various features of the decompiler.
* DLA capability to recover complex data structure like linked-lists and
arrays.
* DLA capability to update segment and section types, so that we emit
nice looking accesses to segments in C.
* Capability to emit nice looking integer literals in C
* Capability to emit inline string literals in C and update the model
types of the segments containg such string literals.
This pass is dedicated to applying a bunch of peephole optimizations
that are useful for decompilation and haven't been implemented in LLVM
for whatever reason.
At the moment it only runs an optimization that tries to reduce the uses
of incoming values of PHINodes, under very specific condidtions, which
enables emitting less LocalVariables.
Simplification includes dropping dependencies onto
`FunctionMetadataCachePass` and `LoadModelWrapperPass`, as well
as removing "StructName" logic outright.
Pietro Fezzardi