From 35bf23e965508a6ca00009ca45ba882d1ba7808c Mon Sep 17 00:00:00 2001 From: Alex Richardson Date: Tue, 9 Mar 2021 20:14:46 +0000 Subject: [PATCH] Avoid shuffle self-assignment in EXPENSIVE_CHECKS builds 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 Reviewed By: RKSimon Differential Revision: https://reviews.llvm.org/D98167 --- llvm/include/llvm/ADT/STLExtras.h | 13 ++++++++++--- llvm/tools/bugpoint/FindBugs.cpp | 2 +- llvm/tools/bugpoint/ListReducer.h | 2 +- llvm/tools/llvm-exegesis/lib/SerialSnippetGenerator.cpp | 2 +- llvm/tools/llvm-stress/llvm-stress.cpp | 2 +- 5 files changed, 14 insertions(+), 7 deletions(-) diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h index 67aa6341..dd09cf8 100644 --- a/llvm/include/llvm/ADT/STLExtras.h +++ b/llvm/include/llvm/ADT/STLExtras.h @@ -1332,8 +1332,15 @@ template 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::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. @@ -1373,7 +1380,7 @@ inline unsigned presortShuffleEntropy() { template inline void presortShuffle(IteratorTy Start, IteratorTy End) { std::mt19937 Generator(presortShuffleEntropy()); - std::shuffle(Start, End, Generator); + llvm::shuffle(Start, End, Generator); } } // end namespace detail diff --git a/llvm/tools/bugpoint/FindBugs.cpp b/llvm/tools/bugpoint/FindBugs.cpp index 2b1146d..7713290 100644 --- a/llvm/tools/bugpoint/FindBugs.cpp +++ b/llvm/tools/bugpoint/FindBugs.cpp @@ -41,7 +41,7 @@ BugDriver::runManyPasses(const std::vector &AllPasses) { // // 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. diff --git a/llvm/tools/bugpoint/ListReducer.h b/llvm/tools/bugpoint/ListReducer.h index 04f2207..06f8ddb 100644 --- a/llvm/tools/bugpoint/ListReducer.h +++ b/llvm/tools/bugpoint/ListReducer.h @@ -92,7 +92,7 @@ template struct ListReducer { // distribution (improving the speed of convergence). if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) { std::vector 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 Result = doTest(ShuffledList, empty); diff --git a/llvm/tools/llvm-exegesis/lib/SerialSnippetGenerator.cpp b/llvm/tools/llvm-exegesis/lib/SerialSnippetGenerator.cpp index f5940bd..962136a 100644 --- a/llvm/tools/llvm-exegesis/lib/SerialSnippetGenerator.cpp +++ b/llvm/tools/llvm-exegesis/lib/SerialSnippetGenerator.cpp @@ -42,7 +42,7 @@ computeAliasingInstructions(const LLVMState &State, const Instruction *Instr, std::vector 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 AliasingInstructions; for (const unsigned OtherOpcode : Opcodes) { diff --git a/llvm/tools/llvm-stress/llvm-stress.cpp b/llvm/tools/llvm-stress/llvm-stress.cpp index 538240d..e3fdd78 100644 --- a/llvm/tools/llvm-stress/llvm-stress.cpp +++ b/llvm/tools/llvm-stress/llvm-stress.cpp @@ -718,7 +718,7 @@ static void IntroduceControlFlow(Function *F, Random &R) { 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(); -- 2.7.4