llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -S -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -bonus-inst-threshold=10 | FileCheck %s
   3
   4 declare void @sideeffect0()
   5 declare void @sideeffect1()
   6 declare void @sideeffect2()
   7 declare void @use8(i8)
   8 declare i1 @gen1()
   9 declare i32 @speculate_call(ptr) #0
  10
  11 ; Basic cases, blocks have nothing other than the comparison itself.
  12
  13 define void @one_pred(i8 %v0, i8 %v1) {
  14 ; CHECK-LABEL: @one_pred(
  15 ; CHECK-NEXT:  pred:
  16 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
  17 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
  18 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
  19 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
  20 ; CHECK:       common.ret:
  21 ; CHECK-NEXT:    ret void
  22 ; CHECK:       final_left:
  23 ; CHECK-NEXT:    call void @sideeffect0()
  24 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
  25 ; CHECK:       final_right:
  26 ; CHECK-NEXT:    call void @sideeffect1()
  27 ; CHECK-NEXT:    br label [[COMMON_RET]]
  28 ;
  29 pred:
  30   %c0 = icmp eq i8 %v0, 0
  31   br i1 %c0, label %dispatch, label %final_right
  32 dispatch:
  33   %c1 = icmp eq i8 %v1, 0
  34   br i1 %c1, label %final_left, label %final_right
  35 final_left:
  36   call void @sideeffect0()
  37   ret void
  38 final_right:
  39   call void @sideeffect1()
  40   ret void
  41 }
  42
  43 define void @two_preds(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
  44 ; CHECK-LABEL: @two_preds(
  45 ; CHECK-NEXT:  entry:
  46 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
  47 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
  48 ; CHECK:       pred0:
  49 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
  50 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3:%.*]], 0
  51 ; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
  52 ; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
  53 ; CHECK:       pred1:
  54 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
  55 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3]], 0
  56 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
  57 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
  58 ; CHECK:       common.ret:
  59 ; CHECK-NEXT:    ret void
  60 ; CHECK:       final_left:
  61 ; CHECK-NEXT:    call void @sideeffect0()
  62 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
  63 ; CHECK:       final_right:
  64 ; CHECK-NEXT:    call void @sideeffect1()
  65 ; CHECK-NEXT:    br label [[COMMON_RET]]
  66 ;
  67 entry:
  68   %c0 = icmp eq i8 %v0, 0
  69   br i1 %c0, label %pred0, label %pred1
  70 pred0:
  71   %c1 = icmp eq i8 %v1, 0
  72   br i1 %c1, label %final_left, label %dispatch
  73 pred1:
  74   %c2 = icmp eq i8 %v2, 0
  75   br i1 %c2, label %dispatch, label %final_right
  76 dispatch:
  77   %c3 = icmp eq i8 %v3, 0
  78   br i1 %c3, label %final_left, label %final_right
  79 final_left:
  80   call void @sideeffect0()
  81   ret void
  82 final_right:
  83   call void @sideeffect1()
  84   ret void
  85 }
  86
  87 ; More complex case, there's an extra op that is safe to execute unconditionally.
  88
  89 define void @one_pred_with_extra_op(i8 %v0, i8 %v1) {
  90 ; CHECK-LABEL: @one_pred_with_extra_op(
  91 ; CHECK-NEXT:  pred:
  92 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
  93 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
  94 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ]], 0
  95 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
  96 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
  97 ; CHECK:       common.ret:
  98 ; CHECK-NEXT:    ret void
  99 ; CHECK:       final_left:
 100 ; CHECK-NEXT:    call void @sideeffect0()
 101 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 102 ; CHECK:       final_right:
 103 ; CHECK-NEXT:    call void @sideeffect1()
 104 ; CHECK-NEXT:    br label [[COMMON_RET]]
 105 ;
 106 pred:
 107   %c0 = icmp eq i8 %v0, 0
 108   br i1 %c0, label %dispatch, label %final_right
 109 dispatch:
 110   %v1_adj = add i8 %v0, %v1
 111   %c1 = icmp eq i8 %v1_adj, 0
 112   br i1 %c1, label %final_left, label %final_right
 113 final_left:
 114   call void @sideeffect0()
 115   ret void
 116 final_right:
 117   call void @sideeffect1()
 118   ret void
 119 }
 120
 121 ; When we fold the dispatch block into pred, the call is moved to pred
 122 ; and the attribute nonnull propagates poison paramater. However, since the
 123 ; function is speculatable, it can never cause UB. So, we need not technically drop it.
 124 define void @one_pred_with_spec_call(i8 %v0, i8 %v1, ptr %p) {
 125 ; CHECK-LABEL: @one_pred_with_spec_call(
 126 ; CHECK-NEXT:  pred:
 127 ; CHECK-NEXT:    [[C0:%.*]] = icmp ne ptr [[P:%.*]], null
 128 ; CHECK-NEXT:    [[X:%.*]] = call i32 @speculate_call(ptr nonnull [[P]])
 129 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 130 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 131 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COMMON_RET:%.*]], label [[FINAL_RIGHT:%.*]]
 132 ; CHECK:       common.ret:
 133 ; CHECK-NEXT:    ret void
 134 ; CHECK:       final_right:
 135 ; CHECK-NEXT:    call void @sideeffect0()
 136 ; CHECK-NEXT:    br label [[COMMON_RET]]
 137 ;
 138 pred:
 139   %c0 = icmp ne ptr %p, null
 140   br i1 %c0, label %dispatch, label %final_right
 141
 142 dispatch:
 143   %x = call i32 @speculate_call(ptr nonnull %p)
 144   %c1 = icmp eq i8 %v1, 0
 145   br i1 %c1, label %final_left, label %final_right
 146
 147 final_left:
 148   ret void
 149
 150 final_right:
 151   call void @sideeffect0()
 152   ret void
 153 }
 154
 155 ; Drop dereferenceable on the parameter
 156 define void @one_pred_with_spec_call_deref(i8 %v0, i8 %v1, ptr %p) {
 157 ; CHECK-LABEL: @one_pred_with_spec_call_deref(
 158 ; CHECK-NEXT:  pred:
 159 ; CHECK-NEXT:    [[C0:%.*]] = icmp ne ptr [[P:%.*]], null
 160 ; CHECK-NEXT:    [[X:%.*]] = call i32 @speculate_call(ptr [[P]])
 161 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 162 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 163 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[COMMON_RET:%.*]], label [[FINAL_RIGHT:%.*]]
 164 ; CHECK:       common.ret:
 165 ; CHECK-NEXT:    ret void
 166 ; CHECK:       final_right:
 167 ; CHECK-NEXT:    call void @sideeffect0()
 168 ; CHECK-NEXT:    br label [[COMMON_RET]]
 169 ;
 170 pred:
 171   %c0 = icmp ne ptr %p, null
 172   br i1 %c0, label %dispatch, label %final_right
 173
 174 dispatch:
 175   %x = call i32 @speculate_call(ptr dereferenceable(12) %p)
 176   %c1 = icmp eq i8 %v1, 0
 177   br i1 %c1, label %final_left, label %final_right
 178
 179 final_left:
 180   ret void
 181
 182 final_right:
 183   call void @sideeffect0()
 184   ret void
 185 }
 186
 187 define void @two_preds_with_extra_op(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 188 ; CHECK-LABEL: @two_preds_with_extra_op(
 189 ; CHECK-NEXT:  entry:
 190 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 191 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 192 ; CHECK:       pred0:
 193 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 194 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
 195 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
 196 ; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
 197 ; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 198 ; CHECK:       pred1:
 199 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 200 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 201 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
 202 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 203 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 204 ; CHECK:       common.ret:
 205 ; CHECK-NEXT:    ret void
 206 ; CHECK:       final_left:
 207 ; CHECK-NEXT:    call void @sideeffect0()
 208 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 209 ; CHECK:       final_right:
 210 ; CHECK-NEXT:    call void @sideeffect1()
 211 ; CHECK-NEXT:    br label [[COMMON_RET]]
 212 ;
 213 entry:
 214   %c0 = icmp eq i8 %v0, 0
 215   br i1 %c0, label %pred0, label %pred1
 216 pred0:
 217   %c1 = icmp eq i8 %v1, 0
 218   br i1 %c1, label %final_left, label %dispatch
 219 pred1:
 220   %c2 = icmp eq i8 %v2, 0
 221   br i1 %c2, label %dispatch, label %final_right
 222 dispatch:
 223   %v3_adj = add i8 %v1, %v2
 224   %c3 = icmp eq i8 %v3_adj, 0
 225   br i1 %c3, label %final_left, label %final_right
 226 final_left:
 227   call void @sideeffect0()
 228   ret void
 229 final_right:
 230   call void @sideeffect1()
 231   ret void
 232 }
 233
 234 ; More complex case, there's an extra op that is safe to execute unconditionally, and it has multiple uses.
 235
 236 define void @one_pred_with_extra_op_multiuse(i8 %v0, i8 %v1) {
 237 ; CHECK-LABEL: @one_pred_with_extra_op_multiuse(
 238 ; CHECK-NEXT:  pred:
 239 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 240 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 241 ; CHECK-NEXT:    [[V1_ADJ_ADJ:%.*]] = add i8 [[V1_ADJ]], [[V1_ADJ]]
 242 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ_ADJ]], 0
 243 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C0]], i1 [[C1]], i1 false
 244 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 245 ; CHECK:       common.ret:
 246 ; CHECK-NEXT:    ret void
 247 ; CHECK:       final_left:
 248 ; CHECK-NEXT:    call void @sideeffect0()
 249 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 250 ; CHECK:       final_right:
 251 ; CHECK-NEXT:    call void @sideeffect1()
 252 ; CHECK-NEXT:    br label [[COMMON_RET]]
 253 ;
 254 pred:
 255   %c0 = icmp eq i8 %v0, 0
 256   br i1 %c0, label %dispatch, label %final_right
 257 dispatch:
 258   %v1_adj = add i8 %v0, %v1
 259   %v1_adj_adj = add i8 %v1_adj, %v1_adj
 260   %c1 = icmp eq i8 %v1_adj_adj, 0
 261   br i1 %c1, label %final_left, label %final_right
 262 final_left:
 263   call void @sideeffect0()
 264   ret void
 265 final_right:
 266   call void @sideeffect1()
 267   ret void
 268 }
 269
 270 define void @two_preds_with_extra_op_multiuse(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 271 ; CHECK-LABEL: @two_preds_with_extra_op_multiuse(
 272 ; CHECK-NEXT:  entry:
 273 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 274 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 275 ; CHECK:       pred0:
 276 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 277 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2:%.*]]
 278 ; CHECK-NEXT:    [[V3_ADJ_ADJ_OLD:%.*]] = add i8 [[V3_ADJ_OLD]], [[V3_ADJ_OLD]]
 279 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_ADJ_OLD]], 0
 280 ; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[C1]], i1 true, i1 [[C3_OLD]]
 281 ; CHECK-NEXT:    br i1 [[OR_COND1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT:%.*]]
 282 ; CHECK:       pred1:
 283 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2]], 0
 284 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 285 ; CHECK-NEXT:    [[V3_ADJ_ADJ:%.*]] = add i8 [[V3_ADJ]], [[V3_ADJ]]
 286 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ_ADJ]], 0
 287 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 288 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 289 ; CHECK:       common.ret:
 290 ; CHECK-NEXT:    ret void
 291 ; CHECK:       final_left:
 292 ; CHECK-NEXT:    call void @sideeffect0()
 293 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 294 ; CHECK:       final_right:
 295 ; CHECK-NEXT:    call void @sideeffect1()
 296 ; CHECK-NEXT:    br label [[COMMON_RET]]
 297 ;
 298 entry:
 299   %c0 = icmp eq i8 %v0, 0
 300   br i1 %c0, label %pred0, label %pred1
 301 pred0:
 302   %c1 = icmp eq i8 %v1, 0
 303   br i1 %c1, label %final_left, label %dispatch
 304 pred1:
 305   %c2 = icmp eq i8 %v2, 0
 306   br i1 %c2, label %dispatch, label %final_right
 307 dispatch:
 308   %v3_adj = add i8 %v1, %v2
 309   %v3_adj_adj = add i8 %v3_adj, %v3_adj
 310   %c3 = icmp eq i8 %v3_adj_adj, 0
 311   br i1 %c3, label %final_left, label %final_right
 312 final_left:
 313   call void @sideeffect0()
 314   ret void
 315 final_right:
 316   call void @sideeffect1()
 317   ret void
 318 }
 319
 320 ; More complex case, there's an op that is safe to execute unconditionally,
 321 ; and said op is live-out.
 322
 323 define void @one_pred_with_extra_op_liveout(i8 %v0, i8 %v1) {
 324 ; CHECK-LABEL: @one_pred_with_extra_op_liveout(
 325 ; CHECK-NEXT:  pred:
 326 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 327 ; CHECK-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
 328 ; CHECK:       dispatch:
 329 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 330 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ]], 0
 331 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
 332 ; CHECK:       common.ret:
 333 ; CHECK-NEXT:    ret void
 334 ; CHECK:       final_left:
 335 ; CHECK-NEXT:    call void @sideeffect0()
 336 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 337 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 338 ; CHECK:       final_right:
 339 ; CHECK-NEXT:    call void @sideeffect1()
 340 ; CHECK-NEXT:    br label [[COMMON_RET]]
 341 ;
 342 pred:
 343   %c0 = icmp eq i8 %v0, 0
 344   br i1 %c0, label %dispatch, label %final_right
 345 dispatch:
 346   %v1_adj = add i8 %v0, %v1
 347   %c1 = icmp eq i8 %v1_adj, 0
 348   br i1 %c1, label %final_left, label %final_right
 349 final_left:
 350   call void @sideeffect0()
 351   call void @use8(i8 %v1_adj)
 352   ret void
 353 final_right:
 354   call void @sideeffect1()
 355   ret void
 356 }
 357 define void @one_pred_with_extra_op_liveout_multiuse(i8 %v0, i8 %v1) {
 358 ; CHECK-LABEL: @one_pred_with_extra_op_liveout_multiuse(
 359 ; CHECK-NEXT:  pred:
 360 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 361 ; CHECK-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
 362 ; CHECK:       dispatch:
 363 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 364 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1_ADJ]], 0
 365 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
 366 ; CHECK:       common.ret:
 367 ; CHECK-NEXT:    ret void
 368 ; CHECK:       final_left:
 369 ; CHECK-NEXT:    call void @sideeffect0()
 370 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 371 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 372 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 373 ; CHECK:       final_right:
 374 ; CHECK-NEXT:    call void @sideeffect1()
 375 ; CHECK-NEXT:    br label [[COMMON_RET]]
 376 ;
 377 pred:
 378   %c0 = icmp eq i8 %v0, 0
 379   br i1 %c0, label %dispatch, label %final_right
 380 dispatch:
 381   %v1_adj = add i8 %v0, %v1
 382   %c1 = icmp eq i8 %v1_adj, 0
 383   br i1 %c1, label %final_left, label %final_right
 384 final_left:
 385   call void @sideeffect0()
 386   call void @use8(i8 %v1_adj)
 387   call void @use8(i8 %v1_adj)
 388   ret void
 389 final_right:
 390   call void @sideeffect1()
 391   ret void
 392 }
 393
 394 define void @one_pred_with_extra_op_liveout_distant_phi(i8 %v0, i8 %v1) {
 395 ; CHECK-LABEL: @one_pred_with_extra_op_liveout_distant_phi(
 396 ; CHECK-NEXT:  entry:
 397 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 398 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED:%.*]], label [[LEFT_END:%.*]]
 399 ; CHECK:       pred:
 400 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 401 ; CHECK-NEXT:    br i1 [[C1]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
 402 ; CHECK:       dispatch:
 403 ; CHECK-NEXT:    [[V2_ADJ:%.*]] = add i8 [[V0]], [[V1]]
 404 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2_ADJ]], 0
 405 ; CHECK-NEXT:    br i1 [[C2]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
 406 ; CHECK:       final_left:
 407 ; CHECK-NEXT:    call void @sideeffect0()
 408 ; CHECK-NEXT:    call void @use8(i8 [[V2_ADJ]])
 409 ; CHECK-NEXT:    br label [[LEFT_END]]
 410 ; CHECK:       common.ret:
 411 ; CHECK-NEXT:    ret void
 412 ; CHECK:       left_end:
 413 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V2_ADJ]], [[FINAL_LEFT]] ], [ 0, [[ENTRY:%.*]] ]
 414 ; CHECK-NEXT:    call void @sideeffect1()
 415 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 416 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 417 ; CHECK:       final_right:
 418 ; CHECK-NEXT:    call void @sideeffect2()
 419 ; CHECK-NEXT:    br label [[COMMON_RET]]
 420 ;
 421 entry:
 422   %c0 = icmp eq i8 %v0, 0
 423   br i1 %c0, label %pred, label %left_end
 424 pred:
 425   %c1 = icmp eq i8 %v1, 0
 426   br i1 %c1, label %dispatch, label %final_right
 427 dispatch:
 428   %v2_adj = add i8 %v0, %v1
 429   %c2 = icmp eq i8 %v2_adj, 0
 430   br i1 %c2, label %final_left, label %final_right
 431 final_left:
 432   call void @sideeffect0()
 433   call void @use8(i8 %v2_adj)
 434   br label %left_end
 435 left_end:
 436   %merge_left = phi i8 [ %v2_adj, %final_left ], [ 0, %entry ]
 437   call void @sideeffect1()
 438   call void @use8(i8 %merge_left)
 439   ret void
 440 final_right:
 441   call void @sideeffect2()
 442   ret void
 443 }
 444
 445 define void @two_preds_with_extra_op_liveout(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 446 ; CHECK-LABEL: @two_preds_with_extra_op_liveout(
 447 ; CHECK-NEXT:  entry:
 448 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 449 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 450 ; CHECK:       pred0:
 451 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 452 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 453 ; CHECK:       pred1:
 454 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 455 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 456 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
 457 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 458 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 459 ; CHECK:       dispatch:
 460 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 461 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
 462 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 463 ; CHECK:       common.ret:
 464 ; CHECK-NEXT:    ret void
 465 ; CHECK:       final_left:
 466 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 467 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 468 ; CHECK-NEXT:    call void @sideeffect0()
 469 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 470 ; CHECK:       final_right:
 471 ; CHECK-NEXT:    call void @sideeffect1()
 472 ; CHECK-NEXT:    br label [[COMMON_RET]]
 473 ;
 474 entry:
 475   %c0 = icmp eq i8 %v0, 0
 476   br i1 %c0, label %pred0, label %pred1
 477 pred0:
 478   %c1 = icmp eq i8 %v1, 0
 479   br i1 %c1, label %final_left, label %dispatch
 480 pred1:
 481   %c2 = icmp eq i8 %v2, 0
 482   br i1 %c2, label %dispatch, label %final_right
 483 dispatch:
 484   %v3_adj = add i8 %v1, %v2
 485   %c3 = icmp eq i8 %v3_adj, 0
 486   br i1 %c3, label %final_left, label %final_right
 487 final_left:
 488   %merge_left = phi i8 [ %v3_adj, %dispatch ], [ 0, %pred0 ]
 489   call void @use8(i8 %merge_left)
 490   call void @sideeffect0()
 491   ret void
 492 final_right:
 493   call void @sideeffect1()
 494   ret void
 495 }
 496
 497 define void @two_preds_with_extra_op_liveout_multiuse(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 498 ; CHECK-LABEL: @two_preds_with_extra_op_liveout_multiuse(
 499 ; CHECK-NEXT:  entry:
 500 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 501 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 502 ; CHECK:       pred0:
 503 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 504 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 505 ; CHECK:       pred1:
 506 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 507 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 508 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3_ADJ]], 0
 509 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 510 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 511 ; CHECK:       dispatch:
 512 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 513 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3_ADJ_OLD]], 0
 514 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 515 ; CHECK:       common.ret:
 516 ; CHECK-NEXT:    ret void
 517 ; CHECK:       final_left:
 518 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 519 ; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 42, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 520 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 521 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT_2]])
 522 ; CHECK-NEXT:    call void @sideeffect0()
 523 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 524 ; CHECK:       final_right:
 525 ; CHECK-NEXT:    call void @sideeffect1()
 526 ; CHECK-NEXT:    br label [[COMMON_RET]]
 527 ;
 528 entry:
 529   %c0 = icmp eq i8 %v0, 0
 530   br i1 %c0, label %pred0, label %pred1
 531 pred0:
 532   %c1 = icmp eq i8 %v1, 0
 533   br i1 %c1, label %final_left, label %dispatch
 534 pred1:
 535   %c2 = icmp eq i8 %v2, 0
 536   br i1 %c2, label %dispatch, label %final_right
 537 dispatch:
 538   %v3_adj = add i8 %v1, %v2
 539   %c3 = icmp eq i8 %v3_adj, 0
 540   br i1 %c3, label %final_left, label %final_right
 541 final_left:
 542   %merge_left = phi i8 [ %v3_adj, %dispatch ], [ 0, %pred0 ]
 543   %merge_left_2 = phi i8 [ %v3_adj, %dispatch ], [ 42, %pred0 ]
 544   call void @use8(i8 %merge_left)
 545   call void @use8(i8 %merge_left_2)
 546   call void @sideeffect0()
 547   ret void
 548 final_right:
 549   call void @sideeffect1()
 550   ret void
 551 }
 552
 553 ; More complex case, there's an op that is safe to execute unconditionally,
 554 ; and said op is live-out, and it is only used externally.
 555
 556 define void @one_pred_with_extra_op_eexternally_used_only(i8 %v0, i8 %v1) {
 557 ; CHECK-LABEL: @one_pred_with_extra_op_eexternally_used_only(
 558 ; CHECK-NEXT:  pred:
 559 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 560 ; CHECK-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
 561 ; CHECK:       dispatch:
 562 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 563 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1]], 0
 564 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
 565 ; CHECK:       common.ret:
 566 ; CHECK-NEXT:    ret void
 567 ; CHECK:       final_left:
 568 ; CHECK-NEXT:    call void @sideeffect0()
 569 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 570 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 571 ; CHECK:       final_right:
 572 ; CHECK-NEXT:    call void @sideeffect1()
 573 ; CHECK-NEXT:    br label [[COMMON_RET]]
 574 ;
 575 pred:
 576   %c0 = icmp eq i8 %v0, 0
 577   br i1 %c0, label %dispatch, label %final_right
 578 dispatch:
 579   %v1_adj = add i8 %v0, %v1
 580   %c1 = icmp eq i8 %v1, 0
 581   br i1 %c1, label %final_left, label %final_right
 582 final_left:
 583   call void @sideeffect0()
 584   call void @use8(i8 %v1_adj)
 585   ret void
 586 final_right:
 587   call void @sideeffect1()
 588   ret void
 589 }
 590 define void @one_pred_with_extra_op_externally_used_only_multiuse(i8 %v0, i8 %v1) {
 591 ; CHECK-LABEL: @one_pred_with_extra_op_externally_used_only_multiuse(
 592 ; CHECK-NEXT:  pred:
 593 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 594 ; CHECK-NEXT:    br i1 [[C0]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
 595 ; CHECK:       dispatch:
 596 ; CHECK-NEXT:    [[V1_ADJ:%.*]] = add i8 [[V0]], [[V1:%.*]]
 597 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1]], 0
 598 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
 599 ; CHECK:       common.ret:
 600 ; CHECK-NEXT:    ret void
 601 ; CHECK:       final_left:
 602 ; CHECK-NEXT:    call void @sideeffect0()
 603 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 604 ; CHECK-NEXT:    call void @use8(i8 [[V1_ADJ]])
 605 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 606 ; CHECK:       final_right:
 607 ; CHECK-NEXT:    call void @sideeffect1()
 608 ; CHECK-NEXT:    br label [[COMMON_RET]]
 609 ;
 610 pred:
 611   %c0 = icmp eq i8 %v0, 0
 612   br i1 %c0, label %dispatch, label %final_right
 613 dispatch:
 614   %v1_adj = add i8 %v0, %v1
 615   %c1 = icmp eq i8 %v1, 0
 616   br i1 %c1, label %final_left, label %final_right
 617 final_left:
 618   call void @sideeffect0()
 619   call void @use8(i8 %v1_adj)
 620   call void @use8(i8 %v1_adj)
 621   ret void
 622 final_right:
 623   call void @sideeffect1()
 624   ret void
 625 }
 626
 627 define void @two_preds_with_extra_op_externally_used_only(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 628 ; CHECK-LABEL: @two_preds_with_extra_op_externally_used_only(
 629 ; CHECK-NEXT:  entry:
 630 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 631 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 632 ; CHECK:       pred0:
 633 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 634 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 635 ; CHECK:       pred1:
 636 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 637 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 638 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
 639 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 640 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 641 ; CHECK:       dispatch:
 642 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 643 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
 644 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 645 ; CHECK:       common.ret:
 646 ; CHECK-NEXT:    ret void
 647 ; CHECK:       final_left:
 648 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 649 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 650 ; CHECK-NEXT:    call void @sideeffect0()
 651 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 652 ; CHECK:       final_right:
 653 ; CHECK-NEXT:    call void @sideeffect1()
 654 ; CHECK-NEXT:    br label [[COMMON_RET]]
 655 ;
 656 entry:
 657   %c0 = icmp eq i8 %v0, 0
 658   br i1 %c0, label %pred0, label %pred1
 659 pred0:
 660   %c1 = icmp eq i8 %v1, 0
 661   br i1 %c1, label %final_left, label %dispatch
 662 pred1:
 663   %c2 = icmp eq i8 %v2, 0
 664   br i1 %c2, label %dispatch, label %final_right
 665 dispatch:
 666   %v3_adj = add i8 %v1, %v2
 667   %c3 = icmp eq i8 %v3, 0
 668   br i1 %c3, label %final_left, label %final_right
 669 final_left:
 670   %merge_left = phi i8 [ %v3_adj, %dispatch ], [ 0, %pred0 ]
 671   call void @use8(i8 %merge_left)
 672   call void @sideeffect0()
 673   ret void
 674 final_right:
 675   call void @sideeffect1()
 676   ret void
 677 }
 678
 679 define void @two_preds_with_extra_op_externally_used_only_multiuse(i8 %v0, i8 %v1, i8 %v2, i8 %v3) {
 680 ; CHECK-LABEL: @two_preds_with_extra_op_externally_used_only_multiuse(
 681 ; CHECK-NEXT:  entry:
 682 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 683 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 684 ; CHECK:       pred0:
 685 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 686 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 687 ; CHECK:       pred1:
 688 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 689 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V1]], [[V2]]
 690 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
 691 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 692 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 693 ; CHECK:       dispatch:
 694 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V1]], [[V2]]
 695 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
 696 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 697 ; CHECK:       common.ret:
 698 ; CHECK-NEXT:    ret void
 699 ; CHECK:       final_left:
 700 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 701 ; CHECK-NEXT:    [[MERGE_LEFT_2:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 42, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 702 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 703 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT_2]])
 704 ; CHECK-NEXT:    call void @sideeffect0()
 705 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 706 ; CHECK:       final_right:
 707 ; CHECK-NEXT:    call void @sideeffect1()
 708 ; CHECK-NEXT:    br label [[COMMON_RET]]
 709 ;
 710 entry:
 711   %c0 = icmp eq i8 %v0, 0
 712   br i1 %c0, label %pred0, label %pred1
 713 pred0:
 714   %c1 = icmp eq i8 %v1, 0
 715   br i1 %c1, label %final_left, label %dispatch
 716 pred1:
 717   %c2 = icmp eq i8 %v2, 0
 718   br i1 %c2, label %dispatch, label %final_right
 719 dispatch:
 720   %v3_adj = add i8 %v1, %v2
 721   %c3 = icmp eq i8 %v3, 0
 722   br i1 %c3, label %final_left, label %final_right
 723 final_left:
 724   %merge_left = phi i8 [ %v3_adj, %dispatch ], [ 0, %pred0 ]
 725   %merge_left_2 = phi i8 [ %v3_adj, %dispatch ], [ 42, %pred0 ]
 726   call void @use8(i8 %merge_left)
 727   call void @use8(i8 %merge_left_2)
 728   call void @sideeffect0()
 729   ret void
 730 final_right:
 731   call void @sideeffect1()
 732   ret void
 733 }
 734
 735 ; The liveout instruction can be located after the branch condition.
 736 define void @one_pred_with_extra_op_externally_used_only_after_cond_distant_phi(i8 %v0, i8 %v1, i8 %v3, i8 %v4, i8 %v5) {
 737 ; CHECK-LABEL: @one_pred_with_extra_op_externally_used_only_after_cond_distant_phi(
 738 ; CHECK-NEXT:  entry:
 739 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 740 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED:%.*]], label [[LEFT_END:%.*]]
 741 ; CHECK:       pred:
 742 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 743 ; CHECK-NEXT:    br i1 [[C1]], label [[DISPATCH:%.*]], label [[FINAL_RIGHT:%.*]]
 744 ; CHECK:       dispatch:
 745 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
 746 ; CHECK-NEXT:    [[V2_ADJ:%.*]] = add i8 [[V4:%.*]], [[V5:%.*]]
 747 ; CHECK-NEXT:    br i1 [[C3]], label [[FINAL_LEFT:%.*]], label [[FINAL_RIGHT]]
 748 ; CHECK:       final_left:
 749 ; CHECK-NEXT:    call void @sideeffect0()
 750 ; CHECK-NEXT:    call void @use8(i8 [[V2_ADJ]])
 751 ; CHECK-NEXT:    br label [[LEFT_END]]
 752 ; CHECK:       common.ret:
 753 ; CHECK-NEXT:    ret void
 754 ; CHECK:       left_end:
 755 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V2_ADJ]], [[FINAL_LEFT]] ], [ 0, [[ENTRY:%.*]] ]
 756 ; CHECK-NEXT:    call void @sideeffect1()
 757 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 758 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 759 ; CHECK:       final_right:
 760 ; CHECK-NEXT:    call void @sideeffect2()
 761 ; CHECK-NEXT:    br label [[COMMON_RET]]
 762 ;
 763 entry:
 764   %c0 = icmp eq i8 %v0, 0
 765   br i1 %c0, label %pred, label %left_end
 766 pred:
 767   %c1 = icmp eq i8 %v1, 0
 768   br i1 %c1, label %dispatch, label %final_right
 769 dispatch:
 770   %c3 = icmp eq i8 %v3, 0
 771   %v2_adj = add i8 %v4, %v5
 772   br i1 %c3, label %final_left, label %final_right
 773 final_left:
 774   call void @sideeffect0()
 775   call void @use8(i8 %v2_adj)
 776   br label %left_end
 777 left_end:
 778   %merge_left = phi i8 [ %v2_adj, %final_left ], [ 0, %entry ]
 779   call void @sideeffect1()
 780   call void @use8(i8 %merge_left)
 781   ret void
 782 final_right:
 783   call void @sideeffect2()
 784   ret void
 785 }
 786 define void @two_preds_with_extra_op_externally_used_only_after_cond(i8 %v0, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %v5) {
 787 ; CHECK-LABEL: @two_preds_with_extra_op_externally_used_only_after_cond(
 788 ; CHECK-NEXT:  entry:
 789 ; CHECK-NEXT:    [[C0:%.*]] = icmp eq i8 [[V0:%.*]], 0
 790 ; CHECK-NEXT:    br i1 [[C0]], label [[PRED0:%.*]], label [[PRED1:%.*]]
 791 ; CHECK:       pred0:
 792 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[V1:%.*]], 0
 793 ; CHECK-NEXT:    br i1 [[C1]], label [[FINAL_LEFT:%.*]], label [[DISPATCH:%.*]]
 794 ; CHECK:       pred1:
 795 ; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[V2:%.*]], 0
 796 ; CHECK-NEXT:    [[C3:%.*]] = icmp eq i8 [[V3:%.*]], 0
 797 ; CHECK-NEXT:    [[V3_ADJ:%.*]] = add i8 [[V4:%.*]], [[V5:%.*]]
 798 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C2]], i1 [[C3]], i1 false
 799 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FINAL_LEFT]], label [[FINAL_RIGHT:%.*]]
 800 ; CHECK:       dispatch:
 801 ; CHECK-NEXT:    [[C3_OLD:%.*]] = icmp eq i8 [[V3]], 0
 802 ; CHECK-NEXT:    [[V3_ADJ_OLD:%.*]] = add i8 [[V4]], [[V5]]
 803 ; CHECK-NEXT:    br i1 [[C3_OLD]], label [[FINAL_LEFT]], label [[FINAL_RIGHT]]
 804 ; CHECK:       common.ret:
 805 ; CHECK-NEXT:    ret void
 806 ; CHECK:       final_left:
 807 ; CHECK-NEXT:    [[MERGE_LEFT:%.*]] = phi i8 [ [[V3_ADJ_OLD]], [[DISPATCH]] ], [ 0, [[PRED0]] ], [ [[V3_ADJ]], [[PRED1]] ]
 808 ; CHECK-NEXT:    call void @use8(i8 [[MERGE_LEFT]])
 809 ; CHECK-NEXT:    call void @sideeffect0()
 810 ; CHECK-NEXT:    br label [[COMMON_RET:%.*]]
 811 ; CHECK:       final_right:
 812 ; CHECK-NEXT:    call void @sideeffect1()
 813 ; CHECK-NEXT:    br label [[COMMON_RET]]
 814 ;
 815 entry:
 816   %c0 = icmp eq i8 %v0, 0
 817   br i1 %c0, label %pred0, label %pred1
 818 pred0:
 819   %c1 = icmp eq i8 %v1, 0
 820   br i1 %c1, label %final_left, label %dispatch
 821 pred1:
 822   %c2 = icmp eq i8 %v2, 0
 823   br i1 %c2, label %dispatch, label %final_right
 824 dispatch:
 825   %c3 = icmp eq i8 %v3, 0
 826   %v3_adj = add i8 %v4, %v5
 827   br i1 %c3, label %final_left, label %final_right
 828 final_left:
 829   %merge_left = phi i8 [ %v3_adj, %dispatch ], [ 0, %pred0 ]
 830   call void @use8(i8 %merge_left)
 831   call void @sideeffect0()
 832   ret void
 833 final_right:
 834   call void @sideeffect1()
 835   ret void
 836 }
 837
 838 define void @pr48450() {
 839 ; CHECK-LABEL: @pr48450(
 840 ; CHECK-NEXT:  entry:
 841 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 842 ; CHECK:       for.body:
 843 ; CHECK-NEXT:    [[COUNTDOWN:%.*]] = phi i8 [ 8, [[ENTRY:%.*]] ], [ [[DEC:%.*]], [[FOR_BODYTHREAD_PRE_SPLIT:%.*]] ]
 844 ; CHECK-NEXT:    [[C:%.*]] = call i1 @gen1()
 845 ; CHECK-NEXT:    br i1 [[C]], label [[FOR_INC:%.*]], label [[IF_THEN:%.*]]
 846 ; CHECK:       for.inc:
 847 ; CHECK-NEXT:    [[DEC]] = add i8 [[COUNTDOWN]], -1
 848 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[COUNTDOWN]], 0
 849 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END_LOOPEXIT:%.*]], label [[FOR_BODYTHREAD_PRE_SPLIT]]
 850 ; CHECK:       if.then:
 851 ; CHECK-NEXT:    [[C2:%.*]] = call i1 @gen1()
 852 ; CHECK-NEXT:    br i1 [[C2]], label [[FOR_INC]], label [[IF_END_LOOPEXIT]]
 853 ; CHECK:       for.bodythread-pre-split:
 854 ; CHECK-NEXT:    call void @sideeffect0()
 855 ; CHECK-NEXT:    br label [[FOR_BODY]]
 856 ; CHECK:       if.end.loopexit:
 857 ; CHECK-NEXT:    ret void
 858 ;
 859 entry:
 860   br label %for.body
 861
 862 for.body:
 863   %countdown = phi i8 [ 8, %entry ], [ %dec, %for.bodythread-pre-split ]
 864   %c = call i1 @gen1()
 865   br i1 %c, label %for.inc, label %if.then
 866
 867 for.inc:
 868   %dec = add i8 %countdown, -1
 869   %cmp.not = icmp eq i8 %countdown, 0
 870   br i1 %cmp.not, label %if.end.loopexit, label %for.bodythread-pre-split
 871
 872 if.then:
 873   %c2 = call i1 @gen1()
 874   br i1 %c2, label %for.inc, label %if.end.loopexit
 875
 876 for.bodythread-pre-split:
 877   call void @sideeffect0()
 878   br label %for.body
 879
 880 if.end.loopexit:
 881   ret void
 882 }
 883
 884 define void @pr48450_2(i1 %enable_loopback) {
 885 ; CHECK-LABEL: @pr48450_2(
 886 ; CHECK-NEXT:  entry:
 887 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 888 ; CHECK:       for.body:
 889 ; CHECK-NEXT:    [[COUNTDOWN:%.*]] = phi i8 [ 8, [[ENTRY:%.*]] ], [ [[DEC:%.*]], [[FOR_BODYTHREAD_PRE_SPLIT:%.*]] ]
 890 ; CHECK-NEXT:    [[C:%.*]] = call i1 @gen1()
 891 ; CHECK-NEXT:    br i1 [[C]], label [[FOR_INC:%.*]], label [[IF_THEN:%.*]]
 892 ; CHECK:       for.inc:
 893 ; CHECK-NEXT:    [[DEC]] = add i8 [[COUNTDOWN]], -1
 894 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[COUNTDOWN]], 0
 895 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[IF_END_LOOPEXIT:%.*]], label [[FOR_BODYTHREAD_PRE_SPLIT]]
 896 ; CHECK:       if.then:
 897 ; CHECK-NEXT:    [[C2:%.*]] = call i1 @gen1()
 898 ; CHECK-NEXT:    br i1 [[C2]], label [[FOR_INC]], label [[IF_END_LOOPEXIT]]
 899 ; CHECK:       for.bodythread-pre-split:
 900 ; CHECK-NEXT:    [[SHOULD_LOOPBACK:%.*]] = phi i1 [ true, [[FOR_INC]] ], [ false, [[FOR_BODYTHREAD_PRE_SPLIT_LOOPBACK:%.*]] ]
 901 ; CHECK-NEXT:    [[DO_LOOPBACK:%.*]] = and i1 [[SHOULD_LOOPBACK]], [[ENABLE_LOOPBACK:%.*]]
 902 ; CHECK-NEXT:    call void @sideeffect0()
 903 ; CHECK-NEXT:    br i1 [[DO_LOOPBACK]], label [[FOR_BODYTHREAD_PRE_SPLIT_LOOPBACK]], label [[FOR_BODY]]
 904 ; CHECK:       for.bodythread-pre-split.loopback:
 905 ; CHECK-NEXT:    call void @sideeffect0()
 906 ; CHECK-NEXT:    br label [[FOR_BODYTHREAD_PRE_SPLIT]]
 907 ; CHECK:       if.end.loopexit:
 908 ; CHECK-NEXT:    ret void
 909 ;
 910 entry:
 911   br label %for.body
 912
 913 for.body:
 914   %countdown = phi i8 [ 8, %entry ], [ %dec, %for.bodythread-pre-split ]
 915   %c = call i1 @gen1()
 916   br i1 %c, label %for.inc, label %if.then
 917
 918 for.inc:
 919   %dec = add i8 %countdown, -1
 920   %cmp.not = icmp eq i8 %countdown, 0
 921   br i1 %cmp.not, label %if.end.loopexit, label %for.bodythread-pre-split
 922
 923 if.then:
 924   %c2 = call i1 @gen1()
 925   br i1 %c2, label %for.inc, label %if.end.loopexit
 926
 927 for.bodythread-pre-split:
 928   %should_loopback = phi i1 [ 1, %for.inc ], [ 0, %for.bodythread-pre-split.loopback ]
 929   %do_loopback = and i1 %should_loopback, %enable_loopback
 930   call void @sideeffect0()
 931   br i1 %do_loopback, label %for.bodythread-pre-split.loopback, label %for.body
 932
 933 for.bodythread-pre-split.loopback:
 934   call void @sideeffect0()
 935   br label %for.bodythread-pre-split
 936
 937 if.end.loopexit:
 938   ret void
 939 }
 940
 941 @f.b = external global i8, align 1
 942 define void @pr48450_3() {
 943 ; CHECK-LABEL: @pr48450_3(
 944 ; CHECK-NEXT:  entry:
 945 ; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
 946 ; CHECK:       for.cond1:
 947 ; CHECK-NEXT:    [[V:%.*]] = load i8, ptr @f.b, align 1
 948 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[V]], 1
 949 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 950 ; CHECK-NEXT:    br label [[FOR_COND1]]
 951 ;
 952 entry:
 953   br label %for.cond1
 954
 955 for.cond1:
 956   %v = load i8, ptr @f.b, align 1
 957   %cmp = icmp slt i8 %v, 1
 958   br i1 %cmp, label %for.body, label %for.end
 959
 960 for.body:
 961   br label %for.cond1
 962
 963 for.end:
 964   %tobool = icmp ne i8 %v, 0
 965   br i1 %tobool, label %if.then, label %if.end
 966
 967 if.then:
 968   unreachable
 969
 970 if.end:
 971   br label %for.cond2
 972
 973 for.cond2:
 974   %c.0 = phi i8 [ undef, %if.end ], [ %inc, %if.end7 ]
 975   %cmp3 = icmp slt i8 %c.0, 1
 976   br i1 %cmp3, label %for.body4, label %for.cond.cleanup
 977
 978 for.cond.cleanup:
 979   br label %cleanup
 980
 981 for.body4:
 982   br i1 undef, label %if.then6, label %if.end7
 983
 984 if.then6:
 985   br label %cleanup
 986
 987 if.end7:
 988   %inc = add nsw i8 %c.0, 1
 989   br label %for.cond2
 990
 991 cleanup:
 992   unreachable
 993 }
 994
 995 @global_pr49510 = external global i16, align 1
 996
 997 define void @pr49510() {
 998 ; CHECK-LABEL: @pr49510(
 999 ; CHECK-NEXT:  entry:
1000 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
1001 ; CHECK:       for.cond:
1002 ; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr @global_pr49510, align 1
1003 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i16 [[TMP0]], 0
1004 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i16 [[TMP0]], 0
1005 ; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[TOBOOL]], [[CMP]]
1006 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[FOR_COND]], label [[FOR_END:%.*]]
1007 ; CHECK:       for.end:
1008 ; CHECK-NEXT:    ret void
1009 ;
1010 entry:
1011   br label %for.cond
1012
1013 for.cond:
1014   %0 = load i16, ptr @global_pr49510, align 1
1015   %tobool = icmp ne i16 %0, 0
1016   br i1 %tobool, label %land.rhs, label %for.end
1017
1018 land.rhs:
1019   %cmp = icmp slt i16 %0, 0
1020   br i1 %cmp, label %for.cond, label %for.end
1021
1022 for.end:
1023   ret void
1024 }
1025
1026 ; FIXME:
1027 ; This is a miscompile if we replace a phi incoming value
1028 ; with an updated loaded value *after* it was stored.
1029
1030 @global_pr51125 = global i32 1, align 4
1031
1032 define i32 @pr51125() {
1033 ; CHECK-LABEL: @pr51125(
1034 ; CHECK-NEXT:  entry:
1035 ; CHECK-NEXT:    br label [[L:%.*]]
1036 ; CHECK:       L:
1037 ; CHECK-NEXT:    [[LD:%.*]] = load i32, ptr @global_pr51125, align 4
1038 ; CHECK-NEXT:    [[ISZERO:%.*]] = icmp eq i32 [[LD]], 0
1039 ; CHECK-NEXT:    br i1 [[ISZERO]], label [[EXIT:%.*]], label [[L2:%.*]]
1040 ; CHECK:       L2:
1041 ; CHECK-NEXT:    store i32 -1, ptr @global_pr51125, align 4
1042 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[LD]], -1
1043 ; CHECK-NEXT:    br i1 [[CMP]], label [[L]], label [[EXIT]]
1044 ; CHECK:       exit:
1045 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[LD]], [[L2]] ], [ [[LD]], [[L]] ]
1046 ; CHECK-NEXT:    ret i32 [[R]]
1047 ;
1048 entry:
1049   br label %L
1050
1051 L:
1052   %ld = load i32, ptr @global_pr51125, align 4
1053   %iszero = icmp eq i32 %ld, 0
1054   br i1 %iszero, label %exit, label %L2
1055
1056 L2:
1057   store i32 -1, ptr @global_pr51125, align 4
1058   %cmp = icmp eq i32 %ld, -1
1059   br i1 %cmp, label %L, label %exit
1060
1061 exit:
1062   %r = phi i32 [ %ld, %L2 ], [ %ld, %L ]
1063   ret i32 %r
1064 }
1065
1066 ; https://github.com/llvm/llvm-project/issues/53861
1067 define i32 @firewall(ptr %data) {
1068 ; CHECK-LABEL: @firewall(
1069 ; CHECK-NEXT:  entry:
1070 ; CHECK-NEXT:    [[I:%.*]] = load i8, ptr [[DATA:%.*]], align 1
1071 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i8, ptr [[DATA]], i64 64
1072 ; CHECK-NEXT:    [[I2:%.*]] = load i16, ptr [[ADD_PTR]], align 2
1073 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[I]], 17
1074 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i16 [[I2]], 1
1075 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP]], i1 [[CMP3]], i1 false
1076 ; CHECK-NEXT:    [[CMP10:%.*]] = icmp eq i16 [[I2]], 2
1077 ; CHECK-NEXT:    [[OR_COND33:%.*]] = select i1 [[CMP]], i1 [[CMP10]], i1 false
1078 ; CHECK-NEXT:    [[OR_COND1:%.*]] = select i1 [[OR_COND]], i1 true, i1 [[OR_COND33]]
1079 ; CHECK-NEXT:    [[CMP19:%.*]] = icmp eq i16 [[I2]], 3
1080 ; CHECK-NEXT:    [[OR_COND34:%.*]] = select i1 [[CMP]], i1 [[CMP19]], i1 false
1081 ; CHECK-NEXT:    [[OR_COND2:%.*]] = select i1 [[OR_COND1]], i1 true, i1 [[OR_COND34]]
1082 ; CHECK-NEXT:    [[CMP28:%.*]] = icmp eq i16 [[I2]], 4
1083 ; CHECK-NEXT:    [[OR_COND35:%.*]] = select i1 [[CMP]], i1 [[CMP28]], i1 false
1084 ; CHECK-NEXT:    [[DOT:%.*]] = zext i1 [[OR_COND35]] to i32
1085 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND2]], i32 1, i32 [[DOT]]
1086 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
1087 ;
1088 entry:
1089   %i = load i8, ptr %data, align 1
1090   %add.ptr = getelementptr inbounds i8, ptr %data, i64 64
1091   %i2 = load i16, ptr %add.ptr, align 2
1092   %cmp = icmp eq i8 %i, 17
1093   %cmp3 = icmp eq i16 %i2, 1
1094   %or.cond = select i1 %cmp, i1 %cmp3, i1 false
1095   br i1 %or.cond, label %cleanup, label %if.end
1096
1097 if.end:
1098   %cmp10 = icmp eq i16 %i2, 2
1099   %or.cond33 = select i1 %cmp, i1 %cmp10, i1 false
1100   br i1 %or.cond33, label %cleanup, label %if.end13
1101
1102 if.end13:
1103   %cmp19 = icmp eq i16 %i2, 3
1104   %or.cond34 = select i1 %cmp, i1 %cmp19, i1 false
1105   br i1 %or.cond34, label %cleanup, label %if.end22
1106
1107 if.end22:
1108   %cmp28 = icmp eq i16 %i2, 4
1109   %or.cond35 = select i1 %cmp, i1 %cmp28, i1 false
1110   %. = zext i1 %or.cond35 to i32
1111   br label %cleanup
1112
1113 cleanup:
1114   %retval.0 = phi i32 [ 1, %entry ], [ 1, %if.end ], [ 1, %if.end13 ], [ %., %if.end22 ]
1115   ret i32 %retval.0
1116 }
1117
1118 define i32 @test_builtin_fpclassify(float %x) {
1119 ; CHECK-LABEL: @test_builtin_fpclassify(
1120 ; CHECK-NEXT:  entry:
1121 ; CHECK-NEXT:    [[ISZERO:%.*]] = fcmp oeq float [[X:%.*]], 0.000000e+00
1122 ; CHECK-NEXT:    br i1 [[ISZERO]], label [[FPCLASSIFY_END:%.*]], label [[FPCLASSIFY_NOT_ZERO:%.*]]
1123 ; CHECK:       fpclassify_end:
1124 ; CHECK-NEXT:    [[FPCLASSIFY_RESULT:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ 0, [[FPCLASSIFY_NOT_ZERO]] ], [ 1, [[FPCLASSIFY_NOT_NAN:%.*]] ], [ [[NORMAL_OR_SUBNORMAL:%.*]], [[FPCLASSIFY_NOT_INF:%.*]] ]
1125 ; CHECK-NEXT:    ret i32 [[FPCLASSIFY_RESULT]]
1126 ; CHECK:       fpclassify_not_zero:
1127 ; CHECK-NEXT:    [[CMP:%.*]] = fcmp uno float [[X]], 0.000000e+00
1128 ; CHECK-NEXT:    br i1 [[CMP]], label [[FPCLASSIFY_END]], label [[FPCLASSIFY_NOT_NAN]]
1129 ; CHECK:       fpclassify_not_nan:
1130 ; CHECK-NEXT:    [[X_ABS:%.*]] = tail call float @llvm.fabs.f32(float [[X]])
1131 ; CHECK-NEXT:    [[ISINF:%.*]] = fcmp oeq float [[X_ABS]], 0x7FF0000000000000
1132 ; CHECK-NEXT:    br i1 [[ISINF]], label [[FPCLASSIFY_END]], label [[FPCLASSIFY_NOT_INF]]
1133 ; CHECK:       fpclassify_not_inf:
1134 ; CHECK-NEXT:    [[ISNORMAL:%.*]] = fcmp uge float [[X_ABS]], 0x3810000000000000
1135 ; CHECK-NEXT:    [[NORMAL_OR_SUBNORMAL]] = select i1 [[ISNORMAL]], i32 4, i32 3
1136 ; CHECK-NEXT:    br label [[FPCLASSIFY_END]]
1137 ;
1138 entry:
1139   %iszero = fcmp oeq float %x, 0.000000e+00
1140   br i1 %iszero, label %fpclassify_end, label %fpclassify_not_zero
1141
1142 fpclassify_end:
1143   %fpclassify_result = phi i32 [ 2, %entry ], [ 0, %fpclassify_not_zero ], [ 1, %fpclassify_not_nan ], [ %normal_or_subnormal, %fpclassify_not_inf ]
1144   ret i32 %fpclassify_result
1145
1146 fpclassify_not_zero:
1147   %cmp = fcmp uno float %x, 0.000000e+00
1148   br i1 %cmp, label %fpclassify_end, label %fpclassify_not_nan
1149
1150 fpclassify_not_nan:
1151   %x.abs = tail call float @llvm.fabs.f32(float %x)
1152   %isinf = fcmp oeq float %x.abs, 0x7FF0000000000000
1153   br i1 %isinf, label %fpclassify_end, label %fpclassify_not_inf
1154
1155 fpclassify_not_inf:
1156   %isnormal = fcmp uge float %x.abs, 0x3810000000000000
1157   %normal_or_subnormal = select i1 %isnormal, i32 4, i32 3
1158   br label %fpclassify_end
1159 }
1160
1161 declare float @llvm.fabs.f32(float)
1162
1163 attributes #0 = { nounwind argmemonly speculatable }