CSc 453Compilers and Systems Software16 : Intermediate Code IVDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergControl StructuresControl 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;Boolean ExpressionsShort Circuit EvaluationWith short circuit evaluation of boolean expressions we onlyevaulate as much of the expression as is necessary todetermine if the expression evaulates to true or false.Pascal does not have short-circuit evaluation. Many Pascalprogrammers have been burnt by this type of code:if p <> nil and p^.data = 32 then ...On the other hand, Modula-2 (which only supportsshort-circuit evaluation) sometimes get burnt when a functionwith side-effects doesn’t get executed:if a < t and (f(45) < 10) then ...Some languages (Ada, Algol) let the programmer decide whento use short-circuit evaluation.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?Numerical RepresentationNumerical RepresentationThe main advantage of implementing boolean expressionsusing a numerical representation is that it is very easy toimplement.We simply extend our arithmetic expressions with newoperators for AND, OR, NOT, and the relational operators.Numerical RepresentationBoolean expressions are evaluated similarly to arithmeticexpressions.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;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:Flow-of-Control RepresentationFlow-of-ControlThe value of a boolean expression is given by our position inthe program.The value of X<10 is given by position 103 (if X<10=TRUE) or101 (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:Short-Circuit EvaluationShort-Circuit CodeWhat happens if the function f has side-effects (e.g. if itchanges the value of a global variable)? Well, in such casesshort-circuit code will have different semantics from thenon-short-circuit code.In this example we use flow-of-control for the short-circuitevaluation, and numerical representation for the fullevaluation. We could have given both examples usingflow-of-control.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:Short-Circuit Code – ORIF (X > 5) OR f(34) THENDEC (X);ENDIFShort CircuitFull 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:Implementing ControlStructuresControl StructuresOne problem we’re faced with when generating code forcontrol structures, is that we generate code for the booleanexpression before we generate code for the statements. Hence,when we generate jumps from out of (a complex) booleanexpression we don’t know where to jump to.Each expression is given two slots (true & false) which arefilled in with the location to which we will jump if theexpression is true or false respectively.Control Structures. . .Each statement also has a slot next which is the location ofthe instruction following the statement. This is used when wewant to jump out of the body of a control statement.Using the next label avoids some jumps-to-jumps. Considerthe example in the slide. When we jump out of the innerIF-statement (when the expression evaluates to false) wejump to the instruction following the IF. That happens to bea jump back to the top of the WHILE-statement. Using thenext-slot fixes this.Implementing Control StructuresWe generate code for the expression before the body of thecontrol structure. How can we know where to jump?We give each expression two slots which get filled in when theappropriate 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 withthe label of the next statement when it becomes known.WHILE x<b DOIF a = 1 THENX := 1;ENDIFENDDO⇒ L1: if x >= b goto L2if a <> 1 goto L4X := 1L4: goto L1L2:Semantic Attributestrue An inherited attribute passed into booleanexpressions. 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. Holdsthe label of the statement following the current one.begin A synthesized attribute that holds the label of thebeginning of a WHILE-statement.IF StatementsWe first generate code for the expression, then the body ofthe loop.We put a label (E .true) at the beginning of the loop body.We jump to this label from every place within the expressionwhere we can determine that it is evaluated to true (theremay be several such places).Similarly, we add a label after the end of the statement(E .false) to which we jump when the statement evaluates tofalse.Control Structures –IFS ::= ’IF’ E ’THEN’ SS1’ENDIF’E.codeto E.trueto E.falseS.codeE.true:E.false:Example:IF (X > 5) THENDEC (X);ENDIF⇓100: IF X > 5 GOTO 102 (=E.true)101: GOTO 103 (=E.false)102: X := X - 1;103:Control Structures –IFThe implementation is encoded into these attribute evaluationrules.We start by creating the new label E .true.Then we set E.false to be the same label as S .next. Thismeans that if the expression evaluates to false, then we willjump to the statement immediately following theIF-statement, which is exactly what we want to do.Control Structures –IF. . .The next rule (S1.next := S.next;) says that: “if weshould need to jump out of the body of the