From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 56973 invoked by alias); 1 Jun 2018 09:49:29 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 56636 invoked by uid 89); 1 Jun 2018 09:49:03 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.9 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,KAM_LINEPADDING,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=no version=3.3.2 spammy=H*r:sk:c23-v6s, integration, citing, deemed X-HELO: mail-ua0-f177.google.com Received: from mail-ua0-f177.google.com (HELO mail-ua0-f177.google.com) (209.85.217.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 01 Jun 2018 09:48:57 +0000 Received: by mail-ua0-f177.google.com with SMTP id c23-v6so10419819uan.3 for ; Fri, 01 Jun 2018 02:48:56 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=PoIiSlLB7TyrlegOpu2nGxIZQeDIK55Jo61XwQcSPVo=; b=owOSF9TmmNXe2vnnplXdu3DhK1me8azIOZmefTE18tHkvjlyjNLGAo+rCylMcE8Jcx o6bJlOn18UXOGT6obNWVxNeug1EervKYMRNnnXIQUeE3Cch56Dw1DccsB0e90UHsO07l XzXLNZct2e9kGFlwyOLUmL24IiFfSmdGThn8LWzG9K4mx00/0WAisJvFGpdcTAL3Sojb jmHY43iHj8jyvWMNWbP4VM85cFw16WINoUVk2Vt9ILuIle6aqbL5YoT2brrLYtevQ1/Y c1roSQ8fePeA8MJFiuSmBVyGMmzMmi4BjAOnOf/RsfqqPu85p9kHqX5e/SlGXwHvt+xW hV+A== X-Gm-Message-State: ALKqPwdAq0jsY/gAaAkRs8UPHwfSHSDHeFs3tqYL0F4eHr5Yu9kpiL9L H62D0Y46CWqk/nBFAjc2RSRlL9IUW6BE3p3aBnA= X-Google-Smtp-Source: ADUXVKJzkSLvKWaQeOKHeVs+AGydEw5yZn9ocvBspYk6BL0CsnUMT+POYK2oA1oCizGNo1ysGZwz8LkGgbFlVUMd0fU= X-Received: by 2002:ab0:17d2:: with SMTP id p18-v6mr6283939uaf.121.1527846534549; Fri, 01 Jun 2018 02:48:54 -0700 (PDT) MIME-Version: 1.0 References: <5607b582-639b-7517-e052-014fabfe0ad4@redhat.com> In-Reply-To: <5607b582-639b-7517-e052-014fabfe0ad4@redhat.com> From: Richard Biener Date: Fri, 01 Jun 2018 09:49:00 -0000 Message-ID: Subject: Re: Project Ranger To: Andrew MacLeod Cc: GCC Development , Aldy Hernandez , Jeff Law Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2018-06/txt/msg00004.txt.bz2 On Wed, May 30, 2018 at 1:53 AM Andrew MacLeod wrote: > > 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: >I'd like to introduce a project we've been working on for the past year an a half. > * 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: So what the wiki pages do not show is how contextual information is handled (and how that's done w/o dominators as the wiki page claims). That is, path_range_on_edge suggests that range information provided by the (all) controlling stmts of that edge are used when determining the range for 'name'. That's probably true for the 'stmt' variant as well. This leads me to guess that either the cache has to be O(number of SSA uses) size or a simple VRP pass implemented using Ranger querying ranges of all SSA ops for each stmt will require O(number of SSA uses) times analysis? One of the advantages of a DOM-style or SSA-with-ASSERT_EXPR pass is that the number of evaluations and the size of the cache isn't that way "unbound". On the WIKI page you mention edge info isn't cached yet - whatever that means ;) So I wonder what's the speed for doing FOR_EACH_BB_FN (bb) FOR_EACH_STMT (stmt) FOR_EACH_SSA_USE (stmt) path_range_on_stmt (..., SSA-USE, stmt); assuming that it takes into account controlling predicates. That's actually what EVRP does (within a DOM walk) given it tries to simplify each stmt with based on range info of the ops. > 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. More generally my remarks are still the same as with the irange introduction attempt. It's a no-no to add yet another set of range op primitives given we already have them implemented (with trees, yes...) in tre-vrp.c. The existing ones are already factored out to some extent so I expect you will continue that and split out the wide-int cases from those existing routines. Yes - that will not be very C++-ish - but who cares. Simply implement C-style workers, for example be inspired by the tree-ssa-ccp.c:bit_value_* routines implementing a kind of non-zero-bits operation primitives ontop of wide_ints (and also wrapping those with tree variants). For most of your on-demand uses I would expect a _much_ simpler and less heavy-weight approach to be extending the recently merged determine_value_range (I've pointed you to this multiple times in the past) to walk SSA def-use chains using the existing SSA on-the-side info as cache (yes, w/o use-granular contextual information). I also think that purely restricting yourself to wide-ints is a mistake - we do very well want to have range information for REAL_CSTs (or composite integers / reals). How do you think of extending Ranger to handle different kind of types? Eric already raised the issue of symbolic ranges. Yes, I do like having wide-int workers for ranges. Yes, I do like the idea of making ranges not restricted to single sub-ranges (didn't review the implementation). But those things should have been done on the existing code, not sticking sth completely new into GCC that cannot subsume the existing stuff. That's the road to maintainance hell which we unfortunately walk way too often with GCC :/ Btw, the original goal of EVRP was to get rid of the ASSERT_EXRP-style VRP pass once the threading bits it has are subsumed by the backwards threader. Does ranger at least allow that - get rid of the threading inside VRP without regressions? Just as a final note - open source development doesn't work like this, citing you "I'd like to introduce a project we've been working on for the past year an a half." - this simply provokes "reviews" like the above. Thanks, Richard. > Andrew, Aldy and Jeff > > > > > > > > > >