Blogged by Ujihisa. Standard methods of programming and thoughts including Clojure, Vim, LLVM, Haskell, Ruby and Mathematics written by a Japanese programmer. github/ujihisa

Saturday, December 26, 2009

LLVM For Starters

Installation of LLVM Compiler and Runtime

See the previous post.

Overview of LLVM

To write a helloworld application, you can choose a path where to start. The typical path is,

  1. Write a code in LLVM Assembly Language (.ll)
    • $ vim sample.ll
  2. Compile it to LLVM Bytecode (.bc)
    • $ llvm-as sample.ll
  3. Run it on LLVM interpreter
    • $ lli sample.bc

Or,

  1. ditto
  2. ditto
  3. Compile it to Executable Binary File
    • $ llc sample.bc
  4. Run it!
    • $ ./sample

In this post, I'll explaing about the first step "LLVM Assembly Language".

Helloworld in LLVM Assembly Language

LLVM is not a stack machine but a register machine.

tableoftype

tableoftype

(This table is from wikipedia)

Let's write helloworld application. Before that, I'll show the equivalent code in C.

int main() {
  puts("Hello, world!");
  return 0;
}

In LLVM Assembly Language, the code will be written as below.

@str = internal constant [14 x i8] c"Hello, world!\00"
declare i32 @puts(i8*)
define i32 @main()
{
  call i32 @puts( i8* getelementptr ([14 x i8]* @str, i32 0,i32 0))
  ret i32 0
}

This code suggests the following notices:

  • We can write an integer number directly in the assembly code, on the other hand, we cannot write a string directly.
  • The long name getelementptr seems to be * in C.

If I write helloworld in C like the LLVM Assembly code, it is like:

char str[14] = "Hello, world!";
int main() {
  puts((char *)str);
  return 0;
}

Fibonacci in in LLVM Assembly Language

Nanki wrote Fibonacci in LLVM Assembly Language.

@str = internal constant [4 x i8] c"%d\0A\00"

define void @main() nounwind {
init:
  br label %loop
loop:
  %i = phi i32 [0, %init], [%i.next, %loop]
  %fib = call i32 @fib(i32 %i)

  call i32 (i8*, ...)* @printf( i8* getelementptr ([4 x i8]* @str, i32 0, i32 0), i32 %fib)

  %i.next = add i32 %i, 1

  %cond = icmp ult i32 %i.next, 30
  br i1 %cond, label %loop, label %exit

exit:
  ret void
}

define i32 @fib(i32 %n) nounwind {
  %cond = icmp ult i32 %n, 2
  br i1 %cond, label %c1, label %c2

c1:
  ret i32 1
c2:
  %n1 = sub i32 %n, 1
  %n2 = sub i32 %n, 2

  %fib1 = call i32 @fib(i32 %n1)
  %fib2 = call i32 @fib(i32 %n2)

  %r = add i32 %fib1, %fib2
  ret i32 %r
}

declare i32 (i8*, ...)* @printf(i8*, ...) nounwind

To understand the code deeper, let me write back the code in C.

#include<stdio.h>
int fibonacci(int n);

int main() {
  int i, i_next, fib;
init:
  i = 0, i_next = 0;
loop:
  i = i_next;
  fib = fibonacci(i);
  printf("%d\n", fib);
  i_next = i + 1;
  if (i_next < 30) {
    goto loop;
  } else {
    goto exit;
  }
exit:
  return 0;
}

int fibonacci(int n) {
  int cond, n1, n2, fib1, fib2, r;
  cond = n < 2;
  if (cond) {
    goto c1;
  } else {
    goto c2;
  }
c1:
  return 1;
c2:
  n1 = n - 1;
  n2 = n - 2;
  fib1 = fibonacci(n1);
  fib2 = fibonacci(n2);
  r = fib1 + fib2;
  return r;
}
  • LLVM Assembly Language enables us to use the same name both for a variable and a function because of the existence of prefix
  • LLVM Assembly Language cannot handle many calculation at the same time like return fib(n-2) + fib(n-1).

7 comments:

  1. Thank you! I was looking for a very simple example and that's exactly what you provided.

    ReplyDelete
  2. You're welcome. I found that the example code didn't work with the latest version of llvm. I'll write a new entry later.

    ReplyDelete
  3. I could fix it like this on llvm-3.1:
    %cast = getelementptr [4 x i8]* @str, i32 0, i32 0
    call i32 (i8*, ...)* @printf( i8* %cast, i32 %fib)

    It should work without the cast tmpvar, but the extended type after "call" is necessary.

    ReplyDelete
  4. update for latest llvm: change the printf call line to:
    call i32 (i8*, ...)* @printf( i8* getelementptr ([4 x i8]* @str, i32 0, i32 0), i32 %fib)

    ReplyDelete
  5. I get the following error when using llvm-as

    fibonacci.ll:10:24: error: invalid forward reference to function 'printf' with wrong type!
    call i32 (i8*, ...)* @printf( i8* getelementptr ([4 x i8]* @str, i32 0, i32 0), i32 %fib)

    ReplyDelete
  6. Right, sorry i was not clear i think or maybe suggested a wrong update. Diff against version above:

    38c38
    < declare i32 (i8*, ...)* @printf(i8*, ...) nounwind
    ---
    > declare i32 @printf(i8*, ...) nounwind

    In other words: the (i8*, ...)* signature must only be added to the 'call' OP, not the 'declare' part.

    lli fib.ll works for me this way, regards.

    ReplyDelete

Followers