From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 90001 invoked by alias); 20 Aug 2015 11:22:21 -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 89237 invoked by uid 89); 20 Aug 2015 11:22:20 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-io0-f181.google.com Received: from mail-io0-f181.google.com (HELO mail-io0-f181.google.com) (209.85.223.181) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Thu, 20 Aug 2015 11:22:19 +0000 Received: by iodv127 with SMTP id v127so41888336iod.3 for ; Thu, 20 Aug 2015 04:22:17 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.107.167.199 with SMTP id q190mr2567586ioe.119.1440069737867; Thu, 20 Aug 2015 04:22:17 -0700 (PDT) Received: by 10.107.32.140 with HTTP; Thu, 20 Aug 2015 04:22:17 -0700 (PDT) In-Reply-To: References: <000801d0c919$220d0b70$66272250$@arm.com> Date: Thu, 20 Aug 2015 11:24:00 -0000 Message-ID: Subject: Re: [PATCH GCC]Improve loop bound info by simplifying conversions in iv base From: Richard Biener To: "Bin.Cheng" Cc: Bin Cheng , GCC Patches Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2015-08/txt/msg01195.txt.bz2 On Thu, Aug 20, 2015 at 10:22 AM, Bin.Cheng wrote: > On Fri, Aug 14, 2015 at 4:28 PM, Richard Biener > wrote: >> On Tue, Jul 28, 2015 at 11:38 AM, Bin Cheng wrote: >>> 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? >> >> It looks quite special given it only handles a very specific pattern. Did you >> do any larger collecting of statistics on how many times this triggers, >> esp. how many times simplify_using_initial_conditions succeeds and >> how many times not? This function is somewhat expensive. > Yes, this is corner case targeting induction variables of small signed > types, just like added test cases. We need to convert it to unsigned, > do the stepping, and convert back. I collected statistics for gcc > bootstrap and spec2k6. The function is called about 400-500 times in > both case. About 45% of calls succeeded in bootstrap, while only ~3% > succeeded in spec2k6. > > I will prepare a new version patch if you think it's worthwhile in > terms of compilation cost and benefit. Yes. Richard. > Thanks, > bin >> >> + || !operand_equal_p (iv->step, >> + fold_convert (type, >> + TREE_OPERAND (e, 1)), 0)) >> >> operand_equal_p can handle sign-differences in integer constants, >> no need to fold_convert here. Also if you know that you are comparing >> integer constants please use tree_int_cst_equal_p. >> >> + extreme = lower_bound_in_type (type, type); >> >> that's a strange function to call here (with two same types). Looks like >> just wide_int_to_tree (type, wi::max/min_value (type)). >> >> + extreme = fold_build2 (MINUS_EXPR, type, extreme, iv->step); >> >> so as iv->step is an INTEGER_CST please do this whole thing using >> wide_ints and only build trees here: >> >> + e = fold_build2 (code, boolean_type_node, base, extreme); >> >> Thanks, >> Richard. >> >>> 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.