Algorithmic Language Compilers
Algorithmic Language Compilers CS 553
Popular in Course
Popular in ComputerScienence
This 18 page Class Notes was uploaded by Betty Kertzmann on Monday September 21, 2015. The Class Notes belongs to CS 553 at Colorado State University taught by Michelle Strout in Fall. Since its upload, it has received 46 views. For similar materials see /class/210167/cs-553-colorado-state-university in ComputerScienence at Colorado State University.
Reviews for Algorithmic Language Compilers
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/21/15
CS553 Compiler Construction Instructor Michelle Strout mstroutcscolostateedu Computer Science Building 342 Of ce hours decide in class URL httpwwwcscolostateeducs553 28553 Lemm l lnrrnduuticn Plan for Today Introductions Motivation 7 Why study compilers Issues 7 Look at some sample program optimizations and assorted issues Administrivia 7 Course details 28553 Lemm l lnrrnduuticn Motivation What is a compiler 7 A translator that converts a source program into an target program What is an optimizing compiler 7 A translator that somehow improves the program Why study compilers 7 They are speci cally important Compilers provide a bridge between applications and architectures 7 They are generally important Compilers encapsulate techniques for reasoning about programs and their behavior 7 They are cool 977 First major computer application A C3553 Lcctnrr l Introdnc 39on Prelude Q Who wrote the rst compiler when and for what language A Admiral Grace Murray Hopper in 1952 Q What language did it compile A A70 similar to 37address code for the UNIVAC I at Eckert7 Mauchly Computer Corporation Q What other interesting things did Admiral Hopper accomplish A Helped develop COBOL for the UNIVAC A In 1969 awarded the rst ever Computer Science Man7of7the7 Year Award from the Data Processing Management Association A Rear Admiral in the Navy highest rank for a woman A In 1986 at 80 oldest active duty of cer in the US A In 1991 the National Medal of Technology rst woman to win Quote It39s easier to ask forgiveness than it is to get permission C3553 Lecture 1 Introduction 4 Traditional View of Compilers Compiling down 7 Translate highlevel language to machine code Highlevel programming languages 7 Increase programmer productivity 7 Improve program maintenance 7 Improve portability Lowlevel architectural details 7 Instruction set 7 Addressing modes 7 Pipelines 7 Registers cache and the rest of the memory hierarchy 7 Instructionlevel parallelism 47 l Ili nduelion Isn t Compilation A Solved Problem Optimization for scalar machines is a Applications keep changing PTOblem that was SOlVed ten years ago 7 Interactive realtime mobile David Kuck 1990 secure Machines keep changing Some apps always want more 7 New features present new problems 7 More precision egu MMX EPIC PTO llng 7 Simulate larger systems support mult1core 7 Changing costs lead to different concerns eg loads Goals keep Changing 7 Correctness 7 Runtime performance Languages keep changing 7 Code Size 7 Wacky ideas eg GOP and GC have gone mainstream 7 Compiletime performance 7 Power 7 Security CS Leann l Ili nduelion 6 Modern View of Compilers Analysis and translation are useful everywhere 7 Analysis and transformations can be performed at run time and link time not just at compile time 7 Optimization can be applied to OS as well as applications 7 Analysis can be used to improve security by nding bugs 7 Analysis can be used in software engineering 7 Program understanding reverse engineering refactoring 7 Debugging and testing 7 Increased interaction between hardware and compilers can improve performance 7 Bottom line 7 Analysis and transformation play essential roles in computer systems 7 Computation important gt understanding computation important 47 l Ili urnduelicm Some Exciting Current Research in PLDI Research PLDI 7 Programming language design and implementation 7 Premier conference for dissemination of compiler and programming languages research Parallel Programming Languages 7 Most common CC or Fortran 90 combined with MP1 andor OpenMP 7 How do you do data ow analysis for MP1 programs 7 Up and coming languages and programming models 7 DARPA HPCS languages Cray s Chapel IBM s X10 Sun s Fortress 7 PGAS languages like UPC and CoArray FORTRAN 7 CUDA and OpenCL for programming GPUs 7 Concurrent Collections Intel and Rice University collaboration 7 Alphaz for expressing programs as equations CSU project CS Lecture 1 Ili urnduelicm S Yes but can it help me get a job Summer internships in past 4 years 7 LLNL with ROSE compiler 2 7 Cray with Chapel group 7 NCAR looking at optimizing look up tables in Fortran 90 code 7 Intel working on handparallelization based on compiler feedback Check out compilerjobscom Government labs often looking for research programmers who know about compilers Remember all of those new languages being developed 1 Io urnduelicm 5 Types of Optimizations De nition 7 An optimization is a transformation that is expected to improve the program in some way often consists of analysis and transformation eg decreasing the running time or decreasing memory requirements Machineindependent optimizations 7 Eliminate redundant computation 7 Move computation to less frequently executed place 7 Specialize some general purpose code 7 Remove useless code CS Lemch l Io urnduelicm 10 Types of Optimizations cont Machinedependent optimizations 7 Replace costly operation with cheaper one 7 Replace sequence of operations with cheaper one 7 Hide latency 7 Improve locality 7 Exploit machine parallelism 7 Reduce power consumption Enabling transformations 7 Expose opportunities for other optimizations 7 Help structure optimizations 3353 Leann l lli ulilclicn 11 Sample Optimizations Arithmetic simpli cation 7 Constant folding eg X 82 X 4 7 Strength reduction eg Xy4 xyltlt2 Constant propagation 7eg X3 x 3 X 3 y4x y43 y7 Copy propagation fag Xz xz y 4X y 4z 3353 Leann l lli ulilclicn 11 Sample Optimizations cont Common subexpression elimination CSE ieg Xab tab y a b X t yt Dead unused assignment elimination ieg X 3 X HOt used this assignment is dead X 4 Dead unreachable code elimination this Statement is dead 7 eg if false true printf debugging quot I ntrkluclion CS 353 Lecan Sample Optimizations cont Loopinvariant code motion ieg for i 1 to 10 do I X3 X3 fori1tolOdo Induction variable elimination ieg for i 1 to 10 do for p ampa1 to ampa10 do ai ai 1 1 p1 Loopunrolling iegfori1tolodo f0ri1t010by2do ai ai 1 ai ai 1 ai1 ai1 1 I ntrkluclion CS 353 Lecan More examples Loop Permutation for Improved Locality Sample code Assume Fortran s Column Major Order array layout doj16 39doi15 doi15 gt doj16 Aji Aji1 Aji Aji1 enddo enddo enddo enddo i gt i gt J 1 2 3 4 5 jr1 7 13 19 25 6 7 8 9 10 2 8 14 20 26 11 12 13 14 15 3 9 15 21 27 16 17 18 19 20 4 10 16 22 28 39 21 22 23 24 25 V 5 11 17 23 29 26 27 28 28 30 6 12 18 24 30 poor cache locality good cache locality 3353 Lecnm Comp mg for Parallelism 3 Locality 15 More examples Parallelization Can we parallelize the following loops do i 1 100 1 Ai Ai1 enddo Yes do i 1100 1 2 3r 4 5 Ai Ai 11 enddo 1 23353 Lecnm Comp mg for Parallelism 3 Locality 15 Is an Optimization Worthwhile Criteria for evaluating optimizations 7 Safety does it preserve behavior 7 Pro tability does it actually improve the code 7 Opportunity is it widely applicable 7 Cost compilation time can it be practically performed 7 Cost complexity can it be practically implemented CS 353 Leann Scope of AnalysisOptimizations Peephole 7 Consider a small window of instructions 7 Usually machine speci c Local 7 Consider blocks of straight line code no control ow 7 Simple to analyze CS 353 Leann l l1 1ltilriiCTl 1 J Global intraprocedural 7 Consider entire procedures 7 Must consider branches loops merging of control ow 7 Use data ow analysis 7 Make simplifying assumptions at procedure calls Whole program interprocedural 7 Consider multiple procedures 7 Analysis even more complex calls returns 7 Hard with separate compilation Introduction IS Limits of Compiler Optimizations Fully Optimizing Compiler FOC 7 FOCP POpt 7 POpt is the smallest program with same IO behavior as P Observe 7 If program Q produces no output and never halts FOCQ L goto L Aha 7 We ve solved the halting problem Moral 7 Cannot build FOC 7 Can always build a better optimizing compiler full employment theorem for compiler writers CS 353 Leanin l lufrkhletion 1 9 Optimizations Don t Always Help Common Subexpression Elimination X a b t a b y a b X t Y t 2 adds 1 add 4 variables 5 variables 23353 Leanin l lufrkhletion 20 Optimizations Don t Always Help cont Fusion and Contraction for i 1 to n Ti Ai Bi for i 1 to n fori1ton tAiilBi Ci Di Ti CL Mi t t ts in a register so no loads or stores in this loop Huge win on most machines Degrades performance on machines with hardware managed stream buffers 8353 Lemm 1 Introduction A Optimizations Don t Always Help cont Backpatching In Java the address of foo is often not known until runtime due to dynamic class loading so the method call requires a table lookup ofoo After the rst execution of this statement backpatching replaces the table lookup with a direct call to the proper function Q How could this optimization ever hurt A The Pentium 4 has a trace cache when any instruction is modi ed the entire trace cache has to be ushed 8353 Lemm 1 Introduction I Phase Ordering Problem In what order should optimizations be performed Simple dependences 7 One optimization creates opportunity for another eg copy propagation and dead code elimination Cyclic dependences 7 eg constant folding and constant propagation Adverse interactions 7 eg common subeXpression elimination and register allocation eg register allocation and instruction scheduling CS Lemch l Ili urndueticm Engineering Issues Building a compiler is an engineering activity Balance multiple goals 7 Bene t for typical programs 7 Complexity of implementation 7 Compilation speed Overall Goal 7 Identify a small set of general analyses and optimization 7 Easier said than done just one more CS Lemch l Ili urndueticm 77 Beyond Optimization Security and Correctness 7 Can we check whether pointers and addresses are valid 7 Can we detect when untrusted code accesses a sensitive part of a system 7 Can we detect whether locks are used properly 7 Can we use compilers to certify that code is correct 7 Can we use compilers to obfuscate code 23353 Lemur l lli ulilelicn 25 Administrative Matters Turn to your syllabus Discuss PAO and PA1 3353 Lemur l lli ulilelicn 26 Expectations DO 7 Expect to spend more time on this course than on a challenging undergraduate course 7 Write more than one draft for your project reports Spelling mistakes will be penalized Correct grammar is also eXpected for help use Word or even better the Writing Center 7 Make decisions when the project is underspeci ed Describe the reasoning for your decisions in the project report 7 Read assigned reading Much of it will take more than two readings and anything in the readings might be on the midterm or nal 7 Implement your projects in small pieces thus making them easier to debug 7 Use a debugger BEFORE coming to me about problems in your implementation 7 Ask questions and come to of ce hours sooner rather than later Thinking is important and should be done frequently CS Leann l GE39KlUQllC r Next Time Reading 7 Chapters 1 and 2 in purple dragon book Projects 7 Take a look at project 0 no turn in required 7 Find a partner for project 1 and get started Lecture 7 Undergrad compiler review CS Leann l GE39KlUQllC ZS Concepts Language implementation is interesting Optimal in name only Optimization scope 7 Peephole local global whole program Example Program Optimizations 7 Arithmetic simpli cation constant folding strength reduction 7 Constantcopy propagation 7 Common subeXpression elimination 7 Dead assignmentcode elimination 7 Loopinvariant code motion 7 Induction variable elimination 7 Loop unrolling permutation and parallelization Phase ordering problem 4 l imndudicm 2 Tiling A Data Locality Optimizing Algorithm Announcements 7 Wednesday doing class surveys Last Week 7 Kelly amp High transformation framework 7 Loop fusion and fission Today 7 Unroll and Jam and Tiling 7 Review of the paper A Data Locality Optimizing Algorithm by Michael E Wolf and Monica S Lam Loop Unrolling Motivation 7 Reduces loop overhead 7 Improves effectiveness of other transformations 7 Code scheduling 7 SE The Transformation 7Make n copies ofthe loop n is the unrolling factor 7Adjust loop bounds accordingly J39ilmg Letmr Trim Loop Unrolling cont Example do i1n do i1n by 2 Ai 31 Ci Ai 51 Ci enddo Ai1 Bi1 Ci1 enddo Details 7 When is loop unrolling legal 7 Handle end cases with a cloned copy ofthe loop 7 Enter this special case ifthe remaining number of iteration is less than the unrolling factor mm mm Loop Balance Problem 7 We d like to produce loops with the right balance ofmemory operations and oating point operations 7 The ideal balance is machinedependent 7eg How many loadstore units are connected to the L1 cache 7eg How many functional units are provided Example 10 j 1 r 2quot 7The inner loop has 1 memory do i 1 operation per iteration and 1 oating A j A j 51 point operation per iteration enddo ur target machine can only enddo support 1 memory opera n f this loop will be memory boun What can we do 3 mm J39ilmg Unroll and Jam Idea 7 Lime pct itclatiuu Unroll and Jam 7 Unroll the outer loop some number of times 7 Fuse Jam the resulting inner loops Example Unr 011 the Outer Loop doj12n doj12n by2 doi1m doi1m Aj Aj 31 Afl Afl 31 enddo enddo enddo do i m Aj1 Aj1 51 Unroll and Jam Example cont Unroll the Outer Loop do j 12n by 2 do i 111 Aj Afl 31 enddo do i 111 Aj1 Aj1 51 enddo enddo Jam the inner loops 7 The inner loop has 1 load per do j 12n by 2 iteration and 2 oating point do i 11 op erations p er iteration Aj Afl 31 7 We reuse the loaded Value ofBi Aj1 Aj1 51 7 The Loop Balance matches the em machine balance enddo 1 Lecmr mmg 39 enddo enddo 13le Lemur Tum b Unroll and Jam cont legality 7 When is Unroll and Jam legal Disadvantages 7 What limits the degree of unrolling 3955 mrm mm Unroll and Jam IS Tiling followed by inner loop unrolling OriginalLoop I O I O O I do j 12n do i 1 Aj Aj 31 I enddo J Q j Alter Unroll and Jam o 39j 12n by 2 j 339 339 d i 1quot Aj AjBi 2 Dim dd Aj1 Aj151 enddo enddo mmg C oncepts Unroll and Jam is the same as Tiling with the inner loop unrolled Tiling can improve 7 loop balance 7 spatial locality ality 7 data loc vim1mer Tm Next Time Student Surveys Lecture 7 Beyond Optimization mug