Add a llvm::shuffle and use it in lld

[respindola]

Summary

With this --shuffle-sections=seed produces the same result in every
host.

[MaskRay]

lld/test/ELF/shuffle-sections.s

9

Also delete mention of std::shuffle in shuffle-sections-init-fini.s

I think keeping ORDERED-SAME and SHUFFLED-NOT in shuffle-sections-init-fini.s as is is fine, though I will not object if you also change them to test a particular order.

llvm/include/llvm/ADT/STLExtras.h

1014

Return if first == last

1015

< -> !=

1018

d can be inlined.

[MaskRay]

llvm/include/llvm/ADT/STLExtras.h

1010

Based on the libc++ implementation. llvm -> LLVM

[respindola]

Update all tests
Simplify the implementation a bit. This is not exactly what was requested, but IMHO it is simpler.

[MaskRay]

llvm/include/llvm/ADT/STLExtras.h

1017

i can be inlined, too.

[grimar]

LGTM with minor nits.

llvm/include/llvm/ADT/STLExtras.h

1013

This file seems has inconsistent variables naming style, but seems
everything that goes below "Extra additions for arrays" uses
an upper case for variable names.

1017

Also we often trying to avoid auto when the result in not obvious.
(here and above).

[MaskRay]

Protect against comma operator overload.

Simplify

lld/ELF/Writer.cpp

static void maybeShuffle(DenseMap<const InputSectionBase *, int> &order) {
   std::vector<int> priorities(inputSections.size() - order.size());
   // Existing priorities are < 0, so use priorities >= 0 for the missing
   // sections.
   int curPrio = 0;
   for (int &prio : priorities)
     prio = curPrio++;
   uint32_t seed = *config->shuffleSectionSeed;
   std::mt19937 g(seed ? seed : std::random_device()());
-  std::shuffle(priorities.begin(), priorities.end(), g);
+  llvm::shuffle(priorities.begin(), priorities.end(), g);
   int prioIndex = 0;
   for (InputSectionBase *sec : inputSections) {
     if (order.try_emplace(sec, priorities[prioIndex]).second)
       ++prioIndex;
   }
 }
 
 // Builds section order for handling --symbol-ordering-file.

lld/test/ELF/shuffle-sections-init-fini.s

 
 # CHECK:      Hex dump of section '.fini'
 # CHECK-NEXT: 00010203 04050607 08090a0b
 
 ## SHT_INIT_ARRAY/SHT_FINI_ARRAY with explicit priorities are still ordered.
 # CHECK:      Hex dump of section '.init_array'
 # CHECK-NEXT: 0x{{[0-9a-f]+}} ff
 # ORDERED-SAME: 000102 03040506 0708090a 0b
-# SHUFFLED-NOT: 000102 03040506 0708090a 0b
+# SHUFFLED-SAME: 04000b 06010a08 09070203 05
 
 # CHECK:      Hex dump of section '.fini_array'
 # CHECK-NEXT: 0x{{[0-9a-f]+}} ff
-# ORDERED-SAME: 000102 03040506 0708090a 0b
-# SHUFFLED-NOT: 000102 03040506 0708090a 0b
+# ORDERED-SAME:  000102 03040506 0708090a 0b
+# SHUFFLED-SAME: 090401 070b0003 080a0605 02
 
 ## With a SECTIONS command, SHT_INIT_ARRAY prirotities are ignored.
 ## All .init_array* are shuffled together.
 # RUN: echo 'SECTIONS {}' > %t.script
 # RUN: ld.lld -T %t.script %t.o -o %t2
 # RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t2 | \
 # RUN:   FileCheck --check-prefixes=CHECK2,ORDERED2 %s
 # RUN: ld.lld -T %t.script %t.o --shuffle-sections=1 -o %t3
 # RUN: llvm-readelf -x .init -x .fini -x .init_array -x .fini_array %t3 | \
 # RUN:   FileCheck --check-prefixes=CHECK2,SHUFFLED2 %s
 
 # CHECK2:       Hex dump of section '.init_array'
 # ORDERED2-NEXT:  0x{{[0-9a-f]+}} 00010203 04050607 08090a0b ff
-# SHUFFLED2-NOT:  0x{{[0-9a-f]+}} 00010203 04050607 08090a0b ff
+# SHUFFLED2-NEXT: 0x{{[0-9a-f]+}} 04000b06 010a0809 07ff0203 05
 
-## std::shuffle have different implementations.
-## When the number of input sections are large, it is almost guaranteed
-## to have an unordered result with --shuffle-sections=.
 .irp i,0,1,2,3,4,5,6,7,8,9,10,11
   .section .init,"ax",@progbits,unique,\i
   .byte \i
   .section .fini,"ax",@progbits,unique,\i
   .byte \i
   .section .init_array,"aw",@init_array,unique,\i
   .byte \i
   .section .fini_array,"aw",@fini_array,unique,\i
   .byte \i
 .endr
 
 .section .init_array.1,"aw",@init_array
 .byte 255
 .section .fini_array.1,"aw",@fini_array
 .byte 255

lld/test/ELF/shuffle-sections.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
 
 # RUN: ld.lld %t.o -o %t.out
 # RUN: llvm-readelf -x .text %t.out | FileCheck %s
 # CHECK: Hex dump of section '.text':
 # CHECK-NEXT: 01020304
 
+## --shuffle-sections= shuffles input sections.
+# RUN: ld.lld --shuffle-sections=1 %t.o -o %t1.out
+# RUN: llvm-readelf -x .text %t1.out | FileCheck %s --check-prefix=SHUFFLE1
+# SHUFFLE1: Hex dump of section '.text':
+# SHUFFLE1-NEXT: 0204cccc 0103
+
 ## Test that --shuffle-sections= can be used with --symbol-ordering-file
 # RUN: echo "foo" > %t_order.txt
 # RUN: echo "_start " >> %t_order.txt
 
 # RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections=2 %t.o -o %t2.out
 # RUN: llvm-readelf -x .text %t2.out | FileCheck %s --check-prefix=SHUFFLE2
 # SHUFFLE2: Hex dump of section '.text':
-# SHUFFLE2-NEXT: 02cccccc 01{{....}}
+# SHUFFLE2-NEXT: 02cccccc 010304
 
 # RUN: ld.lld --symbol-ordering-file %t_order.txt --shuffle-sections=3 %t.o -o %t3.out
 # RUN: llvm-readelf -x .text %t3.out | FileCheck %s --check-prefix=SHUFFLE3
 # SHUFFLE3: Hex dump of section '.text':
-# SHUFFLE3-NEXT: 02cccccc 01{{....}}
+# SHUFFLE3-NEXT: 02cccccc 010403
 
 ## .text has an alignment of 4.
 .global _start
 _start:
   .byte 1
 
 .section .text.foo,"ax"
 .global foo

llvm/include/llvm/ADT/STLExtras.h

struct are_base_of<T, U, Ts...> {
   static const bool value =
       std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
 };
 
 //===----------------------------------------------------------------------===//
 //     Extra additions for arrays
 //===----------------------------------------------------------------------===//
 
+// We have a copy here so that LLVM behaves the same when using different
+// standard libraries.
+template <class Iterator, class RNG>
+void shuffle(Iterator first, Iterator last, RNG &&g) {
+  // It would be better to use a std::uniform_int_distribution,
+  // but that would be stdlib dependent.
+  for (auto size = last - first; size > 1; ++first, (void)--size)
+    std::iter_swap(first, first + g() % size);
+}
+
 /// Find the length of an array.
 template <class T, std::size_t N>
 constexpr inline size_t array_lengthof(T (&)[N]) {
   return N;
 }
 
 /// Adapt std::less<T> for array_pod_sort.
 template<typename T>