Constant Folding

[retronym]

trafficstars

Implement constant folding. Miguel's impl: https://github.com/lrytz/scala/blob/opt/rebaseWip/src/compiler/scala/tools/nsc/backend/bcode/ConstantFolder.java

Existing partest tests: jvm/constant-optimization, t7006

[lrytz]

Also look at the 2.11 optimizer: https://github.com/scala/scala/blob/2.11.x/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala

[DarkDimius]

Is the goal of constant folding is to reduce bytecode size? If not, is there some smart constant optimization planned that is not performed by JVM?

See also https://bugs.openjdk.java.net/browse/JDK-8058164 and related tickets.

[lrytz]

I'm not actually planning to work on this in the near future. As you say, it would only make sense if there was something that we can do considerably better than the JVM.

[lrytz]

one existing test (currently in pending): https://github.com/scala/scala/tree/93fa559f62637fc3a49d7b961a1d07cf843b0e6b/test/pending/jvm/constant-optimization

[retronym]

I think the motivation of this one would be to enable further optimizations, e.g. to prove that some branches are dead, which might in turn enable box/unbox elim etc.

[da-tubi]

@lrytz @retronym Why ConstantOptimization is removed in Scala 2.13? Would it be helpful if someone port it to Scala 2.13.x?

[da-tubi]

@lrytz I'm interested in improving the Scalac Optimizer.

If I write a ConstantOptimizer, is it correct to create a PR under https://github.com/scala/scala/tree/2.13.x/src/compiler/scala/tools/nsc/backend/jvm/opt ?

And also provide a option under -opt: and the essential unit tests.

[lrytz]

Hi @da-tubi, nice to see you interested!

This is the right place for contributions, yes. See https://github.com/scala/scala/tree/2.13.x/test/junit/scala/tools/nsc/backend/jvm/opt for tests.

But first I'd like to learn why you are interested in contributing a constant folder. What is your motivation, do you have a specific project where you know it would help?

In my view, implemention constant folding "for its own sake" is not worth it, as the JVM is doing that already. It would only be worth the effort if constant folding unlocks more optimizations that the Scala optimzier can perform. Or maybe if we can treat certain Scala constructs as "constants" that are not actually constants at the bytecode level, but we know they can be treated as such given Scala's semantics? I don't have anything particular in mind though.

[da-tubi]

No specific project. Just for fun and performance!

[da-tubi]

I'm trying the tuning my Spark ETL code using the scala compiler flags. For CPU bound tasks, it works as expected. That's the motivation (for Performance). Just fixed https://github.com/scala/bug/issues/11247 and I'd like to contribute more on the Scala optimizer (for Fun).

[da-tubi]

I found a ConstantFolder (scala.tools.nsc.typechecker.ConstantFolder) in the typechecker.

That's why I'm asking if src/compiler/scala/tools/nsc/backend/jvm/opt is the right place (a somewhat silly question).

There are many compiler phases. If we expect that constant folding unlocks more optimization, should we implement Constant Folder in earlier phase?

[da-tubi]

• dead code elimination success: https://github.com/da-tubi/scala-optimizer/blob/master/AlwaysTrueIf.scala
• constant folding success: https://github.com/da-tubi/scala-optimizer/blob/master/BinaryConstantFold.scala
• Failed to remove the dead code: https://github.com/da-tubi/scala-optimizer/blob/master/BinaryConstantFoldVal.scala

[da-tubi]

From Wikipedia: https://en.wikipedia.org/wiki/Constant_folding

Constant propagation is the process of substituting the values of known constants in expressions at compile time.

We need to enable constant propagation in the ConstantFolder.

[lrytz]

There is a constant folder in the type checker indeed, it's implemented at the type level. This constant folder is mainly useful for literal types (scala> val a: 1 = 1; val b: 2 = 2; val c: 3 = a + b) and also for handling arguments to ConstantAnnotations.

For executable code, programmers never write code that directly benefits from constant folding (stuff like val x = 1 + 10; if (x == 11) { ... } / if (true) { ... } / true || x == true), so the constant folder in the type checker typically doesn't change anything in the code that it compiles. One exception is maybe code that originates from a code generator.

The reason constant folding is still a useful optimization is inlinling. This is true for almost all local optimizations, they typically optimize patterns that programmers never write directly, but that show up after inlining. One way to think about inilining is specialization: the code of the inlined function is copied and then specialized to the arguments that were previously passed in. If an argument is constant, the constant folder can do something, if it's a lambda, closure elimination can do something, etc.

Many optimizations can enable other optimizations to be applied, so the various optimizations in the backend are executed in a loop until nothing can be done anymore. That's why the constant folder in the type checker is not helpful for optimizing the executable code.

(In case you didn't come across it, this blog post might be interesting to you: https://www.lightbend.com/blog/scala-inliner-optimizer)

[da-tubi]

For the BinaryConstantFoldVal example:

The following code is generated using the optimizer option -opt:l:method

Compiled from "BinaryConstantFoldVal.scala"
public final class BinaryConstantFoldVal$ {
  public static final BinaryConstantFoldVal$ MODULE$;

  public static {};
    Code:
       0: new           #2                  // class BinaryConstantFoldVal$
       3: dup
       4: invokespecial #22                 // Method "<init>":()V
       7: putstatic     #24                 // Field MODULE$:LBinaryConstantFoldVal$;
      10: return

  public void main(java.lang.String[]);
    Code:
       0: bipush        11
       2: bipush        11
       4: if_icmpne     16
       7: getstatic     #32                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
      10: ldc           #34                 // String Yes
      12: invokevirtual #38                 // Method scala/Predef$.println:(Ljava/lang/Object;)V
      15: return
      16: getstatic     #32                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
      19: ldc           #40                 // String Deadcode
      21: invokevirtual #38                 // Method scala/Predef$.println:(Ljava/lang/Object;)V
      24: getstatic     #32                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
      27: getstatic     #45                 // Field scala/runtime/RichInt$.MODULE$:Lscala/runtime/RichInt$;
      30: getstatic     #32                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
      33: iconst_1
      34: invokevirtual #49                 // Method scala/Predef$.intWrapper:(I)I
      37: ldc           #50                 // int 100000
      39: invokevirtual #54                 // Method scala/runtime/RichInt$.to$extension:(II)Lscala/collection/immutable/Range$Inclusive;
      42: getstatic     #57                 // Field scala/math/Numeric$IntIsIntegral$.MODULE$:Lscala/math/Numeric$IntIsIntegral$;
      45: invokevirtual #61                 // Method scala/collection/immutable/Range$Inclusive.sum:(Lscala/math/Numeric;)I
      48: invokestatic  #67                 // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
      51: invokevirtual #38                 // Method scala/Predef$.println:(Ljava/lang/Object;)V
      54: return
}

And the following pattern should be optimized in simplifyJumps

       0: bipush        11
       2: bipush        11
       4: if_icmpne     16