Subzero: Randomly insert nops.

Subzero: Randomly insert nops.

Adds command line options -nop-insertion, -nop-insertion-probability=X, and -max-nops-per-instruction=X.

BUG=none
R=jvoung@chromium.org, stichnot@chromium.org

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

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

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

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

lgtm

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

https://codereview.chromium.org/463563006/diff/20001/src/IceRNG.h#newcode34
src/IceRNG.h:34: class RandomNumberGeneratorWrapper {
Disable default copy ctor etc.

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:36: } // end anonymous namespace
end of anonymous namespace

[jvoung (off chromium), 2014-08-14 15:17:17]

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:34: cl::desc("Nop insertion probability"),
A default of "10" should be a strong hint at the units, but it would be good to
be explicit about the units -- (percentage vs 0.0 to 1.0 fraction).

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

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:133: const uint32_t X86_MAX_NOP_LEN = 9;
Does it actually help to add nops of up to 9 bytes?

The UCI CGO paper only has a table of 7 nop candidates (of which 5 are not awful
for performance). The choices are just the 1-byte nop, and several 2-byte nop
variants. By default only one of the 5 may be randomly inserted. It sounds like
the main point is that the nop can turn non-bundle-aligned streams of
instructions into things that are less useful when executed -- e.g., some of the
2 byte nops, if jumped into the middle-of, are interpreted as privileged
instructions that cannot be run:
(https://www.ics.uci.edu/~ahomescu/multicompiler_cgo13.pdf)

https://codereview.chromium.org/463563006/diff/20001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/nop-insertion.ll (right):

https://codereview.chromium.org/463563006/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/nop-insertion.ll:3: ; RUN: %llvm2ice -rng-seed=1
-insert-nops -nop-probability=50 %s | FileCheck %s
maybe test at 90% also, to test that the nop-probability matters / is not
inverted

[wala, 2014-08-14 23:29:50]

In addition to addressing the comments, I've made the interface identical to the
current version of the LLVM interface (http://reviews.llvm.org/D3392).

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

https://codereview.chromium.org/463563006/diff/20001/src/IceRNG.h#newcode34
src/IceRNG.h:34: class RandomNumberGeneratorWrapper {
On 2014/08/14 01:20:09, stichnot wrote:
> Disable default copy ctor etc.

Done.

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:34: cl::desc("Nop insertion probability"),
On 2014/08/14 15:17:17, jvoung wrote:
> A default of "10" should be a strong hint at the units, but it would be good
to
> be explicit about the units -- (percentage vs 0.0 to 1.0 fraction).

Done.

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:36: } // end anonymous namespace
On 2014/08/14 01:20:10, stichnot wrote:
> end of anonymous namespace

Done.

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

https://codereview.chromium.org/463563006/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:133: const uint32_t X86_MAX_NOP_LEN = 9;
On 2014/08/14 15:17:17, jvoung wrote:
> Does it actually help to add nops of up to 9 bytes?
> 
> The UCI CGO paper only has a table of 7 nop candidates (of which 5 are not
awful
> for performance). The choices are just the 1-byte nop, and several 2-byte nop
> variants. By default only one of the 5 may be randomly inserted. It sounds
like
> the main point is that the nop can turn non-bundle-aligned streams of
> instructions into things that are less useful when executed -- e.g., some of
the
> 2 byte nops, if jumped into the middle-of, are interpreted as privileged
> instructions that cannot be run:
> (https://www.ics.uci.edu/~ahomescu/multicompiler_cgo13.pdf)

Thanks for the link.

That paper makes it clear that length is not the most important attribute of the
nop.

To this end, I've changed the NOP instruction to take a "nop variant" parameter
instead of a "length" parameter.

Variant is currently an integer, but eventually it should be expanded into an
enum once it is decided which nop sequences to use.

https://codereview.chromium.org/463563006/diff/20001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/nop-insertion.ll (right):

https://codereview.chromium.org/463563006/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/nop-insertion.ll:3: ; RUN: %llvm2ice -rng-seed=1
-insert-nops -nop-probability=50 %s | FileCheck %s
On 2014/08/14 15:17:17, jvoung wrote:
> maybe test at 90% also, to test that the nop-probability matters / is not
> inverted

Done.

[Jim Stichnoth, 2014-08-15 14:07:08]

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

https://codereview.chromium.org/463563006/diff/40001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:199: virtual void randomlyInsertNop(float) {}
float Probability

[wala, 2014-08-15 17:57:49]

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

https://codereview.chromium.org/463563006/diff/40001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:199: virtual void randomlyInsertNop(float) {}
On 2014/08/15 14:07:08, stichnot wrote:
> float Probability

Done.

[Jim Stichnoth, 2014-08-15 20:06:39]

Still lgtm, pending Jan's review.

[jvoung (off chromium), 2014-08-15 20:18:12]

LGTM thanks

https://codereview.chromium.org/463563006/diff/60001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/nop-insertion.ll (right):

https://codereview.chromium.org/463563006/diff/60001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/nop-insertion.ll:66: ; PROB90: nop # variant = 0
Interesting, I guess counted pseudo-insts like FakeUse(?)

[wala, 2014-08-15 22:19:46]

A slight change: I've made the nop insertion insert NOPs before the current
instruction rather than after, so that we get a nop before the first instruction
in the list and no nop after ret. Furthermore, I've changed the nop insertion to
ignore the Fake* instructions.

https://codereview.chromium.org/463563006/diff/60001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/nop-insertion.ll (right):

https://codereview.chromium.org/463563006/diff/60001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/nop-insertion.ll:66: ; PROB90: nop # variant = 0
On 2014/08/15 20:18:11, jvoung wrote:
> Interesting, I guess counted pseudo-insts like FakeUse(?) 

Yes. That's probably not what we want. Fixed.

[wala, 2014-08-15 23:22:02]

Committed patchset #5 manually as c330274 (presubmit successful).