Exercises for Week 4

Exercises for Week 4#

Exercise overview#

This week’s exercises are about writing LLVM by hand, which will help us get some understanding of the basic structure of LLVM programs.

Division function#

Basic division#

Write an LLVM function f_mod (a, b) that takes two 64-bit arguments a and b and returns as its result the value. a mod b.

To start, all you need is an empty file, in which you declare your function (single-line comments in LLVM start with a semicolon)

; save this as prog.ll
define i64 @f_mod(i64 %a, i64 %b) {
    ; Write your code here 
    ; ... 
}

To test your program, proceed as follows. Suppose your program is saved in a file prog.ll. Then we can use the following C wrapper main.c.

/* save this as main.c */
#include <stdio.h>
#include <stdlib.h>

extern int f_mod(int a, int b);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        printf("Please call this program with two arguments: %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 link everything with clang

clang main.c prog.ll

Run the resulting program, on several arguments, e.g., ./a.out 1 1 and ensure that you get the right behavior. What happens when the second argument is 0?

Adding division by zero protection#

Let us ensure that we check against division by zero. We will need two things

  1. The error handling code that will ‘’gently’’ stop program execution.

  2. The comparison in the LLVM code.

For the error handling code, let us add a function

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

Our LLVM program will need a line saying that error_div_by_zero is an external function.

declare void @error_div_by_zero()

Note

Observe the difference between declare and define.

Compile, and test your implementmation, and validate that the error handling that you have implemented indeed works.

Euclidean algorithm for computing GCD in LLVM#

In this task, we implement GCD calculation using Euclidean algorithm.

Reference implementation in a programming language of choice.#

Start off by recalling the definition of GCD and Eucli’s algorithm by implementing it in a programming language of your choice. Write two implementation: one using a loop, and one using recursion. Check that they compute the same things.

LLVM implementations#

  • Write an LLVM function gcd_1 that implements the Euclid’s algorithm. Decide whether you want that to be a loop-based one or a recursive one. Modify the C wrapper so that it calls gcd_1 instead of the f_mod from before.

  • Write an LLVM function gcd_2 that uses the other approach for the Euclid’s algorithm. Modify the C wrapper, one more time.

Which of the two is shorter? Which one is easier to understand?

  • How many basic blocks do you have in your program. Can you rearrange the basic blocks and run your program again. Does it change program semantics and how?

Hardening against divisions by zero#

An important aspect of code generation in compilers is that most of the code generation for simple operations, such as division, is context-independent. That means that if your general compilation strategy is such that you generate division by zero checks, then it is normal for these checks to be present against all divisions. The idea is that usually it is the job of the later phases, e.g., compilation, to perform the cleanup and remove unnecessary checks.

  • Write the code for gcd_1 and gcd_2 as if it was generated by a compiler that generates division by zero checks but that is unaware of the context surrounding the division operation.

Contents