From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Z2fyp0Ici4z7AJ7TUwMTBxsFISW9e9g86BIzrUoSWcE=; b=CTkQJQohtm6eefiqWwFi4cJT5/WqBa0JWF6TUVNT9/lYbYY1JNUrpZhwVW/oZLmWHzySmd/Vdh//Ep5ltfHf45n4TFYI+t68rpM/q7Tz5WC37+HP7rqtosnBfUK2LtSFhDLLTn1o4uKMUcJVhRKswBuaJE85pQvT6VhbKTJwYYM= 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 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Z2fyp0Ici4z7AJ7TUwMTBxsFISW9e9g86BIzrUoSWcE=; b=CTkQJQohtm6eefiqWwFi4cJT5/WqBa0JWF6TUVNT9/lYbYY1JNUrpZhwVW/oZLmWHzySmd/Vdh//Ep5ltfHf45n4TFYI+t68rpM/q7Tz5WC37+HP7rqtosnBfUK2LtSFhDLLTn1o4uKMUcJVhRKswBuaJE85pQvT6VhbKTJwYYM= 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 From: Tamar Christina 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-Type: multipart/mixed; boundary="z6b2Bc6/hqfnudp9" 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 List-Id: --z6b2Bc6/hqfnudp9 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline 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 --- 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)) -- --z6b2Bc6/hqfnudp9 Content-Type: text/plain; charset=utf-8 Content-Disposition: attachment; filename="rb17550.patch" 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)) --z6b2Bc6/hqfnudp9--