test/Analysis/DependenceAnalysis/Separability.ll

   1 ; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
   2
   3 ; ModuleID = 'Separability.bc'
   4 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
   5 target triple = "x86_64-apple-macosx10.6.0"
   6
   7
   8 ;;  for (long int i = 0; i < 50; i++)
   9 ;;    for (long int j = 0; j < 50; j++)
  10 ;;      for (long int k = 0; k < 50; k++)
  11 ;;        for (long int l = 0; l < 50; l++)
  12 ;;          A[n][i][j + k] = ...
  13 ;;          ... = A[10][i + 10][2*j - l];
  14
  15 define void @sep0([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
  16 entry:
  17   br label %for.cond1.preheader
  18
  19 for.cond1.preheader:                              ; preds = %for.inc22, %entry
  20   %B.addr.08 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.inc22 ]
  21   %i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ]
  22   br label %for.cond4.preheader
  23
  24 for.cond4.preheader:                              ; preds = %for.inc19, %for.cond1.preheader
  25   %B.addr.16 = phi i32* [ %B.addr.08, %for.cond1.preheader ], [ %incdec.ptr, %for.inc19 ]
  26   %j.05 = phi i64 [ 0, %for.cond1.preheader ], [ %inc20, %for.inc19 ]
  27   br label %for.cond7.preheader
  28
  29 for.cond7.preheader:                              ; preds = %for.inc16, %for.cond4.preheader
  30   %B.addr.24 = phi i32* [ %B.addr.16, %for.cond4.preheader ], [ %incdec.ptr, %for.inc16 ]
  31   %k.03 = phi i64 [ 0, %for.cond4.preheader ], [ %inc17, %for.inc16 ]
  32   br label %for.body9
  33
  34 for.body9:                                        ; preds = %for.body9, %for.cond7.preheader
  35   %l.02 = phi i64 [ 0, %for.cond7.preheader ], [ %inc, %for.body9 ]
  36   %B.addr.31 = phi i32* [ %B.addr.24, %for.cond7.preheader ], [ %incdec.ptr, %for.body9 ]
  37   %conv = trunc i64 %i.07 to i32
  38   %add = add nsw i64 %j.05, %k.03
  39   %idxprom = sext i32 %n to i64
  40   %arrayidx11 = getelementptr inbounds [100 x [100 x i32]]* %A, i64 %idxprom, i64 %i.07, i64 %add
  41   store i32 %conv, i32* %arrayidx11, align 4
  42   %mul = shl nsw i64 %j.05, 1
  43   %sub = sub nsw i64 %mul, %l.02
  44   %add12 = add nsw i64 %i.07, 10
  45   %arrayidx15 = getelementptr inbounds [100 x [100 x i32]]* %A, i64 10, i64 %add12, i64 %sub
  46   %0 = load i32* %arrayidx15, align 4
  47 ; CHECK: da analyze - flow [-10 * * *]!
  48   %incdec.ptr = getelementptr inbounds i32* %B.addr.31, i64 1
  49   store i32 %0, i32* %B.addr.31, align 4
  50   %inc = add nsw i64 %l.02, 1
  51   %cmp8 = icmp slt i64 %inc, 50
  52   br i1 %cmp8, label %for.body9, label %for.inc16
  53
  54 for.inc16:                                        ; preds = %for.body9
  55   %inc17 = add nsw i64 %k.03, 1
  56   %cmp5 = icmp slt i64 %inc17, 50
  57   br i1 %cmp5, label %for.cond7.preheader, label %for.inc19
  58
  59 for.inc19:                                        ; preds = %for.inc16
  60   %inc20 = add nsw i64 %j.05, 1
  61   %cmp2 = icmp slt i64 %inc20, 50
  62   br i1 %cmp2, label %for.cond4.preheader, label %for.inc22
  63
  64 for.inc22:                                        ; preds = %for.inc19
  65   %inc23 = add nsw i64 %i.07, 1
  66   %cmp = icmp slt i64 %inc23, 50
  67   br i1 %cmp, label %for.cond1.preheader, label %for.end24
  68
  69 for.end24:                                        ; preds = %for.inc22
  70   ret void
  71 }
  72
  73
  74 ;;  for (long int i = 0; i < 50; i++)
  75 ;;    for (long int j = 0; j < 50; j++)
  76 ;;      for (long int k = 0; k < 50; k++)
  77 ;;        for (long int l = 0; l < 50; l++)
  78 ;;          A[i][i][j + k] = ...
  79 ;;          ... = A[10][i + 10][2*j - l];
  80
  81 define void @sep1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
  82 entry:
  83   br label %for.cond1.preheader
  84
  85 for.cond1.preheader:                              ; preds = %for.inc22, %entry
  86   %B.addr.08 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.inc22 ]
  87   %i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ]
  88   br label %for.cond4.preheader
  89
  90 for.cond4.preheader:                              ; preds = %for.inc19, %for.cond1.preheader
  91   %B.addr.16 = phi i32* [ %B.addr.08, %for.cond1.preheader ], [ %incdec.ptr, %for.inc19 ]
  92   %j.05 = phi i64 [ 0, %for.cond1.preheader ], [ %inc20, %for.inc19 ]
  93   br label %for.cond7.preheader
  94
  95 for.cond7.preheader:                              ; preds = %for.inc16, %for.cond4.preheader
  96   %B.addr.24 = phi i32* [ %B.addr.16, %for.cond4.preheader ], [ %incdec.ptr, %for.inc16 ]
  97   %k.03 = phi i64 [ 0, %for.cond4.preheader ], [ %inc17, %for.inc16 ]
  98   br label %for.body9
  99
 100 for.body9:                                        ; preds = %for.body9, %for.cond7.preheader
 101   %l.02 = phi i64 [ 0, %for.cond7.preheader ], [ %inc, %for.body9 ]
 102   %B.addr.31 = phi i32* [ %B.addr.24, %for.cond7.preheader ], [ %incdec.ptr, %for.body9 ]
 103   %conv = trunc i64 %i.07 to i32
 104   %add = add nsw i64 %j.05, %k.03
 105   %arrayidx11 = getelementptr inbounds [100 x [100 x i32]]* %A, i64 %i.07, i64 %i.07, i64 %add
 106   store i32 %conv, i32* %arrayidx11, align 4
 107   %mul = shl nsw i64 %j.05, 1
 108   %sub = sub nsw i64 %mul, %l.02
 109   %add12 = add nsw i64 %i.07, 10
 110   %arrayidx15 = getelementptr inbounds [100 x [100 x i32]]* %A, i64 10, i64 %add12, i64 %sub
 111   %0 = load i32* %arrayidx15, align 4
 112 ; CHECK: da analyze - flow [> * * *]!
 113   %incdec.ptr = getelementptr inbounds i32* %B.addr.31, i64 1
 114   store i32 %0, i32* %B.addr.31, align 4
 115   %inc = add nsw i64 %l.02, 1
 116   %cmp8 = icmp slt i64 %inc, 50
 117   br i1 %cmp8, label %for.body9, label %for.inc16
 118
 119 for.inc16:                                        ; preds = %for.body9
 120   %inc17 = add nsw i64 %k.03, 1
 121   %cmp5 = icmp slt i64 %inc17, 50
 122   br i1 %cmp5, label %for.cond7.preheader, label %for.inc19
 123
 124 for.inc19:                                        ; preds = %for.inc16
 125   %inc20 = add nsw i64 %j.05, 1
 126   %cmp2 = icmp slt i64 %inc20, 50
 127   br i1 %cmp2, label %for.cond4.preheader, label %for.inc22
 128
 129 for.inc22:                                        ; preds = %for.inc19
 130   %inc23 = add nsw i64 %i.07, 1
 131   %cmp = icmp slt i64 %inc23, 50
 132   br i1 %cmp, label %for.cond1.preheader, label %for.end24
 133
 134 for.end24:                                        ; preds = %for.inc22
 135   ret void
 136 }
 137
 138
 139 ;;  for (long int i = 0; i < 50; i++)
 140 ;;    for (long int j = 0; j < 50; j++)
 141 ;;      for (long int k = 0; k < 50; k++)
 142 ;;        for (long int l = 0; l < 50; l++)
 143 ;;          A[i][i][i + k][l] = ...
 144 ;;          ... = A[10][i + 10][j + k][l + 10];
 145
 146 define void @sep2([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 147 entry:
 148   br label %for.cond1.preheader
 149
 150 for.cond1.preheader:                              ; preds = %for.inc26, %entry
 151   %B.addr.08 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.inc26 ]
 152   %i.07 = phi i64 [ 0, %entry ], [ %inc27, %for.inc26 ]
 153   br label %for.cond4.preheader
 154
 155 for.cond4.preheader:                              ; preds = %for.inc23, %for.cond1.preheader
 156   %B.addr.16 = phi i32* [ %B.addr.08, %for.cond1.preheader ], [ %incdec.ptr, %for.inc23 ]
 157   %j.05 = phi i64 [ 0, %for.cond1.preheader ], [ %inc24, %for.inc23 ]
 158   br label %for.cond7.preheader
 159
 160 for.cond7.preheader:                              ; preds = %for.inc20, %for.cond4.preheader
 161   %B.addr.24 = phi i32* [ %B.addr.16, %for.cond4.preheader ], [ %incdec.ptr, %for.inc20 ]
 162   %k.03 = phi i64 [ 0, %for.cond4.preheader ], [ %inc21, %for.inc20 ]
 163   br label %for.body9
 164
 165 for.body9:                                        ; preds = %for.body9, %for.cond7.preheader
 166   %l.02 = phi i64 [ 0, %for.cond7.preheader ], [ %inc, %for.body9 ]
 167   %B.addr.31 = phi i32* [ %B.addr.24, %for.cond7.preheader ], [ %incdec.ptr, %for.body9 ]
 168   %conv = trunc i64 %i.07 to i32
 169   %add = add nsw i64 %i.07, %k.03
 170   %arrayidx12 = getelementptr inbounds [100 x [100 x [100 x i32]]]* %A, i64 %i.07, i64 %i.07, i64 %add, i64 %l.02
 171   store i32 %conv, i32* %arrayidx12, align 4
 172   %add13 = add nsw i64 %l.02, 10
 173   %add14 = add nsw i64 %j.05, %k.03
 174   %add15 = add nsw i64 %i.07, 10
 175   %arrayidx19 = getelementptr inbounds [100 x [100 x [100 x i32]]]* %A, i64 10, i64 %add15, i64 %add14, i64 %add13
 176   %0 = load i32* %arrayidx19, align 4
 177 ; CHECK: da analyze - flow [> * * -10]!
 178   %incdec.ptr = getelementptr inbounds i32* %B.addr.31, i64 1
 179   store i32 %0, i32* %B.addr.31, align 4
 180   %inc = add nsw i64 %l.02, 1
 181   %cmp8 = icmp slt i64 %inc, 50
 182   br i1 %cmp8, label %for.body9, label %for.inc20
 183
 184 for.inc20:                                        ; preds = %for.body9
 185   %inc21 = add nsw i64 %k.03, 1
 186   %cmp5 = icmp slt i64 %inc21, 50
 187   br i1 %cmp5, label %for.cond7.preheader, label %for.inc23
 188
 189 for.inc23:                                        ; preds = %for.inc20
 190   %inc24 = add nsw i64 %j.05, 1
 191   %cmp2 = icmp slt i64 %inc24, 50
 192   br i1 %cmp2, label %for.cond4.preheader, label %for.inc26
 193
 194 for.inc26:                                        ; preds = %for.inc23
 195   %inc27 = add nsw i64 %i.07, 1
 196   %cmp = icmp slt i64 %inc27, 50
 197   br i1 %cmp, label %for.cond1.preheader, label %for.end28
 198
 199 for.end28:                                        ; preds = %for.inc26
 200   ret void
 201 }
 202
 203
 204 ;;  for (long int i = 0; i < 50; i++)
 205 ;;    for (long int j = 0; j < 50; j++)
 206 ;;      for (long int k = 0; k < 50; k++)
 207 ;;        for (long int l = 0; l < 50; l++)
 208 ;;          A[i][i][i + k][l + k] = ...
 209 ;;          ... = A[10][i + 10][j + k][l + 10];
 210
 211 define void @sep3([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
 212 entry:
 213   br label %for.cond1.preheader
 214
 215 for.cond1.preheader:                              ; preds = %for.inc27, %entry
 216   %B.addr.08 = phi i32* [ %B, %entry ], [ %incdec.ptr, %for.inc27 ]
 217   %i.07 = phi i64 [ 0, %entry ], [ %inc28, %for.inc27 ]
 218   br label %for.cond4.preheader
 219
 220 for.cond4.preheader:                              ; preds = %for.inc24, %for.cond1.preheader
 221   %B.addr.16 = phi i32* [ %B.addr.08, %for.cond1.preheader ], [ %incdec.ptr, %for.inc24 ]
 222   %j.05 = phi i64 [ 0, %for.cond1.preheader ], [ %inc25, %for.inc24 ]
 223   br label %for.cond7.preheader
 224
 225 for.cond7.preheader:                              ; preds = %for.inc21, %for.cond4.preheader
 226   %B.addr.24 = phi i32* [ %B.addr.16, %for.cond4.preheader ], [ %incdec.ptr, %for.inc21 ]
 227   %k.03 = phi i64 [ 0, %for.cond4.preheader ], [ %inc22, %for.inc21 ]
 228   br label %for.body9
 229
 230 for.body9:                                        ; preds = %for.body9, %for.cond7.preheader
 231   %l.02 = phi i64 [ 0, %for.cond7.preheader ], [ %inc, %for.body9 ]
 232   %B.addr.31 = phi i32* [ %B.addr.24, %for.cond7.preheader ], [ %incdec.ptr, %for.body9 ]
 233   %conv = trunc i64 %i.07 to i32
 234   %add = add nsw i64 %l.02, %k.03
 235   %add10 = add nsw i64 %i.07, %k.03
 236   %arrayidx13 = getelementptr inbounds [100 x [100 x [100 x i32]]]* %A, i64 %i.07, i64 %i.07, i64 %add10, i64 %add
 237   store i32 %conv, i32* %arrayidx13, align 4
 238   %add14 = add nsw i64 %l.02, 10
 239   %add15 = add nsw i64 %j.05, %k.03
 240   %add16 = add nsw i64 %i.07, 10
 241   %arrayidx20 = getelementptr inbounds [100 x [100 x [100 x i32]]]* %A, i64 10, i64 %add16, i64 %add15, i64 %add14
 242   %0 = load i32* %arrayidx20, align 4
 243 ; CHECK: da analyze - flow [> * * *]!
 244   %incdec.ptr = getelementptr inbounds i32* %B.addr.31, i64 1
 245   store i32 %0, i32* %B.addr.31, align 4
 246   %inc = add nsw i64 %l.02, 1
 247   %cmp8 = icmp slt i64 %inc, 50
 248   br i1 %cmp8, label %for.body9, label %for.inc21
 249
 250 for.inc21:                                        ; preds = %for.body9
 251   %inc22 = add nsw i64 %k.03, 1
 252   %cmp5 = icmp slt i64 %inc22, 50
 253   br i1 %cmp5, label %for.cond7.preheader, label %for.inc24
 254
 255 for.inc24:                                        ; preds = %for.inc21
 256   %inc25 = add nsw i64 %j.05, 1
 257   %cmp2 = icmp slt i64 %inc25, 50
 258   br i1 %cmp2, label %for.cond4.preheader, label %for.inc27
 259
 260 for.inc27:                                        ; preds = %for.inc24
 261   %inc28 = add nsw i64 %i.07, 1
 262   %cmp = icmp slt i64 %inc28, 50
 263   br i1 %cmp, label %for.cond1.preheader, label %for.end29
 264
 265 for.end29:                                        ; preds = %for.inc27
 266   ret void
 267 }