Lesson 5: Global Analysis

[sampsyo]

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

[vivianyyd]

Dominator Code and Test Code

Summary

• We (Will and I) did our implementation in Kotlin (built on top of the code from previous lessons).
• We implemented methods to find dominator relations, construct dominator trees, and compute dominance frontiers in CFGs.
• We also implemented an improved CLI and a testing framework to quickly test that our dominator relations were correct

Implementation details

• The algorithm for computing dominators, although similar to, wasn't computed using our dataflow framework from last lesson.
  However, it was reasonably straightforward - we compute the "dominated" and "dominating" nodes for each node in the CFG.
  We wrote functions to convert these maps into strict dominators, and immediate dominators.

• The immediate dominators information is then used to construct Dominator Trees (which we can also visualize using Graphviz). Below is a visualization of the tree for ackermann.bril:
  

• To implement the testing framework, we did a naive algorithm: suppose node A dominates B. We performed a DFS to find
  every path from the entry to B. We then took the intersection among all paths and ensured that A was included.

• One case we missed at first is that in which the entry node has predecessors. However, this was straightforward to fix.

• Another bug we ran into is when unreachable nodes are involved. If we compute dominators by intersecting those of the
  predecessors, but one of our predecessors is unreachable, we may falsely get an empty set. We decided to first prune
  unreachable nodes before running the algorithm to find dominators.

How did you test it? Which test inputs did you use? Do you have any quantitative results to report?

• We wrote a checker which naively finds all paths from the entry to a given node and checks that the intersection of
  nodes on that path is equal to the dominators computed by our analysis.
• Using the new testing framework, we could easily run all test files at once to compare behavior between the naive and
  actual implementations. We used all files in core in addition to a few handwritten tests.

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

• The hardest part was probably deciding when to represent maps as node -> {dom[node]} or node -> {n | node in dom[n]}.
  We decided to just implement both since this makes lookups easier
• Testing was also tricky since the number of paths through the CFG was pretty large. We solved early bugs by creating
  hand-made tests that were mostly control-flow but small in code size

[jdroob]

dominators.py and dominators_test.py

Summary
@20ashah and I completed the assigned tasks of:

• Computing the set of nodes, S, which dominate some node, n, in the CFG

• Computing the dominance trees of arbitrary CFGs

• Computing the dominance frontier of an arbitrary node, n

Implementation details

• To compute the dominators of each node, we implemented the algorithm presented in lecture (if time allows, we will try to implement the O(n) version of the algorithm).

• With each node's dominance information available, we implemented a boolean function to determine whether some node, A, strictly dominates another node B. We implemented an analogous function for immediate dominance relations. With this information at our disposal, we implemented a function to construct a dominator tree given an arbitrary CFG

  CFG for function: @f
  

  Dominator Tree for function: @f
  

  CFG for function: @main
  

  Dominator Tree for function: @main
  

  CFG for function: @pow10
  

  Dominator Tree for function: @pow10
  

CFGs and Dominator Trees for functions in mandelbrot.bril

To implement tests for each of our features, we did the following:

• To test the first feature (computing the set of dominators for some node), we implemented a DFS-based algorithm to find every path from entry to a node, A. Next, we took the intersection of each of those paths which, by definition, returns the set of dominators of A. We compared this to the set of dominators we computed using the algorithm discussed above to confirm the correctness of our dominance sets.

• To test the second feature, we assumed that the "set of dominators test" passed (when it didn't we ignored these results). Since the "set of dominators test" passed, we knew that the dominators that we computed for each node were correct. This meant that we could use this information to confirm that the dominance tree was correct. We confirmed the dominator tree's correctness by confirming that # nodes in dominator tree == # nodes in input CFG and by traversing the dominator tree and: (i) confirming that each parent node, A, strictly dominates each of its child nodes, B, (ii) for each node, A, look at its child node, B, and check every other node in the CFG to confirm that there is no other node that strictly dominates B and is strictly dominated by A

• We used a similar approach to test the dominance frontier feature and assumed that the "set of dominators test" passed (and if it didn't we also ignored these results). We traversed our CFG, and checked that for each B in our computed dominance frontier of A, A did not dominate B and there existed a predecessor of B that was dominated by A.

How did you test it? Which test inputs did you use? Do you have any quantitative results to report?

• To test our implementation, we wrote individual "testing functions" for the dominance computation, dominance tree construction, and dominance frontier computation.

• For the dominance computation test, we passed a vertex, our set of doms and the CFG as input. If any vertex's dominance set was incorrectly computed, the test returned False.

• For the dominator tree computation, we provided the constructed dominator tree and confirmed dominators map as input. If any parent-child relation was incorrect in the dominator tree or if the # nodes in dominator tree != # nodes in CFG, the test returned false.

• For the dominance frontier test, we provided the computed dominance frontier, the confirmed dominators map, a map that stores each node's set of predecessors, and the CFG as input. If any node was incorrectly placed in some node's dominance frontier or if a node was missing from that node's dominance frontier, the test returned False

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

• The hardest part was handling a bug when testing the dominator sets. The test for this feature computed the intersection of all paths from entry to some node, A. Our feature computed A's dominators by taking the intersection of each of its predecessor's dominator sets. If one of its predecessors contained an unreachable path, the dominator set for A would yield an empty set or some other strange result. To remedy this situation, we used a DFS to compute the set of all reachable nodes from the entry point of a CFG. Next, we removed any nodes that were not considered "reachable". This resolved the "unreachable predecessor" bug.

• Computing dominance frontiers was a little tricky when we ran into the following situation: node A is a predecessor of node B but A does NOT dominate B. Since A dominates itself, this implies that B is in the dominance frontier of A. It was strange to find a case where a node's successor is also in its dominance frontier but given the definition of a dominance frontier, we determined that this was still correct.

Sources:

• Finding all paths from entry to a vertex in a directed graph

[20ashah]

Another source that we used was for implementing a dfs traversal of the cfg from the entry node to see all the nodes that can be reached from the entry block. We used this to eliminate unused blocks before computing the dominance relations.
Source: https://favtutor.com/blogs/depth-first-search-python

[NgaiJustin]

Summary

• Repo (link)
• Dominators for a Function (link)
• Dominance Tree (link)
• Dominance Frontier (link)
• Validate Dominators (link)

small	loopcond	perfect

Details

Dominators of a Function

I first implemented the naive algorithm described in lecture to find the dominators of a basic block in the CFG. After this, I implemented the reverse post-order optimization. I thought about extending my current CFG data class representation to support the storing of dominators of a node, but I ultimately decided to make a general “node” class that would represent a block. This “node” class can then be instantiated as a CFG block or contain more information in the form of a dominator tree. This had the added benefit of making my visualization functions much more reusable which made me quite happy.

Dominance Tree

Leveraging the dominator searching function, I implemented a function that would construct a dominance tree given a mapping of nodes to their dominators. This was a simple pairwise search. A potential extension could do some compression on the pairwise searches for better runtime. With the generalized representation of a “node”, I was able to reuse a lot of the CFG visualization code that I wrote for the last task to visualize the dominance tree.

Dominance Frontier

Again leveraging the dominator searching function, I implemented a function that would find the dominance frontier of a given node and entry node. The implementation was a couple of lines of set operations that were modeled on the definition of a frontier.

Dominators and Dominance frontier Visualization as GIF

As a means to inspect and test my dominator searching and dominance frontier functions, I decided not only to create a graphviz representation of the dominators and dominance frontier, but I integrated the visualization as a GIF across all the nodes in the CFG. I leveraged the library that I implemented from the previous lesson task. In the visualization, the labeling is the following

• key node: blue
• dominated node: red
• frontier: red-dotted
• rest: black

Quality of Life

While refactoring my node class, I decided to also update some of my util functions to be more reusable and have a more general CLI interface. I extended my load function to also do CLI flag validation.

Testing/Evaluation

I wrote a validator function that takes in two nodes (A and B) and the CFG nodes, and returns if A dominates B. I also implemented another validator function that checks if A strictly dominates B. The function can be easily inverted to check post-dominator relations too. This was a simple brute force check—doing BFS to list all paths from the entry node to B and then checking to see if A is in all the paths. A small optimization can be done for early terminating with cached paths.

I also visually inspected the dot graph outputs for the dominator tree and the dominance frontier on some small handwritten examples (small.bril and loopcond.bril) and then extended them to larger test cases in benchmark/core. I also inspected the GIF output.

Difficulties

Testing the dominance frontier was a little confusing at first. With the many bril programs that I tested on (including ones from the benchmark/core as well as handwritten ones) a lot of the nodes had empty dominance frontiers. This led me to debug and iterate multiple times on my implementation only to eventually realize that my initial implementation was actually correct. In retrospect, I should’ve tested on an example where I knew what the dominance frontier was from the start (in a true test-driven development style).

[alifarahbakhsh]

Link to the repo

I have implemented dominators, the dominance tree, and the dominance frontier.
I have also written tests for the first two.
I did not, however, include a test for the third one, as I felt that the test itself is as complex as the task, and one has to resort to manual inspection to be sure of correctness.
The test - which is a script - goes through the benchmarks in the core folder of the canonical Bril benchmarks.

The highlight of the test was assessing the correctness of the dominators:

1. I first removed the backedges.
2. Then, for every given block, I recursively computed the paths from the entry to it.
3. Finally, I checked to see whether the dominators of this block are included in all of the paths.

The biggest challenge that I had was the reflexivity of the dominance relation, as it created several edge cases.
I also encountered several of the cute observations mentioned in the comments above:

1. B is in A's dominance frontier if it is a non-dominated successor of A, since A dominates itself.
2. Most blocks have an empty dominance frontier, which makes the output seem wrong at the first glance.

[adi-lb-phoenix]

Greetings @alifarahbakhsh @MrAliFar . Firstly this repo has been great help in understanding implementations
I have a doubt regarding the function get_dominators .

so you have written the code as follows

def get_dominators(_cfg):
    dominators = dict()
    dominatees = dict()
    for _, func in enumerate(_cfg):
        ### Initialize the dominators set.
        dominators[func] = dict()
        dominatees[func] = dict()
        block_names = list(_cfg[func].keys())
        for name in block_names:
            if name == "entry":
                dominators[func][name] = ["entry"]
                dominatees[func][name] = ["entry"]
            else:
                dominators[func][name] = block_names
                dominatees[func][name] = []

        has_changed = True
        while has_changed:
            #print("going again")
            has_changed = False
            for _, block in enumerate(dominators[func]):
                if block == "entry":
                    continue
                res = intersection(block, _cfg[func][block]["predecessors"], dominators[func])
                #print(f"block is {block}, res is {res}, doms are {dominators[func][block]}")
                if not res == dominators[func][block]:
                    has_changed = True
                dominators[func][block] = res

lets look at the intersection function :

def intersection(_block, _preds, _dominators):
	res = list(_dominators.keys())
	for pred in _preds:
		res = list(set(_dominators[pred]) & set(res))
	if not _block in res:
		res.append(_block)
	return res

so in the get_dominator function dominators[func][name] = block_names , meaning dominators[func][name] will contain all the blocks as the dominator .

so when you call the intersection function as below:
res = intersection(block, _cfg[func][block]["predecessors"], dominators[func])

so in the intersection function : def intersection(_block, _preds, _dominators):
res = list(_dominators.keys()) -> this will contain all the blocks present in the brill code .
set(_dominators[pred] -> this basically will contain all the blocks present in dominators[func][pred] which again contains all the nodes so res =list(set(_dominators[pred]) & set(res)) , res will contain all the nodes .
so

if not res == dominators[func][block]: #### this will always be false right ?
                    has_changed = True
                dominators[func][block] = res
``` ## res will never change ?
                
 so dominators[func][for all blocks] will be the same right ? Please correct me if I am wrong .

[bennyrubin]

Link to code
I implemented functions to get the dominators of every node, to construct the dominance tree, and to get the dominance frontier for each node in the cfg.

The pseudo-code from class was straightforward to implement for dominators.
To construct the dominance tree, I used the insight that for a node A, the immediate dominator B must be dominated by all other dominators. I used python’s set arithmetic to easily calculate this.
For the dominance frontier, I used the fact that a node A is in the dominance frontier of all nodes who dominate some, but not all of its predecessors. For this assignment in particular I was happy to be using python, because it made the graph traversals and set arithmetic super straightforward and easy to follow.

To check that all the dominators I calculated for a given node truly dominated that node I used a DFS to enumerate all paths between the entry and that node. Then I made sure each dominator was in every path. I ran my scripts on test programs from the benchmarks directory.

Similar to another comment, I had to add explicit edge cases because the dominator relation is reflexive - this gave me trouble for a bit of time. I also was a bit confused about the successors of any node being in its dominators frontier since every node dominates itself, but resorting to the definitions I decided this was correct.

[MelindaFang-code]

Summary

dominance.py
turnt tests

I have implemented the algorithm to

• find dominators (map from block to the its dominators): I simply use the algorithm provided in class
• the dominance tree: I would need to translate the definition of dominance tree to program. A is B’s direct parent in the dominator tree if A immediately dominates B, which means that A dominates B but A does not strictly dominate any other node that strictly dominates B. To translate this statement to program, I first reverse the dominators map M to create a map from the block to the blocks it dominators M_r. Then for each block b in this reversed map, I check the blocks that b dominates: M_r[b], and remove a block d in M_r[b] if d's dominator intersects with M_r[b] and the intersection is not just b.
• dominance frontier: A’s dominance frontier contains B iff A does not strictly dominate B, but A does dominate some predecessor of B. Similar as above, need to reverse the dominators map to map from the block to the blocks it dominators. For each block A in cfg, I check all the blocks it dominates, and then add their successors into the potential set of frontier of A, and then I iterate through the blocks in the potential set and keep the ones not in the blocks that A dominates or if the block = A

To prove the accuracy of the algorithm, I did

• write a testing algorithm to test the dominator algorithm.
• edit the turnt file to compare my output results to the outputs of the test cases in example/dom folder, which covers all 3 algorithms: dominator/dominator tree/dominance frontier

Testing

By definition, A dominates B iff all paths from the entry to B include A. Hence, for each of the block b in the cfg, I would iterate through its dominators, and for each dominator A, I would do a dfs from the entry to b to check if they all include A.
This is a brute-force approach, but since we are only running it once so it should be fine.

Challenges

One of the first challenge was to determine the entry block of the cfg. At first I thought of finding the block that has no predecessors. However, I realized for some of the test programs it is possible that all the blocks have predecessors. Then i realize that the entry block would just simply be the first block appear in the bril file. Hence, I would need to create a dummy block in the beginning and set its successor to be the the current entry block and predecessor to be empty set. This requires me to change the blockname-to-block map I created and the predecessor & successor list.

Another challenge is to translate the definition of dominance frontier and dominance tree to actual code. I need to consider whether to think traversing down the tree or traversing from bottom up (e.g. should we use predecessors or successors in constructing the dominance frontier?)

[keikun555]

Summarize what you did.

• Lesson 5 Task
• Bril Labeler: This utility hallucinates labels for blocks that don't have labels. This is to make it easier for us to understand the analysis results
• Dominance Analysis Tool: This tool analyzes and reports in a JSON format the following analysis

❯ python3 dominance_analysis.py --help
Usage: dominance_analysis.py [OPTIONS] {dominance|naive-dominance|strict-
                             dominance|naive-strict-dominance|immediate-
                             dominance|naive-immediate-dominance|dominator-
                             tree|naive-dominator-tree|dominance-
                             frontier|naive-dominance-frontier}

Options:
  -p, --post  Same analysis but with post-dominance instead of dominance
  --help      Show this message and exit.
❯

• The naive-.* analysis gives the same results as the non-naive counterparts, and are implemented using all reachable path algorithms added into cfg.py.
• I also added support for post-dominance analysis, and all analyses listed supports this option. This is achieved through the reverse-cfg trick we discussed in class and implemented in cfg.py.

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

• I first collected all *.bril files from the bril repo with the following command:

find . -name '*.bril' -exec cp --parents \{\} ../task/lesson5/test \;

• This preserves all directory structure under the bril repo, as seen in this test directory
• Within the test directory, I created this turnt.toml file, and used turnt's support for differential testing to test whether the naive implementations produced the same output as the actual implementations.
• The results are in turnt.out and are generated through this command

turnt -j $(find . -iname "*.bril") | tee turnt.out

• At first the results look a bit suspicious, as there are 620 not oks.

❯ rg -c "^not ok" turnt.out
620

• However, inspecting these files reveal that most failed files have overwritten CMDs and RETURNs.

❯ rg "^not ok" turnt.out | cut -d' ' -f5 | uniq | xargs rgrep -c -E "CMD:|RETURN:"
./type-infer/tests/fail-infer/br.bril:1
./type-infer/tests/fail-infer/jmp.bril:1
./type-infer/tests/fail-infer/logic_ops.bril:1
./type-infer/tests/fail-infer/many_functions.bril:1
./type-infer/tests/fail-infer/control_ops.bril:1
./type-infer/tests/fail-infer/div.bril:1
./type-infer/tests/fail-infer/comp_ops.bril:1
./type-infer/tests/fail-infer/arith_ops.bril:1
./type-infer/tests/fail-typecheck/br.bril:1
./type-infer/tests/fail-typecheck/tiny.bril:1
./type-infer/tests/fail-typecheck/tricky-jump.bril:1
./type-infer/tests/fail-typecheck/jmp.bril:1
./type-infer/tests/fail-typecheck/logic_ops.bril:1
./type-infer/tests/fail-typecheck/nop.bril:1
./type-infer/tests/fail-typecheck/many_functions.bril:1
./type-infer/tests/fail-typecheck/control_ops.bril:1
./type-infer/tests/fail-typecheck/add.bril:1
./type-infer/tests/fail-typecheck/ret.bril:1
./type-infer/tests/fail-typecheck/div.bril:1
./type-infer/tests/fail-typecheck/comp_ops.bril:1
./type-infer/tests/fail-typecheck/idchain.bril:1
./type-infer/tests/fail-typecheck/arith_ops.bril:1
./examples/test/lvn/clobber.bril:1
./examples/test/lvn/rename-fold.bril:1
./examples/test/lvn/redundant-dce.bril:1
./examples/test/lvn/clobber-fold.bril:1
./test/linking/diamond.bril:0
./test/linking/recursive.bril:0
./test/linking/nested.bril:0
./test/linking/link_ops.bril:0
./test/check/labels.bril:0

• All the files in ./test/linking/ link to files in a directory and bril2json does not like that

❯ rg "^not ok" turnt.out | cut -d' ' -f5 | uniq | grep "linking" | xargs rgrep -c -E "ARGS: \.\."
./test/linking/diamond.bril:1
./test/linking/recursive.bril:1
./test/linking/nested.bril:1
./test/linking/link_ops.bril:1
❯ bril2json < test/linking/diamond.bril
Traceback (most recent call last):
  File "/home/kei/course/6120/6120/bin/bril2json", line 8, in <module>
    sys.exit(bril2json())
  File "/home/kei/course/6120/6120/lib/python3.10/site-packages/briltxt.py", line 339, in bril2json
    print(parse_bril(sys.stdin.read(), '-p' in sys.argv[1:]))
  File "/home/kei/course/6120/6120/lib/python3.10/site-packages/briltxt.py", line 239, in parse_bril
    tree = parser.parse(txt)
  File "/home/kei/course/6120/6120/lib/python3.10/site-packages/lark/lark.py", line 581, in parse
    return self.parser.parse(text, start=start, on_error=on_error)
  File "/home/kei/course/6120/6120/lib/python3.10/site-packages/lark/parser_frontends.py", line 106, in parse
    return self.parser.parse(stream, chosen_start, **kw)
  File "/home/kei/course/6120/6120/lib/python3.10/site-packages/lark/parsers/earley.py", line 297, in parse
    to_scan = self._parse(lexer, columns, to_scan, start_symbol)
  File "/home/kei/course/6120/6120/lib/python3.10/site-packages/lark/parsers/xearley.py", line 144, in _parse
    to_scan = scan(i, to_scan)
  File "/home/kei/course/6120/6120/lib/python3.10/site-packages/lark/parsers/xearley.py", line 118, in scan
    raise UnexpectedCharacters(stream, i, text_line, text_column, {item.expect.name for item in to_scan},
lark.exceptions.UnexpectedCharacters: No terminal matches 'f' in the current parser context, at line 2 col 1

from "link_ops.bril" import @main as @in
^
Expected one of:
        * FUNC
        * STRUCT

• And the last file, ./test/check/labels.bril, is not well-formed because instructions may only refer to labels that exist within the same function

❯ cat ./test/check/labels.bril
@main(b: bool) {
  jmp .bad; # <= does not exist in @main
  br b .foo;
  br b .foo .foo .foo;
  c: bool = not b .foo;
.foo:
.bar:
.bar:
}

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

• At first I thought the hardest part was going to be translating the mathematical dominator definitions to code. I solved this through writing out what each statement meant. For example, for immediate dominators, we have that "The immediate dominator ... of ... node n ... strictly dominates n but does not strictly dominate any other node that strictly dominates n." (from this wiki page) For this definition, I deconstructed the definition to "M strictly dominates N," "M does not strictly dominate any other (node that strictly dominates N)." and wrote out for each phrase into code and combined them to:

        idom[i] = strict_dominators[i].copy()
        for node in strict_dominators[i]:
            idom[i] -= strict_dominators[node]

• The first line constructs "M strictly dominates N," the second line constructs "node that strictly dominates N," and together with the third line constructs "M does not strictly dominate any other (node that strictly dominates N)."
• The actual hard part was running the test suite and determining dominators and the likes of unreachable blocks. When I tested with my test suite, I found that benchmarks/mem/two-sum.bril had unreachable blocks. At first I thought that the definition of dominators was ambiguous for unreachable blocks so I posted on Zulip. Soon after, I realized that every path from the entry to unreachable blocks go through every block (vacuously), and so I determined that every block is a dominator of unreachable blocks. Strict dominators of unreachable blocks are all blocks except the unreachable block. The actual ambiguity arises from the immediate dominators, where we want some kind of uniqueness to guarantee a dominator tree. Since there could be multiple immediate dominator candidates for unreachable blocks, I set the immediate dominators of unreachable blocks to nil since it is not well defined. This worked for both my naive and actual implementation since it guaranteed a dominator tree to be a tree.

[bcarlet]

Summary

• Dominator Utilities
• Testing

Details/Testing

I computed the dom relation using the algorithm from lecture, using reverse post-order iteration. I constructed the dominance tree and frontier using algorithms derived more or less directly from the definitions.

To test, I wrote functions to verify all the above relations using naive algorithms. For example, I verified that a dominates b by checking that b is not reachable from the entry block except by paths containing a. I used brench to run these verifiers on all the benchmarks in the bril repository, as well as the examples in examples/test/dom (which I also checked manually).

Difficulties

I was unsure of how to deal with CFGs containing unreachable blocks, since some of the definitions are well-formed in the presence of unreachable blocks and some (namely, the dominator tree) aren't. My original algorithm for constructing the dominator tree would omit any unreachable blocks, but this didn't agree with my verifiers which applied the definitions more directly. I ended up modifying the dominator tree algorithm, which now produces a graph if there are unreachable blocks.

[matth2k]

• Summary

  • Dominance Info Framework
    • Source Files
      • dminfo.py The main driver code that prints the dominance tree
      • butils Directory for my utility code
        • butils/cfg.py An API to build control flow graphs from programs. Has a Block api as well.
        • butils/dataflow.py The generic dataflow solver framework.
        • butils/dominance.py The generic dominance info framework

• Implementation Details

  • Finding the dominators of each node is quite similar to the dataflow framework we created. I did not reuse the dataflow solver, but you probably could. I wanted to reorder the initial worklist to get convergence in less iterations, but I was having trouble getting the reverse post-order correct with cycles in the DFG.
  • I used GitHub Copilot for some boilerplate code, and I read some other online resources on dominators.
  • One you run the dominance framework on a CFG, I provide the following API
    • def dominates(self, a: Block, i: Block) -> bool returns true if a dominates b
    • def strictly_dominates(self, a: Block, i: Block) -> bool returns true if a dominates b and a != b
    • def immediately_dominates(self, a: Block, i: Block) -> bool returns true if a is an immediate dominator of b
    • def get_dom_tree(self) -> dict[str, set] returns the dominator tree as map from block name to a set of blocks
    • def get_dom_frontier(self) -> dict[str, set] returns map from block name to a set of blocks on the dominance frontier

• Evaluation

  • As for evaluating the implementation of finding dominators, immediate dominators, and dominance tree I first ran my program on every core and float benchmark just as first pass for bugs.
  • Then, I implemented a verify() function to help test for correctness.
    • I use a DFS traversal to find every simple cyclic path in the CFG that starts from the entry block, storing the incremental path as the verticies $(v_1, v_2, ..., v_k)$. At each node visit $v_k$, I check that for all dominators of $v_k$ they are contained within the path (otherwise that would contradict it being a dominator). My rationale is that this approach would find all the false positive dominators. The false negatives are caught by reconstructing the dominators along all paths that end on node $v_k$.
    • Am I missing anything by terminating at simple cycles?
    • Assuming my verify() is watertight, I don't need to go any further to verify the dominator tree or dominance frontier, since I calculated those directly by definition without any shortcuts.

• Anything Hard or Interesting?

  • The fact that the CFG is not a DAG makes the formal verification as well as the run time optimization tricky.
  • When we move to SSA form, I want to try to reuse the dominance framework I've built up for finding dominators of individual operations.

[obhalerao]

I worked with @SanjitBasker on this assignment.

Summary

Repo

Implementation details

In this assignment, we implemented some utility functions for global analysis computations using C++. These included dominators for every block in a CFG, the dominator tree constructed from the dominance relationship, and the dominance frontier for every node in the CFG. Just for fun, we also decided to implement an algorithm for finding all natural loops from the dominance information as well.

To compute block-level dominators, we modified our dataflow analysis framework slightly from the previous assignment to operate on blocks instead of on instructions. Since we didn't want to have to iterate through the CFG to get all variable names for the top element, we chose to wrap each set of dominators in an optional, with the optional element not existing representing the top element. We also made sure to iterate on the blocks in reverse postorder.

Once we got the dataflow analysis framework for the dominators working, computing the other functions was straightforward. To compute the dominator tree, we simply iterated through each block's dominator set and checked which blocks immediately dominated the other, and added those edges to the tree. To compute the dominance frontier, we used a DFS-based algorithm that takes advantage of the fact that, when considering the dominator tree, the dominance frontier of a parent is the same as that of its children, with the parent's immediate undominated successors added. Lastly, to compute natural loops, we first checked for back-edges by verifying that for an edge A -> B, B dominates A. Then, once we found such back-edge, we did a BFS on A's ancestors until we got to B. We then output the set of A, its ancestors we found, and B as the natural loop.

Testing

For testing, we implemented a naive algorithm for computing dominators that, for every node, tries all possible paths from the entry node to that node and computes the intersection of all the nodes seen on that path. This is correct because even if there are loops and there exists a longer path to the node, that path must necessarily also go through that node and thus the new nodes will never be dominators. We verified that this naive algorithm and our dataflow analysis output the same result.

Just for fun, we also computed the number of iterations it took for each algorithm to compute the dominators. Omitting functions with only one basic block (as those are trivial to compute), the results for each function in each test case of the benchmark suite are shown below.

Difficulties

It was also a little tricky to deal with the special case of the entry node, so we ended up hardcoding that in to our worklist algorithm. We also dealt with some bugs with regards to differentiating the nullopt and empty set values in the optional we used for computing dominators.

[stephenverderame]

Summary

• Repo

For this assignment, I implemented some dominator utilities such as constructing a dom tree, finding the dominance frontier, testing the correctness of the dom tree, and displaying the dominator tree. To test whether the dom tree was correct, I used a naive algorithm that, for every pair of nodes, a and b, walked backward in a BFS from a and tested if all paths hit b. If so it would query the dominator tree and ensure that b dominated a, if not it would ensure that b did not dominate a in the dom tree.

Once the dominators were correct, I decided to construct an analysis that would identify natural loops. I added a way to visualize natural loops to my bril2cfg tool to check this.

Feeling ambitious, I decided to use this to implement LICM, which was tested by once again running the optimization as another turnt environment.

Implementation

For the dominators, I used the algorithm presented in class to compute a mapping from each node to its set of dominators. Partly for visualization purposes, and partly because I find it easier to think in terms of a dominating b rather than a is dominated by b, I converted this to a dominator tree. This actually proved a tad tricker than anticipated in order to correctly compute the strict, immediate dominators, from the set of all dominators.

Here is a simple example of output dom tree:

And here is the original CFG:

Once dominators were implemented, I decided to make an analysis that finds natural loops. To do this, I identified all backedges in the graph, then performed a DFS in the transposed CFG starting from the head of the backedge until the tail (loop header) was reached. Natural loops identified with the same header are merged, and I actually construct a tree of natural loops to handle nested loops.

Here is an example of displaying the CFG with loops identified:

With natural loops implemented, I also implemented reaching definitions and LICM. In hindsight, doing this without SSA was a questionable choice, however, it was interesting as I sort of realized that SSA kind of falls out naturally of loop optimizations. For example, to maintain behavior, I needed to rename the defined variables of any hoisted instructions to ensure they only had one definition. Furthermore, phi nodes would allow further optimization of cases where multiple loop invariant computations merge into one use. For this implementation, I just handled that case conservatively. Finally, correctly determining when instructions could be safely moved was also pretty tricky which would obviously be far simpler when the CFG is in SSA form.

To determine the instructions that could be moved, I framed the algorithm given in the lecture notes as a data flow analysis pass. After identifying which instructions could be moved, the definitions of those instructions were given unique names, and all uses of those definitions, as determined by reaching definitions, were renamed. This allows for cases where a loop invariant variable is used by a non-loop invariant instruction before the loop invariant var is replaced with a new loop invariant definition.

Testing

As mentioned earlier, the dominators were checked algorithmically. LICM was tested by running it through all benchmarks. All stages were checked manually by reviewing some of the resulting graphs displaying the dom tree, CFG with loops, and CFG after LICM and making the results golds with turnt.

The result of running all benchmarks is as follows:

Pass Type	Avg Speedup	Quartile 1 Speedup	Median Speedup	Quartile 3 Speedup
LICM	1.101x	1x	1x	1.089x
LICM+LVN+DCE	1.468x	1.004x	1.145x	1.821x
LVN+DCE	1.422x	1x	1.083x	1.703x

Here's a small example before LICM:

And after:

Challenges

The tricky part of the dominators was forming the dominator tree. Finding natural loops using this information was relatively straightforward. Doing LICM was definitely the trickiest part. There were a lot of corner cases to consider and things to check. Another tricky thing was handling the function arguments for LICM, which I did by adding a ghost instruction in Reaching Defs that defines all the function args in the ghost start block.

[he-andy]

Summary

Repo

Implementation

Since my CFG implementation used the petgraph library, some research yielded that petgraph already has an implementation of dominator analysis. The implementation cited this paper -- which, upon inspection, is just the reverse-postorder algorithm discussed in class. However, the included implementation did not yield all the information I needed to construct the dominance frontier. For instance, given a node in the graph, the analysis only yields the nodes dominating that node and the nodes immediately dominated by that node. To extrapolate the set of nodes dominated by a given node, I used the idom information and DFS to build the set of all dom'd nodes. This was useful in solving for the dominance frontier, which I also had to implement by hand.

Constructing a dominator tree was also quite simple after computing the set of nodes idom'd by a given node. I used petgraph to construct this tree as well.

I also added some quality of life updates to my CFG implementation by making it easier to relabel basic blocks and automatically labelling unlabeled blocks to make it easier to debug.

Here's an example output on the core/relative-primes.bril for function @relative_primes.

CFG	Dom Tree	Dominance Frontier

Challenges

Since the implementation of dominator analysis came for free with my graph library, most of the challenges I faced with this project involved understanding how to actually manipulate the data structures returned by the algorithm. There was very sparse documentation provided by petgraph, so I spent considerable time reading through the source code. I actually found an inaccuracy in the documentation that was provided (one of the methods claimed it would return all nodes it imm dominated by except for itself, but actually returned itself).

Testing

I thought it was fair to assume the correctness of the provided algorithm, but I did some simple testing by doing some path analysis using DFS. I also visually inspected the outputs of the dominance frontier and dominance tree as a sanity check.

[evanmwilliams]

Summary

For this task, @emwangs and I implemented dominator analysis. You can find the repository here.

Implementation Details

• We stuck with C++ for this assignment as we already built a lot of infrastructure using the language in the previous few assignments
• The dominator analysis was very similar to what we implemented in CS 4120 last semester!
• We could definitely use the generic dataflow solver to compute dominators, but we chose to go with the algorithms described in lecture instead

Challenges

• Our code is getting a bit messy - we were in the middle of a big refactor before this assignment but had to pause to finish this up. By next week the entire repo will look a bit different
• The dominance frontier was a bit harder to implement (and test), but the algorithms in lecture were useful

Testing/Evaluation

• The program works on the programs we tested last week (i.e. the ones we implemented reaching definitions on)
• We are struggling a bit to output nice CFGs with our current infrastructure but this will surely make debugging a lot easier once we do
• On the benchmarks we computed by hand, we seem to be computing the dominators and the dominance frontier correctly

To verify our dominance frontier, we also made a new Bril program that has a more interesting control flow. This was the resulting dominator tree:

And this was the output from our program:

DOMINANCE FRONTIER
"main": 
0: empty
1: empty
2: 4 
3: 4 
4: empty
5: empty

And for reference here is the program:

@main {
  jmp .A;
  
.A:
  aVal: int = const 10;
  zVal: int = const 0;
  decision: bool = eq aVal zVal;
  br decision .B .C;

.B:
  bVal: int = const 5;
  jmp .D;

.C:
  cVal: int = const 20;
  jmp .D;

.D:
  dVal: int = const 30;
  jmp .E;

.E:
  eVal: int = const 40;
  print eVal;
}

[ryanwmao]

@xalbt and I worked together on lesson 5.

Summary

repo
core files
files are in core and coretest

Implementation

• We used C++ for this lesson's tasks, using the infrastructure we built for the previous tasks.
• We performed dominator analysis, built a dominance tree, and computed the dominance frontiers as specified.
• Overall, we think that everything went pretty smoothly for this task.

Difficulties

• There were some difficulties we had with debugging/segfaults, but these were to be expected
• We had a very peculiar bug where our previously correct code become incorrect. We are not sure where it originated, but with some more debugging we were able to fix

Testing

• We implemented our tests as simple evaluations over all basic blocks in the program.
• Our dominated-by relation was tested by performing a BFS from the entry point, stopping each path at the dominated-by node. If we reached the current node first, our dominated-by relation would then be incorrect
• Our immediate dominators were computed by examining the dominated-by sets of all nodes in this node's dominated-by set. If any of them also included the idom, then our idom is computed incorrectly
• Our dominator tree test followed directly from the idoms, we just check whether or not each successor has the current node as its idom
• For our dominance frontier, we collected all the nodes that would be on each node's dominance frontier (i.e. it's not dominated by the node, but all its predecessors are) and evaluated whether or not this set was equal to our comptued set
• We tested our code using these tests on the core benchmarks.

Example graphviz for quadratic.bril

output:

sqrt
dom_by:
_bb.0: _bb.0,
for.cond.0: _bb.0, for.cond.0,
for.body.0: _bb.0, for.cond.0, for.body.0,
then.7: _bb.0, for.cond.0, for.body.0, then.7,
else.7: _bb.0, for.cond.0, for.body.0, else.7,
endif.7: _bb.0, for.cond.0, for.body.0, else.7, endif.7,
for.end.0: _bb.0, for.cond.0, for.end.0,

dom_tree:
digraph sqrt {
node[shape=rectangle]
label="sqrt";
"_bb.0" [label="_bb.0"];
"for.cond.0" [label="for.cond.0"];
"for.body.0" [label="for.body.0"];
"then.7" [label="then.7"];
"else.7" [label="else.7"];
"endif.7" [label="endif.7"];
"for.end.0" [label="for.end.0"];
"_bb.0"->"for.cond.0";
"for.cond.0"->"for.body.0";
"for.cond.0"->"for.end.0";
"for.body.0"->"then.7";
"for.body.0"->"else.7";
"else.7"->"endif.7";
}

dfront:
_bb.0:
for.cond.0:
for.body.0: for.cond.0,
then.7: else.7,
else.7: for.cond.0,
endif.7: for.cond.0,
for.end.0:

[Enochen]

Summary

Code

I started with the algorithm shown in class to find all dominators for a given node.
I then constructed an inverse mapping from node to dominated nodes. This proved useful for computing the dominance frontier.
Finally, I found the immediate dominator for each node, which allowed me to trivially construct the dominator tree.

Implementation

I used the run-until-no-changes algorithm from class to find the dominators sets for each node.

I then inverted the dominators sets to get a "dominated_by" set, which given a node x gives all the nodes that are dominated by x.
Essentially this process is swapping the keys and values of the dominators sets.

Although the dominated_by set wasn't explicitly part of the task, it made sense to implement because it made finding the dominance frontier very easy. My strategy for the dominance frontier was to do a depth-1 BFS from all the nodes dominated by a given node, collect it all into a set, and then subtracting the original set of nodes that were dominated by the given node.

One nuance I found through testing, however, was that for the set subtraction part I needed to make sure it did not subtract the given node itself, as the dominance frontier definition only states to remove nodes with the "strictly dominates" relation.

Then came another calculation that was not part of the task, which was finding the immediate dominator for a node.
Here I used both the dominators and dominated_by sets: as per the definition of the immediate dominator, I searched through the dominators of the given node to find the one dominator which strictly dominates the given node but not any other dominator.

Finally I made the dominator tree by linking each node with its immediate dominator.
    

Testing

As initial validation for the correctness of my dominators algorithm implementation, I checked the algorithm's output for crafted bril programs against my manual construction of the dominators sets for each node. I made sure to test edge cases in the graph such as having incoming edges into the entry block and having unreachable blocks (from entry block) within the CFG.

Next, I computationally tested my implementation by writing a simple naive algorithm that also computes the dominators set, and verifying that the results from both the naive algorithm and the "efficient" algorithm matched.
The naive algorithm used a graph util to generate all simple paths from the entry block to another particular block. 

I didn't get to implement this, but the graph library I've been using (petgraph) actually had a dominators utility included. I could have used this along with my naive implementation to verify correctness.
 

Challenges

Some specifics of the dominance relations definitions were kind of tricky. For example, the dominance frontier definition uses strict dominance instead of "regular" dominance. The main implication this had when testing my implementation was that a node can be on its own dominance frontier, for example if it dominates an immediate predecessor.

There were also annoying edge cases I discovered relating to the entry block, which I simply had to make special cases for. For example, when writing my naive algorithm for testing, I couldn't apply the definition of dominators using paths from entry to node when the node was the entry block. This example is kind of a technicality on whether not traversing any edges counts as a path from A to A but there were several places where I did something special for the entry block.

I had the idea of adapting the algorithm shown in class to calculate the immediate dominator as opposed to the entire dominators set for each node. Having the immediate dominator makes constructing the dominator tree trivial (as mentioned above) and it also allows for deriving the entire dominators set in an easy way, by traversing up the tree (or following the immediate domination relation backwards). However, I got sick and wasn't able to get it working, so I ended up using the algorithm from class and deriving the immediate dominators in a later step.

[AliceSzzze]

Dominance utilities in repo

Implementation

• Dominators
  • I used the algorithm introduced in class to find the dominators of each node. To make sure that the algorithm runs in linear time, I first obtained the reverse post-order of the graph using DFS, only adding a node to a list after all its successors have been recursively visited.

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

• Dominance Tree

  • To find the immediate dominators of each node, I implemented two relatively naive approaches, both of which use the pre-computed dominators map. First, I just used a pairwise search to find a node A that strictly dominates B but not any node that strictly dominates 'B'. The second approach involves a BFS from the node to find the closest predecessor that strictly dominates that node. The second approach should have better asymptotic complexity than the first one if I am not mistaken.
  • I was reading about the Lengauer-Tarjan algorithm. If I have more time I would like to try to implement it.

• Dominance Frontier

  • for each node, I took the union of the dominators of the node's predecessors, then subtracted the node's own dominators from the union. This tells us whose frontier the node should belong to.

Testing

For each of the utilities, I wrote a slow but obviously correct algorithm to test my implementation. I then ran the verifier on all of Bril's benchmarks using Turnt (toml file).

• Dominators

  • I took the intersection of every possible path to a node and checked that the intersection was the same as the set of dominators. I found the paths using iterative DFS and kept track of the nodes on a given path using a list.

• Dominance Tree

  • I originally wrote the BFS approach to verify the first one, but the first one is more brute-force and obviously correct. In any case, I compared the outputs from both of them and asserted that they were equal.

• Dominance Frontier

  • I verified that for every node n' in node n's frontier, n does not dominate n', but at least one predecessor of n' is dominated by n.

Difficulties

• The reflexivity of dominance made it harder for me to fully grasp the concept of a dominance frontier. Using the CFG below as an example, for.row.cond is in for.row.body's dominance frontier, because for.row.cond isn't dominated by for.row.body, but for.row.cond has a predecessor that is. In this case, that predecessor is for.row.body because there is a back edge, and for.row.body is dominated by itself.

Here is an example taken from the mat_vec function of benchmarks/float/conjugate-gradient.bril:
CFG:

Dominance Tree:

Dominance Frontier:
{for.row.end=[], for.row.body=[for.row.cond], for.row.cond=[], __entry__=[], for.col.cond=[for.row.cond], for.col.body=[for.col.cond], for.col.end=[for.row.cond]}

[zachary-kent]

Summary

Implementation, Tests

Implementation

• I continued my implementation work in Haskell, having found myself very productive with it in previous assignments.
• I decided to implement dominators using my dataflow analysis framework as opposed to the "repeat until no change" algorithm presented in lecture, although they are essentially equivalent. Here, the top value of the lattice for this analysis is "all nodes," the meet operation is set intersection, and the transfer function at node takes the union of the intersection of the dominators together with itself.
• I found constructing the dominance tree efficiently somewhat tricky. My dominator analysis gave me, for every node B, the set { A | A dom B }. However, to compute the dominance tree efficiently, I needed to compute the set { B | A dom B } for every node A. I first computed this set and, by trivial extension, the sets of strict dominators. Finally, I constructed an edge (A, B) in the dominance tree iff A idom B
  For a while, I attempted to compute the dominance frontier using a more efficient method presented in the CS 4120 lecture notes. It points out that B lies on the dominance frontier of A iff A does not dominate B, and either B is a successor of A in the CFG or B lies on the dominance frontier of some node immediately dominated by A. Unfortunately, I was not able to get this working, so I computed the dominance frontier more naively using the definition given in class.

Testing

• Testing for this assignment was significantly more difficult than in the past, as, for the first time, I could no longer use brench :(. Instead, I used the Haskell command library to fork a subprocess that would call bril2json on an input file and then capture the JSON string written to stdout. Then, I could parse this JSON representation in my test suite and manipulate it as usual.
• I used the hspec library to write unit tests for my implementation. I found it incredibly, easy to use, and the output of passing tests is also very satisfying! (the output of failing tests, less so).

• I created a naive reference implementation of dominators by noting that A dom B iff every path from start to B includes A, or equivalently that deleting A from the CFG makes B unreachable from the start node. - I also created a reference implementation for dominance trees that directly creates an edge (A, B) if and only if A dom B. - To test my implementations of dominators and dominance trees, I ensured that their outputs agree on every Bril benchmark (in fact, this is how I realized there was a bug in my complex dominance frontier code -- my current implementation was originally my reference implementation). As such, there was no way I could effectively test my dominance frontier code, as it is already as simple as possible.

Difficulties

• Dealing with unreachable nodes was especially difficult -- technically, every node dominates an unreachable node, as there are no paths from start to an unreachable node.
• I decided to include them in the dominance analysis, but not the dominator tree, the same choice made by LLVM.
• I have already discussed attempting to compute the dominance frontier efficiently, which was probably the biggest pain point.

[yxd97]

Summary

In this task, I implemented three programs that:

• Builds the dominator table of a function
• Builds the dominance tree of a function
• Finds the dominance frontier of each block in a function
• I did not use any AI assistance in this task

Implementation

• The program that builds the dominator table follows the discussion in class, where we start with the universe set and update it with the intersection of its predecessors' dominators, until the whole table does not change any more.
• To build the dominance tree, I first truned the dominator table into a "dominating table", where each entry records the blocks that a block donimates. Then I sort the table by the number of dominating blocks, which makes the immediate dominance relationships more clear; a block's immediate dominator is the nearest entry in the sorted table, whose dominating blocks is a superset of this block's dominating blocks. By finding the immediate dominator of each block, I finally constructed the dominance tree.
• Finding the dominance frontier is simpler. I just followed the definition: first I get the dominating blocks of the queried block from the dominator table, check every successor of the dominating blocks, and if the successor is not in the dominating blocks (i.e., not dominated by the queried block), it belongs to the dominance frontier.
• All three programs will print the results to stdout.

Testing

• To check the aforementioned programs, I first impelmented a way to check if a block donimates the other, by checking the paths from the ENTRY to the target block.
• Checking all paths is not possible, as there might be loops. However, we only need to check the path that circles the loop exactly once, since going around more times makes no difference to the final result. Therefore, I implemented a DFS-like algorithm to find the paths to be checked; it keeps track of the traversal history, as well as which way we took on the branching points.
• If we hit a visited block again (meaning we just wen around a loop), we see if there is another branch that has not been explored; if there is, we continue to the other branch, otherwise, this path is discarded because we will be trapped in the loop and never reach the target. Once we arrive at the target with no branches to explore, the path is checked if it contains the source block.
• With the dominance checker, I can verify the correctness of the dominator table, dominance tree, and dominance frontier by their definitions.
• The test cases include all tests I built for task 4 and the bril programs from bril/benchmark/core.

Challenges

It took me most of the time designing the path finding algorithm to check the dominance. I need to make sure I checked every possibility, but only go around each loop exactly once. An overly loose break condition is easy to check as the algorithm will be trapped in a loop. However, it took much effort to check if there is a missing path. To tackle this challenge, I made many artificial control flow graphs that have no actual instructions but just the graph structure. These ad-hoc graphs include multi-branching, nested loops, twisted loops (like "8"), etc.

[jiahanxie353]

Summary

In this task, I

1. Use graphvix to visualize the CFGs;
2. Constructed dominance maps for all CFGS;
3. Built dominator trees for all CFGs;
4. Computed dominator fontiers of each node, and
5. Wrote testing functions that just use graph/tree traversal to verify dominance relation; and a shell script to have thorough testing for my dominators computation.

Implementation

To build a dominance map from a given CFG, I just followed the algorithm provided in the lesson notes, and it was not hard to implement (though I started with implementing "backward", i.e., post-dominance, so I needed to switch everything back to regular dominance implementation). To build the dominance tree, I first computed immediate dominance map and use that map to find the children level by level, starting from the entry node. (It's worth mentioning that C++'s unique_ptr is very helpful to constructing the dominance tree, in which each child is owned by a single parent.) Lastly, for computing the dominance frontiers, I just used an naive algorithm that implemented plain English

A’s dominance frontier contains B iff A does not strictly dominate B, but A does dominate some predecessor of B
It's easy to follow though there might be more time-efficient way to do it and I will explore it in the future.

Testing

To test the dominance relation, I verify if A dominates B by simply using a DFS traversal. Although it's not fast (still faster then eyeballing), but it's guaranteed to be correct, which is the most important thing for testing. To test the dominance tree, it's equivalent to test the immediate dominatees of a node == the children of that node. And to list the immediate dominance, I had to manually write them out for each CFG, so then I wrote a script to run the tests on different json files, making the testing procedure more automated. For the test cases, I mostly used my own test cases, where I devised some really complicated and tricky situations to test against my implementation.

[collinzrj]

Summary

In this task, I

1. implemented a function to construct and visualize the cfg
2. implemented a function find_dominators to construct the map from each block to its dominators
3. implement a function construct_dominance_tree to find the immediate dominators of a block with its dominators map from 2
4. implement a function compute_dominance_frontier to construct the dominance frontier given the dominators map and the cfg
5. implement a function test_dom_dict that test if a node is the dominator of another node, thus construct a function to test the dominators map

Implementation

To implement find_dominators, I used the script from the lecture notes that takes the intersection of all the predecessors of a blocks best guess of the dominators until reaches a fixed point.
To implement the construct_dominance_tree, I have to find the immediate dominator of a node. Given the dominators set of a node, we can make sure that the immediate dominator must be in the set, we can also make sure that the immediate dominator is the node with the second largest number of dominators in the set, so I sort the list w.r.t their number of dominators in decreasing order, and pick the second node
To implement the compute_dominance_frontier function, I iterate through the list of dominatees of a node, and then iterate through the children of each of the node, if the child is not a dominatee of the node, then it should be in its dominance frontier.

CFG for gcd.bril

Dominator tree for gcd.bril

Test

To implement the test_dom_dict function, I implement a function that checks if node A is the dominator of node B. That is, I first check if there exist a path from the node A to node B, and then check if there exist a path from entry to node B without visiting node A. I apply dfs for both of the search. If both of the conditions are satisfied, then I can make sure node A is the dominator of node B. With the check_is_dom function, I then iterate through all pairs of nodes in the cfg, if the first node is the dom of the second, I check it is in the dom dict, if it is not in the second, I check it is not in the dom dict.

Difficulty

In such a function the jmp .endif.0; expression and .endif.0: expression is unreachable from the entry, so I have to make some changes to the previous build_cfg function to remove the nodes unreachable from the entry.

@pow(x: int, n: int): int {
  v1: int = id n;
  v2: float = const 1;
  v3: bool = feq v1 v2;
  br v3 .then.0 .else.0;
.then.0:
  v4: int = id x;
  ret v4;
  jmp .endif.0;
.else.0:
  v5: int = id x;
  v6: int = id n;
  v7: float = const 2;
  v8: float = fdiv v6 v7;
  half: int = call @pow v5 v8;
  half: int = id half;
  v9: int = id half;
  v10: int = id half;
  v11: int = mul v9 v10;
  half2: int = id v11;
  v13: int = id n;
  v14: float = const 2;
  v15: bool = call @mod v13 v14;
  v16: float = const 1;
  v17: bool = feq v15 v16;
  br v17 .then.12 .else.12;
.then.12:
  v18: int = id half2;
  v19: int = id x;
  v20: int = mul v18 v19;
  ans: int = id v20;
  jmp .endif.12;
.else.12:
  v21: int = id half2;
  ans: int = id v21;
.endif.12:
  v22: int = id ans;
  ret v22;
.endif.0:
}

[janpaulpl]

Source

Dominator Algorithm

Important to note: for this assignment, I made use of a lot of code from the bril repository, namely CFG construction and cleaning basic blocks.

Implementation and issues

For finding dominators, I took the intersection of each predecessors' dominator and reflexive adding. For the dominator frontier, I checked that the successors of each vertex are dominated by the current vertex. Reflexive relations within dominance was unexpected and I did not catch this behavior until I read other's implementations.

Testing

I didn't have enough time to make an automated tool for verification, but with the set of examples from the bril repository, I was able to manually check for each vertex and its dominators, that any upstream path goes through a dominator. For assistance, I used the graphical tools implemented by others!