RFR: 8173709: Fix VerifyLoopOptimizations - step 1 - minimal infrastructure [v7]

Christian Hagedorn chagedorn at openjdk.org
Mon Apr 3 07:44:28 UTC 2023 

On Mon, 3 Apr 2023 06:21:15 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_idom_and_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_idom` and `verify_nodes` on every node. I refactored `verify_nodes` a bit, so that it is more readable.
>>    - I now report all failures, before asserting.
>>  - `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.
>>    - I also converted the asserts to reporting failures, just like in `verify_idom_and_nodes`.
>> 
>> **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.
>
> Emanuel Peter has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Style fix by Tobias

Thanks for doing the updates! Looks much cleaner now. I have some more comments.

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

> 4821:   while (child != nullptr) {
> 4822:     assert(child->_parent == this, "all must be children of this");
> 4823:     children.push(child);

You could directly use:

children.insert_sorted<compare_tree>(child);

instead of `push` + `sort()` afterwards. This would simplify `compare_tree()` to:

int compare_tree(IdealLoopTree* const& a, IdealLoopTree* const& b) {
  assert(a != nullptr && b != nullptr, "must be");
  return a->_head->_idx - b->_head->_idx;
}

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

> 4871:     // Process the two children, or potentially log the failure if we only found one.
> 4872:     if (child_verify == nullptr) {
> 4873:       if (child_verify->_irreducible && Compile::current()->major_progress()) {

Copy-paste error:
Suggestion:

      if (child->_irreducible && Compile::current()->major_progress()) {

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

> 4874:         // Irreducible loops can pick a different header (one of its entries).
> 4875:       } else {
> 4876:         tty->print_cr("We have loop that verify does not have");

Suggestion:

        tty->print_cr("We have a loop that verify does not have");

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

> 4888:         // mean that we lost it, which is not ok.
> 4889:       } else {
> 4890:         tty->print_cr("Verify has loop that we do not have");

Suggestion:

        tty->print_cr("Verify has a loop that we do not have");

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

> 4920:     assert(ctrl != nullptr && ctrl->is_CFG(), "sane loop in-ctrl");
> 4921:     assert(back != nullptr && back->is_CFG(), "sane loop backedge");
> 4922:     Node* loopexit = cl->loopexit(); // assert implied

Local variable assignment can be removed.
Suggestion:

    cl->loopexit(); // assert implied

src/hotspot/share/opto/loopnode.hpp line 797:

> 795: 
> 796: #ifdef ASSERT
> 797:   void collect_children(GrowableArray<IdealLoopTree*> &children) const;

Suggestion:

  void collect_children(GrowableArray<IdealLoopTree*>& children) const;

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

PR Review: https://git.openjdk.org/jdk/pull/13207#pullrequestreview-1368343134
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1155557413
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1155569153
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1155569752
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1155572492
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1155573608
PR Review Comment: https://git.openjdk.org/jdk/pull/13207#discussion_r1155574891

More information about the hotspot-compiler-dev mailing list