Exercises for Week 37

Exercises for Week 37#

Exercise overview#

This week’s exercises focus on writing LLVM– code by hand, understanding control flow structures, and debugging LLVM– programs. Through these exercises, you’ll gain practical experience with loops, conditionals, basic blocks, and common pitfalls in LLVM– programming.

Part 1: Perfect numbers in LLVM–#

Consider the following Dolphin program that finds perfect numbers:

void number_perfect(n : int){
  var i = 1;
  while(i <= n){
    var temp = 0;
    for (var j = 1; j < i; j = j + 1){
      let d = i % j;
      temp = temp + (d == 0 ? j : 0);
    }
    if(temp == i)
      print_perfect(i);
    i = i + 1;
  }
}

The function print_perfect is defined as follows in a C file that is to be linked with your LLVM file:

#include <stdio.h>
#include <inttypes.h>

void print_perfect(int64_t i) {
  printf("%" PRId64 ": perfect\n", i);
}

int main() {
  number_perfect(10000);
  return 0;
}

The expected output is:

6: perfect
28: perfect
496: perfect
8128: perfect

Task: Understanding the algorithm#

Pick your favorite programming language and rewrite the program above, including the C wrapper. Write comments explaining the most important lines of code. In your implementation, identify what makes a number “perfect” (hint: a perfect number equals the sum of its proper divisors).

Task: Translate to LLVM–#

Translate the Dolphin function number_perfect into LLVM–. Test your implementation by linking with the C wrapper and running with different inputs:

clang perfect.ll main.c
./a.out

Task: Analyze basic blocks#

Count the number of basic blocks in your LLVM– program. Identify where each basic block starts and ends, and explain what causes the creation of new basic blocks in your code.

Advanced task: Using Phi nodes#

Rewrite the ternary operator (temp = temp + (d == 0 ? j : 0)) using Phi nodes instead of conditional branches with stores/loads.

Advanced task: SSA form without alloca#

Challenge yourself by rewriting your entire LLVM– implementation without using any alloca instructions. This will require careful use of Phi nodes to maintain SSA form.

Part 2: Division and modulo operations#

Task: Basic modulo function#

Write an LLVM function f_mod(a, b) that takes two 64-bit arguments and returns a mod b:

define i64 @f_mod(i64 %a, i64 %b) {
    ; Your code here
}

Test with this C wrapper:

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

extern int f_mod(int a, int b);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        printf("Usage: %s <a> <b>\n", argv[0]);
        return 1;
    }
    
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);
    int result = f_mod(a, b);
    
    printf("%d\n", result);
    return 0;
}

Compile and test: clang main.c prog.ll

Explore what happens when the second argument is 0.

Task: Adding division by zero protection#

Enhance your implementation with proper error handling:

  1. Add an error handler in C:

void error_div_by_zero() {
    printf("Error: division by zero\n");
    exit(1);
}

  1. Declare it as external in LLVM:

declare void @error_div_by_zero()

  1. Add the necessary comparison and branching in your LLVM code to check for zero divisor before performing the operation.

Test that your error handling works correctly.

Part 3: Euclidean algorithm for GCD#

Task: Reference implementations#

Implement the Euclidean algorithm for computing GCD in your favorite programming language. Create two versions:

  • One using a loop

  • One using recursion

Verify that both compute the same results.

Task: LLVM implementations#

  1. Write an LLVM function gcd_1 that implements Euclid’s algorithm (choose either loop-based or recursive).

  2. Write an LLVM function gcd_2 using the alternative approach.

  3. Compare both implementations:

    • Which is shorter?

    • Which is easier to understand?

    • How many basic blocks does each have?

Task: Basic block analysis#

Experiment with rearranging the basic blocks in your GCD implementations. Does changing their order affect program semantics? Explain your findings.

Task: Compiler-style division checks#

Rewrite both gcd_1 and gcd_2 as if generated by a compiler that always produces division-by-zero checks, regardless of context. This simulates how real compilers generate defensive code that later optimization passes might remove.

Part 4: Debugging LLVM– code#

Consider this Dolphin function:

int rec_fun(acc : int, n : int){
  if(n > 0)
    return rec_fun(acc + 2, n - 1);
  return acc;
}

When called as rec_fun(0, -10), it should return 0.

However, a buggy compiler produced this LLVM– code that crashes with a segmentation fault:

define i64 @dolphin_fun_rec_fun (i64 %acc, i64 %n) {
 %n$1 = alloca i64
 %acc$0 = alloca i64
 store i64 %acc, ptr %acc$0
 store i64 %n, ptr %n$1
 %load_local_var$2 = load i64, ptr %n$1
 %arith_comp_op$3 = icmp sgt i64 %load_local_var$2, 0
 br i1 %arith_comp_op$3, label %ifthenelse_true_branch$4, label %ifthenelse_false_branch$5
 ifthenelse_true_branch$4:
 %load_local_var$7 = load i64, ptr %acc$0
 %arith_bin_op$8 = add i64 %load_local_var$7, 2
 %load_local_var$9 = load i64, ptr %n$1
 %arith_bin_op$10 = sub i64 %load_local_var$9, 1
 %call$11 = call i64 @dolphin_fun_rec_fun (i64 %arith_bin_op$8, i64 %arith_bin_op$10)
 ret i64 %call$11
after_return$12:
 br label %ifthenelse_merge$6
 ifthenelse_false_branch$5:
 br label %ifthenelse_merge$6
 ifthenelse_merge$6:
 %load_local_var$13 = load i64, ptr %acc$0
 ret i64 %load_local_var$13
after_return$14:
 unreachable
}

Task: Identify the bug#

Find the issue in the LLVM– code that causes the segmentation fault when calling rec_fun(0, -10). Explain why the segmentation fault occurs.

Task: Compiler bug analysis#

Make an educated guess about what the compiler did wrong to produce this buggy code. What mistake in the code generation phase led to this issue?

Task: Other potential issues#

Identify at least one other way a subtle mistake in code generation could cause a segmentation fault in recursive programs like this one. Provide a concrete example.

Contents