From patchwork Fri Jul 7 09:37:20 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tamar Christina X-Patchwork-Id: 117049 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9f45:0:b0:3ea:f831:8777 with SMTP id v5csp3139224vqx; Fri, 7 Jul 2023 02:38:51 -0700 (PDT) X-Google-Smtp-Source: APBJJlHCSIPfvQyaLSGWhBMybjEBOZQ4U8rIKNLLTO4I/+IbsvIbYRFExwvXRhsk/ON6Aet17Bsz X-Received: by 2002:aa7:cc15:0:b0:51e:1690:1b97 with SMTP id q21-20020aa7cc15000000b0051e16901b97mr3466329edt.19.1688722730789; Fri, 07 Jul 2023 02:38:50 -0700 (PDT) Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id bo24-20020a0564020b3800b0051e270fe57bsi1874592edb.503.2023.07.07.02.38.50 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 07 Jul 2023 02:38:50 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=N2P+1zt8; arc=fail (signature failed); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 499AF3870C21 for ; Fri, 7 Jul 2023 09:38:31 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 499AF3870C21 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1688722711; bh=Z2fyp0Ici4z7AJ7TUwMTBxsFISW9e9g86BIzrUoSWcE=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=N2P+1zt8dYP0LPjJx8wypvmW50LyHqTmGaeJbNvxqprlRIUTEgMTEdlWIpsHb9oR0 h3njfnvar9VVpGNbSQvFhGUpPAgtUoV70+5USmc17p565PUNoE45quY7h9FyIyc5tE P4yLTlVS4qu6do/eDPCueK2Eeq3fV8HqXkdQxOiQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from EUR05-DB8-obe.outbound.protection.outlook.com (mail-db8eur05on2087.outbound.protection.outlook.com [40.107.20.87]) by sourceware.org (Postfix) with ESMTPS id 26E64385E45D for ; Fri, 7 Jul 2023 09:37:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 26E64385E45D Received: from DUZPR01CA0222.eurprd01.prod.exchangelabs.com (2603:10a6:10:4b4::29) by DBBPR08MB5946.eurprd08.prod.outlook.com (2603:10a6:10:1f6::8) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.17; Fri, 7 Jul 2023 09:37:35 +0000 Received: from DBAEUR03FT053.eop-EUR03.prod.protection.outlook.com (2603:10a6:10:4b4:cafe::81) by DUZPR01CA0222.outlook.office365.com (2603:10a6:10:4b4::29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.25 via Frontend Transport; Fri, 7 Jul 2023 09:37:35 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by DBAEUR03FT053.mail.protection.outlook.com (100.127.142.121) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.25 via Frontend Transport; Fri, 7 Jul 2023 09:37:35 +0000 Received: ("Tessian outbound 997ae1cc9f47:v145"); Fri, 07 Jul 2023 09:37:35 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: dd92e891139bd767 X-CR-MTA-TID: 64aa7808 Received: from 3f5520a87110.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id DCA1C1BF-C6F0-4C23-AC7A-A75D31E2E0F4.1; Fri, 07 Jul 2023 09:37:28 +0000 Received: from EUR03-AM7-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 3f5520a87110.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Fri, 07 Jul 2023 09:37:28 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=SKxNCmIIH91uJk057LXrKb4VC1lB+Sse33ud7enl92Ff/dZ7CQcOA2Emrx8HA2Zwgk1k2zGCVGZWvL/wJUY6zwc3xxRnnL7q2q/k/i5aADTCW1kh8+omZzFprnRlVmmnOXwpoKzcu6fY1xPDheMY1KW919DXcgY5RqNe4E2KMZndDDwlU+/KLdnjdlcf9mMqy0tHA7fj/VTC5iFkoa21YRkTYIkCJ92qlUXHLjFmI21i4ea7e7hy+IatJvYUK6Vq/NX817DSPliu1nFfVFpWvu6g7MVUpxoAk2WvlPhjmjHhqoBxygRk07/T3bEOF/c31TTSm0Oyg6ZY7ZnNRu8kZA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=Z2fyp0Ici4z7AJ7TUwMTBxsFISW9e9g86BIzrUoSWcE=; b=c5SIIM1/lp5rtLRDQvkzhueocTHJNVTHIzVMHfXUQTTdr5BN++g04HHmU1qAZcrU6jjYWGJDME593ABNfbGQDpiyLP5AcKQXocO3CRwY5q8mj67VE88NhO0GvyhS1KrBwK7Acax+g91Q+PUrPC+CfF0cIjebxxa1zIYLmMwhmfIGh46QsxQHPiPL/78YGDmgi06KzssexaeMbVXXJhpF+JArc/RGqEJQKUebmNo+wUfkMj7MRGhvKM/5Wc8tx8gCC2BgC+tOOd2aDulbffpJozIEgMuOlBo9YiWMSfqNJ9WsgVetClo3WV7zuK9JrpOX1CNiWLiJjDd62LHo9nc5WQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; Received: from VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) by DU0PR08MB8231.eurprd08.prod.outlook.com (2603:10a6:10:3b0::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.17; Fri, 7 Jul 2023 09:37:23 +0000 Received: from VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::2301:1cde:cfe7:eaf0]) by VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::2301:1cde:cfe7:eaf0%6]) with mapi id 15.20.6565.016; Fri, 7 Jul 2023 09:37:23 +0000 Date: Fri, 7 Jul 2023 10:37:20 +0100 To: gcc-patches@gcc.gnu.org Cc: nd@arm.com, rguenther@suse.de, jlaw@ventanamicro.com Subject: [PATCH 1/2]middle-end ifcvt: Reduce comparisons on conditionals by tracking truths [PR109154] Message-ID: Content-Disposition: inline X-ClientProxiedBy: LNXP265CA0085.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:76::25) To VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: VI1PR08MB5325:EE_|DU0PR08MB8231:EE_|DBAEUR03FT053:EE_|DBBPR08MB5946:EE_ X-MS-Office365-Filtering-Correlation-Id: 62df8633-ff9d-4e63-e9f8-08db7ecdcbe0 x-checkrecipientrouted: true NoDisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: rQ9aQeYUp6ZS8VqLsn8xhYZOnfy3M9wDqQiSqVqAU8Afz9IGoDkLMjsyhPEApi9KBG5+yXVR9uAEdqu/RVVCxERfU4jjvk+EXfXWqsaBPXhMhqiIdIgU+CoMlLij8OAfSyYBr5YX7ZB49/WroIzxPAW8N0vEVLXk+mz9HSrKZTBAKI2eIUHItUrzdlKygJIKpePbRuBl1OONSJv4yfkYeI7zsOyEUcFz2gJSNZYvELetyhWn2g18OcMECp4xQTBDIoEgKMbzkx8I8lFGhcHRyZerLvmzHyiQ39UhBMLNyqcQH2HQoAfejGUP7WToSfsR6neWEeGO+BoWBBm+vEmHEo4JCfIYElVra+fUSIEmj0YLo9Itwcf6Ck/4RaPRMI6L27IW8sHTRffD/cQriOUDxmdFu4jvvuLJ55hVhhRbHKQtmbw5tHK7N4EzHD0L/OiedRS/MsxAc7CxVSpWLS8BszRU+BYg95JrLSxKbVkT51J/+H5ggGrEvQ6qipnpz93JB06FypmKncxVvAInPv15jXsBfmKShm2FLFEF0rrc+snck3xPXf7eYmYhRrp5xyNRiCcdXwLQ28+/o/u7b30hiC/bcCaDa2L98YjCxym4zUzkUuMn7K2L6eGdFmwF4Uf0Y6UEod+AvWEAf4xOPVu0dA== X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1PR08MB5325.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230028)(4636009)(396003)(136003)(39860400002)(346002)(366004)(376002)(451199021)(36756003)(44832011)(5660300002)(86362001)(2906002)(235185007)(66899021)(6512007)(186003)(83380400001)(6506007)(26005)(66476007)(6916009)(44144004)(33964004)(478600001)(6486002)(66556008)(2616005)(38100700002)(316002)(66946007)(4326008)(8676002)(8936002)(41300700001)(4216001)(2700100001); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU0PR08MB8231 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: DBAEUR03FT053.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: bbf2f517-8868-4c22-5702-08db7ecdc437 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: x3iUAybDBMdpeJkxt8IYBQEgomvrp9PB+ZYEA1wV5QSkA+5SCPFphPYKk1ZYryk+I+d1iWc0vaYZqlfpPgx0TE3A5bUEgATjf874qFbPji6CpyCKNKxgklvBolk3kQ3pj3ams9nacDi9TmsQ/AbKJ89g8mjKnoR4pKxZjuW6FnG2K60dRHv3mBwkqbhUJ40lD5epq92FarG9WRlEDVMYA015RxkpxQJPYT6m9R8RNTWri0cKFfgn5M2Ejt9MeaDsrLuuKz/OHTx+IQo7p7AmwyTKjYYChkJIxxaKPAF3BBbPSMzQyciTZFETfB5Oiyi9q2dknbYMRzYzgiHViHezSMxYDcuufqBXF9lc9Q/dvD79uUUCuPzbY9Dc/zydcDHTT/UIfCjB0B/9usT5yF2EDWDt24S81M+p9Et9KCz+Rlgw5oiD1Do0kEqH5CtgD+UhSOLqRl73/H0m7XV0hamW8qVMj8xflalOukRts3QCPYGk+uF1KY91Wyh3sr4wAbiFTMvELM3fOQDdRtKShb8JsxUd65PSowW9u0tECxOkxLMTg8482Yd7YXgzG5SrbU5/xhaHS100pgoBUGoWvQ8HhtnoTsS9p4IDUfmhqFKnBRas0bIWkpPhfiS2mKJk/QQ5YcCGKCD+J+kJALojS7eBhyQnNDaTWq7TqTkJqBgZZINX8GHWZWofscr7VG9UpMqWItKDXvTLN4GAt9Sacf/B8LCuGlqn75pU5Dq2VdCFQLgeSVuRE7UpSEUiETw5PrBNLAcKTKiFc8i1d4OnOQLSr3XltfMRHyYVMDJGVDlYIvE= X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFS:(13230028)(4636009)(376002)(136003)(346002)(39860400002)(396003)(451199021)(40470700004)(36840700001)(46966006)(235185007)(41300700001)(2906002)(8936002)(66899021)(5660300002)(40460700003)(44832011)(8676002)(82310400005)(36756003)(40480700001)(86362001)(2616005)(82740400003)(478600001)(186003)(6506007)(26005)(6512007)(336012)(107886003)(33964004)(70586007)(6916009)(70206006)(36860700001)(44144004)(6486002)(316002)(4326008)(356005)(83380400001)(81166007)(47076005)(4216001)(2700100001); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Jul 2023 09:37:35.6967 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 62df8633-ff9d-4e63-e9f8-08db7ecdcbe0 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: DBAEUR03FT053.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBBPR08MB5946 X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, FORGED_SPF_HELO, GIT_PATCH_0, KAM_DMARC_NONE, KAM_LOTSOFHASH, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE, UNPARSEABLE_RELAY 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: Tamar Christina via Gcc-patches From: Tamar Christina Reply-To: Tamar Christina 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?1770754126145900212?= X-GMAIL-MSGID: =?utf-8?q?1770754126145900212?= Hi All, Following on from Jakub's patch in g:de0ee9d14165eebb3d31c84e98260c05c3b33acb these two patches finishes the work fixing the regression and improves codegen. As explained in that commit, ifconvert sorts PHI args in increasing number of occurrences in order to reduce the number of comparisons done while traversing the tree. The remaining task that this patch fixes is dealing with the long chain of comparisons that can be created from phi nodes, particularly when they share any common successor (classical example is a diamond node). on a PHI-node the true and else branches carry a condition, true will carry `a` and false `~a`. The issue is that at the moment GCC tests both `a` and `~a` when the phi node has more than 2 arguments. Clearly this isn't needed. The deeper the nesting of phi nodes the larger the repetition. As an example, for foo (int *f, int d, int e) { for (int i = 0; i < 1024; i++) { int a = f[i]; int t; if (a < 0) t = 1; else if (a < e) t = 1 - a * d; else t = 0; f[i] = t; } } after Jakub's patch we generate: _7 = a_10 < 0; _21 = a_10 >= 0; _22 = a_10 < e_11(D); _23 = _21 & _22; _ifc__42 = _23 ? t_13 : 0; t_6 = _7 ? 1 : _ifc__42 but while better than before it is still inefficient, since in the false branch, where we know ~_7 is true, we still test _21. This leads to superfluous tests for every diamond node. After this patch we generate _7 = a_10 < 0; _22 = a_10 < e_11(D); _ifc__42 = _22 ? t_13 : 0; t_6 = _7 ? 1 : _ifc__42; Which correctly elides the test of _21. This is done by borrowing the vectorizer's helper functions to limit predicate mask usages. Ifcvt will chain conditionals on the false edge (unless specifically inverted) so this patch on creating cond a ? b : c, will register ~a when traversing c. If c is a conditional then c will be simplified to the smaller possible predicate given the assumptions we already know to be true. Bootstrapped Regtested on aarch64-none-linux-gnu and no issues. Not sure how to write a non-fragile testcase for this as the conditionals chosen depends on threading etc. Any Suggestions? Ok for master? Thanks, Tamar gcc/ChangeLog: PR tree-optimization/109154 * tree-if-conv.cc (gen_simplified_condition, gen_phi_nest_statement): New. (gen_phi_arg_condition, predicate_scalar_phi): Use it. --- inline copy of patch -- diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc index e342532a343a3c066142adeec5fdfaf736a653e5..16b36dd8b0226f796c1a3fc6d45a9059385e812b 100644 --- diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc index e342532a343a3c066142adeec5fdfaf736a653e5..16b36dd8b0226f796c1a3fc6d45a9059385e812b 100644 --- a/gcc/tree-if-conv.cc +++ b/gcc/tree-if-conv.cc @@ -1870,12 +1870,44 @@ convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi, return rhs; } +/* Generate a simplified conditional. */ + +static tree +gen_simplified_condition (tree cond, scalar_cond_masked_set_type &cond_set) +{ + /* Check if the value is already live in a previous branch. This resolves + nested conditionals from diamond PHI reductions. */ + if (TREE_CODE (cond) == SSA_NAME) + { + gimple *stmt = SSA_NAME_DEF_STMT (cond); + gassign *assign = NULL; + if ((assign = as_a (stmt)) + && gimple_assign_rhs_code (assign) == BIT_AND_EXPR) + { + tree arg1 = gimple_assign_rhs1 (assign); + tree arg2 = gimple_assign_rhs2 (assign); + if (cond_set.contains ({ arg1, 1 })) + arg1 = boolean_true_node; + else + arg1 = gen_simplified_condition (arg1, cond_set); + + if (cond_set.contains ({ arg2, 1 })) + arg2 = boolean_true_node; + else + arg2 = gen_simplified_condition (arg2, cond_set); + + cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, arg1, arg2); + } + } + return cond; +} + /* Produce condition for all occurrences of ARG in PHI node. Set *INVERT as to whether the condition is inverted. */ static tree -gen_phi_arg_condition (gphi *phi, vec *occur, - gimple_stmt_iterator *gsi, bool *invert) +gen_phi_arg_condition (gphi *phi, vec *occur, gimple_stmt_iterator *gsi, + scalar_cond_masked_set_type &cond_set, bool *invert) { int len; int i; @@ -1902,6 +1934,8 @@ gen_phi_arg_condition (gphi *phi, vec *occur, c = TREE_OPERAND (c, 0); *invert = true; } + + c = gen_simplified_condition (c, cond_set); c = force_gimple_operand_gsi (gsi, unshare_expr (c), true, NULL_TREE, true, GSI_SAME_STMT); if (cond != NULL_TREE) @@ -1913,11 +1947,79 @@ gen_phi_arg_condition (gphi *phi, vec *occur, } else cond = c; + + /* Register the new possibly simplified conditional. When more than 2 + entries in a phi node we chain entries in the false branch, so the + inverted condition is active. */ + scalar_cond_masked_key pred_cond ({ cond, 1 }); + if (!invert) + pred_cond.inverted_p = !pred_cond.inverted_p; + cond_set.add (pred_cond); } gcc_assert (cond != NULL_TREE); return cond; } +/* Create the smallest nested conditional possible. On pre-order we record + which conditionals are live, and on post-order rewrite the chain by removing + already active conditions. + + As an example we simplify: + + _7 = a_10 < 0; + _21 = a_10 >= 0; + _22 = a_10 < e_11(D); + _23 = _21 & _22; + _ifc__42 = _23 ? t_13 : 0; + t_6 = _7 ? 1 : _ifc__42 + + into + + _7 = a_10 < 0; + _22 = a_10 < e_11(D); + _ifc__42 = _22 ? t_13 : 0; + t_6 = _7 ? 1 : _ifc__42; + + which produces better code. */ + +static tree +gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi, + scalar_cond_masked_set_type &cond_set, tree type, + hash_map> &phi_arg_map, + gimple **res_stmt, tree lhs0, vec &args, + unsigned idx) +{ + if (idx == args.length ()) + return args[idx - 1]; + + vec *indexes = phi_arg_map.get (args[idx - 1]); + bool invert; + tree cond = gen_phi_arg_condition (phi, indexes, gsi, cond_set, &invert); + tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, phi_arg_map, + res_stmt, lhs0, args, idx + 1); + + unsigned prev = idx; + unsigned curr = prev - 1; + tree arg0 = args[curr]; + tree rhs, lhs; + if (idx > 1) + lhs = make_temp_ssa_name (type, NULL, "_ifc_"); + else + lhs = lhs0; + + if (invert) + rhs = fold_build_cond_expr (type, unshare_expr (cond), + arg1, arg0); + else + rhs = fold_build_cond_expr (type, unshare_expr (cond), + arg0, arg1); + gassign *new_stmt = gimple_build_assign (lhs, rhs); + gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); + update_stmt (new_stmt); + *res_stmt = new_stmt; + return lhs; +} + /* Replace a scalar PHI node with a COND_EXPR using COND as condition. This routine can handle PHI nodes with more than two arguments. @@ -1968,6 +2070,8 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) } bb = gimple_bb (phi); + /* Keep track of conditionals already seen. */ + scalar_cond_masked_set_type cond_set; if (EDGE_COUNT (bb->preds) == 2) { /* Predicate ordinary PHI node with 2 arguments. */ @@ -1976,6 +2080,7 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) first_edge = EDGE_PRED (bb, 0); second_edge = EDGE_PRED (bb, 1); cond = bb_predicate (first_edge->src); + cond_set.add ({ cond, 1 }); if (TREE_CODE (cond) == TRUTH_NOT_EXPR) std::swap (first_edge, second_edge); if (EDGE_COUNT (first_edge->src->succs) > 1) @@ -1988,7 +2093,9 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) } else cond = bb_predicate (first_edge->src); + /* Gimplify the condition to a valid cond-expr conditonal operand. */ + cond = gen_simplified_condition (cond, cond_set); cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true, NULL_TREE, true, GSI_SAME_STMT); true_bb = first_edge->src; @@ -2110,31 +2217,9 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) else { /* Common case. */ - vec *indexes; tree type = TREE_TYPE (gimple_phi_result (phi)); - tree lhs; - arg1 = args[args_len - 1]; - for (i = args_len - 1; i > 0; i--) - { - arg0 = args[i - 1]; - indexes = phi_arg_map.get (args[i - 1]); - if (i != 1) - lhs = make_temp_ssa_name (type, NULL, "_ifc_"); - else - lhs = res; - bool invert; - cond = gen_phi_arg_condition (phi, indexes, gsi, &invert); - if (invert) - rhs = fold_build_cond_expr (type, unshare_expr (cond), - arg1, arg0); - else - rhs = fold_build_cond_expr (type, unshare_expr (cond), - arg0, arg1); - new_stmt = gimple_build_assign (lhs, rhs); - gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); - update_stmt (new_stmt); - arg1 = lhs; - } + gen_phi_nest_statement (phi, gsi, cond_set, type, phi_arg_map, + &new_stmt, res, args, 1); } if (dump_file && (dump_flags & TDF_DETAILS)) --- a/gcc/tree-if-conv.cc +++ b/gcc/tree-if-conv.cc @@ -1870,12 +1870,44 @@ convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi, return rhs; } +/* Generate a simplified conditional. */ + +static tree +gen_simplified_condition (tree cond, scalar_cond_masked_set_type &cond_set) +{ + /* Check if the value is already live in a previous branch. This resolves + nested conditionals from diamond PHI reductions. */ + if (TREE_CODE (cond) == SSA_NAME) + { + gimple *stmt = SSA_NAME_DEF_STMT (cond); + gassign *assign = NULL; + if ((assign = as_a (stmt)) + && gimple_assign_rhs_code (assign) == BIT_AND_EXPR) + { + tree arg1 = gimple_assign_rhs1 (assign); + tree arg2 = gimple_assign_rhs2 (assign); + if (cond_set.contains ({ arg1, 1 })) + arg1 = boolean_true_node; + else + arg1 = gen_simplified_condition (arg1, cond_set); + + if (cond_set.contains ({ arg2, 1 })) + arg2 = boolean_true_node; + else + arg2 = gen_simplified_condition (arg2, cond_set); + + cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, arg1, arg2); + } + } + return cond; +} + /* Produce condition for all occurrences of ARG in PHI node. Set *INVERT as to whether the condition is inverted. */ static tree -gen_phi_arg_condition (gphi *phi, vec *occur, - gimple_stmt_iterator *gsi, bool *invert) +gen_phi_arg_condition (gphi *phi, vec *occur, gimple_stmt_iterator *gsi, + scalar_cond_masked_set_type &cond_set, bool *invert) { int len; int i; @@ -1902,6 +1934,8 @@ gen_phi_arg_condition (gphi *phi, vec *occur, c = TREE_OPERAND (c, 0); *invert = true; } + + c = gen_simplified_condition (c, cond_set); c = force_gimple_operand_gsi (gsi, unshare_expr (c), true, NULL_TREE, true, GSI_SAME_STMT); if (cond != NULL_TREE) @@ -1913,11 +1947,79 @@ gen_phi_arg_condition (gphi *phi, vec *occur, } else cond = c; + + /* Register the new possibly simplified conditional. When more than 2 + entries in a phi node we chain entries in the false branch, so the + inverted condition is active. */ + scalar_cond_masked_key pred_cond ({ cond, 1 }); + if (!invert) + pred_cond.inverted_p = !pred_cond.inverted_p; + cond_set.add (pred_cond); } gcc_assert (cond != NULL_TREE); return cond; } +/* Create the smallest nested conditional possible. On pre-order we record + which conditionals are live, and on post-order rewrite the chain by removing + already active conditions. + + As an example we simplify: + + _7 = a_10 < 0; + _21 = a_10 >= 0; + _22 = a_10 < e_11(D); + _23 = _21 & _22; + _ifc__42 = _23 ? t_13 : 0; + t_6 = _7 ? 1 : _ifc__42 + + into + + _7 = a_10 < 0; + _22 = a_10 < e_11(D); + _ifc__42 = _22 ? t_13 : 0; + t_6 = _7 ? 1 : _ifc__42; + + which produces better code. */ + +static tree +gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi, + scalar_cond_masked_set_type &cond_set, tree type, + hash_map> &phi_arg_map, + gimple **res_stmt, tree lhs0, vec &args, + unsigned idx) +{ + if (idx == args.length ()) + return args[idx - 1]; + + vec *indexes = phi_arg_map.get (args[idx - 1]); + bool invert; + tree cond = gen_phi_arg_condition (phi, indexes, gsi, cond_set, &invert); + tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, phi_arg_map, + res_stmt, lhs0, args, idx + 1); + + unsigned prev = idx; + unsigned curr = prev - 1; + tree arg0 = args[curr]; + tree rhs, lhs; + if (idx > 1) + lhs = make_temp_ssa_name (type, NULL, "_ifc_"); + else + lhs = lhs0; + + if (invert) + rhs = fold_build_cond_expr (type, unshare_expr (cond), + arg1, arg0); + else + rhs = fold_build_cond_expr (type, unshare_expr (cond), + arg0, arg1); + gassign *new_stmt = gimple_build_assign (lhs, rhs); + gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); + update_stmt (new_stmt); + *res_stmt = new_stmt; + return lhs; +} + /* Replace a scalar PHI node with a COND_EXPR using COND as condition. This routine can handle PHI nodes with more than two arguments. @@ -1968,6 +2070,8 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) } bb = gimple_bb (phi); + /* Keep track of conditionals already seen. */ + scalar_cond_masked_set_type cond_set; if (EDGE_COUNT (bb->preds) == 2) { /* Predicate ordinary PHI node with 2 arguments. */ @@ -1976,6 +2080,7 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) first_edge = EDGE_PRED (bb, 0); second_edge = EDGE_PRED (bb, 1); cond = bb_predicate (first_edge->src); + cond_set.add ({ cond, 1 }); if (TREE_CODE (cond) == TRUTH_NOT_EXPR) std::swap (first_edge, second_edge); if (EDGE_COUNT (first_edge->src->succs) > 1) @@ -1988,7 +2093,9 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) } else cond = bb_predicate (first_edge->src); + /* Gimplify the condition to a valid cond-expr conditonal operand. */ + cond = gen_simplified_condition (cond, cond_set); cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), true, NULL_TREE, true, GSI_SAME_STMT); true_bb = first_edge->src; @@ -2110,31 +2217,9 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) else { /* Common case. */ - vec *indexes; tree type = TREE_TYPE (gimple_phi_result (phi)); - tree lhs; - arg1 = args[args_len - 1]; - for (i = args_len - 1; i > 0; i--) - { - arg0 = args[i - 1]; - indexes = phi_arg_map.get (args[i - 1]); - if (i != 1) - lhs = make_temp_ssa_name (type, NULL, "_ifc_"); - else - lhs = res; - bool invert; - cond = gen_phi_arg_condition (phi, indexes, gsi, &invert); - if (invert) - rhs = fold_build_cond_expr (type, unshare_expr (cond), - arg1, arg0); - else - rhs = fold_build_cond_expr (type, unshare_expr (cond), - arg0, arg1); - new_stmt = gimple_build_assign (lhs, rhs); - gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); - update_stmt (new_stmt); - arg1 = lhs; - } + gen_phi_nest_statement (phi, gsi, cond_set, type, phi_arg_map, + &new_stmt, res, args, 1); } if (dump_file && (dump_flags & TDF_DETAILS)) From patchwork Fri Jul 7 09:37:47 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tamar Christina X-Patchwork-Id: 117050 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9f45:0:b0:3ea:f831:8777 with SMTP id v5csp3139515vqx; Fri, 7 Jul 2023 02:39:33 -0700 (PDT) X-Google-Smtp-Source: APBJJlGEIFTFVyuTwQ1/HEZUl2EB4Uhk6hcYg/PdgWWGIeDKX/WEnDp+GUQk8oNW/uszdvxphH8t X-Received: by 2002:a17:906:51a:b0:982:2586:f85 with SMTP id j26-20020a170906051a00b0098225860f85mr2941033eja.65.1688722773332; Fri, 07 Jul 2023 02:39:33 -0700 (PDT) Received: from server2.sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id i17-20020a50fc11000000b0051e33b5ee68si1692826edr.250.2023.07.07.02.39.33 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 07 Jul 2023 02:39:33 -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=Pviamwxo; arc=fail (signature failed); 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 763833870C00 for ; Fri, 7 Jul 2023 09:39:00 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 763833870C00 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1688722740; bh=ZojBfyEweNqy1C0XWVup+buF34pc81clKo7gnKeFrKU=; h=Date:To:Cc:Subject:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=Pviamwxo3zmPo3fQK7YYn4Vp2SSMLK752O0l9vfjdkFmJEUGOqXSj1Hx4h2VLlkOi I4/7nPw4Xx9LJDJaJcMloNPlEG+wfRw7hLHL1ya8OWPn3/PbN2EpuFCs4MbKavQ1C/ VaBQvUIo+uQJskqmujznx08FjGMWpYutNQHe8qOc= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2044.outbound.protection.outlook.com [40.107.21.44]) by sourceware.org (Postfix) with ESMTPS id DC4FA386077D for ; Fri, 7 Jul 2023 09:38:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DC4FA386077D Received: from AS8PR05CA0008.eurprd05.prod.outlook.com (2603:10a6:20b:311::13) by GV1PR08MB8034.eurprd08.prod.outlook.com (2603:10a6:150:99::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.17; Fri, 7 Jul 2023 09:37:59 +0000 Received: from AM7EUR03FT003.eop-EUR03.prod.protection.outlook.com (2603:10a6:20b:311:cafe::fe) by AS8PR05CA0008.outlook.office365.com (2603:10a6:20b:311::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.25 via Frontend Transport; Fri, 7 Jul 2023 09:37:59 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by AM7EUR03FT003.mail.protection.outlook.com (100.127.140.227) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.25 via Frontend Transport; Fri, 7 Jul 2023 09:37:59 +0000 Received: ("Tessian outbound d7adc65d10b4:v145"); Fri, 07 Jul 2023 09:37:58 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 6f8502e00dd401cc X-CR-MTA-TID: 64aa7808 Received: from eb5aa81b87fd.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 40465E34-9471-4ECF-91A7-CA36423FCC84.1; Fri, 07 Jul 2023 09:37:51 +0000 Received: from EUR03-AM7-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id eb5aa81b87fd.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Fri, 07 Jul 2023 09:37:51 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=BRLWl1KeusFxf6GmvwxSkeonbN9OTTNh507JyyGNqd73MLR7ZMv0h0LLtjGrNichdX5UCzR+EDZKhAtpIb6gXkVfSlf6/slFPb0PyNraKufLtMM/Fr0wzlzRHkA4IXKPNiTiv8Ri7wAkZRRjtj6NyHTpQhNwpJGqxsaSDp1FS3jp/p0KKm7sMYIaxuxpF2xo9zvbUgVU0Vn7Vdv1nIicI1JaNNascMZnoPBUqUSA3wBU1izpsnK7YuaTeoD1My0vdyIefbxIugQoVeSW91NDgf/v8prM696Mz+IQ0JA9WUoD46VZavuZi3HMOO5QfWEPKVQcsuaagnZ7DNOLPR0ZMg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=ZojBfyEweNqy1C0XWVup+buF34pc81clKo7gnKeFrKU=; b=G/x8O3U954MDA1f/heLuG8DhirNEYThcB8nwL94hqtBKX3bRh+6SnpMoXaRi3Qg2cozVaqPZvLvjBxFVHY6QmcAzwdz8SRY39Lxo1OD5Q3PeUKVRt06E5IhlfXhYaWhSlldiPagcUt50jHLJuNmDK1yXT16ynYIlQCUIeBnpTOhlZt8PNGbL8ywgKSaJlyU0rn8y75z0y4XtpsmbdT1BGDU5DQ5rOcDhHJYO+4yWfaVmE+tWWsTxGYvD685wtqYcYGjBaj9UK4g2zxqaCmxTlXb/FLtoGf/3bO6FFSt/qbqn7R11tkrV/IuUEn2YGui9p+uwK7PjyxFcjVuAOOL07g== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; Received: from VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) by DU0PR08MB8231.eurprd08.prod.outlook.com (2603:10a6:10:3b0::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.6565.17; Fri, 7 Jul 2023 09:37:49 +0000 Received: from VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::2301:1cde:cfe7:eaf0]) by VI1PR08MB5325.eurprd08.prod.outlook.com ([fe80::2301:1cde:cfe7:eaf0%6]) with mapi id 15.20.6565.016; Fri, 7 Jul 2023 09:37:49 +0000 Date: Fri, 7 Jul 2023 10:37:47 +0100 To: gcc-patches@gcc.gnu.org Cc: nd@arm.com, rguenther@suse.de, jlaw@ventanamicro.com Subject: [PATCH 2/2]middle-end ifcvt: Sort PHI arguments not only occurrences but also complexity [PR109154] Message-ID: Content-Disposition: inline In-Reply-To: X-ClientProxiedBy: LO4P123CA0490.GBRP123.PROD.OUTLOOK.COM (2603:10a6:600:1ab::9) To VI1PR08MB5325.eurprd08.prod.outlook.com (2603:10a6:803:13e::17) MIME-Version: 1.0 X-MS-TrafficTypeDiagnostic: VI1PR08MB5325:EE_|DU0PR08MB8231:EE_|AM7EUR03FT003:EE_|GV1PR08MB8034:EE_ X-MS-Office365-Filtering-Correlation-Id: 407ee748-c53b-4b21-3250-08db7ecdd9d2 x-checkrecipientrouted: true NoDisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: /J7mHbrFyUUGCWwiu4hJVXz98srQaJhmXeF2pC84Bf1uni6EKhQoGwOVms2wXAhwELnavd1Qyo4bor1aWEbBZQkB2D5ms9/k7MYXY6ejTByO7Z6mU/sed84rCOGKqSrxWxCkvxGEuvyF28qL0wY46rvJG/sgUKol9PNq5PPDjLT69t5Lg6HUngSPI40K4/A3j1Wav5Mukfui4H7cX1qNaMpHkKBBw4AI5kaSwjtNhUbsx1wyq+fRr9OZ3ncpV2L06m0CbAP2ymcxG3WkbzrxAqfQt+iAHpVz2k+LE86wrKMYOQG0SbuGHaVE5f6L11XFBLrxA8vdhLWQFCvd+oJLS5rjWD74nR1UPgdv/BB8TAqviik7HLtZINYocMzGI9OqoYytM5r+W/dvGTWBHG1udb3t9rd08LM0voBmgR1blKNzLoOtXT7bFWl/OOOTp4HPpD24/Cpbo0E8JcOURyXfUOyG0jqCEhGD8/5GfuzkpP6IwMrUlfU7HMaCTeHK4fdPcs6q8GSCOhwHLuNzB11NPBa/ZozE9noJl8Hb581eP5pkHIHMROb387Cor/Q8sHq/yzoZpEiRMg2UTrLfc52sLS6vxkklrtljUa7i46353tsqrKwOUqaE1vHyo3/15mpK X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1PR08MB5325.eurprd08.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230028)(4636009)(396003)(136003)(39860400002)(346002)(366004)(376002)(451199021)(36756003)(44832011)(5660300002)(86362001)(2906002)(235185007)(6512007)(186003)(83380400001)(6506007)(26005)(66476007)(6916009)(44144004)(33964004)(478600001)(6486002)(66556008)(2616005)(38100700002)(316002)(66946007)(4326008)(8676002)(8936002)(41300700001)(2700100001); DIR:OUT; SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: DU0PR08MB8231 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: AM7EUR03FT003.eop-EUR03.prod.protection.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: a1808c8f-4b9a-43e3-8886-08db7ecdd3f1 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: AKRflyec2F832WMR+ENBWTPDlpqIy/PNWin9MYq+/jI6wAW9cbHXtjOgZkXd65rVjohaKT7BKsEuNSnC/wZ4jixb/awBJfRIfxXiu0PAcsghJtlr8iJ9grITfidbYAlTNRuQRgdLMQK+iAAJUJjCsP6W9LpHRjULjYiCw2EmbJMgtbE0Dt4MoWkrIyyxJqsovd2hGpwOt6ZnNuxJsgG/wcwy0LCZ7twi3+UqNdS8wuAzgpbgG3qrLbDY2gickDV5uHkTTNxQf4HaJDDde3QqGYMGSwTV/x26cnGJACXxdY5b4DNBQF1XNBTzaauWxeCFUFr6mBgvzYfsTPh5uo5FIos2IGrLTT6uskD7tpaI4VHApmiD63adrGGUkoayWwYJxBj5ft6ETiS0IdNTSItCKfhl5HXPT7vljW6clywfkiWFRGXBGHNSnlUwE/nsVaCa/boMP4W9wlrqZW2kshVYn5BvD8SsoCZFtz7oRwk5CElYXBwVh1hsAUP6HYb7zuUuFHiBXTgef3v+gRmm+xwP7svNO9ODjYBchWAh0mvJRp6ikeW0OXVjrs1VX14/P+5VgxdaiqQ6F7tPQmlnbBvjq8x16+YS2rKsykypp6HarjuWc/HJBfCGi9wgzfAXrK/xbn6G1+W6V3vnOlnQO4BSh8pJmYQccIXrjMX+Rc3so7+unYQNvsPnrCCwAIc517AurXF+Uu6uhRaNOCQIBG6rFbvMlCe2pgqDY5q/ClpJNY8jal1UkI30ppFoJvb1+f4qSisLcJmXfvcmTnaK86aRjA== X-Forefront-Antispam-Report: CIP:63.35.35.123; CTRY:IE; LANG:en; SCL:1; SRV:; IPV:CAL; SFV:NSPM; H:64aa7808-outbound-1.mta.getcheckrecipient.com; PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com; CAT:NONE; SFS:(13230028)(4636009)(396003)(39860400002)(376002)(346002)(136003)(451199021)(40470700004)(46966006)(36840700001)(36860700001)(6486002)(33964004)(478600001)(70586007)(70206006)(44144004)(40460700003)(47076005)(83380400001)(86362001)(36756003)(40480700001)(356005)(82310400005)(2906002)(6512007)(2616005)(107886003)(6506007)(186003)(336012)(316002)(82740400003)(81166007)(4326008)(26005)(41300700001)(6916009)(5660300002)(8936002)(8676002)(44832011)(235185007)(2700100001); DIR:OUT; SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Jul 2023 09:37:59.0102 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 407ee748-c53b-4b21-3250-08db7ecdd9d2 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d; Ip=[63.35.35.123]; Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: AM7EUR03FT003.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: GV1PR08MB8034 X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, FORGED_SPF_HELO, GIT_PATCH_0, KAM_DMARC_NONE, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_PASS, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE, UNPARSEABLE_RELAY 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: Tamar Christina via Gcc-patches From: Tamar Christina Reply-To: Tamar Christina 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?1770754170729272425?= X-GMAIL-MSGID: =?utf-8?q?1770754170729272425?= Hi All, This patch builds on the previous patch by fixing another issue with the way ifcvt currently picks which branches to test. The issue with the current implementation is while it sorts for occurrences of the argument, it doesn't check for complexity of the arguments. As an example: [local count: 528603100]: ... if (distbb_75 >= 0.0) goto ; [59.00%] else goto ; [41.00%] [local count: 216727269]: ... goto ; [100.00%] [local count: 311875831]: ... if (distbb_75 < iftmp.0_98) goto ; [20.00%] else goto ; [80.00%] [local count: 62375167]: ... [local count: 528603100]: # prephitmp_175 = PHI <_173(18), 0.0(17), _174(16)> All tree arguments to the PHI have the same number of occurrences, namely 1, however it makes a big difference which comparison we test first. Sorting only on occurrences we'll pick the compares coming from BB 18 and BB 17, This means we end up generating 4 comparisons, while 2 would have been enough. By keeping track of the "complexity" of the COND in each BB, (i.e. the number of comparisons needed to traverse from the start [BB 15] to end [BB 19]) and using a key tuple of we end up selecting the compare from BB 16 and BB 18 first. BB 16 only requires 1 compare, and BB 18, after we test BB 16 also only requires one additional compare. This change paired with the one previous above results in the optimal 2 compares. For deep nesting, i.e. for ... _79 = vr_15 > 20; _80 = _68 & _79; _82 = vr_15 <= 20; _83 = _68 & _82; _84 = vr_15 < -20; _85 = _73 & _84; _87 = vr_15 >= -20; _88 = _73 & _87; _ifc__111 = _55 ? 10 : 12; _ifc__112 = _70 ? 7 : _ifc__111; _ifc__113 = _85 ? 8 : _ifc__112; _ifc__114 = _88 ? 9 : _ifc__113; _ifc__115 = _45 ? 1 : _ifc__114; _ifc__116 = _63 ? 3 : _ifc__115; _ifc__117 = _65 ? 4 : _ifc__116; _ifc__118 = _83 ? 6 : _ifc__117; _ifc__119 = _60 ? 2 : _ifc__118; _ifc__120 = _43 ? 13 : _ifc__119; _ifc__121 = _75 ? 11 : _ifc__120; vw_1 = _80 ? 5 : _ifc__121; Most of the comparisons are still needed because the chain of occurrences to not negate eachother. i.e. _80 is _73 & vr_15 >= -20 and _85 is _73 & vr_15 < -20. clearly given _73 needs to be true in both branches, the only additional test needed is on vr_15, where the one test is the negation of the other. So we don't need to do the comparison of _73 twice. The changes in the patch reduces the overall number of compares by one, but has a bigger effect on the dependency chain. Previously we would generate 5 instructions chain: cmple p7.s, p4/z, z29.s, z30.s cmpne p7.s, p7/z, z29.s, #0 cmple p6.s, p7/z, z31.s, z30.s cmpge p6.s, p6/z, z27.s, z25.s cmplt p15.s, p6/z, z28.s, z21.s as the longest chain. With this patch we generate 3: cmple p7.s, p3/z, z27.s, z30.s cmpne p7.s, p7/z, z27.s, #0 cmpgt p7.s, p7/z, z31.s, z30.s and I don't think (x <= y) && (x != 0) && (z > y) can be reduced further. Bootstrapped and Regtested on aarch64-none-linux-gnu and no issues. Not sure how to write a non-fragile testcase for this as the conditionals chosen depends on threading etc. Any Suggestions? Ok for master? Thanks, Tamar gcc/ChangeLog: PR tree-optimization/109154 * tree-if-conv.cc (INCLUDE_ALGORITHM): Include. (struct bb_predicate): Add no_predicate_stmts. (set_bb_predicate): Increase predicate count. (set_bb_predicate_gimplified_stmts): Conditionally initialize no_predicate_stmts. (get_bb_num_predicate_stmts): New. (init_bb_predicate): Initialzie no_predicate_stmts. (release_bb_predicate): Cleanup no_predicate_stmts. (insert_gimplified_predicates): Preserve no_predicate_stmts. --- inline copy of patch -- diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc index 16b36dd8b0226f796c1a3fc6d45a9059385e812b..0ed50d99c46f99a4d1ea0e827ee2b2a3f494b2da 100644 --- diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc index 16b36dd8b0226f796c1a3fc6d45a9059385e812b..0ed50d99c46f99a4d1ea0e827ee2b2a3f494b2da 100644 --- a/gcc/tree-if-conv.cc +++ b/gcc/tree-if-conv.cc @@ -80,6 +80,7 @@ along with GCC; see the file COPYING3. If not see :; */ +#define INCLUDE_ALGORITHM #include "config.h" #include "system.h" #include "coretypes.h" @@ -231,6 +232,10 @@ struct bb_predicate { recorded here, in order to avoid the duplication of computations that occur in previous conditions. See PR44483. */ gimple_seq predicate_gimplified_stmts; + + /* Records the number of statements recorded into + PREDICATE_GIMPLIFIED_STMTS. */ + unsigned no_predicate_stmts; }; /* Returns true when the basic block BB has a predicate. */ @@ -254,10 +259,16 @@ bb_predicate (basic_block bb) static inline void set_bb_predicate (basic_block bb, tree cond) { + auto aux = (struct bb_predicate *) bb->aux; gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR && is_gimple_val (TREE_OPERAND (cond, 0))) || is_gimple_val (cond)); - ((struct bb_predicate *) bb->aux)->predicate = cond; + aux->predicate = cond; + aux->no_predicate_stmts++; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Recording block %d value %d\n", bb->index, + aux->no_predicate_stmts); } /* Returns the sequence of statements of the gimplification of the @@ -270,12 +281,16 @@ bb_predicate_gimplified_stmts (basic_block bb) } /* Sets the sequence of statements STMTS of the gimplification of the - predicate for basic block BB. */ + predicate for basic block BB. If PRESERVE_COUNTS then don't clear the predicate + counts. */ static inline void -set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) +set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts, + bool preserve_counts) { ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts; + if (stmts == NULL && !preserve_counts) + ((struct bb_predicate *) bb->aux)->no_predicate_stmts = 0; } /* Adds the sequence of statements STMTS to the sequence of statements @@ -296,18 +311,28 @@ add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) gimple *stmt = gsi_stmt (gsi); delink_stmt_imm_use (stmt); gimple_set_modified (stmt, true); + ((struct bb_predicate *) bb->aux)->no_predicate_stmts++; } gimple_seq_add_seq_without_update (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts); } +/* Return the number of statements the predicate of the basic block consists + of. */ + +static inline unsigned +get_bb_num_predicate_stmts (basic_block bb) +{ + return ((struct bb_predicate *) bb->aux)->no_predicate_stmts; +} + /* Initializes to TRUE the predicate of basic block BB. */ static inline void init_bb_predicate (basic_block bb) { bb->aux = XNEW (struct bb_predicate); - set_bb_predicate_gimplified_stmts (bb, NULL); + set_bb_predicate_gimplified_stmts (bb, NULL, false); set_bb_predicate (bb, boolean_true_node); } @@ -327,7 +352,7 @@ release_bb_predicate (basic_block bb) /* Discard them. */ gimple_seq_discard (stmts); - set_bb_predicate_gimplified_stmts (bb, NULL); + set_bb_predicate_gimplified_stmts (bb, NULL, false); } } @@ -2041,7 +2066,6 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) tree rhs, res, arg0, arg1, op0, op1, scev; tree cond; unsigned int index0; - unsigned int max, args_len; edge e; basic_block bb; unsigned int i; @@ -2145,7 +2169,6 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) bool swap = false; hash_map > phi_arg_map; unsigned int num_args = gimple_phi_num_args (phi); - int max_ind = -1; /* Vector of different PHI argument values. */ auto_vec args (num_args); @@ -2160,28 +2183,38 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) phi_arg_map.get_or_insert (arg).safe_push (i); } - /* Determine element with max number of occurrences. */ - max_ind = -1; - max = 1; - args_len = args.length (); - for (i = 0; i < args_len; i++) + /* Determine element with max number of occurrences and complexity. Looking at only + number of occurrences as a measure for complexity isn't enough as all usages can + be unique but the comparisons to reach the PHI node differ per branch. */ + typedef std::pair > ArgEntry; + auto_vec argsKV; + for (i = 0; i < args.length (); i++) { - unsigned int len; - if ((len = phi_arg_map.get (args[i])->length ()) > max) + unsigned int len = 0; + for (int index : phi_arg_map.get (args[i])) { - max_ind = (int) i; - max = len; + edge e = gimple_phi_arg_edge (phi, index); + len += get_bb_num_predicate_stmts (e->src); } + + unsigned occur = phi_arg_map.get (args[i])->length (); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur); + argsKV.safe_push ({ args[i], { len, occur }}); } - /* Put element with max number of occurences to the end of ARGS. */ - if (max_ind != -1 && max_ind + 1 != (int) args_len) - std::swap (args[args_len - 1], args[max_ind]); + /* Sort elements based on rankings ARGS. */ + std::sort(argsKV.begin(), argsKV.end(), [](ArgEntry &left, ArgEntry &right) { + return left.second < right.second; + }); + + for (i = 0; i < args.length (); i++) + args[i] = argsKV[i].first; /* Handle one special case when number of arguments with different values is equal 2 and one argument has the only occurrence. Such PHI can be handled as if would have only 2 arguments. */ - if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1) + if (args.length () == 2 && phi_arg_map.get (args[0])->length () == 1) { vec *indexes; indexes = phi_arg_map.get (args[0]); @@ -2317,7 +2350,7 @@ insert_gimplified_predicates (loop_p loop) } /* Once the sequence is code generated, set it to NULL. */ - set_bb_predicate_gimplified_stmts (bb, NULL); + set_bb_predicate_gimplified_stmts (bb, NULL, true); } } } --- a/gcc/tree-if-conv.cc +++ b/gcc/tree-if-conv.cc @@ -80,6 +80,7 @@ along with GCC; see the file COPYING3. If not see :; */ +#define INCLUDE_ALGORITHM #include "config.h" #include "system.h" #include "coretypes.h" @@ -231,6 +232,10 @@ struct bb_predicate { recorded here, in order to avoid the duplication of computations that occur in previous conditions. See PR44483. */ gimple_seq predicate_gimplified_stmts; + + /* Records the number of statements recorded into + PREDICATE_GIMPLIFIED_STMTS. */ + unsigned no_predicate_stmts; }; /* Returns true when the basic block BB has a predicate. */ @@ -254,10 +259,16 @@ bb_predicate (basic_block bb) static inline void set_bb_predicate (basic_block bb, tree cond) { + auto aux = (struct bb_predicate *) bb->aux; gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR && is_gimple_val (TREE_OPERAND (cond, 0))) || is_gimple_val (cond)); - ((struct bb_predicate *) bb->aux)->predicate = cond; + aux->predicate = cond; + aux->no_predicate_stmts++; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Recording block %d value %d\n", bb->index, + aux->no_predicate_stmts); } /* Returns the sequence of statements of the gimplification of the @@ -270,12 +281,16 @@ bb_predicate_gimplified_stmts (basic_block bb) } /* Sets the sequence of statements STMTS of the gimplification of the - predicate for basic block BB. */ + predicate for basic block BB. If PRESERVE_COUNTS then don't clear the predicate + counts. */ static inline void -set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) +set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts, + bool preserve_counts) { ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts; + if (stmts == NULL && !preserve_counts) + ((struct bb_predicate *) bb->aux)->no_predicate_stmts = 0; } /* Adds the sequence of statements STMTS to the sequence of statements @@ -296,18 +311,28 @@ add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) gimple *stmt = gsi_stmt (gsi); delink_stmt_imm_use (stmt); gimple_set_modified (stmt, true); + ((struct bb_predicate *) bb->aux)->no_predicate_stmts++; } gimple_seq_add_seq_without_update (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts); } +/* Return the number of statements the predicate of the basic block consists + of. */ + +static inline unsigned +get_bb_num_predicate_stmts (basic_block bb) +{ + return ((struct bb_predicate *) bb->aux)->no_predicate_stmts; +} + /* Initializes to TRUE the predicate of basic block BB. */ static inline void init_bb_predicate (basic_block bb) { bb->aux = XNEW (struct bb_predicate); - set_bb_predicate_gimplified_stmts (bb, NULL); + set_bb_predicate_gimplified_stmts (bb, NULL, false); set_bb_predicate (bb, boolean_true_node); } @@ -327,7 +352,7 @@ release_bb_predicate (basic_block bb) /* Discard them. */ gimple_seq_discard (stmts); - set_bb_predicate_gimplified_stmts (bb, NULL); + set_bb_predicate_gimplified_stmts (bb, NULL, false); } } @@ -2041,7 +2066,6 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) tree rhs, res, arg0, arg1, op0, op1, scev; tree cond; unsigned int index0; - unsigned int max, args_len; edge e; basic_block bb; unsigned int i; @@ -2145,7 +2169,6 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) bool swap = false; hash_map > phi_arg_map; unsigned int num_args = gimple_phi_num_args (phi); - int max_ind = -1; /* Vector of different PHI argument values. */ auto_vec args (num_args); @@ -2160,28 +2183,38 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) phi_arg_map.get_or_insert (arg).safe_push (i); } - /* Determine element with max number of occurrences. */ - max_ind = -1; - max = 1; - args_len = args.length (); - for (i = 0; i < args_len; i++) + /* Determine element with max number of occurrences and complexity. Looking at only + number of occurrences as a measure for complexity isn't enough as all usages can + be unique but the comparisons to reach the PHI node differ per branch. */ + typedef std::pair > ArgEntry; + auto_vec argsKV; + for (i = 0; i < args.length (); i++) { - unsigned int len; - if ((len = phi_arg_map.get (args[i])->length ()) > max) + unsigned int len = 0; + for (int index : phi_arg_map.get (args[i])) { - max_ind = (int) i; - max = len; + edge e = gimple_phi_arg_edge (phi, index); + len += get_bb_num_predicate_stmts (e->src); } + + unsigned occur = phi_arg_map.get (args[i])->length (); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur); + argsKV.safe_push ({ args[i], { len, occur }}); } - /* Put element with max number of occurences to the end of ARGS. */ - if (max_ind != -1 && max_ind + 1 != (int) args_len) - std::swap (args[args_len - 1], args[max_ind]); + /* Sort elements based on rankings ARGS. */ + std::sort(argsKV.begin(), argsKV.end(), [](ArgEntry &left, ArgEntry &right) { + return left.second < right.second; + }); + + for (i = 0; i < args.length (); i++) + args[i] = argsKV[i].first; /* Handle one special case when number of arguments with different values is equal 2 and one argument has the only occurrence. Such PHI can be handled as if would have only 2 arguments. */ - if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1) + if (args.length () == 2 && phi_arg_map.get (args[0])->length () == 1) { vec *indexes; indexes = phi_arg_map.get (args[0]); @@ -2317,7 +2350,7 @@ insert_gimplified_predicates (loop_p loop) } /* Once the sequence is code generated, set it to NULL. */ - set_bb_predicate_gimplified_stmts (bb, NULL); + set_bb_predicate_gimplified_stmts (bb, NULL, true); } } }