From patchwork Fri Oct 20 02:18:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: liuhongt X-Patchwork-Id: 155761 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:612c:2010:b0:403:3b70:6f57 with SMTP id fe16csp778229vqb; Thu, 19 Oct 2023 19:21:29 -0700 (PDT) X-Google-Smtp-Source: AGHT+IE8VferM6sD8XDvrjwMMsm4YhqI/Z+gITSg4c/Ev6RT+3EyhF1O9iZhOk8G7oRnxto61tew X-Received: by 2002:a05:620a:172a:b0:775:9c22:e901 with SMTP id az42-20020a05620a172a00b007759c22e901mr609215qkb.15.1697768488865; Thu, 19 Oct 2023 19:21:28 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1697768488; cv=pass; d=google.com; s=arc-20160816; b=R5Ad0SLPtowQFSzGgcIYsRjgw3kYjgQwJesNVaddc+NE/WRZLVnECltskspU1wagY4 ueuodYCnck52eLxVRi4bilvMJKb4uOSEAiXdBpJ3jFLU9Hjney9wyFb435TinFwq1G1v ErkpglSvODOLbNkFBkuU0wTXlVfd8FC59cnu+6T+B0a3aMxGUDdl+x2CISPx1UvbzRzh 25S07Q9b9xgS+5XRVj1jmyYuDxI3pnZGNo65UfXImmj70kPBsRS7F+DSI13D5XJoMoD6 uRQEfhQs0EQcz7qFdQuCcXSeZG7/PsAAdqUETW1bV6wqamYrjLafIk834uJGfYyxIDAC tnEw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:references:in-reply-to:message-id:date:subject:cc:to :from:dkim-signature:arc-filter:dmarc-filter:delivered-to; bh=ILiTAzfgoMEXU0Vn1tMShxSXdD9VwNV2saI+EJEG48I=; fh=ChXOctppJn0KECDRINafwUY5xHRufGHaa0Ju9pddrcQ=; b=E86Si5b42yBGLTFGGi6ujZti/EbrJtbR2ogE5ixjHjOJ2y6wzLwRM9a9FdqdRb5P3i R8NnUJMU2A/eqkWAQ1WYzOd4nP/RLEL503t9bcBERFpjz214oIPs+AL7bOKwQdJryQ6x uz4hxRnuD1BvUt1wUk/tqSIB6EWjnjzLtKDQLXC5lNQRsN/KLm9/vMAOB1mauYns6gQN oochGoXBa9TZonuqBEfsBUJVhqqOfc2aAItn+ICijvziwYQ77O2yC/I3HKHuQuKsuZy2 NzKTbd1QmmJX5hCTH0x6GvWaL6v0D+1wyqRXB3sOsQIbOVk4DvPaf63HgUUA6GOZuXna FNJQ== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@intel.com header.s=Intel header.b=JifyeADD; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: from server2.sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id z14-20020a05620a100e00b00775a4a305f2si552770qkj.592.2023.10.19.19.21.28 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 19 Oct 2023 19:21:28 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@intel.com header.s=Intel header.b=JifyeADD; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9EF483858426 for ; Fri, 20 Oct 2023 02:21:28 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mgamail.intel.com (mgamail.intel.com [134.134.136.24]) by sourceware.org (Postfix) with ESMTPS id B46213858D33 for ; Fri, 20 Oct 2023 02:20:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B46213858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=intel.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=intel.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org B46213858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=134.134.136.24 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697768462; cv=none; b=l/nKJ+QaWddg6k3k+iGi1f5qQhxqbqCnJ1dQB/fdh2EGm5nSFbBjAkyJ4HJjD7rOb0EvINIGmTMdpUvGxzsuAa/WYg+6b6+1/XmRoB9qwz1iilwYwdk+su3oVqtDoPeu8sm0wMxpAYAk5E/j5h7lVTCHCqvp3EOW+ysGzhSwJs8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697768462; c=relaxed/simple; bh=OlnzujDmkfOFiW/0yXXSLEyX/fIdQi16Ppbnxanb/vY=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=EKkB2UMF10ySGlh+yMVTB9hIiFNREcgC8C2adwrzKy2WLavnK/zqPUkh+S2kAnwCcT3bdt4tanv40Mck1AK1vnGtILLcOA7isZoR+/7eo80sZd6+ZYv9BuRPqp/9UzXWqp+Fg5vUR21Lih1DflYL5EhLh8XqKu7BA4aXy4COW+c= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1697768459; x=1729304459; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=OlnzujDmkfOFiW/0yXXSLEyX/fIdQi16Ppbnxanb/vY=; b=JifyeADDdzCfADGSxegvLv+5PIvzWtOtujfJd+GoFaMg77RDpvVoZhei f82tk9hIRnIAfWBRFn86Pl4GpONBcyy0NpnwU5l7dCg2cemF3s6OWzTcV JviorPQ78qYC3U2JiQqltJH/Pon/RS3OooL5dJZV4vzaIJ7flGNpLYt9v t2KqEO4gnVRfYb8bfMVixnbJ7wB8mVfF0Nhm6pC0aJekXH2nVHChm6S9j UnXGfjOcvJHFSZB38CcaWnMFh95HmlKtjViMGtYZKr7aGlkdvLgEqXDnr kye659TVlXhBqSTlMHc6eNdXYCcSDSRpis2RtpN4not73reeAzssYgc73 A==; X-IronPort-AV: E=McAfee;i="6600,9927,10868"; a="389276628" X-IronPort-AV: E=Sophos;i="6.03,238,1694761200"; d="scan'208";a="389276628" Received: from orsmga005.jf.intel.com ([10.7.209.41]) by orsmga102.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 19 Oct 2023 19:20:58 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=McAfee;i="6600,9927,10868"; a="930857632" X-IronPort-AV: E=Sophos;i="6.03,238,1694761200"; d="scan'208";a="930857632" Received: from shvmail03.sh.intel.com ([10.239.245.20]) by orsmga005.jf.intel.com with ESMTP; 19 Oct 2023 19:20:56 -0700 Received: from shliclel4217.sh.intel.com (shliclel4217.sh.intel.com [10.239.240.127]) by shvmail03.sh.intel.com (Postfix) with ESMTP id 5FBC4100567C; Fri, 20 Oct 2023 10:20:55 +0800 (CST) From: liuhongt To: gcc-patches@gcc.gnu.org Cc: crazylht@gmail.com, hjl.tools@gmail.com Subject: [PATCH] Avoid compile time hog on vect_peel_nonlinear_iv_init for nonlinear induction vec_step_op_mul when iteration count is too big. Date: Fri, 20 Oct 2023 10:18:55 +0800 Message-Id: <20231020021855.482999-1-hongtao.liu@intel.com> X-Mailer: git-send-email 2.31.1 In-Reply-To: References: MIME-Version: 1.0 X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780163503634650155 X-GMAIL-MSGID: 1780239290888505460 >So with pow being available this limit shouldn't be necessary any more and >the testcase adjustment can be avoided? I tries, compile time still hogs on mpz_powm(3, INT_MAX), so i'll just keep this. >and to avoid undefined behavior with too large shift just go the gmp >way unconditionally. Changed. >this comment is now resolved I think. Removed. >mpz_pow_ui uses unsigned long while i think we constrain known niters >to uint64 - so I suggest to use mpz_powm instead (limiting to a possibly >host specific limit - unsigned long - is unfortunately a no-go). Changed. 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)). Also give up vectorization when niters_skip is negative which will be used for fully masked loop. Bootstrapped and regtested on x86_64-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/pr111820-3.c: New test. * gcc.target/i386/pr103144-mul-1.c: Adjust testcase. * gcc.target/i386/pr103144-mul-2.c: Adjust testcase. --- .../gcc.target/i386/pr103144-mul-1.c | 8 +++--- .../gcc.target/i386/pr103144-mul-2.c | 8 +++--- gcc/testsuite/gcc.target/i386/pr111820-1.c | 16 +++++++++++ gcc/testsuite/gcc.target/i386/pr111820-2.c | 16 +++++++++++ gcc/testsuite/gcc.target/i386/pr111820-3.c | 16 +++++++++++ gcc/tree-vect-loop-manip.cc | 28 +++++++++++++++++-- gcc/tree-vect-loop.cc | 13 ++++++--- 7 files changed, 90 insertions(+), 15 deletions(-) create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-1.c create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-2.c create mode 100644 gcc/testsuite/gcc.target/i386/pr111820-3.c diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c index 640c34fd959..913d7737dcd 100644 --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-1.c @@ -11,7 +11,7 @@ foo_mul (int* a, int b) for (int i = 0; i != N; i++) { a[i] = b; - b *= 3; + b *= 4; } } @@ -23,7 +23,7 @@ foo_mul_const (int* a) for (int i = 0; i != N; i++) { a[i] = b; - b *= 3; + b *= 4; } } @@ -34,7 +34,7 @@ foo_mul_peel (int* a, int b) for (int i = 0; i != 39; i++) { a[i] = b; - b *= 3; + b *= 4; } } @@ -46,6 +46,6 @@ foo_mul_peel_const (int* a) for (int i = 0; i != 39; i++) { a[i] = b; - b *= 3; + b *= 4; } } diff --git a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c index 39fdea3a69d..b2ff186e335 100644 --- a/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c +++ b/gcc/testsuite/gcc.target/i386/pr103144-mul-2.c @@ -16,12 +16,12 @@ avx2_test (void) __builtin_memset (epi32_exp, 0, N * sizeof (int)); int b = 8; - v8si init = __extension__(v8si) { b, b * 3, b * 9, b * 27, b * 81, b * 243, b * 729, b * 2187 }; + v8si init = __extension__(v8si) { b, b * 4, b * 16, b * 64, b * 256, b * 1024, b * 4096, b * 16384 }; for (int i = 0; i != N / 8; i++) { memcpy (epi32_exp + i * 8, &init, 32); - init *= 6561; + init *= 65536; } foo_mul (epi32_dst, b); @@ -32,11 +32,11 @@ avx2_test (void) if (__builtin_memcmp (epi32_dst, epi32_exp, 39 * 4) != 0) __builtin_abort (); - init = __extension__(v8si) { 1, 3, 9, 27, 81, 243, 729, 2187 }; + init = __extension__(v8si) { 1, 4, 16, 64, 256, 1024, 4096, 16384 }; for (int i = 0; i != N / 8; i++) { memcpy (epi32_exp + i * 8, &init, 32); - init *= 6561; + init *= 65536; } foo_mul_const (epi32_dst); diff --git a/gcc/testsuite/gcc.target/i386/pr111820-1.c b/gcc/testsuite/gcc.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-optimizations -fdump-tree-vect-details" } */ +/* { dg-final { scan-tree-dump "Avoid compile time hog on vect_peel_nonlinear_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 = 0; + while (-- n) + { + r_0 += r; + r *= 3; + } +} diff --git a/gcc/testsuite/gcc.target/i386/pr111820-2.c b/gcc/testsuite/gcc.target/i386/pr111820-2.c new file mode 100644 index 00000000000..dbeceb228c3 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/pr111820-2.c @@ -0,0 +1,16 @@ +/* { 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 = 0; + while (-- n) + { + r_0 += r ; + r *= 2; + } +} diff --git a/gcc/testsuite/gcc.target/i386/pr111820-3.c b/gcc/testsuite/gcc.target/i386/pr111820-3.c new file mode 100644 index 00000000000..b778f517663 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/pr111820-3.c @@ -0,0 +1,16 @@ +/* { 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 = 14; + while (-- n) + { + r_0 += r ; + r *= 3; + } +} 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 + = 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 == vect_step_op_mul) + { + tree step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info); + tree type = TREE_TYPE (step_expr); + + if (wi::exact_log2 (wi::to_wide (step_expr)) == -1 + && LOOP_VINFO_INT_NITERS(loop_vinfo) >= 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 = LOOP_VINFO_MASK_SKIP_NITERS (loop_vinfo); if ((niters_skip != NULL_TREE - && TREE_CODE (niters_skip) != INTEGER_CST) + && (TREE_CODE (niters_skip) != 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 = STMT_VINFO_LOOP_PHI_EVOLUTION_TYPE (phi_info); if (induction_type != 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..7a6bbff0c8f 100644 --- a/gcc/tree-vect-loop.cc +++ b/gcc/tree-vect-loop.cc @@ -9132,12 +9132,17 @@ vect_peel_nonlinear_iv_init (gimple_seq* stmts, tree init_expr, { tree utype = unsigned_type_for (type); init_expr = gimple_convert (stmts, utype, init_expr); - unsigned skipn = TREE_INT_CST_LOW (skip_niters); + wide_int skipn = wi::to_wide (skip_niters); wide_int begin = wi::to_wide (step_expr); - for (unsigned i = 0; i != skipn - 1; i++) - begin = wi::mul (begin, wi::to_wide (step_expr)); + auto_mpz base, exp, mod, res; + wi::to_mpz (begin, base, TYPE_SIGN (type)); + wi::to_mpz (skipn, exp, UNSIGNED); + mpz_ui_pow_ui (mod, 2, TYPE_PRECISION (type)); + mpz_powm (res, base, exp, mod); + begin = wi::from_mpz (type, res, TYPE_SIGN (type)); tree mult_expr = wide_int_to_tree (utype, begin); - init_expr = gimple_build (stmts, MULT_EXPR, utype, init_expr, mult_expr); + init_expr = gimple_build (stmts, MULT_EXPR, utype, + init_expr, mult_expr); init_expr = gimple_convert (stmts, type, init_expr); } break;