[LLVMdev] Ideas for representing vector gather/scatter and masks in LLVM IR

[Daniel Berlin]

On Thu, Aug 7, 2008 at 3:13 PM, David Greene <dag at cray.com> wrote:
> On Tuesday 05 August 2008 13:27, David Greene wrote:
>
>> Neither solution eliminates the need for instcombine to be careful and
>> consult masks from time to time.
>>
>> Perhaps I'm totally missing something.  Concrete examples would be helpful.
>
> Ok, so I took my own advice and thought about CSE and instcombine a bit.
> I wrote the code by hand in a sort of pseudo-llvm language, so don't
> crucify me for mistakes.  :)
>
> CSE is an optimization that needs to pay attention to masks.  You can't
> (easily) CSE an expression with different masks.

If you are using a value based CSE, you can easily CSE expressions
with different masks.
I'd agree with lexical expression based CSE, you can't, but that's a
pretty weak form of CSE.

>
> Using a mask-per-operation setup, code might look like this:
>
>...
..

>
> With applymask, things look something like this:
>
> applymask:
> %m1 = ...
> %m2 = ...
> %r5 = applymask %r2, %m1
> %r6 = applymask %r3, %m1
> %r7 = applymask %r2, %m2
> %r8 = applymask %r3, %m2
> %r1 = add %r5, %r6
> %r4 = add %r7, %r8
>
> This is interesting because CSE will not do the optimization since the
> operands of the adds are different.

LLVM's main CSE these days is really GVN based.
GVN should happily compute these to be the same value, and if it
doesn't, you have much larger problems.

GCC's value numberer already combines shifts and masks during value
numbering over multiple binary operations.
It is not hard to make LLVM's do the same to the small degree it
doesn't (the value numbering does not value number phi nodes/cycles
iteratively so it misses identities between induction variables and
things based on them in some cases.  SCEV saves it in others)
You don't need to do it to the level instcombine does to get good results.

This is all with my "Person who implemented SCC based value numbering
and value based PRE in GCC" hat on :)
--Dan