Google's 3D view over Vallila/Helsinki

And so Google Earth got 3D view of Helsinki [digitoday.fi]. Here's a picture depicting Vallila, that is, my current home.

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.

Sex differences

I wanted to see what kind of questions we are asking about the opposite sex. Google. Let us assume that questions asked about men are usually asked by women and vice versa.

Top suggestions for 'how do women...':
1. get pregnant
2. think
3. get yeast infections
4. flirt
5. come

Top suggestions for 'how do men...':
1. think
2. fall in love
3. flirt
4. get hpv(*)
5. get yeast infections

(*) human papillomavirus

Comparing the first matches makes me sad.

Emil finds its first defect!

I earlier described the nature of my work at TKK tcslab. My job is to write a tool for automatically testing C programs using a technique called dynamic symbolic execution basing the implementation on LLVM. I call my tool Emil (that is ucfirst(reverse(lower(Lime))) after a similar tool called Lime for testing Java programs, developed here as well).

Emil is currently at 2.9 KLOC, and for the first time, I wrote a test case that should fail, and it failed on the first attempt! This is somewhat a milestone so I now celebrate it by showing the test case and the failing inputs found by Emil. This is of course all trivial and useless, but I believe Emil is going to the right direction.

==divzero.c==

int input(void);
int main() {
    int i = input();
    int j = input();
    if (i > j) {
        i = i / (0*j); // ouch
    } else {
        i = j;
    }
    return i;
}

==Values for i, j by Emil that will lead to division by zero==
{i: 892648572, j: -1285173836}

I hope this is just the beginning for Emil. The future of Emil will be out of my hands, though, because I will (in my current knowledge) leave Emil in the hands of others before next year and be searching for new challenges in the software industry.

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.

C++ name mangling

Ever wondered what the 'extern "C" { ... }' block stands for in C++? In C and C++ the 'extern' keyword is used to declare external variables that are instantiated in other translation units. Using 'extern' tells the compiler not to allocate space for the variable as space is being allocated elsewhere. The keyword is also used within variable instantiation. In that case its semantics are to denote that the variable may be referenced from other translation units.

The 'extern "C" { ... }' block, however, has additional semantics. Let's first explain what name mangling is and why it is required.

In C functions cannot be overloaded by type. Thus we cannot declare, for example, functions with prototypes 'int foo(void)' and 'int foo(int)' in the same program. In C++, however, such overloading is possible. Due to the tight coupling of C and C++, particularly in the past (C++ was first implemented by compiling C++ code to C code and then using a regular C compiler to produce machine code), C++ compilers must use distinct symbols for overloaded functions to be compatible with the linker. Name mangling is the act of adding type information in the function names to separate overloaded functions from each other.

For example, the GNU C compiler mangles the first 'foo' function [int foo(void)] to '_Z3foov' and the second 'foo' function [int foo(int)] to '_Z3fooi'. The '_Z' is just a prefix that is a unique identifier in C/C++ that prevents conflicts with user defined identifiers. The number is the length of the original name, three in case of 'foo', and the following letters encode argument types (here 'i' for int and 'v' for void, respectively).

Now, suppose there is a C++ function 'bar' that we would want to use in our C module. We would declare a prototype for 'bar' in the C module that references the function and link the C module with the C++ module, that provides the definition for 'bar'. Let's try just that:

-------module.c--------
int bar(void);
int hooray() {
    return bar() + 42;
}
-----------------------

-------bar.cpp--------
int bar(void) {
    return 7;
}
-----------------------

Let's first compile our modules:

$ g++ -c -O0 -o bar.o bar.cpp
$ gcc -c -O0 -o module.o module.c


Then link them together to produce an executable

$ gcc -O0 bar.o module.o


 module.o: In function `hooray':
 module.c:(.text+0x7): undefined reference to `bar'
 collect2: ld returned 1 exit status

The linker could not find 'bar' from the symbol table. And that is precisely due to C++ name mangling. Let's have a look inside bar.o:

$ objdump -D bar.o

 -- [clip] --
00000000 <_Z3barv>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   b8 07 00 00 00          mov    $0x7,%eax
   8:   5d                      pop    %ebp
   9:   c3                      ret
 -- [/clip] --

There it is again, the function is called '_Z3barv' instead of 'bar'. This is the point where the extern "C" block comes to the rescue. It declares that the symbols declared inside the block are to be referenced from C context, and thus the compiler cannot mangle the names.

If the code in bar.cpp is wrapped inside the extern "C" block, everything will work:

-------bar.cpp--------
extern "C" {

int bar(void) {
    return 7;
}

}
-----------------------

Recompiling bar.cpp:

$ g++ -c -O0 -o bar.o bar.cpp

.. and relinking the modules:

$ gcc -O0 bar.o module.o


No errors. If you now disassemble bar.o you will see that the name of the bar function is now 'bar' instead of '_Z3barv', and thus the C module is able to reference the C++ function.

Software recommendations

It took a while but I have now replaced grep with ack to satisfy my daily grepping needs.

Another tip of the day is that if you are a Vim user you will want to start using ctags to move around in your codebase.