Re: [RFC] optabs and tree-codes for vector operations

[Dorit Naishlos <DORIT at il dot ibm dot com>]

> You've forgotten about stores again.

I was intentionally trying to separate the discussion, because the handling
of unaligned stores is more involved. In the absence of a general store to
unaligned addresses, some targets require that two adjacent aligned vectors
be loaded, their middle elements replaced by the value to be stored and
then they are stored back. Two or more consecutive unaligned stores can be
broken into an unaligned store prolog, aligned stores and an unaligned
store epilog, by peeling the first and last iterations (provided we can
delay storing elements by one iteration; see [***] below).


> > 2. load from a "floor aligned" address ("LOADFLOOR")
> >    optab (new): load_floor_optab
> >    tree (new): MODIFY_EXPR (z, ALIGN_INDIRECT_REF(ptr_ref))
> >
> > 3. load from an arbitrary address ("LOADU")
> >    optab (new): loadu_optab
> >    tree: option1 (preferred): MODIFY_EXPR (z,ref),
> >                  in which ref has alignment info (ala dannyb)
> >     option2 (new tree, until above is supported): LOADU_EXPR (z,ref)
> >
> > example: LOADU = ldl,ldr,or[mips]/ movdqu[sse]/
> > ldqu,ldqu,extql,extqh,or[alpha]/ lvx,lvx,lvsr,vperm[vmx]
>
> > Again, it's not just loads.  It's stores as well.

right:

- "storefloor":
  optab: store_floor_optab
  tree: MODIFY_EXPR (ALIGN_INDIRECT_REF(ptr_ref), z)

- "store_to_arbitrary_address":
  optab: storeu_optab
  tree: option1: MODIFY_EXPR (ref,z),
                  in which ref is annotated with alignment info
        option2: MODIFY_EXPR (MISALIGNED_INDIRECT_REF (ref,x),z) [**]
        option3: STOREU_EXPR

[**] new proposal; see below.


> vectr = REALIGN_LOAD_EXPR < vect1, vect2, magic >

Let me see if I understand the semantics of the operation you propose:

> magic:          Two cases, depending on whether or not the
>                 target supplies a mask creation builtin.
>
>                 If the builtin exists, this operand receives
>                 the value it generated from the initial address.

You say that magic is either an address, or the result of a builtin that
takes an address. Can the builtin be encapsulated within REALIGN_LOAD_EXPR
? i.e - have a REALIGN_LOAD_EXPR(v1,v2,addr) that on some targets will be
expanded to {x=builtin(addr),smthing(v1,v2,x)} and on other targets will be
expanded directly to {smthing(v1,v2,addr)}? Is there an added value for
exposing it to the vectorizer (for example, could it be used to indicate
whether the REALIGN_LOAD_EXPR allows software-pipelining when the alignment
is unknown?)

>                 If the builtin doesn't exist, this operand
>                 receives an address related to either vect1
>                 or vect2.  We assume that only the low bits
>                 matter here, so any value handy should work.
>                 Our object is to not increase register pressure
>                 more then necessary.

If we only care about the low bits of the address we could pass an offset
rather than an address. But maybe we can't do that because the builtin may
need the whole address? Do we assume anything about the address - e.g. - is
the address assumed to be not aligned, or have a known constant
misalignment?

> vect1, vect2:          Sequential values read from the array, however
>                        we decided to read from the array.

The real assumption is not that the data was loaded sequentially from
memory, but that this utility concatenates the last VS - OFF elements from
vect1 to the first OFF elements of vect2, right? (VS is the vector-size,
OFF is the alignment of addr). The question is, can we use
REALIGN_LOAD_EXPR with vect1/vect2 that are not "sequential values read
from an array"? This comes up for example at the end cases (first and last
iterations) of misaligned store support - when we must not access data
beyond the boundaries of the accessed array (See description below [***]).

Do the semantics of REALIGN_LOAD_EXPR imply that (if it is supported) we
can always generate the following, for a load from unaligned address addr:

      vect1=loadfloor(addr)
      vect2=loadfloor(addr+d)
      vect3=REALIGN_LOAD_EXPR(vect1,vect2,addr)?

(If not, then how would the vectorizer know which loads it can use to feed
a REALIGN_LOAD_EXPR?)

How would the vectorizer know if it can software pipeline the first
loadfloor? e.g, that it can generate:

      [load-scheme2]
            x = loadfloor (addr)
      loop start
            y = loadfloor (addr+d)
            z = REALIGN_LOAD_EXPR (x, y, addr)
            addr += vecsize
            x = y
      loop end

On alpha, the realign utility - {extqh,extql,or} - allows software
pipelining only if we know that the access is not aligned (as you pointed
out). Is that something that a target hook will decide? My thinking was
that there's no point in breaking the unaligned load into a sequence of
{loadfloor;loadfloor;REALIGN_LOAD_EXPR} during vectorization if
REALIGN_LOAD_EXPR doesn't allow software-pipelining. Because then the
vectorizer has to keep the sequence intact, and it may as well generate a
"load_from_arbitrary_address" (a LOADU_EXPR or whatever representation
we'll agree on):

      [load-scheme1]
      loop start
            z = LOADU_EXPR (addr) //or other representation
            addr += vecsize
      loop end

and let the RTL expander create the {loadfloor,loadflor,realign} sequence
from the LOADU_EXPR.

In other words, the fact that REALIGN_LOAD_EXPR is supported should imply
that the loads can be software-pipelined.


> We need a different operation for stores here.  The realignment
> based on the address is reversed.

Yes. A few clarifications on the semantics of
  REALIGN_STORE_EXPR <vect1, vect2, addr>:

Does this operation encapsulate a store in it, or are we going to use it as
follows:
      v3 = REALIGN_STORE_EXPR (vect1, vect2, addr)
      storefloor (v3, addr) ?

I assume that REALIGN_STORE_EXPR can take arbitrary vect1 and vect2, and
that it concatenates last OFF elements of vect1 to first VS - OFF elements
of vect2 (where OFF is the misalignment of addr); right? (i.e, the only
difference between REALIGN_LOAD_EXPR and REALIGN_STORE_EXPR is this
reversing).

To summarize, the suggested building blocks of misalignment support are
for loads: loadfloor + realign_load, or "load_from_arbitrary_address".
for stores: realign_store + storefloor, or "store_to_arbitrary_address".

[***] Below is two possible schemes for handling misaligned stores. One is
an optimized scheme, in which you peel the first and last iterations (if we
can postpone storing elements by one iteration). My question is whether the
building blocks discussed above are properly used here; specifically, the
REALIGN_LOAD_EXPR in lines 3 and 13, where we need to supply some
'dontcare' vector rather than actual data from adjacent memory (which we
must not access cause it's beyond the boundaries of the array). Is that a
valid usage of REALIGN_LOAD_EXPR, or do vect1,vect2 really need to be
results of consecutive loadfloors?

      [store-scheme1]:
      loop_start
            t = computation
            STOREU_EXPR (t, addr) // or other representation
            addr += VS
      loop_end

      [store-scheme2]: (optimized)
            1. t1 = computation
            2. x = loadfloor (addr)
            3. x' = REALIGN_LOAD_EXPR (dontcare, x, addr)
            4. z = REALIGN_STORE_EXPR (x', t1, addr)
            5. storefloor (z, addr)
            6. addr+=VS
      loop_start (iterates one iteration less than original loop)
            7. t2 = computation
            8. z = REALIGN_STORE_EXPR (t1, t2, addr)
            9. storefloor (z, addr) // (part of t2 stored in next iter)
            10. addr+=VS
            11. t1 = t2
      loop_end
            12. y = loadfloor (addr)
            13. y' = REALIGN_LOAD_EXPR (y, dontcare, addr)
            14. z = REALIGN_STORE_EXPR (t2, y', addr)
            15. storefloor (z, addr)


So much for REALIGN_LOAD_EXPR/REALIGN_STORE_EXPR...

Now for:
      LOADU_EXPR (addr) //or other representation
      STOREU_EXPR (t, addr) //or other representation

>>> > <6> load from an unaligned address...
>>>
>>> If dannyb's alignment data can somehow make it through to the rtl
>>> level, we can use MODIFY_EXPR for this case too.
>>>
>> I hope it would be OK to introduce a new tree-code for this
>> purpose (LOADU_EXPR?) temporarily until we figure out how to do that.
>>
> I think the level of effort
> involved in propagating new tree codes that can affect stores is
> about the same as fixing the alignment propagation problem, and is
> less useful generally.

Propagating alignment info is a separate effort that should probably be
considered along with other plans for maintaining information attached to
SSA names through the different SSA passes and translation out of SSA and
into the RTL expander. This effort I think is already being carried out by
others. In the meantime, while this infrastructure is being developed,
maybe we can find a way to make progress on the vectorizer in parallel. I
don't have a good feel for how much work is involved in introducing a new
store tree code vs. propagating alignment info. I agree that propagating
alignment info is the preferred solution. I accept your assessment that
this solution involves about the same effort as introducing a
"store_to_unaligned_address" tree-code. Maybe instead we can consider
adding the following tree-code:
  MISALIGNED_INDIRECT_REF <pointer, mis>
which will be used like the ALIGN_INDIRECT_REF you suggested, as the
operand of a MODIFY_EXPR. 'mis' will be an integer_cst with value -1 if the
alignment of the pointer is unknown, and otherwise will hold the alignment
of the pointer. ?


> > 4.1. "JOIN_CST": optab (new): realign_cst_load_optab?
> > example: extql,extqh,or[alpha]/ lvsl(addr),vperm[vmx]
> >
> > 4.2. "JOIN_ARBIRARY": optab (new): realign_load_optab?
> > example: lvsr(-addr),vperm[vmx]
>
> What are you planning to do with these?  Apart from being able
> to issue "vperm" from them, what semantics do you want?

The vectorizer needs to know if it can use REALIGN_LOAD_EXPR when the
alignment is unknown, and whether it can use REALIGN_LOAD_EXPR with
software-pipelined loadfloor's. The two optabs were meant to provide an
indication whether the 'realign' utility allows software-pipelining the
loads (I tried to scketch how I was thinking to use it at the end of my
previous note; see also below). If I can't get that information through the
optab mechanism, I either need some other way to model that, or I'll have
to do the software-pipelined misalignment handling within target hooks. I
think the software pipelined scheme has enough in common between different
targets to try to avoid doing it in target hooks:

if (alignment == 0)
      no problems here
else if (alignment is constant)
  {
     if (realign_cst_load_optab && load_floor_optab)
       do load-scheme2  // the software-pipelined scheme
     else if (loadu_optab)
       do load-scheme1
     else
       can't vectorize
  }
else /* alignment is unknown */
  {
     if (realign_var_load_optab && load_floor_optab)
       do load-scheme2  // the software-pipelined scheme
     else if (loadu_optab)
       do load-scheme1
     else
       can't vectorize
  }

(There will be a similar framework for stores too).

thanks,

dorit