Subzero: Fix over-aggressive bool folding.

Subzero: Fix over-aggressive bool folding.

The problem is that bitcode like this:

  %cond = cmp %var, [mem]
  store ..., mem
  br cond, target1, target2

would be bool-folded into this:

  //deleted cmp
  store ..., mem
  br (%var==[mem]), target1, target2

And if the memory operands point to the same location, results are incorrect.

In addition to stores, this is a problem for RMW instructions, and most call instructions which could perform stores before returning.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4370
R=eholk@chromium.org, jpp@chromium.org

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

[Jim Stichnoth, 2016-04-21 21:49:57]

Description was changed from

==========
Subzero: Fix over-aggressive bool folding.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4370
==========

to

==========
Subzero: Fix over-aggressive bool folding.

The problem is that bitcode like this:

  %cond = cmp %var, [mem]
  store ..., mem
  br cond, target1, target2

would be bool-folded into this:

  //deleted cmp
  store ..., mem
  br (%var==[mem]), target1, target2

And if the memory operands point to the same location, results are incorrect.

In addition to stores, this is a problem for RMW instructions, and most call
instructions which could perform stores before returning.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4370
==========

[Jim Stichnoth, 2016-04-21 21:49:57]

stichnot@chromium.org changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, kschimpf@google.com, sehr@chromium.org

[Eric Holk, 2016-04-21 22:09:44]

lgtm otherwise.

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode268
src/IceInst.h:268: bool isMemoryWrite() const final { return false; }
What's the reasoning for making these final?

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode934
src/IceInst.h:934: bool isMemoryWrite() const final { return false; }
Since all the other instructions have isMemoryWrite() declared final, would it
make sense to add one for stores that returns true?

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp
File src/IceIntrinsics.cpp (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp#newco...
src/IceIntrinsics.cpp:75: INTRIN(AtomicLoad, SideEffects_T, ReturnsTwice_F,
MemoryWrite_T),        \
Does AtomicLoad write memory?

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.h
File src/IceIntrinsics.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.h#newcode119
src/IceIntrinsics.h:119: enum MemoryWrite IsMemoryWrite : 1;
It looks like this struct is meant to be 32-bits. What about adding a
static_assert to make sure it stays the right size?

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:256: if (Instr.isDeleted())
As a future CL, it would probably be nice to add a non-deleted instructions
iterator (or maybe active or live instructions instead of calling them
non-deleted) so we don't have to remember to do this check.

https://codereview.chromium.org/1904233002/diff/1/tests_lit/llvm2ice_tests/bo...
File tests_lit/llvm2ice_tests/bool-folding.ll (right):

https://codereview.chromium.org/1904233002/diff/1/tests_lit/llvm2ice_tests/bo...
tests_lit/llvm2ice_tests/bool-folding.ll:273: define internal i32
@no_fold_cmp_br_store(i32 %arg2, i32 %argaddr) {
These tests fail without this change, correct?

[John, 2016-04-21 22:50:02]

lgtm

LGTM, but please explain invalidateProducersOnStore... :)

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode142
src/IceInst.h:142: virtual bool isMemoryWrite() const { return true; }
what's wrong with = 0, and forcing each new classes to reason about its return
value?

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode268
src/IceInst.h:268: bool isMemoryWrite() const final { return false; }
I tend to prefer using final for classes only. If you think about it, InstAlloca
should be final -- as should every other HLI? Anyway, consider leaving this
non-final.

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp
File src/IceIntrinsics.cpp (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp#newco...
src/IceIntrinsics.cpp:46: {                                                     
                      \
make format

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:352: /// set to false, then we know the
folding is safe from the store instruction.
"If IsLiveOut has already been set to false, then we know the folding is safe
from the store instruction." why?

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:365: for (SizeT I = 0; !HasMemOperand && I <
SrcSize; ++I) {
why not breaking instead? I would expect llvm to efficiently lower

for (var = init; var < const; ++var)

but I would be surprised if it managed to do anything decent with moar
complicated fors...

[Jim Stichnoth, 2016-04-21 22:50:29]

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode268
src/IceInst.h:268: bool isMemoryWrite() const final { return false; }
On 2016/04/21 22:09:43, Eric Holk wrote:
> What's the reasoning for making these final?

We seem to do that quite regularly in Subzero so I followed suit.  I think John
can approve/disapprove.

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode934
src/IceInst.h:934: bool isMemoryWrite() const final { return false; }
On 2016/04/21 22:09:43, Eric Holk wrote:
> Since all the other instructions have isMemoryWrite() declared final, would it
> make sense to add one for stores that returns true?

Done.

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp
File src/IceIntrinsics.cpp (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp#newco...
src/IceIntrinsics.cpp:75: INTRIN(AtomicLoad, SideEffects_T, ReturnsTwice_F,
MemoryWrite_T),        \
On 2016/04/21 22:09:43, Eric Holk wrote:
> Does AtomicLoad write memory?

It doesn't, but I feel like conservatively you shouldn't be reordering things
with respect to atomics (noting that is.lock.free isn't really an atomic
operation).

I would change it to _F if people are sure it's safe.

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.h
File src/IceIntrinsics.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.h#newcode119
src/IceIntrinsics.h:119: enum MemoryWrite IsMemoryWrite : 1;
On 2016/04/21 22:09:43, Eric Holk wrote:
> It looks like this struct is meant to be 32-bits. What about adding a
> static_assert to make sure it stays the right size?

Done.

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:256: if (Instr.isDeleted())
On 2016/04/21 22:09:43, Eric Holk wrote:
> As a future CL, it would probably be nice to add a non-deleted instructions
> iterator (or maybe active or live instructions instead of calling them
> non-deleted) so we don't have to remember to do this check.

That's a great idea.

https://codereview.chromium.org/1904233002/diff/1/tests_lit/llvm2ice_tests/bo...
File tests_lit/llvm2ice_tests/bool-folding.ll (right):

https://codereview.chromium.org/1904233002/diff/1/tests_lit/llvm2ice_tests/bo...
tests_lit/llvm2ice_tests/bool-folding.ll:273: define internal i32
@no_fold_cmp_br_store(i32 %arg2, i32 %argaddr) {
On 2016/04/21 22:09:43, Eric Holk wrote:
> These tests fail without this change, correct?

Yes, they all fail in the original.

One can easily test this by adding a "return;" statement to the very start of
BoolFolding<Traits>::invalidateProducersOnStore().

[Eric Holk, 2016-04-21 23:03:28]

still lgtm

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp
File src/IceIntrinsics.cpp (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp#newco...
src/IceIntrinsics.cpp:75: INTRIN(AtomicLoad, SideEffects_T, ReturnsTwice_F,
MemoryWrite_T),        \
On 2016/04/21 22:50:29, stichnot wrote:
> On 2016/04/21 22:09:43, Eric Holk wrote:
> > Does AtomicLoad write memory?
> 
> It doesn't, but I feel like conservatively you shouldn't be reordering things
> with respect to atomics (noting that is.lock.free isn't really an atomic
> operation).
> 
> I would change it to _F if people are sure it's safe.

Leaving it at _T seems like the safe option. Optimizing atomics is tricky, so
it's probably better to play it safe.

[Jim Stichnoth, 2016-04-21 23:31:36]

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode142
src/IceInst.h:142: virtual bool isMemoryWrite() const { return true; }
On 2016/04/21 22:50:01, John wrote:
> what's wrong with = 0, and forcing each new classes to reason about its return
> value?

Done.

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode268
src/IceInst.h:268: bool isMemoryWrite() const final { return false; }
On 2016/04/21 22:50:01, John wrote:
> I tend to prefer using final for classes only. If you think about it,
InstAlloca
> should be final -- as should every other HLI? Anyway, consider leaving this
> non-final.

Done.

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp
File src/IceIntrinsics.cpp (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceIntrinsics.cpp#newco...
src/IceIntrinsics.cpp:46: {                                                     
                      \
On 2016/04/21 22:50:02, John wrote:
> make format

Wow, don't know what happened here.

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:352: /// set to false, then we know the
folding is safe from the store instruction.
On 2016/04/21 22:50:02, John wrote:
> "If IsLiveOut has already been set to false, then we know the folding is safe
> from the store instruction." why?

Done, hopefully it's more explanatory now.

https://codereview.chromium.org/1904233002/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:365: for (SizeT I = 0; !HasMemOperand && I <
SrcSize; ++I) {
On 2016/04/21 22:50:02, John wrote:
> why not breaking instead? I would expect llvm to efficiently lower
> 
> for (var = init; var < const; ++var)
> 
> but I would be surprised if it managed to do anything decent with moar
> complicated fors...

Done.

[Jim Stichnoth, 2016-04-21 23:32:41]

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode142
src/IceInst.h:142: virtual bool isMemoryWrite() const { return true; }
On 2016/04/21 23:31:35, stichnot wrote:
> On 2016/04/21 22:50:01, John wrote:
> > what's wrong with = 0, and forcing each new classes to reason about its
return
> > value?
> 
> Done.

Whoops, what I meant was, that would be nice except that g++ doesn't like it
with respect to llvm::ilist<>.

[John, 2016-04-21 23:33:16]

On 2016/04/21 23:32:41, stichnot wrote:
> https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h
> File src/IceInst.h (right):
> 
> https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode142
> src/IceInst.h:142: virtual bool isMemoryWrite() const { return true; }
> On 2016/04/21 23:31:35, stichnot wrote:
> > On 2016/04/21 22:50:01, John wrote:
> > > what's wrong with = 0, and forcing each new classes to reason about its
> return
> > > value?
> > 
> > Done.
> 
> Whoops, what I meant was, that would be nice except that g++ doesn't like it
> with respect to llvm::ilist<>.

then have a default that invokes llvm::report_fatal_error. :)

[John, 2016-04-21 23:33:25]

lgtm

still lgtm

[Jim Stichnoth, 2016-04-21 23:43:38]

On 2016/04/21 23:33:16, John wrote:
> On 2016/04/21 23:32:41, stichnot wrote:
> > https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h
> > File src/IceInst.h (right):
> > 
> > https://codereview.chromium.org/1904233002/diff/1/src/IceInst.h#newcode142
> > src/IceInst.h:142: virtual bool isMemoryWrite() const { return true; }
> > On 2016/04/21 23:31:35, stichnot wrote:
> > > On 2016/04/21 22:50:01, John wrote:
> > > > what's wrong with = 0, and forcing each new classes to reason about its
> > return
> > > > value?
> > > 
> > > Done.
> > 
> > Whoops, what I meant was, that would be nice except that g++ doesn't like it
> > with respect to llvm::ilist<>.
> 
> then have a default that invokes llvm::report_fatal_error. :)

Cool, done.

[Jim Stichnoth, 2016-04-21 23:54:36]

Description was changed from

==========
Subzero: Fix over-aggressive bool folding.

The problem is that bitcode like this:

  %cond = cmp %var, [mem]
  store ..., mem
  br cond, target1, target2

would be bool-folded into this:

  //deleted cmp
  store ..., mem
  br (%var==[mem]), target1, target2

And if the memory operands point to the same location, results are incorrect.

In addition to stores, this is a problem for RMW instructions, and most call
instructions which could perform stores before returning.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4370
==========

to

==========
Subzero: Fix over-aggressive bool folding.

The problem is that bitcode like this:

  %cond = cmp %var, [mem]
  store ..., mem
  br cond, target1, target2

would be bool-folded into this:

  //deleted cmp
  store ..., mem
  br (%var==[mem]), target1, target2

And if the memory operands point to the same location, results are incorrect.

In addition to stores, this is a problem for RMW instructions, and most call
instructions which could perform stores before returning.

BUG= https://bugs.chromium.org/p/nativeclient/issues/detail?id=4370
R=eholk@chromium.org, jpp@chromium.org

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

[Jim Stichnoth, 2016-04-21 23:54:37]

Committed patchset #4 (id:60001) manually as
f1f773dd2c9c7118e07caa61d580bdba4447c25c (presubmit successful).