llvm/test/Analysis/BranchProbabilityInfo/loop.ll

   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
   5 declare void @g1()
   6 declare void @g2()
   7 declare void @g3()
   8 declare void @g4()
   9 declare i32 @g5()
  10
  11 define void @test1(i32 %a, i32 %b) {
  12 entry:
  13   br label %do.body
  14 ; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
  15
  16 do.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
  22 do.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
  31 do.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
  39 do.end5:
  40   call void @g4()
  41   ret void
  42 }
  43
  44 define void @test2(i32 %a, i32 %b) {
  45 entry:
  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
  51 for.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
  56 for.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
  63 for.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
  72 for.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
  80 for.end6:
  81   call void @g4()
  82   ret void
  83 }
  84
  85 define void @test3(i32 %a, i32 %b, i32* %c) {
  86 entry:
  87   br label %do.body
  88 ; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
  89
  90 do.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
  99 do.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
 108 if.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
 116 do.end6:
 117   call void @g4()
 118   ret void
 119 }
 120
 121 define void @test4(i32 %a, i32 %b, i32* %c) {
 122 entry:
 123   br label %do.body
 124 ; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 125
 126 do.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
 135 do.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
 144 do.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
 152 do.end6:
 153   call void @g4()
 154   br label %return
 155 ; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 156
 157 return:
 158   ret void
 159 }
 160
 161 define void @test5(i32 %a, i32 %b, i32* %c) {
 162 entry:
 163   br label %do.body
 164 ; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 165
 166 do.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
 172 do.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
 180 if.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
 188 do.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
 196 do.end6:
 197   call void @g4()
 198   br label %return
 199 ; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 200
 201 return:
 202   ret void
 203 }
 204
 205 define void @test6(i32 %a, i32 %b, i32* %c) {
 206 entry:
 207   br label %do.body
 208 ; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 209
 210 do.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
 216 do.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
 225 do.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
 232 do.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
 240 do.end6:
 241   call void @g4()
 242   br label %return
 243 ; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 244
 245 return:
 246   ret void
 247 }
 248
 249 define void @test7(i32 %a, i32 %b, i32* %c) {
 250 entry:
 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
 256 for.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
 261 for.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
 269 if.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
 275 for.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
 284 for.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
 289 for.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
 296 for.end7:
 297   call void @g4()
 298   ret void
 299 }
 300
 301 define void @test8(i32 %a, i32 %b, i32* %c) {
 302 entry:
 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
 308 for.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
 315 for.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
 322 for.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
 330 if.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
 337 if.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
 344 if.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
 349 for.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
 356 for.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
 364 for.end15:
 365   call void @g4()
 366   ret void
 367 }
 368
 369 ; Test that an irreducible loop gets heavily weighted back-edges.
 370 define void @test9(i32 %i, i32 %x, i32 %c) {
 371 entry:
 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
 377 if.end:
 378   br label %for.cond
 379 ; CHECK:  edge if.end -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 380
 381 for.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
 388 midloop:
 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
 396 for.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
 401 end:
 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.
 407 define i32 @test10(i32 %n, i32* %p) {
 408 entry:
 409   br label %for.cond
 410 ; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 411
 412 for.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
 421 for.cond.cleanup:
 422   ret i32 %sum.0
 423
 424 for.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%
 433 if.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
 438 for.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
 448 define i32 @test11(i32 %n, i32* %p) {
 449 entry:
 450   br label %for.cond
 451 ; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 452
 453 for.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
 462 for.cond.cleanup:
 463   ret i32 %sum.0
 464
 465 for.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
 473 if.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
 479 if.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
 484 for.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.
 494 define void @test12(i32 %a) personality i8 0 {
 495 entry:
 496   br label %loop
 497 ; CHECK: edge entry -> loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 498
 499 loop:
 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
 506 invoke.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
 513 lpad:
 514   %ll = landingpad { i8*, i32 }
 515           cleanup
 516   br label %exit
 517
 518 exit:
 519   ret void
 520 }
 521
 522 declare i32 @InvokeCall()
 523 declare 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.
 527 define 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
 534 entry:
 535   br i1 undef, label %loop, label %exit
 536
 537 loop:
 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
 542 cold:
 543   call void @cold()
 544   br label %exit
 545
 546 exit:
 547   ret void
 548 }
 549
 550 ; This is the same case as test13 but with additional loop 'preheader' block.
 551 define 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
 559 entry:
 560   br i1 undef, label %preheader, label %exit
 561
 562 preheader:
 563   br label %loop
 564
 565 loop:
 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
 570 cold:
 571   call void @cold()
 572   br label %exit
 573
 574 exit:
 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.
 580 define 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
 589 entry:
 590   br i1 undef, label %loop, label %exit
 591
 592 loop:
 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
 597 cont:
 598   br i1 undef, label %loop, label %cold
 599
 600 unreached:
 601   unreachable
 602
 603
 604 cold:
 605   call void @cold()
 606   br label %exit
 607
 608 exit:
 609   ret void
 610 }
 611
 612 ; This is the same case as test15 but with additional loop 'preheader' block.
 613 define 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
 623 entry:
 624   br label %preheader
 625
 626 preheader:
 627   br i1 undef, label %loop, label %exit
 628
 629 loop:
 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
 634 cont:
 635   br i1 undef, label %loop, label %cold
 636
 637 unreached:
 638   unreachable
 639
 640
 641 cold:
 642   call void @cold()
 643   br label %exit
 644
 645 exit:
 646   ret void
 647 }
 648
 649 declare 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.
 653 define 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]
 664 entry:
 665   br label %preheader
 666
 667 preheader:
 668   br i1 undef, label %loop, label %exit
 669
 670 loop:
 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
 675 cont:
 676   br i1 undef, label %cont2, label %cold
 677
 678 cont2:
 679   br i1 undef, label %loop, label %exit
 680
 681 noreturn:
 682   call void @abort()
 683   unreachable
 684
 685 cold:
 686   call void @cold()
 687   br label %exit
 688
 689 exit:
 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.
 696 define 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
 704 entry:
 705  br label %top.loop
 706
 707 top.loop:
 708   %j.0 = phi i32 [ 0, %entry ], [ %j.inc, %cold ]
 709   br i1 undef, label %loop, label %exit
 710
 711 loop:
 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
 716 cold:
 717   call void @cold()
 718   %j.inc = add nsw i32 %j.0, 1
 719   br label %top.loop
 720
 721 exit:
 722   ret void
 723 }
 724
 725
 726