[committed,gomp4] Fix release_dangling_ssa_names

[ was: Re: Expand oacc kernels after pass_fre ]
On 04/06/15 18:02, Tom de Vries wrote:
>> Please move this out of the class body.
>>
>
> Fixed and committed (ommitting patch as trivial).
>
>>> +    {
>>> +      unsigned res = execute_expand_omp ();
>>> +
>>> +      /* After running pass_expand_omp_ssa to expand the oacc kernels
>>> +     directive, we are left in the original function with anonymous
>>> +     SSA_NAMEs, with a defining statement that has been deleted.  This
>>> +     pass finds those SSA_NAMEs and releases them.
>>> +     TODO: Either fix this elsewhere, or make the fix unnecessary.  */
>>> +      unsigned int i;
>>> +      for (i = 1; i < num_ssa_names; ++i)
>>> +    {
>>> +      tree name = ssa_name (i);
>>> +      if (name == NULL_TREE)
>>> +        continue;
>>> +
>>> +      gimple stmt = SSA_NAME_DEF_STMT (name);
>>> +      bool found = false;
>>> +
>>> +      ssa_op_iter op_iter;
>>> +      def_operand_p def_p;
>>> +      FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
>>> +        {
>>> +          tree def = DEF_FROM_PTR (def_p);
>>> +          if (def == name)
>>> +        {
>>> +          found = true;
>>> +          break;
>>> +        }
>>> +        }
>>> +
>>> +      if (!found)
>>> +        {
>>> +          if (dump_file)
>>> +        fprintf (dump_file, "Released dangling ssa name %u\n", i);
>>> +          release_ssa_name (name);
>>> +        }
>>> +    }
>>> +
>>> +      return res;
>>> +    }

This patch implements the TODO.

The cause of the problems is that in replace_ssa_name, we create a new 
ssa_name with the def stmt of the old ssa_name, but do not reset the def 
stmt of the old ssa_name, leaving the ssa_name in the original function 
having a def stmt in the split-off function.

[ And if we don't do anything about that, at some point in another pass 
we use 'gimple_bb (SSA_NAME_DEF_STMT (name))->index' (a bb index in the 
split-off function) as an index into an array with as length the number 
of bbs in the original function. So the index may be out of bounds. ]

This patch fixes that by making sure we reset the def stmt to NULL. This 
means we can simplify release_dangling_ssa_names to just test for NULL 
def stmts.

Default defs are skipped by release_ssa_name, so setting the def stmt 
for default defs to NULL does not result in the name being released, but 
in an ssa-verification error. So instead, we keep the def stmt nop, and 
create a new nop for the copy in the split-off function.

[ The default def bit seems only to be triggered for the default def 
created by expand_omp_target:
...
   /* If we are in ssa form, we must load the value from the default
      definition of the argument.  That should not be defined now,
      since the argument is not used uninitialized.  */
   gcc_assert (ssa_default_def (cfun, arg) == NULL);
   narg = make_ssa_name (arg, gimple_build_nop ());
   set_ssa_default_def (cfun, arg, narg);
...
]

Bootstrapped and reg-tested on x86_64.

Committed to gomp-4_0-branch.

Thanks,
- Tom

On Wed, 5 Aug 2015, Tom de Vries wrote:

> [ was: Re: Expand oacc kernels after pass_fre ]
> On 04/06/15 18:02, Tom de Vries wrote:
> > > Please move this out of the class body.
> > > 
> > 
> > Fixed and committed (ommitting patch as trivial).
> > 
> > > > +    {
> > > > +      unsigned res = execute_expand_omp ();
> > > > +
> > > > +      /* After running pass_expand_omp_ssa to expand the oacc kernels
> > > > +     directive, we are left in the original function with anonymous
> > > > +     SSA_NAMEs, with a defining statement that has been deleted.  This
> > > > +     pass finds those SSA_NAMEs and releases them.
> > > > +     TODO: Either fix this elsewhere, or make the fix unnecessary.  */
> > > > +      unsigned int i;
> > > > +      for (i = 1; i < num_ssa_names; ++i)
> > > > +    {
> > > > +      tree name = ssa_name (i);
> > > > +      if (name == NULL_TREE)
> > > > +        continue;
> > > > +
> > > > +      gimple stmt = SSA_NAME_DEF_STMT (name);
> > > > +      bool found = false;
> > > > +
> > > > +      ssa_op_iter op_iter;
> > > > +      def_operand_p def_p;
> > > > +      FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
> > > > +        {
> > > > +          tree def = DEF_FROM_PTR (def_p);
> > > > +          if (def == name)
> > > > +        {
> > > > +          found = true;
> > > > +          break;
> > > > +        }
> > > > +        }
> > > > +
> > > > +      if (!found)
> > > > +        {
> > > > +          if (dump_file)
> > > > +        fprintf (dump_file, "Released dangling ssa name %u\n", i);
> > > > +          release_ssa_name (name);
> > > > +        }
> > > > +    }
> > > > +
> > > > +      return res;
> > > > +    }
> 
> This patch implements the TODO.
> 
> The cause of the problems is that in replace_ssa_name, we create a new
> ssa_name with the def stmt of the old ssa_name, but do not reset the def stmt
> of the old ssa_name, leaving the ssa_name in the original function having a
> def stmt in the split-off function.
> 
> [ And if we don't do anything about that, at some point in another pass we use
> 'gimple_bb (SSA_NAME_DEF_STMT (name))->index' (a bb index in the split-off
> function) as an index into an array with as length the number of bbs in the
> original function. So the index may be out of bounds. ]
> 
> This patch fixes that by making sure we reset the def stmt to NULL. This means
> we can simplify release_dangling_ssa_names to just test for NULL def stmts.

Not sure if I understand the problem correctly but why are you not simply
releasing the SSA name when you remove its definition?

Richard.

> Default defs are skipped by release_ssa_name, so setting the def stmt for
> default defs to NULL does not result in the name being released, but in an
> ssa-verification error. So instead, we keep the def stmt nop, and create a new
> nop for the copy in the split-off function.
> 
> [ The default def bit seems only to be triggered for the default def created
> by expand_omp_target:
> ...
>   /* If we are in ssa form, we must load the value from the default
>      definition of the argument.  That should not be defined now,
>      since the argument is not used uninitialized.  */
>   gcc_assert (ssa_default_def (cfun, arg) == NULL);
>   narg = make_ssa_name (arg, gimple_build_nop ());
>   set_ssa_default_def (cfun, arg, narg);
> ...
> ]
> 
> Bootstrapped and reg-tested on x86_64.
> 
> Committed to gomp-4_0-branch.
> 
> Thanks,
> - Tom
> 
>

On 05/08/15 09:29, Richard Biener wrote:
>> This patch fixes that by making sure we reset the def stmt to NULL. This means
>> >we can simplify release_dangling_ssa_names to just test for NULL def stmts.
> Not sure if I understand the problem correctly but why are you not simply
> releasing the SSA name when you remove its definition?

In move_sese_region_to_fn we move a region of blocks from one function 
to another, bit by bit.

When we encounter an ssa_name as def or use in the region, we:
- generate a new ssa_name,
- set the def stmt of the old name as def stmt of the new name, and
- add a mapping from the old to the new name.
The next time we encounter the same ssa_name in another statement, we 
find it in the map.

If we release the old ssa name, we effectively create statements with 
operands in the free-list. The first point where that cause breakage, is 
in walk_gimple_op, which expects the TREE_TYPE of the lhs of an assign 
to be defined, which is not the case if it's in the free-list:
...
case GIMPLE_ASSIGN:
   /* Walk the RHS operands.  If the LHS is of a non-renamable type or
      is a register variable, we may use a COMPONENT_REF on the RHS.*/
   if (wi)
     {
       tree lhs = gimple_assign_lhs (stmt);
       wi->val_only
         = (is_gimple_reg_type (TREE_TYPE (lhs)) && !is_gimple_reg (lhs))
            || gimple_assign_rhs_class (stmt) != GIMPLE_SINGLE_RHS;
     }
...

Thanks,
- Tom

On Wed, 5 Aug 2015, Tom de Vries wrote:

> On 05/08/15 09:29, Richard Biener wrote:
> > > This patch fixes that by making sure we reset the def stmt to NULL. This
> > > means
> > > >we can simplify release_dangling_ssa_names to just test for NULL def
> > > stmts.
> > Not sure if I understand the problem correctly but why are you not simply
> > releasing the SSA name when you remove its definition?
> 
> In move_sese_region_to_fn we move a region of blocks from one function to
> another, bit by bit.
> 
> When we encounter an ssa_name as def or use in the region, we:
> - generate a new ssa_name,
> - set the def stmt of the old name as def stmt of the new name, and
> - add a mapping from the old to the new name.
> The next time we encounter the same ssa_name in another statement, we find it
> in the map.
> 
> If we release the old ssa name, we effectively create statements with operands
> in the free-list. The first point where that cause breakage, is in
> walk_gimple_op, which expects the TREE_TYPE of the lhs of an assign to be
> defined, which is not the case if it's in the free-list:
> ...
> case GIMPLE_ASSIGN:
>   /* Walk the RHS operands.  If the LHS is of a non-renamable type or
>      is a register variable, we may use a COMPONENT_REF on the RHS.*/
>   if (wi)
>     {
>       tree lhs = gimple_assign_lhs (stmt);
>       wi->val_only
>         = (is_gimple_reg_type (TREE_TYPE (lhs)) && !is_gimple_reg (lhs))
>            || gimple_assign_rhs_class (stmt) != GIMPLE_SINGLE_RHS;
>     }
> ...

Hmm, ok, probably because the stmt moving doesn't happen in DOM
order (move defs before uses).  But

+
+      if (!SSA_NAME_IS_DEFAULT_DEF (name))
+       /* The statement has been moved to the child function.  It no 
longer
+          defines name in the original function.  Mark the def stmt NULL, 
and
+          let release_dangling_ssa_names deal with it.  */
+       SSA_NAME_DEF_STMT (name) = NULL;

applies also to uses - I don't see why it couldn't happen that you
move a use but not its def (the def would be a parameter to the
split-out function).  You'd wreck the IL of the source function this way.

I think that the whole dance of actually moving things instead of
just copying it isn't worth the extra maintainance (well, if we already
have a machinery duplicating a SESE region to another function - I
suppose gimple_duplicate_sese_region could be trivially changed to
support that).

Trunk doesn't have release_dangling_ssa_names it seems but I think
it belongs to move_sese_region_to_fn and not to omp-low.c and it
could also just walk the d->vars_map replace_ssa_name fills to
iterate over the removal candidates (and if the situation of
moving uses but not defs cannot happen you don't need any
SSA_NAME_DEF_STMT dance either).

Thanks,
Richard.

On 05/08/15 11:30, Richard Biener wrote:
> On Wed, 5 Aug 2015, Tom de Vries wrote:
>
>> On 05/08/15 09:29, Richard Biener wrote:
>>>> This patch fixes that by making sure we reset the def stmt to NULL. This
>>>> means
>>>>> we can simplify release_dangling_ssa_names to just test for NULL def
>>>> stmts.
>>> Not sure if I understand the problem correctly but why are you not simply
>>> releasing the SSA name when you remove its definition?
>>
>> In move_sese_region_to_fn we move a region of blocks from one function to
>> another, bit by bit.
>>
>> When we encounter an ssa_name as def or use in the region, we:
>> - generate a new ssa_name,
>> - set the def stmt of the old name as def stmt of the new name, and
>> - add a mapping from the old to the new name.
>> The next time we encounter the same ssa_name in another statement, we find it
>> in the map.
>>
>> If we release the old ssa name, we effectively create statements with operands
>> in the free-list. The first point where that cause breakage, is in
>> walk_gimple_op, which expects the TREE_TYPE of the lhs of an assign to be
>> defined, which is not the case if it's in the free-list:
>> ...
>> case GIMPLE_ASSIGN:
>>    /* Walk the RHS operands.  If the LHS is of a non-renamable type or
>>       is a register variable, we may use a COMPONENT_REF on the RHS.*/
>>    if (wi)
>>      {
>>        tree lhs = gimple_assign_lhs (stmt);
>>        wi->val_only
>>          = (is_gimple_reg_type (TREE_TYPE (lhs)) && !is_gimple_reg (lhs))
>>             || gimple_assign_rhs_class (stmt) != GIMPLE_SINGLE_RHS;
>>      }
>> ...
>
> Hmm, ok, probably because the stmt moving doesn't happen in DOM
> order (move defs before uses).  But
>

There seems to be similar code for the rhs, so I don't think changing 
the order would fix anything.

> +
> +      if (!SSA_NAME_IS_DEFAULT_DEF (name))
> +       /* The statement has been moved to the child function.  It no
> longer
> +          defines name in the original function.  Mark the def stmt NULL,
> and
> +          let release_dangling_ssa_names deal with it.  */
> +       SSA_NAME_DEF_STMT (name) = NULL;
>
> applies also to uses - I don't see why it couldn't happen that you
> move a use but not its def (the def would be a parameter to the
> split-out function).  You'd wreck the IL of the source function this way.
>

If you first move a use, you create a mapping. When you encounter the 
def, you use the mapping. Indeed, if the def is a default def, we don't 
encounter the def. Which is why we create a nop as defining def for 
those cases. The default def in the source function still has a defining 
nop, and has no uses anymore. I don't understand what is broken here.

> I think that the whole dance of actually moving things instead of
> just copying it isn't worth the extra maintainance (well, if we already
> have a machinery duplicating a SESE region to another function - I
> suppose gimple_duplicate_sese_region could be trivially changed to
> support that).
>

I'll mention that as todo. For now, I think the fastest way to get a 
working version is to fix move_sese_region_to_fn.

>Trunk doesn't have release_dangling_ssa_names it seems

Yep, I only ran into this trouble for the kernels region handling. But I 
don't exclude the possibility it could happen for trunk as well.

> but I think
> it belongs to move_sese_region_to_fn and not to omp-low.c

Makes sense indeed.

> and it
> could also just walk the d->vars_map replace_ssa_name fills to
> iterate over the removal candidates

Agreed, I suppose in general that's a win over iterating over all the 
ssa names.

> (and if the situation of
> moving uses but not defs cannot happen you don't need any
> SSA_NAME_DEF_STMT dance either).

I'd prefer to keep the SSA_NAME_DEF_STMT () = NULL bit. It makes sure a 
stmt is the defining stmt of only one ssa-name at all times.

I'll prepare a patch for trunk then.

Thanks,
- Tom

On Wed, 5 Aug 2015, Tom de Vries wrote:

> On 05/08/15 11:30, Richard Biener wrote:
> > On Wed, 5 Aug 2015, Tom de Vries wrote:
> > 
> > > On 05/08/15 09:29, Richard Biener wrote:
> > > > > This patch fixes that by making sure we reset the def stmt to NULL.
> > > > > This
> > > > > means
> > > > > > we can simplify release_dangling_ssa_names to just test for NULL def
> > > > > stmts.
> > > > Not sure if I understand the problem correctly but why are you not
> > > > simply
> > > > releasing the SSA name when you remove its definition?
> > > 
> > > In move_sese_region_to_fn we move a region of blocks from one function to
> > > another, bit by bit.
> > > 
> > > When we encounter an ssa_name as def or use in the region, we:
> > > - generate a new ssa_name,
> > > - set the def stmt of the old name as def stmt of the new name, and
> > > - add a mapping from the old to the new name.
> > > The next time we encounter the same ssa_name in another statement, we find
> > > it
> > > in the map.
> > > 
> > > If we release the old ssa name, we effectively create statements with
> > > operands
> > > in the free-list. The first point where that cause breakage, is in
> > > walk_gimple_op, which expects the TREE_TYPE of the lhs of an assign to be
> > > defined, which is not the case if it's in the free-list:
> > > ...
> > > case GIMPLE_ASSIGN:
> > >    /* Walk the RHS operands.  If the LHS is of a non-renamable type or
> > >       is a register variable, we may use a COMPONENT_REF on the RHS.*/
> > >    if (wi)
> > >      {
> > >        tree lhs = gimple_assign_lhs (stmt);
> > >        wi->val_only
> > >          = (is_gimple_reg_type (TREE_TYPE (lhs)) && !is_gimple_reg (lhs))
> > >             || gimple_assign_rhs_class (stmt) != GIMPLE_SINGLE_RHS;
> > >      }
> > > ...
> > 
> > Hmm, ok, probably because the stmt moving doesn't happen in DOM
> > order (move defs before uses).  But
> > 
> 
> There seems to be similar code for the rhs, so I don't think changing the
> order would fix anything.
> 
> > +
> > +      if (!SSA_NAME_IS_DEFAULT_DEF (name))
> > +       /* The statement has been moved to the child function.  It no
> > longer
> > +          defines name in the original function.  Mark the def stmt NULL,
> > and
> > +          let release_dangling_ssa_names deal with it.  */
> > +       SSA_NAME_DEF_STMT (name) = NULL;
> > 
> > applies also to uses - I don't see why it couldn't happen that you
> > move a use but not its def (the def would be a parameter to the
> > split-out function).  You'd wreck the IL of the source function this way.
> > 
> 
> If you first move a use, you create a mapping. When you encounter the def, you
> use the mapping. Indeed, if the def is a default def, we don't encounter the
> def. Which is why we create a nop as defining def for those cases. The default
> def in the source function still has a defining nop, and has no uses anymore.
> I don't understand what is broken here.

If you never encounter the DEF then it's broken.  Say, if for

foo(int a)
{
  int b = a;
  if (b)
    {
      < code using b >
    }
}

you move < code using b > to a function.  Then the def is still in 
foo but you create a mapping for its use(s).  Clearly the outlining
process in this case has to pass b as parameter to the outlined
function, something that may not happen currently.

It would probably be cleaner to separate the def and use remapping
to separate functions and record on whether we saw a def or not.

> > I think that the whole dance of actually moving things instead of
> > just copying it isn't worth the extra maintainance (well, if we already
> > have a machinery duplicating a SESE region to another function - I
> > suppose gimple_duplicate_sese_region could be trivially changed to
> > support that).
> > 
> 
> I'll mention that as todo. For now, I think the fastest way to get a working
> version is to fix move_sese_region_to_fn.

Sure.

> > Trunk doesn't have release_dangling_ssa_names it seems
> 
> Yep, I only ran into this trouble for the kernels region handling. But I don't
> exclude the possibility it could happen for trunk as well.
> 
> > but I think
> > it belongs to move_sese_region_to_fn and not to omp-low.c
> 
> Makes sense indeed.
> 
> > and it
> > could also just walk the d->vars_map replace_ssa_name fills to
> > iterate over the removal candidates
> 
> Agreed, I suppose in general that's a win over iterating over all the ssa
> names.
> 
> > (and if the situation of
> > moving uses but not defs cannot happen you don't need any
> > SSA_NAME_DEF_STMT dance either).
> 
> I'd prefer to keep the SSA_NAME_DEF_STMT () = NULL bit. It makes sure a stmt
> is the defining stmt of only one ssa-name at all times.
> 
> I'll prepare a patch for trunk then.

Thanks,
Richard.