1; RUN: opt < %s -scalar-evolution-huge-expr-threshold=1000000 -loop-reduce -S | FileCheck %s 2 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_01 9; CHECK: entry: 10; CHECK-NEXT: br label %loop 11; CHECK: loop: 12; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ] 13; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1 14; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80 15; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop 16; CHECK: exit: 17; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1 18; CHECK-NEXT: [[B2:[^ ]+]] = mul i32 [[B]], [[B]] 19; CHECK-NEXT: [[R1:[^ ]+]] = add i32 [[B2]], -1 20; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]] 21; CHECK-NEXT: ret i32 [[R2]] 22 23entry: 24 br label %loop 25 26loop: ; preds = %loop, %entry 27 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ] 28 %b = add i32 %a, 1 29 %b.pow.2 = mul i32 %b, %b 30 %result = add i32 %b.pow.2, %indvars.iv 31 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1 32 %exitcond = icmp eq i32 %indvars.iv.next, 80 33 br i1 %exitcond, label %exit, label %loop 34 35exit: ; preds = %loop 36 ret i32 %result 37} 38 39; Show that b^8 is expanded correctly. 40define i32 @test_02(i32 %a) { 41; CHECK-LABEL: @test_02 42; CHECK: entry: 43; CHECK-NEXT: br label %loop 44; CHECK: loop: 45; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ] 46; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1 47; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80 48; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop 49; CHECK: exit: 50; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1 51; 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]], -1 55; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]] 56; CHECK-NEXT: ret i32 [[R2]] 57entry: 58 br label %loop 59 60loop: ; preds = %loop, %entry 61 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ] 62 %b = add i32 %a, 1 63 %b.pow.2 = mul i32 %b, %b 64 %b.pow.4 = mul i32 %b.pow.2, %b.pow.2 65 %b.pow.8 = mul i32 %b.pow.4, %b.pow.4 66 %result = add i32 %b.pow.8, %indvars.iv 67 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1 68 %exitcond = icmp eq i32 %indvars.iv.next, 80 69 br i1 %exitcond, label %exit, label %loop 70 71exit: ; preds = %loop 72 ret i32 %result 73} 74 75; Show that b^27 (27 = 1 + 2 + 8 + 16) is expanded correctly. 76define i32 @test_03(i32 %a) { 77; CHECK-LABEL: @test_03 78; CHECK: entry: 79; CHECK-NEXT: br label %loop 80; CHECK: loop: 81; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ] 82; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1 83; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80 84; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop 85; CHECK: exit: 86; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1 87; 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]], -1 95; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]] 96; CHECK-NEXT: ret i32 [[R2]] 97entry: 98 br label %loop 99 100loop: ; preds = %loop, %entry 101 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ] 102 %b = add i32 %a, 1 103 %b.pow.2 = mul i32 %b, %b 104 %b.pow.4 = mul i32 %b.pow.2, %b.pow.2 105 %b.pow.8 = mul i32 %b.pow.4, %b.pow.4 106 %b.pow.16 = mul i32 %b.pow.8, %b.pow.8 107 %b.pow.24 = mul i32 %b.pow.16, %b.pow.8 108 %b.pow.25 = mul i32 %b.pow.24, %b 109 %b.pow.26 = mul i32 %b.pow.25, %b 110 %b.pow.27 = mul i32 %b.pow.26, %b 111 %result = add i32 %b.pow.27, %indvars.iv 112 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1 113 %exitcond = icmp eq i32 %indvars.iv.next, 80 114 br i1 %exitcond, label %exit, label %loop 115 116exit: ; preds = %loop 117 ret i32 %result 118} 119 120; Show how linear calculation of b^16 is turned into logarithmic. 121define i32 @test_04(i32 %a) { 122; CHECK-LABEL: @test_04 123; CHECK: entry: 124; CHECK-NEXT: br label %loop 125; CHECK: loop: 126; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ] 127; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1 128; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80 129; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop 130; CHECK: exit: 131; CHECK-NEXT: [[B:[^ ]+]] = add i32 %a, 1 132; 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]], -1 137; CHECK-NEXT: [[R2:[^ ]+]] = sub i32 [[R1]], [[IV_INC]] 138; CHECK-NEXT: ret i32 [[R2]] 139entry: 140 br label %loop 141 142loop: ; preds = %loop, %entry 143 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ] 144 %b = add i32 %a, 1 145 %b.pow.2 = mul i32 %b, %b 146 %b.pow.3 = mul i32 %b.pow.2, %b 147 %b.pow.4 = mul i32 %b.pow.3, %b 148 %b.pow.5 = mul i32 %b.pow.4, %b 149 %b.pow.6 = mul i32 %b.pow.5, %b 150 %b.pow.7 = mul i32 %b.pow.6, %b 151 %b.pow.8 = mul i32 %b.pow.7, %b 152 %b.pow.9 = mul i32 %b.pow.8, %b 153 %b.pow.10 = mul i32 %b.pow.9, %b 154 %b.pow.11 = mul i32 %b.pow.10, %b 155 %b.pow.12 = mul i32 %b.pow.11, %b 156 %b.pow.13 = mul i32 %b.pow.12, %b 157 %b.pow.14 = mul i32 %b.pow.13, %b 158 %b.pow.15 = mul i32 %b.pow.14, %b 159 %b.pow.16 = mul i32 %b.pow.15, %b 160 %result = add i32 %b.pow.16, %indvars.iv 161 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1 162 %exitcond = icmp eq i32 %indvars.iv.next, 80 163 br i1 %exitcond, label %exit, label %loop 164 165exit: ; preds = %loop 166 ret i32 %result 167} 168 169; The output here is reasonably big, we just check that the amount of expanded 170; instructions is sane. 171define i32 @test_05(i32 %a) { 172; CHECK-LABEL: @test_05 173; CHECK: entry: 174; CHECK-NEXT: br label %loop 175; CHECK: loop: 176; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ] 177; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1 178; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80 179; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop 180; CHECK: exit: 181; CHECK: %100 182; CHECK-NOT: %150 183 184entry: 185 br label %loop 186 187loop: ; preds = %loop, %entry 188 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ] 189 %tmp3 = add i32 %a, 1 190 %tmp4 = mul i32 %tmp3, %tmp3 191 %tmp5 = mul i32 %tmp4, %tmp4 192 %tmp6 = mul i32 %tmp5, %tmp5 193 %tmp7 = mul i32 %tmp6, %tmp6 194 %tmp8 = mul i32 %tmp7, %tmp7 195 %tmp9 = mul i32 %tmp8, %tmp8 196 %tmp10 = mul i32 %tmp9, %tmp9 197 %tmp11 = mul i32 %tmp10, %tmp10 198 %tmp12 = mul i32 %tmp11, %tmp11 199 %tmp13 = mul i32 %tmp12, %tmp12 200 %tmp14 = mul i32 %tmp13, %tmp13 201 %tmp15 = mul i32 %tmp14, %tmp14 202 %tmp16 = mul i32 %tmp15, %tmp15 203 %tmp17 = mul i32 %tmp16, %tmp16 204 %tmp18 = mul i32 %tmp17, %tmp17 205 %tmp19 = mul i32 %tmp18, %tmp18 206 %tmp20 = mul i32 %tmp19, %tmp19 207 %tmp22 = add i32 %tmp20, %indvars.iv 208 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1 209 %exitcond = icmp eq i32 %indvars.iv.next, 80 210 br i1 %exitcond, label %exit, label %loop 211 212exit: ; preds = %loop 213 ret i32 %tmp22 214} 215 216; Show that the transformation works even if the calculation involves different 217; values inside. 218define i32 @test_06(i32 %a, i32 %c) { 219; CHECK-LABEL: @test_06 220; CHECK: entry: 221; CHECK-NEXT: br label %loop 222; CHECK: loop: 223; CHECK-NEXT: [[IV:[^ ]+]] = phi i32 [ [[IV_INC:[^ ]+]], %loop ], [ 0, %entry ] 224; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], -1 225; CHECK-NEXT: [[EXITCOND:[^ ]+]] = icmp eq i32 [[IV_INC]], -80 226; CHECK-NEXT: br i1 [[EXITCOND]], label %exit, label %loop 227; CHECK: exit: 228; CHECK: [[B:[^ ]+]] = add i32 %a, 1 229; 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 %loop 235 236loop: ; preds = %loop, %entry 237 %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %loop ] 238 %b = add i32 %a, 1 239 %b.pow.2.tmp = mul i32 %b, %b 240 %b.pow.2 = mul i32 %b.pow.2.tmp, %c 241 %b.pow.3 = mul i32 %b.pow.2, %b 242 %b.pow.4 = mul i32 %b.pow.3, %b 243 %b.pow.5 = mul i32 %b.pow.4, %b 244 %b.pow.6.tmp = mul i32 %b.pow.5, %b 245 %b.pow.6 = mul i32 %b.pow.6.tmp, %c 246 %b.pow.7 = mul i32 %b.pow.6, %b 247 %b.pow.8 = mul i32 %b.pow.7, %b 248 %b.pow.9 = mul i32 %b.pow.8, %b 249 %b.pow.10 = mul i32 %b.pow.9, %b 250 %b.pow.11 = mul i32 %b.pow.10, %b 251 %b.pow.12.tmp = mul i32 %b.pow.11, %b 252 %b.pow.12 = mul i32 %c, %b.pow.12.tmp 253 %b.pow.13 = mul i32 %b.pow.12, %b 254 %b.pow.14 = mul i32 %b.pow.13, %b 255 %b.pow.15 = mul i32 %b.pow.14, %b 256 %b.pow.16 = mul i32 %b.pow.15, %b 257 %result = add i32 %b.pow.16, %indvars.iv 258 %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1 259 %exitcond = icmp eq i32 %indvars.iv.next, 80 260 br i1 %exitcond, label %exit, label %loop 261 262exit: ; preds = %loop 263 ret i32 %result 264} 265