From patchwork Thu Oct 17 00:50:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andi Kleen X-Patchwork-Id: 1998326 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=intel.com header.i=@intel.com header.a=rsa-sha256 header.s=Intel header.b=S3Um7jiO; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XTTmq3m83z1xw2 for ; Thu, 17 Oct 2024 11:51:39 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5E419385840B for ; Thu, 17 Oct 2024 00:51:37 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.9]) by sourceware.org (Postfix) with ESMTPS id 942033858D20; Thu, 17 Oct 2024 00:51:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 942033858D20 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=linux.intel.com Authentication-Results: sourceware.org; spf=none smtp.mailfrom=linux.intel.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 942033858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=192.198.163.9 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729126279; cv=none; b=h25hgGMOUg1qkpw7PrsGCYimNumwBr5ZR8a/vJrxvrtVGrDes/s+B4R6NZI/ISq6UWoHXgeXWpA9DyjAbI5yseG7KnonrYNgk6Kz0f9TF78s8kQlrHnPKUIYKXt9epEHln5FZK/NXA3+PDioTQBSfYcTV3kmSn4OtCAHUQ6U0yI= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729126279; c=relaxed/simple; bh=pDHzjiLhSvaxvUb9vKmwFFz+kf8lUnXCX0lHODCr1EA=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=wHZu29qJgA46LgLPld3lJ1RmzFPTDxj02YMUqZsQ6NTFaCxXyjmKBWdGCP1yJIrtbd9k7kHXr9sxWfe2OYr8rcN5xGYvv7flNnnpzEPkE9tU646LK/wF5BLmQrgPovmR6IofYLzZnJBSzfqCrtTXykvckxMxhC3RDWCePMLMKD0= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1729126268; x=1760662268; h=from:to:cc:subject:date:message-id:mime-version: content-transfer-encoding; bh=pDHzjiLhSvaxvUb9vKmwFFz+kf8lUnXCX0lHODCr1EA=; b=S3Um7jiOZDIiAJ1whspRHpVeWOgNGd99E8NPgMgDpBbj/otTf4JyhDDG gOljFQ4FzHCfK6D88EcsA8kBi1md6/0s/qLPFJU6I5ThZrcESTR+qYpCM StlACepyXBohOdKs8Dlb5nW5c130jiSUuJ3YIJF9wkVa7RDoPF0CUhqNs WEFdgNfMSph+wAvtOuhUQCyzGH4hbxAhmqodWXedh53AbT+ig0hd/Rdvu 4pAH4mHIUZWAtx1E22qwIyYUDX4IWdxZF6sT3/wO2O5phi7+ARjlZCaGk 9JNahxurQFgbxr5bvxfSxPWWVC0HV7t6tTmiIyyxxnnHSNjcdskCLBGTe g==; X-CSE-ConnectionGUID: 7WnKcKXdSeu1NhCSzl4Rlg== X-CSE-MsgGUID: m3G/6FdnTo2U0JfR02VUSg== X-IronPort-AV: E=McAfee;i="6700,10204,11226"; a="39232650" X-IronPort-AV: E=Sophos;i="6.11,209,1725346800"; d="scan'208";a="39232650" Received: from fmviesa006.fm.intel.com ([10.60.135.146]) by fmvoesa103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 16 Oct 2024 17:51:06 -0700 X-CSE-ConnectionGUID: KGDIIChuRze/9kP3jPPGrw== X-CSE-MsgGUID: O8cdhr6FQCSFQu5895L94w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,209,1725346800"; d="scan'208";a="78006341" Received: from tassilo.jf.intel.com ([10.54.38.190]) by fmviesa006-auth.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 16 Oct 2024 17:51:06 -0700 From: Andi Kleen To: gcc-patches@gcc.gnu.org Cc: Andi Kleen Subject: [PATCH 1/2] Disable -fbit-tests and -fjump-tables at -O0 Date: Wed, 16 Oct 2024 17:50:58 -0700 Message-ID: <20241017005100.3620061-1-ak@linux.intel.com> X-Mailer: git-send-email 2.46.2 MIME-Version: 1.0 X-Spam-Status: No, score=-10.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, KAM_NUMSUBJECT, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org From: Andi Kleen gcc/ChangeLog: * common.opt: Enable -fbit-tests and -fjump-tables only at -O1. * tree-switch-conversion.h (jump_table_cluster::is_enabled): Dito. --- gcc/common.opt | 4 ++-- gcc/tree-switch-conversion.h | 5 +++-- 2 files changed, 5 insertions(+), 4 deletions(-) diff --git a/gcc/common.opt b/gcc/common.opt index 12b25ff486de..4af7a94fea42 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2189,11 +2189,11 @@ Common Var(flag_ivopts) Init(1) Optimization Optimize induction variables on trees. fjump-tables -Common Var(flag_jump_tables) Init(1) Optimization +Common Var(flag_jump_tables) Init(-1) Optimization Use jump tables for sufficiently large switch statements. fbit-tests -Common Var(flag_bit_tests) Init(1) Optimization +Common Var(flag_bit_tests) Init(-1) Optimization Use bit tests for sufficiently large switch statements. fkeep-inline-functions diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index 6468995eb316..fbfd7ff7b3ff 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -442,7 +442,7 @@ public: /* Return whether bit test expansion is allowed. */ static inline bool is_enabled (void) { - return flag_bit_tests; + return flag_bit_tests >= 0 ? flag_bit_tests : (optimize >= 1); } /* True when the jump table handles an entire switch statement. */ @@ -524,7 +524,8 @@ bool jump_table_cluster::is_enabled (void) over-ruled us, we really have no choice. */ if (!targetm.have_casesi () && !targetm.have_tablejump ()) return false; - if (!flag_jump_tables) + int flag = flag_jump_tables >= 0 ? flag_jump_tables : (optimize >= 1); + if (!flag) return false; #ifndef ASM_OUTPUT_ADDR_DIFF_ELT if (flag_pic) From patchwork Thu Oct 17 00:50:59 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andi Kleen X-Patchwork-Id: 1998327 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=intel.com header.i=@intel.com header.a=rsa-sha256 header.s=Intel header.b=c6isYN4S; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XTTnl2C0Bz1xw2 for ; Thu, 17 Oct 2024 11:52:27 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 83C5F3858CD1 for ; Thu, 17 Oct 2024 00:52:25 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mgamail.intel.com (mgamail.intel.com [192.198.163.9]) by sourceware.org (Postfix) with ESMTPS id 01DCC3858D3C; Thu, 17 Oct 2024 00:51:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 01DCC3858D3C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=linux.intel.com Authentication-Results: sourceware.org; spf=none smtp.mailfrom=linux.intel.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 01DCC3858D3C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=192.198.163.9 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729126291; cv=none; b=qYhHQTwrgxYKk4MOi8VNqtR5KCJrXV+6TIGK0i0xmzIAA9CjBEkrTPfb2166a4S7WsaRsGzOpZwcFzekiBi0JBI6qVOrNDLDe6bN5qdI/rPmryPfAwE/ygDnpGnr7B5AuxNzOAIc7s7rs5mR1nyJP9SIzSjMgytSN3en3m/giGI= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1729126291; c=relaxed/simple; bh=ry5jXfElUh7ESCl79JzkcSXMMA6670Xx/MkF5QQ8gpE=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=tlNlKjFXB1czG9NoFOpNa6HV4DAREo+uuofAAwM8iMKpZ7cTu+ILFtTMF60SWINS7ndZeD9F8fOi7euw35Dcr1OZIUlH5rnRhR2XCTI9XTybqYYXQicepLQkbqU9SsYcw+he8ghO2YZSv0l/s6XesN65J2POXOlMkxpbe5rJUA8= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1729126280; x=1760662280; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=ry5jXfElUh7ESCl79JzkcSXMMA6670Xx/MkF5QQ8gpE=; b=c6isYN4SpJn3VzwQHlHQYPGpRGgxBga942eAu6HKY09pb2LRiR8iIUL2 +lyETMoB6bsziJcBOaLO/p6lPRzPx2EI64mPxxTtd8Yo+oQCkUnvq/eAZ Mt9c3LLFZ541fRzYyVRsOnO0BIeaR2Ml805GVH5sIFAPSMbZQcGKs04jP 867dv6KD5k6yC7hvhsu16I2JFWVsS4NmTNWpVUZxu974jEnP6W64g63LN 8gWmbsx5dHbxmtxASA4KExBmhaTZyXfvjpCU+yoiCTZHdclJ6AkwMuasN MgRGQW8UpMZIivtrVBz52pKlVRPm01FIT2k981OxK+KBJFUQYk5vB/pKt w==; X-CSE-ConnectionGUID: DUMZq5eET+Ce0ci+Wm5fGA== X-CSE-MsgGUID: uD8zGzdFRey3v+aZOZrWQw== X-IronPort-AV: E=McAfee;i="6700,10204,11226"; a="39232651" X-IronPort-AV: E=Sophos;i="6.11,209,1725346800"; d="scan'208";a="39232651" Received: from fmviesa006.fm.intel.com ([10.60.135.146]) by fmvoesa103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 16 Oct 2024 17:51:06 -0700 X-CSE-ConnectionGUID: 8kssZXyJSlWMafqxJgHk4g== X-CSE-MsgGUID: SZ2Jsa0jSAOiLrkJ06gbjA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.11,209,1725346800"; d="scan'208";a="78006342" Received: from tassilo.jf.intel.com ([10.54.38.190]) by fmviesa006-auth.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 16 Oct 2024 17:51:06 -0700 From: Andi Kleen To: gcc-patches@gcc.gnu.org Cc: Andi Kleen Subject: [PATCH 2/2] Only do switch bit test clustering when multiple labels point to same bb Date: Wed, 16 Oct 2024 17:50:59 -0700 Message-ID: <20241017005100.3620061-2-ak@linux.intel.com> X-Mailer: git-send-email 2.46.2 In-Reply-To: <20241017005100.3620061-1-ak@linux.intel.com> References: <20241017005100.3620061-1-ak@linux.intel.com> 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_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org From: Andi Kleen The bit cluster code generation strategy is only beneficial when multiple case labels point to the same code. Do a quick check if that is the case before trying to cluster. This fixes the switch part of PR117091 where all case labels are unique however it doesn't address the performance problems for non unique cases. gcc/ChangeLog: PR middle-end/117091 * gimple-if-to-switch.cc (if_chain::is_beneficial): Update find_bit_test call. * tree-switch-conversion.cc (bit_test_cluster::find_bit_tests): Get max_c argument and bail out early if all case labels are unique. (switch_decision_tree::compute_cases_per_edge): Record number of targets per label and return. (switch_decision_tree::analyze_switch_statement): ... pass to find_bit_tests. * tree-switch-conversion.h: Update prototypes. --- gcc/gimple-if-to-switch.cc | 2 +- gcc/tree-switch-conversion.cc | 23 ++++++++++++++++------- gcc/tree-switch-conversion.h | 5 +++-- 3 files changed, 20 insertions(+), 10 deletions(-) diff --git a/gcc/gimple-if-to-switch.cc b/gcc/gimple-if-to-switch.cc index 96ce1c380a59..4151d1bb520e 100644 --- a/gcc/gimple-if-to-switch.cc +++ b/gcc/gimple-if-to-switch.cc @@ -254,7 +254,7 @@ if_chain::is_beneficial () else output.release (); - output = bit_test_cluster::find_bit_tests (filtered_clusters); + output = bit_test_cluster::find_bit_tests (filtered_clusters, 2); r = output.length () < filtered_clusters.length (); if (r) dump_clusters (&output, "BT can be built"); diff --git a/gcc/tree-switch-conversion.cc b/gcc/tree-switch-conversion.cc index 00426d400006..bb7b8cf215a3 100644 --- a/gcc/tree-switch-conversion.cc +++ b/gcc/tree-switch-conversion.cc @@ -1772,12 +1772,13 @@ jump_table_cluster::is_beneficial (const vec &, } /* Find bit tests of given CLUSTERS, where all members of the vector - are of type simple_cluster. New clusters are returned. */ + are of type simple_cluster. max_c is the max number of cases per label. + New clusters are returned. */ vec -bit_test_cluster::find_bit_tests (vec &clusters) +bit_test_cluster::find_bit_tests (vec &clusters, int max_c) { - if (!is_enabled ()) + if (!is_enabled () || max_c == 1) return clusters.copy (); unsigned l = clusters.length (); @@ -2206,18 +2207,26 @@ bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, } /* Compute the number of case labels that correspond to each outgoing edge of - switch statement. Record this information in the aux field of the edge. */ + switch statement. Record this information in the aux field of the edge. + Return the approx max number of cases per edge. */ -void +int switch_decision_tree::compute_cases_per_edge () { + int max_c = 0; reset_out_edges_aux (m_switch); int ncases = gimple_switch_num_labels (m_switch); for (int i = ncases - 1; i >= 1; --i) { edge case_edge = gimple_switch_edge (cfun, m_switch, i); case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1); + /* For a range case add one extra. That's enough for the bit + cluster heuristic. */ + if ((intptr_t)case_edge->aux > max_c) + max_c = (intptr_t)case_edge->aux + + !!CASE_HIGH (gimple_switch_label (m_switch, i)); } + return max_c; } /* Analyze switch statement and return true when the statement is expanded @@ -2235,7 +2244,7 @@ switch_decision_tree::analyze_switch_statement () m_case_bbs.reserve (l); m_case_bbs.quick_push (default_bb); - compute_cases_per_edge (); + int max_c = compute_cases_per_edge (); for (unsigned i = 1; i < l; i++) { @@ -2256,7 +2265,7 @@ switch_decision_tree::analyze_switch_statement () reset_out_edges_aux (m_switch); /* Find bit-test clusters. */ - vec output = bit_test_cluster::find_bit_tests (clusters); + vec output = bit_test_cluster::find_bit_tests (clusters, max_c); /* Find jump table clusters. */ vec output2; diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h index fbfd7ff7b3ff..15f919f24f9f 100644 --- a/gcc/tree-switch-conversion.h +++ b/gcc/tree-switch-conversion.h @@ -399,7 +399,7 @@ public: /* Find bit tests of given CLUSTERS, where all members of the vector are of type simple_cluster. New clusters are returned. */ - static vec find_bit_tests (vec &clusters); + static vec find_bit_tests (vec &clusters, int max_c); /* Return true when RANGE of case values with UNIQ labels can build a bit test. */ @@ -577,8 +577,9 @@ public: bool try_switch_expansion (vec &clusters); /* Compute the number of case labels that correspond to each outgoing edge of switch statement. Record this information in the aux field of the edge. + Returns max number of cases per edge. */ - void compute_cases_per_edge (); + int compute_cases_per_edge (); /* Before switch transformation, record all SSA_NAMEs defined in switch BB and used in a label basic block. */