Bug 192 - String literals don't obey -fdata-sections
Summary: String literals don't obey -fdata-sections
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: 2.95.2
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on:
Blocks:
 
Reported: 2000-05-02 19:46 UTC by greyham
Modified: 2015-05-08 02:05 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2006-02-13 03:56:16


Attachments
ned (11.21 KB, text/plain)
2007-04-02 21:27 UTC, nekto
Details
put string literals into unique sections when -fmerge-constants -fdata-sections (646 bytes, patch)
2015-05-06 16:06 UTC, Matt Whitlock
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description greyham 2000-05-02 19:46:01 UTC
I'm pushing the envelope in order to use gcc's flags -ffunction-sections and
-fdata-sections with ld's --gc-sections for dead function elimination in the
Linux kernel.

I've encountered a problem with constant strings from unused functions not
being optimised away along with the function. In other words, the unused
functions get optimised away, but the strings they used do not. I've verified
this is a problem at least for PowerPC and x86 targets, and I suspect all
others too.

The problem occurs because even with -fdata-sections specified, strings go in
section ".rodata". To be optimised away by ld with --gc-sections, they need to
go in a section like ".rodata.something". Noting that string literals don't
have globally unique names, the "something" may need to be the function name
it appeared in, or derived from the string contents perhaps via a hash.
Either option would allow the section containing unused strings to be
optimised away correctly by the linker.

Similarly, with -fwritable-strings and -fdata-sections, the string data ends
up in ".data", not ".data.something" where I would have expected it.

Here's a trivial example showing the problem:
    char *function()
    {
        return "unused string";
    }

Running this through the latest gcc snapshot on:
    http://www.codesourcery.com/gcc-compile.html
with options:
    -ffunction-sections -fdata-sections -fwritable-strings
yeilds:

        .file   "@2566.1"
        .version        "01.01"
gcc2_compiled.:
.data                                   #### Oh-oh! Plain old .data
.LC0:
        .string "unused string"
        .section        .text.function,"ax",@progbits
        .align 4
.globl function
        .type    function,@function
function:
        pushl   %ebp
        movl    %esp, %ebp
        movl    $.LC0, %eax
        popl    %ebp
        ret
.Lfe1:
        .size    function,.Lfe1-function
        .ident  "GCC: (GNU) 2.96 20000418 (experimental)

Release:
2.95.2

Environment:
Red Hat Linux 6.2
Comment 1 Richard Henderson 2001-01-16 04:41:34 UTC
State-Changed-From-To: open->suspended
State-Changed-Why: Recent changes to the ELF spec allow this to be done in the
    linker.  See SHF_STRINGS.  Once this has been implemented in
    GNU binutils, we can think about doing something with it in
    the compiler.
Comment 2 Richard Henderson 2001-01-16 12:41:34 UTC
From: rth@gcc.gnu.org
To: gcc-gnats@gcc.gnu.org, greyham@research.canon.com.au, nobody@gcc.gnu.org
Cc:  
Subject: Re: optimization/192
Date: 16 Jan 2001 12:41:34 -0000

 Synopsis: String literals don't obey -fdata-sections
 
 State-Changed-From-To: open->suspended
 State-Changed-By: rth
 State-Changed-When: Tue Jan 16 04:41:34 2001
 State-Changed-Why:
     Recent changes to the ELF spec allow this to be done in the
     linker.  See SHF_STRINGS.  Once this has been implemented in
     GNU binutils, we can think about doing something with it in
     the compiler.
 
 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view&pr=192&database=gcc
Comment 3 Andrew Pinski 2003-06-09 19:38:11 UTC
Still happens on the mainline (20030609).
Comment 4 Andrew Pinski 2004-05-22 21:08:59 UTC
Will not fix as -fwritable-strings is no longer supported in 3.5.0 and above.
Comment 5 Joseph S. Myers 2004-05-22 21:53:58 UTC
Subject: Re:  String literals don't obey -fdata-sections

On Sat, 22 May 2004, pinskia at gcc dot gnu dot org wrote:

> Will not fix as -fwritable-strings is no longer supported in 3.5.0 and above.

The basic feature request has nothing to do with -fwritable-strings, that
was just one example.  As far as I know this sort of feature would still
be just as useful as when this feature request was submitted.  (Similarly
- mentioned in the projects list rather than being the subject of a bug
report - an attribute to specify a section for string constants would also
be of use.)

Comment 6 Giovanni Bajo 2004-05-23 02:18:15 UTC
following JSM
Comment 7 Alan Modra 2004-11-30 06:36:28 UTC
This is true of other constants too.  For example, on powerpc-linux, compiling
the testcase in pr9571:
gcc -O2 -m32 -fdata-sections -fno-merge-constants -S /src/tmp/pr9571.c
gives:
        .file   "pr9571.c"
        .globl d
        .section        .sdata.d,"a",@progbits
        .align 3
        .type   d, @object
        .size   d, 8
d:
        .long   1074339512
        .long   1374389535
        .section        .rodata
        .align 3
.LC0:
        .long   1074339512
        .long   1374389535
        .section        ".text"
        .align 2
        .p2align 4,,15
        .globl f
        .type   f, @function
f:
        lis 9,.LC0@ha
        lfd 1,.LC0@l(9)
        blr
        .size   f,.-f
        .ident  "GCC: (GNU) 4.0.0 20041129 (experimental)"
        .section        .note.GNU-stack,"",@progbits

The duplication of the constant isn't ideal either.
Comment 8 nekto 2007-04-02 21:27:50 UTC
Created attachment 13319 [details]
ned
Comment 9 Rahul 2015-05-06 07:09:01 UTC
I am also experiencing the same issue. Is there any solution for it?
Comment 10 Matt Whitlock 2015-05-06 10:59:46 UTC
(In reply to Rahul from comment #9)
> I am also experiencing the same issue. Is there any solution for it?

You can wrap a preprocessor macro around string literals that you want to subject to the linker's garbage collection:

  #define GCSTR(str) ({ static const char __str[] = str; __str; })

  void hello() {
      puts(GCSTR("111")); // NOT in .rodata
      puts("222");        //     in .rodata
  }

  int main() {
      puts(GCSTR("333")); //     in .rodata
      puts("444");        //     in .rodata
      return 0;
  }

$ gcc -ffunction-sections -fdata-sections -Wl,--gc-sections -o gcstr gcstr.c

$ objdump -s -j .rodata gcstr

  gcstr:     file format elf64-x86-64

  Contents of section .rodata:
   4005fd 32323200 34343400 33333300           222.444.333.    

The downside of this strategy, however, is that these strings then become ineligible for merging, so if you have multiple *reachable* occurrences of the same GCSTR in your code, then you'll have multiple copies of the string data in the .rodata section of your linked binary.

These redundant copies would not be present if the compiler were correctly outputting literal-initialized constant character arrays to sections with the "merge" and "strings" flags set (which it should do only if -fmerge-all-constants is set). You can simulate how this could/should work by editing the compiler's assembly output so that it sets the section flags appropriately.

Given this program, gcstr.c:

  #define GCSTR(str) ({ static const char __str[] = str; __str; })

  int main() {
      puts(GCSTR("111"));
      puts(GCSTR("111"));
      puts("111");
      return 0;
  }

Compile (but do not assemble) the program:

$ gcc -S -ffunction-sections -fdata-sections -fmerge-all-constants -o gcstr.s gcstr.c

Edit the assembly code so that all .rodata.__str.* sections are declared with the "merge" and "strings" flags and an entity size of 1:

$ sed -e 's/\(\.section\t\.rodata\.__str\..*\),"a",\(@progbits\)$/\1,"aMS",\2,1/' -i gcstr.s

Now assemble and link the program:

$ gcc -Wl,--gc-sections -o gcstr gcstr.s

Dumping the .rodata section from the resulting executable reveals that the linker did correctly perform string merging.

$ objdump -s -j .rodata gcstr

  gcstr:     file format elf64-x86-64

  Contents of section .rodata:
   40060d 31313100                             111.            

Compare the above objdump output to that which results when skipping the sed step:

   40060d 31313100 31313100 31313100           111.111.111.    

The needed correction is that the compiler should, when -fmerge-all-constants is set, emit literal-initialized constant character array data to a section with flags "aMS" and entsize==sizeof(T), where T is the type of characters in the array.

A further correction (and really the main request in this bug report) would be for the compiler to emit string literals to discrete sections when -fdata-sections is set.
Comment 11 Matt Whitlock 2015-05-06 16:06:57 UTC
Created attachment 35479 [details]
put string literals into unique sections when -fmerge-constants -fdata-sections

This patch puts each string literal into a (probably) unique section when compiling with -fmerge-constants -fdata-sections. The section name is constructed from the character width and string alignment (as before) plus a 32-bit hash of the string contents.

Consider the following program:

  void used() {
      puts("keep me");
      puts("common");
      puts("string");
      puts("tail");
  }
  
  void not_used() {
      puts("toss me");
      puts("common");
      puts("ring");
      puts("entail");
  }
  
  int main() {
      used();
      return 0;
  }

$ gcc -ffunction-sections -fdata-sections -fmerge-constants \
      -Wl,--gc-sections -o test test.c

Compiling with an unpatched GCC produces a binary whose .rodata contains:

   40061d 6b656570 206d6500 636f6d6d 6f6e0073  keep me.common.s
   40062d 7472696e 6700746f 7373206d 6500656e  tring.toss me.en
   40063d 7461696c 00                          tail.           

Compiling with a patched GCC produces a binary whose .rodata contains:

   40061d 6b656570 206d6500 636f6d6d 6f6e0073  keep me.common.s
   40062d 7472696e 67007461 696c00             tring.tail.
Comment 12 H.J. Lu 2015-05-06 16:41:27 UTC
(In reply to Matt Whitlock from comment #11)
> Created attachment 35479 [details]
> put string literals into unique sections when -fmerge-constants
> -fdata-sections
> 
> This patch puts each string literal into a (probably) unique section when
> compiling with -fmerge-constants -fdata-sections. The section name is
> constructed from the character width and string alignment (as before) plus a
> 32-bit hash of the string contents.

Would it better to use MD5 checksum on string contents?
Comment 13 Matt Whitlock 2015-05-06 23:26:11 UTC
(In reply to H.J. Lu from comment #12)
> Would it better to use MD5 checksum on string contents?

MD5 would be slower for not much gain in uniqueness (assuming its output is truncated to 32 bits). This application doesn't require a cryptographically strong hash function, as the consequence of a collision is merely that a string gets included in the binary when maybe it didn't need to be.

Actually, I would favor replacing the very old (1996) Lookup2 hash function (implemented in libiberty/hashtab.c) with a more modern hash function, such as MurmurHash3, CityHash, or even Lookup3, all of which are faster than Lookup2.

I would hesitate to use more than 32 bits, as the section names would start getting rather long.
Comment 14 Jakub Jelinek 2015-05-07 07:19:17 UTC
This doesn't really look like a good idea to me.  Instead, perhaps ld's --gc-sections or new special option should just remove unused string literals from mergeable sections.
With your patch, I bet you lose e.g. all tail merging.  Consider:
const char *used1 () { return "foo bar baz blah blah"; }
in one TU and
const char *used2 () { return "bar baz blah blah"; }
in another.  The linker necessarily knows which strings (or other data) in mergeable sections are used and which are unused.
Comment 15 Matt Whitlock 2015-05-07 10:30:04 UTC
(In reply to Jakub Jelinek from comment #14)
> This doesn't really look like a good idea to me.  Instead, perhaps ld's
> --gc-sections or new special option should just remove unused string
> literals from mergeable sections.

I believe (I've read, but I haven't verified) that Gold already does this.

> With your patch, I bet you lose e.g. all tail merging.

Tail merging still works fine.

> Consider:
> const char *used1 () { return "foo bar baz blah blah"; }
> in one TU and
> const char *used2 () { return "bar baz blah blah"; }
> in another.

Okay, I'll use your example.

$ echo 'const char *used1 () { return "foo bar baz blah blah"; }' > tu1.c
$ echo 'const char *used2 () { return "bar baz blah blah"; }' > tu2.c
$ cat > main.c <<EOF
extern const char * used1(), * used2();
int main() { puts(used1()); puts(used2()); return 0; }
EOF

$ gcc -c -fdata-sections -fmerge-constants -o tu1.o tu1.c
$ gcc -c -fdata-sections -fmerge-constants -o tu2.o tu2.c
$ gcc -c -fdata-sections -fmerge-constants -o main.o main.c

$ objdump -s tu1.o tu2.o | fgrep -A2 .rodata
Contents of section .rodata.str1.1.b4d3fd7d:
 0000 666f6f20 62617220 62617a20 626c6168  foo bar baz blah
 0010 20626c61 6800                         blah.          
--
Contents of section .rodata.str1.1.a07ea0c2:
 0000 62617220 62617a20 626c6168 20626c61  bar baz blah bla
 0010 6800                                 h.              

$ gcc -Wl,--gc-sections -o proof main.o tu1.o tu2.o

$ ./proof
foo bar baz blah blah
bar baz blah blah

$ objdump -s proof | fgrep -A2 .rodata
Contents of section .rodata:
 40061d 666f6f20 62617220 62617a20 626c6168  foo bar baz blah
 40062d 20626c61 6800                         blah.          

As you can see, tail merging across translation units works fine.
Comment 16 Segher Boessenkool 2015-05-07 15:51:32 UTC
Author: segher
Date: Thu May  7 15:51:01 2015
New Revision: 222880

URL: https://gcc.gnu.org/viewcvs?rev=222880&root=gcc&view=rev
Log:
	PR middle-end/192
	PR middle-end/54303
	* varasm.c (function_mergeable_rodata_prefix): New function.
	(mergeable_string_section): Use it.
	(mergeable_constant_section): Use it.

gcc/testsuite/
	* gcc.dg/fdata-sections-2.c: New file.

Added:
    trunk/gcc/testsuite/gcc.dg/fdata-sections-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/varasm.c
Comment 17 Matt Whitlock 2015-05-08 02:05:19 UTC
(In reply to Segher Boessenkool from comment #16)

Thanks for the fix, Segher. Your patch seems more "right" than mine, although I will point out that it doesn't precisely address this bug report, as it places string literal data into unique sections only if -ffunction-sections is set, whereas -fdata-sections has no impact. I can see arguments both ways, and personally this distinction is irrelevant to me, as I always use for -ffunction-sections and -fdata-sections, but the new behavior does seem somewhat counter-intuitive to me.

Anyway, I tested your new patch (backported to GCC 4.9.2) with the use cases in Comment 11 and Comment 15, and both produced the desired results (after I added -ffunction-sections to the command lines in Comment 15). So I'm appeased.