Re: [PATCH GCC][PR62173 partial/2]Improve overflow check on SCEV in IVOPTs using vrp info

[Richard Biener <richard dot guenther at gmail dot com>]

On Fri, Feb 13, 2015 at 10:43 AM, Bin Cheng <bin.cheng@arm.com> wrote:
> Hi,
> For the specific case reported in PR62173, overflow check on SCEV can be
> improved using range information.  Precisely, it's range information of ssa
> name in IV's base that helps, rather than range information of the IV
> itself.  Since the IV is computed in the form of "IV_var = <var_base,
> IV_var_offset>" in loop header, we can derive that var_base takes IV_var's
> range information in the loop.  Even though this may not hold in other parts
> of program.  To address this, this patch iterates each phi node in loop's
> header and propagates range information from IV to base var.  Of course, the
> range information should be restored after IVOPTs.  For now, we only
> propagate IV's range information to base var if it hasn't had it.  This can
> be extended to refine the existing range information.
> Moreover, because of loop header copying, it's very likely to have entry
> condition for the loop.  we also use this to further improve the range
> information.  The patch does this by iterating upwards in dominator tree.
> Actually the range information wouldn't be enough in this exact case.
>
> I was told this causes small regression in some benchmark.  But I did saw
> inner-most loops are improved obviously with this and the hotspot of that
> benchmark isn't affected at all.  I will further go through all the code
> changes later.  Also there are couple of possible improvement, for example,
> factor out the macro; don't iterate dominating tree repeatedly for each phi
> node.
>
> It passes bootstrap and regtest on both x86_64 and aarch64.  But I would
> like to hear more comments on the idea itself then do some refinement.
> So any comments?

+       /* 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?

+            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.

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).

+/* 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.

Otherwise the patch looks ok.

Thanks,
Richard.


> Thanks,
> bin
>
> 2015-02-13  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/62173
>         * tree-ssa-loop-niter.h (split_to_var_and_offset): Expose it.
>         (refine_bounds_using_guard): Expose it.  Change parameters by
>         using below, up directly.
>         * tree-ssa-loop-niter.c (split_to_var_and_offset): Expose it.
>         (refine_bounds_using_guard): Expose it.  Change parameters by
>         using below, up directly.
>         (bound_difference): Change arguments.
>         (scev_probably_wraps_p): Use range info when checking wrap behavior.
>         * tree-ssa-loop-ivopts.c (name_range_info_map): New field in struct
>         ivopts_data.
>         (tree_ssa_iv_optimize_init): Initialize name_range_info_map.
>         (tree_ssa_iv_optimize_finalize): Release name_range_info_map.
>         (MAX_DOMINATORS_TO_WALK): New macro.
>         (refine_ssa_name_range_info, refine_range_info_for_loop)
>         (restore_range_info_for_loop): New functions.
>         (tree_ssa_iv_optimize): Refine and restore range info for loop.
>
> gcc/testsuite/ChangeLog
> 2015-02-13  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/62173
>         * gcc.dg/tree-ssa/pr62173.c: New test.