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 4target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128" 5target 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 20define void @testf(i16* %a, 21 i16* %b, 22 i16* %c, 23 i16* %d, 24 i16* %e, 25 i16* %f) { 26entry: 27 br label %for.body 28 29for.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 58for.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 110define void @testg(i16* %a, 111 i16* %b, 112 i16* %c) { 113entry: 114 br label %for.body 115 116for.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 145for.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 182define void @testh(i16* %a, 183 i16* %b, 184 i16* %c) { 185entry: 186 br label %for.body 187 188for.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 217for.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 259define void @testi(i16* %a, 260 i64 %offset) { 261entry: 262 br label %for.body 263 264for.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 286for.end: ; preds = %for.body 287 ret void 288} 289