* [PATCH] tree-optimization PR/101014 - Limit new value calculations to first order effects.
@ 2021-06-14 21:07 Andrew MacLeod
2021-06-16 9:41 ` Maxim Kuvyrkov
0 siblings, 1 reply; 5+ messages in thread
From: Andrew MacLeod @ 2021-06-14 21:07 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1760 bytes --]
As mentioned in the Text from the PR:
"When a range is being calculated for an ssa-name, the propagation
process often goes along back edges. These back edges sometime require
other ssa-names which have not be processed yet. These are flagged as
"poor values" and when propagation is done, we visit the list of poor
values, calculate them, and see if that may result if a better range for
the original ssa-name.
The problem is that calculating these poor values may also spawn another
set of requests since the block at the far end of the back edge has not
been processed yet... its highly likely that some additional unprocessed
ssa-names are used in the calculation of that name, but typically they
do not affect the current range in a significant way.
Thus we mostly we care about the first order effect only. It turns out
to be very rare that a 2nd order effect on a back edge affects anything
that we don't catch later.
This patch turns off poor-value tagging when looking up the first order
values, thus avoiding the 2nd order and beyond cascading effects.
I haven't found a test case we miss yet because of this change, yet it
probably resolves a number of the outstanding compilation problems in a
significant way.
I think this will probably apply to gcc 11 in some form as well, so I'll
look at an equivalent patch for there."
This patch simplifies the enable_new_value routines.. replacing the
enable/disable with an enable with flag routine, which returns the
previous value.This lets us change the mode and then set it back to what
it was before. Seems better in general.
Then disables new values for 2nd+ order effects. GCC11 patch forthcoming.
Bootstraps on x86_64-pc-linux-gnu, no regressions. pushed.
Andrew
[-- Attachment #2: 101014.patch --]
[-- Type: text/x-patch, Size: 3760 bytes --]
commit 1d65d96fc3a0bc7139e619738793bf3c0ec3d0fa
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Mon Jun 14 15:33:59 2021 -0400
Limit new value calculations to first order effects.
When utilzing poor values during propagation, we mostly care about values that
were undefined/processed directly used in calcualting the SSA_NAME being
processed. 2nd level derivations of such poor values rarely affect the
inital calculation. Leave them to when they are directly encountered.
* gimple-range-cache.cc (ranger_cache::ranger_cache): Adjust.
(ranger_cache::enable_new_values): Set to specified value and
return the old value.
(ranger_cache::disable_new_values): Delete.
(ranger_cache::fill_block_cache): Disable non 1st order derived
poor values.
* gimple-range-cache.h (ranger_cache): Adjust prototypes.
* gimple-range.cc (gimple_ranger::range_of_expr): Adjust.
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 249515fbaf5..d9a57c294df 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -727,7 +727,7 @@ ranger_cache::ranger_cache (gimple_ranger &q) : query (q)
if (bb)
m_gori.exports (bb);
}
- enable_new_values ();
+ enable_new_values (true);
}
ranger_cache::~ranger_cache ()
@@ -748,21 +748,15 @@ ranger_cache::dump (FILE *f)
fprintf (f, "\n");
}
-// Allow the cache to flag and query new values when propagation is forced
-// to use an unknown value.
+// Allow or disallow the cache to flag and query new values when propagation
+// is forced to use an unknown value. The previous state is returned.
-void
-ranger_cache::enable_new_values ()
-{
- m_new_value_p = true;
-}
-
-// Disable new value querying.
-
-void
-ranger_cache::disable_new_values ()
+bool
+ranger_cache::enable_new_values (bool state)
{
- m_new_value_p = false;
+ bool ret = m_new_value_p;
+ m_new_value_p = state;
+ return ret;
}
// Dump the caches for basic block BB to file F.
@@ -1343,7 +1337,12 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
// Calculate a range at the exit from the block so the caches feeding
// this block will be filled, and we'll get a "better" value.
+ // Disallow additonal "poor values" during this phase to avoid
+ // iterations that are unlikely to be profitable for this name.
+ // See PR 101014.
+ bool state = enable_new_values (false);
query.range_on_exit (tmp, calc_bb, rec.calc);
+ enable_new_values (state);
// Then ask for NAME to be re-evaluated on outgoing edges and
// use any new values.
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index ce4449a08db..1a2aaceb3ed 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -101,8 +101,7 @@ public:
bool get_non_stale_global_range (irange &r, tree name);
void set_global_range (tree name, const irange &r);
- void enable_new_values ();
- void disable_new_values ();
+ bool enable_new_values (bool state);
non_null_ref m_non_null;
gori_compute m_gori;
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index b534b8e0a2c..481b89b2b80 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -1173,9 +1173,9 @@ gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
// trigger new value calculations. PR 100781.
if (is_gimple_debug (stmt))
{
- m_cache.disable_new_values ();
+ bool state = m_cache.enable_new_values (false);
m_cache.range_of_expr (r, expr, stmt);
- m_cache.enable_new_values ();
+ m_cache.enable_new_values (state);
return true;
}
basic_block bb = gimple_bb (stmt);
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] tree-optimization PR/101014 - Limit new value calculations to first order effects.
2021-06-14 21:07 [PATCH] tree-optimization PR/101014 - Limit new value calculations to first order effects Andrew MacLeod
@ 2021-06-16 9:41 ` Maxim Kuvyrkov
2021-06-16 16:05 ` Andrew MacLeod
2021-06-16 17:14 ` [PATCH] Avoid loading an undefined value in the ranger_cache constructor Andrew MacLeod
0 siblings, 2 replies; 5+ messages in thread
From: Maxim Kuvyrkov @ 2021-06-16 9:41 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: gcc-patches
> On 15 Jun 2021, at 00:07, Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>
> As mentioned in the Text from the PR:
>
> "When a range is being calculated for an ssa-name, the propagation process often goes along back edges. These back edges sometime require other ssa-names which have not be processed yet. These are flagged as "poor values" and when propagation is done, we visit the list of poor values, calculate them, and see if that may result if a better range for the original ssa-name.
>
> The problem is that calculating these poor values may also spawn another set of requests since the block at the far end of the back edge has not been processed yet... its highly likely that some additional unprocessed ssa-names are used in the calculation of that name, but typically they do not affect the current range in a significant way.
>
> Thus we mostly we care about the first order effect only. It turns out to be very rare that a 2nd order effect on a back edge affects anything that we don't catch later.
>
> This patch turns off poor-value tagging when looking up the first order values, thus avoiding the 2nd order and beyond cascading effects.
>
> I haven't found a test case we miss yet because of this change, yet it probably resolves a number of the outstanding compilation problems in a significant way.
>
> I think this will probably apply to gcc 11 in some form as well, so I'll look at an equivalent patch for there."
>
>
> This patch simplifies the enable_new_value routines.. replacing the enable/disable with an enable with flag routine, which returns the previous value.This lets us change the mode and then set it back to what it was before. Seems better in general.
>
> Then disables new values for 2nd+ order effects. GCC11 patch forthcoming.
>
> Bootstraps on x86_64-pc-linux-gnu, no regressions. pushed.
>
> Andrew
Hi Andrew,
This causes bootstrap-with-ubsan failure on at least aarch64-linux-gnu, likely, others:
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
# 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
>
> @@ -748,21 +748,15 @@ ranger_cache::dump (FILE *f)
> fprintf (f, "\n");
> }
>
> -// Allow the cache to flag and query new values when propagation is forced
> -// to use an unknown value.
> +// Allow or disallow the cache to flag and query new values when propagation
> +// is forced to use an unknown value. The previous state is returned.
>
> -void
> -ranger_cache::enable_new_values ()
> -{
> - m_new_value_p = true;
> -}
> -
> -// Disable new value querying.
> -
> -void
> -ranger_cache::disable_new_values ()
> +bool
> +ranger_cache::enable_new_values (bool state)
> {
> - m_new_value_p = false;
> + bool ret = m_new_value_p;
I think changing this to
bool ret = (bool) m_new_value_p;
might be enough, but you know this code better.
Would you please take a look at this?
> + m_new_value_p = state;
> + return ret;
> }
>
> // Dump the caches for basic block BB to file F.
Thanks,
--
Maxim Kuvyrkov
https://www.linaro.org
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] tree-optimization PR/101014 - Limit new value calculations to first order effects.
2021-06-16 9:41 ` Maxim Kuvyrkov
@ 2021-06-16 16:05 ` Andrew MacLeod
2021-06-16 17:14 ` [PATCH] Avoid loading an undefined value in the ranger_cache constructor Andrew MacLeod
1 sibling, 0 replies; 5+ messages in thread
From: Andrew MacLeod @ 2021-06-16 16:05 UTC (permalink / raw)
To: Maxim Kuvyrkov; +Cc: gcc-patches
On 6/16/21 5:41 AM, Maxim Kuvyrkov wrote:
>> On 15 Jun 2021, at 00:07, Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>>
>> As mentioned in the Text from the PR:
>>
>> "When a range is being calculated for an ssa-name, the propagation process often goes along back edges. These back edges sometime require other ssa-names which have not be processed yet. These are flagged as "poor values" and when propagation is done, we visit the list of poor values, calculate them, and see if that may result if a better range for the original ssa-name.
>>
>> The problem is that calculating these poor values may also spawn another set of requests since the block at the far end of the back edge has not been processed yet... its highly likely that some additional unprocessed ssa-names are used in the calculation of that name, but typically they do not affect the current range in a significant way.
>>
>> Thus we mostly we care about the first order effect only. It turns out to be very rare that a 2nd order effect on a back edge affects anything that we don't catch later.
>>
>> This patch turns off poor-value tagging when looking up the first order values, thus avoiding the 2nd order and beyond cascading effects.
>>
>> I haven't found a test case we miss yet because of this change, yet it probably resolves a number of the outstanding compilation problems in a significant way.
>>
>> I think this will probably apply to gcc 11 in some form as well, so I'll look at an equivalent patch for there."
>>
>>
>> This patch simplifies the enable_new_value routines.. replacing the enable/disable with an enable with flag routine, which returns the previous value.This lets us change the mode and then set it back to what it was before. Seems better in general.
>>
>> Then disables new values for 2nd+ order effects. GCC11 patch forthcoming.
>>
>> Bootstraps on x86_64-pc-linux-gnu, no regressions. pushed.
>>
>> Andrew
> Hi Andrew,
>
> This causes bootstrap-with-ubsan failure on at least aarch64-linux-gnu, likely, others:
>
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 48, which is not a valid value for type 'bool'
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
> # 00:42:32 /home/tcwg-buildslave/workspace/tcwg_gnu_0/abe/snapshots/gcc.git~master/gcc/gimple-range-cache.cc:757:8: runtime error: load of value 32, which is not a valid value for type 'bool'
>
>> @@ -748,21 +748,15 @@ ranger_cache::dump (FILE *f)
>> fprintf (f, "\n");
>> }
>>
>> -// Allow the cache to flag and query new values when propagation is forced
>> -// to use an unknown value.
>> +// Allow or disallow the cache to flag and query new values when propagation
>> +// is forced to use an unknown value. The previous state is returned.
>>
>> -void
>> -ranger_cache::enable_new_values ()
>> -{
>> - m_new_value_p = true;
>> -}
>> -
>> -// Disable new value querying.
>> -
>> -void
>> -ranger_cache::disable_new_values ()
>> +bool
>> +ranger_cache::enable_new_values (bool state)
>> {
>> - m_new_value_p = false;
>> + bool ret = m_new_value_p;
> I think changing this to
> bool ret = (bool) m_new_value_p;
> might be enough, but you know this code better.
>
> Would you please take a look at this?
>
>> + m_new_value_p = state;
>> + return ret;
>> }
>>
>> // Dump the caches for basic block BB to file F.
> Thanks,
>
Huh, not sure why that would matter since m_new_value_p is a bool.
My guess is (and this bugged me after I checked it in, just haven't
gotten to it yet), is that this is initialized in the constructor with a
call, and the return value ignored. Which means there is techincally a
load of an uninitialized value, which is then ignored. but the load may
happen. Im going to guess thats the issue. It needs fixing anyway
Im testing this fix, which i will check in. See if that solves the
ubsan issue.
@@ -727,7 +727,7 @@ ranger_cache::ranger_cache (gimple_ranger &q) :
query (q)
if (bb)
m_gori.exports (bb);
}
- enable_new_values (true);
+ m_new_value_p = true;
}
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH] Avoid loading an undefined value in the ranger_cache constructor.
2021-06-16 9:41 ` Maxim Kuvyrkov
2021-06-16 16:05 ` Andrew MacLeod
@ 2021-06-16 17:14 ` Andrew MacLeod
2021-06-17 8:01 ` Maxim Kuvyrkov
1 sibling, 1 reply; 5+ messages in thread
From: Andrew MacLeod @ 2021-06-16 17:14 UTC (permalink / raw)
To: Maxim Kuvyrkov; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 289 bytes --]
On 6/16/21 5:41 AM, Maxim Kuvyrkov wrote:
>
>> + m_new_value_p = state;
>> + return ret;
>> }
>>
>> // Dump the caches for basic block BB to file F.
> Thanks,
>
> --
> Maxim Kuvyrkov
> https://www.linaro.org
>
Let me know if the problem is resolved.
pushed as obvious.
Andrew
[-- Attachment #2: unin.diff --]
[-- Type: text/x-patch, Size: 953 bytes --]
commit bdfc1207bd20cf1ad81fca121e4f7df4995cc0d6
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Wed Jun 16 13:01:21 2021 -0400
Avoid loading an undefined value in the ranger_cache constructor.
Enable_new_values takes a boolean, returning the old value. The constructor
for ranger_cache initialized the m_new_value_p field by calling this routine
and ignorng the result. This potentially loads the old value uninitialized.
* gimple-range-cache.cc (ranger_cache::ranger_cache): Initialize
m_new_value_p directly.
diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index d9a57c294df..37e2acb19f9 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -727,7 +727,7 @@ ranger_cache::ranger_cache (gimple_ranger &q) : query (q)
if (bb)
m_gori.exports (bb);
}
- enable_new_values (true);
+ m_new_value_p = true;
}
ranger_cache::~ranger_cache ()
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2021-06-17 8:01 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-06-14 21:07 [PATCH] tree-optimization PR/101014 - Limit new value calculations to first order effects Andrew MacLeod
2021-06-16 9:41 ` Maxim Kuvyrkov
2021-06-16 16:05 ` Andrew MacLeod
2021-06-16 17:14 ` [PATCH] Avoid loading an undefined value in the ranger_cache constructor Andrew MacLeod
2021-06-17 8:01 ` Maxim Kuvyrkov
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).