1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -jump-table-density=25 | FileCheck %s --check-prefix=DENSE --check-prefix=CHECK
; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -jump-table-density=10 | FileCheck %s --check-prefix=SPARSE --check-prefix=CHECK
declare void @g(i32)
define void @sparse(i32 %x) {
entry:
switch i32 %x, label %return [
i32 300, label %bb0
i32 100, label %bb1
i32 400, label %bb1
i32 500, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
return: ret void
; Should pivot around 400 for two subtrees with two jump tables each.
; CHECK-LABEL: sparse
; CHECK-NOT: cmpl
; CHECK: cmpl $399
; CHECK: cmpl $100
; CHECK: cmpl $300
; CHECK: cmpl $400
; CHECK: cmpl $500
}
define void @med(i32 %x) {
entry:
switch i32 %x, label %return [
i32 30, label %bb0
i32 10, label %bb1
i32 40, label %bb1
i32 50, label %bb2
i32 20, label %bb3
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
bb3: tail call void @g(i32 2) br label %return
return: ret void
; Lowered as a jump table when sparse, and branches when dense.
; CHECK-LABEL: med
; SPARSE: addl $-10
; SPARSE: cmpl $40
; SPARSE: ja
; SPARSE: jmpq *.LJTI
; DENSE-NOT: cmpl
; DENSE: cmpl $29
; DENSE-DAG: cmpl $10
; DENSE-DAG: cmpl $20
; DENSE-DAG: cmpl $30
; DENSE-DAG: cmpl $40
; DENSE-DAG: cmpl $50
; DENSE: retq
}
define void @dense(i32 %x) {
entry:
switch i32 %x, label %return [
i32 12, label %bb0
i32 4, label %bb1
i32 16, label %bb1
i32 20, label %bb2
i32 8, label %bb3
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
bb3: tail call void @g(i32 2) br label %return
return: ret void
; Lowered as a jump table when sparse, and branches when dense.
; CHECK-LABEL: dense
; CHECK: addl $-4
; CHECK: cmpl $16
; CHECK: ja
; CHECK: jmpq *.LJTI
}
define void @dense_optsize(i32 %x) optsize {
entry:
switch i32 %x, label %return [
i32 12, label %bb0
i32 4, label %bb1
i32 16, label %bb1
i32 20, label %bb2
i32 8, label %bb3
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
bb3: tail call void @g(i32 2) br label %return
return: ret void
; Lowered as branches.
; CHECK-LABEL: dense_optsize
; CHECK: cmpl $11
; CHECK: cmpl $20
; CHECK: cmpl $16
; CHECK: cmpl $12
; CHECK: cmpl $4
; CHECK: cmpl $8
; CHECK: retq
}
define void @dense_pgso(i32 %x) !prof !14 {
entry:
switch i32 %x, label %return [
i32 12, label %bb0
i32 4, label %bb1
i32 16, label %bb1
i32 20, label %bb2
i32 8, label %bb3
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
bb3: tail call void @g(i32 2) br label %return
return: ret void
; Lowered as branches.
; CHECK-LABEL: dense_pgso
; CHECK: cmpl $11
; CHECK: cmpl $20
; CHECK: cmpl $16
; CHECK: cmpl $12
; CHECK: cmpl $4
; CHECK: cmpl $8
; CHECK: retq
}
!llvm.module.flags = !{!0}
!0 = !{i32 1, !"ProfileSummary", !1}
!1 = !{!2, !3, !4, !5, !6, !7, !8, !9}
!2 = !{!"ProfileFormat", !"InstrProf"}
!3 = !{!"TotalCount", i64 10000}
!4 = !{!"MaxCount", i64 10}
!5 = !{!"MaxInternalCount", i64 1}
!6 = !{!"MaxFunctionCount", i64 1000}
!7 = !{!"NumCounts", i64 3}
!8 = !{!"NumFunctions", i64 3}
!9 = !{!"DetailedSummary", !10}
!10 = !{!11, !12, !13}
!11 = !{i32 10000, i64 100, i32 1}
!12 = !{i32 999000, i64 100, i32 1}
!13 = !{i32 999999, i64 1, i32 2}
!14 = !{!"function_entry_count", i64 0}
|
