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

[Niclas Adlertz]

Hi Vladimir, thank you.

When building the IFG, we step backwards through each block, removing 
definitions and adding uses, to the block's LIVEOUT.

When stepping backwards, an lrg has to be live before we reach its 
definition. (Unless it's a dead node or it's a fat_proj, they are 
handled differently.)

This also means that at some point, either at the very end of the block 
(when beginning the backwards stepping) or when stepping, we will see 
that the lrg becomes live, and add the cost to its area. (Either in 
compute_initial_block_pressure or in add_input_to_liveout.)

If the cost is +Inf when we remove it from the area, it must also be 
+Inf earlier when we add it to the area. This means that when we do:
lrg._area -= +Inf, lrg._area is already +Inf.

Kind Regards,
Niclas Adlertz

On 02/19/2014 04:15 PM, Vladimir Kozlov wrote:
> 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
>>
>>
>>
>>