[Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Peter Maydell]

If you run 'make check' under clang's -fsanitize=undefined, then
(among other things) the acpi test provokes these warnings:

/home/petmay01/linaro/qemu-from-laptop/qemu/tcg/optimize.c:833:44:
runtime error: shift exponent 18446744073709551615 is too large for
64-bit type 'tcg_target_ulong' (aka 'unsigned long')
/home/petmay01/linaro/qemu-from-laptop/qemu/tcg/optimize.c:226:28:
runtime error: shift exponent 18446744073709551615 is too large for
64-bit type 'uint64_t' (aka 'unsigned long')

(18446744073709551615 is -1 as an unsigned decimal.)

This turns out to be caused by this guest code:

0x0000000007fe9a56:  xor    %ebp,%ebp
0x0000000007fe9a58:  mov    $0x1,%eax
0x0000000007fe9a5d:  mov    %ebp,%ecx
0x0000000007fe9a5f:  shl    %cl,%eax

which we turn into these TCG ops:

 ---- 0x7fe9a56
 72  discard cc_dst
 73  movi_i64 tmp0,$0x0
 74  ext32u_i64 rbp,tmp0
 75
 ---- 0x7fe9a58
 76  movi_i64 tmp0,$0x1
 77  ext32u_i64 rax,tmp0
 78
 ---- 0x7fe9a5d
 79  mov_i64 tmp0,rbp
 80  ext32u_i64 rcx,tmp0
 81
 ---- 0x7fe9a5f
 82  mov_i64 tmp1,rcx
 83  mov_i64 tmp0,rax
 84  movi_i64 tmp13,$0x1f
 85  and_i64 tmp1,tmp1,tmp13
 86  movi_i64 tmp13,$0x1
 87  sub_i64 tmp3,tmp1,tmp13
 88  shl_i64 tmp3,tmp0,tmp3
 89  shl_i64 tmp0,tmp0,tmp1
 90  ext32u_i64 rax,tmp0
 91  movi_i64 tmp13,$0x0
 92  mov_i64 cc_dst,tmp0
 93  mov_i64 cc_src,tmp3
 94  movi_i32 tmp5,$0x24
 95  movi_i32 tmp6,$0x31
 96  movi_i32 tmp11,$0x0
 97  mov_i32 tmp12,tmp1
 98  movcond_i32 cc_op,tmp12,tmp11,tmp5,tmp6,ne

In this case the constant propagation code is smart
enough to figure out that tmp1 is always zero at op 85,
and therefore tmp3 is -1 at op 87. It then tries to use
the shift constant of -1 in C when looking at op 88, and
clang complains about the C undefined behaviour.

This seems to be the result of the code in gen_shift_rm_T1(),
which (unlike gen_shift_rm_im()) doesn't special case a zero
shift count, and so will generate TCG that has undefined
behaviour if the shift count is zero.

RTH: it looks like you touched this code last, so
at this point I decided that rather than figure out
what exactly the x86 shift semantics are and what
this code was doing I'd just report it and let you
look at it :-)

thanks
-- PMM

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Richard Henderson]

On 03/18/2014 05:33 AM, Peter Maydell wrote:
>  ---- 0x7fe9a5f
>  82  mov_i64 tmp1,rcx
>  83  mov_i64 tmp0,rax
>  84  movi_i64 tmp13,$0x1f
>  85  and_i64 tmp1,tmp1,tmp13
>  86  movi_i64 tmp13,$0x1
>  87  sub_i64 tmp3,tmp1,tmp13
>  88  shl_i64 tmp3,tmp0,tmp3
>  89  shl_i64 tmp0,tmp0,tmp1
>  90  ext32u_i64 rax,tmp0
>  91  movi_i64 tmp13,$0x0
>  92  mov_i64 cc_dst,tmp0
>  93  mov_i64 cc_src,tmp3
>  94  movi_i32 tmp5,$0x24
>  95  movi_i32 tmp6,$0x31
>  96  movi_i32 tmp11,$0x0
>  97  mov_i32 tmp12,tmp1
>  98  movcond_i32 cc_op,tmp12,tmp11,tmp5,tmp6,ne
> 
> In this case the constant propagation code is smart
> enough to figure out that tmp1 is always zero at op 85,
> and therefore tmp3 is -1 at op 87. It then tries to use
> the shift constant of -1 in C when looking at op 88, and
> clang complains about the C undefined behaviour.

The tcg ops are fine here.

We've determined that cc_dst and cc_src are not live at the moment, since the
xor set cc_op to CC_OP_CLR which does not use them.  We optimistically store
into them, and then conditionally store into cc_op itself at the end.

So the shift is undefined (even by tcg's rules), but the result is unused.

So the complaint must be within tcg/optimizer.c?  We can shut up clang by
masking the shift operand while performing constant folding.


r~

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Peter Maydell]

On 18 March 2014 14:20, Richard Henderson <rth@twiddle.net> wrote:
> On 03/18/2014 05:33 AM, Peter Maydell wrote:
>> In this case the constant propagation code is smart
>> enough to figure out that tmp1 is always zero at op 85,
>> and therefore tmp3 is -1 at op 87. It then tries to use
>> the shift constant of -1 in C when looking at op 88, and
>> clang complains about the C undefined behaviour.
>
> The tcg ops are fine here.

Why do you think this? tcg/README says out of
range shifts are undefined behaviour. That means we
mustn't execute them, and this code doesn't attempt
to branch around or otherwise avoid the shift by -1.

> We've determined that cc_dst and cc_src are not live at the moment, since the
> xor set cc_op to CC_OP_CLR which does not use them.  We optimistically store
> into them, and then conditionally store into cc_op itself at the end.
>
> So the shift is undefined (even by tcg's rules), but the result is unused.

The docs say undefined behaviour, not undefined
result value... (Is there a C standard term for
the latter?)

> So the complaint must be within tcg/optimizer.c?  We can shut up clang by
> masking the shift operand while performing constant folding.

I think the optimizer is legitimately relying on
the frontend producing TCG that isn't breaking the
rules about undefined behaviour.

thanks
-- PMM

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Richard Henderson]

On 03/18/2014 07:25 AM, Peter Maydell wrote:
> Why do you think this? tcg/README says out of
> range shifts are undefined behaviour. That means we
> mustn't execute them, and this code doesn't attempt
> to branch around or otherwise avoid the shift by -1.

Bah.  Stuff and nonsense.  None of our backends are so stupid as to start WWIII
with an out of range input.

For most backends, the shift count gets (partially) masked as it is inserted
into the immediate field.  Then either the cpu considers a large shift as
producing zero (arm), or fully masks the input (everyone else).

Though indeed, Sparc considers an out of range shift immediate as an illegal
instruction, so we have an extra step in the backend for exactly this case:

    do_shift32:
        /* Limit immediate shift count lest we create an illegal insn.  */
        tcg_out_arithc(s, args[0], args[1], args[2] & 31, const_args[2], c);
        break;

> The docs say undefined behaviour, not undefined
> result value... (Is there a C standard term for
> the latter?)

The README is hardly standard-ese.  Don't read it like it's been written that way.

The term from C you're looking for is unspecified behaviour.



r~

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Peter Maydell]

On 18 March 2014 14:39, Richard Henderson <rth@twiddle.net> wrote:
> On 03/18/2014 07:25 AM, Peter Maydell wrote:
>> Why do you think this? tcg/README says out of
>> range shifts are undefined behaviour. That means we
>> mustn't execute them, and this code doesn't attempt
>> to branch around or otherwise avoid the shift by -1.
>
> Bah.  Stuff and nonsense.  None of our backends are so
> stupid as to start WWIII with an out of range input.

Then we should document that this case is an
unspecified-result, not use the same term we
do for division-by-zero or division-overflow (which
really can cause things to blow up).

> For most backends, the shift count gets (partially)
> masked as it is inserted into the immediate field.

The interesting question is not immediate shifts
but variable ones. It's trivially easy for the frontend
to avoid passing out of range immediate values
and for the backend to screen them out. This
case is a variable shift TCG op.

thanks
-- PMM

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Peter Maydell]

On 18 March 2014 14:47, Peter Maydell <peter.maydell@linaro.org> wrote:
> On 18 March 2014 14:39, Richard Henderson <rth@twiddle.net> wrote:
>> On 03/18/2014 07:25 AM, Peter Maydell wrote:
>>> Why do you think this? tcg/README says out of
>>> range shifts are undefined behaviour. That means we
>>> mustn't execute them, and this code doesn't attempt
>>> to branch around or otherwise avoid the shift by -1.
>>
>> Bah.  Stuff and nonsense.  None of our backends are so
>> stupid as to start WWIII with an out of range input.
>
> Then we should document that this case is an
> unspecified-result, not use the same term we
> do for division-by-zero or division-overflow (which
> really can cause things to blow up).

Mailing thread from last time around:
 http://lists.gnu.org/archive/html/qemu-devel/2012-09/msg02562.html

I don't particularly object to changing to "undefined
result" if you want to audit the backends and the
optimizer...

thanks
-- PMM

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Richard Henderson]

On 03/18/2014 07:47 AM, Peter Maydell wrote:
> The interesting question is not immediate shifts
> but variable ones. It's trivially easy for the frontend
> to avoid passing out of range immediate values
> and for the backend to screen them out. This
> case is a variable shift TCG op.

Exactly how are you distinguishing between constant and variable shifts?  By
how they were issued in the first place?  By how they are presented to the backend?

Otherwise I'm not following you.


r~

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Peter Maydell]

On 18 March 2014 14:56, Richard Henderson <rth@twiddle.net> wrote:
> On 03/18/2014 07:47 AM, Peter Maydell wrote:
>> The interesting question is not immediate shifts
>> but variable ones. It's trivially easy for the frontend
>> to avoid passing out of range immediate values
>> and for the backend to screen them out. This
>> case is a variable shift TCG op.
>
> Exactly how are you distinguishing between constant and
> variable shifts?  By how they were issued in the first
> place?  By how they are presented to the backend?

By whether the backend or the frontend has trivial
access to the value to be able to avoid doing bad
things if it's out of range. If either do, they can
do a translate-time check to avoid issues. If neither
does then we need the host CPU architecture to be
OK with the out of range value, or we need to insert
an explicit mask op in the backend (which is likely
to be a duplicate of an explicit mask op already
inserted at the frontend to get the frontend-target
mandated behaviour for out of range ops).

Unless all our host architectures have undefined-result
behaviour for variable shifts by out of range values
then we can't make the TCG op semantics do that.
(They probably can; the only counterexample I know
of is the 8086, where the variable-shift cycle count
was proportional to the value of the shift, so feeding
it -1 would effectively cause it to hang.)

thanks
-- PMM

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Richard Henderson]

On 03/18/2014 08:01 AM, Peter Maydell wrote:
> Unless all our host architectures have undefined-result
> behaviour for variable shifts by out of range values
> then we can't make the TCG op semantics do that.
> (They probably can; the only counterexample I know
> of is the 8086, where the variable-shift cycle count
> was proportional to the value of the shift, so feeding
> it -1 would effectively cause it to hang.)

ARM is our only host architecture that does not mask the input to the width of
the operand.  That one, of course, masks with 255 and produces zero for shifts
larger than the width of the operand.

There are several host architectures for which we do not have backends that
e.g. always mask with 63, even for the 32-bit shifts.


r~

Re: [Qemu-devel] target-i386: guest variable shift by 0 provokes shift by -1

[Paolo Bonzini]

Il 18/03/2014 16:01, Peter Maydell ha scritto:
> By whether the backend or the frontend has trivial
> access to the value to be able to avoid doing bad
> things if it's out of range. If either do, they can
> do a translate-time check to avoid issues. If neither
> does then we need the host CPU architecture to be
> OK with the out of range value, or we need to insert
> an explicit mask op in the backend (which is likely
> to be a duplicate of an explicit mask op already
> inserted at the frontend to get the frontend-target
> mandated behaviour for out of range ops).

Isn't that exactly what SPARC does?  But the optimizer should be able to 
remove a redundant AND (not sure it is able to optimize & 255 & 31 to a 
single instruction, but it certainly can remove the second AND in "& 31 
& 255").

Paolo