llvm/test/Transforms/SimplifyCFG/branch-nested.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
   2 ; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
   3
   4 define void @fold_nested_branch(i1 %cond1, i1 %cond2) {
   5 ; CHECK-LABEL: define void @fold_nested_branch(
   6 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
   7 ; CHECK-NEXT:  [[ENTRY:.*:]]
   8 ; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND1]], [[COND2]]
   9 ; CHECK-NEXT:    br i1 [[TMP0]], label %[[BB4:.*]], label %[[BB3:.*]]
  10 ; CHECK:       [[COMMON_RET:.*]]:
  11 ; CHECK-NEXT:    ret void
  12 ; CHECK:       [[BB3]]:
  13 ; CHECK-NEXT:    call void @sideeffect1()
  14 ; CHECK-NEXT:    br label %[[COMMON_RET]]
  15 ; CHECK:       [[BB4]]:
  16 ; CHECK-NEXT:    call void @sideeffect2()
  17 ; CHECK-NEXT:    br label %[[COMMON_RET]]
  18 ;
  19 entry:
  20   br i1 %cond1, label %bb1, label %bb2
  21
  22 bb1:
  23   br i1 %cond2, label %bb3, label %bb4
  24
  25 bb2:
  26   br i1 %cond2, label %bb4, label %bb3
  27
  28 bb3:
  29   call void @sideeffect1()
  30   ret void
  31
  32 bb4:
  33   call void @sideeffect2()
  34   ret void
  35 }
  36
  37 define void @fold_nested_branch_extra_predecessors(i1 %cond0, i1 %cond1, i1 %cond2) {
  38 ; CHECK-LABEL: define void @fold_nested_branch_extra_predecessors(
  39 ; CHECK-SAME: i1 [[COND0:%.*]], i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
  40 ; CHECK-NEXT:  [[ENTRY:.*:]]
  41 ; CHECK-NEXT:    br i1 [[COND0]], label %[[BB0:.*]], label %[[BB1_PRED:.*]]
  42 ; CHECK:       [[BB1_PRED]]:
  43 ; CHECK-NEXT:    call void @sideeffect1()
  44 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB3:.*]], label %[[BB4:.*]]
  45 ; CHECK:       [[BB0]]:
  46 ; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND1]], [[COND2]]
  47 ; CHECK-NEXT:    br i1 [[TMP0]], label %[[BB4]], label %[[BB3]]
  48 ; CHECK:       [[COMMON_RET:.*]]:
  49 ; CHECK-NEXT:    ret void
  50 ; CHECK:       [[BB3]]:
  51 ; CHECK-NEXT:    call void @sideeffect1()
  52 ; CHECK-NEXT:    br label %[[COMMON_RET]]
  53 ; CHECK:       [[BB4]]:
  54 ; CHECK-NEXT:    call void @sideeffect2()
  55 ; CHECK-NEXT:    br label %[[COMMON_RET]]
  56 ;
  57 entry:
  58   br i1 %cond0, label %bb0, label %bb1_pred
  59
  60 bb1_pred:
  61   call void @sideeffect1()
  62   br label %bb1
  63
  64 bb0:
  65   br i1 %cond1, label %bb1, label %bb2
  66
  67 bb1:
  68   br i1 %cond2, label %bb3, label %bb4
  69
  70 bb2:
  71   br i1 %cond2, label %bb4, label %bb3
  72
  73 bb3:
  74   call void @sideeffect1()
  75   ret void
  76
  77 bb4:
  78   call void @sideeffect2()
  79   ret void
  80 }
  81
  82 ; Negative tests
  83
  84 define void @fold_nested_branch_cfg_mismatch(i1 %cond1, i1 %cond2) {
  85 ; CHECK-LABEL: define void @fold_nested_branch_cfg_mismatch(
  86 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
  87 ; CHECK-NEXT:  [[ENTRY:.*:]]
  88 ; CHECK-NEXT:    br i1 [[COND1]], label %[[BB1:.*]], label %[[BB2:.*]]
  89 ; CHECK:       [[BB1]]:
  90 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB3:.*]], label %[[COMMON_RET:.*]]
  91 ; CHECK:       [[BB2]]:
  92 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB4:.*]], label %[[BB3]]
  93 ; CHECK:       [[COMMON_RET]]:
  94 ; CHECK-NEXT:    ret void
  95 ; CHECK:       [[BB3]]:
  96 ; CHECK-NEXT:    call void @sideeffect1()
  97 ; CHECK-NEXT:    br label %[[COMMON_RET]]
  98 ; CHECK:       [[BB4]]:
  99 ; CHECK-NEXT:    call void @sideeffect2()
 100 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 101 ;
 102 entry:
 103   br i1 %cond1, label %bb1, label %bb2
 104
 105 bb1:
 106   br i1 %cond2, label %bb3, label %bb5
 107
 108 bb2:
 109   br i1 %cond2, label %bb4, label %bb3
 110
 111 bb3:
 112   call void @sideeffect1()
 113   ret void
 114
 115 bb4:
 116   call void @sideeffect2()
 117   ret void
 118
 119 bb5:
 120   ret void
 121 }
 122
 123 define void @fold_nested_branch_cond_mismatch(i1 %cond1, i1 %cond2, i1 %cond3) {
 124 ; CHECK-LABEL: define void @fold_nested_branch_cond_mismatch(
 125 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]], i1 [[COND3:%.*]]) {
 126 ; CHECK-NEXT:  [[ENTRY:.*:]]
 127 ; CHECK-NEXT:    br i1 [[COND1]], label %[[BB1:.*]], label %[[BB2:.*]]
 128 ; CHECK:       [[BB1]]:
 129 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB3:.*]], label %[[BB4:.*]]
 130 ; CHECK:       [[BB2]]:
 131 ; CHECK-NEXT:    br i1 [[COND3]], label %[[BB4]], label %[[BB3]]
 132 ; CHECK:       [[COMMON_RET:.*]]:
 133 ; CHECK-NEXT:    ret void
 134 ; CHECK:       [[BB3]]:
 135 ; CHECK-NEXT:    call void @sideeffect1()
 136 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 137 ; CHECK:       [[BB4]]:
 138 ; CHECK-NEXT:    call void @sideeffect2()
 139 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 140 ;
 141 entry:
 142   br i1 %cond1, label %bb1, label %bb2
 143
 144 bb1:
 145   br i1 %cond2, label %bb3, label %bb4
 146
 147 bb2:
 148   br i1 %cond3, label %bb4, label %bb3
 149
 150 bb3:
 151   call void @sideeffect1()
 152   ret void
 153
 154 bb4:
 155   call void @sideeffect2()
 156   ret void
 157 }
 158
 159 define void @fold_nested_branch_non_trivial_succ(i1 %cond1, i1 %cond2) {
 160 ; CHECK-LABEL: define void @fold_nested_branch_non_trivial_succ(
 161 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
 162 ; CHECK-NEXT:  [[ENTRY:.*:]]
 163 ; CHECK-NEXT:    br i1 [[COND1]], label %[[BB1:.*]], label %[[BB2:.*]]
 164 ; CHECK:       [[BB1]]:
 165 ; CHECK-NEXT:    call void @sideeffect1()
 166 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB3:.*]], label %[[BB4:.*]]
 167 ; CHECK:       [[BB2]]:
 168 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB4]], label %[[BB3]]
 169 ; CHECK:       [[COMMON_RET:.*]]:
 170 ; CHECK-NEXT:    ret void
 171 ; CHECK:       [[BB3]]:
 172 ; CHECK-NEXT:    call void @sideeffect1()
 173 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 174 ; CHECK:       [[BB4]]:
 175 ; CHECK-NEXT:    call void @sideeffect2()
 176 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 177 ;
 178 entry:
 179   br i1 %cond1, label %bb1, label %bb2
 180
 181 bb1:
 182   call void @sideeffect1()
 183   br i1 %cond2, label %bb3, label %bb4
 184
 185 bb2:
 186   br i1 %cond2, label %bb4, label %bb3
 187
 188 bb3:
 189   call void @sideeffect1()
 190   ret void
 191
 192 bb4:
 193   call void @sideeffect2()
 194   ret void
 195 }
 196
 197 define i32 @fold_nested_branch_with_phi(i1 %cond1, i1 %cond2, i32 %x) {
 198 ; CHECK-LABEL: define i32 @fold_nested_branch_with_phi(
 199 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]], i32 [[X:%.*]]) {
 200 ; CHECK-NEXT:  [[ENTRY:.*:]]
 201 ; CHECK-NEXT:    br i1 [[COND1]], label %[[BB1:.*]], label %[[BB2:.*]]
 202 ; CHECK:       [[BB1]]:
 203 ; CHECK-NEXT:    br i1 [[COND2]], label %[[COMMON_RET:.*]], label %[[BB4:.*]]
 204 ; CHECK:       [[BB2]]:
 205 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB4]], label %[[COMMON_RET]]
 206 ; CHECK:       [[COMMON_RET]]:
 207 ; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 0, %[[BB4]] ], [ 0, %[[BB1]] ], [ [[X]], %[[BB2]] ]
 208 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
 209 ; CHECK:       [[BB4]]:
 210 ; CHECK-NEXT:    call void @sideeffect2()
 211 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 212 ;
 213 entry:
 214   br i1 %cond1, label %bb1, label %bb2
 215
 216 bb1:
 217   br i1 %cond2, label %bb3, label %bb4
 218
 219 bb2:
 220   br i1 %cond2, label %bb4, label %bb3
 221
 222 bb3:
 223   %ret = phi i32 [ 0, %bb1 ], [ %x, %bb2 ]
 224   ret i32 %ret
 225
 226 bb4:
 227   call void @sideeffect2()
 228   ret i32 0
 229 }
 230
 231 define void @fold_nested_branch_loop1(i1 %cond1, i1 %cond2) {
 232 ; CHECK-LABEL: define void @fold_nested_branch_loop1(
 233 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
 234 ; CHECK-NEXT:  [[ENTRY:.*:]]
 235 ; CHECK-NEXT:    [[COND1_NOT:%.*]] = xor i1 [[COND1]], true
 236 ; CHECK-NEXT:    [[BRMERGE:%.*]] = select i1 [[COND1_NOT]], i1 true, i1 [[COND2]]
 237 ; CHECK-NEXT:    br i1 [[BRMERGE]], label %[[BB3:.*]], label %[[BB4:.*]]
 238 ; CHECK:       [[COMMON_RET:.*]]:
 239 ; CHECK-NEXT:    ret void
 240 ; CHECK:       [[BB3]]:
 241 ; CHECK-NEXT:    call void @sideeffect1()
 242 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 243 ; CHECK:       [[BB4]]:
 244 ; CHECK-NEXT:    call void @sideeffect2()
 245 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 246 ;
 247 entry:
 248   br i1 %cond1, label %bb1, label %bb2
 249
 250 bb1:
 251   br i1 %cond2, label %bb3, label %bb4
 252
 253 bb2:
 254   br i1 %cond2, label %bb1, label %bb3
 255
 256 bb3:
 257   call void @sideeffect1()
 258   ret void
 259
 260 bb4:
 261   call void @sideeffect2()
 262   ret void
 263 }
 264
 265 define void @fold_nested_branch_loop2(i1 %cond1, i1 %cond2) {
 266 ; CHECK-LABEL: define void @fold_nested_branch_loop2(
 267 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
 268 ; CHECK-NEXT:  [[ENTRY:.*:]]
 269 ; CHECK-NEXT:    br label %[[BB0:.*]]
 270 ; CHECK:       [[BB0]]:
 271 ; CHECK-NEXT:    br i1 [[COND1]], label %[[BB1:.*]], label %[[BB2:.*]]
 272 ; CHECK:       [[BB1]]:
 273 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB3:.*]], label %[[BB4:.*]]
 274 ; CHECK:       [[BB2]]:
 275 ; CHECK-NEXT:    br i1 [[COND2]], label %[[BB0]], label %[[BB3]]
 276 ; CHECK:       [[COMMON_RET:.*]]:
 277 ; CHECK-NEXT:    ret void
 278 ; CHECK:       [[BB3]]:
 279 ; CHECK-NEXT:    call void @sideeffect1()
 280 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 281 ; CHECK:       [[BB4]]:
 282 ; CHECK-NEXT:    call void @sideeffect2()
 283 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 284 ;
 285 entry:
 286   br label %bb0
 287
 288 bb0:
 289   br i1 %cond1, label %bb1, label %bb2
 290
 291 bb1:
 292   br i1 %cond2, label %bb3, label %bb4
 293
 294 bb2:
 295   br i1 %cond2, label %bb0, label %bb3
 296
 297 bb3:
 298   call void @sideeffect1()
 299   ret void
 300
 301 bb4:
 302   call void @sideeffect2()
 303   ret void
 304 }
 305
 306 ; Make sure that branch weights are correctly preserved
 307 ; freq(bb4) = 1 * 4 + 2 * 5 = 14
 308 ; freq(bb3) = 1 * 3 + 2 * 6 = 15
 309 define void @fold_nested_branch_prof(i1 %cond1, i1 %cond2) {
 310 ; CHECK-LABEL: define void @fold_nested_branch_prof(
 311 ; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]]) {
 312 ; CHECK-NEXT:  [[ENTRY:.*:]]
 313 ; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[COND1]], [[COND2]]
 314 ; CHECK-NEXT:    br i1 [[TMP0]], label %[[BB4:.*]], label %[[BB3:.*]], !prof [[PROF0:![0-9]+]]
 315 ; CHECK:       [[COMMON_RET:.*]]:
 316 ; CHECK-NEXT:    ret void
 317 ; CHECK:       [[BB3]]:
 318 ; CHECK-NEXT:    call void @sideeffect1()
 319 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 320 ; CHECK:       [[BB4]]:
 321 ; CHECK-NEXT:    call void @sideeffect2()
 322 ; CHECK-NEXT:    br label %[[COMMON_RET]]
 323 ;
 324 entry:
 325   br i1 %cond1, label %bb1, label %bb2, !prof !0 ; 1:2
 326
 327 bb1:
 328   br i1 %cond2, label %bb3, label %bb4, !prof !1 ; 3:4
 329
 330 bb2:
 331   br i1 %cond2, label %bb4, label %bb3, !prof !2 ; 5:6
 332
 333 bb3:
 334   call void @sideeffect1()
 335   ret void
 336
 337 bb4:
 338   call void @sideeffect2()
 339   ret void
 340 }
 341
 342 !0 = !{!"branch_weights", i32 1, i32 2}
 343 !1 = !{!"branch_weights", i32 3, i32 4}
 344 !2 = !{!"branch_weights", i32 5, i32 6}
 345
 346
 347 declare void @sideeffect1()
 348 declare void @sideeffect2()
 349 ;.
 350 ; CHECK: [[PROF0]] = !{!"branch_weights", i32 14, i32 15}
 351 ;.