Add support for undef values in ICE IR.

Add support for undef values in ICE IR. Undef values represent an
arbitrary bit pattern and are lowered to a zero constant.

IceOperand.h: Introduce a new ConstantUndef subclass of
Constant. Add a getConstantZero() method.

IceGlobalContext.h / IceGlobalContext.cpp: Implement pooling for
ConstantUndefs.

IceTargetLoweringX8632.cpp: Legalize ConstantUndefs to constant
zeros.

llvm2ice.cpp: Translate LLVM Undefs into ConstantUndefs.

undef.ll: Test that undef values are recognized and legalized to
zero.

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=d8f4a7d

[Jim Stichnoth, 2014-06-17 06:28:08]

https://codereview.chromium.org/339783002/diff/1/src/IceTargetLoweringX8632.cpp
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/339783002/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:2156: // Undef values are lowered to a register.
Maybe change "lowered to a register" to "lowered to an uninitialized register"
just to be clear, and that also makes it more clear why a FakeDef would be
needed.

Also, it wouldn't hurt to assert(Allowed & Legal_Reg), which I believe is true
for all current calls to legalize() and probably will always be true, but still.

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
File tests_lit/llvm2ice_tests/undef.ll (right):

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
tests_lit/llvm2ice_tests/undef.ll:10: define i32 @return() {
For both of these tests, add i64 and floating-point versions as well.

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
tests_lit/llvm2ice_tests/undef.ll:24: %__1 = add i32 undef, %arg
I think it could be worthwhile to test undef as the first operand, versus the
second operand, versus both operands.  Also, use a non-commutative operator like
sub just in case future changes to lowering code try to improve the sequence by
commuting.

[jvoung (off chromium), 2014-06-17 15:50:11]

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
File tests_lit/llvm2ice_tests/undef.ll (right):

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
tests_lit/llvm2ice_tests/undef.ll:12: ; CHECK: return:
Should we start using CHECK-LABEL more?

http://llvm.org/docs/CommandGuide/FileCheck.html#the-check-label-directive

It's a bit more robust.

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
tests_lit/llvm2ice_tests/undef.ll:28: }
Sometimes function call arguments are "undef". In that case it could use the
uninitialized stack slot instead of the an uninitialized register... but that's
probably not worth avoiding going to a register first, since undef shouldn't be
too common.

[Jim Stichnoth, 2014-06-17 17:51:13]

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
File tests_lit/llvm2ice_tests/undef.ll (right):

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
tests_lit/llvm2ice_tests/undef.ll:12: ; CHECK: return:
On 2014/06/17 15:50:11, jvoung wrote:
> Should we start using CHECK-LABEL more?
> 
> http://llvm.org/docs/CommandGuide/FileCheck.html#the-check-label-directive
> 
> It's a bit more robust.

I agree - most of the tests lack this simply because I was unaware of it.

[wala, 2014-06-17 20:00:19]

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
File tests_lit/llvm2ice_tests/undef.ll (right):

https://codereview.chromium.org/339783002/diff/1/tests_lit/llvm2ice_tests/und...
tests_lit/llvm2ice_tests/undef.ll:28: }
On 2014/06/17 15:50:11, jvoung wrote:
> Sometimes function call arguments are "undef". In that case it could use the
> uninitialized stack slot instead of the an uninitialized register... but
that's
> probably not worth avoiding going to a register first, since undef shouldn't
be
> too common.

There are a number of cases that could be optimized. For instance, when
immediate values are permitted in the instruction, the undef could be lowered to
an immediate constant rather than a register.

The code was designed to lower undefs to a register because, the current way
operand legalization is implemented in Subzero, legalizing to a register is
always permissible. Legalization to a register is also one of the simplest
approaches to legalization.

I suspect that undefs will be too rare in practice that lowering to a register
will cause a performance hit, although the way that undefs are legalized could
always be refined later.

[wala, 2014-06-17 20:38:02]

https://codereview.chromium.org/339783002/diff/1/src/IceTargetLoweringX8632.cpp
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/339783002/diff/1/src/IceTargetLoweringX8632.c...
src/IceTargetLoweringX8632.cpp:2156: // Undef values are lowered to a register.
On 2014/06/17 06:28:07, stichnot wrote:
> Maybe change "lowered to a register" to "lowered to an uninitialized register"
> just to be clear, and that also makes it more clear why a FakeDef would be
> needed.
> 
> Also, it wouldn't hurt to assert(Allowed & Legal_Reg), which I believe is true
> for all current calls to legalize() and probably will always be true, but
still.

I agree that the comment needs to be clarified that undefs will be lowered to
uninitialized registers.

assert(Allowed & Legal_Reg) is already called at the beginning of the function.

[wala, 2014-06-17 21:34:20]

After a discussion with Jim, I've changed the implementation to lower undefs to
a zero constant. This results in more predictable code generation.

I've added a getConstantZero() method to GlobalContext which definitely seems
like it could be used in other locations in the code generator code.

I've updated the tests accordingly to test that undefs are lowered to zero. I've
tried to make the tests with minimal assumptions. I'm concerned that future
optimizations might break the tests if I start testing things such as how undef
is lowered to zero in arithmetic.

[jvoung (off chromium), 2014-06-17 21:45:45]

On 2014/06/17 21:34:20, wala wrote:
> After a discussion with Jim, I've changed the implementation to lower undefs
to
> a zero constant. This results in more predictable code generation.
> 
> I've added a getConstantZero() method to GlobalContext which definitely seems
> like it could be used in other locations in the code generator code.
> 
> I've updated the tests accordingly to test that undefs are lowered to zero.
I've
> tried to make the tests with minimal assumptions. I'm concerned that future
> optimizations might break the tests if I start testing things such as how
undef
> is lowered to zero in arithmetic.


Lowering to 0 seems good to me too, thanks.

[jvoung (off chromium), 2014-06-17 21:48:53]

https://codereview.chromium.org/339783002/diff/80001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/339783002/diff/80001/src/IceOperand.h#newcode210
src/IceOperand.h:210: // ConstantUndef represents an unspecified bit pattern.
The comment says it will be an unspecified bit pattern, which is still true even
if we make it 0.

However, it might be good to clarify that backends should try to make code
generation deterministic and lower to 0.

[wala, 2014-06-18 01:17:46]

https://codereview.chromium.org/339783002/diff/80001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/339783002/diff/80001/src/IceOperand.h#newcode210
src/IceOperand.h:210: // ConstantUndef represents an unspecified bit pattern.
On 2014/06/17 21:48:53, jvoung wrote:
> The comment says it will be an unspecified bit pattern, which is still true
even
> if we make it 0.
> 
> However, it might be good to clarify that backends should try to make code
> generation deterministic and lower to 0.

Agreed; I've updated the comment.

[Jim Stichnoth, 2014-06-18 13:43:33]

lgtm

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

https://codereview.chromium.org/339783002/diff/100001/src/IceTargetLoweringX8...
src/IceTargetLoweringX8632.cpp:2156: // Lower undefs to zero. Another option is
to lower undefs to an
Please help future developers. :)  Leave the FakeDef instruction creation in the
code as a comment.

[jvoung (off chromium), 2014-06-18 15:34:14]

lgtm too

[jvoung (off chromium), 2014-06-18 15:55:57]

On 2014/06/18 15:34:14, jvoung wrote:
> lgtm too

Oh, but please update the part of CL description that talks about using
uninitialized registers. Thanks.

[wala, 2014-06-18 16:05:23]

The CQ bit was checked by wala@chromium.org

[wala, 2014-06-18 16:05:23]

The CQ bit was unchecked by wala@chromium.org

[wala, 2014-06-18 16:55:06]

Committed patchset #6 manually as rd8f4a7d (presubmit successful).