RFR: 8259984: IGV: Crash when drawing control flow before GCM

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

RFR: 8259984: IGV: Crash when drawing control flow before GCM

Roberto Castañeda Lozano-2
The block formation algorithm applied by IGV to schedule graphs without associated CFG information traverses the graph backwards. This makes it difficult to deal with block projection nodes, leading in some cases to double addition of block nodes and block edges, and ultimately causing assertion failures.

This fix replaces the backward traversal by a forward traversal that relies on node category information (introduced in [8261336](https://bugs.openjdk.java.net/browse/JDK-8261336)) to identify control successors. The forward traversal is arguably simpler and, besides avoiding the reported assertion failure, has two advantages:

- it places block projection nodes in the same block as their predecessors, and
- it numbers basic blocks more naturally.

The following screenshots illustrate the improvements (before the fix to the left, after the fix to the right):

![cfgs-before-after](https://user-images.githubusercontent.com/8792647/108204708-6dcf5e00-7124-11eb-956c-fb7f84229b50.png)

Tested automatically on tens of thousands of graphs by running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4 ...` on an instrumented version of IGV that schedules graphs eagerly. Checked manually that the CFGs of a few selected graphs (included the reported one) are well-formed. Also checked that the overall IGV graph scheduling time is not affected by the changes.

Thanks to Christian Hagedorn for checking the fix independently.

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

Commit messages:
 - Form basic blocks using a forward traversal
 - Connect orphan/widow CFG nodes to root
 - Mark CFG nodes before scheduling

Changes: https://git.openjdk.java.net/jdk/pull/2607/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=2607&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8259984
  Stats: 167 lines in 1 file changed: 90 ins; 19 del; 58 mod
  Patch: https://git.openjdk.java.net/jdk/pull/2607.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/2607/head:pull/2607

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM

Christian Hagedorn-3
On Wed, 17 Feb 2021 12:23:55 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

> The block formation algorithm applied by IGV to schedule graphs without associated CFG information traverses the graph backwards. This makes it difficult to deal with block projection nodes, leading in some cases to double addition of block nodes and block edges, and ultimately causing assertion failures.
>
> This fix replaces the backward traversal by a forward traversal that relies on node category information (introduced in [8261336](https://bugs.openjdk.java.net/browse/JDK-8261336)) to identify control successors. The forward traversal is arguably simpler and, besides avoiding the reported assertion failure, has two advantages:
>
> - it places block projection nodes in the same block as their predecessors, and
> - it numbers basic blocks more naturally.
>
> The following screenshots illustrate the improvements (before the fix to the left, after the fix to the right):
>
> ![cfgs-before-after](https://user-images.githubusercontent.com/8792647/108204708-6dcf5e00-7124-11eb-956c-fb7f84229b50.png)
>
> Tested automatically on tens of thousands of graphs by running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4 ...` on an instrumented version of IGV that schedules graphs eagerly. Checked manually that the CFGs of a few selected graphs (included the reported one) are well-formed. Also checked that the overall IGV graph scheduling time is not affected by the changes.
>
> Thanks to Christian Hagedorn for checking the fix independently.

Looks good to me! I played around with it in the IGV. I regularly got some assertion failure messages before - now they are gone now 👍

src/utils/IdealGraphVisualizer/ServerCompiler/src/com/sun/hotspot/igv/servercompiler/ServerCompilerScheduler.java line 634:

> 632:             }
> 633:         }
> 634:

Maybe you could extract the following code into 2 separate methods.

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

Marked as reviewed by chagedorn (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM

Nils Eliasson-2
In reply to this post by Roberto Castañeda Lozano-2
On Wed, 17 Feb 2021 12:23:55 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

> The block formation algorithm applied by IGV to schedule graphs without associated CFG information traverses the graph backwards. This makes it difficult to deal with block projection nodes, leading in some cases to double addition of block nodes and block edges, and ultimately causing assertion failures.
>
> This fix replaces the backward traversal by a forward traversal that relies on node category information (introduced in [8261336](https://bugs.openjdk.java.net/browse/JDK-8261336)) to identify control successors. The forward traversal is arguably simpler and, besides avoiding the reported assertion failure, has two advantages:
>
> - it places block projection nodes in the same block as their predecessors, and
> - it numbers basic blocks more naturally.
>
> The following screenshots illustrate the improvements (before the fix to the left, after the fix to the right):
>
> ![cfgs-before-after](https://user-images.githubusercontent.com/8792647/108204708-6dcf5e00-7124-11eb-956c-fb7f84229b50.png)
>
> Tested automatically on tens of thousands of graphs by running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4 ...` on an instrumented version of IGV that schedules graphs eagerly. Checked manually that the CFGs of a few selected graphs (included the reported one) are well-formed. Also checked that the overall IGV graph scheduling time is not affected by the changes.
>
> Thanks to Christian Hagedorn for checking the fix independently.

Excellent!

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

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM [v2]

Roberto Castañeda Lozano-2
In reply to this post by Roberto Castañeda Lozano-2
> The block formation algorithm applied by IGV to schedule graphs without associated CFG information traverses the graph backwards. This makes it difficult to deal with block projection nodes, leading in some cases to double addition of block nodes and block edges, and ultimately causing assertion failures.
>
> This fix replaces the backward traversal by a forward traversal that relies on node category information (introduced in [8261336](https://bugs.openjdk.java.net/browse/JDK-8261336)) to identify control successors. The forward traversal is arguably simpler and, besides avoiding the reported assertion failure, has two advantages:
>
> - it places block projection nodes in the same block as their predecessors, and
> - it numbers basic blocks more naturally.
>
> The following screenshots illustrate the improvements (before the fix to the left, after the fix to the right):
>
> ![cfgs-before-after](https://user-images.githubusercontent.com/8792647/108204708-6dcf5e00-7124-11eb-956c-fb7f84229b50.png)
>
> Tested automatically on tens of thousands of graphs by running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4 ...` on an instrumented version of IGV that schedules graphs eagerly. Checked manually that the CFGs of a few selected graphs (included the reported one) are well-formed. Also checked that the overall IGV graph scheduling time is not affected by the changes.
>
> Thanks to Christian Hagedorn for checking the fix independently.

Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:

  Extract new logic out of buildUpGraph()

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/2607/files
  - new: https://git.openjdk.java.net/jdk/pull/2607/files/69987721..9f6444ba

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=2607&range=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=2607&range=00-01

  Stats: 12 lines in 1 file changed: 6 ins; 0 del; 6 mod
  Patch: https://git.openjdk.java.net/jdk/pull/2607.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/2607/head:pull/2607

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM [v2]

Roberto Castañeda Lozano-2
In reply to this post by Nils Eliasson-2
On Thu, 18 Feb 2021 10:43:27 GMT, Nils Eliasson <[hidden email]> wrote:

>> Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:
>>
>>   Extract new logic out of buildUpGraph()
>
> Excellent!

Thanks Christian and Nils for reviewing! Christian, I refactored the code as per your suggestion, please have a look again.

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

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM [v2]

Roberto Castañeda Lozano-2
In reply to this post by Christian Hagedorn-3
On Thu, 18 Feb 2021 10:29:28 GMT, Christian Hagedorn <[hidden email]> wrote:

>> Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:
>>
>>   Extract new logic out of buildUpGraph()
>
> src/utils/IdealGraphVisualizer/ServerCompiler/src/com/sun/hotspot/igv/servercompiler/ServerCompilerScheduler.java line 634:
>
>> 632:             }
>> 633:         }
>> 634:
>
> Maybe you could extract the following code into 2 separate methods.

Thanks, done!

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

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM [v2]

Christian Hagedorn-3
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 18 Feb 2021 12:06:53 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

>> The block formation algorithm applied by IGV to schedule graphs without associated CFG information traverses the graph backwards. This makes it difficult to deal with block projection nodes, leading in some cases to double addition of block nodes and block edges, and ultimately causing assertion failures.
>>
>> This fix replaces the backward traversal by a forward traversal that relies on node category information (introduced in [8261336](https://bugs.openjdk.java.net/browse/JDK-8261336)) to identify control successors. The forward traversal is arguably simpler and, besides avoiding the reported assertion failure, has two advantages:
>>
>> - it places block projection nodes in the same block as their predecessors, and
>> - it numbers basic blocks more naturally.
>>
>> The following screenshots illustrate the improvements (before the fix to the left, after the fix to the right):
>>
>> ![cfgs-before-after](https://user-images.githubusercontent.com/8792647/108204708-6dcf5e00-7124-11eb-956c-fb7f84229b50.png)
>>
>> Tested automatically on tens of thousands of graphs by running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4 ...` on an instrumented version of IGV that schedules graphs eagerly. Checked manually that the CFGs of a few selected graphs (included the reported one) are well-formed. Also checked that the overall IGV graph scheduling time is not affected by the changes.
>>
>> Thanks to Christian Hagedorn for checking the fix independently.
>
> Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:
>
>   Extract new logic out of buildUpGraph()

Looks good!

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

Marked as reviewed by chagedorn (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM [v2]

Nils Eliasson-2
In reply to this post by Roberto Castañeda Lozano-2
On Thu, 18 Feb 2021 12:06:53 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

>> The block formation algorithm applied by IGV to schedule graphs without associated CFG information traverses the graph backwards. This makes it difficult to deal with block projection nodes, leading in some cases to double addition of block nodes and block edges, and ultimately causing assertion failures.
>>
>> This fix replaces the backward traversal by a forward traversal that relies on node category information (introduced in [8261336](https://bugs.openjdk.java.net/browse/JDK-8261336)) to identify control successors. The forward traversal is arguably simpler and, besides avoiding the reported assertion failure, has two advantages:
>>
>> - it places block projection nodes in the same block as their predecessors, and
>> - it numbers basic blocks more naturally.
>>
>> The following screenshots illustrate the improvements (before the fix to the left, after the fix to the right):
>>
>> ![cfgs-before-after](https://user-images.githubusercontent.com/8792647/108204708-6dcf5e00-7124-11eb-956c-fb7f84229b50.png)
>>
>> Tested automatically on tens of thousands of graphs by running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4 ...` on an instrumented version of IGV that schedules graphs eagerly. Checked manually that the CFGs of a few selected graphs (included the reported one) are well-formed. Also checked that the overall IGV graph scheduling time is not affected by the changes.
>>
>> Thanks to Christian Hagedorn for checking the fix independently.
>
> Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:
>
>   Extract new logic out of buildUpGraph()

Marked as reviewed by neliasso (Reviewer).

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

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM [v2]

Roberto Castañeda Lozano-2
In reply to this post by Christian Hagedorn-3
On Thu, 18 Feb 2021 12:21:27 GMT, Christian Hagedorn <[hidden email]> wrote:

> Looks good!

Thanks again, Christian.

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

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8259984: IGV: Crash when drawing control flow before GCM [v2]

Roberto Castañeda Lozano-2
In reply to this post by Nils Eliasson-2
On Thu, 18 Feb 2021 12:38:46 GMT, Nils Eliasson <[hidden email]> wrote:

>> Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:
>>
>>   Extract new logic out of buildUpGraph()
>
> Marked as reviewed by neliasso (Reviewer).

Replace backward traversal in the IGV block formation algorithm by forward
traversal guided by node category information. This change addresses the
reported assertion failures, places block projection nodes together with their
predecessors, and gives a more natural block numbering.

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

PR: https://git.openjdk.java.net/jdk/pull/2607
Reply | Threaded
Open this post in threaded view
|

Integrated: 8259984: IGV: Crash when drawing control flow before GCM

Roberto Castañeda Lozano-2
In reply to this post by Roberto Castañeda Lozano-2
On Wed, 17 Feb 2021 12:23:55 GMT, Roberto Castañeda Lozano <[hidden email]> wrote:

> The block formation algorithm applied by IGV to schedule graphs without associated CFG information traverses the graph backwards. This makes it difficult to deal with block projection nodes, leading in some cases to double addition of block nodes and block edges, and ultimately causing assertion failures.
>
> This fix replaces the backward traversal by a forward traversal that relies on node category information (introduced in [8261336](https://bugs.openjdk.java.net/browse/JDK-8261336)) to identify control successors. The forward traversal is arguably simpler and, besides avoiding the reported assertion failure, has two advantages:
>
> - it places block projection nodes in the same block as their predecessors, and
> - it numbers basic blocks more naturally.
>
> The following screenshots illustrate the improvements (before the fix to the left, after the fix to the right):
>
> ![cfgs-before-after](https://user-images.githubusercontent.com/8792647/108204708-6dcf5e00-7124-11eb-956c-fb7f84229b50.png)
>
> Tested automatically on tens of thousands of graphs by running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4 ...` on an instrumented version of IGV that schedules graphs eagerly. Checked manually that the CFGs of a few selected graphs (included the reported one) are well-formed. Also checked that the overall IGV graph scheduling time is not affected by the changes.
>
> Thanks to Christian Hagedorn for checking the fix independently.

This pull request has now been integrated.

Changeset: 61820b74
Author:    Roberto Castañeda Lozano <[hidden email]>
URL:       https://git.openjdk.java.net/jdk/commit/61820b74
Stats:     169 lines in 1 file changed: 92 ins; 15 del; 62 mod

8259984: IGV: Crash when drawing control flow before GCM

Replace backward traversal in the IGV block formation algorithm by forward
traversal guided by node category information. This change addresses the
reported assertion failures, places block projection nodes together with their
predecessors, and gives a more natural block numbering.

Reviewed-by: chagedorn, neliasso

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

PR: https://git.openjdk.java.net/jdk/pull/2607