* [PATCH] Fix compile time complexity of search_type_for_mask (PR tree-optimization/72866)
@ 2016-08-29 19:57 Jakub Jelinek
2016-08-30 4:42 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Jakub Jelinek @ 2016-08-29 19:57 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
Hi!
As the testcase shows, with deep chains of COND_EXPRs with the same
SSA_NAMEs appearing more than once in the various operands we can
hang in search_type_for_mask. Similar check_bool_pattern function
uses a hash_set to handle stmts that have been checked already, this patch
uses a hash_map in which we cache the return values once we've handled some
stmt already.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2016-08-29 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/72866
* tree-vect-patterns.c (search_type_for_mask): Turn into
a small wrapper, move all code to ...
(search_type_for_mask_1): ... this new function. Add caching
and adjust recursive calls.
* gcc.dg/vect/pr72866.c: New test.
--- gcc/tree-vect-patterns.c.jj 2016-07-21 08:59:55.000000000 +0200
+++ gcc/tree-vect-patterns.c 2016-08-29 19:26:12.807164641 +0200
@@ -3459,13 +3459,11 @@ adjust_bool_stmts (hash_set <gimple *> &
return gimple_assign_lhs (pattern_stmt);
}
-/* Return the proper type for converting bool VAR into
- an integer value or NULL_TREE if no such type exists.
- The type is chosen so that converted value has the
- same number of elements as VAR's vector type. */
+/* Helper for search_type_for_mask. */
static tree
-search_type_for_mask (tree var, vec_info *vinfo)
+search_type_for_mask_1 (tree var, vec_info *vinfo,
+ hash_map<gimple *, tree> &cache)
{
gimple *def_stmt;
enum vect_def_type dt;
@@ -3490,6 +3488,10 @@ search_type_for_mask (tree var, vec_info
if (!is_gimple_assign (def_stmt))
return NULL_TREE;
+ tree *c = cache.get (def_stmt);
+ if (c)
+ return *c;
+
rhs_code = gimple_assign_rhs_code (def_stmt);
rhs1 = gimple_assign_rhs1 (def_stmt);
@@ -3498,14 +3500,15 @@ search_type_for_mask (tree var, vec_info
case SSA_NAME:
case BIT_NOT_EXPR:
CASE_CONVERT:
- res = search_type_for_mask (rhs1, vinfo);
+ res = search_type_for_mask_1 (rhs1, vinfo, cache);
break;
case BIT_AND_EXPR:
case BIT_IOR_EXPR:
case BIT_XOR_EXPR:
- res = search_type_for_mask (rhs1, vinfo);
- res2 = search_type_for_mask (gimple_assign_rhs2 (def_stmt), vinfo);
+ res = search_type_for_mask_1 (rhs1, vinfo, cache);
+ res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt), vinfo,
+ cache);
if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2)))
res = res2;
break;
@@ -3517,8 +3520,9 @@ search_type_for_mask (tree var, vec_info
if (TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE)
{
- res = search_type_for_mask (rhs1, vinfo);
- res2 = search_type_for_mask (gimple_assign_rhs2 (def_stmt), vinfo);
+ res = search_type_for_mask_1 (rhs1, vinfo, cache);
+ res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt),
+ vinfo, cache);
if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2)))
res = res2;
break;
@@ -3526,12 +3530,18 @@ search_type_for_mask (tree var, vec_info
comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
if (comp_vectype == NULL_TREE)
- return NULL_TREE;
+ {
+ res = NULL_TREE;
+ break;
+ }
mask_type = get_mask_type_for_scalar_type (TREE_TYPE (rhs1));
if (!mask_type
|| !expand_vec_cmp_expr_p (comp_vectype, mask_type))
- return NULL_TREE;
+ {
+ res = NULL_TREE;
+ break;
+ }
if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
|| !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
@@ -3544,9 +3554,21 @@ search_type_for_mask (tree var, vec_info
}
}
+ cache.put (def_stmt, res);
return res;
}
+/* Return the proper type for converting bool VAR into
+ an integer value or NULL_TREE if no such type exists.
+ The type is chosen so that converted value has the
+ same number of elements as VAR's vector type. */
+
+static tree
+search_type_for_mask (tree var, vec_info *vinfo)
+{
+ hash_map<gimple *, tree> cache;
+ return search_type_for_mask_1 (var, vinfo, cache);
+}
/* Function vect_recog_bool_pattern
--- gcc/testsuite/gcc.dg/vect/pr72866.c.jj 2016-08-29 19:28:22.453646025 +0200
+++ gcc/testsuite/gcc.dg/vect/pr72866.c 2016-08-29 19:28:17.000000000 +0200
@@ -0,0 +1,19 @@
+/* PR tree-optimization/72866 */
+/* { dg-do compile } */
+
+unsigned int dl;
+int rx, lb;
+
+void
+fo (int jv, int be)
+{
+ const unsigned int xw = 16;
+ unsigned int ya, wo;
+
+ for (ya = 0; ya < 2; ++ya)
+ for (wo = 0; wo < xw; ++wo)
+ {
+ dl += (jv ? be : rx);
+ rx += ((lb == 0) + 1);
+ }
+}
Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH] Fix compile time complexity of search_type_for_mask (PR tree-optimization/72866)
2016-08-29 19:57 [PATCH] Fix compile time complexity of search_type_for_mask (PR tree-optimization/72866) Jakub Jelinek
@ 2016-08-30 4:42 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2016-08-30 4:42 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches
On August 29, 2016 9:57:00 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>Hi!
>
>As the testcase shows, with deep chains of COND_EXPRs with the same
>SSA_NAMEs appearing more than once in the various operands we can
>hang in search_type_for_mask. Similar check_bool_pattern function
>uses a hash_set to handle stmts that have been checked already, this
>patch
>uses a hash_map in which we cache the return values once we've handled
>some
>stmt already.
>
>Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Thanks,
Richard.
>2016-08-29 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/72866
> * tree-vect-patterns.c (search_type_for_mask): Turn into
> a small wrapper, move all code to ...
> (search_type_for_mask_1): ... this new function. Add caching
> and adjust recursive calls.
>
> * gcc.dg/vect/pr72866.c: New test.
>
>--- gcc/tree-vect-patterns.c.jj 2016-07-21 08:59:55.000000000 +0200
>+++ gcc/tree-vect-patterns.c 2016-08-29 19:26:12.807164641 +0200
>@@ -3459,13 +3459,11 @@ adjust_bool_stmts (hash_set <gimple *> &
> return gimple_assign_lhs (pattern_stmt);
> }
>
>-/* Return the proper type for converting bool VAR into
>- an integer value or NULL_TREE if no such type exists.
>- The type is chosen so that converted value has the
>- same number of elements as VAR's vector type. */
>+/* Helper for search_type_for_mask. */
>
> static tree
>-search_type_for_mask (tree var, vec_info *vinfo)
>+search_type_for_mask_1 (tree var, vec_info *vinfo,
>+ hash_map<gimple *, tree> &cache)
> {
> gimple *def_stmt;
> enum vect_def_type dt;
>@@ -3490,6 +3488,10 @@ search_type_for_mask (tree var, vec_info
> if (!is_gimple_assign (def_stmt))
> return NULL_TREE;
>
>+ tree *c = cache.get (def_stmt);
>+ if (c)
>+ return *c;
>+
> rhs_code = gimple_assign_rhs_code (def_stmt);
> rhs1 = gimple_assign_rhs1 (def_stmt);
>
>@@ -3498,14 +3500,15 @@ search_type_for_mask (tree var, vec_info
> case SSA_NAME:
> case BIT_NOT_EXPR:
> CASE_CONVERT:
>- res = search_type_for_mask (rhs1, vinfo);
>+ res = search_type_for_mask_1 (rhs1, vinfo, cache);
> break;
>
> case BIT_AND_EXPR:
> case BIT_IOR_EXPR:
> case BIT_XOR_EXPR:
>- res = search_type_for_mask (rhs1, vinfo);
>- res2 = search_type_for_mask (gimple_assign_rhs2 (def_stmt),
>vinfo);
>+ res = search_type_for_mask_1 (rhs1, vinfo, cache);
>+ res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt),
>vinfo,
>+ cache);
> if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2)))
> res = res2;
> break;
>@@ -3517,8 +3520,9 @@ search_type_for_mask (tree var, vec_info
>
> if (TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE)
> {
>- res = search_type_for_mask (rhs1, vinfo);
>- res2 = search_type_for_mask (gimple_assign_rhs2 (def_stmt),
>vinfo);
>+ res = search_type_for_mask_1 (rhs1, vinfo, cache);
>+ res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt),
>+ vinfo, cache);
> if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION
>(res2)))
> res = res2;
> break;
>@@ -3526,12 +3530,18 @@ search_type_for_mask (tree var, vec_info
>
> comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
> if (comp_vectype == NULL_TREE)
>- return NULL_TREE;
>+ {
>+ res = NULL_TREE;
>+ break;
>+ }
>
> mask_type = get_mask_type_for_scalar_type (TREE_TYPE (rhs1));
> if (!mask_type
> || !expand_vec_cmp_expr_p (comp_vectype, mask_type))
>- return NULL_TREE;
>+ {
>+ res = NULL_TREE;
>+ break;
>+ }
>
> if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
> || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
>@@ -3544,9 +3554,21 @@ search_type_for_mask (tree var, vec_info
> }
> }
>
>+ cache.put (def_stmt, res);
> return res;
> }
>
>+/* Return the proper type for converting bool VAR into
>+ an integer value or NULL_TREE if no such type exists.
>+ The type is chosen so that converted value has the
>+ same number of elements as VAR's vector type. */
>+
>+static tree
>+search_type_for_mask (tree var, vec_info *vinfo)
>+{
>+ hash_map<gimple *, tree> cache;
>+ return search_type_for_mask_1 (var, vinfo, cache);
>+}
>
> /* Function vect_recog_bool_pattern
>
>--- gcc/testsuite/gcc.dg/vect/pr72866.c.jj 2016-08-29
>19:28:22.453646025 +0200
>+++ gcc/testsuite/gcc.dg/vect/pr72866.c 2016-08-29 19:28:17.000000000
>+0200
>@@ -0,0 +1,19 @@
>+/* PR tree-optimization/72866 */
>+/* { dg-do compile } */
>+
>+unsigned int dl;
>+int rx, lb;
>+
>+void
>+fo (int jv, int be)
>+{
>+ const unsigned int xw = 16;
>+ unsigned int ya, wo;
>+
>+ for (ya = 0; ya < 2; ++ya)
>+ for (wo = 0; wo < xw; ++wo)
>+ {
>+ dl += (jv ? be : rx);
>+ rx += ((lb == 0) + 1);
>+ }
>+}
>
> Jakub
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2016-08-30 4:42 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-08-29 19:57 [PATCH] Fix compile time complexity of search_type_for_mask (PR tree-optimization/72866) Jakub Jelinek
2016-08-30 4:42 ` 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).