1 ; RUN: opt -basicaa -loop-accesses -analyze < %s | FileCheck %s 2 3 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128" 4 5 ; i and i + 1 can overflow in the following kernel: 6 ; void test1(unsigned long long x, int *a, int *b) { 7 ; for (unsigned i = 0; i < x; ++i) 8 ; b[i] = a[i+1] + 1; 9 ; } 10 ; 11 ; If accesses to a and b can alias, we need to emit a run-time alias check 12 ; between accesses to a and b. However, when i and i + 1 can wrap, their 13 ; SCEV expression is not an AddRec. We need to create SCEV predicates and 14 ; coerce the expressions to AddRecs in order to be able to emit the run-time 15 ; alias check. 16 ; 17 ; The accesses at b[i] and a[i+1] correspond to the addresses %arrayidx and 18 ; %arrayidx4 in the test. The SCEV expressions for these are: 19 ; ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nsw> 20 ; ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)<nsw> 21 ; 22 ; The transformed expressions are: 23 ; i64 {(4 + %a),+,4}<%for.body> 24 ; i64 {(4 + %b),+,4}<%for.body> 25 26 ; CHECK-LABEL: test1 27 ; CHECK: Memory dependences are safe with run-time checks 28 ; CHECK-NEXT: Dependences: 29 ; CHECK-NEXT: Run-time memory checks: 30 ; CHECK-NEXT: Check 0: 31 ; CHECK-NEXT: Comparing group 32 ; CHECK-NEXT: %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom 33 ; CHECK-NEXT: Against group 34 ; CHECK-NEXT: %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11 35 ; CHECK-NEXT: Grouped accesses: 36 ; CHECK-NEXT: Group 37 ; CHECK-NEXT: (Low: (4 + %a) High: (4 + (4 * (1 umax %x)) + %a)) 38 ; CHECK-NEXT: Member: {(4 + %a),+,4}<%for.body> 39 ; CHECK-NEXT: Group 40 ; CHECK-NEXT: (Low: %b High: ((4 * (1 umax %x)) + %b)) 41 ; CHECK-NEXT: Member: {%b,+,4}<%for.body> 42 ; CHECK: Store to invariant address was not found in loop. 43 ; CHECK-NEXT: SCEV assumptions: 44 ; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw> 45 ; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw> 46 ; CHECK: Expressions re-written: 47 ; CHECK-NEXT: [PSE] %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom: 48 ; CHECK-NEXT: ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nsw> 49 ; CHECK-NEXT: --> {(4 + %a),+,4}<%for.body> 50 ; CHECK-NEXT: [PSE] %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11: 51 ; CHECK-NEXT: ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)<nsw> 52 ; CHECK-NEXT: --> {%b,+,4}<%for.body> 53 define void @test1(i64 %x, i32* %a, i32* %b) { 54 entry: 55 br label %for.body 56 57 for.body: ; preds = %for.body.preheader, %for.body 58 %conv11 = phi i64 [ %conv, %for.body ], [ 0, %entry ] 59 %i.010 = phi i32 [ %add, %for.body ], [ 0, %entry ] 60 %add = add i32 %i.010, 1 61 %idxprom = zext i32 %add to i64 62 %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom 63 %ld = load i32, i32* %arrayidx, align 4 64 %add2 = add nsw i32 %ld, 1 65 %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11 66 store i32 %add2, i32* %arrayidx4, align 4 67 %conv = zext i32 %add to i64 68 %cmp = icmp ult i64 %conv, %x 69 br i1 %cmp, label %for.body, label %exit 70 71 exit: 72 ret void 73 } 74 75 ; i can overflow in the following kernel: 76 ; void test2(unsigned long long x, int *a) { 77 ; for (unsigned i = 0; i < x; ++i) 78 ; a[i] = a[i] + 1; 79 ; } 80 ; 81 ; We need to check that i doesn't wrap, but we don't need a run-time alias 82 ; check. We also need an extra no-wrap check to get the backedge taken count. 83 84 ; CHECK-LABEL: test2 85 ; CHECK: Memory dependences are safe 86 ; CHECK: SCEV assumptions: 87 ; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw> 88 ; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw> 89 define void @test2(i64 %x, i32* %a) { 90 entry: 91 br label %for.body 92 93 for.body: 94 %conv11 = phi i64 [ %conv, %for.body ], [ 0, %entry ] 95 %i.010 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 96 %arrayidx = getelementptr inbounds i32, i32* %a, i64 %conv11 97 %ld = load i32, i32* %arrayidx, align 4 98 %add = add nsw i32 %ld, 1 99 store i32 %add, i32* %arrayidx, align 4 100 %inc = add i32 %i.010, 1 101 %conv = zext i32 %inc to i64 102 %cmp = icmp ult i64 %conv, %x 103 br i1 %cmp, label %for.body, label %exit 104 105 exit: 106 ret void 107 } 108
