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.

[anshumanmohan]

My benchmark accepts an argument and prints out the factors of the input. It uses the trial division method and pretty straightforward assembly-style code. My tool counts the number of jmp commands in a given bril program. It, too, is straightforward: nested loops to expose the instructions and then a dictionary search.

I tested both of these using turnt. I got basic implementations working, saved the expected outputs using turnt, and then played with the code some more to try out other ways of saying the same thing. My tool is applicable to all bril programs, so I just copied the entire test/interp/ directory and ran my tool on all those programs.

I was a bit confused by how bril functions take arguments. I figured it out by looking through a few other benchmarks (Ackermann and GCD).

[sampsyo]

You're not alone about the whole arguments thing… I should probably add that into the description of the tasks!

[michaelmaitland]

My benchmark accepts two arguments a and b and outputs to stdout the prime numbers in the interval [a, b]. It is assumed that a, b >= 0. and a <= b. I first wrote this program in C and then converted to the bril textual representation by hand. I felt that by doing so I got familiar with the operations, their arguments, and how functions work. In doing this, I was reminded how tedious it is to write a program in a language that resembles assembly. It makes me thankful that compilers exist! I also realized that I was not writing optimal bril code, but rather code that is easy to understand and debug. I tested it against the C program against multiple imputs to gain confidence that it worked.

My tool is pretty simple. It prints out the variables that each brill function defines. I wonder how it's output for a given brill program will perform by different optimization passes.

[sampsyo]

Neat. Out of curiosity, did you automate the process of doing differential testing between your Bril and C implementations, ir did you just try a few by hand?

[michaelmaitland]

I just tried a few by hand and using diff, but agree doing some differential testing on a larger set of inputs would have been a great idea.

[alaiasolkobreslin]

My benchmark prints the numbers less than some n that are relatively prime to n in descending order. It uses the Euclidean algorithm to check whether the GCD of the current number and n is equal to 1, and prints the current number in this case. While working on this benchmark I realize that bril doesn't support the mod operation, so I looked at another benchmark to find a workaround. I tested this program by running it on several inputs and checking that the relative primes were correct. I saved the expected output output for the input 20 using turnt.

My tool adds a print instruction that prints the number 42 before every jump instruction. I tested the tool on several bril programs in the examples directory, some containing jump instructions and some without any.

[sampsyo]

Looks great! I assume you tried running those transformed programs in the reference interpreter too, just to make sure they're still valid, huh?

[alaiasolkobreslin]

Oh yes, that's what I meant to say.

[tonyjie]

My benchmark implements a Bubble Sort algorithm for a list containing 5 elements. It accepts 6 arguments: the first args is 5, the length of array; the rest args are the 5 elements. The output is 5 sorted number in ascending order.

I use ptr<int> and memory inst to operate the array. Bubble sort is mainly a two-layer for loop. After reading some of the former benchmark bril code, I found that a for loop could be clearly represented as a few parts: .loop, .body, .loop_end, .done. Following this method, I managed to write the benchmark.

One trick I found useful to debug when writing bril code is that, we can also put print one in wherever we want, and locate the ERROR without enough error messages. XD

It is worth to mention that if the same 5 elements are given in different orders, turnt would give ERROR message though the output is the same with ascending order. I think that is because turnt would also examine if the # of dynamic inst is the same. E.g. when the input is changed from 5 3 10 1 9 7 to 5 3 10 1 7 9, the # of swapping changed, causing the # of dynamic insts changing as well.

My tool is a simple program to count the number of add instructions. Note that some instr doesn't have key op, so we need to check whether there is op in keys. But this bug won't reflects in the very simple add.bril testcase. So enlarging testcase is helpful and necessary.

[sampsyo]

Your hypothesis about the dynamic instruction count changing sounds about right. To test it, you can try turnt --diff to see exactly what is changing to cause the failure.

[andrewb1999]

My benchmark implements an algorithm to determine if the input integer is an Armstrong number, a number that is the sum of its own digits, each raised to the power of the number of digits. Implementing this benchmark required implementing mod and pow, as these are not supported by bril natively. To count the number of digits in the input number, I used a recursive function as it was easier than implementing log from scratch. I tested the benchmark with many different input numbers, both those that are Armstrong numbers and those that aren't. For example, 407 is an Armstrong number and 663 is not.

My tool counts the number of add instructions in a bril program. The tool is implemented in rust using the bril-rs library. Testing is performed with turnt on a large number of benchmarks from the bril benchmark suite.

This task was not very difficult, but it took some time to understand how to program in bril.

[sampsyo]

Cool that you got to use the Rust library! It's still evolving, of course, so bug reports and such would be appreciated.

[chhzh123]

Benchmark

I implemented a graph format converter as a benchmark in this PR. It transforms a graph in adjacency matrix format (dense representation) to Compressed Sparse Row (CSR) format (sparse representation). It intensively uses the memory facility of Bril and mimics the behavior of multi-dimensional arrays.

The input graph is randomly generated reusing the algorithm in benchmark/mat-mul.bril. Basically, users can input the number of nodes and a fixed seed to the program, and the program will output the adjacency matrix, the CSR offset array, and the CSR edges array.

Bril Tool

For the tool, I implemented a function inlining pass (written in Python) for Bril, which basically puts all the function calls inside the main function. It is an important compiler optimization that eliminates the overheads of maintaining stacks for function calls. Details can be found in my repository.

At the very beginning, people may think function inlining is just about moving the whole function body to the main function, but actually it needs more consideration. In general, I did the following two things in my pass:

1. Replace variable references.
   I constructed a mapping from local variables (function arguments) to global variables. Since the function signature and the return value will be removed after the function body is inserted into the main function, those input and output variables should be replaced with variables in the main function.

• For operands/inputs, we need to check the "args" field, traverse all the arguments, and replace those in the function signature.
• For returns/outputs, we should first take out all the ret instructions and see what they return. This is because in a function we may have multiple places to return a value, which is not necessary at the end of the function. Those variables should all be replaced as the "dest" one of the call function. Moreover, since this actually involves storing values into memory, we should be very careful about whether they replace the previous useful values, so this comes to the second issue.

2. Resolve naming conflicts.
   It would be simple if users strictly use different variable names in different places, but this is not always the case. For example, we may use i as the iteration variable in all the loops, thus this may possibly lead to naming issues that the variable refers to is not what we want. In my implementation, I used a simple naming rule to resolve the conflicts.

• For variables inside the function, I added _fvar behind the original variable name and further added function ID behind this in order to avoid the same names across different functions.
• For labels, I also added _flabel behind the original name, so that the control flow may not be confused about where to go.

An example program here shows how my pass works.

@main {
  x: int = const 2;
  y: int = const 2;
  z: int = call @add2 x y;
  print y;
  print z;
}

@add2(x: int, y: int): int {
  w: int = add x y;
  y: int = const 5;
  print y;
  print w;
  ret w;
}

We can see that from the following output, there is the only main function. Those variables inside the function are renamed, and no return instructions are involved. But there is also another issue, if we look at the original program, we can see the outer variable y is actually shadowed by the function argument y, although they have the same name. This may cause problems when y inside the function is reassigned, i.e. the scope of the inner y is only inside the function and should not affect the value of the outer y. So we should carefully distinguish the variables here and use different names for variables in different scopes (y_fvar0), which somehow mimics the stack that protects the contexts in between the function.

@main {
  x: int = const 2;
  y: int = const 2;
  z: int = add x y;
  y_fvar0: int = const 5;
  print y_fvar0;
  print z;
  print y;
  print z;
}

After we resolve the above issues, we can finally create a main function that takes in all the function bodies.

I also added five test cases in my test folder and used turnt to test if my pass runs correctly.

Limitations

There is one limitation here -- my pass can only work with the function calls in the main function and cannot support arbitrarily nested function calls. Since for recursive functions, we do not know when it exactly stops, which is runtime information and cannot be obtained during compile time. Thus, as a simple solution, I directly raised a runtime error if some functions have nested function calls.

Discussions

1. I am not sure why for some operations in Bril, they have a parameter list to store the item. For example, the call operation has a field called "funcs" and takes in a list of functions, but I have no idea how this can work for multiple functions. Another one is ret, which also has a "args" list. If the Bril IR is in SSA form, then I think it cannot have multiple return values?

2. Declaration and assignment. I am not sure why the following code can pass the compilation and execute. As I know, Bril has no type casting operators, so how can this be doable conversing from int to bool and back to int. Are there any implicit type casting rules like those in C/C++? Also, does x: bool = const 0; mean declaring a new variable or assigning a new value to the original variable? The vague semantics makes transformation pass hard to be done correctly in some ways.

@main() : int {
  x: int = const 190;
  x: bool = const 0;
  print x;
  ret x;
}

[sampsyo]

I am not sure why the following code can pass the compilation and execute. As I know, Bril has no type casting operators, so how can this be doable conversing from int to bool and back to int.

That program is, in fact, not legal. I assume you ran it with brili and it didn't produce an error? That's because brili does not attempt to do any static type checking; it basically ignores the type annotations and keeps on trucking. (The interpreter promises that it runs every legal Bril program; it does not promise that it does not run every illegal Bril program.)

If you are interested in static type checking, there are options for that too! One example is the type inference tool, which will just fix the type error in this program. Another is the interpreter written in Rust, which has a type-checking mode (-c). Here's what that tool says about your example:

$ brilirs -ct < foo.bril
error: Expected type `Bool` for assignment, found `Int`

[chhzh123]

if your inlining pass deals with control flow: that is, if ret appears earlier in the function than at the end, it seems like it would be necessary to insert a jump to preserve the behavior where returning passes control to the end of the (inlined) function.

Yeah, I just realized this problem. Instead of removing the return statements, I need to add a label indicating the function scope and let all the ret jump to there. Will fix this later.

Here is also one idea for how to make this inlining pass simpler: you could create "unnecessary" copies.

This idea is awesome! But this way still needs to rename all the variables inside the function. A map from original names to these copies is still required I think, and these copies will ultimately be eliminated by copy propagation :)

[chhzh123]

Instructions in Bril look like this because they have a uniform/general structure.

This makes a lot of sense!

[chhzh123]

The interpreter promises that it runs every legal Bril program; it does not promise that it does not run every illegal Bril program.

Thanks for answering the question in class. This is a very interesting property! Is this called completeness? I also wonder if these kinds of false-positive programs are common in other languages' compilers or interpreters?

[sampsyo]

It's possible you could call this "incompleteness," but I think it's honestly a little confusing in terms of terminology… one could also say that brili is "unsound" because it fails to catch all illegal programs. These terms are a little bit perspective-dependent.

Just to boil it down, brili's contract is an implication: "well-formed program => brili executes it correctly." The converse of the implication is not true. A famous way where this comes up in real compilers is in C/C++'s undefined behavior. Compilers say "your program never invokes UB => the compiled program is correct." If your program does invoke UB, on the other hand, all bets are off and the compiled program can do literally anything, such as executing rm -rf /.

[charles-rs]

my benchmark inverts a 3x3 matrix. It uses the usual determinant + adjoint method. Some of the index calculations for the memory would benefit from a CSE pass, which is mostly since i wrote it in a way that i could think about it more easily.

my tool takes a bril program and determines (very conservatively) which functions might have side effects. Side effects include printing and escaping pointers, but I haven't considered nontermination. Ideally, functions that have no side effects can be computed at compile time if their arguments are known, like constexpr in C++. The issue of nontermination is messy here, and even if we can prove that the program would terminate, that doesn't mean it would terminate in a reasonable amount of time, so perhaps a timeout would be a better choice. Right now this is super naive, but it could be expanded to do more interesting things like propagate the "impurity" of functions through a graph of potential calls, as well as the all important escaping pointer analysis.

[sampsyo]

It seems like a very good idea to write benchmarks in a way that is easy to understand instead of efficient! Not least because it makes it possible to write and test useful optimizations down the line.

The purity checker also seems cool. You could imagine doing very fancy things with pointers to look for escaping at some point down the line, for example.

[gsvic]

My benchmark is a simple iterative implementation of a pow(x, n), that returns the n^th power of x.

The tool is a cycle detector, that does a static analysis and detects cycles between between function invocations. The tool works by analyzing a bril program and generating the equivalent DAG of the function-calls. Next, by executing a simple graph traversal for each individual function, it outputs the full path that leads to the cycle, e.g. f1 -> f2 -> f3 -> f1, in case that we check f1 and f3 invokes f1 again, which will potentially lead to a maximum stack size exceeded error. To test that, I am using two test-cases, one with cycles and one without.

Of course, a cycle might not occur despite a cycle between function calls, if the corresponding conditions are added before the calls. Thus, this tool detects only potential cycles, as I do not do any check on the conditions, or, how these methods are called.

[sampsyo]

Neato! You could imagine using such a cycle detector in @chhzh123's inliner, for example, to avoid running forever.

[ayakayorihiro]

My benchmark is a very simple operation; given the lengths of the sides of two rectangles (with the arguments being x1 y1 x2 y2 where x1 and y1 are the lengths of the two sides of rectangle r1, and so on), it computes the difference between the areas of the two rectangles and prints both areas and the difference between the areas.

For the second part of the task, I wrote a simple program to swap integer arithmetic operations; addition is swapped with subtraction and vice versa; multiplication is swapped with division and vice versa. In order to test my transformation, I wrote a number of Bril programs that contained arithmetic operations, and observed both the output of my transformation via the output json, and also via the output of the transformed Bril programs themselves.

The most difficult part of the task was getting used to Bril, and also getting used to reading and modifying json. I read through the documentation of Bril and looked at a couple of the existing Bril programs in the bril/test directories before starting to write my own benchmark. Also, getting used to a language like Bril where each value in the program has to be defined in a variable took some time, as I would get parsing errors frequently, but I can see that the language structure of Bril would be very helpful in analyzing programs specifically because of this property.

[sampsyo]

Awesome! Yeah, Bril is not nice to write by hand at all. Hopefully this is the last time you will write an entire program (instead of just a tiny test case or whatever) by typing in Bril instructions manually.

[zzzDavid]

Benchmark

My benchmark implements Cholesky decomposition, a useful matrix operation for solving systems of linear equations. It decomposes a Hermitian and positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose.

In my implementation, the input is real number matrix, and the output is the lower triangular matrix. There are a few steps in the benchmark:

• Take input matrix A and transpose it
• Multiply A and A transposed, to get a positive-definite matrix
• Feed the matrix to Cholesky decomposition function, and get back the lower triangular matrix.

Validating the result

I validated the result by comparing with scipy.linalg.cholesky:

    hermitian = np.matmul(A, A.T).astype(np.float32)
    result_golden = scipy.linalg.cholesky(hermitian, lower=True)

Problems I met

1. I tried generating Bril from Typescript, but it seems that ts2bril doesn't have support for arrays. I think we can support arrays with pointers in Bril, it would be awesome to have that.
2. I tried to generate random number with a linear congruential generator, but it doesn't work because we don't have mod for floating point number. I also couldn't cast float to int so that I can implement mod with integer division. I couldn't think of any way to bypass that, so I'm using a fixed input right now.

Simple Analysis Pass

My pass is a simple static memory footprint profiler. It tells you how much memory is allocated in the program. I assume that int is 4 Byte, and float is 8 Byte.

For example, for the matrix multiplication benchmark, it tells you how many bytes are allocated in total, along with some other details:

Function randarray allocates 64 Bytes
Function main allocates 4 Bytes
Function randarray is called 3 times
Function main is called 1 time
memory footprint analysis: 196 Bytes are allocated in total.

Implementation

1. I did some simple global analysis to build a call graph: which functions calls other functions, with what arguments, and for how many times.
2. Then I find all alloc operations, try to figure out their size and type. The size part is a bit tricky: if it is a constant defined locally, we can get that information easily; if it is passed from a function argument, then I have to retrieve it from its caller.
3. Finally I traverse the call graph, and calculate how much memory is allocated in total.

[JonathanDLTran]

My benchmark is an implementation of finding the left, midpoint and right Riemann sums for the squaring function, although the function can be replaced by other computable functions. I had some difficulty figuring out how Bril worked initially, but looking over other students' benchmarks allowed me to pick up some of the operations in Bril, and the basic assembly style.

To test the correctness of this benchmark implementation, I used the given example of having a left endpoint at 2, and a right endpoint at 10 on the x-axis, and using 8 subdivisions. I verified that the sums of the squares of the left ends of the subdivisions was equal to the sums of the squares of 2 through 9, and the right Riemann sum equaled the sum of the squares of 3 through 10, and that the midpoint sums were the sum of the squares of 2.5, 3.5,..., 9.5. I also increased the number of subdivisions to be large, to see if the Riemann sums get close to 330.67. The hardest part was getting the sums correct, because I had forgot to multiply by the subdivision length.

My tool iterates over Bril functions and instructions, and inserts a print operation after each instruction. The print operation is made to print the value 1, by printing from a new variable set to the value 1. Writing the tool made me realize appreciate Bril's design, especially the simplicity in seeing how Bril can be manipulated, and the similarity between the different forms in the language, which might make it easier to process than an intermediate representation with a large number of differing forms.

[atucker]

My benchmark adds an implementation of Knuth's up arrow notation for hyper operations, which generalize the idea that multiplication is iterated addition, exponentiation is iterated multiplication, and so forth. I basically wanted something that was a little repetitive and could maybe be streamlined, and which used recursion.

I checked its correctness by comparing its outputs to this table of values.

At first I tried just writing a typescript program and using ts2bril, but that wasn't able to handle the loop, so I removed it and then tried to put the loop back in. That totally worked, but after removing all of the variables created by ts2bril it probably would have been faster for me to just try to write the bril by hand, which I'll do next time.

My tool just counts the number times each constant gets used. This was mostly prompted by me feeling weird not being able to write i: int = add i 1 for i++, and the fact that so many programs wound up writing one: int = const 1. I guess it makes sense that a processor can add the data in registers but not a constant lying around somewhere.

[sampsyo]

Good point about the trouble with loops in the ts2bril frontend. I'm glad you have it a shot anyway, even if it was kind of a waste of time! I don't think it gets enough use as I thought it might. :)

If you ever have a few extra cycles, would you be interested in filing an issue about the missing loop support in the compiler? It's something we could potentially address in the future.

[atucker]

Sure!

[5hubh4m]

Benchmark

I implemented the Adler-32 checksum. The program first creates an array of size 512 using and then populates it with constant values (0, 1, 2, ...) (though perhaps it's possible to use a PRNG as in mat-mul.bril). It then calculates the checksum. The interesting bit was to figure out how to implement bitwise operators using just normal arithmetic operations.

Manipulating Bril Programs

My language of choice is Scala. It's a static, strongly typed language, and so manipulating JSON in an error free way is non-trivial so I created a simple library à la (bril-rs, bril-ocaml, etc.) to represent a Bril program in Scala. Currently it supports the core language, the memory extension, and the floating point extension. I hope to turn in into a standalone library and maybe push it to the monorepo.

I first wrote the program to create a CFG from a Bril program (here's a sample).

Then I wrote a program to calculate the distribution of the in-degrees and out-degrees of all the basic blocks in a program. I tested it using Turnt. The tests are here. One example for the newton.bril benchmark is

In-degrees summary:
    3 blocks with 0 incoming edges.
    1 blocks with 2 incoming edges.
    4 blocks with 1 incoming edges.
Out-degrees summary:
    4 blocks with 0 outgoing edges.
    2 blocks with 1 outgoing edges.
    2 blocks with 2 outgoing edges.

[sampsyo]

Nice; seems great!! And yeah, if you ever feel like it, we could totally merge a Scala library---long compile times notwithstanding. :)

[barabanshek]

I implemented the classic "Maximum sub-array problem" (https://en.wikipedia.org/wiki/Maximum_subarray_problem) that is the simplest ever form of dynamic programming. The program is looking of a sub-sequence with the highest sum of elements in the input sequence. I wrote it in bril.

As the tool pass, I implemented a counter of functions in a given program - very simple, just to start with this.

The most time-consuming part was getting started with the toolchain and learning bril.

[yy665]

Benchmark

I implemented a simple binary search algorithm. The program takes a fixed array of length 5 and a target value as input. It either outputs the index of target, or -1 if the value is not found in the input array.

The benchmark is validated by manually observing multiple pairs of input/output, and by turnt.

Simple Bril pass

I implemented a very naive memory leak checker. (Code is uploaded on CMSX) It basically checks that the variable pointing to the start of a piece of allocated memory gets freed. The implementation is done with Python. To make it actually work, I think it needs to take care of pointer arithmetic to trace the pointer so that we know we are actually freeing a valid & unfreed memory.

Discussion

One thing I found really nice about Bril is to be able to manipulate on JSON itself. It makes writing and debugging compiler passes very easy.
The difficult part of this assignment was to learn about Bril's capability. I had a higher expectation on what Bril could achieve so I was trying to implement some complex algorithm like FFT. It turned out to me I was way too ambitious that Bril only supports very basic abstractions, and to write a FFT I need to build everything from scratch, so I ended up only implementing a binary search.

[sampsyo]

It would be interesting to hear more about your thoughts on the "memory leak" check! Getting this perfectly precise seems hard, so it seems important to think through what the limitations are. I think it works by saying that, if you do x = alloc [...], then you must eventually free x. But if I "copy" the pointer via y = id x and then free y, that won't suffice, right? Or if I play a similar game so that free x actually frees a different pointer, then I can "conceal" a memory leak—is that also right? Being precise about what a pass is and is not capable of is important, even when the capability is limited.

[susan-garry]

For my benchmark, I implemented a recursive function to calculate the _n_th term in the Catalan sequence. It involves many repeated computations, so I thought it would be an interesting challenge for a compiler to attempt to optimize. I tested the program manually on various inputs.

My (very) simple analysis tool, implemented in python, counts the number of constants in each bril program.

For me, the most time-consuming part of this task was trying to come up with a benchmark that was both interesting and not too difficult to implement in bril. I ended up asking a few friends for suggestions before I settled on this one.

[sampsyo]

Nice! You have creative friends.

[thomasyang18]

For my benchmark, I implemented XOR, AND, and OR by simulating bit shifts one by one with repeated multiplication/division (and tracking which "bit" I was on by having just a counter that constantly multiplied by two). Kinda slow, but don't know how to do it any other way :/

My tiny program prints "8080" in addition to every print statement in the program.

Learning bril was a little hard, but it's a lot better than assembly; it's helped me understand assembly a lot better now that I kind of see that assembly is just more limited IR since you can't have infinite registers + the stack is abstracted away.