test/Transforms/JumpThreading/basic.ll

   1 ; RUN: opt < %s -jump-threading -S | FileCheck %s
   2
   3 declare i32 @f1()
   4 declare i32 @f2()
   5 declare void @f3()
   6
   7 define i32 @test1(i1 %cond) {
   8 ; CHECK: @test1
   9
  10         br i1 %cond, label %T1, label %F1
  11
  12 T1:
  13         %v1 = call i32 @f1()
  14         br label %Merge
  15
  16 F1:
  17         %v2 = call i32 @f2()
  18         br label %Merge
  19
  20 Merge:
  21         %A = phi i1 [true, %T1], [false, %F1]
  22         %B = phi i32 [%v1, %T1], [%v2, %F1]
  23         br i1 %A, label %T2, label %F2
  24
  25 T2:
  26 ; CHECK: T2:
  27 ; CHECK: ret i32 %v1
  28         call void @f3()
  29         ret i32 %B
  30
  31 F2:
  32 ; CHECK: F2:
  33 ; CHECK: ret i32 %v2
  34         ret i32 %B
  35 }
  36
  37
  38 ;; cond is known false on Entry -> F1 edge!
  39 define i32 @test2(i1 %cond) {
  40 ; CHECK: @test2
  41 Entry:
  42         br i1 %cond, label %T1, label %F1
  43
  44 T1:
  45 ; CHECK: %v1 = call i32 @f1()
  46 ; CHECK: ret i32 47
  47         %v1 = call i32 @f1()
  48         br label %Merge
  49
  50 F1:
  51         br i1 %cond, label %Merge, label %F2
  52
  53 Merge:
  54         %B = phi i32 [47, %T1], [192, %F1]
  55         ret i32 %B
  56
  57 F2:
  58         call void @f3()
  59         ret i32 12
  60 }
  61
  62
  63 ; Undef handling.
  64 define i32 @test3(i1 %cond) {
  65 ; CHECK: @test3
  66 ; CHECK-NEXT: T1:
  67 ; CHECK-NEXT: ret i32 42
  68         br i1 undef, label %T1, label %F1
  69
  70 T1:
  71         ret i32 42
  72
  73 F1:
  74         ret i32 17
  75 }
  76
  77 define i32 @test4(i1 %cond, i1 %cond2) {
  78 ; CHECK: @test4
  79
  80         br i1 %cond, label %T1, label %F1
  81
  82 T1:
  83 ; CHECK:   %v1 = call i32 @f1()
  84 ; CHECK-NEXT:   br label %T
  85
  86         %v1 = call i32 @f1()
  87         br label %Merge
  88
  89 F1:
  90         %v2 = call i32 @f2()
  91 ; CHECK:   %v2 = call i32 @f2()
  92 ; CHECK-NEXT:   br i1 %cond2,
  93         br label %Merge
  94
  95 Merge:
  96         %A = phi i1 [undef, %T1], [%cond2, %F1]
  97         %B = phi i32 [%v1, %T1], [%v2, %F1]
  98         br i1 %A, label %T2, label %F2
  99
 100 T2:
 101         call void @f3()
 102         ret i32 %B
 103
 104 F2:
 105         ret i32 %B
 106 }
 107
 108
 109 ;; This tests that the branch in 'merge' can be cloned up into T1.
 110 define i32 @test5(i1 %cond, i1 %cond2) {
 111 ; CHECK: @test5
 112
 113         br i1 %cond, label %T1, label %F1
 114
 115 T1:
 116 ; CHECK: T1:
 117 ; CHECK-NEXT:   %v1 = call i32 @f1()
 118 ; CHECK-NEXT:   %cond3 = icmp eq i32 %v1, 412
 119 ; CHECK-NEXT:   br i1 %cond3, label %T2, label %F2
 120
 121         %v1 = call i32 @f1()
 122         %cond3 = icmp eq i32 %v1, 412
 123         br label %Merge
 124
 125 F1:
 126         %v2 = call i32 @f2()
 127         br label %Merge
 128
 129 Merge:
 130         %A = phi i1 [%cond3, %T1], [%cond2, %F1]
 131         %B = phi i32 [%v1, %T1], [%v2, %F1]
 132         br i1 %A, label %T2, label %F2
 133
 134 T2:
 135         call void @f3()
 136         ret i32 %B
 137
 138 F2:
 139         ret i32 %B
 140 }
 141
 142
 143 ;; Lexically duplicated conditionals should be threaded.
 144
 145
 146 define i32 @test6(i32 %A) {
 147 ; CHECK: @test6
 148         %tmp455 = icmp eq i32 %A, 42
 149         br i1 %tmp455, label %BB1, label %BB2
 150
 151 BB2:
 152 ; CHECK: call i32 @f1()
 153 ; CHECK-NEXT: call void @f3()
 154 ; CHECK-NEXT: ret i32 4
 155         call i32 @f1()
 156         br label %BB1
 157
 158
 159 BB1:
 160         %tmp459 = icmp eq i32 %A, 42
 161         br i1 %tmp459, label %BB3, label %BB4
 162
 163 BB3:
 164         call i32 @f2()
 165         ret i32 3
 166
 167 BB4:
 168         call void @f3()
 169         ret i32 4
 170 }
 171
 172
 173 ;; This tests that the branch in 'merge' can be cloned up into T1.
 174 ;; rdar://7367025
 175 define i32 @test7(i1 %cond, i1 %cond2) {
 176 Entry:
 177 ; CHECK: @test7
 178         %v1 = call i32 @f1()
 179         br i1 %cond, label %Merge, label %F1
 180
 181 F1:
 182         %v2 = call i32 @f2()
 183         br label %Merge
 184
 185 Merge:
 186         %B = phi i32 [%v1, %Entry], [%v2, %F1]
 187         %M = icmp ne i32 %B, %v1
 188         %N = icmp eq i32 %B, 47
 189         %O = and i1 %M, %N
 190         br i1 %O, label %T2, label %F2
 191
 192 ; CHECK: Merge:
 193 ; CHECK-NOT: phi
 194 ; CHECK-NEXT:   %v2 = call i32 @f2()
 195
 196 T2:
 197         call void @f3()
 198         ret i32 %B
 199
 200 F2:
 201         ret i32 %B
 202 ; CHECK: F2:
 203 ; CHECK-NEXT: phi i32
 204 }
 205
 206
 207 declare i1 @test8a()
 208
 209 define i32 @test8b(i1 %cond, i1 %cond2) {
 210 ; CHECK: @test8b
 211 T0:
 212         %A = call i1 @test8a()
 213         br i1 %A, label %T1, label %F1
 214
 215 ; CHECK: T0:
 216 ; CHECK-NEXT: call
 217 ; CHECK-NEXT: br i1 %A, label %T1, label %Y
 218
 219 T1:
 220         %B = call i1 @test8a()
 221         br i1 %B, label %T2, label %F1
 222
 223 ; CHECK: T1:
 224 ; CHECK-NEXT: call
 225 ; CHECK-NEXT: br i1 %B, label %T2, label %Y
 226 T2:
 227         %C = call i1 @test8a()
 228         br i1 %cond, label %T3, label %F1
 229
 230 ; CHECK: T2:
 231 ; CHECK-NEXT: call
 232 ; CHECK-NEXT: br i1 %cond, label %T3, label %Y
 233 T3:
 234         ret i32 0
 235
 236 F1:
 237         %D = phi i32 [0, %T0], [0, %T1], [1, %T2]
 238         %E = icmp eq i32 %D, 1
 239         %F = and i1 %E, %cond
 240         br i1 %F, label %X, label %Y
 241 X:
 242         call i1 @test8a()
 243         ret i32 1
 244 Y:
 245         ret i32 2
 246 }
 247
 248
 249 ;;; Verify that we can handle constraint propagation through "xor x, 1".
 250 define i32 @test9(i1 %cond, i1 %cond2) {
 251 Entry:
 252 ; CHECK: @test9
 253         %v1 = call i32 @f1()
 254         br i1 %cond, label %Merge, label %F1
 255
 256 ; CHECK: Entry:
 257 ; CHECK-NEXT:  %v1 = call i32 @f1()
 258 ; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
 259
 260 F1:
 261         %v2 = call i32 @f2()
 262         br label %Merge
 263
 264 Merge:
 265         %B = phi i32 [%v1, %Entry], [%v2, %F1]
 266         %M = icmp eq i32 %B, %v1
 267         %M1 = xor i1 %M, 1
 268         %N = icmp eq i32 %B, 47
 269         %O = and i1 %M1, %N
 270         br i1 %O, label %T2, label %F2
 271
 272 ; CHECK: Merge:
 273 ; CHECK-NOT: phi
 274 ; CHECK-NEXT:   %v2 = call i32 @f2()
 275
 276 T2:
 277         %Q = zext i1 %M to i32
 278         ret i32 %Q
 279
 280 F2:
 281         ret i32 %B
 282 ; CHECK: F2:
 283 ; CHECK-NEXT: phi i32
 284 }
 285
 286
 287
 288
 289 ;;; Duplicate condition to avoid xor of cond.
 290 define i32 @test10(i1 %cond, i1 %cond2) {
 291 Entry:
 292 ; CHECK: @test10
 293         %v1 = call i32 @f1()
 294         br i1 %cond, label %Merge, label %F1
 295
 296 F1:
 297         br label %Merge
 298
 299 Merge:
 300         %B = phi i1 [true, %Entry], [%cond2, %F1]
 301         %M = icmp eq i32 %v1, 192
 302         %N = xor i1 %B, %M
 303         br i1 %N, label %T2, label %F2
 304
 305 T2:
 306         ret i32 123
 307
 308 F2:
 309         ret i32 %v1
 310 }
 311
 312