Subzero: Randomize register assignment.

Subzero: Randomize register assignment.

Randomize the order that registers appear in the free list.  Only
randomize fully "equivalent" registers to ensure no extra spills.

This adds the -randomize-regalloc option.

This is a continuation of https://codereview.chromium.org/456033003/ which Matt owns.

BUG= none
R=jfb@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8

[Jim Stichnoth, 2014-12-17 00:20:56]

stichnot@chromium.org changed reviewers:
+ jfb@chromium.org, jvoung@chromium.org

[JF, 2014-12-17 18:56:19]

https://codereview.chromium.org/807293003/diff/40001/src/IceRNG.h
File src/IceRNG.h (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceRNG.h#newcode46
src/IceRNG.h:46: uint64_t next(uint64_t Max) { return RNG.next(Max); }
I'd only have operator() or next(), not both.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:107:
RandomizeRegisterAllocation(CLRandomizeRegisterAllocation) {}
Missing CallsReturnsTwice and Context.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4537: typedef llvm::SmallVector<int32_t, 8>
RegisterList;
Make 8 a constant somewhere, with an explanation.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4568:
EquivalenceClasses[Class.ClassNum].push_back(RegX8632::val);               \
You can't access Class.ClassNum here: the union's active type is Bits. Undefined
behavior.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4571: #undef X
Can't this table be in rodata?

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4578: I != E; ++I) {
C++11.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4582: for (size_t SI = 0, SE = Shuffled.size();
SI < SE; ++SI) {
C++11.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4595: I != E; ++I) {
C++11.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4598: for (SizeT RI = 0, RE = List.size(); RI !=
RE; ++RI) {
C++11.

https://codereview.chromium.org/807293003/diff/40001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/randomize-regalloc.ll (right):

https://codereview.chromium.org/807293003/diff/40001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-regalloc.ll:12: ; RUN:   | FileCheck %s
--check-prefix=OPTM1
Also test with another seed that 1.

[jvoung (off chromium), 2014-12-17 19:53:34]

https://codereview.chromium.org/807293003/diff/40001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:697: Str << (RegNum == Item->getRegNum() ? "Reassigning " :
"Assigning ")
Should this be AssignedRegNum == Item->getRegNum() also? I guess the
!Item->hasReg() should mean that RegNum == AssignedRegNum, but it might be make
sense to keep it AssignedRegNum throughout this block of code.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:246: const bool RandomizeRegisterAllocation;
Maybe keep the bools together.

[Jim Stichnoth, 2014-12-18 18:52:03]

https://codereview.chromium.org/807293003/diff/40001/src/IceRNG.h
File src/IceRNG.h (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceRNG.h#newcode46
src/IceRNG.h:46: uint64_t next(uint64_t Max) { return RNG.next(Max); }
On 2014/12/17 18:56:18, JF wrote:
> I'd only have operator() or next(), not both.

Done.  Leaving operator() for its use in std::random_shuffle().

https://codereview.chromium.org/807293003/diff/40001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:697: Str << (RegNum == Item->getRegNum() ? "Reassigning " :
"Assigning ")
On 2014/12/17 19:53:34, jvoung wrote:
> Should this be AssignedRegNum == Item->getRegNum() also? I guess the
> !Item->hasReg() should mean that RegNum == AssignedRegNum, but it might be
make
> sense to keep it AssignedRegNum throughout this block of code.

Done.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:107:
RandomizeRegisterAllocation(CLRandomizeRegisterAllocation) {}
On 2014/12/17 18:56:18, JF wrote:
> Missing CallsReturnsTwice and Context.

Done for CallsReturnsTwice.  For Context, its ctor takes no arguments, so
there's really no way to specify it in this initializer list, is there?

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:246: const bool RandomizeRegisterAllocation;
On 2014/12/17 19:53:34, jvoung wrote:
> Maybe keep the bools together.

Done.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4537: typedef llvm::SmallVector<int32_t, 8>
RegisterList;
On 2014/12/17 18:56:19, JF wrote:
> Make 8 a constant somewhere, with an explanation.

Done.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4568:
EquivalenceClasses[Class.ClassNum].push_back(RegX8632::val);               \
On 2014/12/17 18:56:19, JF wrote:
> You can't access Class.ClassNum here: the union's active type is Bits.
Undefined
> behavior.

Done.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4571: #undef X
On 2014/12/17 18:56:19, JF wrote:
> Can't this table be in rodata?

Not so readily, since the table is dependent on the input arg ExcludeRegisters. 
Hopefully the simplified code makes that more clear?

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4578: I != E; ++I) {
On 2014/12/17 18:56:19, JF wrote:
> C++11.

Done.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4582: for (size_t SI = 0, SE = Shuffled.size();
SI < SE; ++SI) {
On 2014/12/17 18:56:19, JF wrote:
> C++11.

I don't think much can be done here, since the index SI is being used directly
(Permutation[List[SI]]) in addition to Shuffled[SI].

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4595: I != E; ++I) {
On 2014/12/17 18:56:18, JF wrote:
> C++11.

Done.

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4598: for (SizeT RI = 0, RE = List.size(); RI !=
RE; ++RI) {
On 2014/12/17 18:56:19, JF wrote:
> C++11.

Done.

https://codereview.chromium.org/807293003/diff/40001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/randomize-regalloc.ll (right):

https://codereview.chromium.org/807293003/diff/40001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-regalloc.ll:12: ; RUN:   | FileCheck %s
--check-prefix=OPTM1
On 2014/12/17 18:56:19, JF wrote:
> Also test with another seed that 1.

Done.

[Jim Stichnoth, 2014-12-18 18:59:35]

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/807293003/diff/40001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:107:
RandomizeRegisterAllocation(CLRandomizeRegisterAllocation) {}
On 2014/12/18 18:52:03, stichnot wrote:
> On 2014/12/17 18:56:18, JF wrote:
> > Missing CallsReturnsTwice and Context.
> 
> Done for CallsReturnsTwice.  For Context, its ctor takes no arguments, so
> there's really no way to specify it in this initializer list, is there?

I don't know what happened before, but it's done now. :)

[JF, 2014-12-18 19:14:00]

https://codereview.chromium.org/807293003/diff/100001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/807293003/diff/100001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4534: llvm::SmallVectorImpl<int32_t>
&Permutation,
You may not want to type-erase the vector's size here.

[Jim Stichnoth, 2014-12-18 23:44:46]

https://codereview.chromium.org/807293003/diff/100001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/807293003/diff/100001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:4534: llvm::SmallVectorImpl<int32_t>
&Permutation,
On 2014/12/18 19:14:00, JF wrote:
> You may not want to type-erase the vector's size here.

Added a TODO to match the TODO on the caller side (in IceRegAlloc.cpp).

[JF, 2014-12-19 05:15:25]

lgtm

[Jim Stichnoth, 2014-12-19 13:42:33]

Committed patchset #7 (id:120001) manually as
e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8 (presubmit successful).