llvm/test/Analysis/LoopNestAnalysis/nests-with-lcssa.ll

   1 ; RUN: opt -S -passes='print<loopnest>' < %s 2>&1 > /dev/null | FileCheck %s
   2
   3 ; int f(int N, int M) {
   4 ;   int res = 0;
   5 ;   for (int i = 0; i < N; ++i) {
   6 ;     for (int j = 0; j < M; ++j) res += i * j;
   7 ;   }
   8 ;   return res;
   9 ; }
  10
  11 define i32 @f(i32 %N, i32 %M) #0 {
  12 ; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.j, Loops: ( for.j )
  13 ; CHECK: IsPerfect=true, Depth=2, OutermostLoop: for.i, Loops: ( for.i for.j )
  14 entry:
  15   %cmp4 = icmp slt i32 0, %N
  16   br i1 %cmp4, label %for.i.ph, label %for.i.end
  17
  18 for.i.ph:                                         ; preds = %entry
  19   br label %for.i
  20
  21 for.i:                                            ; preds = %for.i.ph, %for.i.inc
  22   %i.06 = phi i32 [ 0, %for.i.ph ], [ %inc5, %for.i.inc ]
  23   %res.05 = phi i32 [ 0, %for.i.ph ], [ %res.1.lcssa, %for.i.inc ]
  24   %cmp21 = icmp slt i32 0, %M
  25   br i1 %cmp21, label %for.j.ph, label %for.j.end
  26
  27 for.j.ph:                                         ; preds = %for.i
  28   br label %for.j
  29
  30 for.j:                                            ; preds = %for.j.ph, %for.j.inc
  31   %j.03 = phi i32 [ 0, %for.j.ph ], [ %inc, %for.j.inc ]
  32   %res.12 = phi i32 [ %res.05, %for.j.ph ], [ %add, %for.j.inc ]
  33   %mul = mul nsw i32 %i.06, %j.03
  34   %add = add nsw i32 %res.12, %mul
  35   br label %for.j.inc
  36
  37 for.j.inc:                                        ; preds = %for.j
  38   %inc = add nsw i32 %j.03, 1
  39   %cmp2 = icmp slt i32 %inc, %M
  40   br i1 %cmp2, label %for.j, label %for.j.end_crit_edge
  41
  42 for.j.end_crit_edge:                              ; preds = %for.j.inc
  43   %split = phi i32 [ %add, %for.j.inc ]
  44   br label %for.j.end
  45
  46 for.j.end:                                        ; preds = %for.j.end_crit_edge, %for.i
  47   %res.1.lcssa = phi i32 [ %split, %for.j.end_crit_edge ], [ %res.05, %for.i ]
  48   br label %for.i.inc
  49
  50 for.i.inc:                                        ; preds = %for.j.end
  51   %inc5 = add nsw i32 %i.06, 1
  52   %cmp = icmp slt i32 %inc5, %N
  53   br i1 %cmp, label %for.i, label %for.i.end_crit_edge
  54
  55 for.i.end_crit_edge:                              ; preds = %for.i.inc
  56   %split7 = phi i32 [ %res.1.lcssa, %for.i.inc ]
  57   br label %for.i.end
  58
  59 for.i.end:                                        ; preds = %for.i.end_crit_edge, %entry
  60   %res.0.lcssa = phi i32 [ %split7, %for.i.end_crit_edge ], [ 0, %entry ]
  61   ret i32 %res.0.lcssa
  62 }
  63
  64 ; int g(int N, int M, int K) {
  65 ;   int sum = 0, prod = 1;
  66 ;   for (int i = 0; i < N; ++i) {
  67 ;     for (int j = 0; j < M; ++j) {
  68 ;       for (int k = 0; k < K; ++k) {
  69 ;         sum += i * j * k;
  70 ;       }
  71 ;       prod *= (i + j);
  72 ;     }
  73 ;   }
  74 ;   return sum + prod;
  75 ; }
  76 define i32 @g(i32 %N, i32 %M, i32 %K) #0 {
  77 ; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.k, Loops: ( for.k )
  78 ; CHECK: IsPerfect=false, Depth=2, OutermostLoop: for.j, Loops: ( for.j for.k )
  79 ; CHECK: IsPerfect=false, Depth=3, OutermostLoop: for.i, Loops: ( for.i for.j for.k )
  80 entry:
  81   %cmp10 = icmp slt i32 0, %N
  82   br i1 %cmp10, label %for.i.ph, label %for.i.end
  83
  84 for.i.ph:                                         ; preds = %entry
  85   br label %for.i
  86
  87 for.i:                                            ; preds = %for.i.ph, %for.i.inc
  88   %i.013 = phi i32 [ 0, %for.i.ph ], [ %inc14, %for.i.inc ]
  89   %sum.012 = phi i32 [ 0, %for.i.ph ], [ %sum.1.lcssa, %for.i.inc ]
  90   %prod.011 = phi i32 [ 1, %for.i.ph ], [ %prod.1.lcssa, %for.i.inc ]
  91   %cmp24 = icmp slt i32 0, %M
  92   br i1 %cmp24, label %for.j.ph, label %for.j.end
  93
  94 for.j.ph:                                         ; preds = %for.i
  95   br label %for.j
  96
  97 for.j:                                            ; preds = %for.j.ph, %for.j.inc
  98   %j.07 = phi i32 [ 0, %for.j.ph ], [ %inc11, %for.j.inc ]
  99   %sum.16 = phi i32 [ %sum.012, %for.j.ph ], [ %sum.2.lcssa, %for.j.inc ]
 100   %prod.15 = phi i32 [ %prod.011, %for.j.ph ], [ %mul9, %for.j.inc ]
 101   %cmp51 = icmp slt i32 0, %K
 102   br i1 %cmp51, label %for.k.ph, label %for.k.end
 103
 104 for.k.ph:                                         ; preds = %for.j
 105   br label %for.k
 106
 107 for.k:                                            ; preds = %for.k.ph, %for.k.inc
 108   %k.03 = phi i32 [ 0, %for.k.ph ], [ %inc, %for.k.inc ]
 109   %sum.22 = phi i32 [ %sum.16, %for.k.ph ], [ %add, %for.k.inc ]
 110   %mul = mul nsw i32 %i.013, %j.07
 111   %mul7 = mul nsw i32 %mul, %k.03
 112   %add = add nsw i32 %sum.22, %mul7
 113   br label %for.k.inc
 114
 115 for.k.inc:                                        ; preds = %for.k
 116   %inc = add nsw i32 %k.03, 1
 117   %cmp5 = icmp slt i32 %inc, %K
 118   br i1 %cmp5, label %for.k, label %for.k.end_crit_edge
 119
 120 for.k.end_crit_edge:                              ; preds = %for.k.inc
 121   %split = phi i32 [ %add, %for.k.inc ]
 122   br label %for.k.end
 123
 124 for.k.end:                                        ; preds = %for.k.end_crit_edge, %for.j
 125   %sum.2.lcssa = phi i32 [ %split, %for.k.end_crit_edge ], [ %sum.16, %for.j ]
 126   %add8 = add nsw i32 %i.013, %j.07
 127   %mul9 = mul nsw i32 %prod.15, %add8
 128   br label %for.j.inc
 129
 130 for.j.inc:                                        ; preds = %for.k.end
 131   %inc11 = add nsw i32 %j.07, 1
 132   %cmp2 = icmp slt i32 %inc11, %M
 133   br i1 %cmp2, label %for.j, label %for.j.end_crit_edge
 134
 135 for.j.end_crit_edge:                              ; preds = %for.j.inc
 136   %split8 = phi i32 [ %mul9, %for.j.inc ]
 137   %split9 = phi i32 [ %sum.2.lcssa, %for.j.inc ]
 138   br label %for.j.end
 139
 140 for.j.end:                                        ; preds = %for.j.end1crit_edge, %for.i
 141   %prod.1.lcssa = phi i32 [ %split8, %for.j.end_crit_edge ], [ %prod.011, %for.i ]
 142   %sum.1.lcssa = phi i32 [ %split9, %for.j.end_crit_edge ], [ %sum.012, %for.i ]
 143   br label %for.i.inc
 144
 145 for.i.inc:                                        ; preds = %for.j.end
 146   %inc14 = add nsw i32 %i.013, 1
 147   %cmp = icmp slt i32 %inc14, %N
 148   br i1 %cmp, label %for.i, label %for.i.end_crit_edge
 149
 150 for.i.end_crit_edge:                              ; preds = %for.i.inc
 151   %split14 = phi i32 [ %prod.1.lcssa, %for.i.inc ]
 152   %split15 = phi i32 [ %sum.1.lcssa, %for.i.inc ]
 153   br label %for.i.end
 154
 155 for.i.end:                                        ; preds = %for.i.end_crit_edge, %entry
 156   %prod.0.lcssa = phi i32 [ %split14, %for.i.end_crit_edge ], [ 1, %entry ]
 157   %sum.0.lcssa = phi i32 [ %split15, %for.i.end_crit_edge ], [ 0, %entry ]
 158   %add16 = add nsw i32 %sum.0.lcssa, %prod.0.lcssa
 159   ret i32 %add16
 160 }
 161
 162 ; int h(int N, int M, int K) {
 163 ;   int sum = 0;
 164 ;   for (int i = 0; i < N; ++i) {
 165 ;     for (int j = 0; j < M; ++j) {
 166 ;       for (int k = 0; k < K; ++k) {
 167 ;         sum += i * j * k;
 168 ;       }
 169 ;     }
 170 ;   }
 171 ;   return sum;
 172 ; }
 173 define i32 @h(i32 %N, i32 %M, i32 %K) #0 {
 174 ; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.k, Loops: ( for.k )
 175 ; CHECK: IsPerfect=true, Depth=2, OutermostLoop: for.j, Loops: ( for.j for.k )
 176 ; CHECK: IsPerfect=true, Depth=3, OutermostLoop: for.i, Loops: ( for.i for.j for.k )
 177 entry:
 178   %cmp8 = icmp slt i32 0, %N
 179   br i1 %cmp8, label %for.i.ph, label %for.i.end
 180
 181 for.i.ph:                                         ; preds = %entry
 182   br label %for.i
 183
 184 for.i:                                            ; preds = %for.i.ph, %for.i.inc
 185   %i.010 = phi i32 [ 0, %for.i.ph ], [ %inc12, %for.i.inc ]
 186   %sum.09 = phi i32 [ 0, %for.i.ph ], [ %sum.1.lcssa, %for.i.inc ]
 187   %cmp24 = icmp slt i32 0, %M
 188   br i1 %cmp24, label %for.j.ph, label %for.j.end
 189
 190 for.j.ph:                                         ; preds = %for.i
 191   br label %for.j
 192
 193 for.j:                                            ; preds = %for.j.ph, %for.j.inc
 194   %j.06 = phi i32 [ 0, %for.j.ph ], [ %inc9, %for.j.inc ]
 195   %sum.15 = phi i32 [ %sum.09, %for.j.ph ], [ %sum.2.lcssa, %for.j.inc ]
 196   %cmp51 = icmp slt i32 0, %K
 197   br i1 %cmp51, label %for.k.ph, label %for.k.end
 198
 199 for.k.ph:                                         ; preds = %for.j
 200   br label %for.k
 201
 202 for.k:                                            ; preds = %for.k.ph, %for.k.inc
 203   %k.03 = phi i32 [ 0, %for.k.ph ], [ %inc, %for.k.inc ]
 204   %sum.22 = phi i32 [ %sum.15, %for.k.ph ], [ %add, %for.k.inc ]
 205   %mul = mul nsw i32 %i.010, %j.06
 206   %mul7 = mul nsw i32 %mul, %k.03
 207   %add = add nsw i32 %sum.22, %mul7
 208   br label %for.k.inc
 209
 210 for.k.inc:                                        ; preds = %for.k
 211   %inc = add nsw i32 %k.03, 1
 212   %cmp5 = icmp slt i32 %inc, %K
 213   br i1 %cmp5, label %for.k, label %for.k.end_crit_edge
 214
 215 for.k.end_crit_edge:                              ; preds = %for.k.inc
 216   %split = phi i32 [ %add, %for.k.inc ]
 217   br label %for.k.end
 218
 219 for.k.end:                                        ; preds = %for.k.end_crit_edge, %for.j
 220   %sum.2.lcssa = phi i32 [ %split, %for.k.end_crit_edge ], [ %sum.15, %for.j ]
 221   br label %for.j.inc
 222
 223 for.j.inc:                                        ; preds = %for.k.end
 224   %inc9 = add nsw i32 %j.06, 1
 225   %cmp2 = icmp slt i32 %inc9, %M
 226   br i1 %cmp2, label %for.j, label %for.j.end_crit_edge
 227
 228 for.j.end_crit_edge:                              ; preds = %for.j.inc
 229   %split7 = phi i32 [ %sum.2.lcssa, %for.j.inc ]
 230   br label %for.j.end
 231
 232 for.j.end:                                        ; preds = %for.j.end_crit_edge, %for.i
 233   %sum.1.lcssa = phi i32 [ %split7, %for.j.end_crit_edge ], [ %sum.09, %for.i ]
 234   br label %for.i.inc
 235
 236 for.i.inc:                                        ; preds = %for.j.end
 237   %inc12 = add nsw i32 %i.010, 1
 238   %cmp = icmp slt i32 %inc12, %N
 239   br i1 %cmp, label %for.i, label %for.i.end_crit_edge
 240
 241 for.i.end_crit_edge:                              ; preds = %for.i.inc
 242   %split11 = phi i32 [ %sum.1.lcssa, %for.i.inc ]
 243   br label %for.i.end
 244
 245 for.i.end:                                        ; preds = %for.i.end_crit_edge, %entry
 246   %sum.0.lcssa = phi i32 [ %split11, %for.i.end_crit_edge ], [ 0, %entry ]
 247   ret i32 %sum.0.lcssa
 248 }