Int128 bit shift issue

[Keno]

From #3447

int128(1)<<0

is broken.

Corresponding LLVM IR:

define i128 @julia_foo2599(i32) {
top:
  %1 = shl i32 %0, 4
  %2 = zext i32 %1 to i128
  %3 = shl i128 1, %2
  %4 = icmp ugt i32 %1, 127
  %5 = select i1 %4, i128 0, i128 %3
  ret i128 %5
}
define i32 @main() {
top:
  %0 = call i128 @julia_foo2599(i32 0)
  %1 = lshr i128 %0, 64
  %2 = trunc i128 %1 to i32
  ret i32 %2
}

LLVM bug no: http://llvm.org/bugs/show_bug.cgi?id=16439

[StefanKarpinski]

A couple of questions for someone with a 32-bit system to test on:

1. does this also happen for right shift operations?
2. is this a problem for both Int128 and Uint128? (I just pushed a work-around assuming that it is.)

[Keno]

I can get you access to my 32bit test VM, remind me about it later. To answer your questions:

1. Yes
2. Yes

[StefanKarpinski]

For some reason this diff makes type inference unhappy:

diff --git a/base/int.jl b/base/int.jl
index deed702..3f16c15 100644
--- a/base/int.jl
+++ b/base/int.jl
@@ -135,21 +135,13 @@ mod(x::Int64,  y::Int64)  = box(Int64,smod_int(unbox(Int64,x),unbox(Int64,y)))
 <<(x::Int16,  y::Int32) = box(Int16,shl_int(unbox(Int16,x),unbox(Int32,y)))
 <<(x::Int32,  y::Int32) = box(Int32,shl_int(unbox(Int32,x),unbox(Int32,y)))
 <<(x::Int64,  y::Int32) = box(Int64,shl_int(unbox(Int64,x),unbox(Int32,y)))
-if Int === Int64
 <<(x::Int128, y::Int32) = box(Int128,shl_int(unbox(Int128,x),unbox(Int32,y)))
-else
-<<(x::Int128, y::Int32) = y==0 ? x : box(Int128,shl_int(unbox(Int128,x),unbox(Int32,y)))
-end

 <<(x::Uint8,   y::Int32) = box(Uint8,shl_int(unbox(Uint8,x),unbox(Int32,y)))
 <<(x::Uint16,  y::Int32) = box(Uint16,shl_int(unbox(Uint16,x),unbox(Int32,y)))
 <<(x::Uint32,  y::Int32) = box(Uint32,shl_int(unbox(Int32,x),unbox(Uint32,y)))
 <<(x::Uint64,  y::Int32) = box(Uint64,shl_int(unbox(Uint64,x),unbox(Int32,y)))
-if Int === Int64
 <<(x::Uint128, y::Int32) = box(Uint128,shl_int(unbox(Uint128,x),unbox(Int32,y)))
-else
-<<(x::Uint128, y::Int32) = y==0 ? x : box(Uint128,shl_int(unbox(Uint128,x),unbox(Int32,y)))
-end

 >>(x::Int8,   y::Int32) = box(Int8,ashr_int(unbox(Int8,x),unbox(Int32,y)))
 >>(x::Int16,  y::Int32) = box(Int16,ashr_int(unbox(Int16,x),unbox(Int32,y)))
@@ -175,6 +167,15 @@ end
 >>>(x::Uint64,  y::Int32) = box(Uint64,lshr_int(unbox(Uint64,x),unbox(Int32,y)))
 >>>(x::Uint128, y::Int32) = box(Uint128,lshr_int(unbox(Uint128,x),unbox(Int32,y)))

+# if Int === Int32
+<<(x::Int128, y::Int32)   = y==0 ? x : box(Int128,shl_int(unbox(Int128,x),unbox(Int32,y)))
+<<(x::Uint128, y::Int32)  = y==0 ? x : box(Uint128,shl_int(unbox(Uint128,x),unbox(Int32,y)))
+>>(x::Int128, y::Int32)   = y==0 ? x : box(Int128,ashr_int(unbox(Int128,x),unbox(Int32,y)))
+>>(x::Uint128, y::Int32)  = y==0 ? x : box(Uint128,lshr_int(unbox(Uint128,x),unbox(Int32,y)))
+>>>(x::Int128, y::Int32)  = y==0 ? x : box(Int128,lshr_int(unbox(Int128,x),unbox(Int32,y)))
+>>>(x::Uint128, y::Int32) = y==0 ? x : box(Uint128,lshr_int(unbox(Uint128,x),unbox(Int32,y)))
+# end
+
 bswap(x::Int8)    = x
 bswap(x::Uint8)   = x
 bswap(x::Int16)   = box(Int16,bswap_int(unbox(Int16,x)))

Inference badness:

int.jl
ERROR: type: _basemod: in typeassert, expected CallStack, got EmptyCallStack
 in _basemod at inference.jl:74
 in isconstantfunc at inference.jl:422
 in is_known_call at inference.jl:1927
 in inlining_pass at inference.jl:1780
 in inlining_pass at inference.jl:1809
 in inlining_pass at inference.jl:1793
 in typeinf at inference.jl:1299
 in abstract_call_gf at inference.jl:564
 in abstract_call at inference.jl:642
 in abstract_eval_call at inference.jl:719
 in abstract_eval at inference.jl:752
 in abstract_interpret at inference.jl:900
 in typeinf at inference.jl:1193
 in typeinf_ext at inference.jl:1025
 in include at boot.jl:237
 in include_from_node1 at loading.jl:91
 in process_options at client.jl:251
 in _start at client.jl:321
at int.jl:451
at /Users/stefan/projects/julia/base/sysimg.jl:60

cc: @JeffBezanson

[StefanKarpinski]

The type inference problem went away after I moved this code later in the file. Chalking it up to boot-strap fragility.

[quinnj]

What's the status here? Sounds like the original issue was resolved? Are we tracking an LLVM issue that we can link to here?

[JeffBezanson]

There's a link in the OP.

[quinnj]

Ah, found it. http://llvm.org/bugs/show_bug.cgi?id=16439

[Keno]

Well, somebody knew about this at least: llvm-mirror/llvm@36236b7

[Keno]

Upstream patch is at http://reviews.llvm.org/D4978 with discussion about how best to lower the 128 bit shift. I challenge anyone to come up with a better instruction sequence :).

[Keno]

This was committed upstream.