public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Richard Sandiford <richard.sandiford@linaro.org>
To: Bin Cheng <Bin.Cheng@arm.com>
Cc: "gcc-patches\@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,  nd <nd@arm.com>
Subject: Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
Date: Tue, 23 May 2017 17:56:00 -0000	[thread overview]
Message-ID: <87r2zfzch4.fsf@linaro.org> (raw)
In-Reply-To: <VI1PR0802MB2176A0FA67956247E4503D5DE7F90@VI1PR0802MB2176.eurprd08.prod.outlook.com>	(Bin Cheng's message of "Tue, 23 May 2017 16:23:00 +0000")

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--;
>   	    }
>   	}
>       }

  reply	other threads:[~2017-05-23 17:53 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-05-23 16:23 Bin Cheng
2017-05-23 17:56 ` Richard Sandiford [this message]
2017-05-24 10:54   ` Bin.Cheng
2017-05-24 10:55     ` Richard Sandiford
2017-05-25 15:16       ` Bin.Cheng
2017-05-26 11:43         ` Richard Biener
2017-05-26 12:01           ` Bin.Cheng
2017-05-26 12:31             ` Richard Biener

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=87r2zfzch4.fsf@linaro.org \
    --to=richard.sandiford@linaro.org \
    --cc=Bin.Cheng@arm.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=nd@arm.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).