test/Transforms/SampleProfile/propagate.ll

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