On Tue, Jun 2, 2015 at 4:55 AM, Bin.Cheng wrote: > On Mon, Jun 1, 2015 at 6:45 PM, Richard Biener > wrote: >> On Tue, May 26, 2015 at 1:04 PM, Bin Cheng wrote: >>> Hi, >>> My first part patch improving how we handle overflow in scev is posted at >>> https://gcc.gnu.org/ml/gcc-patches/2015-05/msg01795.html . Here comes the >>> second part patch. >>> >>> This patch does below improvements: >>> 1) Computes and records control iv for each loop's exit edge. This >>> provides a way to compute overflow information in loop niter and use it in >>> different customers. It think it's useful, especially with option >>> -funsafe-loop-optimizers. >>> 2) Improve chrec_convert by adding new interface >>> loop_exits_before_overflow. It checks if a converted IV overflows wrto its >>> type and loop using overflow information of loop's control iv. This >>> basically propagates no-overflow information from control iv to ivs >>> converted from control iv. Moreover, we can further improve the logic by >>> using possible VRP information in the future. >> >> But 2) you already posted (and I have approved it but you didn't commit yet?). >> >> Can you commit that approved patch and only send the parts I didn't approve >> yet? >> >> Thanks, >> Richard. >> >>> With this patch, cases like scev-9.c and scev-10.c in patch can be handled >>> now. Cases reported in PR48052 can be vectorized too. >>> Opinions? >>> >>> Thanks, >>> bin >>> >>> >>> 2015-05-26 Bin Cheng >>> >>> * cfgloop.h (struct control_iv): New. >>> (struct loop): New field control_ivs. >>> * tree-ssa-loop-niter.c : Include "stor-layout.h". >>> (number_of_iterations_lt): Set no_overflow information. >>> (number_of_iterations_exit): Init control iv in niter struct. >>> (record_control_iv): New. >>> (estimate_numbers_of_iterations_loop): Call record_control_iv. >>> (loop_exits_before_overflow): New. Interface factored out of >>> scev_probably_wraps_p. >>> (scev_probably_wraps_p): Factor loop niter related code into >>> loop_exits_before_overflow. >>> (free_numbers_of_iterations_estimates_loop): Free control ivs. >>> * tree-ssa-loop-niter.h (free_loop_control_ivs): New. >>> >>> gcc/testsuite/ChangeLog >>> 2015-05-26 Bin Cheng >>> >>> PR tree-optimization/48052 >>> * gcc.dg/tree-ssa/scev-8.c: New. >>> * gcc.dg/tree-ssa/scev-9.c: New. >>> * gcc.dg/tree-ssa/scev-10.c: New. >>> * gcc.dg/vect/pr48052.c: New. >>> > > Hi Richard, > I think you replied the review message of this patch to another > thread. Sorry for being mis-leading. S I copied and answered your > review comments in this thread thus we can continue here. > >>> + /* Done proving if this is a no-overflow control IV. */ >>> + if (operand_equal_p (base, civ->base, 0)) >>> + return true; >> >> so all control IVs are no-overflow? > > This patch only records known no-overflow control ivs in loop > structure, so it depends on loop niter analyzer. For now, this patch > (and the existing code) sets no-overflow flag only for two cases. One > is the step-1 case, the other one is in assert_no_overflow_lt. > As a matter of fact, we may want to set no_overflow flag for all cases > with -funsafe-loop-optimizations in the future. In that case, we will > assume all control IVs are no-overflow. > >> >>> + base <= UPPER_BOUND (type) - step ;;step > 0 >>> + base >= LOWER_BOUND (type) - step ;;step < 0 >>> + >>> + by using loop's initial condition. */ >>> + stepped = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step); >>> + if (operand_equal_p (stepped, civ->base, 0)) >>> + { >>> + if (tree_int_cst_sign_bit (step)) >>> + { >>> + code = LT_EXPR; >>> + extreme = lower_bound_in_type (type, type); >>> + } >>> + else >>> + { >>> + code = GT_EXPR; >>> + extreme = upper_bound_in_type (type, type); >>> + } >>> + extreme = fold_build2 (MINUS_EXPR, type, extreme, step); >>> + e = fold_build2 (code, boolean_type_node, base, extreme); >> >> looks like you are actually computing base + step <= UPPER_BOUND (type) >> so maybe adjust the comment. But as both step and UPPER_BOUND (type) >> are constants why not compute it the way the comment specifies it? Comparison >> codes also don't match the comment and we try to prove the condition is false. > I tried to prove the condition are satisfied by proving the reverse > condition ("base > UPPER_BOUND (type) - step") is false here. In the > updated patch, I revised comments to reflect that logic. Is it ok? > >> >> This also reminds me of eventually pushing forward my idea of strengthening >> simplify_using_initial_ >> conditions by using the VRP machinery (I have a small >> prototype patch for that). > Interesting. If I understand correctly, VRP info is hold for ssa var > on a global scope basis? The loop's initial condition may strengthen > var's range information, rather than the contrary. Actually I tried > to refine vrp info in scope of loop and used the refined vrp > information in loop optimizer (In the thread which you replied this > review message to). Looking forward to seeing how it's handled in > your patch. Attached (don't remember the state of the patch, but of course some caching is missing here). >> >>> +/* The structure describing a non-overflow control induction variable >>> + of loop's exit edge. */ >>> +struct GTY ((chain_next ("%h.next"))) control_iv { >>> + tree base; >>> + tree step; >>> + struct control_iv *next; >>> +}; >> >> The comment suggests these don't exist for multiple edges? Maybe you >> can clarify this. > As the linked list structure suggests, we can support one no-overflow > iv for each loop's exit edge. I revised the comment a little bit. > >> >> Otherwise the patch looks ok. > > I attached the updated patch, does it look fine? Yes. Thanks, Richard. > Thanks, > bin >> >> Thanks, >> Richard.