RFR: 8173709: Fix VerifyLoopOptimizations - step 1

Tue Mar 28 23:18:33 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.

Few comments

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

> 4654:   // Verify ctrl and idom of every node.
> 4655:   int fail = 0;
> 4656:   verify_nodes(C->root(), &loop_verify, fail);

I think result should be returned using local variables instead of storing it in passed variable.

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

> 4689: void PhaseIdealLoop::verify_node(Node* n, const PhaseIdealLoop* loop_verify, int &fail) const {
> 4690:   uint i = n->_idx;
> 4691:   // The loop-tree was built from def to use. The verification happens from def to use.

I think it is not correct: "The verification happens from def to use."   You put node's inputs (defs) on work list.

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

> 4713:     assert(loop_verify->has_ctrl(n), "sanity");
> 4714:     // n is a data node.
> 4715:     // Verify that it ctrl is the same.

`its control`

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

> 4803: // within the loop tree can be reordered. We attempt to deal with that by
> 4804: // reordering the verify's loop tree if possible.
> 4805: void IdealLoopTree::verify_tree(IdealLoopTree* loop, const IdealLoopTree* parent) const {

Should we rename `loop` to `loop_verify` similar to `verify_node()` code?

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

> 4810:     tty->print_cr("reorder loop tree");
> 4811:     // Find _next pointer to update (where "loop" is attached)
> 4812:     IdealLoopTree **pp = &loop->_parent->_child;

May be use this opportunity and rename `pp` and `nn` to something meaningful.

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

> 4812:     IdealLoopTree **pp = &loop->_parent->_child;
> 4813:     while (*pp != loop) {
> 4814:       pp = &((*pp)->_next);

May be instead of this convoluted search, swap and verification code we can simply reorder whole siblings list first before verification? You don't need to swap - just create local ordered list.

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

PR Review: https://git.openjdk.org/jdk/pull/13207#pullrequestreview-1361945433
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151177078
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151179871
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151187594
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151217615
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151221030
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1151237595