Lesson 4: Data Flow

[sampsyo]

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

[scober]

code

I implemented the live variables analysis as a backward pass and then constructed a forward pass by moving the core loop into its own function and passing all the swappable arguments swapped. I implemented interval analysis as a forward pass and I was pleasantly surprised by how well it worked. It was surprisingly easy to add a new analysis once I had the framework in place.

Live Variables

This was pretty uneventful. I ended up not putting my worklist into topological sort order. All of my test programs were short enough that I didn't need the speedup and I have implemented topological sort before so it didn't seem super valuable.

Interval Analysis

This one had my favorite "bug" of the lesson. I ran into an issue where one of my tests was running for a very long time (it was palindrome.bril in the core benchmarks). It was because there was a counter variable that was incremented by 1 in a cycle in the cfg (it was a for loop). The issue was that the maximum element in my poset was a set of maximal intervals (i.e., a=[-2^63,2^63-1], b=[-2^63,2^63-1],etc.).

So my algorithm was guaranteed to terminate, but it would have to reach 2^63-1 one increment at a time. I decided that was infeasible and just dropped any interval that exceeded the bounds of [-1000,1000]. My logic was that very large intervals are not that useful for optimization anyway (ignoring things like non-negative or non-zero intervals).

It made me curious about how "real" compilers/analysis tools handle this case. Maybe you could identify cycles that have this property and short-cut the trip MAX_INT? It sure seems like vanilla data flow will not be able to handle this efficiently.

Testing

I used turnt to test my analyses. This seemed like exactly the sort of situation turnt is perfect for. Each test case needs to be carefully inspected by a human for correctness and then the only invariant to maintain is that the output hasn't changed. I used some hand-written test cases and some test cases stolen from the bril benchmarks directory.

One turnt lesson I learned: don't make your formatting data-dependent. I had my data flow tool align the in/out sets for each basic block and that was nice for me but terrible for turnt. If I made a small change to fix a bug it could modify every line in the output, making the turnt diff useless.

[sampsyo]

That is indeed a really entertaining problem with interval analysis! I think you're right that the sensible solution here is to "max out" the intervals at some upper bound. Interval analysis itself has a pretty deep literature, so it might be fun to do some googling to see if there are examples of people doing the more advanced thing that you suggest (i.e., more proactively detecting cycles that are guaranteed to expand indefinitely and giving up).

Nice work overall!

[UnsignedByte]

Code

Generic Implementation

I started off by implementing the generic worklist implementation of Dataflow passes here for use in my later algorithms. This was actually surprisingly simple, and I mainly just followed the pseudocode in my implementation. It also supports both forward and reverse passes, which was achieved simply by reversing preds and succs.

Passes

I implemented every recommended pass except for Initialization checking, as bril doesn't have declare-before-initialization behavior, and as such I felt that the pass might not be very useful.

Reaching Definitions

As mentioned in class, I used sets of definitions and a meet function that was simply set union. Therefore, I simply stored variable names along with an identifier for the location of the instruction they were defined in to use as unique definition identifiers. Thus, when a definition happens, it kills all existing definitions with the same name, regardless of the location. When printing, I would access the location of these definitions to create a set of possible definitions for each variable that reach at a given point.

Live Variables

This was even simpler than reaching definitions as reads contained no values, and thus I did not even need to store which specific reads occurred, and instead just saved whether or not a read happened. Here, I once again used sets with unions, but values were just the variable names.

Constant Propogation

For constant propagation my mapping was a dictionary from variables to values, each value in three possible variants: None, referring to a known non-constant value, nothing (which occurs when the variable is missing from the mapping), referring to an undeclared variable, and a constant integer/float/boolean value. In the transfer function, we simply perform constant folding (if we can) and update the mapping. When merging, we perform the following:

1. For each variable, find its value in each of the input maps (if they exist)
2. If there is one unique binding, keep it.
3. Otherwise, set it to None.

This causes undefined behavior if a value that is undefined in some paths and defined in others is accessed, but I decided that was a valid tradeoff as these programs are malformed and could be caught somewhere else (for example in an initialization checking pass)

Available Expressions

For available expressions, the meet function I chose was set intersection, as only expressions that are defined in all incoming paths are guaranteed to be available. Otherwise, I simply stored sets of expressions (provided I knew they had no side effects). In the transfer function, when a new definition occurs, I discard all expressions that depend on the variable (as they may now be invalid).

Interval Analysis

Interval analysis was similar to constant propagation in that I defined a number of functions that performed interval folding in the transfer function. For example, if I am given two intervals [a, b] and [c, d] in an expression add [a, b] [c, d], I get an output interval [a+c, b+d]. This was done for all the constant operations (integer/floating point math, comparison operators, boolean operators) and during the transfer function I simply updated a mapping accordingly. When merging inputs, I simply take the smallest interval containing all intervals of the inputs for each variable.

Unfortunately, as integers/floats do not have a maximum or minimum value, this meant that my function was not guaranteed to ever terminate, especially when loops occur, like the following:

@main(iters: int) {
  one: int = const 1;
  i: int = const 0;
.head:
  cond: bool = lt i iters;
  br cond .body .end;
.body:
  print i;
  i: int = add i one;
  jmp .head;
.end:
  print i iters;
}

Here, i would start as an interval [0, 0] and then repeatedly increment its maximum possible value ad infinitum each iteration. In order to prevent these cases, I decided to simply have a maximum iteration count associated with each block. Each time transfer occurred on a block, its associated iteration count would increase. If the block had not stabilized by the maximum number of iterations, a final iteration occurs and all interval values that change in this iteration are set to infinity. For example, if i starts at [0, 1] and ends at [0, 2], we set the interval to [0, inf) to account for possible problems. I am not totally confident that this is a completely robust solution, but my testing shows that it seems to work generally, and it avoids the infinite looping case. I am not sure how else we would be able to avoid looping, other than maybe setting an arbitrary maximum value on numbers (though this would also cause problems if integer wrapping comes into play...)

Summary

The most complicated passes to implement by far were constant propagation and interval analysis, as both had some extra casework to deal with when loops and branches came into play. Especially with constant propagation, I initially had multiple incorrect implementations including using set union and intersection for values, and particularly when dealing with the loop and branch cases with undeclared variables. Over all, I would say I deserve a star for this week because of all the different passes I implemented. Honestly my main lesson from this week might be that it is time to switch to rust, as my python code is getting messier and messier as each week goes by, and I kept thinking (for example in constant propagation) how useful enums and matching could be...

[sampsyo]

Awesome. Glad that this solution (exploiting undefined behavior) was a reasonable resolution to the whole kerfuffle around constant propagation with partially-undefined uses.

And that is indeed a straightforward solution to the problem of ever-expanding intervals in interval analysis. In general, I think you can conclude that your approach is safe, because it only ever over-approximates the true intervals (which should always be OK). It's a little funky because it involves storing extra per-block metadata that is not part of the lattice of values that we're looking for, but that doesn't seem like an actual problem.

You make a solid point about wanting to switch to Rust, but I can't resist pointing out that Python has both enums and pattern matching these days.

[UnsignedByte]

It turns out my solution was not in fact safe - I think it should instead be simply assuming that all variables written to must become $(-\infty, \infty)$... Take for example if we have x: int = mul x -2;. Then, depending on the parity of the last iteration, we would either get $[x, \infty)$ or $(-\infty, x]$, neither of which is actually correct.

[ananyagoenka]

https://github.com/ananyagoenka/cs6120-lesson-tasks/tree/main/l4

I implemented a general data-flow solver to support multiple analyses, including reaching definitions, live variable analysis, and constant propagation. The solver follows a worklist-based approach, updating in/out sets for each basic block until convergence. It supports both forward and backward analyses by modifying how predecessors and successors are handled.

Reaching Definitions and Live Variables

Reaching definitions tracks where variables are assigned, propagating unique identifiers (variable name + block label) through the program. The challenge was ensuring definitions were properly killed when the same variable was reassigned. Live variable analysis was conceptually simpler but required careful ordering within blocks—variables should only be marked as live if they were used before being overwritten.

One tricky case was handling dead stores: if a variable was defined but never used afterward, it should not be marked live. Initially, I wasn’t properly excluding these cases, leading to unnecessary propagation of variables that didn’t affect program execution. Fixing this made the results more precise.

Constant Propagation

Adding constant propagation required switching from sets to a mapping of variables to known values. A variable could either hold a concrete constant, be undefined (⊥), or be nonconstant (NC) if conflicting values were encountered. The merge function had to carefully track variables across branches:
• If a variable had the same constant value across all paths, it remained constant.
• If it had conflicting values in different paths, it became NC.
• If it was missing in some paths and defined in others, it remained ⊥ unless used, in which case it became NC.

Arithmetic operations were handled by constant folding when all operands were known. A subtle issue arose when dividing by variables—if the divisor was NC, the entire operation had to be marked NC, while a divisor of zero required special handling to avoid division errors.

Debugging & Testing
One unexpected issue came from Python’s mutable dictionaries. Initially, I was mutating the state mappings in-place instead of creating fresh copies, which led to incorrect propagation between blocks. This caused variables to appear constant when they shouldn’t have been, especially in loops where values should have been reset on each iteration.

Another fun bug was dealing with variables that were only defined in some branches but later used unconditionally. Initially, these cases weren’t being caught, which led to incorrect results where undefined values propagated as constants. I fixed this by ensuring any undefined variable used in an operation was immediately marked as NC.

I used turnt to test my implementations against a mix of the benchmarks in the bril repository as well some hand crafted interesting cases.

[sampsyo]

Awesome; this all sounds great! That's an interesting "war story" about aliasing mutable dictionaries in Python; it's easy to see how that could become a huge headache that would be hard to track down. Sounds nasty!

[mt-xing]

This was admittedly a less ambitious week for me due to time constraints.

I did implement a generic solver that can support any workflow analysis provided the right form inputs, as shown in class. This was surprisingly easy in a language with a decent type system and first class functions, like TypeScript. I only had time to use it to implement reaching definitions, but it was quite satisfying to simply call my worklist algorithm, pass in a few lambdas, and have a working solution just kinda fall out of the sky.

My algorithm specifically returns, for each basic block, a map from variable names to a set of instructions where that variable was defined and there exists at least one path from that definition to the end of the current block without the variable being overwritten. You can run my program by cd-ing into the l4 folder of my repo and then running deno index.ts <FILENAME> where <FILENAME> is either a .json or a .bril file path. Deno will ask for file read permissions and, if a .bril file is provided, will also ask for execution permissions as my code automatically invokes bril2json. You will need bril2json on your PATH in this case.

Since my program does not modify code, I wasn't able to use my testing harness from last week. Instead, testing was predominately manual, involving a few handcrafted test cases that exploit loops, branches, and combinations of variables that are either overwritten or not overwritten in each of those cases. The output from these were manually examined for correctness. I also ran my test against my benchmark from week 1, which was a much larger program, and manually checked the output at the end of each function for correctness as well. In the absence of meaningful code modifications, I believe these handcrafted scenarios that test as many edge cases as I could think of are the best I was able to do in terms of convincing myself my code was correct.

The most interesting design decision was deciding what I wanted to return. Originally I just returned a set of variables that were defined, but I found this wasn't actually interesting as nothing ever dies without being replaced by a variable of the same name. I then switched to a map from variables to an array of definitions, before finally switching that array for a set, for ease of computing set unions and equality checking.

While basic, I did complete the task, as well as the optional general solver that can run both forwards and backwards (inside dataflow.ts), which in my opinion was actually really fun. As such, I believe this work deserves a star.

[sampsyo]

Excellent! Sounds like everything worked, time constraints or no. 😃

[Annacaro22]

Code is here.

I implemented the general data flow framework, and used it to implement reaching definitions. I started on initialized variables, too, but that version is still a bit buggy-- I will update if I get it to work, but I'll just submit reaching definitions for now.

I had started before Tuesday's class and so had started with the general framework instead of working on just reaching definitions in specific. I think it did make it easier for me though to abstract the different parts of the algorithm away from each other at the very start.

I found this week's algorithm particularly hard to test, because it doesn't actually change the code itself (for reaching definitions); I wound up just having to come up with edge cases and test them by manually checking my expected output against what was printed to the terminal. I also ran it on my test suite I made last week to check for correctness-- though this doesn't really check for correctness of the algorithm, it just checks to make sure the program actually finishes without getting stuck in an infinite loop or hitting an error.

That was enough to help me catch a pretty significant bug, though. I made the (in hindsight regrettable) design decision to store my reaching definitions as lists of instructions (just storing the instructions which generated the definition that reaches to this point). This was because in python at least, dicts (which was how the instructions were stored) cannot be stored as elements of a set. This meant I had to write my own big union function, but that wasn't too bad. However, where it really bit me in the behind was the "not getting stuck in an infinite loop" part: I wrestled with an infinite loop bug for a couple hours before realizing that when I was checking if the "out" value of the current block was unchanged or not, I had just written "if list != oldlist", and so was also classifying the case where the elements were identical but in a different order (because lists) as one where more things should be added to the worklist. This made things never terminate because the order of, say, the last two definitions could just keep getting swapped over and over infinitely. So, whoops. Honestly, having it stored in lists was a real pain, I wish I had just come up with a different workaround from the start to use sets.

Still, between my testing of as many edge cases as I could think of (including cycles, re-defining variables across blocks and throughout cycles, changing arguments that had been passed in, having multiple functions, etc) and then checking for pure error-and-inf-loop free correctness via testing on the benchmarks (which also helped me catch some actually correctness errors, too, because it led me to more complex edge cases to test), I am now confident that my reaching definitions works as desired.

I do think I deserve a Michelin Star this week because I implemented the general algorithm as well as reaching definitions in specific, and this general algorithm can be used for the other problems. Also, debugging made me suffer. As usual. :)

[sampsyo]

All sounds great, except for the suffering!

I started on initialized variables, too, but that version is still a bit buggy

FWIW, as @UnsignedByte noted above, "initialized variables" is a teensy bit funky in Bril because there is no way to declare a variable without initializing it. So I dunno, you could imagine just skipping that one altogether unless you think there is an interesting Bril-compatible twist to explore.

Honestly, having it stored in lists was a real pain, I wish I had just come up with a different workaround from the start to use sets.

That does indeed sound like a huge pain. One general category of alternative, FWIW, could be to store store the instructions separately and assign them some kind of (small, immutable) identifier. Like an integer or a string that uniquely identifies the instruction. You would want to be able to look up the original instruction using this ID, but by just passing around IDs instead of entire instructions, you avoid both the problem you described and other potential issues arising from instructions that are distinct but structurally identical (e.g., two different occurrences of x: int = add y z that appear at different points in the program).

[mariasoroka]

Here is the code: link

I implemented reaching definition analysis. The implementation itself was not very hard, except for debugging one infinite loop. It was not very clear what the best way to test my code would be. I ended up running it on small handwritten examples to test specific cases (like making sure that function input arguments are killed correctly) and plotting CGFs with ins and outs for each block to make sure that merge and transfer functions are correct. I run the code on the entire benchmark suite to make sure that my code completes on all of the programs and that there are no infinite loops.

I routinely use copilot for autocompletion. I find it useful when it can "guess" what I want to write next i.e. importing missing packages, but useless otherwise. I did not use any text prompts for this assignment.

[sampsyo]

Looks good to me, @mariasoroka! If you have a moment, it would be interesting to know what the root cause of the infinite loop turned out to be.

[mariasoroka]

Oh, it was a simple bug. I had the wrong order of adds and deletes in my transfer function. It can happen that the definition 'a' should be both removed and added to the list of reaching definitions. I was doing both, but instead of deleting first and adding afterward, I was adding it first and then removing it. Essentially, map = {a}; remove a; add a; results in map = {a}, but map = {a}; add a; remove a; results in map = {}. This means that my transfer function is, of course, incorrect, but also it is not strictly monotonic. That makes me wonder... During the lectures, we discussed that the transfer function should be monotonic; will it be more precise to say that it should be strictly monotonic?

[sampsyo]

Aha, that would do it! That sounds interesting!

That's a good question about whether we want the transfer function to be strictly monotonic. You make a good point about wanting to make progress somehow (i.e., being able to prove a liveness property that we eventually make progress toward a goal). But it seems like there are reasonable transfer functions that are only weakly monotonic, such for "live variables." (When a variable is killed within a basic block, I think that adding that variable to the input set keeps the output set the same? So that would be only weakly monotonic with the subset order.)

[mariasoroka]

Ah, I figured that my transfer function was actually violating monotonicity (not only strict monotonicity) in some scenarios, and that led to the infinite loop.

[tean-lai]

Code

I implemented a general data flow framework, and so far I have constant propagation/folding, initialize variables, and liveness implemented. This felt like a good application for functors/dependency injections. When it came to dealing with backwards passes, I just literally swap around pred and succ, and in_prop and out_prop before and after the analyses. I did this because I was lazy, but in hindsight, this kind of made it harder to reason about, not sure if I would recommend doing this.

I started with these analyses for now because they seemed fairly simple to get correct, but I will update this post as I implement more analyses. To be honest, I did start by just immediately implementing the general framework first, but that's because I had written the general framework already prior to last class, but this didn't prove to be much of a hinderance to anything.

A lot of testing was non-rigorous by eye-balling print statements of the trace properties. But I did modify my constant folding dataflow implementation to actually modify the code, and I have tested it against Brench to see that it is still correct. I found that extending a generic dataflow solver to include code modifications to be a bit tricky, after having implemented a couple of passes, the refactoring got a bit annoying.

another edit: I also implemented some dead-code elimination using a liveness analysis, this seems to work on bril programs that have dead code, correctness seems to be preserved with brench on the core benchmark programs. Turns out constant folding + dce based on liveness does not beat last week's lvn + trivial dce on the benchmark.

To run my code, you just have to feed in a Bril .json into python3 dataflow.py.

I think I deserve a star this week since I implemented a pretty flexibile dataflow framework that allows for optimizations to code (or not and just extract properties), as well as several analyses.

[sampsyo]

Looks good overall, @tean-lai!

[emmanueljs1]

Code

Summary
I started by implementing the "defined" dataflow analysis that just runs through a CFG and outputs for each block what variables have been defined so far. I then generalized this to a (forward-only) dataflow analysis and instantiated it with a constant propagation analysis. I ended up finding that easier than reaching definitions. (I'm still not sure what the best 'domain' is for this analysis, maybe a variable name along with the line number at which it was defined?) Afterwards I worked on generalizing it to support both directions and instantiated a live variable analysis.

Testing
I tested that my implementation doesn't have exceptions by running it on the benchmark suite and having no exceptions thrown. Separately I wrote a few simple Bril test files to test my implementation and visually confirmed that for the dataflow analyses I'd written the output was what I expected it to be.

Hardest part of task
The hardest part of the task was figuring out how to reverse the dataflow analysis, mostly because I usually get confused with reversing stuff and end up reversing something twice somewhere.

Michelin Star
I think I deserve a Michelin star since I implemented a generic solver that can support multiple analyses. It was fun to actually use OCaml functors for this (although I found myself wishing modules were first-class values).

[sampsyo]

Sounds great!

(I'm still not sure what the best 'domain' is for this analysis, maybe a variable name along with the line number at which it was defined?)

Yeah, broadly speaking, you want some unique identifier for each instruction. What you describe seems fine, as long as "line number" is the offset of the instruction within the function and not, like, the row in the text-format file (because, of course, you can write two different instructions on the same line in the text format).

At the risk of belaboring the point… if you already have some data structure for storing all the instructions in a program, that's a good opportunity to assign unique identifiers to all of them, which you can then use to look up the original instructions using the ID.

[gabizon103]

code

I started out by implementing a reaching definitions dataflow analysis. It followed pretty easily from what we discussed in class, so it was nice and straightforward. The one thing I added was making sure that function parameters reach the first block of the function. I did this in my initialization step. I tested this pass by writing some programs with interesting-ish control flow (some loops and if-elses) and inspecting the output to see if it was correct. One thing that I played around with was finding a nice way to represent the values we want to track between blocks. In English, we defined it as "the set of definitions that reach a specific program point". In code, I ended up representing it as a HashMap<String, HashSet<(usize, usize)>>, so it is a map from variable names to the set of instructions that define that variable. The (usize, usize) tuple is how I tagged instructions; I store my CFG as a list of blocks which each have a list of instructions, so the first field is the block index and the second field is the instruction index inside that block.

After this, I implemented a generic dataflow analysis solver using the worklist algorithm. It looks like this

pub struct AnalysisFramework<ValType>
where
    ValType: Default + Clone + PartialEq,
{
    pub cfg: ControlFlow,
    pub worklist: VecDeque<usize>,
    pub ins: Vec<ValType>,
    pub outs: Vec<ValType>,
}

The worklist function has the signature fn worklist(&mut self, analysis: impl DataFlowAnalysis<ValType>), where DataFlowAnalysis is a trait I defined that requires merge, transfer, and direction functions to be implemented. So now the worklist function can call analysis.merge(...) and analysis.transfer(...) and everything will work.

Once this was implemented, I re-implemented by reaching defs pass to use this framework and checked that it still worked, which it did. Then, to make sure my implementation of the backward direction was correct I implemented a live variable analysis with this framework. I tested both of these using turnt, on all of the bril programs in benchmarks/core.

I didn't run into any major issues, probably the hardest part was reasoning about how to represent values for the reaching defs pass. But I thought this was way easier than implementing LVN, and probably has a greater payoff since this generic type of solver is pretty powerful.

[sampsyo]

Awesome; this all sounds great!

The (usize, usize) tuple is how I tagged instructions; I store my CFG as a list of blocks which each have a list of instructions, so the first field is the block index and the second field is the instruction index inside that block.

This makes sense! In general, an important thing we didn't address in class was how to identify instructions—and this is a perfectly reasonable way to do it.

[neel-patel-1]

For this lesson, I wrote two data flow analyses:

Reaching Definitions
A forward dataflow analysis that tracks all uses and the definitions that reach them: code

Live Variables
Backwards dataflow analysis that reports the liveness of all variables at the entry of each block. Then does a pass through each block to remove dead definitions: code

Verification/Performance
I compared against baseline DCE and LVN to see whether global analyses provide any improvements over the local analyses.
ns/dce.py

Live variable identification (and the subsequent dead code elimination) only reduce executed instructions for three benchmark. LVN already removed most of the redundant instructions it seems.

[sampsyo]

Awesome! Pretty cool that you got optimizations to work on top of these analyses. And it's cool that you were able to observe actual benefits on top of the local optimizations for so many cases. Rad!

[zihan0822]

source

Generic WorkList Algorithm

In rust, I introduced a WorkListAlgo trait,

Trait WorkListAlgo {
  const FOWARD_PASS: bool; // control backward/forward
  type InFlowType;
  type OutFlowType;	// most of time are the same, keep both for flexibility
	
  // required
  fn transfer(block, in[b]) -> out[b];
  fn merge(vector of out[p]) -> in[b];
	
  // provided
  fn execute(...) -> out;
}

Use cases

• Liveness Analysis: backward pass
  merge: union
  transfer: remove KILL set, add used but not defined variables

• Const Propagation: forward pass
  Each variable can be in one of const, non-const, or unknown state.
  merge: union with a twist. A variable can only be set to const if in all possible paths it is marked as const with the same value or temporarily unknown.
  transfer: add new const var (deterministic operation + all arguments marked as const, or declared with const op), update non-const, mark var as unknown if it is not currently contained in in

I extend my previous local dce with both liveness analysis and global const propagation to exploit more dce opportunities in the global context. I tested it on bril/benchmarks/core. Compared to pure local dce in l3, I'm able to see great improvements on the number of dead codes spotted.

• Initialization Analysis: forward pass
  In bril, I interpret uninitialized variable as undeclared. I try to find variables that are computed from undeclared variable and generate some error messages. Somewhat similar to Const Prop, each variable can be init, uninit or unknown
  merge: union with a twist. A variable is considered to be const if in all possible paths it is marked as init or temporarily unknown
  transfer: add new initialized var (all arguments marked as init, or declared with const operation), update uninit/unknown info

Comments on the last two examples:

1. Both of them can also be equivalently implemented with intersection being the merge function and initial state of in = {all variables} (except for the entry node). I did not end up doing that, because, for example in const propagation, besides identifying all the const variables, I also want compute those const values on the fly. I need to make sure variable currently marked as const has value that actually makes sense.
2. Why need three states instead of two (const vs. T, init vs. T)? Because we are starting with in = empty set, I am imagining the case where if we assume that variable not found in in to be T and there is a cycle, we may never be able to recover from that.

Conclusion

I think the hardest part in my implementation is to handle multiple incoming paths in which there might be conflict regarding the current state of variable. Overall, I think I deserve a Michelin Star because I implemented a generic solver and several analyses. I am happy to see the improvement on core benchmarks compared to l3.

AI usage: python plotting script is generated by o3-mini with zero modification

[sampsyo]

Awesome! Super cool that the optimizations built on these analyses seemed to work pretty well across the board. And thanks for this interesting discussion about how to set up the lattice for each analysis, especially in the presence of "undefined" or "unknown" states.

[gerardogtn]

CODE

Summary

I implemented a generic data flow algorithm for both expressions and constant propagation, written in Kotlin and that produced a json file containing the results of the algorithm. I tested it out with some of the examples that we covered in class as well as benchmarks in the bril repo and smaller examples in bril.

How does it work?

In class we briefly discussed how the dataflow algorithm typically uses a worklist, but could be described by a workset instead (provided we meet the monotonicity requirements to guarantee termination) I took this approach to heart and modeled the algorithm with a workset instead (although i use a TreeSet and process blocks in order of appearance (i.e. from 0 to n in the forwards direction and from n - 1 to 0 in he backwards direction). To establish a generic version of dataflow, I split the algorithm into a strategy and an implementation; where the strategy simply defines the direction, initial value, transfer function and merge function. To allow for ease of implementation of new dataflow strategies, I provide utilities for BigUnion/BigIntersaction that support both Maps and Sets to work out of the box. With this approach in place, I implemented both reaching definitions and constant propagation and I only had to create a different strategy instance, and specify the type of the output without having to make any modifications to the underlying algorithm.

Hardest part?

The hardest part was to set up the right abstractions for supporting generic strategies in the dataflow algorithm, the use of Kotlin's reified generic types allowed me to get default support for BigUnion/BigIntersection without having to rely on custom implementations of these functions for each strategy. But this felt like a scenario where I was fighting the language to get things to work properly

⭐❓

I'd give the results of the task a michelin star.

[sampsyo]

Awesome. Overall, nice work figuring out the set of basic utilities you needed to make the implementation of various analyses easier.

[ngernest]

Group (@ngernest, @katherinewu312, @samuelbreckenridge)

Code
(Katherine: generic solver, Sam: live variables, Ernest: constant propagation)

As a first step we implemented a data flow analysis to identify live variables. Setting up a skeleton of the solver
was pretty straightforward, although we did have to be a bit careful about setting things up consistently to run
backwards instead of forwards. The trickiest part of the live variables analysis was probably finding the appropriate
transfer function, it was helpful to switch to thinking about the set operations as per instruction rather than per
basic block as discussed in class. To test our implementation we chose a selection of Bril tests and benchmarks and
compared the output of our data analysis to a manual tracking of live variables. This certainly revealed bugs that
we were able to fix (e.g. Python sets not getting updated because the union method is not in place) but overall it
was quite tricky to determine live variables manually, especially for complex control flows. This somewhat limits
our ability to gain confidence in our implementation from these more complex tests so we are more reliant on simple
unit tests that can be manually verified.

For constant propagation, the trickiest part was getting the merge function right.
From our discussion in class, we know that the merge function for constant propagation
should take the "union" of all dictionaries within a list of dicts (where each dict maps a variable name to its constant value, or None if it is unknown). Initially, we tried using Python's default dictionary union operator d1 | d2. However, we found out this doesn't work when the same key var is defined in both dicts and d1[var] != d2[var] -- the Python | operator automatically picks d2[var] in this situation, which isn't what we want. As a result, we had to hand-roll our own dictionary union function so that var is always mapped to None in the case above. To gain confidence in our constant propagation implementation, we used property-based random testing (using Python's Hypothesis library) to check that our implementation satisfies various equational properties (e.g. the output dict from the merge function should preserve all keys from the argument dicts). We also set up separate Turnt environments for our different analyses and manually compared our results to the example dataflow tests in the Bril repo to make sure our analysis works for a selection of Bril programs.

We also decided to implement a generic solver that supports multiple analyses. Our code follows the high-level
pseudocode that was mentioned in the lesson. We tried to think of a way to write both the forward and backward data
flow passes as one piece of code, instead of having them as two separate problems. Doing so allowed us to reuse
several variables, making our code less verbose, but this did mean that we were using block_in to represent
block_out and vice versa for the backward pass. Although this did not introduce any technical problems, it did lead
to some confusion in reading the code itself at times. Additionally, we made sure to define a dataclass called
Analysis to distinguish between forward/backward passes, initial values, merge functions, and transfer functions.
Thus, specifying a new data flow analysis simply amounted to assigning values to these variables forward, init,
merge, and transfer. We tested our generic solver using Turnt, using the Bril examples located in the test directory.
We tested the generic solver by setting up Turnt environments that ran the generic solver configured for live
variables / constant propagation and checking that these runs matched the outputs of the respective standalone
implementations. We think we deserve a Michelin star because we implemented multiple data flow analyses and tested
these thoroughly using Turnt before abstracting both implementations into a generic solver while verifying that
correctness was maintained.

[sampsyo]

Awesome; nice work, y'all!

overall it
was quite tricky to determine live variables manually, especially for complex control flows. This somewhat limits
our ability to gain confidence in our implementation from these more complex tests so we are more reliant on simple
unit tests that can be manually verified.

Yeah, this is certainly a thing that most people will encounter: how do you get a "test oracle" for the results of a dataflow analysis? It's pretty tedious for a human to provide this by hand. I think the best answer to this conundrum in the "real world" is that you build some kind of program transformation that consumes the computed dataflow facts and check whether that does the right thing. But the downsides there are also obvious (e.g., when something goes wrong, it can be hard to trace back to the analysis).

To gain confidence in our constant propagation implementation, we used property-based random testing (using Python's Hypothesis library) to check that our implementation satisfies various equational properties (e.g. the output dict from the merge function should preserve all keys from the argument dicts).

And this is certainly another way! That is, in general: if there are good ways to unit-test individual pieces of your analysis, you can gain some kind of confidence that the overall analysis might be correct.

[mb64]

Link to code

For this task, I implemented the constant propagation analysis, because I think it's a very cool data flow analysis. I had hoped to integrate it with my LVN optimization, using it to populate the value table at the head of each basic block to actually do the optimization, but my LVN code doesn't do constant folding already and I didn't have much time this week so I didn't do it.

I did extract a general-purpose solver, which only does forward analyses: to use it you create a type for your analysis and make it an instance of the Dataflow typeclass, and then you can do forwardAnalysis with it.

Since I didn't have much time this week, I just tested it on the example programs in examples/test/df/*.bril, and looked over the outputs manually.

The analysis works and uses a generic solver, but because of my sketchy testing and basic setup, I think this is close to bare minimum to meet Michelin star quality.

[sampsyo]

Looks good! Nice work. And totally defensible to keep it simple when you have less time. 😃

[mse63]

Code

For my task, I implemented Reaching definition analysis, because it seemed interesting as a way to remove deadcode that wouldn't be trivial. Our previous implementations would not necessarily have removed statements that get overwritten in every other basic block because LVN only looks within a basic block, but here we can see that if a statement has no reaching definitions, it can be removed.

I only implemented Reading Definition analysis, and didn't go about making a general-purpose solver. I would have liked to create an interface with functions to be overridden, but I've had a tougher workload this week and just couldn't find the time.

Most of the code I've written for previous assignments has been in Python and treating programs like their json dictionary implementations, which isn't very strongly typed and it's starting to get to the point where I'm paying the price for not having implemented better data structures to represent bril programs. I'm planning to just rewrite it all with nicer data structures in Rust over February break.

As for testing, I wrote a few simple test bril programs and had the program print the reaching definitions at the end of each basic block. I then manually went through and checked them. Unfortunately, it's not clear what automated tests I could implement, like I did for the LVN. Even if I were to modify the brill interpreter to check the definitions at every instruction are always in the set expected reaching definitions, that still wouldn't build much more confidence in my implementation's correctness (For example, a Reaching Definitions implementations that just says all definitions always reach all instructions would pass that test.)

I believe this work is only barely worth a Michelin star - I did, in fact, complete the task assigned, but I didn't go any further with it, such as building a general purpose solver or adding it to my LVN compiler optimizations from last week's task.

[sampsyo]

Looks good; sounds like a good effort to me! FWIW, I think the next step might have been to try actually optimizing your code in the way you envisioned to see if it can beat your local optimizations.

I'm planning to just rewrite it all with nicer data structures in Rust over February break.

Sounds like a fun way to spend a long weekend. 🦀

[lisarli]

In collaboration with @bryantpark04 and @dhan0779
source

Defined Variables: We started by implementing a very simple defined variables analysis to track the set of variables which had been assigned a value. This basic implementation helped us become familiar with the idea of the merge and transfer functions, and we used this analysis to confirm our generic solver was functioning as expected later.

Generic Solver: We created a generic solver (with some wrangling of C++ types) that implements the worklist algorithm and can be parameterized on the initial value for each block, merge function, transfer function, and direction of the analysis (forward or backward). It was pretty straightforward to write this solver by extracting the relevant parts from the initial defined variables implementation, and it was pleasantly simple to add more analyses once we had this framework set up.

Reaching Definitions: We implemented reaching definitions by keeping a map of variable names to sets of definitions, where a definition is a unique identifier of some instruction (denoted <block_number>.<line_number>). We followed the merge and transfer definitions in class (modified slightly for the map representation); the map made it particularly easy to kill old definitions and replace them with a new one.

Live Variables: The live variables analysis gave us a chance to explore a backwards pass analysis. This was achieved by swapping the predecessor and successor maps in the CFG, then running the worklist algorithm as usual. We use a set union of live variable names for the merge function, and for the transfer function, we step over the instructions in the block in reverse while removing their destinations and adding their uses.

Constant Propagation: This was the most involved implementation since we had to do a lot of workarounds with the types in C++. In particular, we set up a variant type for representing Bril values (ints, floats, booleans). Our environment type was simply a mapping from variable names to optional Bril values, where a std::nullopt represented values that were known to be non-const (as opposed to unknown/uninitialized). Our merge function copies over var -> val mappings from the preds, and overwrites them with a std::nullopt if the values conflict with each other. Our transfer function steps through the instructions and either overwrites destination variables with std::nullopt if they depend on an unknown/non-const variable or updates them in the environment with the correct value if all of their args are also const. We also had to think carefully about updates to variables within loop bodies, as our initial implementation incorrectly propagated constants even when the variables were overwritten to a non-constant result in a loop.

Testing: For testing, we created a small test script to diff outputs from the .bril files in the df_tests directory. You can pass in the type of analysis into the script (ex. ./test.sh live) and it will run the specific dataflow analysis on the respective bril files and match with the expected output. Doing this helped us catch a few small bugs in our early implementations. We also ran other test cases such as dealing with multiple functions with more basic blocks and more complex control flow to make sure that the outputs were realistic, and we used Turnt to compare the outputs of our defined variables analysis before and after implementing the generic solver to check our solver.

Conclusions: After implementing the generic solver, it was straightforward to add new analyses. The most involved analysis to implement was constant propagation, as there were more edge cases to consider and many type conversions to perform. Overall, this task was pretty fun to implement, and we believe our work deserves a Michelin star since we implemented the generic solver and three different analyses.

[sampsyo]

Awesome; this all sounds great! Nice work, y'all.

About this one:

Reaching Definitions: We implemented reaching definitions by keeping a map of variable names to sets of definitions, where a definition is a unique identifier of some instruction (denoted <block_number>.<line_number>). We followed the merge and transfer definitions in class (modified slightly for the map representation); the map made it particularly easy to kill old definitions and replace them with a new one.

Sounds cool! In general, figuring out a way to identify instructions uniquely so you can find/modify them later is a minor engineering challenge in all this. I assume that line_number was the offset of the instruction within the basic block?

[lisarli]

Yep, we just used the index of the instruction in the list!

[parthsarkar17]

Code

Here are my reaching analysis template and my generic solver implementation.

Summary

For this task, I implemented a generic worklist-algorithm-based solver, wrote a "template" for reaching definitions to toss into that solver, and wrote a pretty printing function for manual testing. Also, while I didn't get it to work fully by the deadline, I started a global constant propagation analysis.

How it works

OCaml's module, functor, and module type (i.e. signature) separation came in handy for my implementation. Since I started this task earlier and had a bit more time, I started off by abstracting the worklist algorithm from the get-go. I implemented a signature that exposed the type t (e.g. set of reaching defs), transfer function, merge function, and init function we discussed in class (i.e. a "template" interface), and I wrote a functor that takes in an implementation for this interface and exposes the construct_basic_blocks, construct_cfg, and worklist functions. This functor largely operates on the globally-recognized indices I gave each basic block and each instruction. I gave an index 1..n to the basic blocks, and, within a block, I gave the indices 1..m to each instruction. This means that the final instruction can be indexed as (n, m) and the ith block is indexed as i. My construct_cfg function returned two data structures; each mapped a basic block index i to a list of basic block indices, but the first represented the predecessors of i and the second represented the successors of i. The worklist algorithm followed from there; I used these preds/succs structures to index into a global map of basic blocks returned by construct_basic_blocks. One thing I'm proud of is not using any imperative code... definitely my personal preference 🐫.

As for the Reaching Analysis implementation, I did not encounter any huge issues once I had gotten down the abstract module type. It's a good thing I implemented globally-recognized indices (i,j) for each instruction in a function; my implementation for what a "definition" was mapped this 2d index to the variable being written to. Then, my type t in the implementation of the signature just became a set of these (i, j, var) 3-tuples. I implemented a dummy basic block at the beginning of each function (indexed with 0); the initial out flow from this block into the block indexed with 1 was just the arguments to the function. I treated each of these arguments as definitions, with their concrete type being of the form (0, i, var). Finally, I combined different definitions of the same variable in my pretty printing helper, consolidate_reaching_defs. This was so that my output could be more aligned with what was displayed in the current bril/examples/test/df/*.defined.out. files.

Testing

My testing unfortunately wasn't as statistically rigorous as L3 because I didn't actually change any code, and therefore couldn't pin down any performance improvements. But, I manually verified the in and out flows for each basic block for each function within the following files:

• bril/benchmarks/mem/eight-queens.bril
• bril/benchmarks/mem/mat-mul.bril
• bril/examples/test/df/*.bril
  Of course, I chose the examples because we worked with them in class. They provided good mental images while I was writing my code. Once I was done, I also checked against the respective .defined.out files. Next, I chose the mem benchmarks because they have a lot of loops and had some funky CFGs. My analysis works with all of these programs.

Hardest part

I think the hardest part was bringing the abstract math down into code. For me, it was helpful to read the additional readings and learn a bit more on lattices. I definitely saw the overlap between the abstract operations on powerset-lattice-members (i.e. join) mentioned in the textbook and the "template" we talked about in class. I particularly enjoyed how lattice members, applied to our dataflow analysis, seem to articulate how "confident" we are in our analysis over a set of variables or something. For reaching definitions, we are confident that a definition reaches if it exists in any path. But, the sign analysis example was an instance where there are varying levels of uncertainty that can propagate throughout the program.

Eventually, I sort of gave up on trying to map the abstract definitions into my module type signature. At that point, it became clear to me the minimum of what I would need for reaching definitions and potentially constant propagation, so I went ahead and implemented the signature as such. I think I'm missing some stuff, like top and bottom functions, but I'd need to sit down and think about it more. I'm proud that I understand the high-level idea, at least.

Star

I would give myself a star

[sampsyo]

Awesome; very nice work!!

This functor largely operates on the globally-recognized indices I gave each basic block and each instruction. I gave an index 1..n to the basic blocks, and, within a block, I gave the indices 1..m to each instruction. This means that the final instruction can be indexed as (n, m) and the ith block is indexed as i.

Great! Very nice solution to the engineering problem of needing to uniquely identify instructions within a program.

I particularly enjoyed how lattice members, applied to our dataflow analysis, seem to articulate how "confident" we are in our analysis over a set of variables or something.

Yeah, that's a good point. Per a discussion in class, this kind of "degree of confidence" type of reasoning is very much a core aesthetic of abstract interpretation as well.

[devv64]

df code

I started with implementing the pseudocode, which meant just creating the generic solver. I think this approach isn't too bad, as the pseudocode for the dataflow algorithm is pretty straightforward. My biggest problem with this assignment stemmed from my earlier implementation of the cfg algorithms. It turns out that I made several decisions during that assignment that made this one much more difficult. I spent a significant amount of time going back and fixing that. I had to adjust the way I was using some data structures to make the data flow algorithm possible. I also felt that my understanding was not completely clear when I started this implementation, which definitely also led to many extra hours spent on this. This definitely helped me gain a better understanding on cfg and dataflow.

Once I got all the cfg stuff down, I added support for constant propagation. I tested by copying the fmt function from the example implementation provided and comparing my outputs with the example df outputs.

I think I deserve a Michelin star because I met the expectations of the assignment!

[sampsyo]

It turns out that I made several decisions during that assignment that made this one much more difficult. I spent a significant amount of time going back and fixing that.

Any chance you could elaborate on exactly what those decisions were? It seems useful to know what about your earlier data structures painted you into a corner.

I also felt that my understanding was not completely clear when I started this implementation

Similarly: understanding of what? What enlightenments did you experience during the implementation?

[devv64]

The most blaring difference was that my previous implementation was creating cfg's for every function rather than just the main function. This was giving me some issues when trying to figure out what was going on. My cfg also just stored labels rather than the actual blocks, so I had to create a mapping between my blocks data structure and my actual cfg. Through this exercise, I was able to essentially bring my code up to speed with what I already understood about the cfg but lost in details during implementation.

[sampsyo]

That would do it! Thanks for elaborating.

[ethanuppal]

• Code: https://github.com/ethanuppal/cs6120/tree/main/lesson4/dataflow
• CI passing: https://github.com/ethanuppal/cs6120/actions/runs/13322650730/job/37209946152

I first created a simple trait extension for bril_rs::Instruction to give me
kill/gen/etc sets.

Then, I implemented a general solver for dataflow analysis in Rust, and
specifically implemented and tested:

• Reaching definitions
• Live variables

As usual, these are nicely
snafu'd CLI apps.

I handchecked and tested with turnt the examples in examples/test/df with both of the analyses.

For the dataflow solver, I looked at some CMU slides which said to do postorder and reverse-postorder basic block orderings (generalizing the topological sort strategy Professor Sampson proposed in class).

To test reaching definitions, I manually checked that every definition the analysis claimed to be reaching actually was by BFSing from each block + claimed definition, running it on all the core benchmarks (see check.py). Notably, this is not sufficient for a correct reaching definitions analysis, only necessary. However, I have good reason for it to be correct based on the simplicity of the code and the fact that I more rigorously confirmed the correctness of live variable analysis (the two differ only in their transfer function and traversal direction).

To test live variables, I matched my output with that of Professor Sampson's df.py. I ran it only on all core benchmarks with a few excluded because my CFG builder and Professor Sampson's differ on the definition of a basic block. Thus, to avoid extensive manual pruning, I only used the core benchmarks instead of all the benchmarks. Oh, I also ran it on the examples/test/df/ programs.

For reference, here's the relevant CI code:

  - name: Test reaching definitions analysis
    run: |
      cd lesson4/dataflow
      python3 check.py def ../../bril/benchmarks/**/*.bril ../../bril/examples/test/df/*.bril
  - name: Test live variables analysis
    run: |
      cd lesson4/dataflow
      python3 match_outputs.py \
        "python3 ../../bril/examples/df.py live | grep '  in:'" \
        "cargo run --package dataflow --quiet -- --analysis live | grep in:" \
        ../../bril/benchmarks/core/*.bril ../../bril/examples/test/df/*.bril \
        --exclude is-decreasing.bril --exclude recfact.bril --exclude relative-primes.bril # differ on definition of basic block
  - name: Snapshot test analyses on examples/test/df/ programs
    run: |
      cd lesson4/dataflow
      cd turnt && turnt df_copied_from_bril/*.bril

I believe I deserve a Michelin star because I implemented the assigned tasks and tested my implementations.

Total time spent: 6 hours

In other news

• I've been working on making bril-frontend a lossless parser so I can satiate my perfectionism with a brilfmt. This won't be useful at all, but I am OCD about it.
• Haven't pushed this work yet, but going to implement basic Hindley-Milner in bril-frontend so the memory extension can be supported fully.

[sampsyo]

Awesome! Pretty cool idea here to use a graph search (BFS) as a necessary-but-insufficient condition for the correctness of reaching definitions. Getting test oracles for these things can be hard, so even a partial one is way better than nothing.

And thank you for continuing to track your time on these tasks!! 🎉

[ethanuppal]

Yes, the oracle isn't the greatest. I couldn't figure out a better solution than either reimplementing the analysis from scratch or literally implementing meet-over-all-paths, which I didn't anticipate being able to terminate in reasonable time over all core benchmarks (although I could be wrong). I'm interested if there's any reasonable ways to check correctness of global analyses --- I didn't look them up during the assignment for academic integrity reasons, obviously --- where I define reasonable to be "a set of sufficient conditions that can be checked in polynomial time which, when all hold, constitute a necessary condition"

[Jonahcb]

Code

I implemented defined variables. I didn't find it too difficult, but I tried to keep the code in the form of the generic solver so I could easily implement one when I have a chance. I enjoyed the process. I took it easy because I have a lot of other programming for other classes this week. But I'm hoping to implement a few more soon and build up my python file. I tested it using some of the test files in the folder and checked by hand. I need to figure out a better way to test it.

[sampsyo]

OK, taking it easy is just fine! It would still be interesting to know a little more detail about what, if anything, presented a challenge in your implementation or validation. Or maybe the defined-variables analysis was so simple that there was nothing really hard about it?

[arnavm30]

Code

I implemented the Reaching Definitions and Live Variables data flow analyses. I first implemented Reaching Definitions, which involved rewriting the cfg from lesson 2 to be a nested dictionary with keys for the predecessors and successors of each basic block. I stored definitions as a tuple of the variable, the block the definition is in, and the offset within the block. After implementing Reaching Definitions and checking the output matched what I expected on the tests in test/df, I implemented a more generic solver. I then adapted Reaching Definitions to the generic solver, and then also implemented Live Variables, to ensure backward passes worked and that the framework was general enough.

When adapting Reaching Definitions to the generic solver, I verified the outputs didn't change, using brench for snapshot testing. When implementing Live Variables, there were luckily already expected outputs saved, so I could just compare directly against it if I matched the output format exactly. For Live Variables, I also manually inspected the output when ran on my benchmark from lesson 2; however, for Reaching Definitions, the output was far too large even on small inputs to carefully manually verify. I ended up manually inspecting on some smaller benchmarks with iterative behavior like core/reverse.bril and core/gcd.bril.

The hardest part was probably writing the reverse pass properly in the generic solver. In particular, realizing that the handling of arguments is different took me some time. Also, the different set operators in Python were annoying to use, particularly when tuples would unintentionally get unpacked.

[sampsyo]

Sounds good overall; nice work!

[aw578]

code

Summary
I started off by implementing the variable definition dataflow analysis using hardcoded functions. I then generalized this to support constant propagation, resulting in an algorithm that supports generalized forward dataflow analysis.

Testing
I tested my code by running it on the examples and a few benchmarks to confirm that it ran without exceptions, then manually examining the results to confirm that they were correct.

Hardest part of task
The hardest part of the task was probably just manually checking the test cases.

[sampsyo]

(I'm finally getting around to grading late submissions for this task; FYI you now have partial credit.)

[KabirSamsi]

Partner: Noah Schiff (@noschiff)

Code

Overview

This unfortunately is quite late, for which we both apologize. However, we had a great time first devising an idea for more specific data flow, and then generalizing it to a more multi-purpose system in TypeScript. We began with a specific data flow analysis for Live Variable Analysis, before generalizing it and then utilizing it to analyze Reachable Definitions and Constant Propagation.

With more time, it would have been wonderful to explore extending this further for the assignment; that having been said, we fully plan to try more forms of analysis on our own.

Implementation

We implemented our algorithm in TypeScript, designing custom types for blocks, labeled block collections and the control-flow graph.

Our first step was to improve on the basic blocking & CFG-generation algorithms we had explored in L2; we then went about actually using these for Dataflow analysis. We decided to use the video tutorial and our own reasoning sense to implement Live Variable Analysis; we slightly tweaked the general 'recipe' outlined in the video in developing our transfer function in order to implement this.

We first began by setting up a function lva that would directly perform Live Variable Analysis. Using the string handles to represent destination variables, we implemented the merge function as a simple set union; then did a line-by-line upwards traversal for the transfer function. That is to say, we took the more mathematical set-difference implementation and instead performed an upward traversal to update the resultant set of variables with each new definition.

We then were able to factor out the relevant code to create the more general-purpose worklisting algorithm, which we were then able to extend to a few more forms. We also factored out a data type for different forms of analysis.

Subsequently, we implemented the Reachable Definitions analysis using a custom-made record type for Bril instructions, and constant propagation with numbers and booleans.

Constant Propagation Notes
This was our only dataflow analysis that we came up with by ourselves. Our intuition was that the data representation should map handles (variables) to numbers, representing their constants over time. We later extended this to booleans as well.

We further reasoned that set union would not make sense here, since if two incoming blocks have different values on the same variable, it can no longer logically be treated as a constant (as we cannot guarantee which value it will take coming into the basic block). A more logical interpretation, thus, was to tweak the set union operator, but now working over mappings – such that all mappings from variables to constants were included, except if a certain value mapped to different constants from different input blocks. Thus, this extracts only the set of variable $\mapsto$ constant bindings that would legitimately be kept the same across any possible CFG pathway into the block.

The transfer function was also straightforward. Reusing Kabir's constant propagation mapping system from L3, we were able to describe our transfer algorithm as such:

out = in
for each new instruction
   if value is a constant, or an operator is a constant-prop operator and all arguments are defined within out
      add element with its latest constant value to out
return out

Implementing this then gave us our third data flow analysis!

Testing

It was a bit harder to use a general-purpose testing framework like Brench here the way we were able to with L3 (LVN), since our code was not directly modifying Bril source files, but rather outputting results of analysis using the data structures we had created. We began by creating a straightforward script to run with bril programs, and then comparing outputs for each result. We later extended this to working with turnt directly and hand-testing file by file.

Takeaways

It is regrettable that we could not spend more time on this project, as it was incredibly fun and really brought a nice mix of math/algo/compilers all together. We are looking forward to more Dataflow work in the future!

But for the time this took and the lateness, we do feel that this would deserve a star, as we went above the bounds for basic implementation and came up with both a general-purpose implementation of the algorithm and an extension to constant-propagation.

[sampsyo]

(I'm finally getting around to grading late submissions for this task.) This all sounds really great, though! Nice work getting optimizations to actually work here. :)

[InnovativeInventor]

I implemented a sign dataflow analysis, using a generalized forwards-only worklist implementation. ¹

Filling out the add/sub/mul lookup tables was quite tedious and potentially error-prone, so I switched from writing out the $\mathbb{P}( \{1,2,3\} ) \times \mathbb{P}( \{1,2,3 \})$ cases to exploit some symmetries, resulting in a much more manageable 6 (for add and mul) and 9 cases (for sub) respectively.

Correctness

I tested my program on my submitted BBS benchmark. ² I selected this benchmark because:

1. I am familiar with the program, and
2. it contains an interesting and common case for sign analysis (a counter in a for loop).

In particular, I was looking and confirmed that the following is true:

1. In the loop start basic block, the start variable has sign 0.
2. In the loop body, branch, and end basic blocks, the body variable has signs 0 or +.
   as well as program termination.

I am not fully convinced of my implementation's correctness. However, I believe that this program exercises some of the interesting cases of a sign dataflow analysis.

Footnotes

1. https://github.com/InnovativeInventor/bril/blob/lesson-4/lessons/dataflow.py ↩

2. https://github.com/sampsyo/bril/blob/e81593409fe3395ad87aad9117b6d72e012e2362/benchmarks/core/bbs.bril ↩

[sampsyo]

(I'm finally getting around to grading late submissions for this task.) This all sounds good—and thanks for being honest about not being fully sure about the correctness here. :)

[calciiium]

code
I implemented the live analysis for data flow analysis. Instead of directing running the live analysis algorithm, I wrote the generic worklist algorithm for both forward and backward direction first, and then adds live analysis as parameters into the worklist algorithm.

I didn't run brench or other large scaled tests for this task, because I couldn't think of a straightforward way to evaluate the correctness of live analysis results. Instead, I gathered some small tests from benchmark and wrote some small test cases on my own, and manually check the correctness of the live analysis result. They are all correct.

The hardest part of this task is to figure out the correct way to generalize the worklist algorithm, so that different data structures can be properly handled as node in this worklist algorithm.

[sampsyo]

Looks OK at a high level. May I ask what was going on with this docstring?
https://github.com/calciiium/grad-compiler/blob/fc33bb92caaf9c0dbb002651bd132cb699f0c820/l4/impl.py#L135-L151