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.

BUG=none

[wala, 2014-08-12 03:46:08]

This is provisional. There may be changes after Wednesday's design review.

[JF, 2014-08-12 05:27:00]

I'm wondering if it would be a sufficient randomization to start allocating from
the free list at a random location, and then allocate linearly from there on? It
would be faster than doing a full shuffle, and potentially less disruptive for
performance.

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:28: cl::init(false));
I don't think SubZero should pull in LLVM's cl as it represents a fairly big
chunk of the translator's footprint.

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:415: PreDefinedRegisters | ~RegMaskFull);
Tab.

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:159: typedef std::vector<int32_t> RegisterPermutation;
What's the expected size of this vector? Shouldn't it be ~ number of registers?
If so the that should be a SmallVector.

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

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4075: extern cl::opt<bool>
CLRandomizeRegisterAllocation;
This should be imported from the class instead.

[Jim Stichnoth, 2014-08-14 01:10:29]

https://codereview.chromium.org/456033003/diff/20001/src/IceRNG.h
File src/IceRNG.h (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceRNG.h#newcode34
src/IceRNG.h:34: class RandomNumberGeneratorWrapper {
Here and above, add the usual boilerplate disabling default copy ctor etc.

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:28: cl::init(false));
On 2014/08/12 05:27:00, JF wrote:
> I don't think SubZero should pull in LLVM's cl as it represents a fairly big
> chunk of the translator's footprint.

Really?  That's very sad.  cl is already being used quite a bit in other parts
of Subzero so I guess we'll have to deal with all of those.

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:422: Variable *Var = (*I).Var;
I->Var

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:160: virtual void
makeRandomRegisterPermutation(RegisterPermutation &Permutation,
Can this method be const?

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

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4155: void
TargetX8632::makeRandomRegisterPermutation(
I know this has already been discussed offline, but this is an awfully
heavy-handed function for every instruction in Om1 mode.

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4177: uint8_t IsScratch:1;                       
                           \
For bitfields I think you can just use unsigned.

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

https://codereview.chromium.org/456033003/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-regalloc.ll:3: ; RUN: %llvm2ice -rng-seed=1
-randomize-regalloc %s \
Add an explicit -Om1 option.

Also, add the rest of the usual test configurations?  And the target triple
option?

May be worth documenting that everything changes when the RNG implementation
changes.

[wala, 2014-08-15 03:37:24]

I've changed the -Om1 register allocator implementation to begin assigning
registers from a random offset from the start of the free list, instead of going
through makeRandomRegisterPermutation().

Right now it still does not assign scratch registers before callee save
registers.

https://codereview.chromium.org/456033003/diff/20001/src/IceRNG.h
File src/IceRNG.h (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceRNG.h#newcode34
src/IceRNG.h:34: class RandomNumberGeneratorWrapper {
On 2014/08/14 01:10:29, stichnot wrote:
> Here and above, add the usual boilerplate disabling default copy ctor etc.

Done.

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp
File src/IceRegAlloc.cpp (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:415: PreDefinedRegisters | ~RegMaskFull);
On 2014/08/12 05:27:00, JF wrote:
> Tab.

Woops, done.

https://codereview.chromium.org/456033003/diff/20001/src/IceRegAlloc.cpp#newc...
src/IceRegAlloc.cpp:422: Variable *Var = (*I).Var;
On 2014/08/14 01:10:29, stichnot wrote:
> I->Var

Done.

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:159: typedef std::vector<int32_t> RegisterPermutation;
On 2014/08/12 05:27:00, JF wrote:
> What's the expected size of this vector? Shouldn't it be ~ number of
registers?
> If so the that should be a SmallVector.

Done.

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:160: virtual void
makeRandomRegisterPermutation(RegisterPermutation &Permutation,
On 2014/08/14 01:10:29, stichnot wrote:
> Can this method be const?

It changes the state of the RNG, so I wouldn't make it const.

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

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4075: extern cl::opt<bool>
CLRandomizeRegisterAllocation;
On 2014/08/12 05:27:00, JF wrote:
> This should be imported from the class instead.

Done.

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4155: void
TargetX8632::makeRandomRegisterPermutation(
On 2014/08/14 01:10:29, stichnot wrote:
> I know this has already been discussed offline, but this is an awfully
> heavy-handed function for every instruction in Om1 mode.

Done.

https://codereview.chromium.org/456033003/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4177: uint8_t IsScratch:1;                       
                           \
On 2014/08/14 01:10:29, stichnot wrote:
> For bitfields I think you can just use unsigned.

Done.

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

https://codereview.chromium.org/456033003/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-regalloc.ll:3: ; RUN: %llvm2ice -rng-seed=1
-randomize-regalloc %s \
On 2014/08/14 01:10:29, stichnot wrote:
> Add an explicit -Om1 option.
> 
> Also, add the rest of the usual test configurations?  And the target triple
> option?
> 
> May be worth documenting that everything changes when the RNG implementation
> changes.

Done.

[Jim Stichnoth, 2014-12-17 00:39:01]

This is being replaced by https://codereview.chromium.org/807293003/ since I
can't assume ownership of this CL.