[PATCH] PR tree-optimization/103821 - Prevent exponential range calculations.

[Andrew MacLeod <amacleod@redhat.com>]

[-- 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;
     }