1; RUN: opt < %s -analyze -block-freq | FileCheck %s
2
3; A loop with multiple exits isn't irreducible.  It should be handled
4; correctly.
5;
6; CHECK-LABEL: Printing analysis {{.*}} for function 'multiexit':
7; CHECK-NEXT: block-frequency-info: multiexit
8define void @multiexit(i1 %x) {
9; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
10entry:
11  br label %loop.1
12
13; CHECK-NEXT: loop.1: float = 2.0,
14loop.1:
15  br i1 %x, label %exit.1, label %loop.2, !prof !0
16
17; CHECK-NEXT: loop.2: float = 1.75,
18loop.2:
19  br i1 %x, label %exit.2, label %loop.1, !prof !1
20
21; CHECK-NEXT: exit.1: float = 0.25,
22exit.1:
23  br label %return
24
25; CHECK-NEXT: exit.2: float = 0.75,
26exit.2:
27  br label %return
28
29; CHECK-NEXT: return: float = 1.0, int = [[ENTRY]]
30return:
31  ret void
32}
33
34!0 = !{!"branch_weights", i32 1, i32 7}
35!1 = !{!"branch_weights", i32 3, i32 4}
36
37; Irreducible control flow
38; ========================
39;
40; LoopInfo defines a loop as a non-trivial SCC dominated by a single block,
41; called the header.  A given loop, L, can have sub-loops, which are loops
42; within the subgraph of L that excludes the header.
43;
44; In addition to loops, -block-freq has limited support for irreducible SCCs,
45; which are SCCs with multiple entry blocks.  Irreducible SCCs are discovered
46; on they fly, and modelled as loops with multiple headers.
47;
48; The headers of irreducible sub-SCCs consist of its entry blocks and all nodes
49; that are targets of a backedge within it (excluding backedges within true
50; sub-loops).
51;
52; -block-freq is currently designed to act like a block is inserted that
53; intercepts all the edges to the headers.  All backedges and entries point to
54; this block.  Its successors are the headers, which split the frequency
55; evenly.
56;
57; There are a number of testcases below.  Only the first two have detailed
58; explanations.
59;
60; Testcase #1
61; ===========
62;
63; In this case c1 and c2 should have frequencies of 15/7 and 13/7,
64; respectively.  To calculate this, consider assigning 1.0 to entry, and
65; distributing frequency iteratively (to infinity).  At the first iteration,
66; entry gives 3/4 to c1 and 1/4 to c2.  At every step after, c1 and c2 give 3/4
67; of what they have to each other.  Somehow, all of it comes out to exit.
68;
69;       c1 = 3/4 + 1/4*3/4 + 3/4*3^2/4^2 + 1/4*3^3/4^3 + 3/4*3^3/4^3 + ...
70;       c2 = 1/4 + 3/4*3/4 + 1/4*3^2/4^2 + 3/4*3^3/4^3 + 1/4*3^3/4^3 + ...
71;
72; Simplify by splitting up the odd and even terms of the series and taking out
73; factors so that the infite series matches:
74;
75;       c1 =  3/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
76;          +  3/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
77;       c2 =  1/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
78;          +  9/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
79;
80;       c1 = 15/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
81;       c2 = 13/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
82;
83; Since this geometric series sums to 16/7:
84;
85;       c1 = 15/7
86;       c2 = 13/7
87;
88; If we treat c1 and c2 as members of the same loop, the exit frequency of the
89; loop as a whole is 1/4, so the loop scale should be 4.  Summing c1 and c2
90; gives 28/7, or 4.0, which is nice confirmation of the math above.
91;
92; -block-freq currently treats the two nodes as equals.
93define void @multientry(i1 %x) {
94; CHECK-LABEL: Printing analysis {{.*}} for function 'multientry':
95; CHECK-NEXT: block-frequency-info: multientry
96entry:
97; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
98  br i1 %x, label %c1, label %c2, !prof !2
99
100c1:
101; CHECK-NEXT: c1: float = 2.0,
102; The "correct" answer is: float = 2.142857{{[0-9]*}},
103  br i1 %x, label %c2, label %exit, !prof !2
104
105c2:
106; CHECK-NEXT: c2: float = 2.0,
107; The "correct" answer is: float = 1.857142{{[0-9]*}},
108  br i1 %x, label %c1, label %exit, !prof !2
109
110exit:
111; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
112  ret void
113}
114
115!2 = !{!"branch_weights", i32 3, i32 1}
116
117; Testcase #2
118; ===========
119;
120; In this case c1 and c2 should be treated as equals in a single loop.  The
121; exit frequency is 1/3, so the scaling factor for the loop should be 3.0.  The
122; loop is entered 2/3 of the time, and c1 and c2 split the total loop frequency
123; evenly (1/2), so they should each have frequencies of 1.0 (3.0*2/3*1/2).
124; Another way of computing this result is by assigning 1.0 to entry and showing
125; that c1 and c2 should accumulate frequencies of:
126;
127;       1/3   +   2/9   +   4/27  +   8/81  + ...
128;     2^0/3^1 + 2^1/3^2 + 2^2/3^3 + 2^3/3^4 + ...
129;
130; At the first step, c1 and c2 each get 1/3 of the entry.  At each subsequent
131; step, c1 and c2 each get 1/3 of what's left in c1 and c2 combined.  This
132; infinite series sums to 1.
133define void @crossloops(i2 %x) {
134; CHECK-LABEL: Printing analysis {{.*}} for function 'crossloops':
135; CHECK-NEXT: block-frequency-info: crossloops
136entry:
137; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
138  switch i2 %x, label %exit [ i2 1, label %c1
139                              i2 2, label %c2 ], !prof !3
140
141c1:
142; CHECK-NEXT: c1: float = 1.0,
143  switch i2 %x, label %exit [ i2 1, label %c1
144                              i2 2, label %c2 ], !prof !3
145
146c2:
147; CHECK-NEXT: c2: float = 1.0,
148  switch i2 %x, label %exit [ i2 1, label %c1
149                              i2 2, label %c2 ], !prof !3
150
151exit:
152; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
153  ret void
154}
155
156!3 = !{!"branch_weights", i32 2, i32 2, i32 2}
157
158; A true loop with irreducible control flow inside.
159define void @loop_around_irreducible(i1 %x) {
160; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_irreducible':
161; CHECK-NEXT: block-frequency-info: loop_around_irreducible
162entry:
163; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
164  br label %loop
165
166loop:
167; CHECK-NEXT: loop: float = 4.0, int = [[HEAD:[0-9]+]]
168  br i1 %x, label %left, label %right, !prof !4
169
170left:
171; CHECK-NEXT: left: float = 8.0,
172  br i1 %x, label %right, label %loop.end, !prof !5
173
174right:
175; CHECK-NEXT: right: float = 8.0,
176  br i1 %x, label %left, label %loop.end, !prof !5
177
178loop.end:
179; CHECK-NEXT: loop.end: float = 4.0, int = [[HEAD]]
180  br i1 %x, label %loop, label %exit, !prof !5
181
182exit:
183; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
184  ret void
185}
186!4 = !{!"branch_weights", i32 1, i32 1}
187!5 = !{!"branch_weights", i32 3, i32 1}
188
189; Two unrelated irreducible SCCs.
190define void @two_sccs(i1 %x) {
191; CHECK-LABEL: Printing analysis {{.*}} for function 'two_sccs':
192; CHECK-NEXT: block-frequency-info: two_sccs
193entry:
194; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
195  br i1 %x, label %a, label %b, !prof !6
196
197a:
198; CHECK-NEXT: a: float = 0.75,
199  br i1 %x, label %a.left, label %a.right, !prof !7
200
201a.left:
202; CHECK-NEXT: a.left: float = 1.5,
203  br i1 %x, label %a.right, label %exit, !prof !6
204
205a.right:
206; CHECK-NEXT: a.right: float = 1.5,
207  br i1 %x, label %a.left, label %exit, !prof !6
208
209b:
210; CHECK-NEXT: b: float = 0.25,
211  br i1 %x, label %b.left, label %b.right, !prof !7
212
213b.left:
214; CHECK-NEXT: b.left: float = 0.625,
215  br i1 %x, label %b.right, label %exit, !prof !8
216
217b.right:
218; CHECK-NEXT: b.right: float = 0.625,
219  br i1 %x, label %b.left, label %exit, !prof !8
220
221exit:
222; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
223  ret void
224}
225!6 = !{!"branch_weights", i32 3, i32 1}
226!7 = !{!"branch_weights", i32 1, i32 1}
227!8 = !{!"branch_weights", i32 4, i32 1}
228
229; A true loop inside irreducible control flow.
230define void @loop_inside_irreducible(i1 %x) {
231; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_inside_irreducible':
232; CHECK-NEXT: block-frequency-info: loop_inside_irreducible
233entry:
234; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
235  br i1 %x, label %left, label %right, !prof !9
236
237left:
238; CHECK-NEXT: left: float = 2.0,
239  br i1 %x, label %right, label %exit, !prof !10
240
241right:
242; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]
243  br label %loop
244
245loop:
246; CHECK-NEXT: loop: float = 6.0,
247  br i1 %x, label %loop, label %right.end, !prof !11
248
249right.end:
250; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]
251  br i1 %x, label %left, label %exit, !prof !10
252
253exit:
254; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
255  ret void
256}
257!9 = !{!"branch_weights", i32 1, i32 1}
258!10 = !{!"branch_weights", i32 3, i32 1}
259!11 = !{!"branch_weights", i32 2, i32 1}
260
261; Irreducible control flow in a branch that's in a true loop.
262define void @loop_around_branch_with_irreducible(i1 %x) {
263; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_branch_with_irreducible':
264; CHECK-NEXT: block-frequency-info: loop_around_branch_with_irreducible
265entry:
266; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
267  br label %loop
268
269loop:
270; CHECK-NEXT: loop: float = 2.0, int = [[LOOP:[0-9]+]]
271  br i1 %x, label %normal, label %irreducible.entry, !prof !12
272
273normal:
274; CHECK-NEXT: normal: float = 1.5,
275  br label %loop.end
276
277irreducible.entry:
278; CHECK-NEXT: irreducible.entry: float = 0.5, int = [[IRREDUCIBLE:[0-9]+]]
279  br i1 %x, label %left, label %right, !prof !13
280
281left:
282; CHECK-NEXT: left: float = 1.0,
283  br i1 %x, label %right, label %irreducible.exit, !prof !12
284
285right:
286; CHECK-NEXT: right: float = 1.0,
287  br i1 %x, label %left, label %irreducible.exit, !prof !12
288
289irreducible.exit:
290; CHECK-NEXT: irreducible.exit: float = 0.5, int = [[IRREDUCIBLE]]
291  br label %loop.end
292
293loop.end:
294; CHECK-NEXT: loop.end: float = 2.0, int = [[LOOP]]
295  br i1 %x, label %loop, label %exit, !prof !13
296
297exit:
298; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
299  ret void
300}
301!12 = !{!"branch_weights", i32 3, i32 1}
302!13 = !{!"branch_weights", i32 1, i32 1}
303
304; Irreducible control flow between two true loops.
305define void @loop_around_branch_with_irreducible_around_loop(i1 %x) {
306; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_branch_with_irreducible_around_loop':
307; CHECK-NEXT: block-frequency-info: loop_around_branch_with_irreducible_around_loop
308entry:
309; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
310  br label %loop
311
312loop:
313; CHECK-NEXT: loop: float = 3.0, int = [[LOOP:[0-9]+]]
314  br i1 %x, label %normal, label %irreducible, !prof !14
315
316normal:
317; CHECK-NEXT: normal: float = 2.0,
318  br label %loop.end
319
320irreducible:
321; CHECK-NEXT: irreducible: float = 1.0,
322  br i1 %x, label %left, label %right, !prof !15
323
324left:
325; CHECK-NEXT: left: float = 2.0,
326  br i1 %x, label %right, label %loop.end, !prof !16
327
328right:
329; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]
330  br label %right.loop
331
332right.loop:
333; CHECK-NEXT: right.loop: float = 10.0,
334  br i1 %x, label %right.loop, label %right.end, !prof !17
335
336right.end:
337; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]
338  br i1 %x, label %left, label %loop.end, !prof !16
339
340loop.end:
341; CHECK-NEXT: loop.end: float = 3.0, int = [[LOOP]]
342  br i1 %x, label %loop, label %exit, !prof !14
343
344exit:
345; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
346  ret void
347}
348!14 = !{!"branch_weights", i32 2, i32 1}
349!15 = !{!"branch_weights", i32 1, i32 1}
350!16 = !{!"branch_weights", i32 3, i32 1}
351!17 = !{!"branch_weights", i32 4, i32 1}
352
353; An irreducible SCC with a non-header.
354define void @nonheader(i1 %x) {
355; CHECK-LABEL: Printing analysis {{.*}} for function 'nonheader':
356; CHECK-NEXT: block-frequency-info: nonheader
357entry:
358; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
359  br i1 %x, label %left, label %right, !prof !18
360
361left:
362; CHECK-NEXT: left: float = 1.0,
363  br i1 %x, label %bottom, label %exit, !prof !19
364
365right:
366; CHECK-NEXT: right: float = 1.0,
367  br i1 %x, label %bottom, label %exit, !prof !20
368
369bottom:
370; CHECK-NEXT: bottom: float = 1.0,
371  br i1 %x, label %left, label %right, !prof !18
372
373exit:
374; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
375  ret void
376}
377!18 = !{!"branch_weights", i32 1, i32 1}
378!19 = !{!"branch_weights", i32 1, i32 3}
379!20 = !{!"branch_weights", i32 3, i32 1}
380
381; An irreducible SCC with an irreducible sub-SCC.  In the current version of
382; -block-freq, this means an extra header.
383;
384; This testcases uses non-trivial branch weights.  The CHECK statements here
385; will start to fail if we change -block-freq to be more accurate.  Currently,
386; loop headers are affected by the weight of their corresponding back edges.
387define void @nonentry_header(i1 %x, i2 %y) {
388; CHECK-LABEL: Printing analysis {{.*}} for function 'nonentry_header':
389; CHECK-NEXT: block-frequency-info: nonentry_header
390entry:
391; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
392  br i1 %x, label %left, label %right, !prof !21
393
394left:
395; CHECK-NEXT: left: float = 0.14
396  br i1 %x, label %top, label %bottom, !prof !22
397
398right:
399; CHECK-NEXT: right: float = 0.42
400  br i1 %x, label %top, label %bottom, !prof !22
401
402top:
403; CHECK-NEXT: top: float = 8.43
404  switch i2 %y, label %exit [ i2 0, label %left
405                              i2 1, label %right
406                              i2 2, label %bottom ], !prof !23
407
408bottom:
409; CHECK-NEXT: bottom: float = 4.5,
410  br label %top
411
412exit:
413; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
414  ret void
415}
416!21 = !{!"branch_weights", i32 2, i32 1}
417!22 = !{!"branch_weights", i32 1, i32 1}
418!23 = !{!"branch_weights", i32 8, i32 1, i32 3, i32 12}
419