From patchwork Mon May 1 06:29:03 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1775421 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=do7CSnJG; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Q8tfW4TKWz1ydX for ; Mon, 1 May 2023 16:32:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9B1373882AF9 for ; Mon, 1 May 2023 06:32:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9B1373882AF9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682922721; bh=YStZixPr4AIW01MK3flYVbQ6y4Z06mLVI7u64/zIaqo=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=do7CSnJGfBw/GK0rOY3+noEQVdMyHneLcJBU/PNbTKdmNey6UA6DFpBzx/apsWap4 pQQkemIc6r88B9lZc80DTSW3SuMWuI6jBIo1Zr+3iJ7BD6PEYNwOpDCAsqXDybuSDW RoOsScmynKTKhnAIbCQjc1aGCVFw9zMeSSluqFhQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id D7EF33858416 for ; Mon, 1 May 2023 06:29:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D7EF33858416 Received: from mimecast-mx02.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-354-A5LGy5ckMhWgdkNH1gqR5w-1; Mon, 01 May 2023 02:29:14 -0400 X-MC-Unique: A5LGy5ckMhWgdkNH1gqR5w-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.rdu2.redhat.com [10.11.54.8]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 1942B3801FEB for ; Mon, 1 May 2023 06:29:14 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.81]) by smtp.corp.redhat.com (Postfix) with ESMTPS id A4BF5C16024; Mon, 1 May 2023 06:29:13 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.17.1/8.17.1) with ESMTPS id 3416TCsQ564873 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Mon, 1 May 2023 08:29:12 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 3416TCpv564872; Mon, 1 May 2023 08:29:12 +0200 To: GCC patches Cc: Andrew MacLeod , Aldy Hernandez Subject: [COMMITTED] Rewrite bounds_of_var_in_loop() to use ranges. Date: Mon, 1 May 2023 08:29:03 +0200 Message-Id: <20230501062906.564803-9-aldyh@redhat.com> In-Reply-To: <20230501062906.564803-1-aldyh@redhat.com> References: <20230501062906.564803-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.8 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Little by little, bounds_of_var_in_loop() has grown into an unmaintainable mess. This patch rewrites the code to use the relevant APIs as well as refactor it to make it more readable. gcc/ChangeLog: * gimple-range-fold.cc (tree_lower_bound): Delete. (tree_upper_bound): Delete. (vrp_val_max): Delete. (vrp_val_min): Delete. (fold_using_range::range_of_ssa_name_with_loop_info): Call range_of_var_in_loop. * vr-values.cc (valid_value_p): Delete. (fix_overflow): Delete. (get_scev_info): New. (bounds_of_var_in_loop): Refactor into... (induction_variable_may_overflow_p): ...this, (range_from_loop_direction): ...and this, (range_of_var_in_loop): ...and this. * vr-values.h (bounds_of_var_in_loop): Delete. (range_of_var_in_loop): New. --- gcc/gimple-range-fold.cc | 80 +---------- gcc/vr-values.cc | 282 ++++++++++++++++----------------------- gcc/vr-values.h | 4 +- 3 files changed, 117 insertions(+), 249 deletions(-) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 1b76e6e02a3..96cbd799488 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -944,60 +944,6 @@ fold_using_range::range_of_cond_expr (vrange &r, gassign *s, fur_source &src) return true; } -// Return the lower bound of R as a tree. - -static inline tree -tree_lower_bound (const vrange &r, tree type) -{ - if (is_a (r)) - return wide_int_to_tree (type, as_a (r).lower_bound ()); - // ?? Handle floats when they contain endpoints. - return NULL; -} - -// Return the upper bound of R as a tree. - -static inline tree -tree_upper_bound (const vrange &r, tree type) -{ - if (is_a (r)) - return wide_int_to_tree (type, as_a (r).upper_bound ()); - // ?? Handle floats when they contain endpoints. - return NULL; -} - -// Return the maximum value for TYPE. - -static inline tree -vrp_val_max (const_tree type) -{ - if (INTEGRAL_TYPE_P (type) - || POINTER_TYPE_P (type)) - return wide_int_to_tree (const_cast (type), irange_val_max (type)); - if (frange::supports_p (type)) - { - REAL_VALUE_TYPE r = frange_val_max (type); - return build_real (const_cast (type), r); - } - return NULL_TREE; -} - -// Return the minimum value for TYPE. - -static inline tree -vrp_val_min (const_tree type) -{ - if (INTEGRAL_TYPE_P (type) - || POINTER_TYPE_P (type)) - return wide_int_to_tree (const_cast (type), irange_val_min (type)); - if (frange::supports_p (type)) - { - REAL_VALUE_TYPE r = frange_val_min (type); - return build_real (const_cast (type), r); - } - return NULL_TREE; -} - // If SCEV has any information about phi node NAME, return it as a range in R. void @@ -1006,30 +952,8 @@ fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name, fur_source &src) { gcc_checking_assert (TREE_CODE (name) == SSA_NAME); - tree min, max, type = TREE_TYPE (name); - if (bounds_of_var_in_loop (&min, &max, src.query (), l, phi, name)) - { - if (!is_gimple_constant (min)) - { - if (src.query ()->range_of_expr (r, min, phi) && !r.undefined_p ()) - min = tree_lower_bound (r, type); - else - min = vrp_val_min (type); - } - if (!is_gimple_constant (max)) - { - if (src.query ()->range_of_expr (r, max, phi) && !r.undefined_p ()) - max = tree_upper_bound (r, type); - else - max = vrp_val_max (type); - } - if (min && max) - { - r.set (min, max); - return; - } - } - r.set_varying (type); + if (!range_of_var_in_loop (r, name, l, phi, src.query ())) + r.set_varying (TREE_TYPE (name)); } // ----------------------------------------------------------------------- diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc index 31df6b85ce6..86c1bf8ebc6 100644 --- a/gcc/vr-values.cc +++ b/gcc/vr-values.cc @@ -52,23 +52,6 @@ along with GCC; see the file COPYING3. If not see #include "range-op.h" #include "gimple-range.h" -/* Returns true if EXPR is a valid value (as expected by compare_values) -- - a gimple invariant, or SSA_NAME +- CST. */ - -static bool -valid_value_p (tree expr) -{ - if (TREE_CODE (expr) == SSA_NAME) - return true; - - if (TREE_CODE (expr) == PLUS_EXPR - || TREE_CODE (expr) == MINUS_EXPR) - return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME - && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST); - - return is_gimple_min_invariant (expr); -} - /* Return true if op is in a boolean [0, 1] value-range. */ bool @@ -184,178 +167,139 @@ check_for_binary_op_overflow (range_query *query, return true; } -static inline void -fix_overflow (tree *min, tree *max) +/* Set INIT, STEP, and DIRECTION the the corresponding values of NAME + within LOOP, and return TRUE. Otherwise return FALSE, and set R to + the conservative range of NAME within the loop. */ + +static bool +get_scev_info (vrange &r, tree name, gimple *stmt, class loop *l, + tree &init, tree &step, enum ev_direction &dir) { - /* 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); - - gcc_checking_assert (compare_values (*min, *max) != 1); + tree ev = analyze_scalar_evolution (l, name); + tree chrec = instantiate_parameters (l, ev); + tree type = TREE_TYPE (name); + if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) + { + r.set_varying (type); + return false; + } + if (is_gimple_min_invariant (chrec)) + { + if (is_gimple_constant (chrec)) + r.set (chrec, chrec); + else + r.set_varying (type); + return false; + } + + init = initial_condition_in_loop_num (chrec, l->num); + step = evolution_part_in_loop_num (chrec, l->num); + if (!init || !step) + { + r.set_varying (type); + return false; + } + dir = scev_direction (chrec); + if (dir == EV_DIR_UNKNOWN + || scev_probably_wraps_p (NULL, init, step, stmt, + get_chrec_loop (chrec), true)) + { + r.set_varying (type); + return false; + } + return true; } -/* 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. */ +/* Return TRUE if STEP * NIT may overflow when calculated in TYPE. */ -bool -bounds_of_var_in_loop (tree *min, tree *max, range_query *query, - class loop *loop, gimple *stmt, tree var) +static bool +induction_variable_may_overflow_p (tree type, + const wide_int &step, const widest_int &nit) { - tree init, step, chrec, tmin, tmax, type = TREE_TYPE (var); - enum ev_direction dir; - int_range<2> r; + wi::overflow_type ovf; + signop sign = TYPE_SIGN (type); + widest_int max_step = wi::mul (widest_int::from (step, sign), + nit, sign, &ovf); - chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); + if (ovf || !wi::fits_to_tree_p (max_step, type)) + return true; - /* Like in PR19590, scev can return a constant function. */ - if (is_gimple_min_invariant (chrec)) - { - *min = *max = chrec; - fix_overflow (min, max); - return true; - } + /* For a signed type we have to check whether the result has the + expected signedness which is that of the step as number of + iterations is unsigned. */ + return (sign == SIGNED + && wi::gts_p (max_step, 0) != wi::gts_p (step, 0)); +} - if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) - return false; +/* Set R to the range from BEGIN to END, assuming the direction of the + loop is DIR. */ - init = initial_condition_in_loop_num (chrec, loop->num); - step = evolution_part_in_loop_num (chrec, loop->num); +static void +range_from_loop_direction (irange &r, tree type, + const irange &begin, const irange &end, + ev_direction dir) +{ + signop sign = TYPE_SIGN (type); - if (!init || !step) - return false; + if (begin.undefined_p () || end.undefined_p ()) + r.set_varying (type); + else if (dir == EV_DIR_GROWS) + { + if (wi::gt_p (begin.lower_bound (), end.upper_bound (), sign)) + r.set_varying (type); + else + r = int_range<1> (type, begin.lower_bound (), end.upper_bound ()); + } + else + { + if (wi::gt_p (end.lower_bound (), begin.upper_bound (), sign)) + r.set_varying (type); + else + r = int_range<1> (type, end.lower_bound (), begin.upper_bound ()); + } +} - Value_Range rinit (TREE_TYPE (init)); - Value_Range rstep (TREE_TYPE (step)); - /* 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->range_of_expr (rinit, init, stmt)) - rinit.singleton_p (&init); - /* Likewise for step. */ - if (TREE_CODE (step) == SSA_NAME - && query->range_of_expr (rstep, step, stmt)) - rstep.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 - a simple expression, compare_values and possibly other functions - in tree-vrp won't be able to handle it. */ - if (step == NULL_TREE - || !is_gimple_min_invariant (step) - || !valid_value_p (init)) - return false; +/* Set V to the range of NAME in STMT within LOOP. Return TRUE if a + range was found. */ - dir = scev_direction (chrec); - if (/* Do not adjust ranges if we do not know whether the iv increases - or decreases, ... */ - dir == EV_DIR_UNKNOWN - /* ... or if it may wrap. */ - || scev_probably_wraps_p (NULL_TREE, init, step, stmt, - get_chrec_loop (chrec), true)) +bool +range_of_var_in_loop (vrange &v, tree name, class loop *l, gimple *stmt, + range_query *query) +{ + tree init, step; + enum ev_direction dir; + if (!get_scev_info (v, name, stmt, l, init, step, dir)) + return true; + + // Calculate ranges for the values from SCEV. + irange &r = as_a (v); + tree type = TREE_TYPE (init); + int_range<2> rinit (type), rstep (type), max_init (type); + if (!query->range_of_expr (rinit, init, stmt) + || !query->range_of_expr (rstep, step, stmt)) return false; - if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) - tmin = lower_bound_in_type (type, type); - else - tmin = TYPE_MIN_VALUE (type); - if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) - tmax = upper_bound_in_type (type, type); - else - tmax = TYPE_MAX_VALUE (type); - - /* Try to use estimated number of iterations for the loop to constrain the - final value in the evolution. */ - if (TREE_CODE (step) == INTEGER_CST - && is_gimple_val (init) - && (TREE_CODE (init) != SSA_NAME - || (query->range_of_expr (r, init, stmt) - && !r.varying_p () - && !r.undefined_p ()))) + // Calculate the final range of NAME if possible. + if (rinit.singleton_p () && rstep.singleton_p ()) { widest_int nit; + if (!max_loop_iterations (l, &nit)) + return false; - /* We are only entering here for loop header PHI nodes, so using - the number of latch executions is the correct thing to use. */ - if (max_loop_iterations (loop, &nit)) + if (!induction_variable_may_overflow_p (type, rstep.lower_bound (), nit)) { - signop sgn = TYPE_SIGN (TREE_TYPE (step)); - wi::overflow_type overflow; - - widest_int wtmp = wi::mul (wi::to_widest (step), nit, sgn, - &overflow); - /* If the multiplication overflowed we can't do a meaningful - adjustment. Likewise if the result doesn't fit in the type - of the induction variable. For a signed type we have to - check whether the result has the expected signedness which - is that of the step as number of iterations is unsigned. */ - if (!overflow - && wi::fits_to_tree_p (wtmp, TREE_TYPE (init)) - && (sgn == UNSIGNED - || wi::gts_p (wtmp, 0) == wi::gts_p (wi::to_wide (step), 0))) - { - value_range maxvr, vr0, vr1; - if (!query->range_of_expr (vr0, init, stmt)) - vr0.set_varying (TREE_TYPE (init)); - tree tinit = TREE_TYPE (init); - wide_int winit = wide_int::from (wtmp, - TYPE_PRECISION (tinit), - TYPE_SIGN (tinit)); - vr1.set (TREE_TYPE (init), winit, winit); - - range_op_handler handler (PLUS_EXPR, TREE_TYPE (init)); - if (!handler.fold_range (maxvr, TREE_TYPE (init), vr0, vr1)) - maxvr.set_varying (TREE_TYPE (init)); - - /* Likewise if the addition did. */ - if (!maxvr.varying_p () && !maxvr.undefined_p ()) - { - int_range<2> initvr; - - if (!query->range_of_expr (initvr, init, stmt) - || initvr.undefined_p ()) - return false; - - tree initvr_type = initvr.type (); - tree initvr_min = wide_int_to_tree (initvr_type, - initvr.lower_bound ()); - tree initvr_max = wide_int_to_tree (initvr_type, - initvr.upper_bound ()); - tree maxvr_type = maxvr.type (); - tree maxvr_min = wide_int_to_tree (maxvr_type, - maxvr.lower_bound ()); - tree maxvr_max = wide_int_to_tree (maxvr_type, - maxvr.upper_bound ()); - - /* Check if init + nit * step overflows. Though we checked - scev {init, step}_loop doesn't wrap, it is not enough - because the loop may exit immediately. Overflow could - happen in the plus expression in this case. */ - if ((dir == EV_DIR_DECREASES - && compare_values (maxvr_min, initvr_min) != -1) - || (dir == EV_DIR_GROWS - && compare_values (maxvr_max, initvr_max) != 1)) - return false; - - tmin = maxvr_min; - tmax = maxvr_max; - } - } + // Calculate the max bounds for init (init + niter * step). + wide_int w = wide_int::from (nit, TYPE_PRECISION (type), TYPE_SIGN (type)); + int_range<1> niter (type, w, w); + int_range_max max_step; + range_op_handler mult_handler (MULT_EXPR, type); + range_op_handler plus_handler (PLUS_EXPR, type); + if (!mult_handler.fold_range (max_step, type, niter, rstep) + || !plus_handler.fold_range (max_init, type, rinit, max_step)) + return false; } } - - *min = tmin; - *max = tmax; - if (dir == EV_DIR_DECREASES) - *max = init; - else - *min = init; - - fix_overflow (min, max); + range_from_loop_direction (r, type, rinit, max_init, dir); return true; } diff --git a/gcc/vr-values.h b/gcc/vr-values.h index dc0c22df4d8..df79a3a570b 100644 --- a/gcc/vr-values.h +++ b/gcc/vr-values.h @@ -74,7 +74,7 @@ private: extern bool range_fits_type_p (const irange *vr, unsigned dest_precision, signop dest_sgn); -extern bool bounds_of_var_in_loop (tree *min, tree *max, range_query *, - class loop *loop, gimple *stmt, tree var); +extern bool range_of_var_in_loop (vrange &, tree var, class loop *, gimple *, + range_query *); #endif /* GCC_VR_VALUES_H */