CSc 453 — Compilers and Systems Software16 : Intermediate Code IVChristian CollbergDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergOctober 18, 20091Control Structures2 Control StructuresIF E THENSENDIFWHILE E DOSENDDO;REPEATSUNTIL E;LOOPSENDLOOP;IF E THEN SELSE SENDIF;IF E1THEN S1ELSIF E2THEN S2ELSE S3ENDIF<Name>: LOOP S1;EXIT <Name> WHEN E;S2;ENDLOOP;FOR i:INT := E1TO E2BY E3DOSENDFOR;FOR i IN [E1, E2, · · · ] DOSENDFOR;3Boolean Expressions4 Short Circuit Evaluation• With short circuit evaluation of boolean expressions we only evaulate as much of the expression as isnecessary to determine if the expression evaulates to true or false.• Pascal does not have short-circuit evaluation. Many Pascal programmers have been burnt by this typeof code:if p <> nil and p^.data = 32 then ...1• On the other hand, Modula-2 (which only supports short-circuit evaluation) sometimes get burnt whena function with side-effects doesn’t get executed:if a < t and (f(45) < 10) then ...• Some languages (Ada, Algol) let the programmer decide when to use short-circuit evaluation.5 Boolean ExpressionsE ::= E ’OR’ E | E ’AND’ E | ’NOT’ E |’(’E ’)’ |E relop E |’true’ | ’false’relop ::= ’<’ | ’<=’ | ’=’ | ’<>’ | ’>=’ | ’>’Language Design Space:• Short-circuit evaluation of AND & OR?if p <> nil and p^.data = 32 then ...if a < t or (f(45) < 23) then ...Compiler Design Space:• Numerical or flow-of-control representation?6Numerical Representation7 Numerical Representation• The main advantage of implementing boolean expressions using a numerical representation is that itis very easy to implement.• We simply extend our arithmetic expressions with new operators for AND, OR, NOT, and the relationaloperators.8 Numerical Representation• Boolean expressions are evaluated similarly to arithmetic expressions.Operators:FALSE ≡ 0TRUE ≡ any value > 0x AND y ≡ x ∗ yx OR y ≡ x + yNOT x ≡ IF x = 0 THEN t := 1ELSE t := 0;x < y ≡ IF x < y THEN t := 1ELSE t := 0;29 Numerical Representation. . .B := X < 10;WHILE X > 5 DODEC (X);ENDDO100:IF X < 10 GOTO 103101:B := 0102:GOTO 104103:B := 1104:IF X > 5 GOTO 107105:t1:= 0106:GOTO 108107:t1:= 1108:IF t1= 0 GOTO 111109:X := X - 1;110:GOTO 104111:10Flow-of-Control Representation11 Flow-of-Control• The value of a boolean expression is given by our position in the program.• The value of X<10 is given by position 103 (if X<10=TRUE) or 101 (if X<10=TRUE).B := X < 10;WHILE X > 5 DODEC (X);ENDDO100:IF X < 10 GOTO 103101:B := 0102:GOTO 104103:B := 1104:IF X <= 5 GOTO 107105:X := X - 1;106:GOTO 104107:12Short-Circuit Evaluation13 Short-Circuit Code• What happens if the function f has side-effects (e.g. if it changes the value of a global variable)? Well,in such cases short-circuit code will have different semantics from the non-short-circuit code.• In this example we use flow-of-control for the short-circuit evaluation, and numerical representationfor the full evaluation. We could have given both examples using flow-of-control.314 Short-Circuit Code – ANDIF (X > 5) AND f(34) THENDEC (X);ENDIFShort CircuitFull Evaluation100:IF X <= 5 GOTO 103101:IF NOT f(34) GOTO 103102:X := X - 1;103:100:t1:= X > 5;101:t2:= f(34);102:t3:= t1AND t2;103:IF NOT t3GOTO 105104:X := X - 1;105:15 Short-Circuit Code – ORIF (X > 5) OR f(34) THENDEC (X);ENDIFShort Circuit Full Evaluation100:IF X > 5 GOTO 103101:IF f(34) GOTO 103102:GOTO 104103:X := X - 1;104:100:t1:= X > 5;101:t2:= f(34);102:t3:= t1OR t2;103:IF NOT t3GOTO 105104:X := X - 1;105:16Implementing Control Structures17 Control Structures• One problem we’re faced with when generating code for control structures, is that we generate code forthe boolean expression before we generate code for the statements. Hence, when we generate jumpsfrom out of (a complex) boolean expression we don’t know where to jump to.• Each expression is given two slots (true & false) which are filled in with the location to which wewill jump if the expression is true or false respectively.18 Control Structures. . .• Each statement also has a slot next which is the location of the instruction following the statement.This is used when we want to jump out of the body of a control statement.• Using the next label avoids some jumps-to-jumps. Consider the example in the slide. When we jumpout of the inner IF-statement (when the expression evaluates to false) we jump to the instructionfollowing the IF. That happens to be a jump back to the top of the WHILE-statement. Using thenext-slot fixes this.419 Implementing Control Structures• We generate code for the expression before the body of the control structure. How can we know whereto jump?• We give each expression two slots which get filled in when the appropriate label is known:true (false) Where to jump to when the expression is true (false).• We give each statement one slot next which gets filled with the label of the next statement when itbecomes known.WHILE x<b DOIF a = 1 THENX := 1;ENDIFENDDO⇒ L1: if x >= b goto L2if a <> 1 goto L4X := 1L4: goto L1L2:20 Semantic Attributestrue An inherited attribute passed into boolean expressions. Holds the label to which the expressionshould jump if it evaluates to true.false Where to jump to if the expression evaluates to false.next An inherited attribute passed into statements. Holds the label of the statement following the currentone.begin A synthesized attribute that holds the label of the beginning of a WHILE-statement.21 IF Statements• We first generate code for the expression, then the body of the loop.• We put a label (E.true) at the beginning of the loop body. We jump to this label from every placewithin the expression where we can determine that it is evaluated to true (there may be several suchplaces).• Similarly, we add a label after the end of the statement (E.false) to which we jump when the statementevaluates to false.22 Control Structures –IFS ::= ’IF’ E ’THEN’ SS1’ENDIF’E.codeto E.trueto E.falseS.codeE.true:E.false:Example:5IF (X > 5) THENDEC (X);ENDIF⇓100: IF X > 5 GOTO 102 (=E.true)101: GOTO 103 (=E.false)102: X := X - 1;103:23 Control Structures –IF• The implementation is encoded into these attribute evaluation rules.• We start by creating the new label E.true.• Then we set E.false to be the same label as S.next. This means that if the expression evaluatesto false, then we will jump