{"action":"created","issue":{"url":"https://api.github.com/repos/scala/scala/issues/7133","repository_url":"https://api.github.com/repos/scala/scala","labels_url":"https://api.github.com/repos/scala/scala/issues/7133/labels{/name}","comments_url":"https://api.github.com/repos/scala/scala/issues/7133/comments","events_url":"https://api.github.com/repos/scala/scala/issues/7133/events","html_url":"https://github.com/scala/scala/pull/7133","id":353721872,"node_id":"MDExOlB1bGxSZXF1ZXN0MjEwNjk1NDQy","number":7133,"title":"More capable inliner [ci: last-only]","user":{"login":"lrytz","id":119636,"node_id":"MDQ6VXNlcjExOTYzNg==","avatar_url":"https://avatars1.githubusercontent.com/u/119636?v=4","gravatar_id":"","url":"https://api.github.com/users/lrytz","html_url":"https://github.com/lrytz","followers_url":"https://api.github.com/users/lrytz/followers","following_url":"https://api.github.com/users/lrytz/following{/other_user}","gists_url":"https://api.github.com/users/lrytz/gists{/gist_id}","starred_url":"https://api.github.com/users/lrytz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lrytz/subscriptions","organizations_url":"https://api.github.com/users/lrytz/orgs","repos_url":"https://api.github.com/users/lrytz/repos","events_url":"https://api.github.com/users/lrytz/events{/privacy}","received_events_url":"https://api.github.com/users/lrytz/received_events","type":"User","site_admin":false},"labels":[{"id":216463557,"node_id":"MDU6TGFiZWwyMTY0NjM1NTc=","url":"https://api.github.com/repos/scala/scala/labels/release-notes","name":"release-notes","color":"d4c5f9","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/scala/scala/milestones/67","html_url":"https://github.com/scala/scala/milestone/67","labels_url":"https://api.github.com/repos/scala/scala/milestones/67/labels","id":2719691,"node_id":"MDk6TWlsZXN0b25lMjcxOTY5MQ==","number":67,"title":"2.13.0-RC1","description":"Merge to 2.13.x. A PR should have scala/bug issue. No new PRs after Dec 15. Lead: @adriaanm\r\n\r\nRestricted to fixes directly improving the collections, their usage or the migration to 2.13.0. We will also consider fixes for important regressions since 2.12. An exception may be made for a small addition that cannot target 2.13.1 due to binary incompatibilities.","creator":{"login":"adriaanm","id":91083,"node_id":"MDQ6VXNlcjkxMDgz","avatar_url":"https://avatars2.githubusercontent.com/u/91083?v=4","gravatar_id":"","url":"https://api.github.com/users/adriaanm","html_url":"https://github.com/adriaanm","followers_url":"https://api.github.com/users/adriaanm/followers","following_url":"https://api.github.com/users/adriaanm/following{/other_user}","gists_url":"https://api.github.com/users/adriaanm/gists{/gist_id}","starred_url":"https://api.github.com/users/adriaanm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/adriaanm/subscriptions","organizations_url":"https://api.github.com/users/adriaanm/orgs","repos_url":"https://api.github.com/users/adriaanm/repos","events_url":"https://api.github.com/users/adriaanm/events{/privacy}","received_events_url":"https://api.github.com/users/adriaanm/received_events","type":"User","site_admin":false},"open_issues":73,"closed_issues":135,"state":"open","created_at":"2017-08-23T23:45:52Z","updated_at":"2018-10-17T08:45:04Z","due_on":"2019-01-11T08:00:00Z","closed_at":null},"comments":13,"created_at":"2018-08-24T10:02:47Z","updated_at":"2018-10-17T10:07:36Z","closed_at":null,"author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/scala/scala/pulls/7133","html_url":"https://github.com/scala/scala/pull/7133","diff_url":"https://github.com/scala/scala/pull/7133.diff","patch_url":"https://github.com/scala/scala/pull/7133.patch"},"body":"This PR brings several improvements to the inliner and optimizer.\r\n\r\n## Teaser\r\n\r\n```scala\r\nclass C {\r\n  def a = Array.fill[Option[String]](10)(None)\r\n  def b(a: Array[Int]) = a.map(_ + 1)\r\n}\r\n```\r\n```\r\n$> qsc Test.scala -opt:l:inline '-opt-inline-from:**'\r\n\r\n$> cfr-decompiler C.class\r\n```\r\n```java\r\npublic class C {\r\n    public Option<String>[] a() {\r\n        int fill_n = 10;\r\n        if (fill_n <= 0) {\r\n            return new Option[0];\r\n        }\r\n        Option[] fill_array = new Option[fill_n];\r\n        for (int fill_i = 0; fill_i < fill_n; ++fill_i) {\r\n            None$ none$ = None$.MODULE$;\r\n            fill_array[fill_i] = none$;\r\n        }\r\n        return fill_array;\r\n    }\r\n\r\n    public int[] b(int[] a) {\r\n        int n = a.length;\r\n        int[] arrn = new int[n];\r\n        for (int map$extension_i = 0; map$extension_i < n; ++map$extension_i) {\r\n            int n2;\r\n            arrn[map$extension_i] = n2 = a[map$extension_i] + 1;\r\n        }\r\n        return arrn;\r\n    }\r\n}\r\n```\r\n\r\n## State of 2.12\r\n\r\nIn 2.12, there is a single round of inlining.\r\n  - After building the call graph, the heuristic looks at every callsite and decides which ones to select for inlining\r\n  - These inline requests are then filtered (avoid cycles) and ordered (leaves of the request tree are inlined first)\r\n  - The selected callsites are inlined\r\n  - Then the closure optimizer runs and re-writes closure invocations that appear within the same method as the closure allocation (to directly call the closure body method instead).\r\n  - Local optimizatinos then clean up (closure allocation is eliminated, lots of other cleanups)\r\n\r\n## Changes to inlining procedure\r\n\r\nThis PR changes the inlnier and closure optimizer to run in a loop (or, more precisely an inner loop of the inliner and an outer loop of inliner and closure optimizer):\r\n  - The beginning is the same as in 2.12 (build call graph and select inline requests)\r\n  - The inliner no longer \"fixes up\" the call graph of the callsite method (remove inlied callsite, add those of inlined code). Instead, methods changed by the inliner removed and re-added to the call graph. This re-runs the type analysis, which may result in a more precise call graph (callsites may get a more precise receiver type after inlining).\r\n  - Callsites in methods changed by the inliner are re-checked by the inliner heuristic, potentially creating new inline requests (for callsites that could not be inlined in the previous round). This is the inner loop.\r\n  - Once inlining is done the closure optimizer runs\r\n  - Methods changed by the closure optimizer are once again passed to the inliner to check for more callsites to inline. The inliner and closure optimizer run in a loop until they are done, this is the outer loop.\r\n\r\n## Inliner heuristics\r\n\r\nThe inliner heuristics are adjusted, changes in this PR are marked (new). They work as follows\r\n  - Methods or callsites annotated `@noinline` are not inlined\r\n  - We don't inline into forwarder methods (including synthetic ones, such as `foo$anonfun$adapted`, bridges, boxing/unboxing forwarders)\r\n  - Methods or callsites annotated `@inline` are inlined\r\n  - Higher-order methods with a function literal as argument are inlined\r\n  - Higher-order methods where a parameter function of the callsite method is forwarded to the callee are inlined\r\n  - (new) Methods with an `XRef` parameter are inlined. When nested methods update variables of the outer method, those variables are boxed into `XRef` objects. Inlining the nested method usually allows eliminating the `XRef` box.\r\n  - (new) `ScalaRunTime.array_apply` and `.array_update` are inlined if the receiver is statically known to be an array. Those methods have a big pattern match for all primitive array types. This pattern match is later reduced (by cleanup optimizations) to the single matching case.\r\n  - (new) Forwarders, factory methods and trivial methods are inlined. This includes bridges, `anonfun$adapted` methods, trivial methods such as `_+1` closure bodies, etc.\r\n    - Field accessors are **not** inlined, because fields are private. Inlining a field accessor changes a call to a public getter into a field read of a private field. This would mean that methods accessing fields can then no longer be inlined into different classes (it would cause illegal access errors).\r\n    - Trait super accessors (static methods in interfaces that use `invokespecial` to call the default method) are not inlined, because the `invokespecial` would have different semantics when inlined into some different class. (*)\r\n\r\n(*) Note that trait super accessors are still inlined when selected by a differnt heuristic, for example if they are higher-order methods with a function literal argument. In this case the static forwarder is inlined, and then also the `invokespecial` is inlined. So the actual default method body is ultimately inlined.\r\n\r\n## Size limits\r\n\r\nInlining is now subject to size limits. The limits were chosen by looking at method sizes when compiling the compiler and how they affect running time of the ASM analyzers. They are definitely up for dicsussion, and should maybe have command-line flags.\r\n  - `@inline`-annotated, higher-order, synthetic forwarder and `array_apply/update` methods are inlined if the resulting method has <= 3000 ASM instruction nodes\r\n  - higher-order callsites with a forwarderd function parameter, methods with `XRef` params, factories and forwarders that box/unbox are inlined if the result is <= 2000 ASM instructions\r\n  - generic forwarders and trivial methos are inlined up to 1000 ASM instructions\r\n\r\n## Improvements to local optimizations\r\n\r\nThere are several improvements to local optimizations (cleanups)\r\n  - Nullness analysis is now branch-sensitive\r\n  - Local variables created by the inliner for arguments of the callee, and local variables inlined into a method, are nulled out at the end of the inlined code. This fixes https://github.com/scala/bug/issues/9137.\r\n  - The inliner creates fewer local variables hodling arguments: if there is already some local variable holding the argument at the callsite, it is re-used in the inlined code.\r\n  - The optimizer treats module loads as always non-null. This slightly twists semantics: if a module is accessed in its super construtor, the field is still null. The behavior can be disabled with `-opt:-assume-modules-non-null`.\r\n  - The optimizer eliminates module loads of some built-in modules (`Predef`, `ScalaRunTime`, `ClassTag`). This can delay / skip initialization of those modules. The behavior can be disabled with `-opt:-allow-skip-core-module-init`\r\n  - The optimizer can delay class loading, for example by eliminating an unused `Foo.getClass`. This can be disabled with `-opt:-allow-skip-class-loading`.\r\n  - `instanceof` and `checkcast` optimization is improved\r\n    - it knows about array types, which means array type tests can be eliminated statically\r\n    - it uses a nullness analyzer to rewrite `INSTANCEOF` checks\r\n  - Some intrinsics are re-written by the optimizer\r\n    - `ClassTag(classOf[X]).newArray` is rewritten to `new Array[X]`\r\n    - `java.lang.reflect.Arrays.getLength(x)` when `x` is statically known to be an array is rewritten to `ARRAYLENGTH`\r\n    - `x.getClass` when `x` is statically known to be a primitive array is rewritten to `LDC`\r\n\r\n## Compiler performance\r\n\r\nFirst the good news: the compiler built with the new inliner/optimizer runs ~2.5% faster on the larger codebases `scalap` and `scala`, around 1% faster on the small `better-files` codebase. [Results here](https://scala-ci.typesafe.com/grafana/dashboard/db/pr-validation?orgId=1&var-scalaSha=84de40d%7C9eef228&var-source=All&var-bench=HotScalacBenchmark.compile&var-host=scalabench@scalabench@&from=1535455395266&to=1538045749924).\r\n\r\nThe not so good news: running the optimizer is a significantly slower than before. Compiling the compiler with the optimizer enabled: the jvm phase went from 43 seconds to 93 seconds.\r\n\r\nBy far the most amount of time is spent in the `SourceValue` analysis, which computes producers and consumers. This analysis is used in a number of places: rewrite closure invocations, push-pop, box-unbox, remove stale stores. It might be possible to fuse the local optimizations that use this analysis into one.\r\n\r\nBesides taking a lot of cpu cycles, asm analyses also have a huge memory churn. This can be easily observed by attaching a profiler, there is basically constant minor GC going on as soon as the compiler reaches the backend.\r\n\r\n## Bugfixes\r\n\r\nFixes some older bugs\r\n  - An unused `Int.unbox(\"\")` should not be eliminated, as it throws a CCE (bug in 2.12)\r\n  - Inlining may cause a crash when writing the classfile and computing stack map frames (ClassBType of inlined code not created and cached during inlining, also bug in 2.12)\r\n\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/scala/scala/issues/comments/430570247","html_url":"https://github.com/scala/scala/pull/7133#issuecomment-430570247","issue_url":"https://api.github.com/repos/scala/scala/issues/7133","id":430570247,"node_id":"MDEyOklzc3VlQ29tbWVudDQzMDU3MDI0Nw==","user":{"login":"lrytz","id":119636,"node_id":"MDQ6VXNlcjExOTYzNg==","avatar_url":"https://avatars1.githubusercontent.com/u/119636?v=4","gravatar_id":"","url":"https://api.github.com/users/lrytz","html_url":"https://github.com/lrytz","followers_url":"https://api.github.com/users/lrytz/followers","following_url":"https://api.github.com/users/lrytz/following{/other_user}","gists_url":"https://api.github.com/users/lrytz/gists{/gist_id}","starred_url":"https://api.github.com/users/lrytz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lrytz/subscriptions","organizations_url":"https://api.github.com/users/lrytz/orgs","repos_url":"https://api.github.com/users/lrytz/repos","events_url":"https://api.github.com/users/lrytz/events{/privacy}","received_events_url":"https://api.github.com/users/lrytz/received_events","type":"User","site_admin":false},"created_at":"2018-10-17T10:07:36Z","updated_at":"2018-10-17T10:07:36Z","author_association":"MEMBER","body":"> has this been tested with the parallel backend - if nothing else this should be able to reduce some of the extra overheads of inliner as inliner is part of the for local optimisations isn't it?\r\n\r\nVery good point, I'll test the parallel backend. It will not help for inlining, because inlining works across compilation units, so we cannot parallelize. But it works for all the intra-method optimizations, which is where most of the time is spent anyway.\r\n\r\n\r\n> is this change readily back-portable to 2.12\r\n\r\nTechnically I don't see a problem backporting it to 2.12. So it's a question of risk, it's a big change that impacts generated bytecode. We should at least gain a bit of confidence first and see how well it does on 2.13.x.\r\n\r\n> Did you already look at the inliner warnings in the current build\r\n\r\nNo, it's a good suggestion. We might learn a few useful things from looking at those warnings. Last time I looked, the main problem was mixed compilation: when a Scala method references a Java type for which there's no bytecode available, we cannot inline that method. This was very common because we have some core classes in the library written in Java. This PR fixes that by going back to JavaThenScala."}}
{"actor":{"display_login":"lrytz"}}