小型JIT编译器之最佳化技术评估

小型JIT編譯器之最佳化技術評估指導教授:單智君老師指導學長:喬偉豪學長組員:鍾懿軒，蔣季融，李國丞Outline觀察-----------------------------------鍾懿軒動機-----------------------------------鍾懿軒目標-----------------------------------鍾懿軒初步設計-----------------------------李國丞修改過的設計------------------------蔣季融未來進度-----------------------------蔣季融觀察Java是用stack運算。因為底層機器是register-based非stack-based，用interpreter執行，performance不佳。加入JIT將bytecode轉換為register-based的指令，可以增進performance。若於JIT中加入一些機制，增進其效能，則可進一步增進javaperformance。動機加入的機制若能產生IR，使JITcompiler後端處理更方便。就有可能增進JIT的速度。folding機制:讀入bytecode產生register-based的IR，簡便後段處理。因此決定於JIT中加入folding機制。目標將folding機制加入JIT中，以最少的overhead，fold最多的pattern，達到增加performance的目的。初步設計架構圖Bytecode分類Pattern統計遇到的問題舊架構圖舊folding架構圖Bytecode分類1.定義:參考kim’spaper(AdvancedPOCModel-BasedJavaInstructionFoldingMechanism)P:非operation含有push。Op:operation含有push不含pop。Oc:operation含有pop不含push。C:非operation含有pop。On:不含pushpop,無法分類者。Bytecode分類(續)參考學長的paper(stackoperationsfoldinginjavaprocessors)P:transferingdatafromConstantRegisterorLocalVariabletotheoperandstack。O:getsdatafromtheoperandstackandthenperformsdifferenttasksOe:ALUtypeoperatorthatwritestheresultbacktotheoperandstack。Ob:Branchtypeoperator。Oc:Complextypeoperatorincludingarrayaccess,constantpoolaccess。Ot:unableorhardtojointhefoldingoperation。C:consumesdatafromtheoperandstack,andstoresdatabackintothelocalvariable。Bytecode分類(續)2.統計bytecodepush/pop數:檢視kvmsourcecode(bytecodes.c):查看每道bytecode的執行碼中有多少push,pop的動作。檢視jvmspec(chapter6)每道bytecode都已規定好stack情況，可直接紀錄。AnalyzepatternspossibilityinJavaclassfileGetinformationfromJavaclassfileDoitourself(inC++)BCELlibraryforJava()Possibilityofpatterns(1)KIM所統計出的Patterns及出現百分比(2)自行統計”EmbeddedCaffeineMark”的結果ProblemsClassificationcansavetimeofstringmatchingUsing“Hashing”isbetterthanstringmatching!Benefitofclassificationnolongerexistswhenusing“Hashing”!使用stringmatchingsequentialsearch:Toomuchfindingoverhead。修改過的設計新架構圖Folding方法Structureof“JVMwithJIT”JavacodesourceJAVAcompilerJavabytecodeClassloaderBytecodeverifierHardwareOperatingSystemJavaclasslibrariesHotspotInterpretNativecodeJVMInterpreterJITYNInteractionbetweenInterpreter&JITTimeOnemethodHotspotDetectInterpretTimeComplicatedcodeJITEndofmethod(Startofmethod)CodeblockCodeblockStrutureofourJITJITIRgeneratorFoldingCodegeneratorIR1IR2NativecodeMethod方法(4-1)-OverviewO-oriented.SearchbytecodesforO-typebytecodethenfindfoldingpatternforthisO-typebytecode.Datastructure:array.Table:Usedforstoringinformationofbytecodes.方法(4-2)-DataStructureTable:usebytecodeIDnumberasindex.Buffer:length=4;Bytecodeinformation:TypeP_num:PushnumberPostive,stackgrowC_num:PopnumberNegative,stackfall方法(4-3)-Algorithm經由bytecode定義可得:P-type:C_num=0,P_num=1.C-type:P_num=0,C_num=1.O-type:不一定，視其功能而定。以O-type的attribute為尋找pattern的依據。P_num:向後尋找P_num個bytecodesC_num:向前尋找C_num個bytecodes方法(4-4)Match:向前找C_num個bytecodes的P_num剛好和O-type的C_num相抵銷。向後找P_num個bytecodes的C_num剛好和O-type的P_num相抵銷。整個pattern的attribute和要為零。無法match放棄此O-typebytecode，繼續找下一個。針對continuouspattern設計。未來進度TracingcodeModifyingcodeSimulationPerformanceTracingcodeEnvironmentconfigurationTracecodeConcentrateon“HowtoaddFoldingintoJIT?”ModifyingcodeAddingFoldingtoJITModulizingFoldingandaddingitintoJITbetween“IRgenerator”and“Codegenerator”IRGeneratorCodeGeneratorBytecodeNativecodeFoldingSimulationRunbenchmarkonARMsimulatoronLinuxworkstationBenchmark:”EmbeddedCaffeineMark”PerformanceFindout“PerformanceSpeedup”afterusingfoldingSpeedup=(time_with_folding)/(time_without_folding)Performance(cont.)EquationPositive:Make“CodeGenerator”workeasierandfasterNegative(Overhead):Timetosearch“FoldingGroup”inHotspots