/** Computes the max of two integer values */
public int max(int i, int j) {
  int res;
  res = (i > j ? i : j);
  return res;
}

Possible corresponding bytecode:

0: iload_1
1: iload_2
2: if_icmple 5
3: iload_1
4: goto 6
5: iload_2
6: istore_3
7: iload_3
8: ireturn

Notes:

• Instructions 6 and 7 just store the result in res and re-load it to return it.
• The comparison operator used is , the negation of . We could also generate similar code using the bytecode if_icmpgt instead.
• In practice, jump addresses such as the ones given after goto and if_icmple are not encoded as absolute values, but as offsets.

The JVM requires that code blocks be annotated with the maximum stack height they can produce — and therefore implictly requires that this number be computable statically. This value is computed by first computing the stack height at every program point, then taking the maximum. The stack height should be fixed at any given point (ie. it should not depend on the execution path that led to that point). Here is the previous example annotated with stack heights (note that numbers indicate the height before the execution of the instructions):

0: iload_1       -- 0
1: iload_2       -- 1
2: if_icmple 5   -- 2
3: iload_1       -- 0
4: goto 6        -- 1
5: iload_2       -- 0 (because of instruction 2)
6: istore_3      -- 1 (because of instructions 4 and 5)
7: iload_3       -- 0
8: ireturn       -- 1

Notice how both paths leading to instruction 6 also lead to the same stack height. If you want to convince yourself that the invariance of the stack height at a given point must hold, think about loops:

/** An inefficient way of computing 47 - 5 */
public int foo() {
  int i = 0;
  int j = 47;
  while(i < 5) {
    ++i;
    --j;
  }
}

 0: iconst_0      -- 0
 1: istore_1      -- 1
 2: bipush 47     -- 0
 3: istore_2      -- 1
 4: iload_1       -- 0 (because of 3 and 11)
 5: iconst_5      -- 1
 6: if_icmpge 12  -- 2
 7: iinc 1 1      -- 0
10: iinc 2 -1     -- 0
11: goto 4        -- 0
12: iload_2       -- 0 (because of 6 and 11)
13: ireturn       -- 1

Notes:

• An unstable stack height at point 4 or 12 could lead to a stack overflow or starvation.
• Note that iinc doesn't increment the value on top of the stack by 1, as incorrectly stated stated during the exercise session. See iinc.

Read the description of the iinc instruction of the Java virtual machine.

Consider modifying VM for Expressions by adding another case class, Iinc, extending Instruction and taking two Int values as constructors: the index of local variable to increment, and an increment offset (for simplicity, assume that they are both Int values).

Write down the missing lines in the 'step' function to correctly implement the meaning of Iinc.

Use notation described in Translation Correctness for Expressions and Accessing and Storing Variables to compute the translation of assignment

using (in some order) bipush,iadd,iload,istore instructions. Assume a global mapping 'index' that maps variable names to local variable slots.

Show the translation of the same assignment statement but this time using the iinc instruction.

Adapt the notation in Translation Correctness for Expressions and Accessing and Storing Variables to describe 1) the translation and 2) the execution (the run function), of assignment statements. You will need to introduce local variables as an argument of 'run', in addition to stack and instruction sequence. Show that the execution of the translation in Part b) and the execution in Part c) have the same effect on the stack and on the local variables. In other words, prove that code generated using iadd in b) can be correctly replaced by the code generated in part c), because 'run' function produces the same result for both cases.