From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x22f.google.com (mail-lj1-x22f.google.com [IPv6:2a00:1450:4864:20::22f]) by sourceware.org (Postfix) with ESMTPS id 270323858D33 for ; Tue, 27 Jun 2023 07:28:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 270323858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lj1-x22f.google.com with SMTP id 38308e7fff4ca-2b6adef5c22so6016521fa.3 for ; Tue, 27 Jun 2023 00:28:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1687850927; x=1690442927; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=WlgrO6S8ND3ZL41VcvwWerJxaetdJFdstolIRQyL+bE=; b=Og0ikT7ApZDCbDhLt9Mv1AUEGDSHDu60aC2UqcTRzlljnCnYGBEj7wkE8y66++9jIJ lABX34bGfMrPQl4UlJ+/8c3g4BXdJ3nrIElwUDknx5ls8ViEsSku+1qyZksRSu/JzLQB SjUpTqFNJdZjLkaXXq+4M4KeyonSXQQDHvd/2CoHhTKsVWLKo4SWha9bzf90EjMOLa7J QFoj8WXuxIO0PewjCR6iACUSBez0F9upbV2cSjaAHEXg+REZ2pexaXRNbPfe72Qj+Ct4 tlcs+5GmfIGZgrO7Wc9uayJh89qm43/68RdzHMRnYq1b4B/IzppOHT+Rl3+E6ha6bgPa 7sfw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687850927; x=1690442927; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=WlgrO6S8ND3ZL41VcvwWerJxaetdJFdstolIRQyL+bE=; b=hCU5WFQItQHVQF+WeyxIYPW2vkrM1pn1jWHTwywKNEFGkJ9kMgEpd2SjMHzZTI9hXc pOtl2YVWwe1TitlIN0JGPe0l8PxvEXNmvpejH84vW76F6EOIWbEBQPDFmqw4sSWkC15c gMT7GEk7cutEu4FHezEV7v4nFF0wu/qbiplZ2GmZYUz/KYmXybYv2roYRGdEH2IIlfWq aHKDjG36+DhFQNE71yysInwKJjDid7cqRh78WCpWUTVw+nB8hGOHkansFff05h2TSy/3 lTvV88YaF6KJNSRvbhJmHFVneFE2NxgoH1dj7Rrthz9IW1lJhsa50RS6WcGsTcBexeng IHAA== X-Gm-Message-State: AC+VfDxXllRd7BClp1h1YvoPl4wZ8tLmOfdDYQSfXTpHnFbER9l0oIEi nFF71jF1wGzrpZaYvPqfq02MQ+olvrtz8tDhl5ZLoS8C X-Google-Smtp-Source: ACHHUZ4fVi99Tu/r/UayHlK0Ue2Ovx5YzNgtXMLuDzcpNu9+w1lFc4zUTrSDlOGPNNAvGPQjtGSzpmG85BRTenvQ+Vs= X-Received: by 2002:a2e:8009:0:b0:2b5:a710:a688 with SMTP id j9-20020a2e8009000000b002b5a710a688mr5654119ljg.25.1687850927097; Tue, 27 Jun 2023 00:28:47 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Tue, 27 Jun 2023 09:28:35 +0200 Message-ID: Subject: Re: [RFC] GNU Vector Extension -- Packed Boolean Vectors To: Tejas Belagod Cc: "gcc-patches@gcc.gnu.org" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,KAM_LINEPADDING,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Tue, Jun 27, 2023 at 8:30=E2=80=AFAM Tejas Belagod wrote: > > > > > > From: Richard Biener > Date: Monday, June 26, 2023 at 2:23 PM > To: Tejas Belagod > Cc: gcc-patches@gcc.gnu.org > Subject: Re: [RFC] GNU Vector Extension -- Packed Boolean Vectors > > On Mon, Jun 26, 2023 at 8:24=E2=80=AFAM Tejas Belagod via Gcc-patches > wrote: > > > > Hi, > > > > Packed Boolean Vectors > > ---------------------- > > > > I'd like to propose a feature addition to GNU Vector extensions to add = packed > > boolean vectors (PBV). This has been discussed in the past here[1] and= a variant has > > been implemented in Clang recently[2]. > > > > With predication features being added to vector architectures (SVE, MVE= , AVX), > > it is a useful feature to have to model predication on targets. This c= ould > > find its use in intrinsics or just used as is as a GNU vector extension= being > > mapped to underlying target features. For example, the packed boolean = vector > > could directly map to a predicate register on SVE. > > > > Also, this new packed boolean type GNU extension can be used with SVE A= CLE > > intrinsics to replace a fixed-length svbool_t. > > > > Here are a few options to represent the packed boolean vector type. > > The GIMPLE frontend uses a new 'vector_mask' attribute: > > typedef int v8si __attribute__((vector_size(8*sizeof(int)))); > typedef v8si v8sib __attribute__((vector_mask)); > > it get's you a vector type that's the appropriate (dependent on the > target) vector > mask type for the vector data type (v8si in this case). > > > > Thanks Richard. > > Having had a quick look at the implementation, it does seem to tick the b= oxes. > > I must admit I haven't dug deep, but if the target hook allows the mask t= o be > > defined in way that is target-friendly (and I don't know how much effort = it will > > be to migrate the attribute to more front-ends), it should do the job nic= ely. > > Let me go back and dig a bit deeper and get back with questions if any. Let me add that the advantage of this is the compiler doesn't need to support weird explicitely laid out packed boolean vectors that do not match what the target supports and the user doesn't need to know what the target supports (and thus have an #ifdef maze around explicitely specified layouts). It does remove some flexibility though, for example with -mavx512f -mavx512= vl you'll get AVX512 style masks for V4SImode data vectors but of course the target sill supports SSE2/AVX2 style masks as well, but those would not be available as "packed boolean vectors", though they are of course in fact equal to V4SImode data vectors with -1 or 0 values, so in this particular case it might not matter. That said, the vector_mask attribute will get you V4SImode vectors with signed boolean elements of 32 bits for V4SImode data vectors with SSE2/AVX2. Richard. > > > Thanks, > > Tejas. > > > > > > > > > 1. __attribute__((vector_size (n))) where n represents bytes > > > > typedef bool vbool __attribute__ ((vector_size (1))); > > > > In this approach, the shape of the boolean vector is unclear. IoW, it i= s not > > clear if each bit in 'n' controls a byte or an element. On targets > > like SVE, it would be natural to have each bit control a byte of the ta= rget > > vector (therefore resulting in an 'unpacked' layout of the PBV) and on = AVX, each > > bit would control one element/lane on the target vector(therefore resul= ting in a > > 'packed' layout with all significant bits at the LSB). > > > > 2. __attribute__((vector_size (n))) where n represents num of lanes > > > > typedef int v4si __attribute__ ((vector_size (4 * sizeof (int))); > > typedef bool v4bi __attribute__ ((vector_size (sizeof v4si / sizeof (= v4si){0}[0]))); > > > > Here the 'n' in the vector_size attribute represents the number of bits= that > > is needed to represent a vector quantity. In this case, this packed bo= olean > > vector can represent upto 'n' vector lanes. The size of the type is > > rounded up the nearest byte. For example, the sizeof v4bi in the above > > example is 1. > > > > In this approach, because of the nature of the representation, the n bi= ts required > > to represent the n lanes of the vector are packed at the LSB. This does= not naturally > > align with the SVE approach of each bit representing a byte of the targ= et vector > > and PBV therefore having an 'unpacked' layout. > > > > More importantly, another drawback here is that the change in units for= vector_size > > might be confusing to programmers. The units will have to be interpret= ed based on the > > base type of the typedef. It does not offer any flexibility in terms of= the layout of > > the bool vector - it is fixed. > > > > 3. Combination of 1 and 2. > > > > Combining the best of 1 and 2, we can introduce extra parameters to vec= tor_size that will > > unambiguously represent the layout of the PBV. Consider > > > > typedef bool vbool __attribute__((vector_size (s, n[, w]))); > > > > where 's' is size in bytes, 'n' is the number of lanes and an optional = 3rd parameter 'w' > > is the number of bits of the PBV that represents a lane of the target v= ector. 'w' would > > allow a target to force a certain layout of the PBV. > > > > The 2-parameter form of vector_size allows the target to have an > > implementation-defined layout of the PBV. The target is free to choose = the 'w' > > if it is not specified to mirror the target layout of predicate registe= rs. For > > eg. AVX would choose 'w' as 1 and SVE would choose s*8/n. > > > > As an example, to represent the result of a comparison on 2 int16x8_t, = we'd need > > 8 lanes of boolean which could be represented by > > > > typedef bool v8b __attribute__ ((vector_size (2, 8))); > > > > SVE would implement v8b layout to make every 2nd bit significant i.e. w= =3D=3D 2 > > > > and AVX would choose a layout where all 8 consecutive bits packed at LS= B would > > be significant i.e. w =3D=3D 1. > > > > This scheme would accomodate more than 1 target to effectively represen= t vector > > bools that mirror the target properties. > > > > 4. A new attribite > > > > This is based on a suggestion from Richard S in [3]. The idea is to int= roduce a new > > attribute to define the PBV and make it general enough to > > > > * represent all targets flexibly (SVE, AVX etc) > > * represent sub-byte length predicates > > * have no change in units of vector_size/no new vector_size signature > > * not have the number of bytes constrain representation > > > > If we call the new attribute 'bool_vec' (for lack of a better name), co= nsider > > > > typedef bool vbool __attribute__((bool_vec (n[, w]))) > > > > where 'n' represents number of lanes/elements and the optional 'w' is b= its-per-lane. > > > > If 'w' is not specified, it and bytes-per-predicate are implementation-= defined based on target. > > If 'w' is specified, sizeof (vbool) will be ceil (n*w/8). > > > > 5. Behaviour of the packed vector boolean type. > > > > Taking the example of one of the options above, following is an illustr= ation of it's behavior > > > > * ABI > > > > New ABI rules will need to be defined for this type - eg alignment, P= CS, > > mangling etc > > > > * Initialization: > > > > Packed Boolean Vectors(PBV) can be initialized like so: > > > > typedef bool v4bi __attribute__ ((vector_size (2, 4, 4))); > > v4bi p =3D {false, true, false, false}; > > > > Each value in the initizlizer constant is of type bool. The lowest nu= mbered > > element in the const array corresponds to the LSbit of p, element 1 i= s > > assigned to bit 4 etc. > > > > p is effectively a 2-byte bitmask with value 0x0010 > > > > With a different layout > > > > typedef bool v4bi __attribute__ ((vector_size (2, 4, 1))); > > v4bi p =3D {false, true, false, false}; > > > > p is effectively a 2-byte bitmask with value 0x0002 > > > > * Operations: > > > > Packed Boolean Vectors support the following operations: > > . unary ~ > > . unary ! > > . binary&,|and=CB=86 > > . assignments &=3D, |=3D and =CB=86=3D > > . comparisons <, <=3D, =3D=3D, !=3D, >=3D and > > > . Ternary operator ?: > > > > Operations are defined as applied to the individual elements i.e the = bits > > that are significant in the PBV. Whether the PBVs are treated as bitm= asks > > or otherwise is implementation-defined. > > > > Insignificant bits could affect results of comparisons or ternary ope= rators. > > In such cases, it is implementation defined how the unused bits are t= reated. > > > > . Subscript operator [] > > > > For the subscript operator, the packed boolean vector acts like a arr= ay of > > elements - the first or the 0th indexed element being the LSbit of th= e PBV. > > Subscript operator yields a scalar boolean value. > > For example: > > > > typedef bool v8b __attribute__ ((vector_size (2, 8, 2))); > > > > // Subscript operator result yields a boolean value. > > // x[3] is the 7th LSbit and x[1] is the 3rd LSbit of x. > > bool foo (v8b p, int n) { p[3] =3D true; return p[1]; } > > > > Out of bounds access: OOB access can be determined at compile time gi= ven the > > strong typing of the PBVs. > > > > PBV does not support address of operator(&) for elements of PBVs. > > > > . Implicit conversion from integer vectors to PBVs > > > > We would like to support the output of comparison operations to be PB= Vs. This > > requires us to define the implicit conversion from an integer vector = to PBV > > as the result of vector comparisons are integer vectors. > > > > To define this operation: > > > > bool_vector =3D vector vector > > > > There is no change in how vector vector behavior i.e. this co= mparison > > would still produce an int_vector type as it does now. > > > > temp_int_vec =3D vector vector > > bool_vec =3D temp_int_vec // Implicit conversion from int_vec to bo= ol_vec > > > > The implicit conversion from int_vec to bool I'd define simply to be: > > > > bool_vec[n] =3D (_Bool) int_vec[n] > > > > where the C11 standard rules apply > > 6.3.1.2 Boolean type When any scalar value is converted to _Bool, th= e result > > is 0 if the value compares equal to 0; otherwise, the result is 1. > > > > > > [1] https://lists.llvm.org/pipermail/cfe-dev/2020-May/065434.html > > [2] https://reviews.llvm.org/D88905 > > [3] https://reviews.llvm.org/D81083 > > > > Thoughts? > > > > Thanks, > > Tejas.