Bug 67191

trippels@gcc2-power8 tools % cat fwd_set_test.ii
template <typename> class A;
template <typename _Tp> using __allocator_base = _Tp;
template <class T, class = T, class = int, class = __allocator_base<int>>
class B;
template <class T, class H, class P, class A>
bool operator==(B<T, H, P, A> const &, B<T, H, P, A> const &);
template <class T, class H, class P, class A>
bool operator!=(B<T, H, P, A> const &, B<T, H, P, A> const &);
typedef B<int> int_multiset;
int a;
template <typename> struct C {
  C(int) {}
};
template <typename> struct D;
template <typename> struct K;
struct L : C<A<D<int>>>, C<A<K<int>>> {
  template <typename First, typename Second>
  L(First, Second)
      : C<A<D<int>>>(0), C<A<K<int>>>(0) {}
};
template <typename Node> struct F {
  typedef typename Node::node_pointer node_pointer;
  node_pointer node_;
  F();
  F(typename Node::link_pointer p1) : node_(static_cast<node_pointer>(p1)) {}
  void operator++() { node_ = 0; }
  int operator!=(F p1) { return node_ != p1.node_; }
};
struct G {
  typedef G *link_pointer;
};
struct H {
  static int new_bucket_count(int) {
    int b;
    int *c = 0;
    if (a)
      b = *c;
    return b;
  }
};
class functions {
public:
  functions(int, int) {}
  ~functions();
};
template <typename Types> struct table : functions {
  typedef typename Types::policy policy;
  typedef Types node_allocator;
  typedef F<typename Types::node> iterator;
  L allocators_;
  int bucket_count_;
  int size_;
  typename Types::link_pointer get_previous_start() const;
  iterator begin() const { return size_ ? get_previous_start() : 0; }
  table(int, typename Types::hasher, typename Types::key_equal, node_allocator)
      : functions(0, 0), allocators_(0, 0),
        bucket_count_(policy::new_bucket_count(0)), size_() {}
};
template <typename> struct K : G { typedef K *node_pointer; };
struct I {
  typedef G *link_pointer;
};
struct J {
  typedef I::link_pointer link_pointer;
};
template <typename> struct D {
  typedef int hasher;
  typedef int key_equal;
  typedef K<int> node;
  typedef J::link_pointer link_pointer;
  typedef H policy;
};
struct M : table<D<int>> {
  node_allocator grouped_table_impl_a;
  M(int, int) : table(0, 0, 0, grouped_table_impl_a) {}
  void equals(M const &) const {
    for (iterator d = begin(); d.node_;) {
      iterator e;
      group_equals(e);
    }
  }
  static int group_equals(iterator p1) {
    int f;
    iterator g;
    for (; g != p1; ++g)
      if (find())
        if (f)
          return 0;
  }
  static int find();
};
template <class, class, class, class> class B {
  M table_;

public:
  B(unsigned long = 0);
  friend bool operator==<>(B const &, B const &);
  friend bool operator!=<>(B const &, B const &);
};
template <class T, class H, class P, class A>
B<T, H, P, A>::B(unsigned long)
    : table_(0, 0) {}
template <class T, class H, class P, class A>
bool operator==(B<T, H, P, A> const &p1, B<T, H, P, A> const &p2) {
  p1.table_.equals(p2.table_);
}
template <class T, class H, class P, class A>
bool operator!=(B<T, H, P, A> const &p1, B<T, H, P, A> const &p2) {
  p1.table_.equals(p2.table_);
}
void use_multiset_fwd_declared_function_typerun() {
  int_multiset x, y;
  x == y;
  x != y;
}


trippels@gcc2-power8 tools % g++ -O2 -c fwd_set_test.ii
fwd_set_test.ii: In function ‘void use_multiset_fwd_declared_function_typerun()’:
fwd_set_test.ii:111:6: internal compiler error: in before_dom_children, at tree-ssa-sccvn.c:4372
 void use_multiset_fwd_declared_function_typerun() {
      ^

Hmm, doesn't reproduce on x86_64 for me.  Anyway mine, hopefully we'll get a x86_64 testcase as well.

Oh, maybe just the reduced testcase no longer fails after r226814.

(In reply to Richard Biener from comment #3)
> Oh, maybe just the reduced testcase no longer fails after r226814.

Still fails on ppc64le after r226814. So a cross should reproduce this.

Hello ! This simpler C testcase seemingly triggers the exact same ICE at -O1 on my x86_64 machine :

$ cat tested.c
int a;
void f(void)
{
    int b;
    for(a=1; a;);
    for(; b; b++)
lbl:
        b || a;
    if(a)
        goto lbl;
}

$ xgcc -w -O1 tested.c
tested.c: In function ‘f’:
tested.c:11:1: internal compiler error: in before_dom_children, at tree-ssa-sccvn.c:4372
 }
 ^
0xc66ffc sccvn_dom_walker::before_dom_children(basic_block_def*)
	../../srcdir/gcc/tree-ssa-sccvn.c:4371
0x10c46a1 dom_walker::walk(basic_block_def*)
	../../srcdir/gcc/domwalk.c:177
0xc681d6 run_scc_vn(vn_lookup_kind)
	../../srcdir/gcc/tree-ssa-sccvn.c:4459
0xc3a3b2 execute
	../../srcdir/gcc/tree-ssa-pre.c:4959
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

Ok, reproduced with a cross.  The assert means the DOM walk didn't visit the
definition of an operand before its use which shouldn't happen.  The use
is in a loop nested in a loop which contains the definition dominating the
nested loop entry.

Ah, so we are detecting the outer loop as not executable.  But then the DOM
walk goes to a CFG part looking like


   <bb10>
   /    \
  /     <bb11>
 <bb28>  |    \
  |     <bb20> \
  |    /        <loop exit>
 <bb13>
  |    \
  |     <other loop exit>
 <loop latch>

and for some reason it visits this in order 10, 28, 13(!) instead of
what I would expect (10, 28, 11, 20, 13).  So we don't see bb13 as
not executable and thus the assert triggers.

In domwalk the sort using the postorder number is supposed to make
sure that CFG merges inside the dominator children are visited last.
Somehow this doesn't work here and thus results in non-optimal order
for propagation.  Of course due to the CFG the children are
only 13, 28 and 11 (not 20) so there isn't a "merge" within the
children :/

In the end the assert wasn't meant to stay - it's fine if it triggers
for code that ends up being unreachable.  So the immediate fix is to
remove it but we still want to fix that dominator walk ordering issue
IMHO, which of course would make it a non-dominator walk in some sense
(walking bb11 children before completing bb10 children).

PRE uses a worklist approach and defers blocks which have unvisited
predecessors exactly to overcome this ordering issue which is bad
for propagation passes (if only for compile-time reasons).

Author: rguenth
Date: Thu Aug 13 09:39:50 2015
New Revision: 226854

URL: https://gcc.gnu.org/viewcvs?rev=226854&root=gcc&view=rev
Log:
2015-08-13  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/67191
	* tree-ssa-sccvn.c (sccvn_dom_walker::before_dom_children): Remove
	assert we value-numbered last stmts operand because it can validly
	trigger for unreachable code.

	* gcc.dg/torture/pr67191.c: New testcase.
	* g++.dg/torture/pr67191.C: Likewise.

Added:
    trunk/gcc/testsuite/g++.dg/torture/pr67191.C
    trunk/gcc/testsuite/gcc.dg/torture/pr67191.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-sccvn.c

Fixed.