1 ; RUN: opt < %s -basicaa -licm -S | FileCheck %s 2 3 declare i32 @strlen(i8*) readonly 4 5 declare void @foo() 6 7 ; Sink readonly function. 8 define i32 @test1(i8* %P) { 9 br label %Loop 10 11 Loop: ; preds = %Loop, %0 12 %A = call i32 @strlen( i8* %P ) readonly 13 br i1 false, label %Loop, label %Out 14 15 Out: ; preds = %Loop 16 ret i32 %A 17 ; CHECK-LABEL: @test1( 18 ; CHECK: Out: 19 ; CHECK-NEXT: call i32 @strlen 20 ; CHECK-NEXT: ret i32 %A 21 } 22 23 declare double @sin(double) readnone 24 25 ; Sink readnone function out of loop with unknown memory behavior. 26 define double @test2(double %X) { 27 br label %Loop 28 29 Loop: ; preds = %Loop, %0 30 call void @foo( ) 31 %A = call double @sin( double %X ) readnone 32 br i1 true, label %Loop, label %Out 33 34 Out: ; preds = %Loop 35 ret double %A 36 ; CHECK-LABEL: @test2( 37 ; CHECK: Out: 38 ; CHECK-NEXT: call double @sin 39 ; CHECK-NEXT: ret double %A 40 } 41 42 ; This testcase checks to make sure the sinker does not cause problems with 43 ; critical edges. 44 define void @test3() { 45 Entry: 46 br i1 false, label %Loop, label %Exit 47 Loop: 48 %X = add i32 0, 1 49 br i1 false, label %Loop, label %Exit 50 Exit: 51 %Y = phi i32 [ 0, %Entry ], [ %X, %Loop ] 52 ret void 53 54 ; CHECK-LABEL: @test3( 55 ; CHECK: Exit.loopexit: 56 ; CHECK-NEXT: %X.le = add i32 0, 1 57 ; CHECK-NEXT: br label %Exit 58 59 } 60 61 ; If the result of an instruction is only used outside of the loop, sink 62 ; the instruction to the exit blocks instead of executing it on every 63 ; iteration of the loop. 64 ; 65 define i32 @test4(i32 %N) { 66 Entry: 67 br label %Loop 68 Loop: ; preds = %Loop, %Entry 69 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ] 70 %tmp.6 = mul i32 %N, %N_addr.0.pn ; <i32> [#uses=1] 71 %tmp.7 = sub i32 %tmp.6, %N ; <i32> [#uses=1] 72 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1] 73 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1 ; <i1> [#uses=1] 74 br i1 %tmp.1, label %Loop, label %Out 75 Out: ; preds = %Loop 76 ret i32 %tmp.7 77 ; CHECK-LABEL: @test4( 78 ; CHECK: Out: 79 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn 80 ; CHECK-NEXT: mul i32 %N, %[[LCSSAPHI]] 81 ; CHECK-NEXT: sub i32 %tmp.6.le, %N 82 ; CHECK-NEXT: ret i32 83 } 84 85 ; To reduce register pressure, if a load is hoistable out of the loop, and the 86 ; result of the load is only used outside of the loop, sink the load instead of 87 ; hoisting it! 88 ; 89 @X = global i32 5 ; <i32*> [#uses=1] 90 91 define i32 @test5(i32 %N) { 92 Entry: 93 br label %Loop 94 Loop: ; preds = %Loop, %Entry 95 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ] 96 %tmp.6 = load i32, i32* @X ; <i32> [#uses=1] 97 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1] 98 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1 ; <i1> [#uses=1] 99 br i1 %tmp.1, label %Loop, label %Out 100 Out: ; preds = %Loop 101 ret i32 %tmp.6 102 ; CHECK-LABEL: @test5( 103 ; CHECK: Out: 104 ; CHECK-NEXT: %tmp.6.le = load i32, i32* @X 105 ; CHECK-NEXT: ret i32 %tmp.6.le 106 } 107 108 109 110 ; The loop sinker was running from the bottom of the loop to the top, causing 111 ; it to miss opportunities to sink instructions that depended on sinking other 112 ; instructions from the loop. Instead they got hoisted, which is better than 113 ; leaving them in the loop, but increases register pressure pointlessly. 114 115 %Ty = type { i32, i32 } 116 @X2 = external global %Ty 117 118 define i32 @test6() { 119 br label %Loop 120 Loop: 121 %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0 122 %sunk2 = load i32, i32* %dead 123 br i1 false, label %Loop, label %Out 124 Out: ; preds = %Loop 125 ret i32 %sunk2 126 ; CHECK-LABEL: @test6( 127 ; CHECK: Out: 128 ; CHECK-NEXT: %dead.le = getelementptr %Ty, %Ty* @X2, i64 0, i32 0 129 ; CHECK-NEXT: %sunk2.le = load i32, i32* %dead.le 130 ; CHECK-NEXT: ret i32 %sunk2.le 131 } 132 133 134 135 ; This testcase ensures that we can sink instructions from loops with 136 ; multiple exits. 137 ; 138 define i32 @test7(i32 %N, i1 %C) { 139 Entry: 140 br label %Loop 141 Loop: ; preds = %ContLoop, %Entry 142 %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ] 143 %tmp.6 = mul i32 %N, %N_addr.0.pn 144 %tmp.7 = sub i32 %tmp.6, %N ; <i32> [#uses=2] 145 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1] 146 br i1 %C, label %ContLoop, label %Out1 147 ContLoop: 148 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1 149 br i1 %tmp.1, label %Loop, label %Out2 150 Out1: ; preds = %Loop 151 ret i32 %tmp.7 152 Out2: ; preds = %ContLoop 153 ret i32 %tmp.7 154 ; CHECK-LABEL: @test7( 155 ; CHECK: Out1: 156 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn 157 ; CHECK-NEXT: mul i32 %N, %[[LCSSAPHI]] 158 ; CHECK-NEXT: sub i32 %tmp.6.le, %N 159 ; CHECK-NEXT: ret 160 ; CHECK: Out2: 161 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn 162 ; CHECK-NEXT: mul i32 %N, %[[LCSSAPHI]] 163 ; CHECK-NEXT: sub i32 %tmp.6.le4, %N 164 ; CHECK-NEXT: ret 165 } 166 167 168 ; This testcase checks to make sure we can sink values which are only live on 169 ; some exits out of the loop, and that we can do so without breaking dominator 170 ; info. 171 define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) { 172 Entry: 173 br label %Loop 174 Loop: ; preds = %Cont, %Entry 175 br i1 %C1, label %Cont, label %exit1 176 Cont: ; preds = %Loop 177 %X = load i32, i32* %P ; <i32> [#uses=2] 178 store i32 %X, i32* %Q 179 %V = add i32 %X, 1 ; <i32> [#uses=1] 180 br i1 %C2, label %Loop, label %exit2 181 exit1: ; preds = %Loop 182 ret i32 0 183 exit2: ; preds = %Cont 184 ret i32 %V 185 ; CHECK-LABEL: @test8( 186 ; CHECK: exit1: 187 ; CHECK-NEXT: ret i32 0 188 ; CHECK: exit2: 189 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %X 190 ; CHECK-NEXT: %V.le = add i32 %[[LCSSAPHI]], 1 191 ; CHECK-NEXT: ret i32 %V.le 192 } 193 194 195 define void @test9() { 196 loopentry.2.i: 197 br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader 198 no_exit.1.i.preheader: ; preds = %loopentry.2.i 199 br label %no_exit.1.i 200 no_exit.1.i: ; preds = %endif.8.i, %no_exit.1.i.preheader 201 br i1 false, label %return.i, label %endif.8.i 202 endif.8.i: ; preds = %no_exit.1.i 203 %inc.1.i = add i32 0, 1 ; <i32> [#uses=1] 204 br i1 false, label %no_exit.1.i, label %loopentry.3.i.preheader.loopexit 205 loopentry.3.i.preheader.loopexit: ; preds = %endif.8.i 206 br label %loopentry.3.i.preheader 207 loopentry.3.i.preheader: ; preds = %loopentry.3.i.preheader.loopexit, %loopentry.2.i 208 %arg_num.0.i.ph13000 = phi i32 [ 0, %loopentry.2.i ], [ %inc.1.i, %loopentry.3.i.preheader.loopexit ] ; <i32> [#uses=0] 209 ret void 210 return.i: ; preds = %no_exit.1.i 211 ret void 212 213 ; CHECK-LABEL: @test9( 214 ; CHECK: loopentry.3.i.preheader.loopexit: 215 ; CHECK-NEXT: %inc.1.i.le = add i32 0, 1 216 ; CHECK-NEXT: br label %loopentry.3.i.preheader 217 } 218 219 220 ; Potentially trapping instructions may be sunk as long as they are guaranteed 221 ; to be executed. 222 define i32 @test10(i32 %N) { 223 Entry: 224 br label %Loop 225 Loop: ; preds = %Loop, %Entry 226 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ] ; <i32> [#uses=3] 227 %tmp.6 = sdiv i32 %N, %N_addr.0.pn ; <i32> [#uses=1] 228 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1] 229 %tmp.1 = icmp ne i32 %N_addr.0.pn, 0 ; <i1> [#uses=1] 230 br i1 %tmp.1, label %Loop, label %Out 231 Out: ; preds = %Loop 232 ret i32 %tmp.6 233 234 ; CHECK-LABEL: @test10( 235 ; CHECK: Out: 236 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i32 [ %N_addr.0.pn 237 ; CHECK-NEXT: %tmp.6.le = sdiv i32 %N, %[[LCSSAPHI]] 238 ; CHECK-NEXT: ret i32 %tmp.6.le 239 } 240 241 ; Should delete, not sink, dead instructions. 242 define void @test11() { 243 br label %Loop 244 Loop: 245 %dead = getelementptr %Ty, %Ty* @X2, i64 0, i32 0 246 br i1 false, label %Loop, label %Out 247 Out: 248 ret void 249 ; CHECK-LABEL: @test11( 250 ; CHECK: Out: 251 ; CHECK-NEXT: ret void 252 } 253 254 @c = common global [1 x i32] zeroinitializer, align 4 255 256 ; Test a *many* way nested loop with multiple exit blocks both of which exit 257 ; multiple loop nests. This exercises LCSSA corner cases. 258 define i32 @PR18753(i1* %a, i1* %b, i1* %c, i1* %d) { 259 entry: 260 br label %l1.header 261 262 l1.header: 263 %iv = phi i64 [ %iv.next, %l1.latch ], [ 0, %entry ] 264 %arrayidx.i = getelementptr inbounds [1 x i32], [1 x i32]* @c, i64 0, i64 %iv 265 br label %l2.header 266 267 l2.header: 268 %x0 = load i1, i1* %c, align 4 269 br i1 %x0, label %l1.latch, label %l3.preheader 270 271 l3.preheader: 272 br label %l3.header 273 274 l3.header: 275 %x1 = load i1, i1* %d, align 4 276 br i1 %x1, label %l2.latch, label %l4.preheader 277 278 l4.preheader: 279 br label %l4.header 280 281 l4.header: 282 %x2 = load i1, i1* %a 283 br i1 %x2, label %l3.latch, label %l4.body 284 285 l4.body: 286 call void @f(i32* %arrayidx.i) 287 %x3 = load i1, i1* %b 288 %l = trunc i64 %iv to i32 289 br i1 %x3, label %l4.latch, label %exit 290 291 l4.latch: 292 call void @g() 293 %x4 = load i1, i1* %b, align 4 294 br i1 %x4, label %l4.header, label %exit 295 296 l3.latch: 297 br label %l3.header 298 299 l2.latch: 300 br label %l2.header 301 302 l1.latch: 303 %iv.next = add nsw i64 %iv, 1 304 br label %l1.header 305 306 exit: 307 %lcssa = phi i32 [ %l, %l4.latch ], [ %l, %l4.body ] 308 ; CHECK-LABEL: @PR18753( 309 ; CHECK: exit: 310 ; CHECK-NEXT: %[[LCSSAPHI:.*]] = phi i64 [ %iv, %l4.latch ], [ %iv, %l4.body ] 311 ; CHECK-NEXT: %l.le = trunc i64 %[[LCSSAPHI]] to i32 312 ; CHECK-NEXT: ret i32 %l.le 313 314 ret i32 %lcssa 315 } 316 317 ; Can't sink stores out of exit blocks containing indirectbr instructions 318 ; because loop simplify does not create dedicated exits for such blocks. Test 319 ; that by sinking the store from lab21 to lab22, but not further. 320 define void @test12() { 321 ; CHECK-LABEL: @test12 322 br label %lab4 323 324 lab4: 325 br label %lab20 326 327 lab5: 328 br label %lab20 329 330 lab6: 331 br label %lab4 332 333 lab7: 334 br i1 undef, label %lab8, label %lab13 335 336 lab8: 337 br i1 undef, label %lab13, label %lab10 338 339 lab10: 340 br label %lab7 341 342 lab13: 343 ret void 344 345 lab20: 346 br label %lab21 347 348 lab21: 349 ; CHECK: lab21: 350 ; CHECK-NOT: store 351 ; CHECK: br i1 false, label %lab21, label %lab22 352 store i32 36127957, i32* undef, align 4 353 br i1 undef, label %lab21, label %lab22 354 355 lab22: 356 ; CHECK: lab22: 357 ; CHECK: store 358 ; CHECK-NEXT: indirectbr i8* undef 359 indirectbr i8* undef, [label %lab5, label %lab6, label %lab7] 360 } 361 362 ; Test that we don't crash when trying to sink stores and there's no preheader 363 ; available (which is used for creating loads that may be used by the SSA 364 ; updater) 365 define void @test13() { 366 ; CHECK-LABEL: @test13 367 br label %lab59 368 369 lab19: 370 br i1 undef, label %lab20, label %lab38 371 372 lab20: 373 br label %lab60 374 375 lab21: 376 br i1 undef, label %lab22, label %lab38 377 378 lab22: 379 br label %lab38 380 381 lab38: 382 ret void 383 384 lab59: 385 indirectbr i8* undef, [label %lab60, label %lab38] 386 387 lab60: 388 ; CHECK: lab60: 389 ; CHECK: store 390 ; CHECK-NEXT: indirectbr 391 store i32 2145244101, i32* undef, align 4 392 indirectbr i8* undef, [label %lab21, label %lab19] 393 } 394 395 declare void @f(i32*) 396 397 declare void @g() 398
