From b3d77404c060c0d65d8d4c97254995737d0fc032 Mon Sep 17 00:00:00 2001 From: Eric Botcazou Date: Fri, 26 Jun 2020 15:23:05 +0200 Subject: [PATCH] Take into account range info to optimize range tests into bit tests The patch is aimed at addressing the following two issues: 1. In order to protect the shift operation from undefinedness, the new bit test is guarded with a new test, but this new test uses the range of the bit test values, not that of the shift operation so, if the input is in the range of the shift operation but not of the bit test values, then the subsequent VRP pass cannot eliminate the new test. Moreover changing the new test to use the range of the shift operation, instead of that of the bit test values, in the general case would pessimize the cases which are in between. 2. If the new test can be eliminated, then it becomes profitable to do the optimization into a bit test for one fewer comparison in the source code. Therefore the patch changes optimize_range_tests_to_bit_test to use the range info of the input in order to eliminate the new test. gcc/ChangeLog: * tree-ssa-reassoc.c (dump_range_entry): New function. (debug_range_entry): New debug function. (update_range_test): Invoke dump_range_entry for dumping. (optimize_range_tests_to_bit_test): Merge the entry test in the bit test when possible and lower the profitability threshold. gcc/ada/ChangeLog: * exp_ch4.adb (Expand_Set_Membership): Expand the membership test using left associativity instead of right associativity. gcc/testsuite/ChangeLog: * gnat.dg/opt86_pkg.ads: New helper. * gnat.dg/opt86a.adb: New test. * gnat.dg/opt86b.adb: Likewise. * gnat.dg/opt86c.adb: Likewise. --- gcc/ada/exp_ch4.adb | 13 ++-- gcc/testsuite/gnat.dg/opt86_pkg.ads | 8 ++ gcc/testsuite/gnat.dg/opt86a.adb | 36 +++++++++ gcc/testsuite/gnat.dg/opt86b.adb | 37 +++++++++ gcc/testsuite/gnat.dg/opt86c.adb | 37 +++++++++ gcc/tree-ssa-reassoc.c | 116 +++++++++++++++++++++------- 6 files changed, 212 insertions(+), 35 deletions(-) create mode 100644 gcc/testsuite/gnat.dg/opt86_pkg.ads create mode 100644 gcc/testsuite/gnat.dg/opt86a.adb create mode 100644 gcc/testsuite/gnat.dg/opt86b.adb create mode 100644 gcc/testsuite/gnat.dg/opt86c.adb diff --git a/gcc/ada/exp_ch4.adb b/gcc/ada/exp_ch4.adb index 2adebb6f54c..88dcb52349d 100644 --- a/gcc/ada/exp_ch4.adb +++ b/gcc/ada/exp_ch4.adb @@ -12879,16 +12879,19 @@ package body Exp_Ch4 is begin Remove_Side_Effects (Lop); - Alt := Last (Alternatives (N)); + Alt := First (Alternatives (N)); Res := Make_Cond (Alt); + Next (Alt); + + -- We use left associativity as in the equivalent boolean case. This + -- kind of canonicalization helps the optimizer of the code generator. - Prev (Alt); while Present (Alt) loop Res := Make_Or_Else (Sloc (Alt), - Left_Opnd => Make_Cond (Alt), - Right_Opnd => Res); - Prev (Alt); + Left_Opnd => Res, + Right_Opnd => Make_Cond (Alt)); + Next (Alt); end loop; Rewrite (N, Res); diff --git a/gcc/testsuite/gnat.dg/opt86_pkg.ads b/gcc/testsuite/gnat.dg/opt86_pkg.ads new file mode 100644 index 00000000000..92ce45b9202 --- /dev/null +++ b/gcc/testsuite/gnat.dg/opt86_pkg.ads @@ -0,0 +1,8 @@ +package Opt86_Pkg is + + type Enum is (Val0, Val1, Val2, Val3, Val4, Val5, Val6, Val7, + Val8, Val9, Val10, Val11, Val12, Val13, Val14, Val15, + Val16, Val17, Val18, Val19, Val20, Val21, Val22, Val23, + Val24, Val25, Val26, Val27, Val28, Val29, Val30, Val31); + +end Opt86_Pkg; diff --git a/gcc/testsuite/gnat.dg/opt86a.adb b/gcc/testsuite/gnat.dg/opt86a.adb new file mode 100644 index 00000000000..d8cd35ebc8b --- /dev/null +++ b/gcc/testsuite/gnat.dg/opt86a.adb @@ -0,0 +1,36 @@ +-- { dg-do compile } +-- { dg-options "-O2 -fdump-tree-optimized" } + +with Ada.Command_Line; use Ada.Command_Line; +with Opt86_Pkg; use Opt86_Pkg; + +procedure Opt86a is + + S1, S2, S3, S4 : Enum; + +begin + + S1 := Enum'Value (Argument (1)); + S2 := Enum'Value (Argument (2)); + S3 := Enum'Value (Argument (3)); + S4 := Enum'Value (Argument (4)); + + if S1 in Val2 | Val3 | Val9 then + raise Program_Error; + end if; + + if S2 not in Val2 | Val3 | Val9 then + raise Program_Error; + end if; + + if S3 = Val1 or else S3 = Val4 or else S3 = Val8 then + raise Program_Error; + end if; + + if S4 /= Val1 and S4 /= Val4 and S4 /= Val8 then + raise Program_Error; + end if; + +end; + +-- { dg-final { scan-tree-dump-times ">>" 4 "optimized" } } diff --git a/gcc/testsuite/gnat.dg/opt86b.adb b/gcc/testsuite/gnat.dg/opt86b.adb new file mode 100644 index 00000000000..fe46f2e28c6 --- /dev/null +++ b/gcc/testsuite/gnat.dg/opt86b.adb @@ -0,0 +1,37 @@ +-- { dg-do compile } +-- { dg-options "-O2 -fdump-tree-optimized" } + +with Ada.Command_Line; use Ada.Command_Line; +with Opt86_Pkg; use Opt86_Pkg; + +procedure Opt86B is + + S1, S2, S3, S4 : Enum; + +begin + + S1 := Enum'Value (Argument (1)); + S2 := Enum'Value (Argument (2)); + S3 := Enum'Value (Argument (3)); + S4 := Enum'Value (Argument (4)); + + if S1 in Val2 | Val3 | Val9 | Val29 then + raise Program_Error; + end if; + + if S2 not in Val2 | Val3 | Val9 | Val29 then + raise Program_Error; + end if; + + if S3 = Val1 or S3 = Val4 or S3 = Val8 or S3 = Val13 then + raise Program_Error; + end if; + + if S4 /= Val1 and S4 /= Val4 and S4 /= Val8 and S4 /= Val13 then + raise Program_Error; + end if; + +end; + +-- { dg-final { scan-tree-dump-not "> 29" "optimized" } } +-- { dg-final { scan-tree-dump-not "> 13" "optimized" } } diff --git a/gcc/testsuite/gnat.dg/opt86c.adb b/gcc/testsuite/gnat.dg/opt86c.adb new file mode 100644 index 00000000000..77691441eb3 --- /dev/null +++ b/gcc/testsuite/gnat.dg/opt86c.adb @@ -0,0 +1,37 @@ +-- { dg-do compile } +-- { dg-options "-O2 -fdump-tree-optimized" } + +with Ada.Command_Line; use Ada.Command_Line; +with Opt86_Pkg; use Opt86_Pkg; + +procedure Opt86c is + + S1, S2, S3, S4 : Enum; + +begin + + S1 := Enum'Value (Argument (1)); + S2 := Enum'Value (Argument (2)); + S3 := Enum'Value (Argument (3)); + S4 := Enum'Value (Argument (4)); + + if S1 in Val16 | Val8 | Val26 | Val2 | Val10 then + raise Program_Error; + end if; + + if S2 not in Val16 | Val8 | Val26 | Val2 | Val10 then + raise Program_Error; + end if; + + if S3 = Val3 or S3 = Val25 or S3 = Val13 or S3 = Val29 or S3 = Val11 then + raise Program_Error; + end if; + + if S4 /= Val3 and S4 /= Val25 and S4 /= Val13 and S4 /= Val29 and s4 /= Val11 then + raise Program_Error; + end if; + +end; + +-- { dg-final { scan-tree-dump-not "> 26" "optimized" } } +-- { dg-final { scan-tree-dump-not "> 29" "optimized" } } diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 2e67987f6c6..d06b693ec76 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -2416,6 +2416,32 @@ struct range_entry unsigned int idx, next; }; +void dump_range_entry (FILE *file, struct range_entry *r); +void debug_range_entry (struct range_entry *r); + +/* Dump the range entry R to FILE, skipping its expression if SKIP_EXP. */ + +void +dump_range_entry (FILE *file, struct range_entry *r, bool skip_exp) +{ + if (!skip_exp) + print_generic_expr (file, r->exp); + fprintf (file, " %c[", r->in_p ? '+' : '-'); + print_generic_expr (file, r->low); + fputs (", ", file); + print_generic_expr (file, r->high); + fputc (']', file); +} + +/* Dump the range entry R to STDERR. */ + +DEBUG_FUNCTION void +debug_range_entry (struct range_entry *r) +{ + dump_range_entry (stderr, r, false); + fputc ('\n', stderr); +} + /* This is similar to make_range in fold-const.c, but on top of GIMPLE instead of trees. If EXP is non-NULL, it should be an SSA_NAME and STMT argument is ignored, otherwise STMT @@ -2730,12 +2756,7 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange, { struct range_entry *r; fprintf (dump_file, "Optimizing range tests "); - print_generic_expr (dump_file, range->exp); - fprintf (dump_file, " %c[", range->in_p ? '+' : '-'); - print_generic_expr (dump_file, range->low); - fprintf (dump_file, ", "); - print_generic_expr (dump_file, range->high); - fprintf (dump_file, "]"); + dump_range_entry (dump_file, range, false); for (i = 0; i < count; i++) { if (otherrange) @@ -2747,15 +2768,13 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange, && TREE_CODE (r->exp) == SSA_NAME) { fprintf (dump_file, " and "); - print_generic_expr (dump_file, r->exp); + dump_range_entry (dump_file, r, false); } else - fprintf (dump_file, " and"); - fprintf (dump_file, " %c[", r->in_p ? '+' : '-'); - print_generic_expr (dump_file, r->low); - fprintf (dump_file, ", "); - print_generic_expr (dump_file, r->high); - fprintf (dump_file, "]"); + { + fprintf (dump_file, " and"); + dump_range_entry (dump_file, r, true); + } } fprintf (dump_file, "\n into "); print_generic_expr (dump_file, tem); @@ -3121,7 +3140,7 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, int prec = GET_MODE_BITSIZE (word_mode); auto_vec candidates; - for (i = first; i < length - 2; i++) + for (i = first; i < length - 1; i++) { tree lowi, highi, lowj, highj, type; @@ -3184,8 +3203,32 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, candidates.safe_push (&ranges[j]); } - /* If we need otherwise 3 or more comparisons, use a bit test. */ - if (candidates.length () >= 2) + /* If every possible relative value of the expression is a valid shift + amount, then we can merge the entry test in the bit test. In this + case, if we would need otherwise 2 or more comparisons, then use + the bit test; in the other cases, the threshold is 3 comparisons. */ + wide_int min, max; + bool entry_test_needed; + if (TREE_CODE (exp) == SSA_NAME + && get_range_info (exp, &min, &max) == VR_RANGE + && wi::leu_p (max - min, prec - 1)) + { + wide_int ilowi = wi::to_wide (lowi); + if (wi::lt_p (min, ilowi, TYPE_SIGN (TREE_TYPE (lowi)))) + { + lowi = wide_int_to_tree (TREE_TYPE (lowi), min); + mask = wi::lshift (mask, ilowi - min); + } + else if (wi::gt_p (min, ilowi, TYPE_SIGN (TREE_TYPE (lowi)))) + { + lowi = wide_int_to_tree (TREE_TYPE (lowi), min); + mask = wi::lrshift (mask, min - ilowi); + } + entry_test_needed = false; + } + else + entry_test_needed = true; + if (candidates.length () >= (entry_test_needed ? 2 : 1)) { tree high = wide_int_to_tree (TREE_TYPE (lowi), wi::to_widest (lowi) @@ -3224,10 +3267,16 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, } } - tree tem = build_range_check (loc, optype, unshare_expr (exp), - false, lowi, high); - if (tem == NULL_TREE || is_gimple_val (tem)) - continue; + tree tem; + if (entry_test_needed) + { + tem = build_range_check (loc, optype, unshare_expr (exp), + false, lowi, high); + if (tem == NULL_TREE || is_gimple_val (tem)) + continue; + } + else + tem = NULL_TREE; tree etype = unsigned_type_for (TREE_TYPE (exp)); exp = fold_build2_loc (loc, MINUS_EXPR, etype, fold_convert_loc (loc, etype, exp), @@ -3248,27 +3297,34 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, split when it is running. So, temporarily emit a code with BIT_IOR_EXPR instead of &&, and fix it up in branch_fixup. */ - gimple_seq seq; - tem = force_gimple_operand (tem, &seq, true, NULL_TREE); - gcc_assert (TREE_CODE (tem) == SSA_NAME); - gimple_set_visited (SSA_NAME_DEF_STMT (tem), true); + gimple_seq seq = NULL; + if (tem) + { + tem = force_gimple_operand (tem, &seq, true, NULL_TREE); + gcc_assert (TREE_CODE (tem) == SSA_NAME); + gimple_set_visited (SSA_NAME_DEF_STMT (tem), true); + } gimple_seq seq2; exp = force_gimple_operand (exp, &seq2, true, NULL_TREE); gimple_seq_add_seq_without_update (&seq, seq2); gcc_assert (TREE_CODE (exp) == SSA_NAME); gimple_set_visited (SSA_NAME_DEF_STMT (exp), true); - gimple *g = gimple_build_assign (make_ssa_name (optype), - BIT_IOR_EXPR, tem, exp); - gimple_set_location (g, loc); - gimple_seq_add_stmt_without_update (&seq, g); - exp = gimple_assign_lhs (g); + if (tem) + { + gimple *g = gimple_build_assign (make_ssa_name (optype), + BIT_IOR_EXPR, tem, exp); + gimple_set_location (g, loc); + gimple_seq_add_stmt_without_update (&seq, g); + exp = gimple_assign_lhs (g); + } tree val = build_zero_cst (optype); if (update_range_test (&ranges[i], NULL, candidates.address (), candidates.length (), opcode, ops, exp, seq, false, val, val, strict_overflow_p)) { any_changes = true; - reassoc_branch_fixups.safe_push (tem); + if (tem) + reassoc_branch_fixups.safe_push (tem); } else gimple_seq_discard (seq); -- 2.30.2