Avoid shuffle self-assignment in EXPENSIVE_CHECKS builds

[arichardson]

Summary

Some versions of libstdc++ perform self-assignment in std::shuffle. This
breaks the EXPENSIVE_CHECKS builds of TableGen due to an incorrect assertion
in libstdc++.

See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828.

Fixes https://llvm.org/PR37652

[lebedev.ri]

It seems like https://bugs.llvm.org/show_bug.cgi?id=37652 was fixed upstream.
Do we still want to workaround it?

llvm/include/llvm/ADT/STLExtras.h

1339

This should have a comment explaining why this is needed

[arichardson]

In D98167#2610843, @lebedev.ri wrote:

It seems like https://bugs.llvm.org/show_bug.cgi?id=37652 was fixed upstream.
Do we still want to workaround it?

It appears that https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828 was fixed Aug2020, so most Linux distributions still ship a libstdc++ with the assert unless they backported the fix. I think it probably makes sense to work around it.

llvm/include/llvm/ADT/STLExtras.h

1339

Will add a comment if we are happy to proceed with this patch.
How about the following?

[nikic]

This looks reasonable to me. I can also confirm that EXPENSIVE_CHECKS with libstdc++-10 successfully builds after this patch. Presumably the not yet released libstdc++-11 would work without it.

[RKSimon]

llvm/include/llvm/ADT/STLExtras.h

1339

Yes that sounds ok to me

[lebedev.ri]

SGTM

[arichardson]

• Add comment explaining != 0 check

[RKSimon]

LGTM - cheers

llvm/include/llvm/ADT/STLExtras.h

 //===----------------------------------------------------------------------===//
 
 // 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);
+  typedef
+      typename std::iterator_traits<Iterator>::difference_type difference_type;
+  for (auto size = last - first; size > 1; ++first, (void)--size) {
+    difference_type offset = g() % size;
+    // Avoid self-assignment due to incorrect assertions in libstdc++
+    // containers (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828).
+    if (offset != difference_type(0))
+      std::iter_swap(first, first + offset);
+  }
 }
 
 /// Find the length of an array.
 template <class T, std::size_t N>
 constexpr inline size_t array_lengthof(T (&)[N]) {
   return N;
 }
 

 inline unsigned presortShuffleEntropy() {
   static unsigned Result(std::random_device{}());
   return Result;
 }
 
 template <class IteratorTy>
 inline void presortShuffle(IteratorTy Start, IteratorTy End) {
   std::mt19937 Generator(presortShuffleEntropy());
-  std::shuffle(Start, End, Generator);
+  llvm::shuffle(Start, End, Generator);
 }
 
 } // end namespace detail
 #endif
 
 /// array_pod_sort - This sorts an array with the specified start and end
 /// extent.  This is just like std::sort, except that it calls qsort instead of
 /// using an inlined template.  qsort is slightly slower than std::sort, but

llvm/tools/bugpoint/FindBugs.cpp

BugDriver::runManyPasses(const std::vector<std::string> &AllPasses) {
   }
 
   std::mt19937 randomness(std::random_device{}());
   unsigned num = 1;
   while (1) {
     //
     // Step 1: Randomize the order of the optimizer passes.
     //
-    std::shuffle(PassesToRun.begin(), PassesToRun.end(), randomness);
+    llvm::shuffle(PassesToRun.begin(), PassesToRun.end(), randomness);
 
     //
     // Step 2: Run optimizer passes on the program and check for success.
     //
     outs() << "Running selected passes on program to test for crash: ";
     for (int i = 0, e = PassesToRun.size(); i != e; i++) {
       outs() << "-" << PassesToRun[i] << " ";
     }

llvm/tools/bugpoint/ListReducer.h

while (MidTop > 1) { // Binary split reduction loop
         return true;
       }
 
       // If the loop doesn't make satisfying progress, try shuffling.
       // The purpose of shuffling is to avoid the heavy tails of the
       // distribution (improving the speed of convergence).
       if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) {
         std::vector<ElTy> ShuffledList(TheList);
-        std::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
+        llvm::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
         errs() << "\n\n*** Testing shuffled set...\n\n";
         // Check that random shuffle doesn't lose the bug
         Expected<TestResult> Result = doTest(ShuffledList, empty);
         // TODO: Previously, this error was ignored and we treated it as if
         // shuffling hid the bug. This should really either be consumeError if
         // that behaviour was sensible, or we should propagate the error.
         assert(!Result.takeError() && "Shuffling caused internal error?");
 

llvm/tools/llvm-exegesis/lib/SerialSnippetGenerator.cpp

 static std::vector<const Instruction *>
 computeAliasingInstructions(const LLVMState &State, const Instruction *Instr,
                             size_t MaxAliasingInstructions,
                             const BitVector &ForbiddenRegisters) {
   // Randomly iterate the set of instructions.
   std::vector<unsigned> Opcodes;
   Opcodes.resize(State.getInstrInfo().getNumOpcodes());
   std::iota(Opcodes.begin(), Opcodes.end(), 0U);
-  std::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator());
+  llvm::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator());
 
   std::vector<const Instruction *> AliasingInstructions;
   for (const unsigned OtherOpcode : Opcodes) {
     if (OtherOpcode == Instr->Description.getOpcode())
       continue;
     const Instruction &OtherInstr = State.getIC().getInstr(OtherOpcode);
     const MCInstrDesc &OtherInstrDesc = OtherInstr.Description;
     // Ignore instructions that we cannot run.

llvm/tools/llvm-stress/llvm-stress.cpp

 
 static void IntroduceControlFlow(Function *F, Random &R) {
   std::vector<Instruction*> BoolInst;
   for (auto &Instr : F->front()) {
     if (Instr.getType() == IntegerType::getInt1Ty(F->getContext()))
       BoolInst.push_back(&Instr);
   }
 
-  std::shuffle(BoolInst.begin(), BoolInst.end(), R);
+  llvm::shuffle(BoolInst.begin(), BoolInst.end(), R);
 
   for (auto *Instr : BoolInst) {
     BasicBlock *Curr = Instr->getParent();
     BasicBlock::iterator Loc = Instr->getIterator();
     BasicBlock *Next = Curr->splitBasicBlock(Loc, "CF");
     Instr->moveBefore(Curr->getTerminator());
     if (Curr != &F->getEntryBlock()) {
       BranchInst::Create(Curr, Next, Instr, Curr->getTerminator());