Compilers_lec01 (УМК ВМК)

CMSC 430Introduction to CompilersChau-Wen TsengThese slides are based on slides copyrighted by Keith Cooper,Linda Torczon & Ken Kennedy at Rice University, withmodifications by Uli Kremer at Rutgers University, andadditions from Jeff Foster & Chau-Wen Tseng at UMDCMSC 430 — a.k.a. Compilers• Catalog Description→Introduction to compilers. Topics include lexical analysis, parsing,intermediate representations, program analysis, optimization,and code generation.• Course Objectives→CMSC 430At the end of the course, you should be able to Understand the design and implementation of existinglanguages Design and implement a small programming language Extend an existing languageLecture 121Basis for Grading• Tests2-3 Midterms→ Final36%24%→• ProjectsScanner / ParserType Checker & AST→ Code Generator→ Byte Code Analyzer10%10%10%10%→→Notice: This grading scheme is tentative and subject to change.CMSC 430Lecture 13Basis for Grading• TestsClosed-notes, closed-bookFinal is cumulative• Practice problemsReinforce concepts, provide practice• ProjectsCumulativeDon’t fall behind!Midterms→ Final→CMSC 430Lecture 142Syllabus••••••••Regular Languages, ScanningContext-free Languages, ParsingSyntax-directed TranslationIntermediate RepresentationsCode GenerationCode OptimizationDataflow AnalysisAdvanced Code Generation→→Register AllocationInstruction Scheduling• Advanced Optimizations→→ParallelismData LocalityCMSC 430Lecture 15Recommended Textbook• Engineering A Compiler→CMSC 430Keith Cooper & Linda TorczonLecture 163Class-taking technique for CMSC 430• I will use slides extensively→I will moderate my speed, you sometimes need to say “STOP”• Please ask lots of questions→Course will be more productive (and enjoyable) for both you and me• You should read books for details→→Not all material will be covered in classBook complements the lectures• Use the resources provided to youSee me in office hours if you have questions→ Post questions regarding projects on Piazza→CMSC 430Lecture 17Compilers• What is a compiler?A program that translates an executable program in onelanguage into an executable program in another language→ A good compiler should improve the program, in some way→• What is an interpreter?→A program that reads an executable program and produces theresults of executing that program• C is typically compiled, Ruby is typically interpreted• Java is compiled to bytecodes (code for the Java VM)Which are then interpreted→ Or a hybrid strategy is used Just-in-time compilation Dynamic optimization (hot paths)→CMSC 430Lecture 184Why Study Compilation?• Compilers are important system software components→They are intimately interconnected with architecture, systems,programming methodology, and language design• Compilers include many applications of theory to practice→Scanning, parsing, static analysis, instruction selection• Many practical applications have embedded languages→Commands, macros, …• Many applications have input formats that look likelanguages,→Matlab, Mathematica• Writing a compiler exposes practical algorithmic &engineering issues→Approximating hard problems; efficiency & scalabilityCMSC 430Lecture 19Intrinsic interest Compiler construction involves ideas from many differentparts of computer scienceArtificial intelligenceAlgorithmsTheorySystemsArchitectureCMSC 430Greedy algorithmsHeuristic search techniquesGraph algorithms, union-findDynamic programmingDFAs & PDAs, pattern matchingFixed-point algorithmsAllocation & naming,Synchronization, localityPipeline & hierarchy managementInstruction set useLecture 1105Intrinsic merit Compiler construction poses challenging and interestingproblems:→Compilers must do a lot but also run fast→Compilers have primary responsibility for run-time performance→→Compilers are responsible for making it acceptable to use thefull power of the programming languageComputer architects perpetually create new challenges for thecompiler by building more complex machines→Compilers must hide that complexity from the programmer→Success requires mastery of complex interactionsCMSC 430Lecture 111Early Compilers – Making Languages UsableIt was our belief that if FORTRAN, during its first months, wereto translate any reasonable “scientific” source program into anobject program only half as fast as its hand-coded counterpart,then acceptance of our system would be in serious danger...

Ibelieve that had we failed to produce efficient programs, thewidespread use of languages like FORTRAN would have beenseriously delayed.— John BackusCMSC 430Lecture 1126Current Compilers – Improving Language UsabilityToday's programming languages give programmers unprecedentedpower and flexibility, and yet sometimes they are still not enough.There are many occasions when it is possible to encode the solutionto a programming problem in an existing language, but at the cost ofsignificant effort, loss of elegance and clarity, and reducedmaintainability. In these cases, often the best way to solve a problemis to develop a new language that makes the solution easy toexpress correctly, succinctly, and maintainably. Examples of suchlanguages range from "little" ones like Make, XML, JSON, YAML,Wiki, bash, Windows .ini files, autoconf, etc., to "big" ones like Perl,Python, Ruby, PHP, JavaScript, R, MATLAB, etc.

All of theselanguages were invented because existing languages just weren'tgood enough, and in the course of your career, you also may findyourself needing to invent a new programming language!— Jeff FosterCMSC 43013Lecture 1High-level View of a CompilerSourcecodeMachinecodeCompilerErrorsImplications• Must recognize legal (and illegal) programs• Must generate correct code• Must manage storage of all variables (and code)• Must agree with OS & linker on format for object codeBig step up from assembly language—use higher level notationsCMSC 430Lecture 1147Traditional Two-pass CompilerSourcecodeFrontEndIRBackEndMachinecodeErrorsImplications• Use an intermediate representation (IR)• Front end maps legal source code into IR• Back end maps IR into target machine code• Extension: multiple front ends & multiple passes (better code)Typically, front end is O(n) or O(n log n), while back end is NPCCMSC 43015Lecture 1A Common FallacyFortranFrontendSchemeFrontendJavaSmalltalkFrontendFrontendBackendTarget 1BackendTarget 2BackendTarget 3Can we build n x m compilers with n+m components?• Must encode all language specific knowledge in each front end• Must encode all features in a single IR• Must encode all target specific knowledge in each back endLimited success in systems with very low-level IRsCMSC 430Lecture 1168The Front EndSourcecodeScannertokensIRParserErrorsResponsibilities• Recognize legal (& illegal) programs• Report errors in a useful way• Produce IR & preliminary storage map• Shape the code for the back end• Much of front end construction can be automatedCMSC 43017Lecture 1The Front EndSourcecodeScannertokensParserIRErrorsScanner• Maps character stream into words—the basic unit of syntax• Produces pairs — a word & its part of speechx = x + y ; becomes <id,x> = <id,x> + <id,y> ;→ word ≅ lexeme, part of speech ≅ token type→ In casual speech, we call the pair a token• Typical tokens include number, identifier, +, –, new, while, if• Scanner eliminates white space(including comments)• Speed is importantCMSC 430Lecture 1189The Front EndSourcecodeScannertokensIRParserErrorsParser• Recognizes context-free syntax & reports errors• Guides context-sensitive (“semantic”) analysis (type checking)• Builds IR for source programHand-coded parsers are fairly easy to buildMost books advocate using automatic parser generatorsCMSC 43019Lecture 1The Front EndContext-free syntax is specified with a grammarSheepNoise → SheepNoise baa| baaThis grammar defines the set of noises that a sheep makesunder normal circumstancesIt is written in a variant of Backus–Naur Form (BNF)Formally, a grammar G = (S,N,T,P)• S is the start symbol• N is a set of non-terminal symbols• T is a set of terminal symbols or words• P is a set of productions or rewrite rulesCMSC 430Lecture 1(P : N → N ∪T )2010The Front EndContext-free syntax can be put to better use1.

goal → expr2. expr → expr op term3.| termS = goalT = { number, id, +, - }4. term → number5.| id6. op7.N = { goal, expr, term, op }P = { 1, 2, 3, 4, 5, 6, 7}→+| -• This grammar defines simple expressions with addition &•subtraction over “number” and “id”This grammar, like many, falls in a class called “context-freegrammars”, abbreviated CFGCMSC 430Lecture 121The Front EndGiven a CFG, we can derive sentences by repeated substitutionProduction Result125724635goalexprexpr op termexpr op yexpr - yexpr op term - yexpr op 2 - yexpr + 2 - yterm + 2 - yx+2-yTo recognize a valid sentence in some CFG, we reverse thisprocess and build up a parseCMSC 430Lecture 12211The Front EndA parse can be represented by a tree (parse tree or syntax tree)goalx + 2 - yexprexprexproptermterm+<number,2>opterm-<id,y>1.

goal → expr2. expr → expr op term3.| term<id,x>4. term → number5.| idThis contains a lot of unneededinformation.CMSC 4306. op → +7.| 23Lecture 1The Front EndCompilers often use an abstract syntax tree-+<id,x><id,y>The AST summarizes grammaticalstructure, without including detailabout the derivation<number,2>This is much more conciseASTs are one kind of intermediate representation (IR)CMSC 430Lecture 12412The Back EndIRInstructionSelectionIRRegisterAllocationIRInstructionSchedulingMachinecodeErrorsResponsibilities• Translate IR into target machine code• Choose instructions to implement each IR operation• Decide which value to keep in registers• Ensure conformance with system interfacesAutomation has been less successful in the back endCMSC 43025Lecture 1The Back EndIRInstructionSelectionIRRegisterAllocationIRInstructionSchedulingMachinecodeErrorsInstruction Selection• Produce fast, compact code• Take advantage of target features such as addressing modes• Usually viewed as a pattern matching problem→ad hoc methods, pattern matching, dynamic programmingThis was the problem of the future in 1978→→CMSC 430Spurred by transition from PDP-11 to VAX-11Orthogonality of RISC simplified this problemLecture 12613The Back EndIRInstructionSelectionIRRegisterAllocationIRInstructionSchedulingMachinecodeErrorsRegister Allocation••••Have each value in a register when it is usedManage a limited set of resourcesCan change instruction choices & insert LOADs & STOREsOptimal allocation is NP-Complete(1 or k registers)Typically, compilers approximate solutions to NP-CompleteproblemsCMSC 43027Lecture 1The Back EndIRInstructionSelectionIRRegisterAllocationIRInstructionSchedulingMachinecodeErrorsInstruction Scheduling• Avoid hardware stalls and interlocks• Use all functional units productively• Can increase lifetime of variables(changing the allocation)Optimal scheduling is NP-Complete in nearly all casesHeuristic techniques are well developedCMSC 430Lecture 12814Traditional Three-pass CompilerIRFrontEndSourceCodeMiddleEndIRBackEndMachinecodeErrorsCode Improvement (or Optimization)• Analyzes IR and rewrites (or transforms) IR• Primary goal is to reduce running time of the compiled code→May also improve space, power consumption, …• Must preserve “meaning” of the code→Measured by values of named variablesCMSC 43029Lecture 1The Optimizer (or Middle End)IROpt1IROpt2IROpt3IR...OptnIRErrorsModern optimizers are structured as a series of passesTypical Transformations• Discover & propagate some constant value• Move a computation to a less frequently executed place• Specialize some computation based on context• Discover a redundant computation & remove it• Remove useless or unreachable code• Encode an idiom in some particularly efficient formCMSC 430Lecture 13015Example Optimization of Subscript Expressions in FortranAddress(A(I,J)) = address(A(0,0)) + J * (column size) + IDoes the user realizea multiplication isgenerated here?DO I = 1, MA(I,J) = A(I,J) + CENDDOCMSC 43031Lecture 1Example Optimization of Subscript Expressions in FortranAddress(A(I,J)) = address(A(0,0)) + J * (column size) + IDoes the user realizea multiplication isgenerated here?compute addr(A(0,J)DO I = 1, Madd 1 to get addr(A(I,J))A(I,J) = A(I,J) + CENDDODO I = 1, MA(I,J) = A(I,J) + CENDDOCMSC 430Lecture 13216Modern Restructuring CompilerFrontEndSourceCodeHLASTRestructurerHLASTIRGenIROpt +BackEndMachinecodeErrorsTypical Restructuring (source-to-source) Transformations:• Blocking for memory hierarchy and register reuse• Vectorization• Parallelization• All based on dependence• Also full and partial inliningCMSC 430Lecture 133Role of the Run-time System• Memory management servicesAllocate In the heap or in an activation record (stack frame)→ Deallocate→ Collect garbage→• Run-time type checking• Error processing (exception handling)• Interface to the operating system→Input and output• Support of parallelismParallel thread initiation→ Communication and synchronization→CMSC 430Lecture 13417Classic Compilers1980: IBM’s PL.8 CompilerFront EndMiddle EndBack End• Many passes, one front end, several back ends• Collection of 10 or more passesRepeat some passes and analysesRepresent complex operations at 2 levelsBelow machine-level IRMulti-level IRhas becomecommon wisdomCMSC 430Dead code eliminationGlobal CSECode motionConstant foldingStrength reductionValue numberingDead store eliminationCode straighteningTrap eliminationAlgebraic reassociation35*Lecture 1Classic Compilers1986: HP’s PA-RISC CompilerFrontEndMiddle EndBack End• Several front ends, an optimizer, and a back end• Four fixed-order choices for optimization (9 passes)• Coloring allocator, instruction scheduler, peephole optimizerCMSC 430Lecture 13618Classic Compilers2000: The SGI Pro64 Compiler (now Open64 from Intel)FortranC & C++InterproceduralOptsLoopNestOptsGlobalOptsCodeGenJavaFront EndBack EndMiddle EndOpen source optimizing compiler for IA 64• 3 front ends, 1 back end• Five-levels of IR• Gradual lowering of abstraction levelCMSC 43037Lecture 1Classic Compilers2000: The SGI Pro64 Compiler (now Open64 from Intel)FortranC & C++InterproceduralOptsLoopNestOptsGlobalOptsCodeGenJavaFront EndBack EndMiddle EndOpen source optimizing compiler for IA 64Interprocedural• 3 front ends, 1 back end• Five-levels of IR• Gradual lowering of abstraction levelCMSC 430Lecture 1Classic analysisInlining (user & library code)Cloning (constants & locality)Dead function eliminationDead variable elimination3819Classic Compilers2000: The SGI Pro64 Compiler (now Open64 from Intel)FortranC & C++InterproceduralOptsLoopNestOptsGlobalOptsCodeGenJavaFront EndBack EndMiddle EndLoop Nest OptimizationDependence analysisParallelizationLoop transformations (fission,fusion, interchange, peeling,tiling, unroll & jam)Array privitizationOpen source optimizing compiler for IA 64• 3 front ends, 1 back end• Five-levels of IR• Gradual lowering of abstraction levelCMSC 43039Lecture 1Classic Compilers2000: The SGI Pro64 Compiler (now Open64 from Intel)FortranC & C++InterproceduralOptsLoopNestOptsGlobalOptsCodeGenJavaFront EndBack EndMiddle EndOpen source optimizing compiler for IA 64• 3 front ends, 1 back end• Five-levels of IR• Gradual lowering of abstraction levelCMSC 430Lecture 1Global OptimizationSSA-based analysis & opt’nConstant propagation, PRE,OSR+LFTR, DVNT, DCE(also used by other phases)4020Classic Compilers2000: The SGI Pro64 Compiler (now Open64 from Intel)FortranC & C++InterproceduralOptsLoopNestOptsGlobalOptsCodeGenJavaFront EndBack EndMiddle EndOpen source optimizing compiler for IA 64Code Generation• 3 front ends, 1 back end• Five-levels of IR• Gradual lowering of abstraction levelCMSC 430If conversion & predicationCode motionScheduling (inc.

sw pipelining)AllocationPeephole optimization41Lecture 1Classic CompilersEven a 2000 JIT fits the mold, albeit with fewer passesnative codebytecodeMiddle EndBack EndJava Environment• Front end tasks are handled elsewhere• Few (if any) optimizationsAvoid expensive analysisEmphasis on generating native codeCompilation must be profitableCMSC 430Lecture 14221.