* [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations.
@ 2022-01-10 23:27 Andrew MacLeod
2022-01-11 7:01 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: Andrew MacLeod @ 2022-01-10 23:27 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2153 bytes --]
This test case demonstrates an unnoticed exponential situation in range-ops.
We end up unrolling the loop, and the pattern of code creates a set of
cascading multiplies for which we can precisely evaluate them with
sub-ranges.
For instance, we calculated :
_38 = int [8192, 8192][24576, 24576][40960, 40960][57344, 57344]
so _38 has 4 sub-ranges, and then we calculate:
_39 = _38 * _38;
we do 16 sub-range multiplications and end up with: int [67108864,
67108864][201326592, 201326592][335544320, 335544320][469762048,
469762048][603979776, 603979776][1006632960, 1006632960][1409286144,
1409286144][1677721600, 1677721600][+INF, +INF]
This feeds other multiplies (_39 * _39) and progresses rapidly to blow
up the number of sub-ranges in subsequent operations.
Folding of sub-ranges is an O(n*m) process. We perform the operation on
each pair of sub-ranges and union them. Values like _38 * _38 that
continue feeding each other quickly become exponential.
Then combining that with union (an inherently linear operation over the
number of sub-ranges) at each step of the way adds an additional
quadratic operation on top of the exponential factor.
This patch adjusts the wi_fold routine to recognize when the calculation
is moving in an exponential direction, simply produce a summary result
instead of a precise one. The attached patch does this if (#LH
sub-ranges * #RH sub-ranges > 12)... then it just performs the operation
with the lower and upper bound instead. We could choose a different
number, but that one seems to keep things under control, and allows us
to process up to a 3x4 operation for precision (there is a testcase in
the testsuite for this combination gcc.dg/tree-ssa/pr61839_2.c).
Longer term, we might want adjust this routine to be slightly smarter
than that, but this is a virtually zero-risk solution this late in the
release cycle.
This also a generalize ~1% speedup in the VRP2 pass across 380 gcc
source files, but I'm sure has much more dramatic results at -O3 that
this testcase exposes.
Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk?
Andrew
[-- Attachment #2: 821.diff --]
[-- Type: text/x-patch, Size: 1356 bytes --]
commit d8c5c37d5362bd876118949de76086daba756ace
Author: Andrew MacLeod <amacleod@redhat.com>
Date: Mon Jan 10 13:33:44 2022 -0500
Prevent exponential range calculations.
Produce a summary result for any operation involving too many subranges.
PR tree-optimization/103821
* range-op.cc (range_operator::fold_range): Only do precise ranges
when there are not too many subranges.
range_operator::fold_range
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 1af42ebc376..a4f6e9eba29 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -209,10 +209,12 @@ range_operator::fold_range (irange &r, tree type,
unsigned num_rh = rh.num_pairs ();
// If both ranges are single pairs, fold directly into the result range.
- if (num_lh == 1 && num_rh == 1)
+ // If the number of subranges grows too high, produce a summary result as the
+ // loop becomes exponential with little benefit. See PR 103821.
+ if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
{
- wi_fold_in_parts (r, type, lh.lower_bound (0), lh.upper_bound (0),
- rh.lower_bound (0), rh.upper_bound (0));
+ wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
+ rh.lower_bound (), rh.upper_bound ());
op1_op2_relation_effect (r, type, lh, rh, rel);
return true;
}
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations.
2022-01-10 23:27 [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations Andrew MacLeod
@ 2022-01-11 7:01 ` Richard Biener
2022-01-11 14:15 ` Andrew MacLeod
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2022-01-11 7:01 UTC (permalink / raw)
To: Andrew MacLeod; +Cc: gcc-patches
On Tue, Jan 11, 2022 at 12:28 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This test case demonstrates an unnoticed exponential situation in range-ops.
>
> We end up unrolling the loop, and the pattern of code creates a set of
> cascading multiplies for which we can precisely evaluate them with
> sub-ranges.
>
> For instance, we calculated :
>
> _38 = int [8192, 8192][24576, 24576][40960, 40960][57344, 57344]
>
> so _38 has 4 sub-ranges, and then we calculate:
>
> _39 = _38 * _38;
>
> we do 16 sub-range multiplications and end up with: int [67108864,
> 67108864][201326592, 201326592][335544320, 335544320][469762048,
> 469762048][603979776, 603979776][1006632960, 1006632960][1409286144,
> 1409286144][1677721600, 1677721600][+INF, +INF]
>
> This feeds other multiplies (_39 * _39) and progresses rapidly to blow
> up the number of sub-ranges in subsequent operations.
>
> Folding of sub-ranges is an O(n*m) process. We perform the operation on
> each pair of sub-ranges and union them. Values like _38 * _38 that
> continue feeding each other quickly become exponential.
>
> Then combining that with union (an inherently linear operation over the
> number of sub-ranges) at each step of the way adds an additional
> quadratic operation on top of the exponential factor.
>
> This patch adjusts the wi_fold routine to recognize when the calculation
> is moving in an exponential direction, simply produce a summary result
> instead of a precise one. The attached patch does this if (#LH
> sub-ranges * #RH sub-ranges > 12)... then it just performs the operation
> with the lower and upper bound instead. We could choose a different
> number, but that one seems to keep things under control, and allows us
> to process up to a 3x4 operation for precision (there is a testcase in
> the testsuite for this combination gcc.dg/tree-ssa/pr61839_2.c).
> Longer term, we might want adjust this routine to be slightly smarter
> than that, but this is a virtually zero-risk solution this late in the
> release cycle.
I'm not sure we can do smarter in a good way other than maybe having
a range helper that reduces a N component range to M components
with maintaining as much precision as possible? Like for [1, 1] u [3, 3]
u [100, 100] and requesting at most 2 elements merge [1, 1] and [3, 3]
and not [100, 100]. That should eventually be doable in O(n log n).
> This also a generalize ~1% speedup in the VRP2 pass across 380 gcc
> source files, but I'm sure has much more dramatic results at -O3 that
> this testcase exposes.
>
> Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk?
OK.
Thanks,
Richard.
>
> Andrew
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations.
2022-01-11 7:01 ` Richard Biener
@ 2022-01-11 14:15 ` Andrew MacLeod
0 siblings, 0 replies; 3+ messages in thread
From: Andrew MacLeod @ 2022-01-11 14:15 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, Aldy Hernandez
On 1/11/22 02:01, Richard Biener wrote:
> On Tue, Jan 11, 2022 at 12:28 AM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> This test case demonstrates an unnoticed exponential situation in range-ops.
>>
>> We end up unrolling the loop, and the pattern of code creates a set of
>> cascading multiplies for which we can precisely evaluate them with
>> sub-ranges.
>>
>> For instance, we calculated :
>>
>> _38 = int [8192, 8192][24576, 24576][40960, 40960][57344, 57344]
>>
>> so _38 has 4 sub-ranges, and then we calculate:
>>
>> _39 = _38 * _38;
>>
>> we do 16 sub-range multiplications and end up with: int [67108864,
>> 67108864][201326592, 201326592][335544320, 335544320][469762048,
>> 469762048][603979776, 603979776][1006632960, 1006632960][1409286144,
>> 1409286144][1677721600, 1677721600][+INF, +INF]
>>
>> This feeds other multiplies (_39 * _39) and progresses rapidly to blow
>> up the number of sub-ranges in subsequent operations.
>>
>> Folding of sub-ranges is an O(n*m) process. We perform the operation on
>> each pair of sub-ranges and union them. Values like _38 * _38 that
>> continue feeding each other quickly become exponential.
>>
>> Then combining that with union (an inherently linear operation over the
>> number of sub-ranges) at each step of the way adds an additional
>> quadratic operation on top of the exponential factor.
>>
>> This patch adjusts the wi_fold routine to recognize when the calculation
>> is moving in an exponential direction, simply produce a summary result
>> instead of a precise one. The attached patch does this if (#LH
>> sub-ranges * #RH sub-ranges > 12)... then it just performs the operation
>> with the lower and upper bound instead. We could choose a different
>> number, but that one seems to keep things under control, and allows us
>> to process up to a 3x4 operation for precision (there is a testcase in
>> the testsuite for this combination gcc.dg/tree-ssa/pr61839_2.c).
>> Longer term, we might want adjust this routine to be slightly smarter
>> than that, but this is a virtually zero-risk solution this late in the
>> release cycle.
> I'm not sure we can do smarter in a good way other than maybe having
> a range helper that reduces a N component range to M components
> with maintaining as much precision as possible? Like for [1, 1] u [3, 3]
> u [100, 100] and requesting at most 2 elements merge [1, 1] and [3, 3]
> and not [100, 100]. That should eventually be doable in O(n log n).
Yeah, similar to my line of thought. It may also be worth considering
something similar after we have calculated a range sometimes. if the
resulting range has more than N sub-ranges, look to see if it is
worthwhile trying to compress it at that point too maybe. Something for
the next stage-1 to consider.
Andrew
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-01-11 14:15 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-01-10 23:27 [PATCH] PR tree-optimization/103821 - Prevent exponential range calculations Andrew MacLeod
2022-01-11 7:01 ` Richard Biener
2022-01-11 14:15 ` Andrew MacLeod
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).