From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-1.mimecast.com (us-smtp-delivery-1.mimecast.com [207.211.31.120]) by sourceware.org (Postfix) with ESMTP id 015593850417 for ; Tue, 18 Aug 2020 17:05:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 015593850417 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-365-PN5f0y2LNQqMnWdThK0pPg-1; Tue, 18 Aug 2020 13:05:09 -0400 X-MC-Unique: PN5f0y2LNQqMnWdThK0pPg-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 0C376801AE5 for ; Tue, 18 Aug 2020 17:05:08 +0000 (UTC) Received: from [10.10.112.108] (ovpn-112-108.rdu2.redhat.com [10.10.112.108]) by smtp.corp.redhat.com (Postfix) with ESMTP id C9AED5C88A; Tue, 18 Aug 2020 17:05:03 +0000 (UTC) Subject: Re: PING: Fwd: [PATCH 2/2] Decouple adjust_range_from_scev from vr_values and value_range_equiv. To: Aldy Hernandez , gcc-patches , Jeff Law References: <20200804115501.583870-1-aldyh@redhat.com> <20200804115501.583870-3-aldyh@redhat.com> <1677b3a1-750b-fd38-97a6-e33c99f9867e@redhat.com> <666093fc-bd2a-9816-0c53-b3373563f3ea@redhat.com> <8ee43a95-94f9-af71-7e92-75cb6315d55e@redhat.com> From: Andrew MacLeod Message-ID: Date: Tue, 18 Aug 2020 13:05:00 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 MIME-Version: 1.0 In-Reply-To: <8ee43a95-94f9-af71-7e92-75cb6315d55e@redhat.com> Content-Language: en-US X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0.001 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 18 Aug 2020 17:05:14 -0000 On 8/18/20 12:38 PM, Aldy Hernandez wrote: > And here's the patch without the sanity check. > > Aldy That diff was difficult to read.. I had to apply the patch to really follow it :-P Anyway, yeah, this looks better.  effectively, you have   1) left the input range "vr" range merging in adjust-range_with_scev,   2) adjusted for the fact that the code extracted into "bounds_of_var_in_loop" now returns a min/max properly set, which sometimes  includes  basic symbolic expressions which the ranger can simply invoke range-ops on.   3) the only functional difference now is that we still fully call bounds_of_var_in_loop when "vr" is an anti-range.... whereas before we bailed early.  But you added comments that we may be able to utilize that under some circumstances this is OK. > > diff --git a/gcc/vr-values.c b/gcc/vr-values.c > index fe51a6faeb8..9b21441dff3 100644 > --- a/gcc/vr-values.c > +++ b/gcc/vr-values.c > @@ -1006,7 +1006,7 @@ vr_values::extract_range_from_comparison (value_range_equiv *vr, > overflow. */ > > static bool > -check_for_binary_op_overflow (vr_values *store, > +check_for_binary_op_overflow (range_query *store, > enum tree_code subcode, tree type, > tree op0, tree op1, bool *ovf) > { > @@ -1736,42 +1736,40 @@ compare_range_with_value (enum tree_code comp, const value_range *vr, > > gcc_unreachable (); > } > -/* Given a range VR, a LOOP and a variable VAR, determine whether it > - would be profitable to adjust VR using scalar evolution information > - for VAR. If so, update VR with the new limits. */ > > -void > -vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > - gimple *stmt, tree var) > +/* Given a VAR in STMT within LOOP, determine the bounds of the > + variable and store it in MIN/MAX and return TRUE. If no bounds > + could be determined, return FALSE. */ > + > +bool > +bounds_of_var_in_loop (tree *min, tree *max, range_query *query, > + class loop *loop, gimple *stmt, tree var) > { > - tree init, step, chrec, tmin, tmax, min, max, type, tem; > + tree init, step, chrec, tmin, tmax, type = TREE_TYPE (var); > enum ev_direction dir; > > - /* TODO. Don't adjust anti-ranges. An anti-range may provide > - better opportunities than a regular range, but I'm not sure. */ > - if (vr->kind () == VR_ANTI_RANGE) > - return; > - > chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); > > /* Like in PR19590, scev can return a constant function. */ > if (is_gimple_min_invariant (chrec)) > { > - vr->set (chrec); > - return; > + *min = *max = chrec; > + return true; > } > > if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) > - return; > + return false; > > init = initial_condition_in_loop_num (chrec, loop->num); > - tem = op_with_constant_singleton_value_range (init); > - if (tem) > - init = tem; > step = evolution_part_in_loop_num (chrec, loop->num); > - tem = op_with_constant_singleton_value_range (step); > - if (tem) > - step = tem; > + > + /* If INIT is an SSA with a singleton range, set INIT to said > + singleton, otherwise leave INIT alone. */ > + if (TREE_CODE (init) == SSA_NAME) > + query->get_value_range (init, stmt)->singleton_p (&init); > + /* Likewise for step. */ > + if (TREE_CODE (step) == SSA_NAME) > + query->get_value_range (step, stmt)->singleton_p (&step); > > /* If STEP is symbolic, we can't know whether INIT will be the > minimum or maximum value in the range. Also, unless INIT is > @@ -1780,7 +1778,7 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > if (step == NULL_TREE > || !is_gimple_min_invariant (step) > || !valid_value_p (init)) > - return; > + return false; > > dir = scev_direction (chrec); > if (/* Do not adjust ranges if we do not know whether the iv increases > @@ -1789,9 +1787,8 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > /* ... or if it may wrap. */ > || scev_probably_wraps_p (NULL_TREE, init, step, stmt, > get_chrec_loop (chrec), true)) > - return; > + return false; > > - type = TREE_TYPE (var); > if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) > tmin = lower_bound_in_type (type, type); > else > @@ -1806,7 +1803,7 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > if (TREE_CODE (step) == INTEGER_CST > && is_gimple_val (init) > && (TREE_CODE (init) != SSA_NAME > - || get_value_range (init, stmt)->kind () == VR_RANGE)) > + || query->get_value_range (init, stmt)->kind () == VR_RANGE)) > { > widest_int nit; > > @@ -1829,21 +1826,29 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > && (sgn == UNSIGNED > || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0))) > { > - value_range_equiv maxvr; > - tem = wide_int_to_tree (TREE_TYPE (init), wtmp); > - extract_range_from_binary_expr (&maxvr, PLUS_EXPR, > - TREE_TYPE (init), init, tem); > + value_range maxvr, vr0, vr1; > + if (TREE_CODE (init) == SSA_NAME) > + vr0 = *(query->get_value_range (init, stmt)); > + else if (is_gimple_min_invariant (init)) > + vr0.set (init); > + else > + vr0.set_varying (TREE_TYPE (init)); > + tree tem = wide_int_to_tree (TREE_TYPE (init), wtmp); > + vr1.set (tem, tem); > + range_fold_binary_expr (&maxvr, PLUS_EXPR, > + TREE_TYPE (init), &vr0, &vr1); > + > /* Likewise if the addition did. */ > if (maxvr.kind () == VR_RANGE) > { > value_range initvr; > > if (TREE_CODE (init) == SSA_NAME) > - initvr = *(get_value_range (init, stmt)); > + initvr = *(query->get_value_range (init, stmt)); > else if (is_gimple_min_invariant (init)) > initvr.set (init); > else > - return; > + return false; > > /* Check if init + nit * step overflows. Though we checked > scev {init, step}_loop doesn't wrap, it is not enough > @@ -1853,7 +1858,7 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > && compare_values (maxvr.min (), initvr.min ()) != -1) > || (dir == EV_DIR_GROWS > && compare_values (maxvr.max (), initvr.max ()) != 1)) > - return; > + return false; > > tmin = maxvr.min (); > tmax = maxvr.max (); > @@ -1862,66 +1867,62 @@ vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > } > } > > - if (vr->varying_p () || vr->undefined_p ()) > - { > - min = tmin; > - max = tmax; > + *min = tmin; > + *max = tmax; > + if (dir == EV_DIR_DECREASES) > + *max = init; > + else > + *min = init; > > - /* For VARYING or UNDEFINED ranges, just about anything we get > - from scalar evolutions should be better. */ > + /* Even for valid range info, sometimes overflow flag will leak in. > + As GIMPLE IL should have no constants with TREE_OVERFLOW set, we > + drop them. */ > + if (TREE_OVERFLOW_P (*min)) > + *min = drop_tree_overflow (*min); > + if (TREE_OVERFLOW_P (*max)) > + *max = drop_tree_overflow (*max); > > - if (dir == EV_DIR_DECREASES) > - max = init; > - else > - min = init; > - } > - else if (vr->kind () == VR_RANGE) > - { > - min = vr->min (); > - max = vr->max (); > + gcc_checking_assert (compare_values (*min, *max) != 1); > + return true; > +} > + > +/* Given a range VR, a LOOP and a variable VAR, determine whether it > + would be profitable to adjust VR using scalar evolution information > + for VAR. If so, update VR with the new limits. */ > > - if (dir == EV_DIR_DECREASES) > +void > +vr_values::adjust_range_with_scev (value_range_equiv *vr, class loop *loop, > + gimple *stmt, tree var) > +{ > + tree min, max; > + if (bounds_of_var_in_loop (&min, &max, this, loop, stmt, var)) > + { > + if (vr->undefined_p () || vr->varying_p ()) > { > - /* INIT is the maximum value. If INIT is lower than VR->MAX () > - but no smaller than VR->MIN (), set VR->MAX () to INIT. */ > - if (compare_values (init, max) == -1) > - max = init; > + /* For VARYING or UNDEFINED ranges, just about anything we get > + from scalar evolutions should be better. */ > + vr->update (min, max); > + } > + else if (vr->kind () == VR_RANGE) > + { > + /* Start with the input range... */ > + tree vrmin = vr->min (); > + tree vrmax = vr->max (); > > - /* According to the loop information, the variable does not > - overflow. */ > - if (compare_values (min, tmin) == -1) > - min = tmin; > + /* ...and narrow it down with what we got from SCEV. */ > + if (compare_values (min, vrmin) == 1) > + vrmin = min; > + if (compare_values (max, vrmax) == -1) > + vrmax = max; > > + vr->update (vrmin, vrmax); > } > - else > + else if (vr->kind () == VR_ANTI_RANGE) > { > - /* If INIT is bigger than VR->MIN (), set VR->MIN () to INIT. */ > - if (compare_values (init, min) == 1) > - min = init; > - > - if (compare_values (tmax, max) == -1) > - max = tmax; > + /* ?? As an enhancement, if VR, MIN, and MAX are constants, one > + could just intersect VR with a range of [MIN,MAX]. */ > } > } > - else > - return; > - > - /* If we just created an invalid range with the minimum > - greater than the maximum, we fail conservatively. > - This should happen only in unreachable > - parts of code, or for invalid programs. */ > - if (compare_values (min, max) == 1) > - return; > - > - /* Even for valid range info, sometimes overflow flag will leak in. > - As GIMPLE IL should have no constants with TREE_OVERFLOW set, we > - drop them. */ > - if (TREE_OVERFLOW_P (min)) > - min = drop_tree_overflow (min); > - if (TREE_OVERFLOW_P (max)) > - max = drop_tree_overflow (max); > - > - vr->update (min, max); > } > > /* Dump value ranges of all SSA_NAMEs to FILE. */ > @@ -4216,7 +4217,7 @@ simplify_using_ranges::two_valued_val_range_p (tree var, tree *a, tree *b) > return false; > } > > -simplify_using_ranges::simplify_using_ranges (vr_values *store) > +simplify_using_ranges::simplify_using_ranges (range_query *store) > : store (store) > { > to_remove_edges = vNULL; > diff --git a/gcc/vr-values.h b/gcc/vr-values.h > index 330b4605e39..7051e13fc00 100644 > --- a/gcc/vr-values.h > +++ b/gcc/vr-values.h > @@ -22,16 +22,26 @@ along with GCC; see the file COPYING3. If not see > > #include "value-range-equiv.h" > > +// Abstract class to return a range for a given SSA. > + > +class range_query > +{ > +public: > + virtual const value_range_equiv *get_value_range (const_tree, > + gimple * = NULL) = 0; > + virtual ~range_query () { } > +}; > + > // Class to simplify a statement using range information. > // > // The constructor takes a full vr_values, but all it needs is > // get_value_range() from it. This class could be made to work with > // any range repository. > > -class simplify_using_ranges > +class simplify_using_ranges : public range_query > { > public: > - simplify_using_ranges (class vr_values *); > + simplify_using_ranges (class range_query *); > ~simplify_using_ranges (); > bool simplify (gimple_stmt_iterator *); > > @@ -44,7 +54,7 @@ public: > > private: > const value_range_equiv *get_value_range (const_tree op, > - gimple *stmt = NULL); > + gimple *stmt = NULL) OVERRIDE; > bool simplify_truth_ops_using_ranges (gimple_stmt_iterator *, gimple *); > bool simplify_div_or_mod_using_ranges (gimple_stmt_iterator *, gimple *); > bool simplify_abs_using_ranges (gimple_stmt_iterator *, gimple *); > @@ -79,7 +89,7 @@ private: > > vec to_remove_edges; > vec to_update_switch_stmts; > - class vr_values *store; > + class range_query *store; > }; > > /* The VR_VALUES class holds the current view of range information > @@ -96,7 +106,7 @@ private: > gets attached to an SSA_NAME. It's unclear how useful that global > information will be in a world where we can compute context sensitive > range information fast or perform on-demand queries. */ > -class vr_values > +class vr_values : public range_query > { > public: > vr_values (void); > @@ -177,4 +187,7 @@ extern tree get_output_for_vrp (gimple *); > // FIXME: Move this to tree-vrp.c. > void simplify_cond_using_ranges_2 (class vr_values *, gcond *); > > +extern bool bounds_of_var_in_loop (tree *min, tree *max, range_query *,