1; Test the static branch probability heuristics for no-return functions. 2; RUN: opt < %s -analyze -branch-prob -enable-new-pm=0 | FileCheck %s 3; RUN: opt < %s -passes='print<branch-prob>' --disable-output 2>&1 | FileCheck %s 4 5declare void @g1() 6declare void @g2() 7declare void @g3() 8declare void @g4() 9declare i32 @g5() 10 11define void @test1(i32 %a, i32 %b) { 12entry: 13 br label %do.body 14; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 15 16do.body: 17 %i.0 = phi i32 [ 0, %entry ], [ %inc3, %do.end ] 18 call void @g1() 19 br label %do.body1 20; CHECK: edge do.body -> do.body1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 21 22do.body1: 23 %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.body1 ] 24 call void @g2() 25 %inc = add nsw i32 %j.0, 1 26 %cmp = icmp slt i32 %inc, %b 27 br i1 %cmp, label %do.body1, label %do.end 28; CHECK: edge do.body1 -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 29; CHECK: edge do.body1 -> do.end probability is 0x04000000 / 0x80000000 = 3.12% 30 31do.end: 32 call void @g3() 33 %inc3 = add nsw i32 %i.0, 1 34 %cmp4 = icmp slt i32 %inc3, %a 35 br i1 %cmp4, label %do.body, label %do.end5 36; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 37; CHECK: edge do.end -> do.end5 probability is 0x04000000 / 0x80000000 = 3.12% 38 39do.end5: 40 call void @g4() 41 ret void 42} 43 44define void @test2(i32 %a, i32 %b) { 45entry: 46 %cmp9 = icmp sgt i32 %a, 0 47 br i1 %cmp9, label %for.body.lr.ph, label %for.end6 48; CHECK: edge entry -> for.body.lr.ph probability is 0x50000000 / 0x80000000 = 62.50% 49; CHECK: edge entry -> for.end6 probability is 0x30000000 / 0x80000000 = 37.50% 50 51for.body.lr.ph: 52 %cmp27 = icmp sgt i32 %b, 0 53 br label %for.body 54; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 55 56for.body: 57 %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc5, %for.end ] 58 call void @g1() 59 br i1 %cmp27, label %for.body3, label %for.end 60; CHECK: edge for.body -> for.body3 probability is 0x50000000 / 0x80000000 = 62.50% 61; CHECK: edge for.body -> for.end probability is 0x30000000 / 0x80000000 = 37.50% 62 63for.body3: 64 %j.08 = phi i32 [ %inc, %for.body3 ], [ 0, %for.body ] 65 call void @g2() 66 %inc = add nsw i32 %j.08, 1 67 %exitcond = icmp eq i32 %inc, %b 68 br i1 %exitcond, label %for.end, label %for.body3 69; CHECK: edge for.body3 -> for.end probability is 0x04000000 / 0x80000000 = 3.12% 70; CHECK: edge for.body3 -> for.body3 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 71 72for.end: 73 call void @g3() 74 %inc5 = add nsw i32 %i.010, 1 75 %exitcond11 = icmp eq i32 %inc5, %a 76 br i1 %exitcond11, label %for.end6, label %for.body 77; CHECK: edge for.end -> for.end6 probability is 0x04000000 / 0x80000000 = 3.12% 78; CHECK: edge for.end -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 79 80for.end6: 81 call void @g4() 82 ret void 83} 84 85define void @test3(i32 %a, i32 %b, i32* %c) { 86entry: 87 br label %do.body 88; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 89 90do.body: 91 %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ] 92 call void @g1() 93 %0 = load i32, i32* %c, align 4 94 %cmp = icmp slt i32 %0, 42 95 br i1 %cmp, label %do.body1, label %if.end 96; CHECK: edge do.body -> do.body1 probability is 0x40000000 / 0x80000000 = 50.00% 97; CHECK: edge do.body -> if.end probability is 0x40000000 / 0x80000000 = 50.00% 98 99do.body1: 100 %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ] 101 call void @g2() 102 %inc = add nsw i32 %j.0, 1 103 %cmp2 = icmp slt i32 %inc, %b 104 br i1 %cmp2, label %do.body1, label %if.end 105; CHECK: edge do.body1 -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 106; CHECK: edge do.body1 -> if.end probability is 0x04000000 / 0x80000000 = 3.12% 107 108if.end: 109 call void @g3() 110 %inc4 = add nsw i32 %i.0, 1 111 %cmp5 = icmp slt i32 %inc4, %a 112 br i1 %cmp5, label %do.body, label %do.end6 113; CHECK: edge if.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 114; CHECK: edge if.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12% 115 116do.end6: 117 call void @g4() 118 ret void 119} 120 121define void @test4(i32 %a, i32 %b, i32* %c) { 122entry: 123 br label %do.body 124; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 125 126do.body: 127 %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ] 128 call void @g1() 129 %0 = load i32, i32* %c, align 4 130 %cmp = icmp slt i32 %0, 42 131 br i1 %cmp, label %return, label %do.body1 132; CHECK: edge do.body -> return probability is 0x04000000 / 0x80000000 = 3.12% 133; CHECK: edge do.body -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 134 135do.body1: 136 %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ] 137 call void @g2() 138 %inc = add nsw i32 %j.0, 1 139 %cmp2 = icmp slt i32 %inc, %b 140 br i1 %cmp2, label %do.body1, label %do.end 141; CHECK: edge do.body1 -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 142; CHECK: edge do.body1 -> do.end probability is 0x04000000 / 0x80000000 = 3.12% 143 144do.end: 145 call void @g3() 146 %inc4 = add nsw i32 %i.0, 1 147 %cmp5 = icmp slt i32 %inc4, %a 148 br i1 %cmp5, label %do.body, label %do.end6 149; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 150; CHECK: edge do.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12% 151 152do.end6: 153 call void @g4() 154 br label %return 155; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 156 157return: 158 ret void 159} 160 161define void @test5(i32 %a, i32 %b, i32* %c) { 162entry: 163 br label %do.body 164; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 165 166do.body: 167 %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ] 168 call void @g1() 169 br label %do.body1 170; CHECK: edge do.body -> do.body1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 171 172do.body1: 173 %j.0 = phi i32 [ 0, %do.body ], [ %inc, %if.end ] 174 %0 = load i32, i32* %c, align 4 175 %cmp = icmp slt i32 %0, 42 176 br i1 %cmp, label %return, label %if.end 177; CHECK: edge do.body1 -> return probability is 0x04000000 / 0x80000000 = 3.12% 178; CHECK: edge do.body1 -> if.end probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 179 180if.end: 181 call void @g2() 182 %inc = add nsw i32 %j.0, 1 183 %cmp2 = icmp slt i32 %inc, %b 184 br i1 %cmp2, label %do.body1, label %do.end 185; CHECK: edge if.end -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 186; CHECK: edge if.end -> do.end probability is 0x04000000 / 0x80000000 = 3.12% 187 188do.end: 189 call void @g3() 190 %inc4 = add nsw i32 %i.0, 1 191 %cmp5 = icmp slt i32 %inc4, %a 192 br i1 %cmp5, label %do.body, label %do.end6 193; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 194; CHECK: edge do.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12% 195 196do.end6: 197 call void @g4() 198 br label %return 199; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 200 201return: 202 ret void 203} 204 205define void @test6(i32 %a, i32 %b, i32* %c) { 206entry: 207 br label %do.body 208; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 209 210do.body: 211 %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ] 212 call void @g1() 213 br label %do.body1 214; CHECK: edge do.body -> do.body1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 215 216do.body1: 217 %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ] 218 call void @g2() 219 %0 = load i32, i32* %c, align 4 220 %cmp = icmp slt i32 %0, 42 221 br i1 %cmp, label %return, label %do.cond 222; CHECK: edge do.body1 -> return probability is 0x04000000 / 0x80000000 = 3.12% 223; CHECK: edge do.body1 -> do.cond probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 224 225do.cond: 226 %inc = add nsw i32 %j.0, 1 227 %cmp2 = icmp slt i32 %inc, %b 228 br i1 %cmp2, label %do.body1, label %do.end 229; CHECK: edge do.cond -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 230; CHECK: edge do.cond -> do.end probability is 0x04000000 / 0x80000000 = 3.12% 231 232do.end: 233 call void @g3() 234 %inc4 = add nsw i32 %i.0, 1 235 %cmp5 = icmp slt i32 %inc4, %a 236 br i1 %cmp5, label %do.body, label %do.end6 237; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 238; CHECK: edge do.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12% 239 240do.end6: 241 call void @g4() 242 br label %return 243; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 244 245return: 246 ret void 247} 248 249define void @test7(i32 %a, i32 %b, i32* %c) { 250entry: 251 %cmp10 = icmp sgt i32 %a, 0 252 br i1 %cmp10, label %for.body.lr.ph, label %for.end7 253; CHECK: edge entry -> for.body.lr.ph probability is 0x50000000 / 0x80000000 = 62.50% 254; CHECK: edge entry -> for.end7 probability is 0x30000000 / 0x80000000 = 37.50% 255 256for.body.lr.ph: 257 %cmp38 = icmp sgt i32 %b, 0 258 br label %for.body 259; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 260 261for.body: 262 %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc6, %for.inc5 ] 263 %0 = load i32, i32* %c, align 4 264 %cmp1 = icmp eq i32 %0, %i.011 265 br i1 %cmp1, label %for.inc5, label %if.end 266; CHECK: edge for.body -> for.inc5 probability is 0x40000000 / 0x80000000 = 50.00% 267; CHECK: edge for.body -> if.end probability is 0x40000000 / 0x80000000 = 50.00% 268 269if.end: 270 call void @g1() 271 br i1 %cmp38, label %for.body4, label %for.end 272; CHECK: edge if.end -> for.body4 probability is 0x50000000 / 0x80000000 = 62.50% 273; CHECK: edge if.end -> for.end probability is 0x30000000 / 0x80000000 = 37.50% 274 275for.body4: 276 %j.09 = phi i32 [ %inc, %for.body4 ], [ 0, %if.end ] 277 call void @g2() 278 %inc = add nsw i32 %j.09, 1 279 %exitcond = icmp eq i32 %inc, %b 280 br i1 %exitcond, label %for.end, label %for.body4 281; CHECK: edge for.body4 -> for.end probability is 0x04000000 / 0x80000000 = 3.12% 282; CHECK: edge for.body4 -> for.body4 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 283 284for.end: 285 call void @g3() 286 br label %for.inc5 287; CHECK: edge for.end -> for.inc5 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 288 289for.inc5: 290 %inc6 = add nsw i32 %i.011, 1 291 %exitcond12 = icmp eq i32 %inc6, %a 292 br i1 %exitcond12, label %for.end7, label %for.body 293; CHECK: edge for.inc5 -> for.end7 probability is 0x04000000 / 0x80000000 = 3.12% 294; CHECK: edge for.inc5 -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 295 296for.end7: 297 call void @g4() 298 ret void 299} 300 301define void @test8(i32 %a, i32 %b, i32* %c) { 302entry: 303 %cmp18 = icmp sgt i32 %a, 0 304 br i1 %cmp18, label %for.body.lr.ph, label %for.end15 305; CHECK: edge entry -> for.body.lr.ph probability is 0x50000000 / 0x80000000 = 62.50% 306; CHECK: edge entry -> for.end15 probability is 0x30000000 / 0x80000000 = 37.50% 307 308for.body.lr.ph: 309 %cmp216 = icmp sgt i32 %b, 0 310 %arrayidx5 = getelementptr inbounds i32, i32* %c, i64 1 311 %arrayidx9 = getelementptr inbounds i32, i32* %c, i64 2 312 br label %for.body 313; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 314 315for.body: 316 %i.019 = phi i32 [ 0, %for.body.lr.ph ], [ %inc14, %for.end ] 317 call void @g1() 318 br i1 %cmp216, label %for.body3, label %for.end 319; CHECK: edge for.body -> for.body3 probability is 0x50000000 / 0x80000000 = 62.50% 320; CHECK: edge for.body -> for.end probability is 0x30000000 / 0x80000000 = 37.50% 321 322for.body3: 323 %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] 324 %0 = load i32, i32* %c, align 4 325 %cmp4 = icmp eq i32 %0, %j.017 326 br i1 %cmp4, label %for.inc, label %if.end 327; CHECK: edge for.body3 -> for.inc probability is 0x40000000 / 0x80000000 = 50.00% 328; CHECK: edge for.body3 -> if.end probability is 0x40000000 / 0x80000000 = 50.00% 329 330if.end: 331 %1 = load i32, i32* %arrayidx5, align 4 332 %cmp6 = icmp eq i32 %1, %j.017 333 br i1 %cmp6, label %for.inc, label %if.end8 334; CHECK: edge if.end -> for.inc probability is 0x40000000 / 0x80000000 = 50.00% 335; CHECK: edge if.end -> if.end8 probability is 0x40000000 / 0x80000000 = 50.00% 336 337if.end8: 338 %2 = load i32, i32* %arrayidx9, align 4 339 %cmp10 = icmp eq i32 %2, %j.017 340 br i1 %cmp10, label %for.inc, label %if.end12 341; CHECK: edge if.end8 -> for.inc probability is 0x40000000 / 0x80000000 = 50.00% 342; CHECK: edge if.end8 -> if.end12 probability is 0x40000000 / 0x80000000 = 50.00% 343 344if.end12: 345 call void @g2() 346 br label %for.inc 347; CHECK: edge if.end12 -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 348 349for.inc: 350 %inc = add nsw i32 %j.017, 1 351 %exitcond = icmp eq i32 %inc, %b 352 br i1 %exitcond, label %for.end, label %for.body3 353; CHECK: edge for.inc -> for.end probability is 0x04000000 / 0x80000000 = 3.12% 354; CHECK: edge for.inc -> for.body3 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 355 356for.end: 357 call void @g3() 358 %inc14 = add nsw i32 %i.019, 1 359 %exitcond20 = icmp eq i32 %inc14, %a 360 br i1 %exitcond20, label %for.end15, label %for.body 361; CHECK: edge for.end -> for.end15 probability is 0x04000000 / 0x80000000 = 3.12% 362; CHECK: edge for.end -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 363 364for.end15: 365 call void @g4() 366 ret void 367} 368 369; Test that an irreducible loop gets heavily weighted back-edges. 370define void @test9(i32 %i, i32 %x, i32 %c) { 371entry: 372 %tobool = icmp eq i32 %c, 0 373 br i1 %tobool, label %if.end, label %midloop 374; CHECK: edge entry -> if.end probability is 0x30000000 / 0x80000000 = 37.50% 375; CHECK: edge entry -> midloop probability is 0x50000000 / 0x80000000 = 62.50% 376 377if.end: 378 br label %for.cond 379; CHECK: edge if.end -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 380 381for.cond: 382 %i.addr.0 = phi i32 [ %inc, %for.inc ], [ 0, %if.end ] 383 %cmp = icmp slt i32 %i.addr.0, %x 384 br i1 %cmp, label %midloop, label %end 385; CHECK: edge for.cond -> midloop probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 386; CHECK: edge for.cond -> end probability is 0x04000000 / 0x80000000 = 3.12% 387 388midloop: 389 %i.addr.1 = phi i32 [ %i, %entry ], [ %i.addr.0, %for.cond ] 390 %call1 = call i32 @g5() 391 %tobool2 = icmp eq i32 %call1, 0 392 br i1 %tobool2, label %for.inc, label %end 393; CHECK: edge midloop -> for.inc probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 394; CHECK: edge midloop -> end probability is 0x04000000 / 0x80000000 = 3.12% 395 396for.inc: 397 %inc = add nsw i32 %i.addr.1, 1 398 br label %for.cond 399; CHECK: edge for.inc -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 400 401end: 402 ret void 403} 404 405; Check that the for.body -> if.then edge is considered unlikely due to making 406; the if-condition false for the next iteration of the loop. 407define i32 @test10(i32 %n, i32* %p) { 408entry: 409 br label %for.cond 410; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 411 412for.cond: 413 %count.0 = phi i32 [ 0, %entry ], [ %count.1, %for.inc ] 414 %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ] 415 %i.0 = phi i32 [ 0, %entry ], [ %inc3, %for.inc ] 416 %cmp = icmp slt i32 %i.0, %n 417 br i1 %cmp, label %for.body, label %for.cond.cleanup 418; CHECK: edge for.cond -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 419; CHECK: edge for.cond -> for.cond.cleanup probability is 0x04000000 / 0x80000000 = 3.12% 420 421for.cond.cleanup: 422 ret i32 %sum.0 423 424for.body: 425 %arrayidx = getelementptr inbounds i32, i32* %p, i32 %i.0 426 %0 = load i32, i32* %arrayidx, align 4 427 %add = add nsw i32 %sum.0, %0 428 %inc = add nsw i32 %count.0, 1 429 %cmp1 = icmp sgt i32 %count.0, 6 430 br i1 %cmp1, label %if.then, label %for.inc 431; CHECK: edge for.body -> if.then probability is 0x2aaaa8e4 / 0x80000000 = 33.33% 432; CHECK: edge for.body -> for.inc probability is 0x5555571c / 0x80000000 = 66.67% 433if.then: 434 store i32 %add, i32* %arrayidx, align 4 435 br label %for.inc 436; CHECK: edge if.then -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 437 438for.inc: 439 %count.1 = phi i32 [ 0, %if.then ], [ %inc, %for.body ] 440 %sum.1 = phi i32 [ 0, %if.then ], [ %add, %for.body ] 441 %inc3 = add nsw i32 %i.0, 1 442 br label %for.cond 443; CHECK: edge for.inc -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 444} 445 446; Each successor to for.body makes itself not be taken in the next iteration, so 447; both should be equally likely 448define i32 @test11(i32 %n, i32* %p) { 449entry: 450 br label %for.cond 451; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 452 453for.cond: 454 %flip.0 = phi i32 [ 0, %entry ], [ %flip.1, %for.inc ] 455 %sum.0 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ] 456 %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] 457 %cmp = icmp slt i32 %i.0, %n 458 br i1 %cmp, label %for.body, label %for.cond.cleanup 459; CHECK: edge for.cond -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 460; CHECK: edge for.cond -> for.cond.cleanup probability is 0x04000000 / 0x80000000 = 3.12% 461 462for.cond.cleanup: 463 ret i32 %sum.0 464 465for.body: 466 %tobool = icmp eq i32 %flip.0, 0 467 %arrayidx1 = getelementptr inbounds i32, i32* %p, i32 %i.0 468 %0 = load i32, i32* %arrayidx1, align 4 469 br i1 %tobool, label %if.else, label %if.then 470; CHECK: edge for.body -> if.else probability is 0x40000000 / 0x80000000 = 50.00% 471; CHECK: edge for.body -> if.then probability is 0x40000000 / 0x80000000 = 50.00% 472 473if.then: 474 %add = add nsw i32 %0, %sum.0 475 store i32 %add, i32* %arrayidx1, align 4 476 br label %for.inc 477; CHECK: edge if.then -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 478 479if.else: 480 %add2 = add nsw i32 %sum.0, %0 481 br label %for.inc 482; CHECK: edge if.else -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 483 484for.inc: 485 %flip.1 = phi i32 [ 0, %if.then ], [ 1, %if.else ] 486 %sum.1 = phi i32 [ %sum.0, %if.then ], [ %add2, %if.else ] 487 %inc = add nsw i32 %i.0, 1 488 br label %for.cond 489; CHECK: edge for.inc -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 490} 491 492; The loop heuristic should not overwrite the invoke heuristic. The unwind destination 493; of an invoke should be considered VERY rare even in a loop. 494define void @test12(i32 %a) personality i8 0 { 495entry: 496 br label %loop 497; CHECK: edge entry -> loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 498 499loop: 500 %i.0 = phi i32 [ 0, %entry ], [ %inc, %invoke.cont ] 501 invoke i32 @InvokeCall() 502 to label %invoke.cont unwind label %lpad 503; CHECK: edge loop -> invoke.cont probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge] 504; CHECK: edge loop -> lpad probability is 0x00000800 / 0x80000000 = 0.00% 505 506invoke.cont: 507 %inc = add nsw i32 %i.0, 1 508 %cmp = icmp slt i32 %inc, %a 509 br i1 %cmp, label %loop, label %exit 510; CHECK: edge invoke.cont -> loop probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 511; CHECK: edge invoke.cont -> exit probability is 0x04000000 / 0x80000000 = 3.12% 512 513lpad: 514 %ll = landingpad { i8*, i32 } 515 cleanup 516 br label %exit 517 518exit: 519 ret void 520} 521 522declare i32 @InvokeCall() 523declare void @cold() cold 524 525; If loop has single exit and it leads to 'cold' block then edge leading to loop enter 526; should be considered 'cold' as well. 527define void @test13() { 528; CHECK: edge entry -> loop probability is 0x078780e3 / 0x80000000 = 5.88% 529; CHECK: edge entry -> exit probability is 0x78787f1d / 0x80000000 = 94.12% [HOT edge] 530; CHECK: edge loop -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge] 531; CHECK: edge loop -> cold probability is 0x0041edfd / 0x80000000 = 0.20% 532; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 533 534entry: 535 br i1 undef, label %loop, label %exit 536 537loop: 538 %i.0 = phi i32 [ 0, %entry ], [ %inc, %loop ] 539 %inc = add nsw i32 %i.0, 1 540 br i1 undef, label %loop, label %cold 541 542cold: 543 call void @cold() 544 br label %exit 545 546exit: 547 ret void 548} 549 550; This is the same case as test13 but with additional loop 'preheader' block. 551define void @test14() { 552; CHECK: edge entry -> preheader probability is 0x078780e3 / 0x80000000 = 5.88% 553; CHECK: edge entry -> exit probability is 0x78787f1d / 0x80000000 = 94.12% [HOT edge] 554; CHECK: edge preheader -> loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 555; CHECK: edge loop -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge] 556; CHECK: edge loop -> cold probability is 0x0041edfd / 0x80000000 = 0.20% 557; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 558 559entry: 560 br i1 undef, label %preheader, label %exit 561 562preheader: 563 br label %loop 564 565loop: 566 %i.0 = phi i32 [ 0, %preheader ], [ %inc, %loop ] 567 %inc = add nsw i32 %i.0, 1 568 br i1 undef, label %loop, label %cold 569 570cold: 571 call void @cold() 572 br label %exit 573 574exit: 575 ret void 576} 577 578; If loop has multiple low probability exits then edge leading to loop enter 579; should be considered low probable as well. 580define void @test15() { 581; CHECK: edge entry -> loop probability is 0x078780e3 / 0x80000000 = 5.88% 582; CHECK: edge entry -> exit probability is 0x78787f1d / 0x80000000 = 94.12% [HOT edge] 583; CHECK: edge loop -> cont probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 584; CHECK: edge loop -> unreached probability is 0x00000000 / 0x80000000 = 0.00% 585; CHECK: edge cont -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge] 586; CHECK: edge cont -> cold probability is 0x0041edfd / 0x80000000 = 0.20% 587; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 588 589entry: 590 br i1 undef, label %loop, label %exit 591 592loop: 593 %i.0 = phi i32 [ 0, %entry ], [ %inc, %cont ] 594 %inc = add nsw i32 %i.0, 1 595 br i1 undef, label %cont, label %unreached 596 597cont: 598 br i1 undef, label %loop, label %cold 599 600unreached: 601 unreachable 602 603 604cold: 605 call void @cold() 606 br label %exit 607 608exit: 609 ret void 610} 611 612; This is the same case as test15 but with additional loop 'preheader' block. 613define void @test16() { 614; CHECK: edge entry -> preheader probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 615; CHECK: edge preheader -> loop probability is 0x078780e3 / 0x80000000 = 5.88% 616; CHECK: edge preheader -> exit probability is 0x78787f1d / 0x80000000 = 94.12% [HOT edge] 617; CHECK: edge loop -> cont probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 618; CHECK: edge loop -> unreached probability is 0x00000000 / 0x80000000 = 0.00% 619; CHECK: edge cont -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge] 620; CHECK: edge cont -> cold probability is 0x0041edfd / 0x80000000 = 0.20% 621; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 622 623entry: 624 br label %preheader 625 626preheader: 627 br i1 undef, label %loop, label %exit 628 629loop: 630 %i.0 = phi i32 [ 0, %preheader ], [ %inc, %cont ] 631 %inc = add nsw i32 %i.0, 1 632 br i1 undef, label %cont, label %unreached 633 634cont: 635 br i1 undef, label %loop, label %cold 636 637unreached: 638 unreachable 639 640 641cold: 642 call void @cold() 643 br label %exit 644 645exit: 646 ret void 647} 648 649declare void @abort() noreturn 650 651; Check that 'preheader' has 50/50 probability since there is one 'normal' exit. 652; Check that exit to 'cold' and 'noreturn' has lower probability than 'normal' exit. 653define void @test17() { 654; CHECK: edge entry -> preheader probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 655; CHECK: edge preheader -> loop probability is 0x40000000 / 0x80000000 = 50.00% 656; CHECK: edge preheader -> exit probability is 0x40000000 / 0x80000000 = 50.00% 657; CHECK: edge loop -> cont probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge] 658; CHECK: edge loop -> noreturn probability is 0x00000800 / 0x80000000 = 0.00% 659; CHECK: edge cont -> cont2 probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge] 660; CHECK: edge cont -> cold probability is 0x0041edfd / 0x80000000 = 0.20% 661; CHECK: edge cont2 -> loop probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge] 662; CHECK: edge cont2 -> exit probability is 0x04000000 / 0x80000000 = 3.12% 663; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 664entry: 665 br label %preheader 666 667preheader: 668 br i1 undef, label %loop, label %exit 669 670loop: 671 %i.0 = phi i32 [ 0, %preheader ], [ %inc, %cont2 ] 672 %inc = add nsw i32 %i.0, 1 673 br i1 undef, label %cont, label %noreturn 674 675cont: 676 br i1 undef, label %cont2, label %cold 677 678cont2: 679 br i1 undef, label %loop, label %exit 680 681noreturn: 682 call void @abort() 683 unreachable 684 685cold: 686 call void @cold() 687 br label %exit 688 689exit: 690 ret void 691} 692 693 694; This is case with two loops where one nested into another. Nested loop has 695; low probable exit what encreases robability to take exit in the top level loop. 696define void @test18() { 697; CHECK: edge entry -> top.loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 698; CHECK: edge top.loop -> loop probability is 0x546cd4b7 / 0x80000000 = 65.96% 699; CHECK: edge top.loop -> exit probability is 0x2b932b49 / 0x80000000 = 34.04% 700; CHECK: edge loop -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge] 701; CHECK: edge loop -> cold probability is 0x0041edfd / 0x80000000 = 0.20% 702; CHECK: edge cold -> top.loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge] 703 704entry: 705 br label %top.loop 706 707top.loop: 708 %j.0 = phi i32 [ 0, %entry ], [ %j.inc, %cold ] 709 br i1 undef, label %loop, label %exit 710 711loop: 712 %i.0 = phi i32 [ %j.0, %top.loop ], [ %inc, %loop ] 713 %inc = add nsw i32 %i.0, 1 714 br i1 undef, label %loop, label %cold 715 716cold: 717 call void @cold() 718 %j.inc = add nsw i32 %j.0, 1 719 br label %top.loop 720 721exit: 722 ret void 723} 724 725 726 727