CSC 355 Notes
Tuesday Nov 22, 2005 

Topics:

• Code Generation
  • Intermediate Forms
  • Transformational Attribute Grammars
  • Optimization

Setting the stage

• scanner
• parser
• static analysis
• front-end : scanner/parser part of the compiler
• back-end : target language code generation

Intermediate Languages

• representation of the program
• representation of source program from which target translation can be generated
  • internal representation
  • limited formats --> "simple" language compared to source
• could go directly to target language
  • but this is rarely done
• benefits of intermediate form
  • retargeting : combine front/back ends to facilitate different machines and/or language combinations
  • optimization opportunities : study structures to produce better code
• syntax directed techniques used here
• intermediate representation must be expressive enough but should not be too complicated
• regular structure of an intermediate form helps to make if easier to use for translation or optimization

Examples of intermediate representations

• abstract syntax trees
  • graphical representation of structure
  • you have of course read about ASTs by now; we have even drawn them
• postfix
  • can be produced by post-order traversal of syntax tree
• three-address code
• P-code

Three-address code

• sequence of statements ; more limited form than a HLL
  • sort of like assembly really, but not tied to a particular platform
• basic statements will take forms such as
  • a : = b op c  // Assignment statement
    • may be a unary and binary operators or simply assignment from one variable to another
    • b and c may be variables or literals
  • goto L // Unconditional jump statements
    • jump statement ; jump to a defined label location
  • if a relop b goto L  // Conditional jump statement
    • if the condition is true, execute the jump statement; if the condition is not satisfied, simply continue with the next statement
• procedure calls, parameter passing, pointers, arrays, ...
  • intermediate representation must have enough power to represent the computations that are expressed in the source language

Observations

• expressions are limited in size
  • can't do w := a+b+c*d-e  as a single expressions
  • t1  := a + b
  • t2 := c * d
  • t3 = t1 + t2
  • t4 = t3 - e
• store results in temporaries to accumulate the actual value of a more complex expression
  • managing these temps becomes another problem on its own
  • for now, no concern for re-using or optimizing their use
  • just get a new one each time
•  

Some implementation details

• how to store & manipulate the 3-address code during generation
  • textual representation is difficult to work with
• string concatenation can be very expensive
  • allocate memory
  • copy all characters to new string
  • ...
• but notice that there is a limited shape to the instructions
•  consider now a record for each instruction

  • op

    v1

    v2

    v3
• assume now that the "result" is always a temporary
• can use the "instructions" as the temporaries
• no need to manage temp names, which don't really matter anyway

Translation into 3-address code

• define a translation scheme to map our source language constructs into target language images
  • we have already done several syntax directed translations, so this one should not have too many surprises
  • build the code in a bottom-up manner
  • assume the program has been verified to be syntactically correct
• attributes
  • maintain properties, associated with the nonterminals, to produce the 3-address code
  • code, labels, temps, etc.
  • other attributes are of course already in place for type, scope, etc. issues
• consider a language construct such as an assignment statement;   id := E
  • informally, we think of this statements as: Evaluate the expression E and then assign the result value into variable id;    x := 5 + 3;   Evaluate the expression (5+3) to find integer value 8 and assign that value into integer variable x
  • thus, the general template for the translation will take a similar form

  • Code to evaluate E
    Result in temp t
    id := t

• attributes we will use
  • code : the 3-address code image of the construct embodied by a nonterminal
  • res : the location (temp) that contains the result of the code
    • making the assumption (design choice) that all code will end with a value in a single location
    • this location becomes the "glue" to allow you to put pieces together

Simple expressions

• S --> id := E	S.code = E.code & id.res := E.res
  E --> E + E	E.res = new_temp
  	E.code = E1.code & E2.code & E.res := E1.res + E2.res
  E --> id	E.res = id.res
  	E.code = ""

• now continue the same technique to add statements such as control flow instructions to the language
  • if-statements, loops
  • need to manage the labels since jump instructions need to be generated
  • think back to ASM code and flowcharts to get a good idea of how this will work

Daily Assignment - work through in class

• define a translation for the following code fragment:

  • s = 0
    x = 1
    while x < 5
      s = s + x
      x = x + 1
    y = 7

• first step may be to draw a flowchart [ on board ]
  • notice the key elements that control the flow for the fragment as well as the statements that do the work
• now think about the 3-address code to carry out each component
  • assignment statements
    • easy since I only used short expressions
    • they look about the same
• put it all together

  •   t1 := 0
      s := t1
      t2 := 1
      x := t2
    L1: if x < 5 goto L2true
      goto L2false
    L2true:
      t3 := s + x
      s := t3
      t4 := x + 1
      x := t4
      goto L1
    L2false:
      t5 := 7
      y := t5

• our ultimate goal is to be able to translate ANY while loop into 3-address code
• need a template/pattern approach
• what is common, what is custom, ...
• take a general flowchart and identify the common components
• custom information will be synthesized in the components and combined as constructs are formed

While loops

• a

• S --> while E to S	S.start = new_label
  	S.end = new_label
  	S.code = S.start : & E.code & if E.res = 0 goto S.end & S1.code & goto S.start & S.end :

•  

Source language

• continue for other types of statements and expressions
  • loops
  • conditional statements
  • Boolean expressions
  • procedures
• match semantics/behavior of generated code to that of the language
  • short-circuit evaluation - for instance
• loops and conditionals are fairly similar
  • manage labels and jumps
• remember, we are implementing the source language, so the specification rules must be obeyed to have a proper/correct implementation
• this implies, of course, that you know and understand the rules for the language

Consider types and type conversions

• Basic rules for E--> E+E if we include basic types and conversions

• E.res := new_temp
  if E1.type = integer and E2.type = integer then
   begin
     code(E.res := E1.res Int+ E2.res)
     E.type := integer
   end
  else if E1.type = real and E2.type = real then
   begin
     code(E.res := E1.res Real+ E2.res)
     E.type := real
   end
  else if E1.type = integer and E2.type = real then
   begin
     z := newtemp;
     code ( z := int_to_real E1.res)
     code(E.res := z Real+ E2.res)
     E.type := real
   end
  else if E1.type = real and E2.type = integer then
   begin
     z := newtemp;
     code ( z := int_to_real E2.res)
     code(E.res := E1.res Real+ z)
     E.type := real
   end
  else 
   E.type := type_error
   

• That's not so bad
• a = b + c * d  [ a, b: real   c, d: integer ]

• t1 := c Int* d
  t2 := Int2Real t1
  t3 := b Real+ t2
  a := t3

Boolean expressions

• data values true and false
• operators AND, OR, NOT
• also recall: relational expressions produce Boolean results
• in C++, for instance, Booleans can be coerced to a numeric value too
  • 0 : false
  • non-0 : true

Numeric translation of Boolean expressions

• relational expressions produce value 0 or 1
• logical operators work on the numeric values
• a < b

  • if a < b
      r := 1
    else
      r := 0

• a<b or c <d and e < f

• A	if a < b goto D
  B	t1 := 0
  C	goto E
  D	t1 := 1
  E	if c < d goto H
  F	t2 := 0
  G	goto I
  H	t2 := 1
  I	if e < f goto L
  J	t3 := 0
  K	goto M
  L	t3 := 1
  M	t4 := t2 and t3
  N	t5 := t1 or t4

• At the end, t5 will contain a 0 or 1 to indicate the value of the original expression
•