Homework4 - Yashaswini
Dominance
About the Code:
#Dominator Computation (find_dominators):
- This function initializes all nodes to be dominated by every other node. Then, using an iterative approach, it refines the set of dominators until convergence.
- The entry node is assumed to be node 0, and it dominates itself.
- The dominators of each node are found by intersecting the dominator sets of its predecessors and adding the node itself.
#Dominance Tree Construction (construct_dominance_tree):
- This function builds the dominance tree from the dominator sets.
- For each node, the immediate dominator (idom) is the node with the highest index in its dominator set that isn’t itself. The tree is constructed using these relationships.
#Dominance Frontier Computation (compute_dominance_frontier):
- The dominance frontier of a node is the set of nodes where the node dominates one of their predecessors but does not strictly dominate the node itself.
- This is computed using the reverse of the CFG and the dominator sets.
import json
from collections import defaultdict
def load_bril_program(filename):
"""Load the Bril program from a JSON file."""
with open(filename, 'r') as file:
return json.load(file)
def build_cfg(function):
"""Build the Control Flow Graph (CFG) for a given function."""
instrs = function['instrs']
cfg = defaultdict(list)
label_map = {}
# Map labels to instruction indices
for i, instr in enumerate(instrs):
if 'label' in instr:
label_map[instr['label']] = i
for i, instr in enumerate(instrs):
if 'op' in instr and instr['op'] == 'jmp':
target = label_map[instr['labels'][0]]
cfg[i].append(target)
elif 'op' in instr and instr['op'] == 'br':
target1 = label_map[instr['labels'][0]]
target2 = label_map[instr['labels'][1]]
cfg[i].extend([target1, target2])
else:
# Fall-through case: connect to the next instruction
if i + 1 < len(instrs):
cfg[i].append(i + 1)
return cfg
def reverse_cfg(cfg):
"""Compute the reverse of the CFG."""
reverse = defaultdict(list)
for node, successors in cfg.items():
for succ in successors:
reverse[succ].append(node)
return reverse
def find_dominators(function):
"""Find the dominators for each node in the function."""
cfg = build_cfg(function)
nodes = set(cfg.keys())
entry = min(nodes)#0 # Assuming the entry node is at index 0
dom = {node: nodes.copy() for node in nodes}
dom[entry] = {entry}
changed = True
while changed:
changed = False
for node in nodes - {entry}:
#new_dom = set.intersection(*(dom[pred] for pred in reverse_cfg(cfg)[node])) | {node}
preds = reverse_cfg(cfg)[node]
if preds:
# Compute intersection only if there are predecessors
new_dom = set.intersection(*(dom[pred] for pred in preds)) | {node}
else:
# If no predecessors, the dominators are just the node itself
new_dom = {node}
if dom[node] != new_dom:
dom[node] = new_dom
changed = True
return dom
def construct_dominance_tree(dominators):
"""Construct the dominance tree from the dominators."""
tree = defaultdict(list)
for node, dom_set in dominators.items():
if node != min(dom_set):
idom = max(dom_set - {node})
tree[idom].append(node)
return tree
def compute_dominance_frontier(function, dominators):
"""Compute the dominance frontier for each node."""
cfg = build_cfg(function)
df = defaultdict(set)
for node in cfg:
preds = reverse_cfg(cfg)[node]
if len(preds) >= 2:
for pred in preds:
runner = pred
while runner not in dominators[node]:
df[runner].add(node)
#runner = max(dominators[runner] - {runner})
if dominators[runner] - {runner}:
runner = max(dominators[runner] - {runner})
else:
break # If no other dominators, exit the loop
return df
def test_dominance_utilities(function):
"""Test the dominance utilities for a given function."""
print(f"Testing function: {function['name']}")
dominators = find_dominators(function)
print(f"Dominators: {dominators}")
dominance_tree = construct_dominance_tree(dominators)
print(f"Dominance Tree: {dominance_tree}")
dominance_frontier = compute_dominance_frontier(function, dominators)
print(f"Dominance Frontier: {dominance_frontier}")
def main():
# Load the Bril program from a file
#bril_program = load_bril_program('input_bril.json')
for bril_program in bril_programs:
# Run the tests
for function in bril_program['functions']:
test_dominance_utilities(function)
# Run the main function
if __name__ == "__main__":
main()Testing:
I implemented 8 test cases each targeting a different type of CFG. I then manually checked the against the outputs produced by the code. I had to make some changes when the code was unable to handle empty sets but after the output seems to be work correctly
Challanges
The hardest part of this task was understanding ensuring that the algorithm i used could handle various data flow types.
Once I was able to get the code to work for both independent branches and nested branches it became much easier.
Test Cases and Output
Here are the test cases used and the output from the function after running all of the test cases.
#Simple Linear Sequence A program with a single linear sequence of instructions. No branches or loops.
{
"functions": [
{
"name": "linear",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "a", "type": "int", "value": 1},
{"op": "add", "dest": "b", "type": "int", "args": ["a", "a"]},
{"op": "mul", "dest": "c", "type": "int", "args": ["b", "a"]},
{"label": "exit"}
]
}
]
}
#Simple Branch - A conditional branch leading to two different paths and joining back together.
{
"functions": [
{
"name": "branch",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "x", "type": "int", "value": 5},
{"op": "const", "dest": "y", "type": "int", "value": 10},
{"op": "br", "args": ["x"], "labels": ["true_branch", "false_branch"]},
{"label": "true_branch"},
{"op": "add", "dest": "z", "type": "int", "args": ["x", "y"]},
{"op": "jmp", "labels": ["join"]},
{"label": "false_branch"},
{"op": "sub", "dest": "z", "type": "int", "args": ["y", "x"]},
{"label": "join"},
{"op": "mul", "dest": "w", "type": "int", "args": ["z", "x"]}
]
}
]
}
#Loop with Back Edge -A basic loop where a variable is incremented until a condition is met.
{
"functions": [
{
"name": "loop",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "i", "type": "int", "value": 0},
{"label": "loop_start"},
{"op": "lt", "dest": "cond", "type": "bool", "args": ["i", "10"]},
{"op": "br", "args": ["cond"], "labels": ["body", "exit"]},
{"label": "body"},
{"op": "add", "dest": "i", "type": "int", "args": ["i", "1"]},
{"op": "jmp", "labels": ["loop_start"]},
{"label": "exit"}
]
}
]
}#Nested Branches -Two nested conditional branches.
{
"functions": [
{
"name": "nested_branches",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "a", "type": "int", "value": 1},
{"op": "const", "dest": "b", "type": "int", "value": 2},
{"op": "br", "args": ["a"], "labels": ["branch1", "merge"]},
{"label": "branch1"},
{"op": "br", "args": ["b"], "labels": ["branch2", "merge"]},
{"label": "branch2"},
{"op": "mul", "dest": "x", "type": "int", "args": ["a", "b"]},
{"op": "jmp", "labels": ["merge"]},
{"label": "merge"},
{"op": "add", "dest": "c", "type": "int", "args": ["a", "b"]}
]
}
]
}#Multiple Independent Branches - A program with two independent branches and a join.
{
"functions": [
{
"name": "independent_branches",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "a", "type": "int", "value": 3},
{"op": "const", "dest": "b", "type": "int", "value": 6},
{"op": "br", "args": ["a"], "labels": ["branch1", "merge"]},
{"label": "branch1"},
{"op": "add", "dest": "c", "type": "int", "args": ["a", "b"]},
{"op": "jmp", "labels": ["merge"]},
{"label": "branch2"},
{"op": "sub", "dest": "c", "type": "int", "args": ["b", "a"]},
{"op": "jmp", "labels": ["merge"]},
{"label": "merge"},
{"op": "mul", "dest": "d", "type": "int", "args": ["c", "a"]}
]
}
]
}#Simple Two-Way Loop - A loop with a branch that exits early based on a condition.
{
"functions": [
{
"name": "two_way_loop",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "x", "type": "int", "value": 0},
{"label": "loop_start"},
{"op": "lt", "dest": "cond", "type": "bool", "args": ["x", "5"]},
{"op": "br", "args": ["cond"], "labels": ["loop_body", "exit"]},
{"label": "loop_body"},
{"op": "add", "dest": "x", "type": "int", "args": ["x", "1"]},
{"op": "jmp", "labels": ["loop_start"]},
{"label": "exit"},
{"op": "const", "dest": "y", "type": "int", "value": 1}
]
}
]
}Loop with Nested Branch
- A loop that includes a nested branch with its own exit condition.
{
"functions": [
{
"name": "loop_with_branch",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "i", "type": "int", "value": 0},
{"label": "loop_start"},
{"op": "lt", "dest": "cond1", "type": "bool", "args": ["i", "10"]},
{"op": "br", "args": ["cond1"], "labels": ["loop_body", "exit"]},
{"label": "loop_body"},
{"op": "lt", "dest": "cond2", "type": "bool", "args": ["i", "5"]},
{"op": "br", "args": ["cond2"], "labels": ["nested_branch", "loop_continue"]},
{"label": "nested_branch"},
{"op": "add", "dest": "i", "type": "int", "args": ["i", "2"]},
{"op": "jmp", "labels": ["loop_start"]},
{"label": "loop_continue"},
{"op": "add", "dest": "i", "type": "int", "args": ["i", "1"]},
{"op": "jmp", "labels": ["loop_start"]},
{"label": "exit"}
]
}
]
}#Multiple Loops - A program with two independent loops.
{
"functions": [
{
"name": "multiple_loops",
"instrs": [
{"label": "entry"},
{"op": "const", "dest": "a", "type": "int", "value": 0},
{"label": "loop1"},
{"op": "lt", "dest": "cond1", "type": "bool", "args": ["a", "3"]},
{"op": "br", "args": ["cond1"], "labels": ["body1", "loop2"]},
{"label": "body1"},
{"op": "add", "dest": "a", "type": "int", "args": ["a", "1"]},
{"op": "jmp", "labels": ["loop1"]},
{"label": "loop2"},
{"op": "const", "dest": "b", "type": "int", "value": 0},
{"label": "loop2_start"},
{"op": "lt", "dest": "cond2", "type": "bool", "args": ["b", "2"]},
{"op": "br", "args": ["cond2"], "labels": ["body2", "exit"]},
{"label": "body2"},
{"op": "add", "dest": "b", "type": "int", "args": ["b", "1"]},
{"op": "jmp", "labels": ["loop2_start"]},
{"label": "exit"}
]
}
]
}
Output
Testing function: linear
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3]})
Dominance Frontier: defaultdict(<class 'set'>, {})
Testing function: branch
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}, 4: {0, 1, 2, 3, 4}, 5: {0, 1, 2, 3, 4, 5}, 6: {0, 1, 2, 3, 4, 5, 6}, 7: {0, 1, 2, 3, 7}, 8: {0, 1, 2, 3, 7, 8}, 9: {0, 1, 2, 3, 9}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4, 7, 9], 4: [5], 5: [6], 7: [8]})
Dominance Frontier: defaultdict(<class 'set'>, {6: {9}, 5: {9}, 4: {9}, 8: {9}, 7: {9}})
Testing function: loop
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}, 4: {0, 1, 2, 3, 4}, 5: {0, 1, 2, 3, 4, 5}, 6: {0, 1, 2, 3, 4, 5, 6}, 7: {0, 1, 2, 3, 4, 5, 6, 7}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4], 4: [5], 5: [6], 6: [7]})
Dominance Frontier: defaultdict(<class 'set'>, {7: {2}, 6: {2}, 5: {2}, 4: {2}, 3: {2}})
Testing function: nested_branches
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}, 4: {0, 1, 2, 3, 4}, 5: {0, 1, 2, 3, 4, 5}, 6: {0, 1, 2, 3, 4, 5, 6}, 7: {0, 1, 2, 3, 4, 5, 6, 7}, 8: {0, 1, 2, 3, 4, 5, 6, 7, 8}, 9: {0, 1, 2, 3, 9}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4, 9], 4: [5], 5: [6], 6: [7], 7: [8]})
Dominance Frontier: defaultdict(<class 'set'>, {5: {9}, 4: {9}, 8: {9}, 7: {9}, 6: {9}})
Testing function: independent_branches
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}, 4: {0, 1, 2, 3, 4}, 5: {0, 1, 2, 3, 4, 5}, 6: {0, 1, 2, 3, 4, 5, 6}, 7: {7}, 8: {8, 7}, 9: {8, 9, 7}, 10: {10}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4], 4: [5], 5: [6], 7: [8], 8: [9]})
Dominance Frontier: defaultdict(<class 'set'>, {3: {10}, 2: {10}, 1: {10}, 0: {10}, 6: {10}, 5: {10}, 4: {10}, 9: {10}, 8: {10}, 7: {10}})
Testing function: two_way_loop
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}, 4: {0, 1, 2, 3, 4}, 5: {0, 1, 2, 3, 4, 5}, 6: {0, 1, 2, 3, 4, 5, 6}, 7: {0, 1, 2, 3, 4, 5, 6, 7}, 8: {0, 1, 2, 3, 4, 8}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4], 4: [5, 8], 5: [6], 6: [7]})
Dominance Frontier: defaultdict(<class 'set'>, {7: {2}, 6: {2}, 5: {2}, 4: {2}, 3: {2}})
Testing function: loop_with_branch
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}, 4: {0, 1, 2, 3, 4}, 5: {0, 1, 2, 3, 4, 5}, 6: {0, 1, 2, 3, 4, 5, 6}, 7: {0, 1, 2, 3, 4, 5, 6, 7}, 8: {0, 1, 2, 3, 4, 5, 6, 7, 8}, 9: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 10: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 11: {0, 1, 2, 3, 4, 5, 6, 7, 11}, 12: {0, 1, 2, 3, 4, 5, 6, 7, 11, 12}, 13: {0, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4], 4: [5], 5: [6], 6: [7], 7: [8, 11], 8: [9], 9: [10], 11: [12], 12: [13]})
Dominance Frontier: defaultdict(<class 'set'>, {10: {2}, 9: {2}, 8: {2}, 7: {2}, 6: {2}, 5: {2}, 4: {2}, 3: {2}, 13: {2}, 12: {2}, 11: {2}})
Testing function: multiple_loops
Dominators: {0: {0}, 1: {0, 1}, 2: {0, 1, 2}, 3: {0, 1, 2, 3}, 4: {0, 1, 2, 3, 4}, 5: {0, 1, 2, 3, 4, 5}, 6: {0, 1, 2, 3, 4, 5, 6}, 7: {0, 1, 2, 3, 4, 5, 6, 7}, 8: {0, 1, 2, 3, 4, 8}, 9: {0, 1, 2, 3, 4, 8, 9}, 10: {0, 1, 2, 3, 4, 8, 9, 10}, 11: {0, 1, 2, 3, 4, 8, 9, 10, 11}, 12: {0, 1, 2, 3, 4, 8, 9, 10, 11, 12}, 13: {0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 13}, 14: {0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 13, 14}, 15: {0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 13, 14, 15}}
Dominance Tree: defaultdict(<class 'list'>, {0: [1], 1: [2], 2: [3], 3: [4], 4: [5, 8], 5: [6], 6: [7], 8: [9], 9: [10], 10: [11], 11: [12], 12: [13], 13: [14], 14: [15]})
Dominance Frontier: defaultdict(<class 'set'>, {7: {2}, 6: {2}, 5: {2}, 4: {2}, 3: {2}, 15: {10}, 14: {10}, 13: {10}, 12: {10}, 11: {10}})