Re: [PR80803 2/2] Diligent queuing in SRA grp_write prop

[Richard Biener <rguenther at suse dot de>]

On Mon, 12 Jun 2017, Martin Jambor wrote:

> Hi,
> 
> the patch below fixes PR 80803 (and its newer duplicate 81063), it is
> essentially a semi-rewrite of propagate_subaccesses_across_link.
> 
> When fixing the previous fallout from lazy setting of grp_write flag,
> I failed to see that it does not look on sub-accesses of the LHSs at
> all and thus does not ensure proper transitive propagation if the RHS
> does not have an access that LHS has.  The patch fixes it by
> meticulous checking and invoking subtree_mark_written_and_enqueue to
> handle such cases.
> 
> This might seem like a lot of enqueuing but an access is only enqueued
> if its grp_write bit has been set or if new sub-accesses have been
> created under it, so the number of invocations of
> add_access_to_work_queue is bounded by the number of aggregate
> assignments in the function and twice the number of access
> representatives, so nothing drastic.
> 
> An almost identical patch has passed bootstrap and testing on
> x86_64-linux (all languages including Ada and Go), powerpc64le-linux
> (all languages except Ada but including Go) and Aarch64-linux (the
> same).  I am bootstrapping and testing this very same one on an
> x86_64-linux right now, just to be sure.  OK for trunk?
> 
> Thanks,
> 
> Martin
> 
> 
> 
> 2017-06-12  Martin Jambor  <mjambor@suse.cz>
> 
> 	PR tree-optimization/80803
> 	PR tree-optimization/81063
> 	* tree-sra.c (subtree_mark_written_and_enqueue): Move up in the file.
> 	(propagate_subaccesses_across_link): Enqueue subtree whneve necessary

whenever

Ok.

Thanks,
Richard.

> 	instead of relying on the caller.
> 
> testsuite/
> 	gcc.dg/tree-ssa/pr80803.c: New test.
> 	gcc.dg/tree-ssa/pr81063.c: Likewise.
> 
> 
> *** /dev/null	Mon Jun 12 10:27:38 2017
> --- gcc/testsuite/gcc.dg/tree-ssa/pr80803.c	Mon Jun 12 18:24:30 2017
> ***************
> *** 0 ****
> --- 1,72 ----
> + /* { dg-do run } */
> + /* { dg-options "-O" } */
> + 
> + struct S0
> + {
> +   unsigned a : 15;
> +   int b;
> +   int c;
> + };
> + 
> + struct S1
> + {
> +   struct S0 s0;
> +   int e;
> + };
> + 
> + struct Z
> + {
> +   char c;
> +   int z;
> + } __attribute__((packed));
> + 
> + union U
> + {
> +   struct S1 s1;
> +   struct Z z;
> + };
> + 
> + 
> + int __attribute__((noinline, noclone))
> + return_zero (void)
> + {
> +   return 0;
> + }
> + 
> + volatile union U gu;
> + struct S0 gs;
> + 
> + int __attribute__((noinline, noclone))
> + check_outcome ()
> + {
> +   if (gs.a != 6
> +       || gs.b != 80000)
> +     __builtin_abort ();
> + }
> + 
> + int
> + main (int argc, char *argv[])
> + {
> +   union U u;
> +   struct S1 m,n;
> +   struct S0 l;
> + 
> +   if (return_zero ())
> +     u.z.z = 20000;
> +   else
> +     {
> +       u.s1.s0.a = 6;
> +       u.s1.s0.b = 80000;
> +       u.s1.e = 2;
> + 
> +       n = u.s1;
> +       m = n;
> +       m.s0.c = 0;
> +       l = m.s0;
> +       gs = l;
> +     }
> + 
> +   gu = u;
> +   check_outcome ();
> +   return 0;
> + }
> *** /dev/null	Mon Jun 12 10:27:38 2017
> --- gcc/testsuite/gcc.dg/tree-ssa/pr81063.c	Mon Jun 12 18:24:30 2017
> ***************
> *** 0 ****
> --- 1,28 ----
> + /* { dg-do run } */
> + /* { dg-options "-O" } */
> + 
> + struct A
> + {
> +   int b;
> +   int c:2;
> + };
> + 
> + struct B
> + {
> +   int e;
> +   struct A f;
> + } g = {0, {0, 1}}, j;
> + 
> + struct A *h = &g.f;
> + 
> + int main ()
> + {
> +   struct A k;
> +   struct B l = j, i = l;
> +   if (!i.f.b)
> +     k = i.f;
> +   *h = k;
> +   if (g.f.c != 0)
> +     __builtin_abort ();
> +   return 0;
> + }
> *** /tmp/Xkl4Ch_tree-sra.c	Mon Jun 12 18:33:42 2017
> --- gcc/tree-sra.c	Mon Jun 12 18:24:30 2017
> *************** create_artificial_child_access (struct a
> *** 2558,2566 ****
>   }
>   
>   
> ! /* Propagate all subaccesses of RACC across an assignment link to LACC. Return
> !    true if any new subaccess was created.  Additionally, if RACC is a scalar
> !    access but LACC is not, change the type of the latter, if possible.  */
>   
>   static bool
>   propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
> --- 2558,2585 ----
>   }
>   
>   
> ! /* Beginning with ACCESS, traverse its whole access subtree and mark all
> !    sub-trees as written to.  If any of them has not been marked so previously
> !    and has assignment links leading from it, re-enqueue it.  */
> ! 
> ! static void
> ! subtree_mark_written_and_enqueue (struct access *access)
> ! {
> !   if (access->grp_write)
> !     return;
> !   access->grp_write = true;
> !   add_access_to_work_queue (access);
> ! 
> !   struct access *child;
> !   for (child = access->first_child; child; child = child->next_sibling)
> !     subtree_mark_written_and_enqueue (child);
> ! }
> ! 
> ! /* Propagate subaccesses and grp_write flags of RACC across an assignment link
> !    to LACC.  Enqueue sub-accesses as necessary so that the write flag is
> !    propagated transitively.  Return true if anything changed.  Additionally, if
> !    RACC is a scalar access but LACC is not, change the type of the latter, if
> !    possible.  */
>   
>   static bool
>   propagate_subaccesses_across_link (struct access *lacc, struct access *racc)
> *************** propagate_subaccesses_across_link (struc
> *** 2576,2582 ****
>         gcc_checking_assert (!comes_initialized_p (racc->base));
>         if (racc->grp_write)
>   	{
> ! 	  lacc->grp_write = true;
>   	  ret = true;
>   	}
>       }
> --- 2595,2601 ----
>         gcc_checking_assert (!comes_initialized_p (racc->base));
>         if (racc->grp_write)
>   	{
> ! 	  subtree_mark_written_and_enqueue (lacc);
>   	  ret = true;
>   	}
>       }
> *************** propagate_subaccesses_across_link (struc
> *** 2585,2597 ****
>         || lacc->grp_unscalarizable_region
>         || racc->grp_unscalarizable_region)
>       {
> !       ret |= !lacc->grp_write;
> !       lacc->grp_write = true;
>         return ret;
>       }
>   
>     if (is_gimple_reg_type (racc->type))
>       {
>         if (!lacc->first_child && !racc->first_child)
>   	{
>   	  tree t = lacc->base;
> --- 2604,2624 ----
>         || lacc->grp_unscalarizable_region
>         || racc->grp_unscalarizable_region)
>       {
> !       if (!lacc->grp_write)
> ! 	{
> ! 	  ret = true;
> ! 	  subtree_mark_written_and_enqueue (lacc);
> ! 	}
>         return ret;
>       }
>   
>     if (is_gimple_reg_type (racc->type))
>       {
> +       if (!lacc->grp_write)
> + 	{
> + 	  ret = true;
> + 	  subtree_mark_written_and_enqueue (lacc);
> + 	}
>         if (!lacc->first_child && !racc->first_child)
>   	{
>   	  tree t = lacc->base;
> *************** propagate_subaccesses_across_link (struc
> *** 2616,2636 ****
>         struct access *new_acc = NULL;
>         HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
>   
> -       if (rchild->grp_unscalarizable_region)
> - 	{
> - 	  lacc->grp_write = true;
> - 	  continue;
> - 	}
> - 
>         if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
>   					&new_acc))
>   	{
>   	  if (new_acc)
>   	    {
> ! 	      if (!new_acc->grp_write
> ! 		  && (lacc->grp_write || rchild->grp_write))
>   		{
> ! 		  new_acc ->grp_write = true;
>   		  ret = true;
>   		}
>   
> --- 2643,2657 ----
>         struct access *new_acc = NULL;
>         HOST_WIDE_INT norm_offset = rchild->offset + norm_delta;
>   
>         if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size,
>   					&new_acc))
>   	{
>   	  if (new_acc)
>   	    {
> ! 	      if (!new_acc->grp_write && rchild->grp_write)
>   		{
> ! 		  gcc_assert (!lacc->grp_write);
> ! 		  subtree_mark_written_and_enqueue (new_acc);
>   		  ret = true;
>   		}
>   
> *************** propagate_subaccesses_across_link (struc
> *** 2640,2646 ****
>   		ret |= propagate_subaccesses_across_link (new_acc, rchild);
>   	    }
>   	  else
> ! 	    lacc->grp_write = true;
>   	  continue;
>   	}
>   
> --- 2661,2683 ----
>   		ret |= propagate_subaccesses_across_link (new_acc, rchild);
>   	    }
>   	  else
> ! 	    {
> ! 	      if (rchild->grp_write && !lacc->grp_write)
> ! 		{
> ! 		  ret = true;
> ! 		  subtree_mark_written_and_enqueue (lacc);
> ! 		}
> ! 	    }
> ! 	  continue;
> ! 	}
> ! 
> !       if (rchild->grp_unscalarizable_region)
> ! 	{
> ! 	  if (rchild->grp_write && !lacc->grp_write)
> ! 	    {
> ! 	      ret = true;
> ! 	      subtree_mark_written_and_enqueue (lacc);
> ! 	    }
>   	  continue;
>   	}
>   
> *************** propagate_subaccesses_across_link (struc
> *** 2648,2683 ****
>         new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
>   						lacc->grp_write
>   						|| rchild->grp_write);
> !       if (new_acc)
> ! 	{
> ! 	  ret = true;
> ! 	  if (racc->first_child)
> ! 	    propagate_subaccesses_across_link (new_acc, rchild);
> ! 	}
>       }
>   
>     return ret;
>   }
>   
> - /* Beginning with ACCESS, traverse its whole access subtree and mark all
> -    sub-trees as written to.  If any of them has not been marked so previously
> -    and has assignment links leading from it, re-enqueue it.  */
> - 
> - static void
> - subtree_mark_written_and_enqueue (struct access *access)
> - {
> -   if (access->grp_write)
> -     return;
> -   access->grp_write = true;
> -   add_access_to_work_queue (access);
> - 
> -   struct access *child;
> -   for (child = access->first_child; child; child = child->next_sibling)
> -     subtree_mark_written_and_enqueue (child);
> - }
> - 
> - 
> - 
>   /* Propagate all subaccesses across assignment links.  */
>   
>   static void
> --- 2685,2701 ----
>         new_acc = create_artificial_child_access (lacc, rchild, norm_offset,
>   						lacc->grp_write
>   						|| rchild->grp_write);
> !       gcc_checking_assert (new_acc);
> !       if (racc->first_child)
> ! 	propagate_subaccesses_across_link (new_acc, rchild);
> ! 
> !       add_access_to_work_queue (lacc);
> !       ret = true;
>       }
>   
>     return ret;
>   }
>   
>   /* Propagate all subaccesses across assignment links.  */
>   
>   static void
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)