Let’s look at a compiler
                                                                                                                                                                                                                                                     Compiler
                                       Advanced Compiler Design                                                                                                                                                     if (…) {
                                                                                                                                                                                                                     x := …;                                                           Code
                                                                                                                                                                                                                    } else {                         Optimizer
                                                                                                                                                                                                                           Parser                   Compiler                                  Exec
                                                                                                                                                                                                                     y := …;                                                            Gen
                                                                                                                                                                                                                    }
                                                                                      CSE 231                                                                                                                       …;
                                                                     Instructor: Sorin Lerner
                                    Let’s look at a compiler
                                                                                        CCoommppiilleerr                                                                                            Advanced Optimizer Design
                                                              PPaarrsseerr              Optimizer                        CoCoddee
                                                                                                                           GeGenn
                                                                                                                                                                                                                                                   CSE 231
                                                                                                                                                                                                                                  Instructor: Sorin Lerner
                                    What does an optimizer do?                                                                                                                                   What do these tools have in common?
                                                                                                                                                                                                 • Bug finders
                                                                                   Compiler                                                                                                      • Program verifiers
                                                         Parser                    Optimizer                         Code                                                                        • Code refactoring tools
                                                                                                                      Gen                                                                        • Garbage collectors
                                                                                                                                                                                                 • Runtime monitoring system
                                              1.Compute information about a program                                                                                                              • And… optimizers
                                              2.Use that information to perform program 
                                                   transformations 
                                                   (with the goal of improving some metric, e.g. performance)
                                                                                                                                                                                                                                                                                                                                                     1
         What do these tools have in common?
         • Bug finders
         • Program verifiers                      Program Analyses, Transformations,
         • Code refactoring tools                 and Applications
         • Garbage collectors
         • Runtime monitoring system                          CSE 231
                                                          Instructor: Sorin Lerner
         • And… optimizers
             They all analyze and transform programs
             We will learn about the techniques underlying all 
             these tools
         Course goals                             Course topics
         • Understand basic techniques            • Representing programs 
           – cornerstone of a variety of program analysis tools
           – useful no matter what your future path
                                                  • Analyzing and transforming programs
         • Get a feel for compiler research/implementation
                                                  • Applications of these techniques
           – useful if you don’t have a research area picked
           – also useful if you have a research area picked
         Course topics (more details)             Course topics (more details)
         • Representations                        • Analysis/Transformation Algorithms
           – Abstract Syntax Tree                  – Dataflow Analysis
           – Control Flow Graph                    – Interprocedural analysis 
           – Dataflow Graph                        – Pointer analysis
           – Static Single Assignment              – Rule-based analyses and transformations
           – Control Dependence Graph              – Constraint-based analysis
           – Program Dependence Graph
           – Call Graph
                                                                                       2
          Course topics (more details)                Course pre-requisites
          • Applications                              • No compilers background necessary
            – Scalar optimizations                    • No familiarity with lattices
            – Loop optimizations                        – I will review what is necessary in class
            – Object oriented optimizations
            – Program verification                    • Familiarity with functional/OO programming
            – Bug finding                               – Optimization techniques for these kinds of languages
                                                      • Standard ugrad cs curriculum likely enough
                                                        – Talk to me if you’re concerned
          Course work                                 Course project
          • In-class midterm (30%)                    • Goal of the project
          • Take-home final (30%)                       – Get some hands on experience with compilers
                                                         and/orGet a feel for what research is like in PL
          • Course project (35%)                      • Three kinds of projects:
          • Class readings (5%)                         – research-y: explore some interesting ideas and try 
                                                         them out
                                                        – implementation-y: pick some existing idea out there, 
                                                         and implement it 
                                                        – paper-y: read 10 good papers on a topic, and write a 
                                                         report summarizing and integrating
          Course project                              Readings
          • Groups of 3 (make groups by this Friday)  • Paper readings throughout the quarter
          • Pick something to advance your personal   • Seminal papers and state of the art
            enrichment goals                          • Will give you a feel for what research looks like
          • Eg: Pick something related to your research, 
            something that you want to learn about
          • Milestones
            – Project proposal (due end of week 2)
            – Mid-point status report (5 weeks in)
            – Final presentation/written report (end of quarter)
                                                                                               3
                  Administrative info                                                         Academic Integrity
                  • Class web page is up                                                      • Governed by Policy on Integrity of Scholarship 
                     – http://cseweb.ucsd.edu/classes/sp15/cse231-a/                            (http://senate.ucsd.edu/Operating-Procedures/Senate-
                                                                                                Manual/Appendices/2)
                     – (or Google “Sorin Lerner”, follow “Teaching Now”)                      • Allegations are handled by Academic Integrity 
                     – Will post lectures, readings, project info, etc.                         Office (https://students.ucsd.edu/academics/academic-integrity)
                  • Piazza link on web page                                                   • Course penalty for any cheating in 231 will be a 
                     – Use for questions, answers                                               failing grade for the entire class
                     – Especially LLVM/project Q&A                                            • Cheaters may be subject to additional 
                                                                                                administrative sanctions
                  Questions?                                                                  Program Analyzer Issues (discuss)
                                                                                                    Input            Program              Output
                                                                                                                     Analyzer
                  Program Analyzer Issues (discuss)                                           Program Analyzer Issues (discuss)
                        Input            Program              Output                                Input            Program              Output
                                         Analyzer                                                                    Analyzer
                                                                                                                                                                     4