1; Test the static branch probability heuristics for no-return functions.
2; RUN: opt < %s -analyze -branch-prob | FileCheck %s
3
4declare void @g1()
5declare void @g2()
6declare void @g3()
7declare void @g4()
8
9define void @test1(i32 %a, i32 %b) {
10entry:
11  br label %do.body
12; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
13
14do.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
20do.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
29do.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
37do.end5:
38  call void @g4()
39  ret void
40}
41
42define void @test2(i32 %a, i32 %b) {
43entry:
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
49for.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
54for.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
61for.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
70for.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
78for.end6:
79  call void @g4()
80  ret void
81}
82
83define void @test3(i32 %a, i32 %b, i32* %c) {
84entry:
85  br label %do.body
86; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
87
88do.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
97do.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
106if.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
114do.end6:
115  call void @g4()
116  ret void
117}
118
119define void @test4(i32 %a, i32 %b, i32* %c) {
120entry:
121  br label %do.body
122; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
123
124do.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
133do.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
142do.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
150do.end6:
151  call void @g4()
152  br label %return
153; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
154
155return:
156  ret void
157}
158
159define void @test5(i32 %a, i32 %b, i32* %c) {
160entry:
161  br label %do.body
162; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
163
164do.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
170do.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
178if.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
186do.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
194do.end6:
195  call void @g4()
196  br label %return
197; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
198
199return:
200  ret void
201}
202
203define void @test6(i32 %a, i32 %b, i32* %c) {
204entry:
205  br label %do.body
206; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
207
208do.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
214do.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
223do.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
230do.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
238do.end6:
239  call void @g4()
240  br label %return
241; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
242
243return:
244  ret void
245}
246
247define void @test7(i32 %a, i32 %b, i32* %c) {
248entry:
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
254for.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
259for.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
267if.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
273for.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
282for.end:
283  call void @g3()
284  br label %for.inc5
285; CHECK: edge for.end -> for.inc5 probability is 16 / 16 = 100%
286
287for.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
294for.end7:
295  call void @g4()
296  ret void
297}
298
299define void @test8(i32 %a, i32 %b, i32* %c) {
300entry:
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
306for.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
313for.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
320for.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
328if.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
335if.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
342if.end12:
343  call void @g2()
344  br label %for.inc
345; CHECK: edge if.end12 -> for.inc probability is 16 / 16 = 100%
346
347for.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
354for.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
362for.end15:
363  call void @g4()
364  ret void
365}
366