In this commit we instruct the build system to use the unified schema
files instead of collecting the `TUPLE-TREE-YAML` comments.
The fixes to C++ files are necessary because they depend on the order
of the fields in the schema, which was changed.
This commit moves stuff around to enforce complete information being
present by the time the "Internal" assembly output is ready.
Because of that, the "Internal" format needed to change, now it uses
tag representation close to PTML as opposed to the one close to LLVM's
used before now.
HexDumpPipe dumps content of binary file in the similar way as hexdump
tool with addition of PTML markup for instructions addresses.
Continuous parts of binary code are wrapped with <span
data-location-definition=""></span> where data-location-definition
attribute contains Entry/BasicBlock/Instruction addresses in generic
form. <span> tags can be nested if byte(s) belong to many instructions
in code.
At the end of the line every <span> is closed and opened on the next
line again if it still applies to the next byte.
MetaAddress are converted to IntervalMetaAddress (which implements own,
optional-less operator-) and stored in boost::icl::intruval_map. This
map is used to get addresses of instructions to which each byte belongs.
This commit introduces `BasicBlockID` as the unique identifier for a
`efa::BasicBlock` into the CFG. A `BasicBlockID` is defined by a
`MetaAddress` plus an incremental integer. This enables us to have
multiple instances of the same block in a single function, which is
particularly useful when inlining multiple times the same function.
Apart from this, the commit also does the following:
* It drops representing `MetaAddress`es a `structs` in the IR. This created
several issues related to ABI. We now represent them as strings.
* It defines more functions in `support.h`, instead of defining prototypes
by hand in `CodeGenerator.cpp` and the like. Specifically, `unknownPC`
and `raise_exception_helper`. We also introduce a C "constructor" for
`PlainMetaAddress`.
* It significantly reduces the API of `GeneratedCodeBasicInfo`, which
was supposed to be put on a diet since a long time. Specifically,
many jump target related methods have been moved to free functions in
`IRHelpers.h`. Also `GCBI::getSuccessors` has been pushed into its
only user, `PruneRetSuccessors`, to prevent further usage of a
deprecated API. In the future, it would be nice to drop it entirely.
* It introduces `efa::BasicBlock::InlinedFrom`.
* Introduce an enum to represent named argument indices for `newpc`.
This enables us to more effectively manipulate its argument list.
* It improves the verification and error reporting for
`efa::FunctionMetadata`.
* Update tests.
This commit is preliminary to another piece of work to improve the
generality of inlining beyond the simple "fake function" scenario, for
which the feature was originally conceived.
A cyclic dependency between shared objects `revngYield` and
`revngFunctionIsolation` could exist if `FunctionIsolation`
were to use `yield`-defined methods. This has been prevented
by splitting pipes off within `Yield`.
This change introduces some duplication but ensures an important
property of `tuple_tree_generate`d: data structures: all the leaves are
scalars. Previously, yield::Function was using efa::BasicBlock, making
things more difficult under certain conditions.
Specifically, we can rely on the fact that, when generating a visit to
the TupleTree, we know everything about all non-scalars.
(the following is the original commit message)
Now that every single node has gotten its exact position, the only
thing left to do is to route all the edges between them. First of
all, the special edges (like corners) need to be handled.
(the following is the original commit message)
Now, that it's precisely known how much space is needed between each
pair of the layers, it's possible to set the vertical coordinates for
each of the nodes based on the layer heights (the height of the
longest node within said layer) and the number of horizontal lanes
required after it.
(the following is the original commit message)
Now that the nodes are placed into the grid (at least horizontally),
it's possible to focus on the edges. Since, the information about
the number of edges going from/to each of the layers is known, it's
possible to determine the number of horizontal space needed to placed
those.
In this part of the layouter, the focus is on three different laning
points:
- horizontal lanes between layers.
- entry lanes for each of the nodes.
- exit lanes for each of the nodes.
Indexation is done independently for each of the lane types.
(the following is the original commit message)
Since the predetermined order of the nodes for each layer was already
predetermined, what's left is to put their coordinates based on the
size of the nodes and the predefined margins between them.
Except the resulting layouts are extremely left-heavy. As such, it's
important to use the coordinate selection part to push as many nodes
to the right as possible to balance the graph out at least somewhat.
(the following is the original commit message)
Since from this point on, no breaking changes will be done to the graph
It's possible to finalize the layout. Meaning that from this point
onwards the logical positions of the nodes remain unchanged.
Having this guarantee we can proceed to calculating their real
positions, starting from the horizontal coordinates.
(the following is the original commit message)
Now that the layer permutation is finalized, it's possible to select
a couple of node-groups that only depend on a single predecessor and
consider them a single linear segment. This allows to "draw" straight
vertical lines accross the layout for nodes that could benefit from
that.
Such linear segments are also paramount for good looking long edges
(both forwards and backwards facing).
\note: this part of the layouter could still use more work.
If you're looking to rework it, this is the spot.
(the following is the original commit message)
To optimize the algorithms coming from now, having a topological
of the nodes of the graph is benefitial. And, considering, no new
nodes will be added to the graph from this point on, we can only
compute it once.
To optimize the ordering even further, augmented graph is used.
On top of the original (and earlier added artifical) edges, the graph
used for obtaining the ordering get a few extra edges added.
`llvm::ReversePostOrderTraversal` is used to convert the graph to the
ordered node list.
(the following is the original commit message)
To ensure the optimal layout is choosen, it's important to try out
and compare a few different permutations.
First of all, layers are optimized. Those layers, that only contain
irrelevant artificial nodes are removed and all the others are shifted
in order to maintain simple layer indexing.
Then, using a simple hill climbing the permutation with the lowest
number of edge crossings is selected. After which a technique based
on computing barycenters for nodes and layers is used as a fallback
to ensure even the least optimal layout is still usable.
On top of all that, simple clustering based on the classification
obtained while preparing the graph is used to keep original nodes
somewhat separate from the artificial ones.
(the following is the original commit message)
Preparation includes:
- ensuring there are no loops.
- ensuring there are no edges spanning more than a single layer.
- ensuring there are no backwards facing edges that were not split
into a bunch of parts to simplify laying them out.
- ensuring there are no self loops (they are treated similarly to
backwards facing edges, which they theoretically are).
Subproducts include:
- `Classifier` allowing to cheaply determine whether a given node is
adjacent to an artificial edge.
- `Ranks` container allowing to easily determine the layer each of the
nodes belongs to.
Khaled Ismaeel