Scheduler puts operation in dominator; creating correctness and / or performance issues

[manueljacob]

See for example this piece of Impala code:

extern fn test(very_unlikely1: bool, very_unlikely2: bool, a: int, b: int) -> int {
    let d = if very_unlikely1 {
        a / b
    } else {
        a
    };
    let e = if very_unlikely2 {
        a / b
    } else {
        a
    };
    d + e
}

It has two branches with independent conditions, but the then-blocks and the else-blocks are calculating the same values, which means that Thorin will merge the primops:

test_242(mem mem_243, bool very_unlikely1_244, bool very_unlikely2_245, qs32 a_246, qs32 b_247, fn(mem, qs32) return_248) extern 
    qs32 _256 = div a_246, b_247
    br_237(very_unlikely1_244, if_then_249, if_else_258)

    if_else_258()
        next_250(a_246)
    
    if_then_249()
        next_250(_256)
    
    next_250(qs32 d_251)
        br_237(very_unlikely2_245, if_then_252, if_else_257)
    
    if_else_257()
        next_253(a_246)
    
    if_then_252()
        next_253(_256)
    
    next_253(qs32 e_254)
        qs32 _255 = add d_251, e_254
        return_248(mem_243, _255)
    

br_237(bool br_238, fn() br_239, fn() br_240)

Here it can already be seen that the scheduler schedules the division into the block that dominates all uses (in this case, the entry block of test_242).

Here's the LLVM IR:

; ModuleID = 'independent'
source_filename = "independent"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define i32 @test(i1 %very_unlikely1_318, i1 %very_unlikely2_319, i32 %a_320, i32 %b_321) {
test_start:
  br label %test

test:                                             ; preds = %test_start
  %0 = sdiv i32 %a_320, %b_321
  br i1 %very_unlikely1_318, label %if_then, label %if_else

if_else:                                          ; preds = %test
  br label %next

if_then:                                          ; preds = %test
  br label %next

next:                                             ; preds = %if_then, %if_else
  %d = phi i32 [ %0, %if_then ], [ %a_320, %if_else ]
  br i1 %very_unlikely2_319, label %if_then2, label %if_else1

if_else1:                                         ; preds = %next
  br label %next3

if_then2:                                         ; preds = %next
  br label %next3

next3:                                            ; preds = %if_then2, %if_else1
  %e = phi i32 [ %0, %if_then2 ], [ %a_320, %if_else1 ]
  %1 = add nsw i32 %d, %e
  ret i32 %1
}

The problem is that for very_unlikely1 = false, very_unlikely2 = false, b = 0, the original code is defined, while the resulting LLVM IR exhibits undefined behavior (according to http://llvm.org/docs/LangRef.html#id106).

The correctness issue can be solved by letting the div primop consume and yield a value of the mem type. This will serialize divisions w.r.t. other side-effecting operations, which can be intended or not.

However, the problem is more general. If the division is replaced by a side-effect-free computation, the scheduler will still let it execute speculatively. If the computation is very large, this slows down the code, even if the result doesn't end up being used.

[leissa]

Thanks for reporting. This is a known problem. I'll look into that :)

[leissa]

@manueljacob Simon told me that you are interested in an internship. Feel free to contact me via email :)