RFR: 8173709: Fix VerifyLoopOptimizations - step 1

Wed Mar 29 10:36:03 UTC 2023

On Tue, 28 Mar 2023 12:49:57 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

> I am reviving `-XX:+VerifyLoopOptimizations` after many years of abandonment. There were many bugs filed, but so far it has not been addressed.
> 
> The hope is that this work will allow us to catch ctrl / idom / loop body bugs quicker, and fix many of the existing ones along the way.
> 
> **The Idea of VerifyLoopOptimizations**
> Before loop-opts, we build many data-structures for dominance (idom), control, and loop membership. Then, loop-opts use this data to transform the graph. At the same time, they must maintain the correctness of the data-structures, so that other optimizations can be made, without needing to re-compute the data-structures every time.
> `VerifyLoopOptimizations` was implemented to verify correctness of the data-structures. After some loop-opts, we re-compute a verification data-structure and compare it to the one we created before the loop-opts and maintained during loopopts.
> 
> **My Approach**
> I soon realized that there were many reasons why `VerifyLoopOptimizations` was broken. It seemed infeasible to fix all of them at once. I decided to first remove any part that was failing, until I have a minimal set that is working. I will leave many parts commented out. In follow-up RFE's, I will then iteratively improve the verification by re-enabling some verification and fixing the corresponding bugs.
> 
> **What I fixed**
> 
>  - `verify_compare`
>    - Renamed it to `verify_nodes`, since it does verification node-by-node (vs `verify_tree`, which verifies the loop-tree).
>    - Previously, it was implemented as a BFS with recursion, which lead to stack-overflow. I flattened the BFS into a loop.
>    - The BFS calls `verify_node` on every node. I refactored `verify_node` a bit, so that it is more readable.
>    - Rather than having a thread-unsafe static variable `fail`, I now made it a reference argument.
>  - `verify_tree`
>    - I corrected the style and improved comments.
>    - I removed the broken verification for `Opaque` nodes. I added some rudamentary verification for `CountedLoop`. I leave more of this work for follow-up RFE's.
> 
> **Disabled Verifications**
> I commented out the following verifications:
> 
> (A) data nodes should have same ctrl
> (B) ctrl node should belong to same loop
> (C) ctrl node should have same idom
> (D) loop should have same tail
> (E) loop should have same body (list of nodes)
> (F) broken verification in PhaseIdealLoop::build_loop_late_post, because ctrl was set wrong
> 
> 
> Note: verifying `idom`, `ctrl` and `_body` is the central goal of `VerifyLoopOptimizations`. But all of them are broken in many parts of the VM, as we have now not verified them for many years.
> 
> **Follow-Up Work**
> 
> I filed a first follow-up RFE [JDK-8305073](https://bugs.openjdk.org/browse/JDK-8305073). The following tasks should be addressed in it, or in subsequent follow-up RFE's.
> 
> I propose the following order:
> 
>  - idom (C): The dominance structure is at the base of everything else.
>  - ctrl / loop (A, B): Once dominance is fixed, we can ensure every node is assigned to the correct ctrl/loop.
>  - tail (D): ensure the tail of a loop is updated correctly
>  - body (E): nodes are assigned to the `_body` of a loop, according to the node ctrl.
>  - other issues like (F)
>  - Add more verification to IdealLoopTree::verify_tree. For example zero-trip-guard, etc.
>  - Evaluate from where else we should call `PhaseIdealLoop::verify`. Maybe we are missing some cases.
> 
> **Testing**
> I am running `tier1-tier6` and stress testing.
> Preliminary results are all good.
> 
> **Conclusion**
> With this fix, I have the basic infrastructure of the verification working.
> However, all of the substantial verification are now still disabled, because there are too many places in the VM that do not maintain the data-structures properly.
> Follow-up RFE's will have to address these one-by-one.

It's great seeing that this flag is finally being revived! I agree with your suggestion to split the work into multiple patches instead of trying to fix all the issues with the flag. The proposed schedule makes sense.

Maybe you can rename the bug title to reflect the changes that you tackled in this patch (might not be possible to find such a concise title due to the many changes and disabling individual verification).

I also have a few comments.

src/hotspot/share/opto/loopnode.cpp line 4655:

> 4653: 
> 4654:   // Verify ctrl and idom of every node.
> 4655:   int fail = 0;

Could be a `uint`.

src/hotspot/share/opto/loopnode.cpp line 4675:

> 4673:     Node* n = worklist.at(i);
> 4674:     // process node
> 4675:     verify_node(n, loop_verify, fail);

Based on Vladimir's comment above, I think it's cleaner to do

fails += verify_node(n, loop_verify);

instead of using an input/output `int` parameter. But not sure how easy it is to adapt `verify_node()` with the multiple bailouts there.

src/hotspot/share/opto/loopnode.cpp line 4677:

> 4675:     verify_node(n, loop_verify, fail);
> 4676:     // visit inputs
> 4677:     for(uint j = 0; j < n->req(); j++) {

Suggestion:

    for (uint j = 0; j < n->req(); j++) {

src/hotspot/share/opto/loopnode.cpp line 4690:

> 4688: //  (2) Verify dominator structure (IDOM).
> 4689: void PhaseIdealLoop::verify_node(Node* n, const PhaseIdealLoop* loop_verify, int &fail) const {
> 4690:   uint i = n->_idx;

Suggestion:

  const uint i = n->_idx;

src/hotspot/share/opto/loopnode.cpp line 4693:

> 4691:   // The loop-tree was built from def to use. The verification happens from def to use.
> 4692:   // We may thus find nodes during verification that are not in the loop-tree.
> 4693:   if(_nodes[i] == nullptr) {

Suggestion:

  if (_nodes[i] == nullptr) {

src/hotspot/share/opto/loopnode.cpp line 4694:

> 4692:   // We may thus find nodes during verification that are not in the loop-tree.
> 4693:   if(_nodes[i] == nullptr) {
> 4694:     assert(loop_verify->_nodes[i] == nullptr, "both should be unreachable");

Could this also be turned into a `tty->print()` + `fail++` instead of a direct assertion?

src/hotspot/share/opto/loopnode.cpp line 4698:

> 4696:   }
> 4697: 
> 4698:   // Check everything stored in "_nodes".

It might be cleaner to split this method into `verify_node_list()` and `verify_idom()`

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

PR Review: https://git.openjdk.org/jdk/pull/13207#pullrequestreview-1362661846
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151665187
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151664105
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151665398
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151720685
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151667589
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151676395
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151680984