From patchwork Thu Aug 27 09:41:30 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 511208 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 8B1B61401DE for ; Thu, 27 Aug 2015 19:41:55 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=OvzKX/EV; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=YhqzGZOvAE3Jl/AoAfmsSw7/Sue5Xy+7Djo4XGt6AVJhAcbsYZwJ0 F9yD/Atzx8CLwFfJvNYDslv4O6ghCm8msOacE4mJcOxKrb3NqyiGKIFV8HuzdBsD caxE3Qpfo2KqAXV8jjj6s5RP1F3CCSHRdswkjC2u1EKdcIe6+GrW/Q= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type; s= default; bh=ngI206qH8Ml2YP+NudnjyAoIoUY=; b=OvzKX/EV3+hfu20y5Td9 TjfxtlXpSxwkSFZ2uUMzSMLGQm4q/PJOsH0Xn/hZWwoOsPlbf2jwrhMmmc9IflhI uQf0xqI3tAh5rgiLukkrPaV/RUoZKyguOyxgxQo2NdhW3m8Lrsfpkj+1Xd2uL/2C LH89wfyRAaYMf124p/Us1OU= Received: (qmail 111796 invoked by alias); 27 Aug 2015 09:41:48 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 111780 invoked by uid 89); 27 Aug 2015 09:41:47 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=AWL, BAYES_00, KAM_ASCII_DIVIDERS, SPF_PASS autolearn=no version=3.3.2 X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (146.101.78.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 27 Aug 2015 09:41:45 +0000 Received: from cam-owa2.Emea.Arm.com (fw-tnat.cambridge.arm.com [217.140.96.140]) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-33-U1oW3NwUTlWpoDF0WTJBpw-1; Thu, 27 Aug 2015 10:41:40 +0100 Received: from shawin233 ([10.1.2.79]) by cam-owa2.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Thu, 27 Aug 2015 10:41:39 +0100 From: "Bin Cheng" To: Subject: [PATCH GCC][rework]Improve loop bound info by simplifying conversions in iv base Date: Thu, 27 Aug 2015 17:41:30 +0800 Message-ID: <000001d0e0ac$9008b1b0$b01a1510$@arm.com> MIME-Version: 1.0 X-MC-Unique: U1oW3NwUTlWpoDF0WTJBpw-1 X-IsSubscribed: yes Hi, This is a rework for https://gcc.gnu.org/ml/gcc-patches/2015-07/msg02335.html, with review comments addressed. For now, SCEV may compute iv base in the form of "(signed T)((unsigned T)base + step))". This complicates other optimizations/analysis depending on SCEV because it's hard to dive into type conversions. This kind of type conversions can be simplified with additional range information implied by loop initial conditions. This patch does such simplification. With simplified iv base, loop niter analysis can compute more accurate bound information since sensible value range can be derived for "base+step". For example, accurate loop bound&may_be_zero information is computed for cases added by this patch. The code is actually moved from loop_exits_before_overflow. After this patch, the corresponding code in loop_exits_before_overflow will be never executed, so I removed that part code. The patch also includes some code format changes. Bootstrap and test on x86_64. Is it OK? Thanks, bin 2015-08-27 Bin Cheng * tree-ssa-loop-niter.c (tree_simplify_using_condition_1): Support new parameter. (tree_simplify_using_condition): Ditto. (simplify_using_initial_conditions): Ditto. (loop_exits_before_overflow): Pass new argument to function simplify_using_initial_conditions. Remove case for type conversions simplification. * tree-ssa-loop-niter.h (simplify_using_initial_conditions): New parameter. * tree-scalar-evolution.c (simple_iv): Simplify type conversions in iv base using loop initial conditions. gcc/testsuite/ChangeLog 2015-08-27 Bin Cheng * gcc.dg/tree-ssa/loop-bound-2.c: New test. * gcc.dg/tree-ssa/loop-bound-4.c: New test. * gcc.dg/tree-ssa/loop-bound-6.c: New test. Index: gcc/tree-ssa-loop-niter.c =================================================================== --- gcc/tree-ssa-loop-niter.c (revision 227163) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -1926,7 +1926,7 @@ expand_simple_operations (tree expr, tree stop) expression (or EXPR unchanged, if no simplification was possible). */ static tree -tree_simplify_using_condition_1 (tree cond, tree expr) +tree_simplify_using_condition_1 (tree cond, tree expr, tree stop) { bool changed; tree e, te, e0, e1, e2, notcond; @@ -1941,17 +1941,17 @@ static tree { changed = false; - e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); + e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0), stop); if (TREE_OPERAND (expr, 0) != e0) changed = true; - e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); + e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1), stop); if (TREE_OPERAND (expr, 1) != e1) changed = true; if (code == COND_EXPR) { - e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); + e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2), stop); if (TREE_OPERAND (expr, 2) != e2) changed = true; } @@ -2014,7 +2014,7 @@ static tree return boolean_true_node; } - te = expand_simple_operations (expr); + te = expand_simple_operations (expr, stop); /* Check whether COND ==> EXPR. */ notcond = invert_truthvalue (cond); @@ -2038,19 +2038,19 @@ static tree the loop do not cause us to fail. */ static tree -tree_simplify_using_condition (tree cond, tree expr) +tree_simplify_using_condition (tree cond, tree expr, tree stop) { - cond = expand_simple_operations (cond); + cond = expand_simple_operations (cond, stop); - return tree_simplify_using_condition_1 (cond, expr); + return tree_simplify_using_condition_1 (cond, expr, stop); } /* Tries to simplify EXPR using the conditions on entry to LOOP. Returns the simplified expression (or EXPR unchanged, if no - simplification was possible).*/ + simplification was possible). */ -static tree -simplify_using_initial_conditions (struct loop *loop, tree expr) +tree +simplify_using_initial_conditions (struct loop *loop, tree expr, tree stop) { edge e; basic_block bb; @@ -2082,7 +2082,7 @@ static tree gimple_cond_rhs (stmt)); if (e->flags & EDGE_FALSE_VALUE) cond = invert_truthvalue (cond); - expr = tree_simplify_using_condition (cond, expr); + expr = tree_simplify_using_condition (cond, expr, stop); /* Break if EXPR is simplified to const values. */ if (expr && (integer_zerop (expr) || integer_nonzerop (expr))) break; @@ -4114,138 +4114,69 @@ loop_exits_before_overflow (tree base, tree step, help of analyzed loop control IV. This is done only for IVs with constant step because otherwise we don't have the information. */ if (TREE_CODE (step) == INTEGER_CST) - for (civ = loop->control_ivs; civ; civ = civ->next) - { - enum tree_code code; - tree stepped, extreme, civ_type = TREE_TYPE (civ->step); + { + tree stop = (TREE_CODE (base) == SSA_NAME) ? base : NULL; - /* Have to consider type difference because operand_equal_p ignores - that for constants. */ - if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type) - || element_precision (type) != element_precision (civ_type)) - continue; + for (civ = loop->control_ivs; civ; civ = civ->next) + { + enum tree_code code; + tree stepped, extreme, civ_type = TREE_TYPE (civ->step); - /* Only consider control IV with same step. */ - if (!operand_equal_p (step, civ->step, 0)) - continue; + /* Have to consider type difference because operand_equal_p ignores + that for constants. */ + if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type) + || element_precision (type) != element_precision (civ_type)) + continue; - /* Done proving if this is a no-overflow control IV. */ - if (operand_equal_p (base, civ->base, 0)) - return true; - - /* If this is a before stepping control IV, in other words, we have - - {civ_base, step} = {base + step, step} - - Because civ {base + step, step} doesn't overflow during loop - iterations, {base, step} will not overflow if we can prove the - operation "base + step" does not overflow. Specifically, we try - to prove below conditions are satisfied: - - base <= UPPER_BOUND (type) - step ;;step > 0 - base >= LOWER_BOUND (type) - step ;;step < 0 - - by proving the reverse conditions are false using loop's initial - condition. */ - if (POINTER_TYPE_P (TREE_TYPE (base))) - code = POINTER_PLUS_EXPR; - else - code = PLUS_EXPR; - - stepped = fold_build2 (code, TREE_TYPE (base), base, step); - if (operand_equal_p (stepped, civ->base, 0)) - { - if (tree_int_cst_sign_bit (step)) - { - code = LT_EXPR; - extreme = lower_bound_in_type (type, type); - } - else - { - code = GT_EXPR; - extreme = upper_bound_in_type (type, type); - } - extreme = fold_build2 (MINUS_EXPR, type, extreme, step); - e = fold_build2 (code, boolean_type_node, base, extreme); - e = simplify_using_initial_conditions (loop, e); - if (integer_zerop (e)) - return true; - + /* Only consider control IV with same step. */ + if (!operand_equal_p (step, civ->step, 0)) continue; - } - /* Similar to above, only in this case we have: + /* Done proving if this is a no-overflow control IV. */ + if (operand_equal_p (base, civ->base, 0)) + return true; - {civ_base, step} = {(signed T)((unsigned T)base + step), step} - && TREE_TYPE (civ_base) = signed T. + /* If this is a before stepping control IV, in other words, we have - We prove that below condition is satisfied: + {civ_base, step} = {base + step, step} - (signed T)((unsigned T)base + step) - == (signed T)(unsigned T)base + step - == base + step + Because civ {base + step, step} doesn't overflow during loop + iterations, {base, step} will not overflow if we can prove the + operation "base + step" does not overflow. Specifically, we try + to prove below conditions are satisfied: - because of exact the same reason as above. This also proves - there is no overflow in the operation "base + step", thus the - induction variable {base, step} during loop iterations. + base <= UPPER_BOUND (type) - step ;;step > 0 + base >= LOWER_BOUND (type) - step ;;step < 0 - This is necessary to handle cases as below: + by proving the reverse conditions are false using loop's initial + condition. */ + if (POINTER_TYPE_P (TREE_TYPE (base))) + code = POINTER_PLUS_EXPR; + else + code = PLUS_EXPR; - int foo (int *a, signed char s, signed char l) - { - signed char i; - for (i = s; i < l; i++) - a[i] = 0; - return 0; - } + stepped = fold_build2 (code, TREE_TYPE (base), base, step); + if (operand_equal_p (stepped, civ->base, 0)) + { + if (tree_int_cst_sign_bit (step)) + { + code = LT_EXPR; + extreme = lower_bound_in_type (type, type); + } + else + { + code = GT_EXPR; + extreme = upper_bound_in_type (type, type); + } + extreme = fold_build2 (MINUS_EXPR, type, extreme, step); + e = fold_build2 (code, boolean_type_node, base, extreme); + e = simplify_using_initial_conditions (loop, e, stop); + if (integer_zerop (e)) + return true; + } + } + } - The variable I is firstly converted to type unsigned char, - incremented, then converted back to type signed char. */ - if (!CONVERT_EXPR_P (civ->base) || TREE_TYPE (civ->base) != type) - continue; - e = TREE_OPERAND (civ->base, 0); - if (TREE_CODE (e) != PLUS_EXPR - || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST - || !operand_equal_p (step, - fold_convert (type, - TREE_OPERAND (e, 1)), 0)) - continue; - e = TREE_OPERAND (e, 0); - if (!CONVERT_EXPR_P (e) || !operand_equal_p (e, unsigned_base, 0)) - continue; - e = TREE_OPERAND (e, 0); - /* It may still be possible to prove no overflow even if condition - "operand_equal_p (e, base, 0)" isn't satisfied here, like below - example: - - e : ssa_var ; unsigned long type - base : (int) ssa_var - unsigned_base : (unsigned int) ssa_var - - Unfortunately this is a rare case observed during GCC profiled - bootstrap. See PR66638 for more information. - - For now, we just skip the possibility. */ - if (!operand_equal_p (e, base, 0)) - continue; - - if (tree_int_cst_sign_bit (step)) - { - code = LT_EXPR; - extreme = lower_bound_in_type (type, type); - } - else - { - code = GT_EXPR; - extreme = upper_bound_in_type (type, type); - } - extreme = fold_build2 (MINUS_EXPR, type, extreme, step); - e = fold_build2 (code, boolean_type_node, base, extreme); - e = simplify_using_initial_conditions (loop, e); - if (integer_zerop (e)) - return true; - } - return false; } Index: gcc/tree-ssa-loop-niter.h =================================================================== --- gcc/tree-ssa-loop-niter.h (revision 227163) +++ gcc/tree-ssa-loop-niter.h (working copy) @@ -21,6 +21,8 @@ along with GCC; see the file COPYING3. If not see #define GCC_TREE_SSA_LOOP_NITER_H extern tree expand_simple_operations (tree, tree = NULL); +extern tree simplify_using_initial_conditions (struct loop *, + tree, tree = NULL); extern bool loop_only_exit_p (const struct loop *, const_edge); extern bool number_of_iterations_exit (struct loop *, edge, struct tree_niter_desc *niter, bool, Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c (revision 0) @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ + +int *a; + +int +foo (signed char s, signed char l) +{ + signed char i; + int sum = 0; + + for (i = s; i < l; i++) + { + sum += a[i]; + } + + return sum; +} + +/* Check loop niter bound information. */ +/* { dg-final { scan-tree-dump "bounded by 254" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "bounded by 255" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/loop-bound-4.c (revision 0) @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ + +int *a; + +int +foo (signed char s, signed char l) +{ + signed char i; + int sum = 0; + + for (i = s; i > l; i--) + { + sum += a[i]; + } + + return sum; +} + +/* Check loop niter bound information. */ +/* { dg-final { scan-tree-dump "bounded by 254" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "bounded by 255" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/loop-bound-6.c (revision 0) @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ + +int *a; + +int +foo (signed char s) +{ + signed char i; + int sum = 0; + + for (i = s; i > 0; i--) + { + sum += a[i]; + } + + return sum; +} + +/* Check loop niter bound information. */ +/* { dg-final { scan-tree-dump "bounded by 126" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "bounded by 127" "ivopts" } } */ +/* { dg-final { scan-tree-dump-not "zero if " "ivopts" } } */ Index: gcc/tree-scalar-evolution.c =================================================================== --- gcc/tree-scalar-evolution.c (revision 227163) +++ gcc/tree-scalar-evolution.c (working copy) @@ -3234,8 +3234,10 @@ bool simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, affine_iv *iv, bool allow_nonconstant_step) { - tree type, ev; - bool folded_casts; + enum tree_code code; + tree type, ev, base, e, stop; + wide_int extreme; + bool folded_casts, overflow; iv->base = NULL_TREE; iv->step = NULL_TREE; @@ -3276,6 +3278,82 @@ simple_iv (struct loop *wrto_loop, struct loop *us iv->no_overflow = (!folded_casts && ANY_INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_UNDEFINED (type)); + /* Try to simplify iv base: + + (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T + == (signed T)(unsigned T)base + step + == base + step + + If we can prove operation (base + step) doesn't overflow or underflow. + Specifically, we try to prove below conditions are satisfied: + + base <= UPPER_BOUND (type) - step ;;step > 0 + base >= LOWER_BOUND (type) - step ;;step < 0 + + This is done by proving the reverse conditions are false using loop's + initial conditions. + + The is necessary to make loop niter, or iv overflow analysis easier + for below example: + + int foo (int *a, signed char s, signed char l) + { + signed char i; + for (i = s; i < l; i++) + a[i] = 0; + return 0; + } + + Note variable I is firstly converted to type unsigned char, incremented, + then converted back to type signed char. */ + + if (wrto_loop->num != use_loop->num) + return true; + + if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST) + return true; + + type = TREE_TYPE (iv->base); + e = TREE_OPERAND (iv->base, 0); + if (TREE_CODE (e) != PLUS_EXPR + || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST + || !tree_int_cst_equal (iv->step, + fold_convert (type, TREE_OPERAND (e, 1)))) + return true; + e = TREE_OPERAND (e, 0); + if (!CONVERT_EXPR_P (e)) + return true; + base = TREE_OPERAND (e, 0); + if (!useless_type_conversion_p (type, TREE_TYPE (base))) + return true; + + if (tree_int_cst_sign_bit (iv->step)) + { + code = LT_EXPR; + extreme = wi::min_value (type); + } + else + { + code = GT_EXPR; + extreme = wi::max_value (type); + } + overflow = false; + extreme = wi::sub (extreme, iv->step, TYPE_SIGN (type), &overflow); + if (overflow) + return true; + e = fold_build2 (code, boolean_type_node, base, + wide_int_to_tree (type, extreme)); + stop = (TREE_CODE (base) == SSA_NAME) ? base : NULL; + e = simplify_using_initial_conditions (use_loop, e, stop); + if (!integer_zerop (e)) + return true; + + if (POINTER_TYPE_P (TREE_TYPE (base))) + code = POINTER_PLUS_EXPR; + else + code = PLUS_EXPR; + + iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step); return true; }