llvm/test/Analysis/BranchProbabilityInfo/loop.ll

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