3. Exercise 1: CFG Construction (14 tests)

Goal: Build control flow graphs from AST statement lists. Implement the core CFG operations (add edges, query predecessors/successors) and three CFG construction patterns (sequential, if-else diamond, while loop with back edge).

Time: ~30 minutes

Files to edit:

• exercises/cfg-construction/starter/cfg.ml -- core CFG operations
• exercises/cfg-construction/starter/exercises.ml -- CFG construction patterns

Also provided (read-only):

• exercises/cfg-construction/starter/cfg.mli -- interface specification

CFG patterns you will build

Sequential:          If-Else (Diamond):        While (Back Edge):

 ENTRY                  ENTRY                    ENTRY
   |                      |                        |
   v                      v                        v
  B1                   B_cond                    B_pre
   |                   /    \                      |
   v                  v      v                     v
  EXIT             B_then  B_else              B_cond  <---+
                      \    /                   /    \      |
                       v  v                 B_body   \     |
                      B_join                  |       \    |
                        |                     +--------+   |
                        v                              |
                       EXIT                          B_post
                                                       |
                                                       v
                                                      EXIT

What to implement (in order)

In cfg.ml:

#	Function	Hint
1	add_edge cfg src dst	Find both blocks in cfg.blocks, append dst to src's succs and src to dst's preds, update the map with StringMap.add
2	predecessors cfg label	StringMap.find the block, return its preds
3	successors cfg label	StringMap.find the block, return its succs
4	to_string cfg	StringMap.fold over blocks; for each, print label, stmt count, succs, preds

In exercises.ml:

#	Function	Hint
5	build_cfg_sequential stmts	Create ENTRY, B1 (all stmts), EXIT blocks; add edges ENTRY->B1->EXIT
6	build_cfg_ifelse stmts	Partition around the If node; create B_cond, B_then, B_else, B_join; wire the diamond
7	build_cfg_while stmts	Partition around the While node; create B_pre, B_cond, B_body, B_post; wire the back edge B_body->B_cond

Run tests

dune runtest modules/module3-static-analysis/exercises/cfg-construction/

Starter output: .EEEEE.EEEEEEE

Some tests already pass (the dots) because the provided create_block helper function works out of the box -- its tests do not depend on your TODO stubs. The E results are the tests that call your unimplemented functions. As you implement add_edge, predecessors, successors, and to_string, the middle tests will turn to dots. Then tackle exercises.ml for the remaining tests.

Hint for build_cfg_ifelse: You need to split the statement list into three parts: statements before the If, the If itself (from which you extract then_stmts and else_stmts), and statements after the If. A recursive helper or List.fold_left works well for this partitioning.

Hint for build_cfg_while: Same partitioning idea, but around the While node. Remember that B_cond is empty (the condition is implicit in the branching edges), and the key addition is the back edge from B_body to B_cond.

---