LLVM assembly and integer signedness

LLVM assembly does not encode integer signedness which can be a nuisance when reading the assembly code. On the other hand the policy simplifies the representation, as the sign does not make a difference in most of the operations (such as integer addition). In some operations (such as boolean comparisons on integers <, <=, >, >=) signedness is significant, however. For completeness, let's remember that the (dis)equality operator does not care about the sign.

Let's have a look on the following C program block:

if (x < UINT_MAX-1)
    puts("foo");
else
    puts("bar")

Piping clangs's output to llvm-dis gives us the following LLVM assembly representation:

%1 = load i32* %x, align 4
%2 = icmp ult i32 %1, -2
br i1 %2, label %bb, label %bb1

bb:
%3 = call i32 @puts(i8* getelementptr ([4 x i8]* @.str, i32 0, i32 0)) nounwind
br label %bb2

bb1:
%4 = call i32 @puts(i8* getelementptr ([4 x i8]* @.str1, i32 0, i32 0)) nounwind
br label %bb2

bb2:

Now, in the assembly code, it can be read that the %1 register is compared with -2, and the operands are to be interpreted as unsigned 32-bit integers. On the bit level, that is of course correct. However, a human needs to make a conversion in her head to understand on what concrete values of %1 the first branch is taken.

In the two's complement, the first bit represents the sign. For negative numbers, the sign bit is set, for positive, it is unset. The number zero is represented as a value where all bits are unset. The smallest negative value of an n-bit integer is represented as one followed by n-1 zeros. Semantically it can be thought as if the rightmost n-1 bits represent a positive value that is summed with the smallest negative value available (-2^(n-1)), and the result is something between -2^(n-1)..-1.

Assuming 4-bit integers, -2 is represented as 1110 (-2^3 + 6). When 1110 is interpreted as an unsigned integer, that is 14 (2^3 + 2^2 + 2^1). However, in our example, we have 32-bit integers (the i32 type in LLVM), where the min value for int is -2147483648. In the 32-bit world, -2 is represented by a number where there are 31 ones followed by a zero. Interpreted as unsigned, that is 2^31 + 2^30 ... 2^2 + 2^1 = 4294967294.

So we came to the conclusion, for values of %1 < 4294967294, the first branch is taken. Otherwise the second branch is taken. That was not obvious directly from the assembly code. We had to consider the integer width to deduce the concrete unsigned value.

It should be noted that one can decide whether to write integer literals as the llvm tools do or not. Since the bit representation is identical for signed i32 -2 and unsigned i32 4294967294, it does not matter which way it is written. I would still stick to the signed interpretation for consistency's sake. Otherwise it becomes a hopeless mess.

Back to work

Ah, my week-long summer vacation is now over. I mostly spent the time in a friend's summer cottage in Sysmä and in the beautiful archipelago of Sipoo. Last two days I was in Porvoo. Vacation reading included works from Hesse and Solzhenitsyn, but I especially want to raise Erlend Loe's Naive, Super that I fell in love with when sitting in a bus.

As for work, I'm now familiar with LLVM optimization pass architecture and implementation. It all feels intuitive. On the negative side, C++ frequently demonstrates its clumsiness in basic tasks. Also, the LLVM API is poorly documented, so I constantly find myself grepping (actually, ack'ing) around the LLVM tree and reading code rather than the doxygen (huh) generated API. However, all in all I'm definitely thankful for LLVM.org/docs.

About the summer job

Just a few notes to document my initial feelings about the approaching summer job research project at TKK.

I'm going to work in a group where the broad subject of interest is computer aided verification and testing, CAV. My work will be based on Koushik Sen's doctoral thesis Scalable automated methods for dynamic program analysis. More specifically, based on Sen's thesis, friends at TKK (and elsewhere) have developed an automated testing tool LIME which is used to build useful automatic test cases for Java programs.

My job is to experimentate if we can easily build a similar tool for programs written in C - using LLVM. Incidently, or not, the very same tool I'm describing in my master's thesis.

I'm definitely looking forward to the job. I also believe LLVM is the right choice for implementing the tool due to its extendable C++ interface for analysing and transforming LLVM code.

Benchmarking llvm-gcc and gcc

I just compiled llvm-gcc (4.2.1 with LLVM 2.6svn) and did some benchmarking. Given a naive implementation of the Fibonacci sequence (fib.c):

#include <stdio.h>

unsigned long int fib(int n) {
   if (n < 3)
       return 1;    
   return fib(n-2) + fib(n-1);
} 

int main() {
   int i;
   for (i=1; i < 46; i++)
       printf("fib(%d) = %ld\n", i, fib(i));
   return 0;
}

Then we compile with -O3:

llvm-gcc -O3 fib.c -o fib-llvm-gcc
gcc -O3 fib.c -o fib-gcc

And the results:

time ./fib-llvm-gcc
real 0m3.053s
user 0m3.052s
sys 0m0.000s

time ./fib-gcc
real 0m11.176s
user 0m11.173s
sys 0m0.004s

That is something.

What comes to code size (both in x86 assembly), the faster is also the smaller:

wc fib-llvm-gcc.S
108 288 1900 fib-llvm-gcc.S

wc fib-gcc.S
291 738 4485 fib-gcc.S