Lesson 4: Data Flow

[sampsyo]

This thread is for summarizing how your implementation of the data flow framework and its client optimizations went!

[MelindaFang-code]

summary

https://github.com/MelindaFang-code/bril/blob/395081661ffe06083a9ecfae3bd9465918f17c82/assignment/dataflow.py
https://github.com/MelindaFang-code/bril/blob/395081661ffe06083a9ecfae3bd9465918f17c82/assignment/cfg.py
https://github.com/MelindaFang-code/bril/blob/395081661ffe06083a9ecfae3bd9465918f17c82/assignment/utils.py

For this task, I implemented a generic data flow framework. The cfg.py file contains logic for constructing a map with key = block name and value = block, and also the logic for building control flow graph using the map, with nodes being the blocks. The cfg function essentially just return the predecessors and successors of the blocks as we only need them for the dataflow framework.The dataflow.py contains the main logic for the dataflow algorithm. The framework is generic in the sense that we could pass in arguments to decide which analysis to compute. My current implementation only includes live variable analysis and defined variables. To achieve this the framework is programmed to allow for both forwards computation and backwards computation, and depending on the direction we need to switch predecessor & successor, in nodes Map and out nodes Map. In addition, I implemented different merge and transfer functions.

Testing

I first implemented the non-generic version, the live variable analysis. Then I run my program on the bril files in examples and compared with the existing solution manually, as my output print function didn't produce the same output. When I confirmed that my implementation is correct, I used turnt to produce my results tried to implement the generic version. Then I run the tests using turnt to confirm that even after making my functions generic, the test outputs did not change.

Hardest part

What was the hardest part of the task? How did you solve this problem?
One difficulty I encountered is to figure out the transfer functions and the directions. For instance, I got confused when trying to find the transfer function for live variable analysis. In the lecture note in 4120 the transfer function is the Union of used variables and the output variables - variables defined. However the transfer function provided there is based on single instructions, but here we treat and entire block as a unit so the definition if "used" variables is a bit different and we need to consider the variables in the entire block as a whole, meaning that the locally defined variables should not be included when counting the input variables set. Another difficulty is to figure out a way to interchange the predecessor and successor, inVars and outVars in a way that reuse the existing code to the greatest extent

[keikun555]

Summarize what you did.

• Lesson 4 Task
• Control Flow Graph
• Data Flow Analysis Tool With Reachable Definitions and Live Variable Analysis

I implemented a generic data flow analysis framework and implemented reachable definitions and live variable analysis using the framework. First, using the basic block generator from lesson 3's task, I coded a control flow graph generator that takes in a list of Instructions and gives back an adjacency list with the block's indices as IDs. Using this generator I created a data flow analysis framework in the form of an abstract interface that describes the initial conditions, merge, and transfer functions. An instance of an implementation of this interface will then be fed into the analyze_data_flow function where the worklist algorithm resides.

To make the worklist algorithm more general which allows both forward and backwards versions, I opted to have a property in the abstract interface called direction which encoded which direction the analysis should use. Within the analyze_data_flow function, we switch between predecessors/successors and in_/out variables respective to the analysis instance's direction property.

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 compared the outputs of this turnt configuration with the outputs of the turnt configuration within this bril repo directory
• One different I found is that the cond-args.defined.out output doesn't include the function arguments, in this case, cond. Although the outputs were different, I deemed that a reachable definitions analysis should include function arguments, so after this task I may look into the example implementation and raise a pull request that fixes this issue.

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

• The hardest part was implementing function arguments within the reachable definitions analysis while keeping the generic data flow analysis framework general.
• I first created two virtual basic blocks within the control flow graph: entry and exit blocks
• The two blocks serve as single entry and exit points of the control flow graphs. The entry block can only lead to the first block in the function. All blocks ending with ret or the last block in the function (if it doesn't have a terminator operation) leads to the exit block.
• Within the data flow analysis framework, I integrated the entry and exit blocks into the initial in_ and out dictionaries. In particular, for reachable definitions, I set out[cfg.entry] to the function arguments.
• I also accounted for block indices not within the basic block function here.

[he-andy]

Summary

Repo
CFG
Liveness Analysis
Utils

I implemented a CFG and general dataflow analysis framework using the petgraph library. Dataflow analysis was implemented using the worklist algorithm and is generalized to both backward and forward analyses. From this, I implemented a transfer function to perform live variable analysis on the CFG. The CFG was implemented using Rust generics and Trait bounds so it could be extended to both code-level and basic block-level granularity analysis. The CFG supports tracing (converting the CFG back to code) with code block reordering to minimize jumps. It also supports debugging via graphviz.

Here is an example:

To support more efficient basic block level analysis, I implemented a struct that would maintain the uses & defs of each basic block that were precomputed when they were generated. It was extremely simple to integrate this basic block struct into the generic CFG framework by implementing the trait CFGNode.

Usage details are provided in the readme

Testing

Correctness testing was done mostly through manual inspection of the output for several of the provided programs in benchmarks. I also ran brench on benchmarks as a sanity check to ensure that no incorrect mutations were being made to the source code. I would like to do further testing on forward direction analyses, but I only had time to implement live variable analysis for this assignment.

Challenges

My primary challenges were working with Rust generics as I didn't have too much experience with it prior to this assignment. I really wanted to make my framework as general and extensible as possible so this was definitely a priority for me. Since recursive datatypes are generally considered to be somewhat difficult to work with in Rust, I stuck with using the petgraph library which definitely had a major learning curve.

Implementation aside, testing was particularly challenging as there's no really good way of verifying the results besides manual inspection.

[bcarlet]

Summary

• Live Variables
• Reaching Definitions

Details/Testing

I implemented live variable and reaching definitions analyses via a generic solver. The solver uses the worklist algorithm and takes as parameters a direction, a domain of values equiped with a top value and a meet operator, and a transfer function.

I tested the implementation by manually inspecting the output for a number of test programs—all the ones from examples/test/df, plus a few from benchmarks/core.

Difficulties

I didn't have a good mechanism for systematically testing the implementations for this task. Other than running the implementations on all the benchmarks to ensure termination and absence of runtime errors, the best I could do to test correctness was manually inspecting output. I attempted to make this manual testing a bit easier by visualizing the CFG and analysis results using Graphviz, but it was still somewhat painful.

[alifarahbakhsh]

The link to the repo

I have implemented the data flow algorithm for the reaching definitions use case. It is not a general framework yet, but can be extended to one fairly easily.

I have tested my implementation by manual inspection of a number of Bril programs, all included in the repo.

I had two main challenges:

1. For some reason I had to change/modify the data structures that I was using as I kept adding more code. I did not have this issue in the previous tasks.
2. As mentioned in other comments, testing for this task is not straightforward. I did not try a more systematic testing pipeline for the sake of time, but even when thinking of a simple scenario, I couldn't come up with anything other than going through the painstaking process of inspecting the outputs of my code, i.e., reaching definitions at the entrance and the exit of each block.

[adi-lb-phoenix]

@alifarahbakhsh Hello , hope you are fine . I Have been referring your code to learn and understand concepts in cs 6120 .
I have a doubt regarding the function compute_reaching_defs():

in this function there exist a line of code block = worklist[randint(0, len(worklist) - 1)] :

while not worklist == []:
			block = worklist[randint(0, len(worklist) - 1)]
			in_defs[func][block] = df_merge(out_defs[func], _cfg[func][block])
			print(f"The new in_defs for block {block} is {in_defs[func][block]}")
			new_out = df_transfer(in_defs[func][block], _cfg[func][block])
			if not new_out == out_defs[func][block]:
				for successor in _cfg[func][block]["successors"]:
					if not successor in worklist:
						worklist.append(successor)

the question is why use this "block = worklist[randint(0, len(worklist) - 1)]" why couldn't you just use a for loop and just keep iterating until you reach the end . As you are appending the block , letting it iterate through the entire "worklist" seemed more correct and well defined . When you are using randint it generates a random number between 0 and (len(worklist) - 1), How did you account(more like what was your thinking) for the logic of computing definitions of a block when a certain block is chosen at random and not according to natural flow of the program . I am having problem understanding that when " block = worklist[randint(0, len(worklist) - 1)]" and the effect it has on computing definitions as I feel the order of choosing block from worklist at random will effect the incoming_definitions to the particular block . What if the incoming_definitions to this particular block should be the outgoing definitions of some block named block0 and then no definitions have been been computed for block0 as " block = worklist[randint(0, len(worklist) - 1)]" did not generate the block number representing block 0 , in tis case wount the definitions computed for block1 be wrong ?

[MrAliFar]

If I remember correctly, this algorithm is guaranteed to converge no matter the ordering you pick. Note that we maintain a sane connection between the incoming and outgoing definitions as an invariant at all times, so you do not end up messing with anything. You just have to keep repeating the process until nothing changes. I also remember that the random ordering has a better performance on average.

[adi-lb-phoenix]

Got it . Thank you for the clarification

[NgaiJustin]

Summary

• Repo Commit-based link
• Data flow analysis framework Commit-based link
• Data flow analysis (DFA) implementations that leverage the framework
  • Reaching definition DFA Commit-based link
  • Constant propagation DFA Commit-based link
• Custom CFG & DFA Graphviz Commit-based link
• Custom DFA Graphviz Animation Commit-based link

ackermann-reaching-defs	catalan-constant-prop	catalan-reaching-definition

Details

Control Flow Graph (CFG)

First I implement a new cfg library that converts bril programs into a CFG. After discussing with my peer @SanjitBasker, I decided to represent the basic block as the instruction level since this makes reasoning about the transfer and merge functions much easier. This logic is encapsulated in node.py. To ensure that my CFG construction was correct, I implemented functionality to visualize a CFG by outputting a dot file representation that I pasted into edotor to validate.

Generic Solver

I designed a generic solver that is initialized by an entry_node, in_sets, out_sets, transfer_function, and merge_function. I also use a generic T = TypeVar("T") to have a generic representation of the internal sets that are manipulated throughout the data flow analysis. This was critical when extending the solver to support constant propagation since representing the "in_set" and "out_set" as literal sets did not suffice. This enables a generic framework that supports multiple forms of analysis. This logic is encapsulated in the dfa_framework.py module.

DFA Analysis using generic solver

Leveraging my generic solver, I implemented reaching definitions and constant propagation. The reaching definitions implemented followed pretty naturally from the pseudocode in the lecture. My implementation for constant propagation used an abstract ConstantType(ABC) that is implemented by Constant, Unknown, and Uninitialized to represent the different states a variable can be in during the data flow static analysis and to implement custom merging logic that was critical to the implementation of the merge function.

DFA Visualization as a GIF

To inspect and test my data flow analysis, I decided not only to create a graphviz representation of the state of the data flow analysis (displaying the in_set and out_set at each node). I also implemented a standalone library (others can use it through the CLI) that converts a series of dot files into an animation. This enables a smooth visualization of the entire data flow analysis.

I made a few design decisions for the visualization and animations:

• If the in_set and out_set is the same, represent as a “~” to prevent clutter
• The FPS and duration of each frame can be customized, to prevent the files from being too large I picked suitable values. These values can easily be customized. Some examples include: totient.gif, ackermann.gif, catalan-constant-prop.gif, catalan-reaching-definitons.gif... More can be found under the ./lesson_tasks/l4/dfa-animations.

Testing/Evaluation

• Ran brench to make sure that analysis does not mutate/change the program, ensure that it remains correct for core
• Visually inspect the dot graph outputs for reaching definition and constant propagation to make sure that the in and out sets align with expected definitions
• Inspected the gif output of the DFA

Potential Extensions:

• Currently the DFA analysis -> dot_graph_frame -> gif pipeline is a bit slow especially the dot_graph_frame to gif, which can get really slow with many file IO operations, there exists optimization opportunities that stream the PNG as the gif is being written, sidestepping the need for duplicate file io but that’s not really the purpose of this assignment.
• Inspecting the graphviz output made testing the DFA implementations much easier. I initially thought about leveraging DFA analysis results to do basic optimizations and then compare the optimized results with the .out results to ensure parity with the unoptimized code, however, I ultimately decided against this idea since that would mean coupling the testing of the analysis and the optimization that leverage the analysis. A future extension would be to leverage this analysis to drive optimizations.

Difficulties

• Formating the graphviz files was a bit tedious because in the graphviz library I used escaped characters in a weird way, which limited the options I had for formatting the dot file output.
• I was deceived by how simple the merge function was when implementing the reaching definition which led to confusion when implementing constant propagation. Along with some idiosyncrasies of the Python languages that made creating variants slightly tedious. I ultimately resolved this with abstract types that would represent the different states of a “constant” can be in during the analysis

[matth2k]

• Summary

  • Dataflow Solver Framework
    • Source Files
      • dfsolver.py The main driver code
      • 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.

• Implementation Details

  • I implemented a generic dataflow solver that can transfer fowards and backwards.
  • This was a good exercise, because it helped me build more robust infrastructure for building control flow graphs, mutating them, then writing them back out to Json. In the end I get a super clean top-level method:

  brilProgram = json.load(args.input)
  dataflow = ANALYSES[args.analysis]
  for func in brilProgram["functions"]:
      cfg = CFG(func)
      ins, outs = dataflow.solve(cfg)
  

  • I have 5 analyses that you can run:

    • --analysis liveness Live variable analysis
    • --analysis reaching Reaching definitions analysis
    • --analysis defined All possibly defined variables (really just a sanity check for the solver)
    • --analysis constants Constant propagation anaylsis
    • --analysis initialized Variables that are guaranteed to be initialized
    • --anaylsis interval Interval analysis (Missing some features, like propagating to booleans. It also isn't smart enough to understand if it will converge or not)

  • I had Github Copilot on, but only for some repeated boilerplate code.

• Evaluation

  • To test correctness of the generic solver, I tested that all the dataflow algorithm outputs make sense for the test cases in bril/examples/test/df.
  • I also ran on all the benchmarks in /core/ and this helped show some bugs causing the algorithm not to converge. The issues were in merge() and transfer() and not the solver itself. I give details on one of the bugs in the next section.

• Anything Hard or Interesting?

  • Reaching definitions analysis is hard because you don't want just a set of variables, you want the actual complete definition for the variable. But once you get it right, its pretty satisfying because this analysis's output to me is the most insightful into what the program is doing.
  • Interval analysis is hard, because you will want to use the intervals of integers to help find the interval of bools as well. I just didn't do that part. Also, the algorithm does not take into account when control flow edges become impossible (for example knowing that i < n is a pre-condition to entering the body). So even with my current implemention sometimes interval anaylsis does not converge.
  • I use copy() very liberally to avoid unintended side-effects. I don't want my data structures to be mutable when I pass them in. And here I found that if a CFG node had a back-edge onto itself it would cause an infinite loop if the merge() function mutated its inputs! So when a block adds itself to the worklist and the input is wrongly mutated, it causes a re-triggering in the output, adding itself to the work list. And so on! It was hard to debug!

[yxd97]

Summary

• Code repo
• Implemented reaching definitions analysis. The program will print all the definitions, uses, and the definitions reaching each use alongside the bril code in text format.

@main(cond: bool) {     # defs: cond_DEF1, 
  a: int = const 47;    # defs: a_DEF1, 
  b: int = const 42;    # defs: b_DEF1, 
  br cond .left .right; # uses: USE1,                # reaching defs: cond_DEF1, a_DEF1, b_DEF1, 
.left:
  b: int = const 1;     # defs: b_DEF2, 
  c: int = const 5;     # defs: c_DEF1, 
  jmp .end;
.right:
  a: int = const 2;     # defs: a_DEF2, 
  c: int = const 10;    # defs: c_DEF2, 
  jmp .end;
.end:
  d: int = sub a c;     # defs: d_DEF1, uses: USE2,  # reaching defs: cond_DEF1, a_DEF1, c_DEF1, b_DEF2, b_DEF1, c_DEF2, a_DEF2, 
  print d;              # uses: USE3,                # reaching defs: cond_DEF1, a_DEF1, c_DEF1, b_DEF2, b_DEF1, c_DEF2, a_DEF2, d_DEF1, 
.ret:
  ret;
}

Implementation details

• I first created a small library conatining classes for a CFG to faciliate implementation of the worklist algorithm.
• In the analysis program, I first implemented a pass to find all definitions and uses in a a bril function. This pass iterates through all basic blocks and returns a mapping from basic block to lists of definitions and uses. The order of definitions/uses in the lists is their program order in the basic block. Function arguments are treated as definitions of a special block named "ENTRY".
• Based on my previous setp, I implemented the worklist algorithm for reaching definitions. The merge function is simply joining sets of definitions; the transfer function will first look for potential killers in the current basic block: if there is one, all incoming definitions of the smae variable will be removed. The killer is searched in the list of definitions returned by the previous step, from end to the beginning since the definitions that appears later in program order overwrites the ones before it.
• Along with finding the definitions and uses, I also recorded the line number of each def/use so that they can be printed alongside the original program. This makes it easier to read and verify the correctness of the analysis.

Testing

Testing the correctness of this analysis is challenging as the only way is to inspect the outputs. To comprehensively test my implementation, I created multiple test cases
that covers overwriting, branches, for loops, while loops, and nested branches/loops.

Challenges

The most difficult part to me is composing the transfer function. Although in class the definitions and uses are kept in sets; however, elements in a set does not have an order --- so it does not capture the fact that later definitions kills earlier ones. I ended up using a list to preserve the order of the definitions. The downside is that makes the merge function a little less intutive.

[zachary-kent]

Summary

For this task, I implemented a generic dataflow analysis framework and, leveraging this framework, live variable analysis. Then, I used this analysis to implement proper dead code elimination. My implementation is spread across several files as follows:

• Main library
• Generic Solving Framework
• Liveness Analysis and DCE

Implementation

Dataflow Framework

• I started off with the goal of implementing DCE in mind. Using live variable analysis to implement DCE allows me to verify the correctness of my analysis by running every benchmark with DCE optimizations using brench and then ensuring no test outputs differ.
• To support sufficiently granular DCE, I had to implement a CFG that has a node for every instruction; it is desirable to compute the live variables at every instruction so that individual instructions performing assignments to dead variables can be deleted. To this end, I implemented a CFG that stores an instruction at every node, keyed by its original position in the instruction stream.
• I then considered what would be desirable in a generalized dataflow framework so that it is generic as possible. For one, I definitely wanted to support dataflow analyses over CFGs both where each node contains an instruction and each node contains a basic block. I realized that, to enable this, my dataflow framework could not take a concrete CFG type. Instead, I developed a CFG typeclass IsCFG describing the operations that should be supported by a CFG, regardless of the number of instructions stored at a node. Dataflow analysis requires being able to get the successors and predecessors of a node (when computing the input dataflow facts and updating the worklist) and getting all of the nodes of a graph (when initializing the worklist), so I encoded these operations into IsCFG.
• Now, I could finally begin implementing the dataflow analysis framework itself. I first developed a Params typeclass describing the various parameters to an analysis, including the type of dataflow facts, the direction of the analysis, and the transfer function. I did not have to include the meet operator and top value explicit in my Params typeclass; instead, I encoded these in a super class constraint requiring that the facts computed form a bounded lower semi lattice. I used the BoundedMeetSemilattice typeclass exposed by the lattices package to do this.
• Finally, I implemented analyze which performs the main iterative dataflow computation. Following the worklist algorithm developed in lecture, it takes a CFG of type g satisfying IsCFG g and dataflow parameters of type p satisfying Params p and returns a mapping from nodes to the dataflow facts computed at that node.

Liveness Analysis and DCE

I now used this dataflow framework to implement a live variables analysis tailored for DCE. Like a typical live variables analysis, it is a backward analysis where the ordering $\sqsubseteq$ is $\supseteq$, the top element $\top$ is $\emptyset$, and the meet operator $\land$ is $\cup$. It differs from a typical live variables analysis in that variables used by instructions to be deleted -- that is, pure instructions which assign to dead variables -- are not considered generated as live from that node. The transfer function depicts this difference:

$$ in[n] = \begin{cases} out[n] & \text{if $n$ has no side effects and } def[n] \cap out[n] = \emptyset \\ use[n] \cup (out[n] - def[n]) & \text{otherwise} \end{cases} $$

I then used my dataflow framework to compute the variables live out at every instruction. To implement DCE, I deleted every pure instruction which writes to a variable not live out at that program point.

Testing

I tested my implementation of DCE by against every Bril benchmark using the brench tool, ensuring that this optimization did not break any of the benchmarks. This in turn verified the correctness of my live variables analysis, or at least that it is not under-conservative. To ensure that my implementation is not needlessly over-conservative, I compared the performance of TDCE and DCE optimizations, ensuring that DCE always performs no worse than TDCE. My implementation of LVN performs constant/copy propagation and in turn produces large amounts of dead code which was effectively optimized by DCE. I also wrote several simple diff tests using turnt to ensure that assignments to dead variables are removed as expected, including several more complex scenarios like a dead integer variable counter being bumped every iteration of a loop. The tests I ran using brench gave me confidence that this analysis was neither under-conservative nor avoidably over-conservative, and the diff tests allowed me to verify the correctness of my implementation in corner cases.

Evaluation

While comparing the performance of DCE and TDCE of eliminating dead code produced by LVN, I found that DCE never performed worse than TDCE and occasionally performed slightly better, although not significantly so. In fact, the largest speedup of LVN + DCE over LVN + TDCE was little over 1% and the median speedup was 0% (the full dataset is available here for anyone interested). I anticipated this result, as I had previously observed that performance improvements due to LVN + TDCE were largely relegated to benchmarks produced by the TS frontend. I believe identifier names are generated by the TS frontend using a simple counter, so identifier names are likely globally unique anyways, allowing assignments to dead variables to be effectively optimized by TDCE.

Challenges

The largest challenge I encountered was the question of how generic I should make my dataflow analysis framework. In the end, I decided to make it as general as possible to support future analyses. I only encountered one (particularly frustrating) bug while implementing DCE; I had accidentally swapped the infix meet and join operators exposed by the lattices library, resulting in incredibly confusing test failures. However, once I ironed out this issue, I did not encounter any more problems.

...

[evanmwilliams]

Summary

For this task, @emwangs and I implemented a Reaching Definitions analysis. You can see the code here in the lesson 4 folder.

Implementation Details

• We stuck with C++ for this task since we were extending some of the tooling we built up in the past few programming assignments (namely, basic block creation)
• In order to do Dataflow analysis we also had to implement CFGs, as well as functions that attained the successors and predecessors of a node in the graph. This led to some interesting reasoning about memory and references in C++
• The dataflow analysis itself was pretty simple - the worklist algorithm is quite robust and the only real challenge was setting up all of the classes that we wanted to store beforehand
• A generalizable framework in C++ seems a bit challenging - we will definitely come back and try to implement this but didn't have time to do so by tonight. The biggest issue with a generalizable framework is that the types in C++ will be different depending on whether we're building up a set or some other data structure. It would require either a lot of STL and template code or a lot of variants/unions/enums, neither of which sound super appealing

Challenges

• Memory issues! We had a lot of seg faults because we were trying to pass state through different objects. Basic blocks were built on top of instructions and CFGs were built on top of basic blocks, so there were a lot of fun debugging challenges while we were developing
• I personally feel a lot more comfortable with C++ now (and @emwangs was already pretty good at it), so this one actually went a lot smoother than the last one

Testing

• Testing for this one is hard! Since we're just computing facts about the program, it's not easy to verify our outputs against some kind of benchmark. We did our best by picking a representative subset of examples that we thought encapsulated the key control flows that we would run this algorithm one

[willwng]

Analysis Code and CFG Code

Summary

• We (Vivian and I) did our implementation in Kotlin.
• We implemented CFG construction and Graphviz visualization. Visualizations helped us confirm CFG construction was
  reasonable, and they will hopefully give us a nice view of the results of optimizations in the future.
• We then wrote a generic solver and dataflow framework that supports multiple analyses (both forward and backward), and applied it to reaching definitions, live variable, and constant propagation analyses.

Implementation details

• After constructing CFGs, we created some machinery that creates nodes from basic blocks and adds edges according to the control flow. The visualizer also accepts the output results from an analysis (i.e., the in/out data for each node)
• Then, we implemented a generic dataflow solver (worklist algorithm). The solver is generic over dataflow values, and takes in a description of the analysis containing the init, merge, and transfer functions. Class design was a little tricky, but this allowed us the implementation of the worklist algorithm itself to be pretty much equivalent to the pseudocode from lecture.
• We wrote a reaching definitions analysis. This was also rather straightforward due to the simple interface to the
  dataflow solver. We noticed that kill(node) is context-dependent; the instructions in kill(node) are the reaching defs which share a variable name with an instruction in defines(node).
• Live variable analysis was also implemented - this required us to add a few lines to the worklist algorithm which allows it to handle both forward and backward analyses.
• Finally, we implemented constant propagation. With the existing framework, this was reasonably straight-forward. While constant folding has yet to be implemented, this analysis should make this task simpler.

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

• Though we weren't able to test it as rigorously as the previous lesson (since no new optimizations were performed), we found that the several hand-crafted examples and graph visualizations were helpful in determining the correctness of code.
• The visualizations for CFGs helped us verify that the graphs we generated were correct, as well as the data flow along the edges.
• For testing the reaching definitions analysis, we used the tests in bril/examples/test/df, as well as tests that we wrote ourselves. We manually checked that the output was correct.

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

• The tricky part of constant propagation was how to distinguish between uninitialized variables and variables with conflicting definitions (e.g., takes two separate values on the incoming branches). We decided to define a lattice where uninitialized was at the top, known values in the middle, then "multi-defined" on the bottom. We assume that since uninitialized values isn't valid bril, it was ok the define the lattice as such.
• We also found some of the transfer functions harder to write than it looked on paper. For live variable analysis, it ended up being easier defining the equations at the instruction level and iterating through the instructions than to define it at the basic block level.

Example CFG output after live variable and (cropped) constant propagation analysis on ackerman.bril:

[stephenverderame]

Summary

• Repo
• Live Variables Analysis
• Generalized data flow framework
• Global Dead Code Elimination
• Updated the bril2cfg tool to include an option to visualize data flow

Implementation Details

• I implemented the generalized DF framework presented in class, with Live Variable Analysis as an instantiation of it.
• For backward analyses, I simply perform a forward analysis on a reverse CFG
• My DF framework is implemented at a per-instruction level. That is, the user provides a transfer function that operates on a single instruction, and my implementation of the worklist algorithm will iterate through each instruction for each basic block that needs to be run.
• My dead code elimination simply runs the live variable analysis, and any pure instruction that writes to a variable that is not live out from that instruction is removed. This process is then iterated.
• I updated my bril2cfg tool made in assignment 1 to allow the option to display the in and out facts for each block in the displayed CFG.

Testing

• I used turnt snapshot tests to manually check the displayed CFGs and their respective data flow values. Example:
  

• For testing DCE, I did the usual process of running it (and thus the analysis) on all test cases and benchmarks. I was particularly interested in comparing the result of Local + Trivial DCE with Global DCE after LVN. In doing this test, I obtained the following summary statistics of speedup over baseline:

  DCE Style	Mean	StdDev	Quart 1	Median	Quart 3
  Lcl+Trvl	1.415x	0.485	1.000x	1.083x	1.628x
  Global	1.462x	0.684	1.000x	1.086x	1.728x

  So at least for a local optimization, specifically LVN, Global DCE does help, but not by a large amount.

• For testing DCE, I also checked the actual resulting BRIL code to make sure it is also as I would expect

• Between the DF tests and the DCE tests, I felt that both helped point to the correctness of the analysis

Challenges

• My CFGs have special ghost start and end nodes, and handling these took a little care in extra conditionals for doing this correctly

[Arthur-Chang016]

Summary

Liveness Analysis
make live

Implementation Details

• The output would not be the bril program. Instead, it would be the result of analysis, so the usage of the program cannot be pipelined into brili.
• To make life easier, I make every instruction as a single basic block, so when the global analysis performs, I don't have to deal with local analysis.
• To reuse the basic block builder implemented last time, I extended it to be CFG builder (adding edges).
• Make best use of C++ std libraries to perform set union etc.

Difficulties

• To figure out the init, merge function, transfer function myself of liveness analysis. It's a little bit different from what I can find on the internet but I believe it's correct.
• Tons of details I have to deal with.
• To avoid seg faults (I am using C++), I try to avoid all usage of pointers and copy a lot of variables and arguments. Since the performance is not the most important issue here, I turned the code to be safer but slower.

Test

Runnable on hand-written brils and on eight-queens.bril.
The output is reasonable.

Future Work

• It should be able to turn it into a generalized data flow framework which extract merge function, transfer function, and executing order out as independent functions.
• Liveness analysis should be useful for global DCE.
• Change the code to be high performance. Eliminating too much copy in C++ code base. Smart pointer might be a good candidate.

[ryanwmao]

@xalbt and I worked together on lesson 4.

Summary

repo
core files
analysis

Implementation

• We used C++ for this lesson's tasks.
• We first implemented several functionalities in a core folder in the repository in order to parse and work with JSON files, support frameworks for CFGs (and reason about basic blocks), in addition to typing which we anticipate will be very useful for the future.
• We then implemented Liveness Analysis. We implemented a worklist algorithm and closely followed the dataflow analysis. In representing our in/out sets, we use bitmasks to represent membership to the sets.
• We then implemented Reaching Definition Analysis. A lot of the implementation for this analysis was similar to that of Liveness Analysis, excluding the different dataflow equations.
• Drawing from these two implementations, we extracted a lot of the common code between the two analysis to create a generic dataflow analysis solver, which takes a function as input that processes the majority of the dataflow computations. Given a custom initialization function, implementation of a generic dataflow value class, and implementation of an analysis function, this generic solver performs the analysis using the worklist algorithm and our basic block framework.

Difficulties

• Making the framework general was a bit more difficult than we anticipated, because there was quite a bit of dependencies in our implementations and the specific dataflow analysis we were performing. We were eventually able to extract enough boilerplate code, however
• There were a ton of details in the individual analyses that we had to pay close attention to, and debugging the analyses took quite some time
• There were also a lot of details to pay attention to in particular relating to Bril when implementing our parsing functionality as well as the general pipeline towards forming basic blocks
• Overall, there seemed to be a lot more to work with on this assignment compared to the previous assignments, so all stages of the workflow required a bit more effort than we expected.

Testing

• We found testing in general to be quite nontrivial, and we ended up manually verifying our analysis results with those of a human analysis. We performed the testing for 10 of the benchmarks in the core folder to ensure that we were relatively confident about our program's correctness. An example output for liveness is below:

Output for quadratic.bril from benchmarks/core

main
_bb.0
	in : a, b, c,
	out:

sqrt
_bb.0
	in : x,
	out: x, i,
for.cond.0
	in : x, i,
	out: x, i,
for.body.0
	in : x, i,
	out: x, i,
then.7
	in : x, i,
	out: x, i,
else.7
	in : x, i,
	out: x, i,
endif.7
	in : x, i,
	out: x, i,
for.end.0
	in :
	out:

quadratic
_bb.0
	in : a, b, c,
	out:

[obhalerao]

Summary

Repo

Implementation Details

In this assignment @SanjitBasker and I implemented a dataflow analysis framework and instantiated it on two dataflow analyses. We continued to use C++ for the assignment. We implemented the formation of CFGs (which is an extension of the basic block forming algorithm we used in the last assignment) and then wrote a template class for the dataflow analysis. We had some trouble getting the main program to take advantage of our template class, but it can be instantiated through a simple interface in which one provides the meet and transfer functions (and also a utility function for making "top" values with which to initialize the analysis). The analysis can proceed in a forwards or backwards direction, but we realized only after implementing the solver that it may have been a cleaner design to make this a template parameter.

Testing

In order to validate our implementation, we implemented analyses for constant propogation and defined variables. We then visualized our results by generating graphs in DOT. This was a bit painful because we couldn't find any C++ libraries for graphs that give full control over the rendered labels. So we decided to generate the graphs ourselves, which we visualized in Edotor.

For fun, we also implemented a DFS-based traversal of the CFG and used this to solve the dataflow equations: when we discussed this topic in CS 4120, we learned that solving the strongly connected components of the graph in order will result in faster convergence than a naive worklist, since nodes are solved after their dependencies. In both implementations, we measured the number of times that a node was taken off the worklist and processed (this is equivalent to counting the invocations of the meet function). This was the measure of "performance" for our brench benchmark, with the correctness being a text report of the dataflow results. Our results are hopeful, but it seems that in some CFGs the naive worklist can outperform the DFS-based solver. We are happy to report that the results are the same regardless of the solver.

Below are some pretty charts detailing the results of our two solvers on our first analysis, defined variables:

And here are some charts detailing their results on our second analysis, constant propagation:

Firstly, we want to note that the primary purpose of developing this alternate traversal of the CFG to solve the dataflow equations was for testing with our original method, and these results we found here are very preliminary. Regardless, we find it surprising how so many of the speedups are by exactly a factor of 2, and also why the supposedly more efficient DFS-based traversal of the CFG performs so poorly on some of these test cases (most of these poor-performing tests consist of one large SCC), and we feel as though it would be interesting to analyze this behavior further.

Challenges

Getting used to the class hierarchy structure in C++ was something we faced challenges with, as this was the first time we had to deal with them in a project. In addition, we faced some difficulties with the transfer function for constant propagation, as we did not deal with undefined variables correctly on our first pass.

[SanjitBasker]

Some items that didn't make it into the writeup before midnight: (commit based link to code)

Implementation Details

Since we have a figure of merit for each function that we are analyzing, we wrote an extension to brench which allows "labeling" the figures of merit, and parsing them with the regex in the configuration.

Testing

We did investigate why many of our speedups were exactly equal to 2. The first thing we noticed is that our naive solver is extremely naive: instead of maintaining any worklist, it performs the transfer and meet computations at every node in the CFG as long as the values at any node are changing. So we wrote a worklist-based solver to make the comparison more fair.
The other reason is that our naive solver processes nodes for instructions in the order that they appear in the program. For most Bril programs written by a human, this is a decent approximation of the reverse postorder traversal. However, it can be fooled quite easily by reversing the order of the basic blocks. So we wrote a Python script which outputs a Bril program whose CFG is a series of $n$ diamonds, but the blocks are in reverse order, except for a jump at the start of the function. We then ran our benchmarks on these programs (recall that "speedup" is the relative decrease in the number of iterations for the dataflow equation solver).

While the worklist algorithm has some speedup over the naive algorithm, the graphs show that in the worst case, the speedup obtained by DFS traversal is more than a constant factor. This also helps explain why this optimization was so useful for my group in CS 4120 (we went straight from no worklist to DFS + worklist and our compile times improved drastically).

Generative AI

I used ChatGPT to generate some helper functions/classes (indicated in the source code) and also to write the loop that parses command-line arguments. The outputs were generally useful: my strategy was to simplify the problem, then ask ChatGPT, and then adapt back to my situation. I think that ChatGPT is a great tool for avoiding the odium of writing silly things like command line parsers. In particular the command line for this tool doesn't need to be super functional, so installing and using a mature C++ library like Boost seems a bit overkill, whereas if I wrote it myself it would probably be very unidiomatic.

[Enochen]

Summary

I switched over to a new repo after working on a fork of the bril repo. I found it was getting a bit cluttered.

CFG
Generic Worklist
Reaching definitions
Live variables

Implementation

I switched over completely to Rust from TypeScript which led to a lot of time spent learning and catching back up. I had to rebuild (and build new) utility functions, and had opted to reimplement my LVN (previously in TS) just to get more familiar with Rust. As a result I started a bit late on this.

I started by building a CFG. I used a graph library to skip the painful parts and modeled a CFG as a directed graph with each vertex being either a basic block or an empty return, representing the exit. I then just looped over the basic blocks in order as they appear and handled the Return, Jump, and Branch instructions accordingly. As a fun/annoying implementation detail, I ended up referring to each block by its index in the overall ordering for the function; I am new to Rust and I was having a hard time using the Block structs themselves as vertices.

Random note, but I thought to label each directed edge with extra information - namely, for a Branch instruction I labeled the two edges with True and False. This didn't turn out to be useful for the analyses I implemented in this task, but I think this could be used in other kinds of analyses with CFGs, coupled with constant folding for example to eliminate dead blocks.

I then implemented reaching definitions using the CFG, using the worklist algorithm in class as a model but pretty much hardcoding everything. This actually turned out to be the wrong thing to start with because each reaching definition is not a string/variable name but a reference to where something was defined, so it made everything much more complicated.

However I ended up making things work and took advantage of Rust traits to factor everything out into the meet, and transfer abstractions for a generic worklist algorithm. I then used this to pretty easily implement live variable analysis.

Difficulties

Learning Rust was and still is pretty difficult, but I'm sure it'll get better over time.

I found going from a "hardcoded" reaching definitions algorithm to a generic worklist algorithm to be the hardest part of this task. Because as mentioned before, I used block indices to refer to blocks, and a reaching definition required one of these indices to distinguish itself from another reaching definition from a different block. Thus my transfer function ended up taking in one of these indices (totally unneeded for live variables which I implemented later). This additionally introduced complications with the special Return vertex, which doesn't have an index at all. I ended up skipping the Return block when applying the transfer function, which didn't feel like a terrible breach of correctness as this was a special "block" I had made up anyways.

Testing

I mostly relied on handwritten bril programs to verify correctness. I also took some benchmarks (including the one I added) and did the analyses by hand and made sure my code was giving the same results. Finally, I did my DFAs on every benchmark just to make sure nothing crashed, though this wasn't really a convincing test of correctness.

Here is one example output of reaching definitions for a handwritten test (I spent a lot of effort to pretty print the reaching definitions in a readable way)

Next Steps

I'm going to make the worklist algorithm more generic by adding the init "configuration(s)". The two analyses that I implemented ended up using the default of empty vector, so I didn't face the need to factor that out of the algorithm when implementing my second analysis.

I also think I can refactor the way I handled going backwards via the worklist algorithm. It was more of an afterthought as I had started with just the forward version, so there is some hacky logic I think I can improve.

[AliceSzzze]

Repo

Implementation

I started off implementing live variable analysis at the basic block level. To do this, I first had to write code to form basic blocks because I hadn't done that yet. Then I implemented the analysis using the worklist algorithm. The result of the program is what is live on entry and exit of every basic block.

While building the basic blocks, I decided that unreachable code would just be ignored. For example, if there are some instructions after an unconditional jump, they won't be in any basic block. I don't think they are very interesting and it wouldn't be too hard to include them.

Testing

This is harder to test because the analyses aren't direct optimizations in my implementation. I picked a range of bril programs with different control flows and manually verified that the analysis was correct. This is not very satisfying or reassuring, which is why I would like to make them into actual optimizations if I have time.

Thoughts/Challenges

• In hindsight, maybe I should have implemented the analyses at the statement level, which would lead to more precise optimizations.

Example output from the live variable analysis using a snippet from the conjugate gradient benchmark.

[jdroob]

Summary

@20ashah and I implemented a data flow framework for the special case of a reaching definitions analysis. We utilized our CFG module from a previous lesson in order to construct a CFG which was used as input to our implementation of the worklist algorithm. Currently, we are able to accurately compute reaching definitions at any arbitrary block in a given CFG. A goal of ours is to produce a generalized implementation of the data flow framework that takes in arbitrary meet operators, transfer functions, and directions.

Testing

The testing for this task was rather ad-hoc. We verified the correctness of our results manually based on printed output. Obviously, this is not ideal and certainly not a robust way to confirm the correctness of our implementation. Utilizing GraphViz would make results simpler to verify by inspection and we could also write a test that could check the .dot files used to generate GraphViz images.

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

The hardest parts for us were the subtleties of implementing a data flow framework where the fundamental units are blocks rather than instructions (which we'd used in a previous class). An example of a subtlety that through us for a loop was handling the case of a variable being redefined within a single block (e.g. within a single block, x = 4; x = 5; where only x = 5 should be in the out set).

[bennyrubin]

Summary

Implementation code

I implemented reaching definitions, where it keeps track of each definition by the line number in the original program. It will then print out which specific definitions could still be reached in any given block. This gives a little extra information about which specific definition of a variable is reachable, rather than just the name of the variable.

Testing

I tested by having a few programs I inspected manually, including some larger one from the benchmarks. This is not a very satisfying way to test and ideally I would have liked to actually implement an optimization I could test using brench. I was quite excited about this week’s task and enjoyed implementing it. Unfortunately, I didn’t have much time to do anything more interesting than the basics, but I plan on revisiting this topic to build out the general framework and more interesting data flow analyses that I can build into optimizations.

Challenging parts

I had some pretty frustrating debugging experiences with the last assignment, so thankfully this one was much smoother and was easy to translate from what we had done in class. The main difficulty was convincing myself that my implementation is correct, by using manual inspection, which is time consuming, error prone, and not that convincing.

[jiahanxie353]

data flow analysis implementation code here

Summary

I implemented a generic data flow analysis framework and worklist algorithm using templates, and later tested it out with reaching definitions. Since I have been migrating to C++, I started off with rewriting my lesson2's Python CFG implementation to C++ and added more functionalities supporting get successors/predecessors for the data flow analysis task. Then I wrote a generic data flow analysis framework and worklist algorithm, with the goal of supporting multiple analysis. Since different data flow analysis problems have different types, I designed a "function factory" to produce different merge and transfer functions accordingly. Although I ended up with only reaching definitions because of the unforeseen debugging process, I will extend the functionality in the future.

Testing

Testing this task is tricky, and I had to manually draw out the control flow graph and inspect the value passing in/out each basic block. And I used turnt to test some representative cases to verify my reaching definition implementation was correct.

Challenges

I rewrote my form basic blocks and build cfg in C++ and didn't test it out fully before moving on to data flow analysis. This led to long and frustrating debugging process. I will incorporate unit tests for small functions in the future, instead of testing the final deliverable in the end. By testing out bit by bit, although demand more time and effort at the moment, will save a ton of time in the long run.

[collinzrj]

Summary
https://github.com/collinzrj/cs6120tasks/blob/main/task4/dataflow_analysis.py

I used python for this task. I first implement a build_cfg function to build the cfg of the program. The build_cfg function outputs a dictionary of name of the block to its parents and children. I have also implemented a generate worklist_algo function that takes an Analyzer object that helps it perform the data flow analysis. The Analyzer object should have two functions: merge and tranfer, and the worklist_algo function calls these two functions to perform the data flow analysis.
The dataflow analyzer returns the inputs and outputs of each block when it finishes.

Testing
I start with a simple bril program can manually compare the results of the program to the bril program. I have picked several programs such as gcd.bril, rect.bril, bitshift.bril to make sure the program is correct in different cases.

Hardest part
What was the hardest part of the task? How did you solve this problem?
The hardest part I encountered is the implementation of the build_cfg function. When I first implement it, I'm just looking at the end of a block to see if it has a jmp or br operation, then set the labels of that block as its children. However, it turns out to be incorrect since a block and also transfer to another block without a jmp or br statement. To solve this problem, I maintain a list of blocks for which the blocks are sorted in the order as they are in the program, then I iterate through the list to check if the block has a jmp or br operation at the end, if it does not have, then the next block in the list will be its child. Another tricky part is to name the blocks without a label. In my implementation, I generate a uuid as their label when I encountered a new block.

[janpaulpl]

Source

DFA (Constant Propagation)

Implementation and issues

For this lesson, I made use of the existing CFG construction code under the bril repository. I implemented a constant folding worklist algorithm through an intra-procedural analysis. CP computes the set of variables at each point in the CFG that contains an int, float, or bool constant. For each of these, I implement operations that equate to their argument instructions in Python.

Benchmarking

For benchmarking, I made use of brench and I used my own birthday.bril example while manually comparing the results. With the exhaustiveness of brench's output, I'm convinced my eye-ball verification technique is fine enough for this implementation.

Birthday.bril output:

b0:
 {} (in)
 {'v0': 0, 'prob': 0, 'v2': 0, 'i': 0} (out)


for.cond.1:
 {'v0': 0, 'prob': 2, 'v2': 0, 'i': 2, 'v3': 1, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 2, 'log': 2, 'v9': 2, 'v10': 2, 'v11': 2, 'logUpdated': 2, 'v12': 2, 'v13': 2, 'v14': 2, 'v15': 2, 'v16': 2, 'v17': 2} (in)
 {'v0': 0, 'prob': 2, 'v2': 0, 'i': 2, 'v3': 1, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 2, 'log': 2, 'v9': 2, 'v10': 2, 'v11': 2, 'logUpdated': 2, 'v12': 2, 'v13': 2, 'v14': 2, 'v15': 2, 'v16': 2, 'v17': 2} (out)


for.body.1:
 {'v0': 0, 'prob': 2, 'v2': 0, 'i': 2, 'v3': 1, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 2, 'log': 2, 'v9': 2, 'v10': 2, 'v11': 2, 'logUpdated': 2, 'v12': 2, 'v13': 2, 'v14': 2, 'v15': 2, 'v16': 2, 'v17': 2} (in)
 {'v0': 0, 'prob': 2, 'v2': 0, 'i': 2, 'v3': 1, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 2, 'log': 2, 'v9': 2, 'v10': 2, 'v11': 2, 'logUpdated': 2, 'v12': 2, 'v13': 2, 'v14': 2, 'v15': 2, 'v16': 2, 'v17': 2} (out)


for.end.1:
 {'v0': 0, 'prob': 2, 'v2': 0, 'i': 2, 'v3': 1, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 2, 'log': 2, 'v9': 2, 'v10': 2, 'v11': 2, 'logUpdated': 2, 'v12': 2, 'v13': 2, 'v14': 2, 'v15': 2, 'v16': 2, 'v17': 2} (in)
 {'v0': 0, 'prob': 2, 'v2': 0, 'i': 2, 'v3': 1, 'v4': 1, 'v5': 1, 'v6': 2, 'v7': 2, 'v8': 2, 'log': 2, 'v9': 2, 'v10': 2, 'v11': 2, 'logUpdated': 2, 'v12': 2, 'v13': 2, 'v14': 2, 'v15': 2, 'v16': 2, 'v17': 2, 'v18': 3, 'v19': 3, 'v20': 3, 'v21': 3, 'v22': 3, 'v23': 3, 'v24': 3} (out)