Exam prep/practice questions

1. General question style to expect:
   apply the following algorithm (probably one not covered by a previous quiz question) to the following ...

2. Suppose that your CFG rules currently supported expressions using negation (e.g. -x) and subtraction (e.g. x-y), but you now need to add support for post-decrement (e.g. x--) and pre-decrement (e.g. --x).
   Discuss how much more (or how much less) complicated (a) your scanner, and (b) your parser will be if whitespace is mandatory between operators, as opposed to being optional between operators.

3. How would your design priorities and expectations differ if you were developing a compiler for a general purpose language like C++ as compared to developing a compiler for a visual/graphical educational programming language like Snap.

4. Of the optimization techniques we've discussed, which ones would be most applicable to this year's compiler course project? Justify your answer.

5. The Wanderful language specifications (prior to the bonus lab) did not contain any mechanism for user input. Given that, would it be feasible for a compiler to determine the output that would be produced by a valid Wanderful program, and simply generate the program output directly? Why or why not?

6. Suppose that in a HLL like C we had a loop copying elements of an array of (32-bit) ints to an array of (64-bit) longs. Provide a pseudo-assembly algorithm to do this efficiently. (Provide a very brief description of each of the core assembly language instructions you use.)

7. Suppose a system has the following data storage sizes and alignment rules:
   • chars take one byte each and can be stored at any address
   • ints take four bytes and can be stored at any address divisible by four
   • longs take eight bytes and can be stored at any address divisible by eight
   If the compiler stores variables in the order in which they were declared, and the programmer wants to declare a total of two chars, an int, and a long, what is the worst order the programmer can declare them in w.r.t. the total amount of memory needed? How mucn memory would be used (including padding)?

8. Given the following expression (some arithmetic expression of variables and constants here), translate it into (i) one-address (stack) code, (ii) three-address code with naming in an SSA form

9. Describe, as accurately as you can, the relationship between the size of a source code program (in number of tokens) and the size of (i) its parse tree, (ii) its abstract syntax tree.

10. Given the following code segment (some chunk of low-level pseudo-code): (i) identify the basic blocks within the segment by the first and last statement in each block, (ii) give a list of the directed edges in the control flow graph for the segment

11. Languages that support 'goto' statements often only restrict the destination for the goto to labels within the same subroutine. If you were tasked with adding such a restriction to a general purpose language, would you attempt to make it part of the context free grammar, or part of the context sensitive checking? Why?

12. In the two code segments below, the first results in variable a having value 4 and variable b having value 5, while the second produces a compilation error (lvalue required for LHS of assignment). Use an SSA translation of the code segments to explain the difference in behaviour.

    // segment 1 int a=0, b=4; ++a = b++; // segment 2 int a=0, b=4; a++ = b++;

13. For the expression a+b+c-d+e+f+g+h+i:
    (i) assuming normal precedence/associativey rules and that no tree-balancing is performed, how many registers would be needed for a basic tree-walk of the expression (show your work/justify your answer)
    (ii) how many registers would be needed if tree-balancing is performed (show your work/justify your answer)

14. For the code segment below, which of the following loop optimization techniques are applicable: unrolling, splitting, moving invariants and why. Show what the revised loop would look like following your chosen revisions.

    void f(float arr1[], float arr2[], int size) { float prev = arr1[0]; float curr = arr1[1]; float next = arr1[2]; int i = 2; while (i < size) { arr2[i] = (next + curr + prev) / 3; prev = curr; curr = next; i++; next = arr1[i]; } }

15. For each node, n, in the control flow graph below:
    (i) list the node (if any) that is the immediate dominator of n
    (ii) list the nodes that n dominates
    (iii) list the nodes in n's dominance frontier

16. Programmers generally attempt to avoid writing "useless" code. Explain which of the code transformations and optimizations we've discussed might generate "useless" code and how.