Exercises 09

Material for Exercise Session

Translate manually into bytecodes using the techniques in Compilation as Tree Transformation

int activityLevel
boolean action(int signals, boolean objects, int smart, int pretty) {
  if ((signals > 5 || !objects) && smart + 2*pretty > 10) {
    return true;
  } else {
    return false;



Please do these exercises individually, not in groups.

Question 1

Consider the example from Compiling While. Write a version of the translation that does not use any local variable slots, only uses stack.

Check that your translation works by generating the code using cafebabe.

Question 2

Consider Compiling While. Write a different translation of while that, for each loop iteration generates only one conditional branch and no goto statements. Your translation should result in code in which the number of executed goto statements when the loop finishes does not depend on how many times the loop iterates (it can execute a goto statement at most once before or after looping, but not during looping).

You can assume for the purpose of this question that the boolean condition of the loop is simply a local boolean variable (and thus its translation does not introduce any branches).

Question 3

Mr. Chris Omer-Piler works in the JaWeb startup company as a compiler hacker for a language that generates JVM byte codes.

To improve his translation, he decides to change the Convention on Booleans, allowing any integer as the value of a boolean variable and interpreting any non-zero integer as 'true'. He then replaces in his code generator each

if_cmpCOND Label

with the sequence


ifCOND Label

In other words, replace comparison between two 'int' values by subtracting the values and comparing the result with zero.

The idea of this translation comes because we have that, for example,

    x > y

is equivalent to

   x - y > 0

for unbounded integers $x,y$, and similarly for other conditions. Therefore, instead of

if_cmple Label

he emits

ifle Label

He similarly changes code generation for other comparison operations.

Chris deploys his compiler, which seems to work well: customers world-wide rapidly adopt it to write scripts and server code. However, an important customer reports strange behavior in one of their applications. After hours of analysis, Chris traces the problem to the program containing the following code:

  x = readIntWebForm();
  if (x < 0 || x <= 100) {
    while (x > 1) {
        x = x - 10;

For queries coming from some suspicious IP addresses, the code appears to be taking extremely long time to execute and slows down the server substantially.

Chris reasons that, when the body of the if statement executes, then either x is less then zero and loop terminates immediately, or x is at most 100 and it executes at most 10 iterations, which should not cause a performance problem.

Can you help Chris identify the problem in the code above (and thus save his reputation as the JaWeb compiler hacker)?