Hi,
...into bit tests, as done by optimize_range_tests_to_bit_test of the reassoc
pass. 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 if possible.
Tested on x86-64/Linux, OK for the mainline?
2020-06-25 Eric Botcazou <ebotca...@adacore.com>
* 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 in this case.
2020-06-25 Eric Botcazou <ebotca...@adacore.com>
* exp_ch4.adb (Expand_Set_Membership): Expand the membership test
using left associativity instead of right associativity.
2020-06-25 Eric Botcazou <ebotca...@adacore.com>
* gnat.dg/opt86_pkg.ads: New helper.
* gnat.dg/opt86a.adb: New test.
* gnat.dg/opt86b.adb: Likewise.
* gnat.dg/opt86c.adb: Likewise.
--
Eric Botcazoudiff --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/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);
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;
-- { 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" } }
-- { 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" } }
-- { 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" } }
