331 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 52; RUN: opt -passes='print<access-info>' -aa-pipeline='basic-aa' \3; RUN: -disable-output %s 2>&1 | FileCheck %s4 5; For this loop:6; unsigned index = 0;7; for (int i = 0; i < n; i++) {8; A[2 * index] = A[2 * index] + B[i];9; index++;10; }11;12; SCEV is unable to prove that A[2 * i] does not overflow.13;14; Analyzing the IR does not help us because the GEPs are not15; affine AddRecExprs. However, we can turn them into AddRecExprs16; using SCEV Predicates.17;18; Once we have an affine expression we need to add an additional NUSW19; to check that the pointers don't wrap since the GEPs are not20; inbound.21 22; The expression for %mul_ext as analyzed by SCEV is23; (zext i32 {0,+,2}<%for.body> to i64)24; We have added the nusw flag to turn this expression into the SCEV expression:25; i64 {0,+,2}<%for.body>26 27define void @f1(ptr noalias %a, ptr noalias %b, i64 %N) {28; CHECK-LABEL: 'f1'29; CHECK-NEXT: for.body:30; CHECK-NEXT: Memory dependences are safe31; CHECK-NEXT: Dependences:32; CHECK-NEXT: Forward:33; CHECK-NEXT: %loadA = load i16, ptr %arrayidxA, align 2 ->34; CHECK-NEXT: store i16 %add, ptr %arrayidxA, align 235; CHECK-EMPTY:36; CHECK-NEXT: Run-time memory checks:37; CHECK-NEXT: Grouped accesses:38; CHECK-EMPTY:39; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop.40; CHECK-NEXT: SCEV assumptions:41; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nusw>42; CHECK-NEXT: {%a,+,4}<%for.body> Added Flags: <nusw>43; CHECK-EMPTY:44; CHECK-NEXT: Expressions re-written:45; CHECK-NEXT: [PSE] %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext:46; CHECK-NEXT: ((2 * (zext i32 {0,+,2}<%for.body> to i64))<nuw><nsw> + %a)47; CHECK-NEXT: --> {%a,+,4}<%for.body>48;49entry:50 br label %for.body51 52for.body: ; preds = %for.body, %entry53 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]54 %ind1 = phi i32 [ 0, %entry ], [ %inc1, %for.body ]55 56 %mul = mul i32 %ind1, 257 %mul_ext = zext i32 %mul to i6458 59 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext60 %loadA = load i16, ptr %arrayidxA, align 261 62 %arrayidxB = getelementptr i16, ptr %b, i64 %ind63 %loadB = load i16, ptr %arrayidxB, align 264 65 %add = mul i16 %loadA, %loadB66 67 store i16 %add, ptr %arrayidxA, align 268 69 %inc = add nuw nsw i64 %ind, 170 %inc1 = add i32 %ind1, 171 72 %exitcond = icmp eq i64 %inc, %N73 br i1 %exitcond, label %for.end, label %for.body74 75for.end: ; preds = %for.body76 ret void77}78 79; For this loop:80; unsigned index = n;81; for (int i = 0; i < n; i++) {82; A[2 * index] = A[2 * index] + B[i];83; index--;84; }85;86; the SCEV expression for 2 * index is not an AddRecExpr87; (and implictly not affine). However, we are able to make assumptions88; that will turn the expression into an affine one and continue the89; analysis.90;91; Once we have an affine expression we need to add an additional NUSW92; to check that the pointers don't wrap since the GEPs are not93; inbounds.94;95; This loop has a negative stride for A, and the nusw flag is required in96; order to properly extend the increment from i32 -4 to i64 -4.97 98; The expression for %mul_ext as analyzed by SCEV is99; (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)100; We have added the nusw flag to turn this expression into the following SCEV:101; i64 {zext i32 (2 * (trunc i64 %N to i32)) to i64,+,-2}<%for.body>102 103define void @f2(ptr noalias %a, ptr noalias %b, i64 %N) {104; CHECK-LABEL: 'f2'105; CHECK-NEXT: for.body:106; CHECK-NEXT: Memory dependences are safe107; CHECK-NEXT: Dependences:108; CHECK-NEXT: Forward:109; CHECK-NEXT: %loadA = load i16, ptr %arrayidxA, align 2 ->110; CHECK-NEXT: store i16 %add, ptr %arrayidxA, align 2111; CHECK-EMPTY:112; CHECK-NEXT: Run-time memory checks:113; CHECK-NEXT: Grouped accesses:114; CHECK-EMPTY:115; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop.116; CHECK-NEXT: SCEV assumptions:117; CHECK-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nusw>118; CHECK-NEXT: {((4 * (zext i31 (trunc i64 %N to i31) to i64))<nuw><nsw> + %a),+,-4}<%for.body> Added Flags: <nusw>119; CHECK-EMPTY:120; CHECK-NEXT: Expressions re-written:121; CHECK-NEXT: [PSE] %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext:122; CHECK-NEXT: ((2 * (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64))<nuw><nsw> + %a)123; CHECK-NEXT: --> {((4 * (zext i31 (trunc i64 %N to i31) to i64))<nuw><nsw> + %a),+,-4}<%for.body>124;125entry:126 %TruncN = trunc i64 %N to i32127 br label %for.body128 129for.body: ; preds = %for.body, %entry130 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]131 %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]132 133 %mul = mul i32 %ind1, 2134 %mul_ext = zext i32 %mul to i64135 136 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext137 %loadA = load i16, ptr %arrayidxA, align 2138 139 %arrayidxB = getelementptr i16, ptr %b, i64 %ind140 %loadB = load i16, ptr %arrayidxB, align 2141 142 %add = mul i16 %loadA, %loadB143 144 store i16 %add, ptr %arrayidxA, align 2145 146 %inc = add nuw nsw i64 %ind, 1147 %dec = sub i32 %ind1, 1148 149 %exitcond = icmp eq i64 %inc, %N150 br i1 %exitcond, label %for.end, label %for.body151 152for.end: ; preds = %for.body153 ret void154}155 156; We replicate the tests above, but this time sign extend 2 * index instead157; of zero extending it.158 159; The expression for %mul_ext as analyzed by SCEV is160; i64 (sext i32 {0,+,2}<%for.body> to i64)161; We have added the nssw flag to turn this expression into the following SCEV:162; i64 {0,+,2}<%for.body>163 164define void @f3(ptr noalias %a, ptr noalias %b, i64 %N) {165; CHECK-LABEL: 'f3'166; CHECK-NEXT: for.body:167; CHECK-NEXT: Memory dependences are safe168; CHECK-NEXT: Dependences:169; CHECK-NEXT: Forward:170; CHECK-NEXT: %loadA = load i16, ptr %arrayidxA, align 2 ->171; CHECK-NEXT: store i16 %add, ptr %arrayidxA, align 2172; CHECK-EMPTY:173; CHECK-NEXT: Run-time memory checks:174; CHECK-NEXT: Grouped accesses:175; CHECK-EMPTY:176; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop.177; CHECK-NEXT: SCEV assumptions:178; CHECK-NEXT: {0,+,2}<%for.body> Added Flags: <nssw>179; CHECK-NEXT: {%a,+,4}<%for.body> Added Flags: <nusw>180; CHECK-EMPTY:181; CHECK-NEXT: Expressions re-written:182; CHECK-NEXT: [PSE] %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext:183; CHECK-NEXT: ((2 * (sext i32 {0,+,2}<%for.body> to i64))<nsw> + %a)184; CHECK-NEXT: --> {%a,+,4}<%for.body>185;186entry:187 br label %for.body188 189for.body: ; preds = %for.body, %entry190 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]191 %ind1 = phi i32 [ 0, %entry ], [ %inc1, %for.body ]192 193 %mul = mul i32 %ind1, 2194 %mul_ext = sext i32 %mul to i64195 196 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext197 %loadA = load i16, ptr %arrayidxA, align 2198 199 %arrayidxB = getelementptr i16, ptr %b, i64 %ind200 %loadB = load i16, ptr %arrayidxB, align 2201 202 %add = mul i16 %loadA, %loadB203 204 store i16 %add, ptr %arrayidxA, align 2205 206 %inc = add nuw nsw i64 %ind, 1207 %inc1 = add i32 %ind1, 1208 209 %exitcond = icmp eq i64 %inc, %N210 br i1 %exitcond, label %for.end, label %for.body211 212for.end: ; preds = %for.body213 ret void214}215 216; The expression for %mul_ext as analyzed by SCEV is217; i64 (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)218; We have added the nssw flag to turn this expression into the following SCEV:219; i64 {sext i32 (2 * (trunc i64 %N to i32)) to i64,+,-2}<%for.body>220 221define void @f4(ptr noalias %a, ptr noalias %b, i64 %N) {222; CHECK-LABEL: 'f4'223; CHECK-NEXT: for.body:224; CHECK-NEXT: Memory dependences are safe225; CHECK-NEXT: Dependences:226; CHECK-NEXT: Forward:227; CHECK-NEXT: %loadA = load i16, ptr %arrayidxA, align 2 ->228; CHECK-NEXT: store i16 %add, ptr %arrayidxA, align 2229; CHECK-EMPTY:230; CHECK-NEXT: Run-time memory checks:231; CHECK-NEXT: Grouped accesses:232; CHECK-EMPTY:233; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop.234; CHECK-NEXT: SCEV assumptions:235; CHECK-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nssw>236; CHECK-NEXT: {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64))<nsw> + %a),+,-4}<%for.body> Added Flags: <nusw>237; CHECK-EMPTY:238; CHECK-NEXT: Expressions re-written:239; CHECK-NEXT: [PSE] %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext:240; CHECK-NEXT: ((2 * (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64))<nsw> + %a)241; CHECK-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64))<nsw> + %a),+,-4}<%for.body>242;243entry:244 %TruncN = trunc i64 %N to i32245 br label %for.body246 247for.body: ; preds = %for.body, %entry248 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]249 %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]250 251 %mul = mul i32 %ind1, 2252 %mul_ext = sext i32 %mul to i64253 254 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext255 %loadA = load i16, ptr %arrayidxA, align 2256 257 %arrayidxB = getelementptr i16, ptr %b, i64 %ind258 %loadB = load i16, ptr %arrayidxB, align 2259 260 %add = mul i16 %loadA, %loadB261 262 store i16 %add, ptr %arrayidxA, align 2263 264 %inc = add nuw nsw i64 %ind, 1265 %dec = sub i32 %ind1, 1266 267 %exitcond = icmp eq i64 %inc, %N268 br i1 %exitcond, label %for.end, label %for.body269 270for.end: ; preds = %for.body271 ret void272}273 274; The following function is similar to the one above, but has the GEP275; to pointer %A inbounds. The index %mul doesn't have the nsw flag.276; This means that the SCEV expression for %mul can wrap and we need277; a SCEV predicate to continue analysis.278;279; We can still analyze this by adding the required no wrap SCEV predicates.280 281define void @f5(ptr noalias %a, ptr noalias %b, i64 %N) {282; CHECK-LABEL: 'f5'283; CHECK-NEXT: for.body:284; CHECK-NEXT: Memory dependences are safe285; CHECK-NEXT: Dependences:286; CHECK-NEXT: Forward:287; CHECK-NEXT: %loadA = load i16, ptr %arrayidxA, align 2 ->288; CHECK-NEXT: store i16 %add, ptr %arrayidxA, align 2289; CHECK-EMPTY:290; CHECK-NEXT: Run-time memory checks:291; CHECK-NEXT: Grouped accesses:292; CHECK-EMPTY:293; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop.294; CHECK-NEXT: SCEV assumptions:295; CHECK-NEXT: {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> Added Flags: <nssw>296; CHECK-EMPTY:297; CHECK-NEXT: Expressions re-written:298; CHECK-NEXT: [PSE] %arrayidxA = getelementptr inbounds i16, ptr %a, i32 %mul:299; CHECK-NEXT: ((2 * (sext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64))<nsw> + %a)300; CHECK-NEXT: --> {((2 * (sext i32 (2 * (trunc i64 %N to i32)) to i64))<nsw> + %a),+,-4}<%for.body>301;302entry:303 %TruncN = trunc i64 %N to i32304 br label %for.body305 306for.body: ; preds = %for.body, %entry307 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]308 %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]309 310 %mul = mul i32 %ind1, 2311 312 %arrayidxA = getelementptr inbounds i16, ptr %a, i32 %mul313 %loadA = load i16, ptr %arrayidxA, align 2314 315 %arrayidxB = getelementptr inbounds i16, ptr %b, i64 %ind316 %loadB = load i16, ptr %arrayidxB, align 2317 318 %add = mul i16 %loadA, %loadB319 320 store i16 %add, ptr %arrayidxA, align 2321 322 %inc = add nuw nsw i64 %ind, 1323 %dec = sub i32 %ind1, 1324 325 %exitcond = icmp eq i64 %inc, %N326 br i1 %exitcond, label %for.end, label %for.body327 328for.end: ; preds = %for.body329 ret void330}331