Lesson 7: LLVM

[sampsyo]

Share your experiences getting started with writing an LLVM pass here!

[keikun555]

Summarize what you did.

• Lesson 7 Task
• Dead code analysis pass

This uses a library within the Transforms/Utils directory to see whether an instruction is trivially dead, would be trivially dead, or would be trivially dead on unused paths.

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

• I ran the dead code analysis pass on a modified power function implementation inspired from this examples website. The modifications removed its dependency on the iostream library.
• I used this toml file to generate the resulting outputs.
• From the analysis output of the power program LLVM thought 36 lines would be trivially dead.

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

• I initially explored implementing TDCE on LLVM, though I found that erasing an instruction using eraseFromParent has many complications.
• One complication is the need to replace the use of the instruction with something so I referred to this Stack Overflow link and replaced all the deleted value to Undefs before calling eraseFromParent
• However, leaving Undefs made the resulting program core dump, so more engineering was needed to also remove their uses.
• That's when I found LLVM's Dead Code Elimination pass implementation which led me to come across the llvm::wouldInstructionBeTriviallyDead command and settled on using these subroutines to report what instructions LLVM thought would be dead.

[matth2k]

• Summary

  • Strength Reduction for Mul2Shl

• Implementation Details

  • I implemented a pass that rewrites multiply instructions as logical shift lefts when one of the operands is constant and a power of 2. I used Chapter 10 of Hsu, 2021 as a reference.

• Evaluation

  • I specifically did such a small scale optimization so that I could have more confidence that it is correct while using only a handful of tests. Since I wanted to rewrite multiplication by constant powers of 2, my main test case was just multiplying argc:

  int main(int argc, char *argv[]) {
    return argc * 64U;
  }

  Here we can see the before an after of rewriting:
  Before:

  %7 = mul i32 %6, 64
  ret i32 %7
  

  After:

  %7 = shl i32 %6, 6
  ret i32 %7
  

• Anything Hard or Interesting?

  • I learned the difference between an Operator and Instruction in LLVM. Basically, an operator carries less meaning than an instruction. The class is just meant to capture the commonality between constant expressions and instructions in SSA.
  • I did not bother to implement a check to see if one of the operands are negative, so please don't use my pass in a real compiler.
  • How do I rewrite the pass using a pattern matching programming pattern? I couldn't easily find info on this. Is the pattern rewriter MLIR exclusive?

[bennyrubin]

Summary

Link to repo

For this task, I implemented what I call a de-optimization. You might ask yourself, what the point of something like this is, which is a very good question. Please let me know if you think of something. Nevertheless, my de-optimization finds add instructions where one of the operands is a constant (say n). It then replaces that add instruction with n instructions that add 1 to the non constant operand.

Implementation and Testing

My implementation is fairly straightforward. I loop through all instructions in the program and for each add instruction, I check if either operands are a constant. If so, I loop through that many times adding new instructions that add 1 to the other operand. The final step is to replace all uses of the original add instruction with my new value that is equivalent, but took a bit more work to get there.

I briefly looked online for math functions implemented in C, but had trouble finding something that was changed by my pass, so I defaulted to using my own custom test, where I had an addmitedly contrived example of a function that adds constant values to an argument. However, for such a simple implementation I am confident with this.

Anything hard?

• My initial idea was to build some sort of decompiler that would take a bunch of integer instructions and de-compile it into C-like infix notation, as an expression that could be compiled in most high level languages. However, I quickly realized that even when you emit unoptimized code, llvm does constant folding, so a few of my ideas were ruled out.
• Navigating the giant codebase that is llvm took time to get used to, and was a bit frustrating when I knew exactly what I wanted to do (such as test if a value was a constant and then extra the constant as an int), but it took me some time to google and figure out how to do.
• As mentioned in a previous comment, it would be nice to have some sort of pattern matching available. Many nested if statements led to some pretty ugly code. I can imagine for longer optimizations, this would quickly lead to spaghetti.

[evanmwilliams]

Summary

@emwangs and @he-andy and I worked together for this assignment!

• LLVM Pass

Implementation Details

• For this task we implemented something simple - every time we see a floating point operation we print a message as well as the instruction. We thought this was moderately more interesting than the suggested unambitious task, but honestly this is about the same level of ambitious. With the extra time we might go back and implement something fancier
• The implementation felt very simple! I googled a good bit to figure out what is valid and what is not (for example figuring out that you can check an opcode with getOpcode() or that the LLVM type for a floating-point add instruction is Instruction::FAdd

Challenges

• Build systems were a bit irritating. The different versions of LLVM were a bit annoying to figure out, but I used an alias to make my life easier
• I was also having trouble with the .so vs .dylib thing, but I got that cleared up quickly thanks to the handout
• Other than that I found this assignment fun and simple. No problems here!

Testing

We wrote a relatively simple C program to test on:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, const char** argv) {
    float num = 5.0;
    printf("%f\n", num / 2.0);
    printf("%f\n", num / 2.5);
    printf("%f\n", num / 3.0);
    printf("%f\n", num / 3.5);
    printf("%f\n", num * 2.0);
    printf("%f\n", num * 2.5);
    printf("%f\n", num * 3.0);
    printf("%f\n", num * 3.5);
    printf("%f\n", num - 2.0);
    printf("%f\n", num - 2.5);
    printf("%f\n", num - 3.0);
    printf("%f\n", num - 3.5);
    printf("%f\n", num + 2.0);
    printf("%f\n", num + 2.5);
    printf("%f\n", num + 3.0);
    printf("%f\n", num + 3.5);
    return EXIT_SUCCESS;
}

We then verified all of the floating point operations got caught here:

Floating point division found in function: main
Instruction:   %9 = fdiv double %8, 2.000000e+00
Floating point division found in function: main
Instruction:   %13 = fdiv double %12, 2.500000e+00
Floating point division found in function: main
Instruction:   %17 = fdiv double %16, 3.000000e+00
Floating point division found in function: main
Instruction:   %21 = fdiv double %20, 3.500000e+00
Floating point multiplication found in function: main
Instruction:   %25 = fmul double %24, 2.000000e+00
Floating point multiplication found in function: main
Instruction:   %29 = fmul double %28, 2.500000e+00
Floating point multiplication found in function: main
Instruction:   %33 = fmul double %32, 3.000000e+00
Floating point multiplication found in function: main
Instruction:   %37 = fmul double %36, 3.500000e+00
Floating point subtraction found in function: main
Instruction:   %41 = fsub double %40, 2.000000e+00
Floating point subtraction found in function: main
Instruction:   %45 = fsub double %44, 2.500000e+00
Floating point subtraction found in function: main
Instruction:   %49 = fsub double %48, 3.000000e+00
Floating point subtraction found in function: main
Instruction:   %53 = fsub double %52, 3.500000e+00
Floating point add found in function: main
Instruction:   %57 = fadd double %56, 2.000000e+00
Floating point add found in function: main
Instruction:   %61 = fadd double %60, 2.500000e+00
Floating point add found in function: main
Instruction:   %65 = fadd double %64, 3.000000e+00
Floating point add found in function: main
Instruction:   %69 = fadd double %68, 3.500000e+00

We also wanted to verify our program on something more "real". I found a program online that computes a Mandelbrot fractal and saves it as a grayscale PPM:

#include <stdio.h>

#define WIDTH 800
#define HEIGHT 800

int mandelbrot(double real, double imag) {
    int n;
    double r = 0.0;
    double i = 0.0;
    for(n = 0; n < 256; n++) {
        double r2 = r * r;
        double i2 = i * i;
        if (r2 + i2 > 4.0) break;
        i = 2 * r * i + imag;
        r = r2 - i2 + real;
    }
    return n;
}

int main() {
    FILE *fp = fopen("mandelbrot.ppm", "wb");
    fprintf(fp, "P6\n%d %d\n255\n", WIDTH, HEIGHT);
    for (int y = 0; y < HEIGHT; y++) {
        for (int x = 0; x < WIDTH; x++) {
            double real = (x - WIDTH / 2.0) * 4.0 / WIDTH;
            double imag = (y - HEIGHT / 2.0) * 4.0 / HEIGHT;
            int value = mandelbrot(real, imag);
            unsigned char color[3];
            color[0] = value;
            color[1] = value;
            color[2] = value;
            fwrite(color, 1, 3, fp);
        }
    }
    fclose(fp);
    return 0;
}

Here's the output:

Floating point multiplication found in function: mandelbrot
Instruction:   %16 = fmul double %14, %15
Floating point multiplication found in function: mandelbrot
Instruction:   %19 = fmul double %17, %18
Floating point add found in function: mandelbrot
Instruction:   %22 = fadd double %20, %21
Floating point multiplication found in function: mandelbrot
Instruction:   %27 = fmul double 2.000000e+00, %26
Floating point subtraction found in function: mandelbrot
Instruction:   %33 = fsub double %31, %32
Floating point add found in function: mandelbrot
Instruction:   %35 = fadd double %33, %34
Floating point subtraction found in function: main
Instruction:   %22 = fsub double %21, 4.000000e+02
Floating point multiplication found in function: main
Instruction:   %23 = fmul double %22, 4.000000e+00
Floating point division found in function: main
Instruction:   %24 = fdiv double %23, 8.000000e+02
Floating point subtraction found in function: main
Instruction:   %27 = fsub double %26, 4.000000e+02
Floating point multiplication found in function: main
Instruction:   %28 = fmul double %27, 4.000000e+00
Floating point division found in function: main
Instruction:   %29 = fdiv double %28, 8.000000e+02

So we're pretty convinced it will work - after all we aren't doing anything too crazy :)

[willwng]

Vivian and I worked on lesson 7 together.

Summary

• Inspired by our Bril tool (from lesson 2), we decided to do something similar with the LLVM pass.
• The tool swaps branches in conditional br instructions and negates the condition (so as to keep the code working the
  same).
• We tested our tool on several programs (including Fizz-Buzz) and the behavior was identical to the original program

BEFORE:   br i1 %5, label %6, label %34
AFTER:   br i1 %6, label %35, label %7

Implementation details

• We swapped branches using a handy function called swapSuccessors. We were mildly surprised that slick functions like
  this exist, but some simpler functions like negating a boolean didn't. To negate the condition, we compared the original
  condition to the literal 0.
• Our pass produces code which is equivalent to the input, so we were able to test by simply checking that the new
  output was the same before and after our pass.

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

• The hardest part of this task was mostly just getting used to LLVM syntax. Fortunately, the examples in class, the language
  reference (especially the Doxygen pages), and the similarity to Bril made things move smoothly. For example, we did not know
  that the branch instruction also acted as a jump (if it was unconditional).
• Another tricky part was how to handle the types of objects. We noticed that after casting, printing an object would
  sometimes just return a hex number (memory address?) rather than its string representation.

[collinzrj]

Summary

I have implemented a simple pass that checks for binary Mul operations, and switch the left hand side and right hand side in the code. I have saved the output assembly code at foo_original.s and foo_opt.s. After my transformation, the code changed from

	ldr	w8, [sp, #12]
	ldr	w9, [sp, #8]
	mul	w0, w8, w9

to

	ldr	w9, [sp, #12]
	ldr	w8, [sp, #8]
	mul	w0, w8, w9

I was supposing that mul w0, w8, w9 would change to mul w0, w9, w8, but the above two instructions changed instead.

Difficulties

It seems that clang will perform some optimizations before I see the llvm IR. For example, if I have a function like

int main() {
     return 5 + 4;
}

It will directly be transformed to

Instruction:   ret i32 9

So I won't see the 5 + 4 instruction. Is this an optimization handled in the front-end of the compiler?

[ryanwmao]

@xalbt and I worked together on lesson 7.

Summary

llvm pass

Implementation

• We did a simple LLVM pass where we swap the operands of every binary operator, and add a negation to its arguments if they evaluate to a Constant 1.

Difficulties

• We found navigating the docs to be pretty hard, this is probably something we will have to get used to + get better at
• Some minor issues with interacting with llvm classes, but this is related to first bullet point

Testing

We ran our LLVM pass on a few C files. We've included a pretty clear example in hello.c:

#include <stdio.h>

int main() {
  int x = 4;
  int y = 3;
  int j = x - y;
  printf("%d\n", j);
  if (j + 1) {
    printf("true!\n");
  }

  x = 1;
  if (!(x + 1)) {
    printf("false!\n");
  }


  return 0;
}

our output for the pass itself is

Function main
       %7 = sub nsw i32 %6, %5
       %11 = add nsw i32 -1, %10
       %17 = add nsw i32 -1, %16
Function printf

and for our ./a.out:

-1
true!
false!

[alifarahbakhsh]

Link to the repo

I decided to do something similar to the same task that we had with Bril: I look for add and mul instructions, and swap the operands. At first I was doing this by manually swapping the operands, but then I realized that there already is a swapOperands() function that does this for a binary operator.

The main challenge with this task was finding my way around the LLVM docs. In doing so, you can easily see that LLVM is a beast. No wonder why everyone uses it.

Here is a code snippet:

Before swapping:
  %1 = alloca i32, align 4!
  %2 = alloca i32, align 4!
  %3 = alloca i32, align 4!
  %4 = alloca i32, align 4!
  %5 = alloca i32, align 4!
  store i32 0, ptr %1, align 4!
  store i32 8, ptr %2, align 4!
  store i32 3, ptr %3, align 4!
  %6 = load i32, ptr %2, align 4!
  %7 = load i32, ptr %3, align 4!
  %8 = add nsw i32 %6, %7!
  store i32 %8, ptr %4, align 4!
  %9 = load i32, ptr %4, align 4!
  %10 = mul nsw i32 %9, 2!
  store i32 %10, ptr %5, align 4!
  %11 = load i32, ptr %5, align 4!
  %12 = call i32 (ptr, ...) @printf(ptr noundef @.str, i32 noundef %11)!
  ret i32 0!
After swapping:
  %1 = alloca i32, align 4!
  %2 = alloca i32, align 4!
  %3 = alloca i32, align 4!
  %4 = alloca i32, align 4!
  %5 = alloca i32, align 4!
  store i32 0, ptr %1, align 4!
  store i32 8, ptr %2, align 4!
  store i32 3, ptr %3, align 4!
  %6 = load i32, ptr %2, align 4!
  %7 = load i32, ptr %3, align 4!
  %8 = add nsw i32 %7, %6!
  store i32 %8, ptr %4, align 4!
  %9 = load i32, ptr %4, align 4!
  %10 = mul nsw i32 2, %9!
  store i32 %10, ptr %5, align 4!
  %11 = load i32, ptr %5, align 4!
  %12 = call i32 (ptr, ...) @printf(ptr noundef @.str, i32 noundef %11)!
  ret i32 0!

[MelindaFang-code]

Summary

link to my commit
I implemented something similar to the easy challenge mentioned. I replace every floating point division, multiplication. addition, and subtraction with other binary operations. To not make the mutation take place silently, I prints out the function name, the instruction, and the mutated binary operator.

Testing

I basically inspected the program and see if the results are expected as I print out all the results

Challenge

The most challenging part is actually setting up llvm. My computer always uses Clang comes with xcode instead of the clang comes with llvm. I have to change the PATH variable. Also I messed up the installation and I went through a bunch of messy operations like I reinstalled xcode, command line tools.

Another challenging part is to get familiar with the llvm syntax. It has so many functions also I also checked out their tutorials but they seem to be more about building syntax trees and not much about actually changing and optimizing the program during compilation

[NgaiJustin]

Summary

• Repo (link)
  • target/foo.c
  • src/rtlib.c
  • skeleton/Skeleton.cpp

Details

• I implemented a simple LLVM pass that would rotate all add, subtract and multiply operations i.e. add → subtract, subtract → multiply, multiply → add. I also log a message each time this replacement happens

Testing/Evaluation

• I tested the pass on some small c programs with a bunch of addition, subtraction and multiplication. For example the pass for ./target/foo.c

// foo.c
int addSubMul(int x) {
    int a = x + 4;
    int b = a - 3;
    int c = b * 2;
    return c;
}

int main() {
    return addSubMul(5);
}

❯ make
[ 50%] Building CXX object skeleton/CMakeFiles/SkeletonPass.dir/Skeleton.cpp.o
[100%] Linking CXX shared module SkeletonPass.dylib
[100%] Built target SkeletonPass
❯ cc -c ../src/rtlib.c
❯ clang -fpass-plugin=skeleton/SkeletonPass.dylib -c ../target/foo.c
❯ cc ../src/rtlib.o foo.o -o exe
❯ ./exe
computed: 9
computed: -2
computed: 6

Difficulties

• I used VSCode for the task and Intellisense was broken after I updated to MacOS Sonoma. I had to spend some time fixing that, but after that was fixed things went pretty smoothly.

[bcarlet]

Summary

• LLVM Pass

Details/Testing

• I implemented a very basic dead code elimination pass, which deletes values that don't have side effects and whose use lists are empty.
• To test, I translated some of the Bril examples from test/tdce into C and inspected the resulting IR with and without my pass.

Difficulties

I ended up having a lot of trouble getting the mem2reg pass to run before my own (which was necessary because Clang would emit memory references by default, which my pass can't optimize). I'm still not entirely sure how to do this the correct way with the pass manager, but I was at least able to run everything with the opt command line tool.

[SanjitBasker]

I worked with @obhalerao on this project.

Summary

commit-based link

We implemented an LLVM pass that counts the number of times each loop is executed. To do so, we used LLVM's loop analysis to find all the natural loops and inserted a call to a logging utlity to increment the count for that loop. The runtime library is implemented in C++ using a nested std::unordered_map, so its capacity grows dynamically and works for any program that is transformed.

Testing

We used two benchmarks to test our implementation. In both cases, the output of the program to stdout was unchanged so we are confident that we have not altered the behavior of the program.

The first one was a contrived C program which had six for-loops, each of whose bodies execute for two iterations. We used this to check the correctness of our implementation (the header of the loop actually gets entered three times, since the condition is checked three times).

The second one was a C++ implementation of the Ford-Fulkerson algorithm for finding the max flow in a flow network, which has much more interesting control flow. Here is a snippet of the output (note that function 37 is main, and the max flow was 800):

function 4 had its 0th loop header execute 59334722 times
function 206 had its 0th loop header execute 1602 times
function 587 had its 0th loop header execute 80003 times
function 577 had its 0th loop header execute 11336490 times
function 376 had its 0th loop header execute 21 times
function 300 had its 0th loop header execute 41 times
function 329 had its 0th loop header execute 51 times
function 387 had its 0th loop header execute 1020 times
function 256 had its 0th loop header execute 2 times
function 193 had its 0th loop header execute 64082444 times
function 427 had its 0th loop header execute 51 times
function 37 had its 0th loop header execute 801 times
function 37 had its 1th loop header execute 21 times
function 37 had its 3th loop header execute 21 times
function 424 had its 0th loop header execute 51 times
function 101 had its 0th loop header execute 6588 times
function 507 had its 0th loop header execute 80003 times
function 449 had its 0th loop header execute 21 times
function 528 had its 0th loop header execute 80002 times
function 354 had its 0th loop header execute 51 times
function 267 had its 0th loop header execute 2 times
function 460 had its 0th loop header execute 1020 times

All the library functions that were included with the implementation of Ford-Fulkerson were also transformed by our pass, which explains why there seem to be far more loops (and functions) in our output than anticipated.

Difficulties

The main difficulty we encountered was getting the LLVM pass to work properly. In our current version of the code, there is a for-loop through the basic blocks of the function whose body only executes once. For future work, we would like to investigate the cause for this, clean up the code to avoid it, and finally restrict the pass to detect and ignore standard library functions in order to make the logs more comprehensible.

Initially, we implemented the runtime library as a 2D array in C and declared the dimensions of the array as a constant. After learning about C/C++ interoperability, we wrote it in C++ and got it to work pretty easily. We think it would be fun to re-write the runtime library in other languages like OCaml as well.

[rcplane]

Summary

@rcplane , @Enochen , and @zachary-kent collaborated on this project.

mem2reg pass

We were successfully able to modify C programs built with clang to reduce emitted llvm ir instruction count converting unnecessary memory stores to register usage while preserving execution correctness.

Implementation

• We adapted the code from here to develop a rudimentary mem2reg pass that promotes stack slots to variables. Specifically, many compiler frontends emit LLVM IR emulating mutation by reading and writing to a stack slot standing in for a temporary. This is technically SSA because, although it mutates memory, it does not reassign any variable.
• An alloca instruction stands in for a temporary if its only uses are stores; this ensures that no other memory location aliases it.
• After collecting all of the alloca instructions, which stand in for temporaries, we then perform phi insertion to insert phi nodes for the alloca to be converted into a temporary. We treat the initial set of defining blocks for an alloca as the set of blocks that write to that location, and use LLVM's DominatorTreeAnalysis pass and ForwardIDFCalculator to compute the dominance frontier; we then insert phi nodes into these blocks.
• We then proceed with the renaming step of SSA conversion, which is simplified by the fact that the code is already in SSA; stacks of variable names are replaced by stacks of values stored to a stack slot. For example, when we encounter store data, loc, where loc is known to be an alloca, we push data onto the stack of definitions for loc. Then, when we encounter x = load loc, where loc is known to be an alloca, we replace all uses of x with the top of the definitions stack for loc.
• Generative AI Use: ChatGPT4 September 25 version with Bing browsing enabled was used for initial code modifications intended as a reference implementation with some initial success in error reduction, but it failed to close the gap transitioning to function analysis manager refreshing for each function in the module. We did end up making near-complete rewrites of skeleton/Skeleton.cpp with no further ChatGPT input after initial adaptation attempts. ChatGPT4 was quite useful in quickly generating a few sample testing C programs with desired behaviors in short order.

Testing

turnt.toml

• We implemented three sample C programs performing array operations to test different cases of memory usage behavior inculding allocation in loops and printing verifiable results.
• We implemented a substantial set of turnt tests to verify clean build output, consistent execution output, and reduction in emitted llvm ir instruction count.
• Our memory allocation in a loop test exposed a segmentation fault in an early implementation, and required copying out the command with filename inlining to debug in detail.
• Due to time constraints, we did not pursue a broader benchmark suite of sample C programs including standard library program sets but our existing tools should scale reasonably to adding more test cases. Our usage of C++ has not been fully checked for memory safety, another sacrifice due to time constraints. We considered importing Bril programs from llvm conversion to run our optimization pass but did not fully pursue this idea.

Difficulties

• One source of problems was dealing with LLVM. The skeleton pass we started with was modeled as a module pass, but the mem2reg pass we wanted to implement was per-function. There was a lot of googling involved to figure out the right way to write our pass. This was made worse by the fact that LLVM had come out with a "new" Pass Manager system in the intervening time since LLVM 6, which rendered many resources we found (in the context of the legacy PM) unhelpful. We needed to use LLVM's dominator tree algorithms for our implementations as well, so we had to get extra familiar with the LLVM library.

• We also ran into issues while programming that were exacerbated by the fact that we were using C++. Anything in the pass that broke during execution would simply be a segfault, maybe accompanied by a sometimes-useful stacktrace. There were several bugs where the fix was easy and most of the time was spent tracking down the problem. We attempted lldb debugging in Visual Studio Code but resorted to the old fallback of print statements to isolate some issues, notably a need to check for a Def stack empty condition in successor iteration.

• Another obstacle we encountered with squashing bugs was in discovering the bugs themselves. After our "first draft" of the implementation was able to compile, we were able to apply the pass to a simple program and emit correct-looking IR. However, as we tested it on more programs, we discovered more issues. Compared to working with bril and the benchmark programs that were provided, it definitely felt more difficult to be confident in the correctness of our pass given the increased compexity of C/LLVM IR and starting from scratch with test cases. Subtle condition variations can have profound effects on program correctness and ability to compile, as we found when implementing Alloca escapes checking to invalidate potential Alloca instructions from consideration for optimization when later instruction uses can escape the load and store usage patterns we expect as safe to optimize.

[AliceSzzze]

Summary

link to the pass

I implemented a version of local copy/constant propagation in C++. The idea is that we keep track of the values that are stored and loaded into registers and propagate the copies where possible, creating opportunities for dead code elimination.

Implementation

There are two key-value maps for each basic block: one maps pointers to non-pointer operands, and the other maps operands to other operands that have the same value (similar to canonical homes in LVN). I differentiated pointers and non-pointers mostly because I couldn't find a good way to extract the register from the pointer value (e.g. %1 from ptr %1) in LLVM.

When we store an operand to %p, we add this mapping to the ptr2Op map. When a value is loaded from %source to %target, we check if %source exists as a key in our ptr2Op map. If so, there is a canonical home for this value, and we can add another mapping from %target to the canonical home. The %target instruction can then be eliminated because we can just replace its uses with the canonical home.

If there is a new store to a pointer, we replace the mapping in ptr2Op, but the mappings in op2Op can remain unchanged because the values have already been loaded, and we don't assign twice in SSA.

There are some caveats to this. I made some assumptions about aliasing, which might not hold. We could imagine a scenario where multiple pointers point to the same location and we are not able to detect the mutation.

I rewrote some of the arguments in stores and binary operators, but not all pattern are covered. I also tried to add LLVM's dead code pass to the pass pipeline but I wasn't sure how I could do that. So I have not eliminated the dead code and have not measured the speedup. To see which instructions we can eliminate, I added statements that print "dead code {instruction}", as shown below.

Testing

I asked ChatGPT to generate a "real-ish C program", and it gave me one that computes the factorial. I verified that the results were the same with or without the pass. I also ran some smaller hand-written programs.

Difficulties

• Most of the time was spent reading documentation. ChatGPT was surprisingly helpful when I asked it questions like "how do I create a store instruction in LLVM"?
• I spent a while trying to add another pass. If anyone knows how to add this to the existing code do let me know!

Example

The "dead code" statements at the bottom of the output tell us which instructions could be eliminated. For example, %4 can be removed because it can be replaced with %0. Some of the instructions have been rewritten (e.g. %13 was used in the original version but not here), others have not.

; Function Attrs: noinline nounwind optnone ssp uwtable
define i64 @factorial(i32 noundef %0) #0 {
  %2 = alloca i64, align 8
  %3 = alloca i32, align 4
  store i32 %0, ptr %3, align 4
  %4 = load i32, ptr %3, align 4
  %5 = icmp eq i32 %4, 0
  br i1 %5, label %9, label %6

6:                                                ; preds = %1
  %7 = load i32, ptr %3, align 4
  %8 = icmp eq i32 %7, 1
  br i1 %8, label %9, label %10

9:                                                ; preds = %6, %1
  store i64 1, ptr %2, align 8
  br label %17

10:                                               ; preds = %6
  %11 = load i32, ptr %3, align 4
  %12 = sext i32 %11 to i64
  %13 = load i32, ptr %3, align 4
  %14 = sub nsw i32 %0, 1
  %15 = call i64 @factorial(i32 noundef %14)
  %16 = mul i64 %12, %15
  store i64 %16, ptr %2, align 8
  br label %17

17:                                               ; preds = %10, %9
  %18 = load i64, ptr %2, align 8
  ret i64 %18
}


dead code   %4 = load i32, ptr %3, align 4
dead code   %7 = load i32, ptr %3, align 4
dead code   %11 = load i32, ptr %3, align 4
dead code   %13 = load i32, ptr %3, align 4
dead code   %18 = load i64, ptr %2, align 8

[20ashah]

Summary

• Pass

For this task, @JohnDRubio and I implemented the basic task of identifying when we found a floating point division instruction for each instruction in the program.

Implementation

As shown in class, we looped over each function, and through each basic block for that function, and finally through each instruction in that basic block. For each instruction, we first checked if it contained a binary operator. If it didn't, we knew it couldn't be a floating point division instruction. If there was a binary operator, we then extracted the opcode and checked if it was a floating point division operator (by comparing it to the enum Instruction::FDiv).

Testing

We ran some basic tests with and without floating point division to make sure that our pass ran correctly. Once confirming that, we picked a real-ish C++ program to run our pass to verify that nothing broke and that it correctly found floating point division instructions. For this test program, we used the Ray - Sphere Intersection algorithm

Difficulties

There were no real difficulties in the assignment, mainly just using LLVM documentation to figure out how to extract the opcode for an instruction and checking that it was a floating point division opcode.

[yxd97]

Summary

• I implemented an LLVM pass that truns integer multiplication into a series of shifts and adds. (Code)
• I did not use any AI tools for this task.

Implementation

• Any integer can be broken into sum of powers of 2: 10 = 2 + 8
• Therefore, if we find there is an integer multiplication with one operand being a constant, we can distrubute the other operand into the sum of powers of 2, and further turn the multiplication into left shifts:

x * 10 -> x * 2 + x * 8 -> (x << 1) + (x << 3)

• The LLVM pass I implemented will check every instruction in the IR and see if any operand of an integer multiply is a constant. If so, it will add a bunch of shifts and adds after that instruction, and update all uses of the original multiplication to be the new result given by the shifts and adds.
• After the pass, the original instruction/value is not used in the program. It can be easily deleted by dead code elimination.
• If both operands of the multiply are constants, the pass do NOT change it. The idea is this scenario might be captured by constant propapation or constant folding passes.

Testing

• I first created a trivial test case, imul.c, which multiplies any input by 3. This test helped me to develop the basic logic of the LLVM pass.
• I also created test cases including positive, negative, and powers of 2 being the constant side, to fully examine the functionality of my pass.
• In addition, I tested my pass on multiplications that will overflow a 32-bit integer, as well as a chain op multiplications like x*2*3*y.
• All programs will be compiled with clang with/without the pass being applied. Their results are compared to make sure this pass preserves the functionality of the program.
• The LLVM IR of the original and tranformed programs are dumped to verify that my pass actually did something.
• Finally, I generated an FIR filter from an online FIR designer that can generate C code using quantized coeffcients and unrolled convolution. The filter being tested is a low-pass filter with 27 taps. You can find the generated code in SampleFIR.c.

Challenges

Since my pass works on the LLVM IR, I have to keep in mind how a C program is parsed and tranformed into that IR. Actually I initially planned to do something with the logical operators in C (i.e., &&). However, due to the short-circuit behavior, there is no logical operators in the IR; && will be turned into a series of branches. Then I had to re-design my pass to be the one I finally submitted.

[stephenverderame]

Summary

Repo

I implemented an LLVM pass which determines if potentially null pointers are loaded from or stored to, and if so, prints an error message and aborts compilation. To do this, I reimplemented my generalized data flow framework, and developed a conditional interval analysis. I originally thought using LLVM's LazyValueInfo pass would suffice, but this pass doesn't seem to support loops, and the ScalarEvolutionPass seems to only support loops. Perhaps I used them wrong, but I couldn't figure out any pass that would provide global interval analysis, therefore I ended up writing my own, which is the more complicated part of this.

Implementation

This ended up being a bit more ambitious than I originally anticipated, and as mentioned, involved also writing an interval analysis pass. For the null pointer check, I currently perform an abstract interpretation of the IR, and flag every use of a pointer as non null, or potentially null. Then, I run through all the instructions, and check to make sure every load and store uses only pointers that are definitely null. To support array indexing, I use an interval analysis to determine a conservative range of every integer via abstract interpretation. Then, in the null pointer abstract interpretation, getelementptr will return a definitely non null pointer if the bounds of all indices are within the size of the data of the pointer.

There were A LOT of cool ideas I got when implementing this that I didn't have time to work on (yet). Some included expanding the interval analysis to support variables. For example, although a and b might be unbounded, we might know that a < b, the pointer points to b bytes, and the loop index is bounded by a. Other things I didn't get a chance to do include handling intrinsics, C++ dynamic allocations, malloc, and storing intervals in nested pointers. Another idea is to apply interprocedural analysis, which would allow being much less restrictive on functions with internal linkage.

Testing

I developed some tests that cause violations and passes as I was working on this. I wrote tests to try and hit corner cases. However, this is definitely undertested.

Challenges

This ended up being more of an undertaking than I initially anticipated. The interval analysis was also more involved than I anticipated as well.

[jiahanxie353]

Summary

I implemented a pass to flip all predicates of the if-else branch.

Implementation

LLVM has CmpInst whose two subclasses are FCmpInst and ICmpInst. So I also created an abstract class for Int and Float condition class to flip the message and print the message correspondingly. I iterate over the functions, blocks, instructions and check if it's a conditional instruction. If it is and is comparing between two integers, I dynamically cast the condition to IntConditionClass; and do the same for float comparisons. Then I will invoke flip and print and let polymorphism to do its job.
I test it by looking at the emitted LLVM IR and make sure it's doing the right thing.

Challenges

It is a pretty straightforward and unambitious task :)