[RFA] [PATCH][PR tree-optimization/64910] Fix reassociation of binary bitwise operations with 3 operands

[Jeff Law]

On 01/08/2016 02:36 AM, Richard Biener wrote:
>> My original patch did this for all binary operations.  However, reviewing
>> the assembly code & dump files before/after it was pretty clear that doing
>> this for arithmetic was losing (mostly in that we were missing CSE
>> opportunities).
>
> The missed CSE opportunities really are a CSE missed optimization in
> general with respect to two reassociatable chains with some (but not all)
> common operands.
Agreed.  It was a choice between expanding the scope and tracking down 
the missed CSEs or nailing down 64910 without regressing and putting 
that the missed CSEs on the TODO list.

How about I build some testcases for the missed CSEs, xfailed with a BZ 
too, so that we at least don't lose track of 'em.

> So you are really trying to make RTL expansion see a different pattern?
Yes, absolutely.  The code we generate now does

(x OP C) OP y

which makes it bloody hard for the RTL/target bits to recognize bit 
operations.  After the patch we generate

(x OP y) OP C

Which the RTL & backends can easily see as bitwise operations.


>
> It seems to me that in this case using TER and get_def_for_expr /
> get_gimple_for_ssa_name
> should be used there.  [or for future direction instruction selection
> should be performed on
> GIMPLE with some match-and-simplify patterns creating IFNs matching
> optabs if available]
That seems backwards to me -- we have all the infrastructure in place in 
reassoc.c we just make a terrible decision for the ordering of the 
operands.    In fact, the code is fine going into reassoc, it's reassoc 
that mucks things up:

Before reassoc we have:


;;   basic block 2, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 0, next block 3, flags: (NEW, REACHABLE)
;;    pred:       ENTRY [100.0%]  (FALLTHRU,EXECUTABLE)
   _4 = u_2(D) & w_3(D);
   _7 = _4 & 32;
   if (_7 != 0)
     goto <bb 3>;
   else
     goto <bb 4>;


Which looks just like a bit test.  Sadly reassoc comes around and turns 
it into:

;;   basic block 2, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 0, next block 3, flags: (NEW, REACHABLE)
;;    pred:       ENTRY [100.0%]  (FALLTHRU,EXECUTABLE)
   _8 = w_3(D) & 32;
   _7 = _8 & u_2(D);
   if (_7 != 0)
     goto <bb 3>;
   else
     goto <bb 4>;


And we've lost.

Plus doing it in TER is almost certainly more complex than getting it 
right in reassoc to begin with.

Jeff