From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-1.mimecast.com (us-smtp-1.mimecast.com [205.139.110.61]) by sourceware.org (Postfix) with ESMTP id BC4A93851C0D for ; Tue, 18 Aug 2020 16:38:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org BC4A93851C0D Received: from mail-wr1-f69.google.com (mail-wr1-f69.google.com [209.85.221.69]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-540-mS9eTcqlN_K0j68pXZLVpw-1; Tue, 18 Aug 2020 12:38:16 -0400 X-MC-Unique: mS9eTcqlN_K0j68pXZLVpw-1 Received: by mail-wr1-f69.google.com with SMTP id f7so8423582wrs.8 for ; Tue, 18 Aug 2020 09:38:15 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:references:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=P+KKmHXm6s+76pnFks5W8E7pqJjBIzO6+B0QodQprY8=; b=IkxN4w1SafkDbU2BrgL7xDzB1BPJhZQkxhcGd+V1NLSXfVlCHyxaQKM3CivKKqjYqG SB9s5MW7OCPCESomz0hFyDX/waIMm7c3kYYSYv7RlBKvUZ/7jGCYoL4QjsN9G2XKjWrD d98PkosyDuQNyzbsj3IOUmp84j0f4gNqYX9uVl1jx/AbThh87HKhf2UXQ/bz0ZdP4EZZ AayFON+pfjzG+Ot1BSc75i/pqsAvtByBIiIclM5gNGjX//NWx9fGV5Si3J/AkmIrCd36 kovasd1xwCFcXG4W0mDoVd5i+Eopr/GHOvaqqdgat6/04l0ifRTR7QduoYrfEk7BLCGd wFoA== X-Gm-Message-State: AOAM531sOlTDdTkZJNRGc9Qa1SQIYnBsyKyifrUa2SQ05I34R3slOdBQ T5fx8N7TmczLT2suk81iybdEE3IeZQLr8MwKoZh/joi1WVKULRRu5kkIWVq+cAsTSP4Qrd3vsrc mPyPN3WyGZBr2QIx2rQ== X-Received: by 2002:a1c:9616:: with SMTP id y22mr743840wmd.100.1597768694834; Tue, 18 Aug 2020 09:38:14 -0700 (PDT) X-Google-Smtp-Source: ABdhPJx/ruojPRCpfrfjYr+dy4M3pA4CqVKtKkFqid+M2QwqznqFwp+S1C50qr6Wu9imRZcXAgTYtA== X-Received: by 2002:a1c:9616:: with SMTP id y22mr743825wmd.100.1597768694627; Tue, 18 Aug 2020 09:38:14 -0700 (PDT) Received: from abulafia.quesejoda.com ([46.6.241.178]) by smtp.gmail.com with ESMTPSA id i6sm33398124wrp.92.2020.08.18.09.38.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 18 Aug 2020 09:38:12 -0700 (PDT) Subject: Re: PING: Fwd: [PATCH 2/2] Decouple adjust_range_from_scev from vr_values and value_range_equiv. From: Aldy Hernandez To: Andrew MacLeod , 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> Message-ID: <8ee43a95-94f9-af71-7e92-75cb6315d55e@redhat.com> Date: Tue, 18 Aug 2020 18:38:09 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 In-Reply-To: <666093fc-bd2a-9816-0c53-b3373563f3ea@redhat.com> Content-Language: en-US X-Mimecast-Spam-Score: 0.001 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------8959F73B1862462BD7EDF8E1" X-Spam-Status: No, score=-12.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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 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 16:38:20 -0000 This is a multi-part message in MIME format. --------------8959F73B1862462BD7EDF8E1 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit And here's the patch without the sanity check. Aldy --------------8959F73B1862462BD7EDF8E1 Content-Type: text/x-patch; charset=UTF-8; name="curr.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="curr.patch" 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 *, + class loop *loop, gimple *stmt, tree var); + #endif /* GCC_VR_VALUES_H */ --------------8959F73B1862462BD7EDF8E1--