Subzero: Randomize immediates by constant blinding or pooling.

Subzero: Randomize immediates by constant blinding or pooling.

Randomization is invoked through the command line flag
-randomize-immediates=<none,constant-blinding,constant-pooling>.

BUG=none

[wala, 2014-08-12 03:47:24]

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

[JF, 2014-08-12 05:37:47]

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

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:132: const uint64_t
X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD = 65536;
I find 0xFFFF more readable.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:149: return ConstInt->getType() != IceType_i64 &&
Why not i64?

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:152: return false;
What about FP and vectors?

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:193: clEnumValEnd));
Those should probably be composable.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:906: void TargetX8632::emitPooledImmediates()
const {
Are redundant pooled immediates pooled at the same location (and shared between
functions)? Is their ordering predictable? Is there any effort to reduce the
number of "far" immediates from a function?

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4022: // WARNING: Constant blinding overwrites
the flags register.
Is that one random cookie per immediate, or one per function or basic block?

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4050: uint32_t Mask1 =
RNG.next((uint64_t)UINT32_MAX + 1);
Use std::numeric_limits.

[Jim Stichnoth, 2014-08-13 23:30:26]

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:42: } // end anonymous namespace
"end of anonymous namespace" has more votes. :)

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:88: // any type.
Can you clarify in the comment that the string is meant to

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:90: void addConstantPooledImmediate(IceString Name,
Constant *Immediate);
Use const IceString & here and all the way up.

Also, can you use const Constant *Immediate?

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

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:145: } else if
(llvm::isa<ConstantRelocatable>(Immediate)) {
Remove "else" after "return".

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:149: return ConstInt->getType() != IceType_i64 &&
On 2014/08/12 05:37:47, JF wrote:
> Why not i64?

i64 constants are split into i32 operations at this point, so they shouldn't
occur.  Maybe assert this?

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:150: ConstInt->getValue() >=
X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD;
As we discussed offline, you probably want to add
X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD/2 before comparing to deal with
negative immediates.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:152: return false;
On 2014/08/12 05:37:47, JF wrote:
> What about FP and vectors?

FP and vector constants are always pooled, due to lack of immediate addressing
mode in x86 for these types.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:193: clEnumValEnd));
On 2014/08/12 05:37:47, JF wrote:
> Those should probably be composable.

I didn't think it would add any more security to blind *and* pool a constant, so
I suggested using the enum instead of composition.  Composing also increases the
complexity and testing requirements.  (Also, constant folding is another option
that isn't yet included here.)

Unless you mean composable in the sense that some constants could be blinded and
others pooled?  Maybe with the per-instance decision made randomly?

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4049: RandomNumberGenerator &RNG = Ctx->getRNG();
I think it should be one random cookie per function, or the same across all
functions.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4086: if (CLRandomizeImmediates &&
immediateShouldBeRandomized(Offset)) {
Can you just add the CLRandomizeImmediates test into
immediateShouldBeRandomized()?

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

https://codereview.chromium.org/460233002/diff/40001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-immediates.ll:14: ; BLINDING: xor ecx, 216295
Instead of ecx, could you use a pattern that tests that the same register is
used in both instructions?

https://codereview.chromium.org/460233002/diff/40001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-immediates.ll:17: ; POOLING: mov ecx, dword
ptr [L$i32$0]
Instead of ecx, would it be reasonable test for any register?

[wala, 2014-08-16 00:07:13]

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:42: } // end anonymous namespace
On 2014/08/13 23:30:25, stichnot wrote:
> "end of anonymous namespace" has more votes. :)

Done.

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:88: // any type.
On 2014/08/13 23:30:25, stichnot wrote:
> Can you clarify in the comment that the string is meant to 

I don't know exactly what you mean, but I've clarified the usage and purposes of
this pool class.

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/460233002/diff/40001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:90: void addConstantPooledImmediate(IceString Name,
Constant *Immediate);
On 2014/08/13 23:30:25, stichnot wrote:
> Use const IceString & here and all the way up.
> 
> Also, can you use const Constant *Immediate?

const IceString &: Done.

const Constant *: Doesn't work, getImmediatePool() returns a ConstantList whose
elements are non-const.

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

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:132: const uint64_t
X86_INT_IMMEDIATE_RANDOMIZATION_THRESHOLD = 65536;
On 2014/08/12 05:37:47, JF wrote:
> I find 0xFFFF more readable.

Done.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:145: } else if
(llvm::isa<ConstantRelocatable>(Immediate)) {
On 2014/08/13 23:30:25, stichnot wrote:
> Remove "else" after "return".

Done.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:149: return ConstInt->getType() != IceType_i64 &&
On 2014/08/13 23:30:25, stichnot wrote:
> On 2014/08/12 05:37:47, JF wrote:
> > Why not i64?
> 
> i64 constants are split into i32 operations at this point, so they shouldn't
> occur.  Maybe assert this?

Done.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:906: void TargetX8632::emitPooledImmediates()
const {
On 2014/08/12 05:37:47, JF wrote:
> Are redundant pooled immediates pooled at the same location (and shared
between
> functions)? Is their ordering predictable? Is there any effort to reduce the
> number of "far" immediates from a function?

Right now, the implementation uses the Subzero constant pooling infrastructure
which builds global constant pools that are emitted after all the functions have
been emitted.

The ordering of the immediates in the constant pool is predictable for
reproducibility purposes.

There's currently no code that emits per-function constant pools or tries to
locate pooled constants near the functions that use them.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4022: // WARNING: Constant blinding overwrites
the flags register.
On 2014/08/12 05:37:47, JF wrote:
> Is that one random cookie per immediate, or one per function or basic block?

One per immediate.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4049: RandomNumberGenerator &RNG = Ctx->getRNG();
On 2014/08/13 23:30:25, stichnot wrote:
> I think it should be one random cookie per function, or the same across all
> functions.

Done, no CSE yet.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4050: uint32_t Mask1 =
RNG.next((uint64_t)UINT32_MAX + 1);
On 2014/08/12 05:37:47, JF wrote:
> Use std::numeric_limits.

Done.

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:4086: if (CLRandomizeImmediates &&
immediateShouldBeRandomized(Offset)) {
On 2014/08/13 23:30:25, stichnot wrote:
> Can you just add the CLRandomizeImmediates test into
> immediateShouldBeRandomized()?

Done.

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

https://codereview.chromium.org/460233002/diff/40001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-immediates.ll:14: ; BLINDING: xor ecx, 216295
On 2014/08/13 23:30:26, stichnot wrote:
> Instead of ecx, could you use a pattern that tests that the same register is
> used in both instructions?

Done.

https://codereview.chromium.org/460233002/diff/40001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/randomize-immediates.ll:17: ; POOLING: mov ecx, dword
ptr [L$i32$0]
On 2014/08/13 23:30:26, stichnot wrote:
> Instead of ecx, would it be reasonable test for any register?

Done.

[wala, 2014-08-16 00:16:15]

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

https://codereview.chromium.org/460233002/diff/40001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:149: return ConstInt->getType() != IceType_i64 &&
On 2014/08/16 00:07:13, wala wrote:
> On 2014/08/13 23:30:25, stichnot wrote:
> > On 2014/08/12 05:37:47, JF wrote:
> > > Why not i64?
> > 
> > i64 constants are split into i32 operations at this point, so they shouldn't
> > occur.  Maybe assert this?
> 
> Done.

Hmm, it looks like some i64 "immediates" are reaching this function when I run
the crosstests with constant blinding enabled.

I don't know the exact issue that is causing this, but I know that the call is
made in line 4234 of patchset #3 (the second usage of
immediateShouldBeRandomized() in legalize()).

[Jim Stichnoth, 2015-06-22 20:24:38]

Closing.  Moved to https://codereview.chromium.org/1185703004/ .