On-Demand range technology [1/5] - Executive Summary

Andrew MacLeod amacleod@redhat.com
Thu May 23 01:28:00 GMT 2019

Now that stage 1 has reopened, I’d like to reopen a discussion about the 
technology and experiences we have from the Ranger project I brought up 
last year. https://gcc.gnu.org/ml/gcc/2018-05/msg00288.html .  (The 
original wiki pages are now out of date, and I will work on updating 
them soon.)

The Ranger is designed to evaluate ranges on-demand rather than through 
a top-down approach. This means you can ask for a range from anywhere, 
and it walks back thru the IL satisfying any preconditions and doing the 
required calculations.  It utilizes a cache to avoid re-doing work. If 
ranges are processed in a forward dominator order, it’s not much 
different than what we do today. Due to its nature, the order you 
process things in has minimal impact on the overall time… You can do it 
in reverse dominator order and get similar times.

It requires no outside preconditions (such as dominators) to work, and 
has a very simple API… Simply query the range of an ssa_name at any 
point in the IL and all the details are taken care of.

We have spent much of the past 6 months refining the prototype (branch 
“ssa-range”) and adjusting it to share as much code with VRP as 
possible. They are currently using a common code base for extracting 
ranges from statements, as well as simplifying statements.

The Ranger deals with just  ranges. The other aspects of  VRP are 
intended to be follow on work that integrates tightly with it, but are 
also independent and would be available for other passes to use.  These 
- Equivalency tracking
- Relational processing
- Bitmask tracking

We have implemented a VRP pass that duplicates the functionality of EVRP 
(other than the bits mentioned above), as well as converted a few other 
passes to use the interface.. I do not anticipate those missing bits 
having a significant impact on the results.

The prototype branch it quite stable and can successfully build and test 
an entire Fedora distribution (9174 packages). There is an issue with 
switches I will discuss later whereby the constant range of a switch 
edge is not readily available and is exponentially expensive to 
calculate. We have a design to address that problem, and in the common 
case we are about 20% faster than EVRP is.

When utilized in passes which only require ranges for a small number of 
ssa-names we see significant improvements.  The sprintf warning pass for 
instance allows us to remove the calculations of dominators and the 
resulting forced walk order. We see a 95% speedup (yes, 1/20th of the 
overall time!).  This is primarily due to no additional overhead and 
only calculating the few things that are actually needed.  The walloca 
and wrestrict passes are a similar model, but as they have not been 
converted to use EVRP ranges yet, we don’t see similar speedups there.

That is the executive summary.  I will go into more details of each 
major thing mentioned in follow on notes so that comments and 
discussions can focus on one thing at a time.

We think this approach is very solid and has many significant benefits 
to GCC. We’d like to address any concerns you may have, and work towards 
finding a way to integrate this model with the code base during this 
stage 1.

Comments and feedback always welcome!

More information about the Gcc mailing list