Lesson 2: Representing Programs

[sampsyo]

When you finish your tasks for Lesson 2, post here! Include a link here to your benchmark PR and your new Bril tool. Explain what you did and mention anything you found interesting about it.

[SerenaYZhang]

Source code URL

Benchmark Pull Request
I created a new benchmark for sorting an array of 5 integers in ascending order using the insertion sort algorithm. This benchmark is heavily inspired by the existing benchmark bubblesort by Jiajie Li, adopting the functions pack and print_array for easier array manipulation. The size of the array that can be sorted is currently fixed at 5 integers, but this length could be easily edited to be smaller or larger.

I tested my sorting algorithm by editing # ARGS: 5 22 81 7 35 60 with different parameters and making sure that the end result was the correct sorted order.

The hardest part of this task was writing code in bril. Although the syntax is well documented and there are many other benchmarks to reference, the language style feels like a different way of thinking compared to the programming languages I'm most familiar with.

Analyze Bril Programs
I wrote a simple program that prints out what arithmetic operation is being called ("adding", "subtracting", "multiplying", or "dividing"). To validate my program, I wrote my own test cases with different arithmetic operation scenarios and used turnt to check that the output matched with the expectation.

One thing I found annoying was that if there are issues in the program, turnt would only show that the program failed to run on the test cases with error message # exit code: 1 with no additional information. This means that debugging often required me to run the program on the test cases without using turnt, which feels like an extra step that could be streamlined.

CFG
I implemented the CFG algorithm derived in class using Python. One design choice I made was to use numerical indices to identify blocks, and I used a dictionary to map a label to the numerical index of its block.

I again tested my CFG implementation using turnt, creating test cases from the 3 example bril code we saw in class. To check that the blocks are correctly formed, I printed out all of the blocks and the instructions for each block to make sure that the number of blocks is accurate and each one holds the correct order of instructions. To check that I find the correct CFG, I print out each block's successors. Since we went over the 3 examples in class and marked out the blocks and CFG for each, I manually inspected the print statements for each test case and made sure they matched our results.

I believe I deserve a Michelin star for familiarizing myself with bril tools and applying what we learned in class in implementing CFG and adding my own design choices to it.

[jeffreyqdd]

1. Benchmark PR: lesson2 feat: bechmark: add montecarlo simulation to calculate pi bril#426
2. Bril tool and CFG Constructor https://github.com/jeffreyqdd/rust_bril (file)

Benchmark

My benchmark was replicating the very standard montecarlo simulation for calculating pi. Because bril is very minimal, I had to write from scratch the following three functions

1. xor, shift left, shift right
2. random number generator using xor (see xor shift)
3. A "static_cast" from int to float, opposed to the "bit cast" provided by brilirs.

The static_cast was the most interesting part of the benchmark because it presented me with an important design decision. The most correct approach is to open up a PR to add static_cast to the interpreter in addition to bitcast. However, I opted to read the Wikipedia page on double-precision IEEE 754 floats and attempted to implement it in pure bril. The reason I did this was two-fold. Firstly, it would make the code more open to optimizations, and second, I thought it would be fun.

What I noticed: The implementation process allowed me to internalize the language and helped me devise my own conventions for coding bril. For example,
v: int = add const 2 const 3; is not valid syntax, so I ended up doing:

literal_2: int = const 2;
literal_3: int = const 3;
v: int = add literal_2 literal_3;

Tool

My tool inserts a print statement before each br and jmp and brings the number of possible labels the instruction will jump to (so 2 for br and 1 for jmp). Because this tool "mutates" the code, I needed a way to parse in BRIL, modify it, and export to an output file. Using the JSON representation was easiest because I could easily locate code blocks due to the structured data.

Testing

Testing was done using a straightforward turnt environment. To run my turnt test cases, use make test-transform, and to run unit tests, use make test. My unit tests consist of end-to-end tests, parsing tests, and CFG construction tests. My turnt tests would run my transform logic, take the resulting program, execute it, and then check if the output matches the corresponding *.out file. Writing the code in Rust also gives me the peace of mind that there are no memory lifetime bugs in my code.

Conclusion

The most challenging part of the task was writing bril. As mentioned, bril is very minimal, and a lot of my time was spent on re-inventing the wheel. Before starting the task, I had the impression that simple xor or shift_left or shift_right would be provided, since computers are really good at bit manipulation tasks. I quickly realized that was not the case. Implementing xor with only +,-,*, and / proved to be an enjoyable challenge.

I would be deserving of a Michelin star because of the complex code I needed to write for my montecarlo benchmark, as well as the time spent implementing and testing both the CFG and code transform tool I built.

[magg1egao]

Source Code: https://github.com/magg1egao/cs6120_tasks/tree/main/task_2

Benchmark:
Pull Request: sampsyo/bril#431
My benchmark involved finding the greatest prime factor of a number. This involved two primary functions: @isprime and @greatest_prime_factor. @isprime tests to see if an integer is a prime number by trial division. @greatest_prime_factor repeatedly divides out factors of its input integer n and keeps track of the largest one. The @main function prints the greatest prime factor of its input. This benchmark contains multiple nested loops, br and jmp chains, and function calls.

I manually tested this benchmark with a variety of different numbers, making sure the final output was correct. The sample input listed, #ARGS: 13195, also outputs the proper answer of 29. I also tried prime inputs like 13 (result = 13) and composite inputs like 100 (result = 5) to check the algorithm.

Tool:
The tool I created parses the Bril JSON program and counts the number of instructions with the opcode dest. In the end, it prints the total count. I also wrote some tiny test programs for this tool. This includes a straight-line program with const and add instructions. My tool reported 3 destinations, which matches v0, v1, and v2. The second test was a branching program with jmp and br. The tool correctly counted 2 destinations: v0 from the const, and v1 from the add.

CFG:
For my control flow graph algorithm, I first formed all the basic blocks. I found the “leaders” of a block by taking the function entry (index 0), all the labels, the targets of every br and jmp, and the instruction immediately after any terminator. I also properly mapped a given name to each block. Afterwards, I built the control-flow graph by adding edges according to the last instruction of each block.

I tested this with turnt on a variety of different test cases. This include one block, multi-return, loop, and if-else code.

Hardest Part:
The hardest part was getting the block formation rules exactly right for the CFG. I understood what to do at a high level, but the details were a bit more finicky. For example, consistently identifying "leaders", keeping track of the labels each block is mapped to, and making sure everything was printed out properly. Debugging this required walking through small hand-made examples and checking the printed blocks against what I expected. Writing the benchmark was also tricky because as was my first time writing full out Bril with nested loops and branches, but testing with known inputs helped confirm the logic.

Self Assessment:
I believe I deserve one Michelin star. I delivered three concrete pieces with solid, clean implementation quality with a variety of test cases to ensure it was all correct and reliable. Throughout this whole process I also learned a lot about the nitty-gritty details of the syntax of Bril, how to properly run and test programs and tools within its ecosystem, etc.

[maheshejs]

Code: https://github.com/maheshejs/cs6120pr
Benchmark PR: sampsyo/bril#428

Benchmark
My benchmark dayofweek computes the day of the week for a given date (year, month, day) as an integer (1 = Monday, ..., 7 = Sunday). The algorithm starts from an "anchor date" (a known date, such as January 1, 1700, which was a Thursday) and calculates the number of days between that date and the target date, then uses arithmetic modulo 7 to determine the day of the week (details here: https://en.wikipedia.org/wiki/Determination_of_the_day_of_the_week). I implemented it in TypeScript and compiled it to Bril using ts2bril. Since ts2bril lacks some constructs (like the modulo operation heavily used in this benchmark), I implemented a custom modulo function using division, multiplication, and subtraction. I tested the benchmark using turnt on several dates, including the Unix epoch (January 1, 1970 – Thursday), this year’s calendar, and my birthday :). The hardest part was simplifying the TypeScript code enough to satisfy ts2bril. Through this, I gained a deeper understanding of Bril programs and the subset of TypeScript that translates successfully.

Analyzing Bril Programs
I wrote a Racket program that parses a Bril JSON program and outputs a histogram of instructions. This provides quick statistics to analyze Bril programs. The program iterates over each function, counts how many times each instruction occurs (ignoring labels), and outputs the counts alphabetically. I tested it on all Bril core benchmarks. The most challenging part was parsing the JSON and implementing the counting functionally with a running accumulator.

Basic Blocks and CFG
I wrote a Racket program that parses Bril JSON programs to construct basic blocks (BBs) and a control flow graph (CFG), then outputs both textual representations and a Graphviz .dot graph. BBs are formed by iterating through instructions or labels of a function: labels start a new block if the current block contains a mix of label and instructions; otherwise, they are appended. Instructions are added to the current block, and terminator instructions (br, jmp, ret) start a new BB. BBs are stored in a hash table keyed by a block ID. The CFG is a directed graph where edges are added from the last instruction of each BB: branches connect to their targets, and non-branches connect to the next sequential BB if it exists.

While testing on the dayofweek benchmark, I noticed that the existing Bril examples treat each label as starting a new block, which creates unnecessary BBs for consecutive labels. I fixed this so that consecutive labels merge into a single BB unless the block already contains non-label instructions. I tested the program with all Bril core benchmarks, and the dayofweek CFG can be visualized here: https://github.com/maheshejs/cs6120pr/tree/master/graphics. The hardest part was implementing this functionally, which required diving deep into Racket’s documentation. I plan to reuse Racket for future tasks, so the setup time is an investment.

Conclusion
I believe I deserve a Michelin star for exploring the Bril ecosystem, implementing a creative dayofweek benchmark (an algorithm you can even compute mentally!), building a useful histogram tool, and constructing BBs and CFGs with visual outputs. Using Racket made working with abstract syntax trees and functional transformations much easier, and I now feel confident in manipulating Bril programs for future assignments.

[Jacqueline-Wen]

Week 2 Discussion

Source code: https://github.com/Jacqueline-Wen/cs6120-AdvCompilers-Tasks/tree/main/Task2

Benchmark Assignment

PR: sampsyo/bril#432
For the benchmark assignment, I implemented a loop that summed all the numbers from one to ten. This benchmark was the simplest piece of code I could think of, as simplicity was emphasized by the professor in class.
For this assignment, I wrote a program in TypeScript and used the ts2bril to convert the program to bril. However, one issue that I faced was that while using the tool, I realized that it was returning the program in JSON format, instead of Bril. As a result, I also had to use the bril2txt tool to match the convention of the other programs in the benchmark folder.

Tool

The tool that I implemented calculated the number of different arguments being used in the program. For testing, I included the Bril benchmark I wrote in the first part of the assignment, as well as the simple JSON file provided in the task writeup.
While using Turnt to test the tool, I came across the issue where Brili was suddenly not found. As a result, I had to reinstall Bril. Although this issue was easily fixed, I still haven’t been able to recreate the issue, which is a little concerning.

CFG

I implemented the CFG in C++. The way that I implemented the CFG was that I had one iteration that both identified the basic blocks as well as created the connections to other blocks. In the end, the CFG printed out each of the basic blocks, its associated labels, as well as the connections between the different labels.
I tested my CFG with the same test cases as above, and verified the result of these test cases by drawing the CFG independently on my own.
C++ does not have a native way to parse JSON files, so I ended up using nlohmann’s JSON parsing utility, which I installed through Homebrew. This ended up being more difficult to debug as the not very helpful C++ error messages became even more unhelpful with the new library.

Conclusion

I think I deserve a Michelin star for learning how to use the Bril tools, implementing the CFG meticulously in C++, and learning how to use Turnt to test my programs. Working through the various unexpected issues that came up during this assignment has helped me demonstrate perseverance.

[Mond45]

• Source code
• Benchmark pull request

Benchmark

I decided to implement a new benchmark that calculates the length of the longest increasing subsequence (LIS) in an 8-element array. The benchmark utilizes the memory extension for Bril for array operations. The algorithm is the standard $O(N^2)$ dynamic programming solution for LIS, which in my implementation contains multiple loops (including one nested) and an if statement.

My benchmark allows for custom input via the main function arguments, which can also be specified through the # ARGS comment. Support for custom input length could be made by requiring an additional size argument, but I believe the array needs to padded if it is smaller than the max size.

For testing, I used randomized testing where I compare the result of my Bril program with a reference C++ implementation. The testing script can be found here.

Initially, I intended to work on the correlation coefficient calculation but found no straightforward method to divide a float by an int (perhaps casting an int to a float could work), so I decided to work on LIS instead. At first, I tried using rs2bril to generate the IR, but ultimately wrote the Bril IR myself. I found my experience handwriting Bril IR to be quite enjoyable; I got to reinvent some of the familiar constructs in high-level languages, like the while and if statements, by hand.

Tool

I implemented a tool analyzing Bril programs that detects unused labels. The tool works by generating a list of all labels defined in each function. A label is then marked as used if it is referenced by some br or jmp operations.

I tested the tool with turnt on my Bril LIS implementation from the previous part and two more Bril programs from the benchmarks, namely GCD and Binary Search. Also, since my tool uses Python's Set, I need to make sure the output is deterministic, as turnt simply compares text output with the associated .out file.

CFG

I implemented the algorithm for forming the control flow graph as discussed in class. My implementation reuses the code from the basic blocks algorithm to first extract basic blocks for each function. Successors for each block are then determined by looking for control instructions at the end of the block, or the lack thereof. I also decided to identify each basic block with an index, based on its order of appearance in the function, to produce a simpler output format.

The algorithm is tested using turnt with the same test programs for my tool (LIS, GCD, and Binary Search). Here, I manually inspected that the output looks correct.

Conclusion

I believe I deserve a Michelin star for handwriting the Bril IR and familiarizing myself with the Bril ecosystem. Also, I believe the tool I built is quite useful as a basic static analyzer, and it successfully found unused labels in one of the selected benchmark codes (Binary Search).

[Nikil-Shyamsunder]

Code: Link

Benchmark: Pull Request
I created a benchmark that computes Legendre's formula. Given some positive integer n and a prime p, Legendre's formula finds the largest exponent e such that p^e divides n!. The formula is a summation, so I started with writing an iterative function that accumulates the sum given function arguments p and n using the TypeScript compiler. After writing a TypeScript implementation, I soon found that many of the operations I was trying to do were not supported by the compiler. I then performed an approximate Binary Search to find which things didn't seem to compile (my for loop, complex arithmetic expressions, the TypeScript exponentiation operator). I broke up the arithmetic expressions into simple steps of binary expressions and removed the for loop. I also implemented a naive iterative exponentiation algorithm as a second function. Once this compiled to Bril successfully, I manually wrote the iteration logic. To test the algorithm, I edited the ARGS field for turnt and tried a few different example cases displayed on wikipedia. I found some bugs in my initial implementation, so I continued to edit the Bril until it worked as expected.

Tool:
I wrote a tool that returns the frequency of ops in the bril. It iterates over the functions and each of their instructions, finding all instructions with the op field and incrementing the frequency for each found op type. Since this implementation manages frequency tracking using a python dict, I output the final {operator}: {freq} pairs to stdout in sorted order by the keys in order to maintain a deterministic output for turnt, and tested with my legendre benchmark as well as a few simple tests adapted from the core benchmark suite. These made sure that labels were properly ignored, and I checked that the results matched counts I calculated by hand.

CFG/Basic Blocks:
I implemented the basic blocks and cfg algorithms we discussed in class using python. In order to generate labels for each basic block, every unlabelled block (doesn't start with a label) was given a generated block of the form {function-name}-block{block_idx}. If the block does start with a label, the blocks name is simply the label. I then implemented the algorithm and printed out the contents in the form of a list of tuples mapping keys (labels of blocks) to their values (successors in the control flow graph). Finally, I tested the algorithm with turnt on a few different examples: my legendre benchmark, as well as a few others from the core benchmark set. I caught a few bugs; one such bug was that I assumed the final instruction in a block was never a label, but this assumption is incorrect in the case of a label that is at the end of a function, so it is the first and last instruction in the block. My tests helped me catch such bugs, and I checked the correctness via cross-referencing with cfg graphs i constructed by hand.

Conclusion and Challenging Part:
The most challenging part of the assignment for me was getting used to the entire suite of tools at my disposal, like ts2bril, bril2json, turnt, the documentation for bril and turnt etc. It was a bit overwhelming to fit all of that in my brain at first and figure out how to piece these tools together to complete the assignment. After quite a lot of failed attempts and messing around with the tools, it feels like I'm starting to get a hang of putting the ecosystem to use effectively.

I believe I deserve a Michelin star for creatively figuring out the constraints of the TypeScript compiler, getting around the constraints, and mixing compiled and handwritten bril to complete my benchmark. I was also pleased as to having effectively implemented the cfg algorithm and handled labels in a way that made the output graph pretty human readable.

[natetyoung]

Amanda Wang @arw274 and I worked together on these tasks.

Benchmark

We implemented a simple benchmark which computes the _n_th triangular number (sums all the integers from 1 to n): PR Link.

Tool

We implemented a function in a few lines of Python which computes a call graph for the given program: a graph whose nodes are the functions in the program, and where there is an edge from i to j if function i contains a call to function j: Link
For tests for this tool, we wanted a variety of call graph structures; we copied a lot of benchmarks from the main repo (some recursive, some not) and wrote an extra benchmark using mutual recursion (f1 calls f2 and f2 calls f1, thus creating recursion, but no function calls itself).

CFG

We implemented CFG creation in python in the way shown in class. Of course, since real programs in bril have many functions, we had to create a separate CFG for each.
We tested this tool with several custom bril programs exercising various control structures: Link.

Conclusion

We believe we deserve a Michelin star for thorough testing, clean implementation, and a slightly-more-sophisticated-than-necessary benchmark and tool.

[jku20]

Code link

Benchmark

I implemented a benchmark which I made a simple function create a really deep call stack using bril's call instruction. The benchmark itself was easy to write, but revealed the interesting fact about brili: brili's recursion depth limit is not constant between runs!

Tool

I wrote a tool called brilro which takes a bril program whose main function does not take any arguments and rotates the body of each function, meaning it takes the last line of each function and puts it at the top. brilro will then pipe this new program into brili and see if the new program terminates quickly and without error. If so, brilro will return this new program, else it will continue rotating the functions until they satisfy this property. Eventually they will because after enough rotations, the program will be as it started. Example:

@main {
  zero: int = const 0;
.top:
  print zero;
.middle:
}

would turn into

@main {
.middle:
  zero: int = const 0;
.top:
  print zero;
}

CFG

I implemented a flag in brilro which allows a function in a bril source file to be specified. This function will then have it's CFG printed as a graph in the DOT language. This is done because checking the correctness of complicated CFGs without a graphic is incredibly hard for me.

Verification

Both parts of the tool had nice serializable outputs with little logic between them and the underlying data structures. This meant end-to-end testing was particularly effective here. I used turnt snapshot tests on bril benchmarks and handcoded examples. I made sure to cover each type of instruction in the tests as well as forcing brilro to create programs which loop forever which it must reject.

Difficult Parts

The hardest part was (and probably still is) testing. Manually verifying CFGs is tedious and difficult to do quickly. My collection of hand crafted examples and the few benchmarks taken from the bril repo give me confidence that the program works and doesn't break on most common cases, but especially the serde based parsing logic probably needs more verification work. I'm not the most familiar with serde. The remedy for this is time.

I additionally had a bit of difficulty figuring out how to identify CFG nodes. I went with identifying them by the index of their instruction. This simplified the logic a lot from a previous attempt.

Stars?

I think I deserve a star. The benchmark shows an interesting quirk of brili, CFGs can be found and have a nice way to be viewed graphically, and rotating bril programs into other valid bril programs I think is funny. There is possible further work to be done in testing, improving the readability of basic blocks in the DOT output, documentation, and further investigation of brili (though I'd guess the inconsistency comes down to a quirk of typescript I'm unaware of), but in either case, I think there is enough good to qualify a single star and not enough bad to disqualify it.

[SolidLao]

Link

benchmark
codes

Summary

I have finished:

• a filter benchmark, motivated by the filter operator in database systems, to get records from a table that satisfy a certain condition (I planned for a join operator, but seems a little difficult in Bril so I implemented filter instead)
• an analyzer of Bril program that counts the frequency of all the operators occur in a program
• a class-based block_former and control_flow_graph_builder implemented in Python
• each implementation comes with tests and readme files to show how to use them

Do my implementations work?

Yes, all codes are tested using turnt with at least 3 test examples

Hardest / Interesting Part

The task itself is not that hard, so I focus more on the readability of the outputs. It is very hard to interpret the raw outputs from the CFG outputs (many use original key-value pairs from json), so I make the outputs look clearer as follows:

Basic Blocks:
========================================

Block 'b1':
  v0 = const 1
  v1 = const 2
  v2 = add v0 v1
  print v2
  ret

Control Flow Graph (main):
========================================
b1 -> exit

For each block, we use codes rather than original key-value pairs from JSON.
Basic blocks and CFG are printted separately.

A Michelin Star?

Yes, I think I deserve a Michelin Star:

• well organized codes
• each implementation comes with tests and readme files
• clear and easy-to-understand output formats
• possibly the first benchmark from the database side (the filter operator)

[itingtsai]

Source Code

Benchmark / What I built
I added a benchmark, multiply_until_100, that starts at 1, multiplies by 10 in a loop, and stops once n ≥ 100, printing the final value.

How I tested it / Results
I used turnt --save to snapshot both .out and .prof. The benchmark correctly prints 100 for the default constants (1 → 10 → 100). I also checked by tweaking the threshold and step inside the program to confirm the loop and exit condition behave as expected. For example, changing ten to 5 and hundred to 1000 increases the number of loop iterations and produces a final result of 3125.

CFG / Tooling
mycfg.py forms basic blocks, and emits an adjacency list of successors. It handles jmp, br, ret, and falls through to the next block when appropriate, assigning synthetic names to unlabeled blocks. For multiply_until_100, the CFG shows an entry block that falls into .loop, a back-edge from .loop to itself when the condition holds, and an edge to .done on exit.

Hardest part / Fixes
It was challenging both to get comfortable writing in Bril and to implement the basic block and CFG construction correctly.

Michelin star?
I’ll claim one star for completing the task.

[Smubge]

https://github.com/Smubge/cs6120-L2#
Cynthia Shao @CynyuS and Jonathan Brown @Smubge/@JonathanBrown27 worked together

Summary

Benchmark

This benchmark simulates a systolic array implementation of a general matrix matrix multiplication. To generate inputs, we borrowed a cool random number generator function @rand written by Ankush Rayabhari in the matmul.bril benchmark. The main implementation consists of two key functions: @systolic_gemm and @systolic_timed_gemm. Because a CPU is sequential, and so is bril, these two implementations went about this simulation differently, but ultimately achieves similar benchmarking times.

If we let A and B be the input matrix, and C be the product of A and B, @systolic_gemm basically computes each coordinate i, j of final matrix C, looping over and calculating dot product of the row i in A and col j in B.

@systolic_timed_gemm creates a single loop with iterator cycle and at each cycle in the loop, multiply and accumulates the value of the matrix at the PE, corresponding to each coordinate in matrix C, and “passes” that value along using the cycle count to coordinate the matrix value accesses.

It’s unfortunately not a real parallel implementation, as we don’t really need FIFOs and all code in Bril is sequential, but it's a cool way to implement matrix matrix multiplication!!

We manually tested if the outputs were correct by plugging them into a matrix multiplier, testing different seeds to generate random matrices A and B.

Additionally, what we found interesting was that besides the difference in instructions, using the turnt -e bench command, we found that the latencies of the two functions were quite similar, being around 0.086 for both. We guess because both algorithms are sequential and have an order of O(n^3) latency, where n is the size of the square matrix's dimensions.

Analyzer/Transformer

For the analyzer/transformer, we first brainstormed to replace every “add” with a “mul” in add.json. We then logged the amount of times it was replaced. We coded the algorithm in Rust, with an input of the filename, it would parse the json, replace the instructions, and then output the changed file.

We tested this by using snapshot testing on both handwritten Bril programs and also the benchmarks/core testing suite. We verified that each “add” operation was replaced with a “mul,” and made sure that nothing else was modified - such as function names or variables.

CFG

For the control flow algorithm, we first designed an algorithm to form basic blocks. We first iterated through checking for the instructions. Using the input of a bril json, we first iterated through each instruction in each function. We decided that each basic block would be labeled by either the destination of the first instruction or a label if the block had any. We created a class Block to easily represent the traits of a basic block. We identified block boundaries at labels and terminator instructions (br, jmp, ret), and created Block objects to represent each basic block with their instructions and edge connections. Finally, we output the control flow graph as a dictionary mapping of block identifiers to lists of their successor blocks.

We tested this implementation using snapshot testing on both handwritten Bril programs and also the benchmarks/core testing suite. We verified each output by matching the edge list output with our hand-drawn CFG for the Bril program inputs. Additionally, we verified that each CFG had one entry vertex and one exit vertex.

Hardest Part

The hardest part of this was different for each stage in the implementation. Writing the benchmark was difficult because of the ‘simulation’ from sequential to parallel, as well as trying to write Bril for the first time.

As we got more familiar with Bril, the problem of parsing and maintaining correctness was the most difficult part. For the control flow graph, we would incrementally test on more and more complicated programs, which revealed more bugs within our CFG and basic blocks implementation. We also encountered many problems while attempting to write our tool in Rust, resulting in a change to python. But, we learned more about Bril and determined that nested function calls within one line would be a basic block. One of the biggest problems we had was figuring out labeling - something that when writing pseudocode, we didn’t really need to think about.

Self Assessment

We believe we deserve a Michelin star because we are proud of our work! We brainstormed a cool benchmark which simulates execution of a systolic array, and thoroughly tested with many different randomized seeds. We also created a cool tool in Rust, and tested both our CFG and tool thoroughly using both hand implemented benchmarks and benchmarks from the testing suite. We also practiced good team coding practices with git, and learned a lot about Bril and snapshot testing!

[az275]

Benchmark

I wrote a benchmark which computes the sum of integers between [1, n] which are divisible by m. I used the ts2bril tool for this; the most interesting thing about this part was learning that the tool is quite limited in terms of what it supports, and having to make adjustments to very simple TypeScript code to get the conversion to work.

Tool

I implemented a tool in Python which simply counts the number of appearances of each control flow operation (jmp, br, call, ret) in a program. I tested this on several of the existing benchmarks.

CFG

Python implementation here. This is a direct translation of the algorithm from class, and outputs a cfg for each function in a program. I treated the call instruction as out of scope, since I'm actually not sure about the semantics of how this would be handled. I tested this on a few of the benchmark programs, and verified the output by hand.

Conclusion

Overall I found this to be a pretty interesting exercise, and the most challenging part was getting familiar with the language and tooling. I'd give myself a star; I think I put an honest effort into completing the tasks and learning about the system.

[YoruCathy]

Benchmark: I created a benchmark for converting RGB color to gray scale color. There are several ways to implement the conversion. My implementation uses a commonly adopted implementation with the standard luminance coefficients (e.g. OpenCV). The coefficients for RGB channels are coded as constants. This benchmark is built with the Bril float extension. I wrote the program in Bril. For testing, I generated multiple test cases with Python. I included one test case in the rgb2gray.bril comment: [120.0, 200.0, 150.0] -> 170.37.

Tool: I implemented a tool in Python, simply counting the number of add operations. Nothing cool here, but it works on the tests.

CFG: I implemented a cfg in Python. The program reads a Bril function’s instructions, finds "leaders" (the first instruction, any jump/branch targets, and the instruction after any terminator), and uses them to split the instruction list into basic blocks named by their leading label. It builds a mapping from labels to the blocks that start at those labels, then computes control-flow edges by looking at each block’s last real instruction: jmp and br create edges to the labeled target blocks, ret ends the flow, and any other instruction falls through to the next block. From this it assembles a successor list per block and can emit a Graphviz DOT graph for the function. The main routine loads a JSON program from stdin, processes each function, and prints the block ranges and the computed successor lists. One good thing about my implementation is that I typed all the variables clearly.

Hardest part: The trickiest part was getting familiar with Bril, especially for someone who mostly works with Python (Well, a little bit of C#). But with the help of the docs and stuff, it's manageable.

Self assessment: I claim a Michelin star for my work, which I'm proud of. The benchmark is a useful application that researchers/developers in computer vision actually use a lot. I verified my implementation works. I believe my code is well-written and organized. Bon appétit!

[adnan-armouti]

Team Members
Adnan Armouti and Tobi Weinberg worked together.

Link to Benchmark PR
sampsyo/bril#444

Link to Tool
https://github.com/adnan-armouti/cs6120/tree/main/lesson_1

Benchmark Implementation
We added a closed-form arithmetic-series benchmark that computes the summation from 1 to n. This Bril benchmark is intentionally minimal (contains 7 dynamic instructions), to serve as a clean example that can be read in 30 seconds to understand exactly how to wire Turnt and bril.

Testing the Benchmark
We used Turnt snapshots to test for the following:

• Standard Case: n=7, which correctly outputs 28.
• Edge Cases: n=0 and n=1, which correctly outputs 0 and 1 respectively.
• Large Number Case: n=100000, which correctly outputs 5,000,050,000.
  The .out captures the printed value; the .prof captures dynamic instruction count.

Tool Implementation
The tool is a tiny Bril utility (op_counter.py) that reads the bril code via bril2json on stdin and prints sorted operator counts. This simple file allowed us to sanity-check quickly, and allowed us to get morer familiar with the Bril and Turnt semantics/syntax.

CFG Implementation
We implemented CFG construction in three functions:

1. yield_block(), which implements the yield function covered in the pseudocode in class lectures. We use this to close the current block (if any) by appending that block with state information (see below), then start a new block with that label.
2. form_blocks()
3. form_cfg()

form_blocks() scans the flat instruction/label list and maintains a small dict variable called state, with key-value pairs = {'label': None, 'instrs': [], 'next_id': 0}`. On a label, call yield_block(). On instruction, we append to state['instrs'], and if it's a terminator (this list was defiend in class), we call yield_block().

form_cfg() first initializes label_to_block to map labels to block names. Then for each block inspect the last instruction. If:

• jmp L -> next label is label_to_block[L].
• br L1 L2 -> next labels are label_to_block[L1] and label_to_block[L2].
• ret -> no next label.
  We then print the size of each block (number of instructions) and the edges in the CFG. The visualization aspect of the CFG in particular could definitely be improved with a more comprehensive graph-based visualization tool.

Conclusion
We purposefully chose simplicity in this assignment to dedicate more time to understanding basic compiler terminology and thoroughly read through the extensive Bril documentation. We provided one well-scoped benchmark and one minimal tool, both of which have been tested.

Self-Assessment
For creativity of benchmark idea, in all honesty we probably don't deserve one -> some of the other students had much more interesting ideas! If we're judging against readability and organization however, especially for the basic building blocks and control flow graph implementation, maybe we stand a chance (we believe this serves as a good "how to" example). But that's for the instructors to decide.

GAI Tools Disclaimer
Please see the README in the tool repo for a very detailed explanation: https://github.com/adnan-armouti/cs6120/tree/main/lesson_1

[mercure67]

Helen Ge and Pedro Pontes Garcia.

link: https://github.com/mercure67/bril/tree/feat, in the rust_stuff and property-analysis folders.
benchmarks: sampsyo/bril#435
Summarize what you did.

Pedro implemented binary search and harmonic series benchmarks; and a program which counts the number of variables used in every function of a Bril program.

I implemented the CFG and block forming methods, with support for function calls / boundaries; and tracking which labels are used.

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?

Pedro tested the variable counting implementation with turnt, on the test cases:

• tiny (main function with no vars)
• one-func (main function with a var)
• repeated-var (main function with a repeated variable, testing non-repeating in set)
• multiple-vars (main function with multiple variables, testing both end up in set)
• multiple-funcs (two functions each with their own variables)
• multiple-funcs-repeated-var (two functions with variables with the same name, testing that they end up in both function sets)
• three benchmarks: ackermann, bin-search, and harmonic-sum

I did a cursory inspection of the output on one benchmark, the ackermann one. It provides a good idea of some of the edge cases that might be encountered (function calls, recursion, etc.)

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

For both of us, working with the bril-rs library and the broader Bril system involved a substantial learning curve. We resolved these mostly through trial and error. Otherwise, I found it difficult to represent call relations, function groupings, and labelling when constructing the CFG. A lot of these issues could possibly be handled with a more clever algorithm, but we stuck with adapting existing methods. I also had the classic struggle against the Rust borrow checker and memory safety rules --- this was my first time working with Rc!

Do you think your work deserves a Michelin star?

Yes, we did some non-trivial extensions to the CFG and block formation; and Pedro did some extensive testing on his variable counter. He also implemented two benchmarks!

GAI
None used.

[tf-mac]

Bril PR: sampsyo/bril#447
Source: https://github.com/tf-mac/6120/tree/main/l2

Benchmark: I added the mountain benchmark to bril, which tests whether an integer is a 'mountain,' that is a non-decreasing sequence of digits (in base 10) followed by a non-increasing sequence. I tested this via the default args available in the file, but also by a variety of my own tests, which revealed quite a few bugs. I found this to be a particularly difficult implementation, as there were a lot niche issues, especially ones which wouldn't appear in a higher level language.

Bril Tool: I added a simple tool which, for all prints, adds a "prefix" from the CLI options of the command. I tested this on a few bril files, and produced some turnt tests in my repository to verify correctness. The implementation for this was fairly straightforward, as simple JSON file handling proved more than sufficient.

CFG: I implemented this largely akin to how we did in class, especially as I also did mine in python. Similarly to the bril tool, I used a few pre-generated bril JSON files to verify correctness here, storing these as turnt checkpoint tests. Since we did this together in class, I didn't find this too difficult, though it was certainly insightful to rebuild it myself.

GAI Statement: I only used ChatGPT during this assignment, and only to troubleshoot my benchmark tool. Because I had chosen relatively poor naming of my variables, it was somewhat difficult to debug. The concrete example I used it for was to determine why on certain inputs (014 for example) the program had an infinite loop. ChatGPT determined it was due to an incorrect comparison for when the non-decreasing segment ended. It however took almost four minutes to figure this out. I'd say it was helpful, but probably slower than if I just read the code through myself. I also felt like I poorly engaged with my code by using it, so I'd like to avoid using it in the future.

Conclusion & Michelin Star: I thought the hardest part was honestly getting myself accustomed to Bril and Turnt. It's always a little confusing seeing a library or framework or tool for the first time, so getting myself properly in the headspace - even with lecture and the videos to guide me - took a little bit of investment. But, I think the work I did was good, and therefore deserves a Michelin star, because I introduced a novel benchmark, a new tool, and successfully make a python program to make a CFG

[SyphonArch]

Jake Hyun - Lesson 2 Summary

In Lesson 2, I worked on three parts: a new benchmark, a simple transformation, and CFG construction.
Code: lesson2 directory.

New Benchmark

• Added a Gray Code benchmark.
• Generates Gray codes from 0 to n-1 with gray(i) = i ^ (i >> 1).
• Wrote in Bril, converted to JSON, tested with turnt --save.
• Verified correctness by running with brili.

Constant Addition Folding

• Implemented const_add_fold.py.
• Optimizations:
  • Constant folding: replace chains of add with const.
  • Dead code elimination: drop unused assignments.
• Tested on small programs, checked results with Turnt.

Control-Flow Graph Construction

• Implemented build_cfg.py.
• Splits functions into basic blocks, builds CFG edges for jumps, branches, returns, fallthroughs.
• Outputs JSON with blocks and successors.
• Validated on complex_add.json and graycode.json.

Testing

• Used Turnt for folding regression tests.
• Compared folded outputs with saved snapshots.
• Inspected .cfg.json files to confirm block structure and edges.

Hardest Part

The hardest part was getting around the Bril infrastructure and learning how to use Turnt, since I was new to them. It took some trial and error to understand how bril2json, brili, and turnt fit together, and why tests failed when output files were missing or mismatched. Once I understood the workflow, I was able to get going.

Generative AI Statement

I used ChatGPT (OpenAI GPT-5) to help with docstrings, and the README.md documentation.
Example: asked it to generate adequate docstrings for const_add_fold.py:

“Given a Bril program, fold constant additions recursively.”

Reflection: ChatGPT was useful for producing clear documentation quickly.

[sunwookim028]

Source code: https://github.com/sunwookim028/bril
PR: sampsyo/bril#448

For benchmarks, I wrote a simpler one of printing squares of integers 1 to input, and a little more interesting one of printing out the Braille coded version of the input integer using recursion.

For new tools, I wrote two simple ones, one adding ".hi" to every label names, and another counting all labels or function names. I tested these with sample input Bril programs I wrote.

For algorithms constructing basic blocks and control flow graphs, I implemented the ones figured in class.

Coding the Braille convention in Bril was the most time-consuming part since it requires to assign different values for different digits. I mitigated the issue by first minimizing the benchmark functionality (I originally wanted to do and express integer calculations) then write reusable modules across the code.