Re: [PATCH GCC]Proving no-trappness for array ref in tree if-conv using loop niter information.

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

On Thu, Apr 28, 2016 at 2:56 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> Tree if-conversion sometimes cannot convert conditional array reference into unconditional one.  Root cause is GCC conservatively assumes newly introduced array reference could be out of array bound and thus trapping.  This patch improves the situation by proving the converted unconditional array reference is within array bound using loop niter information.  To be specific, it checks every index of array reference to see if it's within bound in ifcvt_memrefs_wont_trap.  This patch also factors out base_object_writable checking if the base object is writable or not.
> Bootstrap and test on x86_64 and aarch64, is it OK?

I think you miss to handle the case optimally where the only
non-ARRAY_REF idx is the dereference of the
base-pointer for, say, p->a[i].  In this case we can use
base_master_dr to see if p is unconditionally dereferenced
in the loop.  You also fail to handle the case where we have
MEM_REF[&x].a[i] that is, you see a decl base.
I suppose for_each_index should be fixed for this particular case (to
return true), same for TARGET_MEM_REF TMR_BASE.

+  /* The case of nonconstant bounds could be handled, but it would be
+     complicated.  */
+  if (TREE_CODE (low) != INTEGER_CST || !integer_zerop (low)
+      || !high || TREE_CODE (high) != INTEGER_CST)
+    return false;
+

handling of a non-zero but constant low bound is important - otherwise
all this is a no-op for Fortran.  It
shouldn't be too difficult to handle after all.  In fact I think your
code does handle it correctly already.

+  if (!init || TREE_CODE (init) != INTEGER_CST
+      || !step || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
+    return false;

step == 0 should be easy to handle as well, no?  The index will simply
always be 'init' ...

+  /* In case the relevant bound of the array does not fit in type, or
+     it does, but bound + step (in type) still belongs into the range of the
+     array, the index may wrap and still stay within the range of the array
+     (consider e.g. if the array is indexed by the full range of
+     unsigned char).
+
+     To make things simpler, we require both bounds to fit into type, although
+     there are cases where this would not be strictly necessary.  */
+  if (!int_fits_type_p (high, type) || !int_fits_type_p (low, type))
+    return false;
+
+  low = fold_convert (type, low);

please use wide_int for all of this.

I wonder if we can do sth for wrapping IVs like

int a[2048];

for (int i = 0; i < 4096; ++i)
  ... a[(unsigned char)i];

as well.  Like if the IVs type max and min value are within the array bounds
simply return true?

Thanks,
Richard.

> Thanks,
> bin
>
> 2016-04-28  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-if-conv.c (tree-ssa-loop.h): Include header file.
>         (tree-ssa-loop-niter.h): Ditto.
>         (idx_within_array_bound, ref_within_array_bound): New functions.
>         (ifcvt_memrefs_wont_trap): Check if array ref is within bound.
>         Factor out check on writable base object to ...
>         (base_object_writable): ... here.