llvm/test/Transforms/LoopStrengthReduce/X86/bin_power.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; 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: define i32 @test_01(
; CHECK-SAME: i32 [[A:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nsw i32 [[LSR_IV]], -1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LSR_IV_NEXT]], -80
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[EXIT:.*]], label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[A]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[TMP1]], -1
; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 [[TMP2]], [[LSR_IV_NEXT]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;

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: define i32 @test_02(
; CHECK-SAME: i32 [[A:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nsw i32 [[LSR_IV]], -1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LSR_IV_NEXT]], -80
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[EXIT:.*]], label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[A]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP2]], [[TMP2]]
; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[TMP3]], -1
; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[TMP4]], [[LSR_IV_NEXT]]
; CHECK-NEXT:    ret i32 [[TMP5]]
;
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: define i32 @test_03(
; CHECK-SAME: i32 [[A:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nsw i32 [[LSR_IV]], -1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LSR_IV_NEXT]], -80
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[EXIT:.*]], label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[A]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 [[TMP3]], [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = mul i32 [[TMP2]], [[TMP4]]
; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[TMP4]], [[TMP4]]
; CHECK-NEXT:    [[TMP7:%.*]] = mul i32 [[TMP5]], [[TMP6]]
; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[TMP7]], -1
; CHECK-NEXT:    [[TMP9:%.*]] = sub i32 [[TMP8]], [[LSR_IV_NEXT]]
; CHECK-NEXT:    ret i32 [[TMP9]]
;
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: define i32 @test_04(
; CHECK-SAME: i32 [[A:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nsw i32 [[LSR_IV]], -1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LSR_IV_NEXT]], -80
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[EXIT:.*]], label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[A]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP2]], [[TMP2]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 [[TMP3]], [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[TMP4]], -1
; CHECK-NEXT:    [[TMP6:%.*]] = sub i32 [[TMP5]], [[LSR_IV_NEXT]]
; CHECK-NEXT:    ret i32 [[TMP6]]
;
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
}

define i32 @test_05(i32 %a) {
; CHECK-LABEL: define i32 @test_05(
; CHECK-SAME: i32 [[A:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nsw i32 [[LSR_IV]], -1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LSR_IV_NEXT]], -80
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[EXIT:.*]], label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[A]], 1
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP1]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP2]], [[TMP2]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 [[TMP3]], [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = mul i32 [[TMP4]], [[TMP4]]
; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[TMP5]], [[TMP5]]
; CHECK-NEXT:    [[TMP7:%.*]] = mul i32 [[TMP6]], [[TMP5]]
; CHECK-NEXT:    [[TMP8:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP9:%.*]] = mul i32 [[TMP8]], [[TMP8]]
; CHECK-NEXT:    [[TMP10:%.*]] = mul i32 [[TMP9]], [[TMP9]]
; CHECK-NEXT:    [[TMP11:%.*]] = mul i32 [[TMP10]], [[TMP10]]
; CHECK-NEXT:    [[TMP12:%.*]] = mul i32 [[TMP11]], [[TMP11]]
; CHECK-NEXT:    [[TMP13:%.*]] = mul i32 [[TMP7]], [[TMP12]]
; CHECK-NEXT:    [[TMP14:%.*]] = mul i32 [[TMP13]], [[TMP6]]
; CHECK-NEXT:    [[TMP15:%.*]] = mul i32 [[TMP14]], [[TMP5]]
; CHECK-NEXT:    [[TMP16:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP17:%.*]] = mul i32 [[TMP16]], [[TMP16]]
; CHECK-NEXT:    [[TMP18:%.*]] = mul i32 [[TMP17]], [[TMP17]]
; CHECK-NEXT:    [[TMP19:%.*]] = mul i32 [[TMP18]], [[TMP18]]
; CHECK-NEXT:    [[TMP20:%.*]] = mul i32 [[TMP19]], [[TMP19]]
; CHECK-NEXT:    [[TMP21:%.*]] = mul i32 [[TMP15]], [[TMP20]]
; CHECK-NEXT:    [[TMP22:%.*]] = mul i32 [[TMP21]], [[TMP13]]
; CHECK-NEXT:    [[TMP23:%.*]] = mul i32 [[TMP22]], [[TMP6]]
; CHECK-NEXT:    [[TMP24:%.*]] = mul i32 [[TMP23]], [[TMP5]]
; CHECK-NEXT:    [[TMP25:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP26:%.*]] = mul i32 [[TMP25]], [[TMP25]]
; CHECK-NEXT:    [[TMP27:%.*]] = mul i32 [[TMP26]], [[TMP26]]
; CHECK-NEXT:    [[TMP28:%.*]] = mul i32 [[TMP27]], [[TMP27]]
; CHECK-NEXT:    [[TMP29:%.*]] = mul i32 [[TMP28]], [[TMP28]]
; CHECK-NEXT:    [[TMP30:%.*]] = mul i32 [[TMP24]], [[TMP29]]
; CHECK-NEXT:    [[TMP31:%.*]] = mul i32 [[TMP30]], [[TMP21]]
; CHECK-NEXT:    [[TMP32:%.*]] = mul i32 [[TMP31]], [[TMP13]]
; CHECK-NEXT:    [[TMP33:%.*]] = mul i32 [[TMP32]], [[TMP6]]
; CHECK-NEXT:    [[TMP34:%.*]] = mul i32 [[TMP33]], [[TMP5]]
; CHECK-NEXT:    [[TMP35:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP36:%.*]] = mul i32 [[TMP35]], [[TMP35]]
; CHECK-NEXT:    [[TMP37:%.*]] = mul i32 [[TMP36]], [[TMP36]]
; CHECK-NEXT:    [[TMP38:%.*]] = mul i32 [[TMP37]], [[TMP37]]
; CHECK-NEXT:    [[TMP39:%.*]] = mul i32 [[TMP38]], [[TMP38]]
; CHECK-NEXT:    [[TMP40:%.*]] = mul i32 [[TMP34]], [[TMP39]]
; CHECK-NEXT:    [[TMP41:%.*]] = mul i32 [[TMP40]], [[TMP30]]
; CHECK-NEXT:    [[TMP42:%.*]] = mul i32 [[TMP41]], [[TMP21]]
; CHECK-NEXT:    [[TMP43:%.*]] = mul i32 [[TMP42]], [[TMP13]]
; CHECK-NEXT:    [[TMP44:%.*]] = mul i32 [[TMP43]], [[TMP6]]
; CHECK-NEXT:    [[TMP45:%.*]] = mul i32 [[TMP44]], [[TMP5]]
; CHECK-NEXT:    [[TMP46:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP47:%.*]] = mul i32 [[TMP46]], [[TMP46]]
; CHECK-NEXT:    [[TMP48:%.*]] = mul i32 [[TMP47]], [[TMP47]]
; CHECK-NEXT:    [[TMP49:%.*]] = mul i32 [[TMP48]], [[TMP48]]
; CHECK-NEXT:    [[TMP50:%.*]] = mul i32 [[TMP49]], [[TMP49]]
; CHECK-NEXT:    [[TMP51:%.*]] = mul i32 [[TMP45]], [[TMP50]]
; CHECK-NEXT:    [[TMP52:%.*]] = mul i32 [[TMP51]], [[TMP40]]
; CHECK-NEXT:    [[TMP53:%.*]] = mul i32 [[TMP52]], [[TMP30]]
; CHECK-NEXT:    [[TMP54:%.*]] = mul i32 [[TMP53]], [[TMP21]]
; CHECK-NEXT:    [[TMP55:%.*]] = mul i32 [[TMP54]], [[TMP13]]
; CHECK-NEXT:    [[TMP56:%.*]] = mul i32 [[TMP55]], [[TMP6]]
; CHECK-NEXT:    [[TMP57:%.*]] = mul i32 [[TMP56]], [[TMP5]]
; CHECK-NEXT:    [[TMP58:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP59:%.*]] = mul i32 [[TMP58]], [[TMP58]]
; CHECK-NEXT:    [[TMP60:%.*]] = mul i32 [[TMP59]], [[TMP59]]
; CHECK-NEXT:    [[TMP61:%.*]] = mul i32 [[TMP60]], [[TMP60]]
; CHECK-NEXT:    [[TMP62:%.*]] = mul i32 [[TMP61]], [[TMP61]]
; CHECK-NEXT:    [[TMP63:%.*]] = mul i32 [[TMP57]], [[TMP62]]
; CHECK-NEXT:    [[TMP64:%.*]] = mul i32 [[TMP63]], [[TMP51]]
; CHECK-NEXT:    [[TMP65:%.*]] = mul i32 [[TMP64]], [[TMP40]]
; CHECK-NEXT:    [[TMP66:%.*]] = mul i32 [[TMP65]], [[TMP30]]
; CHECK-NEXT:    [[TMP67:%.*]] = mul i32 [[TMP66]], [[TMP21]]
; CHECK-NEXT:    [[TMP68:%.*]] = mul i32 [[TMP67]], [[TMP13]]
; CHECK-NEXT:    [[TMP69:%.*]] = mul i32 [[TMP68]], [[TMP6]]
; CHECK-NEXT:    [[TMP70:%.*]] = mul i32 [[TMP69]], [[TMP5]]
; CHECK-NEXT:    [[TMP71:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP72:%.*]] = mul i32 [[TMP71]], [[TMP71]]
; CHECK-NEXT:    [[TMP73:%.*]] = mul i32 [[TMP72]], [[TMP72]]
; CHECK-NEXT:    [[TMP74:%.*]] = mul i32 [[TMP73]], [[TMP73]]
; CHECK-NEXT:    [[TMP75:%.*]] = mul i32 [[TMP74]], [[TMP74]]
; CHECK-NEXT:    [[TMP76:%.*]] = mul i32 [[TMP70]], [[TMP75]]
; CHECK-NEXT:    [[TMP77:%.*]] = mul i32 [[TMP76]], [[TMP63]]
; CHECK-NEXT:    [[TMP78:%.*]] = mul i32 [[TMP77]], [[TMP51]]
; CHECK-NEXT:    [[TMP79:%.*]] = mul i32 [[TMP78]], [[TMP40]]
; CHECK-NEXT:    [[TMP80:%.*]] = mul i32 [[TMP79]], [[TMP30]]
; CHECK-NEXT:    [[TMP81:%.*]] = mul i32 [[TMP80]], [[TMP21]]
; CHECK-NEXT:    [[TMP82:%.*]] = mul i32 [[TMP81]], [[TMP13]]
; CHECK-NEXT:    [[TMP83:%.*]] = mul i32 [[TMP82]], [[TMP6]]
; CHECK-NEXT:    [[TMP84:%.*]] = mul i32 [[TMP83]], [[TMP5]]
; CHECK-NEXT:    [[TMP85:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP86:%.*]] = mul i32 [[TMP85]], [[TMP85]]
; CHECK-NEXT:    [[TMP87:%.*]] = mul i32 [[TMP86]], [[TMP86]]
; CHECK-NEXT:    [[TMP88:%.*]] = mul i32 [[TMP87]], [[TMP87]]
; CHECK-NEXT:    [[TMP89:%.*]] = mul i32 [[TMP88]], [[TMP88]]
; CHECK-NEXT:    [[TMP90:%.*]] = mul i32 [[TMP84]], [[TMP89]]
; CHECK-NEXT:    [[TMP91:%.*]] = mul i32 [[TMP90]], [[TMP76]]
; CHECK-NEXT:    [[TMP92:%.*]] = mul i32 [[TMP91]], [[TMP63]]
; CHECK-NEXT:    [[TMP93:%.*]] = mul i32 [[TMP92]], [[TMP51]]
; CHECK-NEXT:    [[TMP94:%.*]] = mul i32 [[TMP93]], [[TMP40]]
; CHECK-NEXT:    [[TMP95:%.*]] = mul i32 [[TMP94]], [[TMP30]]
; CHECK-NEXT:    [[TMP96:%.*]] = mul i32 [[TMP95]], [[TMP21]]
; CHECK-NEXT:    [[TMP97:%.*]] = mul i32 [[TMP96]], [[TMP13]]
; CHECK-NEXT:    [[TMP98:%.*]] = mul i32 [[TMP97]], [[TMP6]]
; CHECK-NEXT:    [[TMP99:%.*]] = mul i32 [[TMP98]], [[TMP5]]
; CHECK-NEXT:    [[TMP100:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP101:%.*]] = mul i32 [[TMP100]], [[TMP100]]
; CHECK-NEXT:    [[TMP102:%.*]] = mul i32 [[TMP101]], [[TMP101]]
; CHECK-NEXT:    [[TMP103:%.*]] = mul i32 [[TMP102]], [[TMP102]]
; CHECK-NEXT:    [[TMP104:%.*]] = mul i32 [[TMP103]], [[TMP103]]
; CHECK-NEXT:    [[TMP105:%.*]] = mul i32 [[TMP99]], [[TMP104]]
; CHECK-NEXT:    [[TMP106:%.*]] = mul i32 [[TMP105]], [[TMP90]]
; CHECK-NEXT:    [[TMP107:%.*]] = mul i32 [[TMP106]], [[TMP76]]
; CHECK-NEXT:    [[TMP108:%.*]] = mul i32 [[TMP107]], [[TMP63]]
; CHECK-NEXT:    [[TMP109:%.*]] = mul i32 [[TMP108]], [[TMP51]]
; CHECK-NEXT:    [[TMP110:%.*]] = mul i32 [[TMP109]], [[TMP40]]
; CHECK-NEXT:    [[TMP111:%.*]] = mul i32 [[TMP110]], [[TMP30]]
; CHECK-NEXT:    [[TMP112:%.*]] = mul i32 [[TMP111]], [[TMP21]]
; CHECK-NEXT:    [[TMP113:%.*]] = mul i32 [[TMP112]], [[TMP13]]
; CHECK-NEXT:    [[TMP114:%.*]] = mul i32 [[TMP113]], [[TMP6]]
; CHECK-NEXT:    [[TMP115:%.*]] = mul i32 [[TMP114]], [[TMP5]]
; CHECK-NEXT:    [[TMP116:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP117:%.*]] = mul i32 [[TMP116]], [[TMP116]]
; CHECK-NEXT:    [[TMP118:%.*]] = mul i32 [[TMP117]], [[TMP117]]
; CHECK-NEXT:    [[TMP119:%.*]] = mul i32 [[TMP118]], [[TMP118]]
; CHECK-NEXT:    [[TMP120:%.*]] = mul i32 [[TMP119]], [[TMP119]]
; CHECK-NEXT:    [[TMP121:%.*]] = mul i32 [[TMP115]], [[TMP120]]
; CHECK-NEXT:    [[TMP122:%.*]] = mul i32 [[TMP121]], [[TMP105]]
; CHECK-NEXT:    [[TMP123:%.*]] = mul i32 [[TMP122]], [[TMP90]]
; CHECK-NEXT:    [[TMP124:%.*]] = mul i32 [[TMP123]], [[TMP76]]
; CHECK-NEXT:    [[TMP125:%.*]] = mul i32 [[TMP124]], [[TMP63]]
; CHECK-NEXT:    [[TMP126:%.*]] = mul i32 [[TMP125]], [[TMP51]]
; CHECK-NEXT:    [[TMP127:%.*]] = mul i32 [[TMP126]], [[TMP40]]
; CHECK-NEXT:    [[TMP128:%.*]] = mul i32 [[TMP127]], [[TMP30]]
; CHECK-NEXT:    [[TMP129:%.*]] = mul i32 [[TMP128]], [[TMP21]]
; CHECK-NEXT:    [[TMP130:%.*]] = mul i32 [[TMP129]], [[TMP13]]
; CHECK-NEXT:    [[TMP131:%.*]] = mul i32 [[TMP130]], [[TMP6]]
; CHECK-NEXT:    [[TMP132:%.*]] = mul i32 [[TMP131]], [[TMP5]]
; CHECK-NEXT:    [[TMP133:%.*]] = mul i32 [[TMP0]], [[TMP0]]
; CHECK-NEXT:    [[TMP134:%.*]] = mul i32 [[TMP133]], [[TMP133]]
; CHECK-NEXT:    [[TMP135:%.*]] = mul i32 [[TMP134]], [[TMP134]]
; CHECK-NEXT:    [[TMP136:%.*]] = mul i32 [[TMP135]], [[TMP135]]
; CHECK-NEXT:    [[TMP137:%.*]] = mul i32 [[TMP136]], [[TMP136]]
; CHECK-NEXT:    [[TMP138:%.*]] = mul i32 [[TMP132]], [[TMP137]]
; CHECK-NEXT:    [[TMP139:%.*]] = add i32 [[TMP138]], -1
; CHECK-NEXT:    [[TMP140:%.*]] = sub i32 [[TMP139]], [[LSR_IV_NEXT]]
; CHECK-NEXT:    ret i32 [[TMP140]]
;

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: define i32 @test_06(
; CHECK-SAME: i32 [[A:%.*]], i32 [[C:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], %[[LOOP]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[LSR_IV_NEXT]] = add nsw i32 [[LSR_IV]], -1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LSR_IV_NEXT]], -80
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[EXIT:.*]], label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[C]], [[C]]
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[C]], [[TMP0]]
; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[A]], 1
; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP2]], [[TMP2]]
; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 [[TMP3]], [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = mul i32 [[TMP4]], [[TMP4]]
; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 [[TMP5]], [[TMP5]]
; CHECK-NEXT:    [[TMP7:%.*]] = mul i32 [[TMP1]], [[TMP6]]
; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[TMP7]], -1
; CHECK-NEXT:    [[TMP9:%.*]] = sub i32 [[TMP8]], [[LSR_IV_NEXT]]
; CHECK-NEXT:    ret i32 [[TMP9]]
;
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
}