[PR,tree-optimization/71691] Fix unswitching in presence of maybe-undefined SSA_NAMEs

So to recap, the problem with this BZ is we have a maybe-undefined 
SSA_NAME in the IL.  That maybe-undefined name is used as a condition 
inside a loop and we unswitch that condition.

tree-ssa-loop-unswitch.c already tries to avoid doing that, but uses the 
optimistic ssa_undefined_value_p function.

Essentially ssa_undefined_value_p just checks to see if the SSA_NAME is 
set from a real statement.  It doesn't look at the operands of that 
statement to see if they're undefined, nor does it walk the use-def 
chains of the RHS operands.  In short, it's totally inappropriate for 
unswitching's needs.

This patch introduces a new class where we can ask if a particular 
SSA_NAME is defined or may be undefined.  Only the latter interface is 
currently used and I wouldn't object if we wanted to avoid the former 
interface until we needed it (it's just a trivial bitmap test, so we're 
not losing any real knowledge of how to implement it).

We walk the CFG in dominator order.  For each block we walk the PHIs and 
mark the LHS as defined IFF all the RHS arguments are defined.  Then we 
walk the statements and mark their LHSs as defined IIFF all the RHS 
arguments are defined.

This gives us a conservative solution to the may be undefined question. 
We do not try to keep this information up-to-date as statements or CFG 
are updated -- queries on newly added SSA_NAMEs always return 
may-be-undefined.

This information is ephemeral and not kept up-to-date.  We perform the 
analysis in the class's constructor and tear down the resulting bitmap 
in the class's destructor.


Bootstrapped and regression tested on x86_64-linux-gnu.

Ok for the trunk?


Jeff
PR tree-optimization/71691
	* Makefile.in (OBJS): Add tree-ssa-defined-or-undefined.
	* tree-ssa-defined-or-undefined.h: New file.
	* tree-ssa-defined-or-undefined.c: New file.
	* tree-ssa-loop-unswitch.c: Include tree-ssa-defined-or-undefined.h
	(tree_ssa_unswitch_loops): Create a defined_or_undefined class instance
	and pass it to tree_unswitch_single_loop.
	(tree_unswitch_single_loop): Pass instance down through recursive calls
	and into tree_may_unswitch_on.
	(tree_may_unswitch_on): Use defined_or_undefined instance rather than
	ssa_undefined_value_p.
	
	PR tree-optimization/71691
	* gcc.c-torture/execute/pr71691.c: New test.

On Thu, Aug 18, 2016 at 7:29 PM, Jeff Law <law@redhat.com> wrote:
>
> So to recap, the problem with this BZ is we have a maybe-undefined SSA_NAME
> in the IL.  That maybe-undefined name is used as a condition inside a loop
> and we unswitch that condition.
>
> tree-ssa-loop-unswitch.c already tries to avoid doing that, but uses the
> optimistic ssa_undefined_value_p function.
>
> Essentially ssa_undefined_value_p just checks to see if the SSA_NAME is set
> from a real statement.  It doesn't look at the operands of that statement to
> see if they're undefined, nor does it walk the use-def chains of the RHS
> operands.  In short, it's totally inappropriate for unswitching's needs.
>
> This patch introduces a new class where we can ask if a particular SSA_NAME
> is defined or may be undefined.  Only the latter interface is currently used
> and I wouldn't object if we wanted to avoid the former interface until we
> needed it (it's just a trivial bitmap test, so we're not losing any real
> knowledge of how to implement it).
>
> We walk the CFG in dominator order.  For each block we walk the PHIs and
> mark the LHS as defined IFF all the RHS arguments are defined.  Then we walk
> the statements and mark their LHSs as defined IIFF all the RHS arguments are
> defined.
>
> This gives us a conservative solution to the may be undefined question. We
> do not try to keep this information up-to-date as statements or CFG are
> updated -- queries on newly added SSA_NAMEs always return may-be-undefined.
>
> This information is ephemeral and not kept up-to-date.  We perform the
> analysis in the class's constructor and tear down the resulting bitmap in
> the class's destructor.
>
>
> Bootstrapped and regression tested on x86_64-linux-gnu.
>
> Ok for the trunk?

Few comments from only reading parts of tree-ssa-defined-or-undefined.c.

Usually all SSA names will be defined thus it looks more efficient to
record maybe_undefined names (to reduce bitmap cardinality).

Also you are iterating over DOM children which doesn't reliably visit
the merge after a if-then-else after the then or else part.  I think you
want to iterate in RPO order instead which guarantees that predecessors
have been visited (apart from those reachable over backedges).

I think you can spare yourself recording anything for virtual SSA names
(just use SSA_OP_DEFS instead of ALL_DEFS and skip virtual PHIs).

Note that unswitching is not really interested in definedness -- you are
treating parameters as "defined", but inlining may expose they are not.
Thus you are _not_ computing a conservative "defined" either.

Unswitching is interested in
defined-or-used-before-the-point-I-want-to-insert-a-use.

This means that what you can pre-compute for the whole function is the
dominance frontier that specifies either the must-def or all (possibly
unused) must-uses
(uses in PHIs are not uses obviously).

It might be actually cheaper to simply iterate over all immediate uses
of the COND ops
unswitching wants to insert and perform dominator checks (plus of course do the
check for a param default def and the names def).  Like add a

dominated_by_definition_or_use_p (basic_block bb, tree name)

helper for this.

Thanks,
Richard.

>
>
> Jeff
>
>
>         PR tree-optimization/71691
>         * Makefile.in (OBJS): Add tree-ssa-defined-or-undefined.
>         * tree-ssa-defined-or-undefined.h: New file.
>         * tree-ssa-defined-or-undefined.c: New file.
>         * tree-ssa-loop-unswitch.c: Include tree-ssa-defined-or-undefined.h
>         (tree_ssa_unswitch_loops): Create a defined_or_undefined class
> instance
>         and pass it to tree_unswitch_single_loop.
>         (tree_unswitch_single_loop): Pass instance down through recursive
> calls
>         and into tree_may_unswitch_on.
>         (tree_may_unswitch_on): Use defined_or_undefined instance rather
> than
>         ssa_undefined_value_p.
>
>         PR tree-optimization/71691
>         * gcc.c-torture/execute/pr71691.c: New test.
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 7a0160f..9e881b8 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -1491,6 +1491,7 @@ OBJS = \
>         tree-ssa-coalesce.o \
>         tree-ssa-copy.o \
>         tree-ssa-dce.o \
> +       tree-ssa-defined-or-undefined.o \
>         tree-ssa-dom.o \
>         tree-ssa-dse.o \
>         tree-ssa-forwprop.o \
> diff --git a/gcc/testsuite/gcc.c-torture/execute/pr71691.c
> b/gcc/testsuite/gcc.c-torture/execute/pr71691.c
> new file mode 100644
> index 0000000..2c5dbb6
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/execute/pr71691.c
> @@ -0,0 +1,45 @@
> +char b;
> +short f;
> +unsigned e;
> +int g = 20;
> +
> +void
> +foo ()
> +{
> +  int l, h;
> +  for (l = 0; l <= 7; l++)
> +    {
> +      int j = 38;
> +      if (g)
> +       h = 0;
> +      for (; h <= 7; h++)
> +       {
> +         int i, k = b % (j % 4);
> +         g = f;
> +         for (;;)
> +           {
> +             j = 6 || b;
> +             if (e)
> +               {
> +                 for (; j; --j)
> +                   if (k)
> +                     __builtin_printf ("%d", 9);
> +                 if (i)
> +                   __builtin_printf ("%d", j);
> +               }
> +             if (l)
> +               continue;
> +             break;
> +           }
> +         i = f || b;
> +       }
> +    }
> +}
> +
> +int
> +main ()
> +{
> +  foo ();
> +  exit (0);
> +}
> +
> diff --git a/gcc/tree-ssa-defined-or-undefined.c
> b/gcc/tree-ssa-defined-or-undefined.c
> new file mode 100644
> index 0000000..50de443
> --- /dev/null
> +++ b/gcc/tree-ssa-defined-or-undefined.c
> @@ -0,0 +1,128 @@
> +/* Simple class for classifying SSA_NAMEs that are either fully defined
> +   or possibly undefined.
> +
> +   This is meant to support conservative analysis for optimization
> purposes,
> +   not for generating warnings.  The analysis for generating warnings is
> +   deeper to avoid generation of false positives.
> +
> +   Copyright (C) 2001-2016 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify
> +it under the terms of the GNU General Public License as published by
> +the Free Software Foundation; either version 3, or (at your option)
> +any later version.
> +
> +GCC is distributed in the hope that it will be useful,
> +but WITHOUT ANY WARRANTY; without even the implied warranty of
> +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +GNU General Public License for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3.  If not see
> +<http://www.gnu.org/licenses/>.  */
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "backend.h"
> +#include "tree.h"
> +#include "gimple.h"
> +#include "tree-pass.h"
> +#include "ssa.h"
> +#include "gimple-pretty-print.h"
> +#include "diagnostic-core.h"
> +#include "fold-const.h"
> +#include "gimple-iterator.h"
> +#include "tree-ssa.h"
> +#include "params.h"
> +#include "tree-cfg.h"
> +#include "tree-ssa-defined-or-undefined.h"
> +
> +/* Analyze the current function to determine the SSA_NAMEs that are
> +   fully defined and those which may be undefined.  */
> +
> +defined_or_undefined::defined_or_undefined (void)
> +{
> +  m_defined_names = BITMAP_ALLOC (NULL);
> +
> +  /* We can just do a dominator walk of the CFG analyzing each statement
> +     in each block.  If a statement uses a possibly undefined value, then
> +     all results of this statement are considered possibly undefined.
> +
> +     This may give overly conservative results for loops, but that's safe.
> */
> +  walk_bbs (ENTRY_BLOCK_PTR_FOR_FN (cfun));
> +}
> +
> +/* Walk the PHIs and statements within BB to determine the
> defined/undefined
> +   status of each SSA_NAME set in BB.  Then recurse into dominator
> children.  */
> +
> +void
> +defined_or_undefined::walk_bbs (basic_block bb)
> +{
> +  /* Walk each PHI.  The LHS of the PHI is only considered fully defined
> +     if each RHS argument is fully defined.  */
> +  gphi_iterator gsi;
> +  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> +    {
> +      gphi *phi = gsi.phi ();
> +      unsigned int i;
> +      for (i = 0; i < gimple_phi_num_args (phi); i++)
> +       {
> +         tree arg = gimple_phi_arg_def (phi, i);
> +         if (TREE_CODE (arg) == SSA_NAME && is_maybe_undefined (arg))
> +           break;
> +       }
> +
> +      if (i == gimple_phi_num_args (phi))
> +       bitmap_set_bit (m_defined_names,
> +                       SSA_NAME_VERSION (gimple_phi_result (phi)));
> +    }
> +
> +  /* Similarly for all the statements in the block.  The outputs are
> +     considered fully defined if and only iff all the inputs are
> +     fully defined.  */
> +  gimple_stmt_iterator si;
> +  for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
> +    if (!gimple_uses_undefined_value_p (gsi_stmt (si)))
> +      {
> +       tree def;
> +       ssa_op_iter iter;
> +
> +       FOR_EACH_SSA_TREE_OPERAND (def, gsi_stmt (si), iter,
> SSA_OP_ALL_DEFS)
> +         bitmap_set_bit (m_defined_names, SSA_NAME_VERSION (def));
> +      }
> +
> +  /* Recurse into the dominator children of BB.  */
> +  basic_block son;
> +  for (son = first_dom_son (CDI_DOMINATORS, bb);
> +       son;
> +       son = next_dom_son (CDI_DOMINATORS, son))
> +    walk_bbs (son);
> +}
> +
> +defined_or_undefined::~defined_or_undefined (void)
> +{
> +  BITMAP_FREE (m_defined_names);
> +}
> +
> +/* Return TRUE if T (an SSA_NAME) is possibly undefined in this function,
> +   false otherwise.  SSA_NAMEs not encountered during the initial
> +   analysis will be considered undefined.  */
> +
> +bool
> +defined_or_undefined::is_maybe_undefined (tree t)
> +{
> +  return !bitmap_bit_p (m_defined_names, SSA_NAME_VERSION (t));
> +}
> +
> +/* Return TRUE if T (an SSA_NAME) is defined in this function,
> +   false otherwise.  SSA_NAMEs not encountered during the initial
> +   analysis will be considered undefined.  */
> +
> +bool
> +defined_or_undefined::is_defined (tree t)
> +{
> +  return bitmap_bit_p (m_defined_names, SSA_NAME_VERSION (t));
> +}
> diff --git a/gcc/tree-ssa-defined-or-undefined.h
> b/gcc/tree-ssa-defined-or-undefined.h
> new file mode 100644
> index 0000000..e0f98e7
> --- /dev/null
> +++ b/gcc/tree-ssa-defined-or-undefined.h
> @@ -0,0 +1,64 @@
> +/* Simple class for identifying SSA_NAMEs that are either fully defined
> +   or maybe undefined.
> +
> +   Copyright (C) 2001-2016 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify it under
> +the terms of the GNU General Public License as published by the Free
> +Software Foundation; either version 3, or (at your option) any later
> +version.
> +
> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
> + for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3.  If not see
> +<http://www.gnu.org/licenses/>.  */
> +
> +#ifndef GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H
> +#define GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H
> +
> +/* Simple class for identifying SSA_NAMEs that are either fully defined
> +   or maybe undefined.
> +
> +   This is meant to support conservative analysis for optimization
> purposes,
> +   not for generating warnings.  The analysis for generating warnings is
> +   deeper to avoid generation of false positives.
> +
> +   Instantiation of this class triggers analysis which is not kept
> up-to-date
> +   as changes in the IL or CFG are made.
> +
> +   Queries will return the conservative result (maybe undefined) for
> SSA_NAMEs
> +   that were not encountered during the initial analysis.  */
> +
> +class defined_or_undefined
> +{
> + public:
> +  defined_or_undefined ();
> +  ~defined_or_undefined ();
> +
> +  /* Return TRUE if T (an SSA_NAME) is possibly undefined in this function,
> +     false otherwise.  SSA_NAMEs not encountered during the initial
> +     analysis will be considered undefined.  */
> +  bool is_maybe_undefined (tree);
> +
> +  /* Return TRUE if T (an SSA_NAME) is defined in this function,
> +     false otherwise.  SSA_NAMEs not encountered during the initial
> +     analysis will be considered undefined.  */
> +  bool is_defined (tree);
> +
> + private:
> +  /* We do not allow copying this object or initializing one
> +     from another.  */
> +  defined_or_undefined& operator= (const defined_or_undefined&);
> +  defined_or_undefined (const defined_or_undefined&);
> +
> +  void walk_bbs (basic_block);
> +  bitmap m_defined_names;
> +};
> +
> +#endif /* GCC_TREE_SSA_DEFINED_OR_UNDEFINED */
> diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
> index 40905af..fb94807 100644
> --- a/gcc/tree-ssa-loop-unswitch.c
> +++ b/gcc/tree-ssa-loop-unswitch.c
> @@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "gimple-iterator.h"
>  #include "cfghooks.h"
>  #include "tree-ssa-loop-manip.h"
> +#include "tree-ssa-defined-or-undefined.h"
>
>  /* This file implements the loop unswitching, i.e. transformation of loops
> like
>
> @@ -76,8 +77,10 @@ along with GCC; see the file COPYING3.  If not see
>     shape.  */
>
>  static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
> -static bool tree_unswitch_single_loop (struct loop *, int);
> -static tree tree_may_unswitch_on (basic_block, struct loop *);
> +static bool tree_unswitch_single_loop (struct loop *, int,
> +                                      class defined_or_undefined *);
> +static tree tree_may_unswitch_on (basic_block, struct loop *,
> +                                 class defined_or_undefined *);
>  static bool tree_unswitch_outer_loop (struct loop *);
>  static edge find_loop_guard (struct loop *);
>  static bool empty_bb_without_guard_p (struct loop *, basic_block);
> @@ -93,13 +96,14 @@ tree_ssa_unswitch_loops (void)
>  {
>    struct loop *loop;
>    bool changed = false;
> +  class defined_or_undefined defined_or_undefined;
>
>    /* Go through all loops starting from innermost.  */
>    FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
>      {
>        if (!loop->inner)
>         /* Unswitch innermost loop.  */
> -       changed |= tree_unswitch_single_loop (loop, 0);
> +       changed |= tree_unswitch_single_loop (loop, 0,
> &defined_or_undefined);
>        else
>         changed |= tree_unswitch_outer_loop (loop);
>      }
> @@ -113,7 +117,8 @@ tree_ssa_unswitch_loops (void)
>     basic blocks (for what it means see comments below).  */
>
>  static tree
> -tree_may_unswitch_on (basic_block bb, struct loop *loop)
> +tree_may_unswitch_on (basic_block bb, struct loop *loop,
> +                     class defined_or_undefined *defined_or_undefined)
>  {
>    gimple *last, *def;
>    gcond *stmt;
> @@ -137,8 +142,9 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop)
>    FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
>      {
>        /* Unswitching on undefined values would introduce undefined
> -        behavior that the original program might never exercise.  */
> -      if (ssa_undefined_value_p (use, true))
> +        behavior that the original program might never exercise.  Note
> +        carefully we can not unswitch on a maybe undefined value.  */
> +      if (defined_or_undefined->is_maybe_undefined (use))
>         return NULL_TREE;
>        def = SSA_NAME_DEF_STMT (use);
>        def_bb = gimple_bb (def);
> @@ -191,7 +197,8 @@ simplify_using_entry_checks (struct loop *loop, tree
> cond)
>     grow exponentially.  */
>
>  static bool
> -tree_unswitch_single_loop (struct loop *loop, int num)
> +tree_unswitch_single_loop (struct loop *loop, int num,
> +                          class defined_or_undefined *defined_or_undefined)
>  {
>    basic_block *bbs;
>    struct loop *nloop;
> @@ -243,7 +250,7 @@ tree_unswitch_single_loop (struct loop *loop, int num)
>      {
>        /* Find a bb to unswitch on.  */
>        for (; i < loop->num_nodes; i++)
> -       if ((cond = tree_may_unswitch_on (bbs[i], loop)))
> +       if ((cond = tree_may_unswitch_on (bbs[i], loop,
> defined_or_undefined)))
>           break;
>
>        if (i == loop->num_nodes)
> @@ -363,7 +370,8 @@ tree_unswitch_single_loop (struct loop *loop, int num)
>        /* Find a bb to unswitch on.  */
>        for (; found < loop->num_nodes; found++)
>         if ((bbs[found]->flags & BB_REACHABLE)
> -           && (cond = tree_may_unswitch_on (bbs[found], loop)))
> +           && (cond = tree_may_unswitch_on (bbs[found], loop,
> +                                            defined_or_undefined)))
>           break;
>
>        if (found == loop->num_nodes)
> @@ -391,8 +399,8 @@ tree_unswitch_single_loop (struct loop *loop, int num)
>    free_original_copy_tables ();
>
>    /* Invoke itself on modified loops.  */
> -  tree_unswitch_single_loop (nloop, num + 1);
> -  tree_unswitch_single_loop (loop, num + 1);
> +  tree_unswitch_single_loop (nloop, num + 1, defined_or_undefined);
> +  tree_unswitch_single_loop (loop, num + 1, defined_or_undefined);
>    free (bbs);
>    return true;
>  }
>