From: "Bin.Cheng" <amker.cheng@gmail.com>
To: Ajit Kumar Agarwal <ajit.kumar.agarwal@xilinx.com>
Cc: Richard Biener <richard.guenther@gmail.com>,
Bin Cheng <bin.cheng@arm.com>,
GCC Patches <gcc-patches@gcc.gnu.org>,
Vinod Kathail <vinodk@xilinx.com>,
Shail Aditya Gupta <shailadi@xilinx.com>,
Vidhumouli Hunsigida <vidhum@xilinx.com>,
Nagaraju Mekala <nmekala@xilinx.com>
Subject: Re: [PATCH GCC]Improve bound information in loop niter analysis
Date: Tue, 18 Aug 2015 07:53:00 -0000 [thread overview]
Message-ID: <CAHFci29ipRKEvkNGNESAzp5xAVqsC2kng7xwvUEEHa262H_xxg@mail.gmail.com> (raw)
In-Reply-To: <37378DC5BCD0EE48BA4B082E0B55DFAA4295B753@XAP-PVEXMBX02.xlnx.xilinx.com>
On Mon, Aug 17, 2015 at 6:49 PM, Ajit Kumar Agarwal
<ajit.kumar.agarwal@xilinx.com> wrote:
> All:
>
> Does the Logic to calculate the Loop bound information through Value Range Analyis uses the post dominator and
> Dominator info. The iteration branches instead of Loop exit condition can be calculated through post dominator info.
> If the node in the Loop has two successors and post dominates the two successors then the iteration branch can be
> The same node.
>
> For All the nodes L in the Loop B
> If (L1, L2 belongs to successors of (L) && L1,L2 belongs to PosDom(Header of Loop))
> {
> I = I union L1
> }
>
> Thus "I" will have all set of iteration branches. This will handle more cases of Loop bound information that
> Will be accurate through the exact iteration count that are known cases along with Value Range Information
> Where the condition is instead not the Loop exits but other nodes in the Loop.
I don't quite follow your words here. Could you please give a simple
example about it? Especially I don't know how post-dom helps the loop
bound analysis. Seems your pseudo code is collecting some comparison
basic block of loop?
Thanks,
bin
>
> Thanks & Regards
> Ajit
>
>
> -----Original Message-----
> From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches-owner@gcc.gnu.org] On Behalf Of Bin.Cheng
> Sent: Monday, August 17, 2015 3:32 PM
> To: Richard Biener
> Cc: Bin Cheng; GCC Patches
> Subject: Re: [PATCH GCC]Improve bound information in loop niter analysis
>
> Thanks for all your reviews.
>
> On Fri, Aug 14, 2015 at 4:17 PM, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Tue, Jul 28, 2015 at 11:36 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>>> Hi,
>>> Loop niter computes inaccurate bound information for different loops.
>>> This patch is to improve it by using loop initial condition in
>>> determine_value_range. Generally, loop niter is computed by
>>> subtracting start var from end var in loop exit condition. Moreover,
>>> loop bound is computed using value range information of both start and end variables.
>>> Basic idea of this patch is to check if loop initial condition
>>> implies more range information for both start/end variables. If yes,
>>> we refine range information and use that to compute loop bound.
>>> With this improvement, more accurate loop bound information is
>>> computed for test cases added by this patch.
>>
>> + c0 = fold_convert (type, c0);
>> + c1 = fold_convert (type, c1);
>> +
>> + if (operand_equal_p (var, c0, 0))
>>
>> I believe if c0 is not already of type type operand-equal_p will never succeed.
> It's quite specific case targeting comparison between var and it's range bounds. Given c0 is in form of "var + offc0", then the comparison "var + offc0 != range bounds" doesn't have any useful information. Maybe useless type conversion can be handled here though, it might be even corner case.
>
>>
>> (side-note: we should get rid of the GMP use, that's expensive and now
>> we have wide-int available which should do the trick as well)
>>
>> + /* Case of comparing with the bounds of the type. */
>> + if (TYPE_MIN_VALUE (type)
>> + && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
>> + cmp = GT_EXPR;
>> + if (TYPE_MAX_VALUE (type)
>> + && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
>> + cmp = LT_EXPR;
>>
>> don't use TYPE_MIN/MAX_VALUE. Instead use the types precision and all
>> wide_int operations (see match.pd wi::max_value use).
> Done.
>
>>
>> + else if (!operand_equal_p (var, varc0, 0))
>> + goto end_2;
>>
>> ick - goto. We need sth like a auto_mpz class with a destructor.
> Label end_2 removed.
>
>>
>> struct auto_mpz
>> {
>> auto_mpz () { mpz_init (m_val); }
>> ~auto_mpz () { mpz_clear (m_val); }
>> mpz& operator() { return m_val; }
>> mpz m_val;
>> };
>>
>>> Is it OK?
>>
>> I see the code follows existing practice in niter analysis even though
>> my overall plan was to transition its copying of value-range related
>> optimizations to use VRP infrastructure.
> Yes, I think it's easy to push it to VRP infrastructure. Actually from the name of the function, it's more vrp related. For now, the function is called only by bound_difference, not so many as vrp queries. We need cache facility in vrp otherwise it would be expensive.
>
>>
>> I'm still ok with improving the existing code on the basis that I
>> won't get to that for GCC 6.
>>
>> So - ok with the TYPE_MIN/MAX_VALUE change suggested above.
>>
>> Refactoring with auto_mpz welcome.
> That will be an independent patch, so I skipped it in this one.
>
> New version attached. Bootstrap and test on x86_64.
>
> Thanks,
> bin
>>
>> Thanks,
>> RIchard.
>>
>>> Thanks,
>>> bin
>>>
>>> 2015-07-28 Bin Cheng <bin.cheng@arm.com>
>>>
>>> * tree-ssa-loop-niter.c (refine_value_range_using_guard): New.
>>> (determine_value_range): Call refine_value_range_using_guard for
>>> each loop initial condition to improve value range.
>>>
>>> gcc/testsuite/ChangeLog
>>> 2015-07-28 Bin Cheng <bin.cheng@arm.com>
>>>
>>> * gcc.dg/tree-ssa/loop-bound-1.c: New test.
>>> * gcc.dg/tree-ssa/loop-bound-3.c: New test.
>>> * gcc.dg/tree-ssa/loop-bound-5.c: New test.
next prev parent reply other threads:[~2015-08-18 7:38 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-07-28 10:11 Bin Cheng
2015-08-13 8:27 ` Bin.Cheng
2015-08-13 22:10 ` Jeff Law
2015-08-14 3:13 ` Bin.Cheng
2015-08-14 18:32 ` Jeff Law
2015-08-14 8:28 ` Richard Biener
2015-08-14 18:47 ` Jeff Law
2015-08-17 10:06 ` Bin.Cheng
2015-08-17 11:16 ` Ajit Kumar Agarwal
2015-08-17 11:38 ` Ajit Kumar Agarwal
2015-08-18 7:53 ` Bin.Cheng [this message]
2015-08-18 8:16 ` Ajit Kumar Agarwal
2015-08-18 8:51 ` Richard Biener
2015-08-18 9:09 ` Bin.Cheng
2015-08-18 18:38 ` Jeff Law
2015-08-19 2:45 ` Bin.Cheng
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAHFci29ipRKEvkNGNESAzp5xAVqsC2kng7xwvUEEHa262H_xxg@mail.gmail.com \
--to=amker.cheng@gmail.com \
--cc=ajit.kumar.agarwal@xilinx.com \
--cc=bin.cheng@arm.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=nmekala@xilinx.com \
--cc=richard.guenther@gmail.com \
--cc=shailadi@xilinx.com \
--cc=vidhum@xilinx.com \
--cc=vinodk@xilinx.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).