Integer sign-extension miscompile

[asumagic]

While writing a script bytecode->C->MIR compiler I hit what seems to be miscompilation of code that juggles with integer sizes.

I minified the repro as small as I could:

#include <stdio.h>
#include <stdint.h>

int64_t foo(int32_t* target, int32_t* b) {
        *target = 0xAAA + *b;
        return (int64_t)*target;
}

int main()
{
        /* prevents inline somehow */
        int64_t (*alias)(int32_t* target32, int32_t* b) = foo;
        int32_t target32;
        int b = -0xBBB;
        printf("%ld\n", alias(&target32, &b)); 
}

$ c2m repro.c -O3 -el
4294967023
$ c2m repro.c -O0 -el
-273

Tested on both master and v1.0.0.

[asumagic]

Looking more carefully at the outputs, it seems that the reason why uncommenting the /* makes it work */ line is merely that that MIR better manages folding the addition into a constant, and the add is eliminated.

The broken x86 assembly reads:

00007f78a29d1270 <code>:
    7f78a29d1270:	48 8b c7             	mov    %rdi,%rax
    7f78a29d1273:	48 8b 48 08          	mov    0x8(%rax),%rcx
    7f78a29d1277:	c7 41 f4 45 f4 ff ff 	movl   $0xfffff445,-0xc(%rcx)
    7f78a29d127e:	48 63 41 f4          	movslq -0xc(%rcx),%rax
    7f78a29d1282:	81 c0 aa 0a 00 00    	add    $0xaaa,%eax
    7f78a29d1288:	89 41 f8             	mov    %eax,-0x8(%rcx)
    7f78a29d128b:	48 89 41 ec          	mov    %rax,-0x14(%rcx)
    7f78a29d128f:	c3                   	ret

So it correctly stores the constant -0xBBB to that pointer, then reloads it (needlessly, but I suppose it's aliasing shenanigans) as a 32-bit integer value, correctly sign extended to 64-bit.

The add is where it breaks: To my understanding add $0xaaa, %eax zero extend, so what happens is effectively zero-extension, i.e. %rax = (u64)(s32)(0xAAA - 0xBBB);, so of course the value of writing back %rax behind the int64 pointer is wrong.

Seems like a codegen bug? The MIR bytecode seemed fine and there didn't seem to be extra metadata on the types that I missed, at least in the debug output.
EDIT: Unless this somehow breaks two backends, both x86-64 and aarch64 Linux reproduce the issue.

Will try to check later if I can make sense of the source code as to why this happens.

[asumagic]

In the above code, the non-optimized MIR is:

	mov	t1, 2730
	mov	t2, i32:(U0_b):i
	adds	i_0, t1, t2
	mov	i32:(U0_target):i, i_0
	mov	I_1, i32:(U0_target):i
	ret	I_1
	endfunc

Because I_1 is an i64, the code is correct and the mov will perform a sign-extension from i32 to i64.

In -O1, this load with sign-extension from *target is preserved:

  8    	mov	hr0, hr6 # indexes: _,_ # dead: hr6
  7    	mov	hr1, hr7 # indexes: _,_ # dead: hr7
  2    	mov	hr6, i32:(hr0):i # indexes: _,_ # dead: hr0
  3    	adds	hr0, hr6, 2730 # indexes: _,_,_ # dead: hr6
  4    	mov	i32:(hr1):i, hr0 # indexes: _,_ # dead: hr0
  5    	mov	hr0, i32:(hr1):i # indexes: _,_ # dead: hr1
  6    	ret	hr0 # indexes: _ # dead: hr0

In -O2, this load is removed:

  11   	mov	hr0, hr6 # indexes: _,_ # dead: hr6
  10   	mov	hr1, hr7 # indexes: _,_ # dead: hr7
  2    	mov	hr0, i32:(hr0):i # m1 # indexes: _,_ # dead: hr0
  3    	adds	hr0, hr0, 2730 # indexes: _,_,_ # dead: hr0
  4    	mov	i32:(hr1):i, hr0 # m2 # indexes: _,_ # dead: hr1
  6    	ret	hr0 # indexes: _ # dead: hr0

I imagine MIR tracks the type of hr0 from the previous memory load, thus adds happens in i32 space, and the same is correct, but it rets without sign extension. Oh, adds is a 32-bit add, and doesn't stand for "add signed", which makes a lot more sense now.

Maybe some transform should be inserting an ext32 or similar?

If you bypass the write to *target and instead return the int64 directly, it does a sign extension:

	mov	t1, 2730
	mov	t2, i32:(U0_b):i
	adds	i_0, t1, t2
	ext32	I_1, i_0
	ret	I_1
	endfunc

[asumagic]

OK, some possible resolution.

To my understanding, the issue is as follows: The GVN passes uses the memory availability info to determine that *target is equivalent to the result of the sadd, and eliminates the memory reload -- this is where the issue occurs, because this is not an equivalent operation. The upper 32 bits of the register are zeroed (as the x86 instruction for 32-bit adds does) and are no longer sign-extended from the memory load.

This occurs in the /* (mem=x|x=mem); ...; r=mem => (mem=x|x=mem); t=x; ...; r=t */ optimization.

The workaround I implemented generates a signed/unsigned extension:

diff --git a/mir-gen.c b/mir-gen.c
index d04dd6a6..e4fad87e 100644
--- a/mir-gen.c
+++ b/mir-gen.c
@@ -4382,10 +4382,10 @@ static void gvn_modify (gen_ctx_t gen_ctx) {
     for (bb_insn = DLIST_HEAD (bb_insn_t, bb->bb_insns); bb_insn != NULL; bb_insn = next_bb_insn) {
       expr_t e, new_e;
       mem_expr_t prev_mem_expr, mem_expr;
-      MIR_op_t op;
-      int add_def_p, const_p, cont_p;
+      MIR_op_t op, add_ext_temp_op;
+      int add_def_p, add_ext_p, const_p, cont_p;
       MIR_type_t type;
-      MIR_insn_code_t move_code;
+      MIR_insn_code_t move_code, ext_code;
       MIR_insn_t mem_insn, new_insn, new_insn2, def_insn, after, insn = bb_insn->insn;
       ssa_edge_t se, se2;
       bb_insn_t def_bb_insn, new_bb_copy_insn;
@@ -4683,11 +4683,38 @@ static void gvn_modify (gen_ctx_t gen_ctx) {
               copy_gvn_info (bb_insn, mem_bb_insn);
               print_bb_insn_value (gen_ctx, bb_insn);
               temp_reg = mem_expr->temp_reg;
+              add_ext_p = TRUE;
+              switch (op_ref->u.mem.type) {
+                case MIR_T_I8:
+                  ext_code = MIR_EXT8;
+                  break;
+                case MIR_T_I16:
+                  ext_code = MIR_EXT16;
+                  break;
+                case MIR_T_I32:
+                  ext_code = MIR_EXT32;
+                  break;
+                case MIR_T_U8:
+                  ext_code = MIR_UEXT8;
+                  break;
+                case MIR_T_U16:
+                  ext_code = MIR_UEXT16;
+                  break;
+                case MIR_T_U32:
+                  ext_code = MIR_UEXT32;
+                  break;
+                default:
+                  add_ext_p = FALSE;
+              }
+              /* @asumagic got something wrong: wanting to emit an integer ext
+                 with something that is not an integer move?? */
+              gen_assert(insn->code == MIR_MOV || !add_ext_p);
+
               add_def_p = temp_reg == MIR_NON_VAR;
               if (add_def_p) {
                 mem_expr->temp_reg = temp_reg
                   = get_expr_temp_reg (gen_ctx, mem_expr->insn, &mem_expr->temp_reg);
-                new_insn = MIR_new_insn (ctx, insn->code, _MIR_new_var_op (ctx, temp_reg),
+                new_insn = MIR_new_insn (ctx, add_ext_p ? ext_code : insn->code, _MIR_new_var_op (ctx, temp_reg),
                                          op_ref == &mem_insn->ops[0] ? mem_insn->ops[1]
                                                                      : mem_insn->ops[0]);
                 new_insn->ops[1].data = NULL; /* remove ssa edge taken from load/store op */

Now, I'm not super familiar with compilers and MIR, so what I'm not fully sure about is:

• If this being behind the MIR_NON_VAR check is correct
• If this affects anything else in the GVN
• If this is a satisfactory resolution
• How often it is going to cause pointless sign-extension
• If this is ever required for unsigned (I feel like yes, because I think I remember reading from docs that upper bits may be undefined for 32-bit ops)
• If the problem should instead be resolved during the memory availability pass -- or even in an entirely different way if ops should instead track if the upper bits were sign-extended or not

Due to all these issues I don't feel that confident making a PR, but I'd be happy to (if hopefully MIR gets activity again).

However, make test passes and the repro is fixed, so it doesn't seem to regress anything known.