Live Variables

Work on this exercise locally

This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module3-static-analysis/exercises/live-variables

6. Exercise 4: Live Variables (14 tests)

Goal: Implement a backward may-analysis that tracks which variables may be used in the future (are "live") at each program point.

Time: ~25 minutes

Files to edit:

exercises/live-variables/starter/live_variables.ml -- use/def extraction + fixpoint

Also provided (read-only):

exercises/live-variables/starter/comparison.ml -- side-by-side comparison of reaching defs vs. live variables (reference reading)

The example program

         B1: def={a,b}, use={}
        /  \
       v    v
      B2    B3
 def={a,c}  def={b,c}
 use={a}    use={b}
       \   /
        v v
         B4: def={}, use={a,b,c}

Transfer function (backward!)

IN[B]  = use[B] U (OUT[B] - def[B])
OUT[B] = U{ IN[S] | S is a successor of B }

use[B]: variables read in B before being (re)defined
def[B]: variables assigned/written in B

What to implement (in order)

#	Function	Hint
1	`compute_use (label, defs, uses)`	Return `StringSet.of_list uses`
2	`compute_def (label, defs, uses)`	Return `StringSet.of_list defs`
3	`analyze blocks`	Backward iterative fixpoint: initialize IN[B] = {} for all B, merge over successors to get OUT, apply transfer to get IN, repeat until stable

Run tests

dune runtest modules/module3-static-analysis/exercises/live-variables/

Starter output: EEEEEEEEEEEEEE

All 14 tests error because every function is a TODO. The tests include 3 compute_use tests, 2 compute_def tests, 6 diamond-CFG analysis tests, and 3 loop analysis tests. Start with compute_use and compute_def (straightforward one-liners), then tackle analyze.

Key difference from Exercise 3: This is a backward analysis. You merge over successors (not predecessors) to compute OUT, then apply the transfer function to compute IN. The fixpoint check is on IN values (not OUT).

Hint for analyze: The blocks are given as (label, defined_vars, used_vars, successor_labels) tuples. Build a StringMap keyed by label. In each iteration, compute OUT[B] by unioning the IN values of B's successors, then compute IN[B] via the transfer function. Iterate until no IN set changes.

Starter Files

starter

Test Files

tests

starter/comparison.ml

Read-only

Loading editor...