Subzero: Use a "deterministic" random shuffle for register allocation.
To make this work, Subzero provides its own RandomShuffle() as a replacement for std::random_shuffle(), and the Subzero implementation doesn't depend on the stdlib implementation.
BUG= https://code.google.com/p/nativeclient/issues/detail?id=4129
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/1072913002
diff --git a/src/IceRNG.h b/src/IceRNG.h
index bf01e41..a2d8e96 100644
--- a/src/IceRNG.h
+++ b/src/IceRNG.h
@@ -53,6 +53,15 @@
RandomNumberGenerator &RNG;
};
+// RandomShuffle is an implementation of std::random_shuffle() that
+// doesn't change across stdlib implementations. Adapted from a
+// sample implementation at cppreference.com.
+template <class RandomIt, class RandomFunc>
+void RandomShuffle(RandomIt First, RandomIt Last, RandomFunc &&RNG) {
+ for (auto i = Last - First - 1; i > 0; --i)
+ std::swap(First[i], First[RNG(i + 1)]);
+}
+
} // end of namespace Ice
#endif // SUBZERO_SRC_ICERNG_H
diff --git a/src/IceTargetLoweringX8632.cpp b/src/IceTargetLoweringX8632.cpp
index 662ac54..bd67844 100644
--- a/src/IceTargetLoweringX8632.cpp
+++ b/src/IceTargetLoweringX8632.cpp
@@ -4621,7 +4621,7 @@
for (auto I : EquivalenceClasses) {
const RegisterList &List = I.second;
RegisterList Shuffled(List);
- std::random_shuffle(Shuffled.begin(), Shuffled.end(), RNG);
+ RandomShuffle(Shuffled.begin(), Shuffled.end(), RNG);
for (size_t SI = 0, SE = Shuffled.size(); SI < SE; ++SI) {
Permutation[List[SI]] = Shuffled[SI];
++NumShuffled;
diff --git a/tests_lit/llvm2ice_tests/randomize-regalloc.ll b/tests_lit/llvm2ice_tests/randomize-regalloc.ll
index f393938..696fce5 100644
--- a/tests_lit/llvm2ice_tests/randomize-regalloc.ll
+++ b/tests_lit/llvm2ice_tests/randomize-regalloc.ll
@@ -26,11 +26,11 @@
; OPTM1_1-NEXT: movups XMMWORD PTR [esp+0x20],xmm0
; OPTM1_1-NEXT: movups XMMWORD PTR [esp+0x10],xmm1
; OPTM1_1-NEXT: movups xmm0,XMMWORD PTR [esp+0x20]
-; OPTM1_1-NEXT: pshufd xmm7,XMMWORD PTR [esp+0x20],0x31
-; OPTM1_1-NEXT: pshufd xmm4,XMMWORD PTR [esp+0x10],0x31
+; OPTM1_1-NEXT: pshufd xmm1,XMMWORD PTR [esp+0x20],0x31
+; OPTM1_1-NEXT: pshufd xmm2,XMMWORD PTR [esp+0x10],0x31
; OPTM1_1-NEXT: pmuludq xmm0,XMMWORD PTR [esp+0x10]
-; OPTM1_1-NEXT: pmuludq xmm7,xmm4
-; OPTM1_1-NEXT: shufps xmm0,xmm7,0x88
+; OPTM1_1-NEXT: pmuludq xmm1,xmm2
+; OPTM1_1-NEXT: shufps xmm0,xmm1,0x88
; OPTM1_1-NEXT: pshufd xmm0,xmm0,0xd8
; OPTM1_1-NEXT: movups XMMWORD PTR [esp],xmm0
; OPTM1_1-NEXT: movups xmm0,XMMWORD PTR [esp]
@@ -38,14 +38,14 @@
; OPTM1_1-NEXT: ret
; CHECK_1-LABEL: mul_v4i32
-; CHECK_1: movups xmm6,xmm0
+; CHECK_1: movups xmm5,xmm0
; CHECK_1-NEXT: pshufd xmm0,xmm0,0x31
-; CHECK_1-NEXT: pshufd xmm5,xmm1,0x31
-; CHECK_1-NEXT: pmuludq xmm6,xmm1
-; CHECK_1-NEXT: pmuludq xmm0,xmm5
-; CHECK_1-NEXT: shufps xmm6,xmm0,0x88
-; CHECK_1-NEXT: pshufd xmm6,xmm6,0xd8
-; CHECK_1-NEXT: movups xmm0,xmm6
+; CHECK_1-NEXT: pshufd xmm3,xmm1,0x31
+; CHECK_1-NEXT: pmuludq xmm5,xmm1
+; CHECK_1-NEXT: pmuludq xmm0,xmm3
+; CHECK_1-NEXT: shufps xmm5,xmm0,0x88
+; CHECK_1-NEXT: pshufd xmm5,xmm5,0xd8
+; CHECK_1-NEXT: movups xmm0,xmm5
; CHECK_1-NEXT: ret
; OPTM1_123-LABEL: mul_v4i32
@@ -53,11 +53,11 @@
; OPTM1_123-NEXT: movups XMMWORD PTR [esp+0x20],xmm0
; OPTM1_123-NEXT: movups XMMWORD PTR [esp+0x10],xmm1
; OPTM1_123-NEXT: movups xmm0,XMMWORD PTR [esp+0x20]
-; OPTM1_123-NEXT: pshufd xmm2,XMMWORD PTR [esp+0x20],0x31
+; OPTM1_123-NEXT: pshufd xmm1,XMMWORD PTR [esp+0x20],0x31
; OPTM1_123-NEXT: pshufd xmm6,XMMWORD PTR [esp+0x10],0x31
; OPTM1_123-NEXT: pmuludq xmm0,XMMWORD PTR [esp+0x10]
-; OPTM1_123-NEXT: pmuludq xmm2,xmm6
-; OPTM1_123-NEXT: shufps xmm0,xmm2,0x88
+; OPTM1_123-NEXT: pmuludq xmm1,xmm6
+; OPTM1_123-NEXT: shufps xmm0,xmm1,0x88
; OPTM1_123-NEXT: pshufd xmm0,xmm0,0xd8
; OPTM1_123-NEXT: movups XMMWORD PTR [esp],xmm0
; OPTM1_123-NEXT: movups xmm0,XMMWORD PTR [esp]
@@ -65,14 +65,14 @@
; OPTM1_123-NEXT: ret
; CHECK_123-LABEL: mul_v4i32
-; CHECK_123: movups xmm3,xmm0
+; CHECK_123: movups xmm4,xmm0
; CHECK_123-NEXT: pshufd xmm0,xmm0,0x31
-; CHECK_123-NEXT: pshufd xmm7,xmm1,0x31
-; CHECK_123-NEXT: pmuludq xmm3,xmm1
-; CHECK_123-NEXT: pmuludq xmm0,xmm7
-; CHECK_123-NEXT: shufps xmm3,xmm0,0x88
-; CHECK_123-NEXT: pshufd xmm3,xmm3,0xd8
-; CHECK_123-NEXT: movups xmm0,xmm3
+; CHECK_123-NEXT: pshufd xmm2,xmm1,0x31
+; CHECK_123-NEXT: pmuludq xmm4,xmm1
+; CHECK_123-NEXT: pmuludq xmm0,xmm2
+; CHECK_123-NEXT: shufps xmm4,xmm0,0x88
+; CHECK_123-NEXT: pshufd xmm4,xmm4,0xd8
+; CHECK_123-NEXT: movups xmm0,xmm4
; CHECK_123-NEXT: ret
}
diff --git a/unittest/IceELFSectionTest.cpp b/unittest/IceELFSectionTest.cpp
index 8dbcc65..57e43c1 100644
--- a/unittest/IceELFSectionTest.cpp
+++ b/unittest/IceELFSectionTest.cpp
@@ -90,8 +90,11 @@
Strings.push_back(".shstrtab");
Strings.push_back("_start");
const SizeT NumTests = 128;
+ const uint64_t RandomSeed = 12345; // arbitrary value for now
+ RandomNumberGenerator R(RandomSeed);
+ RandomNumberGeneratorWrapper RNG(R);
for (SizeT i = 0; i < NumTests; ++i) {
- std::random_shuffle(Strings.begin(), Strings.end());
+ RandomShuffle(Strings.begin(), Strings.end(), RNG);
ELFStringTableSection Strtab(".strtab", SHT_STRTAB, 0, 1, 0);
for (auto &S : Strings) {
Strtab.add(S);
