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.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
 //===----------------------------------------------------------------------===//
 
+// Based on the one in libc++. We have a copy in 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) {
+  --last;
+  for (; first < last; ++first) {
+    // It would be better to use a std::uniform_int_distribution,
+    // but that would be stdlib dependent.
+    auto d = last - first + 1;
+    auto i = g() % d;
+    std::swap(*first, *(first + i));
+  }
+}
+
 /// 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>