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

[Vladimir Kozlov]

Thank you, Niclas

Very good description of the problem!
Changes are good. I have only one question about subtracting the cost: why you not allow subtract Inf from normal value? 
In other words, can we only exclude +Inf - +Inf but not n - +Inf?

Thanks,
Vladimir

On 2/19/14 4:19 AM, Niclas Adlertz wrote:
> 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
>
>
>
>