test/Transforms/LoopInterchange/lcssa.ll

   1 ; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -pass-remarks-output=%t -S
   2 ; RUN: FileCheck --input-file %t --check-prefix REMARK %s
   3
   4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   5 target triple = "x86_64-unknown-linux-gnu"
   6
   7 @A = common global [100 x [100 x i32]] zeroinitializer
   8 @C = common global [100 x [100 x i32]] zeroinitializer
   9 @X = common global i32 0
  10 @Y = common global i64 0
  11 @F = common global float 0.0
  12
  13 ; We cannot interchange this loop at the moment, because iv.outer.next is
  14 ; produced in the outer loop latch and used in the loop exit block. If the inner
  15 ; loop body is not executed, the outer loop latch won't be executed either
  16 ; after interchanging.
  17 ; REMARK: UnsupportedExitPHI
  18 ; REMARK-NEXT: lcssa_01
  19
  20 define void @lcssa_01() {
  21 entry:
  22   %cmp21 = icmp sgt i64 100, 1
  23   br i1 %cmp21, label %outer.ph, label %for.end16
  24
  25 outer.ph:                                         ; preds = %entry
  26   %cmp218 = icmp sgt i64 100, 1
  27   br label %outer.header
  28
  29 outer.header:                                     ; preds = %outer.inc, %outer.ph
  30   %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
  31   br i1 %cmp218, label %for.body3, label %outer.inc
  32
  33 for.body3:                                        ; preds = %for.body3, %outer.header
  34   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
  35   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
  36   %vA = load i32, i32* %arrayidx5
  37   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
  38   %vC = load i32, i32* %arrayidx9
  39   %add = add nsw i32 %vA, %vC
  40   store i32 %add, i32* %arrayidx5
  41   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
  42   %exitcond = icmp eq i64 %iv.inner.next, 100
  43   br i1 %exitcond, label %outer.inc, label %for.body3
  44
  45 outer.inc:                                        ; preds = %for.body3, %outer.header
  46   %iv.outer.next = add nsw i64 %iv.outer, 1
  47   %cmp = icmp eq i64 %iv.outer.next, 100
  48   br i1 %cmp, label %outer.header, label %for.exit
  49
  50 for.exit:                                         ; preds = %outer.inc
  51   %iv.outer.next.lcssa = phi i64 [ %iv.outer.next, %outer.inc ]
  52   store i64 %iv.outer.next.lcssa, i64* @Y
  53   br label %for.end16
  54
  55 for.end16:                                        ; preds = %for.exit, %entry
  56   ret void
  57 }
  58
  59 ; REMARK: UnsupportedExitPHI
  60 ; REMARK-NEXT: lcssa_02
  61 define void @lcssa_02() {
  62 entry:
  63   %cmp21 = icmp sgt i64 100, 1
  64   br i1 %cmp21, label %outer.ph, label %for.end16
  65
  66 outer.ph:                                         ; preds = %entry
  67   %cmp218 = icmp sgt i64 100, 1
  68   br label %outer.header
  69
  70 outer.header:                                     ; preds = %outer.inc, %outer.ph
  71   %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
  72   br i1 %cmp218, label %for.body3, label %outer.inc
  73
  74 for.body3:                                        ; preds = %for.body3, %outer.header
  75   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
  76   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
  77   %vA = load i32, i32* %arrayidx5
  78   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
  79   %vC = load i32, i32* %arrayidx9
  80   %add = add nsw i32 %vA, %vC
  81   store i32 %add, i32* %arrayidx5
  82   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
  83   %exitcond = icmp eq i64 %iv.inner.next, 100
  84   br i1 %exitcond, label %outer.inc, label %for.body3
  85
  86 outer.inc:                                        ; preds = %for.body3, %outer.header
  87   %iv.inner.end = phi i64 [ 0, %outer.header ], [ %iv.inner.next, %for.body3 ]
  88   %iv.outer.next = add nsw i64 %iv.outer, 1
  89   %cmp = icmp eq i64 %iv.outer.next, 100
  90   br i1 %cmp, label %outer.header, label %for.exit
  91
  92 for.exit:                                         ; preds = %outer.inc
  93   %iv.inner.end.lcssa = phi i64 [ %iv.inner.end, %outer.inc ]
  94   store i64 %iv.inner.end.lcssa, i64* @Y
  95   br label %for.end16
  96
  97 for.end16:                                        ; preds = %for.exit, %entry
  98   ret void
  99 }
 100
 101 ; REMARK: Interchanged
 102 ; REMARK-NEXT: lcssa_03
 103 define void @lcssa_03() {
 104 entry:
 105   br label %outer.header
 106
 107 outer.header:                                     ; preds = %outer.inc, %entry
 108   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 109   br label %for.body3
 110
 111 for.body3:                                        ; preds = %for.body3, %outer.header
 112   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 113   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
 114   %vA = load i32, i32* %arrayidx5
 115   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
 116   %vC = load i32, i32* %arrayidx9
 117   %add = add nsw i32 %vA, %vC
 118   store i32 %add, i32* %arrayidx5
 119   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 120   %exitcond = icmp eq i64 %iv.inner.next, 100
 121   br i1 %exitcond, label %outer.inc, label %for.body3
 122
 123 outer.inc:                                        ; preds = %for.body3
 124   %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ]
 125   %iv.outer.next = add nsw i64 %iv.outer, 1
 126   %cmp = icmp eq i64 %iv.outer.next, 100
 127   br i1 %cmp, label %outer.header, label %for.exit
 128
 129 for.exit:                                         ; preds = %outer.inc
 130   %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
 131   store i64 %iv.inner.lcssa.lcssa, i64* @Y
 132   br label %for.end16
 133
 134 for.end16:                                        ; preds = %for.exit
 135   ret void
 136 }
 137
 138 ; FIXME: We currently do not support LCSSA phi nodes involving floating point
 139 ;        types, as we fail to detect floating point reductions for now.
 140 ; REMARK: UnsupportedPHIOuter
 141 ; REMARK-NEXT: lcssa_04
 142
 143 define void @lcssa_04() {
 144 entry:
 145   br label %outer.header
 146
 147 outer.header:                                     ; preds = %outer.inc, %entry
 148   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 149   %float.outer = phi float [ 1.000000e+00, %entry ], [ 2.000000e+00, %outer.inc ]
 150   br label %for.body3
 151
 152 for.body3:                                        ; preds = %for.body3, %outer.header
 153   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 154   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
 155   %vA = load i32, i32* %arrayidx5
 156   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
 157   %vC = load i32, i32* %arrayidx9
 158   %add = add nsw i32 %vA, %vC
 159   store i32 %add, i32* %arrayidx5
 160   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 161   %exitcond = icmp eq i64 %iv.inner.next, 100
 162   br i1 %exitcond, label %outer.inc, label %for.body3
 163
 164 outer.inc:                                        ; preds = %for.body3
 165   %iv.outer.next = add nsw i64 %iv.outer, 1
 166   %cmp = icmp eq i64 %iv.outer.next, 100
 167   br i1 %cmp, label %outer.header, label %for.exit
 168
 169 for.exit:                                         ; preds = %outer.inc
 170   %float.outer.lcssa = phi float [ %float.outer, %outer.inc ]
 171   store float %float.outer.lcssa, float* @F
 172   br label %for.end16
 173
 174 for.end16:                                        ; preds = %for.exit
 175   ret void
 176 }
 177
 178 ; PHI node in inner latch with multiple predecessors.
 179 ; REMARK: Interchanged
 180 ; REMARK-NEXT: lcssa_05
 181
 182 define void @lcssa_05(i32* %ptr) {
 183 entry:
 184   br label %outer.header
 185
 186 outer.header:                                     ; preds = %outer.inc, %entry
 187   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 188   br label %for.body3
 189
 190 for.body3:                                        ; preds = %bb3, %outer.header
 191   %iv.inner = phi i64 [ %iv.inner.next, %bb3 ], [ 1, %outer.header ]
 192   br i1 undef, label %bb2, label %bb3
 193
 194 bb2:                                              ; preds = %for.body3
 195   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
 196   %vA = load i32, i32* %arrayidx5
 197   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
 198   %vC = load i32, i32* %arrayidx9
 199   %add = add nsw i32 %vA, %vC
 200   br label %bb3
 201
 202 bb3:                                              ; preds = %bb2, %for.body3
 203   %addp = phi i32 [ %add, %bb2 ], [ 0, %for.body3 ]
 204   store i32 %addp, i32* %ptr
 205   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 206   %exitcond = icmp eq i64 %iv.inner.next, 100
 207   br i1 %exitcond, label %outer.inc, label %for.body3
 208
 209 outer.inc:                                        ; preds = %bb3
 210   %iv.inner.lcssa = phi i64 [ %iv.inner, %bb3 ]
 211   %iv.outer.next = add nsw i64 %iv.outer, 1
 212   %cmp = icmp eq i64 %iv.outer.next, 100
 213   br i1 %cmp, label %outer.header, label %for.exit
 214
 215 for.exit:                                         ; preds = %outer.inc
 216   %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
 217   store i64 %iv.inner.lcssa.lcssa, i64* @Y
 218   br label %for.end16
 219
 220 for.end16:                                        ; preds = %for.exit
 221   ret void
 222 }
 223
 224 ; REMARK: UnsupportedExitPHI
 225 ; REMARK-NEXT: lcssa_06
 226
 227 define void @lcssa_06(i64* %ptr, i32* %ptr1) {
 228 entry:
 229   br label %outer.header
 230
 231 outer.header:                                     ; preds = %outer.inc, %entry
 232   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 233   br i1 undef, label %for.body3, label %outer.inc
 234
 235 for.body3:                                        ; preds = %for.body3, %outer.header
 236   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 237   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
 238   %vA = load i32, i32* %arrayidx5
 239   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
 240   %vC = load i32, i32* %arrayidx9
 241   %add = add nsw i32 %vA, %vC
 242   store i32 %add, i32* %ptr1
 243   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 244   %exitcond = icmp eq i64 %iv.inner.next, 100
 245   br i1 %exitcond, label %outer.inc, label %for.body3
 246
 247 outer.inc:                                        ; preds = %for.body3, %outer.header
 248   %sv = phi i64 [ 0, %outer.header ], [ 1, %for.body3 ]
 249   %iv.outer.next = add nsw i64 %iv.outer, 1
 250   %cmp = icmp eq i64 %iv.outer.next, 100
 251   br i1 %cmp, label %outer.header, label %for.exit
 252
 253 for.exit:                                         ; preds = %outer.inc
 254   %sv.lcssa = phi i64 [ %sv, %outer.inc ]
 255   store i64 %sv.lcssa, i64* @Y
 256   br label %for.end16
 257
 258 for.end16:                                        ; preds = %for.exit
 259   ret void
 260 }
 261
 262 ; REMARK: Interchanged
 263 ; REMARK-NEXT: lcssa_07
 264 define void @lcssa_07() {
 265 entry:
 266   br label %outer.header
 267
 268 outer.header:                                     ; preds = %outer.inc, %entry
 269   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 270   br label %for.body3
 271
 272 for.body3:                                        ; preds = %for.body3, %outer.header
 273   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 274   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
 275   %vA = load i32, i32* %arrayidx5
 276   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
 277   %vC = load i32, i32* %arrayidx9
 278   %add = add nsw i32 %vA, %vC
 279   store i32 %add, i32* %arrayidx5
 280   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 281   %exitcond = icmp eq i64 %iv.inner.next, 100
 282   br i1 %exitcond, label %outer.bb, label %for.body3
 283
 284 outer.bb:                                         ; preds = %for.body3
 285   %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ]
 286   br label %outer.inc
 287
 288 outer.inc:                                        ; preds = %outer.bb
 289   %iv.outer.next = add nsw i64 %iv.outer, 1
 290   %cmp = icmp eq i64 %iv.outer.next, 100
 291   br i1 %cmp, label %outer.header, label %for.exit
 292
 293 for.exit:                                         ; preds = %outer.inc
 294   %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
 295   store i64 %iv.inner.lcssa.lcssa, i64* @Y
 296   br label %for.end16
 297
 298 for.end16:                                        ; preds = %for.exit
 299   ret void
 300 }