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
4declare void @g1()
5declare void @g2()
6declare void @g3()
7declare void @g4()
8declare i32 @g5()
9
10define void @test1(i32 %a, i32 %b) {
11entry:
12  br label %do.body
13; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
14
15do.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
21do.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
30do.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
38do.end5:
39  call void @g4()
40  ret void
41}
42
43define void @test2(i32 %a, i32 %b) {
44entry:
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
50for.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
55for.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
62for.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
71for.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
79for.end6:
80  call void @g4()
81  ret void
82}
83
84define void @test3(i32 %a, i32 %b, i32* %c) {
85entry:
86  br label %do.body
87; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
88
89do.body:
90  %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ]
91  call void @g1()
92  %0 = load i32, i32* %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
98do.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
107if.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
115do.end6:
116  call void @g4()
117  ret void
118}
119
120define void @test4(i32 %a, i32 %b, i32* %c) {
121entry:
122  br label %do.body
123; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
124
125do.body:
126  %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
127  call void @g1()
128  %0 = load i32, i32* %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
134do.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
143do.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
151do.end6:
152  call void @g4()
153  br label %return
154; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
155
156return:
157  ret void
158}
159
160define void @test5(i32 %a, i32 %b, i32* %c) {
161entry:
162  br label %do.body
163; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
164
165do.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
171do.body1:
172  %j.0 = phi i32 [ 0, %do.body ], [ %inc, %if.end ]
173  %0 = load i32, i32* %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
179if.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
187do.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
195do.end6:
196  call void @g4()
197  br label %return
198; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
199
200return:
201  ret void
202}
203
204define void @test6(i32 %a, i32 %b, i32* %c) {
205entry:
206  br label %do.body
207; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
208
209do.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
215do.body1:
216  %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ]
217  call void @g2()
218  %0 = load i32, i32* %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
224do.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
231do.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
239do.end6:
240  call void @g4()
241  br label %return
242; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
243
244return:
245  ret void
246}
247
248define void @test7(i32 %a, i32 %b, i32* %c) {
249entry:
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
255for.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
260for.body:
261  %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc6, %for.inc5 ]
262  %0 = load i32, i32* %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
268if.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
274for.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
283for.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
288for.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
295for.end7:
296  call void @g4()
297  ret void
298}
299
300define void @test8(i32 %a, i32 %b, i32* %c) {
301entry:
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
307for.body.lr.ph:
308  %cmp216 = icmp sgt i32 %b, 0
309  %arrayidx5 = getelementptr inbounds i32, i32* %c, i64 1
310  %arrayidx9 = getelementptr inbounds i32, i32* %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
314for.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
321for.body3:
322  %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
323  %0 = load i32, i32* %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
329if.end:
330  %1 = load i32, i32* %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
336if.end8:
337  %2 = load i32, i32* %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
343if.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
348for.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
355for.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
363for.end15:
364  call void @g4()
365  ret void
366}
367
368; Test that an irreducible loop gets heavily weighted back-edges.
369define void @test9(i32 %i, i32 %x, i32 %c) {
370entry:
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
376if.end:
377  br label %for.cond
378; CHECK:  edge if.end -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
379
380for.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
387midloop:
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
395for.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
400end:
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.
406define i32 @test10(i32 %n, i32* %p) {
407entry:
408  br label %for.cond
409; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
410
411for.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
420for.cond.cleanup:
421  ret i32 %sum.0
422
423for.body:
424  %arrayidx = getelementptr inbounds i32, i32* %p, i32 %i.0
425  %0 = load i32, i32* %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%
432if.then:
433  store i32 %add, i32* %arrayidx, align 4
434  br label %for.inc
435; CHECK: edge if.then -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
436
437for.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
447define i32 @test11(i32 %n, i32* %p) {
448entry:
449  br label %for.cond
450; CHECK: edge entry -> for.cond probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
451
452for.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
461for.cond.cleanup:
462  ret i32 %sum.0
463
464for.body:
465  %tobool = icmp eq i32 %flip.0, 0
466  %arrayidx1 = getelementptr inbounds i32, i32* %p, i32 %i.0
467  %0 = load i32, i32* %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
472if.then:
473  %add = add nsw i32 %0, %sum.0
474  store i32 %add, i32* %arrayidx1, align 4
475  br label %for.inc
476; CHECK: edge if.then -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
477
478if.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
483for.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.
493define void @test12(i32 %a) personality i8 0 {
494entry:
495  br label %loop
496; CHECK: edge entry -> loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
497
498loop:
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
505invoke.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
512lpad:
513  %ll = landingpad { i8*, i32 }
514          cleanup
515  br label %exit
516
517exit:
518  ret void
519}
520
521declare i32 @InvokeCall()
522declare 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.
526define 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
533entry:
534  br i1 undef, label %loop, label %exit
535
536loop:
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
541cold:
542  call void @cold()
543  br label %exit
544
545exit:
546  ret void
547}
548
549; This is the same case as test13 but with additional loop 'preheader' block.
550define 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
558entry:
559  br i1 undef, label %preheader, label %exit
560
561preheader:
562  br label %loop
563
564loop:
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
569cold:
570  call void @cold()
571  br label %exit
572
573exit:
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.
579define 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
588entry:
589  br i1 undef, label %loop, label %exit
590
591loop:
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
596cont:
597  br i1 undef, label %loop, label %cold
598
599unreached:
600  unreachable
601
602
603cold:
604  call void @cold()
605  br label %exit
606
607exit:
608  ret void
609}
610
611; This is the same case as test15 but with additional loop 'preheader' block.
612define 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
622entry:
623  br label %preheader
624
625preheader:
626  br i1 undef, label %loop, label %exit
627
628loop:
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
633cont:
634  br i1 undef, label %loop, label %cold
635
636unreached:
637  unreachable
638
639
640cold:
641  call void @cold()
642  br label %exit
643
644exit:
645  ret void
646}
647
648declare 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.
652define 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]
663entry:
664  br label %preheader
665
666preheader:
667  br i1 undef, label %loop, label %exit
668
669loop:
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
674cont:
675  br i1 undef, label %cont2, label %cold
676
677cont2:
678  br i1 undef, label %loop, label %exit
679
680noreturn:
681  call void @abort()
682  unreachable
683
684cold:
685  call void @cold()
686  br label %exit
687
688exit:
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.
695define 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
703entry:
704 br label %top.loop
705
706top.loop:
707  %j.0 = phi i32 [ 0, %entry ], [ %j.inc, %cold ]
708  br i1 undef, label %loop, label %exit
709
710loop:
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
715cold:
716  call void @cold()
717  %j.inc = add nsw i32 %j.0, 1
718  br label %top.loop
719
720exit:
721  ret void
722}
723
724
725
726