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.
