Invalidating build caches using JVM bytecode callgraph analysis

Mill build.mill files run on the JVM; the source code is written in Scala, but it compiles to the same JVM bytecode that Java or Kotlin or any other JVM languages do. When you look at the definition of a task such as:

Task takes a "by-name" block argument of type ⇒ T.

Essentially, this means when you call Task{ …​ }, the …​ is wrapped in a zero-argument function () ⇒ …​ of type Function0[T] that you can call via .apply() returning a T:

"By-name" parameters are just a convenient way to define blocks of runnable code without needing to tediously repeat the () ⇒ in front of every one, but for all intents and purposes the effect is the same: you get a Function0[T] that you can call via .apply to get the value out of it. This Function0 is what lets Mill decide whether or not it needs to run the code in the block:

The problem is, the only thing that a Function0 lets you do is call .apply()! In particular, Function0 does not let you inspect the function to look at its source code or implementation: like function values in any language, all that is encapsulated and hidden away from you. How then can Mill detect that the .toUpperCase in fooTask was replaced by .toLowerCase? Or that modifying barHelper affects barTask, even if barTask's own code block is unchanged?

Because deciding whether a code block has changed is difficult, most build tools punt on the problem entirely:

All these approaches are problematic: (1) is maximally conservative and pessimistic, while (2) is maximally lasse-faire and optimistic, while (3) is workable but awkward. None of these approaches are fatal - people have lived with build tools working like this for decades - but we can do better.

For example, consider barTask:

We mentioned earlier that body of the Task block is wrapped in an anonymous Function0 () ⇒ …​. This anonymous function compiles to an $$anonfun method with the bytecode below, which can be rendered using the javap -c -p command on the relevant compiled .class file:

This bytecode contains a lot of invokevirtual and invokeinterface methods that specify, after all the compiler’s work is done, which methods in the JVM bytecode actually need to be called when this function is actually run. We can see the invocation of scala/Predef$.println and os/read$ in the bytecode, some mill/api helper methods, and also the call to barHelper.

We can also look at the barHelper method in the bytecode, which is defined as follows:

barHelper's bytecode contains a single call to java/lang/String.toUpperCase, which is what we expect given its definition in the source code.

Just like the build graph of tasks we described earlier, the calls between methods in our build codebase also form a graph: a call graph. For the small example snippet above, the (simplified) callgraph looks like this

With this call graph, it is straightforward to do a breadth-first search starting from each task to find all transitively called methods and hash their contents (the bytecode shown above). Any change to this hash would indicate that a method’s implementation changed, and any tasks that depend on it needs to re-evaluate. For example, the change we saw earlier to the barHelper source code:

Would result in a corresponding change in the barHelper bytecode:

This would change the hash of barHelper, and from the callgraph we can then see that barTask depends on barHelper and needs to be invalidated

The bytecode for a method is typically much more stable than the source code: it is not affected by formatting, comments, local variable names, etc.. This means that if the bytecode hash for a method changed, it likely means the implementation changed, and any tasks that call that method (directly or transitively) need to be re-evaluated.

Consider the following example:

Here, we are calling bazHelper on the value in barTask. But the behavior of a qux.bazHelper() doesn’t just depend on the implementation of bazHelper itself, but also:

This actually turns out to work: the fact that you have qux means that you must have called its constructor and passed in arguments (directly or indirectly):

Thus, the existing callgraph analysis above is sufficient to handle the various cases around instance methods without modification.

A similar approach can be take to analyzing fields, which are defined via the var or val keyword in contrast to methods defined via def:

In this case, barTask references the suffix field directly, without going through a bazHelper method. Method call graph analysis does not track fields, but it doesn’t need to: a field can only get its value from the methods that set it, whether the constructor (above setting var suffix = suffix0) or other methods (e.g. def doubleSuffix, which sets suffix = suffix + suffix).

Since these methods are all already captured as part of the normal callgraph analysis, it’s fine to ignore fields entirely: you will never miss a code change that affects a field value because such code changes must occur in methods which we already track.

A follow up example is what happens if the task block relies on a field (val) rather than a method (def) in an enclosing object?

The problem here is that the transitive callgraph of barTask is not sufficient: not only do we need to call barTask, we first need to instantiate object enclosing as well. This is similar to the Instance Methods case we looked at above, but instead of relying on some object instance that barTask instantiates and calls, we are looking at barTask's own object instance, that must have been instantiated earlier. Singleton objects do not take constructor parameters, but in both cases we need to account for the constructor code for the object on which we are calling the method.

In practice, this is straightforward: we just need to add an edge from the enclosing#<init> constructor (and that of any other enclosing objects) to barTask when constructing the callgraph:

The JVM bytecode has direct support for virtual method calls via invokevirtual: e.g. a single call to Qux.bazHelper() may call out to any number of methods defined in various subclasses of Qux:

It is not always obvious what implementation qux.bazHelper will end up calling: indeed in this example it may end up calling different implementations when run at different times! To resolve this, you need to analyze the various classes in your program, so you can resolve such virtual callsites to possible definition sites in subclasses.

There are varying degrees of precision for which you can analyze virtual methods, e.g. Class Hierarchy Analysis and Rapid Type Analysis described in Fast Static Analysis of C++ Virtual Calls, OOPSLA96, or even more sophisticated dataflow approaches such as Points-To Analysis. At a high level, the distinction between these is in how they look for subclasses that may provide an implementation for a virtual method:

Mill uses a variant of (1) Class Hierarchy Analysis: we treat every Mill Task as a potential entrypoint, and find all classes instantiated across your build codebase in one pass. This is less precise than running the analysis separately for every Task that Rapid Type Analysis would require, but is more precise than a naive Class Hierarchy Analysis that doesn’t consider whether a class is instantiated or not.

For example, in the snippet below, Mill is able to identify that qux.bazHelper may call Qux1#bazHelper or Qux2#bazHelper, but not Qux3#bazHelper because there is no new Qux3 being instantiated anywhere in our codebase:

Performance is a big constraint in Mill’s analysis. In particular, we don’t want to have to analyze the entire Java or Scala standard libraries, because that would be very expensive. Mill thus only constructs a call graph for code written and compiled locally as part of your build, modelling upstream libraries in a simplified fashion (similar to Whole-Program Analysis without the Whole Program, ECOOP 2013). In practice this means:

Essentially, we assume that any upstream library methods that we pass objects to - either as parameters or as the method receiver - could call any other methods on those objects. Consider the following case:

Here we are defining our own subclass of Exception and OutputStream, with their own overrides of def printStackTrace and def write respectively. However, when we end up calling ex.printStackTrace, we are calling printStackTrace on the super-type Exception, and def write is not called at all in our code since its calls live upstream in PrintStream and OutputStream! By the rules above, we are able to capture the possibility of these calls:

Since Mill does not do Points-To Analysis or other Data-flow Analyses, it isn’t able to determine that the value ex is of class MyException, or that the value stream is of class MyOutputStream, and so it must treat them broadly as Exception and OutputStream instances that could be of any sub-class. This may result in false positives with Mill treating method as callable when it really isn’t, invalidating more caches than it needs to, but it will never result in Mill missing a potential call and failing to invalidate a task cache when it should have done so.

Mill special-cases handling of inline functions (e.g. () ⇒ …​) and single-abstract method instances (e.g. new Runnable{ def run() = …​ }) and treats them as if they were called immediately at their definition site.

Ideally, we would consider each method called if there is a call-site that could reach it and if its defining class is instantiated, but analyzing that precisely (also called Rapid Type Analysis) would be too expensive.

For most methods, our simpler Class Hierarchy Analysis only considers whether a call-site could reach a definition, without caring about whether the defining class is instantiated. But this has a pathological case for widely-used simple interfaces. Consider the following example where fooTask calls fooHelper in a lambda, and barTask calls barHelper is a lambda:

If we handled lambdas via Class Hierarchy Analysis, with our simplified handling of Library Methods, then:

This results in a callgraph as follows, where every lambda callsite could potentially call every lambda. This is conservatively correct, but imprecise enough to be useless.

As a compromise, for lambdas and SAM types, we instead use the other heuristic: we instead consider them called once they are instantiated, ignoring whether or not there is a callsite. This is still conservatively correct, and can still have false positives if someone instantiates a lambda or SAM they never call. But people generally don’t do that, and so empirically it provides a much more precise callgraph.

With the adjusted handling of lambdas and SAM types, with the various lambdas assumed to be called immediately where-ever they were defined, the callgraph becomes a lot more precise and useful,

We special case methods that return Task to not participate in the callgraph analysis. By removing Task methods from the callgraph analysis, we are essentially making the assumption that these methods do not have side effects, and any change will be tracked at runtime anyway by the build graph we discussed at the start of this article.

Allowing Task methods to participate is problematic because these methods are often defined as part of abstract classs or traits in upstream libraries with many such methods. With the simplified handling of Library Methods above, this results in any call to a Task method potentially calling every other Task method, which again while conservatively correct renders the callgraph imprecise enough to be useless.

The assumption that methods returning Task do not have side effects is not enforced: there is nothing to stop you from performing side effects and mutating variables in a method that returns a Task. But in practice nobody does that, so this turns out to be a fine assumption to make.

The biggest limitation of using method callgraph analysis to detect code changes affecting tasks is the lack of dataflow analysis: we are simply aggregating all methods that get called (transitively) by a task, but we don’t actually know if those methods actually affect the task output. For example, consider the following snippet:

The Qux#<init> method has the following bytecode:

If we modify this by adding a second unused field:

This results in a corresponding change to the bytecode to initialize the new field:

Which affects barTask, because our callgraph has Qux#<init> being called by barTask

However, if you actually track the dataflow of the code, we would realize that the field otherSuffix is not used by barTask at all! Only suffix is used. Thus although our Qux#<init> was affected by the code change, barTask isn’t actually affected, and so invalidating barTask and forcing a re-evaluation would be wasteful and unnecessary.

This is perhaps the largest gap in the callgraph analysis we present here: while we are able to analyze the dependencies between methods based on how they call each other via invokevirtual or invokespecial bytecodes, we are unable to analyze the dependencies between the fields that those methods set or the values that they return. This can result in false positives where changes to constructors or other methods cause our tasks to invalidate unnecessarily.

Another major limitation in this analysis is that it assumes that all method calls in your program are statically specified in the bytecode. This is not true of JVM applications in general: anyone can call Class.getMethod(methodName).invoke() with a dynamically computed methodName: String, leaving static bytecode analysis with no way to figure out what method is actually being called:

In this example, the getMethod call takes the method name as b + h.capitalize, but in general it could require arbitrary runtime computation to decide what method to call. While it is possible to figure out this out in some cases (e.g. the Graal Native Image analyzer gives a best effort attempt at doing so) there will always be scenarios where the reflection cannot be figured out statically.

Unlike the limitation above that results in false positives, this limitation can result in false negatives where a method called by a task changes and the task does not re-evaluate, because the method call happened via getMethod.invoke which our analyzer cannot understand.

Although in theory this could be an issue, in typical Scala code (which build.mill files are written in) runtime reflection is relatively rare. Scala codebases and libraries tend to perform a lot of their work at compile-time: inferring types, resolving implicit parameters, expanding macros, and so on. While that means the compiler is more complicated, it also means the bytecode that gets output by the compiler is much simpler, without the runtime reflection/classloading/classpath-scanning logic often present in Java codebases. Thus, Mill can analyze the JVM bytecode emitted by a Scala program with high confidence that the callgraph defined in the bytecode gives a complete and accurate picture of how the methods in the program call each other.

To test out how well this works in practice, I ran a number of manual tests to exercise the callgraph analysis, using Mill’s own Mill build as the test case.

In general, Mill’s fine-grained task invalidation via bytecode callgraph analysis works as expected: in many cases where the change is trivial it is able to narrow down the effect of the change and reduce the number of tasks we need to invalidate, although for wide-ranging changes (e.g. Deps.scalaVersion) it still ends up invalidating a large number of tasks, and there are some known limitations around the treatment of val fields where the invalidation is less fine grained than it could be. Compared to earlier versions of Mill which aggressively invalidated all caches on every single change, this was a big improvement!

Performance-wise, ad-hoc benchmarks on com-lihaoyi/mill’s own build show a ~5% increase in build.mill compilation times due to the cost of the bytecode callgraph analysis.

Mill’s callgraph analysis is written as a post-processing step on the .class files that are generated by the Scala compiler that Mill uses to compile it’s build.mill and package.mill files. The analysis computes a hash for every method representing its own implementation and that of transitively called methods, and saves that to a methodCodeHashSignatures.json file for the Mill evaluator to include in Task cache keys at runtime. Thus it is easy to separate the time taken for each phase, which I have done below:

This slowdown is not negligible, but it is acceptable: the cost is only paid when the build.mill is re-compiled, and it will likely end up saving much more time in tasks that we can avoid running (e.g. a single no-op Zinc incremental compile may be 100s of milliseconds). The bytecode callgraph analysis can likely be further optimized in future if necessary.