On Tue, Aug 18, 2015 at 4:02 PM, Ajit Kumar Agarwal <ajit.kumar.agar...@xilinx.com> wrote: > > > -----Original Message----- > From: Bin.Cheng [mailto:amker.ch...@gmail.com] > Sent: Tuesday, August 18, 2015 1:08 PM > To: Ajit Kumar Agarwal > Cc: Richard Biener; Bin Cheng; GCC Patches; Vinod Kathail; Shail Aditya > Gupta; Vidhumouli Hunsigida; Nagaraju Mekala > Subject: Re: [PATCH GCC]Improve bound information in loop niter analysis > > On Mon, Aug 17, 2015 at 6:49 PM, Ajit Kumar Agarwal > <ajit.kumar.agar...@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? > > The Algorithm I have given above is based on Post Dominator Info. This helps > to calculate the iteration branches. The iteration branches are the > Branches that determine the loop exit condition. Based on the condition it > either branches to the header of the Loop, Or it may branch to the > Block dominated by the header or exit from the loop. The above Algorithm > finds out such iteration branches and thus decides on the Loop bound > Or iteration count. If such iteration branches are not at the back edge node > and it may be a node inside the loop based on some conditions. > Finding out such iteration branches can be done through the post dominator > info using the above algorithm. Based on the iteration branches the > conditions can be analyzed and that helps in finding out the iteration bound > for Known cases. Know cases are the cases where the loop bound can be > determined at compile time. > > One Example would be Multi-Exits Loops where the Loop exit condition can be > at the back edge or it may be a block inside the Loop based on the > IF conditions and breaks out based on the conditions. Thus having multiple > exits. Such iteration branches can be found using The above Algorithm. As far as I understand, GCC already do loop niter analysis one the basis of exit edge (and the corresponding block and condition). And yes, it uses scev/vrp information for the analysis. The original patch is to improve the analysis with flow sensitive range information. It's not about GCC can't work on exit edge.
Thanks, bin > > Thanks & Regards > Ajit > > Thanks, > bin >> >> Thanks & Regards >> Ajit >> >> >> -----Original Message----- >> From: gcc-patches-ow...@gcc.gnu.org >> [mailto:gcc-patches-ow...@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.guent...@gmail.com> >> wrote: >>> On Tue, Jul 28, 2015 at 11:36 AM, Bin Cheng <bin.ch...@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.ch...@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.ch...@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.
