# Missing iteration invariant optimization?

**URL:** <https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527>\
**Category:** Internals & Design\
**Tags:** llvm, optimization, loops\
**Created:** [December 5, 2017, 12:31pm UTC](https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527 "2017-12-05T12:31:05Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [December 5, 2017, 12:31pm UTC](https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527/1 "2017-12-05T12:31:05Z")

</div>

I have a feeling that iterators are harmful. Consider:

```julia
function baz1(n)
    for i=1:n
        i <1 && return 1
        i>n && return 2
    end
    0
end

function baz2(n)
    I = 1:n
    state = start(I)
    while !done(I, state)
        (i, state) = next(I, state)
        i <1 && return 1
        i>n && return 2
    end
    0
end

function baz3(n)
    i=1
    while i<n
        i <1 && return 1
        i>n && return 2
        i +=1
    end
    0
end

```

Now, baz1 and baz2 are equivalent according to docs (and tested with @code\_llvm on both 0.6 and 0.7 nightly). Let’s look at the code:

```julia
julia> @code_llvm baz1(10)

; Function baz1
; Location: REPL[7]:2
define i64 @julia_baz1_63294(i64) {
top:
  %1 = icmp sgt i64 %0, 0
  %2 = select i1 %1, i64 %0, i64 0
  %3 = add i64 %2, 1
  br label %L3

L3: ; preds = %L12, %top
  %"#temp#.0" = phi i64 [1, %top], [%6, %L12]
  %4 = icmp eq i64 %"#temp#.0", %3
  br i1 %4, label %L18, label %if

if: ; preds = %L3
; Location: REPL[7]:3
  %5 = icmp sgt i64 %"#temp#.0", 0
  br i1 %5, label %L12, label %L18

L18: ; preds = %L12, %if, %L3
  %merge = phi i64 [0, %L3], [1, %if], [2, %L12]
; Location: REPL[7]:6
  ret i64 %merge

L12: ; preds = %if
; Location: REPL[7]:2
  %6 = add nuw i64 %"#temp#.0", 1
; Location: REPL[7]:4
  %7 = icmp sgt i64 %"#temp#.0", %0
  br i1 %7, label %L18, label %L3
}

```

On the other hand,

```julia
julia> @code_llvm baz3(10)

; Function baz3
; Location: REPL[3]:2
define i64 @julia_baz3_63295(i64) {
top:
; Location: REPL[3]:3
  br i1 undef, label %L17, label %L17

L17: ; preds = %top, %top
; Location: REPL[3]:8
  ret i64 0
}

```

The relevance to bounds checks, and hence general performance, is obvious. I think something must be done to help llvm in “for i=a:b” loops, be it more annotations, a special case for iterators over unit ranges, or a new llvm pass.

Is there a way to obtain a better code\_llvm that contains all optimization metadata (all the align / noalias / etc annotations)? Is there a way to obtain code\_llvm at each pass?

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [December 5, 2017, 12:43pm UTC](https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527/2 "2017-12-05T12:43:43Z")

</div>

Big oops. baz3 is of course not equivalent to baz1 and baz2, the correct code is

```julia
julia> function baz4(n)
           i=1
           while i<=n
               i <1 && return 1
               i>n && return 2
               i +=1
           end
           0
       end

julia> @code_llvm baz4(10)

; Function baz4
; Location: REPL[16]:2
define i64 @julia_baz4_63322(i64) {
top:
; Location: REPL[16]:3
  %1 = icmp slt i64 %0, 1
  br i1 %1, label %L17, label %if.preheader

if.preheader: ; preds = %top
; Location: REPL[16]:4
  br label %if

L3: ; preds = %if
; Location: REPL[16]:6
  %2 = add nuw i64 %i.03, 1
; Location: REPL[16]:3
  %3 = icmp sgt i64 %2, %0
  br i1 %3, label %L17.loopexit, label %if

if: ; preds = %if.preheader, %L3
  %i.03 = phi i64 [%2, %L3], [1, %if.preheader]
; Location: REPL[16]:4
  %4 = icmp sgt i64 %i.03, 0
  br i1 %4, label %L3, label %L17.loopexit

L17.loopexit: ; preds = %if, %L3
  %merge.ph = phi i64 [1, %if], [0, %L3]
; Location: REPL[16]:8
  br label %L17

L17: ; preds = %L17.loopexit, %top
  %merge = phi i64 [0, %top], [%merge.ph, %L17.loopexit]
  ret i64 %merge
}

```

which manages to remove only case 2. Still, there should be a way to get these simple loop invariants figured out.

Edit: “gcc -O3” figures this out in C; “clang -O3” doesn’t (tested clang 5.0 and gcc 7.2.0).

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [December 5, 2017, 1:59pm UTC](https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527/3 "2017-12-05T13:59:38Z")

</div>

The title was rather overblown so I’ve edited it to be a bit more restrained. Since `clang` does not do this optimization it’s not too surprising that Julia doesn’t either – it’s LLVM either way. This isn’t a fundamental issue with iterators though, it’s just a missing optimization in LLVM. My guess is that since this kind of optimization is quite natural to do “by hand” (i.e. notice that the branch conditions can’t be met and delete them entirely) it hasn’t been a pressing matter for LLVM. Do you have a use case where this ends up being a problem?

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [December 5, 2017, 2:09pm UTC](https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527/4 "2017-12-05T14:09:08Z")

</div>

Re title: sorry for the bad vibes; thanks for correcting this.

```julia
using BenchmarkTools
function enumsumtest(V)
    s=0
    for i=1:length(V)
        for (j,v) = enumerate(V)
            s+=v
        end
    end
    s
end

function ib_enumsumtest(V)
    s=0
    @inbounds for i=1:length(V)
        for (j,v) in enumerate(V)
            s+=v
        end
    end
    s
end

```

```julia
V = Vector{Int}(5_000);
@btime enumsumtest(V)
  21.564 ms (1 allocation: 16 bytes)

@btime ib_enumsumtest(V)
  3.009 ms (1 allocation: 16 bytes)

```

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [December 5, 2017, 2:47pm UTC](https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527/5 "2017-12-05T14:47:26Z")

</div>

In order to optimize out the bounds-checks, there are actually three issues: First, the enumerate confuses llvm (baz1/baz2 vs baz4); second, llvm somehow fails at something (baz3 vs baz4), and third llvm fails to track the length of the vector (it thinks the length is volatile?).

Consider:

```julia
function enumsumtest_wrong_hint(V)
    s=0
    n=length(V)
    for i=1:n
        j=1
        while j<n
            j < 1 && return 1
            j > n && return 2
            @inbounds s+=V[j]
            j += 1
        end
    end
    s
end
@btime enumsumtest_wrong_hint(V)
  3.052 ms (1 allocation: 16 bytes)

```

which is tantalizingly close to what we want!

On the other hand,

```julia
function enumsumtest_wrong_nohint(V)
    s=0
    n=length(V)
    for i=1:n
        j=1
        while j<length(V)
            j < 1 && return 1
            j > length(V) && return 2
            @inbounds s+=V[j]
            j += 1
        end
    end
    s
end
@btime enumsumtest_wrong_nohint(V)
  19.277 ms (1 allocation: 16 bytes)

```

Edit: I rewrote this and opened an issue [https://github.com/JuliaLang/julia/issues/24925](https://github.com/JuliaLang/julia/issues/24925)

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [December 8, 2017, 12:46am UTC](https://discourse.julialang.org/t/missing-iteration-invariant-optimization/7527/6 "2017-12-08T00:46:28Z")

</div>

Something that should give us hope for getting rid of most boundschecks:

The following correctly vectorizes on 0.6 and emits no boundschecks (even though there is no @inbounds):

```julia
function foo_x(V::Vector{T}) where {T}
    s=zero(T)
    state = 0
    while reinterpret(UInt64,state) < reinterpret(UInt64, size(V,1))
        state += 1
        v =V[state]
        s += v
    end
    return s
end

```