llvm/test/Analysis/LoopAccessAnalysis/underlying-objects-2.ll

   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
  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-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
  48 define void @f(ptr noalias %A, ptr noalias %B, i64 %N) {
  49 for_i.preheader:
  50   %prev_0 = load ptr, ptr %A, align 8
  51   br label %for_i.body
  52
  53 for_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
  60 for_j.preheader:
  61   br label %for_j.body
  62
  63 for_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
  84 for_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
  90 for_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
 100 define void @f_deep(ptr noalias %A, ptr noalias %B, i64 %N) {
 101 for_i.preheader:
 102   %prev_0 = load ptr, ptr %A, align 8
 103   br label %for_i.body
 104
 105 for_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
 112 for_j.preheader:
 113   br label %for_j.body
 114
 115 for_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
 145 for_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
 151 for_i.end:
 152   ret void
 153 }