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