← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to test/Analysis/BlockFrequencyInfo/irreducible.ll

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
test/Analysis/BlockFrequencyInfo/irreducible.ll
 
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
 
8
define void @multiexit(i1 %x) {
 
9
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
10
entry:
 
11
  br label %loop.1
 
12
 
 
13
; CHECK-NEXT: loop.1: float = 2.0,
 
14
loop.1:
 
15
  br i1 %x, label %exit.1, label %loop.2, !prof !0
 
16
 
 
17
; CHECK-NEXT: loop.2: float = 1.75,
 
18
loop.2:
 
19
  br i1 %x, label %exit.2, label %loop.1, !prof !1
 
20
 
 
21
; CHECK-NEXT: exit.1: float = 0.25,
 
22
exit.1:
 
23
  br label %return
 
24
 
 
25
; CHECK-NEXT: exit.2: float = 0.75,
 
26
exit.2:
 
27
  br label %return
 
28
 
 
29
; CHECK-NEXT: return: float = 1.0, int = [[ENTRY]]
 
30
return:
 
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.
 
93
define void @multientry(i1 %x) {
 
94
; CHECK-LABEL: Printing analysis {{.*}} for function 'multientry':
 
95
; CHECK-NEXT: block-frequency-info: multientry
 
96
entry:
 
97
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
98
  br i1 %x, label %c1, label %c2, !prof !2
 
99
 
 
100
c1:
 
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
 
 
105
c2:
 
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
 
 
110
exit:
 
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.
 
133
define void @crossloops(i2 %x) {
 
134
; CHECK-LABEL: Printing analysis {{.*}} for function 'crossloops':
 
135
; CHECK-NEXT: block-frequency-info: crossloops
 
136
entry:
 
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
 
 
141
c1:
 
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
 
 
146
c2:
 
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
 
 
151
exit:
 
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.
 
159
define 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
 
162
entry:
 
163
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
164
  br label %loop
 
165
 
 
166
loop:
 
167
; CHECK-NEXT: loop: float = 4.0, int = [[HEAD:[0-9]+]]
 
168
  br i1 %x, label %left, label %right, !prof !4
 
169
 
 
170
left:
 
171
; CHECK-NEXT: left: float = 8.0,
 
172
  br i1 %x, label %right, label %loop.end, !prof !5
 
173
 
 
174
right:
 
175
; CHECK-NEXT: right: float = 8.0,
 
176
  br i1 %x, label %left, label %loop.end, !prof !5
 
177
 
 
178
loop.end:
 
179
; CHECK-NEXT: loop.end: float = 4.0, int = [[HEAD]]
 
180
  br i1 %x, label %loop, label %exit, !prof !5
 
181
 
 
182
exit:
 
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.
 
190
define void @two_sccs(i1 %x) {
 
191
; CHECK-LABEL: Printing analysis {{.*}} for function 'two_sccs':
 
192
; CHECK-NEXT: block-frequency-info: two_sccs
 
193
entry:
 
194
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
195
  br i1 %x, label %a, label %b, !prof !6
 
196
 
 
197
a:
 
198
; CHECK-NEXT: a: float = 0.75,
 
199
  br i1 %x, label %a.left, label %a.right, !prof !7
 
200
 
 
201
a.left:
 
202
; CHECK-NEXT: a.left: float = 1.5,
 
203
  br i1 %x, label %a.right, label %exit, !prof !6
 
204
 
 
205
a.right:
 
206
; CHECK-NEXT: a.right: float = 1.5,
 
207
  br i1 %x, label %a.left, label %exit, !prof !6
 
208
 
 
209
b:
 
210
; CHECK-NEXT: b: float = 0.25,
 
211
  br i1 %x, label %b.left, label %b.right, !prof !7
 
212
 
 
213
b.left:
 
214
; CHECK-NEXT: b.left: float = 0.625,
 
215
  br i1 %x, label %b.right, label %exit, !prof !8
 
216
 
 
217
b.right:
 
218
; CHECK-NEXT: b.right: float = 0.625,
 
219
  br i1 %x, label %b.left, label %exit, !prof !8
 
220
 
 
221
exit:
 
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.
 
230
define 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
 
233
entry:
 
234
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
235
  br i1 %x, label %left, label %right, !prof !9
 
236
 
 
237
left:
 
238
; CHECK-NEXT: left: float = 2.0,
 
239
  br i1 %x, label %right, label %exit, !prof !10
 
240
 
 
241
right:
 
242
; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]
 
243
  br label %loop
 
244
 
 
245
loop:
 
246
; CHECK-NEXT: loop: float = 6.0,
 
247
  br i1 %x, label %loop, label %right.end, !prof !11
 
248
 
 
249
right.end:
 
250
; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]
 
251
  br i1 %x, label %left, label %exit, !prof !10
 
252
 
 
253
exit:
 
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.
 
262
define 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
 
265
entry:
 
266
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
267
  br label %loop
 
268
 
 
269
loop:
 
270
; CHECK-NEXT: loop: float = 2.0, int = [[LOOP:[0-9]+]]
 
271
  br i1 %x, label %normal, label %irreducible.entry, !prof !12
 
272
 
 
273
normal:
 
274
; CHECK-NEXT: normal: float = 1.5,
 
275
  br label %loop.end
 
276
 
 
277
irreducible.entry:
 
278
; CHECK-NEXT: irreducible.entry: float = 0.5, int = [[IRREDUCIBLE:[0-9]+]]
 
279
  br i1 %x, label %left, label %right, !prof !13
 
280
 
 
281
left:
 
282
; CHECK-NEXT: left: float = 1.0,
 
283
  br i1 %x, label %right, label %irreducible.exit, !prof !12
 
284
 
 
285
right:
 
286
; CHECK-NEXT: right: float = 1.0,
 
287
  br i1 %x, label %left, label %irreducible.exit, !prof !12
 
288
 
 
289
irreducible.exit:
 
290
; CHECK-NEXT: irreducible.exit: float = 0.5, int = [[IRREDUCIBLE]]
 
291
  br label %loop.end
 
292
 
 
293
loop.end:
 
294
; CHECK-NEXT: loop.end: float = 2.0, int = [[LOOP]]
 
295
  br i1 %x, label %loop, label %exit, !prof !13
 
296
 
 
297
exit:
 
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.
 
305
define 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
 
308
entry:
 
309
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
310
  br label %loop
 
311
 
 
312
loop:
 
313
; CHECK-NEXT: loop: float = 3.0, int = [[LOOP:[0-9]+]]
 
314
  br i1 %x, label %normal, label %irreducible, !prof !14
 
315
 
 
316
normal:
 
317
; CHECK-NEXT: normal: float = 2.0,
 
318
  br label %loop.end
 
319
 
 
320
irreducible:
 
321
; CHECK-NEXT: irreducible: float = 1.0,
 
322
  br i1 %x, label %left, label %right, !prof !15
 
323
 
 
324
left:
 
325
; CHECK-NEXT: left: float = 2.0,
 
326
  br i1 %x, label %right, label %loop.end, !prof !16
 
327
 
 
328
right:
 
329
; CHECK-NEXT: right: float = 2.0, int = [[RIGHT:[0-9]+]]
 
330
  br label %right.loop
 
331
 
 
332
right.loop:
 
333
; CHECK-NEXT: right.loop: float = 10.0,
 
334
  br i1 %x, label %right.loop, label %right.end, !prof !17
 
335
 
 
336
right.end:
 
337
; CHECK-NEXT: right.end: float = 2.0, int = [[RIGHT]]
 
338
  br i1 %x, label %left, label %loop.end, !prof !16
 
339
 
 
340
loop.end:
 
341
; CHECK-NEXT: loop.end: float = 3.0, int = [[LOOP]]
 
342
  br i1 %x, label %loop, label %exit, !prof !14
 
343
 
 
344
exit:
 
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.
 
354
define void @nonheader(i1 %x) {
 
355
; CHECK-LABEL: Printing analysis {{.*}} for function 'nonheader':
 
356
; CHECK-NEXT: block-frequency-info: nonheader
 
357
entry:
 
358
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
359
  br i1 %x, label %left, label %right, !prof !18
 
360
 
 
361
left:
 
362
; CHECK-NEXT: left: float = 1.0,
 
363
  br i1 %x, label %bottom, label %exit, !prof !19
 
364
 
 
365
right:
 
366
; CHECK-NEXT: right: float = 1.0,
 
367
  br i1 %x, label %bottom, label %exit, !prof !20
 
368
 
 
369
bottom:
 
370
; CHECK-NEXT: bottom: float = 1.0,
 
371
  br i1 %x, label %left, label %right, !prof !18
 
372
 
 
373
exit:
 
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.
 
387
define void @nonentry_header(i1 %x, i2 %y) {
 
388
; CHECK-LABEL: Printing analysis {{.*}} for function 'nonentry_header':
 
389
; CHECK-NEXT: block-frequency-info: nonentry_header
 
390
entry:
 
391
; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 
392
  br i1 %x, label %left, label %right, !prof !21
 
393
 
 
394
left:
 
395
; CHECK-NEXT: left: float = 0.14
 
396
  br i1 %x, label %top, label %bottom, !prof !22
 
397
 
 
398
right:
 
399
; CHECK-NEXT: right: float = 0.42
 
400
  br i1 %x, label %top, label %bottom, !prof !22
 
401
 
 
402
top:
 
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
 
 
408
bottom:
 
409
; CHECK-NEXT: bottom: float = 4.5,
 
410
  br label %top
 
411
 
 
412
exit:
 
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}