From: Andrew MacLeod <amacleod@redhat.com>
To: gcc-patches <gcc-patches@gcc.gnu.org>
Subject: [PATCH] PR tree-optimization/103254 - Limit depth for all GORI expressions.
Date: Thu, 18 Nov 2021 14:28:10 -0500 [thread overview]
Message-ID: <eb57c126-4b5e-dedf-e4e5-24036616a7aa@redhat.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1572 bytes --]
At issue here is the dynamic approach we currently use for outgoing edge
calculations. It isn't normally a problem, but once you get a very
large number of possible outgoing values (ie very long unrolled blocks)
with pairs of values on a statement, and individual queries for each
one, it becomes exponential if they relate to each other.
So. We previously introduced a param for PR 100081 which limited the
depth of logical expressions GORI would pursue because we always make 2
or 4 queries for each logical expression, which accelerated the
exponential behaviour much quicker.
This patch reuses that to apply to any statement which has 2 ssa-names,
as the potential for 2 queries can happen then as well.. leading to
exponential behaviour. Each statement we step back through with
multiple ssa-names decreases the odds of calculating a useful outgoing
range anyway. This will remove ridiculous behaviour like this PR
demonstrates.
Next release I plan to revamp GORI to cache outgoing values, which will
eliminate all this sort of behaviour, and we can remove all such
restrictions.
Bootstrapped on x86_64-pc-linux-gnu with no regressions. OK for trunk?
Andrew
PS. This also points out something we are investigating with the
threader. There are no uses of _14 outside the block, so asking for its
range is problematic and contributing to excess work and cache filling
that we don't need to be doing. The VRP passes do not demonstrate this
behaviour unless, as observed, we ask for details output which queries
*all* the names.
[-- Attachment #2: 254-2.diff --]
[-- Type: text/x-patch, Size: 2883 bytes --]
commit bfecf512fb719dcb072e54d842b1e7a62fe03d2d
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Wed Nov 17 14:14:06 2021 -0500
Limit depth for all GORI expressions.
Apply the logical_depth limit ranger uses to all stmts with multiple ssa-names
to avoid excessive outgoing calculations.
gcc/
PR tree-optimization/103254
* gimple-range-gori.cc (range_def_chain::get_def_chain): Limit the
depth for all statements with multple ssa names.
gcc/testsuite/
* gcc.dg/pr103254.c: New.
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index fb2d571ef44..911d7ac4ec8 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -331,7 +331,6 @@ range_def_chain::get_def_chain (tree name)
{
tree ssa1, ssa2, ssa3;
unsigned v = SSA_NAME_VERSION (name);
- bool is_logical = false;
// If it has already been processed, just return the cached value.
if (has_def_chain (name))
@@ -348,15 +347,6 @@ range_def_chain::get_def_chain (tree name)
gimple *stmt = SSA_NAME_DEF_STMT (name);
if (gimple_range_handler (stmt))
{
- is_logical = is_gimple_logical_p (stmt);
- // Terminate the def chains if we see too many cascading logical stmts.
- if (is_logical)
- {
- if (m_logical_depth == param_ranger_logical_depth)
- return NULL;
- m_logical_depth++;
- }
-
ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
ssa3 = NULL_TREE;
@@ -376,6 +366,14 @@ range_def_chain::get_def_chain (tree name)
return NULL;
}
+ // Terminate the def chains if we see too many cascading stmts.
+ if (m_logical_depth == param_ranger_logical_depth)
+ return NULL;
+
+ // Increase the depth if we have a pair of ssa-names.
+ if (ssa1 && ssa2)
+ m_logical_depth++;
+
register_dependency (name, ssa1, gimple_bb (stmt));
register_dependency (name, ssa2, gimple_bb (stmt));
register_dependency (name, ssa3, gimple_bb (stmt));
@@ -383,7 +381,7 @@ range_def_chain::get_def_chain (tree name)
if (!ssa1 && !ssa2 & !ssa3)
set_import (m_def_chain[v], name, NULL);
- if (is_logical)
+ if (ssa1 && ssa2)
m_logical_depth--;
return m_def_chain[v].bm;
diff --git a/gcc/testsuite/gcc.dg/pr103254.c b/gcc/testsuite/gcc.dg/pr103254.c
new file mode 100644
index 00000000000..62d2415f216
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr103254.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+/* { dg-timeout 10 } */
+
+short int i;
+
+void
+foo (void)
+{
+ for (i = 1; i < 2; i += 4)
+ {
+ int j;
+
+ for (j = 0; j < 5; j += 4)
+ {
+ int k;
+
+ for (k = 0; k < 68; k += 4)
+ {
+ i &= j;
+ j &= i;
+ }
+ }
+ }
+}
next reply other threads:[~2021-11-18 19:28 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-11-18 19:28 Andrew MacLeod [this message]
2021-11-19 9:21 ` Richard Biener
2021-11-19 15:00 ` Andrew MacLeod
2021-11-19 18:13 ` Richard Biener
2021-11-19 18:53 ` Andrew MacLeod
2021-11-19 16:43 ` Andrew MacLeod
2021-11-19 10:15 ` Aldy Hernandez
2021-11-19 14:38 ` Andrew MacLeod
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=eb57c126-4b5e-dedf-e4e5-24036616a7aa@redhat.com \
--to=amacleod@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).