test/Transforms/LoopInterchange/reductions.ll

   1 ; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
   2
   3 @A = common global [500 x [500 x i32]] zeroinitializer
   4 @X = common global i32 0
   5 @B = common global [500 x [500 x i32]] zeroinitializer
   6 @Y = common global i32 0
   7
   8 ;;  for( int i=1;i<N;i++)
   9 ;;    for( int j=1;j<N;j++)
  10 ;;      X+=A[j][i];
  11
  12 define void @reduction_01(i32 %N) {
  13 entry:
  14   %cmp16 = icmp sgt i32 %N, 1
  15   br i1 %cmp16, label %for.body3.lr.ph, label %for.end8
  16
  17 for.body3.lr.ph:                                  ; preds = %entry, %for.cond1.for.inc6_crit_edge
  18   %indvars.iv18 = phi i64 [ %indvars.iv.next19, %for.cond1.for.inc6_crit_edge ], [ 1, %entry ]
  19   %X.promoted = load i32, i32* @X
  20   br label %for.body3
  21
  22 for.body3:                                        ; preds = %for.body3, %for.body3.lr.ph
  23   %indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]
  24   %add15 = phi i32 [ %X.promoted, %for.body3.lr.ph ], [ %add, %for.body3 ]
  25   %arrayidx5 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv18
  26   %0 = load i32, i32* %arrayidx5
  27   %add = add nsw i32 %add15, %0
  28   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  29   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
  30   %exitcond = icmp eq i32 %lftr.wideiv, %N
  31   br i1 %exitcond, label %for.cond1.for.inc6_crit_edge, label %for.body3
  32
  33 for.cond1.for.inc6_crit_edge:                     ; preds = %for.body3
  34   store i32 %add, i32* @X
  35   %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
  36   %lftr.wideiv20 = trunc i64 %indvars.iv.next19 to i32
  37   %exitcond21 = icmp eq i32 %lftr.wideiv20, %N
  38   br i1 %exitcond21, label %for.end8, label %for.body3.lr.ph
  39
  40 for.end8:                                         ; preds = %for.cond1.for.inc6_crit_edge, %entry
  41   ret void
  42 }
  43
  44 ;; Loop is interchanged check that the phi nodes are split and the promoted value is used instead of the reduction phi.
  45 ; CHECK-LABEL: @reduction_01
  46 ; CHECK:  for.body3:                                        ; preds = %for.body3.preheader, %for.body3.split
  47 ; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3.split ], [ 1, %for.body3.preheader ]
  48 ; CHECK:    br label %for.body3.lr.ph.preheader
  49 ; CHECK:    %add = add nsw i32 %X.promoted
  50
  51
  52 ;; Test for more than 1 reductions inside a loop.
  53 ;;  for( int i=1;i<N;i++)
  54 ;;    for( int j=1;j<N;j++)
  55 ;;      for( int k=1;k<N;k++) {
  56 ;;        X+=A[k][j];
  57 ;;        Y+=B[k][i];
  58 ;;      }
  59
  60 define void @reduction_02(i32 %N)  {
  61 entry:
  62   %cmp34 = icmp sgt i32 %N, 1
  63   br i1 %cmp34, label %for.cond4.preheader.preheader, label %for.end19
  64
  65 for.cond4.preheader.preheader:                    ; preds = %entry, %for.inc17
  66   %indvars.iv40 = phi i64 [ %indvars.iv.next41, %for.inc17 ], [ 1, %entry ]
  67   br label %for.body6.lr.ph
  68
  69 for.body6.lr.ph:                                  ; preds = %for.cond4.for.inc14_crit_edge, %for.cond4.preheader.preheader
  70   %indvars.iv36 = phi i64 [ %indvars.iv.next37, %for.cond4.for.inc14_crit_edge ], [ 1, %for.cond4.preheader.preheader ]
  71   %X.promoted = load i32, i32* @X
  72   %Y.promoted = load i32, i32* @Y
  73   br label %for.body6
  74
  75 for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
  76   %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
  77   %add1331 = phi i32 [ %Y.promoted, %for.body6.lr.ph ], [ %add13, %for.body6 ]
  78   %add30 = phi i32 [ %X.promoted, %for.body6.lr.ph ], [ %add, %for.body6 ]
  79   %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv36
  80   %0 = load i32, i32* %arrayidx8
  81   %add = add nsw i32 %add30, %0
  82   %arrayidx12 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @B, i64 0, i64 %indvars.iv, i64 %indvars.iv40
  83   %1 = load i32, i32* %arrayidx12
  84   %add13 = add nsw i32 %add1331, %1
  85   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  86   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
  87   %exitcond = icmp eq i32 %lftr.wideiv, %N
  88   br i1 %exitcond, label %for.cond4.for.inc14_crit_edge, label %for.body6
  89
  90 for.cond4.for.inc14_crit_edge:                    ; preds = %for.body6
  91   store i32 %add, i32* @X
  92   store i32 %add13, i32* @Y
  93   %indvars.iv.next37 = add nuw nsw i64 %indvars.iv36, 1
  94   %lftr.wideiv38 = trunc i64 %indvars.iv.next37 to i32
  95   %exitcond39 = icmp eq i32 %lftr.wideiv38, %N
  96   br i1 %exitcond39, label %for.inc17, label %for.body6.lr.ph
  97
  98 for.inc17:                                        ; preds = %for.cond4.for.inc14_crit_edge
  99   %indvars.iv.next41 = add nuw nsw i64 %indvars.iv40, 1
 100   %lftr.wideiv42 = trunc i64 %indvars.iv.next41 to i32
 101   %exitcond43 = icmp eq i32 %lftr.wideiv42, %N
 102   br i1 %exitcond43, label %for.end19, label %for.cond4.preheader.preheader
 103
 104 for.end19:                                        ; preds = %for.inc17, %entry
 105   ret void
 106 }
 107
 108 ;; Loop is interchanged check that the phi nodes are split and the promoted value is used instead of the reduction phi.
 109 ; CHECK-LABEL: @reduction_02
 110 ; CHECK:  for.body6:                                        ; preds = %for.body6.preheader, %for.body6.split
 111 ; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body6.split ], [ 1, %for.body6.preheader ]
 112 ; CHECK:    br label %for.cond4.preheader.preheader.preheader
 113 ; CHECK:    %add13 = add nsw i32 %Y.promoted
 114
 115
 116 ;; Not tightly nested. Do not interchange.
 117 ;;  for( int i=1;i<N;i++)
 118 ;;    for( int j=1;j<N;j++) {
 119 ;;      for( int k=1;k<N;k++) {
 120 ;;        X+=A[k][j];
 121 ;;      }
 122 ;;      Y+=B[j][i];
 123 ;;    }
 124 define void @reduction_03(i32 %N)  {
 125 entry:
 126   %cmp35 = icmp sgt i32 %N, 1
 127   br i1 %cmp35, label %for.cond4.preheader.lr.ph, label %for.end19
 128
 129 for.cond4.preheader.lr.ph:                        ; preds = %entry, %for.cond1.for.inc17_crit_edge
 130   %indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ]
 131   %Y.promoted = load i32, i32* @Y
 132   br label %for.body6.lr.ph
 133
 134 for.body6.lr.ph:                                  ; preds = %for.cond4.preheader.lr.ph, %for.cond4.for.end_crit_edge
 135   %indvars.iv37 = phi i64 [ 1, %for.cond4.preheader.lr.ph ], [ %indvars.iv.next38, %for.cond4.for.end_crit_edge ]
 136   %add1334 = phi i32 [ %Y.promoted, %for.cond4.preheader.lr.ph ], [ %add13, %for.cond4.for.end_crit_edge ]
 137   %X.promoted = load i32, i32* @X
 138   br label %for.body6
 139
 140 for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
 141   %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
 142   %add31 = phi i32 [ %X.promoted, %for.body6.lr.ph ], [ %add, %for.body6 ]
 143   %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv37
 144   %0 = load i32, i32* %arrayidx8
 145   %add = add nsw i32 %add31, %0
 146   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 147   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 148   %exitcond = icmp eq i32 %lftr.wideiv, %N
 149   br i1 %exitcond, label %for.cond4.for.end_crit_edge, label %for.body6
 150
 151 for.cond4.for.end_crit_edge:                      ; preds = %for.body6
 152   store i32 %add, i32* @X
 153   %arrayidx12 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @B, i64 0, i64 %indvars.iv37, i64 %indvars.iv41
 154   %1 = load i32, i32* %arrayidx12
 155   %add13 = add nsw i32 %add1334, %1
 156   %indvars.iv.next38 = add nuw nsw i64 %indvars.iv37, 1
 157   %lftr.wideiv39 = trunc i64 %indvars.iv.next38 to i32
 158   %exitcond40 = icmp eq i32 %lftr.wideiv39, %N
 159   br i1 %exitcond40, label %for.cond1.for.inc17_crit_edge, label %for.body6.lr.ph
 160
 161 for.cond1.for.inc17_crit_edge:                    ; preds = %for.cond4.for.end_crit_edge
 162   store i32 %add13, i32* @Y
 163   %indvars.iv.next42 = add nuw nsw i64 %indvars.iv41, 1
 164   %lftr.wideiv43 = trunc i64 %indvars.iv.next42 to i32
 165   %exitcond44 = icmp eq i32 %lftr.wideiv43, %N
 166   br i1 %exitcond44, label %for.end19, label %for.cond4.preheader.lr.ph
 167
 168 for.end19:                                        ; preds = %for.cond1.for.inc17_crit_edge, %entry
 169   ret void
 170 }
 171 ;; Not tightly nested. Do not interchange.
 172 ;; Not interchanged hence the phi's in the inner loop will not be split. Check for the same.
 173 ; CHECK-LABEL: @reduction_03
 174 ; CHECK:  for.body6:                                        ; preds = %for.body6.preheader, %for.body6
 175 ; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body6 ], [ 1, %for.body6.preheader ]
 176 ; CHECK:    %add31 = phi i32 [ %add, %for.body6 ], [ %X.promoted, %for.body6.preheader ]
 177
 178
 179
 180 ;; Multiple use of reduction not safe. Do not interchange.
 181 ;;  for( int i=1;i<N;i++)
 182 ;;    for( int j=1;j<N;j++)
 183 ;;      for( int k=1;k<N;k++) {
 184 ;;        X+=A[k][j];
 185 ;;        Y+=X;
 186 ;;      }
 187 define void @reduction_04(i32 %N) {
 188 entry:
 189   %cmp28 = icmp sgt i32 %N, 1
 190   br i1 %cmp28, label %for.cond4.preheader.preheader, label %for.end15
 191
 192 for.cond4.preheader.preheader:                    ; preds = %entry, %for.inc13
 193   %i.029 = phi i32 [ %inc14, %for.inc13 ], [ 1, %entry ]
 194   br label %for.body6.lr.ph
 195
 196 for.body6.lr.ph:                                  ; preds = %for.cond4.for.inc10_crit_edge, %for.cond4.preheader.preheader
 197   %indvars.iv30 = phi i64 [ %indvars.iv.next31, %for.cond4.for.inc10_crit_edge ], [ 1, %for.cond4.preheader.preheader ]
 198   %X.promoted = load i32, i32* @X
 199   %Y.promoted = load i32, i32* @Y
 200   br label %for.body6
 201
 202 for.body6:                                        ; preds = %for.body6, %for.body6.lr.ph
 203   %indvars.iv = phi i64 [ 1, %for.body6.lr.ph ], [ %indvars.iv.next, %for.body6 ]
 204   %add925 = phi i32 [ %Y.promoted, %for.body6.lr.ph ], [ %add9, %for.body6 ]
 205   %add24 = phi i32 [ %X.promoted, %for.body6.lr.ph ], [ %add, %for.body6 ]
 206   %arrayidx8 = getelementptr inbounds [500 x [500 x i32]], [500 x [500 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv30
 207   %0 = load i32, i32* %arrayidx8
 208   %add = add nsw i32 %add24, %0
 209   %add9 = add nsw i32 %add925, %add
 210   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 211   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 212   %exitcond = icmp eq i32 %lftr.wideiv, %N
 213   br i1 %exitcond, label %for.cond4.for.inc10_crit_edge, label %for.body6
 214
 215 for.cond4.for.inc10_crit_edge:                    ; preds = %for.body6
 216   store i32 %add, i32* @X
 217   store i32 %add9, i32* @Y
 218   %indvars.iv.next31 = add nuw nsw i64 %indvars.iv30, 1
 219   %lftr.wideiv32 = trunc i64 %indvars.iv.next31 to i32
 220   %exitcond33 = icmp eq i32 %lftr.wideiv32, %N
 221   br i1 %exitcond33, label %for.inc13, label %for.body6.lr.ph
 222
 223 for.inc13:                                        ; preds = %for.cond4.for.inc10_crit_edge
 224   %inc14 = add nuw nsw i32 %i.029, 1
 225   %exitcond34 = icmp eq i32 %inc14, %N
 226   br i1 %exitcond34, label %for.end15, label %for.cond4.preheader.preheader
 227
 228 for.end15:                                        ; preds = %for.inc13, %entry
 229   ret void
 230 }
 231 ;; Not interchanged hence the phi's in the inner loop will not be split. Check for the same.
 232 ; CHECK-LABEL: @reduction_04
 233 ; CHECK:  for.body6:                                        ; preds = %for.body6.preheader, %for.body6
 234 ; CHECK:    %indvars.iv = phi i64 [ %indvars.iv.next, %for.body6 ], [ 1, %for.body6.preheader ]
 235 ; CHECK:    %add925 = phi i32 [ %add9, %for.body6 ], [ %Y.promoted, %for.body6.preheader ]