1 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/propagate.prof | opt -analyze -branch-prob | FileCheck %s
3 ; Original C++ code for this test case:
7 ; long foo(int x, int y, long N) {
11 ; for (long i = 0; i < N; i++) {
18 ; for (unsigned j = 0; j < i; j++) {
32 ; printf("foo(%d, %d, %ld) = %ld\n", x, y, N, foo(x, y, N));
36 ; ModuleID = 'propagate.cc'
37 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
38 target triple = "x86_64-unknown-linux-gnu"
40 @.str = private unnamed_addr constant [24 x i8] c"foo(%d, %d, %ld) = %ld\0A\00", align 1
42 ; Function Attrs: nounwind uwtable
43 define i64 @_Z3fooiil(i32 %x, i32 %y, i64 %N) #0 {
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 i32, align 4
51 store i32 %x, i32* %x.addr, align 4
52 store i32 %y, i32* %y.addr, align 4
53 store i64 %N, i64* %N.addr, align 8
54 %0 = load i32* %x.addr, align 4, !dbg !11
55 %1 = load i32* %y.addr, align 4, !dbg !11
56 %cmp = icmp slt i32 %0, %1, !dbg !11
57 br i1 %cmp, label %if.then, label %if.else, !dbg !11
59 if.then: ; preds = %entry
60 %2 = load i32* %y.addr, align 4, !dbg !13
61 %3 = load i32* %x.addr, align 4, !dbg !13
62 %sub = sub nsw i32 %2, %3, !dbg !13
63 %conv = sext i32 %sub to i64, !dbg !13
64 store i64 %conv, i64* %retval, !dbg !13
65 br label %return, !dbg !13
67 if.else: ; preds = %entry
68 store i64 0, i64* %i, align 8, !dbg !15
69 br label %for.cond, !dbg !15
71 for.cond: ; preds = %for.inc16, %if.else
72 %4 = load i64* %i, align 8, !dbg !15
73 %5 = load i64* %N.addr, align 8, !dbg !15
74 %cmp1 = icmp slt i64 %4, %5, !dbg !15
75 br i1 %cmp1, label %for.body, label %for.end18, !dbg !15
76 ; CHECK: edge for.cond -> for.body probability is 10 / 11 = 90.9091% [HOT edge]
77 ; CHECK: edge for.cond -> for.end18 probability is 1 / 11 = 9.09091%
79 for.body: ; preds = %for.cond
80 %6 = load i64* %i, align 8, !dbg !18
81 %7 = load i64* %N.addr, align 8, !dbg !18
82 %div = sdiv i64 %7, 3, !dbg !18
83 %cmp2 = icmp sgt i64 %6, %div, !dbg !18
84 br i1 %cmp2, label %if.then3, label %if.end, !dbg !18
85 ; CHECK: edge for.body -> if.then3 probability is 1 / 5 = 20%
86 ; CHECK: edge for.body -> if.end probability is 4 / 5 = 80%
88 if.then3: ; preds = %for.body
89 %8 = load i32* %x.addr, align 4, !dbg !21
90 %dec = add nsw i32 %8, -1, !dbg !21
91 store i32 %dec, i32* %x.addr, align 4, !dbg !21
92 br label %if.end, !dbg !21
94 if.end: ; preds = %if.then3, %for.body
95 %9 = load i64* %i, align 8, !dbg !22
96 %10 = load i64* %N.addr, align 8, !dbg !22
97 %div4 = sdiv i64 %10, 4, !dbg !22
98 %cmp5 = icmp sgt i64 %9, %div4, !dbg !22
99 br i1 %cmp5, label %if.then6, label %if.else7, !dbg !22
100 ; CHECK: edge if.end -> if.then6 probability is 3 / 6342 = 0.0473037%
101 ; CHECK: edge if.end -> if.else7 probability is 6339 / 6342 = 99.9527% [HOT edge]
103 if.then6: ; preds = %if.end
104 %11 = load i32* %y.addr, align 4, !dbg !24
105 %inc = add nsw i32 %11, 1, !dbg !24
106 store i32 %inc, i32* %y.addr, align 4, !dbg !24
107 %12 = load i32* %x.addr, align 4, !dbg !26
108 %add = add nsw i32 %12, 3, !dbg !26
109 store i32 %add, i32* %x.addr, align 4, !dbg !26
110 br label %if.end15, !dbg !27
112 if.else7: ; preds = %if.end
113 store i32 0, i32* %j, align 4, !dbg !28
114 br label %for.cond8, !dbg !28
116 for.cond8: ; preds = %for.inc, %if.else7
117 %13 = load i32* %j, align 4, !dbg !28
118 %conv9 = zext i32 %13 to i64, !dbg !28
119 %14 = load i64* %i, align 8, !dbg !28
120 %cmp10 = icmp slt i64 %conv9, %14, !dbg !28
121 br i1 %cmp10, label %for.body11, label %for.end, !dbg !28
122 ; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16192 = 99.9938% [HOT edge]
123 ; CHECK: edge for.cond8 -> for.end probability is 1 / 16192 = 0.00617589%
125 for.body11: ; preds = %for.cond8
126 %15 = load i32* %j, align 4, !dbg !31
127 %16 = load i32* %x.addr, align 4, !dbg !31
128 %add12 = add i32 %16, %15, !dbg !31
129 store i32 %add12, i32* %x.addr, align 4, !dbg !31
130 %17 = load i32* %y.addr, align 4, !dbg !33
131 %sub13 = sub nsw i32 %17, 3, !dbg !33
132 store i32 %sub13, i32* %y.addr, align 4, !dbg !33
133 br label %for.inc, !dbg !34
135 for.inc: ; preds = %for.body11
136 %18 = load i32* %j, align 4, !dbg !28
137 %inc14 = add i32 %18, 1, !dbg !28
138 store i32 %inc14, i32* %j, align 4, !dbg !28
139 br label %for.cond8, !dbg !28
141 for.end: ; preds = %for.cond8
144 if.end15: ; preds = %for.end, %if.then6
145 br label %for.inc16, !dbg !35
147 for.inc16: ; preds = %if.end15
148 %19 = load i64* %i, align 8, !dbg !15
149 %inc17 = add nsw i64 %19, 1, !dbg !15
150 store i64 %inc17, i64* %i, align 8, !dbg !15
151 br label %for.cond, !dbg !15
153 for.end18: ; preds = %for.cond
156 if.end19: ; preds = %for.end18
157 %20 = load i32* %y.addr, align 4, !dbg !36
158 %21 = load i32* %x.addr, align 4, !dbg !36
159 %mul = mul nsw i32 %20, %21, !dbg !36
160 %conv20 = sext i32 %mul to i64, !dbg !36
161 store i64 %conv20, i64* %retval, !dbg !36
162 br label %return, !dbg !36
164 return: ; preds = %if.end19, %if.then
165 %22 = load i64* %retval, !dbg !37
166 ret i64 %22, !dbg !37
169 ; Function Attrs: uwtable
170 define i32 @main() #1 {
172 %retval = alloca i32, align 4
173 %x = alloca i32, align 4
174 %y = alloca i32, align 4
175 %N = alloca i64, align 8
176 store i32 0, i32* %retval
177 store i32 5678, i32* %x, align 4, !dbg !38
178 store i32 1234, i32* %y, align 4, !dbg !39
179 store i64 999999, i64* %N, align 8, !dbg !40
180 %0 = load i32* %x, align 4, !dbg !41
181 %1 = load i32* %y, align 4, !dbg !41
182 %2 = load i64* %N, align 8, !dbg !41
183 %3 = load i32* %x, align 4, !dbg !41
184 %4 = load i32* %y, align 4, !dbg !41
185 %5 = load i64* %N, align 8, !dbg !41
186 %call = call i64 @_Z3fooiil(i32 %3, i32 %4, i64 %5), !dbg !41
187 %call1 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([24 x i8]* @.str, i32 0, i32 0), i32 %0, i32 %1, i64 %2, i64 %call), !dbg !41
191 declare i32 @printf(i8*, ...) #2
193 attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
194 attributes #1 = { uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
195 attributes #2 = { "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
198 !llvm.module.flags = !{!8, !9}
201 !0 = metadata !{i32 786449, metadata !1, i32 4, metadata !"clang version 3.5 ", i1 false, metadata !"", i32 0, metadata !2, metadata !2, metadata !3, metadata !2, metadata !2, metadata !""} ; [ DW_TAG_compile_unit ] [propagate.cc] [DW_LANG_C_plus_plus]
202 !1 = metadata !{metadata !"propagate.cc", metadata !"."}
203 !2 = metadata !{i32 0}
204 !3 = metadata !{metadata !4, metadata !7}
205 !4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"foo", metadata !"foo", metadata !"", i32 3, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 false, i64 (i32, i32, i64)* @_Z3fooiil, null, null, metadata !2, i32 3} ; [ DW_TAG_subprogram ] [line 3] [def] [foo]
206 !5 = metadata !{i32 786473, metadata !1} ; [ DW_TAG_file_type ] [propagate.cc]
207 !6 = metadata !{i32 786453, i32 0, null, metadata !"", i32 0, i64 0, i64 0, i64 0, i32 0, null, metadata !2, i32 0, null, null, null} ; [ DW_TAG_subroutine_type ] [line 0, size 0, align 0, offset 0] [from ]
208 !7 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"main", metadata !"main", metadata !"", i32 24, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 false, i32 ()* @main, null, null, metadata !2, i32 24} ; [ DW_TAG_subprogram ] [line 24] [def] [main]
209 !8 = metadata !{i32 2, metadata !"Dwarf Version", i32 4}
210 !9 = metadata !{i32 1, metadata !"Debug Info Version", i32 1}
211 !10 = metadata !{metadata !"clang version 3.5 "}
212 !11 = metadata !{i32 4, i32 0, metadata !12, null}
213 !12 = metadata !{i32 786443, metadata !1, metadata !4, i32 4, i32 0, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [propagate.cc]
214 !13 = metadata !{i32 5, i32 0, metadata !14, null}
215 !14 = metadata !{i32 786443, metadata !1, metadata !12, i32 4, i32 0, i32 0, i32 1} ; [ DW_TAG_lexical_block ] [propagate.cc]
216 !15 = metadata !{i32 7, i32 0, metadata !16, null}
217 !16 = metadata !{i32 786443, metadata !1, metadata !17, i32 7, i32 0, i32 0, i32 3} ; [ DW_TAG_lexical_block ] [propagate.cc]
218 !17 = metadata !{i32 786443, metadata !1, metadata !12, i32 6, i32 0, i32 0, i32 2} ; [ DW_TAG_lexical_block ] [propagate.cc]
219 !18 = metadata !{i32 8, i32 0, metadata !19, null} ; [ DW_TAG_imported_declaration ]
220 !19 = metadata !{i32 786443, metadata !1, metadata !20, i32 8, i32 0, i32 0, i32 5} ; [ DW_TAG_lexical_block ] [propagate.cc]
221 !20 = metadata !{i32 786443, metadata !1, metadata !16, i32 7, i32 0, i32 0, i32 4} ; [ DW_TAG_lexical_block ] [propagate.cc]
222 !21 = metadata !{i32 9, i32 0, metadata !19, null}
223 !22 = metadata !{i32 10, i32 0, metadata !23, null}
224 !23 = metadata !{i32 786443, metadata !1, metadata !20, i32 10, i32 0, i32 0, i32 6} ; [ DW_TAG_lexical_block ] [propagate.cc]
225 !24 = metadata !{i32 11, i32 0, metadata !25, null}
226 !25 = metadata !{i32 786443, metadata !1, metadata !23, i32 10, i32 0, i32 0, i32 7} ; [ DW_TAG_lexical_block ] [propagate.cc]
227 !26 = metadata !{i32 12, i32 0, metadata !25, null}
228 !27 = metadata !{i32 13, i32 0, metadata !25, null}
229 !28 = metadata !{i32 14, i32 0, metadata !29, null}
230 !29 = metadata !{i32 786443, metadata !1, metadata !30, i32 14, i32 0, i32 0, i32 9} ; [ DW_TAG_lexical_block ] [propagate.cc]
231 !30 = metadata !{i32 786443, metadata !1, metadata !23, i32 13, i32 0, i32 0, i32 8} ; [ DW_TAG_lexical_block ] [propagate.cc]
232 !31 = metadata !{i32 15, i32 0, metadata !32, null}
233 !32 = metadata !{i32 786443, metadata !1, metadata !29, i32 14, i32 0, i32 0, i32 10} ; [ DW_TAG_lexical_block ] [propagate.cc]
234 !33 = metadata !{i32 16, i32 0, metadata !32, null}
235 !34 = metadata !{i32 17, i32 0, metadata !32, null}
236 !35 = metadata !{i32 19, i32 0, metadata !20, null}
237 !36 = metadata !{i32 21, i32 0, metadata !4, null}
238 !37 = metadata !{i32 22, i32 0, metadata !4, null}
239 !38 = metadata !{i32 25, i32 0, metadata !7, null}
240 !39 = metadata !{i32 26, i32 0, metadata !7, null}
241 !40 = metadata !{i32 27, i32 0, metadata !7, null}
242 !41 = metadata !{i32 28, i32 0, metadata !7, null}
243 !42 = metadata !{i32 29, i32 0, metadata !7, null}