265 lines · plain
1; RUN: opt < %s -scalar-evolution-huge-expr-threshold=1000000 -loop-reduce -S | FileCheck %s2 3target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"4target triple = "x86_64-unknown-linux-gnu"5 6; Show that the b^2 is expanded correctly.7define i32 @test_01(i32 %a) {8; CHECK-LABEL: @test_019; CHECK: entry:10; CHECK-NEXT: br label %loop11; CHECK: loop:12; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]13; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -114; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -8015; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop16; CHECK: exit:17; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 118; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]19; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B2]], -120; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]21; CHECK-NEXT: ret i32 [[R2]]22 23entry:24 br label %loop25 26loop: ; preds = %loop, %entry27 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]28 %b = add i32 %a, 129 %b.pow.2 = mul i32 %b, %b30 %result = add i32 %b.pow.2, %indvars.iv31 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 132 %exitcond = icmp eq i32 %indvars.iv.next, 8033 br i1 %exitcond, label %exit, label %loop34 35exit: ; preds = %loop36 ret i32 %result37}38 39; Show that b^8 is expanded correctly.40define i32 @test_02(i32 %a) {41; CHECK-LABEL: @test_0242; CHECK: entry:43; CHECK-NEXT: br label %loop44; CHECK: loop:45; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]46; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -147; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -8048; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop49; CHECK: exit:50; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 151; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]52; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]53; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]54; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B8]], -155; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]56; CHECK-NEXT: ret i32 [[R2]]57entry:58 br label %loop59 60loop: ; preds = %loop, %entry61 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]62 %b = add i32 %a, 163 %b.pow.2 = mul i32 %b, %b64 %b.pow.4 = mul i32 %b.pow.2, %b.pow.265 %b.pow.8 = mul i32 %b.pow.4, %b.pow.466 %result = add i32 %b.pow.8, %indvars.iv67 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 168 %exitcond = icmp eq i32 %indvars.iv.next, 8069 br i1 %exitcond, label %exit, label %loop70 71exit: ; preds = %loop72 ret i32 %result73}74 75; Show that b^27 (27 = 1 + 2 + 8 + 16) is expanded correctly.76define i32 @test_03(i32 %a) {77; CHECK-LABEL: @test_0378; CHECK: entry:79; CHECK-NEXT: br label %loop80; CHECK: loop:81; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]82; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -183; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -8084; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop85; CHECK: exit:86; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 187; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]88; CHECK-NEXT: [[B3:[^ ]+]] = mul i32 [[B]], [[B2]]89; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]90; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]91; CHECK-NEXT: [[B11:[^ ]+]] = mul i32 [[B3]], [[B8]]92; CHECK-NEXT: [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]93; CHECK-NEXT: [[B27:[^ ]+]] = mul i32 [[B11]], [[B16]]94; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B27]], -195; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]96; CHECK-NEXT: ret i32 [[R2]]97entry:98 br label %loop99 100loop: ; preds = %loop, %entry101 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]102 %b = add i32 %a, 1103 %b.pow.2 = mul i32 %b, %b104 %b.pow.4 = mul i32 %b.pow.2, %b.pow.2105 %b.pow.8 = mul i32 %b.pow.4, %b.pow.4106 %b.pow.16 = mul i32 %b.pow.8, %b.pow.8107 %b.pow.24 = mul i32 %b.pow.16, %b.pow.8108 %b.pow.25 = mul i32 %b.pow.24, %b109 %b.pow.26 = mul i32 %b.pow.25, %b110 %b.pow.27 = mul i32 %b.pow.26, %b111 %result = add i32 %b.pow.27, %indvars.iv112 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1113 %exitcond = icmp eq i32 %indvars.iv.next, 80114 br i1 %exitcond, label %exit, label %loop115 116exit: ; preds = %loop117 ret i32 %result118}119 120; Show how linear calculation of b^16 is turned into logarithmic.121define i32 @test_04(i32 %a) {122; CHECK-LABEL: @test_04123; CHECK: entry:124; CHECK-NEXT: br label %loop125; CHECK: loop:126; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]127; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1128; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80129; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop130; CHECK: exit:131; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1132; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]133; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]134; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]135; CHECK-NEXT: [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]136; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B16]], -1137; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]]138; CHECK-NEXT: ret i32 [[R2]]139entry:140 br label %loop141 142loop: ; preds = %loop, %entry143 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]144 %b = add i32 %a, 1145 %b.pow.2 = mul i32 %b, %b146 %b.pow.3 = mul i32 %b.pow.2, %b147 %b.pow.4 = mul i32 %b.pow.3, %b148 %b.pow.5 = mul i32 %b.pow.4, %b149 %b.pow.6 = mul i32 %b.pow.5, %b150 %b.pow.7 = mul i32 %b.pow.6, %b151 %b.pow.8 = mul i32 %b.pow.7, %b152 %b.pow.9 = mul i32 %b.pow.8, %b153 %b.pow.10 = mul i32 %b.pow.9, %b154 %b.pow.11 = mul i32 %b.pow.10, %b155 %b.pow.12 = mul i32 %b.pow.11, %b156 %b.pow.13 = mul i32 %b.pow.12, %b157 %b.pow.14 = mul i32 %b.pow.13, %b158 %b.pow.15 = mul i32 %b.pow.14, %b159 %b.pow.16 = mul i32 %b.pow.15, %b160 %result = add i32 %b.pow.16, %indvars.iv161 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1162 %exitcond = icmp eq i32 %indvars.iv.next, 80163 br i1 %exitcond, label %exit, label %loop164 165exit: ; preds = %loop166 ret i32 %result167}168 169; The output here is reasonably big, we just check that the amount of expanded170; instructions is sane.171define i32 @test_05(i32 %a) {172; CHECK-LABEL: @test_05173; CHECK: entry:174; CHECK-NEXT: br label %loop175; CHECK: loop:176; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]177; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1178; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80179; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop180; CHECK: exit:181; CHECK: %100182; CHECK-NOT: %150183 184entry:185 br label %loop186 187loop: ; preds = %loop, %entry188 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]189 %tmp3 = add i32 %a, 1190 %tmp4 = mul i32 %tmp3, %tmp3191 %tmp5 = mul i32 %tmp4, %tmp4192 %tmp6 = mul i32 %tmp5, %tmp5193 %tmp7 = mul i32 %tmp6, %tmp6194 %tmp8 = mul i32 %tmp7, %tmp7195 %tmp9 = mul i32 %tmp8, %tmp8196 %tmp10 = mul i32 %tmp9, %tmp9197 %tmp11 = mul i32 %tmp10, %tmp10198 %tmp12 = mul i32 %tmp11, %tmp11199 %tmp13 = mul i32 %tmp12, %tmp12200 %tmp14 = mul i32 %tmp13, %tmp13201 %tmp15 = mul i32 %tmp14, %tmp14202 %tmp16 = mul i32 %tmp15, %tmp15203 %tmp17 = mul i32 %tmp16, %tmp16204 %tmp18 = mul i32 %tmp17, %tmp17205 %tmp19 = mul i32 %tmp18, %tmp18206 %tmp20 = mul i32 %tmp19, %tmp19207 %tmp22 = add i32 %tmp20, %indvars.iv208 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1209 %exitcond = icmp eq i32 %indvars.iv.next, 80210 br i1 %exitcond, label %exit, label %loop211 212exit: ; preds = %loop213 ret i32 %tmp22214}215 216; Show that the transformation works even if the calculation involves different217; values inside.218define i32 @test_06(i32 %a, i32 %c) {219; CHECK-LABEL: @test_06220; CHECK: entry:221; CHECK-NEXT: br label %loop222; CHECK: loop:223; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ]224; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1225; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80226; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop227; CHECK: exit:228; CHECK: [[B:[^ ]+]] = add i32 %a, 1229; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]]230; CHECK-NEXT: [[B4:[^ ]+]] = mul i32 [[B2]], [[B2]]231; CHECK-NEXT: [[B8:[^ ]+]] = mul i32 [[B4]], [[B4]]232; CHECK-NEXT: [[B16:[^ ]+]] = mul i32 [[B8]], [[B8]]233entry:234 br label %loop235 236loop: ; preds = %loop, %entry237 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ]238 %b = add i32 %a, 1239 %b.pow.2.tmp = mul i32 %b, %b240 %b.pow.2 = mul i32 %b.pow.2.tmp, %c241 %b.pow.3 = mul i32 %b.pow.2, %b242 %b.pow.4 = mul i32 %b.pow.3, %b243 %b.pow.5 = mul i32 %b.pow.4, %b244 %b.pow.6.tmp = mul i32 %b.pow.5, %b245 %b.pow.6 = mul i32 %b.pow.6.tmp, %c246 %b.pow.7 = mul i32 %b.pow.6, %b247 %b.pow.8 = mul i32 %b.pow.7, %b248 %b.pow.9 = mul i32 %b.pow.8, %b249 %b.pow.10 = mul i32 %b.pow.9, %b250 %b.pow.11 = mul i32 %b.pow.10, %b251 %b.pow.12.tmp = mul i32 %b.pow.11, %b252 %b.pow.12 = mul i32 %c, %b.pow.12.tmp253 %b.pow.13 = mul i32 %b.pow.12, %b254 %b.pow.14 = mul i32 %b.pow.13, %b255 %b.pow.15 = mul i32 %b.pow.14, %b256 %b.pow.16 = mul i32 %b.pow.15, %b257 %result = add i32 %b.pow.16, %indvars.iv258 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1259 %exitcond = icmp eq i32 %indvars.iv.next, 80260 br i1 %exitcond, label %exit, label %loop261 262exit: ; preds = %loop263 ret i32 %result264}265