Showing posts with label compilers. Show all posts
Showing posts with label compilers. Show all posts

Wednesday, June 17, 2009

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.

Tuesday, February 17, 2009

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

Friday, March 21, 2008

How little streams of knowledge converge, generating joy

The rewarding moments of studying are those when we realize new applications for previously learned knowledge. Tonight I had to skip taocp and read the Dragon book (_the_ compilers book), because I'm attending a compilers course at the university. So the topic was syntax directed definitions and attribute grammars, and among other things, it discussed the evaluation order of node attributes of a syntax tree with attribute dependence edges already in place. It was immediately obvious that by topologically sorting the graph we can find a valid evaluation order.
In computer science studies, it's not always very clear what the real applications for the techniques presented are. This was one of the happy moments when previously learned knowledge came in to good use.
I remember my history studies in senior high, when it first felt difficult to understand some of the reasons behind historical facts. In the end, after all courses, the little streams of knowledge finally converged and started to explain each other. Understanding is vital in studying, because when you understand something, you don't have to be a good memorizer. It's enough to remember the main points actively, and then you can reconstruct the the rest by deduction.
My advice to fellow students is: don't think reading as memorizing, think it as understanding. This way you won't need to read anything twice.