Eliminate non-escaping boxes, tuples and refs #4858

lrytz · 2015-11-23T15:00:38Z

This PR includes the commits of #4846.

Eliminate boxes, tuples and refs that are created and used within a
single method without escaping. For details on the implementation see
the doc comment in class BoxUnbox.

This allows using an AliasingAnalyzer for copy propagation (subsequent commit).

Previously the VarInstruction extractor did not include IINCs. Also give rename the isVarInstruction predicate to isLoadStoreOrRet, as it doesn't include IINC. Also fixes a bug in removeJumpAndAdjustStack, it checked the wrong opcode range before.

When running DCE, directly remove eliminated callsites from the call graph (instead delegating this task to the callees).

By convention (for performance), `aliasingFrame.aliases(slot) == null` means that the value at `slot` has no aliases, so this is isomorphic to having a singleton `AliasSet(slot)`. When merging an AliasingFrame `other` into `this`, at every value slot we have to keep the intersection of the two alias sets. In other words we have to remove from `this.aliases(slot)` those values that are not in `other.aliases(slot)`. This was wrong for the cases where `other.aliases == null` - we did not treat this case as a singleton set.

Copy propagation uses an AliasingAnalyzer: it replaces a `LOAD n` instruction by `LOAD m` where m is the smallest alias of n. This leads to stale STORE instructions. Stale STOREs are identified using a ProdCons analyzer and replaced by POPs. Values that are pushed on the stack by a side-effect free instruction and consumed by a POP are then removed by `eliminatePushPop`. This includes elimination of unused closure allocations and unused boxes and tuple allocations (*). A final cleanup eliminates `STORE x; LOADx` pairs where the stored value is not otherwise used. Fixes - scala/scala-dev#25 - scala/scala-dev#7 - scala/scala-dev#14 - scala/scala-dev#12 (*) We don't yet rewrite reads of boxes and tuples yet. For example, `val x = (1, 2); x._1` remains a method invocation and the tuple cannot be eliminated (scala/scala-dev#11). Inspired in many ways by Miguel's work!

Fixes scala/scala-dev#52. An IndyLambda may create a specialized function type, where the SAM is the corresponding specialized variant of apply. If this closure is invoked through the generic apply method, the closure optimizer would previously not re-write the invocation to the $anonfun method. This is now done, including the necessary box / unbox operations.

Fix the "consumersOfOutputsFrom" in the prod-cons analysis to support dummy instructions: - UninitializedLocalProducer - ParameterProducer - ExceptionProducer

For methods that are too large to run a producers-consumers analysis, don't run the closure optimizer. This is an oversight, all data flow analyses in the backend are guarded by a method size check.

If a DUP is consumed by two POPs, ensure that the DUP and its producer are eliminated. Before, only the DUP was eliminated, leaving an unused value on the stack.

Eliminate boxes, tuples and refs that are created and used within a single method without escaping. For details on the implementation see the doc comment in class BoxUnbox. This commit also cleans up the logic of inter-dependent method-level optimizations that run until reaching a fixpoint.

Eliminate casts that are statically known to succeed. This enables boxes to be eliminated and simplifies the implementation of closure allocation elimination.

Optimize IFNULL branches to GOTO when (non-)nullness of the tested value is known statically. This enables unreachable code to be removed, which in turn enables boxes to be eliminated. Changed a test flag from `-Ynooptimise` to `-Yopt:l:classpath` - I still have to do this systematically, this will follow later.

retronym · 2016-01-25T03:34:29Z

I think the -YoptTrace option ought to accept an argument that lets one limit the output to a particular class / method pair. As it stands, it is only really useful after you've extracted the method of interest to a standalone test case. Feel free to do this in a followup PR, though.

retronym · 2016-01-25T04:49:22Z

Here's a script to post-process the optimizer trace into a series of diffs (via a temp git repo). I've used your test case from 1a9e649 as the example.

https://gist.github.com/retronym/0efa5cea463aced52fae

Here's another example from the central commit in this PR: https://gist.github.com/retronym/99a026883916abf2d309

retronym · 2016-01-25T05:45:27Z

After looking at those diffs, I notice that eliminateStaleStores doesn't reduce maxLocals. This happens subsequently in dce, but I was wondering whether this is something that could/should be done more eagerly.

lrytz · 2016-01-25T09:16:30Z

the -YoptTrace option ought to accept an argument that lets one limit the output to a particular class / method pair

Added in 3dccf0e

notice that eliminateStaleStores doesn't reduce maxLocals

This is intentional, see this comment: lrytz@29d772d#diff-70147974eed4d5f7faa546e42504ce64R94

retronym · 2016-01-25T10:39:14Z

LGTM

Eliminate non-escaping boxes, tuples and refs

Improve simplifyJumps to rewrite IFEQ L4 L5 GOTO L6 to IFNE L6 L5 This rewrite is only correct if L5 is not the target of any jump instruction (otherwise, removing the GOTO would change semantics). Previously we did not do the rewrite if there was any label between the conditional jump and the goto (like L5). Now we track which labels are jump targets. Also adds a test for SI-9160 which tests the above. The unnecessary boxing mentioned in the ticket is optimzied since push-pop elimination (scala#4858).

Rewrite tests for new optimizer - SI-6941 - SI-2171 - t3430 - t3252 - t4840 - t2171 - t3430 - t3252 - t6157 - t6547 - t8062 - t8306 - t8359 - t9123 - trait-force-info - private-inline test cases for bugs fixed in the new optimizer - SI-9160, the unnecessary boxing mentioned in the ticket is optimzied since push-pop elimination (scala#4858). - SI-8796 - SI-8524 - SI-7807 fix flags file for t3420 remove an empty flags file remove unnecessary partest filters explicit inliner warnings in test t7582 Restore the lisp test. Removing the flags file - our build runs with the (new) optimizer enabled anyway. The test spent the past few years as an optimizer test in pos/ see https://issues.scala-lang.org/browse/SI-4512. The attempt may fail, but why not give it a try. $ git lg -S"lisp" ... | * | | | f785785 - SI-4579 Yoke the power of lisp.scala as a stress for the optimizer. (3 years, 8 months ago) <Jason Zaugg> ... * | | | | | | 622cc99 - Revert the lisp test. (3 years, 10 months ago) <Paul Phillips> ... * | | | | | | 97f0324 - Revived the lisp test. (3 years, 10 months ago) <Paul Phillips> ... * | 1e0f7dc - Imprison the lisp test, no review. (4 years, 4 months ago) <Paul Phillips> ... * | 6b09630 - "Freed the lisp test." Tweaked partest defaults... (4 years, 6 months ago) <Paul Phillips> ... * | fec42c1 - Lisp test wins again, no review. (4 years, 8 months ago) <Paul Phillips> ... * | 1c2d44d - Restored the lisp.scala test. (4 years, 8 months ago) <Paul Phillips> ... * | 15ed892 - Temporarily sending lisp.scala to be interprete... (4 years, 8 months ago) <Paul Phillips> ...

Tuples created for pattern matching are eliminated since scala#4858

lrytz added 11 commits October 29, 2015 21:37

Track aliases of primitive values in AliasingFrame

8cd1f95

This allows using an AliasingAnalyzer for copy propagation (subsequent commit).

[trivial] import Opcodes._ in two files, move a utility method

6ca9490

Remove InstructionResultSize (subsumed by InstructionStackEffect)

7f2a0a2

Clean up DCE: remove eliminated callsites from call graph earlier

5d4d2cc

When running DCE, directly remove eliminated callsites from the call graph (instead delegating this task to the callees).

Clean up optimizer settings.

9fa3783

Fix specialized function class names in closure optimizer

12b6598

Fix in "consumersOfOutputsFrom" query in prod-cons analysis

1161445

Fix the "consumersOfOutputsFrom" in the prod-cons analysis to support dummy instructions: - UninitializedLocalProducer - ParameterProducer - ExceptionProducer

scala-jenkins added this to the 2.12.0-M4 milestone Nov 23, 2015

lrytz force-pushed the opt/elimBoxes branch from 0a33ae3 to 7fc71bc Compare November 23, 2015 16:11

lrytz mentioned this pull request Nov 24, 2015

Eliminate box-unbox pairs, tuples, *Refs scala/scala-dev#11

Closed

lrytz force-pushed the opt/elimBoxes branch from 7fc71bc to 325a8ce Compare December 12, 2015 20:06

lrytz changed the title ~~Box-unbox elimination~~ Eliminate non-escaping boxes, tuples and refs Dec 12, 2015

lrytz added 5 commits December 13, 2015 09:41

Don't run closure optimizer on methods too large for prod-cons

ecbca54

For methods that are too large to run a producers-consumers analysis, don't run the closure optimizer. This is an oversight, all data flow analyses in the backend are guarded by a method size check.

Fix push-pop elimination for values pushed by DUP

b1fd1e8

If a DUP is consumed by two POPs, ensure that the DUP and its producer are eliminated. Before, only the DUP was eliminated, leaving an unused value on the stack.

Minor cleanups in eliminateStaleStores

34fcee8

Rename test MethodLevelOpts -> MethodLevelOptsTest

93de014

Make some testing tools from InlinerTest available to other tests

60ac9ec

lrytz force-pushed the opt/elimBoxes branch 4 times, most recently from 2c3a87b to c620ae7 Compare December 14, 2015 09:44

lrytz added 4 commits December 15, 2015 15:12

Eliminate unnecessary casts

e431978

Eliminate casts that are statically known to succeed. This enables boxes to be eliminated and simplifies the implementation of closure allocation elimination.

Ensure that -Yopt:l:none takes precedence, tidy optimizer settings

eacaee2

lrytz force-pushed the opt/elimBoxes branch from c620ae7 to 80b0660 Compare December 15, 2015 14:13

-YoptTrace takes a package/Class.method parameter

3dccf0e

scala-jenkins added the reviewed label Jan 25, 2016

lrytz added a commit that referenced this pull request Jan 25, 2016

Merge pull request #4858 from lrytz/opt/elimBoxes

90ee1b8

Eliminate non-escaping boxes, tuples and refs

lrytz merged commit 90ee1b8 into scala:2.12.x Jan 25, 2016

lrytz deleted the opt/elimBoxes branch January 25, 2016 12:02

SethTisue mentioned this pull request Jan 26, 2016

2.12.x bootstrap regression: stability test fails scala/scala-dev#77

Closed

lrytz added a commit to lrytz/scala that referenced this pull request Feb 13, 2016

SI-8790 test case

738f273

Tuples created for pattern matching are eliminated since scala#4858

lrytz mentioned this pull request Feb 13, 2016

SI-8790 test case #4965

Merged

adriaanm added the release-notes worth highlighting in next release notes label Feb 23, 2016

adriaanm added 2.12.0 and removed 2.12 labels Oct 29, 2016

This was referenced Apr 7, 2017

Do not needlessly create tuples when pattern matching scala/bug#8790

Closed

Needless pushing and popping of BoxedUnit.UNIT to stack scala/bug#8796

Closed

Unnececary boxing of match return values scala/bug#9160

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Eliminate non-escaping boxes, tuples and refs #4858

Eliminate non-escaping boxes, tuples and refs #4858

Uh oh!

lrytz commented Nov 23, 2015

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

lrytz commented Jan 25, 2016

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Eliminate non-escaping boxes, tuples and refs #4858

Eliminate non-escaping boxes, tuples and refs #4858

Uh oh!

Conversation

lrytz commented Nov 23, 2015

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

lrytz commented Jan 25, 2016

Uh oh!

retronym commented Jan 25, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants