From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 70722 invoked by alias); 18 Aug 2015 07:38:27 -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 70704 invoked by uid 89); 18 Aug 2015 07:38:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-oi0-f50.google.com Received: from mail-oi0-f50.google.com (HELO mail-oi0-f50.google.com) (209.85.218.50) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Tue, 18 Aug 2015 07:38:16 +0000 Received: by oip136 with SMTP id 136so95256182oip.1 for ; Tue, 18 Aug 2015 00:38:14 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.202.194.9 with SMTP id s9mr4602628oif.39.1439883493965; Tue, 18 Aug 2015 00:38:13 -0700 (PDT) Received: by 10.76.94.211 with HTTP; Tue, 18 Aug 2015 00:38:13 -0700 (PDT) In-Reply-To: <37378DC5BCD0EE48BA4B082E0B55DFAA4295B753@XAP-PVEXMBX02.xlnx.xilinx.com> References: <000401d0c918$d7a2e780$86e8b680$@arm.com> <37378DC5BCD0EE48BA4B082E0B55DFAA4295B753@XAP-PVEXMBX02.xlnx.xilinx.com> Date: Tue, 18 Aug 2015 07:53:00 -0000 Message-ID: Subject: Re: [PATCH GCC]Improve bound information in loop niter analysis From: "Bin.Cheng" To: Ajit Kumar Agarwal Cc: Richard Biener , Bin Cheng , GCC Patches , Vinod Kathail , Shail Aditya Gupta , Vidhumouli Hunsigida , Nagaraju Mekala Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2015-08/txt/msg00952.txt.bz2 On Mon, Aug 17, 2015 at 6:49 PM, Ajit Kumar Agarwal wrote: > All: > > Does the Logic to calculate the Loop bound information through Value Rang= e 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 suc= cessors 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(Heade= r of Loop)) > { > I =3D I union L1 > } > > Thus "I" will have all set of iteration branches. This will handle more c= ases of Loop bound information that > Will be accurate through the exact iteration count that are known cases a= long 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 wrote: >> On Tue, Jul 28, 2015 at 11:36 AM, Bin Cheng 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 =3D fold_convert (type, c0); >> + c1 =3D 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 s= ucceed. > 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 + o= ffc0 !=3D 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 =3D GT_EXPR; >> + if (TYPE_MAX_VALUE (type) >> + && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0)) >> + cmp =3D 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 t= he name of the function, it's more vrp related. For now, the function is c= alled 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 >>> >>> * 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 >>> >>> * 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.