This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH GCC]Improve loop bound info by simplifying conversions in iv base
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: "Bin.Cheng" <amker dot cheng at gmail dot com>
- Cc: Bin Cheng <bin dot cheng at arm dot com>, GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 20 Aug 2015 13:22:17 +0200
- Subject: Re: [PATCH GCC]Improve loop bound info by simplifying conversions in iv base
- Authentication-results: sourceware.org; auth=none
- References: <000801d0c919$220d0b70$66272250$ at arm dot com> <CAFiYyc0YSh8t0mC215iEM2BRfi=WztLBx4xAm3yDEez-e4=pKQ at mail dot gmail dot com> <CAHFci2_8R83Y=B_9Dc8OPbyhQXQ-4votBG+-3Sz8psvar=8P9A at mail dot gmail dot com>
On Thu, Aug 20, 2015 at 10:22 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Fri, Aug 14, 2015 at 4:28 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Tue, Jul 28, 2015 at 11:38 AM, Bin Cheng <bin.cheng@arm.com> 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 <bin.cheng@arm.com>
>>>
>>> * 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 <bin.cheng@arm.com>
>>>
>>> * 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.