llvm dev - Mar 2016 - [VSXFMAMutate] OldFMAReg may be wrongly rewritten

Ping?

On Mon, Feb 22, 2016 at 1:06 PM Tim Shen <timshen at google.com> wrote:
> On Fri, Feb 19, 2016 at 5:10 PM Tim Shen <timshen at google.com>
wrote:
>
>> I wonder if we can fix this by making the transformation simpler, that
>> is, instead of doing:
>>
>
> I wrote a prototype (see attach) for this idea, it actually improves some
> of the test cases (e.g. fma-assoc.ll: test_FMADD_ASSOC1), but pessimize
> several other cases (e.g. test_FMADD_ASSOC_EXT1).
>
> I'm not sure what to do at this point, I have several options:
> 1) This pass simply omits the optimization for certain cases
("certain"
> needs to be defined).
> 2) This pass should never mutate anything out of the block, and may add a
> copy at the end of the block, if the value is live-out.
> 3) tune the transformation as I attempted, to make it simpler, working,
> and producing better result? It seems interesting to get the improvement as
> my prototype shown without hurting other test cases, but it needs a bit
> thinking and I'd like to fix the compiler crash soon.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160229/378f1f15/attachment.html>

Relaying an IRC conversation here:

Currently we're going to disable the VSXFMAMutate pass in ToT and talk
about ways to either rewrite or fix it to deal with more complicated cfgs.

Thanks!

-eric

On Mon, Feb 29, 2016 at 2:21 PM Tim Shen <timshen at google.com> wrote:
> Ping?
>
> On Mon, Feb 22, 2016 at 1:06 PM Tim Shen <timshen at google.com>
wrote:
>
>> On Fri, Feb 19, 2016 at 5:10 PM Tim Shen <timshen at google.com>
wrote:
>>
>>> I wonder if we can fix this by making the transformation simpler,
that
>>> is, instead of doing:
>>>
>>
>> I wrote a prototype (see attach) for this idea, it actually improves
some
>> of the test cases (e.g. fma-assoc.ll: test_FMADD_ASSOC1), but pessimize
>> several other cases (e.g. test_FMADD_ASSOC_EXT1).
>>
>> I'm not sure what to do at this point, I have several options:
>> 1) This pass simply omits the optimization for certain cases
("certain"
>> needs to be defined).
>> 2) This pass should never mutate anything out of the block, and may add
a
>> copy at the end of the block, if the value is live-out.
>> 3) tune the transformation as I attempted, to make it simpler, working,
>> and producing better result? It seems interesting to get the
improvement as
>> my prototype shown without hurting other test cases, but it needs a bit
>> thinking and I'd like to fix the compiler crash soon.
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160302/3f16e68b/attachment.html>

I wonder if we can do this in a separate analysis MachineFunction SSA pass.
1) SelectionDAG will generate a pseudo instruction MutatingFMA. When it's
generated it's allowed to have d = a * b + c form, where d doesn't have
to
be in {a, b, c}.
2) Later, the proposed pass uses an algorithm to decide for instruction MI:
`%vreg0 = MutatingFMA %vreg1, %vreg2, %vreg3`, it should tie %vreg0 with,
say %vreg2. Then it tells the scheduler (through ScheduleDAG?) "If you put
instruction MI as the last use of %vreg2, the killed %vreg2 will save us a
copy". The algorithm saves as many copies as possible, and those
suggestions are guarantee to be compatible with each other, so that
scheduler can choose to follow all of them.
3) In Two-Address instruction pass, all MutatingFMA instructions are still
handled and copies get inserted. That's fine. No change is required.
4) Scheduler optionally follows our suggestions.
5) After Scheduling, we do a copy cleanup pass that change:
    %vreg0<def> = COPY %vreg2<kill>
    %vreg0<def, tied2> = MutatingFMA %vreg1, %vreg0<tied0>, %vreg3
    To:
    %vreg2<def, tie2> = MutatingFMA %vreg1, %vreg2<tied0>, %vreg3
    In the same block.
6) 1)~5) are target independent. Now the tied MutatingFMA instruction gets
lowered to one of its real forms.

The only thing left is to formalize the problem and come up with an
algorithm in 2):
Given a DAG of uninteresting nodes and interesting (e.g. MutatingFMA)
nodes, for each interesting nodes, select zero or one of its operand uses
(corresponding to an edge) to mark. Mark as many edges as possible.

I can't come up with an optimal algorithm for 2). Here's my current
greedy
solution:
1) For each vreg, calculate how many MutatingFMA instructions are using
them, and put the result into ref_count. Set up a worklist that's holding
all MutatingFMA instructions.
2) Try to get a MutatingFMA from worklist, as MI, such that, it has at
least one operand %x that has ref_count 1. If we can't find one, go to 4).
3) Make a suggestion about MI and %x. Remove MI from active set and
decrease the ref_count for each of its uses by 1.
4) If active set is empty, then we are done; otherwise remove a random (in
a heuristic manner) MutatingFMA from worklist (by making no suggestions,
aka keeping the copy) and go back to 2).

For small amount (e.g. 5) of instructions, we can also enumerate
copy/no-copy decisions for each of them. That will take 2^5 = 32 different
cases, which isn't that many.

Another concern is that ABI may require values to be put to designated
physical registers (e.g. put return value to F1). It would be good to plumb
a path from F1 as an input, finally to F1 as an output, for example:
f = a * b + c * d + e

it's better to do:
e = FMA c d e
a = FMA a b e
where the first will be an add form and the second will be a multiply form.
The greedy algorithm isn't aware of this, but the exponential algorithm can
pick this up.

The algorithm is unaware of any FMA related knowledge though, so it can be
used for any mixed instructions with in-out registers.

On Wed, Mar 2, 2016 at 3:40 PM Eric Christopher <echristo at gmail.com>
wrote:
> Relaying an IRC conversation here:
>
> Currently we're going to disable the VSXFMAMutate pass in ToT and talk
> about ways to either rewrite or fix it to deal with more complicated cfgs.
>
> Thanks!
>
> -eric
>
> On Mon, Feb 29, 2016 at 2:21 PM Tim Shen <timshen at google.com>
wrote:
>
>> Ping?
>>
>> On Mon, Feb 22, 2016 at 1:06 PM Tim Shen <timshen at google.com>
wrote:
>>
>>> On Fri, Feb 19, 2016 at 5:10 PM Tim Shen <timshen at
google.com> wrote:
>>>
>>>> I wonder if we can fix this by making the transformation
simpler, that
>>>> is, instead of doing:
>>>>
>>>
>>> I wrote a prototype (see attach) for this idea, it actually
improves
>>> some of the test cases (e.g. fma-assoc.ll: test_FMADD_ASSOC1), but
>>> pessimize several other cases (e.g. test_FMADD_ASSOC_EXT1).
>>>
>>> I'm not sure what to do at this point, I have several options:
>>> 1) This pass simply omits the optimization for certain cases
("certain"
>>> needs to be defined).
>>> 2) This pass should never mutate anything out of the block, and may
add
>>> a copy at the end of the block, if the value is live-out.
>>> 3) tune the transformation as I attempted, to make it simpler,
working,
>>> and producing better result? It seems interesting to get the
improvement as
>>> my prototype shown without hurting other test cases, but it needs a
bit
>>> thinking and I'd like to fix the compiler crash soon.
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160305/3fb72195/attachment.html>