1; RUN: opt < %s -basicaa -licm -S | FileCheck %s 2 3declare i32 @strlen(i8*) readonly 4 5declare void @foo() 6 7; Sink readonly function. 8define i32 @test1(i8* %P) { 9 br label %Loop 10 11Loop: ; preds = %Loop, %0 12 %A = call i32 @strlen( i8* %P ) readonly 13 br i1 false, label %Loop, label %Out 14 15Out: ; preds = %Loop 16 ret i32 %A 17; CHECK: @test1 18; CHECK: Out: 19; CHECK-NEXT: call i32 @strlen 20; CHECK-NEXT: ret i32 %A 21} 22 23declare double @sin(double) readnone 24 25; Sink readnone function out of loop with unknown memory behavior. 26define double @test2(double %X) { 27 br label %Loop 28 29Loop: ; preds = %Loop, %0 30 call void @foo( ) 31 %A = call double @sin( double %X ) readnone 32 br i1 true, label %Loop, label %Out 33 34Out: ; preds = %Loop 35 ret double %A 36; CHECK: @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. 44define void @test3() { 45Entry: 46 br i1 false, label %Loop, label %Exit 47Loop: 48 %X = add i32 0, 1 49 br i1 false, label %Loop, label %Exit 50Exit: 51 %Y = phi i32 [ 0, %Entry ], [ %X, %Loop ] 52 ret void 53 54; CHECK: @test3 55; CHECK: Exit.loopexit: 56; CHECK-NEXT: %X = 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; 65define i32 @test4(i32 %N) { 66Entry: 67 br label %Loop 68Loop: ; 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 75Out: ; preds = %Loop 76 ret i32 %tmp.7 77; CHECK: @test4 78; CHECK: Out: 79; CHECK-NEXT: mul i32 %N, %N_addr.0.pn 80; CHECK-NEXT: sub i32 %tmp.6, %N 81; CHECK-NEXT: ret i32 82} 83 84; To reduce register pressure, if a load is hoistable out of the loop, and the 85; result of the load is only used outside of the loop, sink the load instead of 86; hoisting it! 87; 88@X = global i32 5 ; <i32*> [#uses=1] 89 90define i32 @test5(i32 %N) { 91Entry: 92 br label %Loop 93Loop: ; preds = %Loop, %Entry 94 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ] 95 %tmp.6 = load i32* @X ; <i32> [#uses=1] 96 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1] 97 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1 ; <i1> [#uses=1] 98 br i1 %tmp.1, label %Loop, label %Out 99Out: ; preds = %Loop 100 ret i32 %tmp.6 101; CHECK: @test5 102; CHECK: Out: 103; CHECK-NEXT: %tmp.6 = load i32* @X 104; CHECK-NEXT: ret i32 %tmp.6 105} 106 107 108 109; The loop sinker was running from the bottom of the loop to the top, causing 110; it to miss opportunities to sink instructions that depended on sinking other 111; instructions from the loop. Instead they got hoisted, which is better than 112; leaving them in the loop, but increases register pressure pointlessly. 113 114 %Ty = type { i32, i32 } 115@X2 = external global %Ty 116 117define i32 @test6() { 118 br label %Loop 119Loop: 120 %dead = getelementptr %Ty* @X2, i64 0, i32 0 121 %sunk2 = load i32* %dead 122 br i1 false, label %Loop, label %Out 123Out: ; preds = %Loop 124 ret i32 %sunk2 125; CHECK: @test6 126; CHECK: Out: 127; CHECK-NEXT: %dead = getelementptr %Ty* @X2, i64 0, i32 0 128; CHECK-NEXT: %sunk2 = load i32* %dead 129; CHECK-NEXT: ret i32 %sunk2 130} 131 132 133 134; This testcase ensures that we can sink instructions from loops with 135; multiple exits. 136; 137define i32 @test7(i32 %N, i1 %C) { 138Entry: 139 br label %Loop 140Loop: ; preds = %ContLoop, %Entry 141 %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ] 142 %tmp.6 = mul i32 %N, %N_addr.0.pn 143 %tmp.7 = sub i32 %tmp.6, %N ; <i32> [#uses=2] 144 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1] 145 br i1 %C, label %ContLoop, label %Out1 146ContLoop: 147 %tmp.1 = icmp ne i32 %N_addr.0.pn, 1 148 br i1 %tmp.1, label %Loop, label %Out2 149Out1: ; preds = %Loop 150 ret i32 %tmp.7 151Out2: ; preds = %ContLoop 152 ret i32 %tmp.7 153; CHECK: @test7 154; CHECK: Out1: 155; CHECK-NEXT: mul i32 %N, %N_addr.0.pn 156; CHECK-NEXT: sub i32 %tmp.6, %N 157; CHECK-NEXT: ret 158; CHECK: Out2: 159; CHECK-NEXT: mul i32 %N, %N_addr.0.pn 160; CHECK-NEXT: sub i32 %tmp.6 161; CHECK-NEXT: ret 162} 163 164 165; This testcase checks to make sure we can sink values which are only live on 166; some exits out of the loop, and that we can do so without breaking dominator 167; info. 168define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) { 169Entry: 170 br label %Loop 171Loop: ; preds = %Cont, %Entry 172 br i1 %C1, label %Cont, label %exit1 173Cont: ; preds = %Loop 174 %X = load i32* %P ; <i32> [#uses=2] 175 store i32 %X, i32* %Q 176 %V = add i32 %X, 1 ; <i32> [#uses=1] 177 br i1 %C2, label %Loop, label %exit2 178exit1: ; preds = %Loop 179 ret i32 0 180exit2: ; preds = %Cont 181 ret i32 %V 182; CHECK: @test8 183; CHECK: exit1: 184; CHECK-NEXT: ret i32 0 185; CHECK: exit2: 186; CHECK-NEXT: %V = add i32 %X, 1 187; CHECK-NEXT: ret i32 %V 188} 189 190 191define void @test9() { 192loopentry.2.i: 193 br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader 194no_exit.1.i.preheader: ; preds = %loopentry.2.i 195 br label %no_exit.1.i 196no_exit.1.i: ; preds = %endif.8.i, %no_exit.1.i.preheader 197 br i1 false, label %return.i, label %endif.8.i 198endif.8.i: ; preds = %no_exit.1.i 199 %inc.1.i = add i32 0, 1 ; <i32> [#uses=1] 200 br i1 false, label %no_exit.1.i, label %loopentry.3.i.preheader.loopexit 201loopentry.3.i.preheader.loopexit: ; preds = %endif.8.i 202 br label %loopentry.3.i.preheader 203loopentry.3.i.preheader: ; preds = %loopentry.3.i.preheader.loopexit, %loopentry.2.i 204 %arg_num.0.i.ph13000 = phi i32 [ 0, %loopentry.2.i ], [ %inc.1.i, %loopentry.3.i.preheader.loopexit ] ; <i32> [#uses=0] 205 ret void 206return.i: ; preds = %no_exit.1.i 207 ret void 208 209; CHECK: @test9 210; CHECK: loopentry.3.i.preheader.loopexit: 211; CHECK-NEXT: %inc.1.i = add i32 0, 1 212; CHECK-NEXT: br label %loopentry.3.i.preheader 213} 214 215 216; Potentially trapping instructions may be sunk as long as they are guaranteed 217; to be executed. 218define i32 @test10(i32 %N) { 219Entry: 220 br label %Loop 221Loop: ; preds = %Loop, %Entry 222 %N_addr.0.pn = phi i32 [ %dec, %Loop ], [ %N, %Entry ] ; <i32> [#uses=3] 223 %tmp.6 = sdiv i32 %N, %N_addr.0.pn ; <i32> [#uses=1] 224 %dec = add i32 %N_addr.0.pn, -1 ; <i32> [#uses=1] 225 %tmp.1 = icmp ne i32 %N_addr.0.pn, 0 ; <i1> [#uses=1] 226 br i1 %tmp.1, label %Loop, label %Out 227Out: ; preds = %Loop 228 ret i32 %tmp.6 229 230; CHECK: @test10 231; CHECK: Out: 232; CHECK-NEXT: %tmp.6 = sdiv i32 %N, %N_addr.0.pn 233; CHECK-NEXT: ret i32 %tmp.6 234} 235 236; Should delete, not sink, dead instructions. 237define void @test11() { 238 br label %Loop 239Loop: 240 %dead = getelementptr %Ty* @X2, i64 0, i32 0 241 br i1 false, label %Loop, label %Out 242Out: 243 ret void 244; CHECK: @test11 245; CHECK: Out: 246; CHECK-NEXT: ret void 247} 248 249 250