test/Analysis/BranchProbabilityInfo/loop.ll

   1 ; Test the static branch probability heuristics for no-return functions.
   2 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
   3
   4 declare void @g1()
   5 declare void @g2()
   6 declare void @g3()
   7 declare void @g4()
   8
   9 define void @test1(i32 %a, i32 %b) {
  10 entry:
  11   br label %do.body
  12 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
  13
  14 do.body:
  15   %i.0 = phi i32 [ 0, %entry ], [ %inc3, %do.end ]
  16   call void @g1()
  17   br label %do.body1
  18 ; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
  19
  20 do.body1:
  21   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.body1 ]
  22   call void @g2()
  23   %inc = add nsw i32 %j.0, 1
  24   %cmp = icmp slt i32 %inc, %b
  25   br i1 %cmp, label %do.body1, label %do.end
  26 ; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
  27 ; CHECK: edge do.body1 -> do.end probability is 4 / 128
  28
  29 do.end:
  30   call void @g3()
  31   %inc3 = add nsw i32 %i.0, 1
  32   %cmp4 = icmp slt i32 %inc3, %a
  33   br i1 %cmp4, label %do.body, label %do.end5
  34 ; CHECK: edge do.end -> do.body probability is 124 / 128
  35 ; CHECK: edge do.end -> do.end5 probability is 4 / 128
  36
  37 do.end5:
  38   call void @g4()
  39   ret void
  40 }
  41
  42 define void @test2(i32 %a, i32 %b) {
  43 entry:
  44   %cmp9 = icmp sgt i32 %a, 0
  45   br i1 %cmp9, label %for.body.lr.ph, label %for.end6
  46 ; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
  47 ; CHECK: edge entry -> for.end6 probability is 12 / 32
  48
  49 for.body.lr.ph:
  50   %cmp27 = icmp sgt i32 %b, 0
  51   br label %for.body
  52 ; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
  53
  54 for.body:
  55   %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc5, %for.end ]
  56   call void @g1()
  57   br i1 %cmp27, label %for.body3, label %for.end
  58 ; CHECK: edge for.body -> for.body3 probability is 20 / 32 = 62.5%
  59 ; CHECK: edge for.body -> for.end probability is 12 / 32 = 37.5%
  60
  61 for.body3:
  62   %j.08 = phi i32 [ %inc, %for.body3 ], [ 0, %for.body ]
  63   call void @g2()
  64   %inc = add nsw i32 %j.08, 1
  65   %exitcond = icmp eq i32 %inc, %b
  66   br i1 %exitcond, label %for.end, label %for.body3
  67 ; CHECK: edge for.body3 -> for.end probability is 4 / 128
  68 ; CHECK: edge for.body3 -> for.body3 probability is 124 / 128
  69
  70 for.end:
  71   call void @g3()
  72   %inc5 = add nsw i32 %i.010, 1
  73   %exitcond11 = icmp eq i32 %inc5, %a
  74   br i1 %exitcond11, label %for.end6, label %for.body
  75 ; CHECK: edge for.end -> for.end6 probability is 4 / 128
  76 ; CHECK: edge for.end -> for.body probability is 124 / 128
  77
  78 for.end6:
  79   call void @g4()
  80   ret void
  81 }
  82
  83 define void @test3(i32 %a, i32 %b, i32* %c) {
  84 entry:
  85   br label %do.body
  86 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
  87
  88 do.body:
  89   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ]
  90   call void @g1()
  91   %0 = load i32, i32* %c, align 4
  92   %cmp = icmp slt i32 %0, 42
  93   br i1 %cmp, label %do.body1, label %if.end
  94 ; CHECK: edge do.body -> do.body1 probability is 16 / 32 = 50%
  95 ; CHECK: edge do.body -> if.end probability is 16 / 32 = 50%
  96
  97 do.body1:
  98   %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ]
  99   call void @g2()
 100   %inc = add nsw i32 %j.0, 1
 101   %cmp2 = icmp slt i32 %inc, %b
 102   br i1 %cmp2, label %do.body1, label %if.end
 103 ; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
 104 ; CHECK: edge do.body1 -> if.end probability is 4 / 128
 105
 106 if.end:
 107   call void @g3()
 108   %inc4 = add nsw i32 %i.0, 1
 109   %cmp5 = icmp slt i32 %inc4, %a
 110   br i1 %cmp5, label %do.body, label %do.end6
 111 ; CHECK: edge if.end -> do.body probability is 124 / 128
 112 ; CHECK: edge if.end -> do.end6 probability is 4 / 128
 113
 114 do.end6:
 115   call void @g4()
 116   ret void
 117 }
 118
 119 define void @test4(i32 %a, i32 %b, i32* %c) {
 120 entry:
 121   br label %do.body
 122 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
 123
 124 do.body:
 125   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
 126   call void @g1()
 127   %0 = load i32, i32* %c, align 4
 128   %cmp = icmp slt i32 %0, 42
 129   br i1 %cmp, label %return, label %do.body1
 130 ; CHECK: edge do.body -> return probability is 4 / 128
 131 ; CHECK: edge do.body -> do.body1 probability is 124 / 128
 132
 133 do.body1:
 134   %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ]
 135   call void @g2()
 136   %inc = add nsw i32 %j.0, 1
 137   %cmp2 = icmp slt i32 %inc, %b
 138   br i1 %cmp2, label %do.body1, label %do.end
 139 ; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
 140 ; CHECK: edge do.body1 -> do.end probability is 4 / 128
 141
 142 do.end:
 143   call void @g3()
 144   %inc4 = add nsw i32 %i.0, 1
 145   %cmp5 = icmp slt i32 %inc4, %a
 146   br i1 %cmp5, label %do.body, label %do.end6
 147 ; CHECK: edge do.end -> do.body probability is 124 / 128
 148 ; CHECK: edge do.end -> do.end6 probability is 4 / 128
 149
 150 do.end6:
 151   call void @g4()
 152   br label %return
 153 ; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
 154
 155 return:
 156   ret void
 157 }
 158
 159 define void @test5(i32 %a, i32 %b, i32* %c) {
 160 entry:
 161   br label %do.body
 162 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
 163
 164 do.body:
 165   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
 166   call void @g1()
 167   br label %do.body1
 168 ; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
 169
 170 do.body1:
 171   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %if.end ]
 172   %0 = load i32, i32* %c, align 4
 173   %cmp = icmp slt i32 %0, 42
 174   br i1 %cmp, label %return, label %if.end
 175 ; CHECK: edge do.body1 -> return probability is 4 / 128
 176 ; CHECK: edge do.body1 -> if.end probability is 124 / 128
 177
 178 if.end:
 179   call void @g2()
 180   %inc = add nsw i32 %j.0, 1
 181   %cmp2 = icmp slt i32 %inc, %b
 182   br i1 %cmp2, label %do.body1, label %do.end
 183 ; CHECK: edge if.end -> do.body1 probability is 124 / 128
 184 ; CHECK: edge if.end -> do.end probability is 4 / 128
 185
 186 do.end:
 187   call void @g3()
 188   %inc4 = add nsw i32 %i.0, 1
 189   %cmp5 = icmp slt i32 %inc4, %a
 190   br i1 %cmp5, label %do.body, label %do.end6
 191 ; CHECK: edge do.end -> do.body probability is 124 / 128
 192 ; CHECK: edge do.end -> do.end6 probability is 4 / 128
 193
 194 do.end6:
 195   call void @g4()
 196   br label %return
 197 ; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
 198
 199 return:
 200   ret void
 201 }
 202
 203 define void @test6(i32 %a, i32 %b, i32* %c) {
 204 entry:
 205   br label %do.body
 206 ; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
 207
 208 do.body:
 209   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
 210   call void @g1()
 211   br label %do.body1
 212 ; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
 213
 214 do.body1:
 215   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ]
 216   call void @g2()
 217   %0 = load i32, i32* %c, align 4
 218   %cmp = icmp slt i32 %0, 42
 219   br i1 %cmp, label %return, label %do.cond
 220 ; CHECK: edge do.body1 -> return probability is 4 / 128
 221 ; CHECK: edge do.body1 -> do.cond probability is 124 / 128
 222
 223 do.cond:
 224   %inc = add nsw i32 %j.0, 1
 225   %cmp2 = icmp slt i32 %inc, %b
 226   br i1 %cmp2, label %do.body1, label %do.end
 227 ; CHECK: edge do.cond -> do.body1 probability is 124 / 128
 228 ; CHECK: edge do.cond -> do.end probability is 4 / 128
 229
 230 do.end:
 231   call void @g3()
 232   %inc4 = add nsw i32 %i.0, 1
 233   %cmp5 = icmp slt i32 %inc4, %a
 234   br i1 %cmp5, label %do.body, label %do.end6
 235 ; CHECK: edge do.end -> do.body probability is 124 / 128
 236 ; CHECK: edge do.end -> do.end6 probability is 4 / 128
 237
 238 do.end6:
 239   call void @g4()
 240   br label %return
 241 ; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
 242
 243 return:
 244   ret void
 245 }
 246
 247 define void @test7(i32 %a, i32 %b, i32* %c) {
 248 entry:
 249   %cmp10 = icmp sgt i32 %a, 0
 250   br i1 %cmp10, label %for.body.lr.ph, label %for.end7
 251 ; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
 252 ; CHECK: edge entry -> for.end7 probability is 12 / 32
 253
 254 for.body.lr.ph:
 255   %cmp38 = icmp sgt i32 %b, 0
 256   br label %for.body
 257 ; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
 258
 259 for.body:
 260   %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc6, %for.inc5 ]
 261   %0 = load i32, i32* %c, align 4
 262   %cmp1 = icmp eq i32 %0, %i.011
 263   br i1 %cmp1, label %for.inc5, label %if.end
 264 ; CHECK: edge for.body -> for.inc5 probability is 16 / 32 = 50%
 265 ; CHECK: edge for.body -> if.end probability is 16 / 32 = 50%
 266
 267 if.end:
 268   call void @g1()
 269   br i1 %cmp38, label %for.body4, label %for.end
 270 ; CHECK: edge if.end -> for.body4 probability is 20 / 32 = 62.5%
 271 ; CHECK: edge if.end -> for.end probability is 12 / 32 = 37.5%
 272
 273 for.body4:
 274   %j.09 = phi i32 [ %inc, %for.body4 ], [ 0, %if.end ]
 275   call void @g2()
 276   %inc = add nsw i32 %j.09, 1
 277   %exitcond = icmp eq i32 %inc, %b
 278   br i1 %exitcond, label %for.end, label %for.body4
 279 ; CHECK: edge for.body4 -> for.end probability is 4 / 128
 280 ; CHECK: edge for.body4 -> for.body4 probability is 124 / 128
 281
 282 for.end:
 283   call void @g3()
 284   br label %for.inc5
 285 ; CHECK: edge for.end -> for.inc5 probability is 16 / 16 = 100%
 286
 287 for.inc5:
 288   %inc6 = add nsw i32 %i.011, 1
 289   %exitcond12 = icmp eq i32 %inc6, %a
 290   br i1 %exitcond12, label %for.end7, label %for.body
 291 ; CHECK: edge for.inc5 -> for.end7 probability is 4 / 128
 292 ; CHECK: edge for.inc5 -> for.body probability is 124 / 128
 293
 294 for.end7:
 295   call void @g4()
 296   ret void
 297 }
 298
 299 define void @test8(i32 %a, i32 %b, i32* %c) {
 300 entry:
 301   %cmp18 = icmp sgt i32 %a, 0
 302   br i1 %cmp18, label %for.body.lr.ph, label %for.end15
 303 ; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
 304 ; CHECK: edge entry -> for.end15 probability is 12 / 32
 305
 306 for.body.lr.ph:
 307   %cmp216 = icmp sgt i32 %b, 0
 308   %arrayidx5 = getelementptr inbounds i32, i32* %c, i64 1
 309   %arrayidx9 = getelementptr inbounds i32, i32* %c, i64 2
 310   br label %for.body
 311 ; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
 312
 313 for.body:
 314   %i.019 = phi i32 [ 0, %for.body.lr.ph ], [ %inc14, %for.end ]
 315   call void @g1()
 316   br i1 %cmp216, label %for.body3, label %for.end
 317 ; CHECK: edge for.body -> for.body3 probability is 20 / 32 = 62.5%
 318 ; CHECK: edge for.body -> for.end probability is 12 / 32 = 37.5%
 319
 320 for.body3:
 321   %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
 322   %0 = load i32, i32* %c, align 4
 323   %cmp4 = icmp eq i32 %0, %j.017
 324   br i1 %cmp4, label %for.inc, label %if.end
 325 ; CHECK: edge for.body3 -> for.inc probability is 16 / 32 = 50%
 326 ; CHECK: edge for.body3 -> if.end probability is 16 / 32 = 50%
 327
 328 if.end:
 329   %1 = load i32, i32* %arrayidx5, align 4
 330   %cmp6 = icmp eq i32 %1, %j.017
 331   br i1 %cmp6, label %for.inc, label %if.end8
 332 ; CHECK: edge if.end -> for.inc probability is 16 / 32 = 50%
 333 ; CHECK: edge if.end -> if.end8 probability is 16 / 32 = 50%
 334
 335 if.end8:
 336   %2 = load i32, i32* %arrayidx9, align 4
 337   %cmp10 = icmp eq i32 %2, %j.017
 338   br i1 %cmp10, label %for.inc, label %if.end12
 339 ; CHECK: edge if.end8 -> for.inc probability is 16 / 32 = 50%
 340 ; CHECK: edge if.end8 -> if.end12 probability is 16 / 32 = 50%
 341
 342 if.end12:
 343   call void @g2()
 344   br label %for.inc
 345 ; CHECK: edge if.end12 -> for.inc probability is 16 / 16 = 100%
 346
 347 for.inc:
 348   %inc = add nsw i32 %j.017, 1
 349   %exitcond = icmp eq i32 %inc, %b
 350   br i1 %exitcond, label %for.end, label %for.body3
 351 ; CHECK: edge for.inc -> for.end probability is 4 / 128
 352 ; CHECK: edge for.inc -> for.body3 probability is 124 / 128
 353
 354 for.end:
 355   call void @g3()
 356   %inc14 = add nsw i32 %i.019, 1
 357   %exitcond20 = icmp eq i32 %inc14, %a
 358   br i1 %exitcond20, label %for.end15, label %for.body
 359 ; CHECK: edge for.end -> for.end15 probability is 4 / 128
 360 ; CHECK: edge for.end -> for.body probability is 124 / 128
 361
 362 for.end15:
 363   call void @g4()
 364   ret void
 365 }