Project Ranger
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.
The prototype has been refined (branch “ssa-range”) and adjusted 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 include:
- 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.
The old project page goes into some deep details about the approach, and although some things have changed, the core ideas remain the same. the original project page is located Here.
Major Components : Brief description of the primary components of the ranger.
Prototype : Whats been implemented in the branch.
Performance : How does it compare in the real world.
The Future : What else needs doing to replace existing VRP.
Integration : The Path forward to integration with trunk.