binutils-dev only supplies a static archive for libiberty. On AMD64, this means that you can't use libiberty functions in shared libraries, because libiberty.a isn't compiled with -fPIC. Seems to me that all library packages on AMD64 should come with shared libs. d