Почему Джулия не оптимизирует этот код, когда C ++ (LLVM) может? - PullRequest
Новая
       6

Почему Джулия не оптимизирует этот код, когда C ++ (LLVM) может?

8 голосов
/ 28 февраля 2020

При использовании компилятора C ++ с LLVM версии 6.0.0 следующий код 

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

испускает 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 }

См .: https://godbolt.org/z/oPBFey

Это функционально эквивалентно следующей реализации: 

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>

Однако оригинальная реализация C ++, перенесенная на Julia, приводит к совсем другому IR LLVM: 

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>

Может ли кто-нибудь объяснить, почему Джулия не может создать тот же IR, что и компилятор C ++, по существу, для того же кода с почти такой же версией LLVM?

1 Ответ

2 голосов
/ 04 марта 2020

Краткий ответ: Julia и C ++ - это разные языки с разной семантикой и разными компиляторами.

Различная семантика означает, что разные оптимизации легальны. Нужно внимательно присмотреться, чтобы увидеть, был ли это законным в C ++, но незаконным в Джулии. Я был бы удивлен, если бы это было.

Различные компиляторы означают, что компиляторы делают разные вещи. Компиляторам C ++ были потрачены десятилетия и, возможно, сотни миллионов долларов времени разработчиков (даже если большая их часть была пожертвована добровольцами с открытым исходным кодом); даже более молодой компилятор, такой как Clang, все еще может опираться на десятилетия проверенных идей от более старых компиляторов, таких как G CC.

Компилятор Julia был впервые запущен в 2012 году. В него ушло гораздо меньше часов. На самом деле, я не думаю, что у него вообще был собственный оптимизатор до v0.6, который был в 2017 году. LLVM имеет , в котором есть оптимизатор, который используют и Джулия, и Кланг. Но они используют его по-разному, им разрешены разные проходы, и они предоставляют ему разную информацию (из-за разной семантики). Кроме того, вы просматриваете код до запуска LLVM. (поэтому, возможно, захотите взглянуть на сборку экземпляра). Версии LLVM одинаковы для двух, имеют значение только для того, какие инструкции существуют, а не для того, что делает LLVM, так как вы смотрите на код до того, как он запустится.

...