* [PATCH 2/2] tree-optimization/105651 - simplify address range overlap check
@ 2022-07-26 13:41 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-07-26 13:41 UTC (permalink / raw)
To: gcc-patches
The following adds a pattern for ifcombine to match an address overlap
check and use alias analysis to decide overlap at compile-time. This
happens with code generated from std::string as shown in the PR even
if meanwhile the trunk generated code causes the pattern to no longer
match.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
PR tree-optimization/105651
* match.pd: Add pattern optimizing address range overlap.
* gcc.dg/tree-ssa/ssa-ifcombine-14.c: New testcase.
---
gcc/match.pd | 47 +++++++++++++++++++
.../gcc.dg/tree-ssa/ssa-ifcombine-14.c | 18 +++++++
2 files changed, 65 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 330c1db0c8e..7661317a53f 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -7806,6 +7806,53 @@ and,
{ swap_p ? @0 : @2; }))
{ rhs_tree; })))))))))
+/* Similarly handle
+
+ (uint) @A < (uint) @B + @BO & (uint) @B < (uint) @A + @AO
+
+ in particular optimize the case when @A and @B are within distinct
+ objects and all addresses are invariant as happens with std::string
+ in PR105651. */
+(for cmp1 (lt le le lt)
+ cmp2 (lt le lt le)
+ (simplify
+ (bit_and (cmp1:c (convert@4 @0) (convert @1))
+ (cmp2:c (convert@5 @2) (convert @3)))
+ (with
+ {
+ tree addr0, addr1, addr2, addr3;
+ /* Instead of multiple matchings see to extract a base from the
+ conversion operands since all we need to relate is bases. */
+ auto get_addr = [] (tree op) -> tree {
+ if (TREE_CODE (op) == ADDR_EXPR)
+ return op;
+ else if (TREE_CODE (op) == SSA_NAME)
+ if (gassign *ass = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op)))
+ if (gimple_assign_rhs_code (ass) == ADDR_EXPR
+ || gimple_assign_rhs_code (ass) == POINTER_PLUS_EXPR)
+ return gimple_assign_rhs1 (ass);
+ return op;
+ };
+ }
+ (if ((addr0 = get_addr (@0))
+ && (addr1 = get_addr (@1))
+ && (addr2 = get_addr (@2))
+ && (addr3 = get_addr (@3))
+ && INTEGRAL_TYPE_P (TREE_TYPE (@4))
+ && types_match (TREE_TYPE (@4), TREE_TYPE (@5)))
+ (with { poly_int64 diff0, diff1; }
+ (if (ptr_difference_const (addr3, addr0, &diff0)
+ && known_ge (diff0, 0)
+ && ptr_difference_const (addr1, addr2, &diff1)
+ && known_ge (diff1, 0)
+ /* Since we are in the end just comparing whether two objects may
+ overlap via alias analysis it isn't really important to exactly
+ compute the ranges above. ptr_difference_const mainly determines
+ there is a common base and the known_ge is testing we are comparing
+ the proper end points. */
+ && !ptr_derefs_may_alias_p (addr0, addr1))
+ { constant_boolean_node (false, type); }))))))
+
/* Fold REDUC (@0 & @1) -> @0[I] & @1[I] if element I is the only nonzero
element of @1. */
(for reduc (IFN_REDUC_PLUS IFN_REDUC_IOR IFN_REDUC_XOR)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
new file mode 100644
index 00000000000..f058ac04a36
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
@@ -0,0 +1,18 @@
+/* From PR105651 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ifcombine" } */
+
+typedef __UINTPTR_TYPE__ uintptr_t;
+void init (char *a);
+void oops ();
+void foo ()
+{
+ char a[16];
+ init (a);
+ char *p = "foo";
+ if ((uintptr_t)a < (uintptr_t)&p[4] && (uintptr_t)p < (uintptr_t)&a[16])
+ oops ();
+}
+
+/* { dg-final { scan-tree-dump "optimizing two comparisons to 0" "ifcombine" } } */
+/* { dg-final { scan-tree-dump-not "oops" "ifcombine" } } */
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH 2/2] tree-optimization/105651 - simplify address range overlap check
@ 2022-07-26 13:41 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-07-26 13:41 UTC (permalink / raw)
To: gcc-patches
The following adds a pattern for ifcombine to match an address overlap
check and use alias analysis to decide overlap at compile-time. This
happens with code generated from std::string as shown in the PR even
if meanwhile the trunk generated code causes the pattern to no longer
match.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
PR tree-optimization/105651
* match.pd: Add pattern optimizing address range overlap.
* gcc.dg/tree-ssa/ssa-ifcombine-14.c: New testcase.
---
gcc/match.pd | 47 +++++++++++++++++++
.../gcc.dg/tree-ssa/ssa-ifcombine-14.c | 18 +++++++
2 files changed, 65 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 330c1db0c8e..7661317a53f 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -7806,6 +7806,53 @@ and,
{ swap_p ? @0 : @2; }))
{ rhs_tree; })))))))))
+/* Similarly handle
+
+ (uint) @A < (uint) @B + @BO & (uint) @B < (uint) @A + @AO
+
+ in particular optimize the case when @A and @B are within distinct
+ objects and all addresses are invariant as happens with std::string
+ in PR105651. */
+(for cmp1 (lt le le lt)
+ cmp2 (lt le lt le)
+ (simplify
+ (bit_and (cmp1:c (convert@4 @0) (convert @1))
+ (cmp2:c (convert@5 @2) (convert @3)))
+ (with
+ {
+ tree addr0, addr1, addr2, addr3;
+ /* Instead of multiple matchings see to extract a base from the
+ conversion operands since all we need to relate is bases. */
+ auto get_addr = [] (tree op) -> tree {
+ if (TREE_CODE (op) == ADDR_EXPR)
+ return op;
+ else if (TREE_CODE (op) == SSA_NAME)
+ if (gassign *ass = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op)))
+ if (gimple_assign_rhs_code (ass) == ADDR_EXPR
+ || gimple_assign_rhs_code (ass) == POINTER_PLUS_EXPR)
+ return gimple_assign_rhs1 (ass);
+ return op;
+ };
+ }
+ (if ((addr0 = get_addr (@0))
+ && (addr1 = get_addr (@1))
+ && (addr2 = get_addr (@2))
+ && (addr3 = get_addr (@3))
+ && INTEGRAL_TYPE_P (TREE_TYPE (@4))
+ && types_match (TREE_TYPE (@4), TREE_TYPE (@5)))
+ (with { poly_int64 diff0, diff1; }
+ (if (ptr_difference_const (addr3, addr0, &diff0)
+ && known_ge (diff0, 0)
+ && ptr_difference_const (addr1, addr2, &diff1)
+ && known_ge (diff1, 0)
+ /* Since we are in the end just comparing whether two objects may
+ overlap via alias analysis it isn't really important to exactly
+ compute the ranges above. ptr_difference_const mainly determines
+ there is a common base and the known_ge is testing we are comparing
+ the proper end points. */
+ && !ptr_derefs_may_alias_p (addr0, addr1))
+ { constant_boolean_node (false, type); }))))))
+
/* Fold REDUC (@0 & @1) -> @0[I] & @1[I] if element I is the only nonzero
element of @1. */
(for reduc (IFN_REDUC_PLUS IFN_REDUC_IOR IFN_REDUC_XOR)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
new file mode 100644
index 00000000000..f058ac04a36
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
@@ -0,0 +1,18 @@
+/* From PR105651 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ifcombine" } */
+
+typedef __UINTPTR_TYPE__ uintptr_t;
+void init (char *a);
+void oops ();
+void foo ()
+{
+ char a[16];
+ init (a);
+ char *p = "foo";
+ if ((uintptr_t)a < (uintptr_t)&p[4] && (uintptr_t)p < (uintptr_t)&a[16])
+ oops ();
+}
+
+/* { dg-final { scan-tree-dump "optimizing two comparisons to 0" "ifcombine" } } */
+/* { dg-final { scan-tree-dump-not "oops" "ifcombine" } } */
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH 2/2] tree-optimization/105651 - simplify address range overlap check
@ 2022-07-26 13:41 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-07-26 13:41 UTC (permalink / raw)
To: gcc-patches
The following adds a pattern for ifcombine to match an address overlap
check and use alias analysis to decide overlap at compile-time. This
happens with code generated from std::string as shown in the PR even
if meanwhile the trunk generated code causes the pattern to no longer
match.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
PR tree-optimization/105651
* match.pd: Add pattern optimizing address range overlap.
* gcc.dg/tree-ssa/ssa-ifcombine-14.c: New testcase.
---
gcc/match.pd | 47 +++++++++++++++++++
.../gcc.dg/tree-ssa/ssa-ifcombine-14.c | 18 +++++++
2 files changed, 65 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 330c1db0c8e..7661317a53f 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -7806,6 +7806,53 @@ and,
{ swap_p ? @0 : @2; }))
{ rhs_tree; })))))))))
+/* Similarly handle
+
+ (uint) @A < (uint) @B + @BO & (uint) @B < (uint) @A + @AO
+
+ in particular optimize the case when @A and @B are within distinct
+ objects and all addresses are invariant as happens with std::string
+ in PR105651. */
+(for cmp1 (lt le le lt)
+ cmp2 (lt le lt le)
+ (simplify
+ (bit_and (cmp1:c (convert@4 @0) (convert @1))
+ (cmp2:c (convert@5 @2) (convert @3)))
+ (with
+ {
+ tree addr0, addr1, addr2, addr3;
+ /* Instead of multiple matchings see to extract a base from the
+ conversion operands since all we need to relate is bases. */
+ auto get_addr = [] (tree op) -> tree {
+ if (TREE_CODE (op) == ADDR_EXPR)
+ return op;
+ else if (TREE_CODE (op) == SSA_NAME)
+ if (gassign *ass = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op)))
+ if (gimple_assign_rhs_code (ass) == ADDR_EXPR
+ || gimple_assign_rhs_code (ass) == POINTER_PLUS_EXPR)
+ return gimple_assign_rhs1 (ass);
+ return op;
+ };
+ }
+ (if ((addr0 = get_addr (@0))
+ && (addr1 = get_addr (@1))
+ && (addr2 = get_addr (@2))
+ && (addr3 = get_addr (@3))
+ && INTEGRAL_TYPE_P (TREE_TYPE (@4))
+ && types_match (TREE_TYPE (@4), TREE_TYPE (@5)))
+ (with { poly_int64 diff0, diff1; }
+ (if (ptr_difference_const (addr3, addr0, &diff0)
+ && known_ge (diff0, 0)
+ && ptr_difference_const (addr1, addr2, &diff1)
+ && known_ge (diff1, 0)
+ /* Since we are in the end just comparing whether two objects may
+ overlap via alias analysis it isn't really important to exactly
+ compute the ranges above. ptr_difference_const mainly determines
+ there is a common base and the known_ge is testing we are comparing
+ the proper end points. */
+ && !ptr_derefs_may_alias_p (addr0, addr1))
+ { constant_boolean_node (false, type); }))))))
+
/* Fold REDUC (@0 & @1) -> @0[I] & @1[I] if element I is the only nonzero
element of @1. */
(for reduc (IFN_REDUC_PLUS IFN_REDUC_IOR IFN_REDUC_XOR)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
new file mode 100644
index 00000000000..f058ac04a36
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-14.c
@@ -0,0 +1,18 @@
+/* From PR105651 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ifcombine" } */
+
+typedef __UINTPTR_TYPE__ uintptr_t;
+void init (char *a);
+void oops ();
+void foo ()
+{
+ char a[16];
+ init (a);
+ char *p = "foo";
+ if ((uintptr_t)a < (uintptr_t)&p[4] && (uintptr_t)p < (uintptr_t)&a[16])
+ oops ();
+}
+
+/* { dg-final { scan-tree-dump "optimizing two comparisons to 0" "ifcombine" } } */
+/* { dg-final { scan-tree-dump-not "oops" "ifcombine" } } */
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-07-26 13:42 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-26 13:41 [PATCH 2/2] tree-optimization/105651 - simplify address range overlap check Richard Biener
2022-07-26 13:41 Richard Biener
2022-07-26 13:41 Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).