1; RUN: opt -simplifycfg -S -o - < %s | FileCheck %s 2 3declare void @helper(i32) 4 5define void @test1(i1 %a, i1 %b) { 6; CHECK-LABEL: @test1( 7entry: 8 br i1 %a, label %Y, label %X, !prof !0 9; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !0 10 11X: 12 %c = or i1 %b, false 13 br i1 %c, label %Z, label %Y, !prof !1 14 15Y: 16 call void @helper(i32 0) 17 ret void 18 19Z: 20 call void @helper(i32 1) 21 ret void 22} 23 24define void @test2(i1 %a, i1 %b) { 25; CHECK-LABEL: @test2( 26entry: 27 br i1 %a, label %X, label %Y, !prof !1 28; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !1 29; CHECK-NOT: !prof 30 31X: 32 %c = or i1 %b, false 33 br i1 %c, label %Z, label %Y, !prof !2 34 35Y: 36 call void @helper(i32 0) 37 ret void 38 39Z: 40 call void @helper(i32 1) 41 ret void 42} 43 44define void @test3(i1 %a, i1 %b) { 45; CHECK-LABEL: @test3( 46; CHECK-NOT: !prof 47entry: 48 br i1 %a, label %X, label %Y, !prof !1 49 50X: 51 %c = or i1 %b, false 52 br i1 %c, label %Z, label %Y 53 54Y: 55 call void @helper(i32 0) 56 ret void 57 58Z: 59 call void @helper(i32 1) 60 ret void 61} 62 63define void @test4(i1 %a, i1 %b) { 64; CHECK-LABEL: @test4( 65; CHECK-NOT: !prof 66entry: 67 br i1 %a, label %X, label %Y 68 69X: 70 %c = or i1 %b, false 71 br i1 %c, label %Z, label %Y, !prof !1 72 73Y: 74 call void @helper(i32 0) 75 ret void 76 77Z: 78 call void @helper(i32 1) 79 ret void 80} 81 82;; test5 - The case where it jumps to the default target will be removed. 83define void @test5(i32 %M, i32 %N) nounwind uwtable { 84entry: 85 switch i32 %N, label %sw2 [ 86 i32 1, label %sw2 87 i32 2, label %sw.bb 88 i32 3, label %sw.bb1 89 ], !prof !3 90; CHECK-LABEL: @test5( 91; CHECK: switch i32 %N, label %sw2 [ 92; CHECK: i32 3, label %sw.bb1 93; CHECK: i32 2, label %sw.bb 94; CHECK: ], !prof !2 95 96sw.bb: 97 call void @helper(i32 0) 98 br label %sw.epilog 99 100sw.bb1: 101 call void @helper(i32 1) 102 br label %sw.epilog 103 104sw2: 105 call void @helper(i32 2) 106 br label %sw.epilog 107 108sw.epilog: 109 ret void 110} 111 112;; test6 - Some cases of the second switch are pruned during optimization. 113;; Then the second switch will be converted to a branch, finally, the first 114;; switch and the branch will be merged into a single switch. 115define void @test6(i32 %M, i32 %N) nounwind uwtable { 116entry: 117 switch i32 %N, label %sw2 [ 118 i32 1, label %sw2 119 i32 2, label %sw.bb 120 i32 3, label %sw.bb1 121 ], !prof !4 122; CHECK-LABEL: @test6( 123; CHECK: switch i32 %N, label %sw.epilog 124; CHECK: i32 3, label %sw.bb1 125; CHECK: i32 2, label %sw.bb 126; CHECK: i32 4, label %sw.bb5 127; CHECK: ], !prof !3 128 129sw.bb: 130 call void @helper(i32 0) 131 br label %sw.epilog 132 133sw.bb1: 134 call void @helper(i32 1) 135 br label %sw.epilog 136 137sw2: 138;; Here "case 2" is invalidated since the default case of the first switch 139;; does not include "case 2". 140 switch i32 %N, label %sw.epilog [ 141 i32 2, label %sw.bb4 142 i32 4, label %sw.bb5 143 ], !prof !5 144 145sw.bb4: 146 call void @helper(i32 2) 147 br label %sw.epilog 148 149sw.bb5: 150 call void @helper(i32 3) 151 br label %sw.epilog 152 153sw.epilog: 154 ret void 155} 156 157;; This test is based on test1 but swapped the targets of the second branch. 158define void @test1_swap(i1 %a, i1 %b) { 159; CHECK-LABEL: @test1_swap( 160entry: 161 br i1 %a, label %Y, label %X, !prof !0 162; CHECK: br i1 %or.cond, label %Y, label %Z, !prof !4 163 164X: 165 %c = or i1 %b, false 166 br i1 %c, label %Y, label %Z, !prof !1 167 168Y: 169 call void @helper(i32 0) 170 ret void 171 172Z: 173 call void @helper(i32 1) 174 ret void 175} 176 177define void @test7(i1 %a, i1 %b) { 178; CHECK-LABEL: @test7( 179entry: 180 %c = or i1 %b, false 181 br i1 %a, label %Y, label %X, !prof !0 182; CHECK: br i1 %brmerge, label %Y, label %Z, !prof !5 183 184X: 185 br i1 %c, label %Y, label %Z, !prof !6 186 187Y: 188 call void @helper(i32 0) 189 ret void 190 191Z: 192 call void @helper(i32 1) 193 ret void 194} 195 196; Test basic folding to a conditional branch. 197define void @test8(i64 %x, i64 %y) nounwind { 198; CHECK-LABEL: @test8( 199entry: 200 %lt = icmp slt i64 %x, %y 201; CHECK: br i1 %lt, label %a, label %b, !prof !6 202 %qux = select i1 %lt, i32 0, i32 2 203 switch i32 %qux, label %bees [ 204 i32 0, label %a 205 i32 1, label %b 206 i32 2, label %b 207 ], !prof !7 208a: 209 call void @helper(i32 0) nounwind 210 ret void 211b: 212 call void @helper(i32 1) nounwind 213 ret void 214bees: 215 call void @helper(i32 2) nounwind 216 ret void 217} 218 219; Test edge splitting when the default target has icmp and unconditinal 220; branch 221define i1 @test9(i32 %x, i32 %y) nounwind { 222; CHECK-LABEL: @test9( 223entry: 224 switch i32 %x, label %bees [ 225 i32 0, label %a 226 i32 1, label %end 227 i32 2, label %end 228 ], !prof !7 229; CHECK: switch i32 %x, label %bees [ 230; CHECK: i32 0, label %a 231; CHECK: i32 1, label %end 232; CHECK: i32 2, label %end 233; CHECK: i32 92, label %end 234; CHECK: ], !prof !7 235 236a: 237 call void @helper(i32 0) nounwind 238 %reta = icmp slt i32 %x, %y 239 ret i1 %reta 240 241bees: 242 %tmp = icmp eq i32 %x, 92 243 br label %end 244 245end: 246; CHECK: end: 247; CHECK: %ret = phi i1 [ true, %entry ], [ false, %bees ], [ true, %entry ], [ true, %entry ] 248 %ret = phi i1 [ true, %entry ], [%tmp, %bees], [true, %entry] 249 call void @helper(i32 2) nounwind 250 ret i1 %ret 251} 252 253define void @test10(i32 %x) nounwind readnone ssp noredzone { 254entry: 255 switch i32 %x, label %lor.rhs [ 256 i32 2, label %lor.end 257 i32 1, label %lor.end 258 i32 3, label %lor.end 259 ], !prof !7 260 261lor.rhs: 262 call void @helper(i32 1) nounwind 263 ret void 264 265lor.end: 266 call void @helper(i32 0) nounwind 267 ret void 268 269; CHECK-LABEL: @test10( 270; CHECK: %x.off = add i32 %x, -1 271; CHECK: %switch = icmp ult i32 %x.off, 3 272; CHECK: br i1 %switch, label %lor.end, label %lor.rhs, !prof !8 273} 274 275; Remove dead cases from the switch. 276define void @test11(i32 %x) nounwind { 277 %i = shl i32 %x, 1 278 switch i32 %i, label %a [ 279 i32 21, label %b 280 i32 24, label %c 281 ], !prof !8 282; CHECK-LABEL: @test11( 283; CHECK: %cond = icmp eq i32 %i, 24 284; CHECK: br i1 %cond, label %c, label %a, !prof !9 285 286a: 287 call void @helper(i32 0) nounwind 288 ret void 289b: 290 call void @helper(i32 1) nounwind 291 ret void 292c: 293 call void @helper(i32 2) nounwind 294 ret void 295} 296 297;; test12 - Don't crash if the whole switch is removed 298define void @test12(i32 %M, i32 %N) nounwind uwtable { 299entry: 300 switch i32 %N, label %sw.bb [ 301 i32 1, label %sw.bb 302 ], !prof !9 303; CHECK-LABEL: @test12( 304; CHECK-NEXT: entry: 305; CHECK-NEXT: call void @helper 306; CHECK-NEXT: ret void 307 308sw.bb: 309 call void @helper(i32 0) 310 br label %sw.epilog 311 312sw.epilog: 313 ret void 314} 315 316;; If every case is dead, make sure they are all removed. This used to 317;; crash trying to merge the metadata. 318define void @test13(i32 %x) nounwind { 319entry: 320 %i = shl i32 %x, 1 321 switch i32 %i, label %a [ 322 i32 21, label %b 323 i32 25, label %c 324 ], !prof !8 325; CHECK-LABEL: @test13( 326; CHECK-NEXT: entry: 327; CHECK-NEXT: call void @helper 328; CHECK-NEXT: ret void 329 330a: 331 call void @helper(i32 0) nounwind 332 ret void 333b: 334 call void @helper(i32 1) nounwind 335 ret void 336c: 337 call void @helper(i32 2) nounwind 338 ret void 339} 340 341;; When folding branches to common destination, the updated branch weights 342;; can exceed uint32 by more than factor of 2. We should keep halving the 343;; weights until they can fit into uint32. 344@max_regno = common global i32 0, align 4 345define void @test14(i32* %old, i32 %final) { 346; CHECK-LABEL: @test14 347; CHECK: br i1 %or.cond, label %for.exit, label %for.inc, !prof !10 348for.cond: 349 br label %for.cond2 350for.cond2: 351 %i.1 = phi i32 [ %inc19, %for.inc ], [ 0, %for.cond ] 352 %bit.0 = phi i32 [ %shl, %for.inc ], [ 1, %for.cond ] 353 %tobool = icmp eq i32 %bit.0, 0 354 br i1 %tobool, label %for.exit, label %for.body3, !prof !10 355for.body3: 356 %v3 = load i32* @max_regno, align 4 357 %cmp4 = icmp eq i32 %i.1, %v3 358 br i1 %cmp4, label %for.exit, label %for.inc, !prof !11 359for.inc: 360 %shl = shl i32 %bit.0, 1 361 %inc19 = add nsw i32 %i.1, 1 362 br label %for.cond2 363for.exit: 364 ret void 365} 366 367!0 = metadata !{metadata !"branch_weights", i32 3, i32 5} 368!1 = metadata !{metadata !"branch_weights", i32 1, i32 1} 369!2 = metadata !{metadata !"branch_weights", i32 1, i32 2} 370!3 = metadata !{metadata !"branch_weights", i32 4, i32 3, i32 2, i32 1} 371!4 = metadata !{metadata !"branch_weights", i32 4, i32 3, i32 2, i32 1} 372!5 = metadata !{metadata !"branch_weights", i32 7, i32 6, i32 5} 373!6 = metadata !{metadata !"branch_weights", i32 1, i32 3} 374!7 = metadata !{metadata !"branch_weights", i32 33, i32 9, i32 8, i32 7} 375!8 = metadata !{metadata !"branch_weights", i32 33, i32 9, i32 8} 376!9 = metadata !{metadata !"branch_weights", i32 7, i32 6} 377!10 = metadata !{metadata !"branch_weights", i32 672646, i32 21604207} 378!11 = metadata !{metadata !"branch_weights", i32 6960, i32 21597248} 379 380; CHECK: !0 = metadata !{metadata !"branch_weights", i32 5, i32 11} 381; CHECK: !1 = metadata !{metadata !"branch_weights", i32 1, i32 5} 382; CHECK: !2 = metadata !{metadata !"branch_weights", i32 7, i32 1, i32 2} 383; CHECK: !3 = metadata !{metadata !"branch_weights", i32 49, i32 12, i32 24, i32 35} 384; CHECK: !4 = metadata !{metadata !"branch_weights", i32 11, i32 5} 385; CHECK: !5 = metadata !{metadata !"branch_weights", i32 17, i32 15} 386; CHECK: !6 = metadata !{metadata !"branch_weights", i32 9, i32 7} 387; CHECK: !7 = metadata !{metadata !"branch_weights", i32 17, i32 9, i32 8, i32 7, i32 17} 388; CHECK: !8 = metadata !{metadata !"branch_weights", i32 24, i32 33} 389; CHECK: !9 = metadata !{metadata !"branch_weights", i32 8, i32 33} 390;; The false weight prints out as a negative integer here, but inside llvm, we 391;; treat the weight as an unsigned integer. 392; CHECK: !10 = metadata !{metadata !"branch_weights", i32 112017436, i32 -735157296} 393