Fine tune method inlining of static calls in AOT

[alexmarkov]

A lot of instance calls are converted to static calls by CHA-based devirtualization / global type flow analysis. However, they are rarely inlined.

For example, consider the following code (extracted from velocity_tracker Flutter microbenchmark):

import 'dart:typed_data';

class _Vector {
  _Vector(int size) : _offset = 0, _length = size, _elements = new Float64List(size);

  _Vector.fromVOL(List<double> values, int offset, int length)
      : _offset = offset, _length = length, _elements = values;

  final int _offset;

  final int _length;

  final List<double> _elements;

  double operator [](int i) => _elements[i + _offset];
  void operator []=(int i, double value) {
    _elements[i + _offset] = value;
  }

  double operator *(_Vector a) {
    double result = 0.0;
    for (int i = 0; i < _length; i += 1)
      result += this[i] * a[i];
    return result;
  }
}

_Vector v = new _Vector(10);
double x = 0.0;

main(List<String> args) {

  Stopwatch timer = new Stopwatch()..start();

  for (int i = 0; i < 100000000; i++) {
    x = x + v * v;
  }

  timer.stop();
  print ("Elapsed ${timer.elapsedMilliseconds}ms, result $x");
}

In this code, _Vector.[] is not inlined into _Vector.*.

--trace-inlining shows the following:

Inlining calls in _Vector.*
  Depth 1 ----------
  Polymorphic Instance Calls (0)
  Static Calls (2)
  => _Vector.[] (deopt count 0)
     Bailout: cold 0.000000
  => _Vector.[] (deopt count 0)
     Bailout: cold 0.000000

The heuristic which bails out is based on StaticCallInfo.ratio which is calculated using call counters (which don't make much sense in AOT).

Also, this is very different from instance calls: InstanceCallInfo.ratio is calculated but it is not taken into account, and there is no similar heuristic for instance calls.

To summarize, the inlining heuristics should be fine tuned for static calls to allow inlining of small methods.

/cc @mraleph

[aartbik]

Adding feedback from Alex here so we remember.

"The problem is that if we have compiled a function already, we have recorded number of instructions after optimizations. If we haven't compiled a function being inlined, then inliner builds graph and does a very limited set of optimizations before calculating number of instructions. This makes inliner heuristics weaker if we haven't compiled function yet. Maybe we can try compiling a function before inlining it to calculate inline weights for always-inline heuristic.
To see the difference, it is enough to comment out PrecompileConstructors call in precompiler.cc and run it on Golem. There are several benchmarks which regress considerably because constructors are not inlined, as always-inline heuristic doesn't work well on not-fully-optimized functions."

[aartbik]

The new heuristic exposed an issue with more inlining.
The kernel-precomp bots were seeing this error:

../../runtime/vm/object.h: 3134: error: Handle check failed: saw 2249186640 expected Function

This needs to be addressed before we can tune the heuristic properly.

[aartbik]

I did a bisection search on this failure, and found the offending inlining:

Static StaticCall:12( [email protected]<0> v150, v148) has ratio 0.000000

 => new Link.fromRawPath (deopt count 0)
     Success
       with reason AlwaysInline, code size 5, call sites: 1

Which is interesting, since it is not enabled by the new heuristic (ratio is 0.0). So another inlining must somehow interact badly with this one. Looking further.

@mraleph

[aartbik]

With a bisection search on just the inlining based on (the new) nonzero ratio, we arrive at the same culprit, but the cause-and-effect is more clear. We set the ratio of the following call to 1.0:

Static v75 <- StaticCall:134( Link.fromRawPath<0> v0, v73 T{Uint8List?}) T{_Link} has ratio 1.000000

which in turn allows the inlining of this call site in into

dart:io__AsyncDirectoryLister@17069316_next_<anonymous closure>

This in turn allows for inlining of the

StaticCall:12( [email protected]<0> v150, v148)

call I already found above.

Callee graph for inlining dart:io_Link_Link.fromRawPath (unoptimized)
==== dart:io_Link_Link.fromRawPath

--> doms(#1)=B49, preds= <--
B0[graph]:0 {
      v142 <- Constant(#null)
      v143 <- Constant(#<optimized out>)
}

--> dom=B0 doms(#0)= preds=B0, <--
B49[function entry]:2 {
      v144 <- Parameter(0)
      v145 <- Parameter(1)
      v146 <- Constant(#null)
      v148 <- Parameter(1) T{Uint8List?}
}
    DebugStepCheck:10()
    v150 <- AllocateObject(_Link)
    PushArgument(v150)
    PushArgument(v148)
    StaticCall:12( [email protected]<0> v150, v148)
    DebugStepCheck:14()
    Return:16(v150)

[aartbik]

In this method, we have three call sites that are inlined in a very similar way.
The original source code is:

    for (int i = 0; i < result.length; i++) {
          assert(i % 2 == 0);
          switch (result[i++]) {
            case listFile:
              controller.add(new File.fromRawPath(result[i]));
              break;
            case listDirectory:
              controller.add(new Directory.fromRawPath(result[i]));
              break;
            case listLink:
              controller.add(new Link.fromRawPath(result[i]));
              break;

For example, the File call site

   PushArgument(v95 T{Uint8List?})
   v97 <- StaticCall:100( File.fromRawPath<0> v0, v95 T{Uint8List?}) T{_File}
   PushArgument(v97)

becomes

    v170 <- AllocateObject(_File) T{_File}
    PushArgument(v170)
    PushArgument(v95 T{Uint8List?})
    StaticCall:12( [email protected]<0> v170, v95 T{Uint8List?})
    PushArgument(v170 T{_File})

But in the offending inlining of Link, the call site

    PushArgument(v73 T{Uint8List?})
    v75 <- StaticCall:134( Link.fromRawPath<0> v0, v73 T{Uint8List?}) T{_Link}
    PushArgument(v75)

becomes (note the _Link@17069316 instead of _File@17069316):

    v150 <- AllocateObject(_Link) T{_Link}
    PushArgument(v150)
    PushArgument(v73 T{Uint8List?})
    StaticCall:12( [email protected]<0> v150, v73 T{Uint8List?})
    PushArgument(v150 T{_Link})

The only difference I noticed is that File and Directory have a @pragma("vm:entry-point") on the fromRawPath method, and Link does not. Adding this pragma to Link actually makes the test pass.

  @pragma("vm:entry-point")
  factory Link.fromRawPath(Uint8List rawPath) {
    // TODO(bkonyi): handle overrides
    return new _Link.fromRawPath(rawPath);
  }

@mraleph does that make sense?

[mraleph]

@aartbik I think it makes sense if the test is testing directory listing or something like that.

If we inline all invocations of fromRawPath then we would tree shake the factory away. But in reality there are external invocations of this factory from other places.

@sjindel-google actually discovered a lot of missing entry-point annotations in his obfuscation fixing CL (see https://dart-review.googlesource.com/c/sdk/+/81009/17/sdk/lib/io/link.dart ). And he also looked into strengthening checks around entry-points.

[aartbik]

Cool. I verified that all failures with the bots yesterday go away with this one line change. So I will send out a separate CL for that, since it makes File/Directory/Link equivalent again, and unblocks my inlining heuristic CL. I assume @sjindel-google will follow up with other cases.

[aartbik]

Closing this issue, since we went from never inlining static calls to using a reasonably effective heuristics for inlining static calls under AOT (although fine-tuning these is expected to continue of course).