I'd like to introduce a project we've been working on for the past year
an a half.
The original project goal was to see if we could derived accurate range
information from the IL without requiring much effort on the client
side. The idea being that a pass could simply ask "what is the range of
this ssa_name on this statement? " and the compiler would go figure it out.
After lots of experimenting and prototyping the project evolved into
what we are introducing here. I call it the Ranger.
Existing range infrastructure in the compiler works from the top down.
It walks through the IL computing all ranges and propagates these values
forward in case they are needed. For the most part, other passes are
required to either use global information, or process things in
dominator order and work lockstep with EVRP to get more context
sensitive ranges.
The Ranger's model is purely on-demand, and designed to have minimal
overhead. When a range is requested, the Ranger walking backwards
through use-def chains to determine what ranges it can find relative to
the name being requested. This means it only looks at statements which
are deemed necessary to evaluate a range. This can result is some
significant speedups when a pass is only interested in a few specific
cases, as is demonstrated in some of the pass conversions we have
performed. We have also implemented a "quick and dirty" vrp-like pass
using the ranger to demonstrate that it can also handle much heavier
duty range work and still perform well.
The code is located on an svn branch *ssa-range*. It is based on trunk
at revision *259405***circa mid April 2018. **The branch currently
bootstraps with no regressions. The top level ranger class is called
'path_ranger' and is found in the file ssa-range.h. It has 4 primary API's:
* bool path_range_edge (irange& r, tree name, edge e);
* bool path_range_entry (irange& r, tree name, basic_block bb);
* bool path_range_on_stmt (irange&r, tree name, gimple *g);
* bool path_range_stmt (irange& r, gimple *g);
This allows queries for a range on an edge, on entry to a block, as an
operand on an specific statement, or to calculate the range of the
result of a statement. There are no prerequisites to use it, simply
create a path ranger and start using the API. There is even an
available function which can be lightly called and doesn't require
knowledge of the ranger:
static inline bool
on_demand_get_range_on_stmt (irange &r, tree ssa, gimple *stmt)
{
path_ranger ranger;
return ranger.path_range_on_stmt (r, ssa, stmt);
}
The Ranger consists of 3 primary components:
* range.[ch] - A new range representation purely based on wide-int ,
and allows ranges to consist of multiple non-overlapping sub-ranges.
* range-op.[ch] - Implements centralized tree-code operations on the
irange class (allowing adding, masking, multiplying, etc).
* ssa-range*.[ch] - Files containing a set of classes which implement
the Ranger.
We have set up a project page on the wiki which contains documentation
for the approach as well as some converted pass info and a to-do list here:
https://gcc.gnu.org/wiki/AndrewMacLeod/Ranger
We would like to include the ranger in GCC for this release, and realize
there are still numerous things to be done before its ready for
integration. It has been in prototype mode until now, so we have not
prepared the code for a merge yet. No real performance analysis has
been done on it either, but there is an integration page where you will
find information about the 4 passes that have been converted to use the
Ranger and the performance of those:
https://gcc.gnu.org/wiki/AndrewMacLeod/RangerIntegration
One of the primary tasks over the next month or two is to improve the
sharing of operation code between the VRPs and the Ranger. We haven't
done a very good job of that so far. This is included along with a
list ofknown issues we need to look at on the to-do page:
https://gcc.gnu.org/wiki/AndrewMacLeod/RangerToDo .
The Ranger is far enough along now that we have confidence in both its
approach and ability to perform, and would like to solicit feedback on
what you think of it, any questions, possible uses, as well as
potential requirements to integrate with trunk later this stage.
Please visit the project page and have a look. We've put as much
documentation, comments, and to-dos there as we could think of. We will
try to keep it up-to-date.
Andrew, Aldy and Jeff
