From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21341 invoked by alias); 24 Jun 2019 13:25:06 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 21332 invoked by uid 89); 24 Jun 2019 13:25:06 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-4.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_2,KAM_ASCII_DIVIDERS,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=mails, transparent, HTo:U*aldyh, virtually X-HELO: mail-lj1-f169.google.com Received: from mail-lj1-f169.google.com (HELO mail-lj1-f169.google.com) (209.85.208.169) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 24 Jun 2019 13:25:04 +0000 Received: by mail-lj1-f169.google.com with SMTP id 131so12614036ljf.4 for ; Mon, 24 Jun 2019 06:25:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=rmjorJBwYyoLDY2OQVHnY6mqfxrAtZSx0kJ11ENgxE0=; b=UHYIKohJErZrWoG4Ey3EUHH7b2SYHi44k8ELXa+ThDGMXy3wBtp2GWFVI7N1NkhE57 werO2CFgMoOX8yPWfTiF6jnQYRUyLCuZQkQKgVXZLU7fpp6NNTKzU6ZjuH1LThNebiwS feHgeDhmrnxg4Qg6jVu6YR9KOFDA/uaXM87qli0dEBfVmqm4m0oiaIkxc8H2ejgP6xuX JVr80Fm2cHjZmQmfm/I+bra+faK5pK6yae+IZaKotVeBRLcI+2bM04q9dp5jduMdZ3SH gc4q2f5qL48m8SNvvH+EQefMXvoMMJJQEZvNXDuhTH7jcUP6DlX6zi+4KvkYD0WlPhXR THJQ== MIME-Version: 1.0 References: <684d495e-d931-ab7f-672e-1ccd13f1bc00@redhat.com> In-Reply-To: <684d495e-d931-ab7f-672e-1ccd13f1bc00@redhat.com> From: Richard Biener Date: Mon, 24 Jun 2019 13:25:00 -0000 Message-ID: Subject: Re: value_range and irange unification To: Aldy Hernandez Cc: gcc-patches , Andrew MacLeod Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2019-06/txt/msg01445.txt.bz2 On Fri, Jun 21, 2019 at 1:41 PM Aldy Hernandez wrote: > > Hi Richard. Hi folks. > > In order to unify the APIs for value_range and irange, we'd like to make > some minor changes to value_range. We believe most of these changes > could go in now, and would prefer so, to get broader testing and > minimize the plethora of changes we drag around on our branch. > > First, introduce a type for VR_VARYING and VR_UNDEFINED. > -------------------------------------------------------- > > irange utilizes 0 or more sub-ranges to represent a range, and VARYING > is simply one subrange [MIN, MAX]. value_range represents this with > VR_VARYING, and since there is no type associated with it, we cannot > calculate the lower and upper bounds for the range. There is also a > lack of canonicalness in value range in that VR_VARYING and [MIN, MAX] > are two different representations of the same value. > > We tried to adjust irange to not associate a type with the empty range > [] (representing undefined), but found we were unable to perform all > operations properly. In particular, we cannot invert an empty range. > i.e. invert ( [] ) should produce [MIN, MAX]. Again, we need to have a > type associated with this empty range. > > We'd like to tweak value_range so that set_varying() and set_undefined() > both take a type, and then always set the min/max fields based on that > type. This takes no additional memory in the structure, and is > virtually transparent to all the existing uses of value_range. > > This allows: > 1) invert to be implemented properly for both VARYING and UNDEFINED > by simply changing one to the other. > 2) the type() method to always work without any special casing by > simply returning TREE_TYPE(min) > 3) the new incoming bounds() routines to work trivially for these > cases as well (lbound/ubound, num_pairs(), etc). > > This functionality is provided in the first attached patch. > > Note, the current implementation sets min/max to TREE_TYPE, not to > TYPE_MIN/MAX_VALUE. We can fix this if preferred. How does this work with value_range * vr_values::get_value_range (const_tree var) { static const value_range vr_const_varying (VR_VARYING, NULL, NULL); ... /* If we query the range for a new SSA name return an unmodifiable VARYING. We should get here at most from the substitute-and-fold stage which will never try to change values. */ if (ver >= num_vr_values) return CONST_CAST (value_range *, &vr_const_varying); ? > Second, enforce canonicalization at value_range build time. > ----------------------------------------------------------- > > As discussed above, value_range has multiple representations for the > same range. For instance, ~[0,0] is the same as [1,MAX] in unsigned and > [MIN, MAX] is really varying, among others. We found it quite difficult > to make things work, with multiple representations for a given range. > Canonicalizing at build time solves this, as well as removing explicit > set_and_canonicalize() calls throughout. Furthermore, it avoids some > special casing in VRP. > > Along with canonicalizing, we also enforce the existing value_range API > more strongly. For instance, we don't allow setting equivalences for > either VR_VARYING or VR_UNDEFINED. > > This functionality is provided in the second patch. Fair enough. Didn't look at the patch yet, sending separate mails would have been prefered - or are the patches not independent of each other? Note canonicalization performs quite some work so a shortcut set () with just checking the input is already canonicalized would be nice? I wonder you still have anti-ranges since you can handle > 1 subranges in ranger? > Third, irange on value_range implementation. > --------------------------------------------- > > The third attached patch shows how we use the above two to implement > irange using value_ranges. value_range would be a drop-in replacement > for irange, by just doing the following in range.h: > > +// Enable this to implement irange piggybacking on value_range. > +#define IRANGE_WITH_VALUE_RANGE 1 > + > +#if IRANGE_WITH_VALUE_RANGE > +#include "tree-vrp.h" > +typedef value_range_base irange; > +typedef value_range_storage irange_storage; > +#define IRANGE_PLAIN VR_RANGE > +#define IRANGE_INVERSE VR_ANTI_RANGE > +#else > ... > > The additions to the value_range API would be mostly the following (full > details in the third attached patch): > > + value_range_base (tree, tree); > + value_range_base (value_range_kind, > + tree type, const wide_int &, const wide_int &); > + value_range_base (tree type, const wide_int &, const wide_int &); > + value_range_base (tree type, const value_range_storage *); > + value_range_base (tree type); > > void set (value_range_kind, tree, tree); > void set (tree); > @@ -77,7 +86,25 @@ public: > bool singleton_p (tree *result = NULL) const; > void dump (FILE *) const; > > + /* Support machinery for irange. */ > + static const unsigned int m_max_pairs = 2; > + static bool supports_type_p (tree type); > + static bool supports_ssa_p (tree ssa); > + static bool supports_p (tree expr); > + void cast (tree); > + bool contains_p (tree) const; > + unsigned num_pairs () const; > + wide_int lower_bound (unsigned = 0) const; > + wide_int upper_bound (unsigned) const; > + wide_int upper_bound () const; > + void invert (); > + void dump () const { dump (stderr); } > + // FIXME: Perhaps rewrite the irange versions to use pointers instead. > + void union_ (const value_range_base &); > + void intersect (const value_range_base &); > + > protected: > + value_range_base normalize_symbolics () const; > > There are no regressions from mainline, and we are catching every one of > our internal ranger tests, with the exception of two that require more > than 2 sub-ranges to work. i.e. Not a regression from mainline-- just > new functionality we can't get with the limited sub-ranges in value_range. > > Note: Please ignore the value_range_base::normalize_symbolics stuff. > It's likely to go through multiple revisions as Andrew gets the ranger > to deal with symbolics. > > Finally > ------- > > All these patches are already in our branch, and irange with value_range > can be enabled by #define IRANGE_WITH_VALUE_RANGE 1. > > With these changes, we can successfully build and run the ranger branch > using value_range in place of irange, which indicates a successful API > merge. > > After some minor cleanups, I would like to contribute at least the first > two patches to trunk (VARYING types and the enforced canonicalization). > This will enable us to move forward with trying to integrate the > range-ops code which makes heavy use of the subrange interface, and > allows for broader testing instead of dropping everything in one-go. > These two patches stand on their own independently, and IMO provide > useful functionality right now. Works for me. Please send any such patches separately (after cleanup) > I would ideally like to contribute the third patch to mainline, but I do > understand that it currently has no users... although I could rewrite > bits of tree-vrp to use these new functions (lower_bound, upper_bound, > etc), thus providing a use case ??. However, I do understand if you'd > prefer to keep this last patch on the branch. I'd prefer to keep the last one on the branch indeed. Richard. > Thoughts? > > Aldy (and Andrew)