Add a new dummy node as the source of each backedge found in the graph,
during the preprocessing.
This help in the semplification phase of the SCS, since the new dummy
node helps triggering merging of metaregions with have a non empty
intersection.
The new SCS merging criterion, checks that there are no abnormal
retreating nodes between SCS, meaning retreatings which exit from the
current SCS and do not point to the head of another SCS.
This kind of situation, if ignored could cause the introduction of some
cycles between outlined nodes and existing nodes, inserting new cycles
during the restructuring, which is a behavior which we aim to avoid.
When outlining nodes, we now include them in eventual parent metaregions
that included the nodes collapsed.
This should lead to minor duplication (as in the `cp` benchmark), since
we avoid duplicating two times nodes if also the external region causes
the first iteration outlining.
* Introduce `ShrinkInstructionOperandsPass`: a transformation shrinking
operands and the results of instructions if they are
zero/sign-extended immediately before and after the instruction.
* Introduce `ConstantRangeSet`: similar to `ConstantRange` but allows
disjoint ranges.
* Introduce `MaterializedValue`: a class that can represent a constant
value or a symbol plus offset pair.
* Introduce `DropHelperCallsPass`: a transformation removing calls to
helpers and replacing them with a function call reading the CSVs that
the helper reads and writing the CSVs that the helper writes
(according to CSAA).
* Introduce `DropRangeMetadataPass`: a transformation dropping the
`range` metadata, which, in certain situations, lowers the quality of
the results provided by `LazyValueInfo`.
* Introduce `AdvancedValueInfo`: an analysis exploiting results of
`LazyValueInfo` but collecting them as `ConstantRangeSet` with a
monotone framework. It produces `MaterializedValue`.
* Anticipate linking of helpers: `AVI` requires `CSAA`, which requires
helper functions to be linked in.
* Drop `--no-link`.
* Force x86-64 `DataLayout`.
* Reorganize harvesting to either collect simple literals or go with
(incremental) `AVI`.
* Drop `SET`, `OSRA`, the reaching definition analysis, the
`SimplifyComparisonsPass` and all the sumjump-related code: e now
clone `root`, optimize it and analyze it with `AVI`.
* Temporarily drop the `NoReturnAnalysis`.
* Link `libLLVMInstCombine`, `libLLVMCodeGen` and `libLLVMPasses`.
* Introduce tests for `AdvancedValueInfo`,
`ShrinkInstructionOperandsPass` and `ConstantRangeSet`.
* Fix test results.
* Add `llvm.bswap.i64` and `@pc` to the LLVM template module for unit
tests.
Any stack pointer value greater than or equal to the original one used
to be OK for stack analysis to recognize an instruction as a
return. This commit changes this policy by collecting the value of the
stack pointer on all the return points and, at the end, elect a final
stack pointer value. All non-compliant returns are marked a
`BranchType::BrokenReturn`. The function is now considered fake only if
all the return instructions agree on a specific value of the stack
pointer, and it's lower than the original one.
* Drop `BranchType::IndirectTail`.
* `s/BranchType::FunctionSummary/BranchType::RegularFunction/`.
A series of algorithms working on `llvm::GraphTraits`.
* `nodesBetween` computes the set of nodes on all the paths from a node
A to B.
* Factor out code to iterate over infinite loops into
`exitless_scc_range`.
* Introduce unit tests.
* Introduce `KeyContainer::compare` and drop the `getKey` method.
* Let users of ZipMapIterator specify a trait class instead of using the
default one.
We know keep updated the RPOT during node removals (otherwise we have
situation of pointer clashes) instead of recomputing it at each
metaregion restructuring iteration.
* `GeneratedCodeBasicInfo::getCSVUsedByHelperCall` and
`GeneratedCodeBasicInfo::extractCSVs`: make the call argument an
`Instruction`.
* Introduce `blockByName`
* Introduce `getUniqueUser`.
* Fix linking issues.
Dropped the use of a temporary file containing the necessary includes
for clang-tooling to work correctly (at the moment `#include <stdint.h>`
) in favor of a single file which is installed in `root/share/revngc`
and used by clang-tooling.
If the `-decompiled-prefix` is passed to the `revng opt` command the
decompilation pass takes care of serializing the decompiled code of each
function in a different file.
The filename is composed by the prefix string passed as parameter and by
the function name.
To avoid skeing the results the serialization of `DOT` intermediate file
for both restructuring and AST semplification passes are now serialized
only when the corresponding loggers (`CombLogger` and `BeautifyLogger`)
are enabled.
When a retreating edge involves as source node a `SetNode` belonging to
an internal region (which should be the default `SetNode` that remains
outside the collpased node), move it just after the `CheckNode` that is
being introduced, so that the semantics of the code remains untouched.
Use a `llvm::SmallString` for the `Name` field of `BasicBlockNode`.
This enables us to modify the name of the node, which is very useful
during debugging and manual inspection of the graph serialized in
output.
Fix the metaregion identification phase, in particular the add of the
addditional nodes merged when encountering a node which is the target of
a backedge identifying another metaregion.
The add of the additional nodes must be done in a fixed point fashion,
otherwise in case of dependent insertions the order of the nodes
triggers different behaviours (and bugs).
`BasicBlockNode` and `RegionCFG` classes are now template classes. This
means that the `BasicBlockNode` class can be used as a generic wrapper
for any type of object in the original graph (it is usually used to wrap
a `llvm::BasicBlock *` for decompilation purposes, but in tests it can
be used to wrap a `DotNode` object) that implementes `GraphTraits`.
Improved the interaction with the `StringRef` name field of
`BasicBlockNode`.
In case of artificial nodes, the name is left empty and created
on-the-fly for serialization purposes.
Removed the computation of the information contained in the
`NDuplicates` prevously done in the `MarkForSerialization` pass, since
the information is now precomputed in the `RestructureCFG` pass and
exposed with a dedicated method.
Add a `DotGraph` and `DotNode` classes, which implements `GraphTraits`,
so that we can create a `RegionCFG` starting from a graph specified in
a `.dot` file.
The `DotClass` implements a minimal parser for graph specified in `.dot`
format.
The `.dot` should begin with the specification of the name of the graph
`digraph TestGraph {`, followed by an arbitrary number of lines which
specify the edges in the graph (no attributes allowed, e.g., `a -> b;`).
The file should end with a single line ending in `}`.
Add helpers to test if two `RegionCFG` objects can be considered
equivalent.
This will be used in the test environment to check if the comb
transformation is consistent with the expected behavior.
Update the `OriginalBB` map (which will be later used for retrieving the
original basic block linked to a certain BBNode) during nested
`RegionCFG` creation and during flattening, which are steps that modify
the allocation of the `BBNode` objects.
The `RegionCFG::initialize` method is now a template method, which
accepts as input any kind of object which exposes the `GraphTraits`.
In this way we can build a `RegionCFG` object not only starting from
LLVM IR, which can be very useful for testing purpose.
Since we also removed the information about the original
`llvm::BasicBlock` inside the `BasicBlockNode`, we need to keep this
link to later feed this information to the GHAST in an external data
structure (potentially a `std::map`).
Andrea Gussoni