Besides a faster register allocation algorithm and some trade-off in control and data-flow analysis for optimization purposes, which components/phases of a JIT compiler are different from a traditional ahead of time compiler?
-
2If this is trying to ask about the pros/cons of JIT vs AOT, possible duplicate I noticed after writing my answer: programmers.stackexchange.com/questions/65822/…– IxrecCommented Jan 11, 2015 at 16:32
-
1There are two big differences: JIT is severely time-constrained, so it cannot do things the way traditional backends do. But what the AOTs do not have, unlike JITs, is a very precise runtime profiling information, and the modern JITs use that a lot.– SK-logicCommented Jan 11, 2015 at 18:47
-
1… heap and patch up all use sites after the fact if it detects that the reference escapes. Escape Detection is simply watching the references … nothing Halting Problem-y about it. Inlining of potentially overloaded virtual methods is another one. Statically proving that it is legal is equivalent to solving the HP, but a JIT can just do it, and if an overload does come along, it just un-inlines back out. So, JITs cannot afford costly analysis, but oftentimes, they don't actually need it. The "generate code specific to the target platform" bit is the most boring part. And actually wrong, …– Jörg W MittagCommented Jan 12, 2015 at 2:46
-
1… too, you don't need JIT for that, AOT upon installation would work just as well for that use case.– Jörg W MittagCommented Jan 12, 2015 at 2:48
-
1@JörgWMittag - "a JIT can just do it, and if an overload does come along, it just un-inlines back out" -- or compile a second copy of the method, dispatching to the new overload, and vary which copy method calls are dispatched to based on the runtime type of the parameters. There are a lot of tricks like this... optimizing array access based on assumptions about array size, for example.– JulesCommented Jan 12, 2015 at 19:24
|
Show 5 more comments
3 Answers
The main differences between an AOT and a JIT compiler are resources and information.
An AOT compiler has infinite resources. It can use as much RAM as it likes, and take as much time as it wants. (Note that this is only theoretically true. Pragmatically, people don't like long time compiles. Plus, compilers are now typically embedded into IDEs, where they provide instant feedback while-you-type, so that at least lexing, parsing, semantic analysis, type inference, type checking, macro expansion, etc., basically everything except the actual code generation and optimization have to happen very fast and with low memory usage.)
A JIT compiler OTOH has to "steal" its resources from the running application. (Again, theoretically. Pragmatically, the JIT compiler has to work hardest, when a lot of new code is introduced into the system, this is typically when the application starts, at which point the loading of configuration files and setting up of object graphs is the bottleneck, not the JIT compiler.)
A JIT compiler has much more information available than an AOT compiler, and it doesn't have to work hard to get it. An AOT compiler can only get static information about the code. Static analysis algorithms are usually very expensive (often at least O(n2) in at least one of time and space, sometimes exponential) and they don't even reliably work, because many of them are equivalent to solving the Halting Problem (Class Hierarchy Analysis, Escape Analysis, Dead Code Elimination, for example).
A JIT compiler OTOH doesn't run into the Halting Problem, because it doesn't do static analysis. And it doesn't have to run expensive algorithms: want to know whether a method is being overridden or not so that you can potentially inline it? Don't need to run Class Hierarchy Analysis, just look at the classes, they're all there. Or even better yet: don't even bother, just inline it anyway, and if it turns out you were wrong about it not being overridden, un-inline it again. Want to know whether a reference escapes a local scope or not so that you can potentially allocate it on the stack? Don't bother, just allocate it on the stack, tag it, and when the tag shows up somewhere else, re-allocate on the heap. And since you only compile code when it is running, Dead Code Elimination is totally trivial because dead code will never run and thus never be compiled.
So, the basic difference is that the analysis in a JIT compiler can be simpler, because it has a lot of information available that an AOT compiler doesn't have, and the optimization and code generation must be simpler, because it has a lot less resources available. Note, however, that a JIT compiler can nonetheless perform much more aggressive optimizations than an AOT compiler can, because it doesn't necessarily have to prove the optimizations correct. If it turns out an optimization is wrong, it can always de-optimize again. (Not all JITs do this (the CLR JIT for example, is incapable of de-optimizing), but for example the HotSpot JIT in the Oracle JDK does.) Speculative Inlining is one such optimization that is only possible in a de-optimizing JIT.
One thing that is peculiar about JITs is that very often the languages they compile are designed to be easily compilable by a machine (e.g. JVM bytecode, CPython bytecode, Rubinius bytecode, LLVM IR, CLI CIL, Dalvik bytecode), whereas the languages that a typical AOT compiler compiles are designed to be easily readable by humans (e.g. Ruby, Python, Java). But I understood your question to be about an AOT vs. a JIT for the same language, so none of this applies. Obviously, if you compare compilers for different languages, there will be a lot of differences, and many of those will be totally unrelated to the difference between JIT and AOT and more related to the differences between the two languages.
answered Jan 12, 2015 at 3:33
Since that is a very broad question, I'll stick to conceptual differences rather than implementation details:
A JIT compiler can theoretically perform more platform-specific optimizations, since it doesn't have to worry about producing a binary that's compatible with as many machines as possible.
A JIT compiler has access to some information only available at runtime, which means it can do things like make an optimized integer-only version of your function because it's only seen integer arguments so far (this makes it good for dynamic languages), or try to use less memory because your system doesn't have much left.
An AOT compiler never needs to be installed on your users' machines. A JIT compiler (and the runtime or VM it usually comes with) needs to be there every time they run a program using it.
An AOT compiler typically looks at your entire program, or at least very large portions of it, allowing it to do things like check for type errors across modules (which is good in static languages that rigidly define the types each function will accept) and remove code it knows will never be called.
Because AOT compilation only happens once, the executable's performance is more predictable and repeatable, even in situations when a JIT may perform better on average.
-
Now that the question has been edited to say "phases", it sounds like it's asking about how JITs and AOTs are typically implemented, so this answer may not be relevant. I'll post it anyway since I already went to the trouble of typing it out, and it's still not clear whether OP would consider this information helpful or not.– IxrecCommented Jan 11, 2015 at 16:32
-
the question contained already the 'phases' part, I don't know why someone edited it by changing it to 'facets'– MatthiasCommented Jan 11, 2015 at 16:38
-
It looked to me like a typo for "facets", probably because "facets" is closer to being a synonym for "components" than "phases" is imo. Sounds like I totally misinterpreted the question then. I'll probably delete my answer once one about phases shows up.– IxrecCommented Jan 11, 2015 at 16:44
Most of the JIT compilers take an intermediate or bytecode language as their input. For that reason, the structure of a JIT compiler is closer to that of a traditional assembler than that of an AOT compiler.
Lexical analysis and parsing are much simpler, because the input language is much simpler that your typical high level programming language.
Semantic analysis is probably completely absent, trusting that the bytecode doesn't try to do the impossible (like mixing integer and floating point operations without the required conversions).
What a AOT and JIT compiler have in common are the optimisations and code generation, although a JIT compiler can't perform lengthy optimisations but can easily do optimisations that require information about how the code is actually being used.
answered Jan 11, 2015 at 17:54
-
Is there support for dynamic type checking for dynamically typed languages (with regard to instruction generation)?– MatthiasCommented Jan 11, 2015 at 17:56
-
1@Matthias: That depends on the capabilities of the bytecode. Commented Jan 11, 2015 at 18:36