Hi Andrew, Thanks for working on this.
Enable elimination of zext/sext with VRP patch had to be reverted in (https://gcc.gnu.org/ml/gcc-patches/2014-09/msg00672.html) due to the need for value ranges in PROMOTED_MODE precision for at least 1 test case for alpha. Playing with ranger suggest that it is not possible to get value ranges in PROMOTED_MODE precision on demand. Or is there any way we can use on-demand ranger here? Thanks, Kugan On Thu, 23 May 2019 at 11:28, Andrew MacLeod <amacl...@redhat.com> wrote: > > 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 > 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. > > 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! > Thanks > Andrew