Lesson 5: Global Analysis

[sampsyo]

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

[michaelmaitland]

Implementation

I implemented utility functions:

1. find_dom which takes a function and returns a mapping where keys are all blocks in the function and values are the blocks that dominate that key.
2. dom_tree which takes a function and returns a dominator tree rooted at the entry node to the function
3. dom_frontier which takes a function and returns a mapping where keys are all blocks in the function and values are the blocks that are the the dominator frontier for the block corresponding to the key.
4. print_tree which takes a tree returned by the dom_tree function, and prints out the graphviz code to view the tree.

Finding dominators

The find_dom function first computes the reverse post order traversal of the cfg starting with the entry block. This code can be found here. I implemented the post order traversal using DFS. In each recursive call, we make an O(n) lookup to see if we visited the node we are at. If we have visited it, we refrain from visiting again so we don't endlessly follow cycles. If we have not visited it, we add it to the visited list, DFS search the successors, and then add it to the path we are building. We maintain a separate visited list and path list because we want the post order path, but need to process visited nodes before we recurse to avoid infinite recursion. One improvement to this DFS would be to make the visited list a visited set for faster lookup. The reverse_post_order function just reverses the path returned by post_order.

The rest of the find_doms function is almost exactly 1:1 with the pseudocode discussed in class.

Testing Finding Dominators

Before moving onto building the other util functions, I wanted to be confident of my solution since the other functions would rely on this one. I created a test script which takes a bril program along with a command line argument. I added support for a doms argument so we could test the the find_doms function.

It works by calling find_doms for each function in the program. Then, I also implemented another util function all_paths(found here) which returns all paths from the start block of the cfg to all possible exit blocks, requiring that no path has a cycle. Then I call assert_doms which checks the following property holds for all blocks: a block dominates another block when it is on all paths from the entry block to any finish blocks. This assert_doms function must iterate over all items in the doms mapping, all items for each value we are currently on, iterate over all paths, and check to make sure if the current key in the doms iteration is in the path, that the dominated node we are currently on is in the path. More simply:

def assert_doms(paths, doms):
    """
    We know that a block dominates another block
    when it is on all paths from the entry block
    to any finish blocks. We assert this property
    for all blocks.
    """
    for dominated_by, dominated in doms.items():
        for b in dominated:
            for path in paths:
                if dominated_by in path:
                    assert b in path

And to build each path in the first place also has poor time complexity. We must DFS from the start node to all possible exit nodes and concat those lists together.

So in order to test this, the complexity is large, but we are very confident our solution is correct. And note that the complexity to actually find the dominators is solved fast. I ran this against all programs in benchmarks and all tests are passing.

Building a Dominator Tree

I initially tried to implemented the naive approach to building a dominator tree from this paper. However, I felt the wording used in the paper was not descriptive enough to recreate this on my own in a straightforward manner. Instead, I opted to use the mapping returned from the find_doms function I had just written and tested. I implemented this by inverting the find_doms mapping, pruning the inversion to make sure that all dominations were strict, making sure each binding only consisted of immediate domination, and finally constructing an actual tree. I defined a Tree data structure that has a root node and a list of children that can be empty. We can recursively traverse this structure to process it.

The time complexity of this is bounded by the time that it takes for find_doms because it just has a few non-nested iterations over the number of bindings in the mappings returned by find_doms

Testing Dominator Tree

I testing this by writing an assert_tree function that asserted that the tree is constructed correctly, i.e when forall node, forall children, the root immediately dominates the child. More clearly:

def assert_tree(tree, doms):
    """
    Assert that the tree is constructed correctly, i.e when
    forall node, forall childrenn, the root immediatley
    dominates the child.
    """
    if tree != None:
        # Assert tree immediatley dominates all children
        for c in tree.children:
            assert c.root in doms[c.root]
        # Assert holds for rest of tree
        for c in tree.children:
            assert_tree(c, doms)

I ran this against all benchmarks and passed. This makes me very confident of my solution. The time complexity of the test is quite cheap as well. It also passes against the turnt output in the test/dom directory.

Print Tree

I also opted to implement a function that printed out the dominator tree for graphviz. I manually inspected for the files in examples/test/dom to make sure they were correct. I also ran it for all benchmarks and noticed that some functions had an empty dominator tree. This occurred when there was only one basic block for the function. At first I thought this was a mistake, but realized it was correct since the single entry block is not a strict dominator of the entry block, so it should not be in the tree.

Implementing Dom Frontier

Implementing dom_front was straightforward after I had the dom_tree function at my disposal. I walked the tree, adding to the frontier for a given block if a block was a successor but not a child in the dominator tree. I could recursively do this for all nodes in the dom tree.

The complexity for this function is O(mn) because each node in the tree recursively processes all successors within each recursive call. It is likley that m is much too large of an upper bound since most CFGs have much sparser edge sets as successors.

Testing Dom Frontier

Testing this was also straight forward. assert_front asserted that the frontier is constructed correctly, i.e. when all succs to nodes in the dom tree, who are not part of the dom tree themselves are listed as on the dom frontier:

for k, v in front.items():
        for b in v:
            ret  = False
            for d in doms[k]:
                succs = cfg.get_succ(d)
                for succ in succs:
                    ret |= b == block_name(succ)
            assert ret

I ran this for all in benchmarks and passed. The time complexity of this test is worse than checking the assert_tree but better than that of assert_doms.

Overall

Overall, I feel quite confident with my solution because of thorough testing, felt that I had nice clean code, and felt that I worked hard to have good time complexities for my solution. I also felt that I have a much more intimate understanding of domination theory after building and testing my implementation. I'm quite happy about how all this came out.

[sampsyo]

Awesome; thanks for the detailed retrospective! The approach to testing the dominator-finding algorithm was especially neat. One thing I'm curious about is how slow the testing was—no need for specific numbers, but just roughly: did it take milliseconds, seconds, minutes, or hours to test all the benchmarks?

[michaelmaitland]

It took 4 seconds to test all the benchmarks programs. One thing I thought was missing from the benchmark's directory is a program that is quite large. I feel like all programs in this folder are especially short, at least in the size of the CFG.

[sampsyo]

Awesome. Yep; some of the programs run for a long time (in the reference interpreter), but they are all statically quite short (which makes sense given that they're primarily hand-written in isolation over a matter of hours, rather than compiled from a large project developed over years or something).

[zzzDavid]

Implementation

My implementation is here.

• -dom: print dominator of each basic block. code
• -domtree: print dominance tree. code
• -frontier: find dominance frontier. code
• verify: verify dominator results. code

Ideas

Finding dominators

I followed the pseudo code to take intersection of each predecessors's dominator and adding itself.

Build dominance tree

The idea is to identify the immediate dominators in each node's set of dominators. My implementation checks if a vertex's dominator dominates other dominators in the set, if it doesn't, then it's an immediate dominator.

Find domination frontier

My implementation checks the successors of vertices dominated by the current vertex. If it is not dominated by the current vertex, it's in the frontier.

A new thing for me is that a vertex's dominance frontier can contain itself.

Verification

I implemented a verifier to check if the domination relation is correct. For a given vertex and its dominators, the verifier visits all the predecessors of the vertex and make sure every upstream path goes through every dominator. If any upstream path doesn't go through a dominator when it meets the root (entry) block, the verification fails.

Discussions

Finding Dominators with Worklist Algorithm

I remember someone brought up whether we can use last lesson's worklist algorithm to find dominators. I tried this idea and it worked. The implementation is quite straightforward:

• Merge function: intersection. code
• Transfer function: add the label of current block. code

Visualization

I find it very helpful to visualize the CFGl. I may be the last one to know about graphviz for visualization. I implemented a simple visualizer to plot CFG from a Bril function:

[sampsyo]

Awesome! I'm glad the worklist approach worked for finding dominators. That's a clever way to set it up! (And I too cannot think of any counterexamples.)

[chhzh123]

In this task, I implemented several utility functions to construct the following sets of nodes based on the definitions:

• Dominators
• Strict dominators
• Immediate dominators
• Dominator tree
• Dominance frontier

All of them are very straightforward. Code can be found in my repository.

Dominators

The update rule of the dominator is very simple, and I can write it using higher-order functions (functool.reduce) in one line in Python. However, I didn't make the whole algorithm correct in the first place since I naturally initialized all the dominator sets as empty. But the correct way should be initializing the dominator of the entry block as itself, and setting all blocks as dominators for all other blocks. (I noticed someone had the same mistake as mine on Zulip:) )

Another tricky thing here is that I first thought entry block should be the block that has no predecessors, but later I found I was wrong -- if the entry point of a program is a loop, then it may have a backedge which means the first block in the program even has a predecessor. Thus, to make things work normally, the best way is to automatically generate an .entry label at the beginning of the program, so that this entry block will never have a predecessor.

Dominance Tree

To construct the dominance tree, we should first get the strict dominators and find the immediate dominators. Finding strict dominators is easy, which just needs to eliminate the node itself from the dominator set. For finding the immediate dominators, we should follow its definition -- for all the node B test its strict dominators, if some node A is not in the dominator sets of the other node that strictly dominates B, then A is the immediate dominator of B. After we get the immediate dominators, we have already got the edges for the dominator tree. Thus, I built a class Node for the tree representation, which stores its parents and children, and is useful for tree traversal in both directions.

Dominance frontier

We have the strict dominators, and constructing domination frontier is also straightforward -- "A’s dominance frontier contains B iff A does not strictly dominate B, but A does dominate some predecessor of B".

Though the implementation is easy, the result is surprising. From the loopcond-front example, we can see that the node itself can even be contained in the dominance frontier. This may happen when a backedge/loop appears in the CFG. The entry block of the loop may dominate its predecessors from the bottom, causing it to fit the definition.

Testings

For testing, I used a brute force method to test if some nodes are exactly the dominators of a given node. Basically, I used DFS to do the CFG traversal and generate paths from the entry point to the given node. A stack-like structure is maintained. Each time a node is visited, it will be added to the path, and at the end of an iteration, the newly added node will be popped out to restore the previous state. When the traversal reaches the destination node, this path will be added to a global path list. Finally, I test if the dominator is contained in all the paths. If so, the implementation is correct.

[sampsyo]

Good point about the entry block and predecessors! Adding a predecessor-less entry block is a common way to "canonicalize" a CFG, just like creating a unique exit block.

[charles-rs]

Implementation

It's here.
Implemented a couple really cool functions here:

• dominators is a function that, well, computes the dominators. It returns a map from blocks to those that dominate them (e.g. A -> B means B dominates A)
• invert-dominators is a function which gives the map the "other way" which is helpful sometimes
• dominance-tree is a function that returns the dominance tree in hashmap form, which is really just a map from blocks to the blocks that they immediately dominate

I do not support any command line options, as my testing strategy does not involve exposing these functions.

dominators

copy and paste from the lecture really, the most interesting part was probably checking for termination, which cleanly fits into reducing over a list.

dominance-tree

There is almost definitely a better way to do this. I took the definition at face value, and started with a map of dominators and removed anything that wasn't immediate.

dom-frontier

Implemented by calculating a "potential frontier" of all of the successors of the dominatees, and then removing those which are dominated. I messed this up initially since i didn't get the strict/non-strict parts correct.

testing

For this assignment, I thought back to my 3110 days of reading the pragmatic programmer, and decided not to test the dominators since they are a very internal mechanism. Instead, I wanted to implement something that used them, and then test that. I know based on how i implemented it that if the dominance frontier is correct, the rest is probably right since it is heavily dependent on the other stuff.

I chose to implement SSA as my testing strategy, since it was familiar content from 4120, and the reference interpreter can execute the φ instruction. This means i can convert a program to SSA, and then run it back through the interpreter and the output should be the same, which is pretty cool. I used the benchmarks in the repo for this.

This testing revealed the bug that I had messed up the strict/non strict stuff with the dominance frontier. I also found the bug that I wasn't dealing with arguments correctly in SSA, but that's not really a dominance bug.

discussion

This assignment didn't present too many major issues, and I got back into a more comfortable workflow where most of my testing was done at the REPL. This basically gives the power of a really good debugger where I can interact with the code and dynamically recompile it, so it is significantly faster to work with than command line based testing, though that became important to verify that I was done.

[sampsyo]

Wow! If you've done the whole SSA thing, then you've gotten a jump on next lesson's tasks. 😃

[5hubh4m]

Dominator Utilities

I implemented the three dominator utilities in Haskell. The main reason for doing it in Haskell was (aside from the fact that it's fun) I wanted the ability to test my implementation using QuickCheck.

My Main.hs file takes in a JSON Bril program and prints the output of a dominator utility. There is support for the following:

• doms: Outputs the dominators of the CFG of a function.
  dominator :: CFG -> HashMap Ident (HashSet Ident)

• tree: Outputs the dominator tree of the CFG of a function.
  dominationTree :: CFG -> Tree Ident

• front: Outputs the domination frontier of the CFG of a function.
  dominationFrontier :: CFG -> HashMap Ident (HashSet Ident)

Using it is as simple as a bril2json < path/to/bril/program | stack run [doms | tree | front] command.

Testing

Fuzzing with QuickCheck

This was arguably the more fun part. I wrote an Arbitrary instance for my CFG that generates random CFGs. It starts by generating a set of unique block labels, then for each label it selects anywhere from 0 to 2 blocks as successors. My first implementation put the additional condition on the randomly generated CFG that each block should be reachable from the entry block --- but ultimately I encountered two problems with this approach:

• It's not true of "real" CFGs, i.e they might have blocks that are unreachable.
• It made the process of random CFG generation really slow, as testing this property on large graphs is not cheap!

So I resorted to admitting arbitrary CFGs with the change that its blocks have exactly one successor with high probability (to mimic "real" programs; I tried to find some statistics online about the real world programs' CFGs but couldn't). This had two effects; this uncovered a lot of edge cases in my implementation (around CFGs with unreachable blocks) and since this made my CFG generation quite fast I was able to run 10000s of tests which made me quite confident in my implementation (when I later fixed those edge cases).

Specification

I wrote properties that the three utility functions should satisfy, briefly summarized below:

• prop_dominatorsDefn: Dominators of a block are the common blocks in all paths from entry to that block. To check this property I generate all possible paths from entry to that block and take the intersection of that set.

• prop_dominationTreeDefn: To check this property I recursively traverse the dominance tree and verify that the recursive children are the blocks that a block strictly dominates.

• prop_dominationFrontierDefn: To check this property, I test two properties, that the frontier set for a block is exactly one edge away from the blocks that the given block dominates, and that this block does not strictly dominate them.

Results and Experience

I manually verified the output of my functions on the examples given in examples/test/dom folder in the Bril repo. Aside from that I pass all QuickCheck tests.

$ stack test
bril-hs> test (suite: bril-hs-test)

=== prop_dominatorsDefn from test/Bril/Structure/Spec.hs:75 ===
+++ OK, passed 10000 tests.

=== prop_dominationTreeDefn from test/Bril/Structure/Spec.hs:91 ===
+++ OK, passed 10000 tests.

=== prop_dominationFrontierDefn from test/Bril/Structure/Spec.hs:107 ===
+++ OK, passed 10000 tests.

bril-hs> Test suite bril-hs-test passed
Completed 2 action(s).

Implementing first the JSON conversion utilities and then all this in Haskell was a lot of work. I had to think very hard about how to represent the computation of dominators etc. purely declaratively which gave me a greater sense of what these structures are rather than just how to compute them, for example finding a succinct expression for strict dominators, and children in a domination tree was quite challenging.

QuickCheck also quickly decimated many first attempts, and I discovered a lot of subtleties in the definitions. For instance, when finding the dominators, you must initialize the dominators for the entry block to itself and never update it. Another problem was in cases where the CFG is not completely reachable from the entry block, in which case the dominators of a block that cannot be reached from the entry block must be an empty set. Another case was the realization that the domination frontier of a block can contain itself.

[sampsyo]

Wow, the QuickCheck setup does indeed sound like a lot of work! Out of curiosity, how would you roughly characterize the balance of implementation vs. testing work you did? Sounds like maybe it was 75%/25% (where testing was the majority)?

[5hubh4m]

Hard to say since it was some back and forth between running tests -> tweak the implementation -> running tests. But writing the QuickCheck framework and property tests was definitely more work than the actual implementation!

[JonathanDLTran]

Summary

My implementation is found at: dominator-utilities and tests are at tests.

I implemented the dominator utilities suggested in lesson 5, finding the dominators of a node, the strict dominators, the immediate dominator, the dominator tree and the dominance frontier.

I followed the pseudocode and definitions for each of these constructs from the lesson 5 page, almost exactly as stated. For the most part, I found that these definitions worked intuitively, and the algorithm appeared to work, except for some small situations I discovered during testing.

Testing

I wrote several test programs to check my implementation of the utilities. These programs have different structures, such as loops that include the entry, unreachable blocks of code, and one that is a small web of basic blocks. I made these programs small so that I could verify the result manually, by calculating each of these dominator results by hand, and then checking with the program's calculated results.

Results

Here's a simple program that I caused me some trouble with debugging my implementation:

@main{
.cycle:
    jmp .next;
.next:
    jmp .cycle;
}

and the results

Dominators
	cycle is dominated by:	[cycle]
	next is dominated by:	[cycle, next]
Dominator Tree
digraph main {
  cycle;
  next;
  cycle -> next;
}
Dominance Frontier
	cycle:	[cycle]
	next:	[cycle]

Something left desired is making larger CFGs to test on, and making these CFGs be examples of "tricky" edge cases.

To also help validate that the dominators are calculated correctly, I have a function called check_dominators, which verifies that node B really is dominated by node A if every path from the entry to B contains A in it. I don't allow loops in these paths, because I reasoned even if there was a loop, we could remove the loop and continue trying to find our way from the entry to B. To calculate these paths, I repeatedly use DFS from the entry node and search my way towards node B.

This validation function is called every time the get_dominators function is called, to validate the result actually makes sense. I run this on the turnt tests, and no exception is raised, meaning that the validator function cannot find a counter example path to the dominators I found.

I also do the same for calculating dominance frontiers, where I make sure there is at least one predecessor node, of the node in the frontier, which is dominated by the original node. This validation function is also called every time build_domination_frontiers is called.

Difficulties

Implementing dominators ended up being a bit trickier than I imagined. In particular, I was caught off guard by some edge cases when computing dominators, which ended up exposing some confusion that I had with the dominator definitions. This caused me to change some implementational details when calculating dominators. For example, I wrote an example program where the CFG consists of 2 basic blocks (A and B, A being an entry), forming a loop. The naive algorithm computes A as being dominated by both B and A, while B is dominated both A and B. This does not make sense as the path from the entry to the entry does not include B in it. I changed the algorithm to only consider A to be dominated by itself.

Another problem arising over computation of dominators is with unreachable blocks of code. By definition, these unreachable blocks of code should be dominated by every basic block, since there is no path from the entry to these unreachable blocks. However, this produces unintuitive results later on, when computing the dominator tree and the dominance frontier. I decided to do a DFS to find all the reachable blocks of code, and set the dominators of all unreachable blocks to be only the entry block of the CFG. I don't think this is a justified decision, though it appears to give more intuitive results when calculating dominance frontiers in testing.

I also had a few issues with finding a unique immediate dominator, but this was fixed through some debugging, and realizing that I had implemented one of the sub-algorithms incorrectly.

[sampsyo]

Awesome! Thanks for the useful discussion about unreachable blocks; that's an important wrinkle in taking these algorithms into the "real world."

[alaiasolkobreslin]

Implementation

The implementation can be found here.

The code can be run with one argument:

• dominators prints a dictionary mapping blocks to their dominators
• tree prints the dominator tree as a dictionary mapping blocks to their children
• frontier prints a dictionary mapping blocks to the blocks in their dominance frontier

To compute the dominators in a CFG, I first checked whether the first block had any predecessors. If it did, then I added an entry node (with a fresh name) with its successor being the first block. Then I followed the pseudocode we went over in class.

To generate the dominance tree, I first computed the dominators of the CFG. Next, I computed the inverse of this dictionary, which maps blocks to blocks they dominate. Then I iterated through each (a, b) pair (where b is dominated by a) and added b to a's immediate children if the dominators of b were equal to the dominators of a union b

To generate the dominance frontier, I first computed the dominators of the CFG. For each pair (a, b) of blocks in the CFG, I checked whether a dominates b. If not, then I iterate through each predecessor of b, and if a dominates that predecessor, add b to the dominance frontier of a.

Testing

The test file can be found here. The arguments are the same as in l5.py (running l5_test dominators tests the find_dominators function in l5.py)

I wrote a function does_dominate that checks whether a dominates b in a CFG by verifying that all paths from entry to b contain a. To check the correctness of find_dominators, I assert that does_dominate returns true for every a that is supposed to dominate b to make sure that it actually does. To check the correctness of dominance_frontier, I used does_dominate to verify that a dominates some predecessor of b if b is in a's dominance frontier. To check the correctness of dominator_tree, I check that the children of a block in the dominator tree are dominated by that block using does_dominate, and I also checked that each node only has one parent.

Discussion

I briefly struggled to figure out why this test case that I added was marking jmp3 as a dominator of jmp1. This ended up just being a bug in the function I wrote that adds an entry node- I had accidentally wrote the function so that even if the first block in the CFG had an incoming edge, it wouldn't add a new entry node.

[michaelmaitland]

You’re code is so clean and readable!!

[sampsyo]

Indeed! Great work making the Python look like pseudocode for defining the algorithm. 😃

[gsvic]

The pull request for L5 at my repo can be found here: gsvic/CornellCS6120#2

What's New

• Added unit tests that compare the default .out files from the bril repo with the outputs of this implementation programatically. I used pytest and GitHub actions for automated testing when new commits are pushed. Live results can be seen in the following badge.

• Updates to the CFG class(lib/CFG.py). I added the following methods:
  • get_dominatees(): Returns a dictionary where the keys are the node names, and each value is the list of blocks that this node dominates, i.e. {"node": ["dominatee1", "dominatee2", ..., "dominateeN"]}
  • get_immediate_dominators(): Returns the immediate dominators per block. I use this in order to build the dominator tree
  • get_domination_frontiers(): Returns the domination frontier list of each node (in a dict() format)

Implementation

The code for L5 can be found here. All implementations were added ass extra methods to the already existing CFG class.

Methods

Dominators

Implemented as the get_dominators() method. It simply follows the iterative algorithm presented in the class, by constructing the dominators per node by intersecting the dominators of each predecessor until convergence.

Dominator Tree

Implemented as the get_immediate_dominators method.

Domination Frontier

Implemented as the get_domination_frontier method. This method first invokes the get_dominatees() method, which returns the dict of blocks along with a list of the dominated nodes per block. Given a node n, for each dominated node d it iterates through all successors of d. If the successor s is not dominated by n, it's added to n's frontier list.

Check if a Block Dominates Another Block

I created a custom method that checks the validity of the output of the get_dominators(). The method signature is the following:

def check_dominator(self, root, block, dominated_by, path=list(), seen=set())

In summary, it recursively traverses all the possible paths from root to the given block. Along the way, it also constructs the path. When/if block is reached, it checks if the dominated_by exists in the path. If it exists, the method returns True for that specific traversal, or False otherwise. The final answer is computed by recursively aggregating the outputs of all possible traversals from root to block, using a binary and (&&). Even if one traversal returns False, the final answer will be False as well.

An additional test for this method is added in the unit tests.

Testing

Unit tests for each case are provided in the test directory. I borrowed all the test-cases from bril repo. Tests can be run either locally with pytest, or the status can be seen below (same badge as above).

[sampsyo]

Awesome; super cool work setting up GitHub Actions for your tests! Very snazzy.

[atucker]

My code is here: atucker/bril#4

Implementation

I implemented

• Finding the dominators for a function here.
• Constructing the dominance tree here.
• Computing the dominance frontier here.
• A simple way to print short strings in bril mostly here but also here.

Finding dominators

This mostly worked the way I would have expected it to from the video, though python's reduce returns the starting output if there's nothing that it gets reduced with, so I needed to special-case the situation for when there's no predecessors.

Dominator tree

For a while I was trying to keep track of a structure which, for each node in the dominator tree, kept track of its ancestors. It took me a bit to realize that this should always be the dominator set, and so I didn't need to keep track of it separately.

Dominator frontier

The main trick here for me was realizing that predecessors meant predecessors in the CFG, not in the dominator tree, and I was confusedly trying to figure out how something could dominate a node but something that it dominated. After that it was pretty straightforward.

Testing

I tested the dominators, dominator tree, and dominator frontier code using the tests in the examples folder, with everything passing. I also tested the correctness of my dominator finding in a more involved way described below.

Printing

The most fun part of the assignment for me was reading the prompt at the end to figure out how to test your code. My first thought was "I'll just add print statements that tell me whenever I enter a new block". But then I noticed that basic BRIL doesn't actually have strings...

Instead of fixing this by adding strings, I realized that I could just encode short strings as integers while adding the print instructions to the bril program, print the integers while the bril program runs, and then write a python program to convert the integers back into strings. ASCII uses 8 bits per character, and looking through an ascii table I decided that I could get most of what I want by just encoding SPACE - ? and ` - DEL. This is only 64 characters, so I could encode it using 6 bits. Since BRIL uses 64 bit strings, I figured this meant I could have a 4 bit prefix followed by 10 characters which each use 6 bits. For simplicity sake, I right-padded every string with SPACE, so I could just take every 64 bit integer that starts with my prefix and convert it into the corresponding string.

After setting this up, I made a turnt directory where I modify the bril programs to print out which cfg block they're in, run the modified program, save it, and then run a program to check that whenever we see a print statement for a cfg block entry (i.e., any bril output which got covered to a string) the only blocks we've seen before are in the dominator set for the block label we just got to. The turnt script is here.

After that, I filled the directory with some of the other tests we've used. The check code just prints True if everything is okay, so after checking that all the programs resulted in True, I created the .out files.

This setup isn't great in that it doesn't handle >10 character strings at all, but I think a future extension might just be to have a convention where we end on the DEL character (unusable AFAICT in BRIL) whenever we want to append the next string to the current one. I could also imagine a more thoughtfully chosen character set, perhaps by just listing a set of substitutions to convert into/out of in the character encoding/decoding functions.

[sampsyo]

Wow; that string-printing setup is pretty wild! Nice work making that happen.

At the risk of Monday morning quarterbacking, a couple of other ideas that are similar in spirit come to mind:

• You could transform the program to rename all the labels something like, .lab42. Then you could print out those numbers.
• You could invent a string-type extension for Bril and add it to the reference interpreter! 😃

Anyway, I think it was a cool idea to try using dynamic executions for testing. Most folks enumerated the paths statically to check for dominance. But checking actual executions is a nice way to avoid needing to enumerate all the paths.

[susan-garry]

My code is here. The dominator functions are under dom.py, and the test files are under test/dom.

Implementation

Get Dominators

get_dom returns a dictionary that maps each block to its dominators, using the algorithm outline in class. My implementation does not optimize the order of the input to ensure the best time complexity for reducible CFGs. Like many others, I was tripped up by the fact that (1) all nodes in a natural loop will not recognize the entry block as a dominator unless you initialize the set of their dominators to include all blocks, unless they are the entry block, because (2) the entry block may be part of a loop. I solved this second problem by initializing the dominators of the entry block to include only the entry block and only iterating over the other vertices in the graph.

Get Domination Tree

get_dom_tree returns a dictionary that maps every node in the domination tree to its immediate successors using the output of get_dom. I used graphviz to visually verify the correctness of serval of these trees.

Get Domination Frontier

get_dom_frontier returns a dictionary that maps every block in the CFG to the set of blocks in its domination frontier.

Testing

To test get_dom, I initially relied on the output of get_dom_tree and get_dom_frontier, which rely on the output of get_dom, but I ended up implementing a function to calculate the dominators of each block as the intersection of all acyclic paths that end at a given block. When the test argument is invoked, dom.py asserts that the output of this intersection-over-paths calculation is equivalent to that of get_dom. This ensures that for all blocks b, every block in get_dom(cfg)[b] is indeed a dominator of b, and that all dominators of b are in get_dom(cfg)[b]. This also allowed me to test additional programs without examining them by hand. The other functions were verified by testing them on small examples.

[sampsyo]

Great! Thanks for the detailed explanation of how to set up the enumerate-all-acyclic-paths approach to testing.

[orkosinha]

My implementation is here.

Usage

usage: lesson5.py [-h] [-c] [-d] [-dt] [-df] [-v]

options:
  -h, --help          show this help message and exit
  -c, --cfg           display cfg in dot
  -d, --dom           compute dominators
  -dt, --domtree      compute dominator tree
  -df, --domfrontier  compute dominance frontier
  -v, --verify        test dominators

Example: bril2json < ../bril/benchmarks/orders.bril | ./lesson5.py -c -d

Dominators

This was a fairly straightforward implementation from the algorithm in class. However, I also encountered my first major bug which I figured out from testing with my check_dominator.check_dom function which computes all paths and check if dominators actually do dominate the labels they say they are dominating. Essentially, I never had a notion of an entry block which never has anything dominating it.

Something like this causes issues with no entry block being defined. My quick solution was to track the first block in the function in my CFG class, check if the update to the dominators is affecting my entry block and if they are just discard the result. It's not a very elegant solution, but I found it to work on all of the bril/benchmarks directory's bril programs.

Dominator Tree

Now I needed to invert the relationship and to build the tree a bit easier from the top down. I also needed to make it immediate to get the levels on the tree and strict to avoid self references. The tree is just a tuple tree.

Dominance Frontier

I was a bit confused about the definition at first, particularly with the meaning of predecessors, but I eventually understood it meant the predecessors of the CFG. Then the implementation was pretty straight forward, but it is something that I struggled with for a while.

Testing

I have a pretty basic check_dom function which I mentioned earlier. I made it as soon as I completed by regular dominator function as both dominator tree and dominance frontier rely on a correct dom. I checked over the bril/benchmarks directory and some tests I wrote to address the entry block issue I was having.

[sampsyo]

Awesome! Thanks for being honest about the trickiness of keeping things straight between "successors in the CFG" vs. "children in the dominance tree" or similar. That tripped more than one person up!

[tonyjie]

My code is here

Implement dominance utilities

dom.py implements several dominance utilities with different input arguments (they are complimentary, you can use them together).

• -dom: Find dominators for a function.
• -tree: Construct the dominance tree.
• -frontier: Compute the dominance frontier.

Examples:

bril2json < test/while.bril | python3 dom.py -dom -tree -frontier

Test Correctness

All the testcases under test/ (loopcond and while) would pass. The results are verified manually.

cd test/
turnt *.bril

Test the Implementations Algorithmically

I use DFS (Depth First Search) algorithm on the Control-Flow-Graph to test the implementations. Using DFS traversal, I can get all the possible paths from Entry to B. Then I check if every path include A: if so, A dominates B correctly; otherwise, A is not the dominator of B.

The code passes all the testcases. If I manually make it wrong as follows in the benchmark loopcond:

dom['endif'].add('then')
dom['endif'].add('exit')
dom['body'].add('then')

The testing function would print the error message as follows:

then is not the Dominator of body
exit,then is not the Dominator of endif

Discussion

It is worth to note that when testing the test/while.bril initially, my code fails. After investigating, I found this is due to the first block has in-edges. We need to ensure that a CFG has a unique entry block with no predecessors to make the algorithm work. So I add another entry block and jump to the original first block to solve this problem.

[sampsyo]

Awesome! Good idea to add an extra entry block so you are guaranteed to have one with no predecessors.

[anshumanmohan]

My work is here, split into two files:

• dom.py, where I construct the basic domination relation
• dom_extensions.py, where I use the basic relation to construct relations for strict domination, immediate domination, and the domination frontier.

It was a reasonably straightforward process, more or less proceeding as discussed in class. I found myself wrestling with Python a fair bit; I'm realizing that I really am a functional programmer at heart and so I tend to want/expect things like partial application and immutability. That said, who among us can argue against a Python gem like if v1 in strict_doms[v2] and (v1 not in strict_doms[v3] for v3 in strict_doms[v2])? It's poetry, dammit.

I tested my work using Turnt the whole time, borrowing from the course repository's examples/test/dom/ and also adding skipped.bril from a previous lesson. I'm glad I did, since it proved to be an interesting example (see below). Compared to what others seem to have done re: testing, my work is quite meagre, essentially just "testing by eye". Plus, it wasn't even that easy: variations in Python's set-ordering meant that Turnt repeatedly threw false alarms.

I ran into two interesting issues:

Issue 1: Entry labels that have predecessors. I was a bit stumped but then found a helpful thread about it on Zulip. I followed the advice given there and was out of the woods pretty quickly. Many thanks to @5hubh4m for posting that.

Issue 2: My example skipped.bril shows what happens when one tries to compute the domination relation using a CFG that is malformed (for some definition of malformed). The CFG marks "l0" and "l1" as the preds of "end", but in fact "l1" is unreachable (it has no preds) and will always be skipped. Having it around in the CFG causes an incorrect calculation of the dominators. Had we run a cleanup pass using CFG data before running the domination algorithm, we would have killed off the unreachable block "l1" and avoided this issue.

[sampsyo]

On "it's poetry, dammit": yeah! I enjoy map and reduce as much as the next functional programmer, but list comprehensions sometimes feel like exactly the right thing for algorithms like this.

One engineering-level comment: you mentioned getting false alarms because Python's sets got ordered in different ways. It's pretty common in compilers to need to counteract arbitrary/nondeterministic hash-table ordering. In Python, it's often as easy as just running your final set through sorted(...) while printing it to force a deterministic order.

[andrewb1999]

Sorry for the late post! My code can be found here.

Find Dominators

I provide a function find_dominators to find the dominators of a given CFG. This function uses the algorithm given in class to find dominators. Vertices are iterated in reverse post-order to achieve linear runtime on reducible CFGs. Special care is required for the entry node, which must be initialized correctly and not modified during the iteration. Output is given as a HashMap from String to a HashSet of Strings that provides the dominators for that block. find_dominators_num is also provided which returns the same output, but with block numbers from the CFG rather than block names. This method makes it easier to access information about a block in the CFG.

Form Dominance Tree

The dominance tree is represented as a pair of rust structs, using the arena allocation pattern. Each tree node has a block label, a parent index, and a vector of child indices. The tree is constructed by first finding the immediate dominators, which is determined using the definition directly, then using the immediate dominators to construct edges in the tree.

Get Dominance Frontier

The dominance frontier is computed directly using the definition that A's dominance frontier contains B iff A does not strictly dominate B, but A does dominate some predecessor of B. The dominance frontier is also represented as a HashMap from a String to a HashSet of Strings.

Testing

A testing framework for dominators is built in test.rs. It compares the computed domiators to the naive algorithm for determining if one block dominates the other, by computing all paths from the entry node to B and seeing if A is in all those paths. This is slow compared to the real dominators algorithm, but still runs within 0.2s user time for small test cases (thanks Rust!).

Arena Allocation

One of the more challenging parts of this assignment for we was how to represent the dominance tree correctly in Rust. I struggled for a bit trying to use a more C-like style to point tree nodes to each other, but ended up learning about the wonders of arena allocated data structures. In this pattern, all nodes are owned by a vector in a parent struct, and then the "pointers" are actually just indexes into the vector that owns all the nodes. Using this pattern you are able to completely avoid the challenges of ownership and borrowing that arise in tree-like data structures.

Example arena allocation pattern:

#[derive(Default, Debug)]
pub struct DomTree {
    arena : Vec<DomNode>,
    num_to_id : HashMap<i32, usize>,
}

#[derive(Default, Debug, Clone)]
pub struct DomNode {
    pub idx : usize,
    pub label : String,
    parent : Option<usize>,
    children : Vec<usize>,
}

[sampsyo]

Great! I'm glad the "exhaustive" approach to testing the dominator algorithm turned out to be reasonably fast in terms of wall-clock time.

It's also really interesting to read about your "flattened" tree data structures. Those are definitely a good way to work around Rust's inherent awkwardness with graph-like data structures. And I'm sure they also come with performance (i.e., locality) benefits—those would be interesting to measure someday.

[andreyyao]

Sorry for late post. My implementation is here. One might also want to check out the related files graph.ml and graph.mli.

Find dominators

I implemented a function reverse_post_order, which basically finds the reverse post order of an input cfg. It was actually not as difficult to implement in functional style as I imagined. I just did a recursive function folding on the subtrees of each node. The accumulators for this folding function include a set of strings to record which nodes have been visited, as well as a list of nodes representing the reversed post order, which really just functions as a stack because in OCaml you prepend to a list in O(1).

I wrote a helper function step_dom to take in the current dominators map and a block b and return an updated dominator block with just doms[b] updated, based on the algorithm from the lecture 5 page. A little trick is that I make step_dom return None iff there is no change in dom[b].

Before going on I should mention that the dominator map is represented as a bidirectional graph where edges are unlabelled. Thus the successors of each node is exactly its dominators. More particularly, succs g n returns the set of succs of n in graph g. One advantage of doing so is that there is no need for an additional pass to invert all the edges of dominator graph to get the submissive graph. The submissive graph can be simulated by looking at predecessors.

The function dominators calls step_dom repeatedly until convergence, which happens only iff for all the nodes in the cfg, step_dom returns None. In the function we initialize a graph to have every node having successors as all the nodes. This sounds expensive, but OCaml internally only construct one instance of such "set of everything", so it's fine.

Dominator tree

The dominator tree is also represented as a graph. It is actually just a BFS on the graph starting from the entry node. I attempted to do the BFS functionally, but it felt quite unnatural, so i resorted to imperative ways. I used a stack to basically store the edges of the tree to be constructed, a queue for the BFS algorithm, and a Hashset to keep track of which nodes have been visited. All of this is inside a while loop. (I haven't written while loop many times in OCaml, and it felt quite satisfying...) Oh and when doing the BFS, self-edges are ignored.

Dominance Frontier

[TODO edit later] I haven't finished implementing this, but it should be easy.

Testing

I have written a few property tests to ensure that my dominance graph is working properly. The tests require that a given dominance graph is a partial order. In graph theoretic terms, every node needs to have a self-loop(reflexivity), there can be no loops except for self-loops(antisymmetry), and if node v is reachable from v by some path then there is an edge from u to v(transitivity). However these tests were written before I changed some type signatures, so I will need to update them.

[TODO test dominance tree]. Haven't gotten around to implementing this, but I plan on first checking that it is in fact a tree: there is a unique path between any two nodes. This can be checked efficiently by doing a BFS, DFS, or whatever graph search starting from the entry node. For a graph to be a tree one must not be able to visit the same node twice. I believe that given a dominance tree, if one takes the transitive closure of tree and then add self-loops to each node, it should give you back the original dominator graph. These two properties combined should suffice to show that the tree is correct.

Difficulties

I spent many many more hours on this task than I should have because I kept switching my implementation around to make my program structure more "elegant", whatever that means... If you dig into my git commit history(with the very unhelpful commit messages), you can see that I fiddled around with many different implementations of the dominance map. I even changed the cfg representation many times. Initially my dominance map is just a dictionary from strings to string sets. However the step of inverting the edges to get the dominance tree(isn't it really the submissive tree?) felt clunky, so I tried using the ocamlgraph library. But that thing isn't suitable for what I want because it doesn't view vertices with the same label as the same vertex... So I wrote an entire generic graph module from scratch, which is now being used for both the cfg and the dominance analysis. In hindsight this is really silly, but I did have quite a bit of fun in the process. It also allowed me to output graphviz files from generic graphs, like this:

Updates:

{
In the process of doing SSA I found many many bugs in my dominators inplementation... First of all, the terminologies are a little confusing to be honest, because the "dominators" algorithm gives a map from block b the nodes that dominate b, whereas the "dominator tree" is basically a map from a block b to the nodes immediately dominated by b... Shouldn't it be post dominator tree instead? I don't know...

Second of all, finding the dominator tree is not as simple as doing a BFS on the dominator graph. In fact, since the entry dominates everything, BFS just gives you a tree of depth 2 that looks like a leaf rake... I resorted to just filtering the "dominated nodes" of b by the idom relation, which is inefficient but intuitive.

Testing -

I did a few more tests ensuring that the dom tree is correct. same_vertices just makes sure that the dom tree and the dominator graph have the same node set. check_degree makes sure it is a tree: in degree of each node must be at most 1. idempotent makes sure that the dominator tree computed from a dominator tree is equal to the original(so the edge set really is minimal)

}

[sampsyo]

Very interesting approach to use a graph to represent dominators (instead of merely the dominator tree, which obviously wants to be a graph)!

While I'm impressed at the learning that happened along the way while searching for "elegance," I also want to encourage you to continue reminding yourself that the perfect is the enemy of the good. So long as you're getting something useful out of reshaping your implementation for elegance, that's great! But if it ends up taking too much time, there is something to be said for getting things done in the quickest, dirtiest way first—and then only cleaning things up in retrospect.

[yy665]

Sorry for the late post. Here is my implementation

The implementation for all three tasks is under examples/self_dom.py. The codes are fairly straight forward, but I did not have enough time to actually refine it (Sorry about that), so it's more like a proof-of-work and might not be edge-case-prone.

Find Dominators

My implementation works exactly in the same way as pseudo-code provided in lecture. Initially, I tried to set up the dom relation such that every block maps to empty set from the very beginning, as I feel like this is more intuitive and should work as intended. However, it turned out that having every block maps mapped to all blocks is more efficient. Because the first approach requires a couple of ramping up iterations. The rest is fairly straight-forward and I didn't have much issues. The only thing I concerned about is that I reused the code from form_blocks and cfg which I assumed to provide block_map in reverse post-order already. This might not be true, and I should probably have reorder the vertices myself.

Dominator tree

This might be the hardest part of the assignment and took me sometime to actually get the algorithm right. Still, my implementation on Dominator Tree might be overcomplicated and inefficient. I used multiple loops over the computed dom relations from part 1 to generate the dominator tree. My algorithm works as follow:

1. For each vertex, remove its reflexive dominators(a.k.a. self). (which leaves only the set of vertices that strictly dominates this vertex)
2. Find immediate dominators of each vertex. (when there's only 1 vertex left, the last one has to be the immediate vertex)
3. For each immediate dominator, add the vertex to its children.
4. For each vertex, remove the set we found from step 3. (Since for any vertex v, they are either processed already, or are not immediate dominators of v)
5. Remove vertices that has no (processed) dominators left, to achieve progression.

Dominance Frontier

This is the easiest part of this assignment. I basically just followed the definition and add the set of vertices that satisfy the properties. However, my implementation is inefficient (O(n^2) worst case) and I still need to figure out how to make it faster.

Testing

I have tested my implementation on all tests under test/dom, with turnt and human observation. At the moment, I am still writing tests for edge-cases.

[sampsyo]

Interesting description of the dominator tree algorithm! If you do end up coming up with ways to simplify the algorithm later on, it would be interesting to hear what insights allowed you to do that.

[barabanshek]

Hi, sorry for the later post too. My implementation is here.

It includes passes for:

• Finding dominators for a function: the naive algorithm from the lecture;
• Constructing the dominance tree: an algorithm that takes the list of dominators from the previous step and reconstructs the tree out of them in reversed order;
• Computing the dominance frontier: a naive algorithm that (1) figures out which nodes a given node does NOT dominate, and (2) checks if it dominates any predecessor for each of them.

Some example of the output for loopcond-front.bril:

Dominators:
 {0: [0], 1: [1, 0], 2: [2, 1, 0], 3: [3, 2, 1, 0], 4: [4, 2, 1, 0], 5: [5, 1, 0]}
Dominator tree:
 {0: [1], 1: [5, 2], 2: [4, 3], 3: [], 4: [], 5: []}
Domination Fronties:
 {1: [], 2: [1], 3: [], 4: [], 5: []}
Correctness for get_dominators() ->  True

I also added the general test pass for finding dominators. Here, I just implemented the very naive DFS-based walk across the CFG to get all possible paths between the root node and the target node and checked that all the paths indeed include the dominant that we are verifying. The algorithm repeats this for all dominants and for all nodes.

I tested the implementation of the dominators finder with the test above, and for other passes, I just verified the output manually on the given test cases and some other manually-created test here.

[sampsyo]

Sounds great! Thanks for showing off your example output.

[thomasyang18]

My implementation is here.

• Another cool algorithm! I feel like this is similar to workflow, but not really since I'm pretty sure in actuality the sets can only possibly shrink at every iteration. It still has that weird magic though of just working out. I also implemented a post-order DFS traversal because that apparently works. To validate this, I did an O(n^3) brute force check to check that node A has node B in its "dominators" set iff B dominates A. To check that if a node dominates another, you try to actively avoid the dominator and see if the dominatee was reached. This assumes that all nodes are reachable from the entry block, which actually caught an edge case where in some bril programs, you can have statements directly after jump/return statements, and you needed to remove the "dead nodes" from the CFG. I'm not sure if the benchmark that had that was intentional or not, but it was useful either way.

• Building the dominator tree was interesting, I'm not sure of this approach is entirely correct. You go in assuming that the dominator algorithm will give you a tree, and that each list of dominators for each node is just the DFS-traversal you would see in the tree. So you sort in ascending order in terms of list size, and set the dominator of v with maximum depth as your parent. I wrote a pretty convincing test (dfs through the tree and check that the dfs stack was the same as dominators at each step), so the "going in assuming that the dominators were formed a tree" caught quite a few bugs related to my initial understanding of dominators (for example, I had to make sure that the entry node always had a set of itself and nothing else).

• My dominator frontier algorithm was literally just an o(n^4) brute force check. Across all pairs (A,B), if A does not dominate B, and A dominates any predecessor of B, then B is in the domination frontier of A. Was even too lazy to implement preprocessing to reduce this down to O(n^2). On the bright side, I don't think I can write a simpler validator than this, so I didn't write a test for this one, since it would be pointless. I really want to see if you can use LCA to speed up this algorithm faster than O(n^2), but the bottleneck is still that I think you have to consider across all pairs the domination frontier, so LCA probably wouldn't speed things up.