On Tue, Aug 13, 2024 at 7:34 PM Andi Kleen <[email protected]> wrote:
>
> Andi Kleen <[email protected]> writes:
>
> I wanted to ping this patch. I believe Richard ok'ed most of it earlier
> but need an ok for the changes resulting from his review too
> (but they were mostly only test suite and comment fixes
> apart from some minor tweaks)
OK.
Thanks,
Richard.
> -Andi
>
> > 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<data_reference_p> refs)
> > case GIMPLE_COND:
> > return true;
> >
> > + case GIMPLE_SWITCH:
> > + return if_convertible_switch_p (as_a <gswitch *> (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 <gswitch *> (*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 <gcond *> (*gsi_last_bb (bb)))
> > + if (!safe_is_a <gcond *> (*gsi_last_bb (bb))
> > + && !safe_is_a <gswitch *> (*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);
