RFR: 8298952: All nodes should have type(n) == Value(n) after IGVN

[Emanuel Peter]

On Thu, 26 Jan 2023 22:30:00 GMT, Vladimir Kozlov <kvn at openjdk.org> wrote:

>> I want to verify that **type(n) == Value(n)** after every IGVN round. Basically: all optimizations that can be made should be made.
>> 
>> FYI: this is a part of a bigger effort to verify IGVN, and refactor the notification code for CCP and IGVN:
>> [JDK-8298951](https://bugs.openjdk.org/browse/JDK-8298951) `Umbrella: improve CCP and IGVN verification`
>> I recently implemented CCP Node::Value verification [JDK-8257197](https://bugs.openjdk.org/browse/JDK-8257197).
>> 
>> I'm extending the flag `-XX:+VerifyIterativeGVN` (used to enable Use-Def verification) to `-XX:VerifyIterativeGVN=XY`, where `X` can enable the Value verification (low overhead), and `Y` enables the Use-Def verification (very slow, requires increasing timeouts).
>> 
>> This patch has passed tier1-5 and stress testing. Performance testing is running...
>> 
>> **I would love to hear your opinion, especially about the special cases, but also my fixes named below.**
>> 
>> For the verification to pass, I had to **fix some things**:
>> - Add `gvn.transform` to some `new Node` cases where it was missing, else I got `type(n) == nullptr`.
>> - Add missing notification logic in `PhaseIterGVN::add_users_to_worklist`: notify tripcount phi of LongCountedLoop if the limit changes (int case was already implemented), notify Sub node if input CastII has changing input, notify And in shift-and (shift-mask) operation. Every optimization should have corresponding notification if (recursive) inputs change. These were easy to fix examples.
>> - `ConstraintCastNode::Value` violated the idempotence guarantee: subsequent calls to Value returned different values. Fixed that.
>> - `CastLLNode::Ideal` can be widened after loop-opts, with the goal of commoning CastLL nodes. For that, we need to call `record_for_post_loop_opts_igvn` for them, even before IGVN (when `can_reshape` is still false). They may otherwise not land on the post loop-opts worklist.
>> - During CCP, some integer types are saturated (widened). But IGVN could narrow them again. So add them to IGVN worklist if they are saturated (widened) during CCP.
>> - `kill_dead_code`: tries to remove dead nodes recursively, in analogy to what IGVN would do, but more efficiently. Unfortunately, we do not call `add_users_to_worklist` for the dead nodes, which IGVN would do. I do the notification once per dead node now. `kill_dead_code` could be refactored and made more efficient, maybe we can do that in a future RFE.
>> - `PhaseIdealLoop::clone_loop_handle_data_uses` calls `_igvn.replace_input_of(use, idx, phi)`, but does not notify the users. I got a failure in tier5-common, where use was a CmpI of a loop-exit test, and the tripcount-phi needed to be notified. I added notification here, but I wonder if it needs to be added to `replace_input_of` generally?
>> - `CastII`: implemented notification for `CmpI -> Bool -> If -> IfProj -> CastII`. This handles case where previously we have `in1 != X`, see comment in code.
>> - `Sub` with input of chain of `ConstraintCast`: rare case, implemented a BFS traversal down the casts, to the `Sub` nodes.
>> - Replaced a `set_req` with `set_req_X` in `CmpPNode::Ideal`, as it removed the last use of the previous input, and lead to `fatal error: no reachable node should have no use`.
>> 
>> As with CCP Node::Value verification, a few cases have to be **exempt from verification (special cased)**.
>> https://github.com/openjdk/jdk/blob/fe5552be65e9dd9c044d41e8295bb176d9754e28/src/hotspot/share/opto/phaseX.cpp#L1244-L1296
>> 
>> - `Integer` widen: expected, must special case.
>> - `Load`: must special case because of deep traversal in Value. We may be able to make special case logic more precise. One might also experiment with deep notification, but that could be expensive and complex. I would leave special case as is, and address improvements in a future RFE.
>> - `CmpP`: deep traversal of CFG to determine domination (independence between two pointers). Probably needs to be special cased.
>> 
>> **Note**: I want to address these `memory` optimizations in a follow up RFE. We had the idea of simply putting all these nodes on a special list that is always processed during IGVN. We will have to investigate performance impact either way.
>
> src/hotspot/share/opto/castnode.cpp line 59:
> 
>> 57:   if (ft->speculative() == nullptr && // speculative was dropped
>> 58:       _type->speculative() != nullptr &&   // but was present
>> 59:       in_type->speculative() != nullptr) { // for cast and input
> 
> May be move comments on these 3 lines to one comment before first line.

Ok, I will do that.

> src/hotspot/share/opto/parse1.cpp line 547:
> 
>> 545:   }
>> 546: 
>> 547:   gvn().set_type(root(), root()->bottom_type());
> 
> I am not sure about this. This `gvn` is local to `Parse` which is used separately for each parsed inlined method and intrinsic.

@vnkozlov I moved this code out to here:
https://github.com/openjdk/jdk/blob/6ce2768c37713bb342608f7017292bec74a060a6/src/hotspot/share/opto/compile.cpp#L760
The issue was that other paths did not have the type of `root` set.

Are you sure that the `gvn` is local?
https://github.com/openjdk/jdk/blob/6ce2768c37713bb342608f7017292bec74a060a6/src/hotspot/share/opto/parse.hpp#L151
https://github.com/openjdk/jdk/blob/6ce2768c37713bb342608f7017292bec74a060a6/src/hotspot/share/opto/graphKit.hpp#L58-L63
https://github.com/openjdk/jdk/blob/6ce2768c37713bb342608f7017292bec74a060a6/src/hotspot/share/opto/graphKit.cpp#L56-L78
It looks like the `gvn` in `Parse` is the same as `C->initial_gvn()`

And we set that just before we create the `ParseGenerator` (osr / intrinsic / inline):
https://github.com/openjdk/jdk/blob/6ce2768c37713bb342608f7017292bec74a060a6/src/hotspot/share/opto/compile.cpp#L715
https://github.com/openjdk/jdk/blob/6ce2768c37713bb342608f7017292bec74a060a6/src/hotspot/share/opto/compile.cpp#L725

So instead of only setting the type in `Parse::Parse`, I now set it for all of those cases:
https://github.com/openjdk/jdk/blob/6ce2768c37713bb342608f7017292bec74a060a6/src/hotspot/share/opto/compile.cpp#L760

I can also set the type both out in `Compile::Compile`, and also in `Parse::Parse` if that makes us feel safer. Let me know what you think.

> src/hotspot/share/opto/phaseX.cpp line 1245:
> 
>> 1243: 
>> 1244: // Check that if type(n) == n->Value(), return true if we have a failure
>> 1245: // We have a list of exceptions, see comments in code.
> 
> May be enumerate list of exceptions and short description.

Ok, I can do that. I will just make a short list, and a quick sentence per item. The detailed description I will still leave further down, at the block that actually implements the exception, ok?

-------------

PR: https://git.openjdk.org/jdk/pull/11775