[gcc r11-1675] Take into account range info to optimize range tests into bit tests
Eric Botcazou
ebotcazou@gcc.gnu.org
Fri Jun 26 13:27:13 GMT 2020
https://gcc.gnu.org/g:b3d77404c060c0d65d8d4c97254995737d0fc032
commit r11-1675-gb3d77404c060c0d65d8d4c97254995737d0fc032
Author: Eric Botcazou <ebotcazou@gcc.gnu.org>
Date: Fri Jun 26 15:23:05 2020 +0200
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.
Diff:
---
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(-)
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<struct range_entry *, 64> 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);
More information about the Gcc-cvs
mailing list