Warum optimiert Julia diesen Code nicht, wenn C ++ (LLVM) dies kann?

8

Bei Verwendung eines C ++ - Compilers mit LLVM Version 6.0.0 wird der folgende Code verwendet

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

sendet das LLVM IR aus 

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 }

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

Dies entspricht funktional der folgenden Implementierung:

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>

Die ursprüngliche C ++ - Implementierung, die auf Julia portiert wurde, führt jedoch zu einer ganz anderen LLVM-IR:

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>

Kann jemand erklären, warum Julia nicht in der Lage ist, dieselbe IR wie ein C ++ - Compiler für im Wesentlichen denselben Code mit fast derselben Version von LLVM zu erzeugen?

julia llvm-ir kdheepak
quelle
2
Ich denke, diskurs.julialang.org könnte ein besserer Ort sein, um diese Frage zu stellen.
28.
Es scheint also kein Problem mit dem Julia-Code zu sein. Ich habe es auf Diskurs geschrieben für Diskussion: discourse.julialang.org/t/...
kdheepak

Antworten:

2

Die kurze Antwort lautet: Julia und C ++ sind unterschiedliche Sprachen mit unterschiedlicher Semantik und unterschiedlichen Compilern.

Die unterschiedliche Semantik bedeutet, dass unterschiedliche Optimierungen bei legal sind. Es würde einige Zeit dauern, um zu sehen, ob dies in C ++ legal, in Julia jedoch illegal ist. Ich wäre überrascht, wenn es so wäre.

Die verschiedenen Compiler bedeuten, dass die Compiler verschiedene Dinge tun. In C ++ - Compilern wurden Jahrzehnte und wahrscheinlich Hunderte Millionen Dollar an Entwicklerzeit investiert (auch wenn ein Großteil davon von Open-Source-Freiwilligen gespendet wurde). Selbst ein jüngerer Compiler wie Clang kann immer noch direkt auf jahrzehntelangen bewährten Ideen älterer Compiler wie GCC aufbauen.

Der Julia-Compiler wurde erstmals im Jahr 2012 gestartet. Es sind viel weniger Stunden vergangen. Tatsächlich glaube ich nicht, dass es bis Version 0.6, das 2017 war, überhaupt einen eigenen Optimierer hatte. LLVM hat einen Optimierer, den sowohl Julia als auch Clang verwenden. Sie verwenden es jedoch unterschiedlich, haben unterschiedliche Durchgänge aktiviert und stellen unterschiedliche Informationen bereit (aufgrund unterschiedlicher Semantik). Außerdem sehen Sie sich den Code an, bevor LLVM ausgeführt wird. (Vielleicht möchten Sie sich das Assembly-Instread ansehen.) Die LLVM-Versionen, die zwischen den beiden identisch sind, sind nur für die vorhandenen Anweisungen von Bedeutung - nicht für die von LLVM vorgenommenen Optimierungen, da Sie sich den Code ansehen, bevor dieser ausgeführt wird.

Lyndon White
quelle
Danke für die Antwort! Ich hatte den Eindruck, dass die von Julia erzeugte LLVM-IR nach einem "Pass" erfolgte. Aber Sie haben Recht, es führt keine Optimierung durch und ich sollte mir wirklich den Maschinencode ansehen.
Kdheepak
Ich kann nicht ausschließen, dass bei diesem LLVM-IR 1 oder mehr Durchgänge durchgeführt wurden. Ich müsste jemanden finden, der tief in diesen Teil des Compilers eingedrungen ist, um ihn anzusehen. (und das ist einer der Teile, die ich noch nie gesehen habe. Ich denke, es wird in den Codegen-Dateien sein. Aber nicht 100% sicher.)
Lyndon White