test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll

   1 ; RUN: opt -loop-accesses -analyze < %s | FileCheck %s
   2 ; RUN: opt -passes='require<scalar-evolution>,require<aa>,loop(print-access-info)' -disable-output  < %s 2>&1 | FileCheck %s
   3
   4 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
   5 target triple = "aarch64--linux-gnueabi"
   6
   7 ; 3 reads and 3 writes should need 12 memchecks
   8 ; CHECK: function 'testf':
   9 ; CHECK: Memory dependences are safe with run-time checks
  10
  11 ; Memory dependencies have labels starting from 0, so in
  12 ; order to verify that we have n checks, we look for
  13 ; (n-1): and not n:.
  14
  15 ; CHECK: Run-time memory checks:
  16 ; CHECK-NEXT: Check 0:
  17 ; CHECK: Check 11:
  18 ; CHECK-NOT: Check 12:
  19
  20 define void @testf(i16* %a,
  21                i16* %b,
  22                i16* %c,
  23                i16* %d,
  24                i16* %e,
  25                i16* %f) {
  26 entry:
  27   br label %for.body
  28
  29 for.body:                                         ; preds = %for.body, %entry
  30   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
  31
  32   %add = add nuw nsw i64 %ind, 1
  33
  34   %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
  35   %loadA = load i16, i16* %arrayidxA, align 2
  36
  37   %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
  38   %loadB = load i16, i16* %arrayidxB, align 2
  39
  40   %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %ind
  41   %loadC = load i16, i16* %arrayidxC, align 2
  42
  43   %mul = mul i16 %loadB, %loadA
  44   %mul1 = mul i16 %mul, %loadC
  45
  46   %arrayidxD = getelementptr inbounds i16, i16* %d, i64 %ind
  47   store i16 %mul1, i16* %arrayidxD, align 2
  48
  49   %arrayidxE = getelementptr inbounds i16, i16* %e, i64 %ind
  50   store i16 %mul, i16* %arrayidxE, align 2
  51
  52   %arrayidxF = getelementptr inbounds i16, i16* %f, i64 %ind
  53   store i16 %mul1, i16* %arrayidxF, align 2
  54
  55   %exitcond = icmp eq i64 %add, 20
  56   br i1 %exitcond, label %for.end, label %for.body
  57
  58 for.end:                                          ; preds = %for.body
  59   ret void
  60 }
  61
  62 ; The following (testg and testh) check that we can group
  63 ; memory checks of accesses which differ by a constant value.
  64 ; Both tests are based on the following C code:
  65 ;
  66 ; void testh(short *a, short *b, short *c) {
  67 ;   unsigned long ind = 0;
  68 ;   for (unsigned long ind = 0; ind < 20; ++ind) {
  69 ;     c[2 * ind] = a[ind] * a[ind + 1];
  70 ;     c[2 * ind + 1] = a[ind] * a[ind + 1] * b[ind];
  71 ;   }
  72 ; }
  73 ;
  74 ; It is sufficient to check the intervals
  75 ; [a, a + 21], [b, b + 20] against [c, c + 41].
  76
  77 ; 3 reads and 2 writes - two of the reads can be merged,
  78 ; and the writes can be merged as well. This gives us a
  79 ; total of 2 memory checks.
  80
  81 ; CHECK: function 'testg':
  82
  83 ; CHECK: Run-time memory checks:
  84 ; CHECK-NEXT:   Check 0:
  85 ; CHECK-NEXT:     Comparing group ([[ZERO:.+]]):
  86 ; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
  87 ; CHECK-NEXT:       %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
  88 ; CHECK-NEXT:     Against group ([[ONE:.+]]):
  89 ; CHECK-NEXT:       %arrayidxA1 = getelementptr inbounds i16, i16* %a, i64 %add
  90 ; CHECK-NEXT:       %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
  91 ; CHECK-NEXT:   Check 1:
  92 ; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
  93 ; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
  94 ; CHECK-NEXT:       %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
  95 ; CHECK-NEXT:     Against group ([[TWO:.+]]):
  96 ; CHECK-NEXT:       %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
  97 ; CHECK-NEXT:   Grouped accesses:
  98 ; CHECK-NEXT:    Group {{.*}}[[ZERO]]:
  99 ; CHECK-NEXT:       (Low: %c High: (80 + %c))
 100 ; CHECK-NEXT:         Member: {(2 + %c)<nsw>,+,4}
 101 ; CHECK-NEXT:         Member: {%c,+,4}
 102 ; CHECK-NEXT:     Group {{.*}}[[ONE]]:
 103 ; CHECK-NEXT:       (Low: %a High: (42 + %a))
 104 ; CHECK-NEXT:         Member: {(2 + %a)<nsw>,+,2}
 105 ; CHECK-NEXT:         Member: {%a,+,2}
 106 ; CHECK-NEXT:     Group {{.*}}[[TWO]]:
 107 ; CHECK-NEXT:       (Low: %b High: (40 + %b))
 108 ; CHECK-NEXT:         Member: {%b,+,2}
 109
 110 define void @testg(i16* %a,
 111                i16* %b,
 112                i16* %c) {
 113 entry:
 114   br label %for.body
 115
 116 for.body:                                         ; preds = %for.body, %entry
 117   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
 118   %store_ind = phi i64 [ 0, %entry ], [ %store_ind_next, %for.body ]
 119
 120   %add = add nuw nsw i64 %ind, 1
 121   %store_ind_inc = add nuw nsw i64 %store_ind, 1
 122   %store_ind_next = add nuw nsw i64 %store_ind_inc, 1
 123
 124   %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
 125   %loadA = load i16, i16* %arrayidxA, align 2
 126
 127   %arrayidxA1 = getelementptr inbounds i16, i16* %a, i64 %add
 128   %loadA1 = load i16, i16* %arrayidxA1, align 2
 129
 130   %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
 131   %loadB = load i16, i16* %arrayidxB, align 2
 132
 133   %mul = mul i16 %loadA, %loadA1
 134   %mul1 = mul i16 %mul, %loadB
 135
 136   %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
 137   store i16 %mul1, i16* %arrayidxC, align 2
 138
 139   %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 140   store i16 %mul, i16* %arrayidxC1, align 2
 141
 142   %exitcond = icmp eq i64 %add, 20
 143   br i1 %exitcond, label %for.end, label %for.body
 144
 145 for.end:                                          ; preds = %for.body
 146   ret void
 147 }
 148
 149 ; 3 reads and 2 writes - the writes can be merged into a single
 150 ; group, but the GEPs used for the reads are not marked as inbounds.
 151 ; We can still merge them because we are using a unit stride for
 152 ; accesses, so we cannot overflow the GEPs.
 153
 154 ; CHECK: function 'testh':
 155 ; CHECK: Run-time memory checks:
 156 ; CHECK-NEXT:   Check 0:
 157 ; CHECK-NEXT:     Comparing group ([[ZERO:.+]]):
 158 ; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 159 ; CHECK-NEXT:         %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
 160 ; CHECK-NEXT:     Against group ([[ONE:.+]]):
 161 ; CHECK-NEXT:         %arrayidxA1 = getelementptr i16, i16* %a, i64 %add
 162 ; CHECK-NEXT:         %arrayidxA = getelementptr i16, i16* %a, i64 %ind
 163 ; CHECK-NEXT:   Check 1:
 164 ; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
 165 ; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 166 ; CHECK-NEXT:         %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
 167 ; CHECK-NEXT:     Against group ([[TWO:.+]]):
 168 ; CHECK-NEXT:         %arrayidxB = getelementptr i16, i16* %b, i64 %ind
 169 ; CHECK-NEXT:   Grouped accesses:
 170 ; CHECK-NEXT:     Group {{.*}}[[ZERO]]:
 171 ; CHECK-NEXT:       (Low: %c High: (80 + %c))
 172 ; CHECK-NEXT:         Member: {(2 + %c)<nsw>,+,4}
 173 ; CHECK-NEXT:         Member: {%c,+,4}
 174 ; CHECK-NEXT:     Group {{.*}}[[ONE]]:
 175 ; CHECK-NEXT:       (Low: %a High: (42 + %a))
 176 ; CHECK-NEXT:         Member: {(2 + %a),+,2}
 177 ; CHECK-NEXT:         Member: {%a,+,2}
 178 ; CHECK-NEXT:     Group {{.*}}[[TWO]]:
 179 ; CHECK-NEXT:       (Low: %b High: (40 + %b))
 180 ; CHECK-NEXT:         Member: {%b,+,2}
 181
 182 define void @testh(i16* %a,
 183                i16* %b,
 184                i16* %c) {
 185 entry:
 186   br label %for.body
 187
 188 for.body:                                         ; preds = %for.body, %entry
 189   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
 190   %store_ind = phi i64 [ 0, %entry ], [ %store_ind_next, %for.body ]
 191
 192   %add = add nuw nsw i64 %ind, 1
 193   %store_ind_inc = add nuw nsw i64 %store_ind, 1
 194   %store_ind_next = add nuw nsw i64 %store_ind_inc, 1
 195
 196   %arrayidxA = getelementptr i16, i16* %a, i64 %ind
 197   %loadA = load i16, i16* %arrayidxA, align 2
 198
 199   %arrayidxA1 = getelementptr i16, i16* %a, i64 %add
 200   %loadA1 = load i16, i16* %arrayidxA1, align 2
 201
 202   %arrayidxB = getelementptr i16, i16* %b, i64 %ind
 203   %loadB = load i16, i16* %arrayidxB, align 2
 204
 205   %mul = mul i16 %loadA, %loadA1
 206   %mul1 = mul i16 %mul, %loadB
 207
 208   %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
 209   store i16 %mul1, i16* %arrayidxC, align 2
 210
 211   %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 212   store i16 %mul, i16* %arrayidxC1, align 2
 213
 214   %exitcond = icmp eq i64 %add, 20
 215   br i1 %exitcond, label %for.end, label %for.body
 216
 217 for.end:                                          ; preds = %for.body
 218   ret void
 219 }
 220
 221 ; Don't merge pointers if we need to perform a check against a pointer
 222 ; to the same underlying object (doing so would emit a check that could be
 223 ; falsely invalidated) For example, in the following loop:
 224 ;
 225 ; for (i = 0; i < 5000; ++i)
 226 ;   a[i + offset] = a[i] + a[i + 10000]
 227 ;
 228 ; we should not merge the intervals associated with the reads (0,5000) and
 229 ; (10000, 15000) into (0, 15000) as this will pottentially fail the check
 230 ; against the interval associated with the write.
 231 ;
 232 ; We cannot have this check unless ShouldRetryWithRuntimeCheck is set,
 233 ; and therefore the grouping algorithm would create a separate group for
 234 ; each pointer.
 235
 236 ; CHECK: function 'testi':
 237 ; CHECK: Run-time memory checks:
 238 ; CHECK-NEXT:   Check 0:
 239 ; CHECK-NEXT:     Comparing group ([[ZERO:.+]]):
 240 ; CHECK-NEXT:       %storeidx = getelementptr inbounds i16, i16* %a, i64 %store_ind
 241 ; CHECK-NEXT:     Against group ([[ONE:.+]]):
 242 ; CHECK-NEXT:       %arrayidxA1 = getelementptr i16, i16* %a, i64 %ind
 243 ; CHECK-NEXT:   Check 1:
 244 ; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
 245 ; CHECK-NEXT:       %storeidx = getelementptr inbounds i16, i16* %a, i64 %store_ind
 246 ; CHECK-NEXT:     Against group ([[TWO:.+]]):
 247 ; CHECK-NEXT:       %arrayidxA2 = getelementptr i16, i16* %a, i64 %ind2
 248 ; CHECK-NEXT:   Grouped accesses:
 249 ; CHECK-NEXT:     Group {{.*}}[[ZERO]]:
 250 ; CHECK-NEXT:       (Low: ((2 * %offset) + %a)<nsw> High: (10000 + (2 * %offset) + %a))
 251 ; CHECK-NEXT:         Member: {((2 * %offset) + %a)<nsw>,+,2}<nsw><%for.body>
 252 ; CHECK-NEXT:     Group {{.*}}[[ONE]]:
 253 ; CHECK-NEXT:       (Low: %a High: (10000 + %a))
 254 ; CHECK-NEXT:         Member: {%a,+,2}<nw><%for.body>
 255 ; CHECK-NEXT:     Group {{.*}}[[TWO]]:
 256 ; CHECK-NEXT:       (Low: (20000 + %a) High: (30000 + %a))
 257 ; CHECK-NEXT:         Member: {(20000 + %a),+,2}<nw><%for.body>
 258
 259 define void @testi(i16* %a,
 260                    i64 %offset) {
 261 entry:
 262   br label %for.body
 263
 264 for.body:                                         ; preds = %for.body, %entry
 265   %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
 266   %store_ind = phi i64 [ %offset, %entry ], [ %store_ind_inc, %for.body ]
 267
 268   %add = add nuw nsw i64 %ind, 1
 269   %store_ind_inc = add nuw nsw i64 %store_ind, 1
 270
 271   %arrayidxA1 = getelementptr i16, i16* %a, i64 %ind
 272   %ind2 = add nuw nsw i64 %ind, 10000
 273   %arrayidxA2 = getelementptr i16, i16* %a, i64 %ind2
 274
 275   %loadA1 = load i16, i16* %arrayidxA1, align 2
 276   %loadA2 = load i16, i16* %arrayidxA2, align 2
 277
 278   %addres = add i16 %loadA1, %loadA2
 279
 280   %storeidx = getelementptr inbounds i16, i16* %a, i64 %store_ind
 281   store i16 %addres, i16* %storeidx, align 2
 282
 283   %exitcond = icmp eq i64 %add, 5000
 284   br i1 %exitcond, label %for.end, label %for.body
 285
 286 for.end:                                          ; preds = %for.body
 287   ret void
 288 }