Methods defined in traits are not inlined

[scabug]

Compiling

trait Foo {
  @inline final def foo(x: Int): Unit = {
    println(x)
  }
}
class Bar {
  def bar(y: Foo): Unit = {
    y.foo(7)
  }
}

yields (with -Ydebug and -Ylog:inline)

[log inliner] Treating CALL_METHOD test2.Foo.foo (dynamic)
	receiver: trait Foo
	icodes.available: true
	concreteMethod.isEffectivelyFinal: true
[log inliner] inline failed for test2.Foo.foo:
  pair.sameSymbols: false
  inc.numInlined < 2: true
  inc.hasCode: false
  isSafeToInline: false
  shouldInline: false
        
test2.scala:12: warning: Could not inline required method foo because bytecode was unavailable.
    y.foo(7)
         ^
[log inliner]  test2.Bar.bar blocks before inlining: 1 (4) after: 1 (4)
[log inliner] Analyzing test2.Foo$class
[log inliner] Not inlining into foo because it is marked @inline.
[log inliner]  test2.Foo$class.foo blocks before inlining: 1 (7) after: 1 (7)

Expected behavior would be inlining foo into bar. It all works if you change Foo to be a class instead of a trait.

I did some digging around and apparently ICode reading does not resolve methods bodies in traits:

scala> global.icodes.icode(global.definitions.getClass("scala.collection.immutable.MapLike"),true).methods.map(_.code)
res0: List[global.icodes.global.icodes.Code] = List(null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, ICode 'companion', null, null, null, null, null, null, null, null, null, null, ...

Furthermore, it looks like class file reading will never load a trait's impl class (which actually contains the method bodies):

scala> global.definitions.getClass("scala.collection.immutable.MapLike")
res2: global.Symbol = trait MapLike

scala> res2.implClass
res3: global.Symbol = <none>

There's really no way to get at it:

scala> global.definitions.getClass("scala.collection.immutable.MapLike$class")
scala.reflect.internal.MissingRequirementError: class scala.collection.immutable.MapLike$class not found.
	at scala.reflect.internal.Definitions$definitions$.getModuleOrClass(Definitions.scala:662)
	at scala.reflect.internal.Definitions$definitions$.getClass(Definitions.scala:615)

The reason is that ClassPath.scala explicitly excludes these class files (ending in $class.class):

/** A useful name filter. */
def isTraitImplementation(name: String) = name endsWith "$class.class"
...
object DefaultJavaContext extends JavaContext {
  override def isValidName(name: String) = !isTraitImplementation(name)
}

I believe this is a bug on its own - commenting out isValidName fixes the implClass behavior but not the inlining issue altogether.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4767?orig=1
Reporter: @TiarkRompf
Other Milestones: 2.12.0-M2

[scabug]

@paulp said:
That filter is only in place if inlining isn't on. I don't have a good explanation for what seems like an unreasonable amount of indirection, but you can see it in the PathResolver constructor.

class PathResolver(settings: Settings, context: JavaContext) {
  def this(settings: Settings) = this(settings, if (settings.inline.value) new JavaContext else DefaultJavaContext)

% scala3 -Yinline

scala> global.definitions.getClass("scala.collection.immutable.MapLike$class")
res0: global.Symbol = class MapLike$class

[scabug]

@paulp said:
That sample code doesn't really go all the way to inliner for you, does it? Foo$class doesn't have a method with that signature: it's "foo(Foo, int)", not "foo(int)".

[scabug]

@paulp said:
Also, see (from my last time to this dance) http://lampsvn.epfl.ch/trac/scala/changeset/22335 where the enclosed test case http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/test/files/pos/bug3234.scala includes this case and says "need more work before this one works." I do not unfortunately remember why I stopped short of that one.

[scabug]

@paulp said:
Oh (not tired of talking to myself yet) I see that the test case for 3234 is testing jack. The trait method marked @inline isn't inlined, but no warning is emitted because (presumably) it's never even considered.

[scabug]

@TiarkRompf said:
Sorry about the confusion, the correct signature is def bar(y: Foo): Unit (fixed above). I didn't follow up all the way to the check in PathResolver, I guess you're right about that. Not sure whether implClass always returning NoSymbol is a problem in other circumstances.

[scabug]

@paulp said:
I've got a handle on what's happening; I can't see how this was ever close to working. When looking up method implementations for inlining, it only looks at base classes. It needs to make the "lateral" jump to the implementation class to find anything worth inlining. I'm not sure if it's finding the forwarder method, but it doesn't seem interested in inlining it if it is. I hacked more logic into the inliner and eventually got to the point where the trait-defined method with implementation in Foo$class would be inlined; but then it fell apart because it has the wrong signature (i.e. the receiver is the first argument to a static method.)

So before I continue any more down this road, since it feels like rather a lot of "original research" for something I had thought was closer to working order, I thought I'd ask for a sanity check.

[scabug]

@TiarkRompf said:
Inlining the forwarder method could be sufficient: since the forwarder contains an explicit call of the implementation method wouldn't that be dealt with transitively?

However it seems like lookupIMethod would need to do the same thing as lookupImplFor, namely look at overridingSymbol while walking up the inheritance chain.

Also, lookupImplFor aborts the traversal if sym.owner.isTrait. I'm not sure about the reasoning behind that check.

I may be missing something (a lot, possibly) but to me it looks like the lookup logic could be simplified into something like this:

      // look up methSym for a receiver instance of classSym:
      var actualClass = classSym
      var actualMeth = methSym
      while (actualMeth.owner != actualClass) {
        val ov = actualMeth.overridingSymbol(actualClass)
        if (ov != NoSymbol) {
          actualMeth = ov
          assert(actualMeth.owner == actualClass)
        } else {
          actualClass = actualClass.superClass
        }
      }
      val iclass = icodes.icode(actualClass,true)
      val imethod = iclass.lookupMethod(actualMeth)

[scabug]

@paulp said:
In a trait, the methods are abstract and they have no code. That's presumably why lookupImplFor aborts, and that's also how I ended up hacking in the implementation class the last time around.

GenICode:

      case DefDef(mods, name, tparams, vparamss, tpt, rhs) =>
        debuglog("Entering method " + name)
        val m = new IMethod(tree.symbol)
        ...
        if (!m.isAbstractMethod && !m.native) {
          // stuff which leads to m.code being populated
        }
        else
          ctx1.method.setCode(null)

I'll look around some more.

[scabug]

@adriaanm said (edited on Jul 6, 2012 9:01:17 AM UTC):
I'm upping this to critical because I believe this is, well, critical.
I was looking a bit into the bytecode generated from PatternMatching.scala and was horrified to see none of my methods were being inlined.

[scabug]

@magarciaEPFL said:
Then refactor those methods you want inlined into a utility object, pass them only the environment values they need, compile with -optimize, to find out whether that makes the pattern matcher faster. If that doesn't make it faster, the reasons for slow performance must lie somewhere else, most likely.

[scabug]

@adriaanm said:
Thanks, yes, I know about the workaround, but I do believe this ticket should still be fixed ASAP.

[scabug]

@magarciaEPFL said:
Just before releasing M3 you also suggested a last-minute change in the optimizer, so please let us know in advance what requests you'll make shortly before M6.

[scabug]

@adriaanm said (edited on Jul 6, 2012 2:59:01 PM UTC):
I didn't request you fix it this weekend. You don't agree this is an important bug?
As a reminder, I'm using 'critical' to indicate bugs that should be fixed before we go into RC mode.

[scabug]

@paulp said:
Sorry to interrupt, but I'd like to put in a request for it to be fixed this weekend.

[scabug]

@magarciaEPFL said:
there's one TODO in scala/scala#849 . Improvements are welcome, specially before Monday.

[scabug]

@paulp said:
Wow, that worked? I'd also like to request someone to wash my car this weekend.

I threw some code at the TODO but am not 100% sure what DO equals so let me know if we're after something else.

[scabug]

@adriaanm said (edited on Jul 9, 2012 9:43:34 AM UTC):
I'd be happy to take it to the carwash on my way to picking up your cappuccino.
Let me know on which boat you'll be shipping it over. I'll be waiting in the port.

Also, Miguel, thanks for looking into this. Traits are everywhere. So is a strong desire for inlining.

[scabug]

@magarciaEPFL said:
By popular demand here's a draft version of the not-so-minor changes to Inliner this ticket requires:
magarciaEPFL/scala@scala:2.10.x...magarciaEPFL:SI-4767-b

Still needs to be tested with the nightly. It would be great if @gkossakowski could gather data on its performance effect.

[scabug]

@gkossakowski said:
Miguel: I don't think this will have any immediate performance effect. If we get this ticket fixed we might be able to refactor some code in a compiler and only then see the performance effect.

[scabug]

@magarciaEPFL said:
Discussion on fixing ICodeReader at https://groups.google.com/d/topic/scala-internals/w_ySCPJRmvg/discussion

[scabug]

@magarciaEPFL said:
To get a handle on this problem, I've implemented a fix in the experimental optimizer http://magarciaepfl.github.com/scala/

As a result:

• all callsites to final methods of traits are emitted as invokestatic
• of the above, those methods additionally marked @inline are inlined too

In the example

trait T {
  @inline final def m(x: Int) {
    println(x)
  }
}
class C {
  def host(y: T) {
    y.m(7)
  }
}

The resulting bytecode for host() is:

public void host(T);
  Code:
   Stack=2, Locals=3, Args_size=2
   0:	bipush	7
   2:	istore_2
   3:	getstatic	#15; //Field scala/Predef$.MODULE$:Lscala/Predef$;
   6:	iload_2
   7:	invokestatic	#21; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   10:	invokevirtual	#25; //Method scala/Predef$.println:(Ljava/lang/Object;)V
   13:	return

Without the @inline annotation, the bytecode for host() looks like:

public void host(T);
  Code:
   Stack=2, Locals=2, Args_size=2
   0:	aload_1
   1:	bipush	7
   3:	invokestatic	#15; //Method T$class.m:(LT;I)V
   6:	return

With the current optimizer as we know the callsite to T.m(Int) is emitted as:

   3:	invokeinterface	#15,  2; //InterfaceMethod T.m:(I)V

Here's how the new optimizer supports inlining of trait methods, documentation included:

magarciaEPFL/scala@dbf85bf

[scabug]

@adriaanm said:
It would be great if you could take the knowledge gained from this quest and push the current optimizer a little further down the right path.

[scabug]

@adriaanm said:
Un-assigning to foster work stealing, as announced in https://groups.google.com/forum/?fromgroups=#!topic/scala-internals/o8WG4plpNkw

[scabug]

@adriaanm said:
Unassigning and rescheduling to M6 as previous deadline was missed.

[scabug]

Malcolm Greaves (malcolmgreaves) said:
Hi! I was just bitten by this bug in a Scala 2.11.7 program. I see that the last update to this ticket was over a year ago. Have any brave volunteers made a dent in this one yet?

[scabug]

@retronym said:
Yes!, @lrytz has fixed this in the experimental backend ("-Ybackend:GenBCode -Yopt:l:classpath") in Scala 2.11.7. This backend will be on by default in Scala 2.12.

See: scala/scala#4312