RFR(S) 8033260: assert(lrg._area >= 0.0) failed: negative spill area

[Niclas Adlertz]

Hi all,

Background:
In 8034198, where we did a big cleanup in the build_ifg_physical method. 
One thing we did was to change an assert from:
lrg._area -= cost;
assert(!(lrg._area < 0.0), "negative spill area" );
to:
lrg._area -= cost;
assert(lrg._area >= 0.0, "negative spill area" );

There is a subtle difference between the two; the second assert also 
detects NaN values.
Since NaN < 0.0 == false, and NaN >= 0.0 == false.

In this bug, we encounter NaN for lrg._area.
This happens when the cost is +Inf, and the lrg._area already is +Inf.
+Inf - +Inf = NaN.

The reason why the cost is +Inf is because the block frequency is +Inf.
The block frequency is +Inf because the test for this bug (stmp0101_364) 
is written in such a way that we get 140+ loops, with a loop depth of 
140~. The test is a .jasm, and looks like this:

                      X1                      X0
                     +-------------+         +------------+
                     | i = 1;      |  True   |            |
             +-----> | if (i == 0) |+------> | return;    |
             |       |             |         |            |
             |       +------+------+         +------------+
      True   |              |
             |        X2    v
             |       +-------------+
             |       |             |
             +------+| if (i == 0) |
                     |             |
                     +------+------+
                            |
                            v
                            .
             +------>       .
             |         Xn   .
      True   |       +--------------+
             |       | if (i == 0)  |
             +------+| i = 0;       |
                     | goto Xn;     |
                     +--------------+

We start off in frame X1 by assigning i = 1; then we check if i is 0, if 
it's true, we go to X0 and return. If not, we go to the next frame X2. 
In X2 we check if i == 0, if true, we go back to the previous frame, if 
false, we continue to the next frame. We do this X number of times, 
until finally, in Xn, we do the same check on i, and if false we set i = 
0; then go to Xn again. This will trigger if (i == 0) to be true in all 
frames, and eventually we will pop up to X1 and finally to X0.

As mentioned, this test creates a loop depth of 140~. And because we do 
static branch profiling (because of -Xcomp), the trip count for each 
loop will be approximated to 10.
Starting at the top loop, which will have frequency of 1.0, each nested 
loop will increase its estimated frequency with a factor of about 10.0. 
Which means that at the loop depth 140 we will have a frequency of 
10^140, which is by far bigger than the maximum number of a float.

The maximum number for a float is reached around loop depth 40~.

Solution:
In reality, I would say these kinds of frequencies will never occur. 
Writing a method with a loop depth of 40, with an actual trip count of 
10, would take forever to execute. Because of this I don't want to do a 
big change in the frequency estimation which could potentially harm the 
performance in the more common use cases.

Instead, my suggestion is to change the frequency type from float to 
double. This will make this test pass since 10^140 can be represented as 
a double (which has a max-value of 1.79769e+308).

Also, adding a check before subtracting the cost from the lrg area:
if (!isinf(cost)) {
   lrg._area -= cost;
}

will prevent us from getting NaN in even more extreme cases (when the 
double max value isn't enough). Instead of setting the area to be NaN, 
with the risk of having the score() for live ranges to be NaN, we will 
instead have +Inf as score().

(I also changed the other asserts in ifg.cpp to be on the format (x >= 
0) instead of !(x < 0))

webrev: http://cr.openjdk.java.net/~adlertz/JDK-8033260/webrev00/
bug: https://bugs.openjdk.java.net/browse/JDK-8033260

Kind Regards,
Niclas Adlertz