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 = !{!"0x11\004\00clang version 3.5 \000\00\000\00\000", !1, !2, !2, !3, !2, !2} ; [ DW_TAG_compile_unit ] [propagate.cc] [DW_LANG_C_plus_plus]
202 !1 = !{!"propagate.cc", !"."}
205 !4 = !{!"0x2e\00foo\00foo\00\003\000\001\000\006\00256\000\003", !1, !5, !6, null, i64 (i32, i32, i64)* @_Z3fooiil, null, null, !2} ; [ DW_TAG_subprogram ] [line 3] [def] [foo]
206 !5 = !{!"0x29", !1} ; [ DW_TAG_file_type ] [propagate.cc]
207 !6 = !{!"0x15\00\000\000\000\000\000\000", i32 0, null, null, !2, null, null, null} ; [ DW_TAG_subroutine_type ] [line 0, size 0, align 0, offset 0] [from ]
208 !7 = !{!"0x2e\00main\00main\00\0024\000\001\000\006\00256\000\0024", !1, !5, !6, null, i32 ()* @main, null, null, !2} ; [ DW_TAG_subprogram ] [line 24] [def] [main]
209 !8 = !{i32 2, !"Dwarf Version", i32 4}
210 !9 = !{i32 1, !"Debug Info Version", i32 2}
211 !10 = !{!"clang version 3.5 "}
212 !11 = !{i32 4, i32 0, !12, null}
213 !12 = !{!"0xb\004\000\000", !1, !4} ; [ DW_TAG_lexical_block ] [propagate.cc]
214 !13 = !{i32 5, i32 0, !14, null}
215 !14 = !{!"0xb\004\000\000", !1, !12} ; [ DW_TAG_lexical_block ] [propagate.cc]
216 !15 = !{i32 7, i32 0, !16, null}
217 !16 = !{!"0xb\007\000\000", !1, !17} ; [ DW_TAG_lexical_block ] [propagate.cc]
218 !17 = !{!"0xb\006\000\000", !1, !12} ; [ DW_TAG_lexical_block ] [propagate.cc]
219 !18 = !{i32 8, i32 0, !19, null}
220 !19 = !{!"0xb\008\000\000", !1, !20} ; [ DW_TAG_lexical_block ] [propagate.cc]
221 !20 = !{!"0xb\007\000\000", !1, !16} ; [ DW_TAG_lexical_block ] [propagate.cc]
222 !21 = !{i32 9, i32 0, !19, null}
223 !22 = !{i32 10, i32 0, !23, null}
224 !23 = !{!"0xb\0010\000\000", !1, !20} ; [ DW_TAG_lexical_block ] [propagate.cc]
225 !24 = !{i32 11, i32 0, !25, null}
226 !25 = !{!"0xb\0010\000\000", !1, !23} ; [ DW_TAG_lexical_block ] [propagate.cc]
227 !26 = !{i32 12, i32 0, !25, null}
228 !27 = !{i32 13, i32 0, !25, null}
229 !28 = !{i32 14, i32 0, !29, null}
230 !29 = !{!"0xb\0014\000\000", !1, !30} ; [ DW_TAG_lexical_block ] [propagate.cc]
231 !30 = !{!"0xb\0013\000\000", !1, !23} ; [ DW_TAG_lexical_block ] [propagate.cc]
232 !31 = !{i32 15, i32 0, !32, null}
233 !32 = !{!"0xb\0014\000\000", !1, !29} ; [ DW_TAG_lexical_block ] [propagate.cc]
234 !33 = !{i32 16, i32 0, !32, null}
235 !34 = !{i32 17, i32 0, !32, null}
236 !35 = !{i32 19, i32 0, !20, null}
237 !36 = !{i32 21, i32 0, !4, null}
238 !37 = !{i32 22, i32 0, !4, null}
239 !38 = !{i32 25, i32 0, !7, null}
240 !39 = !{i32 26, i32 0, !7, null}
241 !40 = !{i32 27, i32 0, !7, null}
242 !41 = !{i32 28, i32 0, !7, null}
243 !42 = !{i32 29, i32 0, !7, null}