Started with r229360.  Debugging.

So far this looks like some tree sharing issue.
                      *expr_p = gimple_boolify (*expr_p);
                      if (!useless_type_conversion_p (org_type,
                                                      TREE_TYPE (*expr_p)))
                        {
                          *expr_p = fold_convert_loc (input_location,
                                                      org_type, *expr_p);
                          ret = GS_OK;
                        }
changes in place unsigned int type into bool and then wraps into cast to unsigned int, but that now bool EQ_EXPR appears somewhere else too.

So, it is indeed that
/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
(simplify
 (minus (bit_and:cs @0 (bit_not @1)) (bit_and:cs @0 @1))
  (minus (bit_xor @0 @1) @1))
pattern which uses @1 more than once.  For normal generic folding it wouldn't be as big problem, because we unshare everything before gimplification.
Except that in this case it triggers late, already during gimplification:
#0  generic_simplify_87 (loc=2147483653, type=<integer_type 0x7fffefae0690 unsigned int>, op0=<bit_and_expr 0x7fffefc51398>, 
    op1=<bit_and_expr 0x7fffefc51348>, captures=0x7fffffffb6b0) at generic-match.c:3644
#1  0x00000000016f22d1 in generic_simplify_MINUS_EXPR (loc=2147483653, code=MINUS_EXPR, type=<integer_type 0x7fffefae0690 unsigned int>, 
    op0=<bit_and_expr 0x7fffefc51398>, op1=<bit_and_expr 0x7fffefc51348>) at generic-match.c:12824
#2  0x00000000017406be in generic_simplify (loc=2147483653, code=MINUS_EXPR, type=<integer_type 0x7fffefae0690 unsigned int>, 
    op0=<bit_and_expr 0x7fffefc51398>, op1=<bit_and_expr 0x7fffefc51348>) at generic-match.c:33944
#3  0x0000000000d3a0ab in fold_binary_loc (loc=2147483653, code=MINUS_EXPR, type=<integer_type 0x7fffefae0690 unsigned int>, 
    op0=<bit_and_expr 0x7fffefc51398>, op1=<bit_and_expr 0x7fffefc51348>) at ../../gcc/fold-const.c:9157
#4  0x0000000000d4a1d5 in fold_build2_stat_loc (loc=2147483653, code=MINUS_EXPR, type=<integer_type 0x7fffefae0690 unsigned int>, 
    op0=<bit_and_expr 0x7fffefc51398>, op1=<bit_and_expr 0x7fffefc51348>) at ../../gcc/fold-const.c:12285
#5  0x0000000000bef110 in convert_to_integer_1 (type=<integer_type 0x7fffefae0690 unsigned int>, expr=<minus_expr 0x7fffefc511b8>, dofold=true)
    at ../../gcc/convert.c:850
#6  0x0000000000befb32 in convert_to_integer_maybe_fold (type=<integer_type 0x7fffefae0690 unsigned int>, expr=<minus_expr 0x7fffefc511b8>, 
    dofold=true) at ../../gcc/convert.c:978
#7  0x0000000000971dc6 in ocp_convert (type=<integer_type 0x7fffefae0690 unsigned int>, expr=<minus_expr 0x7fffefc511b8>, convtype=143, flags=17, 
    complain=3) at ../../gcc/cp/cvt.c:812
#8  0x0000000000974646 in convert (type=<integer_type 0x7fffefae0690 unsigned int>, expr=<minus_expr 0x7fffefc511b8>) at ../../gcc/cp/cvt.c:1590
#9  0x0000000000adfc72 in c_gimplify_expr (expr_p=0x7fffefc51318, pre_p=0x7fffffffd988, post_p=0x7fffffffd2a0)
    at ../../gcc/c-family/c-gimplify.c:247
#10 0x0000000000a4ae60 in cp_gimplify_expr (expr_p=0x7fffefc51318, pre_p=0x7fffffffd988, post_p=0x7fffffffd2a0) at ../../gcc/cp/cp-gimplify.c:863
#11 0x0000000000df0bdd in gimplify_expr (expr_p=0x7fffefc51318, pre_p=0x7fffffffd988, post_p=0x7fffffffd2a0, 
    gimple_test_f=0xdc4cde <is_gimple_reg_rhs_or_call(tree)>, fallback=1) at ../../gcc/gimplify.c:11145
#12 0x0000000000dd5b63 in gimplify_modify_expr (expr_p=0x7fffffffd3b8, pre_p=0x7fffffffd988, post_p=0x7fffffffd2a0, want_value=false)
    at ../../gcc/gimplify.c:5465

So, either we need to unshare_expr in GENERIC every time some operand is used multiple times, or have some flag we set after unsharing fn body and is set until expansion in case GENERIC folding is used during gimple optimizations (fold_build* etc.).
So far genmatch.c uses unshare_expr only for COND_EXPR or VEC_COND_EXPR conditions.
Dunno how many patterns are affected:
(simplify
 (mult (abs@1 @0) @1)
 (mult @0 @0))

(for copysigns (COPYSIGN)
 (simplify
  (mult (copysigns@2 @0 @1) @2)
  (mult @0 @0)))

(simplify
 (bit_ior:c (bit_and:cs @0 (bit_not @2)) (bit_and:cs @1 @2))
 (bit_xor (bit_and (bit_xor @0 @1) @2) @0))

(for cmp (eq ge le)
 (simplify
  (cmp @0 @0)
  (if (! FLOAT_TYPE_P (TREE_TYPE (@0))
       || ! HONOR_NANS (@0))
   { constant_boolean_node (true, type); }
   (if (cmp != EQ_EXPR)
    (eq @0 @0)))))

(for cmp (unlt ungt)
 (simplify
  (cmp @0 @0)
  (unordered @0 @0)))

       (if (! HONOR_NANS (@0))
        { constant_boolean_node (true, type); }
        /* x <= +Inf is the same as x == x, i.e. !isnan(x).  */
        (eq @0 @0)))

(simplify
 (minus (bit_and:cs @0 (bit_not @1)) (bit_and:cs @0 @1))
  (minus (bit_xor @0 @1) @1))
(simplify
 (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
 (if (wi::bit_not (@2) == @1)
  (minus (bit_xor @0 @1) @1)))

(simplify
 (minus (bit_and:cs @0 @1) (bit_and:cs @0 (bit_not @1)))
  (minus @1 (bit_xor @0 @1)))

are what I found.  So shall genmatch.c watch for captures used multiple times and in GENERIC emit unshare_expr for the second and further uses in there?

genmatch (correctly) allows tree sharing in GENERIC, just uses unshare_expr on GENERIC parts that we still have in GIMPLE.

folding from inside the gimplifier is tricky for this reason (as it expects unshared GENERIC).  I'd say the gimplifier needs to avoid GENERIC folding
and/or call unshare_expr on its results...

Given we now have "SSA" during gimplification the gimplifier could use
fold_stmt (gsi, follow_single_use_edges).  But I see this case is even
from the gimplify langhook doing the folding ... :/

As said, genmatch not avoiding tree sharing in GENERIC is a feature and
mimics what fold-const.c does so the issue isn't new but latent anyway.

We can experiment with adding unshare_exprs to genmatch and see in how many patterns that triggers.  But as said, the general issue looks latent to me.
Folding during gimplification is dangerous.

(In reply to Richard Biener from comment #5)
> We can experiment with adding unshare_exprs to genmatch and see in how many
> patterns that triggers.  But as said, the general issue looks latent to me.
> Folding during gimplification is dangerous.

It isn't just folding during gimplification, we have hundreds of fold_build* calls in tons of GIMPLE passes too, and at that point unsharing is also needed.
I'll try to implement the unsharing and we can see how many patterns it affects and based on that decide if we want some cfun flag to control the unsharing or not, ok?

On Tue, 4 Apr 2017, jakub at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80297
> 
> --- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #5)
> > We can experiment with adding unshare_exprs to genmatch and see in how many
> > patterns that triggers.  But as said, the general issue looks latent to me.
> > Folding during gimplification is dangerous.
> 
> It isn't just folding during gimplification, we have hundreds of fold_build*
> calls in tons of GIMPLE passes too, and at that point unsharing is also needed.

Well, any GENERIC created there needs to go through force_gimple_operand
again.  Hmm, but that doesn't unshare either.

> I'll try to implement the unsharing and we can see how many patterns it affects
> and based on that decide if we want some cfun flag to control the unsharing or
> not, ok?

Ok.  But given the above we have no choice..

What are the exact rules for GENERIC?  ISTR it was that 
sub-expression sharing is allowed, right?  Or is that just for
frontend GENERIC?  OTOH it would mean that fold-const.c has to cope
with tree sharing but may not generate "new" sharing?  That would be
quite a difficult thing to verify with a verifier...

Created attachment 41121 [details]
gcc7-pr80297.patch

Patch I'm going to test.

On Tue, 4 Apr 2017, jakub at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80297
> 
> --- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
> Created attachment 41121 [details]
>   --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=41121&action=edit
> gcc7-pr80297.patch
> 
> Patch I'm going to test.

LGTM.

Author: jakub
Date: Tue Apr  4 19:14:47 2017
New Revision: 246693

URL: https://gcc.gnu.org/viewcvs?rev=246693&root=gcc&view=rev
Log:
	PR c++/80297
	* genmatch.c (capture::gen_transform): For GENERIC unshare_expr
	captures used multiple times, except for the last use.
	* generic-match-head.c: Include gimplify.h.

	* g++.dg/torture/pr80297.C: New test.

Added:
    trunk/gcc/testsuite/g++.dg/torture/pr80297.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/generic-match-head.c
    trunk/gcc/genmatch.c
    trunk/gcc/testsuite/ChangeLog

Fixed on the trunk so far.

Author: jakub
Date: Fri May  5 21:52:00 2017
New Revision: 247697

URL: https://gcc.gnu.org/viewcvs?rev=247697&root=gcc&view=rev
Log:
	Backported from mainline
	2017-04-04  Jakub Jelinek  <jakub@redhat.com>
		    Richard Biener  <rguenther@suse.de>

	PR c++/80297
	* genmatch.c (capture::gen_transform): For GENERIC unshare_expr
	captures used multiple times, except for the last use.
	* generic-match-head.c: Include gimplify.h.

	* g++.dg/torture/pr80297.C: New test.

Added:
    branches/gcc-6-branch/gcc/testsuite/g++.dg/torture/pr80297.C
Modified:
    branches/gcc-6-branch/gcc/ChangeLog
    branches/gcc-6-branch/gcc/generic-match-head.c
    branches/gcc-6-branch/gcc/genmatch.c
    branches/gcc-6-branch/gcc/testsuite/ChangeLog

Fixed.