12CS 536 Spring 2007©Teaching AssistantMatt Renzelmann1306 Computer SciencesTelephone: 262-6601E-mail: [email protected] Hours:10:50 - 11:40, Mondays,Wednesdays & Fridays,12:30 - 1:00, Mondays &Wednesdays ,or by appointment13CS 536 Spring 2007©History of CompilersThe term compiler was coinedin the early 1950s by GraceMurray Hopper. Translation wasviewed as the “compilation” ofa sequence of machine-language subprograms selectedfrom a library.One of the first real compilerswas the FORTRAN compiler ofthe late 1950s. It allowed aprogrammer to use a problem-oriented source language.14CS 536 Spring 2007©Ambitious “optimizations” wereused to produce efficientmachine code, which was vitalfor early computers with quitelimited capabilities.Efficient use of machineresources is still an essentialrequirement for moderncompilers.15CS 536 Spring 2007©Compilers EnableProgramming LanguagesProgramming languages areused for much more than“ordinary” computation.• TeX and LaTeX use compilers totranslate text and formattingcommands into intricate typesettingcommands.• Postscript, generated by text-formatters like LaTeX, Word, andFrameMaker, is really a programminglanguage. It is translated andexecuted by laser printers anddocument previewers to produce areadable form of a document. Astandardized documentrepresentation language allows16CS 536 Spring 2007©documents to be freely interchanged,independent of how they werecreated and how they will be viewed.• Mathmatica is an interactive systemthat intermixes programming withmathematics; it is possible to solveintricate problems in both symbolicand numeric form. This system reliesheavily on compiler techniques tohandle the specification, internalrepresentation, and solution ofproblems.• Verilog and VHDL support thecreation of VLSI circuits. A siliconcompiler specifies the layout andcomposition of a VLSI circuit mask,using standard cell designs. Just as anordinary compiler understands andenforces programming language17CS 536 Spring 2007©rules, a silicon compiler understandsand enforces the design rules thatdictate the feasibility of a givencircuit.• Interactive tools often need aprogramming language to supportautomatic analysis and modificationof an artifact.How do you automatically filter orchange a MS Word document? Youneed a text-based specification thatcan be processed, like a program, tocheck validity or produce an updatedversion.18CS 536 Spring 2007©When do We Run a Compiler?• Prior to executionThis is standard. We compile aprogram once, then use it repeatedly.• At the start of each executionWe can incorporate values known atthe start of the run to improveperformance.A program may be partially complied,then completed with values set atexecution-time.• During executionUnused code need not be compiled.Active or “hot” portions of a programmay be specially optimized.• After executionWe can profile a program, looking forheavily used routines, which can bespecially optimized for later runs.19CS 536 Spring 2007©What do Compilers Produce?Pure Machine CodeCompilers may generate codefor a particular machine, notassuming any operating systemor library routines. This is “purecode” because it includesnothing beyond the instructionset. This form is rare; it issometimes used with systemimplementation languages, thatdefine operating systems orembedded applications (like aprogrammable controller). Purecode can execute on barehardware without dependenceon any other software.20CS 536 Spring 2007©Augmented Machine CodeCommonly, compilers generatecode for a machine architectureaugmented with operatingsystem routines and run-timelanguage support routines.To use such a program, aparticular operating systemmust be used and a collectionof run-time support routines(I/O, storage allocation,mathematical functions, etc.)must be available. Thecombination of machineinstruction and OS and run-timeroutines define a virtualmachine—a computer thatexists only as a hardware/software combination.21CS 536 Spring 2007©Virtual Machine CodeGenerated code can consistentirely of virtual instructions(no native code at all). Thisallows code to run on a varietyof computers.Java, with its JVM (Java VirtualMachine) is a great example ofthis approach.If the virtual machine is keptsimple and clean, its interpretercan be easy to write. Machineinterpretation slows executionby a factor of 3:1 to perhaps10:1 over compiled code.A “Just in Time” (JIT) compilercan translate “hot” portions ofvirtual code into native code tospeed execution.22CS 536 Spring 2007©Advantages of VirtualInstructionsVirtual instructions serve avariety of purposes.• They simplify a compiler by providingsuitable primitives (such as methodcalls, string manipulation, and so on).• They contribute to compilertransportability.• They may decrease in the size ofgenerated code since instructions aredesigned to match a particularprogramming language (for example,JVM code for Java).23CS 536 Spring 2007©Almost all compilers, to agreater or lesser extent,generate code for a virtualmachine, some of whoseoperations must be interpreted.24CS 536 Spring 2007©Formats of TranslatedProgramsCompilers differ in the formatof the target code theygenerate. Target formats maybe categorized as assemblylanguage, relocatable binary,or memory-image.• Assembly Language (Symbolic)FormatA text file containing assemblersource code is produced. Anumber of code generationdecisions (jump targets, longvs. short address forms, and soon) can be left for theassembler. This approach isgood for instructional projects.25CS 536 Spring 2007©Generating assembler codesupports cross-compilation(running a compiler on onecomputer, while its target is asecond computer). Generatingassembly language alsosimplifies debugging andunderstanding a compiler(since you can see thegenerated code).C rather than a specificassembly language cangenerated, using C as a“universal assembly language.”26CS 536 Spring 2007©C is far more machine-independent than anyparticular assembly language.However, some aspects of aprogram (such as the run-timerepresentations of program anddata) are inaccessible using Ccode, but readily accessible inassembly language.27CS 536 Spring 2007©• Relocatable Binary FormatTarget code may be generatedin a binary format withexternal references and localinstruction and data addressesare not yet bound. Instead,addresses are assigned relativeto the beginning of the moduleor relative