JIT编译器

楼主确定要跳这个坑了么…？ 
如果只是想笼统的了解JVM的JIT编译器的话，我不建议从C2入手。 
好吧我确定楼主确实是要跳这坑的。跟我来

可以先看看前同事Vladimir Ivanov讲解JIT编译器： 
JIT-compiler in JVM seen by a Java developer, Vladimir Ivanov, JavaOne 2013 Moscow, 2013

Charles Nutter的系列演讲也OK： 
JVM JIT for Dummies, JavaOne 2012, 2012

请楼主先说说你已经知道的（包括基本的编译原理、JIT编译器的特定知识、其它JVM JIT编译器的实现），以及研究C2的动机，然后我看看如何引导你进入C2的世界。

hellhell 写道有个叫IdealGraphVisualizer的工具，可以看C2的node。 
期待R大的答案。

嗯嗯，IdealGraphVisualizer是研究C2的实用工具之一。我之前在第0回JVM源码阅读活动的“为啥别读HotSpot VM的源码”里有提到和演示它。 
工具的下载链接用这个：http://ssw.jku.at/General/Staff/PH/igv_latest.zip

=================================================

C2包含许多传统编译器的技术，例如 
* SSA形式的中间表现（intermediate representation） 
* GVN（global value numbering） 
* CSE（common sub-expression elimination） 
* CCP（conditional constant propagation） 
* Constant folding 
* DCE（dead code elimination） 
* Alias analysis 
* LICM（loop-invariant code motion） 
* Loop unrolling 
* Loop peeling 
* Escape analysis 
* Scalar replacement / SRoA（Scalar Replacement of Aggregate） 
* BURS（bottom-up rewrite system） 
* Code Scheduling: Global Code Motion (GCM) / Local Code Motion (LCM) 
* Graph-coloring register allocator 
* Peephole optimization

LeafInWind 写道字节码是如何转换为Ideal Graph的

字节码转换为Ideal Graph的过程在C2里叫做parsing，这是一个抽象解释（abstract interpretation）的过程。

LeafInWind 写道而Ideal Graph又是如何基于ad文件转换为机器码的

ad文件是个DSL（domain-specific language），描述了一个BURS匹配系统的匹配规则。

也有一些JIT编译器/运行时特有的技术，例如： 
* uncommon trap / deoptimization 
* OSR（on-stack replacement） 
* dynamic profile-based optimization 
  * devirtualization 
  * guarded inlining 
  * inline caching

还有跟GC交互的VM会用到的技术，例如： 
* Safepoint 
* OopMap / stack map 
* base-pointer / derived-pointer tracking

还有Java或者跟Java类似的面向对象语言特有的技术，例如： 
* CHA（class hierarchy analysis） 
* Lock elision 
* Lock coarsening 
* Array Bounds Check Elimination / Range Check Elimination

还有C2特有的技术，例如： 
* Sea-of-node IR / Program Dependence Graph（Ideal Graph）

就不穷举术语了。借用John Rose在这个演示稿里的介绍，HotSpot VM的JIT编译器所用到的技术的列表如下（包括C1和C2）：

John Rose 写道

挺多知识点的？

这些背景知识都得先有所掌握才能开始真的探索C2的工作过程。最好先找几本编译原理的书把基础知识（特别是编译器后端知识）打扎实了再考虑真的着手深入研究C2。

等楼主补充一下信息我再回复。也欢迎其他同学来参与讨论喔！

=================================================

相关资料：

入门C2最好的材料就是Thomas Würthinger写的关于IdealGraphVisualizer的硕士论文： 
Visualization of Program Dependence Graphs, Thomas Würthinger, 2007 
其中第三章对C2的讲解非常精辟，是初学C2必读文章。文中这张图清晰讲解了C2的工作流程：

Thomas Würthinger 写道

C2的整体介绍最好的资料还是原始论文： 
The Java HotSpot™ Server Compiler, Michael Paleczny, Christopher Vick, Cliff Click, JVM’01

Overview of Ideal, C2’s high level intermediate representation, HotSpot Internals, OpenJDK Wiki 
介绍了C2 Ideal Graph的设计思路

但要真的理解Ideal Graph的设计思路，也就是“sea-of-nodes”或者叫“program dependence graph”，还是得把Cliff Click原本的几篇论文读了才行。C2的核心设计跟Cliff最初做这几篇论文时几乎一模一样，甚至还有部分代码就是从当时他的博士毕业作品一直遗留至今。 
From Quads to Graphs: An Intermediate Representation’s Journey, Cliff Click, 1993 
A Simple Graph-Based Intermediate Representation, Cliff Click, Michael Paleczny, 1995 
Combining Analyses, Combining Optimizations, Cliff Click, Keith Cooper, 1995 
Global Code Motion, Global Value Numbering, Cliff Click, PLDI’95 
这几篇里面1993年那篇写得很生动，建议先读。

John Rose写了篇讨论编译器IR的文章，也值得一读： 
Thinking About Intermediate Representations, John Rose, 2014-09

Cliff Click讲解C2里的类型格（type lattice）： 
Too Much Theory, 2012-02-12 
Too Much Theory, Part 2, 2012-02-27 
Too Much Theory, Part 3, 2012-03-24

Escape Analysis for Java, Jong-deok Choi, Mannish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff, OOPSLA’99, 1999

Exploiting Superword Level Parallelism with Multimedia Instruction Sets, Samuel Larsen , Saman Amarasinghe, PLDI’00, 2000

A Tutorial on Adding New Instructions to the Oracle® Java HotSpot ™ Virtual Machine, Vasanth Venkatachalam, AMD 
介绍了ad文件的格式，以及如何对其添加新指令

Optimal Code Generation for Expression Trees: An Application of BURS Theory, Eduardo Pelegri-Llopart, Susan L. Graham, 1988 
Engineering a Simple, Efficient Code Generator Generator, Christopher W. Fraser, David R. Hanson, Todd A. Proebsting, 1992 
讲解BURS的早期论文。C2的指令选择就是基于BURS的思想设计的，而ad文件正是C2的BURS系统的一部分。

The C2 Register Allocator, HotSpot Internals, OpenJDK Wiki 
介绍了C2的基于Chaitin算法的图着色寄存器分配器

Graph Coloring Register Allocation Papers, HotSpot Internals, OpenJDK Wiki 
图着色寄存器分配器的相关论文链接

C2的寄存器分配器还有许多潜在的改进点。它可以说是C2最慢的部分了。Niclas Adlertz在做一些相关研究，近期OpenJDK里C2寄存器分配器的改进也主要是他在做。可以关注一下他的论文（现在还没发表）。

=================================================

既然楼主特别指出关心两个过程——字节码->Ideal Graph、Ideal Graph->Machine Graph（MachNode）——那我推荐先通过另外两个项目熟悉相关概念，然后再回来研究C2的实现。

首先是Graal。

Graal是一个用Java实现的JIT编译器，可以插在HotSpot VM与Maxine VM上使用。 
它衍生自Maxine VM更早的一个用Java写的JIT编译器——C1X。C1X则是HotSpot C1编译器的Java移植版，基本结构与C1几乎完全一致。 
Graal保持了C1X的大致思路，特别是后端结构基本上还是一样的；但是它完全重写了前端，把C1X的HIR改为与C2相似的“sea-of-nodes”/program dependence graph的“StructuredGraph”。

由于StructuredGraph与Ideal Graph比较相似，从字节码到它们的构造过程也有相似之处；而Graal的代码结构比C2清晰得多，所以先从Graal入手去了解Program Dependence Graph的特性，然后再去看C2会舒服许多。 
更好的是Graal IR也可以用IdealGraphVisualizer来可视化。研究Graal与C2共用一个工具，在两者之间可以轻松切换。

Graal将Java字节码转换为StructuredGraph的实现代码在此：com.oracle.graal.java.GraphBuilderPhase 
（顺带一提，这就是个抽象解释的过程的实现）

Graal IR的介绍可以参考这篇论文： 
Graal IR: An Extensible Declarative Intermediate Representation, Gilles Duboscq, Lukas Stadler, Thomas Würthinger, Doug Simon, Christian Wimmer, Hanspeter Mössenböck, APPLC 2013, 2013

Graal的整体设计可以参考这个演讲： 
Wholly Graal: Accelerating GPU Offload for Java [CON6419], Christian Thalinger, Christian Wimmer, Vasanth Venkatachalam, JavaOne 2013

——————————————————————-

其次是Jikes RVM。

Jikes RVM是个用纯Java实现的JVM。上面提到的Maxine VM也是如此。 
这里提到Jikes RVM是因为它的优化编译器的指令选择跟C2相似，也用到了BURS。所以指令选择这部分可以先参考Jikes RVM的实现和相关文档，然后再回去看C2的实现。

但其实Jikes RVM的BURS代码就这么直接读也不算易读的。我比较不喜欢Jikes RVM里各种要在构建过程中生成代码的地方，这里正是其中之一——Jikes RVM的源码里有BURS的规则文件，构建过程中由它会生成出真正负责匹配的状态机的C代码。

那为啥还要推荐它呢？因为它胜在“有根可寻”。它的BURS名为jburg，是iburg的移植版。后者的一个变种在lcc里也有用到。

《A Retargetable C Compiler: Design and Implementation》详细介绍了lcc的实现。其中第14章提到了其BURS系统的实现，非常建议阅读。 
这本书有中文版，但翻译太烂所以我不推荐读中文版。

=================================================

Hmm，下次做个简易案例来带大家走一遍C2的编译过程好了〜

说来我以前就分析过一个案例，涉及了C2工作流程的一部分，在这 
里：http://hllvm.group.iteye.com/group/topic/34932 
请先读读这篇案例看是否有帮助 😉

还有几个主要面向Java应用开发者的实验： 
逃逸分析的实验：HotSpot 17.0-b12的逃逸分析/标量替换的一个演示 
基于superword的向量化的实验：降序循环总是比升序循环快？ 
Uncommon trap的实验：JIT编译找不到类？ 

感谢R神。你提到的上述技术我基本都了解。我目前主要对hotspot JIT的inline cache、逆优化、OSR还算熟悉。 
目前对C2编译器最关注的其实是它的寄存器分配问题。 
但也希望能借这个机会对C2有一个全面的理解。 

LeafInWind 写道RednaxelaFX 写道请楼主先说说你已经知道的（包括基本的编译原理、JIT编译器的特定知识、其它JVM JIT编译器的实现），以及研究C2的动机，然后我看看如何引导你进入C2的世界。

你提到的上述技术我基本都了解。我目前主要对hotspot中x86平台相关部分的代码比较熟悉，对JIT的inline cache、逆优化、OSR也算熟悉。

这里求个详细。能先介绍一下具体熟悉的部分是哪些不？

LeafInWind 写道但对字节码到理想图的转换，以及ad文件在理想图到最终机器码之间转换的细节，由于平台无关，目前还不算熟悉。

这些都是编译原理的基础知识。也就是说对编译原理并不太熟悉？还是说只是特定于C2的实现，因为它的代码太⋯那啥，所以想知道编译原理的各种概念如何在C2中体现？ 
如果编译原理基础都没啥问题的话我就不用多说啦，直奔具体实现。反之楼主就得补习一下了。

LeafInWind 写道目前对C2编译器最关注的其实是它的寄存器分配问题。

这个好办。C2的寄存器分配器用的是graph coloring的思路，具体来说是基于Chaitin算法。它的一部分声明就在ad文件里（平台相关的寄存器声明、每条指令的“开销”声明之类）。相关论文在这儿有链接：https://wiki.openjdk.java.net/display/HotSpot/Graph+Coloring+Register+Allocation+Papers

所以研究C2的寄存器分配就是你的研究动机了是么？或许不只如此？

这个更新太全面了，现在再不敢说这些技术都了解了，看来今后一段时间有得忙了，感谢R神。 
我对编译的理解主要来自大学时的课程学习以及之前对ideal graph的学习（也就是看的Würthinger的硕士论文），但总感觉一知半解，所以想基于C2编译器做更深入的学习。 

呵呵，总算知道楼主在做的是啥项目了。加油！

我又稍微更新了一下前面的回复，主要是针对你在顶楼问的那两点，希望对你有帮助 

可能是因为你关心的是个实现细节而那个实在太直观，作者觉得没必要写出来orz

有没有去看看Graal的parser？（GraphBuilderPhase）

现在开始看，呵呵

哈哈。C2编译的主入口确实是Compile::Compile()

Parse的部分的入口就在这里： 
http://hg.openjdk.java.net/hsx/hotspot-main/hotspot/file/a61af66fc99e/src/share/vm/opto/compile.cpp 
其中有调用cg->generate(jvms)，留意一下那里。这里的cg是调用CallGenerator::for_inline()得到的，实际上是个ParseGenerator： 
http://hg.openjdk.java.net/hsx/hotspot-main/hotspot/file/a61af66fc99e/src/share/vm/opto/callGenerator.cpp 
然后ParseGenerator::generate()会构造一个Parse实例， 
http://hg.openjdk.java.net/hsx/hotspot-main/hotspot/file/a61af66fc99e/src/share/vm/opto/callGenerator.cpp 
真正的parsing就是从其构造函数Parse::Parse()开始的。

Parse的过程中，（几乎）每个节点在生成出来之后都会马上经过PhaseGVN::transform()的优化： 
http://hg.openjdk.java.net/hsx/hotspot-main/hotspot/file/a61af66fc99e/src/share/vm/opto/phaseX.cpp 
而这就是图里右上角的部分：Ideal() -> Value() -> Identity() -> global value numbering

Ideal()、Value()、Identity()是Node类上可以说最核心的三个方法，它们的作用贯穿在整个C2的优化过程中。嘛说“整个”可能有点过头，至少可以说是在instruction selection之前吧。 
http://hg.openjdk.java.net/hsx/hotspot-main/hotspot/file/a61af66fc99e/src/share/vm/opto/node.hpp 
这仨主要是跟GVN和Iterative GVN配套使用的。

其实并不难找啦，给点耐心。有什么疑问欢迎继续来讨论～

看不见的话复制下来就可以看到啦。 
ci就是Compiler Interface，主要是为了让编译器不受runtime其它部分的变化而影响的抽象层。其中很多类都是跟runtime里的类对应的，特别是oops目录下的类。

例如说： 
ci/ciConstantPoolCache -> oops/cpCache 
ci/ciInstance -> oops/instanceOop 
ci/ciInstanceKlass -> oops/InstanceKlass 
ci/ciKlass -> oops/klass 
ci/ciStreams -> interpreter/bytecodeStream

还有少量本来应该是在C1和C2之间共享的一些公共服务，结果只有一个编译器用，例如说ciTypeFlow。它的作用是在C2真正parse字节码之前先找出基本块边界，并且计算出每个local variable slot的抽象类型。