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: (78 + %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: (40 + %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: (38 + %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: (78 + %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: (40 + %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: (38 + %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: (9998 + (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: (9998 + %a)) 254 ; CHECK-NEXT: Member: {%a,+,2}<%for.body> 255 ; CHECK-NEXT: Group {{.*}}[[TWO]]: 256 ; CHECK-NEXT: (Low: (20000 + %a) High: (29998 + %a)) 257 ; CHECK-NEXT: Member: {(20000 + %a),+,2}<%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 } 289
