llvm/test/Transforms/LoopInterchange/lcssa.ll

   1 ; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -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
   6 @A = common global [100 x [100 x i32]] zeroinitializer
   7 @C = common global [100 x [100 x i32]] zeroinitializer
   8 @X = common global i32 0
   9 @Y = common global i64 0
  10 @F = common global float 0.0
  11
  12 ; We cannot interchange this loop at the moment, because iv.outer.next is
  13 ; produced in the outer loop latch and used in the loop exit block. If the inner
  14 ; loop body is not executed, the outer loop latch won't be executed either
  15 ; after interchanging.
  16 ; REMARK: UnsupportedExitPHI
  17 ; REMARK-NEXT: lcssa_01
  18
  19 define void @lcssa_01() {
  20 entry:
  21   %cmp21 = icmp sgt i64 100, 1
  22   br i1 %cmp21, label %outer.ph, label %for.end16
  23
  24 outer.ph:                                         ; preds = %entry
  25   %cmp218 = icmp sgt i64 100, 1
  26   br label %outer.header
  27
  28 outer.header:                                     ; preds = %outer.inc, %outer.ph
  29   %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
  30   br i1 %cmp218, label %for.body3, label %outer.inc
  31
  32 for.body3:                                        ; preds = %for.body3, %outer.header
  33   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
  34   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %iv.inner, i64 %iv.outer
  35   %vA = load i32, ptr %arrayidx5
  36   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @C, i64 0, i64 %iv.inner, i64 %iv.outer
  37   %vC = load i32, ptr %arrayidx9
  38   %add = add nsw i32 %vA, %vC
  39   store i32 %add, ptr %arrayidx5
  40   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
  41   %exitcond = icmp eq i64 %iv.inner.next, 100
  42   br i1 %exitcond, label %outer.inc, label %for.body3
  43
  44 outer.inc:                                        ; preds = %for.body3, %outer.header
  45   %iv.outer.next = add nsw i64 %iv.outer, 1
  46   %cmp = icmp eq i64 %iv.outer.next, 100
  47   br i1 %cmp, label %outer.header, label %for.exit
  48
  49 for.exit:                                         ; preds = %outer.inc
  50   %iv.outer.next.lcssa = phi i64 [ %iv.outer.next, %outer.inc ]
  51   store i64 %iv.outer.next.lcssa, ptr @Y
  52   br label %for.end16
  53
  54 for.end16:                                        ; preds = %for.exit, %entry
  55   ret void
  56 }
  57
  58 ; REMARK: UnsupportedExitPHI
  59 ; REMARK-NEXT: lcssa_02
  60 define void @lcssa_02() {
  61 entry:
  62   %cmp21 = icmp sgt i64 100, 1
  63   br i1 %cmp21, label %outer.ph, label %for.end16
  64
  65 outer.ph:                                         ; preds = %entry
  66   %cmp218 = icmp sgt i64 100, 1
  67   br label %outer.header
  68
  69 outer.header:                                     ; preds = %outer.inc, %outer.ph
  70   %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
  71   br i1 %cmp218, label %for.body3, label %outer.inc
  72
  73 for.body3:                                        ; preds = %for.body3, %outer.header
  74   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
  75   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %iv.inner, i64 %iv.outer
  76   %vA = load i32, ptr %arrayidx5
  77   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @C, i64 0, i64 %iv.inner, i64 %iv.outer
  78   %vC = load i32, ptr %arrayidx9
  79   %add = add nsw i32 %vA, %vC
  80   store i32 %add, ptr %arrayidx5
  81   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
  82   %exitcond = icmp eq i64 %iv.inner.next, 100
  83   br i1 %exitcond, label %outer.inc, label %for.body3
  84
  85 outer.inc:                                        ; preds = %for.body3, %outer.header
  86   %iv.inner.end = phi i64 [ 0, %outer.header ], [ %iv.inner.next, %for.body3 ]
  87   %iv.outer.next = add nsw i64 %iv.outer, 1
  88   %cmp = icmp eq i64 %iv.outer.next, 100
  89   br i1 %cmp, label %outer.header, label %for.exit
  90
  91 for.exit:                                         ; preds = %outer.inc
  92   %iv.inner.end.lcssa = phi i64 [ %iv.inner.end, %outer.inc ]
  93   store i64 %iv.inner.end.lcssa, ptr @Y
  94   br label %for.end16
  95
  96 for.end16:                                        ; preds = %for.exit, %entry
  97   ret void
  98 }
  99
 100 ; REMARK: Interchanged
 101 ; REMARK-NEXT: lcssa_03
 102 define void @lcssa_03() {
 103 entry:
 104   br label %outer.header
 105
 106 outer.header:                                     ; preds = %outer.inc, %entry
 107   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 108   br label %for.body3
 109
 110 for.body3:                                        ; preds = %for.body3, %outer.header
 111   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 112   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %iv.inner, i64 %iv.outer
 113   %vA = load i32, ptr %arrayidx5
 114   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @C, i64 0, i64 %iv.inner, i64 %iv.outer
 115   %vC = load i32, ptr %arrayidx9
 116   %add = add nsw i32 %vA, %vC
 117   store i32 %add, ptr %arrayidx5
 118   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 119   %exitcond = icmp eq i64 %iv.inner.next, 100
 120   br i1 %exitcond, label %outer.inc, label %for.body3
 121
 122 outer.inc:                                        ; preds = %for.body3
 123   %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ]
 124   %iv.outer.next = add nsw i64 %iv.outer, 1
 125   %cmp = icmp eq i64 %iv.outer.next, 100
 126   br i1 %cmp, label %outer.header, label %for.exit
 127
 128 for.exit:                                         ; preds = %outer.inc
 129   %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
 130   store i64 %iv.inner.lcssa.lcssa, ptr @Y
 131   br label %for.end16
 132
 133 for.end16:                                        ; preds = %for.exit
 134   ret void
 135 }
 136
 137 ; Loops with floating point reductions are interchanged with fastmath.
 138 ; REMARK: Interchanged
 139 ; REMARK-NEXT: lcssa_04
 140
 141 define void @lcssa_04() {
 142 entry:
 143   br label %outer.header
 144
 145 outer.header:                                     ; preds = %outer.inc, %entry
 146   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 147   %float.outer = phi float [ 1.000000e+00, %entry ], [ %float.outer.next, %outer.inc ]
 148   br label %for.body3
 149
 150 for.body3:                                        ; preds = %for.body3, %outer.header
 151   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 152   %float.inner = phi float [ %float.inner.next, %for.body3 ], [ %float.outer, %outer.header ]
 153   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %iv.inner, i64 %iv.outer
 154   %vA = load i32, ptr %arrayidx5
 155   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @C, i64 0, i64 %iv.inner, i64 %iv.outer
 156   %vC = load i32, ptr %arrayidx9
 157   %add = add nsw i32 %vA, %vC
 158   %float.inner.next = fadd fast float %float.inner, 1.000000e+00
 159   store i32 %add, ptr %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   %float.outer.next = phi float [ %float.inner.next, %for.body3 ]
 166   %iv.outer.next = add nsw i64 %iv.outer, 1
 167   %cmp = icmp eq i64 %iv.outer.next, 100
 168   br i1 %cmp, label %outer.header, label %for.exit
 169
 170 for.exit:                                         ; preds = %outer.inc
 171   %float.outer.lcssa = phi float [ %float.outer.next, %outer.inc ]
 172   store float %float.outer.lcssa, ptr @F
 173   br label %for.end16
 174
 175 for.end16:                                        ; preds = %for.exit
 176   ret void
 177 }
 178
 179 ; PHI node in inner latch with multiple predecessors.
 180 ; REMARK: Interchanged
 181 ; REMARK-NEXT: lcssa_05
 182
 183 define void @lcssa_05(ptr %ptr) {
 184 entry:
 185   br label %outer.header
 186
 187 outer.header:                                     ; preds = %outer.inc, %entry
 188   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 189   br label %for.body3
 190
 191 for.body3:                                        ; preds = %bb3, %outer.header
 192   %iv.inner = phi i64 [ %iv.inner.next, %bb3 ], [ 1, %outer.header ]
 193   br i1 undef, label %bb2, label %bb3
 194
 195 bb2:                                              ; preds = %for.body3
 196   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %iv.inner, i64 %iv.outer
 197   %vA = load i32, ptr %arrayidx5
 198   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @C, i64 0, i64 %iv.inner, i64 %iv.outer
 199   %vC = load i32, ptr %arrayidx9
 200   %add = add nsw i32 %vA, %vC
 201   br label %bb3
 202
 203 bb3:                                              ; preds = %bb2, %for.body3
 204   %addp = phi i32 [ %add, %bb2 ], [ 0, %for.body3 ]
 205   store i32 %addp, ptr %ptr
 206   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 207   %exitcond = icmp eq i64 %iv.inner.next, 100
 208   br i1 %exitcond, label %outer.inc, label %for.body3
 209
 210 outer.inc:                                        ; preds = %bb3
 211   %iv.inner.lcssa = phi i64 [ %iv.inner, %bb3 ]
 212   %iv.outer.next = add nsw i64 %iv.outer, 1
 213   %cmp = icmp eq i64 %iv.outer.next, 100
 214   br i1 %cmp, label %outer.header, label %for.exit
 215
 216 for.exit:                                         ; preds = %outer.inc
 217   %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
 218   store i64 %iv.inner.lcssa.lcssa, ptr @Y
 219   br label %for.end16
 220
 221 for.end16:                                        ; preds = %for.exit
 222   ret void
 223 }
 224
 225 ; REMARK: UnsupportedExitPHI
 226 ; REMARK-NEXT: lcssa_06
 227
 228 define void @lcssa_06(ptr %ptr, ptr %ptr1) {
 229 entry:
 230   br label %outer.header
 231
 232 outer.header:                                     ; preds = %outer.inc, %entry
 233   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 234   br i1 undef, label %for.body3, label %outer.inc
 235
 236 for.body3:                                        ; preds = %for.body3, %outer.header
 237   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 238   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %iv.inner, i64 %iv.outer
 239   %vA = load i32, ptr %arrayidx5
 240   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @C, i64 0, i64 %iv.inner, i64 %iv.outer
 241   %vC = load i32, ptr %arrayidx9
 242   %add = add nsw i32 %vA, %vC
 243   store i32 %add, ptr %ptr1
 244   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 245   %exitcond = icmp eq i64 %iv.inner.next, 100
 246   br i1 %exitcond, label %outer.inc, label %for.body3
 247
 248 outer.inc:                                        ; preds = %for.body3, %outer.header
 249   %sv = phi i64 [ 0, %outer.header ], [ 1, %for.body3 ]
 250   %iv.outer.next = add nsw i64 %iv.outer, 1
 251   %cmp = icmp eq i64 %iv.outer.next, 100
 252   br i1 %cmp, label %outer.header, label %for.exit
 253
 254 for.exit:                                         ; preds = %outer.inc
 255   %sv.lcssa = phi i64 [ %sv, %outer.inc ]
 256   store i64 %sv.lcssa, ptr @Y
 257   br label %for.end16
 258
 259 for.end16:                                        ; preds = %for.exit
 260   ret void
 261 }
 262
 263 ; REMARK: Interchanged
 264 ; REMARK-NEXT: lcssa_07
 265 define void @lcssa_07() {
 266 entry:
 267   br label %outer.header
 268
 269 outer.header:                                     ; preds = %outer.inc, %entry
 270   %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
 271   br label %for.body3
 272
 273 for.body3:                                        ; preds = %for.body3, %outer.header
 274   %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
 275   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %iv.inner, i64 %iv.outer
 276   %vA = load i32, ptr %arrayidx5
 277   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @C, i64 0, i64 %iv.inner, i64 %iv.outer
 278   %vC = load i32, ptr %arrayidx9
 279   %add = add nsw i32 %vA, %vC
 280   store i32 %add, ptr %arrayidx5
 281   %iv.inner.next = add nuw nsw i64 %iv.inner, 1
 282   %exitcond = icmp eq i64 %iv.inner.next, 100
 283   br i1 %exitcond, label %outer.bb, label %for.body3
 284
 285 outer.bb:                                         ; preds = %for.body3
 286   %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ]
 287   br label %outer.inc
 288
 289 outer.inc:                                        ; preds = %outer.bb
 290   %iv.outer.next = add nsw i64 %iv.outer, 1
 291   %cmp = icmp eq i64 %iv.outer.next, 100
 292   br i1 %cmp, label %outer.header, label %for.exit
 293
 294 for.exit:                                         ; preds = %outer.inc
 295   %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
 296   store i64 %iv.inner.lcssa.lcssa, ptr @Y
 297   br label %for.end16
 298
 299 for.end16:                                        ; preds = %for.exit
 300   ret void
 301 }
 302
 303 ; Should not crash when the outer header branches to
 304 ; both the inner loop and the outer latch, and there
 305 ; is an lcssa phi node outside the loopnest.
 306 ; REMARK: Interchanged
 307 ; REMARK-NEXT: lcssa_08
 308 define i64 @lcssa_08(ptr %Arr) {
 309 entry:
 310   br label %for1.header
 311
 312 for1.header:                                         ; preds = %for1.inc, %entry
 313   %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
 314   br i1 undef, label %for2, label %for1.inc
 315
 316 for2:                                        ; preds = %for2, %for1.header
 317   %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
 318   %arrayidx = getelementptr inbounds [100 x [100 x i64]], ptr %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
 319   %lv = load i64, ptr %arrayidx, align 4
 320   %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
 321   %exit1 = icmp eq i64 %indvars.iv.next.3, 100
 322   br i1 %exit1, label %for1.inc, label %for2
 323
 324 for1.inc:                                ; preds = %for2, %for1.header
 325   %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
 326   %exit2 = icmp eq i64 %indvars.iv.next24, 100
 327   br i1 %exit2, label %for1.loopexit, label %for1.header
 328
 329 for1.loopexit:                                 ; preds = %for1.inc
 330   %sum.outer.lcssa = phi i64 [ %indvars.iv23, %for1.inc ]
 331   ret i64 %sum.outer.lcssa
 332 }
 333