| 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' |
| 37 |
target datalayout = "e-m:e-i64:64-f80: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 !dbg !6 { |
| 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 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 |
|
| 62 |
if.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 |
|
| 70 |
if.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 |
|
| 75 |
for.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 |
|
| 81 |
for.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 |
|
| 90 |
if.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 |
|
| 96 |
if.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 |
|
| 105 |
if.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 |
|
| 114 |
if.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 |
|
| 119 |
for.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 |
for.body10: ; preds = %for.cond8 |
| 127 |
%14 = load i64, ptr %j, align 8, !dbg !69 |
| 128 |
%15 = load i32, ptr %x.addr, align 4, !dbg !71 |
| 129 |
%conv11 = sext i32 %15 to i64, !dbg !71 |
| 130 |
%add12 = add nsw i64 %conv11, %14, !dbg !71 |
| 131 |
%conv13 = trunc i64 %add12 to i32, !dbg !71 |
| 132 |
store i32 %conv13, ptr %x.addr, align 4, !dbg !71 |
| 133 |
%16 = load i32, ptr %y.addr, align 4, !dbg !72 |
| 134 |
%sub14 = sub nsw i32 %16, 3, !dbg !72 |
| 135 |
store i32 %sub14, ptr %y.addr, align 4, !dbg !72 |
| 136 |
br label %for.inc, !dbg !73 |
| 137 |
|
| 138 |
for.inc: ; preds = %for.body10 |
| 139 |
%17 = load i64, ptr %j, align 8, !dbg !74 |
| 140 |
%inc15 = add nsw i64 %17, 1, !dbg !74 |
| 141 |
store i64 %inc15, ptr %j, align 8, !dbg !74 |
| 142 |
br label %for.cond8, !dbg !76 |
| 143 |
|
| 144 |
for.end: ; preds = %for.cond8 |
| 145 |
br label %if.end16 |
| 146 |
|
| 147 |
if.end16: ; preds = %for.end, %if.then6 |
| 148 |
br label %for.inc17, !dbg !77 |
| 149 |
|
| 150 |
for.inc17: ; preds = %if.end16 |
| 151 |
%18 = load i64, ptr %i, align 8, !dbg !78 |
| 152 |
%inc18 = add nsw i64 %18, 1, !dbg !78 |
| 153 |
store i64 %inc18, ptr %i, align 8, !dbg !78 |
| 154 |
br label %for.cond, !dbg !80 |
| 155 |
|
| 156 |
for.end19: ; preds = %for.cond |
| 157 |
br label %if.end20 |
| 158 |
|
| 159 |
if.end20: ; preds = %for.end19 |
| 160 |
%19 = load i32, ptr %y.addr, align 4, !dbg !81 |
| 161 |
%20 = load i32, ptr %x.addr, align 4, !dbg !82 |
| 162 |
%mul = mul nsw i32 %19, %20, !dbg !83 |
| 163 |
%conv21 = sext i32 %mul to i64, !dbg !81 |
| 164 |
store i64 %conv21, ptr %retval, align 8, !dbg !84 |
| 165 |
br label %return, !dbg !84 |
| 166 |
|
| 167 |
return: ; preds = %if.end20, %if.then |
| 168 |
%21 = load i64, ptr %retval, align 8, !dbg !85 |
| 169 |
ret i64 %21, !dbg !85 |
| 170 |
} |
| 171 |
|
| 172 |
; Function Attrs: nounwind readnone |
| 173 |
declare void @llvm.dbg.declare(metadata, metadata, metadata) |
| 174 |
|
| 175 |
; Function Attrs: norecurse uwtable |
| 176 |
define i32 @main() #2 !dbg !86 { |
| 177 |
entry: |
| 178 |
%retval = alloca i32, align 4 |
| 179 |
%x = alloca i32, align 4 |
| 180 |
%y = alloca i32, align 4 |
| 181 |
%N = alloca i64, align 8 |
| 182 |
store i32 0, ptr %retval, align 4 |
| 183 |
call void @llvm.dbg.declare(metadata ptr %x, metadata !89, metadata !12), !dbg !90 |
| 184 |
store i32 5678, ptr %x, align 4, !dbg !90 |
| 185 |
call void @llvm.dbg.declare(metadata ptr %y, metadata !91, metadata !12), !dbg !92 |
| 186 |
store i32 1234, ptr %y, align 4, !dbg !92 |
| 187 |
call void @llvm.dbg.declare(metadata ptr %N, metadata !93, metadata !12), !dbg !94 |
| 188 |
store i64 9999999, ptr %N, align 8, !dbg !94 |
| 189 |
%0 = load i32, ptr %x, align 4, !dbg !95 |
| 190 |
%1 = load i32, ptr %y, align 4, !dbg !96 |
| 191 |
%2 = load i64, ptr %N, align 8, !dbg !97 |
| 192 |
%3 = load i32, ptr %x, align 4, !dbg !98 |
| 193 |
%4 = load i32, ptr %y, align 4, !dbg !99 |
| 194 |
%5 = load i64, ptr %N, align 8, !dbg !100 |
| 195 |
%call = call i64 @_Z3fooiil(i32 %3, i32 %4, i64 %5), !dbg !101 |
| 196 |
%call1 = call i32 (ptr, ...) @printf(ptr @.str, i32 %0, i32 %1, i64 %2, i64 %call), !dbg !102 |
| 197 |
ret i32 0, !dbg !104 |
| 198 |
} |
| 199 |
|
| 200 |
declare i32 @printf(ptr, ...) |
| 201 |
|
| 202 |
attributes #0 = { nounwind uwtable "use-sample-profile" } |
| 203 |
attributes #2 = { norecurse uwtable "use-sample-profile" } |
| 204 |
|
| 205 |
!llvm.dbg.cu = !{!0} |
| 206 |
!llvm.module.flags = !{!3, !4} |
| 207 |
!llvm.ident = !{!5} |
| 208 |
|
| 209 |
!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) |
| 210 |
!1 = !DIFile(filename: "propagate.cc", directory: ".") |
| 211 |
!2 = !{} |
| 212 |
!3 = !{i32 2, !"Dwarf Version", i32 4} |
| 213 |
!4 = !{i32 2, !"Debug Info Version", i32 3} |
| 214 |
!5 = !{!"clang version 3.9.0 (trunk 266819)"} |
| 215 |
!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) |
| 216 |
!7 = !DISubroutineType(types: !8) |
| 217 |
!8 = !{!9, !10, !10, !9} |
| 218 |
!9 = !DIBasicType(name: "long int", size: 64, align: 64, encoding: DW_ATE_signed) |
| 219 |
!10 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed) |
| 220 |
!11 = !DILocalVariable(name: "x", arg: 1, scope: !6, file: !1, line: 3, type: !10) |
| 221 |
!12 = !DIExpression() |
| 222 |
!13 = !DILocation(line: 3, column: 14, scope: !6) |
| 223 |
!14 = !DILocalVariable(name: "y", arg: 2, scope: !6, file: !1, line: 3, type: !10) |
| 224 |
!15 = !DILocation(line: 3, column: 21, scope: !6) |
| 225 |
!16 = !DILocalVariable(name: "N", arg: 3, scope: !6, file: !1, line: 3, type: !9) |
| 226 |
!17 = !DILocation(line: 3, column: 29, scope: !6) |
| 227 |
!18 = !DILocation(line: 4, column: 7, scope: !19) |
| 228 |
!19 = distinct !DILexicalBlock(scope: !6, file: !1, line: 4, column: 7) |
| 229 |
!20 = !DILocation(line: 4, column: 11, scope: !19) |
| 230 |
!21 = !DILocation(line: 4, column: 9, scope: !19) |
| 231 |
!22 = !DILocation(line: 4, column: 7, scope: !6) |
| 232 |
!23 = !DILocation(line: 5, column: 12, scope: !24) |
| 233 |
!24 = distinct !DILexicalBlock(scope: !19, file: !1, line: 4, column: 14) |
| 234 |
!25 = !DILocation(line: 5, column: 16, scope: !24) |
| 235 |
!26 = !DILocation(line: 5, column: 14, scope: !24) |
| 236 |
!27 = !DILocation(line: 5, column: 5, scope: !24) |
| 237 |
!28 = !DILocalVariable(name: "i", scope: !29, file: !1, line: 7, type: !9) |
| 238 |
!29 = distinct !DILexicalBlock(scope: !30, file: !1, line: 7, column: 5) |
| 239 |
!30 = distinct !DILexicalBlock(scope: !19, file: !1, line: 6, column: 10) |
| 240 |
!31 = !DILocation(line: 7, column: 15, scope: !29) |
| 241 |
!32 = !DILocation(line: 7, column: 10, scope: !29) |
| 242 |
!33 = !DILocation(line: 7, column: 22, scope: !34) |
| 243 |
!34 = !DILexicalBlockFile(scope: !35, file: !1, discriminator: 2) |
| 244 |
!35 = distinct !DILexicalBlock(scope: !29, file: !1, line: 7, column: 5) |
| 245 |
!36 = !DILocation(line: 7, column: 26, scope: !34) |
| 246 |
!37 = !DILocation(line: 7, column: 24, scope: !34) |
| 247 |
!38 = !DILocation(line: 7, column: 5, scope: !34) |
| 248 |
!39 = !DILocation(line: 8, column: 11, scope: !40) |
| 249 |
!40 = distinct !DILexicalBlock(scope: !41, file: !1, line: 8, column: 11) |
| 250 |
!41 = distinct !DILexicalBlock(scope: !35, file: !1, line: 7, column: 34) |
| 251 |
!42 = !DILocation(line: 8, column: 15, scope: !40) |
| 252 |
!43 = !DILocation(line: 8, column: 17, scope: !40) |
| 253 |
!44 = !DILocation(line: 8, column: 13, scope: !40) |
| 254 |
!45 = !DILocation(line: 8, column: 11, scope: !41) |
| 255 |
!46 = !DILocation(line: 9, column: 10, scope: !40) |
| 256 |
!47 = !DILocation(line: 9, column: 9, scope: !40) |
| 257 |
!48 = !DILocation(line: 10, column: 11, scope: !49) |
| 258 |
!49 = distinct !DILexicalBlock(scope: !41, file: !1, line: 10, column: 11) |
| 259 |
!50 = !DILocation(line: 10, column: 15, scope: !49) |
| 260 |
!51 = !DILocation(line: 10, column: 17, scope: !49) |
| 261 |
!52 = !DILocation(line: 10, column: 13, scope: !49) |
| 262 |
!53 = !DILocation(line: 10, column: 11, scope: !41) |
| 263 |
!54 = !DILocation(line: 11, column: 10, scope: !55) |
| 264 |
!55 = distinct !DILexicalBlock(scope: !49, file: !1, line: 10, column: 22) |
| 265 |
!56 = !DILocation(line: 12, column: 11, scope: !55) |
| 266 |
!57 = !DILocation(line: 13, column: 7, scope: !55) |
| 267 |
!58 = !DILocalVariable(name: "j", scope: !59, file: !1, line: 14, type: !61) |
| 268 |
!59 = distinct !DILexicalBlock(scope: !60, file: !1, line: 14, column: 9) |
| 269 |
!60 = distinct !DILexicalBlock(scope: !49, file: !1, line: 13, column: 14) |
| 270 |
!61 = !DIBasicType(name: "long long int", size: 64, align: 64, encoding: DW_ATE_signed) |
| 271 |
!62 = !DILocation(line: 14, column: 24, scope: !59) |
| 272 |
!63 = !DILocation(line: 14, column: 14, scope: !59) |
| 273 |
!64 = !DILocation(line: 14, column: 31, scope: !65) |
| 274 |
!65 = !DILexicalBlockFile(scope: !66, file: !1, discriminator: 2) |
| 275 |
!66 = distinct !DILexicalBlock(scope: !59, file: !1, line: 14, column: 9) |
| 276 |
!67 = !DILocation(line: 14, column: 33, scope: !65) |
| 277 |
!68 = !DILocation(line: 14, column: 9, scope: !65) |
| 278 |
!69 = !DILocation(line: 15, column: 16, scope: !70) |
| 279 |
!70 = distinct !DILexicalBlock(scope: !66, file: !1, line: 14, column: 45) |
| 280 |
!71 = !DILocation(line: 15, column: 13, scope: !70) |
| 281 |
!72 = !DILocation(line: 16, column: 13, scope: !70) |
| 282 |
!73 = !DILocation(line: 17, column: 9, scope: !70) |
| 283 |
!74 = !DILocation(line: 14, column: 41, scope: !75) |
| 284 |
!75 = !DILexicalBlockFile(scope: !66, file: !1, discriminator: 4) |
| 285 |
!76 = !DILocation(line: 14, column: 9, scope: !75) |
| 286 |
!77 = !DILocation(line: 19, column: 5, scope: !41) |
| 287 |
!78 = !DILocation(line: 7, column: 30, scope: !79) |
| 288 |
!79 = !DILexicalBlockFile(scope: !35, file: !1, discriminator: 4) |
| 289 |
!80 = !DILocation(line: 7, column: 5, scope: !79) |
| 290 |
!81 = !DILocation(line: 21, column: 10, scope: !6) |
| 291 |
!82 = !DILocation(line: 21, column: 14, scope: !6) |
| 292 |
!83 = !DILocation(line: 21, column: 12, scope: !6) |
| 293 |
!84 = !DILocation(line: 21, column: 3, scope: !6) |
| 294 |
!85 = !DILocation(line: 22, column: 1, scope: !6) |
| 295 |
!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) |
| 296 |
!87 = !DISubroutineType(types: !88) |
| 297 |
!88 = !{!10} |
| 298 |
!89 = !DILocalVariable(name: "x", scope: !86, file: !1, line: 25, type: !10) |
| 299 |
!90 = !DILocation(line: 25, column: 7, scope: !86) |
| 300 |
!91 = !DILocalVariable(name: "y", scope: !86, file: !1, line: 26, type: !10) |
| 301 |
!92 = !DILocation(line: 26, column: 7, scope: !86) |
| 302 |
!93 = !DILocalVariable(name: "N", scope: !86, file: !1, line: 27, type: !9) |
| 303 |
!94 = !DILocation(line: 27, column: 8, scope: !86) |
| 304 |
!95 = !DILocation(line: 28, column: 38, scope: !86) |
| 305 |
!96 = !DILocation(line: 28, column: 41, scope: !86) |
| 306 |
!97 = !DILocation(line: 28, column: 44, scope: !86) |
| 307 |
!98 = !DILocation(line: 28, column: 51, scope: !86) |
| 308 |
!99 = !DILocation(line: 28, column: 54, scope: !86) |
| 309 |
!100 = !DILocation(line: 28, column: 57, scope: !86) |
| 310 |
!101 = !DILocation(line: 28, column: 47, scope: !86) |
| 311 |
!102 = !DILocation(line: 28, column: 3, scope: !103) |
| 312 |
!103 = !DILexicalBlockFile(scope: !86, file: !1, discriminator: 2) |
| 313 |
!104 = !DILocation(line: 29, column: 3, scope: !86) |