Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Tue, 25 May 2021 16:14:56 GMT, Jan Lahoda wrote: > I'd like to note this is a preview feature - we can change the desugaring. At > the same time, I don't think this does not work with sub-patterns (those can > be easily desugared to guards, I think). Yes, but in that case the classcheck du to a sub-pattern matching will be either an instanceof or some other invokedynamic. Having several indy will bloat the code and if we use instanceof, why not using instanceof all along the way. > Regarding efficiency, it may be a balance between classfile overhead (which > will be higher if we need to desugar every guard to a separate method), and > the possibility to tweak the matching at runtime. I fear more the 2 bytes length bytecode limit of a method than the constant pool length limit mostly because people are already using a bunch of lambdas to simulate pattern matching. - PR: https://git.openjdk.java.net/jdk/pull/3863
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Tue, 25 May 2021 16:00:43 GMT, Rémi Forax wrote: > > The reason for this integer (which is not a constant in the case of this > > switch) is to restart the matching in case guards fail to "match". > > Considering the example here: > > ``` > > class Example { > > void example(Object o) { > > switch (o) { > > case String s && s.length() == 0 -> > > System.out.println("1st case"); > > case String s && s.length() == 1 -> // line 6 > > System.out.println("2nd case"); // line 7 > > case String s -> // line 8 > > System.out.println("3rd case"); // line 9 > > default -> // line 10 > > System.out.println("default case"); // line 11 > > } > > } > > } > > ``` > > > > > > > > > > > > > > > > > > > > > > > > If `o` is `String`, then the first call to indy will be `indy[...](o, 0)`, > > returning `0`. Then the guard will be evaluated `s.length() == 0`. If the > > length is not zero, the local variable 3 will be reassigned to `1`(bytecode > > index 58, 59) and the whole switch is restarted - just this time, the > > matching in the indy will start at index `1`, not `0`, i.e. `indy[...](o, > > 1)`. And so on. I believe there is a text explaining the meaning of the > > parameter in the javadoc of the bootstrap, and in TransPatterns in javac. > > The problem with this design is that calling example("foo") forces the VM > will do 6 checkcast String on "foo", and it doesn't work with sub-patterns. > Desugaring the guards as static method like with lambdas seems more > promising, indy can be called with the pairs [String, MethodHandle(s -> > s.length() == 0)], [String, MethodHandle(s -> s.length() == 0)] and [_,_] > (with the guards passed as a constant method handles again like lambdas are > desugared). > It means that the indy needs to capture all local variables that are used in > the guards, instead of passing an int. > > I believe that a translation using constant method handles for guards is far > more efficient than using an int and a backward branch but it has a higher > cost in term of runtime data structures. I'd like to note this is a preview feature - we can change the desugaring. At the same time, I don't think this does not work with sub-patterns (those can be easily desugared to guards, I think). Regarding efficiency, it may be a balance between classfile overhead (which will be higher if we need to desugar every guard to a separate method), and the possibility to tweak the matching at runtime. - PR: https://git.openjdk.java.net/jdk/pull/3863
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Tue, 25 May 2021 14:22:57 GMT, Jan Lahoda wrote: > The reason for this integer (which is not a constant in the case of this > switch) is to restart the matching in case guards fail to "match". > Considering the example here: > > ``` > class Example { > void example(Object o) { > switch (o) { > case String s && s.length() == 0 -> > System.out.println("1st case"); > case String s && s.length() == 1 -> // line 6 > System.out.println("2nd case"); // line 7 > case String s -> // line 8 > System.out.println("3rd case"); // line 9 > default -> // line 10 > System.out.println("default case"); // line 11 > } > } > } > ``` > > If `o` is `String`, then the first call to indy will be `indy[...](o, 0)`, > returning `0`. Then the guard will be evaluated `s.length() == 0`. If the > length is not zero, the local variable 3 will be reassigned to `1`(bytecode > index 58, 59) and the whole switch is restarted - just this time, the > matching in the indy will start at index `1`, not `0`, i.e. `indy[...](o, > 1)`. And so on. I believe there is a text explaining the meaning of the > parameter in the javadoc of the bootstrap, and in TransPatterns in javac. The problem with this design is that calling example("foo") forces the VM will do 6 checkcast String on "foo", and it doesn't work with sub-patterns. Desugaring the guards as static method like with lambdas seems more promising, indy can be called with the pairs [String, MethodHandle(s -> s.length() == 0)], [String, MethodHandle(s -> s.length() == 0)] and [_,_] (with the guards passed as a constant method handles again like lambdas are desugared). It means that the indy needs to capture all local variables that are used in the guards, instead of passing an int. I believe that a translation using constant method handles for guards is far more efficient than using an int and a backward branch but it has a higher cost in term of runtime data structures. - PR: https://git.openjdk.java.net/jdk/pull/3863
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Tue, 25 May 2021 14:13:55 GMT, Rémi Forax wrote: > 7: iconst_0 < this zero @forax as far as I understood this will be a value of parameter `startIndex` in `java.lang.runtime. SwitchBootstraps.doSwitch` Please correct me @lahodaj if I'm wrong. - PR: https://git.openjdk.java.net/jdk/pull/3863
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Tue, 25 May 2021 14:13:55 GMT, Rémi Forax wrote: > > Thanks Evgeny, I'll take a look. > > @forax, do you mean why there is "0" in: > > 11: invokedynamic #13, 0 > > ? > > Not this one, the one on the stack. > > 7: iconst_0 < this zero > 8: istore_3 > 9: aload_2 > 10: iload_3 > 11: invokedynamic #13, 0 // InvokeDynamic > #0:typeSwitch:(Ljava/lang/Object;I)I > > Why the descriptor is (Ljava/lang/Object;I)I instead of (Ljava/lang/Object;)I, > what is the semantics associated to that integer ? The reason for this integer (which is not a constant in the case of this switch) is to restart the matching in case guards fail to "match". Considering the example here: class Example { void example(Object o) { switch (o) { case String s && s.length() == 0 -> System.out.println("1st case"); case String s && s.length() == 1 -> // line 6 System.out.println("2nd case"); // line 7 case String s -> // line 8 System.out.println("3rd case"); // line 9 default -> // line 10 System.out.println("default case"); // line 11 } } } If `o` is `String`, then the first call to indy will be `indy[...](o, 0)`, returning `0`. Then the guard will be evaluated `s.length() == 0`. If the length is not zero, the local variable 3 will be reassigned to `1`(bytecode index 58, 59) and the whole switch is restarted - just this time, the matching in the indy will start at index `1`, not `0`, i.e. `indy[...](o, 1)`. And so on. I believe there is a text explaining the meaning of the parameter in the javadoc of the bootstrap, and in TransPatterns in javac. > > > The "0" is an artifact of how invokedynamic is represented in the classfile > > (invokedynamic, 2 bytes of constant pool reference, byte 0, byte 0) - javap > > shows the value of the first zero byte. That is probably not needed > > anymore, but there is nothing special in this patch, I think - all > > invokedynamic calls look like this, AFAIK. > > I know that a little to well, i'm one of the guys behind the design of indy :) - PR: https://git.openjdk.java.net/jdk/pull/3863
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Tue, 25 May 2021 12:20:02 GMT, Jan Lahoda wrote: > Thanks Evgeny, I'll take a look. > > @forax, do you mean why there is "0" in: > 11: invokedynamic #13, 0 > ? Not this one, the one on the stack. 7: iconst_0 < this zero 8: istore_3 9: aload_2 10: iload_3 11: invokedynamic #13, 0 // InvokeDynamic #0:typeSwitch:(Ljava/lang/Object;I)I Why the descriptor is (Ljava/lang/Object;I)I instead of (Ljava/lang/Object;)I, what is the semantics associated to that integer ? > The "0" is an artifact of how invokedynamic is represented in the classfile > (invokedynamic, 2 bytes of constant pool reference, byte 0, byte 0) - javap > shows the value of the first zero byte. That is probably not needed anymore, > but there is nothing special in this patch, I think - all invokedynamic calls > look like this, AFAIK. I know that a little to well, i'm one of the guys behind the design of indy :) - PR: https://git.openjdk.java.net/jdk/pull/3863
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Wed, 19 May 2021 08:00:12 GMT, Jan Lahoda wrote: >> This is a preview of a patch implementing JEP 406: Pattern Matching for >> switch (Preview): >> https://bugs.openjdk.java.net/browse/JDK-8213076 >> >> The current draft of the specification is here: >> http://cr.openjdk.java.net/~gbierman/jep406/jep406-20210430/specs/patterns-switch-jls.html >> >> A summary of notable parts of the patch: >> -to support cases expressions and patterns in cases, there is a new common >> superinterface for expressions and patterns, `CaseLabelTree`, which >> expressions and patterns implement, and a list of case labels is returned >> from `CaseTree.getLabels()`. >> -to support `case default`, there is an implementation of `CaseLabelTree` >> that represents it (`DefaultCaseLabelTree`). It is used also to represent >> the conventional `default` internally and in the newly added methods. >> -in the parser, parenthesized patterns and expressions need to be >> disambiguated when parsing case labels. >> -Lower has been enhanced to handle `case null` for ordinary >> (boxed-primitive, String, enum) switches. This is a bit tricky for boxed >> primitives, as there is no value that is not part of the input domain so >> that could be used to represent `case null`. Requires a bit shuffling with >> values. >> -TransPatterns has been enhanced to handle the pattern matching switch. It >> produces code that delegates to a new bootstrap method, that will classify >> the input value to the switch and return the case number, to which the >> switch then jumps. To support guards, the switches (and the bootstrap >> method) are restartable. The bootstrap method as such is written very simply >> so far, but could be much more optimized later. >> -nullable type patterns are `case String s, null`/`case null, String >> s`/`case null: case String s:`/`case String s: case null:`, handling of >> these required a few tricks in `Attr`, `Flow` and `TransPatterns`. >> >> The specdiff for the change is here (to be updated): >> http://cr.openjdk.java.net/~jlahoda/8265981/specdiff.preview.01/overview-summary.html > > Jan Lahoda has updated the pull request incrementally with one additional > commit since the last revision: > > Fixing various error-related bugs. Thanks Evgeny, I'll take a look. @forax, do you mean why there is "0" in: 11: invokedynamic #13, 0 ? The "0" is an artifact of how invokedynamic is represented in the classfile (invokedynamic, 2 bytes of constant pool reference, byte 0, byte 0) - javap shows the value of the first zero byte. That is probably not needed anymore, but there is nothing special in this patch, I think - all invokedynamic calls look like this, AFAIK. - PR: https://git.openjdk.java.net/jdk/pull/3863
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
- Mail original - > De: "Evgeny Mandrikov" > À: "build-dev" , "compiler-dev" > , "core-libs-dev" > , "javadoc-dev" > Envoyé: Mardi 25 Mai 2021 11:32:03 > Objet: Re: RFR: 8262891: Compiler implementation for Pattern Matching for > switch (Preview) [v4] > On Mon, 17 May 2021 19:01:01 GMT, Jan Lahoda wrote: > >>> Good work. There's a lot to take in here. I think overall, it holds up well >>> - I >>> like how case labels have been extended to accommodate for patterns. In the >>> front-end, I think there are some questions over the split between Attr and >>> Flow - maybe it is unavoidable, but I'm not sure why some control-flow >>> analysis >>> happens in Attr instead of Flow and I left some questions to make sure I >>> understand what's happening. >>> >>> In the backend it's mostly good work - but overall the structure of the >>> code, >>> both in Lower and in TransPattern is getting very difficult to follow, given >>> there are many different kind of switches each with its own little twist >>> attached to it. It would be nice, I think (maybe in a separate cleanup?) if >>> the >>> code paths serving the different switch kinds could be made more separate, >>> so >>> that, when reading the code we can worry only about one possible code shape. >>> That would make the code easier to document as well. >> >> @mcimadamore, @forax, thanks a lot for comments! I tried to apply the >> requested >> changes in recent commits >> (https://github.com/openjdk/jdk/pull/3863/commits/3fc2502a33cec20f39fe571eb25538ee3b459a9b >> https://github.com/openjdk/jdk/pull/3863/commits/aeddb85e65bf77ed62dc7fa1ad00c29646d02c99 >> ). >> >> I've also tried to update the implementation for the latest spec changes >> here: >> https://github.com/openjdk/jdk/pull/3863/commits/54ba974e1aac00bbde1c3bd2627f01caaaeda09b >> >> The spec changes are: total patterns are nullable; pattern matching ("new") >> statement switches must be complete (as switch expressions). >> >> Any further feedback is welcome! > > Hi @lahodaj , > > I tried `javac` built from this PR and for the following `Example.java` > > > class Example { >void example(Object o) { >switch (o) { >case String s && s.length() == 0 -> >System.out.println("1st case"); >case String s && s.length() == 1 -> // line 6 >System.out.println("2nd case"); // line 7 >case String s -> // line 8 >System.out.println("3rd case"); // line 9 >default -> // line 10 >System.out.println("default case"); // line 11 >} >} > } > > > execution of > > > javac --enable-preview --release 17 Example.java > javap -v -p Example.class > > > produces > > > void example(java.lang.Object); >descriptor: (Ljava/lang/Object;)V >flags: (0x) >Code: > stack=2, locals=7, args_size=2 > 0: aload_1 > 1: dup > 2: invokestatic #7 // Method > > java/util/Objects.requireNonNull:(Ljava/lang/Object;)Ljava/lang/Object; > 5: pop > 6: astore_2 > 7: iconst_0 > 8: istore_3 > 9: aload_2 >10: iload_3 >11: invokedynamic #13, 0 // InvokeDynamic >#0:typeSwitch:(Ljava/lang/Object;I)I >16: tableswitch { // 0 to 2 > 0: 44 > 1: 74 > 2: 105 > default: 122 >} >44: aload_2 >45: checkcast #17 // class java/lang/String >48: astore4 >50: aload 4 >52: invokevirtual #19 // Method > java/lang/String.length:()I >55: ifeq 63 >58: iconst_1 >59: istore_3 >60: goto 9 >63: getstatic #23 // Field >java/lang/System.out:Ljava/io/PrintStream; >66: ldc #29 // String 1st case >68: invokevirtual #31 // Method >java/io/PrintStream.println:(Ljava/lang/String;)V >71: goto 133 >74: aload_2 >75: checkca
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
On Mon, 17 May 2021 19:01:01 GMT, Jan Lahoda wrote: >> Good work. There's a lot to take in here. I think overall, it holds up well >> - I like how case labels have been extended to accommodate for patterns. In >> the front-end, I think there are some questions over the split between Attr >> and Flow - maybe it is unavoidable, but I'm not sure why some control-flow >> analysis happens in Attr instead of Flow and I left some questions to make >> sure I understand what's happening. >> >> In the backend it's mostly good work - but overall the structure of the >> code, both in Lower and in TransPattern is getting very difficult to follow, >> given there are many different kind of switches each with its own little >> twist attached to it. It would be nice, I think (maybe in a separate >> cleanup?) if the code paths serving the different switch kinds could be made >> more separate, so that, when reading the code we can worry only about one >> possible code shape. That would make the code easier to document as well. > > @mcimadamore, @forax, thanks a lot for comments! I tried to apply the > requested changes in recent commits > (https://github.com/openjdk/jdk/pull/3863/commits/3fc2502a33cec20f39fe571eb25538ee3b459a9b > > https://github.com/openjdk/jdk/pull/3863/commits/aeddb85e65bf77ed62dc7fa1ad00c29646d02c99 > ). > > I've also tried to update the implementation for the latest spec changes here: > https://github.com/openjdk/jdk/pull/3863/commits/54ba974e1aac00bbde1c3bd2627f01caaaeda09b > > The spec changes are: total patterns are nullable; pattern matching ("new") > statement switches must be complete (as switch expressions). > > Any further feedback is welcome! Hi @lahodaj , I tried `javac` built from this PR and for the following `Example.java` class Example { void example(Object o) { switch (o) { case String s && s.length() == 0 -> System.out.println("1st case"); case String s && s.length() == 1 -> // line 6 System.out.println("2nd case"); // line 7 case String s -> // line 8 System.out.println("3rd case"); // line 9 default -> // line 10 System.out.println("default case"); // line 11 } } } execution of javac --enable-preview --release 17 Example.java javap -v -p Example.class produces void example(java.lang.Object); descriptor: (Ljava/lang/Object;)V flags: (0x) Code: stack=2, locals=7, args_size=2 0: aload_1 1: dup 2: invokestatic #7 // Method java/util/Objects.requireNonNull:(Ljava/lang/Object;)Ljava/lang/Object; 5: pop 6: astore_2 7: iconst_0 8: istore_3 9: aload_2 10: iload_3 11: invokedynamic #13, 0 // InvokeDynamic #0:typeSwitch:(Ljava/lang/Object;I)I 16: tableswitch { // 0 to 2 0: 44 1: 74 2: 105 default: 122 } 44: aload_2 45: checkcast #17 // class java/lang/String 48: astore4 50: aload 4 52: invokevirtual #19 // Method java/lang/String.length:()I 55: ifeq 63 58: iconst_1 59: istore_3 60: goto 9 63: getstatic #23 // Field java/lang/System.out:Ljava/io/PrintStream; 66: ldc #29 // String 1st case 68: invokevirtual #31 // Method java/io/PrintStream.println:(Ljava/lang/String;)V 71: goto 133 74: aload_2 75: checkcast #17 // class java/lang/String 78: astore5 80: aload 5 82: invokevirtual #19 // Method java/lang/String.length:()I 85: iconst_1 86: if_icmpeq 94 89: iconst_2 90: istore_3 91: goto 9 94: getstatic #23 // Field java/lang/System.out:Ljava/io/PrintStream; 97: ldc #37 // String 2nd case 99: invokevirtual #31 // Method java/io/PrintStream.println:(Ljava/lang/String;)V 102: goto 133 105: aload_2 106: checkcast #17 // class java/lang/String 109: astore6 111: getstatic #23 // Field java/lang/System.out:Ljava/io/PrintStream; 114: ldc #39 // String 3rd case 116: invokevirtual #31 // Method java/io/PrintStream.println:(Ljava/lang/String;)V 119: goto 133 122: getstatic #23 //
Re: RFR: 8262891: Compiler implementation for Pattern Matching for switch (Preview) [v4]
> This is a preview of a patch implementing JEP 406: Pattern Matching for > switch (Preview): > https://bugs.openjdk.java.net/browse/JDK-8213076 > > The current draft of the specification is here: > http://cr.openjdk.java.net/~gbierman/jep406/jep406-20210430/specs/patterns-switch-jls.html > > A summary of notable parts of the patch: > -to support cases expressions and patterns in cases, there is a new common > superinterface for expressions and patterns, `CaseLabelTree`, which > expressions and patterns implement, and a list of case labels is returned > from `CaseTree.getLabels()`. > -to support `case default`, there is an implementation of `CaseLabelTree` > that represents it (`DefaultCaseLabelTree`). It is used also to represent the > conventional `default` internally and in the newly added methods. > -in the parser, parenthesized patterns and expressions need to be > disambiguated when parsing case labels. > -Lower has been enhanced to handle `case null` for ordinary (boxed-primitive, > String, enum) switches. This is a bit tricky for boxed primitives, as there > is no value that is not part of the input domain so that could be used to > represent `case null`. Requires a bit shuffling with values. > -TransPatterns has been enhanced to handle the pattern matching switch. It > produces code that delegates to a new bootstrap method, that will classify > the input value to the switch and return the case number, to which the switch > then jumps. To support guards, the switches (and the bootstrap method) are > restartable. The bootstrap method as such is written very simply so far, but > could be much more optimized later. > -nullable type patterns are `case String s, null`/`case null, String s`/`case > null: case String s:`/`case String s: case null:`, handling of these required > a few tricks in `Attr`, `Flow` and `TransPatterns`. > > The specdiff for the change is here (to be updated): > http://cr.openjdk.java.net/~jlahoda/8265981/specdiff.preview.01/overview-summary.html Jan Lahoda has updated the pull request incrementally with one additional commit since the last revision: Fixing various error-related bugs. - Changes: - all: https://git.openjdk.java.net/jdk/pull/3863/files - new: https://git.openjdk.java.net/jdk/pull/3863/files/5fa8005a..0875377b Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3863=03 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3863=02-03 Stats: 117 lines in 6 files changed: 94 ins; 13 del; 10 mod Patch: https://git.openjdk.java.net/jdk/pull/3863.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3863/head:pull/3863 PR: https://git.openjdk.java.net/jdk/pull/3863