; RUN: opt < %s -scalar-evolution-huge-expr-threshold=1000000 -loop-reduce -S | FileCheck %s
target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
; Show that the b^2 is expanded correctly.
define i32 @test_01(i32 %a) {
; CHECK-LABEL: @test_01
; CHECK: entry:
; CHECK-NEXT: br label %loop
; CHECK: loop:
; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1
; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop
; CHECK: exit:
; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1
; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B2]], -1
; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
; CHECK-NEXT: ret i32 [[R2]]
entry:
br label %loop
loop: ; preds = %loop, %entry
%indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
%b = add i32 %a, 1
%b.pow.2 = mul i32 %b, %b
%result = add i32 %b.pow.2, %indvars.iv
%indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
%exitcond = icmp eq i32 %indvars.iv.next, 80
br i1 %exitcond, label %exit, label %loop
exit: ; preds = %loop
ret i32 %result
}
; Show that b^8 is expanded correctly.
define i32 @test_02(i32 %a) {
; CHECK-LABEL: @test_02
; CHECK: entry:
; CHECK-NEXT: br label %loop
; CHECK: loop:
; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1
; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop
; CHECK: exit:
; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1
; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B8]], -1
; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
; CHECK-NEXT: ret i32 [[R2]]
entry:
br label %loop
loop: ; preds = %loop, %entry
%indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
%b = add i32 %a, 1
%b.pow.2 = mul i32 %b, %b
%b.pow.4 = mul i32 %b.pow.2, %b.pow.2
%b.pow.8 = mul i32 %b.pow.4, %b.pow.4
%result = add i32 %b.pow.8, %indvars.iv
%indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
%exitcond = icmp eq i32 %indvars.iv.next, 80
br i1 %exitcond, label %exit, label %loop
exit: ; preds = %loop
ret i32 %result
}
; Show that b^27 (27 = 1 + 2 + 8 + 16) is expanded correctly.
define i32 @test_03(i32 %a) {
; CHECK-LABEL: @test_03
; CHECK: entry:
; CHECK-NEXT: br label %loop
; CHECK: loop:
; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1
; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop
; CHECK: exit:
; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1
; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
; CHECK-NEXT: [[B3:[^ ]+]] = mul i32 [[B]], [[B2]]
; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
; CHECK-NEXT: [[B11:[^ ]+]] = mul i32 [[B3]], [[B8]]
; CHECK-NEXT: [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]
; CHECK-NEXT: [[B27:[^ ]+]] = mul i32 [[B11]], [[B16]]
; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B27]], -1
; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
; CHECK-NEXT: ret i32 [[R2]]
entry:
br label %loop
loop: ; preds = %loop, %entry
%indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
%b = add i32 %a, 1
%b.pow.2 = mul i32 %b, %b
%b.pow.4 = mul i32 %b.pow.2, %b.pow.2
%b.pow.8 = mul i32 %b.pow.4, %b.pow.4
%b.pow.16 = mul i32 %b.pow.8, %b.pow.8
%b.pow.24 = mul i32 %b.pow.16, %b.pow.8
%b.pow.25 = mul i32 %b.pow.24, %b
%b.pow.26 = mul i32 %b.pow.25, %b
%b.pow.27 = mul i32 %b.pow.26, %b
%result = add i32 %b.pow.27, %indvars.iv
%indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
%exitcond = icmp eq i32 %indvars.iv.next, 80
br i1 %exitcond, label %exit, label %loop
exit: ; preds = %loop
ret i32 %result
}
; Show how linear calculation of b^16 is turned into logarithmic.
define i32 @test_04(i32 %a) {
; CHECK-LABEL: @test_04
; CHECK: entry:
; CHECK-NEXT: br label %loop
; CHECK: loop:
; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1
; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop
; CHECK: exit:
; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1
; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
; CHECK-NEXT: [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]
; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B16]], -1
; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]
; CHECK-NEXT: ret i32 [[R2]]
entry:
br label %loop
loop: ; preds = %loop, %entry
%indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
%b = add i32 %a, 1
%b.pow.2 = mul i32 %b, %b
%b.pow.3 = mul i32 %b.pow.2, %b
%b.pow.4 = mul i32 %b.pow.3, %b
%b.pow.5 = mul i32 %b.pow.4, %b
%b.pow.6 = mul i32 %b.pow.5, %b
%b.pow.7 = mul i32 %b.pow.6, %b
%b.pow.8 = mul i32 %b.pow.7, %b
%b.pow.9 = mul i32 %b.pow.8, %b
%b.pow.10 = mul i32 %b.pow.9, %b
%b.pow.11 = mul i32 %b.pow.10, %b
%b.pow.12 = mul i32 %b.pow.11, %b
%b.pow.13 = mul i32 %b.pow.12, %b
%b.pow.14 = mul i32 %b.pow.13, %b
%b.pow.15 = mul i32 %b.pow.14, %b
%b.pow.16 = mul i32 %b.pow.15, %b
%result = add i32 %b.pow.16, %indvars.iv
%indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
%exitcond = icmp eq i32 %indvars.iv.next, 80
br i1 %exitcond, label %exit, label %loop
exit: ; preds = %loop
ret i32 %result
}
; The output here is reasonably big, we just check that the amount of expanded
; instructions is sane.
define i32 @test_05(i32 %a) {
; CHECK-LABEL: @test_05
; CHECK: entry:
; CHECK-NEXT: br label %loop
; CHECK: loop:
; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1
; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop
; CHECK: exit:
; CHECK: %100
; CHECK-NOT: %150
entry:
br label %loop
loop: ; preds = %loop, %entry
%indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
%tmp3 = add i32 %a, 1
%tmp4 = mul i32 %tmp3, %tmp3
%tmp5 = mul i32 %tmp4, %tmp4
%tmp6 = mul i32 %tmp5, %tmp5
%tmp7 = mul i32 %tmp6, %tmp6
%tmp8 = mul i32 %tmp7, %tmp7
%tmp9 = mul i32 %tmp8, %tmp8
%tmp10 = mul i32 %tmp9, %tmp9
%tmp11 = mul i32 %tmp10, %tmp10
%tmp12 = mul i32 %tmp11, %tmp11
%tmp13 = mul i32 %tmp12, %tmp12
%tmp14 = mul i32 %tmp13, %tmp13
%tmp15 = mul i32 %tmp14, %tmp14
%tmp16 = mul i32 %tmp15, %tmp15
%tmp17 = mul i32 %tmp16, %tmp16
%tmp18 = mul i32 %tmp17, %tmp17
%tmp19 = mul i32 %tmp18, %tmp18
%tmp20 = mul i32 %tmp19, %tmp19
%tmp22 = add i32 %tmp20, %indvars.iv
%indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
%exitcond = icmp eq i32 %indvars.iv.next, 80
br i1 %exitcond, label %exit, label %loop
exit: ; preds = %loop
ret i32 %tmp22
}
; Show that the transformation works even if the calculation involves different
; values inside.
define i32 @test_06(i32 %a, i32 %c) {
; CHECK-LABEL: @test_06
; CHECK: entry:
; CHECK-NEXT: br label %loop
; CHECK: loop:
; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]
; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1
; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80
; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop
; CHECK: exit:
; CHECK: [[B:[^ ]+]] = add i32 %a, 1
; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]
; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]
; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]
; CHECK-NEXT: [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]
entry:
br label %loop
loop: ; preds = %loop, %entry
%indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]
%b = add i32 %a, 1
%b.pow.2.tmp = mul i32 %b, %b
%b.pow.2 = mul i32 %b.pow.2.tmp, %c
%b.pow.3 = mul i32 %b.pow.2, %b
%b.pow.4 = mul i32 %b.pow.3, %b
%b.pow.5 = mul i32 %b.pow.4, %b
%b.pow.6.tmp = mul i32 %b.pow.5, %b
%b.pow.6 = mul i32 %b.pow.6.tmp, %c
%b.pow.7 = mul i32 %b.pow.6, %b
%b.pow.8 = mul i32 %b.pow.7, %b
%b.pow.9 = mul i32 %b.pow.8, %b
%b.pow.10 = mul i32 %b.pow.9, %b
%b.pow.11 = mul i32 %b.pow.10, %b
%b.pow.12.tmp = mul i32 %b.pow.11, %b
%b.pow.12 = mul i32 %c, %b.pow.12.tmp
%b.pow.13 = mul i32 %b.pow.12, %b
%b.pow.14 = mul i32 %b.pow.13, %b
%b.pow.15 = mul i32 %b.pow.14, %b
%b.pow.16 = mul i32 %b.pow.15, %b
%result = add i32 %b.pow.16, %indvars.iv
%indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
%exitcond = icmp eq i32 %indvars.iv.next, 80
br i1 %exitcond, label %exit, label %loop
exit: ; preds = %loop
ret i32 %result
}