Lesson 5: Global Analysis

[sampsyo]

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

[UnsignedByte]

Code

This week was finally the week I decided to redo everything in rust, so most of my time was spent actually reimplementing all the library features like basic block identification, Call Graphs, CFGs, and Dataflow. I also added some traits for graphviz dot generation which lets me do some very concise and pretty code to generate callgraphs where each node can be anything from a single node, a CFG, or a Dominator Tree (see here).

Calculating Dominators

The dominators were calculated using the given algorithm, but I decided to implement it using a worklist just to avoid rewriting similar code. For this, I set my meet function to set intersection, and in my transfer function I added i to block i's in values, to make sure a node dominates itself. At the end, the out_values should contain all the valid dominators (non-strict) of each node. As described in the pseudocode, sets are initialized to 1..n, where n is the number of blocks, rather than the emptyset (except for the entry). This prevents values from stabilizing at {i} only.

Everything Else

Next, I needed to calculate the Strict Dominators, Immediate Dominators, and Domination Frontier for each block. I realized that each of these could be calculated solely from the Dominators in relatively non-slow algorithms.

1. Strict dominators were very simple, just take the dominator set for block x and remove x
2. Immediate dominators are strict dominators that do not strictly dominate other strict dominators. We can do this as follows:

# For a given block x with strict dominators sdom[x]

# These nodes dominate x's strict dominators, and thus cannot be immediate
non_immediate_doms = union(sdom[i] for i in sdom[x])

# There should be only one dominator that satisfies this (assuming sdom is valid)
immediate_dom = (sdom[x] - non_immediate_doms)[0]

3. The dominance frontiers can be seen as non-dominated successors of dominated blocks.

# For a given block x that dominates dom_by[x]

# These nodes are the successors of all of x's dominated
successors = union(succs[i] for i in dom_by[x])

# The successors that are not dominated become the frontier
frontier = successors - dom_by[x]

Graph generation

I used Graphviz to generate dominator trees as well as a a special pass that finds the unique block in a bril program named selected and colors nodes in a CFG based on their dominance relations to the selected block.

In the example shown below (a simple nested loop), the dominator tree contains the actual CFG edges dashed, while the actual dominator tree is in black. On the right, the red node is selected, with its strict dominators in dark green, the nodes it dominates in light green, and its dominance frontier in blue.

Dominator Tree	Dominance information for selected block

Testing

For testing I did a very slow brute force method - I used DFS to generate all (non-cyclic) paths from the entry node to a target node x, and made sure that each path visited only nodes present within the dominator set of x. To check the entire tree, I just looped through each basic block and made sure its dominators were valid.

Summary

I spent most of my time this week actually restructuring all my old python code and I am now pretty happy with how everything is laid out now! I think the most interesting part of this assignment was definitely calculating all the other dominance relations from the initial dominators, but otherwise the algorithm was fairly straightforward and easy to implement after I decided to reuse my worklist implementation. I would say I deserve a star just because I spent a bunch of time to make the graphs look good and I personally quite like them.

[sampsyo]

Very very cool! I really like your approach to GraphViz generation, and the visual outputs are clearly worth the effort. 😃 I really like the visualization that shows the dominator tree with the CFG edges layered on top (and apparently not affecting the tree-directed layout of the nodes?).

And you also made a neat observation here that you can use the worklist algorithm to do your dominator work for you. Saves a bit of typing vs. implementing something similar manually just for this task.

[UnsignedByte]

Yes, graphviz has a very nice constraint=false that removes edges from the placement constraints on nodes, which lets keep the nice tree structure!

[mt-xing]

I implemented all three dominator functions in TypeScript here: https://github.com/mt-xing/cs6120/tree/main/l5

For the most part, I just followed the algorithm given in class to compute dominator nodes. Once I had those, I could compute the tree by sorting all the nodes by number of dominators, least to max, and then just constructing the tree by walking each node down from the root. To get the frontiers, I inverted my dominator mapping to get me the list of what each node dominates (instead of what dominates it), and then just looped through all of those node successors, checking if they're already in the dominated set.

Also, up until now, I'd been representing my CFGs as maps from blocks to sets of other blocks that are their successors, but this representation got annoying enough to work with that I bit the bullet and wrote some helper code to convert the map into a proper graph data structure with actual pointers to other blocks, both successors and predecessors.

To test my implementation, I hooked into my Bril testing library from L3, with some minor retooling. Instead of running the interpreter and checking for identical output, I could instead manually verify domination relationships by recursively DFS-ing backwards from any given dominated node through its predecessors. If any given backwards path either looped or resulted in the node I expected to find as the dominator, the path was okay, but if any path made it to ENTRY without hitting the expected node, the path was marked as bad. I could then need only assert that all paths were okay and none were bad to guarantee that all the claimed dominators were correct.

Using the same method, I also tested that nodes in the dominator tree correctly dominated all their (recursive) children, and that the domination frontier consisted of nodes that were not dominated but who had at least one predecessor who was.

With this test harness in hand, I was able to test my implementation against the entirety of the bril benchmarks and bril tests folder to verify correctness. This revealed quite a few bugs, basically all of which stemmed from me going off my sketchy notes from class intead of reading the online notes, as I forgot to initialize the dom mapping to start with mapping all blocks except ENTRY to all other blocks.

I believe this deserves a Michelin star as the extensive testing I performed against the hundreds of benchmark and test files allows me high confidence that my implementation is fully correct. It's also nice to see the previous engineering investments I made begin to pay off, as I was able to leverage lots of old CFG and testing code to make my life easier and code more correct.

[sampsyo]

Awesome; this all sounds great! Including those graph-search-based oracles to test the correctness of our in-class algorithms. Nice work!

[gabizon103]

code

I implemented the algorithm for computing the dominator sets that we discussed in class. It was pretty straightforward, and I don't think there were any weird corner cases I had to consider. It is nice to be able to use code that I've written previously to make things easier. I'm building up a pretty nice utils crate lol. Once I wrote the code to compute the dominator set for a node, I implemented a function that will prune the set of everything except the nodes that it immediately dominates. This was nice for building the dominator tree. I used some graphviz stuff to output the dominator tree as an actual graph, which is nice for visualizing stuff. Finally, I also wrote some code to compute the dominator frontier.

I tested my code for computing the dominator set by brute-forcing it, sorta, and comparing it against that. I used a bfs to accumulate all the non-cyclic paths to a node, took the intersection over all of that, and made sure that all the nodes in that resulting set were in the dominator set my algorithm computed. I tested it on all the core benchmarks.

For the immediate dominators and dominator frontier, I inspected the output from a bunch of benchmarks and manually verified it was right. I thought this less-rigorous approach was fine, since they only required small add-ons to the main algorithm for computing the dominator set.

[sampsyo]

Sounds perfectly reasonable! Glad this one wasn't too much work. :)

[scober]

code

I implemented the three algorithms mentioned on the lesson page (dominators, dominance tree, dominance frontier). I started with a goal of re-using my worklist algorithm from the previous lesson, but I realized that all of the dataflow algorithms I implemented had been functions of the block contents while the dominator algorithm is a function of the blocks' labels. So it would have required a fair amount of plumbing to make it work. In the end I just implemented the dominator algorithm from scratch.

The dominance tree was pretty uneventful (although implementing a version that output the tree in dot once again made debugging much, much easier). The dominance frontier was more interesting because I had an intuition about what the dominance frontier was and that intuition turned out to be completely wrong. For example, loop bodies seem to often have loop headers in their dominance frontier. It made sense when I thought about it, but I had a feeling that loop headers come "before" loop bodies and only things that come "after" you belong in your dominance frontier. Another oddity was how many blocks have no dominance frontier at all. The roots and leaves of dominance trees have no dominance frontier by definition so in small functions it was common for me to find that all or almost all dominance frontiers were empty. So mark that one as another win for "implementation deepening my understanding".

For testing, I just enumerated paths (without excessive looping) from entry blocks and made sure every path that reached a given node included all of its dominators. Then I used turnt and hand-verification to round everything out.

[sampsyo]

Totally makes sense; I can see how reusing the worklist algorithm would be awkward if you hadn't previously "plumbed through" any information about the blocks' identities (just their contents).

And those are fun observations about the intuition (faulty and otherwise) about what "should" be in the DF. Your initial idea makes sense to me on an intuitive level, even though it was wrong in the end!

[ananyagoenka]

Implementation

I implemented the three algorithms discussed in the lesson: computing dominators, building the dominator tree (with some primitive visualization), and computing the dominance frontier.

I started with the standard iterative approach for computing dominators, which refines sets until they converge. The algorithm itself is simple, but I had to make sure the CFG had a unique entry block. I initially overlooked this, which led to weird cases where dominator sets didn’t make sense.

The dominance frontier turned out to be the most interesting part. I had an intuition that was completely wrong—I initially assumed a block’s frontier only contained things that came “after” it, but in practice, loop headers frequently show up in their own dominance frontier. It made sense once I thought about it: if a loop body has a back edge to its header, the header needs to be in the frontier.

For testing, I verified the dominator sets using a naive path enumeration algorithm (on the bril benchmarks)—essentially listing all paths from the entry block and making sure every dominator was present on all of them. It’s slow, but it works for small cases and confirmed that the results matched expectations. For dominance frontiers, I manually checked a few tricky cases, mostly focusing on loops and conditionals to make sure the results were reasonable.

[sampsyo]

Sounds good, @ananyagoenka! Did you read @scober's summary, just one comment up in the thread? Sounds like he had an identical observation to you about the intuition behind what should be in the DF.

[neel-patel-1]

Dominators, Tree, and Frontier
For this lesson, I implemented a script that (1) generates a dictionary which maps basic blocks to their dominators, (2) creates a tree that links parent their immediately dominated children, and (3) maps basic blocks to nodes in their dominance frontier.

(1) uses the algorithm and initialization presented in lecture. (2) uses the program's cfg combined with the map from (1) to find children satisfying the immediately dominates relation. (3) uses the map from (1) and the cfg to find the undominated successors of each basic block.

Verification
One way to test whether the implementations are correct is to use them in an SSA conversion algorithm. I had initially tricked myself into thinking my implementations were correct by implementing checks for the constructed dominator sets, dominator tree, and dominance frontier, but found out my dominance tree implementation was incorrect only after finding out that the SSA conversion relying on it was incorrect.

I inlined the correctness checks in the same script as the implementations such that the original bril program was emitted to stdout only if the analyses passed their associated checks. Then I ran all of the core benchmarks through the analyses using brench, and found that all produced valid output. Since my dominance frontier check gave a false negative, I made sure that the SSA conversion algorithm that used the implementation produced valid SSA on the core bril benchmarks.

Challenges:
4 programs in the core benchmarks contained unreachable basic blocks breaking a cfg.find() method my dominance frontier and tree implementations were using.

[sampsyo]

One way to test whether the implementations are correct is to use them in an SSA conversion algorithm.

That is certainly one way to do it! 😂 Any chance you have a short way to describe why your original checks missed the problem? Because I think it's interesting how hard it is to get a perfect oracle for the dominator-related stuff in isolation, it would be interesting to know exactly where your original testing approach had "blind spots."

[lisarli]

In collaboration with @bryantpark04 and @dhan0779
source

Dominators: Getting the dominators for each node was pretty straightforward, and we followed the algorithm discussed in class with a reverse post-order traversal for linear time complexity. We didn’t face any major issues with this step, although we did make small modifications to our previous CFG implementation and utils to make the interfaces cleaner and more usable.

Dominance Tree: The dominance tree builds off the dominator mapping. From the inverted mapping, we can identify for each current node which of the nodes it dominates are also dominated by another node it dominates, in which case the current node is not its immediate dominator. The resulting mapping from each node to the nodes it immediately dominates becomes our dominance tree.

Dominance Frontier: We determined the dominance frontier for each block using the mapping of nodes to their dominators produced in the first part of this task. We inverted the mapping to get the set of blocks dominated by a given block, and we found the frontier by selecting the set of successors of dominated nodes which were not also strictly dominated by the current block. One small issue we ran into was forgetting the "strictly dominated" aspect of this last step, which resulted in some initial outputs which did not include nodes in their own dominance frontier.

Testing: We tested our dominator implementation using a brute-force approach to BFS over all paths from the entry to each block; we expect the intersection of nodes on all the paths to be equal to the set of dominators. Similarly, for each block and each of its dominators, we performed a BFS from the entry to the block and pruned branches as we encountered the dominator. If we ever encountered the block before the branch was pruned (meaning we found a path without the dominator), we would throw an error indicating the dominator set was incorrect. We ran these checks over all the core Bril benchmarks to verify our dominator set computation. We also manually tested our dominance tree and frontier implementations over various benchmarks, particularly those with tricky branching and loops, to check we handled edge cases correctly.

Conclusions: Overall, the implementations were straightforward, with only occasional edge cases and sometimes a need to tweak our prior representation of structures and utils. We believe we deserve a Michelin star since we implemented each of the three algorithms and carefully thought about and tested their edge cases.

[sampsyo]

Awesome; all sounds great! Thanks for the straightforward summary.

[zihan0822]

source

Dominator

I combined the algo discussed in class with previous generic worklist solver. out is initialized with the universe set for every cfg node.
merge: in[b] = intersection of out[p] where p is the predecessor node in cfg
transfer: out[b] = self U in[b]

Dominance Tree

Dominance tree can built from the dominator set found in previous step. For each cfg node, we sort its dominator set in ascending order based on the number of dominators each dominator has. This forms a path from dominance tree root to the current cfg node. We are able to reconstruct the dom tree by progressively adding new path starting from root to existing tree.

Dominance Frontier

For a given cfg node, we just take one step forward from all the nodes in the sub dominance tree rooted at the current node. I initially made a mistake by excluding the current node when computing its dominance frontier. I just realize this after today's SSA lecture. In my previous impl, for those leaf nodes in the dom tree, they won't have any dominance frontier to insert the phi node. This is apparently wrong in a simple diamond-shaped cfg case.

Here is a sample graphic output for bitwise-ops benchmark. Dominance tree is drawn alongside original cfg graph. In this particular example, .useless_lbl block marked in red is the target node for which we are trying to find frontier and its frontier is marked in green.

Testing

I test my program by brute forcing all of the paths from entry node to any particular node in the original cfg and keep taking intersection of nodes in the path that leads to the destination node. I then check whether the dominator set found with this brute force method is the same as the one found with my worklist algorithm. I tested my program against all general core benchmarks.

Conclusion

One of the problem is handling some edge cases in the definition of dominance frontier, for example, dominance can be reflexive and a node's dominance frontier can contain itself. I think I deserve a Michelin star since I completed three tasks, did throughout testing and did some extra visualization stuff.

[sampsyo]

Awesome; this all sounds great! Thanks for the very clear illustration of what could go wrong with that incorrect definition of the DF. And this GraphViz output looks useful!

[mariasoroka]

Here is the code: link

Overall, I did not find this assignment very hard. I've implemented all three parts and checked them on a few benchmarks. I also made sure that there were no infinite loops in my implementation on all the benchmarks from the core set. To find all the dominators, I used the pseudocode from the slides (i.e. not the worklist version). Here are the visualizations for the gcd benchmark:

I was a bit sick this week and I did not implement the proper testing.

I routinely use copilot when coding. It helps me to write repetitive code. I rarely find "long suggestions" (when copilot writes the whole function) useful; most of the time I remove all such code. I did not use any text prompts for this assignment.

[mariasoroka]

I've looked again at the diagrams today and figured that they are not correct. I fixed my bug (not initializing the dominator set with the set of all possible blocks) and implemented proper testing where I computed all possible paths with DFS. Now I'm confident that my code computes dominators correctly for all the benchmarks. I've updated my repo and here are the fixed diagrams:

[sampsyo]

This makes sense! Good catch on the incorrect "least fixed point" solution here.

[mb64]

Dominators: code

I implemented the tasks in Haskell. To compute dominators, I used my existing dataflow framework: this made it pretty easy, only like 10 lines. I was actually quite pleased with the extent to which I was able to make the overall implementation fairly concise: with a few minor changes to the rest of the code, it ended up just ~50 lines for the dominators computation and tests. I think this speaks to the utility of the general-purpose dataflow framework, since I was able to reuse it for this task.

While implementing, I noted that some things don't really make sense for unreachable basic blocks, so in my main function I removed unreachable basic blocks before doing any other processing on it. I already had a function to do this from previous assignments.

For tests, I implemented a very slow operation that checks if block A dominates block B, by simply doing a BFS from the start node, skipping block A, and seeing if block B is reachable. This is true iff A does not dominate B: if A dominates B, then if you remove A, then B should become unreachable. I then tested for all pairs that this agreed with what my dominators function returned, and also agreed with what the tree I computed said.

I ran these tests on all bril programs in the core benchmarks directory, and they all passed, so I am pretty confident it works. I think this merits a star.

[sampsyo]

I used my existing dataflow framework: this made it pretty easy, only like 10 lines. I was actually quite pleased with the extent to which I was able to make the overall implementation fairly concise

Indeed; I think this is a super cool outcome. Nice work making your worklist implementation generic enough that it could solve this just as easily.

While implementing, I noted that some things don't really make sense for unreachable basic blocks, so in my main function I removed unreachable basic blocks before doing any other processing on it.

This is a very good point, and I officially endorse the solution of simply dropping unreachable blocks before doing these analyses.

[ethanuppal]

Code: https://github.com/ethanuppal/cs6120/tree/main/lesson5/dominators
CI Passing: https://github.com/ethanuppal/cs6120/actions/runs/13535362610

I implemented these algorithms with a Rust CLI/library with snafu as usual:

• cargo run -- --algo dom - Runs the lecture algorithm using a reverse postorder traversal.
• cargo run -- --algo tree - I have a naive $O(n^2)$ implementation that removes intermediate elements of the dominance relation from a SecondaryMap (I use slotmap for a completely flattened graph representation; not sure if I've mentioned this before) to build the covering relation.
• cargo run -- --algo front - Computes the dominance frontier with some interesting quirks (see notes below).

Testing dominators

I was thinking about this for quite some time.

The brute force solution will iterate over all possible paths from the entry to a given node and check that a purported dominator really appears on each path, but (of course) there are an infinite number of such paths. One could try restricting to a certain number of loops around a cycle, but an implementation of DFS, for example, that allows visiting the same vertex again up to a limit has the possibility to get stuck in reducible CFGs, I think. I was initially thinking of something similar to Bellman Ford where I look at paths up to $2n$ away from the target node (like how BF looks at nodes $n-1$ away), but quick thought reveals that this does not provide a representative sample of paths with loops. Maybe we use the strongly-connected components algorithm somehow.

The next idea was to think about fuzzing paths. It is already nontrivial to fuzz simple paths from entry to a given node, and this alone is not sufficient since it only takes one cyclic path avoiding the purported dominator to invalidate the instance. It is probably extremely difficult to have a uniform fuzz over paths that can loop around a natural loop zero or once.

I'm really curious on how brute-force testing paths in CFGs is possible, given that even simple paths are annoying to fuzz over and are very unrepresentative.

Practical testing for dominators

I ended up simply using the oracles that Professor Sampson wrote under examples/test. (I did not and never intend to look at their implementations nor any other implementation of the homework algorithms.) I used this to test that my program was correct on every single benchmark by comparing output diffs with the oracle.

Professor Sampson's implementation has additional basic blocks that I did not compute (I specifically implemented my CFG builder to produce the minimal number of basic blocks required for lossless conversion). Thus, I wrote a silly jq script on the outputs to clean the extra JSON produced by the oracles.

This is the relevant CI code:

      - name: Test dominators
        run: |
          cd lesson5/dominators
          python3 ../../lesson4/dataflow/match_outputs.py \
            "python3 ../../bril/examples/dom.py dom | jq 'del(.entry1, .b1, .b2, .b3, .b4, .b5, .b6, .b7, .b8, .b9, .b10) | with_entries(.value |= map(select(. != \"entry1\" and . != \"b1\" and . != \"b2\" and . != \"b3\" and . != \"b4\" and . != \"b5\" and . != \"b6\" and . != \"b7\" and . != \"b8\" and . != \"b9\" and . != \"b10\")))'" \
            "cargo run --quiet -- --algo dom | jq" \
            ../../bril/examples/test/dom/*.bril \
            ../../bril/benchmarks/**/*.bril
          python3 ../../lesson4/dataflow/match_outputs.py \
            "python3 ../../bril/examples/dom.py tree | jq 'del(.entry1, .b1, .b2, .b3, .b4, .b5, .b6, .b7, .b8, .b9, .b10) | with_entries(.value |= map(select(. != \"entry1\" and . != \"b1\" and . != \"b2\" and . != \"b3\" and . != \"b4\" and . != \"b5\" and . != \"b6\" and . != \"b7\" and . != \"b8\" and . != \"b9\" and . != \"b10\")))'" \
            "cargo run --quiet -- --algo tree | jq" \
            ../../bril/examples/test/dom/*.bril \
            ../../bril/benchmarks/**/*.bril
          # we omit cases where the Bril program seems to be maybe malformed
          python3 ../../lesson4/dataflow/match_outputs.py \
           "python3 ../../bril/examples/dom.py front | jq 'del(.entry1, .b1, .b2, .b3, .b4, .b5, .b6, .b7, .b8, .b9, .b10) | with_entries(.value |= map(select(. != \"entry1\" and . != \"b1\" and . != \"b2\" and . != \"b3\" and . != \"b4\" and . != \"b5\" and . != \"b6\" and . != \"b7\" and . != \"b8\" and . != \"b9\" and . != \"b10\")))'" \
           "cargo run --quiet -- --algo front | jq" \
           ../../bril/examples/test/dom/*.bril \
           ../../bril/benchmarks/**/*.bril \
           --exclude core/is-decreasing.bril \
           --exclude core/relative-primes.bril \
           --exclude mem/two-sum.bril \
           --exclude core/recfact.bril \
           --exclude float/euler.bril \
           --exclude float/mandelbrot.bril

You may notice that a small number of files are excluded from the dominance frontier tests. That's because the oracle (I believe incorrectly, but I'm not sure), considers

ret foo
jmp .bar

part of the same basic block, and considers .bar to be a successor of the basic block. This construct, while valid Bril, I believe is an artifact of slightly suboptimal frontend generation. My implementation (I believe correctly) does not have .bar as a successor. I agree with the oracle on every other benchmark.

I believe I should get a Michelin star because I implemented and tested the assigned tasks.

[ethanuppal]

Forgot to log my Toggl time: I spent 5 hours, but I also had barely any sleep, so this time may or may not be representative

[ethanuppal]

Professor Sampson brought to my attention that the scripts under examples/ are not reference implementations. However, the fact that the implementations agree on every benchmark supports the fact that they at least typically agree, and given that I wrote my implementations completely separately, the testing confidence I have is the heuristic that (it is unlikely for the implementations to agree given that either or both are incorrect) and (my hand-checked cases are correct).

[sampsyo]

Awesome; very nice work!

I'm really curious on how brute-force testing paths in CFGs is possible, given that even simple paths are annoying to fuzz over and are very unrepresentative.

TBQH, I don't really know! You're absolutely right that even some straightforward brute-force approaches are unsatisfying, and randomly sampling representative paths seems surprisingly hard. This seems pretty nontrivial to me, and it would be interesting to think through any kind of sampling-based approach that would be better than the naive version. I wonder if one could actually find interesting bugs in compilers this way... maybe not, since the dominance-related algorithms are so central that they are likely to be implicitly very well tested via downstream optimizations? Could be fun to try anyway!

[katherinewu312]

Group (@ngernest, @katherinewu312, @samuelbreckenridge)

Code
(Sam: dominators, Katherine: dominator tree, Ernest: dominance frontier)

Our code for finding dominators is a straightforward implementation of the pseudocode discussed in class. Coming up with a way to algorithmically confirm the dominators we compute was probably one of the trickier parts of the task as it involved thinking about different (potentially naive/slow) ways to compute dominators. To check the dominators output by our code, we implemented a version of DFS which enumerates all paths (without repeating nodes) between two nodes within a CFG. We then used DFS to enumerate all paths from the entry node to each node v in a CFG and checked that the intersection of all those paths contained v's dominators. We run this check alongside our code for printing the dominator map so it runs for tests of our get_dominators functionality. As test cases for finding dominators we used a few simple bril examples which we checked manually and we run our implementation on all core bril benchmarks to confirm the code does not crash and the DFS based check passes. Running on all benchmarks revealed that our implementation did not handle functions with unreachable basic blocks so in the get_dominators function we added a pass to remove non-entry basic blocks with no predecessors.

For the dominance tree, each node's children are those nodes it immediately dominates. To implement the tree, which we represent as a mapping from nodes to its successors, we first reversed the dominators set obtained from get_dominators() in dominators.py to obtain a post-dominance set for each vertex in the cfg. For each vertex, we then took the intersection of its post-dominance set with its set of successors in the cfg to obtain those nodes that the vertex immediately dominates. This task was pretty straightforward, and we believe our implementation for this is quite concise. We also decided to use graphviz to generate dominator trees to better illustrate the trees; a visualization can be generated if you specify a --draw option when running the program (see below for what our program generates for loopcond.bril and while.bril in examples/test/dom). We tested our implementation using Turnt with those tests in the Bril dominator examples repo, and verified that our code behaves the same.

For dominance frontiers, we implemented a few helper functions which indicate for two nodes x and y, whether x (strictly) dominates y. With this in place, the main logic for constructing DFs could be encapsulated using just one Python set comprehension! To test our DF implementation, we implemented unit tests which checked that no condition in the definition of DFs is violated. Specifically, we check that for every node A, A does not strictly dominate any node in its DF, and that A dominates some predecessor of each element in its DF. We manually constructed some CFGs using examples from the CS 4120 lecture notes, and created unit tests which checked that our algorithms computed the same DFs as the lecture notes. We also manually compared the results of our Turnt tests with those in the Bril dominator examples repo to check that our code behaves the same as the reference implementation.

We believe our work merits a Michelin star due to the extensive testing we did to ensure our implementations worked correctly, e.g. testing our implementations on all the bril programs in the core benchmarks directory.

[tean-lai]

Code: blocks.py

For this task I extended my basic blocks library to compute dominators too. I compute the dominators following the algorithm shown in class. Some issues came about from using Python sets, just a bunch of mutation things.

I also implemented dominance trees. To do this, I had some helper functions check if nodes are strictly domminating or immediately dominating each other, and then to create the tree it tests it for the relevant properties. My implementation might not be the most optimal speed-wise, but I feel fairly confident in its correctness. The overall runtime is O(n^3), which probably could be improved.

I also have a function that can compute dominance frontiers.

For testing, I run brench on a script that constructs basic blocks for each core benchmark (which would automatically construct dominators). Then I check if they are valid using some BFS and crashing the programs if they are not valid, therefore failing the test.

[Annacaro22]

Code is here.

I found the actual algorithms-- find dominators, create dom tree, and calculate dom frontier-- to be pretty simple in themselves. I did these parts over the weekend and didn't think they were too hard-- however, I did keep mixing up whether "doms" held dominators or postdominators-- I realized at one point my domtree function had accidentally made the postdominator tree instead of the dominator tree. I kept mixing up whether the value of A in doms was the nodes that dominate A, or the nodes that A dominates. Luckily, this error was quickly fixable by just reversing the CFG at the start of my function 😄 .

In general, I do think doing these implementations helped me understand the dominance concepts better; I kept having to go back to clarify things to myself that I thought I understood but apparently didn't (for example, for the dominance frontier, I was momentarily if A dominates nothing, but has B as a child, then is B in its dominance frontier, even though there's not any unique node C such that A doms C and C does not dom B? Answer: yes, this is just the case where C=A).

I'm starting to wonder if my CFG representation isn't the most optimal. I keep it as a dictionary of {parent : children}, but I also created an 'end' block, which all exit blocks point to. This has been useful in some cases, but is also an annoying thing to keep lugging around from algorithm to algorithm; instead of looping over the keys in the CFG, I have to remember to loop over the keys in the CFG plus 'end' every time. Still, it's useful to only have to deal with one block with no children in the CFG.

The part I struggled with the most here was the testing. I have domtree and domfrontier tests that work, but I couldn't quite get my dominator tests to work-- those pesky cycles! I tested my dominator function on benchmarks in the bril benchmarks computer by hand-computing the intended dominators, though, so I have confidence that my dominator function is right even if I couldn't quite get the test to work. The tests for domtree and domfrontier, assuming that dominator calculation works, were pretty trivial to code up, and I ran those on benchmarks in the bril benchmarks folder; these finding no bugs also supports that my dominator calculation is correct.

To be honest, I am less confident that I deserve a Michelin star this time, since I couldn't quite get my dominance test to work by the deadline. If I have time after the deadline, I will come back and see if I can fix it to give myself total confidence in my solution. Still, it wasn't for lack of trying; I spent a lot of time on debugging, and have sufficient tests for the other algorithms for this week, so I'm hopeful that I can still earn a Michelin star for the work I did.

[parthsarkar17]

Code

Here is my domination analysis file and my correctness-check script

Summary + How it works

Reusing my implementation for basic block and CFG construction, I built out a tail-recursive function that accumulates a map called block2dominators and returns it if the previous function call did not result in any changes. Every block b is identified by an integer, and the map takes each block to a set of integers that represent the blocks that dominate b.

In order to build out the domination tree, I translated this block2dominators map into a block2strictlydominated map. I then iterated through every three blocks, A, B, and C. If both A and B dominated C and if A dominated B, then I would remove C from the set of blocks that A strictly dominates. I was then left with a map taking each block to the set of blocks that it immediately dominates, which is exactly the domination tree.

To build the domination frontier, I wrote code where, for every block A and for every block B, if B is not strictly dominated by A and there exists a predecessor of B that is normally-dominated (i.e. reflexively) dominated by A, then add B to A's frontier set. Finally, still happy to say I'm still using only functional code!

Testing

I wrote a function that enumerates all paths in a CFG, given an entry node (which I ensure exists because I made a dummy entry basic block). I made sure not to visit the same node twice by keeping a running set of visited nodes. Then, for each block B, I would take every path that ended at B, transform the nodes of the path into a set, and take the intersection of the sets. This set represents the basic blocks that must execute before (or must include) B in all possible ways the program could execute. This is pretty much the domination set that we computed earlier, so I checked for equality in these sets. If the dominators of every block in a Bril function are equal to the intersection of the CFG paths up to that block, then I print out true and false otherwise.

Then, I wrote a Python script to call my binary on every file in the /benchmarks directory. I saw nothing but trues in the output, so I was convinced my implementation was correct!

Hardest Part

I think the hardest part was implementing the enumeration of the paths. I forgot how to implement DFS haha, and also doing it in a functional style took a little thought to get right.

Star

I think my work deserves a star!

[InnovativeInventor]

I implemented a function that computed the dominance relation, iterating over the CFG in reverse post-order. ¹ I then implemented a function that inverts the relation and computes post-dominance. From this, I wrote functions that compute the dominance tree and dominance frontier.

Testing

Testing was by hand and quite limited; I tested on the BBS benchmark that I wrote since I am most familiar with that program. I additionally hand-tested on a few benchmarks from the core benchmark suite. An issue was not many programs were sophisticated enough (or long enough) to have an interesting dominance frontier. More testing on this front would increase my confidence in the correctness of my dominance utilities.

Footnotes

1. https://github.com/InnovativeInventor/bril/blob/lesson-5/lessons/dom.py ↩

[smd21]

Summary
I decided that I'd had enough of Typescript and switched to Python for this task. I honestly kind of hate Python but the switch worked out since I was able to take advantage of the Networkx library structures for a slightly cleaner cfg representation. I really don't know why I was doing the implementation tasks in Typescript in the first place since Python was so much easier lol.
To implement finding the dominators, I first attempted to use the code we learned about in class. Unfortunately, I had to give up on this since I just could not figure out what a post order traversal is or how to write one. I decided to use my worklist algorithm from the previous implementation task. Since I used a custom class for Block objects, I did have some small (but time consuming) problems figuring out how to get custom equality and hashing. Once I figured that out, the rest was pretty straightforward.

Side note: Using the networkx library's DiGraph object to represent my CFG was one of the best decisions I made (for my sanity). Previously, I was storing the CFG as two separate adjacency lists -- one for predecessors and one for successors. Using the Networkx library made my code much more concise and easier to debug, which allowed me to focus more on testing and ensuring my implementations are efficient!

To output the dominance tree, I loop over the CFG and delete any edges A->B where A is not one of the dominators of B. My solution to output the dominance frontier of a given block A is a little bit naive. I first loop through my dominators graph and collect a list of all blocks B where A dominates B. Then, I loop through the dominators graph again and collect all the blocks C where B dominates C but A does not dominate C. This works, but I'm sure there's a more elegant solution out there.

Testing
Testing was by far the hardest part for me since I honestly struggle a lot with implementing graph traversals. I decided to compare my domination to the output from running a "naive" domination algorithm (enumerate all paths from entry to some node n, then take the intersection). I spent a lot of time debugging the naive algorithm since I just kept forgetting to account for edge cases. Once this was done, I ran my code against a few test cases and manually inspected the output. Once this was working, I tested my algorithm by running it on the benchmarks and ensuring that no errors were thrown.

[aw578]

code

I implemented the algorithms to find dominators, calculate a dominance tree, and compute the dominance frontier. The hardest part of the task was probably just understanding the terminology. I didn't realize what a dominance tree was until I had already messed up my implementation, but after actually watching the video things went a lot smoother. I tested my implementation by writing a naive implementation for finding dominators that just traverses every path and calculates the intersection of all paths that travel through a node. I manually verified that the naive implementation output correct results, then compared the naive and optimized implementations for the benchmarks to make sure they returned the same results. For the dominance calculation tree and domination frontier, I again compared the code outputs on the core benchmarks to manually calculated results. I think I deserve a Michelin star for all the manual verification ...

[KabirSamsi]

Partner: Noah Schiff (@noschiff)

Code

Summary

Our implementation for global analysis was done in TypeScript, building up on the infrastructure which we had set up in the previous two sections. In line with the way the project was prompted, we had two clear workflows, one in first fleshing out the algorithms as they had been described in the unit, and then implementing slower, more naive and obviously accurate algorithms with which we could verify the correctness of our outputs by confirming that our dominator analyses we indeed correct.

Implementation

We followed the implementations described in lecture and in the videos to develop our implementation for dominators, dominator trees and the domination frontier. A rough summary of our approach is as follows:

Dominators

Here, we used a TypeScript map to map vertices to the nodes which they dominate. Following the algorithm, we then iterated to convergence, repeatedly intersecting the current set with the set of dominated nodes of predecessors.

Dominator Trees

For the dominance tree, we again relied on the ideas discussed throughout the videos. Using an inverted dominance mapping (by inverting our dominator map), we then used second-level strict dominance rules to compute the initial set, before finally removing any values present in the second-level set to construct the entire dominator tree. Ultimately, this tree had the same type as a CFG.

Dominance Frontier

We finally again used the video's techniques to implement the dominance frontier, again using the inverted map structure and analyzing successor nodes in the CFG.

Testing

Testing was split up into three components initially – dominator analysis, dominator tree analysis, and dominator frontier analysis. We later realized that we could optimize this a bit, and merge the first two of these into a test to determine that a) The correct dominators were generated and b) that they are were correctly represented in tree form. Both test components relied on us modifying straightforward and well-known graph/tree algorithms.

Dominator/Dominator Tree Analysis

We were given the following premise for dominators (let's define $A \sim B$ as $A$ dominates $B$):

$$A \sim B \iff \text{All paths from entry to } B \text{ include } A$$

To integrate this into our dominator tree analysis, we expressed the following:

$$\text{All paths from entry to } B \text{ include } A \iff B \text{ is a descendent of } A \text { in the dominator tree}$$

So to assist with this process, we developed two functions:

Dom

The dom function simply does what the assignment handout specified – algorithmically answers the question, 'Does $A$ dominate $B$?' We do so via a breadth-first search traversal of the graph, but with one notable step – we omit $A$. Subsequently, we reasoned that that if $A \sim B$, then by definition there should be no path from the entry to $B$ that does not pass through $A$; thus, removing $A$ should remove all possible paths to $B$. Finding $B$ in the BFS automatically tells us that $A \not\sim B$, and being unsuccessful in the process tells us that it does.

GetDominated

This second function, getDominated uses a postorder traversal of the dominator tree, to compute all nodes in the CFG that a given node dominates. We were careful to preserve the reflexive nature of the dominance relation. The operation is straightforward – recursively compute the dominated descendants of each child of a given node, add the current node as well, and return that.

Tree Analysis

Another worthwhile test here was just to indeed verify that the dominator tree we had constructed was successfully a tree. The previously test sufficiently shows that all relationships it outlines are correct; a simple, algorithmic verification that our ultimate structure (which, in fact, has the same type as our CFG representation) is a tree, simply involves iterating through each edge. This was done easily by performing a variant of Kruskal's Algorithm with Union Find, and breaking if we ever found a cycle.

A Note On Types

For our CFG, we use the type Map<string, Array<string>>, mapping labels of basic blocks to other labels. This extended to how we represented dominator trees (which we further classified as trees via the analysis discussed above), as well as to our dominance frontier.

Domination Frontier Analysis

We outlined the algorithm for this approach around this biconditional statement:

$$B \in \textit{Frontier}(A) \iff (A = B \lor A \not\sim B) \land \exists C \in \text{pred}(B). A \sim C$$

In plain language, that $B$ is in $A$'s frontier if and only if $A$ does not strictly dominate $B$, and there is some $C$ in the list of $B$'s predecessors such that $A$ dominates $C$. Subsequently, in our verifyDominanceFrontier() function, we iterated through each frontier node and within this, each CFG block, making two passes to ensure that both directions were met:

Forward Pass
In the forward pass, we analyze a given neighbor if it is part of a given node's frontier. We assert that if the neighbor is distinct from our current node, is it not dominated by the current node. If this is met, we then traverse through its predecessors (using functionality developed from L4), and search for at least one instance of a predecessor which is dominated by the starting node. If this is found, we conclude that this is a valid dominance relationship in the forwards direction.

Backwards Pass
In the backwards pass, we reverse the check. In the case that we either are dealing with a case where node = neighbor, or where the current neighbor is not dominated by the current node, we then scan to see if there are any predecessors which are dominated by node. If there are not, then this isn't a valid frontier candidate; otherwise, we assert that it must be.

Thus, with both directions satisfied, this completes a thorough test that the dominance frontier has been correctly computed.

Further Testing
We also ran our implementation against the many turnt benchmarks, to confirm that tests were passing as desired. We had an interesting situation where our loopcond output was not matching the desired result; we later realized that in the cases that the entry block served as a successor to any other basic block, the provided implementation was adding yet another (empty) basic block into the CFG, that would point to the prior entry node. Once we realized this, our tests were successful.

Takeaways

This was definitely an invigorating assignment focusing us to both use skills in implementing the proposed algorithms for dominator analysis, but also relying on our fundamentals working with graphs and trees to develop good tests. Each subsequent assignment has also given us the opportunity to go back and clean up our code, focusing on writing with good types and correct implementations.

This unfortunately was a lot later than desired, but spending the time to really get through this implementation has really ensured our full understanding of the material, and we are excited for this next mission!

[ethanuppal]

To check if it's a tree, could you check that it's connected with DFS and then count the number of vertices and edges? Or does using Kruskal's give some more information?

[KabirSamsi]

That is a good approach; one which we could definitely have employed. There are no weights between basic block connections in the CFG so there's no real added information, I guess.

In part it was also just fun to experiment with using Union Find to verify our construction!

[gerardogtn]

Code

I implemented a few functions related to dominators:

• "is dominated by": Given a node n, the set of nodes that dominate n. This was implemented using the algorithm that we covered in class and i referred to it as the dominators graph in code.
• "dominates graph": While writing some functions, I sometimes found it easier to think about the inverse relation, i.e. given a node n, the set of nodes that are dominated by n. So i implemented a function flip_doms that flips the relation, as a utility it also supports stripping reflexive relations from the graph.
• I then implemented the immediately dominates graph, I used two approaches:
  • Naive implementation in O(n^3) complexity from directly translating the mathematical definition of immediately dominates.
  • Search based implementation: Process nodes from the ones with the least dominates relations to the most dominates relation, marking those that have already been visited as such.
• Building the dominator tree was trivial once the immediately dominates graph was built as it just involved recursively visiting nodes to build the tree structure.
• Finally I implemented the dominance frontier with a simple algorithm from the definition.

For testing I used a couple simple bril scripts to verify that the algorithms were working as expected, and for more through testing on more complex scripts (in the benchmarks dir) I spent most of my time making sure that the outputs from both of the immediately dominates implementation matched.

I'm still pretty happy with some of the decisions in the way i've modeled Cfgs, mainly in that graphs use integer ids that can later be mapped to the labels in the source, as that simplified several parts of the algorithm and allowed me to reason and test the implementations on arbitrary graphs. Overall, I found the assigment fun as to implement a few algorithms on graphs.