diff options
Diffstat (limited to 'test/Transforms/StraightLineStrengthReduce')
4 files changed, 240 insertions, 84 deletions
diff --git a/test/Transforms/StraightLineStrengthReduce/X86/no-slsr.ll b/test/Transforms/StraightLineStrengthReduce/X86/no-slsr.ll index 94c47c7..e2201ce 100644 --- a/test/Transforms/StraightLineStrengthReduce/X86/no-slsr.ll +++ b/test/Transforms/StraightLineStrengthReduce/X86/no-slsr.ll @@ -5,8 +5,8 @@ target triple = "x86_64-unknown-linux-gnu" ; Do not perform SLSR on &input[s] and &input[s * 2] which fit into addressing ; modes of X86. -define i32 @slsr_gep(i32* %input, i64 %s) { -; CHECK-LABEL: @slsr_gep( +define i32 @no_slsr_gep(i32* %input, i64 %s) { +; CHECK-LABEL: @no_slsr_gep( ; v0 = input[0]; %p0 = getelementptr inbounds i32, i32* %input, i64 0 %v0 = load i32, i32* %p0 @@ -28,3 +28,17 @@ define i32 @slsr_gep(i32* %input, i64 %s) { ret i32 %2 } +define void @no_slsr_add(i32 %b, i32 %s) { +; CHECK-LABEL: @no_slsr_add( + %1 = add i32 %b, %s +; CHECK: add i32 %b, %s + call void @foo(i32 %1) + %s2 = mul i32 %s, 2 +; CHECK: %s2 = mul i32 %s, 2 + %2 = add i32 %b, %s2 +; CHECK: add i32 %b, %s2 + call void @foo(i32 %2) + ret void +} + +declare void @foo(i32 %a) diff --git a/test/Transforms/StraightLineStrengthReduce/slsr-add.ll b/test/Transforms/StraightLineStrengthReduce/slsr-add.ll new file mode 100644 index 0000000..4c79be0 --- /dev/null +++ b/test/Transforms/StraightLineStrengthReduce/slsr-add.ll @@ -0,0 +1,101 @@ +; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s + +target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64" + +define void @shl(i32 %b, i32 %s) { +; CHECK-LABEL: @shl( + %1 = add i32 %b, %s +; [[BASIS:%[a-zA-Z0-9]+]] = add i32 %b, %s + call void @foo(i32 %1) + %s2 = shl i32 %s, 1 + %2 = add i32 %b, %s2 +; add i32 [[BASIS]], %s + call void @foo(i32 %2) + ret void +} + +define void @stride_is_2s(i32 %b, i32 %s) { +; CHECK-LABEL: @stride_is_2s( + %s2 = shl i32 %s, 1 +; CHECK: %s2 = shl i32 %s, 1 + %1 = add i32 %b, %s2 +; CHECK: [[t1:%[a-zA-Z0-9]+]] = add i32 %b, %s2 + call void @foo(i32 %1) + %s4 = shl i32 %s, 2 + %2 = add i32 %b, %s4 +; CHECK: [[t2:%[a-zA-Z0-9]+]] = add i32 [[t1]], %s2 + call void @foo(i32 %2) + %s6 = mul i32 %s, 6 + %3 = add i32 %b, %s6 +; CHECK: add i32 [[t2]], %s2 + call void @foo(i32 %3) + ret void +} + +define void @stride_is_3s(i32 %b, i32 %s) { +; CHECK-LABEL: @stride_is_3s( + %1 = add i32 %s, %b +; CHECK: [[t1:%[a-zA-Z0-9]+]] = add i32 %s, %b + call void @foo(i32 %1) + %s4 = shl i32 %s, 2 + %2 = add i32 %s4, %b +; CHECK: [[bump:%[a-zA-Z0-9]+]] = mul i32 %s, 3 +; CHECK: [[t2:%[a-zA-Z0-9]+]] = add i32 [[t1]], [[bump]] + call void @foo(i32 %2) + %s7 = mul i32 %s, 7 + %3 = add i32 %s7, %b +; CHECK: add i32 [[t2]], [[bump]] + call void @foo(i32 %3) + ret void +} + +; foo(b + 6 * s); +; foo(b + 4 * s); +; foo(b + 2 * s); +; => +; t1 = b + 6 * s; +; foo(t1); +; s2 = 2 * s; +; t2 = t1 - s2; +; foo(t2); +; t3 = t2 - s2; +; foo(t3); +define void @stride_is_minus_2s(i32 %b, i32 %s) { +; CHECK-LABEL: @stride_is_minus_2s( + %s6 = mul i32 %s, 6 + %1 = add i32 %b, %s6 +; CHECK: [[t1:%[a-zA-Z0-9]+]] = add i32 %b, %s6 +; CHECK: call void @foo(i32 [[t1]]) + call void @foo(i32 %1) + %s4 = shl i32 %s, 2 + %2 = add i32 %b, %s4 +; CHECK: [[bump:%[a-zA-Z0-9]+]] = shl i32 %s, 1 +; CHECK: [[t2:%[a-zA-Z0-9]+]] = sub i32 [[t1]], [[bump]] + call void @foo(i32 %2) +; CHECK: call void @foo(i32 [[t2]]) + %s2 = shl i32 %s, 1 + %3 = add i32 %b, %s2 +; CHECK: [[t3:%[a-zA-Z0-9]+]] = sub i32 [[t2]], [[bump]] + call void @foo(i32 %3) +; CHECK: call void @foo(i32 [[t3]]) + ret void +} + +; t = b + (s << 3); +; foo(t); +; foo(b + s); +; +; do not rewrite b + s to t - 7 * s because the latter is more complicated. +define void @simple_enough(i32 %b, i32 %s) { +; CHECK-LABEL: @simple_enough( + %s8 = shl i32 %s, 3 + %1 = add i32 %b, %s8 + call void @foo(i32 %1) + %2 = add i32 %b, %s +; CHECK: [[t:%[a-zA-Z0-9]+]] = add i32 %b, %s{{$}} + call void @foo(i32 %2) +; CHECK: call void @foo(i32 [[t]]) + ret void +} + +declare void @foo(i32) diff --git a/test/Transforms/StraightLineStrengthReduce/slsr-gep.ll b/test/Transforms/StraightLineStrengthReduce/slsr-gep.ll index 47e6637..3944739 100644 --- a/test/Transforms/StraightLineStrengthReduce/slsr-gep.ll +++ b/test/Transforms/StraightLineStrengthReduce/slsr-gep.ll @@ -2,77 +2,108 @@ target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64" -define i32 @slsr_gep(i32* %input, i64 %s) { +; foo(input[0]); +; foo(input[s]); +; foo(input[s * 2]); +; => +; p0 = &input[0]; +; foo(*p); +; p1 = p0 + s; +; foo(*p1); +; p2 = p1 + s; +; foo(*p2); +define void @slsr_gep(i32* %input, i64 %s) { ; CHECK-LABEL: @slsr_gep( ; v0 = input[0]; %p0 = getelementptr inbounds i32, i32* %input, i64 0 %v0 = load i32, i32* %p0 + call void @foo(i32 %v0) ; v1 = input[s]; %p1 = getelementptr inbounds i32, i32* %input, i64 %s ; CHECK: %p1 = getelementptr inbounds i32, i32* %input, i64 %s %v1 = load i32, i32* %p1 + call void @foo(i32 %v1) ; v2 = input[s * 2]; - %s2 = mul nsw i64 %s, 2 + %s2 = shl nsw i64 %s, 1 %p2 = getelementptr inbounds i32, i32* %input, i64 %s2 ; CHECK: %p2 = getelementptr inbounds i32, i32* %p1, i64 %s %v2 = load i32, i32* %p2 + call void @foo(i32 %v2) - ; return v0 + v1 + v2; - %1 = add i32 %v0, %v1 - %2 = add i32 %1, %v2 - ret i32 %2 + ret void } -define i32 @slsr_gep_sext(i32* %input, i32 %s) { +; foo(input[0]); +; foo(input[(long)s]); +; foo(input[(long)(s * 2)]); +; => +; p0 = &input[0]; +; foo(*p); +; p1 = p0 + (long)s; +; foo(*p1); +; p2 = p1 + (long)s; +; foo(*p2); +define void @slsr_gep_sext(i32* %input, i32 %s) { ; CHECK-LABEL: @slsr_gep_sext( ; v0 = input[0]; %p0 = getelementptr inbounds i32, i32* %input, i64 0 %v0 = load i32, i32* %p0 + call void @foo(i32 %v0) - ; v1 = input[(long)s]; + ; v1 = input[s]; %t = sext i32 %s to i64 %p1 = getelementptr inbounds i32, i32* %input, i64 %t ; CHECK: %p1 = getelementptr inbounds i32, i32* %input, i64 %t %v1 = load i32, i32* %p1 + call void @foo(i32 %v1) - ; v2 = input[(long)(s * 2)]; - %s2 = mul nsw i32 %s, 2 + ; v2 = input[s * 2]; + %s2 = shl nsw i32 %s, 1 %t2 = sext i32 %s2 to i64 %p2 = getelementptr inbounds i32, i32* %input, i64 %t2 ; CHECK: %p2 = getelementptr inbounds i32, i32* %p1, i64 %t %v2 = load i32, i32* %p2 + call void @foo(i32 %v2) - ; return v0 + v1 + v2; - %1 = add i32 %v0, %v1 - %2 = add i32 %1, %v2 - ret i32 %2 + ret void } -define i32 @slsr_gep_2d([10 x [5 x i32]]* %input, i64 %s, i64 %t) { +; int input[10][5]; +; foo(input[s][t]); +; foo(input[s * 2][t]); +; foo(input[s * 3][t]); +; => +; p0 = &input[s][t]; +; foo(*p0); +; p1 = p0 + 5s; +; foo(*p1); +; p2 = p1 + 5s; +; foo(*p2); +define void @slsr_gep_2d([10 x [5 x i32]]* %input, i64 %s, i64 %t) { ; CHECK-LABEL: @slsr_gep_2d( ; v0 = input[s][t]; %p0 = getelementptr inbounds [10 x [5 x i32]], [10 x [5 x i32]]* %input, i64 0, i64 %s, i64 %t %v0 = load i32, i32* %p0 + call void @foo(i32 %v0) ; v1 = input[s * 2][t]; - %s2 = mul nsw i64 %s, 2 + %s2 = shl nsw i64 %s, 1 ; CHECK: [[BUMP:%[a-zA-Z0-9]+]] = mul i64 %s, 5 %p1 = getelementptr inbounds [10 x [5 x i32]], [10 x [5 x i32]]* %input, i64 0, i64 %s2, i64 %t ; CHECK: %p1 = getelementptr inbounds i32, i32* %p0, i64 [[BUMP]] %v1 = load i32, i32* %p1 + call void @foo(i32 %v1) - ; v2 = input[s * 3][t]; + ; v3 = input[s * 3][t]; %s3 = mul nsw i64 %s, 3 %p2 = getelementptr inbounds [10 x [5 x i32]], [10 x [5 x i32]]* %input, i64 0, i64 %s3, i64 %t ; CHECK: %p2 = getelementptr inbounds i32, i32* %p1, i64 [[BUMP]] %v2 = load i32, i32* %p2 + call void @foo(i32 %v2) - ; return v0 + v1 + v2; - %1 = add i32 %v0, %v1 - %2 = add i32 %1, %v2 - ret i32 %2 + ret void } %struct.S = type <{ i64, i32 }> @@ -83,27 +114,55 @@ define i32 @slsr_gep_2d([10 x [5 x i32]]* %input, i64 %s, i64 %t) { ; which may not be divisible by typeof(input[s][t].f1) = 8. Therefore, we ; rewrite the candidates using byte offset instead of index offset as in ; @slsr_gep_2d. -define i64 @slsr_gep_uglygep([10 x [5 x %struct.S]]* %input, i64 %s, i64 %t) { +define void @slsr_gep_uglygep([10 x [5 x %struct.S]]* %input, i64 %s, i64 %t) { ; CHECK-LABEL: @slsr_gep_uglygep( ; v0 = input[s][t].f1; %p0 = getelementptr inbounds [10 x [5 x %struct.S]], [10 x [5 x %struct.S]]* %input, i64 0, i64 %s, i64 %t, i32 0 %v0 = load i64, i64* %p0 + call void @bar(i64 %v0) ; v1 = input[s * 2][t].f1; - %s2 = mul nsw i64 %s, 2 + %s2 = shl nsw i64 %s, 1 ; CHECK: [[BUMP:%[a-zA-Z0-9]+]] = mul i64 %s, 60 %p1 = getelementptr inbounds [10 x [5 x %struct.S]], [10 x [5 x %struct.S]]* %input, i64 0, i64 %s2, i64 %t, i32 0 ; CHECK: getelementptr inbounds i8, i8* %{{[0-9]+}}, i64 [[BUMP]] %v1 = load i64, i64* %p1 + call void @bar(i64 %v1) ; v2 = input[s * 3][t].f1; %s3 = mul nsw i64 %s, 3 %p2 = getelementptr inbounds [10 x [5 x %struct.S]], [10 x [5 x %struct.S]]* %input, i64 0, i64 %s3, i64 %t, i32 0 ; CHECK: getelementptr inbounds i8, i8* %{{[0-9]+}}, i64 [[BUMP]] %v2 = load i64, i64* %p2 + call void @bar(i64 %v2) + + ret void +} + +define void @slsr_out_of_bounds_gep(i32* %input, i32 %s) { +; CHECK-LABEL: @slsr_out_of_bounds_gep( + ; v0 = input[0]; + %p0 = getelementptr i32, i32* %input, i64 0 + %v0 = load i32, i32* %p0 + call void @foo(i32 %v0) - ; return v0 + v1 + v2; - %1 = add i64 %v0, %v1 - %2 = add i64 %1, %v2 - ret i64 %2 + ; v1 = input[(long)s]; + %t = sext i32 %s to i64 + %p1 = getelementptr i32, i32* %input, i64 %t +; CHECK: %p1 = getelementptr i32, i32* %input, i64 %t + %v1 = load i32, i32* %p1 + call void @foo(i32 %v1) + + ; v2 = input[(long)(s * 2)]; + %s2 = shl nsw i32 %s, 1 + %t2 = sext i32 %s2 to i64 + %p2 = getelementptr i32, i32* %input, i64 %t2 +; CHECK: %p2 = getelementptr i32, i32* %p1, i64 %t + %v2 = load i32, i32* %p2 + call void @foo(i32 %v2) + + ret void } + +declare void @foo(i32) +declare void @bar(i64) diff --git a/test/Transforms/StraightLineStrengthReduce/slsr-mul.ll b/test/Transforms/StraightLineStrengthReduce/slsr-mul.ll index 0a7e472..1c7333d 100644 --- a/test/Transforms/StraightLineStrengthReduce/slsr-mul.ll +++ b/test/Transforms/StraightLineStrengthReduce/slsr-mul.ll @@ -2,37 +2,32 @@ target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64" -declare i32 @foo(i32 %a) - -define i32 @slsr1(i32 %b, i32 %s) { +define void @slsr1(i32 %b, i32 %s) { ; CHECK-LABEL: @slsr1( - ; v0 = foo(b * s); + ; foo(b * s); %mul0 = mul i32 %b, %s ; CHECK: mul i32 ; CHECK-NOT: mul i32 - %v0 = call i32 @foo(i32 %mul0) + call void @foo(i32 %mul0) - ; v1 = foo((b + 1) * s); + ; foo((b + 1) * s); %b1 = add i32 %b, 1 %mul1 = mul i32 %b1, %s - %v1 = call i32 @foo(i32 %mul1) + call void @foo(i32 %mul1) - ; v2 = foo((b + 2) * s); + ; foo((b + 2) * s); %b2 = add i32 %b, 2 %mul2 = mul i32 %b2, %s - %v2 = call i32 @foo(i32 %mul2) + call void @foo(i32 %mul2) - ; return v0 + v1 + v2; - %1 = add i32 %v0, %v1 - %2 = add i32 %1, %v2 - ret i32 %2 + ret void } -; v0 = foo(a * b) -; v1 = foo((a + 1) * b) -; v2 = foo(a * (b + 1)) -; v3 = foo((a + 1) * (b + 1)) -define i32 @slsr2(i32 %a, i32 %b) { +; foo(a * b) +; foo((a + 1) * b) +; foo(a * (b + 1)) +; foo((a + 1) * (b + 1)) +define void @slsr2(i32 %a, i32 %b) { ; CHECK-LABEL: @slsr2( %a1 = add i32 %a, 1 %b1 = add i32 %b, 1 @@ -43,63 +38,50 @@ define i32 @slsr2(i32 %a, i32 %b) { %mul2 = mul i32 %a, %b1 %mul3 = mul i32 %a1, %b1 - %v0 = call i32 @foo(i32 %mul0) - %v1 = call i32 @foo(i32 %mul1) - %v2 = call i32 @foo(i32 %mul2) - %v3 = call i32 @foo(i32 %mul3) + call void @foo(i32 %mul0) + call void @foo(i32 %mul1) + call void @foo(i32 %mul2) + call void @foo(i32 %mul3) - %1 = add i32 %v0, %v1 - %2 = add i32 %1, %v2 - %3 = add i32 %2, %v3 - ret i32 %3 + ret void } ; The bump is a multiple of the stride. ; -; v0 = foo(b * s); -; v1 = foo((b + 2) * s); -; v2 = foo((b + 4) * s); -; return v0 + v1 + v2; -; -; ==> -; +; foo(b * s); +; foo((b + 2) * s); +; foo((b + 4) * s); +; => ; mul0 = b * s; -; v0 = foo(mul0); ; bump = s * 2; ; mul1 = mul0 + bump; // GVN ensures mul1 and mul2 use the same bump. -; v1 = foo(mul1); ; mul2 = mul1 + bump; -; v2 = foo(mul2); -; return v0 + v1 + v2; -define i32 @slsr3(i32 %b, i32 %s) { +define void @slsr3(i32 %b, i32 %s) { ; CHECK-LABEL: @slsr3( %mul0 = mul i32 %b, %s ; CHECK: mul i32 - %v0 = call i32 @foo(i32 %mul0) + call void @foo(i32 %mul0) %b1 = add i32 %b, 2 %mul1 = mul i32 %b1, %s -; CHECK: [[BUMP:%[a-zA-Z0-9]+]] = mul i32 %s, 2 +; CHECK: [[BUMP:%[a-zA-Z0-9]+]] = shl i32 %s, 1 ; CHECK: %mul1 = add i32 %mul0, [[BUMP]] - %v1 = call i32 @foo(i32 %mul1) + call void @foo(i32 %mul1) %b2 = add i32 %b, 4 %mul2 = mul i32 %b2, %s ; CHECK: %mul2 = add i32 %mul1, [[BUMP]] - %v2 = call i32 @foo(i32 %mul2) + call void @foo(i32 %mul2) - %1 = add i32 %v0, %v1 - %2 = add i32 %1, %v2 - ret i32 %2 + ret void } ; Do not rewrite a candidate if its potential basis does not dominate it. -; v0 = 0; +; ; if (cond) -; v0 = foo(a * b); -; v1 = foo((a + 1) * b); -; return v0 + v1; -define i32 @not_dominate(i1 %cond, i32 %a, i32 %b) { +; foo(a * b); +; foo((a + 1) * b); +define void @not_dominate(i1 %cond, i32 %a, i32 %b) { ; CHECK-LABEL: @not_dominate( entry: %a1 = add i32 %a, 1 @@ -108,14 +90,14 @@ entry: then: %mul0 = mul i32 %a, %b ; CHECK: %mul0 = mul i32 %a, %b - %v0 = call i32 @foo(i32 %mul0) + call void @foo(i32 %mul0) br label %merge merge: - %v0.phi = phi i32 [ 0, %entry ], [ %mul0, %then ] %mul1 = mul i32 %a1, %b ; CHECK: %mul1 = mul i32 %a1, %b - %v1 = call i32 @foo(i32 %mul1) - %sum = add i32 %v0.phi, %v1 - ret i32 %sum + call void @foo(i32 %mul1) + ret void } + +declare void @foo(i32) |