From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 41813 invoked by alias); 28 Jul 2015 09:38:31 -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 41796 invoked by uid 89); 28 Jul 2015 09:38:30 -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) (207.82.80.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 28 Jul 2015 09:38:29 +0000 Received: from cam-owa1.Emea.Arm.com (fw-tnat.cambridge.arm.com [217.140.96.140]) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-2-0OXaGpuqSmWaZReeiLLpmg-1; Tue, 28 Jul 2015 10:38:24 +0100 Received: from shawin233 ([10.1.2.79]) by cam-owa1.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Tue, 28 Jul 2015 10:38:22 +0100 From: "Bin Cheng" To: Subject: [PATCH GCC]Improve loop bound info by simplifying conversions in iv base Date: Tue, 28 Jul 2015 10:14:00 -0000 Message-ID: <000801d0c919$220d0b70$66272250$@arm.com> MIME-Version: 1.0 X-MC-Unique: 0OXaGpuqSmWaZReeiLLpmg-1 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0009_01D0C95C.303135D0" X-IsSubscribed: yes X-SW-Source: 2015-07/txt/msg02337.txt.bz2 This is a multipart message in MIME format. ------=_NextPart_000_0009_01D0C95C.303135D0 Content-Type: text/plain; charset=WINDOWS-1252 Content-Transfer-Encoding: quoted-printable Content-length: 1456 Hi, 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. For many cases, such 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 borrowed from loop_exits_before_overflow. Moreover, with simplified iv base, the second case handled in that function now becomes the first case. I didn't remove that part of code because it may(?) still be visited in scev analysis itself and simple_iv isn't an interface for that. Is it OK? Thanks, bin 2015-07-28 Bin Cheng * tree-ssa-loop-niter.c (tree_simplify_using_condition): Export the interface. * tree-ssa-loop-niter.h (tree_simplify_using_condition): Declare. * tree-scalar-evolution.c (simple_iv): Simplify type conversions in iv base using loop initial conditions. gcc/testsuite/ChangeLog 2015-07-28 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. ------=_NextPart_000_0009_01D0C95C.303135D0 Content-Type: text/plain; name=simplify-iv_base-using-loop-initial-conditions-20150728.txt Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="simplify-iv_base-using-loop-initial-conditions-20150728.txt" Content-length: 7150 Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-2.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- 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 =3D 0; + + for (i =3D s; i < l; i++) + { + sum +=3D 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 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- 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 =3D 0; + + for (i =3D s; i > l; i--) + { + sum +=3D 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 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- 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 =3D 0; + + for (i =3D s; i > 0; i--) + { + sum +=3D 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-ssa-loop-niter.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- gcc/tree-ssa-loop-niter.c (revision 225859) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -1779,9 +2043,9 @@ tree_simplify_using_condition (tree cond, tree exp =20 /* 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). */ =20 -static tree +tree simplify_using_initial_conditions (struct loop *loop, tree expr) { edge e; Index: gcc/tree-ssa-loop-niter.h =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- gcc/tree-ssa-loop-niter.h (revision 225859) +++ gcc/tree-ssa-loop-niter.h (working copy) @@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. If not see #define GCC_TREE_SSA_LOOP_NITER_H =20 extern tree expand_simple_operations (tree, tree =3D NULL); +extern tree simplify_using_initial_conditions (struct loop *, tree); 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/tree-scalar-evolution.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D --- gcc/tree-scalar-evolution.c (revision 225859) +++ gcc/tree-scalar-evolution.c (working copy) @@ -3234,7 +3234,8 @@ bool simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, affine_iv *iv, bool allow_nonconstant_step) { - tree type, ev; + enum tree_code code; + tree type, ev, base, e, extreme; bool folded_casts; =20 iv->base =3D NULL_TREE; @@ -3276,6 +3277,77 @@ simple_iv (struct loop *wrto_loop, struct loop *us iv->no_overflow =3D (!folded_casts && ANY_INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_UNDEFINED (type)); =20 + /* Try to simplify iv base: + + (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) =3D=3D sig= ned T + =3D=3D (signed T)(unsigned T)base + step + =3D=3D base + step + + If we can prove operation (base + step) doesn't overflow or underflow. + Specifically, we try to prove below conditions are satisfied: + + base <=3D UPPER_BOUND (type) - step ;;step > 0 + base >=3D 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 =3D s; i < l; i++) + a[i] =3D 0; + return 0; + } + + Note variable I is firstly converted to type unsigned char, increment= ed, + then converted back to type signed char. */ + + if (wrto_loop->num !=3D use_loop->num) + return true; + + if (!CONVERT_EXPR_P (iv->base)) + return true; + type =3D TREE_TYPE (iv->base); + e =3D TREE_OPERAND (iv->base, 0); + if (TREE_CODE (e) !=3D PLUS_EXPR + || TREE_CODE (TREE_OPERAND (e, 1)) !=3D INTEGER_CST + || !operand_equal_p (iv->step, + fold_convert (type, + TREE_OPERAND (e, 1)), 0)) + return true; + e =3D TREE_OPERAND (e, 0); + if (!CONVERT_EXPR_P (e)) + return true; + base =3D TREE_OPERAND (e, 0); + if (!useless_type_conversion_p (type, TREE_TYPE (base))) + return true; + + if (tree_int_cst_sign_bit (iv->step)) + { + code =3D LT_EXPR; + extreme =3D lower_bound_in_type (type, type); + } + else + { + code =3D GT_EXPR; + extreme =3D upper_bound_in_type (type, type); + } + extreme =3D fold_build2 (MINUS_EXPR, type, extreme, iv->step); + e =3D fold_build2 (code, boolean_type_node, base, extreme); + e =3D simplify_using_initial_conditions (use_loop, e); + if (!integer_zerop (e)) + return true; + + if (POINTER_TYPE_P (TREE_TYPE (base))) + code =3D POINTER_PLUS_EXPR; + else + code =3D PLUS_EXPR; + + iv->base =3D fold_build2 (code, TREE_TYPE (base), base, iv->step); return true; } =20 ------=_NextPart_000_0009_01D0C95C.303135D0--