1; RUN: opt -passes='print<access-info>' -disable-output < %s 2>&1 | FileCheck %s 2 3; This loop: 4; 5; int **A; 6; for (i) 7; for (j) { 8; A[i][j] = A[i-1][j] * B[j] 9; B[j+1] = 2 // backward dep between this and the previous 10; } 11; 12; is transformed by Load-PRE to stash away A[i] for the next iteration of the 13; outer loop: 14; 15; Curr = A[0]; // Prev_0 16; for (i: 1..N) { 17; Prev = Curr; // Prev = PHI (Prev_0, Curr) 18; Curr = A[i]; 19; for (j: 0..N) { 20; Curr[j] = Prev[j] * B[j] 21; B[j+1] = 2 // backward dep between this and the previous 22; } 23; } 24; 25; Since A[i] and A[i-1] are likely to be independent, getUnderlyingObjects 26; should not assume that Curr and Prev share the same underlying object. 27; 28; If it did we would try to dependence-analyze Curr and Prev and the analysis 29; would fail with non-constant distance. 30; 31; To illustrate one of the negative consequences of this, if the loop has a 32; backward dependence we won't detect this but instead fully fall back on 33; memchecks (that is what LAA does after encountering a case of non-constant 34; distance). 35 36target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" 37target triple = "x86_64-apple-macosx10.10.0" 38 39; CHECK-LABEL: function 'f' 40; CHECK: for_j.body: 41; CHECK-NEXT: Report: unsafe dependent memory operations in loop 42; CHECK-NEXT: Backward loop carried data dependence. 43; CHECK-NEXT: Dependences: 44; CHECK-NEXT: Backward: 45; CHECK-NEXT: %loadB = load i8, ptr %gepB, align 1 -> 46; CHECK-NEXT: store i8 2, ptr %gepB_plus_one, align 1 47 48define void @f(ptr noalias %A, ptr noalias %B, i64 %N) { 49for_i.preheader: 50 %prev_0 = load ptr, ptr %A, align 8 51 br label %for_i.body 52 53for_i.body: 54 %i = phi i64 [1, %for_i.preheader], [%i.1, %for_j.end] 55 %prev = phi ptr [%prev_0, %for_i.preheader], [%curr, %for_j.end] 56 %gep = getelementptr inbounds ptr, ptr %A, i64 %i 57 %curr = load ptr, ptr %gep, align 8 58 br label %for_j.preheader 59 60for_j.preheader: 61 br label %for_j.body 62 63for_j.body: 64 %j = phi i64 [0, %for_j.preheader], [%j.1, %for_j.body] 65 66 %gepPrev = getelementptr inbounds i8, ptr %prev, i64 %j 67 %gepCurr = getelementptr inbounds i8, ptr %curr, i64 %j 68 %gepB = getelementptr inbounds i8, ptr %B, i64 %j 69 70 %loadPrev = load i8, ptr %gepPrev, align 1 71 %loadB = load i8, ptr %gepB, align 1 72 73 %mul = mul i8 %loadPrev, %loadB 74 75 store i8 %mul, ptr %gepCurr, align 1 76 77 %gepB_plus_one = getelementptr inbounds i8, ptr %gepB, i64 1 78 store i8 2, ptr %gepB_plus_one, align 1 79 80 %j.1 = add nuw i64 %j, 1 81 %exitcondj = icmp eq i64 %j.1, %N 82 br i1 %exitcondj, label %for_j.end, label %for_j.body 83 84for_j.end: 85 86 %i.1 = add nuw i64 %i, 1 87 %exitcond = icmp eq i64 %i.1, %N 88 br i1 %exitcond, label %for_i.end, label %for_i.body 89 90for_i.end: 91 ret void 92} 93 94; CHECK-LABEL: function 'f_deep' 95; CHECK: for_j.body: 96; FIXME: This is incorrect and is going to be fixed with D86669. 97; CHECK-NEXT: Memory dependences are safe with run-time checks 98; CHECK-NEXT: Dependences: 99 100define void @f_deep(ptr noalias %A, ptr noalias %B, i64 %N) { 101for_i.preheader: 102 %prev_0 = load ptr, ptr %A, align 8 103 br label %for_i.body 104 105for_i.body: 106 %i = phi i64 [1, %for_i.preheader], [%i.1, %for_j.end] 107 %prev = phi ptr [%prev_0, %for_i.preheader], [%curr, %for_j.end] 108 %gep = getelementptr inbounds ptr, ptr %A, i64 %i 109 %curr = load ptr, ptr %gep, align 8 110 br label %for_j.preheader 111 112for_j.preheader: 113 br label %for_j.body 114 115for_j.body: 116 %j = phi i64 [0, %for_j.preheader], [%j.1, %for_j.body] 117 118 %gepPrev = getelementptr inbounds i8, ptr %prev, i64 %j 119 %gepCurr = getelementptr inbounds i8, ptr %curr, i64 %j 120 %gepB = getelementptr inbounds i8, ptr %B, i64 %j 121 %gepB1 = getelementptr inbounds i8, ptr %gepB, i64 %j 122 %gepB2 = getelementptr inbounds i8, ptr %gepB1, i64 0 123 %gepB3 = getelementptr inbounds i8, ptr %gepB2, i64 0 124 %gepB4 = getelementptr inbounds i8, ptr %gepB3, i64 0 125 %gepB5 = getelementptr inbounds i8, ptr %gepB4, i64 0 126 %gepB6 = getelementptr inbounds i8, ptr %gepB5, i64 0 127 %gepB7 = getelementptr inbounds i8, ptr %gepB6, i64 0 128 %gepB8 = getelementptr inbounds i8, ptr %gepB7, i64 0 129 %gepB9 = getelementptr inbounds i8, ptr %gepB8, i64 0 130 131 %loadPrev = load i8, ptr %gepPrev, align 1 132 %loadB = load i8, ptr %gepB9, align 1 133 134 %mul = mul i8 %loadPrev, %loadB 135 136 store i8 %mul, ptr %gepCurr, align 1 137 138 %gepB_plus_one = getelementptr inbounds i8, ptr %gepB, i64 1 139 store i8 2, ptr %gepB_plus_one, align 1 140 141 %j.1 = add nuw i64 %j, 1 142 %exitcondj = icmp eq i64 %j.1, %N 143 br i1 %exitcondj, label %for_j.end, label %for_j.body 144 145for_j.end: 146 147 %i.1 = add nuw i64 %i, 1 148 %exitcond = icmp eq i64 %i.1, %N 149 br i1 %exitcond, label %for_i.end, label %for_i.body 150 151for_i.end: 152 ret void 153} 154