From patchwork Fri May 19 09:43:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ajit Agarwal X-Patchwork-Id: 69661 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 444623858C5F for ; Fri, 19 May 2023 09:44:23 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 444623858C5F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1684489463; bh=AOf3sgGuqLFhZii7s1Nn7tE7wxDUm6hWS8pY9eBqeYA=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=YxVqc5/TLd2RUovXcRaR5PxILTqCvg26oJ6X/iqWFAqGSyxV8D1O1o3sWAPsX2ftn +058nMl6C1BO8BTfa6NERyAQyCww9NIvVXe0dm4d3JSiCAUNVaU39dcGZbf5P1CWc6 gMpDFUaBh9eIsJUNrrCzWMRRVvCsLvF8YujPkP7Q= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id 9FAEA3858D28 for ; Fri, 19 May 2023 09:43:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9FAEA3858D28 Received: from pps.filterd (m0356517.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 34J9b8KV012138; Fri, 19 May 2023 09:43:50 GMT Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3qp5d3jqyc-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 19 May 2023 09:43:49 +0000 Received: from m0356517.ppops.net (m0356517.ppops.net [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 34J9bV8G015448; Fri, 19 May 2023 09:43:49 GMT Received: from ppma02dal.us.ibm.com (a.bd.3ea9.ip4.static.sl-reverse.com [169.62.189.10]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3qp5d3jqy5-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 19 May 2023 09:43:48 +0000 Received: from pps.filterd (ppma02dal.us.ibm.com [127.0.0.1]) by ppma02dal.us.ibm.com (8.17.1.19/8.17.1.19) with ESMTP id 34J7jOCw025323; Fri, 19 May 2023 09:43:48 GMT Received: from smtprelay04.wdc07v.mail.ibm.com ([9.208.129.114]) by ppma02dal.us.ibm.com (PPS) with ESMTPS id 3qj266e614-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 19 May 2023 09:43:47 +0000 Received: from smtpav05.wdc07v.mail.ibm.com (smtpav05.wdc07v.mail.ibm.com [10.39.53.232]) by smtprelay04.wdc07v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 34J9hk7B30147148 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 19 May 2023 09:43:46 GMT Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 8B32358053; Fri, 19 May 2023 09:43:46 +0000 (GMT) Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id B85835805F; Fri, 19 May 2023 09:43:43 +0000 (GMT) Received: from [9.43.39.194] (unknown [9.43.39.194]) by smtpav05.wdc07v.mail.ibm.com (Postfix) with ESMTP; Fri, 19 May 2023 09:43:43 +0000 (GMT) Message-ID: <97ba4caa-8072-98ab-83cb-6570db6a04b7@linux.ibm.com> Date: Fri, 19 May 2023 15:13:41 +0530 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Content-Language: en-US To: gcc-patches Cc: Segher Boessenkool , Peter Bergner , Jeff Law , Richard Biener Subject: [PATCH v2] tree-ssa-sink: Improve code sinking pass X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: 22Y8ecxjFUVjUbf91FtIHUI3CmgcnEUU X-Proofpoint-GUID: qjX2vBlArBA9SfbQ7Q6YylJCc6R1smQH X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.170.22 definitions=2023-05-19_06,2023-05-17_02,2023-02-09_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 mlxscore=0 priorityscore=1501 bulkscore=0 suspectscore=0 clxscore=1015 malwarescore=0 mlxlogscore=999 spamscore=0 impostorscore=0 phishscore=0 lowpriorityscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2304280000 definitions=main-2305190080 X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, 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: Ajit Agarwal via Gcc-patches From: Ajit Agarwal Reply-To: Ajit Agarwal Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Hello All: This patch improves code sinking pass to sink statements before call to reduce register pressure. Review comments are incorporated. For example : void bar(); int j; void foo(int a, int b, int c, int d, int e, int f) { int l; l = a + b + c + d +e + f; if (a != 5) { bar(); j = l; } } Code Sinking does the following: void bar(); int j; void foo(int a, int b, int c, int d, int e, int f) { int l; if (a != 5) { l = a + b + c + d +e + f; bar(); j = l; } } Bootstrapped regtested on powerpc64-linux-gnu. Thanks & Regards Ajit tree-ssa-sink: Improve code sinking pass Code Sinking sinks the blocks after call.This increases register pressure for callee-saved registers. Improves code sinking before call in the use blocks or immediate dominator of use blocks. 2023-05-18 Ajit Kumar Agarwal gcc/ChangeLog: * tree-ssa-sink.cc (statement_sink_location): Move statements before calls. (block_call_p): New function. (def_use_same_block): New function. (select_best_block): Add heuristics to select the best blocks in the immediate post dominator. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase. * gcc.dg/tree-ssa/ssa-sink-21.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 15 ++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 19 +++ gcc/tree-ssa-sink.cc | 160 ++++++++++++++++++-- 3 files changed, 183 insertions(+), 11 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c new file mode 100644 index 00000000000..69fa6d32e7c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c @@ -0,0 +1,15 @@ +/* { dg-options "-O2 -fdump-tree-optimized -fdump-tree-sink-stats" } */ + +void bar(); +int j; +void foo(int a, int b, int c, int d, int e, int f) +{ + int l; + l = a + b + c + d +e + f; + if (a != 5) + { + bar(); + j = l; + } +} +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c new file mode 100644 index 00000000000..b34959c8a4d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c @@ -0,0 +1,19 @@ +/* { dg-options "-O2 -fdump-tree-sink-stats" } */ + +void bar(); +int j, x; +void foo(int a, int b, int c, int d, int e, int f) +{ + int l; + l = a + b + c + d +e + f; + if (a != 5) + { + bar(); + if (b != 3) + x = 3; + else + x = 5; + j = l; + } +} +/* { dg-final { scan-tree-dump-times "Sunk statements: 5" 1 "sink" } } */ diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc index b1ba7a2ad6c..091aa90d289 100644 --- a/gcc/tree-ssa-sink.cc +++ b/gcc/tree-ssa-sink.cc @@ -171,6 +171,71 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) return commondom; } +/* Return TRUE if immediate uses of the defs in + STMT occur in the same block as STMT, FALSE otherwise. */ + +bool +def_use_same_block (gimple *stmt) +{ + use_operand_p use; + def_operand_p def; + imm_use_iterator imm_iter; + ssa_op_iter iter; + + FOR_EACH_SSA_DEF_OPERAND (def, stmt, iter, SSA_OP_DEF) + { + FOR_EACH_IMM_USE_FAST (use, imm_iter, DEF_FROM_PTR (def)) + { + if (is_gimple_debug (USE_STMT (use))) + continue; + + if (use && (gimple_bb (USE_STMT (use)) == gimple_bb (stmt))) + return true; + } + } + return false; +} + +/* Return TRUE if the block has only one call statement, FALSE otherwise. */ + +bool +block_call_p (basic_block bb) +{ + int i = 0; + bool is_call = false; + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gimple *last_stmt = gsi_stmt (gsi); + + if (last_stmt && gimple_code (last_stmt) == GIMPLE_COND) + { + if (!gsi_end_p (gsi)) + gsi_prev (&gsi); + + for (; !gsi_end_p (gsi);) + { + gimple *stmt = gsi_stmt (gsi); + + /* We have already seen a call. */ + if (is_call) + return false; + + if (is_gimple_call (stmt)) + is_call = true; + else + return false; + + if (!gsi_end_p (gsi)) + gsi_prev (&gsi); + + ++i; + } + } + if (is_call && i == 1) + return true; + + return false; +} + /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator tree, return the best basic block between them (inclusive) to place statements. @@ -190,7 +255,8 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts) static basic_block select_best_block (basic_block early_bb, basic_block late_bb, - gimple *stmt) + gimple *stmt, + gimple *use) { basic_block best_bb = late_bb; basic_block temp_bb = late_bb; @@ -230,14 +296,47 @@ select_best_block (basic_block early_bb, if (threshold > 100) threshold = 100; } - /* If BEST_BB is at the same nesting level, then require it to have significantly lower execution frequency to avoid gratuitous movement. */ if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb) /* If result of comparsion is unknown, prefer EARLY_BB. Thus use !(...>=..) rather than (...<...) */ && !(best_bb->count * 100 >= early_bb->count * threshold)) - return best_bb; + { + basic_block new_best_bb = get_immediate_dominator (CDI_DOMINATORS, best_bb); + /* Return best_bb if def and use are in same block otherwise new_best_bb. + + Things to consider: + + new_best_bb is not equal to best_bb and early_bb. + + stmt is not call. + + new_best_bb doesnt have any phis. + + use basic block is not equal to early_bb. + + use basic block post dominates to new_best_bb. + + new_best_bb dominates early_bb. */ + if (new_best_bb && use + && (new_best_bb != best_bb) + && (new_best_bb != early_bb) + && !is_gimple_call (stmt) + && gsi_end_p (gsi_start_phis (new_best_bb)) + && (gimple_bb (use) != early_bb) + && !is_gimple_call (use) + && dominated_by_p (CDI_POST_DOMINATORS, new_best_bb, gimple_bb(use)) + && dominated_by_p (CDI_DOMINATORS, new_best_bb, early_bb) + && block_call_p (new_best_bb)) + { + if (def_use_same_block (use)) + return best_bb; + + return new_best_bb; + } + return best_bb; + } /* No better block found, so return EARLY_BB, which happens to be the statement's original block. */ @@ -382,7 +481,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, { /* Do not sink loads from hard registers. */ if (gimple_assign_single_p (stmt) - && VAR_P (gimple_assign_rhs1 (stmt)) + && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))) return false; @@ -439,7 +538,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb)) return false; - commondom = select_best_block (frombb, commondom, stmt); + commondom = select_best_block (frombb, commondom, stmt, NULL); if (commondom == frombb) return false; @@ -456,19 +555,58 @@ statement_sink_location (gimple *stmt, basic_block frombb, continue; break; } + use = USE_STMT (one_use); if (gimple_code (use) != GIMPLE_PHI) { - sinkbb = select_best_block (frombb, gimple_bb (use), stmt); + sinkbb = select_best_block (frombb, gimple_bb (use), stmt, use); if (sinkbb == frombb) return false; - if (sinkbb == gimple_bb (use)) - *togsi = gsi_for_stmt (use); - else - *togsi = gsi_after_labels (sinkbb); + gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p)); + + if ((gimple_bb (def_stmt) == gimple_bb (use)) + && (gimple_bb (use) != sinkbb)) + sinkbb = gimple_bb (use); + + if (sinkbb == gimple_bb (use)) + { + gimple_stmt_iterator gsi = gsi_last_bb (sinkbb); + gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p)); + gimple *last_stmt = gsi_stmt (gsi); + + /* Update sinking point as stmt before call if the sinking block + has only calls. Otherwise update sinking point as the use + stmt. */ + if (gsi_stmt (gsi) == use + && !is_gimple_call (last_stmt) + && gimple_code (last_stmt) != GIMPLE_SWITCH + && gimple_code (last_stmt) != GIMPLE_COND + && gimple_code (last_stmt) != GIMPLE_GOTO + && (!gimple_vdef (use) || !def_use_same_block (def_stmt))) + { + if (!gsi_end_p (gsi)) + gsi_prev (&gsi); + + gimple *stmt = gsi_stmt (gsi); + + if (!gsi_end_p (gsi)) + gsi_prev (&gsi); + + if (gsi_end_p (gsi) && stmt && is_gimple_call (stmt) + && gsi_end_p (gsi_start_phis (sinkbb)) + && !is_gimple_call (def_stmt)) + *togsi = gsi_for_stmt (stmt); + else + *togsi = gsi_for_stmt (use); + } + else + *togsi = gsi_for_stmt(use); + } + else + *togsi = gsi_after_labels (sinkbb); return true; } @@ -480,7 +618,7 @@ statement_sink_location (gimple *stmt, basic_block frombb, if (!sinkbb) return false; - sinkbb = select_best_block (frombb, sinkbb, stmt); + sinkbb = select_best_block (frombb, sinkbb, stmt, NULL); if (!sinkbb || sinkbb == frombb) return false;