[getUnderlyingOjbects] Analyze loop PHIs further to remove false positives
[oota-llvm.git] / test / Analysis / LoopAccessAnalysis / underlying-objects-2.ll
1 ; RUN: opt -basicaa -loop-accesses -analyze < %s | 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
36 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
37 target triple = "x86_64-apple-macosx10.10.0"
38
39 ; CHECK: for_j.body:
40 ; CHECK-NEXT: Store to invariant address was not found in loop
41 ; CHECK-NEXT: Report: unsafe dependent memory operations in loop
42 ; CHECK-NEXT: Interesting Dependences:
43 ; CHECK-NEXT: Backward:
44 ; CHECK-NEXT: %loadB = load i8, i8* %gepB, align 1 ->
45 ; CHECK-NEXT: store i8 2, i8* %gepB_plus_one, align 1
46
47 define void @f(i8** noalias %A, i8* noalias %B, i64 %N) {
48 for_i.preheader:
49   %prev_0 = load i8*, i8** %A, align 8
50   br label %for_i.body
51
52 for_i.body:
53   %i = phi i64 [1, %for_i.preheader], [%i.1, %for_j.end]
54   %prev = phi i8* [%prev_0, %for_i.preheader], [%curr, %for_j.end]
55   %gep = getelementptr inbounds i8*, i8** %A, i64 %i
56   %curr = load i8*, i8** %gep, align 8
57   br label %for_j.preheader
58
59 for_j.preheader:
60   br label %for_j.body
61
62 for_j.body:
63   %j = phi i64 [0, %for_j.preheader], [%j.1, %for_j.body]
64
65   %gepPrev = getelementptr inbounds i8, i8* %prev, i64 %j
66   %gepCurr = getelementptr inbounds i8, i8* %curr, i64 %j
67   %gepB = getelementptr inbounds i8, i8* %B, i64 %j
68
69   %loadPrev = load i8, i8* %gepPrev, align 1
70   %loadB = load i8, i8* %gepB, align 1
71
72   %mul = mul i8 %loadPrev, %loadB
73
74   store i8 %mul, i8* %gepCurr, align 1
75
76   %gepB_plus_one = getelementptr inbounds i8, i8* %gepB, i64 1
77   store i8 2, i8* %gepB_plus_one, align 1
78
79   %j.1 = add nuw i64 %j, 1
80   %exitcondj = icmp eq i64 %j.1, %N
81   br i1 %exitcondj, label %for_j.end, label %for_j.body
82
83 for_j.end:
84
85   %i.1 = add nuw i64 %i, 1
86   %exitcond = icmp eq i64 %i.1, %N
87   br i1 %exitcond, label %for_i.end, label %for_i.body
88
89 for_i.end:
90   ret void
91 }