From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-return-167664-listarch-gcc=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 4111 invoked by alias); 22 Mar 2011 16:52:53 -0000
Received: (qmail 3990 invoked by uid 22791); 22 Mar 2011 16:52:50 -0000
X-SWARE-Spam-Status: No, hits=-2.3 required=5.0	tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW
X-Spam-Check-By: sourceware.org
Received: from mail-bw0-f47.google.com (HELO mail-bw0-f47.google.com) (209.85.214.47)    by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 22 Mar 2011 16:52:40 +0000
Received: by bwz10 with SMTP id 10so6187992bwz.20        for <gcc@gcc.gnu.org>; Tue, 22 Mar 2011 09:52:38 -0700 (PDT)
Received: by 10.204.126.227 with SMTP id d35mr306771bks.122.1300812757833;        Tue, 22 Mar 2011 09:52:37 -0700 (PDT)
Received: from richards-thinkpad (gbibp9ph1--blueice3n2.emea.ibm.com [195.212.29.84])        by mx.google.com with ESMTPS id c11sm5275398bkc.2.2011.03.22.09.52.35        (version=TLSv1/SSLv3 cipher=OTHER);        Tue, 22 Mar 2011 09:52:36 -0700 (PDT)
From: Richard Sandiford <richard.sandiford@linaro.org>
To: gcc@gcc.gnu.org
Mail-Followup-To: gcc@gcc.gnu.org, richard.sandiford@linaro.org
Subject: RFC: Representing vector lane load/store operations
Date: Tue, 22 Mar 2011 16:52:00 -0000
Message-ID: <g4lj07w10t.fsf@linaro.org>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc/>
List-Post: <mailto:gcc@gcc.gnu.org>
List-Help: <http://gcc.gnu.org/ml/>
Sender: gcc-owner@gcc.gnu.org
X-SW-Source: 2011-03/txt/msg00322.txt.bz2

This is an RFC about adding gimple and optab support for things like
ARM's load-lane and store-lane instructions.  It builds on an earlier
discussion between Ira and Julian, with the aim of allowing these
instructions to be used by the vectoriser.

These instructions operate on N vector registers of M elements each and
on a sequence of 1 or M N-element structures.  They come in three forms:

  - full load/store:

      0<=I<N, 0<=J<M, register[I][J] = memory[J*M+I]

    E.g., for N=3, M=4:

         Registers                   Memory
         ----------------            ---------------
         RRRR  GGGG  BBBB    <--->   RGB RGB RGB RGB

  - lane load/store:

      given L, 0<=I<N register[I][L] = memory[I]

    E.g., for N=3. M=4, L=2:

         Registers                   Memory
         ----------------            ---------------
         ..R.  ..G.  ..B.    <--->   RGB

  - load-and-duplicate:

      0<=I<N, 0<=J<M, register[I][J] = memory[I]

    E.g. for N=3 V4HIs:

         Registers                   Memory
         ----------------            ----------------
         RRRR  GGGG  BBBB    <----   RGB

Starting points:

  1) Memory references should be MEM_REFs at the gimple level.
     We shouldn't add new tree codes for memory references.

  2) Because of the large data involved (at least in the "full" case),
     the gimple statement that represents the lane interleaving should
     also have the MEM_REF.  The two shouldn't be split between
     statements.

  3) The ARM doubleword instructions allow the N vectors to be in
     consecutive registers (DM, DM+1, ...) or in every second register
     (DM, DM+2, ...).  However, the latter case is only interesting
     if we're dealing with halves of quadword vectors.  It's therefore
     reasonable to view the N vectors as one big value.

(3) significantly simplifies things at the rtl level for ARM, because it
avoids having to find some way of saying that N separate pseudos must
be allocated to N consecutive hard registers.  If other targets allow the
N vectors to be stored in arbitrary (non-consecutive) registers, then
they could split the register up into subregs at expand time.
The lower-subreg pass should then optimise things nicely.

The easiest way of dealing with (1) and (2) seems to be to model the
operations as built-in functions.  And if we do treat the N vectors as
a single value, the load functions can simply return that value.  So we
could have something like:

  - full load/store:

      combined_vectors = __builtin_load_lanes (memory);
      memory = __builtin_store_lanes (combined_vectors);

  - lane load/store:

      combined_vectors = __builltin_load_lane (memory, combined_vectors, lane);
      memory = __builtin_store_lane (combined_vectors, lane);

  - load-and-duplicate:

      combined_vectors = __builtin_load_dup (memory);

We could then use normal component references to set or get the individual
vectors of combined_vectors.  Does that sound OK so far?

The question then is: what type should combined_vectors have?  (At this
point I'm just talking about types, not modes.)  The main possibilities
seemed to be:

1. an integer type

     Pros
       * Gimple registers can store integers.

     Cons
       * As Julian points out, GCC doesn't really support integer types
         that are wider than 2 HOST_WIDE_INTs.  It would be good to
         remove that restriction, but it might be a lot of work.

       * We're not really using the type as an integer.

       * The combination of the integer type and the __builtin_load_lanes
         array argument wouldn't be enough to determine the correct
         load operation.  __builtin_load_lanes would need something
         like a vector count argument (N in the above description) as well.

2. a vector type

     Pros
       * Gimple registers can store vectors.

     Cons
       * For vld3, this would mean creating vector types with non-power-
         of-two vectors.  GCC doesn't support those yet, and you get
         ICEs as soon as you try to use them.  (Remember that this is
         all about types, not modes.)

         It _might_ be interesting to implement this support, but as
         above, it would be a lot of work.  It also raises some tricky
         semantic questions, such as: what is the alignment of the new
         vectors? Which leads to...

       * The alignment of the type would be strange.  E.g. suppose
         we're dealing with M=2, and use uint32xY_t to represent a
         vector of Y uint32_ts.  The types and alignments would be:

           N=2 uint32x4_t, alignment 16
           N=3 uint32x6_t, alignment 8 (if we follow the convention for modes)
           N=4 uint32x8_t, alignment 32

         We don't need alignments greater than 8 in our intended use;
         16 and 32 are overkill.

       * We're not really using the type as a single vector,
         but as a collection of vectors.

       * The combination of the vector type and the __builtin_load_lanes
         array argument wouldn't be enough to determine the correct
         load operation.  __builtin_load_lanes would need something
         like a vector count argument (N in the above description) as well.

3. an array-of-vectors type

     Pros
       * No support for new GCC features (large integers or non-power-of-two
         vectors) is needed.

       * The alignment of the type would be taken from the alignment of the
         individual vectors, which is correct.

       * It accurately reflects how the loaded value is going to be used.

       * The type uniquely identifies the correct load operation,
         without need for additional arguments.  (This is minor.)

     Cons
       * Gimple registers can't store array values.

So I think the only disadvantage of using an array of vectors is that the
result can never be a gimple register.  But that isn't much of a disadvantage
really; the things we care about are the individual vectors, which can
of course be treated as gimple registers.  I think our tracking of memory
values is good enough for combined_vectors to be treated as such.

These arrays of vectors would still need to have a non-BLK mode,
so that they can be stored in _rtl_ registers.  But we need that anyway
for ARM's arm_neon.h; the code that today's GCC produces for the intrinsic
functions is very poor.

So how about the following functions?  (Forgive the pascally syntax.)

    __builtin_load_lanes (REF : array N*M of X)
      returns array N of vector M of X
      maps to vldN on ARM
      in practice, the result would be used in assignments of the form:
        vectorY = ARRAY_REF <result, Y>

    __builtin_store_lanes (VECTORS : array N of vector M of X)
      returns array N*M of X
      maps to vstN on ARM
      in practice, the argument would be populated by assignments of the form:
        ARRAY_REF <VECTORS, Y> = vectorY

    __builtin_load_lane (REF : array N of X,
			 VECTORS : array N of vector M of X,
			 LANE : integer)
      returns array N of vector M of X
      maps to vldN_lane on ARM

    __builtin_store_lane (VECTORS : array N of vector M of X,
			  LANE : integer)
      returns array N of X
      maps to vstN_lane on ARM

    __builtin_load_dup (REF : array N of X)
      returns array N of vector M of X
      maps to vldN_dup on ARM

I've hacked up a prototype of this and it seems to produce good code.
What do you think?

Richard