CSC362 2004S, Class 36: Translating Loops

Admin:
* Questions on the project?
* May miss class on Wednesday.  Expect email tomorrow.
* No grading.

Overview:
* Translating case statements.
* Translating while loops.
* Translating repeat loops.
* Translating for loops.

Review (1):
* Goal: Associate a "code" attribute with many nodes in the tree
* Form of case statements
	CASE <expression> OF
	  <constant>: <statement>;
	  <constant>,<constant>: <statement>
	END
* Meaning of case statement
  * Evaluate the expression
  * Find the matching value
  * Execute the corresponding statement
* Side note: Empty label:statement pairs permitted so that the user can use extra semicolons
* Multiple labels permitted
* Statements can be a compound statement
* What happens if expression matches none of the labels?
  * Fall through (what you are permitted to do)
  * Permit or require a default, such as else: or default: (changes syntax)
  * It is an error to write a case statement in which the expression may take on a value other than those listed. (What Wirth says.)
* What happens if expression matches more than one of the labels?
	case x of 
	  1: ...
	  1: ...
	end
  * Execute only the first one 
  * Execute whichever is easiest (what you are permitted to do)
  * Execute all the matching ones (dangerous)
  * Disallow at compile time (Best idea; Not required)

How do we translate a case statement?
	CASE <expression> OF
	  <constant>: <statement>;
	  <constant>,<constant>: <statement>
	END
1. Generate the code for the expression
   exp.code and exp.loc
2. Translate each <constant>: <statement> as
  if (exp.loc == <constant>) then <statement> else ...
   Translate each <constant>,<constant>: statement as
  if (exp.loc == <constant>0) or (exp.loc) == <constant>1 ...
3. Shove all the code together

Advantages:
* Easy and straightforward
* Gives an immediate solution to two case labels having the same value
Disadvantages:
* Seems to be extra work in translation
* Possibly lots of jumps (since we do a jump in each if) (Solution: Do variant translation)
* Potentially slow (O(#ofentries))

Alternate solution: Jump table
* Generate code for the expression
* Generate a label and code for each statement 
  * Add JUMP END_OF_CASE to each statement
* Generate an array of the appropriate size.  Fill in the <constant>th entry with the corresponding label
* code for expression + JUMP ARRAY[exp.loc] + code for statements + END_OF_CASE
Advantages:
* Fast/few jumps
Disadvantages: 
* Requires every label be filled in (solution: Fill the rest of the array with END_OF_CASE)
* Potentially space-consuming if you have few values in a large range
* What if the expression can be an integer?  That's a *big* array?
  Insert (if (exp.loc < smallest) or (exp.loc > largest) goto END_OF_CASE)

When the numbers are not arranged in a small group, the optimal solution is ... a binary search tree

case x of
  1..1000: ...
end
i
The bad translation
  JMEQ x 1: ...
  JMEQ x 2: ...
  JMEQ x 3: ...
  JMEQ x 4: ...

Review:
* Two mechanisms for translating Booleans
  * As expressions (with location)
  * Using desired jump destinations
* The latter is more efficient, but more complicated.

Translating WHILE loops
	<while_statement> ::= WHILE <expression> DO <statement>
1. Translate the expression
2. Translate the statement
3. <while>.code =
  WHILE:
    <exp>.code
    JZ <exp.loc> END_WHILE
    <statement>.code
    JUMP WHILE
  END_WHILE:
 
Suppose we were using the form of translation in which we pass a true label and a false label to the translate procedurea
  WHILE:
    translate(<exp>, BODY, END_WHILE) 
  BODY:
    <statement>.code
    JUMP WHILE
  END_WHILE:
                                                                                
<repeat_statement> ::= REPEAT <statement> { SEMICOLON <statement> }
                       UNTIL <expression>

  REPEAT:
    <statement>0.code
    <statement>1.code
    ...
    <statements>n.code
    <exp>.code
    JZ <exp>.loc REPEAT
  END_REPEAT:

Saves one jump or test on each repetition (fairly inconsequential)

<for_statement> ::= FOR <identifier> BECOMES
                    <expression>0 <direction> <expression>1
                    DO <statement>

meaning question: How often are <expression>0 and <expression>1 evaluated?
* Once?  <expression>0 <expression>1
* Once per repetition? 

	  <expression>0.code
	  <expression>1.code
	  MOVE <expression>0.loc <identifier>.loc
	BODY:
	  <statement>.code
	  JEQ <identifier>.loc <expression>1.loc END_FOR
	  IADD <identifier>.loc 1 -> <identifier>loc
          JUMP BODY
	END_FOR:

	for i := MAXINT-2 to MAXINT do
	   ...