157 lines · plain
1; RUN: opt -passes='print<access-info>' -disable-output < %s 2>&1 | FileCheck %s2 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 previous10; }11;12; is transformed by Load-PRE to stash away A[i] for the next iteration of the13; outer loop:14;15; Curr = A[0]; // Prev_016; 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 previous22; }23; }24;25; Since A[i] and A[i-1] are likely to be independent, getUnderlyingObjects26; 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 analysis29; would fail with non-constant distance.30;31; To illustrate one of the negative consequences of this, if the loop has a32; backward dependence we won't detect this but instead fully fall back on33; memchecks (that is what LAA does after encountering a case of non-constant34; 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 loop42; 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 147 48define void @f(ptr noalias %A, ptr noalias %B, i64 %N) {49for_i.preheader:50 %prev_0 = load ptr, ptr %A, align 851 br label %for_i.body52 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 %i57 %curr = load ptr, ptr %gep, align 858 br label %for_j.preheader59 60for_j.preheader:61 br label %for_j.body62 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 %j67 %gepCurr = getelementptr inbounds i8, ptr %curr, i64 %j68 %gepB = getelementptr inbounds i8, ptr %B, i64 %j69 70 %loadPrev = load i8, ptr %gepPrev, align 171 %loadB = load i8, ptr %gepB, align 172 73 %mul = mul i8 %loadPrev, %loadB74 75 store i8 %mul, ptr %gepCurr, align 176 77 %gepB_plus_one = getelementptr inbounds i8, ptr %gepB, i64 178 store i8 2, ptr %gepB_plus_one, align 179 80 %j.1 = add nuw i64 %j, 181 %exitcondj = icmp eq i64 %j.1, %N82 br i1 %exitcondj, label %for_j.end, label %for_j.body83 84for_j.end:85 86 %i.1 = add nuw i64 %i, 187 %exitcond = icmp eq i64 %i.1, %N88 br i1 %exitcond, label %for_i.end, label %for_i.body89 90for_i.end:91 ret void92}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 checks98; 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 8103 br label %for_i.body104 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 %i109 %curr = load ptr, ptr %gep, align 8110 br label %for_j.preheader111 112for_j.preheader:113 br label %for_j.body114 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 %j119 %gepCurr = getelementptr inbounds i8, ptr %curr, i64 %j120 %gepB = getelementptr inbounds i8, ptr %B, i64 %j121 %gepB1 = getelementptr inbounds i8, ptr %gepB, i64 %j122 %gepB2 = getelementptr inbounds i8, ptr %gepB1, i64 0123 %gepB3 = getelementptr inbounds i8, ptr %gepB2, i64 0124 %gepB4 = getelementptr inbounds i8, ptr %gepB3, i64 0125 %gepB5 = getelementptr inbounds i8, ptr %gepB4, i64 0126 %gepB6 = getelementptr inbounds i8, ptr %gepB5, i64 0127 %gepB7 = getelementptr inbounds i8, ptr %gepB6, i64 0128 %gepB8 = getelementptr inbounds i8, ptr %gepB7, i64 0129 %gepB9 = getelementptr inbounds i8, ptr %gepB8, i64 0130 %gepB10 = getelementptr inbounds i8, ptr %gepB9, i64 0131 %gepB11 = getelementptr inbounds i8, ptr %gepB10, i64 0132 %gepB12 = getelementptr inbounds i8, ptr %gepB11, i64 0133 134 %loadPrev = load i8, ptr %gepPrev, align 1135 %loadB = load i8, ptr %gepB12, align 1136 137 %mul = mul i8 %loadPrev, %loadB138 139 store i8 %mul, ptr %gepCurr, align 1140 141 %gepB_plus_one = getelementptr inbounds i8, ptr %gepB, i64 1142 store i8 2, ptr %gepB_plus_one, align 1143 144 %j.1 = add nuw i64 %j, 1145 %exitcondj = icmp eq i64 %j.1, %N146 br i1 %exitcondj, label %for_j.end, label %for_j.body147 148for_j.end:149 150 %i.1 = add nuw i64 %i, 1151 %exitcond = icmp eq i64 %i.1, %N152 br i1 %exitcond, label %for_i.end, label %for_i.body153 154for_i.end:155 ret void156}157