Make the bloom filter a bit larger.

[ruiu]

Summary

I created https://reviews.llvm.org/D42202 to see how large the bloom
filter should be. With that patch, I tested various bloom filter sizes
with the following commands:

$ cmake -GNinja -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_LLD=true \
  -DLLVM_ENABLE_PROJECTS='clang;lld' -DBUILD_SHARED_LIBS=ON \
  -DCMAKE_SHARED_LINKER_FLAGS=-Wl,-bloom-filter-bits=<some integer> \
  ../llvm-project/llvm
$ rm -f $(find . -name \*.so.7.0.0svn)
$ ninja lld
$ LD_BIND_NOW=1 perf stat bin/ld.lld

Here is the result:

-bloom-filter-bits=8   0.220351609 seconds
-bloom-filter-bits=10  0.217146597 seconds
-bloom-filter-bits=12  0.206870826 seconds
-bloom-filter-bits=16  0.209456312 seconds
-bloom-filter-bits=32  0.195092075 seconds

Currently we allocate 8 bits for a symbol, but according to the above
result, that number is not optimal. Even though the numbers follow the
diminishing return rule, the point where a marginal improvement becomes
too small is not -bloom-filter-bits=8 but 12. So this patch sets it to 12.

[grimar]

I also observed that increasing of filter size gives boost.
And wiki says:
"A Bloom filter with 1 % error and an optimal value of k, in contrast, requires only about 9.6 bits per element, regardless of the size of the elements. This advantage comes partly from its compactness, inherited from arrays, and partly from its probabilistic nature. The 1 % false-positive rate can be reduced by a factor of ten by adding only about 4.8 bits per element."
So I think value = 12 is probably should be fine balance.

Patch increases size of output though and orthogonal to other possible optimizations (like attemps to tweak Shift2). Are we ok to increase output size atm ?

lld/ELF/SyntheticSections.cpp

 // safe bet is to specify -hash-style=both for backward compatibilty.
 GnuHashTableSection::GnuHashTableSection()
     : SyntheticSection(SHF_ALLOC, SHT_GNU_HASH, Config->Wordsize, ".gnu.hash") {
 }
 
 void GnuHashTableSection::finalizeContents() {
   getParent()->Link = InX::DynSymTab->getParent()->SectionIndex;
 
-  // Computes bloom filter size in word size. We want to allocate 8
+  // Computes bloom filter size in word size. We want to allocate 12
   // bits for each symbol. It must be a power of two.
-  if (Symbols.empty())
+  if (Symbols.empty()) {
     MaskWords = 1;
-  else
-    MaskWords = NextPowerOf2((Symbols.size() - 1) / Config->Wordsize);
+  } else {
+    uint64_t NumBits = Symbols.size() * 12;
+    MaskWords = NextPowerOf2(NumBits / (Config->Wordsize * 8));
+  }
 
   Size = 16;                            // Header
   Size += Config->Wordsize * MaskWords; // Bloom filter
   Size += NBuckets * 4;                 // Hash buckets
   Size += Symbols.size() * 4;           // Hash values
 }
 
 void GnuHashTableSection::writeTo(uint8_t *Buf) {