¿Por qué Julia no optimiza este código cuando C ++ (LLVM) puede?

8

Cuando se utiliza un compilador de C ++ con LLVM versión 6.0.0, el siguiente código

bool isEven(int n) {
    bool ret = true;
    for (int i = 0; i < n; i ++) {
        ret = !ret;
    }
    return ret;
}

emite el LLVM IR 

define zeroext i1 @_Z6isEveni(i32) local_unnamed_addr #0 !dbg !7 {
  call void @llvm.dbg.value(metadata i32 %0, metadata !14, metadata !DIExpression()), !dbg !18
  call void @llvm.dbg.value(metadata i8 1, metadata !15, metadata !DIExpression()), !dbg !19
  call void @llvm.dbg.value(metadata i32 0, metadata !16, metadata !DIExpression()), !dbg !20
  %2 = icmp slt i32 %0, 1, !dbg !21
  %3 = and i32 %0, 1, !dbg !23
  %4 = icmp eq i32 %3, 0, !dbg !23
  %5 = or i1 %4, %2, !dbg !23
  ret i1 %5, !dbg !24
}

declare void @llvm.dbg.value(metadata, metadata, metadata) #1

attributes #0 = { nounwind readnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind readnone speculatable }

Ver: https://godbolt.org/z/oPBFey

Esto es funcionalmente equivalente a la siguiente implementación:

julia> isEven(n::Int) = rem(n, 2) != 0
isEven (generic function with 1 method)

julia> @code_llvm debuginfo=:none isEven(7)

define i8 @julia_isEven_18796(i64) {
top:
  %1 = trunc i64 %0 to i8
  %2 = and i8 %1, 1
  %3 = xor i8 %2, 1
  ret i8 %3
}

julia>

Sin embargo, la implementación original de C ++ portada a Julia da como resultado un IR LLVM muy diferente:

julia> function isEven(n::Int)
           out = true
           for i in 0:n-1
               out = !out
           end
           return out
       end
isEven (generic function with 1 method)

julia> @code_llvm debuginfo=:none isEven(7)

define i8 @julia_isEven_18793(i64) {
top:
  %1 = add i64 %0, -1
  %2 = icmp sgt i64 %1, -1
  br i1 %2, label %L8.L12_crit_edge, label %L25

L8.L12_crit_edge:                                 ; preds = %top
  %min.iters.check = icmp ult i64 %0, 128
  br i1 %min.iters.check, label %scalar.ph, label %vector.ph

vector.ph:                                        ; preds = %L8.L12_crit_edge
  %n.vec = and i64 %0, -128
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %vec.phi = phi <32 x i8> [ <i8 1, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0, i8 0>, %vector.ph ], [ %3, %vector.body ]
  %vec.phi8 = phi <32 x i8> [ zeroinitializer, %vector.ph ], [ %4, %vector.body ]
  %vec.phi9 = phi <32 x i8> [ zeroinitializer, %vector.ph ], [ %5, %vector.body ]
  %vec.phi10 = phi <32 x i8> [ zeroinitializer, %vector.ph ], [ %6, %vector.body ]
  %3 = xor <32 x i8> %vec.phi, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
  %4 = xor <32 x i8> %vec.phi8, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
  %5 = xor <32 x i8> %vec.phi9, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
  %6 = xor <32 x i8> %vec.phi10, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
  %index.next = add i64 %index, 128
  %7 = icmp eq i64 %index.next, %n.vec
  br i1 %7, label %middle.block, label %vector.body

middle.block:                                     ; preds = %vector.body
  %bin.rdx = xor <32 x i8> %vec.phi8, %vec.phi
  %bin.rdx14 = xor <32 x i8> %5, %bin.rdx
  %bin.rdx15 = xor <32 x i8> %6, %bin.rdx14
  %rdx.shuf = shufflevector <32 x i8> %bin.rdx15, <32 x i8> undef, <32 x i32> <i32 16, i32 17, i32 18, i32 19, i32 20, i32 21, i32 22, i32 23, i32 24, i32 25, i32 26, i32 27, i32 28, i32 29, i32 30, i32 31, 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>
  %bin.rdx16 = xor <32 x i8> %bin.rdx15, %rdx.shuf
  %rdx.shuf17 = shufflevector <32 x i8> %bin.rdx16, <32 x i8> undef, <32 x i32> <i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15, 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>
  %bin.rdx18 = xor <32 x i8> %bin.rdx16, %rdx.shuf17
  %rdx.shuf19 = shufflevector <32 x i8> %bin.rdx18, <32 x i8> undef, <32 x i32> <i32 4, i32 5, i32 6, i32 7, 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>
  %bin.rdx20 = xor <32 x i8> %bin.rdx18, %rdx.shuf19
  %rdx.shuf21 = shufflevector <32 x i8> %bin.rdx20, <32 x i8> undef, <32 x i32> <i32 2, i32 3, 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>
  %bin.rdx22 = xor <32 x i8> %bin.rdx20, %rdx.shuf21
  %rdx.shuf23 = shufflevector <32 x i8> %bin.rdx22, <32 x i8> undef, <32 x i32> <i32 1, 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>
  %bin.rdx24 = xor <32 x i8> %bin.rdx22, %rdx.shuf23
  %8 = extractelement <32 x i8> %bin.rdx24, i32 0
  %cmp.n = icmp eq i64 %n.vec, %0
  br i1 %cmp.n, label %L25, label %scalar.ph

scalar.ph:                                        ; preds = %middle.block, %L8.L12_crit_edge
  %bc.resume.val = phi i64 [ %n.vec, %middle.block ], [ 0, %L8.L12_crit_edge ]
  %bc.merge.rdx = phi i8 [ %8, %middle.block ], [ 1, %L8.L12_crit_edge ]
  br label %L12

L12:                                              ; preds = %L12, %scalar.ph
  %value_phi2 = phi i8 [ %bc.merge.rdx, %scalar.ph ], [ %9, %L12 ]
  %value_phi3 = phi i64 [ %bc.resume.val, %scalar.ph ], [ %11, %L12 ]
  %9 = xor i8 %value_phi2, 1
  %10 = icmp eq i64 %value_phi3, %1
  %11 = add i64 %value_phi3, 1
  br i1 %10, label %L25, label %L12

L25:                                              ; preds = %L12, %middle.block, %top
  %value_phi6 = phi i8 [ 1, %top ], [ %9, %L12 ], [ %8, %middle.block ]
  ret i8 %value_phi6
}


julia> versioninfo()
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.6.0)
  CPU: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

julia>

¿Alguien puede explicar por qué Julia no puede producir el mismo IR que un compilador de C ++ para esencialmente el mismo código con casi la misma versión de LLVM?

julia llvm-ir kdheepak
fuente
2
Creo que disrse.julialang.org podría ser un mejor lugar para hacer esta pregunta.
crstnbr
Entonces parece que no es un problema con el código de Julia. Lo
publiqué

Respuestas:

2

La respuesta corta es: Julia y C ++ son lenguaje diferente con semántica diferente y compiladores diferentes.

La semántica diferente significa que diferentes optimizaciones en legal. Se necesitaría un poco de atención para ver si era legal en C ++ pero ilegal en Julia. Me sorprendería si lo fuera.

Los diferentes compiladores significan que los compiladores hacen cosas diferentes. Los compiladores de C ++ han tenido décadas y probablemente cientos de millones de dólares de tiempo de desarrollo invertidos en ellos (incluso si una gran parte fue donada por voluntarios de código abierto); Incluso un compilador más joven como Clang todavía puede construir directamente sobre décadas de ideas comprobadas de compiladores más antiguos como GCC.

El compilador de Julia se inició por primera vez en 2012. Se han empleado muchas menos horas. De hecho no creo que en realidad tenía su propio optimizador en absoluto hasta v0.6, que era de 2017. LLVM no tienen un optimizador, que tanto Julia y Clang uso. Pero lo usan de manera diferente, tienen pases diferentes habilitados y le proporcionan información diferente (debido a la semántica diferente). Además, está mirando el código antes de que se ejecute LLVM. (por lo que es posible que desee ver el mensaje de montaje) Las versiones de LLVM que son las mismas entre los dos solo importan para qué instrucciones existen, no para qué optimizaciones hace LLVM, ya que está mirando el código antes de que se ejecute.

Lyndon White
fuente
¡Gracias por la respuesta! Tenía la impresión de que el IR LLVM que fue generado por Julia fue después de hacer un "pase". Pero tienes razón, no hace la optimización y realmente debería estar mirando el código de la máquina.
kdheepak
No puedo descartar que este LLVM IR haya tenido 1 o más pasadas sobre él. Necesitaría que alguien que haya profundizado en esa parte del compilador lo vea. (y esa es una de las partes en las que nunca lo he visto. Creo que estará en los archivos de codegen, pero no 100% seguro.)
Lyndon White