Homework
COP-5621, Spring 2024

Due 03/13

Read The Task of the Referee (alternative link). Note one or two new things you learned about academic paper reading or something you found surprising or interesting.

Due 03/11

The code generation scheme described in class always loads variables from memory into a register whenever used and always stores the value back into memory right after assignment. Sketch an algorithm that could help reduce the amount of loads and/or stores caused by this approach.

Due 03/04 03/06

Pick a machine language you are familiar with (x86, arm, mips, etc.). What assembly instructions might correspond to the five While3Addr instructions in our intermediate representation?

Show an example translation a simple While3Addr program in assembly code.

Due 02/26

Read Program Analysis Section 4.3 and 4.4.

How do local and global analyses differ in the handling of data-flow facts?

Due 02/21

Read Program Analysis Section 4.1 and 4.2 and do Exercises 1 and 2.

Due 02/19

Continue optimizing the in-class example by applying another round of copy propagation and dead code elimination. Show (1) the states for available expressions and the line(s) rewritten, (2) the states for live variables on the new program and the line(s) eliminated, and finally (3) the optimized program.

y := inparam
x := 10
_t1 := y + x
outparam := _t1

Due 02/14

What analysis might a dead code elimination optimization need? Sketch a rough idea for how the analysis would work.

Due 02/12

In your program from 02/05, circle the subgraphs that correspond the control-flow constructs in the While source language and draw the control tree (which is the inferred hierarchy of language constructs, akin to the AST).

Due 02/07

Draw a control-flow graph for the While3Addr version of the Fibonacci number program from 01/22.

Due 02/05

What is a basic block and what part does it play in a control-flow graph?

Due 01/31

What is backpatching in the context of generating code in a compiler and why might it be useful?

Due 01/29

Write a small While program that uses at least one control-flow construct.

Create a parse tree for the program.

Create a While3Addr version by traversing the tree and applying the translation rules.

Due 01/24

Read Program Analysis Sections 2.2, 3.1.2, 3.1.3.

Write a While3Addr version of your Fibonacci solution from the previous homework.

How might you demonstrate that both the While and While3Addr versions are equivalent?

Due 01/22 Write a WHILE program that computes the inparam Fibonacci number and stores it in outparam, e.g, (inparam=1, outparam=1), (inparam=2, outparam=1), (inparam=6, outparam=8)

Draw the program's parse tree or write its derivation from the (abstract) WHILE grammar.

Due 01/17

Read Program Analysis Sections 2.1 and 3.1.1

Derive the value of the following program using the proof rules for big-step semantics with the starting state \(\{x \mapsto 8\}\).

if x < 10 then x = x + 1
else x = 1