448 lines
8.4 KiB
LLVM
448 lines
8.4 KiB
LLVM
|
; RUN: opt -S -loop-sink < %s | FileCheck %s
|
||
|
|
; RUN: opt -S -verify-memoryssa -enable-mssa-in-legacy-loop-sink -loop-sink < %s | FileCheck %s
|
||
|
|
; RUN: opt -S -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
|
||
|
|
; RUN: opt -S -verify-memoryssa -enable-mssa-in-loop-sink -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
|
||
|
|
|
||
|
|
@g = global i32 0, align 4
|
||
|
|
|
||
|
|
; b1
|
||
|
|
; / \
|
||
|
|
; b2 b6
|
||
|
|
; / \ |
|
||
|
|
; b3 b4 |
|
||
|
|
; \ / |
|
||
|
|
; b5 |
|
||
|
|
; \ /
|
||
|
|
; b7
|
||
|
|
; preheader: 1000
|
||
|
|
; b2: 15
|
||
|
|
; b3: 7
|
||
|
|
; b4: 7
|
||
|
|
; Sink load to b2
|
||
|
|
; CHECK: t1
|
||
|
|
; CHECK: .b2:
|
||
|
|
; CHECK: load i32, i32* @g
|
||
|
|
; CHECK: .b3:
|
||
|
|
; CHECK-NOT: load i32, i32* @g
|
||
|
|
define i32 @t1(i32, i32) #0 !prof !0 {
|
||
|
|
%3 = icmp eq i32 %1, 0
|
||
|
|
br i1 %3, label %.exit, label %.preheader
|
||
|
|
|
||
|
|
.preheader:
|
||
|
|
%invariant = load i32, i32* @g
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b2, label %.b6, !prof !1
|
||
|
|
|
||
|
|
.b2:
|
||
|
|
%c2 = icmp sgt i32 %iv, 1
|
||
|
|
br i1 %c2, label %.b3, label %.b4
|
||
|
|
|
||
|
|
.b3:
|
||
|
|
%t3 = sub nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b4:
|
||
|
|
%t4 = add nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b5:
|
||
|
|
%p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
|
||
|
|
%t5 = mul nsw i32 %p5, 5
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b6:
|
||
|
|
%t6 = add nsw i32 %iv, 100
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b7:
|
||
|
|
%p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
|
||
|
|
%t7 = add nuw nsw i32 %iv, 1
|
||
|
|
%c7 = icmp eq i32 %t7, %p7
|
||
|
|
br i1 %c7, label %.b1, label %.exit, !prof !3
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
; b1
|
||
|
|
; / \
|
||
|
|
; b2 b6
|
||
|
|
; / \ |
|
||
|
|
; b3 b4 |
|
||
|
|
; \ / |
|
||
|
|
; b5 |
|
||
|
|
; \ /
|
||
|
|
; b7
|
||
|
|
; preheader: 500
|
||
|
|
; b1: 16016
|
||
|
|
; b3: 8
|
||
|
|
; b6: 8
|
||
|
|
; Sink load to b3 and b6
|
||
|
|
; CHECK: t2
|
||
|
|
; CHECK: .preheader:
|
||
|
|
; CHECK-NOT: load i32, i32* @g
|
||
|
|
; CHECK: .b3:
|
||
|
|
; CHECK: load i32, i32* @g
|
||
|
|
; CHECK: .b4:
|
||
|
|
; CHECK: .b6:
|
||
|
|
; CHECK: load i32, i32* @g
|
||
|
|
; CHECK: .b7:
|
||
|
|
define i32 @t2(i32, i32) #0 !prof !0 {
|
||
|
|
%3 = icmp eq i32 %1, 0
|
||
|
|
br i1 %3, label %.exit, label %.preheader
|
||
|
|
|
||
|
|
.preheader:
|
||
|
|
%invariant = load i32, i32* @g
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b2, label %.b6, !prof !2
|
||
|
|
|
||
|
|
.b2:
|
||
|
|
%c2 = icmp sgt i32 %iv, 1
|
||
|
|
br i1 %c2, label %.b3, label %.b4, !prof !1
|
||
|
|
|
||
|
|
.b3:
|
||
|
|
%t3 = sub nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b4:
|
||
|
|
%t4 = add nsw i32 5, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b5:
|
||
|
|
%p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
|
||
|
|
%t5 = mul nsw i32 %p5, 5
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b6:
|
||
|
|
%t6 = add nsw i32 %iv, %invariant
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b7:
|
||
|
|
%p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
|
||
|
|
%t7 = add nuw nsw i32 %iv, 1
|
||
|
|
%c7 = icmp eq i32 %t7, %p7
|
||
|
|
br i1 %c7, label %.b1, label %.exit, !prof !3
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
; b1
|
||
|
|
; / \
|
||
|
|
; b2 b6
|
||
|
|
; / \ |
|
||
|
|
; b3 b4 |
|
||
|
|
; \ / |
|
||
|
|
; b5 |
|
||
|
|
; \ /
|
||
|
|
; b7
|
||
|
|
; preheader: 500
|
||
|
|
; b3: 8
|
||
|
|
; b5: 16008
|
||
|
|
; Do not sink load from preheader.
|
||
|
|
; CHECK: t3
|
||
|
|
; CHECK: .preheader:
|
||
|
|
; CHECK: load i32, i32* @g
|
||
|
|
; CHECK: .b1:
|
||
|
|
; CHECK-NOT: load i32, i32* @g
|
||
|
|
define i32 @t3(i32, i32) #0 !prof !0 {
|
||
|
|
%3 = icmp eq i32 %1, 0
|
||
|
|
br i1 %3, label %.exit, label %.preheader
|
||
|
|
|
||
|
|
.preheader:
|
||
|
|
%invariant = load i32, i32* @g
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b2, label %.b6, !prof !2
|
||
|
|
|
||
|
|
.b2:
|
||
|
|
%c2 = icmp sgt i32 %iv, 1
|
||
|
|
br i1 %c2, label %.b3, label %.b4, !prof !1
|
||
|
|
|
||
|
|
.b3:
|
||
|
|
%t3 = sub nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b4:
|
||
|
|
%t4 = add nsw i32 5, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b5:
|
||
|
|
%p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
|
||
|
|
%t5 = mul nsw i32 %p5, %invariant
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b6:
|
||
|
|
%t6 = add nsw i32 %iv, 5
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b7:
|
||
|
|
%p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
|
||
|
|
%t7 = add nuw nsw i32 %iv, 1
|
||
|
|
%c7 = icmp eq i32 %t7, %p7
|
||
|
|
br i1 %c7, label %.b1, label %.exit, !prof !3
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
; For single-BB loop with <=1 avg trip count, sink load to b1
|
||
|
|
; CHECK: t4
|
||
|
|
; CHECK: .preheader:
|
||
|
|
; CHECK-NOT: load i32, i32* @g
|
||
|
|
; CHECK: .b1:
|
||
|
|
; CHECK: load i32, i32* @g
|
||
|
|
; CHECK: .exit:
|
||
|
|
define i32 @t4(i32, i32) #0 !prof !0 {
|
||
|
|
.preheader:
|
||
|
|
%invariant = load i32, i32* @g
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t1, %.b1 ], [ 0, %.preheader ]
|
||
|
|
%t1 = add nsw i32 %invariant, %iv
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b1, label %.exit, !prof !1
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
; b1
|
||
|
|
; / \
|
||
|
|
; b2 b6
|
||
|
|
; / \ |
|
||
|
|
; b3 b4 |
|
||
|
|
; \ / |
|
||
|
|
; b5 |
|
||
|
|
; \ /
|
||
|
|
; b7
|
||
|
|
; preheader: 1000
|
||
|
|
; b2: 15
|
||
|
|
; b3: 7
|
||
|
|
; b4: 7
|
||
|
|
; There is alias store in loop, do not sink load
|
||
|
|
; CHECK: t5
|
||
|
|
; CHECK: .preheader:
|
||
|
|
; CHECK: load i32, i32* @g
|
||
|
|
; CHECK: .b1:
|
||
|
|
; CHECK-NOT: load i32, i32* @g
|
||
|
|
define i32 @t5(i32, i32*) #0 !prof !0 {
|
||
|
|
%3 = icmp eq i32 %0, 0
|
||
|
|
br i1 %3, label %.exit, label %.preheader
|
||
|
|
|
||
|
|
.preheader:
|
||
|
|
%invariant = load i32, i32* @g
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b2, label %.b6, !prof !1
|
||
|
|
|
||
|
|
.b2:
|
||
|
|
%c2 = icmp sgt i32 %iv, 1
|
||
|
|
br i1 %c2, label %.b3, label %.b4
|
||
|
|
|
||
|
|
.b3:
|
||
|
|
%t3 = sub nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b4:
|
||
|
|
%t4 = add nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b5:
|
||
|
|
%p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
|
||
|
|
%t5 = mul nsw i32 %p5, 5
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b6:
|
||
|
|
%t6 = call i32 @foo()
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b7:
|
||
|
|
%p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
|
||
|
|
%t7 = add nuw nsw i32 %iv, 1
|
||
|
|
%c7 = icmp eq i32 %t7, %p7
|
||
|
|
br i1 %c7, label %.b1, label %.exit, !prof !3
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
; b1
|
||
|
|
; / \
|
||
|
|
; b2 b6
|
||
|
|
; / \ |
|
||
|
|
; b3 b4 |
|
||
|
|
; \ / |
|
||
|
|
; b5 |
|
||
|
|
; \ /
|
||
|
|
; b7
|
||
|
|
; preheader: 1000
|
||
|
|
; b2: 15
|
||
|
|
; b3: 7
|
||
|
|
; b4: 7
|
||
|
|
; Regardless of aliasing store in loop this load from constant memory can be sunk.
|
||
|
|
; CHECK: t5_const_memory
|
||
|
|
; CHECK: .preheader:
|
||
|
|
; CHECK-NOT: load i32, i32* @g_const
|
||
|
|
; CHECK: .b2:
|
||
|
|
; CHECK: load i32, i32* @g_const
|
||
|
|
; CHECK: br i1 %c2, label %.b3, label %.b4
|
||
|
|
define i32 @t5_const_memory(i32, i32*) #0 !prof !0 {
|
||
|
|
%3 = icmp eq i32 %0, 0
|
||
|
|
br i1 %3, label %.exit, label %.preheader
|
||
|
|
|
||
|
|
.preheader:
|
||
|
|
%invariant = load i32, i32* @g_const
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t7, %.b7 ], [ 0, %.preheader ]
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b2, label %.b6, !prof !1
|
||
|
|
|
||
|
|
.b2:
|
||
|
|
%c2 = icmp sgt i32 %iv, 1
|
||
|
|
br i1 %c2, label %.b3, label %.b4
|
||
|
|
|
||
|
|
.b3:
|
||
|
|
%t3 = sub nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b4:
|
||
|
|
%t4 = add nsw i32 %invariant, %iv
|
||
|
|
br label %.b5
|
||
|
|
|
||
|
|
.b5:
|
||
|
|
%p5 = phi i32 [ %t3, %.b3 ], [ %t4, %.b4 ]
|
||
|
|
%t5 = mul nsw i32 %p5, 5
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b6:
|
||
|
|
%t6 = call i32 @foo()
|
||
|
|
br label %.b7
|
||
|
|
|
||
|
|
.b7:
|
||
|
|
%p7 = phi i32 [ %t6, %.b6 ], [ %t5, %.b5 ]
|
||
|
|
%t7 = add nuw nsw i32 %iv, 1
|
||
|
|
%c7 = icmp eq i32 %t7, %p7
|
||
|
|
br i1 %c7, label %.b1, label %.exit, !prof !3
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
; b1
|
||
|
|
; / \
|
||
|
|
; b2 b3
|
||
|
|
; \ /
|
||
|
|
; b4
|
||
|
|
; preheader: 1000
|
||
|
|
; b2: 15
|
||
|
|
; b3: 7
|
||
|
|
; Do not sink unordered atomic load to b2
|
||
|
|
; CHECK: t6
|
||
|
|
; CHECK: .preheader:
|
||
|
|
; CHECK: load atomic i32, i32* @g unordered, align 4
|
||
|
|
; CHECK: .b2:
|
||
|
|
; CHECK-NOT: load atomic i32, i32* @g unordered, align 4
|
||
|
|
define i32 @t6(i32, i32) #0 !prof !0 {
|
||
|
|
%3 = icmp eq i32 %1, 0
|
||
|
|
br i1 %3, label %.exit, label %.preheader
|
||
|
|
|
||
|
|
.preheader:
|
||
|
|
%invariant = load atomic i32, i32* @g unordered, align 4
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t3, %.b4 ], [ 0, %.preheader ]
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b2, label %.b3, !prof !1
|
||
|
|
|
||
|
|
.b2:
|
||
|
|
%t1 = add nsw i32 %invariant, %iv
|
||
|
|
br label %.b4
|
||
|
|
|
||
|
|
.b3:
|
||
|
|
%t2 = add nsw i32 %iv, 100
|
||
|
|
br label %.b4
|
||
|
|
|
||
|
|
.b4:
|
||
|
|
%p1 = phi i32 [ %t2, %.b3 ], [ %t1, %.b2 ]
|
||
|
|
%t3 = add nuw nsw i32 %iv, 1
|
||
|
|
%c2 = icmp eq i32 %t3, %p1
|
||
|
|
br i1 %c2, label %.b1, label %.exit, !prof !3
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
@g_const = constant i32 0, align 4
|
||
|
|
|
||
|
|
; b1
|
||
|
|
; / \
|
||
|
|
; b2 b3
|
||
|
|
; \ /
|
||
|
|
; b4
|
||
|
|
; preheader: 1000
|
||
|
|
; b2: 0.5
|
||
|
|
; b3: 999.5
|
||
|
|
; Sink unordered atomic load to b2. It is allowed to sink into loop unordered
|
||
|
|
; load from constant.
|
||
|
|
; CHECK: t7
|
||
|
|
; CHECK: .preheader:
|
||
|
|
; CHECK-NOT: load atomic i32, i32* @g_const unordered, align 4
|
||
|
|
; CHECK: .b2:
|
||
|
|
; CHECK: load atomic i32, i32* @g_const unordered, align 4
|
||
|
|
define i32 @t7(i32, i32) #0 !prof !0 {
|
||
|
|
%3 = icmp eq i32 %1, 0
|
||
|
|
br i1 %3, label %.exit, label %.preheader
|
||
|
|
|
||
|
|
.preheader:
|
||
|
|
%invariant = load atomic i32, i32* @g_const unordered, align 4
|
||
|
|
br label %.b1
|
||
|
|
|
||
|
|
.b1:
|
||
|
|
%iv = phi i32 [ %t3, %.b4 ], [ 0, %.preheader ]
|
||
|
|
%c1 = icmp sgt i32 %iv, %0
|
||
|
|
br i1 %c1, label %.b2, label %.b3, !prof !1
|
||
|
|
|
||
|
|
.b2:
|
||
|
|
%t1 = add nsw i32 %invariant, %iv
|
||
|
|
br label %.b4
|
||
|
|
|
||
|
|
.b3:
|
||
|
|
%t2 = add nsw i32 %iv, 100
|
||
|
|
br label %.b4
|
||
|
|
|
||
|
|
.b4:
|
||
|
|
%p1 = phi i32 [ %t2, %.b3 ], [ %t1, %.b2 ]
|
||
|
|
%t3 = add nuw nsw i32 %iv, 1
|
||
|
|
%c2 = icmp eq i32 %t3, %p1
|
||
|
|
br i1 %c2, label %.b1, label %.exit, !prof !3
|
||
|
|
|
||
|
|
.exit:
|
||
|
|
ret i32 10
|
||
|
|
}
|
||
|
|
|
||
|
|
declare i32 @foo()
|
||
|
|
|
||
|
|
!0 = !{!"function_entry_count", i64 1}
|
||
|
|
!1 = !{!"branch_weights", i32 1, i32 2000}
|
||
|
|
!2 = !{!"branch_weights", i32 2000, i32 1}
|
||
|
|
!3 = !{!"branch_weights", i32 100, i32 1}
|