Lesson 2: Representing Programs

[sampsyo]

Post any questions you have about Lesson 2! And, when you finish your implementation tasks, 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.

[matth2k]

• Summary
  • BRIL Benchmark PR
  • My new Bril tool
• Implementation Details
  • I used the ts2bril tool to generate my benchmark from TypeScript. The benchmark itself is the CORDIC algorithm which can be used to approximate sine and cosine.
  • My bril tool uses Python to parse the json and count how many bits need to be allocated for constant values. The idea being: maybe you want an estimate of the size of the read-only data section when compiling. The tool also then calculates how many bits of space can be saved by elminating redundant const values. Here is an example output running on my CORDIC benchmark:

  ~$ python3 countBits.py cordic.json 
  There are 1984 bits-worth of constants used in the program.
  If you remove duplicates values, only 1088 bits-worth of constants are used in the program.
  

• Anything Hard or Interesting?
  • I wanted to use a constant array in my program from the TypeScript frontend. However, I noticed that arrays are an extension to both the ts2bril tool and the Bril IR. The main issue I ran into is that I did not know how to initialize my Bril memory through the TypeScript frontend. I wanted to use the normal syntax of let myArray: number[] = [1, 2, ...];, but I could not figure out how.

[keikun555]

Summarize what you did.

• Euler's Number Approximation Benchmark
• Operation Counter Tool

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

• I used ts2bril to convert my typescript code (in the comments of the euler.bril benchmark) that approximates Euler's number to Bril code.
• I found that the float approximation converges after 18 iterations of the Taylor series since the number of decimal digits in a Bril float is bounded.
• Checked that the converged value is the first digits of Euler's number
• The Operation Counter Tool uses Python to count how many of each operation is present in the program. I tested using the simple jmp.bril and the more complex euler.bril files. The outputs are also in the tools repo.

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

• I originally wanted to write a Runge-Kutta method benchmark. I soon realized that it's not possible to pass in functions as arguments. I solved this problem by choosing a new benchmark: Euler's Number Approximation. Perhaps it may be a good extension to enable function arguments.

[stephenverderame]

Summary

• BRIL Mandelbrot Benchmark which was generated from the typescript frontend and a recursive factorial benchmark that was handwritten.
• CFG Generation and Display Tool that converts BRIL programs into CFGs and outputs graphs that can be rendered with Graphviz.

Testing

• To test graph visualization, I first wrote some test cases to check simple and edge cases such as empty blocks, long sequences of jumps, and infinite loops to check the resulting graph is as I would expect.
• After that was looking good, I took some benchmarks, generated the CFGs, and spot-checked the outputs for anything that looked out of the ordinary. I was mainly focusing on things like loops, branches, and returns, and making sure no instructions were being missed or anything weird was going on.
• Once I was happy with the results, I used Turnt to save the outputs as gold references.
• For greater confidence, I also implemented a conversion from CFGs back into BRIL instructions. I created a program, dummy-pass that simply takes a Bril program, converts it to CFGs, and then reconstructs the BRIL program. I then used Turnt to ensure the outputs of all benchmarks were equal when running them through brili and running them through dummy-pass | brili.

Difficulties

• With the typescript frontend, it took me a bit to realize that when you invoke a function call, you need to save the result into a type-annotated variable before using it.
• I also realized that prints always have a newline, so the mandelbrot x resolution was limited to fit in the roughly 20-digit limit of max for a 64-bit int.
• I found it quite funny that for the CFG conversion, I made many of the same mistakes I made during CS 4120 such as correctly dealing with empty blocks at the end of the program.

[willwng]

Vivian and I worked on lesson 2 together.

Summary

• Conjugate gradient solver for Ax=b
• Branch swap tool

Implementation details

Conjugate gradient solver:

• The bril code for the conjugate gradient solver was written (perhaps painstakingly) by hand, using simple implementations of vectors, matrices, and vector operations.
• We verified the code with scipy's implementation of conjugate gradient on a 100x100 matrix.

Bril program transformation:

• The tool swaps branches in br instructions and inserts a print statement before the branch which displays the UTF-8 encoding of "Haha, you thought".
• Before printing this number, it needs to be saved to a variable. We wrote a fresh name generator which stores existing variables and yields unique names. Each time we print, we store the number in a fresh variable. This is not really necessary since we only ever print the same value, just done for the exercise.
• We tested using a few small programs, including those with multiple branch instructions and adversarially picked variable names (in the same form as those produced by the fresh name generator). We confirmed that the output programs were as expected by both inspecting them and running brili.

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

• The hardest part was debugging the values in memory in Bril. We think a cool extension (if it doesn't already exist) would be strings and vectors/arrays, maybe with the size/metadata of the array also stored in memory so we know its size/shape. One thing that helped was creating helper functions to print out the contents of an array.
• The rust interpreter noticing when uninitialized data was trying to be loaded was very helpful. The interpreter didn't pick up on type checking mistakes, which brilck did.

[obhalerao]

Summary

• Bril Totient Function Benchmark
• Bril Tool - Counting Branches

Implementation Details

Benchmark:

• The totient function benchmark was written by hand in Bril, closely following an earlier implementation I had written. Since the mod operation was not supported natively in Bril, I had to implement my own version, taking advantage of the fact that a % b is equal to a - b*(a/b).
• The benchmark was manually verified for many randomly selected values of n between 1 and 100.

Tool:

• The tool to count the number of branch instructions was written in C++, using the RapidJSON library to parse the input JSON file. I used CMake to ensure a consistent build setup for this project along with future ones.
• This was also tested manually with a few of the example Bril benchmarks.

Difficulties

• Initially; I tried to write my benchmark in TypeScript and use the ts2bril compiler; however, the exact features of the compiler were not well-documented, and the error messages the compiler provided were very cryptic (e.g. Unsupported binary operation 35), as such, I chose to write the benchmark directly in Bril. Perhaps the error reporting of the ts2bril compiler can be improved and what language features it supports be better documented.
• As I had not worked with C++ in some time, it took some effort to get RapidJSON working and to get used to its general layout.

[bcarlet]

Summary

• Tower of Hanoi benchmark
• A tool that swaps branch targets

Details

• The benchmark was written by hand, using the standard recursive algorithm.
• The tool is a Python script to locate all br instructions and swap the branch targets. It was tested on additional manually-written benchmarks. Apparently, another group is already offering a competing product in the market of branch swapping tools; in contrast to their offering, mine avoids adding extraneous prints, in case that's not to your taste.

Difficulties

• For the benchmark, I had originally intended to visualize the state of the disks and rods after each move, but the bril print instruction didn't offer enough flexibility (specifically with regard to control over whitespace) to make that practical. Instead, the benchmark simply prints moves as pairs of numbers indicating the source and destination rod.

[kevinnegy-exo]

Programs:
dot-product.bril
count terminators tool

Summary:

• Wrote dot-product bril implementation by hand. The program creates a set of two vectors with 5 ints each, then calls the dot-product function to multiply the elements and then add the results all together. Tested with turnt, but still using the hardcoded test in the dot-product.bril file itself. Not sure how to convert the bril file into a general file for testing with turnt (especially since I wouldn't know how to pass in ptr to my program with turnt).
• Wrote a simple Python script based on what we wrote in class, except this one just counts the number of terminators. Tested on my dot-product program (has 2 terminators).

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

• Trying to figure out what to do for the benchmark was the hardest part. When I think of benchmark, I think of SPEC or PARSEC, e.g. so at first I thought the scope for this assignment was huge. Then after seeing the other benchmark examples I started trying to think of any well-known math concept, but I'd love to know more specifically what constitutes a microbenchmark (e.g., are microbenchmarks just each individual test that constitute a benchmark?, should these be general math equations or actually something more language specific like doing a million jmp commands?)
• Also confused on how to use turnt with my bril program. Haven't figured out how to pass in arguments from turnt into the bril main function.

[alifarahbakhsh]

I wrote the following pieces of code:
Benchmark: Palindrome.bril
Tool: A short piece of code that locates all the add and mul instructions, and swaps the args.

Testing and the difficulties within:

• Palindrome.bril: I tested this through the usual turnt pipeline of adding #ARGS = x at the beginning of the code. You can use any integer.
• Tool: I'm still having difficulties at testing this with turnt. I have to compare the outputs of two Bril programs - the one before swapping, and the one after it. Technically, the results should be the same. However, I'm having difficulties at reshaping this specific pipeline into a turnt test. The easiest way of testing this seems to be a simple script that executes the two programs using Brili, writes the output to some file, and compares them.

[bennyrubin]

Summary

Rectangle Fitting Benchmark
Bril tool for calculating a program's "Jumping Distance"

Implementation Details

• I wrote the Rectangle fitting benchmark by hand. The program takes in the height and width of two rectangles and outputs true if the first rectangle fits inside of the second. I tested this by coming up with a few examples of positive and negative cases and making sure I got the output expected. I also used turnt to "freeze" my output to test against later implementations.
• The program "Jumping Distance" is a measure of how far each jmp instruction in the program "jumps", in terms of instructions skipped over. It assumes that jmps don't cross function boundaries. I tested this by writing a number of example bril programs and calculating by hand the "Jumping Distance", before using turnt to save the output.

Difficulties

• The main difficulty I ran into was the original program I was trying to write. I wanted to write a program that given an integer N prints out all the permutations from 1..N. I tried writing it by hand using Bril and pointers for arrays, but after tinkering for a bit, I couldn't get it to work. Perhaps with more time I could've gotten something running, but for the sake of having something to submit I wrote the simple rectangle program.
• I also had some issues with the typescript bril compiler. I couldn’t get the bril typescript compiler to compile &&, ||, or expressions inside of parenthesis
• The final oddity was that using the bril2json tool, jmp instructions sometimes got translated with a “labels” field and sometimes the label was in “args”, so I had to check for that in my python code.

[emwangs]

Summary
Bril Benchmark
My Bril Tool

Implementation

• I wrote an LCM function, which required me to write my own implementation of %. What I used was that the quotient of two numbers was just a/b with integer division, and I could get the remainder by subtracting a - a/b
• The LCM function itself I wrote as a combination of by hand and by Typescript. I would generate a couple examples of Bril lines from the ts2bril compiler. I found using the ts2bril compiler rather limiting, so I would try a couple lines at a time, and write the control flow logic in bril by hand. The function itself is a very dummy LCM function -- it starts from the max of 2 args and INCREMENTS by one until both numbers are a clean multiple of it.
• In CPP, I implemented a benchmark that parsed the JSON and looked for all the "op"s, and printed out what that "op" was. I ran into linking issues when trying to use the jsoncpp library, that I am still working on. It seems from some of my classmates that the nlohmann/json library has a single include solution to linking against that cpp library 🤩 , so I may consider switching to that library, or setting up a CMake.

Difficulties

• The first difficulty was even choosing a function to implement -- a lot "canonical" algorithms require more data structures than just an int/bool. I spent a while thinking about how I could do something string manipulation related, but decided against it. Eventually I settled on LCM because we have a GCD! I ran into a LOT of issues trying to use the ts2bril compiler (as I didn't read the bril documentation very thoroughly about what was supported in the language or not), but it was not too difficult to write a program directly in bril and I only needed to iterate on it like 2 or 3 times.
• The second difficulty was setting up linking for my new tool. I decided to CPP, because I like it. Unfortunately there is no built-in parser into the stdlib for CPP, so it might be a fun exercise to write one on my own, as I had MANY issues trying to link against a library I installed externally. I haven't quite set up a nice environment to work in yet for CPP, so I want to put in some time into that later on. I'd say linking errors are my greatest weakness so I probably spent a good 3-4 hours on it :")

[evanmwilliams]

Summary

• Euclidean Norm Benchmark
• Count Add Instructions Tool

Implementation

• For the benchmark, I wrote a function that computes the Euclidean norm over a vector of floats. To do this, I leveraged some of the existing benchmark code (primarily for things like power and n-th root. I then extended the functions to iterate over the array of floats and compute the sum of squares, and finally take the square root and return the result.
• The benchmark is written entirely in native Bril. I attempted a solution using the TypeScript compiler but I discovered that it doesn't support arrays, so I ended up just following the example programs and creating one from scratch
• For the tool, I implemented a program that simply counts the number of add instructions in a Bril program. My implementation is in C++ and uses the nlohmann library for JSON parsing

Difficulties

• As for the benchmarks, I had trouble understanding some of the limitations of the tooling. For example, I did a lot of fighting with the TypeScript compiler before realizing I'd be better off writing the Bril programs by hand. I also played with the Rust compiler but I didn't like the code it emitted (it was really difficult to read and made the benchmark quite unintuitive)
• For the implementation, I ran into some silly C++ issues with linking and input parsing. Including nlohmann ended up being pretty annoying, so I just copy/pasted the header file directly into my project. This works but feels a bit hacky, so I'll probably set up CMake for future assignments
• The last difficulty for me was figuring out turnt. I found the article linked in the GitHub repo very helpful - I just needed to refactor my tool a bit to take a file from the command line

Generative AI

• I did not use ChatGPT for this assignment, but I did use Warp, an AI-powered terminal. I found it pretty useful for basic C++ things as I was debugging, as I'm still learning the details of the language. A few concrete examples include fixing the errors I was having with nlohmann (it told me to copy/paste the header file into my repo) and fixing a C++ file reading error. I think that generative AI is best for these types of things - I didn't ask it to produce a lot of code or complete a task for me, but I used it to get basic information for me that would take a bit longer for me to find through Google. I particularly like the integration with the terminal - Warp has a feature where you can click a button on an error message and it automatically asks the AI-chatbot what the problem was and how to debug it. I will probably keep using it in future assignments, but I'll refrain from using ChatGPT.

[Enochen]

Summary

Two Sum Benchmark PR
Print Before Jump (TypeScript)
Print Before Jump (Rust)

Implementation

Benchmark

• I wrote a TypeScript program that solves Two Sum and used the ts2bril tool to turn it into bril.
• I hardcoded the array contents, using the mem extension.
• I added some finishing touches to the bril itself, including adding an input to the main function which serves as the "target" integer.

Tool

• For the transformation tool, I opted to do something simple in different languages to evaluate the developer experience between languages. This time I chose to implement the same thing in TypeScript and Rust.
• The idea itself, which is printing something before every jmp, comes from the handout. It defines an integer const to a variable called tmp (possibly overwriting an existing variable of the same name) and follows it up with a print to tmp.

Difficulties

Benchmark

• ts2bril's bigint workaround for defining integers within TypeScript was a little wonky to get around. It also wasn't able to read negative numbers like -1n (I'm not sure if I did something wrong).

Tool

• I had a good amount of trouble implementing the tool with Rust as a beginner. I was used to being able to mutate the list of instructions while iterating over it, and the whole borrow checker thing took a while to get used to.
• I also didn't enjoy writing in TypeScript as the pattern matching capabilities weren't there, such as distinguishing between instructions.
• In the edge case where the tmp name is actually used in the original source, this transformation will break correctness. I could have addressed this by going through all instructions and generating a variable name that is never used, however I opted to learn Rust and implement the simple logic multiple times.

Generative AI

I didn't use Generative AI for this assignment.

[SanjitBasker]

Post any questions you have about Lesson 2! And, when you finish your implementation tasks, 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.

Summary

• My benchmark finds a primitive root modulo a prime number $p$, which is useful in number theory.
• My tool generates the function call graph for a Bril program.

Other thoughts

• Benchmark
  • I actually wrote my benchmark in Bril from the outset (I wrote some clever array allocation in IR for my compiler in CS 4120 so I was feeling a bit too confident in my IR programming skills)
  • It turned out to take a bit longer than I expected, mostly because of the quantity of code I wrote
  • I was slightly bothered that alloc 0 is an error in Brill, since it's nice to have an empty array as a base case
  • I also decided to store my prime divisors in arrays and prepend onto the array, despite the poor asymptotic complexity of this representation for lists. This probably inflates my dynamic instruction count above the complexity of the task.
  • I tested it manually with a bunch of small prime numbers (working it out in my head) and some large prime numbers (I used some online calculators that I first sanity-checked with Python terminal)
• Tool
  • I intentionally picked an easier task for this one because I spent a while on my benchmark.
  • I tested it on a bunch of the benchmarks as well as some basic program I wrote in Bril that uses recursion.
  • I peeked at briltxt.py to copy over the input parsing logic to my tool because I got lazy. This reminded me of the -p flag, so my tool also supports a -p flag. If the input was generated with bril2json -p, the information of which calls occur where in the text program is carried over :)

[20ashah]

Summary

Me and @JohnDRubio worked on writing a tool to generate a CFG for a given function, and did further analysis to output the method that control was transferred for each edge in the CFG, whether that be a jump, branch, or a fall-through.

Implementation

• We wrote the algorithm to generate basic blocks and the CFG from a bril json file in python
• If there were basic blocks that didn't have labels, we made sure that unique ones were generated for them
• Our CFG was a dictionary, where the keys were labels for basic blocks, and the values were a list of labels that represent its successors.
• For each edge in the CFG, we specified if it was a result of a branch, jump, or a fall-through

Benchmark

• The benchmark we created was the approximation of Pi using Nilkantha's series
• We generated the bril test file for this using the Typescript compiler from a typescript program that implemented this algorithm
• We wanted to choose a benchmark that had loops, since this would generate a more interesting CFG and more interesting edges within the CFG that wouldn't just be fall-through cases
• We verified from this test that the CFG and the edge analysis on the CFG aligned with the bril instructions for this benchmark

Difficulties

• A difficulty we encountered was thinking of a lot of the edge cases in the CFG algorithm, such as removing empty basic blocks, dealing with blocks that didn't have labels, and return instructions
• Another challenge we faced was coming up with a benchmark to use that was unique from the ones already added, but also one that would produce an interesting CFG we could analyze
• We did not use any resources or generative AI to write our algorithm

[yxd97]

Summary

• CSR SpMV Benchmark multiplies a sparse matrix in CSR format with a dense vector. Inputs are generated with Linear Feedback Shift Register (LFSR) RNG.
• Operation to Memory Ratio Analyzer counts the number of arithmetic&logical operations and memory accesses of every basic block in a program, and calculate the ratio of operations to memory accesses.
• I did not use any generative AI in this task.

Implementation

• The benchmark is hand-written in Bril. The core of the benchmark contains a 2-level loop. The outer loop iterates over the row pointer array of the CSR data structure to obtain the start and end locations of a row; the inner loop iterates all non-zero values in this row, multiplies it with the value from the input vector (pointed by column index), and accumulate it over the result (pointed by row index).
• To generate inputs for the benchmark, I implemented an LFSR RNG which shifts right its state by 1 and fills the LSB with the XOR of its 11-th, 13-th, 14-th and 16-th bits.
• The op-mem ratio analyzer first split each function into a list of basic blocks and name each block with its starting label. If a baisc lock does not have a label, it will name it as bb_0, bb_1, ... depending on its occurance in this function. Block names are prefixed with the name of the function it belongs to.
  • E.g., main.bb_0 or foo.loop_cond are possible names for a baisc block.

Testing

• The output of the SpMV program is cpoied into a python script, which creates a CSR matrix using the scipy.sparse package. The vectors are numpy arrays which can be multiplied with the matrix as m @ v. The results from scipy matches the output of brili.
• The analyzer tool is tested on the fizz-buzz benchmark, the mat-mul benchmark, and my csrmv benchmark.
  • fizz-buzz contains plenty of labels and branches, as well as basic blocks with just a label. So it serves as a good test case for verifying the functionality of the tool.
  • mat-mul and csrmv are picked to form a comparison. mat-mul should be more compute-intensive while csrmv should incur more memory accesses. The output of my tool confirms this conjecture: the matmul.sum.body block, which is the loop body of the matrix-matrix multiply, has an op-mem ratio of 3; while the csr_spmv.loop_nnzs_body bock only has an op-mem ratio of 0.6.

Difficulties

• Debugging the SpMV benchmark is the most challenging part. Plenty of indirect memory accesses make it hard to track with mind. To tackle this problem, I incrementally build the program: everytime I compose or modify a function, I will make a ad-hoc test in the main funcion and verify it with brili.

[collinzrj]

Summary
Bitshift Benchmark
Bril Tool

Implementation Details
There has been bitwise and, or, xor in the benchmarks, but there hasn't been leftshift or rightshift. Moreover, there has been float pow function but not integer pow function, so I have implemented these three functions. I wrote the code in typescript at first, then compile it to bril with ts2bril.

Sometimes we need to silent the log of a program to avoid log slow down the program, so I have wrote a tool that removes all print operation in a bril code.

Difficulties
The main issue I ran into is that when bril compiles typescript to bril, some integers in typescript is represented as float, and some comparative operators are represented as their float version. As a result, I have to manually change them to int.

[AliceSzzze]

Summary
QuickSort benchmark
Tool to count frequencies of different op types

Implementation Details

• benchmark :
  • I wrote an implementation of quicksort, using pseudocode from Wikipedia as a reference. I used the simple partition scheme of picking the last element to partition on, but this could be easily optimized by using a better heuristic (e.g. picking the median of the first, middle, and last element). I had to hardcode 6 as the length of the array, but the program will work for other lengths.
  • I stole some utility functions from the bubble sort benchmark (referenced in the code). Thanks @tonyjie!
  • I wrote the program by hand because I don't know any typescript.
• tool: I used Python for the tool, because AFAIK it is the nicest to parse JSON in. The tool prints out the counts of different op types in the program (e.g. add, alloc, load), sorted by frequency. I used a counter (dictionary), nothing fancy.

Testing

• benchmark: ran the Bril program and a Python program on randomly generated inputs and compared the results.
• tool: I used turnt to test the tool on different jsons in the Bril repo. I tried to cover different op types and I think I have got most if not all of them (I don't think there is an exhaustive list of op types?).

Difficulties

• benchmark
  • probably spent the most time just getting all the tools set up, mostly because my PATH was not pointing to the right places, and my tools were not in the right place either. For a while, the benchmark would run fine in my terminal but not when I ran turnt, and all I got from turnt was "not ok", so I wasn't too sure what was wrong. No one else seems to be having this problem though, so it's probably just a consequence of me doing something stupid with the PATH variable in the past.
  • reading other benchmarks was really helpful to see how to code in Bril! Especially when they are documented.

[NgaiJustin]

Summary

• IsDecreasing Benchmark
• Terminator Counter Tool

Implementation

Benchmark

• I wanted to use this as an opportunity to practice Rust so I opted to use it for both the benchmark and the tool
• I wrote a rust program to scan the digits, checking if it contains digits in strictly decreasing order
• I used the rs2bril tool to turn it into bril
• I manually added the input to the main fn for the digit to inspect
• I tested this by rolling random numbers, feeding them into the bril script, and inspecting the result from brili

Tool

• In a similar vein as the CFG construction shown in class, I decided to implement a counter for terminators
• I use the provided bril parser and filtered through all the instructions that match with the instruction effect op of EffectOps::Jump, EffectOps::Branch, or EffectOps::Return.
• I tested on smaller files add.json, call.json, comment.json, float.json, and then larger files that contain more jumps and branching. I also tested it on the bril benchmark I generated for the previous task.
• I automated the testing with a simple script that just runs the turnt command on the files in the test directory

Difficulties

Benchmark

• I had a bit of trouble installing rs2bril because I just had so much technical debt in my env from ancient package managers and just random copy and paste from StackOverflow. But this was an excellent opportunity to clean all this up.
• I originally had some other benchmarks in mind but after playing around with ts2bril I realized that there were a bunch of things that I couldn't use: arrays, strings, the modulo operator, etc. Instead of just picking a simple math-based benchmark I thought it would be fun to reimplement these functionalities using basic operations in Rust (good practice). The r2bril error messages were also much more informative (after toying with the RUST_BACKTRACE) than ts2bril. A lot of the ts2bril error messages were hard to understand such as (Uncaught (in promise) "unimplemented type {}") and Uncaught (in promise) "unhandled binary operator kind 44" I think going forward I will continue to use Rust both for practice and a better developer experience.

Tool

• It took me a long time to set up the rust project such that the code navigation worked across my cargo projects and the bril-rs src. I think I was too used to simply working on a larger project where all the project structure is already set up, this was a good exercise to learn practice for setting up nested Cargo.toml.
• I stared at the lines 1..1 not ok 1 - turnt.toml for a time longer than I would like to admit, until I finally realised that I was supposed to pass a file in rather than just the turnt config. I felt very silly...

[Arthur-Chang016]

Summary

sum-check benchmark
Tool for count number of basic blocks for each function

Implementation Details

• Benchmark:

  • I implemented two function to compute the sum of [1, n]
  • The first one is by for loop. The second one is by the Trapezoid formula
  • Finally compare to see if they generate the same output, which can be a kind of self-testing

• Tool:

  • I implemented a function to count the number of basic block of each bril function
  • By the concept from the lesson, I just need to detect if a block is starting with a label or ended with a control instruction
    • If both conditions are satisfied, still count as 1 BB boundary (bug!)

Difficulties

• Benchmark:
  • learn bril language which is pretty different from what CS4120 uses which is even higher level that can have a tree style expressions
• Tool:
  • Thoroughly think about what a basic block is.
  • Still not getting used to python syntax. Maybe I will move to java in the future

Generative AI

I only use chatgpt for python syntax sys.stdin.read() for reading the whole file as a string for this task.
I thought GAI is very useful for such specific usage of syntax which would be much faster than using Google (at least for me)

The strength for this kind of tool is that it can actually understand what I am asking. For my previous use, it can give me a correct direction of how to do. I can treat it as my software architect instead of code writer.
The drawback is that it won't generate the correct code, especially for a bigger chunk. I cannot avoid improving my programming skills.

[he-andy]

Summary

vsmul benchmark
simple debugger tool

Implementation Details

• The benchmark is designed to test the performance of simd/vectorization operations by initializing a large array with random values and then looping through each element and multiplying it by a constant scalar. The random valued array implementation is borrowed from the mem/matmul.bril benchmark I tried using rs2bril initially but was having difficulties writing concise code. I ended up writing the bril by hand.
• The tool is a simple debugger that simply prints the name of the method every time the method is called. This tool was written using Rust. The tool uses the serde-json library for parsing.

Difficulties

Most of the difficulties associated with the benchmark came from being unfamiliar with bril and its associated syntax & ecosystem. Looking at example bril code in the benchmarks directory helped a lot with this.

Parsing JSON with Rust was a little more complicated than expected. It is slightly less convenient to work with than Python, but after an hour or so of messing around, I was able to deserialize the JSON into my own Rust types.

My initial idea for the simple debugger was to also print a count for the # of times each method is called as well by wrapping each method in another method that counts each call. This turned out more challenging than expected as I haven't figured out how to deserialize the individual instructions yet. Instead I settled with just printing whether a method has been called at the start. This also was quite challenging as printing does not seem to support string (or character) literals. It took some finessing to print out a series of characters and it is still somewhat awkward as there are spaces between each character.

[janpaulpl]

Summary

Benchmark: Birthday paradox benchmark
Tool: Return if there are any empty arguments

Implementation

Benchmark

• I implemented the benchmark in typescript first, and used ts2bril birthday.ts for the translation to Bril.
• I decided to go for a simulation of the Birthday Paradox. Originally I wanted to go for a full simulation given any amount of iterations, albeit because of issues detailed below I decided to just go for a single iteration. Ideally, the full benchmark would include multiple iterations.
• The concept is simple, the program calculates the probability of two people sharing the same birthday for a randomly selected amount of people. It makes use of simple arithmetic.

Tool

• Due to my difficulties outlined below, I got inspired to make a simple tool that returns information in regards to the arguments of our JSON. If there are argument keys that don't have any values, it will return such. Otherwise, we just return the actual arguments listed.
• It is written in Python and makes use of the json library.

Difficulties

Bril

There were several issues when getting Bril setup:

• At first, I couldn't figure out the settings on my Arch distribution. This is 100% my fault. Either way, it was important for me that to get flit working I had to create a virtual environment and call all commands in the form path/to/venv/command.
• I struggled to find a good microbenchmark inspiration. Three times whatever I thought of implementing was already under the benchmarks directory, and the limitations on typescript did not help:
  • Arrays not working was a big letdown, but I didn't want to hard code nor manually program in Bril.
  • I kept getting unhelpful error messages for unsupported binary operators and untyped expressions. The binary operators made sense (most of the time), although it would be nice if instead of getting a cryptic number (e.g., 51 for <<) I got the actual meta-data for the line it's on.
  • As I mentioned in the previous bullet, the error message for untyped expressions was weird. It was due to nesting an order of operations of the form ((365 - i)/365) which I had to decompose into two lines. I don't immediately understand why Bril doesn't support parenthesis, but I'm interested in looking through the source code now and finding out!

Benchmark

• On the command path/to/venv/bin/bril2json < birthday.bril | brilirs I kept getting an error error: Expected '1' function arguments, found '0', which was weird because I got an output fine for the manual input:

brili 23 < birthday.json 
0.50729723432398566

Not really sure what I was doing wrong, but it might also be correlated to the fact that generating the json always resulted in a duplication of the main function (although I suspect this could also be that a main function is always placed for every json translation regardless if it already exists.)

[ryanwmao]

@xalbt and I worked together on lesson 2.

Summary

Benchmark: quickselect
Tool: scramble operations

Implementation

Benchmark

• Referencing a previous implementation of the quickselect algorithm, we implemented the benchmark directly in bril (couldn't use arrays in ts2bril). Given an array of unsorted numbers and a number k, return the kth smallest number in the array
• We used an implementation of arrays from the bubblesort benchmark
• We had a few bugs initially, but bril print statements + rerunning the brili commands was actually pretty helpful in debugging
• The actual inputs are hard coded into the main function, but we tested using different inputs

Tool

• Our tool is a relatively simple program modifier that randomizes each of the [add, sub, mul, div] operations wherever they appear in the program. We use the random python module for the implementation. We tested the tool thoroughly using a command line pipeline along with several of the test files in the bril repository.

Difficulties

• Bril: manually writing the Bril file proved to be a bit difficult, especially because we weren't 100% familiar with the syntax. This led to some bugs later on when testing the file with brili, but there was enough information available between the brili output and print statements to properly debug the code
• Setup: we also ran into a few issues with setting up the tools, but this was due to not following instructions closely
• Time: we did not allocate enough time to explore more interesting tools, but we hope to avoid this issue in the future
• We did not use any generative AI for our submissions

[zachary-kent]

Summary

• Quicksort with Hoare Partitioning
• Add to Mul Converter

For my benchmark, I decided to implement quicksort using a Hoare partitioning scheme and median of three pivot selection. For my Bril transform, I decided to implement as pass that would transform all Add instructions into Mul instructions while keeping their destination and operands the same.

Implementation

Benchmark

• I implemented quicksort using a hoare partitioning scheme, where you maintain that the "left" half of the array is less than the pivot and the right half of the array is greater than the pivot. Having had these loop invariants burned into my mind since CS 2110, this was actually not too bad.
• Unfortunately, I discovered that the TS frontend did not support Arrays (yet!), so I had to implement this by hand. This was also probably the most difficult part of these tasks, as the Rust interpreter is often unforgiving to syntax errors. Surprisingly, however, once I ironed out all of the Syntax errors, I did not actually have to debug my code.
• I added a small "test" by generating 5 arrays with 50 pseudorandom elements and then writing a function that would scan through the arrays after sorting them to ensure they were in non-decreasing order. Of course, this does not preclude the possibility of other faults (such as duplicating elements), but it did provide me with some confidence.

Bril Transform

• I was originally working on a Coq library for Bril, but eventually realized it would not be feasible to complete by the time this task was due (I probably realized too late -- hence why I'm typing away furiously now). It did give me a good foundation for future work, however, and I'm excited to complete it soon!
• I then pivoted to implementing a transform that swaps all add instructions with multiplication instructions, which was fairly easy to complete--the OCaml Bril library is quite complete.
• I tested my implementation using the turnt tool; I included a Bril program containing a couple functions with add instructions, and ensured they were all changed into mul instructions. Although this test was quite small, I do believe it achieved good coverage as well.

[MelindaFang-code]

Summary

sampsyo/bril#262
Bril analysis Tool

Implementation

I wrote a function to reverse the digits of an integer (for instance from 123 to 321).
Normally if we want to implement this function in python, it is intuitive to use the % operator to get the remainder from division by 10. However, this operator is not supported in bril, so I have to do it in a slow way: say I want to reverse A, I will first get a = A // 10, and then the remainder r = A - a * 10.

For the analysis tool, I choose python and use the json file of the 8-queens problem as an example. My analysis script would keep track of all the labels in one program, grouped them by the function in which they appear (key = function name, value = list of label names), and print them out. For the return value I sort everything in alphabetical order. In this way I can guarantee that for how many times we run the script the result would be the same.

Difficulties

The first difficulty is to set up the bril tool. My python environment and path variables do not seem to be set up properly and I have problem when running the commands, so I have to figure out where the python scripts are installed and figure out the linking issue.

The second difficulty is to get familiar with the bril tool and figure out how to implement the task. I first tried to use the existing typescript compiler to generate bril code, but the compiler is quite limited and could not translate my code correctly (for instance it keeps complaining about unsupported types) After trying to debug the typescript compiler for a while I start to write bril program by hand, which turns out to be much easier.

[jiahanxie353]

Summarize what I did

1. Wrote a bril program to count the majority element and made a pull request to benchmark
2. Implement a simple function to count the most frequent control op in a bril program

How do I know my implementation works

1. My implementation for the majority element uses Moore's voting algorithm, which isn't very sophisticated but I found it very elegant. Since the program is not large so it's easy to debug if have any. I crafted some test cases, small and large, including some edge cases. And I'm convinced that my implementation is correct.
2. For the second implementation to count the most frequent control op in a bril program, I randomly copied some test cases in the repository. I also wrote some special case tests, such as there exists tiers, or there is no control op at all, etc. By passing these test cases, I'm pretty confident that my implementation is correct.

Difficulties
I found some learning curves to set up bril tool and learn to write programs using bril, since it's more assembly like