小型jit編譯器之最佳化技術(shù)

1、小型JIT編譯器之最佳化技術(shù)評(píng)估,指導(dǎo)教授:單智君老師指導(dǎo)學(xué)長(zhǎng):喬偉豪學(xué)長(zhǎng)組員:鍾懿軒，蔣季融，李國(guó)丞,Outline,觀察-----------------------------------鍾懿軒動(dòng)機(jī)-----------------------------------鍾懿軒目標(biāo)-----------------------------------鍾懿軒初步設(shè)計(jì)-----------------------------李

2、國(guó)丞修改過的設(shè)計(jì)------------------------蔣季融未來進(jìn)度-----------------------------蔣季融,觀察,Java是用stack運(yùn)算。因?yàn)榈讓訖C(jī)器是register-based非stack-based，用interpreter執(zhí)行，performance不佳。加入JIT將bytecode轉(zhuǎn)換為register-based的指令，可以增進(jìn)performance。若於JIT中加入一些機(jī)制

3、，增進(jìn)其效能，則可進(jìn)一步增進(jìn)java performance。,動(dòng)機(jī),加入的機(jī)制若能產(chǎn)生IR，使JIT compiler後端處理更方便。就有可能增進(jìn)JIT的速度。folding機(jī)制:讀入bytecode產(chǎn)生register-based的IR，簡(jiǎn)便後段處理。因此決定於JIT中加入folding機(jī)制。,目標(biāo),將folding機(jī)制加入JIT中，以最少的overhead，fold最多的pattern，達(dá)到增加performance的目的。,

4、初步設(shè)計(jì),架構(gòu)圖Bytecode分類Pattern 統(tǒng)計(jì)遇到的問題,舊架構(gòu)圖,,舊folding架構(gòu)圖,Bytecode分類,1.定義:參考kim’s paper(Advanced POC Model-Based Java Instruction Folding Mechanism)P:非operation含有push。Op:operation含有push不含pop。Oc:operation含有pop不含push。C:非

5、operation含有pop。On:不含push pop,無法分類者。,Bytecode分類(續(xù)),參考學(xué)長(zhǎng)的paper(stack operations folding in java processors)P: transfering data from Constant Register or Local Variable to the operand stack。O: gets data from the operand

6、stack and then performs different tasks Oe: ALU type operator that writes the result back to the operand stack。Ob: Branch type operator。Oc: Complex type operator including array access, constant pool access 。Ot: una

7、ble or hard to join the folding operation。C: consumes data from the operand stack, and stores data back into the local variable。,Bytecode分類(續(xù)),2.統(tǒng)計(jì)bytecode push/pop數(shù):檢視kvm source code(bytecodes.c):查看每道bytecode的執(zhí)行碼中有多少

8、push, pop的動(dòng)作。檢視jvm spec(chapter 6)每道bytecode都已規(guī)定好stack情況，可直接紀(jì)錄。,Analyze patterns possibility in Java class file,Get information from Java class fileDo it our self (in C++)BCEL library for Java (http://jakarta.apach

9、e.org/bcel),Possibility of patterns,(1)KIM所統(tǒng)計(jì)出的Patterns及出現(xiàn)百分比(2)自行統(tǒng)計(jì)”Embedded CaffeineMark”的結(jié)果,Problems,Classification can save time of string matchingUsing “Hashing” is better than string matching !Benefit of class

10、ification no longer exists when using “Hashing” !使用string matching sequential search:Too much finding overhead。,修改過的設(shè)計(jì),新架構(gòu)圖Folding方法,Structure of “JVM with JIT”,,Java code source,JAVA compiler,Java bytecode,Class load

11、erBytecode verifier,,Hardware,Operating System,Java class libraries,,,,,,,,,,Hotspot,Interpret,,,,Native code,,,,JVM,Interpreter,JIT,,,Y,N,Interaction between Interpreter & JIT,,,,,,,Time,,One method,,Hotspot Detec

12、t,,Interpret,,Time,,Complicated code,,,,,,,JIT,,,End of method,(Start of method),Code block,,,,Code block,Struture of our JIT,JIT,IR generator,Folding,Code generator,,,,,IR1,IR2,Native code,,,Method,方法(4-1)-Overview,O-or

13、iented.Search bytecodes for O-type bytecode then find folding pattern for this O-type bytecode.Data structure: array.Table:Used for storing information of bytecodes.,方法(4-2)-Data Structure,Table: use bytecode ID numbe

14、r as index.Buffer: length=4;Bytecode information:TypeP_num: Push number Postive, stack growC_num: Pop number Negative, stack fall,方法(4-3)-Algorithm,經(jīng)由bytecode定義可得:P-type: C_num=0, P_num=1.C-type: P_num=0, C_num=

15、1.O-type: 不一定，視其功能而定。以O(shè)-type的attribute為尋找pattern的依據(jù)。P_num: 向後尋找P_num個(gè)bytecodesC_num: 向前尋找C_num個(gè)bytecodes,方法(4-4),Match: 向前找C_num個(gè)bytecodes的P_num剛好和O-type的C_num相抵銷。向後找P_num個(gè)bytecodes的C_num剛好和O-type的P_num相抵銷。整個(gè)patte

16、rn的attribute和要為零。無法match放棄此O-type bytecode，繼續(xù)找下一個(gè)。針對(duì)continuous pattern設(shè)計(jì)。,未來進(jìn)度,Tracing codeModifying codeSimulationPerformance,Tracing code,Environment configurationTrace codeConcentrate on “How to add Folding int

17、o JIT?”,Modifying code,Adding Folding to JITModulizing Folding and adding it into JIT between “IR generator” and “Code generator”,IR Generator,Code Generator,Bytecode,,,,,,Native code,Folding,Simulation,Run benchmark on

18、 ARM simulator on Linux workstationBenchmark : ”Embedded CaffeineMark”,Performance,Find out “Performance Speedup” after using foldingSpeedup=(time_with_folding)/(time_without_folding),Performance(cont.),EquationPo