test/Transforms/LICM/sinking.ll

   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: @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: @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: @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 ;
  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: @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
  90 define i32 @test5(i32 %N) {
  91 Entry:
  92         br label %Loop
  93 Loop:           ; 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
  99 Out:            ; 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
 117 define i32 @test6() {
 118         br label %Loop
 119 Loop:
 120         %dead = getelementptr %Ty* @X2, i64 0, i32 0
 121         %sunk2 = load i32* %dead
 122         br i1 false, label %Loop, label %Out
 123 Out:            ; 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 ;
 137 define i32 @test7(i32 %N, i1 %C) {
 138 Entry:
 139         br label %Loop
 140 Loop:           ; 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
 146 ContLoop:
 147         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
 148         br i1 %tmp.1, label %Loop, label %Out2
 149 Out1:           ; preds = %Loop
 150         ret i32 %tmp.7
 151 Out2:           ; 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.
 168 define i32 @test8(i1 %C1, i1 %C2, i32* %P, i32* %Q) {
 169 Entry:
 170         br label %Loop
 171 Loop:           ; preds = %Cont, %Entry
 172         br i1 %C1, label %Cont, label %exit1
 173 Cont:           ; 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
 178 exit1:          ; preds = %Loop
 179         ret i32 0
 180 exit2:          ; 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
 191 define void @test9() {
 192 loopentry.2.i:
 193         br i1 false, label %no_exit.1.i.preheader, label %loopentry.3.i.preheader
 194 no_exit.1.i.preheader:          ; preds = %loopentry.2.i
 195         br label %no_exit.1.i
 196 no_exit.1.i:            ; preds = %endif.8.i, %no_exit.1.i.preheader
 197         br i1 false, label %return.i, label %endif.8.i
 198 endif.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
 201 loopentry.3.i.preheader.loopexit:               ; preds = %endif.8.i
 202         br label %loopentry.3.i.preheader
 203 loopentry.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
 206 return.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.
 218 define i32 @test10(i32 %N) {
 219 Entry:
 220         br label %Loop
 221 Loop:           ; 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
 227 Out:            ; 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