1 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/propagate.prof | opt -analyze -branch-prob | 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 < i; 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 = 999999; 32 ; printf("foo(%d, %d, %ld) = %ld\n", x, y, N, foo(x, y, N)); 33 ; return 0; 34 ; } 35 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" 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 43 define i64 @_Z3fooiil(i32 %x, i32 %y, i64 %N) #0 { 44 entry: 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 58 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 66 67 if.else: ; preds = %entry 68 store i64 0, i64* %i, align 8, !dbg !15 69 br label %for.cond, !dbg !15 70 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% 78 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% 87 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 93 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] 102 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 111 112 if.else7: ; preds = %if.end 113 store i32 0, i32* %j, align 4, !dbg !28 114 br label %for.cond8, !dbg !28 115 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% 124 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 134 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 140 141 for.end: ; preds = %for.cond8 142 br label %if.end15 143 144 if.end15: ; preds = %for.end, %if.then6 145 br label %for.inc16, !dbg !35 146 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 152 153 for.end18: ; preds = %for.cond 154 br label %if.end19 155 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 163 164 return: ; preds = %if.end19, %if.then 165 %22 = load i64* %retval, !dbg !37 166 ret i64 %22, !dbg !37 167 } 168 169 ; Function Attrs: uwtable 170 define i32 @main() #1 { 171 entry: 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 188 ret i32 0, !dbg !42 189 } 190 191 declare i32 @printf(i8*, ...) #2 192 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" } 196 197 !llvm.dbg.cu = !{!0} 198 !llvm.module.flags = !{!8, !9} 199 !llvm.ident = !{!10} 200 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} 244