re PR tree-optimization/47615 (ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra)

2011-02-07  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/47615
	* tree-ssa-sccvn.h (run_scc_vn): Take a vn-walk mode argument.
	* tree-ssa-sccvn.c (default_vn_walk_kind): New global.
	(run_scc_vn): Initialize it.
	(visit_reference_op_load): Use it.
	* tree-ssa-pre.c (execute_pre): Use VN_WALK if in PRE.

	* g++.dg/opt/pr47615.C: New testcase.

From-SVN: r169888

6 files changed, 738 insertions, 7 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 55c1643..0664328 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2011-02-07  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/47615
+	* tree-ssa-sccvn.h (run_scc_vn): Take a vn-walk mode argument.
+	* tree-ssa-sccvn.c (default_vn_walk_kind): New global.
+	(run_scc_vn): Initialize it.
+	(visit_reference_op_load): Use it.
+	* tree-ssa-pre.c (execute_pre): Use VN_WALK if in PRE.
+
 2011-02-07  Ulrich Weigand  <Ulrich.Weigand@de.ibm.com>
 
 	* config/spu/spu.c (spu_init_libfuncs): Install SImode and
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 558f192..eca3d7f 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,10 @@
 2011-02-07  Richard Guenther  <rguenther@suse.de>
 
+	PR tree-optimization/47615
+	* g++.dg/opt/pr47615.C: New testcase.
+
+2011-02-07  Richard Guenther  <rguenther@suse.de>
+
 	PR tree-optimization/47621
 	* gcc.dg/torture/pr47621.c: New testcase.
 
diff --git a/gcc/testsuite/g++.dg/opt/pr47615.C b/gcc/testsuite/g++.dg/opt/pr47615.C
new file mode 100644
index 0000000..bbbcbe1
--- /dev/null
+++ b/gcc/testsuite/g++.dg/opt/pr47615.C
@@ -0,0 +1,711 @@
+// { dg-do compile }
+// { dg-options "-O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra" }
+
+typedef __SIZE_TYPE__ size_t;
+namespace std 
+{
+  template < class _T1, class > struct pair
+  {
+    _T1 first;
+  };
+}
+namespace __gnu_cxx
+{
+  template < typename _Tp > class new_allocator
+  {
+  public:
+    typedef size_t size_type;
+    typedef _Tp * pointer;
+    typedef _Tp const_pointer;
+    typedef _Tp & reference;
+    typedef const _Tp & const_reference;
+    template < typename _Tp1 > struct rebind
+    {
+      typedef new_allocator < _Tp1 > other;
+    };
+  };
+}
+namespace std
+{
+template < typename _Tp > class allocator:
+  public __gnu_cxx::new_allocator < _Tp >
+  {};
+  template < typename, typename, typename > struct binary_function;
+  template < typename _Tp > struct less:binary_function < _Tp, _Tp, bool >
+  {};
+}
+namespace __gnu_cxx
+{
+  namespace typelist
+  {
+    struct null_type;
+    template < typename Root > struct node
+    {
+      typedef Root root;
+    };
+    template < typename, typename > struct chain;
+    namespace detail
+    {
+      template < typename, int >struct chain_at_index_;
+      template
+	<
+	typename
+	Hd, typename Tl > struct chain_at_index_ <chain < Hd, Tl >, 0 >
+      {
+	typedef Hd type;
+      };
+      template
+	<
+	typename
+	Hd, typename Tl, int i > struct chain_at_index_ <chain < Hd, Tl >, i >
+      {
+	typedef typename chain_at_index_ < Tl, i - 1 >::type type;
+      };
+    }
+    template < typename Typelist, int i > struct at_index
+    {
+      typedef typename Typelist::root root_type;
+      typedef detail::chain_at_index_ < root_type, i > index_type;
+      typedef typename index_type::type type;
+    };
+    template < typename T1, typename T2 > struct create2
+    {
+      typedef node < chain < T1, chain < T2, null_type > > >type;
+    };
+  }
+}
+namespace std
+{
+  namespace tr1
+  {
+    template < typename _Tp, _Tp __v > struct integral_constant
+    {
+      static const _Tp value = __v;
+    };
+    typedef integral_constant < bool, false > false_type;
+    template < typename, typename > struct is_same:false_type
+    {};
+  }
+}
+using std::tr1::is_same;
+namespace __gnu_pbds
+{
+  struct null_mapped_type;
+  struct rb_tree_tag;
+  namespace detail
+  {
+    template < typename, typename, typename > struct basic_tree_policy_base;
+    template
+      <
+      typename
+      Const_Node_Iterator,
+      typename
+      Allocator
+      >
+      struct
+      basic_tree_policy_base
+      <Const_Node_Iterator, Const_Node_Iterator, Allocator >
+    {};
+  }
+  template
+    < typename, typename, typename, typename > struct null_tree_node_update;
+template < typename Const_Node_Iterator, typename Node_Iterator, typename, typename Allocator > class tree_order_statistics_node_update:
+  detail::basic_tree_policy_base
+    < Const_Node_Iterator, Node_Iterator, Allocator >
+  {
+  public:
+    typedef Allocator allocator_type;
+    typedef typename allocator_type::size_type size_type;
+    typedef size_type metadata_type;
+    typedef Const_Node_Iterator const_node_iterator;
+    typedef Node_Iterator node_iterator;
+    typedef
+      typename
+      allocator_type::template
+      rebind < metadata_type >::other::reference metadata_reference;
+    void operator () (node_iterator, const_node_iterator) const;
+  };
+  template
+    <
+    typename
+    Const_Node_Iterator,
+    class
+    Node_Iterator,
+    class
+    Cmp_Fn,
+    class
+    Allocator
+    >
+    inline
+    void
+    tree_order_statistics_node_update
+    <
+    Const_Node_Iterator,
+    Node_Iterator,
+    Cmp_Fn,
+    Allocator
+    >::operator
+    () (node_iterator node_it, const_node_iterator end_nd_it) const
+  {
+    node_iterator l_child_it;
+    size_type
+      l_rank = (l_child_it == end_nd_it) ? : l_child_it.get_metadata ();
+    node_iterator r_child_it = node_it.get_r_child ();
+    size_type
+      r_rank = (r_child_it == end_nd_it) ? : r_child_it.get_metadata ();
+    const_cast
+      < metadata_reference > (node_it.get_metadata ()) = l_rank + r_rank;
+  }
+  namespace
+  {
+    template < typename, typename, typename, bool > struct value_type_base;
+    template
+      <
+      typename
+      Key,
+      typename
+      Allocator
+      > struct value_type_base <Key, null_mapped_type, Allocator, false >
+    {
+      typedef Key value_type;
+      typedef
+	typename
+	Allocator::template rebind < value_type >::other value_type_allocator;
+      typedef typename value_type_allocator::pointer pointer;
+      typedef typename value_type_allocator::const_pointer const_pointer;
+      typedef typename value_type_allocator::reference reference;
+      typedef typename value_type_allocator::const_reference const_reference;
+    };
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped, typename Alloc, bool Store_Extra > struct vt_base_selector
+    {
+      typedef value_type_base < Key, Mapped, Alloc, Store_Extra > type;
+    };
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped,
+      typename
+      Alloc,
+      bool
+      Store_Extra
+      >
+      struct
+      types_traits:vt_base_selector < Key, Mapped, Alloc, Store_Extra >::type
+    {};
+    template < typename, class, class > struct dumconst_node_iterator;
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped,
+      class,
+      class
+      Node_And_It_Traits, class Allocator > class bin_search_tree_no_data_
+    {
+    protected:
+      typedef
+	typename
+	Allocator::template
+	rebind
+	< typename Node_And_It_Traits::node >::other::pointer node_pointer;
+      typedef
+	typename
+	types_traits
+	< Key, Mapped, Allocator, false >::const_reference const_reference;
+      typedef typename Node_And_It_Traits::point_iterator point_iterator;
+      typedef typename Node_And_It_Traits::node_update node_update;
+      void rotate_right (node_pointer);
+      template
+	<
+	typename
+	Node_Update_ > void apply_update (node_pointer, Node_Update_ *);
+    };
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped,
+      class
+      Cmp_Fn,
+      class
+      Node_And_It_Traits,
+      class
+      Allocator
+      >
+      void
+      bin_search_tree_no_data_
+      <
+      Key,
+      Mapped,
+      Cmp_Fn, Node_And_It_Traits, Allocator >::rotate_right (node_pointer p_x)
+    {
+      node_pointer p_y = p_x->m_p_parent;
+      p_y->m_p_right = p_x;
+      apply_update (p_x, this);
+      apply_update (p_x->m_p_parent, (node_update *) this);
+    }
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped,
+      class
+      Cmp_Fn,
+      class
+      Node_And_It_Traits,
+      class
+      Allocator
+      >
+      template
+      <
+      typename
+      Node_Update_
+      >
+      void
+      bin_search_tree_no_data_
+      <
+      Key,
+      Mapped,
+      Cmp_Fn,
+      Node_And_It_Traits,
+      Allocator >::apply_update (node_pointer p_nd, Node_Update_ *)
+    {
+      node_update ()((p_nd), ((0)));
+    }
+  }
+  namespace detail
+  {
+  template < typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename Allocator > class rb_tree_no_data_:
+    bin_search_tree_no_data_
+      < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator >
+    {
+      typedef
+	bin_search_tree_no_data_
+	< Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator > base_type;
+      typedef typename base_type::node_pointer node_pointer;
+    public:
+      typedef typename base_type::const_reference const_reference;
+      typedef typename base_type::point_iterator point_iterator;
+      std::pair < point_iterator, bool > insert (const_reference);
+      void insert_fixup (node_pointer);
+    };
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped,
+      typename
+      Cmp_Fn,
+      typename
+      Node_And_It_Traits,
+      typename
+      Allocator
+      >
+      std::pair
+      <
+      typename
+      rb_tree_no_data_
+      <
+      Key,
+      Mapped,
+      Cmp_Fn,
+      Node_And_It_Traits,
+      Allocator
+      >::point_iterator,
+      bool
+      >
+      rb_tree_no_data_
+      <
+      Key,
+      Mapped,
+      Cmp_Fn, Node_And_It_Traits, Allocator >::insert (const_reference)
+    {
+      std::pair < point_iterator, bool > ins_pair;
+{
+	insert_fixup (ins_pair.first.m_p_nd);
+      }
+    }
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped,
+      typename
+      Cmp_Fn,
+      typename
+      Node_And_It_Traits,
+      typename
+      Allocator
+      >
+      void
+      rb_tree_no_data_
+      <
+      Key,
+      Mapped,
+      Cmp_Fn,
+      Node_And_It_Traits, Allocator >::insert_fixup (node_pointer p_nd)
+    {
+{
+{
+{
+	    rotate_right (p_nd);
+	  }
+	}
+      }
+    }
+    template
+      <
+      typename,
+      typename, typename, typename, typename > struct container_base_dispatch;
+    template
+      <
+      typename
+      Key,
+      typename
+      Policy_Tl,
+      typename
+      Alloc
+      >
+      struct
+      container_base_dispatch
+      <Key, null_mapped_type, rb_tree_tag, Policy_Tl, Alloc >
+    {
+      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 0 > at0;
+      typedef typename at0::type at0t;
+      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 1 > at1;
+      typedef typename at1::type at1t;
+      typedef
+	rb_tree_no_data_ < Key, null_mapped_type, at0t, at1t, Alloc > type;
+    };
+    template
+      <
+      typename
+      Node_Pointer,
+      typename,
+      typename,
+      typename,
+      typename, typename, bool, class > class bin_search_tree_const_it_
+    {
+    public:
+      Node_Pointer m_p_nd;
+    };
+    template
+      <
+      typename
+      Node,
+      class
+      Const_Iterator,
+      class Iterator, class Allocator > class bin_search_tree_const_node_it_
+    {
+      typedef
+	typename
+	Allocator::template rebind < Node >::other::pointer node_pointer;
+    public:
+      typedef typename Node::metadata_type metadata_type;
+      typedef
+	typename
+	Allocator::template
+	rebind
+	< metadata_type >::other::const_reference const_metadata_reference;
+    bin_search_tree_const_node_it_ (node_pointer p_nd):
+      m_p_nd ((p_nd))
+      {}
+      const_metadata_reference get_metadata ()
+      {
+	return (m_p_nd->get_metadata ());
+      }
+      bin_search_tree_const_node_it_ ()
+      {}
+      bin_search_tree_const_node_it_
+	< Node, Const_Iterator, Iterator, Allocator > get_r_child ()
+      {
+	return ((m_p_nd->m_p_right));
+      }
+      bool operator == (bin_search_tree_const_node_it_)
+      {}
+      node_pointer m_p_nd;
+    };
+    template
+      <
+      typename,
+      typename,
+      class,
+      template
+      <
+      typename,
+      class,
+      class, class > class, class, class > struct bin_search_tree_traits;
+    template
+      <
+      typename
+      Key,
+      class
+      Cmp_Fn,
+      template
+      <
+      typename,
+      class,
+      class,
+      class
+      >
+      class
+      Node_Update,
+      class
+      Node,
+      class
+      Allocator
+      >
+      struct
+      bin_search_tree_traits
+      <Key, null_mapped_type, Cmp_Fn, Node_Update, Node, Allocator >
+    {
+      typedef
+	types_traits < Key, null_mapped_type, Allocator, false > type_traits;
+      typedef Node node;
+      typedef
+	bin_search_tree_const_it_
+	<
+	typename
+	Allocator::template
+	rebind
+	<
+	node
+	>::other::pointer,
+	typename
+	type_traits::value_type,
+	typename
+	type_traits::pointer,
+	typename
+	type_traits::const_pointer,
+	typename
+	type_traits::reference,
+	typename
+	type_traits::const_reference, true, Allocator > const_point_iterator;
+      typedef const_point_iterator point_iterator;
+      typedef
+	bin_search_tree_const_node_it_
+	<
+	Node,
+	const_point_iterator, point_iterator, Allocator > const_node_iterator;
+      typedef const_node_iterator node_iterator;
+      typedef
+	Node_Update
+	< const_node_iterator, node_iterator, Cmp_Fn, Allocator > node_update;
+    };
+    template < typename Node_Update, bool > struct tree_metadata_helper
+    {
+      typedef typename Node_Update::metadata_type type;
+    };
+    template
+      <
+      typename
+      Key,
+      typename
+      Data,
+      class
+      Cmp_Fn,
+      template
+      <
+      typename,
+      class,
+      class,
+      class
+      >
+      class Node_Update, class Allocator > struct tree_node_metadata_selector
+    {
+      typedef
+	dumconst_node_iterator < Key, Data, Allocator > dumconst_node_it;
+      enum
+      {
+	null_update = is_same < Node_Update < dumconst_node_it,
+	dumconst_node_it,
+	Cmp_Fn,
+	Allocator >,
+	null_tree_node_update < dumconst_node_it,
+	dumconst_node_it,
+	Cmp_Fn,
+	Allocator > >::value
+      };
+      typedef
+	typename
+	tree_metadata_helper
+	<
+	Node_Update
+	<
+	dumconst_node_it,
+	dumconst_node_it, Cmp_Fn, Allocator >, null_update >::type type;
+    };
+    template
+      <
+      typename,
+      typename,
+      class,
+      template
+      <
+      typename,
+      class, class, class > class, class, class > struct tree_traits;
+    template < typename Value_Type, class Metadata, class Allocator > struct rb_tree_node_
+    {
+      typedef Metadata metadata_type;
+      typedef
+	typename
+	Allocator::template
+	rebind
+	<
+	rb_tree_node_
+	< Value_Type, Metadata, Allocator > >::other::pointer node_pointer;
+      typedef
+	typename
+	Allocator::template
+	rebind < metadata_type >::other::reference metadata_reference;
+        metadata_reference get_metadata ()
+      {
+	return m_metadata;
+      }
+      node_pointer m_p_right;
+      node_pointer m_p_parent;
+      metadata_type m_metadata;
+    };
+    template
+      <
+      typename
+      Key,
+      typename
+      Mapped,
+      typename
+      Cmp_Fn,
+      template
+      <
+      typename,
+      class,
+      class,
+      class
+      >
+      class
+      Node_Update,
+      typename
+      Allocator
+      >
+      struct
+      tree_traits
+      <Key,
+      Mapped,
+      Cmp_Fn,
+      Node_Update,
+      rb_tree_tag,
+      Allocator
+      >:bin_search_tree_traits
+      <
+      Key,
+      Mapped,
+      Cmp_Fn,
+      Node_Update,
+      rb_tree_node_
+      <
+      typename
+      types_traits
+      <
+      Key,
+      Mapped,
+      Allocator,
+      false
+      >::value_type,
+      typename
+      tree_node_metadata_selector
+      <
+      Key,
+      Mapped, Cmp_Fn, Node_Update, Allocator >::type, Allocator >, Allocator >
+    {};
+  }
+template < typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator > class container_base:
+  public
+    detail::container_base_dispatch
+    < Key, Mapped, Tag, Policy_Tl, Allocator >::type
+  {};
+template < typename Key, typename Mapped, typename Tag, typename, typename Policy_Tl, typename Allocator > class basic_tree:
+  public
+    container_base < Key, Mapped, Tag, Policy_Tl, Allocator >
+  {};
+  template
+    <
+    typename
+    Key,
+    typename
+    Mapped,
+    typename
+    Cmp_Fn
+    =
+    std::less
+    <
+    Key
+    >,
+    typename
+    Tag
+    =
+    rb_tree_tag,
+    template
+    <
+    typename,
+    typename,
+    typename,
+    typename
+    >
+    class
+    Node_Update
+    =
+    null_tree_node_update,
+    typename
+    Allocator
+    =
+    std::allocator
+    <
+    char
+    > >class
+    tree:public
+    basic_tree
+    <
+    Key,
+    Mapped,
+    Tag,
+    detail::tree_traits
+    <
+    Key,
+    Mapped,
+    Cmp_Fn,
+    Node_Update,
+    Tag,
+    Allocator
+    >,
+    typename
+    __gnu_cxx::typelist::create2
+    <
+    Cmp_Fn,
+    detail::tree_traits
+    < Key, Mapped, Cmp_Fn, Node_Update, Tag, Allocator > >::type, Allocator >
+  {};
+}
+using namespace std;
+using namespace __gnu_pbds;
+typedef
+  tree
+  <
+  int,
+  null_mapped_type,
+  less < int >, rb_tree_tag, tree_order_statistics_node_update > set_t;
+main ()
+{
+  set_t s;
+  s.insert (12);
+}
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index e179c4f..00ff8cc 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -4853,7 +4853,7 @@ execute_pre (bool do_fre)
   if (!do_fre)
     loop_optimizer_init (LOOPS_NORMAL);
 
-  if (!run_scc_vn ())
+  if (!run_scc_vn (do_fre ? VN_WALKREWRITE : VN_WALK))
     {
       if (!do_fre)
 	loop_optimizer_finalize ();
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index e37668e..9222cb5 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -1244,6 +1244,7 @@ vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
 
 static tree *last_vuse_ptr;
 static vn_lookup_kind vn_walk_kind;
+static vn_lookup_kind default_vn_walk_kind;
 
 /* Callback for walk_non_aliased_vuses.  Adjusts the vn_reference_t VR_
    with the current VUSE and performs the expression lookup.  */
@@ -2261,14 +2262,15 @@ visit_reference_op_load (tree lhs, tree op, gimple stmt)
 
   last_vuse = gimple_vuse (stmt);
   last_vuse_ptr = &last_vuse;
-  result = vn_reference_lookup (op, gimple_vuse (stmt), VN_WALKREWRITE, NULL);
+  result = vn_reference_lookup (op, gimple_vuse (stmt),
+				default_vn_walk_kind, NULL);
   last_vuse_ptr = NULL;
 
   /* If we have a VCE, try looking up its operand as it might be stored in
      a different type.  */
   if (!result && TREE_CODE (op) == VIEW_CONVERT_EXPR)
     result = vn_reference_lookup (TREE_OPERAND (op, 0), gimple_vuse (stmt),
-    				  VN_WALKREWRITE, NULL);
+    				  default_vn_walk_kind, NULL);
 
   /* We handle type-punning through unions by value-numbering based
      on offset and size of the access.  Be prepared to handle a
@@ -3463,15 +3465,18 @@ set_hashtable_value_ids (void)
 }
 
 /* Do SCCVN.  Returns true if it finished, false if we bailed out
-   due to resource constraints.  */
+   due to resource constraints.  DEFAULT_VN_WALK_KIND_ specifies
+   how we use the alias oracle walking during the VN process.  */
 
 bool
-run_scc_vn (void)
+run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
 {
   size_t i;
   tree param;
   bool changed = true;
 
+  default_vn_walk_kind = default_vn_walk_kind_;
+
   init_scc_vn ();
   current_info = valid_info;
 
diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h
index 3d9ee5f..bf99702 100644
--- a/gcc/tree-ssa-sccvn.h
+++ b/gcc/tree-ssa-sccvn.h
@@ -165,11 +165,13 @@ typedef struct vn_ssa_aux
   unsigned needs_insertion : 1;
 } *vn_ssa_aux_t;
 
+typedef enum { VN_NOWALK, VN_WALK, VN_WALKREWRITE } vn_lookup_kind;
+
 /* Return the value numbering info for an SSA_NAME.  */
 extern vn_ssa_aux_t VN_INFO (tree);
 extern vn_ssa_aux_t VN_INFO_GET (tree);
 tree vn_get_expr_for (tree);
-bool run_scc_vn (void);
+bool run_scc_vn (vn_lookup_kind);
 void free_scc_vn (void);
 tree vn_nary_op_lookup (tree, vn_nary_op_t *);
 tree vn_nary_op_lookup_stmt (gimple, vn_nary_op_t *);
@@ -187,7 +189,6 @@ void copy_reference_ops_from_ref (tree, VEC(vn_reference_op_s, heap) **);
 void copy_reference_ops_from_call (gimple, VEC(vn_reference_op_s, heap) **);
 bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, tree,
 				    VEC (vn_reference_op_s, heap) *);
-typedef enum { VN_NOWALK, VN_WALK, VN_WALKREWRITE } vn_lookup_kind;
 tree vn_reference_lookup_pieces (tree, alias_set_type, tree,
 				 VEC (vn_reference_op_s, heap) *,
 				 vn_reference_t *, vn_lookup_kind);