Incorrect transformation in lift_enters pass

[madmann91]

Compilation of the following code produces an incorrect result:

static stack_sentinel = 0x76543210u32;

struct Stack {
    data: [i32 * 64],
    id: i32
}

fn empty_stack() -> Stack {
    let mut stack: Stack;
    stack.id = 0;
    stack.data(0) = stack_sentinel as i32;
    stack
}

fn pop(mut stack: &Stack) -> i32 {
    let ret = stack.data(stack.id);
    stack.id--;
    ret
}

fn main() -> i32 {
    let mut stack = empty_stack();
    let mut node_id = 0;
    while (node_id as u32) < stack_sentinel {
        node_id = pop(&stack);
    }
    node_id
}

The llvm output is:

%0 = type { [64 x i32], i32 }

define i32 @main_impala() {
main_impala_start:
  br label %main_impala

main_impala:                                      ; preds = %main_impala_start
  %stack_114 = alloca %0
  %0 = getelementptr inbounds %0* %stack_114, i32 0, i32 0
  store [64 x i32] [i32 1985229328, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef], [64 x i32]* %0
  %1 = getelementptr inbounds %0* %stack_114, i32 0, i32 1
  br label %while_head

while_head:                                       ; preds = %while_body, %main_impala
  %node_id = phi i32 [ 0, %main_impala ], [ %5, %while_body ]
  %2 = icmp ult i32 %node_id, 1985229328
  br i1 %2, label %while_body, label %next

while_body:                                       ; preds = %while_head
  %3 = load i32* %1
  %4 = getelementptr inbounds [64 x i32]* %0, i64 0, i32 %3
  %5 = load i32* %4
  %6 = load i32* %1
  %7 = sub nsw i32 %6, 1
  store i32 %7, i32* %1
  br label %while_head

next:                                             ; preds = %while_head
  ret i32 %node_id
}

One can clearly see that the id member of the stack is not initialized when it should be in the main_impala function. The Thorin IR is correct up to the _liftenters pass.

Before _liftenters:

main_impala_102(mem mem_103, fn(mem, qs32) return_104) extern 
    (mem, frame) _106 = enter mem_103
    frame _108 = extract _106, qu32 1
    Stack{[64 x qs32], qs32}* stack_114 = slot _108
    mem _107 = extract _106, qu32 0
    mem _115 = store _107, stack_114, (insert (insert bottom Stack{[64 x qs32], qs32}, qu32 1, qs32 0), qu32 0, (definite_array qs32 1985229328, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32))
    qs32* _242 = lea stack_114, qu32 1
    [64 x qs32]* _250 = lea stack_114, qu32 0
    while_head_121 _115, qs32 0

    while_head_121(mem mem_123, qs32 node_id_125)
        pu32 _126 = cast node_id_125
        bool _127 = lt _126, pu32 1985229328
        fn(mem) _134 = @ _127 select while_body_128, next_131
        _134 mem_123

    while_body_128(mem mem_130)
        (mem, frame) _236 = enter mem_130
        mem _237 = extract _236, qu32 0
        (mem, Stack{[64 x qs32], qs32}) _239 = load _237, stack_114
        mem _240 = extract _239, qu32 0
        (mem, qs32) _244 = load _240, _242
        mem _245 = extract _244, qu32 0
        (mem, Stack{[64 x qs32], qs32}) _247 = load _245, stack_114
        mem _248 = extract _247, qu32 0
        qs32 _254 = extract _244, qu32 1
        (mem, [64 x qs32]) _252 = load _248, _250
        qs32* _256 = lea _250, _254
        mem _253 = extract _252, qu32 0
        (mem, qs32) _258 = load _253, _256
        mem _259 = extract _258, qu32 0
        (mem, qs32) _261 = load _259, _242
        qs32 _263 = extract _261, qu32 1
        qs32 _264 = sub _263, qs32 1
        mem _262 = extract _261, qu32 0
        qs32 ret_266 = extract _258, qu32 1
        mem _265 = store _262, _242, _264
        while_head_121 _265, ret_266

    next_131(mem mem_133)
        return_104 mem_133, node_id_125

After _liftenters:

main_impala_102(mem mem_103, fn(mem, qs32) return_104) extern 
    (mem, frame) _106 = enter mem_103
    frame _108 = extract _106, qu32 1
    Stack{[64 x qs32], qs32}* stack_114 = slot _108
    [64 x qs32]* _250 = lea stack_114, qu32 0
    mem _107 = extract _106, qu32 0
    mem _282 = store _107, _250, (definite_array qs32 1985229328, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32, bottom qs32)
    qs32* _242 = lea stack_114, qu32 1
    while_head_121 _282, qs32 0

    while_head_121(mem mem_123, qs32 node_id_125)
        pu32 _126 = cast node_id_125
        bool _127 = lt _126, pu32 1985229328
        fn(mem) _134 = @ _127 select while_body_128, next_131
        _134 mem_123

    while_body_128(mem mem_130)
        (mem, Stack{[64 x qs32], qs32}) _291 = load mem_130, stack_114
        mem _292 = extract _291, qu32 0
        (mem, qs32) _294 = load _292, _242
        mem _295 = extract _294, qu32 0
        (mem, Stack{[64 x qs32], qs32}) _297 = load _295, stack_114
        mem _298 = extract _297, qu32 0
        qs32 _302 = extract _294, qu32 1
        (mem, [64 x qs32]) _300 = load _298, _250
        qs32* _304 = lea _250, _302
        mem _301 = extract _300, qu32 0
        (mem, qs32) _306 = load _301, _304
        mem _307 = extract _306, qu32 0
        (mem, qs32) _309 = load _307, _242
        qs32 _311 = extract _309, qu32 1
        qs32 _312 = sub _311, qs32 1
        mem _310 = extract _309, qu32 0
        qs32 ret_314 = extract _306, qu32 1
        mem _313 = store _310, _242, _312
        while_head_121 _313, ret_314

    next_131(mem mem_133)
        return_104 mem_133, node_id_125

[leissa]

The code before _liftenters is already broken. The qs32* _242 = lea stack_114, qu32 1 is never initialized.

[madmann91]

So this (insert bottom Stack{[64 x qs32], qs32}, qu32 1, qs32 0) does not initialize the first field of the stack ?

[madmann91]

I mean, the stack_id member.

[leissa]

Oh crap, you are right.