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 124 / 124 = 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 62 / 124 = 50% 59 ; CHECK: edge for.body -> for.end probability is 62 / 124 = 50% 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* %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 62 / 124 = 50% 95 ; CHECK: edge do.body -> if.end probability is 62 / 124 = 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* %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 124 / 124 = 100% 169 170 do.body1: 171 %j.0 = phi i32 [ 0, %do.body ], [ %inc, %if.end ] 172 %0 = load 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 124 / 124 = 100% 213 214 do.body1: 215 %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ] 216 call void @g2() 217 %0 = load 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* %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 62 / 124 = 50% 265 ; CHECK: edge for.body -> if.end probability is 62 / 124 = 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 62 / 124 = 50% 271 ; CHECK: edge if.end -> for.end probability is 62 / 124 = 50% 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 124 / 124 = 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* %c, i64 1 309 %arrayidx9 = getelementptr inbounds 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 62 / 124 = 50% 318 ; CHECK: edge for.body -> for.end probability is 62 / 124 = 50% 319 320 for.body3: 321 %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] 322 %0 = load 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 62 / 124 = 50% 326 ; CHECK: edge for.body3 -> if.end probability is 62 / 124 = 50% 327 328 if.end: 329 %1 = load 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 62 / 124 = 50% 333 ; CHECK: edge if.end -> if.end8 probability is 62 / 124 = 50% 334 335 if.end8: 336 %2 = load 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 62 / 124 = 50% 340 ; CHECK: edge if.end8 -> if.end12 probability is 62 / 124 = 50% 341 342 if.end12: 343 call void @g2() 344 br label %for.inc 345 ; CHECK: edge if.end12 -> for.inc probability is 124 / 124 = 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 } 366
