Compilation: A RetrospectiveWhat You’ve Learned This SemesterAn Interface to High-Level LanguagesAn Interface to Computer ArchitecturesSimplified Compiler StructureBuilding a LexerHigh Level ViewLex: A Lexical Analyzer GeneratorPhases of a CompilerParsing – Syntax AnalysisContext-Free Grammar TerminologyShift-Reduce ParsingShift-Reduce Parsing TableParsing TableYacc / BisonParsing - Semantic AnalysisSymbol Table ImplementationTypical Semantic ErrorsStack FramesSlide 20Intermediate Code GenerationSlide 22Analysis and TransformationData-Flow AnalysisStatic Single Assignment FormOptimizationsSlide 27Scope of OptimizationSlide 29Instruction TilingRegister AllocationInstruction SchedulingModern Topics!Alternatives to the Traditional ModelJust-in-Time CompilationCompiling for the Core ArchitectureCompiling for GPUsSlide 37Slide 38Shader Compiler (SC)Power-Aware ComputingPower Issues in MicroprocessorsCode Optimizations for Low PowerCode Optimization of Parallel ProgramsThe Big PictureCompilation: A RetrospectiveCS 671April 29, 20082CS 671 – Spring 2008What You’ve Learned This SemesterWhat happens when you compile your codeTheory of compilers–Internal challenges and solutions: widely-used algorithms–Available tools and their other applications–Traditional and modern challengesCompilerHigh-Level Programming LanguagesMachine CodeError Messages3CS 671 – Spring 2008An Interface to High-Level LanguagesProgrammers write in high-level languages•Increases productivity•Easier to maintain/debug•More portableHLLs also protect the programmer from low-level details•Registers and caches – the register keyword•Instruction selection•Instruction-level parallelismThe catch: HLLs are less efficientCompilerHigh-Level Programming LanguagesMachine Code4CS 671 – Spring 2008An Interface to Computer ArchitecturesParallelism•Instruction level–multiple operations at once; minimize dependences•Processor level –multiple threads at once; minimize synchronizationMemory Hierarchies•Register allocation (only portion explicitly managed in SW)•Code and data layout (helps the hardware cache manager)Designs driven by how well compilers can leverage new features!CompilerHigh-Level Programming LanguagesMachine Code5CS 671 – Spring 2008Simplified Compiler StructureLexical AnalysisParsingIntermediate Code GenerationCode GenerationSource code(character stream)if (b==0) a = b;Assembly code(character stream)CMP CX, 0CMOVZ CX, DXToken streamAbstract syntax treeIntermediate codeFront EndBack EndMachine dependentMachine independentCode OptimizationIR6CS 671 – Spring 2008Building a LexerSpecification“if”“while”[a-zA-Z][a-zA-Z0-9]*[0-9][0-9]*()NFA for each REGiant NFAGiant DFA Table-driven code7CS 671 – Spring 2008High Level ViewRegular expressions = specificationFinite automata = implementationEvery regex has a FSA that recognizes its languageScannerScannerGeneratorsource codespecificationtokensDesign timeCompile time8CS 671 – Spring 2008Lex: A Lexical Analyzer Generator• Lex produces a C program from a lexical specification • http://www.epaperpress.com/lexandyacc/index.html%%DIGITS [0-9]+ALPHA [A-Za-z]CHARACTER {ALPHA}|_IDENTIFIER {ALPHA}({CHARACTER}|{DIGITS})* %%if {return IF; }{IDENTIFIER} {return ID; }{DIGITS} {return NUM; }([0-9]+”.”[0-9]*)|([0-9]*”.”[0-9]+) {return REAL; }. {error(); }9CS 671 – Spring 2008Phases of a CompilerLexical AnalysisParsingIntermediate Code GenerationCode GenerationSource code(character stream)if (b==0) a = b;Assembly code(character stream)CMP CX, 0CMOVZ CX, DXToken streamAbstract syntax treeIntermediate codeFront EndBack EndMachine dependentMachine independentCode OptimizationIR10CS 671 – Spring 2008Parsing – Syntax Analysis• Convert a linear structure – sequence of tokens – to a hierarchical tree-like structure – an AST• The parser imposes the syntax rules of the language• Work should be linear in the size of the input  type consistency cannot be checked in this phase•Deterministic context free languages for the basis• Bison and yacc allow a user to construct parsers from CFG specifications11CS 671 – Spring 2008Context-Free Grammar Terminology• Terminals–Token or ε• Non-terminals–Syntactic variables• Start symbol–A special nonterminal is designated (S)• Productions–Specify how non-terminals may be expanded to form strings–LHS: single non-terminal, RHS: string of terminals or non-terminals• Vertical bar is shorthand for multiple productionsS  (S) SS  ε12CS 671 – Spring 2008Shift-Reduce ParsingBottom-up parsing uses two kinds of actions: Shift and ReduceShift: Move I one place to the right•Shifts a terminal to the left stringE + (I int )  E + (int I )Reduce: Apply an inverse production at the right end of the left string•If E  E + ( E ) is a production, thenE + (E + ( E ) I )  E +(E I )13CS 671 – Spring 2008Shift-Reduce Parsing TableAction table1. shift and goto state n2. reduce using X → γ–pop symbols γ off stack–using state label of top (end) of stack, look up X in goto table and goto that state• DFA + stack = push-down automaton (PDA)next actionsnext state onreductionstateterminal symbols non-terminal symbols14CS 671 – Spring 2008Parsing Table( ) id , $ S L1 s3 s2 g42 S→id S→id S→id S→id S→id3 s3 s2 g7 g54 accept5 s6 s86 S→(L)S→(L)S→(L)S→(L)S→(L)7 L→S L→S L→S L→S L→S8 s3 s2 g99 L→L,SL→L,SL→L,SL→L,SL→L,S15CS 671 – Spring 2008Yacc / Bison•Yet Another Compiler Compiler•Automatically constructs an LALR(1) parsing table from a set of grammar rules•Yacc/Bison specification:parser declarations%%grammar rules%%auxiliary codebison –vd file.y-or-yacc –vd file.yy.tab.cy.tab.hy.outputfile.y16CS 671 – Spring 2008Parsing - Semantic Analysis• Calculates the program’s “meaning”• Rules of the language are checked (variable declaration, type checking)• Type checking also needed for code generation (code gen for a + b depends on the type of a and b)17CS 671 – Spring 2008Symbol Table ImplementationCan consist of:• a hash table for all names, and •a stack to keep track of scopey \x \xyxyxaa \xXScope change18CS 671 – Spring 2008Typical Semantic ErrorsTraverse the AST created by the parser to find:•Multiple declarations: a variable should be declared (in the same scope) at most once •Undeclared variable: a variable should not be used before being declared•Type mismatch: type of the