From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yw1-x1133.google.com (mail-yw1-x1133.google.com [IPv6:2607:f8b0:4864:20::1133]) by sourceware.org (Postfix) with ESMTPS id DAD1C3858CDB for ; Wed, 18 Oct 2023 08:35:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DAD1C3858CDB Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org DAD1C3858CDB Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::1133 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697618120; cv=none; b=PpNIHAfANF9H6PYvAXosumYrYRWtJNul0JjKhPZZkEeiixxT3JyB45TSXv050cqzdnvBnZfNhstg6Q+6JYLKNdvQAe4aeWJpVIQHYC/ZoLxxNYU4B5VrJFkK5Hsb93n0TqFag2adRWTUibMERGHiE/ceTcUzyuYERJGbof1gg2U= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697618120; c=relaxed/simple; bh=LgykSLOGl7On6b6hQAO0wCIVwMisRzlOBiNztNw2IrA=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=Hm8znvpPHTghQLAsk6S83SxTUs6+YZrKIUGwbHFnMktc4TlVhyH836o+vL/O4S74qKDBu12IKtgRB6VDzK5TsGkk5Q71dLWBtVtZODHuJJ2prWCsiRx+0wZc36xaH/Mnbq6nzahXOIxeDwUbsQZTmmVmcFwHHUw1S8qTODy/8FU= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-yw1-x1133.google.com with SMTP id 00721157ae682-5a81ab75f21so64296877b3.2 for ; Wed, 18 Oct 2023 01:35:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1697618117; x=1698222917; darn=gcc.gnu.org; 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=JqxR+m03ZkIOfk7wKCwPltQIW/+k+BM6u+Fn0tCiJcQ=; b=Yabp8aHS1f/IgupFil7vHX1QGXvaKpg54x+p64ZCJ29O1x8VqdJKDy3PnMiK9QIBew a8634MmfwukZL14AeE9bqtAtcQbdugIfA2Yxh9kVIF89qOsX2Pt4AxKf3wx1YgbXJa3Z n8UfUkw2RPZvq45ZTNhFcMNA9WcoxNXJA+7vYAJ9OkVD5FEe5F393l8CC1TjVPppsb38 BU7MAIUDaRivGXF+oHc//PSyQK3Dzc7uYj3Sr9AF6nZjeO9XzHcYYzu0h916jyKIY/qD mfQR/mZVx5g9S+UA1RN33ERPZIO4YSUZjE0izjN3rPyZUBlruxYyjePEW313yMTUjFUR 78ag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697618117; x=1698222917; 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=JqxR+m03ZkIOfk7wKCwPltQIW/+k+BM6u+Fn0tCiJcQ=; b=CyBCtsWbe89ZQJ/JrABRqX1tFvprxY6x3f/ee1JrI0zxF3ZtZQkdV4Y7GK2xgPDj6e g/bYp1E7dXapYfTAuz+EeE2BsRER8vNcyqZ7gNebAAzQZa8E6nFSLdonAY5pTikYemCh K614GREy55WDPtWGgyHWdtvb3t1Naqk/61z1Solm2ib52MHXI7lxmOK7tuNB+w/vRRf9 gjxrGN3X+/nbhE1pu7MNR6LZxjhK/YjsvOWcVp5ZYXQyskQftnv9RQVXIYcqdva+DXXx l/nYwZ0ueOu17HuVgZSCWxUs16hgTiIY4IV1IYuKFTUxRMjurUEs7JjPmWa5KAirpV3O kGIA== X-Gm-Message-State: AOJu0YzZvml95TbuA3g6jiKluKGp0rrF1HwX96ihsNcYBPQfHHhJRBf5 zGBMVGAB8e5zvEQo49VO7i2UzYg2/M+q/yKcy6g= X-Google-Smtp-Source: AGHT+IGUTyY29a6f6cTa6xhfpKEC9Bgx40tVTIkiFa3l+amuJ1eSWmJXYCMPx+C+E2JrB5I5p/sXC0JdadrJBfSwoao= X-Received: by 2002:a81:a0d5:0:b0:59b:d3cd:ffb6 with SMTP id x204-20020a81a0d5000000b0059bd3cdffb6mr4507259ywg.33.1697618117193; Wed, 18 Oct 2023 01:35:17 -0700 (PDT) MIME-Version: 1.0 References: <20231018083259.2386650-1-hongtao.liu@intel.com> In-Reply-To: <20231018083259.2386650-1-hongtao.liu@intel.com> From: Hongtao Liu Date: Wed, 18 Oct 2023 16:43:34 +0800 Message-ID: Subject: Re: [PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big. 65; 6800; 1c There's loop in vect_peel_nonlinear_iv_init to get init_expr * pow (step_expr, skip_niters). When skipn_iters is too big, compile time hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is pow of 2, otherwise give up vectorization when skip_niters >= TYPE_PRECISION (TREE_TYPE (init_expr)). To: liuhongt Cc: gcc-patches@gcc.gnu.org, rguenther@suse.de Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_HUGESUBJECT,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, Oct 18, 2023 at 4:33=E2=80=AFPM liuhongt wr= ote: > Cut from subject... There's a loop in vect_peel_nonlinear_iv_init to get init_expr * pow (step_expr, skip_niters). When skipn_iters is too big, compile time hogs. To avoid that, optimize init_expr * pow (step_expr, skip_niters) to init_expr << (exact_log2 (step_expr) * skip_niters) when step_expr is pow of 2, otherwise give up vectorization when skip_niters >=3D TYPE_PRECISION (TREE_TYPE (init_expr)). > Also give up vectorization when niters_skip is negative which will be > used for fully masked loop. > > Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}. > Ok for trunk? > > gcc/ChangeLog: > > PR tree-optimization/111820 > PR tree-optimization/111833 > * tree-vect-loop-manip.cc (vect_can_peel_nonlinear_iv_p): Give > up vectorization for nonlinear iv vect_step_op_mul when > step_expr is not exact_log2 and niters is greater than > TYPE_PRECISION (TREE_TYPE (step_expr)). Also don't vectorize > for nagative niters_skip which will be used by fully masked > loop. > (vect_can_advance_ivs_p): Pass whole phi_info to > vect_can_peel_nonlinear_iv_p. > * tree-vect-loop.cc (vect_peel_nonlinear_iv_init): Optimize > init_expr * pow (step_expr, skipn) to init_expr > << (log2 (step_expr) * skipn) when step_expr is exact_log2. > > gcc/testsuite/ChangeLog: > > * gcc.target/i386/pr111820-1.c: New test. > * gcc.target/i386/pr111820-2.c: New test. > * gcc.target/i386/pr103144-mul-1.c: Adjust testcase. > --- > .../gcc.target/i386/pr103144-mul-1.c | 6 ++-- > gcc/testsuite/gcc.target/i386/pr111820-1.c | 16 ++++++++++ > gcc/testsuite/gcc.target/i386/pr111820-2.c | 17 ++++++++++ > gcc/tree-vect-loop-manip.cc | 28 ++++++++++++++-- > gcc/tree-vect-loop.cc | 32 ++++++++++++++++--- > 5 files changed, 88 insertions(+), 11 deletions(-) > create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c > create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c > > diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsui= te/gcc.target/i386/pr103144-mul-1.c > index 640c34fd959..f80d1094097 100644 > --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c > +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c > @@ -23,7 +23,7 @@ foo_mul_const (int* a) > for (int i =3D 0; i !=3D N; i++) > { > a[i] =3D b; > - b *=3D 3; > + b *=3D 4; > } > } > > @@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b) > for (int i =3D 0; i !=3D 39; i++) > { > a[i] =3D b; > - b *=3D 3; > + b *=3D 4; > } > } > > @@ -46,6 +46,6 @@ foo_mul_peel_const (int* a) > for (int i =3D 0; i !=3D 39; i++) > { > a[i] =3D b; > - b *=3D 3; > + b *=3D 4; > } > } > diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/g= cc.target/i386/pr111820-1.c > new file mode 100644 > index 00000000000..50e960c39d4 > --- /dev/null > +++ b/gcc/testsuite/gcc.target/i386/pr111820-1.c > @@ -0,0 +1,16 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -Wno-aggressive-loop-optimizat= ions -fdump-tree-vect-details" } */ > +/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonl= inear_iv_init for nonlinear induction vec_step_op_mul when iteration count = is too big" "vect" } } */ > + > +int r; > +int r_0; > + > +void f1 (void) > +{ > + int n =3D 0; > + while (-- n) > + { > + r_0 +=3D r; > + r *=3D 3; > + } > +} > diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/g= cc.target/i386/pr111820-2.c > new file mode 100644 > index 00000000000..bbdb40798c6 > --- /dev/null > +++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c > @@ -0,0 +1,17 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -mavx2 -fno-tree-vrp -fdump-tree-vect-details -Wno-= aggressive-loop-optimizations" } */ > +/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */ > + > +int r; > +int r_0; > + > +void f (void) > +{ > + int n =3D 0; > + while (-- n) > + { > + r_0 +=3D r ; > + r *=3D 2; > + } > +} > + > diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc > index 2608c286e5d..a530088b61d 100644 > --- a/gcc/tree-vect-loop-manip.cc > +++ b/gcc/tree-vect-loop-manip.cc > @@ -1783,8 +1783,10 @@ iv_phi_p (stmt_vec_info stmt_info) > /* Return true if vectorizer can peel for nonlinear iv. */ > static bool > vect_can_peel_nonlinear_iv_p (loop_vec_info loop_vinfo, > - enum vect_induction_op_type induction_type) > + stmt_vec_info stmt_info) > { > + enum vect_induction_op_type induction_type > + =3D STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (stmt_info); > tree niters_skip; > /* Init_expr will be update by vect_update_ivs_after_vectorizer, > if niters or vf is unkown: > @@ -1805,11 +1807,31 @@ vect_can_peel_nonlinear_iv_p (loop_vec_info loop_= vinfo, > return false; > } > > + /* Avoid compile time hog on vect_peel_nonlinear_iv_init. */ > + if (induction_type =3D=3D vect_step_op_mul) > + { > + tree step_expr =3D STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info); > + tree type =3D TREE_TYPE (step_expr); > + > + if (wi::exact_log2 (wi::to_wide (step_expr)) =3D=3D -1 > + && LOOP_VINFO_INT_NITERS(loop_vinfo) >=3D TYPE_PRECISION (type)= ) > + { > + if (dump_enabled_p ()) > + dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, > + "Avoid compile time hog on" > + " vect_peel_nonlinear_iv_init" > + " for nonlinear induction vec_step_op_mul" > + " when iteration count is too big.\n"); > + return false; > + } > + } > + > /* Also doens't support peel for neg when niter is variable. > ??? generate something like niter_expr & 1 ? init_expr : -init_expr= ? */ > niters_skip =3D LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo); > if ((niters_skip !=3D NULL_TREE > - && TREE_CODE (niters_skip) !=3D INTEGER_CST) > + && (TREE_CODE (niters_skip) !=3D INTEGER_CST > + || (HOST_WIDE_INT) TREE_INT_CST_LOW (niters_skip) < 0)) > || (!vect_use_loop_mask_for_alignment_p (loop_vinfo) > && LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) < 0)) > { > @@ -1870,7 +1892,7 @@ vect_can_advance_ivs_p (loop_vec_info loop_vinfo) > induction_type =3D STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info); > if (induction_type !=3D vect_step_op_add) > { > - if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, induction_type)) > + if (!vect_can_peel_nonlinear_iv_p (loop_vinfo, phi_info)) > return false; > > continue; > diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc > index 89bdcaa0910..6bb1f3dc462 100644 > --- a/gcc/tree-vect-loop.cc > +++ b/gcc/tree-vect-loop.cc > @@ -9134,11 +9134,33 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, t= ree init_expr, > init_expr =3D gimple_convert (stmts, utype, init_expr); > unsigned skipn =3D TREE_INT_CST_LOW (skip_niters); > wide_int begin =3D wi::to_wide (step_expr); > - for (unsigned i =3D 0; i !=3D skipn - 1; i++) > - begin =3D wi::mul (begin, wi::to_wide (step_expr)); > - tree mult_expr =3D wide_int_to_tree (utype, begin); > - init_expr =3D gimple_build (stmts, MULT_EXPR, utype, init_expr, m= ult_expr); > - init_expr =3D gimple_convert (stmts, type, init_expr); > + int pow2_step =3D wi::exact_log2 (begin); > + /* Optimize init_expr * pow (step_expr, skipn) to > + init_expr << (log2 (step_expr) * skipn). */ > + if (pow2_step !=3D -1) > + { > + if (skipn >=3D TYPE_PRECISION (type) > + || skipn > (UINT_MAX / (unsigned) pow2_step) > + || skipn * (unsigned) pow2_step >=3D TYPE_PRECISION (type= )) > + init_expr =3D build_zero_cst (type); > + else > + { > + tree lshc =3D build_int_cst (utype, skipn * (unsigned) po= w2_step); > + init_expr =3D gimple_build (stmts, LSHIFT_EXPR, utype, > + init_expr, lshc); > + } > + } > + /* Any better way for init_expr * pow (step_expr, skipn)???. */ > + else > + { > + gcc_assert (skipn < TYPE_PRECISION (type)); > + for (unsigned i =3D 0; i !=3D skipn - 1; i++) > + begin =3D wi::mul (begin, wi::to_wide (step_expr)); > + tree mult_expr =3D wide_int_to_tree (utype, begin); > + init_expr =3D gimple_build (stmts, MULT_EXPR, utype, > + init_expr, mult_expr); > + } > + init_expr =3D gimple_convert (stmts, type, init_expr); > } > break; > > -- > 2.31.1 > --=20 BR, Hongtao