Lesson 5: Global Analysis

[sampsyo]

In this task, you have implemented some fundamental operators on CFGs involving dominators!

[maheshejs]

Code: https://github.com/maheshejs/cs6120pr

Dominance Utilities
Finding Dominators via the Worklist Algorithm
I implemented this in Racket using the worklist algorithm from Task 4, since the equation for dominator sets, Dom(v) = {v} ∪ ⋂(Dom(p) for p in v.preds), is itself a dataflow equation. The worklist algorithm runs forward: every vertex except the entry initializes to the set of all vertices, while the entry initializes to just itself. The meet operator is set intersection, and the transfer function adds the current vertex to the input set. The algorithm converges to a fixed point, giving the dominator set for each vertex.

Constructing Dominator Tree
I implemented the dominator tree by computing each vertex’s immediate dominator and using those to build the dominator tree. For a vertex v, I examine Dom(v), found with the previous utility function, and pick the vertex w in Dom(v) \ {v} whose dominator set has one fewer element than Dom(v), that w is the immediate dominator of v. Then, I construct an unweighted directed graph with Racket’s graph library, adding an edge from each immediate dominator to its child (idom(w) → v).

Computing Dominance Frontier
I implemented dominance frontiers using two methods. The first follows the definition directly: for each vertex v, I compute its dominated set from the dominator sets, collect the immediate successors of all nodes in that set, and remove those strictly dominated by v. The second follows the algorithm of Cytron et al. (Efficiently Computing Static Single Assignment Form and the Control Dependence Graph) to efficiently compute the dominance frontier. For each convergence point q (a CFG vertex with multiple predecessors), I examine each predecessor x. Starting from x, I walk up the dominator tree until reaching idom(q). For every vertex p along this path, I add q to DF(p). This gives the dominance frontier set DF(v)for each vertex v.

Testing
I tested the dominance utilities with handwritten cases using RackUnit, Racket’s unit-testing framework. Like turnt, these are essentially snapshot tests: I compare the actual outputs to golden reference outputs. To aid debugging, I wrote a helper function that visualizes both the input graph and the resulting dominator tree using Racket’s Graphz, which generates a DOT representation of the graph. Finally, to confirm that a block A algorithmically dominates a block B, I remove A in the original graph and compute BFS from the entry node to check if B is still reachable.

Example input graph:

Example computed dominator tree:

More visualizations can be found here: https://github.com/maheshejs/cs6120pr/tree/master/graphics/dom

Hardest Part
The dominance utilities themselves were straightforward to implement, just a few lines with Racket’s higher-order functions. The real challenge was testing: setting up RackUnit properly and designing diverse test cases. To expose corner cases, I relied on custom examples instead of using real Bril programs. RackUnit really helped organize the tests.

Conclusion
I believe I deserve a Michelin star for implementing dominance utilities (efficiently computing the dominance frontier), testing them thoroughly, and providing clear visualizations of both the input graphs and their dominator trees.

GenAI
I used ChatGPT to set up RackUnit and generate some basic test cases, which I then extended with my own. I prompted it with my dominance functions and asked to set up tests. GenAI was especially useful for handling boilerplate and giving me a solid starting point to build on.

[sampsyo]

Very very nice! It's cool that you were able to find the better dominance frontier algorithm within the classic Cytron SSA construction paper. And thanks for including a few sample GraphViz outputs!

[jeffreyqdd]

Code https://github.com/jeffreyqdd/rust_bril/

Dominance Utilities + Testing

I ran the tests on all of the files in the bril benchmarks, so I have reasonable confidence that the path coverage is good.

1. Finding Dominators

I implemented the pseudocode discussed in class, adding reverse post-order traversal for the optimal time complexity.

dom = {every block -> all blocks}
dom[entry] = {entry}
rpo = reverse_post_order(graph)
while dom is still changing:
    for vertex in rpo except entry:
        dom[vertex] = {vertex} ∪ ⋂(dom[p] for p in vertex.preds}

testing
I leverage the following property to test: A dominates B implies that B is unreachable from ENTRY if A is removed. I would look at an entry B: {D1, D2, ..., DN} and perform a flood fill from INIT, with a different $D_i$ removed every iteration, and assert B was unreachable.

To show the backwards, I leverage the contrapositive (A does not dominate B => B is reachable from entry). If N is all nodes and S = N \ {D1, D2, ..., DN}, then B must be reachable from INIT with a different $S_i$ removed every iteration. This indicates that a path exists without $S_i$.

2. Constructing a Dominator Tree

For every domination set B: {D1, ..., DN}, I would calculate the strict domination $S$. I would then find an $P$ such that $P$ is not dominated by any other node in $S \setminus {P}$. I would then use a parent array of type Vec<Option<usize>> where arr[i]=Some(P) (only arr[0] == None, because INIT should dominate all other nodes)

testing
I observed that for node $N_i$, all nodes in the root-to-$N_i$ path must dominate $N_i$, so we apply the same algorithm as part 1 to verify. We also check that nodes not in the path do not dominate $N_i$ (because if they do, they should be in the path).

3. Generating a Dominator Frontier

Because of the data structures I used, I found it easy to pick an arbitrary node $B$ and find all $(P, B)$ edges. I then would iterate through all $A = \cup_{\forall P} dom(P)$ and check if $a_i$ dominated P but not B.

To test, I wrote a check based on the definition discussed in class.

Hardest Part

This was surprisingly non-trivial. I initially thought this would take me less than 4 hours, but I'm now on hour 8 due to my poor decisions. I spent the last 2 hours debugging an infinite loop inside my tree, and nearing the end, my entire worldview almost imploded because I started to think my CFG construction algorithm was wrong.

TURNS OUT that dead blocks posed a problem. Since all non-initial blocks start with the set of all nodes, dead blocks are never iterated upon, and thus they incorrectly believe they dominate all other nodes upon convergence. After I went back and implemented a method called prune_unreachable in my CFG, I was able to pass my test cases.

Conclusion

I think I deserve a Michelin star for putting in the effort to prove the correctness of the algorithms.

AI

I used Copilot to write my test cases and tedious traversal algorithms, e.g., post-order, flood fill for reachability, and traversing predecessors in the dominance tree.

[sampsyo]

I really like your testing approach here!

I leverage the following property to test: A dominates B implies that B is unreachable from ENTRY if A is removed. I would look at an entry B: {D1, D2, ..., DN} and perform a flood fill from INIT, with a different Di removed every iteration, and assert B was unreachable.

This is a cool way to avoid enumerating "all paths" while still hewing pretty close to the original definition of dominance. Snazzy!

TURNS OUT that dead blocks posed a problem. Since all non-initial blocks start with the set of all nodes, dead blocks are never iterated upon, and thus they incorrectly believe they dominate all other nodes upon convergence.

Argh! I do see how this could make you question the nature of reality. Nice work cleaning it up with a pre-processing pass! And sorry that this caused you some pain. 😓

[SyphonArch]

Team Members

Jake Hyun

Summary

In this assignment, I built a tool that:

1. Computes dominators for each block in a control-flow graph.
2. Constructs the dominance tree from immediate dominators.
3. Computes the dominance frontier for each block.
4. Optionally checks correctness against a naive checker.
5. Optionally visualizes tree.

Together, these analyses provide a clear picture of the dominance structure in a program’s control flow.

Testing

I verified correctness in two ways:

1. A naive checker that enumerates all paths from the entry block to confirm dominance relations match the definition.
2. A visualizer that generates dominance trees, making it easier to spot mistakes by eye.

Here’s an example visualization of the Palindrome benchmark:

Hardest Part

The hardest part was ensuring that the mathematical definitions of dominance and dominance frontier were precisely matched by the code.

Generative AI

I used ChatGPT to:

• Clarify dominance-related definitions when I got stuck on the formalism.
• Help with boilerplate writing for README, code for visualization and relevant visualization libraries.

Code

You can find the implementation here: Lesson 5 Code.

[sampsyo]

Cool; all sounds good!

Looks like pygraphviz worked to get some outputs somewhat quickly. This is SUPER off-topic, but TBH it seems kinda wild to me that it requires a C compiler and stuff? Because emitting a GraphViz dot file is so easy (you literally just need print calls and some string formatting), so it seems kinda elaborate to require native code for the library. Anyway, if it works it works!

[SyphonArch]

Yeah I was also initially a bit thrown off when just doing pip install didn't work — it seems like PyGraphiviz is just a wrapper around a C library. But once I had it installed things were all smooth so it didn't bother me too much down the line.

[Fangtangtang]

In this task, I implemented algorithms to compute dominators, construct the dominator tree, and determine dominance frontiers.
To test my implementation, I mainly used a brute-force algorithm based directly on the definitions and checked for consistency between its results and those of my implementation.

A Cool Observation

While designing the testing algorithm for dominator computation, I realized that the definition requires enumerating all paths from the entry block to a given block. However, since the CFG may contain loops, the number of such paths is infinite. Interestingly, I found that removing back edges from the CFG does not affect dominator analysis.

The intuition is as follows: when enumerating paths from the entry, a loop can be traversed any number of times (0 to ∞). For a back edge with destination block D, any block B reached after D that is not part of the loop still has an alternative path from the entry to B that skips the loop entirely. By definition, this means that none of the loop blocks (except D) can dominate B. Thus, we can safely eliminate back edges during traversal, transforming the CFG into a DAG, and compute dominators on this DAG without changing the results.

For constructing the dominator tree, I found it more straightforward to work directly on this DAG. My approach was to first compute a topological order of the DAG. Since the entry block is unique, its immediate dominator is set to None, and it serves as the root of the dominator tree. Then, processing blocks in topological order, the immediate dominator of each block is computed as the least common ancestor (LCA) of all its predecessors' immediate dominators in the current tree.

I compared the results of this approach against the brute-force implementation across bril benchmark suite (commit c96fa8e2f7190c31ebb6bd10e54eb49e277df663), and they matched exactly. While I am not entirely sure if I have overlooked some corner cases, I found this observation quite insightful.
I would be glad to hear any thoughts or feedback on this idea!!

[sampsyo]

That is indeed a cool approach to testing!

For a back edge with destination block D, any block B reached after D that is not part of the loop still has an alternative path from the entry to B that skips the loop entirely.

I wonder if this turns out to be equivalent to saying: for every cyclic path, define its "reduction" to be a new path that only goes around each cycle once. It suffices to check only the (finite) "reductions" of the (infinite) set of paths in the graph to establish dominance.

Thus, we can safely eliminate back edges during traversal, transforming the CFG into a DAG, and compute dominators on this DAG without changing the results.

One thing that's a little funny about this is that (IIUC) you're using your dominator information to identify backedges, then using that to test your dominator information. So there's something a little cyclical about that. Anyway, still seems useful as a testing strategy!

Nice work!

[Fangtangtang]

Thanks!

I wonder if this turns out to be equivalent to saying: for every cyclic path, define its "reduction" to be a new path that only goes around each cycle once. It suffices to check only the (finite) "reductions" of the (infinite) set of paths in the graph to establish dominance.

I actually think we could define a “reduction” as traversing a cycle 0 times. I feel that “going around a cycle once” is a bit unnecessary or ambiguous (especially when considering nested cycles, the order in which cycles appear in a path can have many combinations. Though I think keeping any single combination or all combinations would not affect the ability to establish dominance.)

One thing that's a little funny about this is that (IIUC) you're using your dominator information to identify backedges, then using that to test your dominator information. So there's something a little cyclical about that.

Sorry, I might not have been clear.😓 Here I’m actually using another backedge definition: a backedge is any edge that goes to an already-visited node during DFS.
I perform a DFS starting from the entry basic block, obtain the DFS tree, and then remove the “back edges” based on this definition.

[Jacqueline-Wen]

Team Members
Serena Zhang (syz8), Maggie Gao (mg2447), Jacqueline Wen (jw2347)

Source code URL

Find Dominators

Finding the dominators (findDominators) for each block involved starting with the assumption that every block is dominated by all the blocks, except for the entry which only dominates itself. We then repeatedly updated each block's dominator set with the rule: a block’s dominators are the intersection of its predecessors’ dominators plus the block itself. These iterations continue until the sets stop changing. The result is a mapping from blocks to the exact set of dominators.

Dominance Tree

To find the dominance tree, we constructed findImmediateDominators to take the full dominator sets and prune them down to only the immediate dominators. The function involes removing any dominators that also dominate another dominator of the node. After filtering out the non-immediate ones, only the closest dominator remains. The result is a map where each node is paired with its immediate dominator, forming the dominance tree.

Dominance Frontier

The function for finding the dominance frontier (findDominanceFrontier) involves first inverting the dominator relation. This is so we now have a mapping of each node knowing which blocks it dominates. Then, for all blocks that a block dominates, the algorithm checks that if a successor is not itself dominated, it belongs in the block's dominance frontier.

Testing

For testing, we decided that the most reasonable way to test our code is the manually verify our test results. We chose some simple test cases to run our program on, and manually drew out the dominance graph and verified that the dominators, dominance tree, and dominance frontier that was outputted by our program matched the results we manually derived.

Hardest Part

The hardest part of the assignment was not the coding itself, but the process of carefully reviewing the test results. To make sure our implementation was correct, this involved manually laying out the basic blocks, drawing the control-flow graph, and tracking all the connections. Manually checking dominators, immediate dominators, and dominance frontiers required meticulous detail, as one small mistake could throw off all later computations.

Michelin Star

We believe that we deserve a michelin star as our program is well-tested, and we came up with protocols with reasonable time-complexity to correctly calculate the dominators, dominance tree, and dominance frontier.

[sampsyo]

Sounds reasonable! Indeed, if you opt for manual testing, that is definitely the most time-consuming part. 😃

[Mond45]

Source: https://github.com/Mond45/cs6120_tasks/tree/master/task5

What I Do

I implemented algorithms for finding dominators, dominance frontiers, and the dominator tree for a Bril control flow graph in Rust. The dominator-finding algorithm iterates through the blocks in reverse postorder to ensure linear-time complexity. The algorithms for computing dominance frontiers and the dominator tree build upon the dominator-finding algorithm, following the definitions discussed in class.

I also implemented a utility for converting a CFG into GraphViz's DOT format for easier visualization. Both the dominator finder and CFG utility output JSON files to facilitate integration with my testing scripts.

Testing

I first verified each algorithm by hand, greatly helped by my DOT CFG converter. Later, I implemented a dominators verifier in Python. It checks that for each output "A dominates B", every simple path from the entry block to B includes A. I believe this check is sufficient, though I have not fully proven it. My intuition is that cycles in the CFG don't add new information to the domination relation. I ran this verifier across the entire Bril benchmark suite.

For dominance frontiers and the dominator tree, I only tested my outputs against the test cases in the Bril repository. I am still wondering if there's a systematic way, beyond handwriting test cases, to test these algorithms more thoroughly.

The Hardest Part

I found mapping the formal definitions to code implementation quite challenging, though the implementations themselves are not that complicated. I admit I might not fully understand the intuition for dominance frontiers and immediate dominators.

Conclusion

I believe I deserve a Michelin star for this work. I successfully implemented all three algorithms and verified their correctness. That said, I could spend more time testing the dominator tree and dominance frontier algorithms, as well as learning their definitions.

[sampsyo]

Looks great! Nice work.

My intuition is that cycles in the CFG don't add new information to the domination relation.

I think this is probably true, but it of course depends on the way you formalize it. :)

For dominance frontiers and the dominator tree, I only tested my outputs against the test cases in the Bril repository. I am still wondering if there's a systematic way, beyond handwriting test cases, to test these algorithms more thoroughly.

If you're interested, take a look at the first couple of posts in this thread! Some folks found a few creative ways to implement test oracles.

[jku20]

See here for the bulk of the implementation.

Summary

I implemented a function which finds the dominator tree of each block. To do this I used a worklist algorithm to compute all blocks which dominate any given node. I then reverse the relation. This gives an adjacency list for the dominator tree rooted at a given node.

To compute the dominator frontier, I then take the transitive closure of this adjacency list relation and iterate over nodes, adding them to the dominator frontier of a given node based on the two criteria in the definition. The step where I iterate to take the transitive closure introduces some pretty bad avoidable inefficiency (though it doesn't show in any of the tests as all the functions I tested on are fairly small). A more efficient implementation could have not taken a transitive closure and instead computed the frontier of a node with a simple recursive traversal (also computing the frontier of the children at the same time). I didn't do this because it is slightly more complicated.

Testing

Firstly, I manually tested the frontier and dominator tree functions using solutions I manually created and worked through from my own tests as well as from the benchmarks.

I additionally wrote a checker for the domination relation which given nodes a and b, which by recursive search checks all paths from the entry node up to a certain length (which I set to be the one more than the number of blocks in the CFG) to see if it can reach node b without going through node a. I check all pairs of nodes a and b to make sure if my implementation says a dominates b, no path without a can be found and if my implementation doesn't say a dominates b, a path can be found. This was run on every single core bril benchmark, giving confidence my implementation is correct.

As in the last assignment, the hardest part was verifying my implementation is correct. Manually working through dominator trees is tedious and while the checker can be used to test my implementation, I still needed to think really hard about the (albeit simpler) checker as well as test the checker!

🛞 ⭐

I provide an implementation of a couple dominance utilities and implement a programmatic way to check the results. I don't think the spots of poor efficiency is enough to preclude a star. I think this work deserves one ⭐.

[sampsyo]

Excellent all around! 👏

checks all paths from the entry node up to a certain length (which I set to be the one more than the number of blocks in the CFG)

Nice! I like this as a simple, bounded way to operationalize the (otherwise intractable) definition of dominance. Just adding a constant bound is an elegant way to approximate the real thing.

[YoruCathy]

Code

https://github.com/YoruCathy/cs6120-tasks/tree/main/lesson5

Implementation

I implemented a tool to

• Find dominators for a function.
• Construct the dominance tree.
• Compute the dominance frontier.
• Visualize the cfg, dominator tree, and dominance frontier (result on the lcm benchmark here)
  Using the tool, I can also optionally check if my implementation is correct by comparing my result with the result from NetworkX.

My implementation follows this algorithm from the lecture

dom = {every block -> all blocks}
dom[entry] = {entry}
rpo = reverse_post_order(graph)
while dom is still changing:
    for vertex in rpo except entry:
        dom[vertex] = {vertex} ∪ ⋂(dom[p] for p in vertex.preds)

I didn't do any pruning of unreachable nodes and assumed the full graph in this implementation.
I computed immediate dominators by picking the dominator that dominates all other strict dominators and built the dominator tree by inverting the idom relation, and implemented the dominance frontiers.

Testing

I tried 3 testing methods. The first one is manual verification. I ran my code on multiple Bril benchmarks. But I realized it's not very efficient, and once the tree becomes large, it's not very scalable (e.g. dayofweek). The second one I tried is to give the result pictures to GPT and also the corresponding Bril benchmark. I then ask: (take lcm as an example) These are the results of running this lcm benchmark in Bril. Are the results correct? The answer from GPT (detailed in Detailed version of GPT's thinking process) confirms it's correct. The third way is to check if my implementation returns the same result as the one in the NetworkX package.

GenAI usage

I used GPT-5 for the following tasks:

• Explain the concept and help me understand the lecture better
• Implement the visualization function that visualizes and saves cfg.png, cfg_with_dom.png, dominance_frontier.png, and dominator_tree.png
• Implement the visualization that prints out the ASCII visualization for the dominator tree
• Implement the checker to compare if my code's result is the same with NetworkX's result
• Write a readme for my code
• As one of the ways to verify the result is correct

Detailed version of GPT's thinking process

Thought

I’m checking if the control flow graph (CFG) aligns with the program structure from the images. The dominator tree suggests B0 dominates everything. I’m confirming if the cfg structure corresponds to the blocks described: Entry at B0 splitting to B1 and B2, then looping back as described.

I’m confirming block dominance. B0 clearly dominates all, while B1 and B2 only dominate themselves and B0. B3 dominates B4, B5, B6, and B7, considering the paths. I also need to check the dominance frontier of B1, B2, and B4, especially whether B4 includes itself.

The diagram shows some odd DF edges, like B4 linking back to itself and to B6. I’m checking the flow: nodes with multiple predecessors, like B3, have a specific idom (B0 for B3). B4’s DF edges make sense after verifying idoms and loops. It looks like B4’s loopback to itself fits this rule.

The diagram’s DF edges look good. B6’s DF includes B4, and B4 has a self-loop, which makes sense with the backedge. The DF sets are also aligned with expectations. I’ll summarize:

DF(B1) = {B3}

DF(B2) = {B3}

DF(B3) = ∅

DF(B4) = {B4}

DF(B5) = ∅

DF(B6) = {B4}

Looking solid! I’ll confirm everything in a more detailed explanation.

Done

Yep — those results look right for your lcm CFG. Quick sanity check (discussion-style, tying to your figures):

What the CFG is doing (at a glance)

B0 branches to B1/B2 (the x > y test).

B1 or B2 falls into join B3 (.endif.1).

B3 → B4 is the loop header (.foreverloop): test bothZero.

If true: B4 → B5 → B7 (print & exit).

If false: B4 → B6 → B4 (increment & loop back).

Immediate dominators (matches your dom-tree figure)

idom(B0) = ⌀

idom(B1) = B0

idom(B2) = B0

idom(B3) = B0 (both paths must reconverge here)

idom(B4) = B3 (every path to the loop body goes through B3)

idom(B5) = B4

idom(B6) = B4

idom(B7) = B5

This yields exactly the tree you showed:

B0
├─ B1
├─ B2
└─ B3
   └─ B4
      ├─ B5
      │   └─ B7
      └─ B6

Dominator sets (consistent with the tree)

Dom(B0) = {B0}

Dom(B1) = {B0,B1}

Dom(B2) = {B0,B2}

Dom(B3) = {B0,B3}

Dom(B4) = {B0,B3,B4}

Dom(B5) = {B0,B3,B4,B5}

Dom(B6) = {B0,B3,B4,B6}

Dom(B7) = {B0,B3,B4,B5,B7}

Dominance frontier (matches your dashed DF figure)

Join points drive the DF:

B3 has preds B1,B2 → walking up from each pred to idom(B3)=B0 puts B3 into:

DF(B1) = {B3}

DF(B2) = {B3}

B4 has preds B3,B6 → walking up from B6 to idom(B4)=B3 adds B4 to:

DF(B6) = {B4}

and along the walk you record the self-loop: DF(B4) = {B4} (totally expected for loop headers with a backedge)

Everything else has empty DF:

DF(B0)=∅, DF(B3)=∅, DF(B5)=∅, DF(B7)=∅

So your three visuals line up perfectly:

CFG: structure and backedge B6 → B4

Dom-tree: exactly the parent/child relations above

DF overlay: dashed edges B1→B3, B2→B3, B6→B4, and the self-loop B4→B4

The hardest part

Manually checking the results (especially when the graph gets big) is very hard, so I tried to find ways to make testing easier. I think GPT's answer makes sense, but because it is a black box we can't rely on it. And comparing against a common library (assume it's correct) is a scalable way.

Star

I claim a star for my implementation and attempts toward scalable and reliable testing.

[sampsyo]

All looks good!

Using the tool, I can also optionally check if my implementation is correct by comparing my result with the result from NetworkX.

Aha; that's a fun idea! I didn't know that NetworkX had its own implementations. Comparing directly to its implementation is a great way to get a test oracle!

And that's a fascinating set of GPT "reasoning" steps. I have no idea how to check whether it's correct, but it's interesting to look at?

[SolidLao]

Team Members

Ning Wang (nw366), Jiale Lao (jl4492)

Source Code

https://github.com/NingWang0123/cs6120/tree/main/assa5

Implementations

We implement the functions to (1) find the dominators for a function, (2) construct the dominance tree, (3) compute the dominance frontier in Python.

The hardest part

I think for the tasks of these weeks, one of the most challenging part is how to do testing to ensure that our implementation is correct. How to make sure that, the test cases are complete to cover all situations and identify all possible bugs? Also, it would require many efforts to prepare a complete set of test cases, and then how about the evaluation? We can use the existing benchmarks for experiments, but what about ground truth and evaluation?

Testing and Visualization (Also the Generative AI Part)

Since LLMs are just so good at generating test cases and visualizing results, our final solution is to use GPT-5 to generatec 5 test cases, combined with one test case from the benchmark, and visualization figures, and then we manually check whether these results are correct.

As shown in the figure, with good visualizations, it is very easy to tell whether the construction is correct or not.

Michelin Star

I think we deserve a star, given that we implement all the functions, good testing, and good visualization.

[sampsyo]

Sounds good enough from here! I'm glad that a visualization was useful for manual checks.

[az275]

Code

I implemented the functions for finding dominators, building the dominance tree, and finding the dominance frontier. The most challenging part was testing. For finding dominators, I verified correctness by programmatically validating that the output meets the condition: if block0 dominates block1, then all paths from the entry block to block1 include block0. I ran this on the 2 tests under bril/examples/test/dom and all of the core bril benchmarks, confirming that it passes the correctness check on each of them.

Testing revealed two issues. First, apparently when I had initially implemented the cfg building utilities in lesson2, I didn't consider the case where a program did not have a unique entry block; this resulted in some weird output for while.bril. Second, my initial implementation failed to run when a bril program has blocks that are unreachable, e.g. is-decreasing.bril.

I did not implement some form of systematic checker for build_dominator_tree and find_dominance_frontier. I verified the correctness of these by hand on the loopcond.bril and while.bril test cases, plus a few functions in the programs in bril/benchmarks/core with nontrivial cfgs. For these, I hand-computed the correct results, and compared the printed output to these results. This looks to me like it does what it's supposed to do, though I wouldn't claim that this was production-level testing.

I asked ChatGPT to write the function to print the tree.

Star? I'm reasonably confident that my implementation is complete and correct, so I would say I deserve a star. The output formatting/visualization is not the nicest, but it works.

[keikun555]

Good job! Yes, the unreachable blocks and non-unique entry blocks are indeed tricky for this task :)

[adnan-armouti]

Team Members
Adnan Armouti and Tobi Weinberg

Link to Implementation
Repo available here

Implementation Overview
We implemented dominance analysis for Bril programs using three different approaches:

1. Naive Implementation (naive.py): Definition-based dominance checking using DFS traversal for each dominance query.
2. Iterative Data Flow Analysis** (df.py): Standard iterative algorithm computing dominator sets, immediate dominators, dominator tree, and dominance frontier based on pseudocode covered in lecture.
3. Cooper-Harvey-Kennedy Algorithm (chk.py): Efficient CHK algorithm for immediate dominators using reverse postorder traversal, as per ChatGPT ("please see GAI Disclaimer" below).

Testing Methodology
We organized Bril benchmarks by size into three categories:

• Small (≤50 lines): 14 benchmarks tested with naive dominance checking
• Medium (51-200 lines): 8 benchmarks tested with both naive and CHK methods
• Large (>200 lines): 12 benchmarks tested with fast CHK method only

Each category used turnt.toml files to run tests with appropriate flags (--check_slow, --check_fast, or both), generating .out files with verification results. Our check_match.py script parsed these .out files to provide an overview for mismatches, revealing three problematic benchmarks: mandelbrot, gol, and montecarlo that required extensive debugging.

Hardest Part
Debugging three failing benchmarks (mandelbrot, gol, montecarlo) required fixing unreachable block handling:

1. Our initial approach incorrectly computed dominator sets for unreachable blocks, assigning them full dominator sets instead of empty ones. We inadverdently initialized unreachable blocks with all blocks as dominators, and our intersection logic didn't handle unreachable predecessors correctly. To fix this, we added is_reachable() function to identify unreachable blocks and set empty dominator sets for them.
2. In addition, immediate dominator computation failed for unreachable blocks, assigning incorrect parents instead of None. We discovered that our initial reachability check was too simple, only checking if entry was in dominator set. We fixed this by using proper DFS reachability checking in get_immediate_doms_and_tree().
3. Our initial code did not perform a self-dominance check, so we had to add one.
4. For the fast dominance check using precomputed dominator sets in the run() function in df.py: our method incorrectly handled entry block dominance over unreachable blocks. We added an arbitrary semantics rule: entry dominates all blocks, even unreachable ones (not sure how correct this is but it helped pass the test).

Results/Output
Our implementation successfully passes all 34 Bril benchmarks across three size categories:

• Small: 14/14 benchmarks pass with naive dominance checking
• Medium: 8/8 benchmarks pass with both naive and CHK checking
• Large: 12/12 benchmarks pass with CHK checking

Each benchmark generates .out files showing dominator sets, immediate dominators, dominator tree, and dominance frontier, with verification markers indicating agreement between our implementation and the two reference algorithms.

Self-Assessment
We successfully implemented three dominance analysis algorithms and resolved edge cases involving unreachable blocks.

GAI Tools Disclaimer
Please see the README in our repo for a very detailed explanation: https://github.com/adnan-armouti/cs6120/tree/main/lesson_5

[keikun555]

Awesome job with the evaluation. It's cool that ChatGPT provided the entire chk file. Good job on the GAI disclaimer too!

unreachable block handling

Yes, the unreachable blocks are one of the trickiest parts of this task!

[zc579]

What I did
I implement a program that could computes three types of dominance relationships from control flow graphs, which is dominance, dominance frontier and dominant tree. I used add_entry and add_terminators in cfg.py to complete control flow graph. Then I use successor also in cfg.py and reverse it to get successor and predecessor of each block. After that I use DFS in recursion to get a reversed version of CFG. Finally, I use the principle that the dominator of a block is the block itself and the intersect of all its predecessor to get dominators until there's no change in dominators' set. For dominate frontier, I find the block that is the successor of current block but not dominated by it. For dominance tree, I find the block that is one step away from strict dominance.
Test
I first use examples in /example/test/ssa to test my program and it has the same output as expected. I then run several benchmarks and use chatgpt to generate their dominance tree to compare with my output. I have to say it is very good at doing such job and my output is correct.

[keikun555]

Cool! For next time, it would be good to talk about which benchmarks you ran the tests on and what you felt was the hardest part of the task!

[natetyoung]

Amanda Wang @arw274 and I worked together on this.

Code Link

What we did

We implemented algorithms for finding dominators, constructing a dominator tree, and finding dominance frontiers.

The algorithm for finding dominators proceeded as shown in the lesson. Our algorithm for constructing the dominator tree leans heavily on the basic fact that allows the dominator tree to exist: that if A and B both dominate C (and C is reachable, i.e. nontrivially dominated), then it must be that A dominates B or vice versa, so the dominators of any node form a path ending at that node in the dominator tree. Our algorithm involves constructing that path explicitly for every node n (by sorting the dominators d of n in order of how many dominators each d has) and adding those paths to the tree. Our dominance frontier algorithm updates frontiers iteratively: each node's dominance frontier is whichever nodes it does not dominate among its own successors and the dominance frontiers of its children in the dominator tree. We perform these updates in reverse postorder so that we do not have to iterate many times.

Testing

We implemented brute-force versions of the dominator-finding algorithm (DFS with an excluded node) and the dominance frontier algorithm in order to compare against our versions, and then confirmed that they match on all the core Bril benchmarks. We also round-tripped our dominators through the dominator tree and confirmed that this round-trip preserved the dominator sets, again for all the core benchmarks.

For the second week in a row, this testing revealed a bug in a more fundamental algorithm (it turned out my fix for ret handling in CFGs from last week broke handling of empty basic blocks, so I had to modify it; that was caught by the dominator tree test).

Appraisal

We believe we deserve a Michelin star for clean implementations of all the algorithms and thorough testing.

[keikun555]

Good job! Indeed, sometimes we find bugs in our previous implementations when we use it in our tasks, and that's okay!
It would be good to elaborate more on how y'all solved the issue!

[mercure67]

Who / Where

Pedro Pontes Garcia, Helen Ge; https://github.com/mercure67/bril/tree/feat

Summarize what you did.

We completed a set of tools for reasoning about block domination in a function's CFG. This includes a mapping of each block to the set of blocks which dominate it, a domination tree, and a function which returns the domination frontier. We also have some basic pretty printing for these elements.

For more information about the algorithm we used to find the domination frontier, see bds/docs/global.md.

Explain how you know your implementation works—how did you test it? Which test inputs did you use? Do you have any quantitative results to report?

We wrote our code to hew pretty closely to the reference algorithms discussed in class. To test our output, we used a specific example (see bds/tests/global/wisc.bril) as well as some example programs. Honestly, after some time, you kind of get an intuitive sense of what is correct.

What was the hardest part of the task? How did you solve this problem?

Testing. We manually tested a special case (discussed above) and manually checked some other programs. Working is shown in bds/docs/global.md (we reason about some examples).

Do you think your work deserves a Michelin star?

Yes. The implementation works. In addition to testing on some example cases, we tested some important corner cases which Pedro found in his reading. Further, we think our implementations are fairly idiomatic, and spent a decent amount of time refining code and documentation for this and previous tasks, including documentation of the code plus its use; as well as flattening nested conditionals throughout. We also used the reverse post-order traversal optimisation suggested in lecture.

[keikun555]

Awesome! What were the "important corner cases" that Pedro found?

It'll be very good if we can put the link to the documentation in this discussion!

[tf-mac]

Code: HERE

Summary:

In this task I upgraded my program to build the dominance tree and the frontier of a CFG (in this case a map between node names and sets of nodes which it dominates/its frontier, which is isomorphic). I did this using the pseudo code and rusts internal set functions, which were extremely useful as I could do true intersections. The only issue I had was when initializing the new set I intersected the empty set with a predecessors (which is obviously empty). Realizing I had to initialize to at least one of the predecessors set fixed this.

The frontier algorithm was even more trivial. I simply traversed the descendants of a dominator's children, and if any were not dominated I added them to the frontier.

Testing:

Testing added its own implementation issues, as Rust's typing system and my novice level with the language led to some inefficient and confusing code. I'm improving however, and after an insidious bug relating to the order of two function inputs (which, due to the HashMaps and the randomization of hashes in Rust, disappeared occasionally when adding print statements) I was able to build a checker. This functioned via manually traversing the tree, and ensuring every path from the entry to a given node passed through it's dominator. It's a slow but exhaustive method. I'd say this was the hardest part, and certainly the most frustrating (the fact that commenting print statements seemingly changed the semantics was infuriating).

Using turnt, I used this to test every single bril benchmark in the core benchmarks. With all successes, I know my code is likely correct.

Michelin Star:

I completed the assignment and proved it correct, and did so in a way that built on previous assignments. I think this deserves a Michelin star. I will say however, I wish I started this assignment earlier. There were a lot of cool visualizations possible, but I wanted to do them right and not just mess up my codebase with AI code (as I noted in my previous GenAI statements), and that takes time and effort. I think as a result I'll try to start the others a little earlier to leave room for any cool post-script items. This is one of those assignments that, if I had more time, I think I could do work worthy of two Michelin stars with the post-script addons. Perhaps I'll be able to do it next week, since we have extra time

[keikun555]

Good job! It sound like rust was giving a hard time for this task 😨
I'm glad you were able to resolve the issues!

[sunwookim028]

Code

I implemented the algorithm for computing dominators within the worklist framwork, and implemented naive algorithms to compute the dominant tree and the dominance frontier with that results. The hardest part was to reason about more efficient algorithms on the CFG structure and how to check correctness. I used GenAI to suggest Python expressions fast (e.g. Me: set Len or size; AI: Use len() to get the size of a set). I do not claim a star.

[keikun555]

It's ok! It would be good to elaborate on how the implementation was tested and how you solved the hardest part of the task!

[Nikil-Shyamsunder]

Repo: https://github.com/Nikil-Shyamsunder/compilers-cs6120/
Work
For this assignment, I reimplemented CFG construction in C++ (I had only done this in Python before). With that foundation, I implemented the dominator set computation using the iterative algorithm from class. From the dominator sets, I built the dominator tree by, for each block B, scanning its dominators to find the “closest” one: the dominator that does not itself dominate any other dominator of B. To make this efficient, I stored dominators in unordered_sets for constant-time lookups.

Finally, I implemented the dominance frontier. I followed the rule that q is in the dominance frontier of p if:

• p does not strictly dominate q, and
• p dominates at least one predecessor of q.

Testing and Evaluation
I began by manually verifying results for cond.bril, tail-call.bril, and triangle.bril, since they each exercise interesting control flow. I checked that the printed results for dominator sets, dominator trees, and dominance frontiers matched my expectations.

To strengthen testing, I wrote a “naive” checker that enumerates all paths to a node in the CFG via DFS. Using this, I verified that if block B was identified as a dominator of block A by my algorithm, then B appeared on all paths to A. I wrote a Python script (verify.py) to automate this check across the full Bril core benchmark suite. It reported no errors, which gave me confidence that my dominator analysis was correct.

Hardest Part
The dominance frontier was the trickiest piece. Unlike dominator sets or the tree, I didn’t have as strong an intuition for what the frontier should look like. I had to carefully work through non-trivial examples by hand before I could be confident that my implementation was correct.

Gen AI Statement
I mainly used ChatGPT to write my verify.py script. For example, I wasn’t sure how to find all the .bril files in the benchmarks folder and then run each through my dominator utility in a subprocess while checking for errors. ChatGPT was very useful here: small scripting tasks in a language like Python, where there’s lots of training data, are where it really shines.

Michelin Star
I believe I deserve a Michelin star for this assignment because I not only implemented dominator sets, trees, and frontiers correctly, but also developed a robust testing workflow with a secondary “naive” validator.

[keikun555]

Awesome! I like how you evaluated the work!

[itingtsai]

Souce Code

Implementation

I implemented a control flow graph (CFG) that breaks a program into basic blocks, connects them by control flow edges, and then analyzes their dominance relationships. The code computes dominators, builds the dominator tree, and determines dominance frontiers. It also includes checks to verify correctness and utilities to print the results / summary.

Testing

I tested my code on both loopcond.bril and while.bril from examples/test/dom. After getting the printout results for loopcond and while, I copied both my outputs and the corresponding bril code into ChatGPT-5 and asked: “Do the dominance utilities match the loopcond.bril program?” For loopcond.bril, the answer was yes, everything matched the loop-and-if structure. For while.bril, the answer was almost, everything matched except the dominance frontier for B1. Specifically, B1 to B0 is a back edge, but since the entry block B0 has only one predecessor B1, the join-only algorithm never considers B0 and misses that B0 belongs in B1’s dominance frontier. The problem is that I should be using the standard two-phase (local + up) computation instead of relying only on join nodes.

Michelin Star

I’ll claim one Michelin star for completing this task. Understanding the concept is fine, but I still found implementing, debugging, and testing it all together challenging.

[keikun555]

Good job! Debugging this task is indeed tricky, since there are many edge cases like unreachable blocks and multiple entry blocks.

[keikun555]

It would be cool to test on more cases -- I wonder if there is a naive way to calculate the dominators 🤔

[CynyuS]

open source: here

Cynthia Shao and Jonathan Brown worked together on this task.

Summary

We implemented a finding dominators algorithm, as well as a verifying dominators algorithm. We verified correctness via snapshot testing and the verification algorithm for dominators. We debugged our cfg from identifying interprocedural dominators and changed it to just a global analysis.

Benchmark

We utilized the core benchmark suite to snapshot test and debug across a variety of different programs, catching bugs for labels without bodies. The naive algorithmic testing for the dominators was super helpful, as it provided insight into all the paths enumerated and checked what dominators didn’t follow the concrete definition. This algorithm is meant to throw an error if the dominators are incorrect, and thus all our snapshot testing passed without exiting, giving us reasonable confidence to believe our dominators algorithm is correct.

Dominator

For the dominator, I implemented it as specified in the lecture. However, on creating the find_pred function, I realized quickly that if my result did not start out as a set, I could not do the set intersections to see all the predecessors of a given block. (I initially had it so that my result was the empty set, and then realized the empty set’s intersection with any set would be… the empty set. It took me a bit of time to realize that was the reason no predecessors were being found). Furthermore, I learned more about python’s semantics, specifically the fact that you could shorthand sets if you want to make an index (For example, for all i in items make an empty table). It was a really cool feature that I played around with a bit (but was a bit cautious using in code as I wasn’t perfectly comfortable with it). There were also some problems with the logic of the dominator creation where I mixed up the cfg with the blocks, assuming they did the same thing (which was not noticeable at first, but caused many errors, such as no dominators being found). Otherwise, the dominator creation was made as follows from the lecture.

Testing

To create an algorithm for checking the output of dominators, I first approached the verification from the definition. For all basic blocks A, basic block B is a dominator if all paths to B pass through A. Thus, I devised two functions. One function traverse_cfg was created to find all paths from the entry node to every block B, and I stored it in a dictionary, where keys were the basic block names, and values were a list of all paths from entry to B. I found it a little hard to keep track of all paths within an acyclic graph, due to predecessors possibly coming from a cycle. Thus, I created a modification of BFS where I check that this block and its neighbor are unique predecessor successor pairs within the visitor set. I would prepend all paths that the predecessor had to this successor, and thus had a path enumeration function that iterated to convergence. This does mean that I create paths with cycles encoded, like a path like source -> A -> B -> C -> B, but it ensures that block B will always end the path, and only cycle once. I believe this BFS modification runs in O(V^2 + E) time, where V is the number of basic blocks, and E is the number of edges. V^2 is because we touch each basic block as many times as its predecessors, a large upper bound is that each vertex possibly has V other predecessors. We add E because we examine each edge at most once for each unique path.

The second algorithm parsed through all blocks A, and for each dominator B in the set for block A, I naively checked to see if dominator B occurred before the first instance of block A.

I think this algorithm is probably on the order of O(n^4), where n is the number of total blocks due to worst case parsing through all blocks, the dominators of each block, all paths to that block, and each item in the path. This is supposing that the number of paths to traverse isn’t terribly large, because the programs I am running this algorithm on are somewhat sparse, and usually have natural loops.

I think some cool next steps would be to possibly optimize this algorithm, due to the possibility that there be an exponential amount of paths!

Hardest Part

The hardest part was debugging our implementation. Implementing the algorithmic testing function revealed a lot of bugs within our dominators and CFG implementation. The core bug was that our cfg implementation was interprocedural, and Jonathan thought that functions within a bril program would automatically execute one after the other, and he linked the cfg accordingly. Thus, our dominator set went through the global program, which is cool, but not what we wanted. So, we refactored our cfg to be function based, as well as adding unique naming to labels that used the same names within functions.

Self Assessment

We believe we deserve a Michelin star because we are proud of our work! We brainstormed an implementation of dominators, and thoroughly tested. We tested thoroughly using both hand implemented benchmarks, against the core bril benchmark suite, and devised a naive algorithm that correctly enumerated all paths to test correctness. Additionally, we analyzed the runtime of our naive verification algorithm, and realized that brute force verification could be very slow. Overall, we collaborated on the dominator’s design decisions and ensured correctness. We also practiced good team coding practices with git, and learned a lot about dominators and global analysis as a whole! We believe we deserve a Michelin star for the creativity and persistence put into the task.

[keikun555]

Awesome job! Great descriptions all around on your implementation, the hardest part, and how you fixed them. Good job with the complexity analysis too!