From 8e97bc2bdb4013cbb62d9910083b240e0eb01941 Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Sat, 20 Nov 2010 00:48:57 +0100 Subject: [PATCH] re PR tree-optimization/45830 (Code+rodata increase with -ftree-switch-conversion) PR tree-optimization/45830 * stmt.c (expand_switch_using_bit_tests_p): New function. (expand_case): Use it. * tree.h (expand_switch_using_bit_tests_p): New prototype. * tree-switch-conversion.c (struct switch_conv_info): Add bit_test_uniq, bit_test_count and bit_test_bb fields. (check_range): Fix a comment. (check_process_case): Compute bit_test_uniq and bit_test_count. (create_temp_arrays): Use XCNEWVEC, merge 3 arrays into one allocation. (free_temp_arrays): Use XDELETEVEC, adjust for the 3 arrays merging. (constructor_contains_same_values_p): Use FOR_EACH_VEC_ELT. (array_value_type): New function. (build_one_array): Use it, if it returned different type, fold_convert all constructor fields and convert back to the wider type in the generated code. (process_switch): Initialize bit_test_uniq, bit_test_count and bit_test_bb fields. Don't optimize if expand_switch_using_bit_tests_p returned true. * gcc.target/i386/pr45830.c: New test. * gcc.c-torture/execute/pr45830.c: New test. From-SVN: r166966 --- gcc/ChangeLog | 22 +++ gcc/stmt.c | 28 ++- gcc/testsuite/ChangeLog | 6 + gcc/testsuite/gcc.c-torture/execute/pr45830.c | 97 +++++++++++ gcc/testsuite/gcc.target/i386/pr45830.c | 31 ++++ gcc/tree-switch-conversion.c | 161 +++++++++++++++--- gcc/tree.h | 2 + 7 files changed, 320 insertions(+), 27 deletions(-) create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr45830.c create mode 100644 gcc/testsuite/gcc.target/i386/pr45830.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f1f06ce7a8d..b5dbd5b19d9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,25 @@ +2010-11-20 Jakub Jelinek + + PR tree-optimization/45830 + * stmt.c (expand_switch_using_bit_tests_p): New function. + (expand_case): Use it. + * tree.h (expand_switch_using_bit_tests_p): New prototype. + * tree-switch-conversion.c (struct switch_conv_info): Add + bit_test_uniq, bit_test_count and bit_test_bb fields. + (check_range): Fix a comment. + (check_process_case): Compute bit_test_uniq and bit_test_count. + (create_temp_arrays): Use XCNEWVEC, merge 3 arrays into one + allocation. + (free_temp_arrays): Use XDELETEVEC, adjust for the 3 arrays merging. + (constructor_contains_same_values_p): Use FOR_EACH_VEC_ELT. + (array_value_type): New function. + (build_one_array): Use it, if it returned different type, + fold_convert all constructor fields and convert back to the + wider type in the generated code. + (process_switch): Initialize bit_test_uniq, bit_test_count and + bit_test_bb fields. Don't optimize if expand_switch_using_bit_tests_p + returned true. + 2010-11-19 Michael Matz PR tree-optimization/46077 diff --git a/gcc/stmt.c b/gcc/stmt.c index e24ed4ebb31..e045330ef31 100644 --- a/gcc/stmt.c +++ b/gcc/stmt.c @@ -2250,6 +2250,25 @@ emit_case_bit_tests (tree index_type, tree index_expr, tree minval, #define HAVE_tablejump 0 #endif +/* Return true if a switch should be expanded as a bit test. + INDEX_EXPR is the index expression, RANGE is the difference between + highest and lowest case, UNIQ is number of unique case node targets + not counting the default case and COUNT is the number of comparisons + needed, not counting the default case. */ +bool +expand_switch_using_bit_tests_p (tree index_expr, tree range, + unsigned int uniq, unsigned int count) +{ + return (CASE_USE_BIT_TESTS + && ! TREE_CONSTANT (index_expr) + && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 + && compare_tree_int (range, 0) > 0 + && lshift_cheap_p () + && ((uniq == 1 && count >= 3) + || (uniq == 2 && count >= 5) + || (uniq == 3 && count >= 6))); +} + /* Terminate a case (Pascal/Ada) or switch (C) statement in which ORIG_INDEX is the expression to be tested. If ORIG_TYPE is not NULL, it is the original ORIG_INDEX @@ -2384,14 +2403,7 @@ expand_case (gimple stmt) /* Try implementing this switch statement by a short sequence of bit-wise comparisons. However, we let the binary-tree case below handle constant index expressions. */ - if (CASE_USE_BIT_TESTS - && ! TREE_CONSTANT (index_expr) - && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0 - && compare_tree_int (range, 0) > 0 - && lshift_cheap_p () - && ((uniq == 1 && count >= 3) - || (uniq == 2 && count >= 5) - || (uniq == 3 && count >= 6))) + if (expand_switch_using_bit_tests_p (index_expr, range, uniq, count)) { /* Optimize the case where all the case values fit in a word without having to subtract MINVAL. In this case, diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 7b8cb74df90..38a694cf3d5 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2010-11-20 Jakub Jelinek + + PR tree-optimization/45830 + * gcc.target/i386/pr45830.c: New test. + * gcc.c-torture/execute/pr45830.c: New test. + 2010-11-19 Nicola Pero * objc.dg/attributes/class-attribute-1.m: Rewritten. diff --git a/gcc/testsuite/gcc.c-torture/execute/pr45830.c b/gcc/testsuite/gcc.c-torture/execute/pr45830.c new file mode 100644 index 00000000000..0f83e050e25 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr45830.c @@ -0,0 +1,97 @@ +/* PR tree-optimization/45830 */ + +extern void abort (void); + +long long va, vb, vc, vd, ve; + +__attribute__((noinline)) int +foo (int x) +{ + long long a, b, c, d, e; + switch (x) + { + case 0: + case 3: + case 1: + case 2: + case 4: + a = 1; + b = 129; + c = -12; + d = -4; + e = 128; + break; + case 23: + case 26: + case 19: + case 65: + case 5: + a = 2; + b = 138; + c = 115; + d = 128; + e = -16; + break; + case 21: + case 20: + case 22: + case 38: + case 27: + case 66: + case 45: + case 47: + a = 3; + b = 6; + c = 127; + d = 25; + e = 257; + break; + default: + a = 0; + b = 18; + c = 0; + d = 64; + e = 32768L; + break; + } + va = a; + vb = b; + vc = c; + vd = d; + ve = e; +} + +int +bar (int x) +{ + if (x < 0) + return 3; + if (x < 5) + return 0; + if (x == 5 || x == 19 || x == 23 | x == 26 || x == 65) + return 1; + if ((x >= 20 && x <= 22) || x == 27 || x == 38 + || x == 45 || x == 47 || x == 66) + return 2; + return 3; +} + +long long expected[] = +{ 1, 129, -12, -4, 128, 2, 138, 115, 128, -16, + 3, 6, 127, 25, 257, 0, 18, 0, 64, 32768L }; + +int +main (void) +{ + int i, v; + for (i = -4; i < 70; i++) + { + foo (i); + v = bar (i); + if (va != expected[5 * v] || vb != expected[5 * v + 1] + || vc != expected[5 * v + 2] || vd != expected[5 * v + 3] + || ve != expected[5 * v + 4]) + abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.target/i386/pr45830.c b/gcc/testsuite/gcc.target/i386/pr45830.c new file mode 100644 index 00000000000..a74d4345464 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/pr45830.c @@ -0,0 +1,31 @@ +/* PR target/45830 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-switchconv-all -mtune=generic" } */ + +int +foo (int *a) +{ + switch (*a) + { + case 0: + case 3: + case 1: + case 2: + case 4: + case 23: + case 26: + case 19: + case 5: + case 21: + case 20: + case 22: + case 27: + return 1; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump "Expanding as bit test is preferable" "switchconv" } } */ +/* { dg-final { scan-assembler-not "CSWTCH" } } */ +/* { dg-final { cleanup-tree-dump "switchconv" } } */ diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 05c0a652516..fc333f7480d 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -156,6 +156,12 @@ struct switch_conv_info /* String reason why the case wasn't a good candidate that is written to the dump file, if there is one. */ const char *reason; + + /* Parameters for expand_switch_using_bit_tests. Should be computed + the same way as in expand_case. */ + unsigned int bit_test_uniq; + unsigned int bit_test_count; + basic_block bit_test_bb[2]; }; /* Global pass info. */ @@ -174,7 +180,7 @@ check_range (gimple swtch) tree range_max; /* The gimplifier has already sorted the cases by CASE_LOW and ensured there - is a default label which is the last in the vector. */ + is a default label which is the first in the vector. */ min_case = gimple_switch_label (swtch, 1); info.range_min = CASE_LOW (min_case); @@ -234,7 +240,26 @@ check_process_case (tree cs) info.default_count = e->count; } else - info.other_count += e->count; + { + int i; + info.other_count += e->count; + for (i = 0; i < 2; i++) + if (info.bit_test_bb[i] == label_bb) + break; + else if (info.bit_test_bb[i] == NULL) + { + info.bit_test_bb[i] = label_bb; + info.bit_test_uniq++; + break; + } + if (i == 2) + info.bit_test_uniq = 3; + if (CASE_HIGH (cs) != NULL_TREE + && ! tree_int_cst_equal (CASE_LOW (cs), CASE_HIGH (cs))) + info.bit_test_count += 2; + else + info.bit_test_count++; + } if (!label_bb) { @@ -336,13 +361,10 @@ create_temp_arrays (void) { int i; - info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree)); - info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count, - sizeof (tree)); - info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree)); - info.target_outbound_names = (tree *) xcalloc (info.phi_count, - sizeof (tree)); - + info.default_values = XCNEWVEC (tree, info.phi_count * 3); + info.constructors = XCNEWVEC (VEC (constructor_elt, gc) *, info.phi_count); + info.target_inbound_names = info.default_values + info.phi_count; + info.target_outbound_names = info.target_inbound_names + info.phi_count; for (i = 0; i < info.phi_count; i++) info.constructors[i] = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1); @@ -355,10 +377,8 @@ create_temp_arrays (void) static void free_temp_arrays (void) { - free (info.constructors); - free (info.default_values); - free (info.target_inbound_names); - free (info.target_outbound_names); + XDELETEVEC (info.constructors); + XDELETEVEC (info.default_values); } /* Populate the array of default values in the order of phi nodes. @@ -468,13 +488,12 @@ build_constructors (gimple swtch) static tree constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec) { - int i, len = VEC_length (constructor_elt, vec); + unsigned int i; tree prev = NULL_TREE; + constructor_elt *elt; - for (i = 0; i < len; i++) + FOR_EACH_VEC_ELT (constructor_elt, vec, i, elt) { - constructor_elt *elt = VEC_index (constructor_elt, vec, i); - if (!prev) prev = elt->value; else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST)) @@ -483,6 +502,79 @@ constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec) return prev; } +/* Return type which should be used for array elements, either TYPE, + or for integral type some smaller integral type that can still hold + all the constants. */ + +static tree +array_value_type (gimple swtch, tree type, int num) +{ + unsigned int i, len = VEC_length (constructor_elt, info.constructors[num]); + constructor_elt *elt; + enum machine_mode mode; + int sign = 0; + tree smaller_type; + + if (!INTEGRAL_TYPE_P (type)) + return type; + + mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type))); + if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode)) + return type; + + if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32)) + return type; + + FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt) + { + double_int cst; + + if (TREE_CODE (elt->value) != INTEGER_CST) + return type; + + cst = TREE_INT_CST (elt->value); + while (1) + { + unsigned int prec = GET_MODE_BITSIZE (mode); + if (prec > HOST_BITS_PER_WIDE_INT) + return type; + + if (sign >= 0 + && double_int_equal_p (cst, double_int_zext (cst, prec))) + { + if (sign == 0 + && double_int_equal_p (cst, double_int_sext (cst, prec))) + break; + sign = 1; + break; + } + if (sign <= 0 + && double_int_equal_p (cst, double_int_sext (cst, prec))) + { + sign = -1; + break; + } + + if (sign == 1) + sign = 0; + + mode = GET_MODE_WIDER_MODE (mode); + if (mode == VOIDmode + || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type))) + return type; + } + } + + if (sign == 0) + sign = TYPE_UNSIGNED (type) ? 1 : -1; + smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0); + if (GET_MODE_SIZE (TYPE_MODE (type)) + <= GET_MODE_SIZE (TYPE_MODE (smaller_type))) + return type; + + return smaller_type; +} + /* Create an appropriate array type and declaration and assemble a static array variable. Also create a load statement that initializes the variable in question with a value from the static array. SWTCH is the switch statement @@ -512,10 +604,19 @@ build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi, load = gimple_build_assign (name, cst); else { - tree array_type, ctor, decl, value_type, fetch; + tree array_type, ctor, decl, value_type, fetch, default_type; - value_type = TREE_TYPE (info.default_values[num]); + default_type = TREE_TYPE (info.default_values[num]); + value_type = array_value_type (swtch, default_type, num); array_type = build_array_type (value_type, arr_index_type); + if (default_type != value_type) + { + unsigned int i; + constructor_elt *elt; + + FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt) + elt->value = fold_convert (value_type, elt->value); + } ctor = build_constructor (array_type, info.constructors[num]); TREE_CONSTANT (ctor) = true; TREE_STATIC (ctor) = true; @@ -534,6 +635,12 @@ build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi, fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, NULL_TREE); + if (default_type != value_type) + { + fetch = fold_convert (default_type, fetch); + fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE, + true, GSI_SAME_STMT); + } load = gimple_build_assign (name, fetch); } @@ -818,6 +925,10 @@ process_switch (gimple swtch) info.default_prob = 0; info.default_count = 0; info.other_count = 0; + info.bit_test_uniq = 0; + info.bit_test_count = 0; + info.bit_test_bb[0] = NULL; + info.bit_test_bb[1] = NULL; /* An ERROR_MARK occurs for various reasons including invalid data type. (comment from stmt.c) */ @@ -841,6 +952,18 @@ process_switch (gimple swtch) return false; } + if (info.bit_test_uniq <= 2) + { + rtl_profile_for_bb (gimple_bb (swtch)); + if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch), + info.range_size, info.bit_test_uniq, + info.bit_test_count)) + { + info.reason = " Expanding as bit test is preferable\n"; + return false; + } + } + if (!check_final_bb ()) return false; diff --git a/gcc/tree.h b/gcc/tree.h index 6ae90f4128a..90170e78d07 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -5314,6 +5314,8 @@ extern bool parse_input_constraint (const char **, int, int, int, int, const char * const *, bool *, bool *); extern void expand_asm_stmt (gimple); extern tree resolve_asm_operand_names (tree, tree, tree, tree); +extern bool expand_switch_using_bit_tests_p (tree, tree, unsigned int, + unsigned int); extern void expand_case (gimple); extern void expand_decl (tree); #ifdef HARD_CONST -- 2.30.2