git bisect points to r241329:

commit 34b94be25f231249fa213152feb6b7208b4c0d13
Author: rguenth <rguenth@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Wed Oct 19 08:39:55 2016 +0000

    2016-10-19  Richard Biener  <rguenther@suse.de>
    
            * domwalk.c (dom_walker::walk): Use RPO order.

While I could reproduce this yesterday on x86_64-linux (but only with bootstrapped gcc), I can't reproduce this anymore today.  My tree includes the PR80436 fix, but it doesn't seem that changed spot is ever encountered while compiling the testcase.

(In reply to Jakub Jelinek from comment #2)
> While I could reproduce this yesterday on x86_64-linux (but only with
> bootstrapped gcc), I can't reproduce this anymore today.  My tree includes
> the PR80436 fix, but it doesn't seem that changed spot is ever encountered
> while compiling the testcase.

It was "fixed" by r246965, which doesn't make much sense.

(In reply to Markus Trippelsdorf from comment #3)
> 
> It was "fixed" by r246965, which doesn't make much sense.

On the other hand r246965 "causes" a new heisenbug on ppc64le:


 % /home/trippels/gcc_test/usr/local/bin/g++ --save-temps -fcompare-debug -fPIC -fvisibility-inlines-hidden -Werror=date-time -std=c++11 -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wno-maybe-uninitialized -Wdelete-non-virtual-dtor -Wno-comment -ffunction-sections -fdata-sections -Wno-implicit-fallthrough -O3 -pipe -UNDEBUG -fno-exceptions -fno-rtti -c BasicBlockUtils.ii -w
g++: warning: -pipe ignored because -save-temps specified
g++: error: BasicBlockUtils.ii: -fcompare-debug failure (length)


--- BasicBlockUtils.gkd 2017-04-19 14:19:18.678115265 +0000
+++ BasicBlockUtils.gk.gkd      2017-04-19 14:19:29.648375254 +0000
@@ -35537,7 +35537,7 @@
 (insn:TI # 0 0 (set (reg:DI 5 5)
         (const_int 1 [0x1])) "BasicBlockUtils.ii":61700# {*movdi_internal64}
      (nil))
-(insn # 0 0 (set (reg/f:DI 31 31 [orig:174 _36 ] [174])
+(insn # 0 0 (set (reg/f:DI 31 31 [orig:177 _36 ] [177])
         (reg:DI 3 3)) "BasicBlockUtils.ii":46281# {*movdi_internal64}
      (expr_list:REG_DEAD (reg:DI 3 3)
         (nil)))
@@ -35547,7 +35547,7 @@
             (const_int 32 [0x20]))
         (nil)))
 (insn # 0 0 (set (reg:DI 4 4)
-        (reg/f:DI 31 31 [orig:174 _36 ] [174])) "BasicBlockUtils.ii":61700# {*movdi_internal64}
+        (reg/f:DI 31 31 [orig:177 _36 ] [177])) "BasicBlockUtils.ii":61700# {*movdi_internal64}
      (nil))
 (call_insn # 0 0 (parallel [
             (call (mem:SI (symbol_ref/i:DI ("_ZN4llvm14TerminatorInst12SuccIteratorIPS0_NS_10BasicBlockEEC1ES2_b") [flags 0x3]  <function_decl # __comp_ctor >) [ __comp_ctor  S4 
A8])
@@ -35566,21 +35566,21 @@
             (expr_list:DI (use (reg:DI 4 4))
                 (expr_list:QI (use (reg:DI 5 5))
                     (nil))))))
-(insn # 0 0 (set (reg/f:DI 9 9 [orig:602 SR.2614 ] [602])
+(insn # 0 0 (set (reg/f:DI 9 9 [orig:175 SR.2614 ] [175])
         (mem/f/c:DI (plus:DI (reg/f:DI 1 1)
                 (const_int 32 [0x20])) [ MEM[(struct SuccIterator *)&D.xxxx]+0 S8 A128])) "BasicBlockUtils.ii":61700# {*movdi_internal64}
      (expr_list:REG_EQUIV (mem/f/c:DI (plus:DI (reg/f:DI 113 sfp)
                 (const_int 32 [0x20])) [ MEM[(struct SuccIterator *)&D.xxxx]+0 S8 A128])
         (nil)))
-(insn:TI # 0 0 (set (reg/v:DI 26 26 [orig:387 SR.2615 ] [387])
+(insn:TI # 0 0 (set (reg/v:DI 26 26 [orig:173 SR.2615 ] [173])
         (zero_extend:DI (mem/c:SI (plus:DI (reg/f:DI 1 1)
                     (const_int 40 [0x28])) [ MEM[(struct SuccIterator *)&D.xxxx + 8B]+0 S4 A64]))) "BasicBlockUtils.ii":61700# {zero_extendsidi2}
      (nil))
 (insn # 0 0 (set (reg:CCUNS 75 7 [642])
-        (compare:CCUNS (reg/f:DI 31 31 [orig:174 _36 ] [174])
-            (reg/f:DI 9 9 [orig:602 SR.2614 ] [602]))) "BasicBlockUtils.ii":60645# {*cmpdi_unsigned}
-     (expr_list:REG_DEAD (reg/f:DI 31 31 [orig:174 _36 ] [174])
-        (expr_list:REG_DEAD (reg/f:DI 9 9 [orig:602 SR.2614 ] [602])
+        (compare:CCUNS (reg/f:DI 9 9 [orig:175 SR.2614 ] [175])
+            (reg/f:DI 31 31 [orig:177 _36 ] [177]))) "BasicBlockUtils.ii":60645# {*cmpdi_unsigned}
+     (expr_list:REG_DEAD (reg/f:DI 31 31 [orig:177 _36 ] [177])
+        (expr_list:REG_DEAD (reg/f:DI 9 9 [orig:175 SR.2614 ] [175])
             (nil))))
 (jump_insn # 0 0 (set (pc)
         (if_then_else (ne (reg:CCUNS 75 7 [642])

Created attachment 41228 [details]
another unreduced testcase

So, for the #c0 testcase with r246965 reverted on x86_64-linux, the ugly thing is that -fdump-tree-all makes the -fcompare-debug failure go away, but trying individual -fdump-tree-* usually works.  The retslot dump is still pretty much the same except for added DEBUG stmts and some minor changes in decl uids (that is fine), but fre3 already in one function has different number of basic blocks and major changes like that.
The first change in -fdump-tree-fre3-all when I ignore decl numbers, # DEBUG stmts and <Tnnnnn> differences is:
 Value numbering iftmp.63_180 stmt = iftmp.63_180 = PHI <iftmp.63_175(75), iftmp.63_179(76)>
-Setting value number of iftmp.63_180 to iftmp.63_169 (changed)
+Setting value number of iftmp.63_180 to iftmp.63_73 (changed)
 Starting iteration 2
 Value numbering iftmp.63_180 stmt = iftmp.63_180 = PHI <iftmp.63_175(75), iftmp.63_179(76)>
-Setting value number of iftmp.63_180 to iftmp.63_169
+Setting value number of iftmp.63_180 to iftmp.63_73
 Processing SCC needed 2 iterations
 Visiting control stmt ending BB 77: if (iftmp.63_73 == iftmp.63_180)
-Visiting BB 78
-Recording temporarily iftmp.63_73 eq_expr iftmp.63_180 == false
-Recording temporarily iftmp.63_73 ne_expr iftmp.63_180 == true
+Applying pattern match.pd:2342, gimple-match.c:6143
+Marking all edges out of BB 77 but (77 -> 79) as not executable
+Marking all outgoing edges of unreachable BB 78 as not executable
 Visiting BB 79

I think the bug is that sccvn uses DECL_UIDs in hash computations, so in some cases we end up with different hashcodes, different collisions and if unlucky enough, e.g. vn_phi_lookup can find a different value based on that.
If I instrument:
@@ -3120,6 +3120,9 @@ vn_phi_insert (gimple *phi, tree result)
   vp1->result = result;
   vp1->hashcode = vn_phi_compute_hash (vp1);
 
+fprintf (stderr, "vn_phi_insert %08x %d %d\n", vp1->hashcode, TREE_CODE (result) == SSA_NAME ? SSA_NAME_VERSION (result) : -1);
+extern void debug_gimple_stmt (gimple *);
+debug_gimple_stmt (phi);
   slot = current_info->phis->find_slot_with_hash (vp1, vp1->hashcode, INSERT);
 
   /* Because we iterate over phi operations more than once, it's
I see:
 vn_phi_insert 127d0253 12 146
 .MEM_12 = PHI <.MEM_13(D)(2), .MEM_26(3)>
-vn_phi_insert e38159ce 29 146
-_29 = PHI <&D.834312(2), &D.834311(3)>
-vn_phi_insert e38159ce 29 146
-_29 = PHI <&D.834312(2), &D.834311(3)>
+vn_phi_insert 851182e7 29 146
+_29 = PHI <&D.834716(2), &D.834715(3)>
+vn_phi_insert 851182e7 29 146
+_29 = PHI <&D.834716(2), &D.834715(3)>
 vn_phi_insert 77edc47d 9 146
 .MEM_9 = PHI <.MEM_13(4), .MEM_14(3)>

While -g vs. -g0 guarantees the bbs and SSA_NAME_VERSIONs etc. are always the same, we don't have any such a guarantee for DECL_UIDs, there is just a guarantee that the corresponding DECL_UIDs in between -g and -g0 compare the same, but they can have different gaps in between them.

Not really sure what is the way out of this (nor does this really look like a recent regression, it is just something really hard to reproduce, one has to be unlucky enough).  Perhaps in inchash::add_expr optionally use a DECL_UID -> uid hash map if the caller asks for it, which would map DECL_UIDs (only if seen in non-debug stmts) to say visit #s.  Or try to guarantee identical DECL_UIDs between -g and -g0 (we'd need to have some flag for decl creation in "debug only" contexts and use say negative uids, dunno if we'd need to be prepared to bump those "debug only" uids into normal uids if they are looked up in non-"debug only" contexts later on.

I've seen the same issue with gcc-6, so it is not a trunk regression.

So the issue is that vn_phi_eq depends on cond_stmts_equal_p which may change
if we value-number the controlling condition after the PHI itself which can
trivially happen with SCC based value-numbering as controlling conditions are
not part of the SCC.

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c        (revision 246964)
+++ gcc/tree-ssa-sccvn.c        (working copy)
@@ -2941,10 +2941,12 @@ cond_stmts_equal_p (gcond *cond1, gcond
   else
     return false;
 
+#if 0
   lhs1 = vn_valueize (lhs1);
   rhs1 = vn_valueize (rhs1);
   lhs2 = vn_valueize (lhs2);
   rhs2 = vn_valueize (rhs2);
+#endif
   return ((expressions_equal_p (lhs1, lhs2)
           && expressions_equal_p (rhs1, rhs2))
          || (commutative_tree_code (code1)

would fix this (and pessimize PHI VN of course).

Created attachment 41234 [details]
patch

Patch I am testing that is less pessimizing (we need to remember valueized controlling condition args).

Author: rguenth
Date: Thu Apr 20 14:23:10 2017
New Revision: 247024

URL: https://gcc.gnu.org/viewcvs?rev=247024&root=gcc&view=rev
Log:
2017-04-20  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/80453
	* tree-ssa-sccvn.h (struct vn_phi_s): Add cclhs and ccrhs members.
	* tree-ssa-sccvn.c (cond_stmts_equal_p): Use recorded lhs and rhs
	from the conditions.
	(vn_phi_eq): Pass them down.
	(vn_phi_lookup): Record them.
	(vn_phi_insert): Likewise.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-sccvn.c
    trunk/gcc/tree-ssa-sccvn.h

Fixed on trunk sofar.

Author: rguenth
Date: Wed May  3 11:22:34 2017
New Revision: 247545

URL: https://gcc.gnu.org/viewcvs?rev=247545&root=gcc&view=rev
Log:
2017-05-03  Richard Biener  <rguenther@suse.de>

	Backport from mainline
	2017-04-20  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/80453
	* tree-ssa-sccvn.h (struct vn_phi_s): Add cclhs and ccrhs members.
	* tree-ssa-sccvn.c (cond_stmts_equal_p): Use recorded lhs and rhs
	from the conditions.
	(vn_phi_eq): Pass them down.
	(vn_phi_lookup): Record them.
	(vn_phi_insert): Likewise.

	2017-04-25  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/80492
	* alias.c (compare_base_decls): Handle registers with asm
	specification conservatively.

	* gcc.dg/pr80492.c: New testcase.

	2017-04-27  Richard Biener  <rguenther@suse.de>

	PR middle-end/80539
	* tree-chrec.c (chrec_fold_plus_poly_poly): Deal with not
	being in loop-closed SSA form conservatively.
	(chrec_fold_multiply_poly_poly): Likewise.

	* gcc.dg/torture/pr80539.c: New testcase.

Added:
    branches/gcc-7-branch/gcc/testsuite/gcc.dg/pr80492.c
    branches/gcc-7-branch/gcc/testsuite/gcc.dg/torture/pr80539.c
Modified:
    branches/gcc-7-branch/gcc/ChangeLog
    branches/gcc-7-branch/gcc/alias.c
    branches/gcc-7-branch/gcc/testsuite/ChangeLog
    branches/gcc-7-branch/gcc/tree-chrec.c
    branches/gcc-7-branch/gcc/tree-ssa-sccvn.c
    branches/gcc-7-branch/gcc/tree-ssa-sccvn.h

Fixed.

Author: rguenth
Date: Thu Jun 22 07:30:03 2017
New Revision: 249499

URL: https://gcc.gnu.org/viewcvs?rev=249499&root=gcc&view=rev
Log:
2017-06-22  Richard Biener  <rguenther@suse.de>

	Backport from mainline
	2017-04-20  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/80453
	* tree-ssa-sccvn.h (struct vn_phi_s): Add cclhs and ccrhs members.
	* tree-ssa-sccvn.c (cond_stmts_equal_p): Use recorded lhs and rhs
	from the conditions.
	(vn_phi_eq): Pass them down.
	(vn_phi_lookup): Record them.
	(vn_phi_insert): Likewise.

	2017-04-07  Richard Biener  <rguenther@suse.de>

	PR middle-end/80341
	* tree.c (get_unwidened): Also handle ! for_type case for
	INTEGER_CSTs.
	* convert.c (do_narrow): Split out from ...
	(convert_to_integer_1): ... here.  Do not pass final truncation
	type to get_unwidened for TRUNC_DIV_EXPR.

	* gcc.dg/torture/pr80341.c: New testcase.

	2017-04-04  Richard Biener  <rguenther@suse.de>

	PR middle-end/80281
	* match.pd (A + (-B) -> A - B): Make sure to preserve unsigned
	arithmetic done for the negate or the plus.  Simplify.
	(A - (-B) -> A + B): Likewise.
	* fold-const.c (split_tree): Make sure to not negate pointers.

	* gcc.dg/torture/pr80281.c: New testcase.

Modified:
    branches/gcc-6-branch/gcc/ChangeLog
    branches/gcc-6-branch/gcc/convert.c
    branches/gcc-6-branch/gcc/fold-const.c
    branches/gcc-6-branch/gcc/match.pd
    branches/gcc-6-branch/gcc/testsuite/ChangeLog
    branches/gcc-6-branch/gcc/tree-ssa-sccvn.c
    branches/gcc-6-branch/gcc/tree-ssa-sccvn.h
    branches/gcc-6-branch/gcc/tree.c