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 = 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}