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/reaching-definitions

Reaching Definitions

5. Exercise 3: Reaching Definitions (15 tests)

Goal: Implement a forward may-analysis that tracks which variable definitions can reach each program point.

Time: ~25 minutes

Files to edit:

  • exercises/reaching-definitions/starter/reaching_definitions.ml -- gen/kill sets + fixpoint

Also provided (read-only):

  • exercises/reaching-definitions/starter/example_program.ml -- the test program
  • exercises/reaching-definitions/starter/worksheet.md -- guided walkthrough

The example program

    B1: a = 1  (d1)           CFG:   B1
        b = 2  (d2)                 / \
                                   v   v
    B2: a = 3  (d3)              B2    B3
        c = a  (d4)               \   /
                                   v v
    B3: b = 4  (d5)               B4
        c = b  (d6)

    B4: print(a, b, c)

Transfer function

OUT[B] = gen[B] U (IN[B] - kill[B])
IN[B]  = U{ OUT[P] | P is a predecessor of B }
  • gen[B]: definitions created in block B (last def of each variable in B)
  • kill[B]: definitions killed by B (other defs of variables that B defines)

What to implement (in order)

#FunctionHint
1compute_gen defs blockFilter defs by block, keep only the last definition per variable, return their def_ids as a StringSet
2compute_kill defs blockFor each variable defined in this block, find all OTHER definitions of that variable from any block; exclude gen[B]
3analyze cfg defsIterative fixpoint: initialize OUT[B] = {} for all B, repeat merge + transfer until stable

Run tests

dune runtest modules/module3-static-analysis/exercises/reaching-definitions/

Starter output: EEEEEEEEEEEEEEE

All 15 tests error because every function is still a TODO stub. The tests are organized in groups: 4 gen tests, 4 kill tests, 7 analyze tests. Implement compute_gen first to get the first 4 passing, then compute_kill, then analyze.

Hint for compute_gen: Filter defs to those in the given block. If a variable has multiple definitions in the same block, only the last one counts. Use List.filter and List.rev or fold from right to left.

Hint for analyze: The CFG is given as (label, predecessor_labels) pairs (not full block objects). Use StringMap to store the OUT set for each block and iterate until no OUT set changes.