match.pd: Optimize (x & y) ^ (x | y)

[Richard Biener]

On Sat, 13 Jun 2015, Marc Glisse wrote:

> On Fri, 12 Jun 2015, Marek Polacek wrote:
> 
> > > > > fold-const.c traditionally avoided the combinatorial explosion by
> > > > > using
> > > > > strip_nops.
> > > > 
> > > > Yeah.  We can probably special case conditional conversions in code
> > > > generation instead of lowering it.  And then go the full way and special
> > > > case nop conversions so you can avoid writing the predicate as well.
> > > 
> > > Without special casing, I currently have:
> > > 
> > > (match (nopcvt @0)
> > >  (convert? @0)
> > >  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))))
> > > (simplify
> > >  (bit_xor:c (convert1? (bit_and@2 (nopcvt @0) (nopcvt @1)))
> > >             (convert2? (bit_ior:c (nopcvt @0) (nopcvt @1))))
> > >  (if (tree_nop_conversion_p (type, TREE_TYPE (@2)))
> 
> This could use @0 instead of @2 to save 2 characters.
> 
> > >   (bit_xor (convert @0) (convert @1))))
> > > 
> > > which simplifies Jakub's testcase without exploding the size of *-match.c,
> > > but it is still not very satisfying.
> > 
> > Yeah, imagine if we'd have to change every pattern like that :-(.

Indeed.  I don't like adding that (match (nopcvt)).  We should improve
on the IL instead.

> I am not sure that we will be able to completely avoid it. Nop conversions can
> be ignored in some places, but not everywhere, so we have to be explicit about
> it. We could make a nice short notation, say bit_and# to switch whether there
> is an implicit strip_nops or not, and pick the default that applies to most
> patterns. We would still need a way to access the unstripped version of @2
> (@#2 maybe?). And we would still need the 'convert' in the output pattern,
> unless we teach genmatch to add nop conversions in many places, which sounds
> complicated.

Yeah, I also think we want to be explicit, which means adding both
the conditional nop-convert and the output convert.  What we can do
is invent new [s]nop (according to STRIP_NOPS / STRIP_SIGN_NOPS)
codes that when used conditional (not sure if we want to support
unconditional use?) always act like if you were using nop1, nop2, nop3, 
... but special-case it in code-generation to magically add
a tree_nop_conversion_p check (somewhere).

I think we can't easily remove the exponential explosion in the number
of nodes in the decision tree though (but for a single leaf op or by
outlining to a function which is the effect of your (match (nopcvt))
approach - though in the end I'd like to have those "inlined")

Richard.