Re: [gold] Merging string literals with bigger alignment

[Alexander Ivchenko <aivchenk@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1678 bytes --]

Hi,

Please, take a look at the attached patch that enables merging
of string literals with alignment bigger than the char size (alignment
is preserved).

Make check-gold passes, testcase is included.

thanks,
Alexander

2013/2/12 Ian Lance Taylor <iant@google.com>:
> On Tue, Feb 12, 2013 at 7:30 AM, Alexander Ivchenko <aivchenk@gmail.com> wrote:
>> The testcase in the patch from my first letter has those .c files. But
>> it's very simple anyway:
>>>cat merge_string_literals_1.c
>>
>> const char* bar1() {
>>   return "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
>> }
>> const char* bar1_short() {
>>     return "SSSSSS";
>> }
>>
>>>gcc -c merge_string_literals_1.c -O2
>>>readelf -S merge_string_literals_1.o | grep rodata
>>   [ 5] .rodata.str1.8    PROGBITS         0000000000000000  00000058
>>   [ 6] .rodata.str1.1    PROGBITS         0000000000000000  0000007d
>>
>>>objdump -s -j.rodata.str1.8 merge_string_literals_1.o
>>
>> merge_string_literals_1.o:     file format elf64-x86-64
>>
>> Contents of section .rodata.str1.8:
>>  0000 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAA
>>  0010 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAA
>>  0020 41414141 00                          AAAA.
>>
>> I mentioned .rodata.str1.4 before - that could happen if we compile
>> for 32 bits..
>
>
> Thanks.  I see the code in GCC now.  It's in ix86_constant_alignment
> in gcc/config/i386/i386.c.  For a string constant of 31 bytes or more,
> GCC sets the alignment to the word size.  This means that GCC may use
> vector instructions to load the string constant.  So gold has to honor
> the alignment of each individual entry in the mergeable string
> section.
>
> Ian

[-- Attachment #2: merging_string_literals_02.patch --]
[-- Type: application/octet-stream, Size: 17833 bytes --]

diff --git a/gold/ChangeLog b/gold/ChangeLog
index 6913ace..e84e7dd 100644
--- a/gold/ChangeLog
+++ b/gold/ChangeLog
@@ -1,3 +1,30 @@
+2013-03-19  Alexander Ivchenko  <alexander.ivchenko@intel.com>
+
+	* output.cc (Output_section::add_merge_input_section): Allow
+	to merge sections if the alignment is more than character size.
+	* merge.h (Output_merge_string::Output_merge_string): Remove
+	assert.
+	* merge.cc (Output_merge_string<Char_type>::do_add_input_section): Use
+	add_with_length_and_alignment instead of add_with_length.
+	* stringpool.h (Stringpool_template<Stringpool_char>::new_key_offset):
+	Add new argument - alignment of the string.
+	(Stringpool_template<Stringpool_char>::add_with_length_and_alignment):
+	New method.
+	(Stringpool_template<Stringpool_char>::Hashkey): New class member -
+	alignment of the string. Constructors are updated accordingly.
+	* stringpool.cc (Stringpool_template<Stringpool_char>::new_key_offset):
+	Add new argument - alignment of the string.
+	(Stringpool_template<Stringpool_char>::set_string_offsets):
+	Updating offsets according to the given alignment.
+	* merge.h (Output_merge_string::Output_merge_string): Remove
+	assert.
+	* testsuite/Makefile.am (text_section_grouping): Test if string
+	literals are getting merged.
+	* testsuite/Makefile.in: Regenerate.
+	* testsuite/merge_string_literals_1.c: New file.
+	* testsuite/merge_string_literals_2.c: Ditto.
+	* testsuite/merge_string_literals.sh: Ditto.
+
 2013-03-13  Alan Modra  <amodra@gmail.com>
 
 	* powerpc.cc (is_branch_reloc): Forward declare.
diff --git a/gold/merge.cc b/gold/merge.cc
index dde43e9..47e8299 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -555,7 +555,9 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
       size_t len = string_length(p);
 
       Stringpool::Key key;
-      this->stringpool_.add_with_length(p, len, true, &key);
+      this->stringpool_.add_with_length_and_alignment(p, len,
+						      this->addralign(),
+						      true, &key);
 
       merged_strings.push_back(Merged_string(i, key));
 
diff --git a/gold/merge.h b/gold/merge.h
index 625d731..82fe961 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -464,7 +464,6 @@ class Output_merge_string : public Output_merge_base
     : Output_merge_base(sizeof(Char_type), addralign), stringpool_(),
       merged_strings_lists_(), input_count_(0), input_size_(0)
   {
-    gold_assert(addralign <= sizeof(Char_type));
     this->stringpool_.set_no_zero_null();
   }
 
diff --git a/gold/output.cc b/gold/output.cc
index 22c0bf0..75ce840 100644
--- a/gold/output.cc
+++ b/gold/output.cc
@@ -2635,11 +2635,6 @@ Output_section::add_merge_input_section(Relobj* object, unsigned int shndx,
 {
   bool is_string = (flags & elfcpp::SHF_STRINGS) != 0;
 
-  // We only merge strings if the alignment is not more than the
-  // character size.  This could be handled, but it's unusual.
-  if (is_string && addralign > entsize)
-    return false;
-
   // We cannot restore merged input section states.
   gold_assert(this->checkpoint_ == NULL);
 
diff --git a/gold/stringpool.cc b/gold/stringpool.cc
index 434b2d6..fb93ae6 100644
--- a/gold/stringpool.cc
+++ b/gold/stringpool.cc
@@ -214,15 +214,16 @@ Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, bool copy,
 
 template<typename Stringpool_char>
 void
-Stringpool_template<Stringpool_char>::new_key_offset(size_t length)
+Stringpool_template<Stringpool_char>::new_key_offset(size_t length, uint64_t addralign)
 {
   section_offset_type offset;
   if (this->zero_null_ && length == 0)
     offset = 0;
   else
     {
-      offset = this->offset_;
-      this->offset_ += (length + 1) * sizeof(Stringpool_char);
+      // We don't do alignment for zero-length strings.
+      offset = length == 0 ? offset_ : align_address(this->offset_, addralign);
+      this->offset_ = offset + (length + 1) * sizeof(Stringpool_char);
     }
   this->key_to_offset_.push_back(offset);
 }
@@ -234,6 +235,18 @@ Stringpool_template<Stringpool_char>::add_with_length(const Stringpool_char* s,
 						      bool copy,
 						      Key* pkey)
 {
+  return this->add_with_length_and_alignment(s, length, 1, copy, pkey);
+}
+
+template<typename Stringpool_char>
+const Stringpool_char*
+Stringpool_template<Stringpool_char>::
+add_with_length_and_alignment(const Stringpool_char* s,
+			      size_t length,
+			      uint64_t addralign,
+			      bool copy,
+			      Key* pkey)
+{
   typedef std::pair<typename String_set_type::iterator, bool> Insert_type;
 
   // We add 1 so that 0 is always invalid.
@@ -244,7 +257,7 @@ Stringpool_template<Stringpool_char>::add_with_length(const Stringpool_char* s,
       // When we don't need to copy the string, we can call insert
       // directly.
 
-      std::pair<Hashkey, Hashval> element(Hashkey(s, length), k);
+      std::pair<Hashkey, Hashval> element(Hashkey(s, length, addralign), k);
 
       Insert_type ins = this->string_set_.insert(element);
 
@@ -254,7 +267,7 @@ Stringpool_template<Stringpool_char>::add_with_length(const Stringpool_char* s,
 	{
 	  // We just added the string.  The key value has now been
 	  // used.
-	  this->new_key_offset(length);
+	  this->new_key_offset(length, addralign);
 	}
       else
 	{
@@ -271,7 +284,7 @@ Stringpool_template<Stringpool_char>::add_with_length(const Stringpool_char* s,
   // canonicalize it by copying it into the canonical list. The hash
   // code will only be computed once.
 
-  Hashkey hk(s, length);
+  Hashkey hk(s, length, addralign);
   typename String_set_type::const_iterator p = this->string_set_.find(hk);
   if (p != this->string_set_.end())
     {
@@ -280,7 +293,7 @@ Stringpool_template<Stringpool_char>::add_with_length(const Stringpool_char* s,
       return p->first.string;
     }
 
-  this->new_key_offset(length);
+  this->new_key_offset(length, addralign);
 
   hk.string = this->add_string(s, length);
   // The contents of the string stay the same, so we don't need to
@@ -421,8 +434,8 @@ Stringpool_template<Stringpool_char>::set_string_offsets()
 			      * charsize));
           else
             {
-              this_offset = offset;
-              offset += ((*curr)->first.length + 1) * charsize;
+              this_offset = align_address(offset, (*curr)->first.addralign);
+              offset = this_offset + ((*curr)->first.length + 1) * charsize;
             }
 	  this->key_to_offset_[(*curr)->second - 1] = this_offset;
 	  last_offset = this_offset;
diff --git a/gold/stringpool.h b/gold/stringpool.h
index c51b143..0aadcef 100644
--- a/gold/stringpool.h
+++ b/gold/stringpool.h
@@ -229,6 +229,12 @@ class Stringpool_template
   const Stringpool_char*
   add_with_length(const Stringpool_char* s, size_t len, bool copy, Key* pkey);
 
+  // Add string S of length LEN characters and alignment ADDRALIGN
+  // to the pool.  If COPY is true, S need not be null terminated.
+  const Stringpool_char*
+  add_with_length_and_alignment(const Stringpool_char* s, size_t len,
+				uint64_t addralign, bool copy, Key* pkey);
+
   // If the string S is present in the pool, return the canonical
   // string pointer.  Otherwise, return NULL.  If PKEY is not NULL,
   // set *PKEY to the key.
@@ -315,7 +321,7 @@ class Stringpool_template
 
   // Add a new key offset entry.
   void
-  new_key_offset(size_t);
+  new_key_offset(size_t length, uint64_t addralign);
 
   // Copy a string into the buffers, returning a canonical string.
   const Stringpool_char*
@@ -336,22 +342,30 @@ class Stringpool_template
     const Stringpool_char* string;
     // Length is in characters, not bytes.
     size_t length;
+    // Preserve the alignment of the string in the input section.
+    uint64_t addralign;
+
     size_t hash_code;
 
     // This goes in an STL container, so we need a default
     // constructor.
     Hashkey()
-      : string(NULL), length(0), hash_code(0)
+      : string(NULL), length(0), addralign(0), hash_code(0)
     { }
 
     // Note that these constructors are relatively expensive, because
     // they compute the hash code.
     explicit Hashkey(const Stringpool_char* s)
-      : string(s), length(string_length(s)), hash_code(string_hash(s, length))
+      : string(s), length(string_length(s)),
+	addralign(1), hash_code(string_hash(s, length))
     { }
 
     Hashkey(const Stringpool_char* s, size_t len)
-      : string(s), length(len), hash_code(string_hash(s, len))
+      : string(s), length(len), addralign(1), hash_code(string_hash(s, len))
+    { }
+
+    Hashkey(const Stringpool_char* s, size_t len, uint64_t align)
+      : string(s), length(len), addralign(align), hash_code(string_hash(s, len))
     { }
   };
 
diff --git a/gold/testsuite/Makefile.am b/gold/testsuite/Makefile.am
index 5b5c86b..b4e17a5 100644
--- a/gold/testsuite/Makefile.am
+++ b/gold/testsuite/Makefile.am
@@ -329,6 +329,18 @@ icf_sht_rel_addend_test: icf_sht_rel_addend_test_1.o icf_sht_rel_addend_test_2.o
 icf_sht_rel_addend_test.stdout: icf_sht_rel_addend_test
 	$(TEST_NM) icf_sht_rel_addend_test > icf_sht_rel_addend_test.stdout
 
+check_SCRIPTS += merge_string_literals.sh
+check_DATA += merge_string_literals.stdout
+MOSTLYCLEANFILES += merge_string_literals
+merge_string_literals_1.o: merge_string_literals_1.c
+	$(CXXCOMPILE) -O2 -c -fPIC -g -o $@ $<
+merge_string_literals_2.o: merge_string_literals_2.c
+	$(CXXCOMPILE) -O2 -c -fPIC -g -o $@ $<
+merge_string_literals: merge_string_literals_1.o merge_string_literals_2.o gcctestdir/ld
+	$(CXXLINK) -Bgcctestdir/ merge_string_literals_1.o merge_string_literals_2.o -O2 -shared -nostdlib
+merge_string_literals.stdout: merge_string_literals
+	$(TEST_OBJDUMP) -s -j.rodata merge_string_literals > merge_string_literals.stdout
+
 check_PROGRAMS += basic_test
 check_PROGRAMS += basic_pic_test
 basic_test.o: basic_test.cc
diff --git a/gold/testsuite/Makefile.in b/gold/testsuite/Makefile.in
index ec0acb9..c47dd34 100644
--- a/gold/testsuite/Makefile.in
+++ b/gold/testsuite/Makefile.in
@@ -85,6 +85,7 @@ check_PROGRAMS = $(am__EXEEXT_1) $(am__EXEEXT_2) $(am__EXEEXT_3) \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_preemptible_functions_test.sh \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_string_merge_test.sh \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_sht_rel_addend_test.sh \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	merge_string_literals.sh \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	two_file_shared.sh weak_plt.sh \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	debug_msg.sh undef_symbol.sh \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	ver_test_1.sh ver_test_2.sh \
@@ -119,6 +120,7 @@ check_PROGRAMS = $(am__EXEEXT_1) $(am__EXEEXT_2) $(am__EXEEXT_3) \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_preemptible_functions_test.stdout \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_string_merge_test.stdout \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_sht_rel_addend_test.stdout \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	merge_string_literals.stdout \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	two_file_shared.dbg \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	weak_plt_shared.so debug_msg.err
 @GCC_TRUE@@NATIVE_LINKER_TRUE@am__append_4 = incremental_test \
@@ -140,6 +142,7 @@ check_PROGRAMS = $(am__EXEEXT_1) $(am__EXEEXT_2) $(am__EXEEXT_3) \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_preemptible_functions_test \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_string_merge_test \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	icf_sht_rel_addend_test \
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	merge_string_literals \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	two_file_shared.dbg \
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	alt/weak_undef_lib.so
 @GCC_TRUE@@NATIVE_LINKER_TRUE@am__append_5 = icf_virtual_function_folding_test \
@@ -3736,6 +3739,8 @@ icf_string_merge_test.sh.log: icf_string_merge_test.sh
 	@p='icf_string_merge_test.sh'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
 icf_sht_rel_addend_test.sh.log: icf_sht_rel_addend_test.sh
 	@p='icf_sht_rel_addend_test.sh'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
+merge_string_literals.sh.log: merge_string_literals.sh
+	@p='merge_string_literals.sh'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
 two_file_shared.sh.log: two_file_shared.sh
 	@p='two_file_shared.sh'; $(am__check_pre) $(LOG_COMPILE) "$$tst" $(am__check_post)
 weak_plt.sh.log: weak_plt.sh
@@ -4419,6 +4424,14 @@ uninstall-am:
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	$(CXXLINK) -Bgcctestdir/ -Wl,--icf=all icf_sht_rel_addend_test_1.o icf_sht_rel_addend_test_2.o
 @GCC_TRUE@@NATIVE_LINKER_TRUE@icf_sht_rel_addend_test.stdout: icf_sht_rel_addend_test
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	$(TEST_NM) icf_sht_rel_addend_test > icf_sht_rel_addend_test.stdout
+@GCC_TRUE@@NATIVE_LINKER_TRUE@merge_string_literals_1.o: merge_string_literals_1.c
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(CXXCOMPILE) -O2 -c -fPIC -g -o $@ $<
+@GCC_TRUE@@NATIVE_LINKER_TRUE@merge_string_literals_2.o: merge_string_literals_2.c
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(CXXCOMPILE) -O2 -c -fPIC -g -o $@ $<
+@GCC_TRUE@@NATIVE_LINKER_TRUE@merge_string_literals: merge_string_literals_1.o merge_string_literals_2.o gcctestdir/ld
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(CXXLINK) -Bgcctestdir/ merge_string_literals_1.o merge_string_literals_2.o -O2 -shared -nostdlib
+@GCC_TRUE@@NATIVE_LINKER_TRUE@merge_string_literals.stdout: merge_string_literals
+@GCC_TRUE@@NATIVE_LINKER_TRUE@	$(TEST_OBJDUMP) -s -j.rodata merge_string_literals > merge_string_literals.stdout
 @GCC_TRUE@@NATIVE_LINKER_TRUE@basic_test.o: basic_test.cc
 @GCC_TRUE@@NATIVE_LINKER_TRUE@	$(CXXCOMPILE) -O0 -c -o $@ $<
 @GCC_TRUE@@NATIVE_LINKER_TRUE@basic_test: basic_test.o gcctestdir/ld
diff --git a/gold/testsuite/merge_string_literals.sh b/gold/testsuite/merge_string_literals.sh
new file mode 100755
index 0000000..486a895
--- /dev/null
+++ b/gold/testsuite/merge_string_literals.sh
@@ -0,0 +1,41 @@
+#!/bin/sh
+
+# merge_string_literals.sh -- test
+
+# Copyright 2013 Free Software Foundation, Inc.
+# Written by Alexander Ivchenko <alexander.ivchenko@intel.com>.
+
+# This file is part of gold.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+# MA 02110-1301, USA.
+
+# The goal of this program is to check whether string literals from different
+# object files are merged together
+
+set -e
+
+check()
+{
+    number_of_occurrence=`grep $2 ./$1 -o| wc -l`
+    if [ $number_of_occurrence != $3 ]
+    then
+	echo "String literals were not merged"
+	exit 1
+    fi
+}
+
+# If string literals were merged, then "abcd" appears two times
+check merge_string_literals.stdout "abcd" 2
diff --git a/gold/testsuite/merge_string_literals_1.c b/gold/testsuite/merge_string_literals_1.c
new file mode 100644
index 0000000..079382f
--- /dev/null
+++ b/gold/testsuite/merge_string_literals_1.c
@@ -0,0 +1,31 @@
+// merge_string_literals_1.c -- a test case for gold
+
+// Copyright 2012 Free Software Foundation, Inc.
+// Written by Alexander Ivchenko <alexander.ivchenko@intel.com>
+
+// This file is part of gold.
+
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation; either version 3 of the License, or
+// (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+// MA 02110-1301, USA.
+
+// The goal of this program is to check whether string literals from different
+// object files are merged together
+
+const char* bar1() {
+    return "abcdefghijklmnopqrstuvwxyz0123456789";
+}
+const char* bar1_short() {
+    return "abcdef";
+}
diff --git a/gold/testsuite/merge_string_literals_2.c b/gold/testsuite/merge_string_literals_2.c
new file mode 100644
index 0000000..d4876f8
--- /dev/null
+++ b/gold/testsuite/merge_string_literals_2.c
@@ -0,0 +1,31 @@
+// merge_string_literals_2.c -- a test case for gold
+
+// Copyright 2012 Free Software Foundation, Inc.
+// Written by Alexander Ivchenko <alexander.ivchenko@intel.com>
+
+// This file is part of gold.
+
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation; either version 3 of the License, or
+// (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+// MA 02110-1301, USA.
+
+// The goal of this program is to check whether string literals from different
+// object files are merged together
+
+const char* bar2() {
+    return "abcdefghijklmnopqrstuvwxyz0123456789";
+}
+const char* bar2_short() {
+    return "abcdef";
+}