From patchwork Thu Aug 8 15:44:55 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andi Kleen X-Patchwork-Id: 1970597 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=firstfloor.org header.i=@firstfloor.org header.a=rsa-sha256 header.s=mail header.b=QqfjwaZx; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; 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 [8.43.85.97]) (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 4WfrwY0kR0z1ybS for ; Fri, 9 Aug 2024 01:45:32 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 38FEF3861806 for ; Thu, 8 Aug 2024 15:45:31 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from one.firstfloor.org (one.firstfloor.org [65.21.254.221]) by sourceware.org (Postfix) with ESMTPS id 932E03860762 for ; Thu, 8 Aug 2024 15:45:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 932E03860762 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=firstfloor.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=firstfloor.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 932E03860762 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=65.21.254.221 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1723131905; cv=none; b=FA4Z39BoMi3w7HcxNJgKWSB5a3l2+MJJQnrGw/NdnZHqjb7qhywy2NkkqHxJK+Y+wENFV/ZO5e79mWRiCVgMm8OSnRh4dtuEA7kLyFXAa3+/xKMexo1yN+TIa2LuEBJRHWkmYnDYQLZcjzNskarXKIEkggqFqaPcVi3OSstBLl0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1723131905; c=relaxed/simple; bh=Ds3ilDYyh0WcRBSsRIwWwQwz7YNkKAL8KuVABVPWtzk=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=m112XYrQqXmUetYzsGHliGrG6t3IpK7jOo42Jvtl1Nn79HANqdYdY7vcxhnyaHkJeYq3BidmmY359UBAaRw7519+IdHMm06g+vVpLeS7/K/AT8Mv/CZeMj5tLYktagRHtjmNj2AK4friLrmt1O5aY6sQDkYtUUm1ZH84Yhv9L5I= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=firstfloor.org; s=mail; t=1723131901; bh=Ds3ilDYyh0WcRBSsRIwWwQwz7YNkKAL8KuVABVPWtzk=; h=From:To:Cc:Subject:Date:From; b=QqfjwaZxvmtLB7V8TWd+qfTNZqSBajYfSYe5cOEZPh7obqoUx0MNyhV3hbxDM6eJQ Gw4wNrYBWHierDa+JI0244AXgkzKQ1EX5/52D9qs4l9eruvrkEV3n9FEveJ0pULdTC iGUM6edW4JpT5+HEpNCHsQv3lHkCjeo3AhSCzCrM= Received: from firstfloor.org (c-24-21-55-115.hsd1.or.comcast.net [24.21.55.115]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by one.firstfloor.org (Postfix) with ESMTPSA id 12C415DA09; Thu, 8 Aug 2024 17:45:01 +0200 (CEST) Received: by firstfloor.org (Postfix, from userid 1000) id 0DB9C1617D6; Thu, 08 Aug 2024 08:44:58 -0700 (PDT) From: Andi Kleen To: gcc-patches@gcc.gnu.org Cc: richard.guenther@gmail.com, tamar.christina@arm.com, Andi Kleen Subject: [PATCH v2] Support if conversion for switches Date: Thu, 8 Aug 2024 08:44:55 -0700 Message-ID: <20240808154455.31390-1-andi@firstfloor.org> X-Mailer: git-send-email 2.45.2 MIME-Version: 1.0 X-Spam-Status: No, score=-10.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_PASS, SPF_PASS, 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 The gimple-if-to-switch pass converts if statements with multiple equal checks on the same value to a switch. This breaks vectorization which cannot handle switches. Teach the tree-if-conv pass used by the vectorizer to handle simple switch statements, like those created by if-to-switch earlier. These are switches that only have a single non default block, They are handled similar to COND in if conversion. This makes the vect-bitfield-read-1-not test fail. The test checks for a bitfield analysis failing, but it actually relied on the ifcvt erroring out early because the test is using a switch. The if conversion still does not work because the switch is not in a form that this patch can handle, but it fails much later and the bitfield analysis succeeds, which makes the test fail. I marked it xfail because it doesn't seem to be testing what it wants to test. [v2: Fix tests to run correctly. Update comments and commit log. Fix gimple switch accessor use.] gcc/ChangeLog: PR tree-opt/115866 * tree-if-conv.cc (if_convertible_switch_p): New function. (if_convertible_stmt_p): Check for switch. (get_loop_body_in_if_conv_order): Handle switch. (predicate_bbs): Likewise. (predicate_statements): Likewise. (remove_conditions_and_labels): Likewise. (ifcvt_split_critical_edges): Likewise. (ifcvt_local_dce): Likewise. gcc/testsuite/ChangeLog: * gcc.dg/vect/vect-switch-ifcvt-1.c: New test. * gcc.dg/vect/vect-switch-ifcvt-2.c: New test. * gcc.dg/vect/vect-switch-search-line-fast.c: New test. * gcc.dg/vect/vect-bitfield-read-1-not.c: Change to xfail. --- gcc/doc/cfg.texi | 4 +- .../gcc.dg/vect/vect-bitfield-read-1-not.c | 2 +- .../gcc.dg/vect/vect-switch-ifcvt-1.c | 115 ++++++++++++++++++ .../gcc.dg/vect/vect-switch-ifcvt-2.c | 49 ++++++++ .../vect/vect-switch-search-line-fast.c | 17 +++ gcc/tree-if-conv.cc | 93 +++++++++++++- 6 files changed, 272 insertions(+), 8 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-1.c create mode 100644 gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c create mode 100644 gcc/testsuite/gcc.dg/vect/vect-switch-search-line-fast.c diff --git a/gcc/doc/cfg.texi b/gcc/doc/cfg.texi index 9a22420f91f..a6f2b9f97d6 100644 --- a/gcc/doc/cfg.texi +++ b/gcc/doc/cfg.texi @@ -83,13 +83,13 @@ lexicographical order, except @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}. The macro @code{FOR_ALL_BB} also visits all basic blocks in lexicographical order, including @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}. -@findex post_order_compute, inverted_post_order_compute, walk_dominator_tree +@findex post_order_compute, inverted_post_order_compute, dom_walker::walk The functions @code{post_order_compute} and @code{inverted_post_order_compute} can be used to compute topological orders of the CFG. The orders are stored as vectors of basic block indices. The @code{BASIC_BLOCK} array can be used to iterate each basic block by index. Dominator traversals are also possible using -@code{walk_dominator_tree}. Given two basic blocks A and B, block A +@code{dom_walker::walk}. Given two basic blocks A and B, block A dominates block B if A is @emph{always} executed before B@. Each @code{basic_block} also contains pointers to the first diff --git a/gcc/testsuite/gcc.dg/vect/vect-bitfield-read-1-not.c b/gcc/testsuite/gcc.dg/vect/vect-bitfield-read-1-not.c index 0d91067ebb2..85f4de8464a 100644 --- a/gcc/testsuite/gcc.dg/vect/vect-bitfield-read-1-not.c +++ b/gcc/testsuite/gcc.dg/vect/vect-bitfield-read-1-not.c @@ -55,6 +55,6 @@ int main (void) return 0; } -/* { dg-final { scan-tree-dump-not "Bitfield OK to lower." "ifcvt" } } */ +/* { dg-final { scan-tree-dump-times "Bitfield OK to lower." 0 "ifcvt" { xfail *-*-* } } } */ diff --git a/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-1.c b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-1.c new file mode 100644 index 00000000000..f5352ef8ed7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-1.c @@ -0,0 +1,115 @@ +/* { dg-require-effective-target vect_int } */ +#include "tree-vect.h" + +extern void abort (void); + +int +f1 (char *s) +{ + int c = 0; + int i; + for (i = 0; i < 64; i++) + { + switch (*s) + { + case ',': + case '|': + c++; + } + s++; + } + return c; +} + +int +f2 (char *s) +{ + int c = 0; + int i; + for (i = 0; i < 64; i++) + { + if (*s != '#') + { + switch (*s) + { + case ',': + case '|': + c++; + } + } + s++; + } + return c; +} + +int +f3 (char *s) +{ + int c = 0; + int i; + for (i = 0; i < 64; i++) + { + if (*s != '#') + if (*s == ',' || *s == '|' || *s == '@' || *s == '*') + c++; + s++; + } + return c; +} + + +int +f4 (char *s) +{ + int c = 0; + int i; + for (i = 0; i < 64; i++) + { + if (*s == ',' || *s == '|' || *s == '@' || *s == '*') + c++; + s++; + } + return c; +} + +#define CHECK(f, str, res) \ + __builtin_strcpy(buf, str); n = f(buf); if (n != res) abort(); + +int +main () +{ + int n; + char buf[64]; + + __builtin_memset (buf, 0, sizeof buf); + + check_vect (); + + CHECK (f1, ",,,,,,,,,,", 10); + CHECK (f1, "||||||||||", 10); + CHECK (f1, "aaaaaaaaaa", 0); + CHECK (f1, "", 0); + CHECK (f1, ",|,|xxxxxx", 4); + + CHECK (f2, ",,,,,,,,,,", 10); + CHECK (f2, "||||||||||", 10); + CHECK (f2, "aaaaaaaaaa", 0); + CHECK (f2, "", 0); + CHECK (f2, ",|,|xxxxxx", 4); + + CHECK (f3, ",,,,,,,,,,", 10); + CHECK (f3, "||||||||||", 10); + CHECK (f3, "aaaaaaaaaa", 0); + CHECK (f3, "", 0); + CHECK (f3, ",|,|xxxxxx", 4); + + CHECK (f4, ",,,,,,,,,,", 10); + CHECK (f4, "||||||||||", 10); + CHECK (f4, "aaaaaaaaaa", 0); + CHECK (f4, "", 0); + CHECK (f4, ",|,|xxxxxx", 4); + + return 0; +} + +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 4 "vect" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c new file mode 100644 index 00000000000..f0fcb43e177 --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/vect-switch-ifcvt-2.c @@ -0,0 +1,49 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target vect_int } */ + +/* Check for cases currently not supported by switch tree if conversion. */ + +int +f1 (char *s) +{ + int c = 0; + int i; + for (i = 0; i < 64; i++) + { + switch (*s) + { + case ',': + case '|': + c++; + break; + case '^': + c += 2; + break; + } + s++; + } + return c; +} + +int +f2 (char *s) +{ + int c = 0; + int i; + for (i = 0; i < 64; i++) + { + switch (*s) + { + case ',': + case '|': + c++; + /*fallthrough*/ + default: + c+=2; + } + s++; + } + return c; +} + +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 0 "vect" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/vect-switch-search-line-fast.c b/gcc/testsuite/gcc.dg/vect/vect-switch-search-line-fast.c new file mode 100644 index 00000000000..15f3a4ef38a --- /dev/null +++ b/gcc/testsuite/gcc.dg/vect/vect-switch-search-line-fast.c @@ -0,0 +1,17 @@ +/* PR116126 -- once this works use this version in libcpp/lex.c. + This also requires working value range propagation for s/end. */ +/* { dg-do compile } */ +/* { dg-require-effective-target vect_int } */ + +const unsigned char *search_line_fast2 (const unsigned char *s, + const unsigned char *end) +{ + while (s < end) { + if (*s == '\n' || *s == '\r' || *s == '\\' || *s == '?') + break; + s++; + } + return s; +} + +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail *-*-* } } } */ diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc index 57992b6deca..5aac65cfbd1 100644 --- a/gcc/tree-if-conv.cc +++ b/gcc/tree-if-conv.cc @@ -124,6 +124,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-vectorizer.h" #include "tree-eh.h" #include "cgraph.h" +#include "print-tree.h" /* For lang_hooks.types.type_for_mode. */ #include "langhooks.h" @@ -1082,11 +1083,35 @@ if_convertible_gimple_assign_stmt_p (gimple *stmt, return true; } +/* Return true when SW switch statement is equivalent to cond, that + all non default labels point to the same label. + + Fallthrough is not checked for and could even happen + with cond (using goto), so is handled. + + This is intended for switches created by the if-switch-conversion + pass, but can handle some programmer supplied cases too. */ + +static bool +if_convertible_switch_p (gswitch *sw) +{ + if (gimple_switch_num_labels (sw) <= 1) + return false; + tree label = CASE_LABEL (gimple_switch_label (sw, 1)); + for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++) + { + if (CASE_LABEL (gimple_switch_label (sw, i)) != label) + return false; + } + return true; +} + /* Return true when STMT is if-convertible. A statement is if-convertible if: - it is an if-convertible GIMPLE_ASSIGN, - it is a GIMPLE_LABEL or a GIMPLE_COND, + - it is a switch equivalent to COND - it is builtins call, - it is a call to a function with a SIMD clone. */ @@ -1100,6 +1125,9 @@ if_convertible_stmt_p (gimple *stmt, vec refs) case GIMPLE_COND: return true; + case GIMPLE_SWITCH: + return if_convertible_switch_p (as_a (stmt)); + case GIMPLE_ASSIGN: return if_convertible_gimple_assign_stmt_p (stmt, refs); @@ -1327,6 +1355,7 @@ get_loop_body_in_if_conv_order (const class loop *loop) case GIMPLE_CALL: case GIMPLE_DEBUG: case GIMPLE_COND: + case GIMPLE_SWITCH: gimple_set_uid (gsi_stmt (gsi), 0); break; default: @@ -1426,6 +1455,58 @@ predicate_bbs (loop_p loop) cond = NULL_TREE; } + /* Assumes the limited COND like switches checked for earlier. */ + else if (gswitch *sw = safe_dyn_cast (*gsi_last_bb (bb))) + { + location_t loc = gimple_location (*gsi_last_bb (bb)); + + tree default_label = CASE_LABEL (gimple_switch_default_label (sw)); + tree cond_label = CASE_LABEL (gimple_switch_label (sw, 1)); + + edge false_edge = find_edge (bb, label_to_block (cfun, default_label)); + edge true_edge = find_edge (bb, label_to_block (cfun, cond_label)); + + /* Create chain of switch tests for each case. */ + tree switch_cond = NULL_TREE; + tree index = gimple_switch_index (sw); + for (unsigned i = 1; i < gimple_switch_num_labels (sw); i++) + { + tree label = gimple_switch_label (sw, i); + tree case_cond; + if (CASE_HIGH (label)) + { + tree low = build2_loc (loc, GE_EXPR, + boolean_type_node, + index, CASE_LOW (label)); + tree high = build2_loc (loc, LE_EXPR, + boolean_type_node, + index, CASE_HIGH (label)); + case_cond = build2_loc (loc, TRUTH_AND_EXPR, + boolean_type_node, + low, high); + } + else + case_cond = build2_loc (loc, EQ_EXPR, + boolean_type_node, + index, + CASE_LOW (gimple_switch_label (sw, i))); + if (i > 1) + switch_cond = build2_loc (loc, TRUTH_OR_EXPR, + boolean_type_node, + case_cond, switch_cond); + else + switch_cond = case_cond; + } + + add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond), + unshare_expr (switch_cond)); + switch_cond = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node, + unshare_expr (switch_cond)); + add_to_dst_predicate_list (loop, false_edge, + unshare_expr (cond), switch_cond); + cond = NULL_TREE; + } + /* If current bb has only one successor, then consider it as an unconditional goto. */ if (single_succ_p (bb)) @@ -2852,9 +2933,9 @@ predicate_statements (loop_p loop) } } -/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks - other than the exit and latch of the LOOP. Also resets the - GIMPLE_DEBUG information. */ +/* Remove all GIMPLE_CONDs and GIMPLE_LABELs and GIMPLE_SWITCH of all + the basic blocks other than the exit and latch of the LOOP. Also + resets the GIMPLE_DEBUG information. */ static void remove_conditions_and_labels (loop_p loop) @@ -2875,6 +2956,7 @@ remove_conditions_and_labels (loop_p loop) { case GIMPLE_COND: case GIMPLE_LABEL: + case GIMPLE_SWITCH: gsi_remove (&gsi, true); break; @@ -3265,7 +3347,8 @@ ifcvt_split_critical_edges (class loop *loop, bool aggressive_if_conv) continue; /* Skip basic blocks not ending with conditional branch. */ - if (!safe_is_a (*gsi_last_bb (bb))) + if (!safe_is_a (*gsi_last_bb (bb)) + && !safe_is_a (*gsi_last_bb (bb))) continue; FOR_EACH_EDGE (e, ei, bb->succs) @@ -3330,7 +3413,7 @@ ifcvt_local_dce (class loop *loop) continue; } code = gimple_code (stmt); - if (code == GIMPLE_COND || code == GIMPLE_CALL) + if (code == GIMPLE_COND || code == GIMPLE_CALL || code == GIMPLE_SWITCH) { gimple_set_plf (stmt, GF_PLF_2, true); worklist.safe_push (stmt);