From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 55164 invoked by alias); 20 Jun 2019 03:05:32 -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 55131 invoked by uid 89); 20 Jun 2019 03:05:29 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-11.7 required=5.0 tests=AWL,BAYES_00,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=20th, experiences, Simply, anticipate X-HELO: mail-lf1-f54.google.com Received: from mail-lf1-f54.google.com (HELO mail-lf1-f54.google.com) (209.85.167.54) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 20 Jun 2019 03:05:25 +0000 Received: by mail-lf1-f54.google.com with SMTP id q26so1251372lfc.3 for ; Wed, 19 Jun 2019 20:05:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=kZgkVa0G5+j+htPblR/ADE4h++OO3KMUwA0OMmR1wms=; b=mQBgRLhpuz8f2+uuWNl0C+xJAUOH/g+BdHlULj4FlzlKiAMxDV5ttFBSoETiI2L1N2 I+NwPXymDP3T7ETkEd1sJSyHq6Haebjv1MOb/0sVEpbYSBUvpVtZDIjJKSTSUJgxi8pE sv6F/71eYJIEsGx1lryfW0aGgt56rbp4ktypLtNGHjIaq8nsjRvk60zkAeyelSmo498Y /1cYExvIxC4smJQU/H4sHjdfGb9WXwOBDXl55lzv5AedZIl3Ffgzsxw6AJKIeAn4/+cp pDnNLe5hZQUjEIxhWvSEblR4HqUtIuTL8xRufg5g73Hhe3P6wH/xF0lygUHM/bsW289p wXkQ== MIME-Version: 1.0 References: In-Reply-To: From: Kugan Vivekanandarajah Date: Thu, 20 Jun 2019 03:05:00 -0000 Message-ID: Subject: Re: On-Demand range technology [1/5] - Executive Summary To: Andrew MacLeod Cc: GCC , Jeff Law , Aldy Hernandez Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg00203.txt.bz2 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 wrote: > > Now that stage 1 has reopened, I=E2=80=99d like to reopen a discussion ab= out 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=E2=80=99s 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=E2=80=A6 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=E2=80=A6 Simply query the range of an ssa_name at a= ny > 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 > =E2=80=9Cssa-range=E2=80=9D) 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=E2=80=99t see similar speedups t= here. > > 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=E2=80=99d 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