Safe Identical Code Folding for X86-64.

[Sriraman Tallam <tmsriram at google dot com>]

Hi,

     I am implementing a safe ICF option for gold that looks at
relocation types and tries to figure out if it is a function pointer
taken versus a function call. Please recall that ICF is not safe when
function pointer checks are present in the code. So, with safe ICF, I
try to fold only functions that are guaranteed to not have their
function pointer taken other than for vtable purposes. Currently, safe
ICF only folds ctors and dtors as their pointers can never be taken.

I have tried to do this for AMD X86-64. Here are the observations I
have used to write the patch. Most of this stuff should be familiar to
you all. I have also attached the patch.

Case (i) : For position dependent code (non-PIC),  there is no
problem. A function call is always a PC relative relocation and a
function pointer is a direct relocation.

Here is an example :

test.cc :

int foo()
{
 return 1;
}

int bar()
{
 int (*p)() = foo;
 p();
}

$ g++ -c test.cc
$ readelf --relocs test.o

Relocation section '.rela.text._Z3barv' at offset 0x660 contains 2 entries:
 Offset          Info           Type           Sym. Value    Sym. Name + Addend
00000000000c  000a0000000b R_X86_64_32S      0000000000000000 _Z3foov + 0
000000000011  000a00000002 R_X86_64_PC32     0000000000000000 _Z3foov
+ fffffffffffffffc


R_X86_64_32S is the relocation type of the pointer and R_X86_64_PC32
is the relocation type of the call. Hence, I can look at the
relocation type and exclude any function from being folded if there is
a direct relocation against it.

Case (ii) : Shared Libraries.

For shared libraries, in x86_64, they *have to be built in -fPIC mode.
Further, for shared libraries, any function whose symbol is exported
will get a PLT entry. Hence, the function pointers for these functions
will be the PLT entry's address and not the real function address.
Hence, it is always safe to fold functions whose symbols are exported
as their pointers *can never be equal*. I do not need any relocation
based disambiguation here.

Here is an example :

t.cc

int foo()
{
 return 1;
}

int bar()
{
 return 1;
}

$ g++ -fPIC -shared t.cc -o libt.so -Wl,--icf
$ nm t.so

000000000000025c T _Z3barv
000000000000025c T _Z3foov

Notice that foo and bar have been folded into one function.

Now,

main.cc

extern int foo();
extern int bar();

int main()
{
 if (foo == bar)
   printf("equal\n");
 else
   printf("not equal\n");
}

$ g++ main.cc -L./ -lt
$ a.out
not equal

However, for shared libraries; protected, hidden, internal symbols and
static functions cause a problem. They dont have a PLT entry and their
relocations for call and pointers are the same. So, safe ICF will
assume that these can never be folded. Fine so far.

Case (iii) Position-independent executables.

This is a monster. AFAIU, PIE is nothing but PIC code that is
executable. However, the function pointer for a function whose symbol
is exported is the address of the function, not the PLT entry. There
is no PLT entry for exported functions because they cannot be
over-ridden.

Further, It can be created in two ways as far as I know.

Sub-case 1) The individual objects can be compiled with -fPIC and then
linked into an executable.

In this case, the relocations for pointer taken versus a function call
are *still* different. The function pointer has a GOTPCREL relocation
whereas a function call has a PC relative relocation. Hence, we can
differentiate and do a safe folding, again accounting for those
special symbols (hidden, protected, internal and static functions.)


Sub-case 2) The individual objects can be compiled with -fPIE and then
linked into an executable.

In this case, the relocations for function pointer taken versus a call
are the same. From what I understood, the difference between -fPIC
objects and -fPIE objects is that objects compiled with -fPIE can
never go into a shared object hence the function pointer relocations
never have to be GOT relative.

Hence, for PIE executables, safe ICF defaults to folding only ctors and dtors.

Case (iv) Building non-PIE binaries using PIE objects.

Safe ICF should not be used in this case. I have a plan to record the
build type of each object in a separate section that can be used by
the linker to decide what kind of safety is possible. Till then,
building non-PIE binaries with PIC/PIE objects is wrong.


Here is the patch to implement really safe ICF for X86-64. Some
experiments I have conducted show that safe ICF for X86-64 is 98 % as
effective as full ICF in reducing code size with the safety guarantee
against function pointer checks.

Please let me know what you think ?


2010-01-21  Sriraman Tallam  <tmsriram@google.com>

	* arm.cc (Scan::local_for_icf): New function.
	(Scan::global_for_icf): New function.
	* sparc.cc (Scan::local_for_icf): New function.
	(Scan::global_for_icf): New function.
	* powerpc.cc (Scan::local_for_icf): New function.
	(Scan::global_for_icf): New function.
	* i386.cc (Scan::local_for_icf): New function.
	(Scan::global_for_icf): New function.
	* x86_64.cc (Scan::local_for_icf): New function.
	(Scan::global_for_icf): New function.
	(Scan::is_non_pic_reloc_type_func_ptr): New function.
	* gc.h (gc_process_relocs): Scan relocation types to determine if
        function pointers were taken for targets that support it.
	* icf.cc (Icf::find_identical_sections): Include functions for
	folding in safe ICF whose pointer is not taken.
	* icf.h (Secn_fptr_taken_set): New typedef.
	(fptr_section_id_): New member.
	(is_section_fptr_taken): New function.
	(set_section_fptr_taken): New function.
	(check_section_for_fptr_taken): New function.
	* options.h: Fix comment for safe ICF option.
	* target.h (is_fptr_taken_checked): New function.
	* testsuite/Makefile.am: Add icf_safe_so_test test case.
	Modify icf_safe_test for X86-64.
	* testsuite/Makefile.in: Regenerate.
	* testsuite/icf_safe_so_test.cc: New file.
	* testsuite/icf_safe_so_test.sh: New file.
	* testsuite/icf_safe_test.cc (kept_func_3): New function.
	(main): Change to take pointer to function kept_func_3.
	* testsuite/icf_safe_test.sh (arch_specific_safe_fold): Check if safe
	folding is done correctly for X86-64.

Thanks,
-Sriraman.

Attachment: gold_safe_icf_2010_01_21_patch.txt
Description: Text document