llvm/test/Transforms/SampleProfile/propagate.ll

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