Class Note for EECS 700 with Professor Kulkarni at KU 3
Class Note for EECS 700 with Professor Kulkarni at KU 3
Popular in Course
Popular in Department
This 20 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 22 views.
Reviews for Class Note for EECS 700 with Professor Kulkarni at KU 3
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Optimizing an ANSI C Interpreter with Superoperators By Todd A Proebsting University of Arizona Presented by Jonathan Lanning University of Kansas Introduction to the paper Translator Output Superoperator Optimization Translator Design Interpreter Generation Implementation Details Overview System Obstacles Experimental Results Limitations and Extensions Related Work Discussion Acknowledgements and References Conclusion Overview Cont d Introduction 0 This paper will describe the design and implementation of hti a hybrid translator interpreter system for ANSI C that has been targeted to both the MIPS R3000 KH92 and the SPARC Sun91 o hti will introduce superoperators a novel optimization technique for customizing interpreted code for space and time Superoperators automatically fold many atomic operations into a more efficient compound operation in a fashion similar to supercombinators in functional language implementations Translator Output o For example the tree for 23 would be ADD I CNSTI CNSTI where ADD I represents integer addition ADD I o For this VM the translation of 23 would be similar to the following byte 36 CNSTI word 2 immediate value byte 36 CNSTI word 3 immediate value byte 8 ADDI A prologue on the R3000 looks like the following 0 main li 24 192 put activation record size in 24 li 8 96 put location of evaluation stack in la 25 11 put location of bytecode in 25 jprologuescalar jump to interpreter Superoperator Optimization ADDP INDIRP x CNSTI is the most common 3 node IR pattern produced by lcc when it compiles itself The lcc IR has 109 operators 3 El 147 bytecodes for superoperators For example assume that the input trees with weights are n IAZ Y 10 AY Y 1 The original operators s frequencies of use are n Y 12 z 10 I 10 A 11 The frequencies of the parent child pairs are n IA 10 AZ 10 A Y 11 AY 1 The resulting trees are n IBZ 10 BY 1 The new frequencies of parent child pairs are n IB 10 BZ 10 BY 1 Translator Design Bytecode Emitter hti translates lCC S IR into bytecodes and attributes The optimal translation of an IR tree into bytecodes is automated Via tree pattern matching using burg Some sample patterns in the burg specification n stk ADDP INDIRP stk CNSTI 51 n stk ADDPstk stk 91 n stk CNSTI 36 1 a stk INDIRPstk 77 1 o Attribute Emitter hti must emit node attributes after appropriate bytecodes n ADDI MULI x CNSTI CNSTI becomes a reg CNSTI 1 emitsymbol P gtsyms o gtX name 4 4 Interpreter Generation The interpreter is implemented in assembly language The pattern matcher processes superoperator trees to determine how to best translate each into machine code The interpreter generator selects instructions and allocates temporary registers for each superoperator Machine emitter specifications are not limited to single operator patterns Complex IR tree patterns may better express the relationship between target machine instructions and lcc s IR Implementation Details A target machine emitter specification lcc back end code to handle data layout calling conventions etc A library of interpreter routines for observing calling conventions Machine dependent interpreter generator routines Limitations of system software on both R3000 and SPARC systems System Obstacles Neither machine s assembler supports unaligned initialized data words or halfwords Experimental Results Comparisons were made for three programs a burg A 5oooline tree pattern matcher generator p ocessing a 136rule specification n hti The 13oooline translator and subject of this paper translating a 1117line C file a loop An empty for loop that executes 106 times Experimental Results REDDITCEEG Size Summary in bytea Benchmark Translator 1 I hti htiso cede code I interp l waste 1 ma a lute11p waster burg l 5657 61 92448 c1564 1 15395 72616 12388 13862 111 7 230160 3150411 1564 51858 2895113 11296 64299 loop 52 4554 4 41 600 6 Figure 2 R3000 Benchka Girdle Sizes SPARC coa ize Summary in bytes Benchmark Translator ace l hti htiso code E code I inter waste code inberp 1 waste 1 burg V 15248 39 847211 411511 135511 63992 11340 111862 1151 397 N 271136 292568 4080 41423 2548118 10512 37507 loop 80 56 10311 2 18 312 1 Figure 3 SPARC Benchmark Code Sizes Experimental Results R3000 Exe h nn Summary Benchmark Times in seconds 7 i 7 r Katina h 11cc 1 11125 htiso 5 htiflcc humane htifhtisn I burg quot 39 1155 1 14114 107 35 39 43 211 mi 2619 4283 2331 1 159 133 18 mapquot 153 4312 7 1383 1 quot282 3991 31 Figure 4 R3000 Benchmark Code Speeds SPARE Execution Summary Benchmark Timee in seconds WW 7 W Ratios i ace L hti l htiau htija39acc htisofacc htihtiso burg 178 1352 i317 11111 4 39 39 23 11317 439 5324 2873 133 15 7 211 loop 211051 93 all 3 Figure 5 SPARC Benchmark Cutie Speeds g Each additional superoperator contributes decreasing marginal returns Limitations and Extensions The C expression X y cannot be expressed as a single tree by lcc hti generates bytecode as data assembler directives and function prologues as assembly language instructions Related Work Supercombinators optimize combinator based functional language interpreters in a way similar to how superoperators optimize hti C interpreter Cint that like hti maintained C calling conventions in order to link with native code routines Saber C performs approximately 70 run time error checks g o For the MIPS R3000 and the SPARC each machine required fewer than 800 lines of machine specific code to be retargeted Discussion Superoperators make the interpreted code both smaller and faster Heuristics can automatically isolate beneficial superoperators from static or dynamic feedback information g Acknowledgements and References These are on the last page You should have read them already Introduction to the paper Translator Output Superoperator Optimization Translator Design Interpreter Generation Implementation Details Conclusion System Obstacles Experimental Results Limitations and Extensions Related Work Discussion Acknowledgements and References Conclusion Cont d g Questions
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'