xref: /llvm-project/llvm/test/Transforms/SampleProfile/propagate.ll (revision bb6497ffa6a88d1b3a32101d9b6519094d75ef2a) 
1; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/propagate.prof | opt -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
2
3; Original C++ code for this test case:
4;
5; #include <stdio.h>
6;
7; long foo(int x, int y, long N) {
8;   if (x < y) {
9;     return y - x;
10;   } else {
11;     for (long i = 0; i < N; i++) {
12;       if (i > N / 3)
13;         x--;
14;       if (i > N / 4) {
15;         y++;
16;         x += 3;
17;       } else {
18;         for (unsigned j = 0; j < 100; j++) {
19;           x += j;
20;           y -= 3;
21;         }
22;       }
23;     }
24;   }
25;   return y * x;
26; }
27;
28; int main() {
29;   int x = 5678;
30;   int y = 1234;
31;   long N = 9999999;
32;   printf("foo(%d, %d, %ld) = %ld\n", x, y, N, foo(x, y, N));
33;   return 0;
34; }
35
36; ModuleID = 'propagate.cc'
37target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
38target triple = "x86_64-unknown-linux-gnu"
39
40@.str = private unnamed_addr constant [24 x i8] c"foo(%d, %d, %ld) = %ld\0A\00", align 1
41
42; Function Attrs: nounwind uwtable
43define i64 @_Z3fooiil(i32 %x, i32 %y, i64 %N) #0 !dbg !6 {
44entry:
45  %retval = alloca i64, align 8
46  %x.addr = alloca i32, align 4
47  %y.addr = alloca i32, align 4
48  %N.addr = alloca i64, align 8
49  %i = alloca i64, align 8
50  %j = alloca i64, align 8
51  store i32 %x, ptr %x.addr, align 4
52  call void @llvm.dbg.declare(metadata ptr %x.addr, metadata !11, metadata !12), !dbg !13
53  store i32 %y, ptr %y.addr, align 4
54  call void @llvm.dbg.declare(metadata ptr %y.addr, metadata !14, metadata !12), !dbg !15
55  store i64 %N, ptr %N.addr, align 8
56  call void @llvm.dbg.declare(metadata ptr %N.addr, metadata !16, metadata !12), !dbg !17
57  %0 = load i32, ptr %x.addr, align 4, !dbg !18
58  %1 = load i32, ptr %y.addr, align 4, !dbg !20
59  %cmp = icmp slt i32 %0, %1, !dbg !21
60  br i1 %cmp, label %if.then, label %if.else, !dbg !22
61
62if.then:                                          ; preds = %entry
63  %2 = load i32, ptr %y.addr, align 4, !dbg !23
64  %3 = load i32, ptr %x.addr, align 4, !dbg !25
65  %sub = sub nsw i32 %2, %3, !dbg !26
66  %conv = sext i32 %sub to i64, !dbg !23
67  store i64 %conv, ptr %retval, align 8, !dbg !27
68  br label %return, !dbg !27
69
70if.else:                                          ; preds = %entry
71  call void @llvm.dbg.declare(metadata ptr %i, metadata !28, metadata !12), !dbg !31
72  store i64 0, ptr %i, align 8, !dbg !31
73  br label %for.cond, !dbg !32
74
75for.cond:                                         ; preds = %for.inc17, %if.else
76  %4 = load i64, ptr %i, align 8, !dbg !33
77  %5 = load i64, ptr %N.addr, align 8, !dbg !36
78  %cmp1 = icmp slt i64 %4, %5, !dbg !37
79  br i1 %cmp1, label %for.body, label %for.end19, !dbg !38
80
81for.body:                                         ; preds = %for.cond
82  %6 = load i64, ptr %i, align 8, !dbg !39
83  %7 = load i64, ptr %N.addr, align 8, !dbg !42
84  %div = sdiv i64 %7, 3, !dbg !43
85  %cmp2 = icmp sgt i64 %6, %div, !dbg !44
86  br i1 %cmp2, label %if.then3, label %if.end, !dbg !45
87; CHECK:  edge %for.body -> %if.then3 probability is 0x51292fa6 / 0x80000000 = 63.41%
88; CHECK:  edge %for.body -> %if.end probability is 0x2ed6d05a / 0x80000000 = 36.59%
89
90if.then3:                                         ; preds = %for.body
91  %8 = load i32, ptr %x.addr, align 4, !dbg !46
92  %dec = add nsw i32 %8, -1, !dbg !46
93  store i32 %dec, ptr %x.addr, align 4, !dbg !46
94  br label %if.end, !dbg !47
95
96if.end:                                           ; preds = %if.then3, %for.body
97  %9 = load i64, ptr %i, align 8, !dbg !48
98  %10 = load i64, ptr %N.addr, align 8, !dbg !50
99  %div4 = sdiv i64 %10, 4, !dbg !51
100  %cmp5 = icmp sgt i64 %9, %div4, !dbg !52
101  br i1 %cmp5, label %if.then6, label %if.else7, !dbg !53
102; CHECK:  edge %if.end -> %if.then6 probability is 0x5d89d89e / 0x80000000 = 73.08%
103; CHECK:  edge %if.end -> %if.else7 probability is 0x22762762 / 0x80000000 = 26.92%
104
105if.then6:                                         ; preds = %if.end
106  %11 = load i32, ptr %y.addr, align 4, !dbg !54
107  %inc = add nsw i32 %11, 1, !dbg !54
108  store i32 %inc, ptr %y.addr, align 4, !dbg !54
109  %12 = load i32, ptr %x.addr, align 4, !dbg !56
110  %add = add nsw i32 %12, 3, !dbg !56
111  store i32 %add, ptr %x.addr, align 4, !dbg !56
112  br label %if.end16, !dbg !57
113
114if.else7:                                         ; preds = %if.end
115  call void @llvm.dbg.declare(metadata ptr %j, metadata !58, metadata !12), !dbg !62
116  store i64 0, ptr %j, align 8, !dbg !62
117  br label %for.cond8, !dbg !63
118
119for.cond8:                                        ; preds = %for.inc, %if.else7
120  %13 = load i64, ptr %j, align 8, !dbg !64
121  %cmp9 = icmp slt i64 %13, 100, !dbg !67
122  br i1 %cmp9, label %for.body10, label %for.end, !dbg !68
123; CHECK: edge %for.cond8 -> %for.body10 probability is 0x7e941a89 / 0x80000000 = 98.89% [HOT edge]
124; CHECK: edge %for.cond8 -> %for.end probability is 0x016be577 / 0x80000000 = 1.11%
125
126
127for.body10:                                       ; preds = %for.cond8
128  %14 = load i64, ptr %j, align 8, !dbg !69
129  %15 = load i32, ptr %x.addr, align 4, !dbg !71
130  %conv11 = sext i32 %15 to i64, !dbg !71
131  %add12 = add nsw i64 %conv11, %14, !dbg !71
132  %conv13 = trunc i64 %add12 to i32, !dbg !71
133  store i32 %conv13, ptr %x.addr, align 4, !dbg !71
134  %16 = load i32, ptr %y.addr, align 4, !dbg !72
135  %sub14 = sub nsw i32 %16, 3, !dbg !72
136  store i32 %sub14, ptr %y.addr, align 4, !dbg !72
137  br label %for.inc, !dbg !73
138
139for.inc:                                          ; preds = %for.body10
140  %17 = load i64, ptr %j, align 8, !dbg !74
141  %inc15 = add nsw i64 %17, 1, !dbg !74
142  store i64 %inc15, ptr %j, align 8, !dbg !74
143  br label %for.cond8, !dbg !76
144
145for.end:                                          ; preds = %for.cond8
146  br label %if.end16
147
148if.end16:                                         ; preds = %for.end, %if.then6
149  br label %for.inc17, !dbg !77
150
151for.inc17:                                        ; preds = %if.end16
152  %18 = load i64, ptr %i, align 8, !dbg !78
153  %inc18 = add nsw i64 %18, 1, !dbg !78
154  store i64 %inc18, ptr %i, align 8, !dbg !78
155  br label %for.cond, !dbg !80
156
157for.end19:                                        ; preds = %for.cond
158  br label %if.end20
159
160if.end20:                                         ; preds = %for.end19
161  %19 = load i32, ptr %y.addr, align 4, !dbg !81
162  %20 = load i32, ptr %x.addr, align 4, !dbg !82
163  %mul = mul nsw i32 %19, %20, !dbg !83
164  %conv21 = sext i32 %mul to i64, !dbg !81
165  store i64 %conv21, ptr %retval, align 8, !dbg !84
166  br label %return, !dbg !84
167
168return:                                           ; preds = %if.end20, %if.then
169  %21 = load i64, ptr %retval, align 8, !dbg !85
170  ret i64 %21, !dbg !85
171}
172
173; Function Attrs: nounwind readnone
174declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
175
176; Function Attrs: norecurse uwtable
177define i32 @main() #2 !dbg !86 {
178entry:
179  %retval = alloca i32, align 4
180  %x = alloca i32, align 4
181  %y = alloca i32, align 4
182  %N = alloca i64, align 8
183  store i32 0, ptr %retval, align 4
184  call void @llvm.dbg.declare(metadata ptr %x, metadata !89, metadata !12), !dbg !90
185  store i32 5678, ptr %x, align 4, !dbg !90
186  call void @llvm.dbg.declare(metadata ptr %y, metadata !91, metadata !12), !dbg !92
187  store i32 1234, ptr %y, align 4, !dbg !92
188  call void @llvm.dbg.declare(metadata ptr %N, metadata !93, metadata !12), !dbg !94
189  store i64 9999999, ptr %N, align 8, !dbg !94
190  %0 = load i32, ptr %x, align 4, !dbg !95
191  %1 = load i32, ptr %y, align 4, !dbg !96
192  %2 = load i64, ptr %N, align 8, !dbg !97
193  %3 = load i32, ptr %x, align 4, !dbg !98
194  %4 = load i32, ptr %y, align 4, !dbg !99
195  %5 = load i64, ptr %N, align 8, !dbg !100
196  %call = call i64 @_Z3fooiil(i32 %3, i32 %4, i64 %5), !dbg !101
197  %call1 = call i32 (ptr, ...) @printf(ptr @.str, i32 %0, i32 %1, i64 %2, i64 %call), !dbg !102
198  ret i32 0, !dbg !104
199}
200
201declare i32 @printf(ptr, ...) #3
202
203attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "frame-pointer"="all" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" "use-sample-profile" }
204attributes #1 = { nounwind readnone }
205attributes #2 = { norecurse uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "frame-pointer"="all" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" "use-sample-profile" }
206attributes #3 = { "disable-tail-calls"="false" "less-precise-fpmad"="false" "frame-pointer"="all" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
207
208!llvm.dbg.cu = !{!0}
209!llvm.module.flags = !{!3, !4}
210!llvm.ident = !{!5}
211
212!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.9.0 (trunk 266819)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
213!1 = !DIFile(filename: "propagate.cc", directory: ".")
214!2 = !{}
215!3 = !{i32 2, !"Dwarf Version", i32 4}
216!4 = !{i32 2, !"Debug Info Version", i32 3}
217!5 = !{!"clang version 3.9.0 (trunk 266819)"}
218!6 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooiil", scope: !1, file: !1, line: 3, type: !7, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, unit: !0, retainedNodes: !2)
219!7 = !DISubroutineType(types: !8)
220!8 = !{!9, !10, !10, !9}
221!9 = !DIBasicType(name: "long int", size: 64, align: 64, encoding: DW_ATE_signed)
222!10 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
223!11 = !DILocalVariable(name: "x", arg: 1, scope: !6, file: !1, line: 3, type: !10)
224!12 = !DIExpression()
225!13 = !DILocation(line: 3, column: 14, scope: !6)
226!14 = !DILocalVariable(name: "y", arg: 2, scope: !6, file: !1, line: 3, type: !10)
227!15 = !DILocation(line: 3, column: 21, scope: !6)
228!16 = !DILocalVariable(name: "N", arg: 3, scope: !6, file: !1, line: 3, type: !9)
229!17 = !DILocation(line: 3, column: 29, scope: !6)
230!18 = !DILocation(line: 4, column: 7, scope: !19)
231!19 = distinct !DILexicalBlock(scope: !6, file: !1, line: 4, column: 7)
232!20 = !DILocation(line: 4, column: 11, scope: !19)
233!21 = !DILocation(line: 4, column: 9, scope: !19)
234!22 = !DILocation(line: 4, column: 7, scope: !6)
235!23 = !DILocation(line: 5, column: 12, scope: !24)
236!24 = distinct !DILexicalBlock(scope: !19, file: !1, line: 4, column: 14)
237!25 = !DILocation(line: 5, column: 16, scope: !24)
238!26 = !DILocation(line: 5, column: 14, scope: !24)
239!27 = !DILocation(line: 5, column: 5, scope: !24)
240!28 = !DILocalVariable(name: "i", scope: !29, file: !1, line: 7, type: !9)
241!29 = distinct !DILexicalBlock(scope: !30, file: !1, line: 7, column: 5)
242!30 = distinct !DILexicalBlock(scope: !19, file: !1, line: 6, column: 10)
243!31 = !DILocation(line: 7, column: 15, scope: !29)
244!32 = !DILocation(line: 7, column: 10, scope: !29)
245!33 = !DILocation(line: 7, column: 22, scope: !34)
246!34 = !DILexicalBlockFile(scope: !35, file: !1, discriminator: 2)
247!35 = distinct !DILexicalBlock(scope: !29, file: !1, line: 7, column: 5)
248!36 = !DILocation(line: 7, column: 26, scope: !34)
249!37 = !DILocation(line: 7, column: 24, scope: !34)
250!38 = !DILocation(line: 7, column: 5, scope: !34)
251!39 = !DILocation(line: 8, column: 11, scope: !40)
252!40 = distinct !DILexicalBlock(scope: !41, file: !1, line: 8, column: 11)
253!41 = distinct !DILexicalBlock(scope: !35, file: !1, line: 7, column: 34)
254!42 = !DILocation(line: 8, column: 15, scope: !40)
255!43 = !DILocation(line: 8, column: 17, scope: !40)
256!44 = !DILocation(line: 8, column: 13, scope: !40)
257!45 = !DILocation(line: 8, column: 11, scope: !41)
258!46 = !DILocation(line: 9, column: 10, scope: !40)
259!47 = !DILocation(line: 9, column: 9, scope: !40)
260!48 = !DILocation(line: 10, column: 11, scope: !49)
261!49 = distinct !DILexicalBlock(scope: !41, file: !1, line: 10, column: 11)
262!50 = !DILocation(line: 10, column: 15, scope: !49)
263!51 = !DILocation(line: 10, column: 17, scope: !49)
264!52 = !DILocation(line: 10, column: 13, scope: !49)
265!53 = !DILocation(line: 10, column: 11, scope: !41)
266!54 = !DILocation(line: 11, column: 10, scope: !55)
267!55 = distinct !DILexicalBlock(scope: !49, file: !1, line: 10, column: 22)
268!56 = !DILocation(line: 12, column: 11, scope: !55)
269!57 = !DILocation(line: 13, column: 7, scope: !55)
270!58 = !DILocalVariable(name: "j", scope: !59, file: !1, line: 14, type: !61)
271!59 = distinct !DILexicalBlock(scope: !60, file: !1, line: 14, column: 9)
272!60 = distinct !DILexicalBlock(scope: !49, file: !1, line: 13, column: 14)
273!61 = !DIBasicType(name: "long long int", size: 64, align: 64, encoding: DW_ATE_signed)
274!62 = !DILocation(line: 14, column: 24, scope: !59)
275!63 = !DILocation(line: 14, column: 14, scope: !59)
276!64 = !DILocation(line: 14, column: 31, scope: !65)
277!65 = !DILexicalBlockFile(scope: !66, file: !1, discriminator: 2)
278!66 = distinct !DILexicalBlock(scope: !59, file: !1, line: 14, column: 9)
279!67 = !DILocation(line: 14, column: 33, scope: !65)
280!68 = !DILocation(line: 14, column: 9, scope: !65)
281!69 = !DILocation(line: 15, column: 16, scope: !70)
282!70 = distinct !DILexicalBlock(scope: !66, file: !1, line: 14, column: 45)
283!71 = !DILocation(line: 15, column: 13, scope: !70)
284!72 = !DILocation(line: 16, column: 13, scope: !70)
285!73 = !DILocation(line: 17, column: 9, scope: !70)
286!74 = !DILocation(line: 14, column: 41, scope: !75)
287!75 = !DILexicalBlockFile(scope: !66, file: !1, discriminator: 4)
288!76 = !DILocation(line: 14, column: 9, scope: !75)
289!77 = !DILocation(line: 19, column: 5, scope: !41)
290!78 = !DILocation(line: 7, column: 30, scope: !79)
291!79 = !DILexicalBlockFile(scope: !35, file: !1, discriminator: 4)
292!80 = !DILocation(line: 7, column: 5, scope: !79)
293!81 = !DILocation(line: 21, column: 10, scope: !6)
294!82 = !DILocation(line: 21, column: 14, scope: !6)
295!83 = !DILocation(line: 21, column: 12, scope: !6)
296!84 = !DILocation(line: 21, column: 3, scope: !6)
297!85 = !DILocation(line: 22, column: 1, scope: !6)
298!86 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 24, type: !87, isLocal: false, isDefinition: true, scopeLine: 24, flags: DIFlagPrototyped, isOptimized: false, unit: !0, retainedNodes: !2)
299!87 = !DISubroutineType(types: !88)
300!88 = !{!10}
301!89 = !DILocalVariable(name: "x", scope: !86, file: !1, line: 25, type: !10)
302!90 = !DILocation(line: 25, column: 7, scope: !86)
303!91 = !DILocalVariable(name: "y", scope: !86, file: !1, line: 26, type: !10)
304!92 = !DILocation(line: 26, column: 7, scope: !86)
305!93 = !DILocalVariable(name: "N", scope: !86, file: !1, line: 27, type: !9)
306!94 = !DILocation(line: 27, column: 8, scope: !86)
307!95 = !DILocation(line: 28, column: 38, scope: !86)
308!96 = !DILocation(line: 28, column: 41, scope: !86)
309!97 = !DILocation(line: 28, column: 44, scope: !86)
310!98 = !DILocation(line: 28, column: 51, scope: !86)
311!99 = !DILocation(line: 28, column: 54, scope: !86)
312!100 = !DILocation(line: 28, column: 57, scope: !86)
313!101 = !DILocation(line: 28, column: 47, scope: !86)
314!102 = !DILocation(line: 28, column: 3, scope: !103)
315!103 = !DILexicalBlockFile(scope: !86, file: !1, discriminator: 2)
316!104 = !DILocation(line: 29, column: 3, scope: !86)
317