JIT In Android ART

Interestingly, although Android claim that it's latest Runtime(ART) adopts Ahead-Of-Time(AOT) compiling, a jit folder was silently shipped into art/compiler folder within AOSP around the early era of Marshmallow.

Fact is that: the installation procedure takes a long time on some of the devices running on ART. E.g. Facebook sometimes takes 2 minutes to install! Perhaps that's the reason why Android want to move back to JIT.

Projects usually use interpreter along with JIT engine. That is, interpreting the code or byte code first and collecting the profile information including how often a method is executed, aka. how "hot" the method is, and type information if you're working with dynamic type language. After several turns, if a method is "hot" enough, the execution engine would use the JIT compiler to compile the code into native code and delegate the execution to the native compiled method in every invoking of that method afterward. E.g. Dalvik VM's JIT engine.

Nevertheless, there are also some projects don't use interpreter, but instead using an extremely fast compiler to compile each method executes next ahead before using another optimizing compiler to do more optimized compiling on those "hot" methods. E.g. Google V8 javascript engine.

The latter approach is usually faster, but to my surprise, the new ART JIT adopts the first, the interpreter combo.

The great journey of ART's JIT starts from art/runtime/jit/jit_instrumentation.cc. Instrumentation in ART acts like a listener listens for various of interpreting or compilation events. E.g. methods invoking, branches and OSR(On Stack Replacement). JitInstrumentationCache::CreateThreadPool() adds the JitInstrumentationListener instance to the runtime instrumentation set.

JitInstrumentationListener listens to three events: method entered(JitInstrumentationListener::MethodEntered()), branches(JitInstrumentationListener::Branch()) and virtual or interface method invoking(JitInstrumentationListener::InvokeVirtualOrInterface()). The compilation triggers, instrumentation_cache_->AddSamples(...), reside within method entered and branches callbacks. 

JitInstrumentationCache::AddSamples() shows that ART JIT uses a slightly modified counter approach to profile execution flows. Usually, JIT compiler simply set a counter threshold and trigger compilation task after exceeding that value. But there seems to be THREE counter thresholds in this case: warm_method_threshold_, hot_method_threshold_ and osr_method_threshold_. Constructing a JIT system with more levels. The values are passed from the JVM arguments(JVM is an interface, not an unique instance, ART is one of the implementations) but I can't find those arguments at this time. But from the code arrangement we can inferred that warm_method_threshold < hot_method_threshold < osr_method_threshold. I'm also wondering how osr_method_threshold woks.

If one of the thresholds is reached, it would arrange a JitCompileTask. The following flow is pretty interesting:  Jit::CompileMethod() would be invoked, but Jit::Compile() is actually a stub of jit_compile_method(). What's special about jit_compile_method()? It's a C symbol loaded from dynamic library libart-compiler.so.  libart-compiler.so has nothing special, it's source files live side by side with source files mentioned above, I think modularization is the main reason why they adopt this kind of ad-hoc approach.

After going into jit_compile_method(), OptimizingCompiler::TryCompile() would be called. Few months ago, there are two compilation levels in TryCompile(): CompileBaseline and CompileOptimized. But now, those levels is replaced by a neater, single level  approach:

  // Try compiling a method and return the code generator used for
  // compiling it.
  // This method:
  // 1) Builds the graph. Returns null if it failed to build it.
  // 2) Transforms the graph to SSA. Returns null if it failed.
  // 3) Runs optimizations on the graph, including register allocator.
  // 4) Generates code with the `code_allocator` provided.
  CodeGenerator* TryCompile(ArenaAllocator* arena,
                            CodeVectorAllocator* code_allocator,
                            const DexFile::CodeItem* code_item,
                            uint32_t access_flags,
                            InvokeType invoke_type,
                            uint16_t class_def_idx,
                            uint32_t method_idx,
                            jobject class_loader,
                            const DexFile& dex_file,
                            Handle<mirror::DexCache> dex_cache,
                            bool osr) const;

The comments had explained almost everything. The graph is an instance of HGraph class, which is easy to perform various of compiler optimizations. ART JIT use a method-based JIT compiler in contrast with the old DalvikVM JIT, which use trace-based compiler and switch to method-based compiler only under device charging.

In summary, JIT in ART doesn't seem to use any special techniques, so in my opinion, the key of performance falls on the interpreter, I would take some time researching on that part.

[Quick Note] V8 Javascript Engine's First Stage Compiler

V8 is properly, in my opinion, the fastest javascript runtime at the time(No offense SpiderMonkey, although benchmarks differ from one to another, V8 got the best grade in average). There are some well known properties that make it run so fast:

• No interpreter, use baseline compiler instead. But this characteristic has just been subverted on the bleeding edge of the development tree. 
• No intermediate representation(IR) in baseline compiler. But optimization(second stage) compiler do use its own IR.
• Use method-based JIT strategy. This is fairly controversial, but as we can see later, use function as its compilation scope makes lots of works easier in comparison with trace-based strategy, which spends lots of efforts on determining trace boundary.
• Hidden class. In short, if a variable modifies its object layout, adding a new field for example, v8 create a new layout(class) instead of changing the origin object layout(e.g. Using linked list to "chain" object fields, which appears in many implementation of early era javascript runtime). 
• Code patch and inline cache. These two feature are less novel since they have already beed used in lots of dynamic type runtime for over twenty years.

I'm going to talk about the baseline compiler. The code journey starts from Script::Compile API which as the name suggest, compiles the script. V8 has a fabulous characteristic that it can be used standalone, that's the very key which bears Node.js. You can checkout V8's embedder guide for related resource.

After several asserting checks, the main compilation flow comes to Compiler::CompileScript(compiler.cc:1427). One of the important things done here is checking code cache. (compiler.cc:1465)

    // First check per-isolate compilation cache.
    maybe_result = compilation_cache->LookupScript(
        source, script_name, line_offset, column_offset, resource_options,
        context, language_mode);
    if (maybe_result.is_null() && FLAG_serialize_toplevel &&
        compile_options == ScriptCompiler::kConsumeCodeCache &&
        !isolate->debug()->is_loaded()) {
      // Then check cached code provided by embedder.
      HistogramTimerScope timer(isolate->counters()->compile_deserialize());
      Handle<SharedFunctionInfo> result;
      if (CodeSerializer::Deserialize(isolate, *cached_data, source)
              .ToHandle(&result)) {
        // Promote to per-isolate compilation cache.
        compilation_cache->PutScript(source, context, language_mode, result);
        return result;
      }
      // Deserializer failed. Fall through to compile.
    }

If there are previous compiled code(or snapshot in v8's term), it would deserialize them from disk. Otherwise, the real compilation procedure would be triggered, namely, CompileToplevel (compiler.cc:1242). In this function, parsing information and compilation information would be setup and passed to CompileBaselineCode (compiler.cc:817). Let's ignore the Compiler::Analyze first and jump to GenerateBaselineCode.
Here comes some interesting things: (compiler.cc:808)

static bool GenerateBaselineCode(CompilationInfo* info) {
  if (FLAG_ignition && UseIgnition(info)) {
    return interpreter::Interpreter::MakeBytecode(info);
  } else {
    return FullCodeGenerator::MakeCode(info);
  }
}

Previous says that one of the advantages V8 has is entering compilation process directly without interpreting ahead. So why there are codes related to interpreter ? It turns out that V8 is also going to have a interpreter! Here is a brief introduction about Ignition, the new interpreter engine. But let's just stare on the compilation part first.

So now we comes to FullCodeGenerator::MakeCode (full-codegen/full-codegen.cc:26). There are a few important things here where we'll come back to, for now, let's focus on FullCodeGenerator::Generate .
Now here's the exciting part. FullCodeGenerator::Generate is a architecture-specific function, which residents in source code files in separated folders like arm, x64 .etc. Let's pick few lines of code from x64 version:

      if (locals_count >= 128) {
        Label ok;
        __ movp(rcx, rsp);
        __ subp(rcx, Immediate(locals_count * kPointerSize));
        __ CompareRoot(rcx, Heap::kRealStackLimitRootIndex);
        __ j(above_equal, &ok, Label::kNear);
        __ CallRuntime(Runtime::kThrowStackOverflow);
        __ bind(&ok);
      }

Pretty familiar right? It seems that it directly generates the assembly code!
Normally this sort of approach would appears in education project like homework in college compiler courses. Mature compiler framework often has lots of procedures on generating native codes. Directly generate native assembly is thus one of the most important factors that speed up V8.
Another worth mentioned thing is the "__" at the prefix of each several lines above. It's a macro defined in full-codegen/full-codegen.cc:

#define __ ACCESS_MASM(masm())

Here MASM does not means Microsoft's MASM where the first 'M' character of the latter one stands for Microsoft. Our MASM stands for macro assembler, which is responded for assembly code generating.

Back to FullCodeGenerator::Generate. VisitStatements seems to be the code emitter for js function body. Now we stop the code tracing here and step back to see the declaration of FullCodeGenerator.(full-codegen/full-codegen.h) 

class FullCodeGenerator: public AstVisitor

It turns out that the code generator itself is a huge AST visitor! And VisitStatements is the top level visitor function that would dispatch different part of code to visitors like FullCodeGenerator::VisitSwitchStatement, FullCodeGenerator::VisitForInStatement or FullCodeGenerator::VisitAssignment to name a few.

Last but not the least, some people say Ignition, the interpreter mentioned before, is not like SpiderMonkey or JavascriptCore(Safari). I'm really curious about that, maybe I would wrote another article about that : )

[Quick Note] OrcJIT in LLVM

JIT(Just in Time) compilation becomes more and more popular in recent years due to the rising demand on higher dynamic type language performance, Javascript and Python, to name a few.

However, LLVM, which is developed mainly for static type language like C/C++, also joined JIT's battlefield few years ago. Although applying LLVM on dynamic compilation has some drawbacks, for example, long running optimizations increase latencies and inadequate type system which is originally developed for static type rather than dynamic type. It doesn't stop the community from working on this subsystem. More and more enhancements come up like native support for patch points and stack maps, which debut in version 3.8 as experiment features.

There are mainly two kinds of compilation strategies: method base and trace base. Difference between them falls on the compilation scope they adopt. As their name suggests, method-based approach take functions or methods as minimum compilation units. Google's V8 Javascript engine is a well-known example. Trace-based JIT use traces, where we can treat them as a range of control flow, as the compilation units. Firefox's TraceMonkey and Lua's JIT use this kind of approach. Which of them is better may required several academic papers to explain and the debate still goes on now.

Back to LLVM, the main JIT implementation is called MCJIT. It adopted the popular MC- framework within LLVM, which is kind of LLVM's own assembler, as its backend to gain more flexibility. MCJIT use non of strategies mentioned above, instead, it use LLVM's Module as the compilation unit. You can use the llvm::EngineBuilder class to build a llvm::ExecutionEngine, which is the main JIT interface, then you can either retrieve compiled symbols or run compiled functions directly by its rich APIs like getPointerToFunction or runFunction.

There are several drawbacks on using module as compilation unit, in short, module scope is too big in comparison with method and trace, which may spend too much time on compilation procedure and increase latency. And that's what OrcJIT tries to fix.

Orc is the shorthand of on-request-compiling. As the name suggests, it lazily performs the compilation process of each functions within the module until it is used. OrcJIT also build from scratch instead of building on MCJIT. Even more, it introduced a concept called Layer. Layer is like LLVM's IR pass, but handles compilation procedure rather than IR. It provides flexibilities for building your own JIT compilation flow. Nevertheless, OrcJIT still lacks of central layer manager similar to llvm::PassManager and even common layer interface! In another word, we can only construct our own compilation "stack" by passing the base layer instance to the first argument of another layer constructor and non of the layer class inherit a common parent class as interface. For example, the lli program construct its compilation stack as below:

OrcLazyJIT(std::unique_ptr<TargetMachine> TM,
             std::unique_ptr<CompileCallbackMgr> CCMgr,
             IndirectStubsManagerBuilder IndirectStubsMgrBuilder,
             bool InlineStubs)
             : TM(std::move(TM)), DL(this->TM->createDataLayout()),
             CCMgr(std::move(CCMgr)),
             ObjectLayer(),
             CompileLayer(ObjectLayer, orc::SimpleCompiler(*this->TM)),
             IRDumpLayer(CompileLayer, createDebugDumper()),
             CODLayer(IRDumpLayer, extractSingleFunction, *this->CCMgr,
                 std::move(IndirectStubsMgrBuilder), InlineStubs),
             CXXRuntimeOverrides(
                 [this](const std::string &S) { return mangle(S); }) {}

The compilation flow would run as the order: ObjectLayer, CompileLayer, IRDumpLayer, CODLayer. Where CODLayer is the instance of CompileOnDemandLayer and treated as the highest level class in OrcJIT. We would use CODLayer to add module by addModuleSet and invoke findSymbol to retrieve compiled function symbols. OrcJIT would differ the compilation of each function until we called findSymbol.

Pros of OrcJIT would be the decreasing compilation region, brings potential to add profiler for detecting hot method which is used in merely every dynamic compilation framework nowadays. On the other hand, OrcJIT does not use the llvm::ExecutionEngine interface. Although it provides llvm::orc::OrcMCJITReplacement as an wrapper,  the main author tends to use its own interface, this raises lots of questions and arguments on the mailing list from the debut of OrcJIT. What's more, as previous mentioned, OrcJIT's layer still has no common interface and layer manger.

I was pretty excited when I saw OrcJIT, because smaller compilation unit is what trace-based JIT overwhelms method-based JIT. It looks that LLVM gets another armor in the battlefield of dynamic compilation.