RE: [PATCH]middle-end: check memory accesses in the destination block [PR113588].

[Richard Biener <rguenther@suse.de>]

On Tue, 30 Jan 2024, Tamar Christina wrote:

> > -----Original Message-----
> > From: Richard Biener <rguenther@suse.de>
> > Sent: Tuesday, January 30, 2024 9:51 AM
> > To: Tamar Christina <Tamar.Christina@arm.com>
> > Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; jlaw@ventanamicro.com
> > Subject: Re: [PATCH]middle-end: check memory accesses in the destination block
> > [PR113588].
> > 
> > On Mon, 29 Jan 2024, Tamar Christina wrote:
> > 
> > > Hi All,
> > >
> > > When analyzing loads for early break it was always the intention that
> > > for the exit where things get moved to we only check the loads that can
> > > be reached from the condition.
> > 
> > Looking at the code I'm a bit confused that we always move to
> > single_pred (loop->latch) - IIRC that was different at some point?
> > 
> > Shouldn't we move stores after the last early exit condition instead?
> 
> Yes it was changed during another PR fix.  The rationale at that time didn't take into account
> the peeled case.  It used to be that we would "search" for the the exit to place it in.
> 
> At that time the rational was, well it doesn't make sense. It has to go in the block that is the
> last to be executed.  With the non-peeled case it's always the one before the latch.
> 
> Or put differently, I think the destination should be the main IV block.  I am not quite sure
> I'm following why you want to put the peeled cases inside the latch block.
> 
> Ah, is it because the latch block is always going to only be executed when you make a full iteration?
> That makes sense, but then I think we should also analyze the stores in all blocks (which your change
> maybe already does, let me check) since we'll also lifting past the final block we need to update the vuses
> there too.
> 
> If the above is correct then I think I understand what you're saying and 
> will update the patch and do some Checks.

Yes, I think that's what I wanted to say.

Richard.

> Thanks,
> Tamar
> 
> > 
> > In particular for the peeled case single_pred (loop->latch) is the
> > block with the actual early exit condition?  So for that case we'd
> > need to move to the latch itself instead?  For non-peeled we move
> > to the block with the IV condition which looks OK.
> > 
> > > However the main loop checks all loads and we skip the destination BB.
> > > As such we never actually check the loads reachable from the COND in the
> > > last BB unless this BB was also the exit chosen by the vectorizer.
> > >
> > > This leads us to incorrectly vectorize the loop in the PR and in doing so access
> > > out of bounds.
> > >
> > > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues.
> > >
> > > Ok for master?
> > 
> > The patch ends up with a worklist and another confusing comment
> > 
> > +  /* For the destination BB we need to only analyze loads reachable from
> > the early
> > +     break statement itself.  */
> > 
> > But I think it's a downstream issue from the issue above.  That said,
> > even for the non-peeled case we need to check ref_within_array_bound,
> > no?
> > 
> > So what about re-doing that initial loop like the following instead
> > (and also fix dest_bb, but I'd like clarification here).  Basically
> > walk all blocks, do the ref_within_array_bound first and only
> > after we've seen 'dest_bb' do the checks required for moving
> > stores for all upstream BBs.
> > 
> > And dest_bb should be
> > 
> >   /* Move side-effects to the in-loop destination of the last early
> >      exit.  */
> >   if (LOOP_VINFO_EARLY_BREAKS_VECT_PEELED (loop_vinfo))
> >     dest_bb = loop->latch;
> >   else
> >     dest_bb = single_pred (loop->latch);
> > 
> > 
> > diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
> > index f592aeb8028..d6c8910dd6c 100644
> > --- a/gcc/tree-vect-data-refs.cc
> > +++ b/gcc/tree-vect-data-refs.cc
> > @@ -668,7 +668,6 @@ vect_analyze_early_break_dependences (loop_vec_info
> > loop_vinfo)
> >    auto_vec<data_reference *> bases;
> >    basic_block dest_bb = NULL;
> > 
> > -  hash_set <gimple *> visited;
> >    class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
> >    class loop *loop_nest = loop_outer (loop);
> > 
> > @@ -681,15 +680,11 @@ vect_analyze_early_break_dependences
> > (loop_vec_info loop_vinfo)
> >       side-effects to is always the latch connected exit.  When we support
> >       general control flow we can do better but for now this is fine.  */
> >    dest_bb = single_pred (loop->latch);
> > -  basic_block bb = dest_bb;
> > +  basic_block bb = loop->latch;
> > +  bool check_deps = false;
> > 
> >    do
> >      {
> > -      /* If the destination block is also the header then we have nothing to do.  */
> > -      if (!single_pred_p (bb))
> > -	continue;
> > -
> > -      bb = single_pred (bb);
> >        gimple_stmt_iterator gsi = gsi_last_bb (bb);
> > 
> >        /* Now analyze all the remaining statements and try to determine which
> > @@ -707,6 +702,25 @@ vect_analyze_early_break_dependences (loop_vec_info
> > loop_vinfo)
> >  	  if (!dr_ref)
> >  	    continue;
> > 
> > +	  /* Check if vector accesses to the object will be within bounds.
> > +	     must be a constant or assume loop will be versioned or niters
> > +	     bounded by VF so accesses are within range.  */
> > +	  if (!ref_within_array_bound (stmt, DR_REF (dr_ref)))
> > +	    {
> > +	      if (dump_enabled_p ())
> > +		dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > +				 "early breaks not supported: vectorization "
> > +				 "would %s beyond size of obj.",
> > +				 DR_IS_READ (dr_ref) ? "read" : "write");
> > +	      return opt_result::failure_at (stmt,
> > +				 "can't safely apply code motion to "
> > +				 "dependencies of %G to vectorize "
> > +				 "the early exit.\n", stmt);
> > +	    }
> > +
> > +	  if (!check_deps)
> > +	    continue;
> > +
> >  	  /* We currently only support statically allocated objects due to
> >  	     not having first-faulting loads support or peeling for
> >  	     alignment support.  Compute the size of the referenced object
> > @@ -739,22 +753,6 @@ vect_analyze_early_break_dependences (loop_vec_info
> > loop_vinfo)
> >  				 "the early exit.\n", stmt);
> >  	    }
> > 
> > -	  /* Check if vector accesses to the object will be within bounds.
> > -	     must be a constant or assume loop will be versioned or niters
> > -	     bounded by VF so accesses are within range.  */
> > -	  if (!ref_within_array_bound (stmt, DR_REF (dr_ref)))
> > -	    {
> > -	      if (dump_enabled_p ())
> > -		dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > -				 "early breaks not supported: vectorization "
> > -				 "would %s beyond size of obj.",
> > -				 DR_IS_READ (dr_ref) ? "read" : "write");
> > -	      return opt_result::failure_at (stmt,
> > -				 "can't safely apply code motion to "
> > -				 "dependencies of %G to vectorize "
> > -				 "the early exit.\n", stmt);
> > -	    }
> > -
> >  	  if (DR_IS_READ (dr_ref))
> >  	    bases.safe_push (dr_ref);
> >  	  else if (DR_IS_WRITE (dr_ref))
> > @@ -814,8 +812,16 @@ vect_analyze_early_break_dependences (loop_vec_info
> > loop_vinfo)
> >  				 "marked statement for vUSE update: %G", stmt);
> >  	    }
> >  	}
> > +      if (!single_pred_p (bb))
> > +	{
> > +	  gcc_assert (bb == loop->header);
> > +	  break;
> > +	}
> > +      if (bb == dest_bb)
> > +	check_deps = true;
> > +      bb = single_pred (bb);
> >      }
> > -  while (bb != loop->header);
> > +  while (1);
> > 
> >    /* We don't allow outer -> inner loop transitions which should have been
> >       trapped already during loop form analysis.  */
> > 
> > > Thanks,
> > > Tamar
> > >
> > > gcc/ChangeLog:
> > >
> > > 	PR tree-optimization/113588
> > > 	* tree-vect-data-refs.cc (vect_analyze_early_break_dependences_1): New.
> > > 	(vect_analyze_data_ref_dependence):  Use it.
> > > 	(vect_analyze_early_break_dependences): Update comments.
> > >
> > > gcc/testsuite/ChangeLog:
> > >
> > > 	PR tree-optimization/113588
> > > 	* gcc.dg/vect/vect-early-break_108-pr113588.c: New test.
> > > 	* gcc.dg/vect/vect-early-break_109-pr113588.c: New test.
> > >
> > > --- inline copy of patch --
> > > diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_108-pr113588.c
> > b/gcc/testsuite/gcc.dg/vect/vect-early-break_108-pr113588.c
> > > new file mode 100644
> > > index
> > 0000000000000000000000000000000000000000..e488619c9aac41fafbcf479
> > 818392a6bb7c6924f
> > > --- /dev/null
> > > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_108-pr113588.c
> > > @@ -0,0 +1,15 @@
> > > +/* { dg-do compile } */
> > > +/* { dg-add-options vect_early_break } */
> > > +/* { dg-require-effective-target vect_early_break } */
> > > +/* { dg-require-effective-target vect_int } */
> > > +
> > > +/* { dg-final { scan-tree-dump-not "LOOP VECTORIZED" "vect" } } */
> > > +
> > > +int foo (const char *s, unsigned long n)
> > > +{
> > > + unsigned long len = 0;
> > > + while (*s++ && n--)
> > > +   ++len;
> > > + return len;
> > > +}
> > > +
> > > diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_109-pr113588.c
> > b/gcc/testsuite/gcc.dg/vect/vect-early-break_109-pr113588.c
> > > new file mode 100644
> > > index
> > 0000000000000000000000000000000000000000..488c19d3ede809631d1a7
> > ede0e7f7bcdc7a1ae43
> > > --- /dev/null
> > > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_109-pr113588.c
> > > @@ -0,0 +1,44 @@
> > > +/* { dg-add-options vect_early_break } */
> > > +/* { dg-require-effective-target vect_early_break } */
> > > +/* { dg-require-effective-target vect_int } */
> > > +/* { dg-require-effective-target mmap } */
> > > +
> > > +/* { dg-final { scan-tree-dump-not "LOOP VECTORIZED" "vect" } } */
> > > +
> > > +#include <sys/mman.h>
> > > +#include <unistd.h>
> > > +
> > > +#include "tree-vect.h"
> > > +
> > > +__attribute__((noipa))
> > > +int foo (const char *s, unsigned long n)
> > > +{
> > > + unsigned long len = 0;
> > > + while (*s++ && n--)
> > > +   ++len;
> > > + return len;
> > > +}
> > > +
> > > +int main()
> > > +{
> > > +
> > > +  check_vect ();
> > > +
> > > +  long pgsz = sysconf (_SC_PAGESIZE);
> > > +  void *p = mmap (NULL, pgsz * 3, PROT_READ|PROT_WRITE,
> > > +     MAP_ANONYMOUS|MAP_PRIVATE, 0, 0);
> > > +  if (p == MAP_FAILED)
> > > +    return 0;
> > > +  mprotect (p, pgsz, PROT_NONE);
> > > +  mprotect (p+2*pgsz, pgsz, PROT_NONE);
> > > +  char *p1 = p + pgsz;
> > > +  p1[0] = 1;
> > > +  p1[1] = 0;
> > > +  foo (p1, 1000);
> > > +  p1 = p + 2*pgsz - 2;
> > > +  p1[0] = 1;
> > > +  p1[1] = 0;
> > > +  foo (p1, 1000);
> > > +  return 0;
> > > +}
> > > +
> > > diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
> > > index
> > f592aeb8028afd4fd70e2175104efab2a2c0d82e..52cef242a7ce5d0e525bff639fa
> > 1dc2f0a6f30b9 100644
> > > --- a/gcc/tree-vect-data-refs.cc
> > > +++ b/gcc/tree-vect-data-refs.cc
> > > @@ -619,10 +619,69 @@ vect_analyze_data_ref_dependence (struct
> > data_dependence_relation *ddr,
> > >    return opt_result::success ();
> > >  }
> > >
> > > -/* Funcion vect_analyze_early_break_dependences.
> > > +/* Function vect_analyze_early_break_dependences_1
> > >
> > > -   Examime all the data references in the loop and make sure that if we have
> > > -   mulitple exits that we are able to safely move stores such that they become
> > > +   Helper function of vect_analyze_early_break_dependences which performs
> > safety
> > > +   analysis for load operations in an early break.  */
> > > +
> > > +static opt_result
> > > +vect_analyze_early_break_dependences_1 (data_reference *dr_ref, gimple
> > *stmt)
> > > +{
> > > +  /* We currently only support statically allocated objects due to
> > > +     not having first-faulting loads support or peeling for
> > > +     alignment support.  Compute the size of the referenced object
> > > +     (it could be dynamically allocated).  */
> > > +  tree obj = DR_BASE_ADDRESS (dr_ref);
> > > +  if (!obj || TREE_CODE (obj) != ADDR_EXPR)
> > > +    {
> > > +      if (dump_enabled_p ())
> > > +	dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > > +			 "early breaks only supported on statically"
> > > +			 " allocated objects.\n");
> > > +      return opt_result::failure_at (stmt,
> > > +			 "can't safely apply code motion to "
> > > +			 "dependencies of %G to vectorize "
> > > +			 "the early exit.\n", stmt);
> > > +    }
> > > +
> > > +  tree refop = TREE_OPERAND (obj, 0);
> > > +  tree refbase = get_base_address (refop);
> > > +  if (!refbase || !DECL_P (refbase) || !DECL_SIZE (refbase)
> > > +      || TREE_CODE (DECL_SIZE (refbase)) != INTEGER_CST)
> > > +    {
> > > +      if (dump_enabled_p ())
> > > +	dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > > +			 "early breaks only supported on"
> > > +			 " statically allocated objects.\n");
> > > +      return opt_result::failure_at (stmt,
> > > +			 "can't safely apply code motion to "
> > > +			 "dependencies of %G to vectorize "
> > > +			 "the early exit.\n", stmt);
> > > +    }
> > > +
> > > +  /* Check if vector accesses to the object will be within bounds.
> > > +     must be a constant or assume loop will be versioned or niters
> > > +     bounded by VF so accesses are within range.  */
> > > +  if (!ref_within_array_bound (stmt, DR_REF (dr_ref)))
> > > +    {
> > > +      if (dump_enabled_p ())
> > > +	dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > > +			 "early breaks not supported: vectorization "
> > > +			 "would %s beyond size of obj.",
> > > +			 DR_IS_READ (dr_ref) ? "read" : "write");
> > > +      return opt_result::failure_at (stmt,
> > > +			 "can't safely apply code motion to "
> > > +			 "dependencies of %G to vectorize "
> > > +			 "the early exit.\n", stmt);
> > > +    }
> > > +
> > > +  return opt_result::success ();
> > > +}
> > > +
> > > +/* Function vect_analyze_early_break_dependences.
> > > +
> > > +   Examine all the data references in the loop and make sure that if we have
> > > +   multiple exits that we are able to safely move stores such that they become
> > >     safe for vectorization.  The function also calculates the place where to move
> > >     the instructions to and computes what the new vUSE chain should be.
> > >
> > > @@ -639,7 +698,7 @@ vect_analyze_data_ref_dependence (struct
> > data_dependence_relation *ddr,
> > >       - Multiple loads are allowed as long as they don't alias.
> > >
> > >     NOTE:
> > > -     This implemementation is very conservative. Any overlappig loads/stores
> > > +     This implementation is very conservative. Any overlapping loads/stores
> > >       that take place before the early break statement gets rejected aside from
> > >       WAR dependencies.
> > >
> > > @@ -668,7 +727,6 @@ vect_analyze_early_break_dependences (loop_vec_info
> > loop_vinfo)
> > >    auto_vec<data_reference *> bases;
> > >    basic_block dest_bb = NULL;
> > >
> > > -  hash_set <gimple *> visited;
> > >    class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
> > >    class loop *loop_nest = loop_outer (loop);
> > >
> > > @@ -683,6 +741,7 @@ vect_analyze_early_break_dependences (loop_vec_info
> > loop_vinfo)
> > >    dest_bb = single_pred (loop->latch);
> > >    basic_block bb = dest_bb;
> > >
> > > +  /* First analyse all blocks leading to dest_bb excluding dest_bb itself.  */
> > >    do
> > >      {
> > >        /* If the destination block is also the header then we have nothing to do.  */
> > > @@ -707,53 +766,11 @@ vect_analyze_early_break_dependences
> > (loop_vec_info loop_vinfo)
> > >  	  if (!dr_ref)
> > >  	    continue;
> > >
> > > -	  /* We currently only support statically allocated objects due to
> > > -	     not having first-faulting loads support or peeling for
> > > -	     alignment support.  Compute the size of the referenced object
> > > -	     (it could be dynamically allocated).  */
> > > -	  tree obj = DR_BASE_ADDRESS (dr_ref);
> > > -	  if (!obj || TREE_CODE (obj) != ADDR_EXPR)
> > > -	    {
> > > -	      if (dump_enabled_p ())
> > > -		dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > > -				 "early breaks only supported on statically"
> > > -				 " allocated objects.\n");
> > > -	      return opt_result::failure_at (stmt,
> > > -				 "can't safely apply code motion to "
> > > -				 "dependencies of %G to vectorize "
> > > -				 "the early exit.\n", stmt);
> > > -	    }
> > > -
> > > -	  tree refop = TREE_OPERAND (obj, 0);
> > > -	  tree refbase = get_base_address (refop);
> > > -	  if (!refbase || !DECL_P (refbase) || !DECL_SIZE (refbase)
> > > -	      || TREE_CODE (DECL_SIZE (refbase)) != INTEGER_CST)
> > > -	    {
> > > -	      if (dump_enabled_p ())
> > > -		dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > > -				 "early breaks only supported on"
> > > -				 " statically allocated objects.\n");
> > > -	      return opt_result::failure_at (stmt,
> > > -				 "can't safely apply code motion to "
> > > -				 "dependencies of %G to vectorize "
> > > -				 "the early exit.\n", stmt);
> > > -	    }
> > > -
> > > -	  /* Check if vector accesses to the object will be within bounds.
> > > -	     must be a constant or assume loop will be versioned or niters
> > > -	     bounded by VF so accesses are within range.  */
> > > -	  if (!ref_within_array_bound (stmt, DR_REF (dr_ref)))
> > > -	    {
> > > -	      if (dump_enabled_p ())
> > > -		dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
> > > -				 "early breaks not supported: vectorization "
> > > -				 "would %s beyond size of obj.",
> > > -				 DR_IS_READ (dr_ref) ? "read" : "write");
> > > -	      return opt_result::failure_at (stmt,
> > > -				 "can't safely apply code motion to "
> > > -				 "dependencies of %G to vectorize "
> > > -				 "the early exit.\n", stmt);
> > > -	    }
> > > +	  /* Check if the operation is one we can safely do.  */
> > > +	  opt_result res
> > > +	    = vect_analyze_early_break_dependences_1 (dr_ref, stmt);
> > > +	  if (!res)
> > > +	    return res;
> > >
> > >  	  if (DR_IS_READ (dr_ref))
> > >  	    bases.safe_push (dr_ref);
> > > @@ -817,6 +834,51 @@ vect_analyze_early_break_dependences
> > (loop_vec_info loop_vinfo)
> > >      }
> > >    while (bb != loop->header);
> > >
> > > +  /* For the destination BB we need to only analyze loads reachable from the
> > early
> > > +     break statement itself.  */
> > > +  auto_vec <tree> workset;
> > > +  hash_set <tree> visited;
> > > +  gimple *last_stmt = gsi_stmt (gsi_last_bb (dest_bb));
> > > +  gcond *last_cond = dyn_cast <gcond *> (last_stmt);
> > > +  /* If the cast fails we have a different control flow statement in the latch.  Most
> > > +     commonly this is a switch.  */
> > > +  if (!last_cond)
> > > +   return opt_result::failure_at (last_stmt,
> > > +			     "can't safely apply code motion to dependencies"
> > > +			     " to vectorize the early exit, unknown control fow"
> > > +			     " in stmt %G", last_stmt);
> > > +  workset.safe_push (gimple_cond_lhs (last_cond));
> > > +  workset.safe_push (gimple_cond_rhs (last_cond));
> > > +
> > > +  imm_use_iterator imm_iter;
> > > +  use_operand_p use_p;
> > > +  tree lhs;
> > > +  do
> > > +    {
> > > +      tree op = workset.pop ();
> > > +      if (visited.add (op))
> > > +	continue;
> > > +      stmt_vec_info stmt_vinfo = loop_vinfo->lookup_def (op);
> > > +
> > > +      /* Not defined in loop, don't care.  */
> > > +      if (!stmt_vinfo)
> > > +	continue;
> > > +      gimple *stmt = STMT_VINFO_STMT (stmt_vinfo);
> > > +      auto dr_ref = STMT_VINFO_DATA_REF (stmt_vinfo);
> > > +      if (dr_ref)
> > > +	{
> > > +	  opt_result res
> > > +	    = vect_analyze_early_break_dependences_1 (dr_ref, stmt);
> > > +	  if (!res)
> > > +	    return res;
> > > +	}
> > > +      else
> > > +	FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
> > > +	  if ((lhs = gimple_get_lhs (USE_STMT (use_p))))
> > > +	    workset.safe_push (lhs);
> > > +    }
> > > +  while (!workset.is_empty ());
> > > +
> > >    /* We don't allow outer -> inner loop transitions which should have been
> > >       trapped already during loop form analysis.  */
> > >    gcc_assert (dest_bb->loop_father == loop);
> > >
> > >
> > >
> > >
> > >
> > 
> > --
> > Richard Biener <rguenther@suse.de>
> > SUSE Software Solutions Germany GmbH,
> > Frankenstrasse 146, 90461 Nuernberg, Germany;
> > GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)