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
   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 = !{!"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", !"."}
 203 !2 = !{i32 0}
 204 !3 = !{!4, !7}
 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 = !MDLocation(line: 4, scope: !12)
 213 !12 = !{!"0xb\004\000\000", !1, !4} ; [ DW_TAG_lexical_block ] [propagate.cc]
 214 !13 = !MDLocation(line: 5, scope: !14)
 215 !14 = !{!"0xb\004\000\000", !1, !12} ; [ DW_TAG_lexical_block ] [propagate.cc]
 216 !15 = !MDLocation(line: 7, scope: !16)
 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 = !MDLocation(line: 8, scope: !19)
 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 = !MDLocation(line: 9, scope: !19)
 223 !22 = !MDLocation(line: 10, scope: !23)
 224 !23 = !{!"0xb\0010\000\000", !1, !20} ; [ DW_TAG_lexical_block ] [propagate.cc]
 225 !24 = !MDLocation(line: 11, scope: !25)
 226 !25 = !{!"0xb\0010\000\000", !1, !23} ; [ DW_TAG_lexical_block ] [propagate.cc]
 227 !26 = !MDLocation(line: 12, scope: !25)
 228 !27 = !MDLocation(line: 13, scope: !25)
 229 !28 = !MDLocation(line: 14, scope: !29)
 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 = !MDLocation(line: 15, scope: !32)
 233 !32 = !{!"0xb\0014\000\000", !1, !29} ; [ DW_TAG_lexical_block ] [propagate.cc]
 234 !33 = !MDLocation(line: 16, scope: !32)
 235 !34 = !MDLocation(line: 17, scope: !32)
 236 !35 = !MDLocation(line: 19, scope: !20)
 237 !36 = !MDLocation(line: 21, scope: !4)
 238 !37 = !MDLocation(line: 22, scope: !4)
 239 !38 = !MDLocation(line: 25, scope: !7)
 240 !39 = !MDLocation(line: 26, scope: !7)
 241 !40 = !MDLocation(line: 27, scope: !7)
 242 !41 = !MDLocation(line: 28, scope: !7)
 243 !42 = !MDLocation(line: 29, scope: !7)