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.

[scober]

Benchmark PR: sampsyo/bril#356
Bril tool: https://github.com/scober/cs6120-lessons/blob/main/l2/analyzer.py

My benchmark was a 5-input sorting network. For those who aren't familiar, a sorting network is a way of sorting fixed size inputs using a static arrangement of "comparators" that compare two values and swap them if they are not in sorted order. For small-ish inputs (like 5) it is possible to identify the fewest possible number of comparators needed for a correct sorting network and my network is optimal in that sense (AFAIK). I built it using the typescript compiler and the first thing I learned was that the warning that the ts compiler produces inefficient code was an understatement. My bril code has multiple instances of this pattern:

vi: int = const n;
vj: int = id vi;

Otherwise I found the process to be pretty painless. My code works (on a few inputs) and the tools mostly work as advertised.

My Bril tool outputs basic blocks and cfgs (in graphviz format, shout out to the lesson 2 videos) and my "do any other thing" thing was to print some basic descriptive statistics about programs. Number of functions, number of labels, how often different opcodes appear, that sort of thing. That effort brought home for me what Adrian means when he talks about this sort of assembly-like IR being "regular". For simple questions like "what percentage of all instructions are function calls?" it is just a little easier to traverse a list of instructions than it would have been to traverse a syntax tree.

I think my biggest challenge was probably wrapping my head around turnt. It took me a while to realize I could use environments with different output files to define different sorts of tests on the same files. I also missed the ability to programmatically generate tests. A small sorting network can be more or less exhaustively tested and while the number of tests is not prohibitive if you can generate test cases on the fly, it is a very inconvenient number of tests if you have to generate a file for each one. My other lingering complaint with turnt is that it identifies the output of a program with its correctness. For the sorts of human-readable tools I was developing for this lesson, it would be nice to separate the formatting of the output from the content of the output. That being said, I can already see the appeal of snapshot testing and I think I just need to reframe how I think about testing.

[sampsyo]

This all looks great; nice work, Simon! And yeah, snapshot testing is a weird philosophy unto itself—makes sense that it would require some adjustment.

[gerardogtn]

Benchmark PR
Transformation script
cfg algo

For my benchmark I chose Conway's Game of Life Game. I first started by generating a random nxn matrix from a seed (inspired by mat-mul.bril) but with a couple modifications (improved values for a m and c to increase period length and using a modulo operation that doesn't generate negative numbers). Then i implemented the game of life game by writing some handmade bril code, which required a bit of debugging to make sure that indices were being accessed correctly. Finally i printed out the output matrix. For testing, I ran the gol algorithm on a couple of different generated matrices to make sure that the output was what I expected.

For my bril program transformation, I choose the problem of assigning unique, mnemonic, fixed-character-length variable names to all variables and arguments in a bril program (supports up to 1,000 transformations), like plum-glass-camera (they all follow the pattern color-material-item). I used Kotlin for the script and used Moshi for parsing, which was useful to become more familiar with Bril as i had to model all nodes as json classes, but required the use of custom adapters for a few types and turned verbose relatively quickly. For testing I used a diff tool and compared the output json of different bril programs (the json was formated using jq and with keys sorted), and made sure that only variable names and args where modified and to make sure that they matched any changes from when vars/args were used in any instruction.

Finally, I implemented the basic blocks and cfg algorithms that we covered in class, using all the infrastructure I used for parsing for the program transformation. This wasn't too bad, the biggest difference from the lecture notes is that i relied on block ids of type int instead of strings; which meant that my cfg was a dictionay from int to a set of ints, instead of showing the labels of the blocks. I tested it out in a couple of different bril programs to make sure that it was behaving as expected (tests helped me fix a bug where i was including empty blocks).

The hardest part of the assignment was to debug the bril benchmark, as I relied on a lot of printing statements (with ids and locations that helped me identify up to which point the program ran without failing). I do think that i deserve a michelin star.

[sampsyo]

Really nice work! The Game of Life benchmark is definitely creative. 😃 And I like these funny mnemonic names!

It probably doesn't make sense yet, but if you ever end up developing anything interesting reusable for working with Bril from Kotlin, maybe we should consider merging it into the Bril monorepo.

[UnsignedByte]

Benchmark

PR, Source

My benchmark was a general matrix multiplier on binary matrices in pure base bril (no extensions), which I built by hand. This means that each element of a matrix is a single bit, 1 or 0 in the field $\mathbb F_2$. Binary matrix multiplication can be seen as doing normal matrix multiplication followed by a parity check. The function takes the two matrices a and b as integers where the values in the matrix are packed. This packing is done in row-major order and from lowest to highest significance, meaning the top left $(0, 0)$ in the matrix is represented by the least significant bit, and generally $(a, b)$ is represented by $a\cdot c + b$ where $c$ is the number of columns in the matrix. The function additionally takes 3 arguments representing the dimensions $n, m, k$ such that $a \in \mathbb F_2^{n \times m}$ and $a \in \mathbb F_2^{m \times k}$.

The algorithm was pretty interesting mainly due to the lack of bitwise logic functions in base bril, which meant that in order to check for parity I had to use integer division quirks to check for oddness and evenness, namely by checking whether n/2 == (n+1)/2. Additionally, in order to check bits at certain locations within the matrix, I had to hand-implement some divide-by-two loops that would return the ith least significant bit in an integer, and a simple pow2 loop to take powers of two. I believe both of these would have been easier with recursion instead, but loops seemed more interesting to implement.

The bulk of the algorithm does a very basic O(nmk) matrix multiplication, looping through each pair of row and column and performing dot products, then storing the parity of the result in the output matrix.

Tool

Source

For my program transformation, I wrote a simple script that inserts an instruction counter into every function that increments a variable at each instruction, and prints the total instructions ran whenever exiting the function (before all returns as well as at the end of the function). Additionally, it removes existing print statements to avoid clashing of outputs. For input sanitization, it also detects whether a given input filename is .bril, in which case it runs bril2json to convert it to json before doing further processing.

Testing

Config

Testing was done using a very simple set of turnt environments, one which ran the function and checked stdout for the expected print statements, and another which ran my instruction counting tool. Testing can be run automatically using make test.

Conclusions

I would say the most difficult part of this task was definitely handwriting bril. I have a fair amount of experience writing LLVM but the restrictiveness of bril's instruction set made a lot of simple processes more difficult than I expected, mainly when dealing with bitwise operations, which unfortunately my idea had a whole lot of. Some of my workarounds definitely felt like reinventing the wheel but poorly, especially as computers are usually great at bitwise logic. Additionally, as I had no access to dynamic memory allocation this also limited the scope of what I could do, for example when implementing pow2 I decided to just go with a simple naive implementation rather than a DP approach which would have been much faster. I was also used to SSA so being able to redefine variables required a bit of a perspective shift for me. As for Michelin Stars - I would be inclined to say the benchmark algorithm is deserving of one mainly because I hand-wrote it in bril rather than using an external compiler; although I will admit the testing and tool portions of the task were much simpler and also took me much less time.

[sampsyo]

Very tricky work on the benchmark! Maybe this is the excuse we need to add a bitwise-op extension to Bril… not many people have needed that before.

[mt-xing]

Benchmark PR: sampsyo/bril#362

Implementation: https://github.com/mt-xing/cs6120/tree/main/l2

My original plan for my benchmark was to implement the legendary Quake 3 Fast Inverse Square Root Algorithm using Bril. Unfortunately, I found that Bril does not support re-interpreting the bytes of a float as an int and vice versa, which is the crux of the algorithm's speedup. Through discussions on Zulip, I found that one of my peers has already submitted a PR to add this functionality to Bril, so I decided to keep this benchmark in for future use. In the meantime, I also added a second benchmark that uses the far less fun Newton's method starting at 1 / x to compute the same inverse square root.

My Bril analysis tool counts the number of unique variable names declared in every function of a program (not including arguments). This is written in TypeScript and can be run with Deno. It is inside the analyzer folder and can be run with, for example, deno --allow-read=. countVar.ts .\lamefastinvsqrtExtra.json. To test this, I took my lame fast inverse square root calculator and added a bunch of extra methods. Using the existing nontrivial code with jumps and branches was useful as a baseline, and then the extra methods tested edge cases, including a function with no variables, with exactly one variable, where the variables shadow previous declarations, and where there are arguments but no variables. All of this is snapshot-tested with Turnt, and the goal is to ensure that I have coverage both of normal use cases but also as many edge cases as possible.

My CFG algorithm is in the cfg directory and is also built with TypeScript / Deno the same way. Run it with deno --allow-read=. cfg.ts .\lamefastinvsqrtLabels.json. I basically just transcribed the algorithm I wrote in class with minimal changes. I did add a pass to the block creation that removes empty blocks that don't have any labels; this cleaned up the last dangling block I had, as well as if the first block is immediately ended by a label. My CFG is a mapping from blocks to sets of blocks, and the labels are not stored in the blocks themselves, instead being passed in as a separate map. Any block that does not have a mapping is implicity pointing to the exit of the CFG, and the entry point is the first entry in the map from an empty array. This was also tested against a modified lame fast inverse square root calculator, this time predominately adding a bunch more labels. The edge cases exploited here were when there is a label at the top of a function and when there are multiple labels in a row with no commands between them. The branches and jumps inside the existing code served to round out the tested scenarios. This was also tested with Turnt.

The hardest part was figuring out how to set up the environment and the Bril syntax. Most of the instructions do not work on Windows, and while I was able to figure out everything involving Deno, as far as I can tell, Flit just does not work on Windows at all, and I ultimately had to use WSL to get the bril2json working. The other difficulty is that I could not find the syntax for the .bril files documented on the official website. I ultimately looked at existing benchmarks inside the repo to figure out the syntax of the format.

I believe this work is worthy of a Michelin star because one benchmark pushes the boundaries of what Bril can do, and on top of that I went back and wrote a second benchmark that runs on the current capabilities of Bril. These benchmarks were all written by hand in Bril. On top of that, the implementations were all tested against a battery of edge cases and I even wrote out type annotations for the parsed Bril JSON, so that the TypeScript isn't just using raw any objects.

[sampsyo]

Hey, Michael—sorry about the Windows trouble. Unless you're content with just using WSL, any chance you can point out any specific places where the instructions were too Unixy?

About Flit in particular: I'm surprised it doesn't work on Windows, but FWIW I did update the instructions to recommend uv instead, which should be a little easier to get going on Windows.

The other difficulty is that I could not find the syntax for the .bril files documented on the official website.

Here's the docs page for the text format. Is that missing something you'd find helpful?

and I even wrote out type annotations for the parsed Bril JSON, so that the TypeScript isn't just using raw any objects.

If you like, there is a more extensive version of this in the Bril monorepo that you can feel free to use:
https://github.com/sampsyo/bril/blob/main/bril-ts/bril.ts

[neel-patel-1]

Benchmark/Tool
I wrote a benchmark in bril that creates a non-cryptographic hash (fnv1-hash) of an array of integers which are allocated and freed using the manually managed memory extension:
I also created a python tool that groups instructions in a bril program into basic blocks, assigns them names according to their label (if they have one), and creates the control flow graph for the program.
The tool reports the number of functions, total number of basic blocks, and number of edges in the CFG. It also prints the mappings from predecessors to successors in (PredecessorLabel, SuccessorLabel) format, which is not useful for visualization, but could be used for optimizations that use the CFG representation of the program. I also added a function for counting and reporting the number of add instructions in the program.
Instructions for using the tool and running the benchmark are in the repo.

Validation
To validate that my tool worked, I used turnt to produce the outputs for all of the core benchmarks in the bril repo. I manually validated the outputs for the first 6 programs and my own benchmark.
The tool works for programs where the labels are used to indicate the target of a br or jmp instruction. For programs that use labels for other purposes, the tool reports additional basic blocks -- one extra basic block for every superfluous label.
Otherwise, I was sufficiently convinced in the tool's correctness, since the functionality it implements is simple -- counting basic blocks, functions, instructions, and building a CFG.
The tools are fully implemented and tested. I think this work deserves a Michelin star for its top quality ingredients and distinct flavours.

[sampsyo]

All looks great; nice work!

I think this work deserves a Michelin star for its top quality ingredients and distinct flavours.

🥣

[bryantpark04]

Benchmark

The benchmark I wrote sums up all of the digits of an input integer and prints the sum. It was slightly challenging since Bril doesn't have a modulo instruction, so I had to approximate with a division-multiplication-subtraction instruction sequence. The input arg I defined for the turnt testing was 1234567890. I chose this number because it has all 10 digits. After verifying that the Bril program outputs 45, I was convinced of my program's correctness.

Bril tool

My Bril tool outputs the number of labels in a Bril program. I wrote it in TypeScript. The initial idea for this tool was to modify the Bril proram to print out the name of each label reached; however, after getting through 80% of the implementation I realized that printing out a string would be a lot harder than I had originally reckoned, so I switched it to just counting labels. To test it, I selected sample Bril files from benchmarks/mixed and test/parse, and manually counted the number of labels in each program. Then, I used turnt to save outputs from running my tool on each test file and made sure that the outputs matched what was expected. I initially had my tool take a filename as a command-line argument, but decided to change it to ingest Bril JSON from stdin. I was trying to read from stdin in a way that ensured that a huge JSON file would be completely read before attempting to parse it, and after I implemented this I looked in bril-ts/util.ts and found a helper method that did the exact same thing. Go figure.

I also implemented the basic block forming and CFG building algorithms in TypeScript.

I think my work deserves a Michelin star because my benchmark program had to circumvent the limitations of Bril not having a modulo instruction and my Bril tools were structured well for future extension, with common types separated from implementations and taking in input through stdin so that compiler stages can eventually be chained.

[sampsyo]

All seems great! Nice work on the artisanal, handcrafted modulus operator.

I was trying to read from stdin in a way that ensured that a huge JSON file would be completely read before attempting to parse it

Yeah, kinda wild that this isn't more straightforward in the popular JavaScript runtimes!

[KabirSamsi]

Benchmark

Link – Bril Issue #366

My benchmark is a DFS-based traversal to print and count all the connected components in an undirected graph. I designed this using the text representation of Bril; here I hard-coded an $n \times n$ adjacency matrix (here with $n = 8$), and for the purpose of setup, I manually added in a series of edges. Though not present within the benchmark, I have tested this by varying the nodes and edges, to good result. I experimented with randomization but found it a bit hard to work consistently with the pseudo-random generation code in Bril done on previous benchmarks. Here is a visualization of the primary graph that is used in my benchmark:

My implementation of the depth-first search algorithm is iterative, and thus relies on a stack. When I was initially implementing a benchmark, I felt that it would prove fun to try doing something unintuitive with memory, and experiment with creating an almost 'abstraction function' of sorts for Bril memory blocks. As a result, one fairly significant component of my benchmark involves implementing a stack abstraction in Bril, allowing one to freely push and pop elements from a memory block. Using Bril's memory extension, I implemented an abstraction for this, and then utilized the relevant push and pop functions to create a dfs function. Interestingly, I discovered an issue with storing 'empty' memory – that is, allocating no space to blocks of memory. This forced me to come up with a slightly scrappy albeit verifiably correct workaround for an empty stack abstraction.

The program ultimately prints out a series of integer sequences (each sequence separated by an empty line), representing each component; and finally an integer representing the number of connected components in the graph. This benchmark is stored under the mem subdirectory.

Tool

Link – Source Code

My tool is a program which scans through unique variable names declared in each program, and categorizes them by type. It then also counts the number of times that a given variable is referenced – that is to say, used 'on the right-hand side of another expression'. This was done via JSON parsing and iterative scanning in Python. I tested this initially on my own (rather large) benchmark, but utilized both turnt and the ubiquitous present benchmarks to verify the quality and consistency of the analysis. From a pragmatic standpoint, I feel that this could be a tidy tool in the early stages of Dead Code Elimination for simpler programs – cleaning up variables which aren't used at all. (In part, this is what drove my somewhat flawed discussion today morning 😁).

Below is an example of analysis for one function (from my benchmark):

CFG

Link – Source Code

My CFG-generator algorithm is developed in Python in the same directory as my tool. I implemented rough algorithms for blocking and CFG generation when we initially discussed potential algorithms; subsequently, I have since polished them up and included them in here. As with the tool development, I found the JSON-Python connection to be wonderfully straightforward. It was helpful again to test the implementation against a large subset of the programs within benchmark. As with my tool, I initially developed primarily using my own benchmark (since I was the most familiar with the program flow), but soon migrated to others as well. Such an example of a small CFG (in Python dictionary form) is below:

Insights

Amusingly, I found perhaps the hardest challenge of this task to be setup. My Bril setup has been somewhat inconsistent – notably, shutting down my system resulted in certain libraries/variables being reset (?) though I'm sure there's a more logical explanation for this. Optimistically I feel that I could have taken half the time I did on this had my setup been a little more firm.

I was pleasantly surprised to find that I have been able to pick up the Bril syntax fairly quickly. I contrast this to my experience with other IRs (for example, CAPRA's Calyx IR) with which I had a steeper learning curve (but in many senses, the syntax here is much easier). All the same, I felt that the benchmark in particular allowed me to really get in touch with a lot of syntax, and I am excited to continue to work with it! I found the tool fairly straightforward to develop, with Bril's JSON representation easy to work with and test. But I most definitely feel that it will prove fun to work more with Bril in the future, both as a target IR and as a tool to write more programs in the future!

Overall, I would say that I think that I do earn a Michelin Star for this; my Bril benchmark especially did allow for a rich exploration of the IR, along with a few interesting steps with the memory extension. I also felt that my tool has built nicely on the concepts we have covered so far, including briefly touching on some of the concepts covered early today.

[sampsyo]

Interestingly, I discovered an issue with storing 'empty' memory – that is, allocating no space to blocks of memory.

I assume that the "issue" you're referring to is that the reference interpreter, brili, crashed when allocating this zero-element region? I would really like to nail down a semantics for this either way—maybe we should prohibit it, or maybe we should allow it (and fix the interpreter). Perhaps we should see what the other interpreters do, for example?

One nasty consequence of allowing zero-element allocations would be that the returned pointer would already be invalid. But maybe that's OK, because we already allow invalid pointers (it is an error to dereference them).

notably, shutting down my system resulted in certain libraries/variables being reset (?) though I'm sure there's a more logical explanation for this.

What were the symptoms, when this happened? Maybe we can sort out the problem for future students and make the instructions more bulletproof.

[KabirSamsi]

I was able to recreate the zero memory error more clearly! Here's a simple Bril program for example:

@main() {
  zero : int = const 0;
  empty : ptr<int> = alloc zero;
}

Which compiles, but fails to execute with the following message:

For something like this, my understanding if that compilers like javac would just store empty arrays on the heap. So I'm not sure if that's something of interest? At any rate, unless one plans to create a mutable array interface like I did here, empty memory blocks aren't all that useful. But I still think that it could be an interesting venture.

What were the symptoms, when this happened? Maybe we can sort out the problem for future students and make the instructions more bulletproof.

It's a bit hard to demonstrate visually, but essentially, every time I restart my environment (e.g. terminal, VSCode), the brili command is no longer accessible. So I reinstall it with deno, add it to my PATH and things work fine after that. Here's an example below:

(The issue with bril2json seems to have resolved itself somehow, but the brili one persists).

[sampsyo]

Got it; thanks. To add something permanently to your $PATH, you will want to edit your shell configuration, like this:
https://stackoverflow.com/a/11530176/39182

[ananyagoenka]

Benchmark:
Source: sampsyo/bril#357
For my benchmark, I implemented recursive Fibonacci in Bril by writing the Bril code by hand. Since Bril doesn’t optimize for recursion, this serves as a good test for function call overhead. Writing the benchmark manually helped me get a better understanding of Bril’s instruction set and control flow. I tested it by running the function on small values like fib(5), fib(10), and fib(15), verifying the outputs against expected Fibonacci numbers.

Tool:
Source: https://github.com/ananyagoenka/cs6120-lesson-tasks/tree/main/l2/debug_jumps_in_bril!
For my transformation, I built a print statement injector that adds print statements before every jmp and br instruction. This makes control flow much easier to track when running Bril programs. The implementation parses a Bril JSON file, finds all jumps, and inserts a print before each one. I tested it by running transformed programs and checking that the modified output still preserved program behavior while providing additional execution trace information. Turnt helped automate testing, but setting it up was more involved than expected—making sure .out and .prof files matched the expected outputs took a bit of tweaking.

For basic block formation and CFG construction, I followed the standard approach of identifying block boundaries at labels, jumps, and function entry points. The biggest challenge was making sure fallthrough edges were handled correctly, especially for blocks without explicit jmp instructions. Debugging this helped reinforce how Bril programs execute, and once fixed, the output matched expectations.

Turnt was definitely the most challenging part of this assignment. It works well once set up, but it feels rigid in how it ties output to correctness. Formatting changes can cause tests to fail even if the transformation is functionally correct, and I found myself wishing for a way to separate formatting from actual correctness checks. I also see the appeal of snapshot testing, though—it forces you to carefully track changes in program behavior, which is useful for verifying transformations.

Overall, I think this turned out well. Writing the benchmark by hand was a good exercise in working with Bril directly, and the print injection tool makes debugging easier. CFG construction was satisfying once all the edges lined up correctly. Now that Turnt is set up, it should make testing future transformations much easier.

[sampsyo]

All looks good; nice work!

Turnt was definitely the most challenging part of this assignment. It works well once set up, but it feels rigid in how it ties output to correctness. Formatting changes can cause tests to fail even if the transformation is functionally correct, and I found myself wishing for a way to separate formatting from actual correctness checks.

FWIW, frequent users of snapshot testing usually rely on frequently doing turnt --save or the equivalent, to adapt to minor changes in formatting. Then using git diff suffices to show you that the changes were actually minor. For bonus points, git diff --word-diff can help adapt to a lot of minor changes that would otherwise cause diff noise.

[gabizon103]

Benchmark: source
My benchmark implements the CORDIC algorithm, which is more common in hardware than software but I thought it'd be a fun benchmark because it does something non-trivial (computes the sine of a number) and uses language features like loops and pointers. I couldn't get ts2bril to emit bril that uses pointers, loads, and stores (it might be unimplemented, I didn't look too hard). I took that stuff out of the algorithm, generated the bril, and then wrote the parts that use pointers by hand. I tested it with a few different numbers, but hard-coded the input in my PR just for simplicity. Programming in bril is like programming in assembly without worrying about a specific ISA's quirks with memory/super-specific instructions, which is about what I expected. It's pretty tedious and probably untenable for large programs, but not impossible.

Tool: source
I wrote the algorithms to construct basic blocks and a control flow graph for each function in a bril program, using the bril-rs infrastructure. I took some time to figure out how the infrastructure was set up, but it was pretty easy to follow and use. For fun, I also wrote some code to turn a cfg into a visual graph using graphviz. This was pretty helpful for verifying that my algorithms were correct, and I thought it might be helpful for future assignments if I want to examine the results of an optimization in a different way. Here's the output for ackermann.bril:

My actual tool is just something that walks over the CFG and counts the in-degree of each basic block. This includes when the block is the target of a jump or branch, and also when it is the destination of some fall-through edge. I thought this was simple enough and could be an interesting analysis to do. It tells you a bit about how a program is structured. I tested it pretty much manually using most of the core bril benchmarks, and set it up to use turnt afterwards just to see how it works.

To run the tool to generate the graph, run bril2json < {input_filename} | cargo run -- -o {output_filename}
To generate the block target numbers, run bril2json < {input_filename} | cargo run -- --stats}, and they will get printed out.

I think I deserve a star because I implemented what was asked, plus some extra stuff. I tested things thoroughly enough to expose and fix some bugs, and convinced myself that it works.

[sampsyo]

Really cool, Ethan! The CORDIC sine implementation looks tedious to write indeed, but the outcome is rad. 😃

[dhan0779]

Benchmark PR: sampsyo/bril#354

For my benchmark, I implemented a simple permutation function P(n, k) which represents the number of possible permutations of k objects from a set of n. This benchmark also uses a factorial function to easily calculate the permutation, so I initially wrote both a recursive and iterative method to see how it's converted to different representations. The permutation function was tested with smaller numbers such as n=6 and k=3 (output=120) for validation.

Tool: https://github.com/dhan0779/cs6120-impl/tree/main/l2
For the tool, I created a python script for printing all constants that are in a Bril program. It iterates through all instructions in the json, and identifies each instruction with the 'op' == 'const'. Then a new print instruction is added using the instr['dest'] and instr['value'] to create a print operation. When the script runs, there's an additional Python print that outputs all the constants as well to make sure all are identified.

Basic Block/CFG: https://github.com/dhan0779/cs6120-impl/tree/main/l2
Writing the basic block algorithm was pretty interesting and it helped me to gain a better understanding of how Bril json is represented. I used the videos on the course website to construct the implementation of the algorithm and most of it was pretty straightforward.

For constructing the CFG, I created a map to give a name for each block to make it easier to identify edges and nodes using the 'label'. There are some cases where the list of basic blocks are empty or don't have explicit terminators, so handling those were probably the trickiest part of this. I manually checked the CFG to make sure the edges made sense for each function using the benchmarks.

I think the hardest part of this assignment was setting up turnt. It wasn't too complicated after messing around with the different parameters, but I think getting it to work the first time took a while. Overall, I think this work deserves a Michelin star since I really familiarized myself with Bril/turnt and tested my implementations on multiple benchmarks.

[sampsyo]

Awesome; looks great, David!

[emmanueljs1]

Code:
Benchmark
Tool
Basic Block Building/Computing CFG algorithms

Summary:

• Benchmark: I wrote a program that shuffles a list until it is sorted ("bogosort"), mostly because I thought it would be fun to write. I used the LFSR implementation written in another benchmark to generate pseudorandom numbers for my shuffle function.
• Tool: I wrote a program that adds a jump to the next label for every label in the program. I thought this would be a nice way to "preprocess" a Bril program before building basic blocks because it would guarantee all blocks end with a jump.
• Basic Block / CFG algorithms: I took the code I wrote for my Bril tool and modified it to instead build basic blocks and compute a CFG from a Bril file. I ended up not using the tool itself as a preprocessing step when writing an implementation of the algorithms, mostly so that my basic blocks / CFG correspond exactly to the original Bril program (which I ended up finding easier to debug).

Correctness

• Benchmark: As part of my benchmark I actually let someone run the program with a list of 5 numbers to be sorted, as well as a seed from which to start generating random numbers. The program prints out the sorted list, or fails after 100 attempts (otherwise technically the program could loop forever since this is a randomized algorithm). I ran the program with a few different 5-element lists and seeds and the program succeeded at sorting all of them, so I was fairly certain my program was correct!
• Tool: I used turnt for a command that would translate a human-readable Bril file into JSON, run my tool on it, and then output the corresponding human-readable Bril code. I ran this command on a few test files that represented edge cases (e.g. no labels) and one for the average case (some labels). I committed my average case, but didn't save its output.
• Basic Block / CFG algorithms: My code prints out the CFGs of all functions in a Bril program. At this point I was more familiar with turnt so I wrote a few different test files and tested all of them with turnt -p to see that the printed out CFGs corresponded with what I would have expected them to be.

Hardest Part
The hardest part was getting used to the Bril ecosystem and trying to write my benchmark, especially because I spent a significant amount of time writing the benchmark in Typescript (it was hard to tell what Typescript features were supported by the Typescript compiler). Eventually I switched to writing human-readable Bril directly and found it to be much easier (and at this point I had played around with the different Bril tools quite a bit so was more familiar).

Grade
I think my work deserves a Michelin star. I worked hard on my benchmark and wrote my Bril tool / CFG code so that it is extensible and I can keep using it in future lesson tasks.

[sampsyo]

The bogosort implementation is a VERY fun idea for a benchmark; nice work! And yeah, it would be a good test case if anyone ever needed a loop that could run a really large number of times, if anyone needs that. :smiley.

I spent a significant amount of time writing the benchmark in Typescript (it was hard to tell what Typescript features were supported by the Typescript compiler).

Yeah, it's super duper limited, and we haven't spelled out those limitations clearly anywhere. That would be nice to do someday… but I guess it's not clear whether time is best spent on that or on just adding features to the compiler.

[samuelbreckenridge]

benchmark
source

My benchmark implements modular exponentiation using the right-to-left binary method. To create it I first converted pseudocode I found on Wikipedia to Typescript, then used ts2bril to compile this to bril. Getting this working was probably the hardest part of the task as it took some trial and error to figure out what functionality was supported by ts2bril and the bril core language. For instance I had to replace the mod/bitshift operators and while loop I had initially used in my Typescript code and edit my code to not evaluate a function returning an int in the condition of an if statement as this produced a type mismatch error in bril. I found this debugging process to be very valuable in getting me up to speed with the bril core language features.

My tool is a Python script that reads in a bril program and outputs some basic statistics on the variable name usage of the program (unique variable names, total variable uses, top 10 variable names). It does this by iterating over all instructions and using a Python Counter to track occurrences of strings in either the dest or args field of instructions.

The implementation of the basic blocks and CFG algorithms was pretty straightforward based on the pseudocode we came up with in class. The one thing I had to think about a bit was how to handle labels, I ended up leaving labels in the basic blocks rather than storing them in a separate data structure which I think is nice to keep things simple, but might be a bit annoying in cases where you want to assume all instructions in a basic block have ops.

I did my testing using turnt, which I quite like. I can see it being annoying in some cases to have correctness tied to the output format but very much appreciate the simplicity and flexibility of the .toml config file. For my tool I used a few bril tests/benchmarks as inputs and manually counted variable usage to be sure the output was correct. For my CFG I started by testing on the programs we looked at in class, then moved on to using a few benchmarks with more complex control flow. Testing on my mod_pow benchmark revealed a bug where two consecutive labels with no separating instruction caused my implementation to crash, so I was able to fix this.

I think my work deserves a Michelin star because I familiarized myself with bril core features and associated tools beyond what was necessary and my implementations are clean and appropriately tested.

[sampsyo]

Awesome; this all looks great!

It does this by iterating over all instructions and using a Python Counter to track occurrences of strings

I love that Python stdlib Counter class. So convenient for so many things!

[zihan0822]

Benchmarks

benchmark PR, source

I tried to think of benchmarks that are heavily recursed. My first trial a classic Hanoi problem but I later found that it has already been implemented in previous semester. I then did another path counting benchmark, famously known as delannoy number, which counts the total number of paths to reach the goal given that only three possible moves are allowed. It was implemented recursively without memo. Those bril programs were compiled from typescript.

Tools

source

My bril analyzer tools are a simple operation counter and a cfg visualizer written in Rust. The input bril json is first deserialized into its Rust counterpart and then traversed to get the necessary op statistics and cfg information. The counter simply tracks the number of occurrences of each op type. The cfg finding algorithm is a full fledged version of the one I wrote in class. It involves two passes: i) chunk instrs into basic blocks and associate blocks with labels; ii) connect those blocks with edges. The final cfg can be converted to dot format for graphviz rendering. Some of the edge cases have been taken care of, for example consecutive labels, there might be basic blocks contain only label but no instrs (found in bril compiled from ts program with nested if-else statement). Tools have been tested thoroughly with turnt on existing codes in bril/benchmark. I manually checked the correctness of the cfg for some the programs with complicate control flow. Here is one sample output of cfg graph for primes-between benchmark

Conclusions

I would say the most challenging part is to actually write a typescript program that can be compiled into bril. I found some of typescript semantics that are supported by current ts2bril. I think I deserve a Michelin star because I familiarize myself of with bril infrastructure and have convince myself my tools work with thorough test on bencmarks.

[sampsyo]

Looks fantastic all around!

[parthsarkar17]

CFG & basic blocks implementation
Program analysis tool
Benchmark

For this task, I wrote a tool to build a list of basic blocks and construct a control-flow graph, I wrote a trivial analysis tool to count the number of instantiated const variables in a bril program, and I wrote a 1d-convolution benchmark.

Basic Blocks & CFG
I wrote my implementation of these two algorithms using the JSON functionality and data structures provided inbril-ocaml. While writing my algorithms, I also wrote helpful functions that can print out a program's BBs and CFG to the terminal. This helped me verify that the right basic blocks were being produced in the correct order, and the successor labels of each BB were as expected. While I was developing the algorithm, I used the same program that Prof. Sampson used in his video lectures (jmp.bril). After I had finished, I dug into the printed outputs for the bubblesort.bril and eightqueens.bril benchmarks; all of the (many, haha) basic blocks and CFG transitions are as expected. I'm convinced my implementation is correct because both of these designs have good amounts of complexity: there are a lot of basic blocks and a great deal of jumping around between basic blocks.

Counting consts
This was a simple analysis function to actually write. Just to be sure that it was working, I set up a turnt framework as asked, and tested the tool on dot-product.bril in the benchmarks directory. I then manually counted the number of consts in that program and validated them against the number in the .out file.

Benchmark
My benchmark is a 1-d convolution operation. It generates an array and a kernel (the sizes are up to the user, but kernel should be smaller ofc), and feeds these into the convolve function. This function then loops through the array, applying the kernel and producing the entries of the output array. I wrote this by-hand in order to get familiar with Bril. I am convinced this is a correct implementation because I tried out the algorithm on a variety of array/kernel sizes, and they all produced a correct-length output with the right entries.

Writing the benchmark was also the hardest part of this task for me. Figuring out the convolution algorithm should work (e.g. ensuring correct indices of the kernel, array, and output, and producing the result in each index of the output) took some time, and then figuring out how to map that abstract algorithm onto an assembly-adjacent language was another layer of complexity. I was also nervous that I'd introduce some inconspicuous bug that would be impossible to debug... that almost happened but thankfully an easy fix. The upside is, I feel like I know the language well now! In the future, hopefully digging through program transformations we do won't be scary.

Finally, I think my work deserves a Michelin star due to my benchmark implementation and my methodology in visually testing my BB & CFG implementation.

[sampsyo]

Excellent! Exactly as you say, the idea with getting you to write a benchmark was to get you comfortable with the Bril language and its quirks. Hopefully, you do not need to write many more Bril programs by hand for the rest of the semester. 😃

[ngernest]

• Benchmark PR
• Repo for Tool + CFG Algo

Basic Blocks & CFG Algo
I implemented this algorithm in OCaml, in a (mostly) purely functional manner. The hardest part was figuring out how to translate the use of generators & imperative language constructs (e.g. loops) in the lecture videos into a functional program with immutable data structures. I overcame this challenge by translating loops to List.map & List.fold, using a mutable list when accumulating instructions in a block, figuring out when to update this list as List.fold traverses over a list of instructions. (IN the rest of my implementation, I relied only on immutable data structures.)

To test my CFG algorithm, I used property-based random testing à la QuickCheck (via Jane Street's ppx_quick_check tool) to check that certain invariants were upheld. For example, I tested that terminators (if they exist) are always the final instruction in a basic block, and that every block appears in the name2block map. This involved writing QuickCheck generators that generate random instructions, which was pretty fun! I also checked that my algorithm returns the same CFGs for the two Bril programs discussed in the lesson 2 videos.

I also implemented JSON serialization / deserialization from scratch, and also used QuickCheck to make sure that the serialization was done properly. I also defined a typed AST for core Bril in OCaml -- being able to pattern match on instructions was very helpful when implementing the CFG algorithm.

Adding Nops
I added a transformation which adds a [Nop] instruction after each instruction. This transformation is applied to every function within a Bril program. To make sure this change didn't break any programs, I tested this transformation on all the Bril files (where main takes in zero arguments) in the core interpreter benchmarks folder using Turnt.

Benchmark
My benchmark implements the Montgomery reduction algorithm for computing $ab \text{ mod } N$ efficiently (where $a, b \in \mathbb{N}$). To implement this, I manually translated the pseudocode in the Wikipedia article to Bril.

Idea behind the algorithm: for example, if $a = 7, b = 5, N = 17$, to compute (7 * 15) % 17 using the algorithm, we convert 7 and 15 to their Montgomery form $t$ using some appropriately chosen constants. The algorithm then takes advantage of some results from modular arithmetic to compute $ab \text{ mod } N$ efficiently. For this example, my Bril implementation returns the correct result of 11, which is the Montgomery form of 3 = (7 * 15) % 17.

I think my work deserves a Michelin star as I actively thought of new ways to test my code using QuickCheck beyond just using Turnt & unit tests (including writing QuickCheck generators for random instructions), and I built custom OCaml infrastructure for de/serializing Bril.

[sampsyo]

Wow! The QuickCheck approach to generating random instructions for testing is pretty rad. Nice job getting this to work!

[devv64]

Benchmark: sampsyo/bril#374
For my benchmark, I chose to compute a finite geometric sum using a formulaic approach. This algorithm takes in 3 parameters (a, r and n) and computes the following formula: S_n = a * (1 - r^n) / (1 - r). This represents computing the summation of a * r^=k for k = 1..n. The challenge with creating this was the learning curve of the bril ecosystem. It took me some time to learn how to use all of the tools. After getting over this initial hump, it took me some time to land on an algorithm to compute. Once I landed on finite geometric sum, it still took me some time to create the functionality in bril.

Bril tool: https://github.com/devv64/6120/blob/main/lesson2/analyze.py
My tool takes a stab at naive dead code elimination - I implemented the first iteration of dead code elimination from class today. This was not too complicated, especially stemming from the pseudocode. It was an insightful experience that helped me understand the structure of bril programs and get familiar with parsing/ manipulating them.

CFG: https://github.com/devv64/6120/blob/main/lesson2/cfg.py
This part is pretty standard, I followed along with the video lesson and it was really helpful!

Conclusion:
This was an enjoyable exercise. It took me surprisingly longer than I expected and I ran in to a lot of issues with the setup of different tools. After figuring out these technical details, I had a lot of fun figuring out the bril language and ecosystem. I also do not have much experience with programming languages so I think this exercise really helped to get the ball rolling. I believe I deserve a Michelin star for my efforts. Although my work is not overly complex, I spent a lot of time on it and learned a great deal by going through the motions!

[sampsyo]

Awesome; nice work!!

About this in general:

The challenge with creating this was the learning curve of the bril ecosystem. It took me some time to learn how to use all of the tools.

In case you have any suggestions about how to improve the docs to allow for an easier ramp-up, let me know!

[ethanuppal]

• Benchmark: ethanuppal/cs6120/lesson2/benchmark.bril. I don't have a PR because Bril doesn't support the instructions needed. I implemented and opened a PR for the extension.
• Tool: type inferer+checker at cs6120/bril-frontend/src/infer_types.rs

CI for all tests (there's a lot of them) passing! https://github.com/ethanuppal/cs6120/actions/runs/13065966149/job/36458272723

Benchmark

• I implemented the Quake fast inverse square root algorithm and tested it on a few inputs (I imagine it could be easily fuzz-tested) after implementing bit casting primitives in Bril.

CFG Builder

• I wrote the CFG builder in Rust and tested it against every single Bril file in the benchmarks directory by ensuring that my CFG parser+printer was a roundtrip nop. This is tested on CI using a simple parallel Python runner I cooked up.

bril-frontend

• I wrote a custom 3000LOC frontend library for Bril's textual format in a day.
• The AST uses lifetimes for the text and all nodes are wrapped in a Loc<T> deref type.
• Overall I'm super proud with how I designed the AST representation and parser. Extra care was put into good error messages and parser recovery.
• I also have a full pretty printer using my inform library for pretty-printing.
• I used expect testing on the lexer and parser (using insta; for both success and failures) as well as roundtripping on every single Bril file in the core benchmarks directly. This is also tested on CI using the same parallel test runner.
• TOOL: I wrote a type checker/inferer and tested it with expect testing using insta. I also tested it on all core Bril benchmarks using turnt (also on CI).

bril-lsp

• I wrote a language server for Bril using Bril-frontend (for parsing and type-checking) that supports autocompletion, hover, document symbols, and diagnostic reporting.
• I wrote Neovim and VSCode clients for the language server.

I think my works at least a Michelin star, following this definition:

indicating excellent implementation work, insightful participation, a thoughtful blog post, or a spectacularly successful project.

I believe these projects are successful and represent solid implementation work. I've spent over 20 hours working on them.

[sampsyo]

This looks awesome, Ethan! Very cool that a working LSP server came out of it.

[mariasoroka]

My benchmark PR: link
My Basic Blocks, CFG and an unambitious program: link

For my benchmark, I added a function checking whether a ray intersects an axis-aligned bounding box in 2D. This is a very common operation in ray tracing, except that everything has to be in 3D there. I used the slab method for it. Interestingly, I did not know before writing this comment that the method has a name:) I wrote the code in typescript first, translated it to Bril, and then spent a lot of time cleaning up the final code from all the intermediate variables (there were 79! unnecessary variables). I ran multiple tests to make sure that my modifications did not alter the code. This part of the assignment helped me to get more used to Bril syntax.

My small program is very simple. It finds all the labels for all the functions in the given program. I implemented it in python. The trickiest part was to get used to using turnt as a testing tool.

Finally, I implemented the algorithms for basic block detection and CFG computation. I based my implementation on the pseudocode that we wrote during the lecture. I run the code on multiple programs. I used examples from the lecture, fact.bril, and my code for the benchmark, as well as tests designed to specifically check corner cases like consecutive labels with no code in between. To make sure that the code is correct, I plotted the CFG using graphviz. That's what the output looks like for my benchmark:

When writing code, I routinely use copilot autocompletion to avoid retyping similar lines of code. For example, if I already have a line with t_x_min_num = x_min - x_ray_origin in the next line, it is enough to type t_x_max_num and then use copilot suggestion for the rest of the line. For some reason, copilot does not work for Bril code, but I did not try to do anything about that. For this assignment, I did not use any text prompts.

[sampsyo]

Awesome; this is a very nifty benchmark!

I wrote the code in typescript first, translated it to Bril, and then spent a lot of time cleaning up the final code from all the intermediate variables (there were 79! unnecessary variables).

This was certainly a valiant enterprise! FWIW, with the local optimizations you are writing this week, you could imagine automating some of this cleanup instead of deleting unnecessary variables by hand.

[Annacaro22]

Benchmark Pull Request: sampsyo/bril#363
My mini bril tool: https://github.com/Annacaro22/6120L2/blob/main/minibrilprogram.py

For my benchmark, I made a combination function, aka n choose k, defined on positive ints (I return 1 for n choose 0, and 0 for n choose k, n < k, and 0 as well for negative n or k). I tested this using turnt, using both expected inputs (ie 12 choose 3, 20 choose 10), as well as these edge cases where n or k is negative/0/n<k. One difficult thing was that I kept remembering more edge cases which I wanted to cover just in case someone inserted inputs which were not expected, and it depends on the specific definition you're using whether you want to define combinations as existing on negative numbers at all (I chose not to implement negative combinations for simplicity's sake as I was still learning to use bril; something to come back to later!).

For my mini bril tool, I counted the number of "significant" commands; this is arbitrary, but I defined "significant" commands as jmp, br, function calls, and labels. This was mostly to help me build up to doing the basic blocks algorithm, as obviously already having a program which tests for these commands would be helpful when trying to separate blocks based on them (I had forgotten that we don't use function calls as delimiters for our definition of basic blocks [shoutout to the zulip post clarifying this, saved me a lot of pain with the blocks algorithm]; I could have gone back and deleted the counting of function calls, but I thought it might be useful for a different definition of CFG which is interpracedural, so I left it). Parsing the json file was a real pain in the neck, especially for my brain which gets confused where there are more than three brackets []{} next to each other. Once I figured that out, though, it wasn't too bad. I tested this again using turnt, feeding in my combination benchmark as well as the nifty benchmarks and json files laying around in the bril repo. I don't really like turnt at the moment; I couldn't get it to work for my mini bril tool and it took me longer than I'd care to admit that it was because I'd named my file "minturnt.toml" rather than "turnt.toml". But maybe I'll come to love it with time.

The basic blocks algorithm and CFG algorithms weren't too bad, with the pseudocode and the json parsing work I'd already done for my mini bril tool. I had to make some design decisions for the CFG; I enforced that every block must have a child, so for leaves I just set them to have 'end' as a child. Also, it was annoying to account for blocks which might be unlabelled, like if there's a jump on line 20 that skips to line 30, and everything on lines 20-30 is inaccessible, but you still have to consider it a block. For the future when typing bril programs I will make sure to use labels liberally in order to perhaps save this pain for someone else. I just tested in the terminal for this one (my program prints the blocks and the cfg directly to the terminal, so it was easy to just test it there), using again the benchmarks and .bril files laying around in the bril repo; helped me catch a bug that I had missed when building up my cfg program using my own benchmark (which I used to test as I was building the program because it had a decent but not overwhelming amount of branches).

I do think I deserve a Michelin star because I tried to build a benchmark that would be genuinely useful for the future, and while my mini bril tool was mostly just for practice, my blocks/cfg file has the advantage of printing everything out very clearly so that it is very readable; I couldn't stand the long strings of brackets that it originally generated when I just returned my entire list of blocks, so I tried to get to as close to a "pretty print" as possible for the blocks, to at least make it manageable to read. I learned a lot about bril here, and put in a lot of effort to the code I am submitting.

[tean-lai]

Benchmark

Binpow Bril Program
For my benchmark, I wrote binary exponentiation that is as close to a tail-recursive implementation as possible. I'm thinking that this could be a way to benchmark tail-recursion, and thought this might be a good benchmark because this operation is probably used fairly often in real-world programs. There's also a small-helper function there that is called, so I'm thinking maybe this benchmark can test slightly for inlining too.

I tried to implement it in typescript and compile it with ts2bril, but I ran into some errors that I wasn't sure how to fix, so I pivoted to implementing the benchmark in Bril directly; I figured it might be good practice with familiarizing myself more with Bril.

I did some ad-hoc testing on the terminal with fairly basic inputs, but I tested even, odd, and zero exponents and it seems to be working.

Program Analysis

Count Mini-Tool
Dup Mini-Tool
For my analysis, I wrote two mini-analyses: one to count each type of instruction in the program, and one to duplicate each instruction in the program. The latter transformation is a little non-sensical though, considering stuff like returns and assignments would be a little redundant to dupe. I just wanted to do one that just did some basic analysis without any modications, and one with basic modifications. These would apply to every function in the program. I tried to make the program outputs pipeable.

Basic Blocks and CFGs

Code
I implemented basic blocks and CFG algorithms in OCaml. I tried to form the basic blocks based off of the algorithm in these slides, which were slightly different than covered in class, it's just a bit more conservative with making labels into a new block, only doing so if they are a target of a branch/jump. I printed the results for a few .bril benchmarks that had a decent amount of control flow, and it seems correct by inspection.

Conclusion

Getting things set up initially proved to be a bit tricky. Learning how to use a bunch of new tools incurred a bit of overhead. I underestimated how much time it would take to go through these things. This was pretty fun though. I found it quite interesting thinking about what makes a benchmark pragmatic. Implementing basic blocks and CFGs was a bit hard for me, I think part of it was that I was thinking very imperatively, and it just felt very unergonomic to implement those thoughts into OCaml. Also, I wanted to write my own function to convert a Bril json to an AST, but this ended up consuming a lot of time to hit all cases, and I eventually abandoned this approach. On the Michelin star, not sure if I deserve it since I did finish up a bit late, but I am pretty happy with my work overall.

[sampsyo]

Awesome; this looks great, Tean!

Getting things set up initially proved to be a bit tricky. Learning how to use a bunch of new tools incurred a bit of overhead. I underestimated how much time it would take to go through these things.

If there's anything we can improve in the Bril docs to make this easier for future students, let me know.

On the Michelin star, not sure if I deserve it since I did finish up a bit late, but I am pretty happy with my work overall.

No worries; you earned a star. 😃

[arnavm30]

Benchmark sampsyo/bril#376

I implemented Karatsuba algorithm for fast integer multiplication by hand in Bril. This involved implementing several small functions like counting number of digits, max, and modulo: functions that I typically take for granted in high-level programming languages. I was originally planning to use the Typescript compiler rather than hand-writing it, but I quickly saw the compiler was much more limiting. Hand-writing it also helped me get a lot more familiar with the syntax and semantics of Bril. To verify the correctness of my implementation, I used differential testing. I wrote a python script to generate 500 random integer pairs and asserted that the product of each pair were the same in python and in my implementation.

Tool https://github.com/arnavm30/CS6120-tasks/tree/main/l2/tool

I implemented a tool that swaps the arguments of add and multiply operations. Since these operations are commutative, the swap should not change the outputs of the programs. I verified the correctness by using turnt, which naturally worked well as the already produced .outs of the benchmarks could still be compared against directly. I ran against all the benchmarks in core/, float/, long/, mem/, and mixed/. All but long/function_call.bril passed, but that’s because it’s the only one with the .out file missing.
I spent some time trying to extend the tool to swap other things that should be equivalent, like simultaneously “swapping” the condition variable and branch targets for branch instructions; however, this was a lot less trivial than I realized.

Basic Blocks and CFG https://github.com/arnavm30/CS6120-tasks/tree/main/l2/cfg

My implementation of the algorithms to form basic blocks and then the CFG is heavily based on the discussion in class as well as the videos. Compared to the other tasks, this was harder to convince myself of its correctness. To gain more confidence in the correctness, I drew out the CFG of a few programs from benchmarks. I also compared the CFGs my implementation generated with that of the one generated in the playground. Moreover, I used turnt, which was helpful when I wanted to make some small as I could easily see if something changed from what I thought should be right.

I think this work is worthy of a Michelin star because the benchmark exercises a lot of the core capabilities of Bril, and I did a solid job on testing.

[sampsyo]

I wrote a python script to generate 500 random integer pairs and asserted that the product of each pair were the same in python and in my implementation.

Very cool! This is a fun way to do the testing for something where there is an easy reference implementation available (i.e., multiplication).

[katherinewu312]

Benchmark
Source

For my benchmark, I chose to compute the characteristic polynomial of a 3x3 matrix, although it is easily extensible to nxn matrices as well. The input is a flattened matrix, or an array of 9 values, and the benchmark outputs an array of 4 values representing the coefficients of the resulting polynomial. For example, given the matrix [[1,2,3], [4,5,6], [7,8,9]], the arguments to the program are thus 1 2 3 4 5 6 7 8 9, and the program outputs -1 15 18 0, which represents the polynomial -x^3+15x^2+18x. The most commonly known way to calculate the characteristic polynomial of a matrix is to use the formula det(A - xI), where I is the identity matrix. However, there is also a closed form formula to this problem, -x^3+trace(A)x^2-trace(adjoint(A))x+det(A)=0, which is what I used. The challenge here was the allocation aspect: since I was allocating twice (once for the matrix and again for the resulting array), I was worried that the pointers would collide, resulting in overwrites, but this wasn't too difficult to fix.

For my tool, I decided to implement a program that counts the number of function invocations in a Bril program. This was fairly straightforward, and allowed me to become more familiar with the nested structure of Bril as I had to iterate through the json lists. This task simply amounted to keeping track of a count variable that updated every time the "call" opcode was found in the instrs list.

For my basic blocks / CFG algorithm, I used the pseudocode in the lecture video as a rough guide, ie the same high-level idea. For my CFG algorithm in particular, I named the blocks according to their label names, and for those blocks without labels, I decided to name them based on their index in the basic blocks list. Then, I created a dictionary that mapped block names to the names of their successors. I made sure to identify labels, jumps, branches, and return statements so that block boundaries could be realized. The challenge here was to make sure that fallthrough edges were handled correctly.

I tested my programs using turnt, which was difficult to set up. However, I believe the effort was worth it as I can see how turnt will be useful down the line with future tasks in this class. I used several Bril programs in the repo as inputs to test my programs. Overall, I think I deserve a Michelin star for taking the effort to familiarize myself with Bril and for actively thinking about edge cases during my implementations.

[sampsyo]

Awesome; this all looks great!

I tested my programs using turnt, which was difficult to set up.

Just for my own understanding, what was hard to set up? Was it installing the tool, writing the turnt.toml, learning the command-line interface, or something else? Maybe there are some parts of the docs we can improve.

[aw578]

benchmark pr: Benchmark
new tool: Tool

My benchmark was an implementation of rot13, using integers as a standin for characters as brili doesn't support chars yet. I wrote it manually, but the benchmark wasn't complicated so this wasn't bad. My tool just prints out the name of every function in a program. I tested this using programs with zero, one, and multiple functions. I think the hardest part of these tasks was getting used to the bril tools and turnt. As for a Michelin star, I think I'd feel bad asking for one if I just did this, so I also wrote a small utility function that removes blocks that are never entered from a program. I think that I deserve a star for implementing and testing the assigned tasks, then adding extra functionality.

[sampsyo]

My benchmark was an implementation of rot13, using integers as a standin for characters as brili doesn't support chars yet.

I don't think that's true:

$ cat char.bril
@main() {
  c1: char = const 'h';
  c2: char = const 'e';
  c3: char = const 'y';
  c4: char = const '🐶';
  print c1 c2 c3 c4;
}
$ bril2json < char.bril | brili
h e y 🐶

Any chance you're using an old version of the interpreter or something?

[mb64]

Benchmark PR: link

CFG implementation / other code: link

For this task, I decided to use Haskell. I defined my own datatypes for Bril programs, and used the Aeson JSON library to parse the input JSON and turn it into my own representations. This was nontrivial since I have not used Aeson before. I would say that it's a good library, but it has a nonzero learning curve: it's pretty opinionated about certain things, and to some extent you need to just read through the whole Hackage docs to figure out how you're supposed to do anything. As an example of things it's opinionated about, it primarily works with lazy ByteStrings -- while many other Haskell packages would prefer Texts, or Strings, or strict ByteStrings. I would say that getting the JSON parser up and working was the hardest part -- and to be honest, I think there are still cases where either serialization or deserialization has a bug.

For the extra task, I wrote a simple CFG dead code elimination function, which does DFS in the CFG to explore reachable basic blocks, and then gets rid of all the others. However, I didn't have time to test it adequately, so I ended up just making my program count the number of basic blocks -- much easier to test.

Michelin star: I think I would've said yes if I were posting this before the deadline, but it's already 12:05am and I haven't clicked "comment" yet, so I think that means no star 😅.

[sampsyo]

No big deal, happy to give you a star for this. (And yeah, the Haskell aspect does seem like it added a level of challenge to the hacking!)

[calciiium]

Benchmarks

I first implemented the Ackermann's algorithm, but then realized this has been added to the benchmarks 3 years ago. So I turned to the logistic map and wrote another bril code, which takes three arguments (r x n) and prints n lines of x_i.

Tools

I simply made an uninteresting move: count the number of each type of instructions and output it. I tested the tool with turnt using existing test programs in the test folder.

CFG

I used Python to write the CFG code and used turnt with existing programs in the test folder and also my benchmarks. It works well and correctly.

Conclusion

The hardest part is to install all the packages (honestly), because I went into a small issue when installing turnt. I do think that I deserve a Michelin star. One thing I realized after finished the work is that I shouldn't only use tests in test folder, but also should make use of other benchmarks, so I'll be more careful on this matter in order to ensure a great coverage.

[sampsyo]

Looks good!

The hardest part is to install all the packages (honestly), because I went into a small issue when installing turnt.

What was the issue? Maybe we can add something to the docs to avoid whatever it was in the future.

One thing I realized after finished the work is that I shouldn't only use tests in test folder, but also should make use of other benchmarks

Always a good lesson! Using programs written by other people is a great and low-cost way to find bugs.

[polybeandip]

Benchmark PR

A simple random walk on $\mathbb Z^d$ begins at the origin $(0, ..., 0)$ and repeatedly makes random moves of length one in one of the lattice directions: $(\pm 1, 0, \ldots, 0), (0, \pm 1, 0, \ldots, 0), \ldots, (0, \ldots, 0, \pm 1)$. In other words, the walker moves to a neighbor by adding or subtracting $1$ to one of its coordinates.

Here's a nifty fact (Theorem 3.15 and 3.11 form here):

If $d = 1, 2$, a random walk returns to the origin with probability $1$. If $d \geq 3$, the probability of returning to the origin is $&lt; 1$.

(for $d = 3$, the exact odd are about 34%)

random_walk.bril hopes to demonstrate this fact. It takes the dimension d and a seed for a PRNG as inputs and prints a random walk. The walk terminates after 100000 steps or upon returning to the start. To test the benchmark, I wrote a script that both verifies the produced walk is valid (distance between consective vertices is $1$) and draws it with matplotlib (eyeballing the walk helped check the PRNG worked).

d = 2 and seed = 5

d = 3 and seed = 11

Another script I wrote counts how many walks terminated by returning to the start via varying the random seed from 1 to 100: 73% of 2D walks returned while only 35% of 3D walks did!

also, thanks @gerardogtn, I used your tweaks to the PRNG from mat-mul.bril and they were super helpful!

CFG

Fairly straightforward implementation of the algorithm from class. This was fun to implement and helpful for getting used to bril-ocaml!

Bril tool

reorder.ml uses bril-ocaml to swap consecutive independent instructions: i.e.

• instructions that don't affect control flow
• instructions without data dependencies between them (output of one isn't input of the other)
• instructions with different destination registers

Since this type of reordering preserves program behavior, I tested it with brench to make sure my reordered venison of benchmarks/core/ matches the expected outputs. As seen by results.csv, the "optimization" is correct on all but two programs. Inspecting them revealed minor issues with bril-ocaml:

• the float type isn't supported
• Typo in Instr.to_string for stores (offending line)

Otherwise, everything went rather smoothly!

[sampsyo]

EXTREMELY cool benchmark, Akash! I like the 2D plot; it made for some pretty cool accidental art. 😃

[smd21]

Benchmark PR: Link
CFG/tool: Link

For my benchmark, I decided to (also lol) implement Karatsuba's multiplication algorithm. I decided to represent my inputs as binary numbers to make some of the calculations easier via bit manipulation. For the algorithm, I needed to implement a way to calculate the size of numbers in binary. I was able to find (borrow) existing implementations of Rightshift, mod, leftshift, and a power function from other benchmarks in the suite, which was very helpful since I found writing Bril to be pretty time consuming.

I wanted to challenge myself to build a tool that could feasibly be used when implementing a feature in a compiler or IDE. For this, I made a program that counts the number of times each variable has been used, not including initialization. This could be used for implementing something like unused variable warnings in an IDE/compiler. I wrote my tool in Typescript and didn't use any additional libraries/extensions.

For my cfg, I used the algorithm discussed in class. I made the decision to begin a new block every time a label is encountered in my block building algorithm. I used these labels to create a mapping of labels and their corresponding blocks, which was helpful when implementing my CFG algorithm.

Challenges: My first challenge is that I absolutely did not install anything correctly and spent most of Wednesday + Thursday just trying to debug that. I also wrote my implementation in typescript first, before realizing that most of the functions I used could not be ported to Bril, which meant I had to start over midway through Thursday :'( Besides those logistical issues, I found the rest of the implementation task to be pretty smooth + very fun!

Michelin star: This is incredibly late so I probably do not deserve one.

[sampsyo]

My first challenge is that I absolutely did not install anything correctly and spent most of Wednesday + Thursday just trying to debug that.

Argh, sorry to hear that! Any chance you remember any of the installation challenges you encountered? Maybe we can improve the docs so this is easier in the future.

Michelin star: This is incredibly late so I probably do not deserve one.

Don't worry about it; you have earned a star. 😃

[Jonahcb]

Benchmark PR: link
CFG/tool: link

For my benchmark, I implemented a 2d convolution. The inputs are the image size (just the # of rows or columns), kernel size, and an int seed for filling the array. Originally, I manually filled the arrays, but it got very messy and wasn't easy to scale so I borrowed functions for generating arrays, filling arrays and printing arrays. I have barely every written in a language like Bril so it was fun to learn.

For my tool, I was already so behind schedule because of installation issues and whatnot so I just went with something simple and counting the number of memory access instructions in a program and output the counts for the different types.

For my cfg, I used the algorithm in class. I used the labels as the names for blocks if there was a branch/jump statement to it and if not I just used a default name. I also display it using graphviz.

Challenges: I spent a lot of time installing things and then it worked for a while and then when I was committing to GitHub I think I broke something so I reinstalled the bril tools. I found it easy to learn Bril though and implement the tasks. I still don't really understand how Turnt works but I think I used it properly because it looks right.

Michelin star: This is really late, so I probably do not deserve one, but I was working constantly, so it was just late because of installation trouble.

[sampsyo]

Sounds good! No worries, Jonah; I can give you a star for this one. 😃

[mse63]

Benchmark PR
Tool and CFG/Basic Block Code

Installing Bril went surprisingly smoothly - I'm a NixOS user, so I usually expect a little bit of turmoil to get things made for generic Linux environments to run, but here everything largely worked.

For my benchmark, I wanted to create something non-trivial that would still be interesting. I saw that there was a typescript to bril compiler, so I learned a little bit of typescript and wrote a program to find the square root of an integer using a binary search. I struggled for a bit with the ts2bril, as I didn't realize just how much of a subset of typescript it could handle: not even a while loop, or expressions like (1 + 2) + 3. I did eventually make a typescript example that could run in bril, with lots of intermediate variables, and using recursion instead of loops (going back to functional programming core values), then manually edited the bril to make it only one function, instead of having main call another recursive function.

For my tool, I wanted to make something that I could plausibly imagine someone using. I decided to make a tool to count the number of instances of recursion in a program, which would just be the number of times a function has a call to itself in its own body. Of course, this couldn't handle cases where foo calls bar which calls foo, but I could imagine this being useful if, perhaps, someone implemented an optimization that they believe would improve recursion (maybe they just did tail recursion), and they wanted to measure performance difference for bril programs with lots of instances of recursion, as opposed to fewer instances of recursion. When testing, I wanted a simple program that used recursion and an equivalent program that doesn't use recursion, so I used the loopfact.bril and recfact.bril programs in the testbench to test my code. I hadn't heard of turnt before, but I enjoyed using it. I especially liked that it could generate the test cases from running the code, so I could imagine, for example, running an already-proven-correct program to generate test cases, then using those to test an in-development program.

For my CFG and Benchmark, I used the algorithms in class. I did only look at the main function in the program and ignore function calls, because although a function call could be easy to represent in the CFG by treating it as a jump, finding all the possible instructions you could return to from a function would require more analysis of the program. It did also take a little bit of fiddling for to get networkx to display the graph in a clean way, but the final results do look nice. Here is the loopfact.bril CFG, both with and without basic-blocks.

I believe my work would deserve a Michelin star had it been on-time, but it is 3 days late. I was ill for most of last week, though, so I'm asking for leniency.

[sampsyo]

Looks good; nice work, Mahmoud!

Of course, this couldn't handle cases where foo calls bar which calls foo,

Just for fun: the compiler nerd way to phrase this generalization would be "cycles in the call graph," and the case you can handle is when that cycle consists of only one edge.

[lisarli]

Benchmark PR: sampsyo/bril#387
The benchmark I implemented computes the hamming distance between two integers, a and b. Since the Bril core doesn't seem to support bitwise operations, I had to do some minor workarounds to perform operations like computing the least significant bit of a value and computing xor, but overall the syntax was easy to understand. I decided to write my benchmark manually instead of compiling from TypeScript to gain familiarity with Bril, which was helpful for manipulating Bril programs and building CFGs, but I can see the appeal of compiling from TypeScript for writing larger programs. To test my benchmark, I verified the outputs over inputs spanning both random and edge cases.

Tool: source
I implemented a C++ tool that counts the number of integer arithmetic operations (add, sub, mul, div) that occur in a Bril program and prints it out. This was made relatively painless using nlohmann/json to avoid dealing with parsing in C++. Building this tool primarily helped me familiarize myself with Turnt, as it was my first time using snapshot testing, but the docs were pretty helpful in setting up the configuration file, and it was easier to go from there. I tested my tool over many benchmarks, including my own and others from the core Bril benchmarks, and I manually verified the outputs of each, saving them using Turnt for future comparison. The tests can be run via make test.

Basic Blocks and CFG: source
I also implemented the basic blocks and CFG algorithms in C++ by following the pseudocode in the lecture videos. I incrementally developed this by first writing and thoroughly testing the basic blocks logic, including manually checking the output over multiple benchmarks. This allowed me to catch some small bugs early on, such as the creation of empty blocks, and made the later extension of CFG logic pretty seamless. For constructing the CFG, I found it easiest to assign numerical IDs to each basic block and look up IDs for labels as they were needed, and I verified the CFG output using benchmarks involving multiple jumps and branches, including checking for correct fallthrough behaviors.

Conclusions: I think I got decently comfortable with the Bril tools and workflow through these tasks, and I'm starting to develop an appreciation for Turnt. I didn't run into any major issues with any of the tools, and I liked how simple the core of Bril is, which made it relatively easy to understand and pick up. Writing the tool and CFG generator was also helpful for setting up a workflow for manipulating Bril programs. Overall, I think my work deserves a Michelin star because of the Bril exploration in writing my benchmark, thorough testing with Turnt, and familiarization with the ecosystem.

[sampsyo]

Very brave of you to use C++ for all this! 😃 Looks good.