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

[Vladimir Kozlov]

Thank you for explanation. Changes are good.

Vladimir

On 2/20/14 6:38 AM, Niclas Adlertz wrote:
> 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
>>>
>>>
>>>
>>>