From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x133.google.com (mail-lf1-x133.google.com [IPv6:2a00:1450:4864:20::133]) by sourceware.org (Postfix) with ESMTPS id 9EA31395B07B for ; Wed, 16 Nov 2022 15:29:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9EA31395B07B 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-lf1-x133.google.com with SMTP id r12so30079549lfp.1 for ; Wed, 16 Nov 2022 07:29:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; 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=ijcomMWejmJxIus2LyNJkXS3Gc70QUztqc+IGkqnSYY=; b=DqMcoXddf4ckq7U+/DlOab/AOMa7aHiK61biZWfFgenw0yfkS0x++oVGLYari7dx29 fTqETixoeUOAOIhkv4e4L+u3+Wvtd8RbA6ET+EHQ3IslwMh6y2YtUS6OikHKNvnJw0GQ gpasXlpHMngOBFh292QTdw2BPHSANve8rYUUTNwbcjH3pOCn7iVw8PYJrBoalxxW+n4w CvVLzr9DdYhBuxsDoesM1qDIQg9niXk4DI3qNzR+975XkDTVFMj30VTTT3MtRqdmHViz AV7KX1QqgFo2gu6crhUKBZSxZg4M/nWC9aw0G9QDUmLzrU9rj7AhDp1yRZlbn4oJoRiC mRew== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; 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=ijcomMWejmJxIus2LyNJkXS3Gc70QUztqc+IGkqnSYY=; b=RTBw6kf6hbnkXU3PK7TbE0HwyvEMFJlrzXKM28+Yn9EsvO0xHMRe8lR5P2FCrZBc8j Ce7NlppTGIiFBGWgxzNXfH2urRPgKxRtmcnldr71ZPhWYYp3bS30psbQP/ps1x3ifkkE CycjKFrl3uap88TY0j8c05sXMPxzKq4RThDzqoNE9i3oT6I8dPrsyhMaqiqLZs4hCYL7 7ZXTjg+FCQYWiiZh7SXc9t064gmDlsfSDJdDnKSvYsExQdFtMad7Qaj5GLmrBkkc6BiE 0vYW+1xTK3I0KKlLDgGFg4/BftQhdfKbRB0QJ2qdGvaMPVWLzNoWqlnpcvc+Eae7R4LX olsw== X-Gm-Message-State: ANoB5pnjUsVqJZiZbhAgshduB7bGAULpBYjeuhkThAcc2WNxeetwA8f4 5UUrJ/7svAlAG4FDNLq96LRa3p+qhcXvPlI7WjQ= X-Google-Smtp-Source: AA0mqf6HUnVGDyUa+HiPFdhxqA8Y2yCXUyYw13gbZ2IbFw/KoTJuA6v/oaNgn/evmnzFXIPBq3hVfuLRGAiSIf9cRtA= X-Received: by 2002:a05:6512:3c89:b0:499:b4b3:2f68 with SMTP id h9-20020a0565123c8900b00499b4b32f68mr7215488lfv.203.1668612596079; Wed, 16 Nov 2022 07:29:56 -0800 (PST) MIME-Version: 1.0 References: <20221104000432.15254-1-hongyu.wang@intel.com> In-Reply-To: From: Richard Biener Date: Wed, 16 Nov 2022 16:29:43 +0100 Message-ID: Subject: Re: [PATCH] Optimize VEC_PERM_EXPR with same permutation index and operation [PR98167] To: Tamar Christina Cc: Hongyu Wang , Prathamesh Kulkarni , Richard Sandiford , Hongyu Wang , "hongtao.liu@intel.com" , "gcc-patches@gcc.gnu.org" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-5.5 required=5.0 tests=BAYES_00,BODY_8BITS,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham 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 Wed, Nov 16, 2022 at 4:25 PM Tamar Christina w= rote: > > Hi, > > This patch is causing several ICEs because it changes the permutes from a= single register > permute to a multi register due to the lowering of the expressions to dif= ferent SSA names. > > See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D107717 > > I have a prototype fix which adds a new rule to CSE this back to a single= register permute, > but would this be the right solution? It seems hard to later on during ex= pand realize that > the two operands are the same. > > It's probably also ok to just block this from happening after vec_lower, = however I'm worried that > If it wasn't CSE'd before vec_lower it'll lower it so something much less= efficient. You can use (vec_perm (op@7 @0 @1) @3) to avoid this issue. > Thanks, > Tamar > > > -----Original Message----- > > From: Gcc-patches > bounces+tamar.christina=3Darm.com@gcc.gnu.org> On Behalf Of Richard > > Biener via Gcc-patches > > Sent: Monday, November 14, 2022 2:53 PM > > To: Hongyu Wang > > Cc: Prathamesh Kulkarni ; Richard > > Sandiford ; Hongyu Wang > > ; hongtao.liu@intel.com; gcc- > > patches@gcc.gnu.org > > Subject: Re: [PATCH] Optimize VEC_PERM_EXPR with same permutation > > index and operation [PR98167] > > > > On Thu, Nov 10, 2022 at 3:27 PM Hongyu Wang > > wrote: > > > > > > > Well, with AVX512 v64qi that's 64*64 =3D=3D 4096 cases to check. I > > > > think a lambda function is fine to use. The alternative (used by > > > > the vectorizer in some places) is to use sth like > > > > > > > > auto_sbitmap seen (nelts); > > > > for (i =3D 0; i < nelts; i++) > > > > { > > > > if (!bitmap_set_bit (seen, i)) > > > > break; > > > > count++; > > > > } > > > > full_perm_p =3D count =3D=3D nelts; > > > > > > > > I'll note that you should still check .encoding > > > > ().encoded_full_vector_p () and only bother to check that case, tha= t's a > > very simple check. > > > > > > Thanks for the good example! We also tried using wide_int as a bitmas= k > > > but your code looks more simple and reasonable. > > > > > > Updated the patch accordingly. > > > > OK. > > > > Thanks, > > Richard. > > > > > Richard Biener =E4=BA=8E2022=E5=B9=B411= =E6=9C=8810=E6=97=A5=E5=91=A8=E5=9B=9B > > 16:56=E5=86=99=E9=81=93=EF=BC=9A > > > > > > > > > > > > > > On Thu, Nov 10, 2022 at 3:27 AM Hongyu Wang > > wrote: > > > > > > > > > > Hi Prathamesh and Richard, > > > > > > > > > > Thanks for the review and nice suggestions! > > > > > > > > > > > > I guess the transform should work as long as mask is same for > > > > > > > both vectors even if it's not constant ? > > > > > > > > > > > > Yes, please change accordingly (and maybe push separately). > > > > > > > > > > > > > > > > Removed VECTOR_CST for integer ops. > > > > > > > > > > > > If this transform is meant only for VLS vectors, I guess you > > > > > > > should bail out if TYPE_VECTOR_SUBPARTS is not constant, > > > > > > > otherwise it will crash for VLA vectors. > > > > > > > > > > > > I suppose it's difficult to create a VLA permute that covers al= l > > > > > > elements and that is not trivial though. But indeed add > > > > > > ().is_constant to the VECTOR_FLOAT_TYPE_P guard. > > > > > > > > > > Added. > > > > > > > > > > > Meh, that's quadratic! I suggest to check .encoding > > > > > > ().encoded_full_vector_p () (as said I can't think of a non-ful= l > > > > > > encoding that isn't trivial but covers all elements) and then > > > > > > simply .qsort () the vector_builder (it derives from vec<>) so > > > > > > the scan is O(n log n). > > > > > > > > > > The .qsort () approach requires an extra cmp_func that IMO would > > > > > not be feasible to be implemented in match.pd (I suppose lambda > > > > > function would not be a good idea either). > > > > > Another solution would be using hash_set but it does not work her= e > > > > > for int64_t or poly_int64 type. > > > > > So I kept current O(n^2) simple code here, and I suppose usually > > > > > the permutation indices would be a small number even for O(n^2) > > > > > complexity. > > > > > > > > Well, with AVX512 v64qi that's 64*64 =3D=3D 4096 cases to check. I > > > > think a lambda function is fine to use. The alternative (used by > > > > the vectorizer in some places) is to use sth like > > > > > > > > auto_sbitmap seen (nelts); > > > > for (i =3D 0; i < nelts; i++) > > > > { > > > > if (!bitmap_set_bit (seen, i)) > > > > break; > > > > count++; > > > > } > > > > full_perm_p =3D count =3D=3D nelts; > > > > > > > > I'll note that you should still check .encoding > > > > ().encoded_full_vector_p () and only bother to check that case, tha= t's a > > very simple check. > > > > > > > > > > > > > > Attached updated patch. > > > > > > > > > > Richard Biener via Gcc-patches > > > > > =E4=BA=8E2022=E5=B9=B411=E6=9C=888=E6=97=A5=E5=91=A8=E4=BA=8C 22:= 38=E5=86=99=E9=81=93=EF=BC=9A > > > > > > > > > > > > > > > > > > > > > > On Fri, Nov 4, 2022 at 7:44 AM Prathamesh Kulkarni via > > > > > > Gcc-patches wrote: > > > > > > > > > > > > > > On Fri, 4 Nov 2022 at 05:36, Hongyu Wang via Gcc-patches > > > > > > > wrote: > > > > > > > > > > > > > > > > Hi, > > > > > > > > > > > > > > > > This is a follow-up patch for PR98167 > > > > > > > > > > > > > > > > The sequence > > > > > > > > c1 =3D VEC_PERM_EXPR (a, a, mask) > > > > > > > > c2 =3D VEC_PERM_EXPR (b, b, mask) > > > > > > > > c3 =3D c1 op c2 > > > > > > > > can be optimized to > > > > > > > > c =3D a op b > > > > > > > > c3 =3D VEC_PERM_EXPR (c, c, mask) for all integer vect= or > > > > > > > > operation, and float operation with full permutation. > > > > > > > > > > > > > > > > Bootstrapped & regrtested on x86_64-pc-linux-gnu. > > > > > > > > > > > > > > > > Ok for trunk? > > > > > > > > > > > > > > > > gcc/ChangeLog: > > > > > > > > > > > > > > > > PR target/98167 > > > > > > > > * match.pd: New perm + vector op patterns for int a= nd fp > > vector. > > > > > > > > > > > > > > > > gcc/testsuite/ChangeLog: > > > > > > > > > > > > > > > > PR target/98167 > > > > > > > > * gcc.target/i386/pr98167.c: New test. > > > > > > > > --- > > > > > > > > gcc/match.pd | 49 +++++++++++++= ++++++++++++ > > > > > > > > gcc/testsuite/gcc.target/i386/pr98167.c | 44 > > > > > > > > ++++++++++++++++++++++ > > > > > > > > 2 files changed, 93 insertions(+) create mode 100644 > > > > > > > > gcc/testsuite/gcc.target/i386/pr98167.c > > > > > > > > > > > > > > > > diff --git a/gcc/match.pd b/gcc/match.pd index > > > > > > > > 194ba8f5188..b85ad34f609 100644 > > > > > > > > --- a/gcc/match.pd > > > > > > > > +++ b/gcc/match.pd > > > > > > > > @@ -8189,3 +8189,52 @@ and, > > > > > > > > (bit_and (negate @0) integer_onep@1) > > > > > > > > (if (!TYPE_OVERFLOW_SANITIZED (type)) > > > > > > > > (bit_and @0 @1))) > > > > > > > > + > > > > > > > > +/* Optimize > > > > > > > > + c1 =3D VEC_PERM_EXPR (a, a, mask) > > > > > > > > + c2 =3D VEC_PERM_EXPR (b, b, mask) > > > > > > > > + c3 =3D c1 op c2 > > > > > > > > + --> > > > > > > > > + c =3D a op b > > > > > > > > + c3 =3D VEC_PERM_EXPR (c, c, mask) > > > > > > > > + For all integer non-div operations. */ (for op (plus > > > > > > > > +minus mult bit_and bit_ior bit_xor > > > > > > > > + lshift rshift) > > > > > > > > + (simplify > > > > > > > > + (op (vec_perm @0 @0 VECTOR_CST@2) (vec_perm @1 @1 > > VECTOR_CST@2)) > > > > > > > > + (if (VECTOR_INTEGER_TYPE_P (type)) > > > > > > > > + (vec_perm (op @0 @1) (op @0 @1) @2)))) > > > > > > > Just wondering, why should mask be CST here ? > > > > > > > I guess the transform should work as long as mask is same for > > > > > > > both vectors even if it's not constant ? > > > > > > > > > > > > Yes, please change accordingly (and maybe push separately). > > > > > > > > > > > > > > + > > > > > > > > +/* Similar for float arithmetic when permutation constant = covers > > > > > > > > + all vector elements. */ (for op (plus minus mult) > > > > > > > > +(simplify > > > > > > > > + (op (vec_perm @0 @0 VECTOR_CST@2) (vec_perm @1 @1 > > VECTOR_CST@2)) > > > > > > > > + (if (VECTOR_FLOAT_TYPE_P (type)) > > > > > > > > + (with > > > > > > > > + { > > > > > > > > + tree perm_cst =3D @2; > > > > > > > > + vec_perm_builder builder; > > > > > > > > + bool full_perm_p =3D false; > > > > > > > > + if (tree_to_vec_perm_builder (&builder, perm_cst)) > > > > > > > > + { > > > > > > > > + /* Create a vec_perm_indices for the integer ve= ctor. */ > > > > > > > > + int nelts =3D TYPE_VECTOR_SUBPARTS > > > > > > > > +(type).to_constant (); > > > > > > > If this transform is meant only for VLS vectors, I guess you > > > > > > > should bail out if TYPE_VECTOR_SUBPARTS is not constant, > > > > > > > otherwise it will crash for VLA vectors. > > > > > > > > > > > > I suppose it's difficult to create a VLA permute that covers al= l > > > > > > elements and that is not trivial though. But indeed add > > > > > > ().is_constant to the VECTOR_FLOAT_TYPE_P guard. > > > > > > > > > > > > > > > > > > > > Thanks, > > > > > > > Prathamesh > > > > > > > > + vec_perm_indices sel (builder, 1, nelts); > > > > > > > > + > > > > > > > > + /* Check if perm indices covers all vector elem= ents. */ > > > > > > > > + int count =3D 0, i, j; > > > > > > > > + for (i =3D 0; i < nelts; i++) > > > > > > > > + for (j =3D 0; j < nelts; j++) > > > > > > > > > > > > Meh, that's quadratic! I suggest to check .encoding > > > > > > ().encoded_full_vector_p () (as said I can't think of a non-ful= l > > > > > > encoding that isn't trivial but covers all elements) and then > > > > > > simply .qsort () the vector_builder (it derives from vec<>) so > > > > > > the scan is O(n log n). > > > > > > > > > > > > Maybe Richard has a better idea here though. > > > > > > > > > > > > Otherwise looks OK, though with these kind of (* (op ..) (op > > > > > > ..)) patterns it's always that they explode the match decision > > > > > > tree, we'd ideally have a way to match those with (op ..) (op > > > > > > ..) first to be able to share more of the matching code. That > > > > > > said, match.pd is a less than ideal place for these (but mostly > > > > > > because of the way we code generate *-match.cc) > > > > > > > > > > > > Richard. > > > > > > > > > > > > > > + { > > > > > > > > + if (sel[j].to_constant () =3D=3D i) > > > > > > > > + { > > > > > > > > + count++; > > > > > > > > + break; > > > > > > > > + } > > > > > > > > + } > > > > > > > > + full_perm_p =3D count =3D=3D nelts; > > > > > > > > + } > > > > > > > > + } > > > > > > > > + (if (full_perm_p) > > > > > > > > + (vec_perm (op @0 @1) (op @0 @1) @2)))))) > > > > > > > > diff --git a/gcc/testsuite/gcc.target/i386/pr98167.c > > > > > > > > b/gcc/testsuite/gcc.target/i386/pr98167.c > > > > > > > > new file mode 100644 > > > > > > > > index 00000000000..40e0ac11332 > > > > > > > > --- /dev/null > > > > > > > > +++ b/gcc/testsuite/gcc.target/i386/pr98167.c > > > > > > > > @@ -0,0 +1,44 @@ > > > > > > > > +/* PR target/98167 */ > > > > > > > > +/* { dg-do compile } */ > > > > > > > > +/* { dg-options "-O2 -mavx2" } */ > > > > > > > > + > > > > > > > > +/* { dg-final { scan-assembler-times "vpshufd\t" 8 } } */ > > > > > > > > +/* { dg-final { scan-assembler-times "vpermilps\t" 3 } } *= / > > > > > > > > + > > > > > > > > +#define VEC_PERM_4 \ > > > > > > > > + 2, 3, 1, 0 > > > > > > > > +#define VEC_PERM_8 \ > > > > > > > > + 4, 5, 6, 7, 3, 2, 1, 0 > > > > > > > > +#define VEC_PERM_16 \ > > > > > > > > + 8, 9, 10, 11, 12, 13, 14, 15, 7, 6, 5, 4, 3, 2, 1, 0 > > > > > > > > + > > > > > > > > +#define TYPE_PERM_OP(type, size, op, name) \ > > > > > > > > + typedef type v##size##s##type __attribute__ > > > > > > > > +((vector_size(4*size))); \ > > > > > > > > + v##size##s##type type##foo##size##i_##name > > (v##size##s##type a, \ > > > > > > > > + > > > > > > > > +v##size##s##type b) \ > > > > > > > > + { \ > > > > > > > > + v##size##s##type a1 =3D __builtin_shufflevector (a, a,= \ > > > > > > > > + VEC_PERM= _##size); \ > > > > > > > > + v##size##s##type b1 =3D __builtin_shufflevector (b, b,= \ > > > > > > > > + VEC_PERM= _##size); \ > > > > > > > > + return a1 op b1; \ > > > > > > > > + } > > > > > > > > + > > > > > > > > +#define INT_PERMS(op, name) \ > > > > > > > > + TYPE_PERM_OP (int, 4, op, name) \ > > > > > > > > + > > > > > > > > +#define FP_PERMS(op, name) \ > > > > > > > > + TYPE_PERM_OP (float, 4, op, name) \ > > > > > > > > + > > > > > > > > +INT_PERMS (+, add) > > > > > > > > +INT_PERMS (-, sub) > > > > > > > > +INT_PERMS (*, mul) > > > > > > > > +INT_PERMS (|, ior) > > > > > > > > +INT_PERMS (^, xor) > > > > > > > > +INT_PERMS (&, and) > > > > > > > > +INT_PERMS (<<, shl) > > > > > > > > +INT_PERMS (>>, shr) > > > > > > > > +FP_PERMS (+, add) > > > > > > > > +FP_PERMS (-, sub) > > > > > > > > +FP_PERMS (*, mul) > > > > > > > > + > > > > > > > > -- > > > > > > > > 2.18.1 > > > > > > > >