From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 57044 invoked by alias); 3 Sep 2018 06:58:46 -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 56920 invoked by uid 89); 3 Sep 2018 06:58:45 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-6.9 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_2,KAM_LAZY_DOMAIN_SECURITY,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy=apologize, carried, forwarded, SIGN X-HELO: mail-wm0-f52.google.com Received: from mail-wm0-f52.google.com (HELO mail-wm0-f52.google.com) (74.125.82.52) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 03 Sep 2018 06:58:42 +0000 Received: by mail-wm0-f52.google.com with SMTP id c14-v6so10347327wmb.4 for ; Sun, 02 Sep 2018 23:58:42 -0700 (PDT) Return-Path: Received: from abulafia.quesejoda.com (247.red-79-147-188.dynamicip.rima-tde.net. [79.147.188.247]) by smtp.gmail.com with ESMTPSA id q5-v6sm21787404wmd.29.2018.09.02.23.58.39 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 02 Sep 2018 23:58:39 -0700 (PDT) Subject: PING: Re: lightweight class to wide int ranges in VRP and friends References: <6c1f90ae-d77a-4ed6-e6fc-9ef0334cedcb@redhat.com> To: gcc-patches , Richard Biener From: Aldy Hernandez X-Forwarded-Message-Id: <6c1f90ae-d77a-4ed6-e6fc-9ef0334cedcb@redhat.com> Message-ID: Date: Mon, 03 Sep 2018 06:58:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: <6c1f90ae-d77a-4ed6-e6fc-9ef0334cedcb@redhat.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2018-09/txt/msg00079.txt.bz2 -------- Forwarded Message -------- Subject: Re: lightweight class to wide int ranges in VRP and friends Date: Fri, 24 Aug 2018 13:40:29 -0400 From: Aldy Hernandez To: Richard Biener CC: GCC Patches On 08/24/2018 06:32 AM, Richard Biener wrote: > On Wed, Aug 15, 2018 at 7:31 PM Aldy Hernandez wrote: >> >> I kept seeing the same patterns over and over in all this re-factoring: >> >> 1. extract value_range constants into pairs of wide ints >> >> 2. mimic symbolics as [-MIN, +MAX] (most of the time :)) >> >> 3. perform some wide int operation on the wide int range >> >> 4. convert back to a value range >> >> So I've decided to clean this up even more. Instead of passing a pair >> of wide ints plus sign, precision, and god knows what to every >> wide_int_range_* function, I've implemented a lighweight class >> (wi_range) for a pair of wide ints. It is not meant for long term >> storage, but even so its footprint is minimal. >> >> The only extra bits are another 64-bit word per pair for keeping >> attributes such as precision, sign, overflow_wraps, and a few other >> things we'll need shortly. In reality we only need one set of >> attributes for both sets of pairs, so we waste one 64-bit word. I don't >> care. They're short lived, and the resulting code looks an awful lot >> nicer. For example, the shift code gets rewritten from this: >> >> if (range_int_cst_p (&vr1) >> && !vrp_shift_undefined_p (vr1, prec)) >> { >> if (code == RSHIFT_EXPR) >> { >> if (vr0.type != VR_RANGE || symbolic_range_p (&vr0)) >> { >> vr0.type = type = VR_RANGE; >> vr0.min = vrp_val_min (expr_type); >> vr0.max = vrp_val_max (expr_type); >> } >> extract_range_from_multiplicative_op (vr, code, &vr0, &vr1); >> return; >> } >> else if (code == LSHIFT_EXPR >> && range_int_cst_p (&vr0)) >> { >> wide_int res_lb, res_ub; >> if (wide_int_range_lshift (res_lb, res_ub, sign, prec, >> wi::to_wide (vr0.min), >> wi::to_wide (vr0.max), >> wi::to_wide (vr1.min), >> wi::to_wide (vr1.max), >> TYPE_OVERFLOW_UNDEFINED (expr_type), >> TYPE_OVERFLOW_WRAPS (expr_type))) >> { >> min = wide_int_to_tree (expr_type, res_lb); >> max = wide_int_to_tree (expr_type, res_ub); >> set_and_canonicalize_value_range (vr, VR_RANGE, >> min, max, NULL); >> return; >> } >> } >> } >> set_value_range_to_varying (vr); >> >> into this: >> >> wi_range w0 (&vr0, expr_type); >> wi_range w1 (&vr1, expr_type); >> if (!range_int_cst_p (&vr1) >> || wi_range_shift_undefined_p (w1) >> || (code == LSHIFT_EXPR >> && !range_int_cst_p (&vr0))) >> { >> vr->set_varying (); >> return; >> } >> bool success; >> if (code == RSHIFT_EXPR) >> success = wi_range_multiplicative_op (res, code, w0, w1); >> else >> success = wi_range_lshift (res, w0, w1); >> >> if (success) >> vr->set_and_canonicalize (res, expr_type); >> else >> vr->set_varying (); >> return; > > not sure whether I like the munging of lshift and right shift (what exactly gets > done is less clear in your version ...). Having a light-weigth class for > the wi_range_ parameters is nice though. No worries. I'm not emotionally attached to munging them :). > >> I also munged together the maybe/mustbe nonzero_bits into one structure. >> >> Finally, I've pontificated that wide_int_range_blah is too much typing. >> Everyone's RSI will thank me for rewriting the methods as wi_range_blah. >> >> I've tried to keep the functionality changes to a minimum. However, >> there are some slight changes where I treat symbolics and VR_VARYING as >> [MIN, MAX] and let the constant code do its thing. It is considerably >> easier to read. >> >> I am finally happy with the overall direction of this. If this and the >> last one are acceptable, I think I only need to clean MIN/MAX_EXPR and >> ABS_EXPR and I'm basically done with what I need going forward. >> >> Phew... >> >> How does this look? > > +struct wi_range > +{ > + wide_int min; > + wide_int max; > + /* This structure takes one additional 64-bit word apart from the > + min/max bounds above. It is laid out so that PRECISION and SIGN > + can be accessed without any bit twiddling, since they're the most > + commonly accessed fields. */ > + unsigned short precision; > + bool empty_p:1; > + bool pointer_type_p:1; > + bool overflow_wraps:1; > + bool overflow_undefined:1; > + signop sign; > > isn't precision already available in min.get_precision () which is > required to be equal to max.get_precision ()? Indeed. Good point. > > + wi_range () { empty_p = false; } > > true I suppose? Better not allow default construction? OK. > > empty_p doesn't seem to be documented, nor is pointer_type_p > or why that is necessary - maybe simply store a tree type > instead all of the bits? I was trying to avoid dereferencing another pointer by perhaps flattening out the needed bits, but again-- not emotionally attached. Easier for me... > > +/* A structure to pass maybe and mustbe nonzero bitmasks. This is for > + use in wi_range_set_zero_nonzero_bits and friends. */ > + > +struct maybe_nonzero_bits > +{ > + /* If some bit is unset, it means that for all numbers in the range > + the bit is 0, otherwise it might be 0 or 1. */ > + wide_int may_be; > + > + /* If some bit is set, it means that for all numbers in the range > + the bit is 1, otherwise it might be 0 or 1. */ > + wide_int must_be; > }; > > eh - multiple changes in one patch ... Well, is it? I'm trying to avoid passing tons of things to the wide_int_range_* functions, and that includes wide ints and the nonzero bit pairs. Could I please leave these in the patch? > > @@ -52,6 +54,58 @@ struct GTY((for_user)) value_range > > /* Dump value range to stderr. */ > void dump (); > + > + void set (const wi_range &r, tree type); > + void set_and_canonicalize (const wi_range &r, tree type); > + void set_undefined (); > + void set_varying (); > +}; > > likewise ... you introduce those methods but not use them consistently. > Please leave out this change (I would object to this kind of change > if carried out through). I was really avoiding having to convert every caller. But really, why would you object even if carried out through? > > +/* Construct a new range from the contents of a value_range. Varying > + or symbolic ranges are normalized to the entire possible range. */ > + > +inline > +wi_range::wi_range (value_range *vr, tree type) > +{ > + precision = TYPE_PRECISION (type); > + pointer_type_p = POINTER_TYPE_P (type); > + overflow_wraps = TYPE_OVERFLOW_WRAPS (type); > + overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type); > + sign = TYPE_SIGN (type); > + empty_p = false; > + if (vr->type == VR_VARYING || symbolic_range_p (vr)) > + { > + min = wi::min_value (precision, sign); > + max = wi::max_value (precision, sign); > + } > + else if (vr->type == VR_RANGE) > + { > + min = wi::to_wide (vr->min); > + max = wi::to_wide (vr->max); > + } > + else > + gcc_unreachable (); > +} > > What about VR_ANTI_RANGE? Note the above doesn't exactly look > "light-weight". Yes, I should handle anti range, or ICE or something, considering the pain it was to find the anti range problem with the POINTER_PLUS_EXPR code recently. Is "not exactly light-weight" an objection, or just a btw type of comment :)? Would it make it less painful if we stored the entire type in the wi_range as mentioned earlier? > > -/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in > - [WMIN,WMAX]. */ > +/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in RES. > + Return TRUE if operation succeeded. */ > > did I say multiple changes...? I think this isn't a good one given "succeed" > doesn't imply that if not the result is UNDEFINED ... Point taken, but hey I can't read your responses as you're typing them ;-). > > As said above the shift handlign structrue is now unreadable :/ Given we do > different things for lshift vs. rshift it makes sense to simply split Unreadable? Surely you jest! As opposed to the super-readable stuff in VRP before? Come on! But I can split the shifts. That's not a problem :). > > else if (code == RSHIFT_EXPR > || code == LSHIFT_EXPR) > { > > even if that means duplicating a few lines. > > Just to remind you review (and approval) isn't easier if you put unrelated stuff > into a patch ;) If you mention it three times in a review and I apologize three times, are we at peace now? :-P Aldy