After the various discussions, I've evaluated how I think everything can
fit together, so this is my proposal for integration with trunk.
The complete Ranger prototype consists of 5 major components, one of
which is missing/un-implemented as yet :-)
1 - irange - This is the non-symbolic range implementation we've
been using which represents ranges as groups of ordered sub-ranges.
2 - range-ops - This is the component which extracts ranges from
statements, and so performs the functionality of extract_range_from_*,
except it operates on the irange API and also allows for solving of
operands other than just the LHS of the expression.
3 - GORI-computes - This is the component which utilizes range-ops to
compute a range on an outgoing edge for any ssa-name in the definition
chain of the branch
a_3 = b_6 * 2
d_8 = a_3 - 20
if (d_8 < 30)
the GORI-compute component can generate ranges for d_8, a_3 and b_6.
4 - GORI-Cache and the Ranger. Working together, this provides the
on-demand range functionality to resolve ranges
5 - relational/equivalency tracker - This is the sketched out but
unimplemented bit which tracks the symbolic relationships, and remove
the need for ranges to support symbolics. ( <,<=, >, >=, ==, != and none).
The consensus appears to be that range-ops and gori-computes are good
candidates to replace aspects of vr-values and assert generation.
A)
Until I get to (5) (relational tracker), using (1) (irange) is a
non-starter since it doesn't handle symbolics.
To eliminate the range issue from the equation, Aldy is currently
working on unifying the irange and value_range APIs. This will allow
the rest of the ranger code base to use the value_range implementation
transparently. We can talk about irange or some alternate
implementation of ranges at some later point, but there'll be an API
that works for all clients.
The existing value_range API gets a few tweaks/cleanups, but mostly
there is an additional set of calls to query sub-ranges which the ranger
and range-ops require. These routines basically translate the various
value ranges formats into discrete sub-ranges. Thru these rotuines,
ANTI_RANGE will appear as 2 sub-ranges, VARYING as a [MIN, MAX] range,
and UNDEFINED as an empty range []. These additions should allow
value_range to function as the range implementation for both the ranger
and VRP.
I suspect he will have patches coming shortly that will help to unify
the 2 range implementations, we can discuss details over those patches..
B)
A Unified range API then allows us to work on integrating the range-ops
and GORI-computes component into the code base. Range ops would
replace the various extract_range_from_*_ routines in vr_values for
statement level ranges. GORI-computes would then replace the assert
building code for calculating outgoing ranges on edges. In theory EVRP
then simply calls range_on_edge() from gori_compute instead of
register_edge_assert() .
The range ops code is designed to perform all evaluations assuming an
arbitrary number of sub-ranges. Aldy spent a lot of time last year
unifying the VRP code and the range-ops code to get the identical
results, and they frequently share a common base. He has gone thru
excruciating care to ensure the calculations are identical and verifies
it by calculating everything using both code bases, comparing them, and
aborting if the results ever get diverge.
We will need to adjust the range-ops code to work with symbolics in
certain place. This means PLUS, MINUS, all the relations (<,>, etc), and
copy. Probably something else as it is encountered. This is un-sized as
yet, but I'm hoping won't be too bad assuming we can utilize some of the
existing code for those bits.. More details when we actually start
doing this and find the lurking dragons.
we'll worry about bitmasks and equivalencies when we get closer to
functioning, but I don't foresee too much problem since value_range_base
is still being used.
C) That will keep us busy for a while, and should result in the core
integration. Meanwhile, we'll try to figure out the relational code
design. I'll go back to my original design, adjust that, then we can
figure out how best to proceed to address the various needs.
D) Finally, the GORI-cache and on-demand ranger are blocked until the
above work is finished.
One additional thing I would like to do eventually is tweak EVRP
slightly to align with the ranger model.
The ranger API is basically just 5 entry points which the ranger uses to
determine ranges.
range_of_expr - range of a use on a statement
range_of_stmt - range of the result of the statement, (calculated
by range-ops).
range_on_edge - range on an edge - (provided by gori_computes)
range_on_entry - range on entry to a block (provided by gori-cache)
range_on_exit - range after the last statement in a block
Abstracted and simplified, I believe EVRP functions more or less like
this? :
- EVRP starts a block with it's "current range" vector initialized to
the range on entry values. (provided as you step into the block),
- It then walks the IL for the block, evaluating each statement,
possibly simplifying, and updating this current range vector.
- when it reaches the bottom of the block, it calculates outgoing ranges
on each edge and updates those to provide a current range at the start
each successor block.
If one considers EVRP without making any IL changes, it can be viewed as
another range calculator. If that is mapped that to the ranger API:
range_of_expr - This is always the current value in the
current-range vector as you walk the IL.
range_of_stmt - range of the result of the statement (to be
provided by range_ops). so this is identical
range_on_edge - this is also identical, to be provided by
gori_computes.
range_on_entry - Provided at the start of block processing, never
needed again since it is updated on the fly.
range_on_exit - range after the last statement in a block. when
EVRP reaches the end of the block, current value is this as well.
EVRP and the ranger have now become alternate implementations of the
same model, the ranger is on-demand and EVRP just requires processing
everything linearly through a basic block.
We can tweak the interface's to align a bit better, and then adjust the
simplification code so it works with that API. That should make EVRP and
the on-demand Ranger interchangeable during a forward walk.
This would allow a much more accurate comparison of how the 2
implementations behave and what kinds of results they can get.
It also opens up the unexplored possibility of some sort of hybrid
version which can resolve some of the drawbacks to each approach.
===================
Short summary:
a) we'll unify value_range and the irange API, confirm there are no new
bugs nor performance issue. This would considered complete when the
ranger is able to fully run using value_range instead of irange.
b) we'll then port the required parts of range-ops and gori-computes to
handle basic symbolics in value_range so that the VRPs' will see the
same results with range-ops as it does with the extract and assert
code. Then we will integrate it with vr_values and EVRP. This would be
considered complete when results are identical and there is no
unacceptable performance impact.
c) meanwhile we'll work on the relational tracking mechanism.
d) Then we can revisit the on-demand engine vs the EVRP walk mechanism
and any other things dreamed up between now and then.
Does this seem reasonable?
Andrew
