From patchwork Thu May 11 10:12:00 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Li, Pan2 via Gcc-patches" X-Patchwork-Id: 92472 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp4252216vqo; Thu, 11 May 2023 03:13:13 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6fWcqQhlsYXwSPuQqsT43ZXgNHKoI/QDMcZnA0m1udXDE8RmXNKhfU6sFFS3+K1cmNogIM X-Received: by 2002:a17:907:a0c:b0:966:2123:e0ca with SMTP id bb12-20020a1709070a0c00b009662123e0camr14601446ejc.34.1683799993187; Thu, 11 May 2023 03:13:13 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1683799993; cv=none; d=google.com; s=arc-20160816; b=NCb39QrDTxHG+0sHc/gNRa3KoXMpQXtFmEaXGE4mIZc/MA245pi+nspSsgYjKXsTQa FiS73l8gGyZJymKE+DS5VEv1EC4H74fEZknpLRcllkem1VP0LBn5G0DEf86yqcbBkSS+ rWKR051F3ungOOjr1ElrvOhIFRcz6grOQnMkt6mDiLBXHjQYJmdXx075AKy0yI4WXBbx xI8o6fbwIzRlga8iXCc8urSMBTRUYZI9IZ6GYi+G9PYtMRt0zrUzLKHd2N2Dm5LGG0tr VP8IWfGvkx7A7SMh0t3q9RJwB6LpLweQKoyjFLjY84YaF2SqXQh7Ghy3nlE2oCXzDs3T VznQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:cc :to:dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=a6eFYHNt0PIeNXB2CIxWSPbRk/eMiDIj+6X5Xvg3ahQ=; b=pyWg3JeJLWIu2d8AJNjyFWK7CGS6iUTf9sSl4642L9oec7j7Kvt9ugGNRrxlioSO26 2Ibx1SzZXAt2bk8k0qXgAT0Z3nbI6pO4kgLLmaRNXA5pZS8vh1A4R7xYWVBBTZ/Cl68a 9NzaHCggvaE5VCDYAfIyHryPAyYvz56p999Y+9PSyn5IxJHu2l0TszCKDg54icnblusu IzlgCeG1GIcLHH6Xi0GVQdaFBBTG0KLMyR5ob1o2nNK8DeDZx0qunvKuEP9DdBBjBz3w h0QUdoaPcwCJsdL3M38USNu5xElhlytleEw3yit9iaRaycDmeyboiNg/glCu5f0Wcmmk ktQw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=NFSDZF8Q; 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=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id g23-20020a50ee17000000b0050bc3b40192si4927114eds.638.2023.05.11.03.13.12 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 11 May 2023 03:13:13 -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=@gcc.gnu.org header.s=default header.b=NFSDZF8Q; 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=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0B1043856968 for ; Thu, 11 May 2023 10:12:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0B1043856968 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1683799973; bh=a6eFYHNt0PIeNXB2CIxWSPbRk/eMiDIj+6X5Xvg3ahQ=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=NFSDZF8QaHhjUcHH1fIPDdKIESWkdn2x5H9gmZahwXzd1lU548x9+dfZ7VFuuvLLy T9SenuQDHepSYFZJld3uayQIlEBsBsEHBJFzTTxU/O6gO9UiDhlR0TeEJSA0lqHrs7 K8oSdAWcS3C5BN4DMlQzTA4NUUOy6GGkmw38lp1o= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by sourceware.org (Postfix) with ESMTPS id F33243858C83 for ; Thu, 11 May 2023 10:12:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org F33243858C83 X-IronPort-AV: E=McAfee;i="6600,9927,10706"; a="330815122" X-IronPort-AV: E=Sophos;i="5.99,266,1677571200"; d="scan'208";a="330815122" Received: from orsmga007.jf.intel.com ([10.7.209.58]) by fmsmga107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 11 May 2023 03:12:03 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=McAfee;i="6600,9927,10706"; a="693740205" X-IronPort-AV: E=Sophos;i="5.99,266,1677571200"; d="scan'208";a="693740205" Received: from scymds03.sc.intel.com ([10.148.94.166]) by orsmga007.jf.intel.com with ESMTP; 11 May 2023 03:12:03 -0700 Received: from shgcc101.sh.intel.com (shgcc101.sh.intel.com [10.239.85.97]) by scymds03.sc.intel.com (Postfix) with ESMTP id C5BB878; Thu, 11 May 2023 03:12:02 -0700 (PDT) To: gcc-patches@gcc.gnu.org Cc: Lili Cui Subject: [PATCH 1/2] PR gcc/98350:Add a param to control the length of the chain with FMA in reassoc pass Date: Thu, 11 May 2023 10:12:00 +0000 Message-Id: <20230511101201.2052667-1-lili.cui@intel.com> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: "Cui, Lili via Gcc-patches" From: "Li, Pan2 via Gcc-patches" Reply-To: "Cui, Lili" Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1765592261564359060?= X-GMAIL-MSGID: =?utf-8?q?1765592261564359060?= From: Lili Cui Hi, Those two patches each add a param to control the length of the chain with FMA in reassoc pass and a tuning option in the backend. Bootstrapped and regtested. Ok for trunk? Regards Lili. Add a param for the chain with FMA in reassoc pass to make it more friendly to the fma pass later. First to detect if this chain has ability to generate more than 2 FMAs,if yes and param_reassoc_max_chain_length_with_fma is enabled, We will rearrange the ops so that they can be combined into more FMAs. When the chain length exceeds param_reassoc_max_chain_length_with_fma, build parallel chains according to given association width and try to keep FMA opportunity as much as possible. TEST1: float foo (float a, float b, float c, float d, float *e) { return *e + a * b + c * d ; } For -Ofast -march=icelake-server GCC generates: vmulss %xmm3, %xmm2, %xmm2 vfmadd132ss %xmm1, %xmm2, %xmm0 vaddss (%rdi), %xmm0, %xmm0 ret with "--param=reassoc-max-chain-length-with-fma=3" GCC generates: vfmadd213ss (%rdi), %xmm1, %xmm0 vfmadd231ss %xmm2, %xmm3, %xmm0 ret gcc/ChangeLog: PR gcc/98350 * params.opt (reassoc-max-fma-chain-length): New param. * tree-ssa-reassoc.cc (rewrite_expr_tree_parallel_for_fma): New. (rank_ops_for_fma): Ditto. (reassociate_bb): Handle new function. gcc/testsuite/ChangeLog: PR gcc/98350 * gcc.dg/pr98350-1.c: New test. * gcc.dg/pr98350-2.c: Ditto. --- gcc/params.opt | 4 + gcc/testsuite/gcc.dg/pr98350-1.c | 31 +++++ gcc/testsuite/gcc.dg/pr98350-2.c | 17 +++ gcc/tree-ssa-reassoc.cc | 228 ++++++++++++++++++++++++++++--- 4 files changed, 264 insertions(+), 16 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/pr98350-1.c create mode 100644 gcc/testsuite/gcc.dg/pr98350-2.c diff --git a/gcc/params.opt b/gcc/params.opt index 823cdb2ff85..f7c719afe64 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -1182,4 +1182,8 @@ The maximum factor which the loop vectorizer applies to the cost of statements i Common Joined UInteger Var(param_vect_induction_float) Init(1) IntegerRange(0, 1) Param Optimization Enable loop vectorization of floating point inductions. +-param=reassoc-max-chain-length-with-fma= +Common Joined UInteger Var(param_reassoc_max_chain_length_with_fma) Init(1) IntegerRange(1, 65536) Param Optimization +The maximum chain length with fma considered in reassociation pass. + ; This comment is to ensure we retain the blank line above. diff --git a/gcc/testsuite/gcc.dg/pr98350-1.c b/gcc/testsuite/gcc.dg/pr98350-1.c new file mode 100644 index 00000000000..32ecce13a2d --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr98350-1.c @@ -0,0 +1,31 @@ +/* { dg-do compile } */ +/* { dg-options "-Ofast -mfpmath=sse -mfma --param=reassoc-max-chain-length-with-fma=7 -Wno-attributes " } */ + +/* Test that the compiler properly optimizes multiply and add + to generate more FMA instructions. */ +#define N 1024 +double a[N]; +double b[N]; +double c[N]; +double d[N]; +double e[N]; +double f[N]; +double g[N]; +double h[N]; +double j[N]; +double k[N]; +double l[N]; +double m[N]; +double o[N]; +double p[N]; + + +void +foo (void) +{ + for (int i = 0; i < N; i++) + { + a[i] += b[i] * c[i] + d[i] * e[i] + f[i] * g[i] + h[i] * j[i] + k[i] * l[i] + m[i]* o[i] + p[i]; + } +} +/* { dg-final { scan-assembler-times "vfm" 6 } } */ diff --git a/gcc/testsuite/gcc.dg/pr98350-2.c b/gcc/testsuite/gcc.dg/pr98350-2.c new file mode 100644 index 00000000000..246025d43b8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr98350-2.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-Ofast -mfpmath=sse -mfma --param=reassoc-max-chain-length-with-fma=6 -Wno-attributes " } */ + +/* Test that the compiler properly build parallel chains according to given + association width and try to keep FMA opportunity as much as possible. */ +#define N 33 +double a[N]; + +void +foo (void) +{ + a[32] = a[0] *a[1] + a[2] * a[3] + a[4] * a[5] + a[6] * a[7] + a[8] * a[9] + + a[10] * a[11] + a[12] * a[13] + a[14] * a[15] + a[16] * a[17] + + a[18] * a[19] + a[20] * a[21] + a[22] * a[23] + a[24] + a[25] + + a[26] + a[27] + a[28] + a[29] + a[30] + a[31]; +} +/* { dg-final { scan-assembler-times "vfm" 12 } } */ diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc index 067a3f07f7e..6d2e158c4f5 100644 --- a/gcc/tree-ssa-reassoc.cc +++ b/gcc/tree-ssa-reassoc.cc @@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-reassoc.h" #include "tree-ssa-math-opts.h" #include "gimple-range.h" +#include "internal-fn.h" /* This is a simple global reassociation pass. It is, in part, based on the LLVM pass of the same name (They do some things more/less @@ -5468,6 +5469,114 @@ get_reassociation_width (int ops_num, enum tree_code opc, return width; } +/* Rewrite statements with dependency chain with regard to the chance to + generate FMA. When the dependency chain length exceeds + param_max_reassoc_chain_length_with_fma, build parallel chains according to + given association width and try to keep fma opportunity as much as possible. + E.g. + e + f + g + a * b + c * d; + + ssa1 = e + f; + ssa2 = g + a * b; + ssa3 = ssa1 + c * d; + ssa4 = ssa2 + ssa3; + + This reassociation approach preserves the chance of fma generation as much + as possible. */ +static void +rewrite_expr_tree_parallel_for_fma (gassign *stmt, int width, + const vec &ops) +{ + enum tree_code opcode = gimple_assign_rhs_code (stmt); + int op_num = ops.length (); + gcc_assert (op_num > 0); + int stmt_num = op_num - 1; + gimple **stmts = XALLOCAVEC (gimple *, stmt_num); + int op_index = op_num - 1; + int width_count = width; + int i = 0, j = 0; + tree tmp_op[2], op1; + operand_entry *oe; + gimple *stmt1 = NULL; + tree last_rhs1 = gimple_assign_rhs1 (stmt); + + /* We start expression rewriting from the top statements. + So, in this loop we create a full list of statements + we will work with. */ + stmts[stmt_num - 1] = stmt; + for (i = stmt_num - 2; i >= 0; i--) + stmts[i] = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmts[i+1])); + + /* Build parallel FMA dependency chain according to width. */ + for (i = 0; i < width; i++) + { + for (j = 0; j < 2; j++) + { + oe = ops[op_index--]; + tmp_op[j] = oe->op; + stmt1 = oe->stmt_to_insert; + if (stmt1) + insert_stmt_before_use (stmts[i], stmt1); + stmt1 = NULL; + } + stmts[i] = build_and_add_sum (TREE_TYPE (last_rhs1), tmp_op[1], tmp_op[0], opcode); + gimple_set_visited (stmts[i], true); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " into "); + print_gimple_stmt (dump_file, stmts[i], 0); + } + } + + for (i = width; i < stmt_num; i++) + { + /* We keep original statement only for the last one. All others are + recreated. */ + if ( op_index < 0) + { + if (width_count == 2) + { + + gimple_assign_set_rhs1 (stmts[i], gimple_assign_lhs (stmts[i-1])); + gimple_assign_set_rhs2 (stmts[i], gimple_assign_lhs (stmts[i-2])); + } + else + { + + stmts[i] = + build_and_add_sum (TREE_TYPE (last_rhs1), + gimple_assign_lhs (stmts[i-width_count]), + gimple_assign_lhs (stmts[i-width_count+1]), + opcode); + width_count--; + } + update_stmt (stmts[i]); + } + else + { + oe = ops[op_index--]; + op1 = oe->op; + stmt1 = oe->stmt_to_insert; + if (stmt1) + insert_stmt_before_use (stmts[i], stmt1); + stmt1 = NULL; + stmts[i] = build_and_add_sum (TREE_TYPE (last_rhs1), + gimple_assign_lhs (stmts[i-width]), + op1, + opcode); + gimple_set_visited (stmts[i], true); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " into "); + print_gimple_stmt (dump_file, stmts[i], 0); + } + } + remove_visited_stmt_chain (last_rhs1); +} + /* Recursively rewrite our linearized statements so that the operators match those in OPS[OPINDEX], putting the computation in rank order and trying to allow operations to be executed in @@ -6649,6 +6758,64 @@ transform_stmt_to_multiply (gimple_stmt_iterator *gsi, gimple *stmt, } } +/* Rearrange ops to generate more FMA when the chain may has more than 2 fmas. + Putting ops that not def from mult in front can generate more fma. + E.g. + a * b + c * d + e generates: + + _4 = c_9(D) * d_10(D); + _12 = .FMA (a_7(D), b_8(D), _4); + _11 = e_6(D) + _12; + + Rtearrange ops to -> e + a * b + c * d generates: + + _4 = .FMA (c_7(D), d_8(D), _3); + _11 = .FMA (a_5(D), b_6(D), _4); + */ +static bool +rank_ops_for_fma (vec *ops) +{ + operand_entry *oe; + unsigned int i; + auto_vec ops_mult; + auto_vec ops_others; + + FOR_EACH_VEC_ELT (*ops, i, oe) + { + if (TREE_CODE (oe->op) == SSA_NAME) + { + gimple *def_stmt = SSA_NAME_DEF_STMT (oe->op); + if (is_gimple_assign (def_stmt) + && gimple_assign_rhs_code (def_stmt) == MULT_EXPR) + ops_mult.safe_push (oe); + else + ops_others.safe_push (oe); + } + else + ops_others.safe_push (oe); + } + /* When ops_mult.length == 2, like the following case, + + a * b + c * d + e. + + we need to rearrange the ops. + + Putting ops that not def from mult in front can generate more fmas. */ + if (ops_mult.length () >= 2) + { + /* If all ops are defined with mult, we don't need to rearrange them. */ + if (ops_mult.length () != ops->length ()) + { + ops->truncate (0); + FOR_EACH_VEC_ELT (ops_mult, i, oe) + ops->safe_push (oe); + FOR_EACH_VEC_ELT (ops_others, i, oe) + ops->safe_push (oe); + } + return true; + } + return false; +} /* Reassociate expressions in basic block BB and its post-dominator as children. @@ -6813,6 +6980,7 @@ reassociate_bb (basic_block bb) machine_mode mode = TYPE_MODE (TREE_TYPE (lhs)); int ops_num = ops.length (); int width; + bool keep_fma_chain = false; /* For binary bit operations, if there are at least 3 operands and the last operand in OPS is a constant, @@ -6826,36 +6994,64 @@ reassociate_bb (basic_block bb) && TREE_CODE (ops.last ()->op) == INTEGER_CST) std::swap (*ops[0], *ops[ops_num - 1]); + optimization_type opt_type = bb_optimization_type (bb); + + /* When enabling param_reassoc_max_chain_length_with_fma to + keep the chain with fma, rank_ops_for_fma will detect if + the chain has fmas and if so it will rearrange the ops. */ + if (param_reassoc_max_chain_length_with_fma > 1 + && direct_internal_fn_supported_p (IFN_FMA, + TREE_TYPE (lhs), + opt_type) + && (rhs_code == PLUS_EXPR || rhs_code == MINUS_EXPR)) + { + keep_fma_chain = rank_ops_for_fma(&ops); + } + + int len = ops.length (); /* Only rewrite the expression tree to parallel in the last reassoc pass to avoid useless work back-and-forth with initial linearization. */ if (!reassoc_insert_powi_p - && ops.length () > 3 + && len > 3 + && (!keep_fma_chain + || (keep_fma_chain + && len > param_reassoc_max_chain_length_with_fma)) && (width = get_reassociation_width (ops_num, rhs_code, - mode)) > 1) + mode)) > 1) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "Width = %d was chosen for reassociation\n", - width); - rewrite_expr_tree_parallel (as_a (stmt), - width, ops); + if (keep_fma_chain) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Break chain len = %d into width for FMA\n", + len); + rewrite_expr_tree_parallel_for_fma + (as_a (stmt), width, ops); + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Width = %d was chosen for reassociation\n", + width); + rewrite_expr_tree_parallel (as_a (stmt), + width, ops); + } } else - { - /* When there are three operands left, we want - to make sure the ones that get the double - binary op are chosen wisely. */ - int len = ops.length (); - if (len >= 3) + { + /* When there are three operands left, we want + to make sure the ones that get the double + binary op are chosen wisely. */ + if (len >= 3 && !keep_fma_chain) swap_ops_for_binary_stmt (ops, len - 3); new_lhs = rewrite_expr_tree (stmt, rhs_code, 0, ops, powi_result != NULL || negate_result, len != orig_len); - } - + } /* If we combined some repeated factors into a __builtin_powi call, multiply that result by the reassociated operands. */