Programming Lang & Compilers
Programming Lang & Compilers CS 5363
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 171 page Class Notes was uploaded by Mireya Heidenreich on Thursday October 29, 2015. The Class Notes belongs to CS 5363 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/231399/cs-5363-university-of-texas-at-san-antonio in ComputerScienence at University of Texas at San Antonio.
Reviews for Programming Lang & Compilers
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Make Utility Compile simple program hello c program include ltstdiohgt int mainO printf Hello worldn gcc helloc aout Hello World gcc o hello helloc Gcc Switches g output debugging information O 02 O3 activate optimization With different level gt activate only about releasing system gt detect memory bugs When activate it Wall issue Warnings When the compiler parses bad programming styles install your binary files to usrbin usrlocalbin or homedanbin set path export PATH PATHhomedanbin setenv PATH PATH homedanbin Make Utility Umx System Prugmmmmg Dan Lu DepanmmtquumputerSnmEE UTSA Page 1 Make Utility Umx System Prugzmmmg Dan Lu Department uf Computer Science UTSA Page 2 Program with many source les gcc o foo foolc fooZc foo3c foo4c compile every time gcc c foolc make an object le called foolo gcc c fooZc gcc c foo3c gcc c foo4c gcc o foo foolo fooZo foo3o foo4o link them together gt make some changes only in foolc gcc c foolc gcc o foo foolo fooZo foo3o foo4o no recompilation nm foolo list symbols in the object dynamic linking run time and namemangling link objects coming from different languages Building Libraries ar cru libfooa fool o fooZo foo3o foo4o ranlib libfooa gcc baro libfooa o foo invoke library gt equivalent to gcc baro fool o fooZo foo3o foo4o o foo install library to usrlocallib or usrlib using 1 ag gcc o foo baro lfoo gt must be named With the form liba gcc o bar baro Lhomedanlib lfoo L tells the library path for the libfooa Make Unlity Um th pr WWquot Danl UTSA Page Make uamy n u v UTSA Page4 Header Files Public and private headers include lttirnerhgt and include Inyheaderh Standard locations usrinclude or usrlocalinclude include ltunistdhgt nonstandard headers homedaninclude gcc c Ihornedaninclude barc gcc o bar baro Lhornedanlib lfoo gcc Ihornedaninclude barc o bar Lhornedanlib lfoo gcc I testc searching headers start from current directory Make Utility UmX System Pregmnrning Dan Le DepanmmtquumputerSnence UTSA Page 5 Header Files cont Avoid name con iction put headers into usrlocalincludefoo put one head fooh into usrlocalinclude gt contains fool h fooZh foo3h foo4h Header Files cont Avoid multiple inclusion destination Will be in usrlocalinclude or usrinclude ifndefidefmedifooih define idefmedifooih contents destination Will be in usrlocalincludedir or usrincludedir ifndefidefmedidirifooih define idefmedidirifooih contmts 1 mdif A matching header file for each source file Make Utility UmX System Prugzmmmg Dan Le Department of Computer Science UTSA Page a Run time Library Compile the hello program gcc c helloc gcc o hello helloo Something behind the scene libca gcc c helloc gcc o hello helloo lc Why Take a look at the object code nm helloo uuuuuuuu t gchicompiled A private function definition f n uuuuuuuu T main A unction definitio printf A used symbol but not defined in this fiie Make uamy Um W pr WWquot Dani UTSA F2ge7 Make Utility n n v UTSA Page a Run time Library c0nt 1nclude lt5tdiohgt 1nclude ltmathhgt lnt m in sqrua gcc 0 test testc lrn rnath library needs to be explicitly speci ed auto linkage libca int C libca and libstcha in CH explicitly libsocketa libnsla libgHa libxl la libUfora libpthreada Basic Makefile Concepts rebuild only the modified part ofa system make utility reads commands from Makefile a Makefile contains a list of rules Each rule has the format TARGET DEPENDENCES TAB COMMAND TAB COMMAND BLANKLINE TARGET a le name or an action phony target DEPENDENCY files or targets separated by spaces in a line Make Utility Umx System Prugmmmmg Dan Le DepanmmtquumputerSnence UTSA Page 9 Make Utility Umx System Prugzmmmg Dan Le Department uf Cumputer Science UTSA Page in Basic Make le Concepts c0nt build the dependencies build the target dependence first rebuild the file target if one of its dependencies is newer and generate the file do the action target Whenever it is invoked make will print a message if there is nothing to do actions as dependencies will always be taken Examples Makefile version 1 hello helloc helloh g c 70 hello helloc Makefile version 2 hello helloo gcc 70 hello helloo helloo helloc helloh gcc ec helloc Makefile version 3 hello helloo g c 70 hello helloo helloo helloc helloh gcc ec lloc Make Unlity Um th pr WWquot Dml UTSA Page Make Utility n quotv UTSA page 12 Examples cont clean rm e hello hell00 lnstall hello Cp hello u5rlocalblnhello more complicated example dependencies 001c includes gleep2h and gleep3h 002c includes gleep1h f003c includes gleep1h and gleep2h 004c includes gleep3h Make Uubty UmX System Prugmmmmg Dan Lu DepartmentquumputerSmence UTSA Page 13 00 0010 0020 0030 0040 gcc 70 00 0010 0020 0030 0040 0010 001c gleep2h gleep3h gc ec 001c 0020 002c gleep1h c ec 002c 0030 f003c gleep1h gleep2h gcc ec f003c 0040 004c gleep3h gcc ec 004c clean rm er 00 0010 0020 0030 0040 install mkdlr ep usrlocalbln rm er usrlocalblnfoo cp hello usrlocalblnfoo Remove Redundancy Makefile variables definition variable value usage variable Abstract rules su lsu 2 bulld tsurz from tsurl lt are the dependencies cause the need to rebuild a target is the target 3 are all the dependencies for the current rule 0 gcc ec slt bulld an object from a source ile Make Uubty UmX System Prugzmmmg Dan Lu Department uf Cumputer Science UTSA Page 14 Make uuiity Um W pr WWquot Dml UTSA Pagels Complete Example su ix s2 is an empty strlng gcc 3A 70 8 bulld the executable ile from objects SUFFIXES 51 52 5n list all sufflxes put them together c gcc CFLAGS Wall OBJECTS 0010 0020 0030 0040 PREFIX u5rlocal SUFFIXES C O c0 cc CE LAGS ec lt CC CFLAGS SA 0 8 Make mm n quotv UTSA Page is Machine Independent Code Optimizations Enabling optimizations Useless code elimination and redundant expression elimination 5555 63 Code optimization Source 1R 0 timizer iTarget program gt5idend W compiler El The goal of code optimization is to discover at compile time information about the runtime behavior of the program and to use that information to improve the code generated by the compiler I Speed up the runtime execution of compiled code I Reduce the size of compiled code I Correctness safety I Optimizations must preserve the meaning of the input computation El Profitability I Optimizations must improve code quality c55363 2 Applying optimizations a Most optimizations are separated into two phases I Program analysis discover opportunity and prove safety I Program transformation rewrite code to improve quality a A procedure may benefit from many optimizations I Every optimization acts as a filtering pass that translate one IR into another IR for further optimization n Compilers I Select a set of optimizations to implement I Decide orders of applying implemented optimizations u The safety of optimizations depends on results of program analysis a Optimizations often interact with each other and need to be combined in specific ways in Some optimizations may need to applied multiple times Eg dead code elimination redundancy elimination copy folding I Implement predetermined passes of optimizations c55363 3 Compiler transformations on scalar uniprooessor machines a Machine independent transformations I Enable other transformations in Inlining cloning loop unrolling I Eliminate useless and unreachable code a Dead code elimination I Eliminate redundancy a redundant expression elimination I Specialize computation in Constant propagation peephole optimization I Move operations to lessfrequently executed places a Loop invariant code motion a Machine dependent transformations I Take advantage of special hardware features a Instruction selection prefetching I Manage or hide latency introduce parallelism in Instruction scheduling prefetching I Manage bounded machine resources in Register allocation c55363 Loop unrolling n An enabling transformation to expose opportunities for other optimizations I Reduce the number of branches by a factor 4 l Provide bigger a basic block loop body for local optimziation n Better efficiency in instruction scheduling and register allocation doi 1to 100 by4 do i 1 to n by 1 am ai 30 ai ai W ai1 ai1 bi1 end ai2 ai2 bi2 ai3 ai3 bi3 end Original loop Unrolled by 4 n 100 c55363 Loop unrolling arbitrary n i 1 do i 1t0 n3 by 4 if modn2 gt 0 then ai ai bi it a W ai1 ai1 bi1 JJ1 ai2 ai2 bi2 39f Eggdjg gifba the Enadi3 ai3 bi3 aif1ai1bi1 do While i lt n dolili2to n by 4 1251a W ai ai bi end ai1 ai1 bi1 ai2 ai2 bi2 Unrolled by 4 arbitrary n ai3 ai3 bi3 end Unrolled by 4 arbitrary n c55363 UselessDead code elimination n Eliminate instructions whose results are never used void fooint b int C 1 mark all critical 39 t a d elf instructions as useful a b C 1 instructions that d b 39 Cr return values e b c perform inputoutput f b c or modify externally return e visible storage 2 mark all instructions that affect already marked instruction l Useless code a Instructions that a b C define operands of i d 39 b C or control the execution of i f b c c55363 UselessDead code elimination algorithm MarkPass M 339 WorkList o MarkPass for each operation i SweepPassO if i is critical then Sweeppasso mark i WorkList U i while WorkList I Q remove i from WorkList letibexyopz if defy is not marked then for each operation i if i is unmarked then if i is a branch then rewrite i with a jump to i s nearest marked mark defy WorkLiStUd8fY postdominator if defz is not marked then if i is not a jump then mark dEfZ WOFkLiStUdEfZ delete i for each branchj that controls execution of i Compute defvar data flow ifj is not marked then ana39ys39s or SSA markj WorkList U j Compute controli reverse dominance frontier analysis c55363 8 Example useless code elimination A a 5 nab if n lt 10 goto 1 3 pcd rcd 1 qarb rcd if qltr goto 2 A NL 2eb18 s u ea17 uef goto 3 ab ef E 3XeF Print X if xlt 1 goto 1 5 yab zrd return 2 c55363 a5 A nab if n lt 10 goto 1 C 1 qab B rcd pcd rcd if qltr goto 2 2eb18 sab uef ea17 uef goto 3 E 11 3 xeF Print x if xlt1 goto 1 5 yab zrd return 2 Eliminate useless control flow n Optimizations may introduction superfluous control flow eg SSA conversion that breaks CFG edges Br QM tr l J 1 Folding redundant branch 2 Removing an empty block Bi Bi Bi Bi l Bi l i g Bj g Bj B39 B 3 Combining blocks 4 Hoisting a branch Bj is empty C55363 10 Eliminating redundant expressnons Original code Rewritten code m2yz t02y n3YZ mt0z o2yz n3yz otOz El The second 2y computation is redundant El What about yz I 2yz 2y 2 not 2yz I 3yz 3y 2 not 3yz l Change associativity may change evaluation result a For integer operations optimization is sensitive to ordering of operands C55363 11 Pointer assignment What about n A pointer could point to anywhere I If p points to y then 2y is no longer redundant I All variables memory locations may be modified from modifying p n Pointer analysis I Reduce the set of variables associated with p C55363 12 Eliminating redundancy in basic blocks Value numbering 1 n Simulate the runtime evaluation of expressions I For every distinct runtime value create a unique integer number as compiletime handle I Use a hash table to map every expression e to a integer value number VNe I Represent the runtime value of expression VN e1 op e2 uniquemapopVNe1VNe2 u If an expression has a already defined value number I It is redundantly evaluated and can be removed c55363 alt3gt blt5gt clt6gt dlt5gt blt1gtclt2gt alt3gt dlt4gt blt5gtclt2gt alt3gt dlt4gt CL 3 CT 0 Eliminating redundancy in basic block Value numbering 2 for each expression e of the form result opd1 op opd2 1 Find value numbers for opdl and ode if VNopdl or VNopd2 is a constant or has a replacement variable replace opdlopd2 with the value 2 Construct a hash key for expression e from op VNopd 1 and VNopd2 3 if the hash key is already defined in hash table with a value number if result is a temporary then remove e else replace e with a copy record the value number for result else insert e into hash table with new value number record value number for result set replacement variable of value number Extensions When valuating a hash key k for expression e if operation can be simplified simplify the expression if op is commutative sort operands by their value numbers C55363 14 Example value numbering ADDRLOADI C 9 r9 INTLOADA i 9 r10 ADDRLOADI C 9 r9 INTLOADI 4 9 r11 INTLOADA i 9 r10 INTMULT r10 r11 9 r12 INTMULTI r10 4 9 r12 INTPLUS r9 r12 9 r13 INTPLUS r9 r12 9 r13 FLOATLOADI 00 9 r14 FLOATSTOREI 00 9 r13 FLOATSTORE r14 9 r13 OP opdl opd2 Valuenumber C 1 Valuenumber variable ALOADI r9 r9 i ILOADA i r10 r10 r12 The role of naming aXy bXy m2YZ a17 Yi3YZ cxY 392y39z 1 2 1 The expression xy is redundant but no longer available in a when being assigned to c I Keep track of available variables for each value number I Create new temporary variables for value numbers if necessary 2 The expression 2y is not redundant the two 2y evaluation have different value numbers C55363 16 Implementing value numbering n Implementing value numbers I Two types of value numbers n Compiletime integer constants in Integers representing unknown runtime values I Use a tag bit to tell which type of value number n Implementing hash table I Must uniquely map each expression to a value number a variable name value number n op VNl VN2 value number I Evaluating hash key a int hashconst char name a int hashint op int vnl int vn2 I Need to resolve hash conflicts if necessary a Keeping track of variables for value numbers I Every runtime value number resides in one or more variables I Replace redundant evaluations with saved variables C55363 17 Scope of optimization El El Local methods I Applicable only to basic blocks Superlocal methods I Operate on extended basic blocks EBB BlBZB3Bm where Bi is the single predecessor of Bi1 Regional methods I Operate beyond EBBs eg loops conditionals Global intraprocedural methods I Operate on entire procedure subroutine Wholeprogram interprocedural methods I Operate on entire program c55363 x V I I l 50 goto s1 z I I I I I 1 I I s1t1b2 a at1 gotosO EBBx Superlocal value numbering A mab nab pcd C qab rcd rcd A A eb18 ea17 D sab E tcd uef uef vab F wcd xef yab G zcd c55363 El Finding EBBs in control flow graph AB ACD ACE F G Expressions can be in multiple EBBs El Need to restore state of hash table at each block boundary Record and restore Use scoped value table I Weakness does not catch redundancy at block F El Algorithm ValueNumberEBBbtblVN PushBlocktbl VN ValueNumberingbtblVN for each child bi of b if b is the only parent of bi VaueNumberEBBbitblVN PopBlocktblVN 19 Dominator based value A moaobo The execution of C noaobo always precedes F B I Can we use value p0c0d0 C q0a0b0 theofClbrF r0C000 r1C0d0 Problem variables in C e0b818 e1o17 may be redefined in D D sOaObO E t0c0d0 OrE uOeOfO u1e1f0 SOIUt39On rename variables so that each e2 eoe1 variable is defined once F u2 u0u1 l SSA static single v0 a0b0 assmrwnent 3831 Similarly can use table 39 of A for optimizing G G r2 r6r1 yOaObO zOcOdO c55363 20 Global redundancy elimination a Value numbering cannot handle cycles in CFG I Makes a single pass over all basic blocks in predetermined order 2 El Global redundancy elimination z I Intra procedural methods a Handles arbitrarily shaped CFG I Based on expression syntax not value a The first and second yz considered identical expression despite different values a Consistent with DAG approach different from value number approach C55363 21 Global redundancy elimination 1 Collect all expressions in the code each expression given a unique M J temporary name AVE El Expressions in M m y gtllt 2 Q yz y z y y 2 Y2 2 At each CFG point p determine the o y 2 Y392 set of available expressions I An expression e is available at p if every CFG path leading to p contains a definition of e and no operand of e is modified after the definition 3At each CFG point replace redundant evaluation of available expressions with a copy of the temporary variables C55363 22 Computing available expressions n For each basic block n let I DEExprnexpressions evaluated by n and available at exit of n I ExerillneXpressions whose operands are modified by n killed by n Goal evaluate expressions available on entry to n I AvailnmEEJredll Exprm Availm Exerillm for each basic block bi compute DEExprbi and Exerillbi Availbi Q for changed true changed changed false for each basic block bi oldAvail Availbi AvailbiU DEExprm Availm Exerillm mEpredbi if Availbi oldAvail changed true C55363 23 Compute local sets for each basic block nSlSZS3Sk VarKiII Q DEExprn Q for i k to 1 suppose Si is x y op 2quot if y i VarKiII and z i VarKiII DEExprn DEExprn n y op z VarKiII VarKiII m X Exerin Q for each expression e in the procedure for each variable v E e if v E VarKiII then Exerin Exerin n e C55363 24 Example applying GRE A mab nab B p Cd C a3939b rcd rcd eb18 ea17 D sab E tcd aef def vab F w cd x ef y ab G zcd c55363 25 Instruction Selection 5555 63 Machine code generation Intermediate machine Code generator I 39 Code generator I Input intermediate code symbol tables I All variables have values that machines can directly manipulate I Each operation has at most two operands I Assume program is free of errors a Type checking has taken place type conversion done El Output I Absoluterelocatable machine assembly code I Architectures u RISC machines CISC processors stack machines El Issues I Instruction selection I Instruction scheduling I Register allocation and memory management c55363 Retargetable backend Instruction MaCh39ne Back end selector descri tion 9 generator pattern Matching engine Build retargetable compilers I Isolate machine dependent information I Compilers on different machines share a common IR 1 Can have common front and mid ends I Tablebased back ends share common algorithms El Tablebased instruction selector I Create a description of target machine use backend generator c55363 Variations on instruction selection IDaARP4 IDbARP8 IDaARP4 NUM2 Generated code Generated code loadI 4 gt r5 loadI 4 gt r5 loadAO Farp r5 gt r6 loadAO rarp r5 gt r6 Load18 gt r7 loadI 2 gt r7 loadAO rarp r7 gt r8 Mut r6 r7 gt r8 Mult r6 r8 gt r9 Desired code Desired code loadAI rarp 4 gt 5 IoadAI ram 4 gt r5 loadAI rarp 8 gt r6 muItI r5 2 gt r6 Mult r5 r6 Based on locations of operands different instructions may be selected c55363 4 Treepattern matching El Use a lowlevel AST to expose all the impl details I Define a collection of operation patterns I Define a code generation template for each pattern El Match each AST subtree with an operation pattern I Select instructions accordingly Example low level AST for w 6 x 2 y lt 3 arp 4 MA 2 Mx f arp 12 c55363 Rewrite rules through tree grammar El Use attributed grammar to define code generation rules Summarize structures of AST through contextfree grammar Each production defines a tree pattern in prefixnotation Each production is associated with a cost Each grammar symbol terminal or nonterminal has an attribute location of value production cost Code template Goal Assign Assign lt Regl RegZ Store r2 gt r1 Assign lt Regl RegZ Reg3 storeAO r3 gt r1 r2 Assign lt Regl num2 Reg3 storeAI r3 gt r1 n2 Reglab1 a relocatable symbol loadI lab1 gt rnew Regval1 value in reg eg rarp 0 1 1 1 Assign lt num1 RegZ Reg3 1 storeAI r3 gt r2 n1 1 0 1 00 J Ch Ln 4gt 00 RJ F4 Reg Num1 constant integer value loadI num1 gt rnew c55363 Example applying rewrite rules production cost Code template 9 Reg MRegl Load r1 gt rnew 10 Reg M Reg1RegZ loadAO r1 r2 gt rnew 11 Reg M Reg1Num2 loadAI r1 n2 gt rnew 12 Reg M Num1Reg2 loadAi r2 n1 gt rnew 13 Reg M Reg1 Lab2 loadAI r1 2 gt rnew 14 Reg M Lab1Reg2 loadAI r2 1 gt rnew 15 Reg Reg1Reg2 Sub r1 r2 gt rnew 16 Reg Reg1 Num2 subI r1 n2 gt rnew 17 Reg Reg1 Reg2 add r1 r2gt rnew 18 Reg Reg1 Num2 addI r1 n2 gt rnew 19 Reg Num1 Reg2 addI r2 n1 gt rnew 20 Reg Reg1 Lab2 addI r1 I2 gt rnew I lI lI lI lI ll ll ll lI lI lI lI ll l 21 Reg Lab1 Reg2 addI r2 1 gt rnew c55363 Tiling the AST n Given an AST and a collection of operation trees tiling the AST maps each AST subtree to an operation tree a A tiling is a collection of ltASTnode op treegt pairs each specifying the implementation for a AST node I Storage for result of each AST operation must be consistent across different operation trees lRegReg1Num2l LabG Num12 RegLab1 c55363 Finding a tiling n Bottom up walk of the AST for each node n l Labeln contains the set of all applicable tree patterns Tilen Labeln Q if n is a binary node then Tileleftn Tilerightn for each rule r that matches n s operation if leftr E Labelleftn ancl rightr E Labelrightn then Lablen Labeln U r else if n is a unary node then Tileleftn for each rule r that matches n s operation if leftr E Labelleftn then Labeln Labeln U r else n is a AST leaf Labeln all rules thatrmatch the operation in n JJJJ u Finding the lowcost matches a iihng can nclallthe n1atches Hithe pattern set I Multiple matches exist because grammar is ambiguous i To find the one with lowest cost must keep track of the costnteachrnatchedtran a on Example low level AST for w 6 x 2 y 45 26 loadAI rarp8gtr1 lt 174 subI r1 2gt r2 1 15 92 loadAI rarp12gtr3 39 162 M111 Add r2 r3 gt r4 70arp 811 92 2 his storeAI r4gtrarp 4 M 111 81 Jam v t 7r2 73539 81 20 3quot 881 39 C55363 10 Summary of tree matching approach El Need to select lowest cost instructions in bottom up traversal of AST I Need to determine lowest cost match for each storage class i Automatic tools I Hand coding of tree matching I Encode the tree matching problem as a finite automata I Use parsing techniques 1 Need to be extended to handle ambiguity I Use string matching techniques 1 Linearize the tree into a prefix string 1 Apply string pattern matching algorithms C55363 11 Peephole optimization El Use simple scheme to match IR to machine code I Efficiently discover local improvements by examining short sequences of adjacent operations StoreAI r1 gt rarp 8 storeAI r1 gt rarp 8 loadAI rarp8 gt r15 IZi r1 gt r15 addI r2 0 gt r7 Mult r4 r7 gt no i lMuit r4 r2 gt r10 jumpI gt L10 jumpI gt L11 L10 jumpI gt L11 L10 jumpI gt L11 C55363 12 Systematic peephole optimization IR Expander LLIR Simplifier LLIR Matcher eSM ASMgtLLIR LLIRgtLLIR LLIRgtASM n Expander I Rewrites each assemblK instruction to a sequence of lowlevel IRs that represent all t e direct effects of operation a Simplifier I Examine and improve LLIR operations in a small sliding window I Forward substitution algebraic simplification constant evaluation eliminating useless effects a Matcher I Match simplified LLIR against pattern library for instructions that best captures the LLIR effects C55363 13 Peephole optimization example mult 2 y gt t1 sub x t1 gt w lexpand r10 2 r11 G r12 12 r13 r11 r12 r14 Mr13 r15 r10 r14 r16 16 r17 rarp r16 r18 Mr17 r19 Mr18 r20 r19 r15 r21 4 r22 rarp r21 Mr22 r20 Optimizations r1 n1 r1r2n1 r1r2n1 r2 r3 r1 r3Mr1 Mr1r3 1 R2r3n1 r3Mr2n1 Mr2n1r3 r10 2 load12 gt r10 r11 G loadI G gt r11 r14 Mr1112 loadAI r11 12gtr14 r15 r10 r14 Mult r10 r14 gt r15 r18 Mrarp 16 loadAI rarp 16gtr18 r19 Mr18 Load r18 gt r19 r20 r19 r15 Sub r19 r15 gt r20 Mrarp4 r20 storeAI r20 gt rarp 4 Simplify c55363 Match Week 8 Scope Rules Rule 1 All constants types variables and procedures de ned in the same block must have different names Example const X 10 var X y integer X is rede ned The part of a block where a de ned object can be referenced is called the scope of the object Generally an object is known from its de nition to the end of the block If recursive procedure calls are permitted the scope should be eXtended to the beginning of an object s de nition Rule 2 A constant type or variable de ned in a block is normally known from the end of its de nition to the end of the block A procedure de ned in a block B is normally known from the beginning of the procedure block to the end of the block B Rule 3 Given a block Q that de nes an object X If Q contains a block R that de nes another object name X the rst object is unknown in the scope of the second object The process to nd a de nition for a name is called a binding Binding a name is preceded in the same block by a de nition of an object the name X refers to that object otherwise the name is searched from the smallest block containing the previous block If no such de nition is found the name is unde ned Stack name de nitions and record levels For eXample standard block Program P type T array 1100 of integer var X procedure Q X integer const c l3 begin X end OOONONUIAUJNt IO procedure R 10 var b c Boolean ll beginXend l3 begin end CS 5363 Programming Languages and Compilers Appendix 1 The difference of procedures and functions is that a function returns a value to its caller whereas a procedure does not The rationale behind procedures and functions is the divideandconquer principle A big problem can be decomposed into several smaller problems each of which can be easily solved Each smaller problem can be implemented through procedures or functions and can be compiled and tested separately Other than that procedures share same properties as functions Name Space A procedure has anisolated protected name space ie it has its own variables labels etc Calling conventionsequence de nes mapping arguments from caller s name space to callee s External Interface of procedures define rules for addressability name scoping activation records etc This allows user library development The stack mechanism is used to handle call and return behavior Recursion can be handled as well Example compute 5 factorial fact 5 de ne fact k cond lt k 1 1 else fact subl k k fact 5 calls fact 4 fact 4 calls fact 3 fact 3 calls fact 2 fact 2 calls fact 1 fact 1 returrs l fact 2 returns 2 fact 3 returns 6 fact 4 returns 24 fact 5 retums 120 Some language such as Scheme allows a procedure to retum a procedure and its runtime context called a closure To preserve memory used by a called procedure some other data structure may be used Most traditional programming languages inherit many conventions and rules de ned in Algol 60 Lexical scoping is one of them In a given scope each name refers to its lexically closest declaration If s is used in the current scope it refers to the s declared in the current scope if one exists If not it refers to the declaration of s that occurs in the closest enclosing scope The outermost scope contains global variables The static coordinate is used to reference each name in lexical scoping languages The static coordinate is a pair ltlevel 0 setgt where level the lexical nesting level from the symbol table and o set is the offset of its memory location in the data area for the scope Dynamic scoping on the other hand is similar to lexical scoping but a free variable variable not de ned in the current scope is bound to the declaration in the closest activation record Scoping rules Fortran creates two scopes 1 global scope that holds procedure names and commonblock names 2 local scope one per procedure C creates a global scope to hold all procedures names and global variables Each procedure has its own local scope Procedures can not next inside one another Pascal can but a procedure can contain a block use curly braces can be nested that creates a separate local scope C introduces a lewide scope Static procedures defined in a file are visible to any procedure in the le only Java has a limited global name space the only global names are those of classes declared public Each class resides in a package Fields and methods can be accessed in other classes by declaring them as public in a public class Fields and methods are accessible to methods in all other classes in the same package A procedure s activation record AR holds its local data and state information An AR typically contains actual parameters context static link dynamic link and return address and local data Global variables are usually stored outside all ARs The compiler uses the initialization features commonly found in loaders Local variables must be initialized at run time The set of registers used by a caller must be saved during a procedure call Whoever saves the registers they are stored in its AR If a procedure outlives its caller or a procedure returns an object such as a closure ARs can be kept in heap E g Scheme and ML use heap allocated ARs A garbage collector is used to deallocate objects when they become unreachable Saving Registers Some register values that a caller expects to survive across the call must be saved into memory The caller knows precisely which values are live across the call It might preserve fewer registers than the callee This convention is called caller saves A callee can perform this task because it knows precisely which registers it will use and le some values remain untouched in their registers This is called callee saves Typically long lived values are put in calleesaves registers where they will be stored only if the callee actually needs the register and short lived values are put in callersaves registers where it may avoid saving them at a call Memory Allocation In recent research the studies have shown that object oriented applications written in C can run up to 10 times slower than comparable C programs This emcution time overhead can largely be contributed to inef cient heap management algorithms Since objectoriented applications tend to be more memory intensive than procedural languages ability to effectively manage heap is crucial to the performances of such systems In software approaches the dynamic memory management execution time is linearly proportional to the number of objects existing in the system For example as the calls to malloc intersperse with the calls to delete the heap becomes increasingly fragmented and the occupied list and free list become longer as well Again longer lists usually translate to longer search time Some of the most commonly used dynamic memory allocation schemes are sequential fits e g first fit and best t segregated fits buddy systems and bitmapped fits While these schemes have their own advantages and disadvantages they share one common trait that is they are used for variablesize allocations and they yield nondeterministic turnaround time In rst t approach the list is searched from the beginning The free block that is large enough to satisfy the request is then selected If the block is larger than necessary it is split and the remainder is put back on the free list The major problem with rst t is that the larger blocks at the beginning of the list are often split first Since these blocks are often larger than the requested size the remaining portions are put back on the list If the splitting occurs frequently the beginning of the list may have many small unusable blocks Therefore the search time may increase since the search must go past them each time a larger block is requested In best fit the list is searched to nd the smallest free block large enough to satisfy a request The basic rationale for this approach is to minimize the amount of fragmented space caused by splitting However the problem may still occur if the selected block is not a perfect t to the requested size In such situation the splitting may put small memory blocks back to the list These small blocks may be unusable Additionally the search in best t is very exhaustive Thus this scheme may not scale well to large heaps with many free blocks Segregated fit uses an array of free lists where each list holds free block of a particular size One of the fastest allocator available today is Doug Lea s version 25 In this scheme every heap consists of 128 linked lists For the rst 64 lists each list represents one size The first list has the size of eight bytes and the subsequent 63 lists have eight bytes separation between them For example list 1 would contain the objects of size eight bytes List 2 would contain the objects of size 16 bytes and list 3 would contain the objects of size 24 bytes For the last 64 lists the size granularity is not xed These lists are used to store objects larger than 512 bytes and the rst t approach is used in these lists The The Procedure Abstraction Scope and storage management 5555 63 Procedure abstractions El Procedures are fundamental programming abstractions They are used to support dynamically nested blocks a Paired function call and return jumps I They provide separate name spaces for local variableslabels n Implementation details hidden from outside I They have standalone semantics defined by an external interface n input parameters return values global side effects El Procedures are the unit of separate compilation They represent parameterized block of computation k float bar float r return r int mainint argc char argv oat f00 quot float a int a b C a foo r bar return r c55363 Blocks and name spaces n Blocks regions with local declarations I Blocks can be nested but not partially overlapped 1 Cannotjumping from outside into the middle of a block I Localglobal variables variables declared inside the block El Name space scope of a variable I Region of program where declaration is visible a Lifetime of a variable storage I Period of time when a storage is allocated for the variable int x int y I Inner declaration of x hides outer one int x a hole in scopequot I Lifetime of outer x includes time when inner block is executed c55363 3 Scoping rules El Global and local variables program mainonputloutput var x integer function gz integer integer begin g xz end outer block h3 function hz Integer Integer var x integer v begin x 1 hgz end 912 t begin x 0 printh3 end El Static scope I Find global variables in enclosing blocks in program text a Dynamic scope I Find global variables in the most recently evaluated blocks I Easier to implement in interpreted languages I What is the scoping rule for CC Java c55363 4 Activation Record El Allocate storage for each block dynamically l Allocate an activation record before evaluating block 1 Storage for each local variable determined as compile time a Values of local variables evaluated at runtime l Delete activation record after block exits int X0 Allocate AR with space for x y int yx1 Set values of x y Allocate AR for inner block int 2 x x Y Y Set value of z Delete AR for inner block Delete AR for outer block May need space for variables and intermediate results like Xy XY c55363 Activation record for functions static scope Activation record pointerrarp i El Access link I Pointer to activation record of enclosmg scope a Return address I Pointer to the instruction immediately following function call I Retu rn result address I Address of the storage to put result being returned I Register save area I Saveregister values before function call I Restore register values before return I Parameters I Storage for function parameters I Parameter values must be initialized by caller c55363 6 Parameter passing in function calls El Functions parameterized blocks of Formal parameter computation I Formal and actual parameters El Passbyvalue int f int 0 Formal parameters contain values of actual parameters Callee cannot change values of actual parameters I El Passbyreference Ta39no Formal parameters contain locations mt y 0 of actual parameters pr39nt 17WYi Callee can change values of actual parameters Formal parameters in activation record may be aliased ACtual parameter 1 Aliasing two names refer to same location X X1 return X c55363 7 Example What is the nal result DSEUdO39COde n Draw the activation any recerdsfor the vast eva uatlon 47 int f int x El What parameter Bassmg IS supported y the languages you x x1 return x know main int y 0 pass b A y print fyy 1 Value c55363 8 Allocating activation records on stack int x0 ii if int yx1 int zxyXy n Push activation record on stack I Set caller ARP to rarp I Set rarp to new AR a Pop activation record off stack I Reset rarp to caller s ARP I When making function calls I Caller must also set return address return value addr Activation record pomterrarp saved registers and parameters Example activation records for functions a Function int factint n if nlt 1 then return 1 else return n factn l a Return address I Instruction following function call a Return result address I location to put factn n Parameters I Formal parameter n a Local variables Activation record pointerrarp I Intermediate results i 1 Eg value of factnl C55363 10 l 3 fquot r 7 u i v H r in i aquot factk l Control link Access link Return address Returnresult addr n k factn l Environment pointer E int factint n if nlt 1 then return 1 else return n factn 1 l fact3 factZ factl c55363 Control link Returnresult addr n 3 factn l Control link Return result addr l n 2 factnl Control link Return result addr n 1 factnl l Exercise Managing Function Calls n Draw the runtime stack of the following C code after the call to h inside the body of g I What is the final result of the code 1 int x 5 2 int fint y return x y 2 3 int gint h 4 int x 7 5 return hx 6 7 int main 8 9 int x 10 10 return gf 11 C55363 12 Linkage convention Implementing function calls Procedure p prologue i Procedure q Ca prologue precall 56 Postreturn Q J l epilogue epHogue Linkage convention programs in different files must follow a single contract of function call implementation El Precall Push callee s AR increment rarp Set caller s ARP Set return address Set return result addr Save live register values initialize formal parameters El Postreturn Restore live register values Pop callee s ARdecrement rarp El Prologue Initialize local variables Load local environment access link El Epilogue Deallocate local variables Goto return address C55363 13 Simpli ed memory model El Runtime stack activation records of blocksfunctions I Block entry add new data to stack I Block exit remove outdated data El Heap data of varying lifetime I Variables that last throughout the program I Address may be contained by variables on the runtime stack Code Data Stack Program Counter Heap static Activation record pointerrarp 5363 data Managing Data Storage ii Local variables activation records on stack I Declared inside a computation block function body in Enter block allocate space 2 Exit block deallocate space I Local variables in an enclosing block 1 Already allocated before entering current Block D Remain allocated after exiting current block I Function parameters and return value a Allocated and initialized before entering function body a Formal parameters dallocated after exiting function body El Globalstatic variables static data areas I Allocated when program is loaded to memory I Storage remain until program exits ii Dynamically allocated variables heap I Storage dynamically allocated at runtime eg malloc in C I Storage remain until explicitly deallocated or garbage collected C55363 15 Accessing variables in memory a Each memory storage has an address Accessing local variable a I Base address the startin address of a data area 9 LoadAI rarp a gt r1 1 Local variables of current block activation record pointer rarp loadI a gt F1 I Offset the number of bytes loadAO rarp r1 gt r2 after the base address a Local variables of current block loadI a gt r1 Add rarp r1 gt r2 predetermined at compile tIme load r2 gt r3 El Address of variable base address offset C55363 16 Accessing global static variables El Allocated separately in static data area Accessing global variable fee I Base address unknown until program is loaded into memory 1 Use symbolic labels to substitute at compile time El Symbolic labels replaced with runtime value by assembler and LoadI ampfee gt r1 Load r1 gt r2 Accessing fooa loader LoadI ampfoo gt r1 l Offset calculated at compile time LoadAI r1 fooa gt r3 1 Individual variables offset0 a Group of data layout predetermined LoadI ampfoo gt r1 Add r1 fooa gt r2 Load r2 gt r3 C55363 17 Local variables of enclosing scopes Outer block int x1 int gint z return xz l int hint z int x 1 A I return gz h3 prInt h3 Use access link to find local variables in an enclosing scope static scope 1 Access link is always set to frame 93 of closest enclosing lexical block 1 For function body this is block that contains function declaration C55363 18 Accessing variables in enclosing scopes El Accessing local variables int x1 I Offset calculated at compile time int gint z return z l I Need to find the base address int mint 2 u The AR that contains the variable I Lexical level of a block I Number of enclosing scopes n g 1 h 1 outerblock O I For each variable x int x 1 A return g print h3 I Coordinate of x is ltn ogt where Coordinate for X ltO8gt u n leXIcal level of block that defines x LeXIcal level of g 1 n O offset of X in it s AR LOBd mStI UCtlonS I If a block at lexical level m loadAI Farp 4 gt r1 references x loadAI r1 8 gt r2 1 Follow access link mn times to find the base address for X C55363 19 Lexical scoping through global display n Allocate a global array display I hold the address of most recent ARs at each lexical level I No longer need access links in ARs El To access variable ltnogt I use the ARP at element n of display c55363 Ru ntime stack LevelO AR Display levelO level1 l gt Levell AR level2 level3 Level2 AR Level3 AR 20 Global display vs access links El Maintenance I Constant cost for global display I When entering every block at lexical level n save the leveln ARP from global display replace it with new ARP a When exiting the block restore the old leveln ARP into display I Varying cost for access links a If a levelm block invokes a leveln block mn 1 callee s access link points to caller s AR mn callee s access link caller s access link m gt n callee s access link caller s level n1 access link I Referencing variables in enclosing scope I Constant cost through global display I Varying cost through access links El The tradeoff depends on the ratio of non local references I If ARs can outlive their invocation access link must be used I The chosen approach by functional programming languages C55363 21 Department of Computer Science UTSA Week 13 and 14 Code Generation The code generator includes two pars object code translation and forward references resolution Each object code includes op code and operands Op code is declared as follows typedef enum Add2 And2 Arrow2 Assign2 Bar2 CallZ Constant2 Divide2 EndProcZ EndProg2 Equa12 Fi2 Greater2 lndex2 Less2 Minus2 Modulo2 Multiply2 Not2 Or2 ProcZ Prog2 Read2 Subtrath Value2 Variable2 VarParamZ Write2 DefAddr2 DefArg2 OpCodeT39 DefAddr and DefArg are ps eudoinstructions that are used during code generation but not program execution Depending on number words generated the compiler uses the following procedures to output op code and operands int codeMaxCodeSize439 keep intermediate code code length op code argl arg2 static int codelndex index of code in code table static int codeAddr39 address of code int labelTableMaxTableSize39 keep address for label emitl int op codecodelndex0 139 this first field indicates number of words codecodelndexl op39 this is the op code codeA Variable Addressing To generate code like Variablel 3 the parser has to figure out the level and the displacement of the variable The level is tracked by a global level variable and the displacement is counted by passing an integer to the VariableGropup function VariableGroup int length NameObjectT typex VariableDefinition int number NameObjectT typex VariableGroup ampnumber amptypex 39 length number TypeLengthtypeX39 EXpectSEMICOLON stop The length of a variable is calculated by a recursive function as follows in TypeLengthNameObjectT typex if typexgtkind StandardType return 139 else if typexgtkin ArrayType return typeXgtuarrayupperBound 7 typeXgtuarraylowerBound 1 TypeLengthtypex gtuarrayelementType ese record type Return typexgturecordlength39 The procedure that parses variable definitions is described as follows VariableDefinitionPartint length CS 5363 by Dr Chia Tien Dan L0 2003 1 Department of Computer Science UTSA NameObj ectT lastVar39 int 39 Expect var 39 VariableDefinitionamplastVar length 39 while isNamecurrToken VaribleDefinitionamplastVar ampmore 39 leng more VariableAddressinglength lastVar The lastVar points to the last defined variable We use VariableAddressing to fill in level and displacement information for each variable define VariabelAddressingint varLength NameObjectT lastVar int disp 3 varLength39 for varLengthgt339 disp disp TypeLengthlastVargtuvariabletype lastVargtuvariablelevel cuIrBlockLevel39 lastVargtuvariabledisplacement disp39 lastVar lastVargtnext39 The formal parameter addressing is a little bit different in that a negative displacement is assigned to each formal parameter ParameterAddressingint paramLength NameObjectT lastParam int disp 039 for disp gt ParamLength39 39 astParam gtkind VarParameter disp disp l39 else disp disp 7 TypeLengthlastParamgtuvariabletype lastParam gtuvariablelevel cuIrBlockLevel39 lastParam gtuvariabledisplacement disp39 lastParam lastParamgtnext39 Once the variable addressing information is built a variable access is simply be translated to either VarParam or Variable instruction with corresponding level and displacement arguments Example level cuIrBlockLevel 7 obj gtuvariablelevel39 if objgtkind VarParameter emit3VarParam2 level objgtuvariabledisplacement else emit3Variable2 level objgtuvariabledisplacement An array of this form ai is compiled to have the address of a the evaluation of i and an Index instruction as follows Emit5lndex2 objgtuarraylowerBound objgtuarrayupperBound TypeLengthobjgtuarrayelementType lineNo CS 5363 by Dr Chia Tien Dan L0 2003 2 Department of Computer Science UTSA Expression Code Two things 1 output instruction to replace addresses with real values on stack and 2 keep track of size of run time stack Expression SimpleExpression Term and Factor are used to parse an expression Factor recognizes a variable access and the following routines are used VariableAccesstypex stop length TypeLengthtypex emit2Value length pushlengthl stack size increased by length l b When Term finds a multiplication operator it calls Factor again 0 Term outputs object code by the following routines if typex typelnteger CheckTypetypex typex2 if Operator Asterisk emitl Multiply2 else if Operator Divl emitl Divide2 else if Operator Modl emitl ModuloZ else if Operator Andl emitl And2 p0p1 Example y z div 5 Variable0 3 Valuel Variable0 4 Valuel Multiply Constant5 Divide To keep track of temporary storage of every block we add tempLength and maxTemp to the block table data structure typedef struct iBlockTable NameObjectT nameObject struct iBlockTable next struct iBlockTable pre int tempLength maxTemp BlockTableT The tempLength keeps the current stack length and maxTemp keeps the maximal stack length used in a block pushint len currBlockP gttempLength len if cuIrBlockPgtmaxTemp lt currBlockP gttempLength currBlockP gtmaxTemp cuIrBlockPgttempLength popintlen currBlockP gttempLength len Assignment Statement CS 5363 by Dr Chia Tien Dan L0 2003 3 Department of Computer Science UTSA The code for assignment statement has the form AssignmentStatement VariableAccess Expression Assign The procedure is modified as follows AssignmentStatementunsigned long long stop NameObjectT varType exprType39 int leng 39 VariableAccessampvaritype 39 Expect 39 ExpressionampexprType stop CheckTypevarType exprType length TypeLengthexprType39 emit2Assign2 length popllength39 Temp property If the temporary part of the stack is empty before the execution of the statement it is also empty after the execution of the statement The assignment statement follows the Temp property While Statement and Forward References The while statement while B do S has the following object code Ll B DoL2 s GotoLl L2 About emitting the Do instruction the statement S is not yet compiled and thus L2 is unknown This problem of forward references is solved in three steps 1 The forward references are assigned a numeric value say 17 and 18 as a label The following intermediate code is generated DefAddrl 7 B code Dol 8 S code Gotol 7 DefAddrl 8 An assembler resolves the real address for each label by scanning the intermediate code and tracking the address of instructions Assume the following addressing is scanned 279 DefAddrl 7 279 B code 287 Dol 8 289 S code 320 Gotol 7 322 DefAddrl 8 A table is built to map numeric label to real address Output code with real jump address The jump displacement ofDol8 instruction is calculated 322287 35 Thus Do35 is the final code The Gotol7 is replaced with Goto4l in a similar manner N V L V The NewLabel is used to generate a unique number to represent a label whenever needed The function also checks if a maximal number of labels is reached NewLabelint tag static int labelNo039 if labelNo gt MAXLABEL Error Maximal Label is Reached CS 5363 by Dr Chia Tien Dan L0 2003 4 Department of Computer Science UTSA tag labelNo The parsing of a while statement is modified as follows WhileStatementunsigned long long stop lnt Labell Labe12 NameObjectT exprType NewLabelampLabe12 Emit2DefAddr2 Labell Expect while ExpressionampexprType CheckTypeexprType typeBoolean Expect do NewLabelampLabe12 Emit2DoZ Labe12 Papa Statementstop Emit2Goto2 Labell Emit2DefAddr2 LabelZ To handle the mapping from label to address a label table is maintained The unresolved code is stored in a code table emit int emitl int op codecodelndex0 l codecodelndexl op codeAddri F int emit2int op int argl if op DefAddr2 labelTableargl codeAddr patch real address for label else codecodelndex0 2 codecodelndexl op codecodelndex 2 argl codeAddr2 After labels are resolved to addresses the real object code is obtained The Temp property can be probed by mathematical induction as follows 1 Base the elementary statements have the property empty statement assign statement and procedure statement Hypothesis finite statement holds the Temp property Induction the following statements hold the Temp property where Si s hold the Temp property lfB then Sl else 82 b While B do S 0 Begin 1 2 Sn When measuring the maximal extent of the stack the statemenm are treated as a sequential piece of code MaxTemp ifB then Sl else 82 MaxTempB 1 2 Maxtempwhile B do S MaxTempB S MN VV CS 5363 by Dr Chia Tien Dan L0 2003 5 Code Shape Three address translation Thgytcode mn a on n A single language construct can have many implementations I many to many mappings from high level source language to low level target machine language I Different implementations have different efficiency 1 Speed memory space register power consumption Source code Lowlevel threeaddress code Xyz r1rxry F11FXFZ r1ryrz r2 r1rz F21F1FY r2r1rX l l l J x z Y Q i ll c55363 Z Assigning storage locations El Compilers must choose storage locations for all values I Procedurelocal storage I Local variables not preserved across procedural calls I Procedurestatic storage a Local variables preserved across procedural calls I Global storage global variables I Run time heap dynamically allocated storage El Relgisters temporary storage for applying operations to va ues I Unambiguous values can be assigned to registers with no backup storage void fee int a bc a0 bampa b1 c a b c55363 Translating to three address code El No more support for structured control flow I Function calls gt explicit memory management and goto jumps a Every three address instruction maps into several target machine instructions I The original evaluation order is maintained a Memory management I Every variable must have a location to store its value 1 Register stack heap static storage I Memory allocation convention n Scalaratomic values and addresses gt registers stacks n Arrays gt heap a Global variables gt static storage c55363 4 Translating expressions to three address I For every non terminal expression E I Epace temporary variable used to store result El Synthesized attributes for E I Bottom up traversal ensures Epace assigned before used I Symbol table has value types and storage for variables El What about the value types of expressions E id E1 EpaceE1pIace genvarstoreidentry E1pace E E1 E2 Epacenewtmp gencodeADDE1placeE2placeEpIace E E1 Epace E1pace E id EpIacegenvarLoadidentry E num Epacenewtmp gencodeLOADI numva O Epace Example input a bcb2 Should we reuse register for variable b c55363 Storing and accessing arrays El Single dimensional array Accessing ith element base How w Low lower bound of dimension w element size Multi dimensional arrays need to locate base addr of each dimension n Row major column major Indirection vector Extend attribute grammar to support array access What about struct access l11 112 113l 21l 2 2l 2 3 l Aijvaue at Ailow1len2wjlow2w Row major 11 i21 12 2 2 13 2 3 Aijvaue at Ajlow2len1wilow1w Indirection vector Aij value at Ailow1wpjlow2w Column major c55363 6 Character strings El Languages provide different support for strings I CCJava through library routines I PLILispMLPerlpython through language implementation I Important string operations 1 Assignment concatenation El Representing strings I Nullterminated vs explicit length field El Treat strings as arrays of bytes I More complex if hardware does not support op on bytes I Translate collective string operations to array operations before three address translation lalsltlrlilnlglwl l l7lalsltlrll lnlgl l Null termination Explicit length field loadI b gt r1 String aSSignment cloadAI r1 2 gt r2 all b2 loadI a gt r3 cstoreAI r2 gt r3 1 c55363 Translating Procedural calls Procedure p prologue l precall Postreturn l epHogue Procedure q Ca prologue epHogue El El c55363 Functionprocedural calls need to be translated into calling sequences Sideeffect of procedural calls I Determined by linkage convention I If function call has side effects Orig evaluation order need be preserved Function pointer as parameters I If function definitions can be nested need to pass both starting address and the access link of the function Saving and restoring registers I Expensive for large register sets I Use special routines or operations to spee it up I Combine responsibility of caller and callee Optimizing small procedures that don t call others I Reduce precall and prologue I Reduce number of registers need to be saved Passing arrays as parameters El Arrays are pointers to data areas I Mostly treated as addresses pointers I Must know dimension and size to support elem access I Must have compound type info when passed as parameters D Handled either by compilers or programmers El Compiler support for dynamic arrays I Arrays passed as parameters or dynamically allocated I Must save type information at runtime El Dope vector runtime descriptor of arrays I Saves starting address number of dimensions lowerupper bound and size of each dimension I Build a dope vector for each array parameter before function call I Can support runtime range checking for each element access El Before accessing the element is it a valid access c55363 9 Translation of boolean expressions a Two translation options I Same as translating regular expressions true1nonzero false O I Translate into controlflow branches For every boolean expression E EtrueEfalse the labels to goto if E is truefalse Numerical translation i CmpLT ra rb gt rc Controlflow translation if a lt b goto Et cmp ra rb gt cc1 else goto Ef CbrLT cc1 gtL1 L2 Et c true L1 loadI true gt rC goto next jumpI gt L3 Ef c false L2 loadI falsegt rc next L3 c55363 Hardware support for relational operations a Straight conditional code I Special conditioncode Translating a x lt y Comp rx ry gt cc1 registers interpreted only Cbr LT ccl gt L1 L2 by conditional branches a Conditional move I Add a special conditional move instruction a Boolean valued comparisons I Store boolean values directly in registers El Predicated evaluation I Conditionally executing instructions L1 loadI true gt ra L2 I39oadI false gt ra Comp rx ry gt cc1 i2iLT cc1truefase gtra Straight conditional code Conditional move cmpLT rx ry gt ra Cbr ra gt L1 L2 L1 L2 CmpLT rx ry gt r1 Not r1 gt r2 r1 r2 Bool valued comparison Predicated eval c55363 Short Circuit evaluation of boolean expressions El Evaluate only subexpressions required to determine the final result I E a lt b ampamp c lt d if a gt b there is no need to evaluate whether c lt d I For every boolean expression E l EtrueEfase the labels to goto if E is truefalse cmp ra rb gt ccl if a lt b goto L1 cbrLT cc1 gt L1Ef else goto Efalse L1 cmp rCI rd gt CCZ L1 if c lt d goto Etrue Cbr LT CCZ gt EtIEf else goto Efalse Et 3quot JumpI next Ef Next What about translating E a lt b H c lt dquot C55363 12 Translating control ow statements Ecode s if E THEN 51 Etrue Slcode Efase Ecode s if E THEN 51 else 52 E39true Slcode Ef I goto Snext 39a se39 SZcode Sbegin Ecode s While E DO 51 E39true Slcode goto Sbegin Efase c55363 Example Translating control ow statements Ealtbampampcltd if a lt b goto L1 else goto Efase L1 if c lt d goto Etrue else goto Efase ifaltbampampcltd xa else xd q cmp ra rb gt cc1 cbrLT cc1 gt L1Ef L1 cmp rc rd gt cc2 cbrLT cc2 gt EtEf Et jumpI next Ef Next cmp ra rb gt cc1 cbrLT cc2 gt Et Et move ra gt rx jumpI next Ef move rx gt rd Next cbrLT cc1 gt L1Ef L1 cmp rc rd gt cc2 What about E a while stmt c55363 Position based translation of of boolean expressions El Every boolean expression E has two attributes I Etruefalse the label to goto if E is truefalse El Evaluate Etrue and Efase as synthesized attribute I Create a new label for every unknown jump destination I Set destination of created jump labels later El Usually evaluated by traversing the AST instead of during parsing I Issue creationmerginginsertion of instruction labels E true Etrue newabe Efase0 gencodejumpI00Etrue E false Efase newabe Etrue0 gencodejumpI00Efase E1 relop E2 Etrue newabe Efasenewabe rnewtmp gencodecmpE1placeE2placer gencoderelopcbr r Etrue Efase I39I39I Example input r a lt b C55363 15 Translating control ow statements El For every statement S add two additional attributes I Sbegin the label of S l Snext the label of statement following S S if Sbegin O genabeSbegin E SnextmergeEtrueEfalse S WHILE if Sbegin0 Sbeginnewlabel genabeSbegin E SlbeginEtrue Sl SnextEfalse mergelabeISlnextSbegin gencodejumpI00Sbegin S LBRACE stmtsbegin Sbegin stmts RBRACE Snextstmtsnext stmts Sbeginstmtsbegin S stmtsnext Snext stmts Sbeginstmtsbegin S stmtslbegin Snext stmtsl stmtsnext stmtslnext c55363 Week 3 7 Lexical Analysis 0 Tasks of Lexical Analysis 0 Why separating lexical analysis and parsing o Tokens Patterns and Lexemes 0 Complex tokens like identi er and numeral are described using regular expression notations Attributes for Tokens provide actual value for a lexeme a pointer to an entry in symbol table 0 A symbol table may contain word symbols names and numerals o Buffering Techniques Buffer Fairs and Sentinels o Buffer Paris a buffer contains 2 N character halves Each system read system call brings N characters into buffer Two pointers are maintained forward and lexemeibeginning o Drawback can not recognize token with length more than N I aeandaEOFa if forward at end of rst half then begin reload second half forward forward 1 end else if forward at end of second half then begin reload first half move forward to beginning of first half end else forward forward 1 Sentinels reduce two comparisons to on e EEOFI E E E EeEnEdEEOFE E forward forward 1 if forward EOF then begin if forward at end of rst half then begin reload second half forward forward 1 end else if forward at end of second half then begin reload rst half move forward to beginning of rst half end else terminate lexical analysis end Token Speci cation Strings and Languages A language denotes any set of strings over some xed alphabet The empty set or the set that contains empty string are languages Operations on Languages union concatenation and closure Regular Expressiom Regular expressions over alphabet sigma is de ned as follows 1 epsilon is a regular expression that denotes epsilon 2 if a is a symbol in alphabet then a is a regular expression that denotes a 3 suppose r and s are regular expressions denoting the languages Lr and Ls then a r l s is a regular expression denoting Lr U Ls b r s is a regular expression denoting LrLs c r is a regular expression denoting Lr d r is a regular expression denoting Lr o A language denoted by a regular expression is said to be a regular set 0 Regular De nitions A regular de nition over sigma is a sequence of de nitions of the form dl gt rl d2 gt r2 dn gt rn where each di is a distinct name and each ri is a reqular expression over the symbols in sigmaU d1 d2 dil o Nonregular sets Some language can not be described by any regular expression 1 Balanced or nested construct e g the set of all strings of balanced parentheses can not be described by a regular expression However it can be speci ed by a contextfree grammar Repeating strings cannot be described by regular expressions wcwl w is a string of a s and b s can not be described by any regular expression nor can it be speci ed by a cont extfree grammar N V 0 Recognition of Tokens Consider the Pascal grammar The terminals program etc generate sets of strings given by the following regular de nitions add Line 41 and 42 to recognize names and numbers where digit 0 l 2 9 and letter A B Z a b 2 Numeral gt digit Name gt letter letter l digit program gt program const gt const TypeName gt Name VariableName gt Name ProcedureName gt Name FieldName gt Name ConstantName gt Name We also assume lexemes are separated by white space consisting of nonnull sequences of blanks tabs and newlines The lexical analyzer will do so by comparing a string against the regular de nition ws delim gt blank l tab l newline ws gt delim Our goal is to isolate the lexeme for the next token in the input buffer and produce as output a pair consisting of the appropriate token and attributevalue using the translation table The PROGRAM SEMICOLON CONST are prede ned constants the pointer to table entry may be the index of the table 0 Transition Diagrams Start state accepting state double cirle and asterisk retract forward pointer Each edge is associated with a character If failure occurs in all transition diagrams a lexical error has been detected and an error recovery routine is invoked For performance consideration looking for frequently occurring tokens before less frequently occurring ones eg white space other retumBarBAR retumLeftSquare LSQUARE A technique for separating word symbols and names is to initialize a symbol table with word symbols 0 Implementing a Transition Diagram Procedure Begin c neXtChar If c then c neXtChar switch c case retumBar BAR case c in delimiter while c in delimiter c neXtC har case while c c neXtChar default retract retumLeftSquare LSQUARE endif end Procedure neXtTokenO begin skipSeparatorO switch ch Instruction Scheduling 5555 63 Instruction scheduling original Instruction Reordered code Scheduler code El Reorder operations to decrease running time I Different operations take different no of cycles a Referencing values not yet ready causes operation pipeline to stall l Processors can issue multiple instructions every cycle a VLIW processors can issue one operation per functional unit in each cycle a Superscalar processors tries to issue the next k instructions if possible c55363 Instruction scheduling example Assumptions memory load 3 cycles mult 2 cycles other 1 cycle sta rt loadAI rarp w 9 r1 add r1 r1 r1 loadAI rarp X 9 r2 mult r1 r2 r1 loadAi rarp y 9 r2 mult r1 r2 r1 loadAI rarp Z 9 r2 mult r1 r2 r1 storeAI r1 9 rarp O sta rt 1 l KOOU39lIgtUON II Instruction level parallelism ILP l Independent operations can be evaluated in parallel n Given enough ILP a scheduler can hide memory and functional unit latency c55363 loadAI rarp w 9 r1 loadAI rarp X 9 r2 loadAi rarp y 9 r3 add r1 r1 r1 mult r1 r2 r1 loadAI rarp Z 9 r2 mult r1 r3 r1 mult r1 r2 r1 storeAI r1 9 rarp O Instruction scheduling Dependence graph El Instruction reordering must maintain original result El Dependenceprecedence graph G NE I Each node n E N is a single operation a typen type of functionalunit that can execute n u delayn number of cycles required to complete n I Edge n1n2 E N indicates n2 uses result of n1 as operand I G is acyclic within each basic block a IoadAI rarp w r1 a Dependence graph b add r1 r1 r1 b C c IoadAI rarp X 9 r2 cl mult r1 r2 9 r1 d e e IoadAi rarp y 9 r2 f mult r1 r2 9 r1 f g g IoadAI rarp Z 9 r2 h h mult r1 r2 9 r1 i i storeAI r1 9 rarp O c55363 4 The scheduling problem El El Given a dependence graph D NE a schedule S ma 5 each node n E N to the cycle number that n should be issue Each schedule S must satisfy three constraints Wellformed for each node n E N Sn gt 1 there is at least one node n E N such that Sn 1 I Correctness if n1n2 E E then Snl delaynl lt Sn2 Feasibility for each cycle i gt 1 and each functionalunit type t number of node n where typent and Sni s number of functionalunit t on the target machine Given a wellformed schedule S that is both correct and feasible the length of the schedule is Ls maxSn delayn nEN A schedule S is timeoptimal if it is the shortest I For all other schedules Sj which contain the same set of operations LS lt LSj S has shorter length than Sj c55363 The instruction scheduling problem El Measures of schedule quality I Execution time I Demands for registers a Try to minimize the number of live values at any point I Number of resulting instructions from combining operations into VLIW I Demands for power efficiency in using functional units ii Difficulty of instruction scheduling I Balancing multiple requirements while searching for time optimality n Register pressure readiness of operands combining multiple operations to form a single instruction El Local instruction scheduling scheduling on a single basic block is NP complete for all but the most simplistic architectures I Compilers produce approximate solutions using greedy heuristics c55363 Anti dependences a IoadAI rarp w r1 a Dependence graph b add r1 r1 r1 b C c IoadAI rarp X 9 r2 cl mult r1 r2 9 r1 d e e loadAi rarp y 9 r2 f mult r1 r2 9 r1 f g g IoadAI rarp Z 9 r2 h h mult r1 r2 9 r1 i i storeAI r1 9 rarp 0 El Node operation e cannot be issued before d even if e does not use result of d I e overwrites the value of r2 that d uses I There is an antidependence from d to e I To handle anti dependences schedulers can I Add antidependences as new edges in dependence graph or I Rename registers to eliminate antidependences c55363 7 Critical path of dependence graph a IoadAI rarp w r1 a Dependence graph b add r1 r1 r1 b C c IoadAI rarp X 9 r2 cl mult r1 r2 9 r1 d e e IoadAi rarp y 9 r2 f mult r1 r2 9 r1 f g g IoadAI rarp Z 9 r2 h h mult r1 r2 9 r1 i i storeAI r1 9 rarp O El Given a dependence graph D I Each node ni can start only if all other nodes that ni depend on have finished I Length of any dependence path n1n2ni any path in D is delayn1delayn2deayni a Critical path the longest path in the dependence graph I should schedule nodes on critical path as early as possible c55363 8 List scheduling El A greedy heuristic to scheduling operations in a single basic block I The most dominating approach since 19705 I Find reasonable scheduling and adapts easily to different processor architectures a List scheduling steps I Rename to avoid anti dependences a Each definition receives a unique name I Build a dependence graph I Assign priorities to each operation n 1 Eg the length of longest latency path from n to end I Iterativer select an operation and schedule it 1 Keep a ready list of operations with operands available c55363 9 List scheduling algorithm Example loadAI add loadAI mult loadAi mult rarp W 9 r1 r1 r1 9 r2 rarp X 9 r3 r2 r3 9 r4 rarp y 9 r5 r4 r5 9 r6 loadAI rarp Z 9 r7 mult r6 r7 9 r8 storeAI r8 9 rarp O ZTLQTPFDQDO39QJ a 13 Dependence graph 19 C12 bg d e10 f gs 7 M4 i3 Cycle 1 Ready leaves of D Active Q While Ready U Active I Q if Ready I Q then remove an opi top priority from Ready Sopi Cycle add opi to Active Cycle for each opi E Active if Sopi delayopi lt Cycle then remove opi from Active for each successor opj of opi in D Mark edge opiopj ready if all edges to opj are ready then add opj to Ready c55363 Example list scheduling cycle Ready active integer memory 1 ceg a a 2 eg c c 3 e e 4 g b b 5 9 cl cl 6 g g 7 f f 8 9 h h I IO c55363 sta rt HKOVONLnhWNI l loadAI loadAI loadAi add mult loadAI mult mult storeAI r1 rarp W 9 r1 rarp X 9 r2 rarp y 9 r3 r11 r1 9 r1 r1 r2 rarp Z 9 r2 r1 r3 r1 r2 9r1 9 r1 9 r1 9 rarp O The list scheduling algorithm El How good is the solution I Optimal if a single op is ready at any point I If multiple ops are ready schedule the op with best priority ranking a Result depends on assignment of priority ranking El Complexity ONogN E assuming DNE I Scheduling all operations ON 3 Assume for each n E N delayn is a small constant I When making each scheduling decision 1 Scan Ready list to find the toppriority op OIogN if using priority queue 1 Scan Active list to modify Ready list Separate ops in Active list according to their complete cycles Each edge must be marked as ready once OE C55363 12 Context sensitive Analysis Attribute grammar and type checking c55363 1 Context sensitive analysis El To understand the input computation a compilerinterpreter must discover I The type of value stored in each variable I The type of argument and return values for each function I The representationinterpretation of each value I The memory space allocated for each variable I The scope and live range of each variable El Static definition of variables variable declarations I Compilers need properties of variables before translation I Use symbol tables to keep track of variable information El Context sensitive analysis I Determine properties of program constructs I Cannot be handled by contextfree grammar u Eg CFG cannot enforce all variables are declared before used c55363 Syntax directed translation n Compilers translate language constructs I Need to keep track of relevant information a Attributes relevant information associated with a construct l Attribute grammar syntaxdirected definition I Associate a collection of attributes with each grammar symbol 2 Define actions to evaluate attribute values during parsing e n ee e e eeee Attributes for expressions type of value int float double char string type of construct variable constant operations Attributes for constants values Attributes for variables name scope Attributes for operations arity operands operator c55363 Attribute grammar Syntax directed de nition El Associate a set of attributes with each grammar symbol El Associate a set of semantic rules with each production Specify how to compute attribute values of symbols El Systematic evaluation of context information through traversal of parse tree or abstract syntax tree e n ee e e eeee production Semantic rules Annotated parse tree for 51520 e n eval nval eVal305 e el e2 eval e1val e2val eVa300 eval5 e e1 e2 eval e1val e2val y gt eval15 e e1 e2 eval e1val e2val 5 aim 20 e e1 e2 eval e1val e2val 15 20 c55363 4 Synthesized attribute de nition El An attribute is synthesized if I The attribute value of parent is determined from attribute values of children in the parse tree ee e e eeee Semantic rules eval nval eval e1val e2val eval e1val e2val eval e1val e2val e 39 n eva305 pI OductIon i I 300 e If n eval5 j39 a e el e2 l 15 lt e i 81 e2 eva e val 20 5 e e1 e2 15 20 e e1 e2 eval e1val e2val c55363 Inherited attribute de nition I An attribute is inherited if I The attribute value of a parsetree node is determined from attribute values of its parent and siblings D T L T int real L L id id D Ttypereal L39mrea Linreal I real Linrea Ii idz l id1 l id3 Production Semantic rules DT L LinTtype T int TTypeinteger T real Ttypereal LL1 id L1in Lin AddtypeidentryLin L id AddtypeidentryLin c55363 6 Dependences in attribute evaluation I If value of attribute b depends on attribute c l Value of b must be evaluated after evaluating value of c I There is a dependence from c to b Annotated parse tree Dependency graph D real Ttype L3in L3addentry YD L2 quotngt L2addentry L2inrea I id3 real i Lli id2 ntry Llinfrea39 id2 L1addentry id1 id1entry c55363 7 Evaluation order of attributes El Topological order of the dependence graph l Edges go from nodes earlier in the ordering to later nodes I No cycles are allowed in dependence graph InQUt Parse Dependency I Evaluation order for Strlng tree graph Semantic rules real Tt pe L3in gtL3addentry d5 L2in id3entry L2addentry L1i t1addentry id2entry T id1entr c55363 8 Evaluation of semantic rules a Dynamic methods compile time I Build a parse tree for each input I Build a dependency graph from the parse tree I Obtain evaluation order from a topological order of the dependency graph El Rule based methods compiler construction time I Predetermine the order of attribute evaluation based on grammar structure of each production I Example semantic rules defined in Yacc El Oblivious methods compiler construction time I Evaluation order is independent of semantic rules I Evaluation order forced by parsing methods I Restrictive in acceptable attribute definitions c55363 L attributed de nitions El A syntax directed definition is L attributed if each inherited attribute of Xj 1ltjltn on the right side of AX1X2Xn depends only on I the attributes of X1X2Xj1 to the left of Xj in the production I the inherited attributes of A Lattributed definition Non Lattributed definition Production Semantic rules D T L L Tt Production Semantic rules m e Yp ALM Li Ai T Int TTypenteger M i L S Treal Ttyperea AS MS LL1 id A Q R AddtypeidentryLin QJ RS Lid AddtypeidentryLin As Qs c55363 Synthesized and inherited attributes El Lattributes may include both synthesized and inherited attributes e va305 e inhs yn305 nva15 e inh15 8 syn300 i e inh eva 20 Syn200 nva20 e inh 15 8 s n20 20 y 2 e n e e ee ee a production Semantic rules e n e e inhnva eva e syn e e e 1 e 1inh e inh eva e syn e 1syn e e e 1 e 1inh e inh eva e syn e 1syn e s e syn e inh 8 c55363 Exercise II Given the following grammar for a binary number generator SL LLBB BOl1 II Compute the value of each resulting number I Eg ifs gt gt 1101 then the value of s is 13 El Compute the contribution of each digit I Eg ifs gt gt 1101 the contribution of the four digits are 8401 respectively Steps 1 Define a set of attributes for each grammar symbol 2 Categorize each attribute as synthesized or inherited 3 For each production 31 if the lefthand symbol has a synthesized attribute define a rule for evaluating the attribute 32 if any righthand symbol has a inherited attribute define a rule for evaluating the attribute c55363 12 Translation schemes I A translation scheme is a CFG where Attributes are associated with grammar symbols and l Semantic actions are inserted within right sides of productions El Notation for specifying translation during parsing Parse tree for 95 with actions Translation scheme E E T R R T print R1 T R I s lt AA I T num prlntnumval 9 prlnt 9 T prlnt R 2 5 print 5 2 Treat actions as though they are terminal symbols c55363 Designing translation schemes El How to compute attribute values at each production DT L LinTtype T int TTypeinteger T real Ttypereal LL1 id L1in Lin AddtypeidentryLin L id AddtypeidentryLin El Every attribute value must be available when referenced I Sattribute of lefthand symbol computed at end of production I Iattribute of right hand symbol computed before the symbol I Sattribute of right hand symbol referenced after the symbol DT LinTtype L T int TTypeinteger Tquot real Ttypereal L L L1in Lin L1id AddtypeidentryLin id AddtypeidentryLin C55363 14 Exercise II Given the following grammar for a binary number generator SL LLBB BOl1 II Compute the value of each resulting number I Eg ifs gt gt 1101 then the value of s is 13 El Compute the contribution of each digit I Eg ifs gt gt 1101 the contribution of the four digits are 8401 respectively Steps for writing translation schemes 1 Define a set of attributes for each grammar symbol 2 Categorize each attribute as synthesized or inherited 3 For each production 31 if the lefthand symbol has a synthesized attribute define a rule for evaluating the attribute 32 if any righthand symbol has a inherited attribute define a rule for evaluating the attribute 4 Insert each attribute evaluation inside the production Inherited attributegt before the symbol synthesized attribute 22gt at end of production C55363 15 Top down translation n For each non terminal A construct a function that I Has a formal parameter for each inherited attribute of A I Returns the values of the synthesized attributes of A El The code associated with each production does the following I Save the sattribute of each token X into a variable Xx I Generate an assignment BsparseBBi1Bi2Bik for each non terminal B where Bi1Bik are values for the L attributes of B and BS is a variable to store sattributes of B I Copy the code for each action replacing references to attributes by the corresponding variables C55363 16 Top down translation Example void parseD Type t parseTO parseLt Type parseT switch currentToken case INT return TYPEINT case REAL return TYPEREAL void parseLType in SymEntry e parseID AddTypee in if currentToken COMMA parseTerminalCOMMA parseLin c55363 Bottom up evaluation of attributes El Sattributed definitions I Syntaxdirected definitions with only synthesized attributes I Can be evaluated through postorder traversal of parse tree El Synthesized attributes and bottomup parsing Keep attribute values of grammar symbols in stack Evaluate attribute values at each reduction El Inherited attribute attributes already stored in stack Each inherited attribute evaluation is treated as a dummy grammar symbol evaluation results pushed into stack for later use Configuration of LR parser sz1S1X2szXmSm aiai1an V1V2Vm states inputs values Rightsentential form X1X2Xmaiai1an Automata states sos1szSm Grammar symbols in stack X1X2Xm Synthesized attribute values of Xi Vi C55363 18 Bottom up translation in Yacc DT LinTtype L T int TTypeinteger Treal Ttyperea L L1in Lin L1id AddtypeidentryLin Lid AddtypeidentryLin 1 DT 1L T INT integer REAL real L L COMMA ID Addtype3 0 ID Addtype10 Exercise how to add C array and function declarations c55363 Types in Programming El A type is a collection of computable values I Represent concepts from problem domain 1 Accounts banks employees students I Represent different implementation of values a Integers strings floating points lists records tuples n Languages use types to I Support organization of concepts I Support consistent interpretation of values a Compile time and runtime type checking a Prevent meaningless computation 3 true Bill I Support efficient translation by compilers a Short integers require fewer bits n Access record component by a known offset in Use integer units for integer operations C55363 20 Values and Types El Basic types types of atomic values I int bool character real symbol I Values of different types 1 have different layouts u have different operations I Explicit vs implicit type conversion of values El Compound types types of compound values I List record array tuple struct ref pointer I Built from type constructors 1 int arr100 9 arr arrayint100 1 3 4 abc int int string 1 int x 9 x pointerint 1 int fint x return x 5 9 f int9int C55363 21 A Deeper View The Type System n A language supports each type by I Providing ways to introduce values of the type I Literal integers 1 23 3290 n Literal floating point numbers 35 012 n Arrays pointers structs classes type constructors I Providing ways to operate on values of the type 1 Evaluation rules equality introduction and elimination operations a Every type comes with a set of operations I Each operation defined on specific types of operands and return a specific type of value a A type error occurs if operation applied to operands outside its domain a Type declarations I Provide ways to declare types of variables I Provide ways to introduce new types userdefined types C55363 22 Type Error I When a value is misinterpreted or misused with unintended semantics a type error occurs I May cause hardware error function call x where x is not a function u may cause jump to instruction that does not contain a legal op code I May simply return incorrect value intadd3 45 1 not a hardware error a bit pattern of 45 can be interpreted as an integer u just as much an error as x above C55363 23 Relative type safety of languages El BCPL family including C and C I Not safe casts pointer arithmetic ii Algol family Pascal Ada I Almost safe I Dangling pointers u Pointers to locations that have been deallocated a No language with explicit deallocation of memory is fully type safe El Type safe languages with garbage collection I Lisp ML Smalltalk Java I Dynamically typed Lisp Smalltalk I Statically typed ML JAVA C55363 24 Compile time vs Run time Type Checking Run time type checking PerlPOETLispScheme Example in POET when evaluating each HEADx I Check to see whether X is a list I Compile time type checking CCJava ML Examplein CCJava I if a function f is declared int ffoat x a Value x must have type float I Type inference ML without type declarations automatically determine the types of variables via static program analysis n Both prevent type errors I Run time checking slows down execution I Compile time checking restricts program flexibility I Combination of compile and runtime checking a Example Java array bound check at runtime C55363 25 Static Type Systems Find Type Errors Without Running the Program n Types of variables I Each variable must have a single type a It can hold only values of this type I Types of expressions I Every expression must have a single type a It maps input values to a return value 1 It can return only values of this type a Type system I Rules for deciding types of expressions 1 These rules specify the proper usage of each operator I Accept only expressions that can be typed according to rules I Explicit vs implicit type conversion C55363 26 Type environment a Symbol table I Record information about names defined in programs 2 Types of variables and functions a Additional properties eg scope of variable I Contain information about context of program fragment I Name conflicts I The same name may represent different things in different places a Separate symbol tables for names in different scopes a Multiple layers of symbol definitions for nested scopes n Implementation of symbol tables I Hash table from strings names to properties types C55363 27 Evaluating types of expressions P D E D D D id T T char integer E literal num id E mod E D E D D id T addtypeidentry Ttype char Ttype char integer Ttype integer literal Etype char num Etype num id Etype lookupTypeidentry E1 mod E2 if E1type integer ampamp E2typeinteger Etype integer else Etype typeerror I39I1IU39U Exercise how to add support for arrays C55363 28 Example type checking with coercion n Implicit type conversion I When type mismatch happens compilers automatically convert inconsistent types into required types a 2 35 convert 2 to 20 before adding 20 with 35 ICONST Etype integer FCONST Etype real id Etype lookupidentry E1 op E2 if E1typeinteger and E2typeinteger Etype integer else if E1typeinteger and E2typereal Etypereal else if E1typereal and E2typeinteger Etypereal else if E1typereal and E2typereal Etypereal C55363 29 Exercise type Checking of statements D S D D id T char integer id E SS ifE S I while E S literal num id E mod E mmIU39U iiiiii Ilii How to add support for arrays How to add support for function calls How to support C declaration syntax What are the YACC definitions C55363 30 Solution evaluating types with arrays P D E D D D id T T char integer T num E literal num id E mod E EE P D E D D D id T addtypeidentry Ttype T char Ttype char integer Ttype integer T1num Ttype arraynumval T1type E literal Etype char num Etype num id Etype lookupTypeidentry E1 mod E2 if E1type integer ampamp E2typeinteger Etype integer else Etype typeerror E1E2 if E2type integer ampamp E1typearrayst Etype t else Etype typeerror C55363 31 Solution type Checking of statements D S D D idT char integer T num id E SS ifE S I while ES literal num id E mod E EE S id E if Etypetypeerror ampamp EquivlookuptypeidentryEtype Stype void else Stype typeerror S1 52 if S1type void Stype SZtype else Stype typeerror I if E S1 if Etype integer StypeS1type else Stypetypeerror I while E S1 if Etype integer StypeS1type else Stypetypeerror lmIU39U C55363 32 Solution type Checking with function calls P D E D DDidTTidTlist Tlist T Tlist T T char integer T num E literal num id E mod E EE EElist Elist E Elist E D T1 id Tlist addtypeidentry funT1typeTlisttype Tlist T Tlist1 Tlisttype tupleT1type Tlist1type T Tlisttype Ttype E E1 Elist if E1type funr p ampamp p Elisttype Etype r else Etype typeerror Elist E Elist1 Elisttype tupleE1type Elist1type E Elisttype Etype C55363 33 CSS363 Appendix 2 A compiler can implement some source language constructs on a given target machine in many ways Code shape refers to the differences and it has a strong impact both on the behavior of the compiled code and on the ability of the optimizer and back end to improve it Storage allocation If X is declared locally in procedure p and its value is not preserved across distinct invocations of p then assign it to procedure local storage if its value is preserved across invocations of p then assign it to procedure static storage If X is declared as globally visible then assign it to global storage If X is allocated under program control then assign it to the runtime heap A local variable can be kept in a register as long as its address is never taken its value is never used in a nested procedure and it is not passed as a callbyreference parameter to another procedure The assignment b ampa creates a second name of 61 Neither is kept in a register unless code between two references does not update a or b A value that can be kept in a register is called an unambiguous value a variable that can have more than one name is called an ambiguous value Treewalk Code Generation EXample X 7 2 y postorder walk of the parse tree lo adI X gt rl load offset loadAO rarp rl gt r2 get X using activation record pointer and offset loadI 2 gt r3 loadI y gt r4 loadAO rarp r4 gt r5 get y using activation record pointer and offset mult r3 r5 gt r6 sub r2 r6 gt r7 There are 8 register used in the above code but the number of registers can be reduced by sharing offset and variable in one register loadI gt r loadAO rarp rl gt rl loadI 2 gt r2 loadI y gt r3 loadAO rarp r3 gt r3 mult r2 r3 gt r2 sub rl r2 gt r2 There is no need to load X before 2y is computed Thus 2y is rst evaluated loadI y gt rl loadAO rarp rl gt rl loadI 2 gt r2 mult r2 r1 gt rl loadI x gt r2 loadAO rarp r2 gt r2 sub r2 r1 gt rl However evaluating the right child first is not a general solution A callbyreference parameter passed in the AR requires one additional indirection loadI x gt rl loadAI rarp rl gt r2 load r2 gt r3 Many linkage conventions pass the first few parameters in registers To evaluate a function call the compiler simply generates the calling sequence needed to invoke the function and emits the code necessary to move the returned value to a register The function may have side effects that modify the values of variables used in the expression Code motion takes an expression that yields the same result independent of the number of times a loop is executed a loop invariant computation while i lt limit2 statement does not change limit Code motion will result in the equivalent of t limit 239 while i lt t statement does not change limit ort The result of evaluation on the right hand side of an assignment as an rvlaue and the result of evaluation of the lefthand side of an assignment as an lvalue The compiler should use commutativity and associativity to improve the quality of code it generates However due to limitations in precision oatingpoint numbers on a computer represent only a subset of the real numbers and oatingpoint operations do not preserve associativity As a result compilers should not reorder oatingpoint computations unless the language definition specifically allows it Example we can assign oatingpoint values to x y and Z such that x y lt Z Z x Z and ZyZ but Zxy ltgt Z Numerical encoding and positional encoding are used to evaluate Boolean expressions Numerical encoding assigns true or false that are operands for Boolean instructions and or not Positional encoding avoids assigning an actual value to the expression until and operation requires a value Shortcircuit evaluation evaluates only as much of the expression as is required to determine the nal value It relies on two Boolean identities For all x false and x false For all x true or x true Example numerical encoding a lt b or c lt d and e lt f comp ra rb gt ccl a lt b cbriLT ccl gt L1 L2 L1 loadI true gt rl jumpI gt L3 L2 laodI false gt rl jumpI gtL3 L3 comp rc rd gt cc2 c lt d cbr LT cc2 gt L4 L5 L4 loadI true gt r2 jumpI gt L6 L5 loadI false gt r2 jumpI gtL6 L6 comp re rf gt cc3 e lt f cbriLT cc3 gt L7 L8 L7 loadI true gt r3 jumpI gtL9 L8 loadI false gt r3 jumpI gtL9 L9 and r2 r3 gt r4 or r1 r4 gt r5 Example ositional encoding with short circuit evaluation a lt b or c lt d and e lt f comp ra rb gt ccl a lt b cbriLT ccl gt L1 L2 L2 comp rc rd gt cc2 c lt d cbriLT cc2 gt L4 L5 L4 comp re rf gt cc3 e lt f cbriLT cc3 gt L1 L5 L5 loadI false gt rl JumpI gt L3 L1 loadI true gt rl jumpI gt L3 L3 nop Array Addressing One dimensional array Vlow high is declared where low and high are the vector s lower and upper bounds The V is the starting address of Vlow and w is the length of each array element To access the ith element of V we have to calculate the offset away from V that is iloww The address of Vi is then Viloww The following code loads Vi to rv loadI V gt rV get V s starting address subI 1i rlow gt rl offset multI rl rw gt r2 get offset add rV r2 gt r3 address of Vi load r3 gt r4 value of Vi The calculation can be optimized using false zero V i7 low w V iw7 low w V 7 low w iw Let VO V 7 low w this is a constant called false zero Ifthe w is 4 the above code can be optimized as follows loadI VO gt rV0 lshiftI 1i 2 gt r1 i w loadAO rV0 rl gt rv value of Vi Array Storage Layout rowmajor order C columnmajor order Fortran and indirection vectors BCPL and Java Row major order stores array elements such as Al l Al 2 A2 l A2 2 A33 Columnmajor order stores array elements such as Al l A2 l A3 l Al 2 A2 2 A3 2 Al 3 A3 3 Indirection vectors each row has its own contiguous storage Within a row elements are addressed as in a vector Referencing an Multi dimens ional Array Element Let Alowlhighl lowZ high2 be a two dimensional array and stored in row major order We want to calculate the address of Ai j The lenl highllowll and len2 high2 low2l The offset of ai j ilowllen2wjlow2w The address of Aij is A i lowllen2wjlow2w A ilowllen2wjlow2w A7 lowllen2w 7low2w ilen2w jw Let AO A 7 lowl lenZ wlow2w be the false zero The address of Aij A0 ilen2 jw The code to access Ai j is loadI AO gt rA0 false zero multI 1i len2 gt rl ilen2 add rlj gt r2 i len2 j lshiftI r2 2 gt r3 assume w 4 loadAO rA0 r3 gt rA value of Ai j Indirection vectors To access Bi j k the compiler uses the starting address ofB and i to nd the vector for the subarray Bi Then it uses the results andj to nd the address of Bi j and nally uses k and element length w to nd Bi j k loadI BO gt rB0 starting address of B More on Type Checking Type Checking done at compile time is said to be static type checking Type Checking done at run time is said to be dynamic type checking Dynamic type checking is usually performed immediately before the execution of a particular operation Dynamic type checking is usually implemented by storing a type tag in each data object that indicates the data type of the object Dynamic type checking languages include SNOBOL4 LISP APL PERL Visual BASIC Ruby and Python Dynamic type checking is more often used in interpreted languages whereas static type checking is used in compiled languages Static type checking languages include C Java ML FORTRAN PLI and Haskell Static and Dynamic Type Checking The choice between static and dynamic typing requires some trade offs Many programmers strongly favor one over the other some to the point of considering languages following the disfavored system to be unusable or crippled Static typing finds type errors reliably and at compile time This should increase the reliability of delivered program However programmers disagree over how common type errors are and thus what proportion of those bugs which are written would be caught by static typing Static typing advocates believe programs are more reliable when they have been typechecked while dynamic typing advocates point to distributed code that has proven reliable and to small bug databases The value of static typing then presumably increases as the strength of the type system is increased Advocates of languages such as ML and Haskell have suggested that almost all bugs can be considered type errors if the types used in a program are sufficiently well declared by the programmer or inferred by the compiler Static typing usually results in compiled code that executes more quickly When the compiler knows the exact data types that are in use it can produce machine code that just does the right thing Further compilers in statically typed languages can nd shortcuts more easily Dynamically typed languages such as Common Lisp use optional type declarations for optimization for this very reason Static typing makes this pervasive Staticallytyped languages which lack type inference 7 such as Javai require that programmers declare the types they intend a method or function to use This can serve as additional documentation for the program which the compiler will not permit the programmer to ignore or drift out of synchronization However a language can be statically typed without requiring declarations so this is not a consequence of static typing Static typing allows construction of libraries which are less likely to be accidentally misused by their users This can be used as an additional mechanism for communicating the intentions of the library developer A static type system constrains the use of powerful language constructs more than it constrains less powerful ones This makes powerful constructs harder to use and thus places the burden of choosing the quotright tool for the problemquot on the shoulders of the programmer who might otherwise be inclined to use the most powerful tool available Choosing overly powerful tools may cause additional performance reliability or correctness problems because there are theoretical limits on the properties that can be expected from powerful language constructs For example indiscriminate use of recursion or global variables may cause welldocumented adverse effects Dynamic typing allows constructs that would be illegal in some static type systems For example eval functions that execute arbitrary data as code are possible however the typing within that evaluated code might be static Furthermore dynamic typing accommodates transitional code and prototyping such as allowing a string to be used in place of a data structure Dynamic typing allows debuggers to be more functional in particular the debugger can modify the code arbitrarily and let the program continue to run Programmers in dynamic languages sometimes quotprogram in the debuggerquot and thus have a shorter editcompile test debug cycle However the need to use debuggers is sometimes considered as a sign of design or development process problems Dynamic typing allows compilers to run more quickly since there is less checki1g to perform and less code to revisit when something changes This too may shrink the edit compile testdebug cycle For the programmers dynamic typing is hard to be debugged because it checks data types at the time of execution of an operation operations on program execution paths that are not executed are never checked During program testing not all possible execution paths can be tested in general Any untested execution paths may still contain argument type errors and these errors may only appear that a much later time during use of the program when some unsuspecting user provides input data that takes the program down an untested path Dynamic type checking requires that type information be kept for each data object during program execution The extra storage required can be substantial Dynamic type checking must ordinarily be implemented in software since the underlying hardware seldom provides support Since the checking must be done before each execution of each operation the speed of execution of the program is likely to be greatly slowed Static type checking includes all operations that appear in any program statement Thus all possible execution paths are checked and further testing for type errors is not needed Therefore type tags on data objects at run time are not required and no dynamic type checking is needed the result is a substantial gain in efficiency of storage use and execution speed Strong and Weak Typing A strongly typed language does not allow an operation to succeed on arguments which are of the wrong type An example of the absence of strong typing is a C cast gone wrong if you cast a value in C not only is the compiler required to allow the code but the runtime is expected to allow it as well This allows C code to be compact and fast but it can make debugging more dif cult Sometimes the term safe language is used more generally for languages that do not allow nonsense to occur For example a safe language will also check array bounds which can only be done dynamically Weak typing means that types are implicitly converted or cast when they are used Example varx 5 1 var y quothiquot 2 x y39 3 Ifthe code above was written a weaklytyped language such as Visual Basic the code would run properly yielding the result quot5hiquot The number 5 is converted to a string quot5quot to make sense of the operation There are problems with such conversions in weakly typed languages though For example would the result of the following code be 9 or quot54quot varx 5 var y quot4quot X y Many say that weak typing gets programmers into bad habits because it doesn t teach them to use explicit type conversion C and PERL are weak typing Java Lisp and on are strong typing Type Conversion and Coercion If during type checking a mismatch occurs between the actual type of an argument and the expected type for that operation then two operations arise l The type mismatch may be agged as an error and an appropriate error action taken or 2 A coercion or implicit type conversion may be applied to change the type of the actual argument to the correct type Most languages provide type conversions in two ways 1 As a set of built in functions that the programmer may explicitly invoke to effect the conversion For example C provides the function at0i that converts a string object to an integer data object 2 As coercions invoked automatically in certain cases of type mismatch In Pascal if the arguments for an arithmetic operation such as are of mixed real and Dataflow analysis Iterative algorithms and SSA 5555 63 Optimization and analysis n Compilers perform optimizations to improve execution efficiency of generated code I Correctness safety a The optimized code must preserve the original meaning a Profitability the optimized code must improve code quality a Program analysis I Examines input code to ensure safety and profitability of optimizations I Compile time reasoning of runtime program behavior a Undecidable in general due to unknown program input complex control flow and pointerarray references a Conservative approximation of program runtime behavior may miss opportunities but ensure all optimizations are correct a Data flow analysis I Reason about flow of values on controlflow graphs in Example available expression analysis for global redundancy elimination I Can be used for program optimization or understanding c55363 Controlflow graph El Graphical representation of runtime control flow paths I Nodes of graph basic blocks straightline computations I Edges of graph flows of control n Useful for collecting information about computation I Detect loops remove redundant computations register allocation instruction scheduling ii Alternative CFG Each node contains a single statement i0 while ilt50 t1b2 aat1 t1b2 ii1 aat1 ii1 c55363 Building controlflow graphs Identifying basic blocks El Input a sequence of threeaddress statements El Output a list of basic blocks El Method I Determine each statement that starts a new basic block including a The first statement of the input sequence a Any statement that is the target of a goto statement I Any statement that immediately follows a goto statement I Each basic block consists of n A starting statement SO leader of the basic block a All statements following SO up to but not including the next starting statement or the end of input Starting statements I I Esoifilt5090tosl 39O C goto 52 SO slt1b2 goto 52 a a t1 51 goto 50 52 52 c55363 Building controlflow graphs n Identify all the basic blocks I Create a flow graph node for each basic block I For each basic block Bl I If Bl ends with a jump to a statement that starts basic block BZ create an edge from Bl to BZ I If Bl does not end with an unconditional jump create an edge from Bl to the basic block that immediately follows Bl in the original evaluation order c i0 C so ifi lt 50 goto 51 SO ifi lt 50 goto 51 gotosZ sltlb2 aat1 sltlb 2 E52 goto 50 c55363 Live variable analysis El A data flow analysis problem I A variable v is live at CFG point p iff there is a path from p to a use of v along which v is not redefined I At any CFG point p what variables are alive a Live variable analysis can be used in I Global register allocation 1 Dead variables no longer need to be in registers I SSA static single assignment construction a Dead variables don t need functions at CFG merge points I Useless store elimination 1 Dead variables don t need to be stored back in memory I Uninitialized variable detection 1 No variable should be alive at program entry point c55363 6 Computngdive variables A mab a Domain mab I All variables inside a function n For each basic block n let 5 pcd C qab l UEVarn r39Cd r Cd vars used before defined 39 I VarKin t18 f 17 vars defined killed by n D e E e39a Goal evaluate vars alive on 51 t Cdf entry to and at from n u39e u39e LiveOutnUmesuccnLiveInm LiveInmUEVarm o F Vab LiveOutmVarKiIm gt LiveOutn U mEsuccn m H UEVarm U G 3er LiveOutmVarKiIm c55363 Algorithm computing live variables n For each basic block n let I UEVarnvariables used before any definition in n I VarKillnvariables defined modified in n killed by n Goal evaluate names of variables alive on exit from n I LiveOutn U UEVarm U LiveOutm VarKillm mesucc n for each basic block bi compute UEVarbi and VarKillbi LiveOutbi Q for changed true changed changed false for each basic block bi old LiveOutbi LiveOutbi U UEVarm U LiveOutm VarKillm mesuccbl if LiveOutbi old changed true c55363 Solution Compu ng live variables A mab nab B pcd C qab rcd rcd A A eb18 ea17 Dsab E tcd uef uef vab F wcd mab G ncd a Domain abcdefmnpqrstuvw UE Vark Live LiveOu LiveOut var OUt t A ab mn Q abcd abcd f f cd pr abcd abcd C ab M Q abcd abcd cd f D ab es Q abcd abcd f u f E ac etu Q abcd abcd df F ab vw Q abcd abcd cd f G ab mn Q Q Q cd o c55363 Other dataflow problems Reaching definitions a Domain of analysis I Set of definition points in a procedure I A definition point cl of variable v reaches CFG point p iff there is a path from cl to p along which v is not redefined I At any CFG point p what definition points can reach p n Reaching definition analysis can be used in I Building dafaflow graphs provide info where each operand is defined I SSA static single assignment construction A representation that encodes both control and data flow of a procdure n For each basic block n let I DEDefn definition points whose variables are not redefined in n I DefKilln definitions obsured by redefinition of the same name in n cl Goal evaluate all definition points that can reach entry of n I Reachesn DEDefm Reachesm DefKillm mepredn C55363 10 More about dataflow analysis n Sources of imprecision I Unreachable control flow edges array and pointer references procedural calls In Other data flow programs I Reaching definition analysis a A definition point d of variable v reaches CFG point p iff there is a path from d to p along which v is not redefined a At any CFG point p what definition points can reach p I Very busy expression analysis a An expression e is very busy at a CFG point p if it is evaluated on every path leaving p and evaluating e at p yields the same result a At any CFG point p what expressions are very busy I Constant propagation analysis a A variablevalue pair vc is valid at a CFG point p if on every path from procedure entry to p variable v has value c a At any CFG point p what variables have constants C55363 11 The Overall Pattern II Each dataflow analysis takes the form Inputn Q if n is program entryexit A mEFlown Resultm Resultn fn Inputn I where A is n or U may vs must analysis a May analysis detect properties satisfied by at least one path U 1 Must analysis detect properties satisfied by all pathsm I Flown is either predn or succn forward vs backward flow 1 Forward flow data flow forward along controlflow edges Inputn is data entering n Result is data exiting n Inputn is Q if n is program entry 1 Backward flow data flow backward along controlflow edges Inputn is data exiting n Result is data entering n Inputn is Q if n is program exit I Function fn is the transfer function associated with each block n otherwise c55363 Iterative dataflow algorithm for each basic block bi compute Genbi and Killbi Resultbi Q for changed true changed changed false for each basic block bi old Resultbi Resultbi D or U mEpredbi or succbi Genm U Resultm Killm if Resultbi old changed true n Iterative evaluation of result sets until a fixed point is reached I Does the algorithm always terminate a If the result sets are bounded and grow monotonically then yes Otherwise no u Fixedpoint solution is independent of evaluation order I What answer does the algorithm compute 1 Unique fixedpoint solution 1 The meetoveralIpaths solution I How long does it take the algorithm to terminate a Depends on traversing order of basic blocks C55363 13 Traversing order of basic blocks a Facilitate fast convergence to the fixed point postorder n Postorder traversal I Visits as many of a nodes successors as possible before visiting the node I Used in backward dataflow analysis a Reverse postorder traversal I Visits as many of a node s predecessors as possible before visiting the node a I Used in forward dataflow Reverse anal sis I postorder y c55363 Static Single Assignment form El Data flow analysis x0 17 4 I Analyze roperties of program on control fow graph I Every analysis needs several X1ab passes over CFG 2 El Static Single Assignment form X quoty392 I Encode both controlflow and dataflow in a single IR 13 XZIX0 Intermediate Representation 413 I Two rules must hold in SSA X 39 1 Each variable definition creates a unique name X5 1 X4IX3 a Each variable use refers to a z X5q single definition I Construction of SSA n Rename redefinition of variables 1 Insert functions to merge X639 X1IX5 variable definitions where multiple swX6 paths converge C55363 15 Building maximal SSA form 1Insert functions for every basic block bi that has multiple predecessors for each variable y used or defined in bi insert function y yyy where each y in Q corresponds to a predecessor 2 Renaming Compute reaching definitions on CFG Each variable use has only one reachable definition Rename all definitions so that each defines a different name Rename all uses of variables according to its definition point n Many extraneous functions are inserted I To reduce size of SSA need a better algorithm 1 Introduce functions only where they are required C55363 16 Dominators A a 5 n For each block y nab I xdominates y ie XE Domy if pcd C qab u xappears on all paths from rcd rcd entry tOY I x strictly dominates y if eb18 ea17 U XEDomWHr dXtY D sab E tcd XE WWW y uef uef I x immediately dominates y if n x e Domy and V2 E Domy z E Domx F Vlab 1 Written as x IDomy if n Immediate dominators X39e IDomFC IDomGA G IDomDC C55363 17 Where to insert functions A moaobo n For each definition point inbasic n0a0b0 block n which Jomt ponnts in B CFG need a Q function for the pocodo q0a0b0 defined variable r0c0d0 r11C0d0 l A definition in n forces a gt function just outside the region D 0ib018 E 11ao17 of CFG that n dominates sofa tiicol g I A function must be inserted 0quote0 0 U quote at each dominance frontier of n F 3322388133 m e Wow it Voaobo 1 n dominates a predecessor of m w0c0d0 El q E predsm st n E Domq X0ezf0 2 n does not strict dominate m G r2 r0r1 m 95 Domn 39 n y0a0b0 ZO C0d0 c55363 18 Reconstructing executable from SSA in SSA form is not directly executable Processors don t support Q function evaluations Must rewrite functions into copy instructions 1 Need to split incoming edges of each function i Need to break cycles in function references by adding temporaries Rewriting made complex by transformations on SSA O ic 1 i l i1 IOI11 x1 x0 y1 I y1 yOX1 zi1 c55363 Other dataflow problems Very busy expressions a Domain of analysis I Set of expressions in a procedure I An expression e is very busy at a CFG point p if it is evaluated on every path leaving p and evaluating e at p yields the same result I At any CFG point p what expressions are very busy in If an expression e is very busy at p we can evaluate e at p and then remove all future evaluation of e I Code hoisting reduces code space but may lengthen live range of variables I For each basic block n let I UEExprn expressions used before any operands being redefined in n I Exerilln expressions whose operands are redefined in n Goal evaluate very busy expressions on exit from n I VeryBusyn U UEExprm VeryBusym Exerillm mesuccn C55363 20 Other dataflow problems Constant propagation a Domain of analysis I Set of variablevalue pairs in a procedure I A pair vc is valid at a CFG point p if on every path from procedure entry to p variable v has value c I v v has undefined value VJ v has unknown value v ci v has a constant value ci a If a variable v always has a constant value c at point p the compiler can replace uses of v at p with c I Allows specialization of code based on value cz n For each basic block n I Evaluate all variablevalue pairs valid on entry to n Constantsn FmConstantsm mepredsn where pairwise meet of varval pairs FmConstantsm varval pairs on exit from m C55363 21 Constant propagation Local sets and meetoveraIIpaths A a 5 nab pcd C qab rcd rcd eb18 ea17 D sab E tcd uef uef vab F wcd Xef yab G zcd n For each basic block n Constantsn FmConstantsm mepredsn where FmConstantsm is varval pairs on exit from m f 2 Vlcl Vlcz vc1 c1 c A v J otherwise I Compute Fminput Let m 51 52 Sk for each i 1 k If Si is X y Suppose Xc1yc2 6 input input input Xc1 xc2 If Si is y op 2 Suppose Xc1yc2zc3 6 input input input xc1 xc2 op c3 Constant if c2c3 are constants c2 0 c3 D J otherwise C55363 22 More on constant propagation n Termination of constant propagation I Iterative dataflow algorithms are guaranteed to terminate if the result sets are bounded and grow monotonically I Constant propagation does not have a bounded result set the set of all constant values is infinite I However each variablevalue pair can be updated at most twice So constant propagation is guaranteed to terminate a Using constant propagation to specialize code I Constant folding evaluate integer expressions at compile time instead of runtime I Eliminate unreachable code if a conditional test is always false the entire branch can be removed I Enable more precision in other program analysis Eg knowing the bounds of loops can eliminate superfluous reordering constraints C55363 23 Computing dominators Skip another dataflow problem El Domain of analysis I Set of basic blocks in a procedure I A basic block x dominates basic block y in CFG if x appears on all paths from entry to y I At any CFG node y what basic blocks dominate y El For each basic block n I Domn n U n Domm mEpredsn I IDomn the block in Domn with smallest RPO sequence number A mab nab E3 pcd C qab rcd rcd A A eb18 ea17 D sab E tcd uef uef vab F wcd Xef yab G zcd c55363 a Each basic block n has a single IDomn n Can use IDom relation to build a dominator tree 24 Computing dominance frontiersSkip pcd rcd A a 5 nab gt C qab rcd eb18 ea17 D sab E tcd uef uef vab F wcd Xef yab zcd for each CFG node n DFn Q for each CFG node n if n has multiple predecessors for each predecessor p of n runner p while runner I IDomn DFrunner DFrunner U n runner IDomrunner Dominance tree C55363 25 Inserting functions skip Finding g ba names Inserting Qfunctions Globals Q for each variable x for each name X E Globals Blocksx Q WorkList Blocksx for each block bi SlSZSk for each block b E WorkList VarKiII Q for each block cl in DFb forj 1 to k insert a function for x in cl let 5139 be X i Y 0D Z WorkListWorkList U cl if y i VarKiII then Globals Globals U y if z i VarKiII then Globals Globals U z VarKiII VarKiII U X Blocksx Blocksx U b C55363 26
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'