optimizer bug on ind2sub

[tanmaykm]

julia> let S = [1 2 3; 4 5 6; 7 8 9]
           println(ind2sub(size(S), 5));
           @test S[1] == 1
       end
(1,2)

This is incorrect. Surprisingly, not using @test gives the correct result:

julia> let S = [1 2 3; 4 5 6; 7 8 9]
                  println(ind2sub(size(S), 5));
              end
(2,2)

I'm on:

julia> versioninfo()
Julia Version 0.3.0-prerelease+3609
Commit 664cab5* (2014-06-10 05:18 UTC)
Platform Info:
  System: Darwin (x86_64-apple-darwin13.2.0)
  CPU: Intel(R) Core(TM)2 Duo CPU     P7550  @ 2.26GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY)
  LAPACK: libopenblas
  LIBM: libopenlibm

[mauro3]

Seems to be a problem with the let-block. Running

 begin
       S = [1 2 3; 4 5 6; 7 8 9]
       println(ind2sub(size(S), 5));
       @test S[1] == 1
end

works. Thus work around for sparse-test in above PR.

[JeffBezanson]

Reduced case:

function foo()
  S = [1 2 3; 4 5 6; 7 8 9]
  ind2sub(size(S), 5)
end

julia> foo()
(1,2)

Even worse, turning off LLVM optimizations fixes it.
The unoptimized code contains:

oksrem:                                           ; preds = %pass
  %60 = srem i64 4, %56, !dbg !789
  br label %after_srem, !dbg !789

after_srem:                                       ; preds = %oksrem, %minus1
  %61 = phi i64 [ 0, %minus1 ], [ %60, %oksrem ], !dbg !789
  %62 = add i64 %61, 1, !dbg !789

and the optimizer changes this to

oksrem:                                           ; preds = %top
  %26 = srem i64 4, %24, !dbg !1609
  %phitmp3 = or i64 %26, 1, !dbg !1609
  br label %after_srem, !dbg !1609

after_srem:                                       ; preds = %top, %oksrem
  %27 = phi i64 [ %phitmp3, %oksrem ], [ 1, %top ]

It looks like add 1 was replaced with or 1.

[Keno]

Seems to work fine on LLVM 3.5

[ViralBShah]

What do we do for the 0.3 release?

[Keno]

One of,

1. Bisect, see what fixed it and backport the fix
2. Switch to 3.5
3. Live with it
   .

[Keno]

Of course there's still the issue of distributions including vanilla 3.3

[ViralBShah]

Is it possible that a particular optimizer pass is doing it, and we can disable it?

[JeffBezanson]

Found it. Here's the llvm commit that fixed it:

diff --git a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
index 8add1ea..a7bfe09 100644
--- a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
+++ b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
@@ -754,7 +754,7 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
       ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth+1);
       // If it's known zero, our sign bit is also zero.
       if (LHSKnownZero.isNegative())
-        KnownZero |= LHSKnownZero;
+        KnownZero.setBit(KnownZero.getBitWidth() - 1);
     }
     break;
   case Instruction::URem: {

I'm inclined to include this patch.

The culprit is the InstructionCombining pass. We could remove all uses of it when not using our own llvm; the performance difference seems to be fairly small.

[ViralBShah]

Cc: @ArchRobison

[ViralBShah]

Do we just use USE_SYSTEM_LLVM setting in the Makefile to detect if we are using our patched LLVM?

[ivarne]

Will that patch actually be applied for people that just git pull && make? Wouldn't it be better to patch a LLVM header file to indicate that the patch has been applied?

[nalimilan]

I'm not going to be able to fix the system LLVM in Fedora, so if you want this to be fixed in distro packages it would be good to find a workaround in Julia until it is ported to LLVM 3.5.

[JeffBezanson]

Yes I am just using USE_SYSTEM_LLVM here.

We do have a workaround; certain optimization passes can be disabled. However the patch currently causes a mysterious test failure on travis.

[ArchRobison]

I like the suggestion of patching an LLVM header file with a #define that says the bug is fixed. There are likely to be more of these issues in the future and it's nice to have one place that lists all the bug switches.

[StefanKarpinski]

So does this require a make -C deps clean-llvm or something?

[JeffBezanson]

I find the following works with minimal rebuild time:

cd deps
patch -p0 < instcombine-llvm-3.3.patch
rm -rf ../usr/lib/libLLVM*
make install-llvm

[StefanKarpinski]

For the record, the clean-llvm thing worked too but took a while.

[timholy]

Jeff's practice of tagging new tests with their issue numbers is awesome. In this case, it helped me answer "why doesn't Julia pass its tests, and how do I fix it?" in 30s flat.

[StefanKarpinski]

That is a really effective and useful practice.

[tkelman]

@ihnorton this test is failing in the Windows binaries, can you make sure the LLVM patch gets applied next rebuild? cheers