Exercises for Week 45

Contents

Exercises for Week 45#

This week’s exercises are about getting to know how to use LLVM’s getelementptr (GEP) instruction.

Tuples#

  1. Create an LLVM struct for tuples, called Tuple, consisting of two i64 fields.

  2. Create the following LLVM functions:

    1. create_tuple that takes two i64 arguments and returns a tuple initialized with these arguments. Use the C malloc function to allocate the tuple on the heap. Discuss in class what size argument to pass to malloc.

    2. get_first that takes a tuple and returns its first element.

    3. get_second that takes a tuple and returns its second element.

    4. set_first that takes a tuple, and an i64 value and performs an in-place update of the first element of the tuple.

    5. set_second that takes a tuple, and an i64 value and performs an in-place update of the second element of the tuple.

    6. swap_elements that in-place swaps the first and the second elements of the tuple.

  3. Write an LLVM program that tests the functionality of the above functions.

  4. Modify your create_tuple function so that the allocation takes place on stack instead of the heap. Does the program created in step (3) above still work? If yes, can you come up with a program that works in the heap-allocated version of create_tuple but does not work in the stack-allocated version?

  5. Write an LLVM function swap_tuple_array that takes three arguments:

    1. a pointer to an array of tuples

    2. an i64 integer i

    3. an i64 integer j

    This function should swap the elements i and j in the provided array.

  6. Write an LLVM program that tests the functionality of the above functions.

  7. Consider two alternative implementations of the Tuple

    1. as an LLVM array of two fields.

    2. as an LLVM pointer.

    How would your implementation of the above functions change in each case?

Nested GEPs#

Consider the following C program

#include <stdlib.h>

struct B { 
  int p;
  int *f; 
  int q;
};

struct A {
  int g;
};

void update_two (struct A** a, struct B b) {
  a[b.f[2]]->g = b.p + b.q;
}

int main() {
  struct A **a = malloc(10 * sizeof(struct A*)); 

  for (int i = 0; i < 10; ++i) {
    a[i] = malloc(sizeof(struct A));
    a[i]->g = 0;
  }

  struct B b;
  update_two (a,b);

  int array_for_f[3] = {0, 1, 4}; 
  b.f = array_for_f;


  return 0;
}

Compile the above function to LLVM, using -emit-llvm -S flag passed to clang. Modify the LLVM code for function update_two to use as few GEPs as possible.

Note

Counting the number of GEPs is generally not a meaningful metric for the quality of code generation. We use it here only as an exercise device to learn GEP.

Contents