We now implement the `nodesBetween` primitive with a double DFS visit.
Specifically, we have:
1) A forward DFS that starts from the `Source`, and stops at `Target`.
2) A backward DFS that starts from the `Target`, and stops at `Source`.
The final result is then the intersection of the nodes found by the two
above DFS visits.
A new `findReachableNodes` primitive is also added to perform a DFS from
a `Source` node, which stops at the `Stop` parameter node, if present.
Added unit tests to improve the coverage.
This commit sets a name for types we use in OpaqueExtractValues.
These are StructTypes that can only be returned from isolated functions
with RawFunctionType prototype on the model, or from helpers that do not
represent isolated functions.
The name is required because when we will converto to MLIR LLVM Dialect,
there are checks in place that forbid unnamed types.
The code re-uses code that is used to print C code, in order to make
sure that the struct names we use for this are the same as those we emit
in C, to ease debugging.
This commit also cleans up the unittest to make it more concise, while
still testing the same things.
This commit changes the following method names across the codebase:
* `storeToDisk` -> `store`
* `loadFromDisk` -> `load`
This has been done since the storage is no longer bound to the local
storage.
This commit introduces the concept of `Component` to a pipeline step.
This, in turn, can be used by clients to figure out which artifacts are
produced by which revng component.
Additionally, this commit overhauls the `revng daemon-self-test`
command, renaming it to `revng graphql` and adding extra flexibility.
* Fix non-PrimitiveTypes with low IDs.
* Ensure we use `revng model compare` to test the model.
* Updates the name to reflect the recent changes in naming convention
and in the way we represent `model::Type::ID`s.
This commit switches `model::Type::ID` from being a GUID to be a
progressive number, in order to make things easier for humans.
On top of this, this commit introduces the following changes:
* TypeCopier: import all the necessary PrimitiveTypes and improve
handling of CustomName.
* Move Kind as the last field of the key of each TupleTree type used in
an `UpcastablePointer`.
* Update the ground truth of tests to ignore the `CustomName` in favor
of focusing on `OriginalName`.
* Increase adoption of `model::Binary::makeType`, equivalent to
`Binary.recordNewType(makeType<model::*Type>())`.
We now switch to the `llvm::df_iterator` based `nodesBetween`
implementation.
This new implementation makes use of the idiomatic way of extending the
DFS implementation provided by LLVM, instead of rolling our custom
implementation for the `nodesBetween` algorithm.
We improve the `getBackedges` and `nodesBetween` helper functions that
can be used for backedge discovery and computation of all the nodes
reachable on all the paths defined between two nodes in a graph.
We build upon the `llvm::df_iterator` function, by customizing the visit
stack to perform the desired visits.
`ValueMaterializer` is a rewrite of what was called `AdvancedValueInfo`
which follows the same principles.
The main benefits over the old version is:
* We materialize the data-flow graph and the CFG of the relevant part of
root. This makes debugging significantly easier.
* We drop the old MonotoneFramework infrastructure in favor of
getMaximalFixedPoint.
* We significantly reduce the amount of queries we make to
AdvancedValueInfo.
Before this commit, the TwosComplementArithmeticNormalizationPass wasn't
taking into consideration properly all the cases where the arithmetic
can wrap around in case of expression such as (x + const1 <=> const2) or
(x - const1 <=> const 2).
This caused 2 different classes of problems that affected semantics.
1) In some cases we were emitting comparisons that were too broad,
meaning that they were true in a larger set of cases than the
original one.
2) In other cases we were emitting tautological comparisons, i.e.
comparisons that were always demonstrably true or false at compile
time.
This commit fixes the problem, treating all the cases in a generalized
unique way that works correctly for every case.
Implements transforms when the results of sub or add with a constant
operand are compared against constant:
1) x + a == b --> x == b - a
2) x + a != b --> x != b - a
3) x + a <= b --> x <= b - a
4) x + a < b --> x < b - a
5) x + a >= b --> x >= b - a
6) x + a > b --> x > b - a
After the transformation, the right hand side is also enqued for
analysis to detect opporunities to use unary minus if a-b is a negative
constant.
Ivan Krysak