This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check


AIUI, the reason the old code mishandled negative steps was that the
associated segment lengths were stored as sizetype and so looked like
big unsigned values.  Those values therefore satisfied tree_fits_uhwi_p
even though they were semantically negative.  Is that right?

Assuming yes, and quoting the change as a context diff...

> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> index a5f8c1c..f0799d9 100644
> *** a/gcc/tree-data-ref.c
> --- b/gcc/tree-data-ref.c
> ***************
> *** 1259,1264 ****
> --- 1259,1273 ----
>   	      != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node))
>   	    continue;
>  
> + 	  bool neg_step
> + 	    = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0);
> + 
> + 	  /* DR_A1 and DR_A2 must have the same step if it's negative.  */
> + 	  if (neg_step
> + 	      && tree_int_cst_compare (DR_STEP (dr_a1->dr),
> + 				       DR_STEP (dr_a2->dr)) != 0)
> + 	    continue;
> +

[Why do they need to be the same step?]

>   	  /* Make sure dr_a1 starts left of dr_a2.  */
>   	  if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
>   	    std::swap (*dr_a1, *dr_a2);
> ***************
> *** 1266,1325 ****
>   	  bool do_remove = false;
>   	  unsigned HOST_WIDE_INT diff
>   	    = (tree_to_shwi (DR_INIT (dr_a2->dr))
> !                - tree_to_shwi (DR_INIT (dr_a1->dr)));
>  
> ! 	  /* If the left segment does not extend beyond the start of the
> ! 	     right segment the new segment length is that of the right
> ! 	     plus the segment distance.  */
> ! 	  if (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 	      && compare_tree_int (dr_a1->seg_len, diff) <= 0)
>   	    {
> ! 	      dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
> ! 					   size_int (diff));
> ! 	      do_remove = true;
>   	    }
> ! 	  /* Generally the new segment length is the maximum of the
> ! 	     left segment size and the right segment size plus the distance.
> ! 	     ???  We can also build tree MAX_EXPR here but it's not clear this
> ! 	     is profitable.  */
> ! 	  else if (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		   && tree_fits_uhwi_p (dr_a2->seg_len))
> ! 	    {
> ! 	      unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
> ! 	      unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
> ! 	      dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
> ! 	      do_remove = true;
> ! 	    }
> ! 	  /* Now we check if the following condition is satisfied:
>  
> ! 	     DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
>  
> ! 	     where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
> ! 	     SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
> ! 	     have to make a best estimation.  We can get the minimum value
> ! 	     of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
> ! 	     then either of the following two conditions can guarantee the
> ! 	     one above:
>  
> ! 	     1: DIFF <= MIN_SEG_LEN_B
> ! 	     2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
> ! 	  else
>   	    {
> ! 	      unsigned HOST_WIDE_INT min_seg_len_b
> ! 		= (tree_fits_uhwi_p (dr_b1->seg_len)
> ! 		   ? tree_to_uhwi (dr_b1->seg_len)
> ! 		   : factor);
>  
>   	      if (diff <= min_seg_len_b
>   		  || (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
>   		{
> ! 		  dr_a1->seg_len = size_binop (PLUS_EXPR,
> ! 					       dr_a2->seg_len, size_int (diff));
>   		  do_remove = true;
>   		}
>   	    }
>  
>   	  if (do_remove)
>   	    {
>   	      if (dump_enabled_p ())
> --- 1275,1375 ----
>   	  bool do_remove = false;
>   	  unsigned HOST_WIDE_INT diff
>   	    = (tree_to_shwi (DR_INIT (dr_a2->dr))
> ! 	       - tree_to_shwi (DR_INIT (dr_a1->dr)));
> ! 	  tree new_seg_len;
> ! 	  unsigned HOST_WIDE_INT min_seg_len_b;
>  
> ! 	  if (tree_fits_uhwi_p (dr_b1->seg_len))
>   	    {
> ! 	      min_seg_len_b = tree_to_uhwi (dr_b1->seg_len);
> ! 	      if (tree_int_cst_sign_bit (dr_b1->seg_len))
> ! 		min_seg_len_b = 0 - min_seg_len_b;
>   	    }
> ! 	  else
> ! 	    min_seg_len_b = factor;

...I'm not sure how safe this or the later neg_step handling is
for 16-bit and 32-bit sizetypes.  It might be better to use wide_int
instead, so that all arithmetic and comparisons happen in the precision
of sizetype.

The situation seems very close to RTL in the sense that the segment
length has no inherent sign and we have to instead get the sign from
the DR_STEP.  Unless we can change that of course...

>  
> ! 	  /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b.
>  
> ! 	     Case A:
> ! 	       check if the following condition is satisfied:
>  
> ! 	       DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
> ! 
> ! 	       where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
> ! 	       SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
> ! 	       have to make a best estimation.  We can get the minimum value
> ! 	       of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
> ! 	       then either of the following two conditions can guarantee the
> ! 	       one above:
> ! 
> ! 	       1: DIFF <= MIN_SEG_LEN_B
> ! 	       2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B
> ! 		  Because DIFF - SEGMENT_LENGTH_A is done in sizetype, we need
> ! 		  to take care of wrapping behavior in it.
> ! 
> ! 	     Case B:
> ! 	       If the left segment does not extend beyond the start of the
> ! 	       right segment the new segment length is that of the right
> ! 	       plus the segment distance.
> ! 
> ! 	     Note 1: Case A.2 and B combined together effectively merges every
> ! 	     dr_a1 & dr_b and dr_a2 & dr_b when SEGMENT_LENGTH_A is const.  We
> ! 	     test them separately for clarity, also because Case A never
> ! 	     introduces false alias, while Case B does.
> ! 
> ! 	     Note 2: Above description is based on positive DR_STEP, we need to
> ! 	     take care of negative DR_STEP for wrapping behavior.  See PR80815
> ! 	     for more information.  */
> ! 	  if (neg_step)
>   	    {
> ! 	      /* Case A.  */
> ! 	      if (diff <= min_seg_len_b
> ! 		  || (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && (diff + tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b
> ! 			  || diff < 0 - tree_to_uhwi (dr_a1->seg_len)))
> ! 		  /* Case B.  */
> ! 		  || (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && diff > 0 - tree_to_uhwi (dr_a1->seg_len)))

a2 is to the right of a1, and both segment lengths are conceptually
negative, so I think this should be using dr_a2->seg_len instead of
dr_a1->seg_len.  E.g. for A.2, A2's segment overlaps A1's if

  diff < 0 - tree_to_uhwi (dr_a2->seg_len)

TBH, given that the comment has already explained why this reduces to:

  (diff <= min_seg_len_b
   || TREE_CODE (dr_a2(?)->seg_len) == INTEGER_CST)

I think it'd better just to write that.  The clarity kind-of belongs in the
comments instead.

> ! 		{
> ! 		  if (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && tree_fits_uhwi_p (dr_a2->seg_len))
> ! 		    new_seg_len
> ! 		      = size_int (MIN (tree_to_uhwi (dr_a1->seg_len),
> ! 				       tree_to_uhwi (dr_a2->seg_len) - diff));
> ! 		  else
> ! 		    new_seg_len = size_binop (MINUS_EXPR,
> ! 					      dr_a2->seg_len, size_int (diff));
>  
> + 		  dr_a2->seg_len = new_seg_len;
> + 		  do_remove = true;
> + 		}
> + 	    }
> + 	  else
> + 	    {
> + 	      /* Case A.  */
>   	      if (diff <= min_seg_len_b
>   		  || (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && (diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b
> ! 			  || diff < tree_to_uhwi (dr_a1->seg_len)))
> ! 		  /* Case B.  */
> ! 		  || (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && diff > tree_to_uhwi (dr_a1->seg_len)))
>   		{
> ! 		  if (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && tree_fits_uhwi_p (dr_a2->seg_len))
> ! 		    new_seg_len
> ! 		      = size_int (MAX (tree_to_uhwi (dr_a1->seg_len),
> ! 				       diff + tree_to_uhwi (dr_a2->seg_len)));
> ! 		  else
> ! 		    new_seg_len
> ! 		      = size_binop (PLUS_EXPR, dr_a2->seg_len, size_int (diff));
> ! 
> ! 		  dr_a1->seg_len = new_seg_len;
>   		  do_remove = true;
>   		}
>   	    }
>  
> + 
>   	  if (do_remove)
>   	    {
>   	      if (dump_enabled_p ())
> ***************
> *** 1334,1340 ****
>   		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
>   		  dump_printf (MSG_NOTE, "\n");
>   		}
> ! 	      alias_pairs->ordered_remove (i--);
>   	    }
>   	}
>       }
> - - 
> --- 1384,1391 ----
>   		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
>   		  dump_printf (MSG_NOTE, "\n");
>   		}
> ! 	      alias_pairs->ordered_remove (neg_step ? i - 1 : i);
> ! 	      i--;
>   	    }
>   	}
>       }


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]