Improvements for the inlining heuristics

[lrytz]

• Right now, we inline a any higher-order method call where the argument function is either a Literal, or a parameter of the callsite method

def m                = foo(x => e) // foo is inlined
def n(f: Int => Int) = foo(f)      // foo is inlined

• We should inline higher-order methods only if that will eliminate a megamorphic callsite. This means:
  • The argument function is ultimately invoked
  • We can inline enough such that the function callsite moves to the same method as the closure instantiation

def m(f: Int => Int) = f(0)
def n(f: Int => Int) = m(f)
def t = n(x => x + 1) // if we can inline both m and n, the function invocation moves to t and becomes monomorphic

• We should take into account additional information at the callsite
  • In the example below, we know that b.m2 will invoke m1 (the type of b is B). Note that we don't need a type analysis for this: the invocation b.m2 is generated as INVOKEVIRTUAL B.m2, even though m2 is declared in the superclass A. This doesn't make type analysis useless though, see Type propagation analysis #13.

abstract class A {
  def m1(f: Int => Int): Int
  def m2(f: Int => Int): Int = m1(x => f(x + 1))
}
final class B extends A {
  def m1(f: Int => Int) = f(0)
}
class Test {
  def t(b: B) = b.m2(x => x + 1) // after inlining m2, can also inline m1 - we know it's B.m1
}

• We should start creating inline requests with downstream requests. In the example above, after inlining m2, we want to inline m1.
• We should only create inline requests that we know will succeed. It does not make sense to have an inline request with a number of downstream requests that may fail: if one of them fails, the goal is missed (making a callsite monomorphic). In that case we should not start inlining at all.
• We should extend the heuristic with criteria about method sizes / method size growth.
• We should run the closure optimizer (that re-writes (x => e).apply() to the closure's body method) right after / during inlining some method, to enable inlining closure body methods. Currently it runs in a separate pass over all methods after inlining is done.
• We should keep future optimizations in mind: they will create new goals for the inliner heuristics. For example, a closure that captures an IntRef should be entirely inlined, including the closure body, so the IntRef doesn't escape its defining method.

def f = {
  var r = 0
  for (i <- (1 to 10)) r += i
  r
}

• We should keep the possibility open to make methods public to enable inlining (Investigate: make private methods public to enable inlining #41)
• box elimination as inlining goal, example: avoid boxing scala#5303

[lrytz]

Closing this. There are a number of ideas here, but many of the actionable ones are done in scala/scala#7133