[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103821

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
Interesting.  This isn't caused by jump threading, just exposed by it.

We end up unrolling this loop, and the pattern of code creates a set of
cascading multiplies for which we can precisely evaluate them with subranges.

For instance, we calculate:

_38 = int [8192, 8192][24576, 24576][40960, 40960][57344, 57344]

so _38 has 4 subranges, and then we calculate:

_39 = _38 * _38;

we do 16 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 and progresses rapidly to blow up the number of
subranges, which are then propagated via PHIs and other operations.

Folding of subranges is an O(n*m) process. We perform the operation on each
pair of subranges 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 subranges) at each step of the way adds an additional quadratic operation on
top of the exponential factor. 

I will adjust the wi_fold routine to recognize when the calculation is moving
in an exponential direction, simply produce a summary a result instead of a
precise one.  Longer term, we could consider merging some of the subranges to
prevent the exponential growth, but still retain some precision.