llvm/test/Transforms/LoopInterchange/profitability.ll

   1 ; Remove 'S' Scalar Dependencies #119345
   2 ; Scalar dependencies are not handled correctly, so they were removed to avoid
   3 ; miscompiles. The loop nest in this test case used to be interchanged, but it's
   4 ; no longer triggering. XFAIL'ing this test to indicate that this test should
   5 ; interchanged if scalar deps are handled correctly.
   6 ;
   7 ; XFAIL: *
   8
   9 ; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -pass-remarks-output=%t -verify-dom-info -verify-loop-info \
  10 ; RUN:     -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange
  11 ; RUN: FileCheck -input-file %t %s
  12
  13 ; RUN: opt < %s -passes=loop-interchange,loop-interchange -cache-line-size=64 \
  14 ; RUN:     -pass-remarks-output=%t -pass-remarks='loop-interchange' -S
  15 ; RUN: cat %t |  FileCheck --check-prefix=PROFIT %s
  16
  17 ;; We test profitability model in these test cases.
  18
  19 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
  20
  21 @A = common global [100 x [100 x i32]] zeroinitializer
  22 @B = common global [100 x [100 x i32]] zeroinitializer
  23
  24 ;;---------------------------------------Test case 01---------------------------------
  25 ;; Loops interchange will result in better cache locality and hence profitable. Check for interchange.
  26 ;;   for(int i=1;i<100;i++)
  27 ;;     for(int j=1;j<100;j++)
  28 ;;       A[j][i] = A[j - 1][i] + B[j][i];
  29
  30 ; CHECK:      Name:            Interchanged
  31 ; CHECK-NEXT: Function:        interchange_01
  32
  33 define void @interchange_01() {
  34 entry:
  35   br label %for2.preheader
  36
  37 for2.preheader:
  38   %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]
  39   br label %for2
  40
  41 for2:
  42   %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]
  43   %j.prev = add nsw i64 %j,  -1
  44   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j.prev, i64 %i30
  45   %lv1 = load i32, ptr %arrayidx5
  46   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %j,  i64 %i30
  47   %lv2 = load i32, ptr %arrayidx9
  48   %add = add nsw i32 %lv1, %lv2
  49   %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j,  i64 %i30
  50   store i32 %add, ptr %arrayidx13
  51   %i.next = add nuw nsw i64 %j,  1
  52   %exitcond = icmp eq i64 %j,  99
  53   br i1 %exitcond, label %for1.inc14, label %for2
  54
  55 for1.inc14:
  56   %i.next31 = add nuw nsw i64 %i30, 1
  57   %exitcond33 = icmp eq i64 %i30, 99
  58   br i1 %exitcond33, label %for.end16, label %for2.preheader
  59
  60 for.end16:
  61   ret void
  62 }
  63
  64 ;; ---------------------------------------Test case 02---------------------------------
  65 ;; Check loop interchange profitability model.
  66 ;; This tests profitability model when operands of getelementpointer and not exactly the induction variable but some
  67 ;; arithmetic operation on them.
  68 ;;   for(int i=1;i<N;i++)
  69 ;;    for(int j=1;j<N;j++)
  70 ;;       A[j-1][i-1] = A[j - 1][i-1] + B[j-1][i-1];
  71
  72 ; CHECK:      Name:            Interchanged
  73 ; CHECK-NEXT: Function:        interchange_02
  74 define void @interchange_02() {
  75 entry:
  76   br label %for1.header
  77
  78 for1.header:
  79   %i35 = phi i64 [ 1, %entry ], [ %i.next36, %for1.inc19 ]
  80   %i.prev = add nsw i64 %i35, -1
  81   br label %for2
  82
  83 for2:
  84   %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
  85   %j.prev = add nsw i64 %j,  -1
  86   %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j.prev, i64 %i.prev
  87   %lv1 = load i32, ptr %arrayidx6
  88   %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %j.prev, i64 %i.prev
  89   %lv2 = load i32, ptr %arrayidx12
  90   %add = add nsw i32 %lv1, %lv2
  91   store i32 %add, ptr %arrayidx6
  92   %i.next = add nuw nsw i64 %j,  1
  93   %exitcond = icmp eq i64 %j,  99
  94   br i1 %exitcond, label %for1.inc19, label %for2
  95
  96 for1.inc19:
  97   %i.next36 = add nuw nsw i64 %i35, 1
  98   %exitcond39 = icmp eq i64 %i35, 99
  99   br i1 %exitcond39, label %for.end21, label %for1.header
 100
 101 for.end21:
 102   ret void
 103 }
 104
 105 ;;---------------------------------------Test case 03---------------------------------
 106 ;; Loops interchange is not profitable.
 107 ;;   for(int i=1;i<100;i++)
 108 ;;     for(int j=1;j<100;j++)
 109 ;;       A[i-1][j-1] = A[i - 1][j-1] + B[i][j];
 110
 111 ; CHECK:      Name:            InterchangeNotProfitable
 112 ; CHECK-NEXT: Function:        interchange_03
 113 define void @interchange_03(){
 114 entry:
 115   br label %for1.header
 116
 117 for1.header:
 118   %i34 = phi i64 [ 1, %entry ], [ %i.next35, %for1.inc17 ]
 119   %i.prev = add nsw i64 %i34, -1
 120   br label %for2
 121
 122 for2:
 123   %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
 124   %j.prev = add nsw i64 %j, -1
 125   %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %i.prev, i64 %j.prev
 126   %lv1 = load i32, ptr %arrayidx6
 127   %arrayidx10 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %i34, i64 %j
 128   %lv2 = load i32, ptr %arrayidx10
 129   %add = add nsw i32 %lv1, %lv2
 130   store i32 %add, ptr %arrayidx6
 131   %i.next = add nuw nsw i64 %j,  1
 132   %exitcond = icmp eq i64 %j,  99
 133   br i1 %exitcond, label %for1.inc17, label %for2
 134
 135 for1.inc17:
 136   %i.next35 = add nuw nsw i64 %i34, 1
 137   %exitcond38 = icmp eq i64 %i34, 99
 138   br i1 %exitcond38, label %for.end19, label %for1.header
 139
 140 for.end19:
 141   ret void
 142 }
 143
 144 ;; Loops should not be interchanged in this case as it is not profitable.
 145 ;;  for(int i=0;i<100;i++)
 146 ;;    for(int j=0;j<100;j++)
 147 ;;      A[i][j] = A[i][j]+k;
 148
 149 ; CHECK:      Name:            InterchangeNotProfitable
 150 ; CHECK-NEXT: Function:        interchange_04
 151 define void @interchange_04(i32 %k) {
 152 entry:
 153   br label %for.cond1.preheader
 154
 155 for.cond1.preheader:
 156   %indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ]
 157   br label %for.body3
 158
 159 for.body3:
 160   %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]
 161   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv
 162   %0 = load i32, ptr %arrayidx5
 163   %add = add nsw i32 %0, %k
 164   store i32 %add, ptr %arrayidx5
 165   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 166   %exitcond = icmp eq i64 %indvars.iv.next, 100
 167   br i1 %exitcond, label %for.inc10, label %for.body3
 168
 169 for.inc10:
 170   %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
 171   %exitcond23 = icmp eq i64 %indvars.iv.next22, 100
 172   br i1 %exitcond23, label %for.end12, label %for.cond1.preheader
 173
 174 for.end12:
 175   ret void
 176 }
 177
 178 ;;---------------------------------------Test case 05---------------------------------
 179 ;; This test is to make sure, that multiple invocations of loop interchange will not
 180 ;; undo previous interchange and will converge to a particular order determined by the
 181 ;; profitability analysis.
 182 ;;   for(int i=1;i<100;i++)
 183 ;;     for(int j=1;j<100;j++)
 184 ;;       A[j][0] = A[j][0] + B[j][i];
 185
 186 ; CHECK:      Name:            Interchanged
 187 ; CHECK-NEXT: Function:        interchange_05
 188
 189 ; PROFIT-LABEL: --- !Passed
 190 ; PROFIT-NEXT: Pass:            loop-interchange
 191 ; PROFIT-NEXT: Name:            Interchanged
 192 ; PROFIT-LABEL: Function:        interchange_05
 193 ; PROFIT-NEXT: Args:
 194 ; PROFIT-NEXT:   - String:          Loop interchanged with enclosing loop.
 195 ; PROFIT-NEXT: ...
 196 ; PROFIT: --- !Missed
 197 ; PROFIT-NEXT: Pass:            loop-interchange
 198 ; PROFIT-NEXT: Name:            InterchangeNotProfitable
 199 ; PROFIT-NEXT: Function:        interchange_05
 200 ; PROFIT-NEXT: Args:
 201 ; PROFIT-NEXT:   - String:          Interchanging loops is not considered to improve cache locality nor vectorization.
 202 ; PROFIT-NEXT: ...
 203 define void @interchange_05() {
 204 entry:
 205   br label %for2.preheader
 206
 207 for2.preheader:
 208   %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]
 209   br label %for2
 210
 211 for2:
 212   %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]
 213   %j.prev = add nsw i64 %j,  -1
 214   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 0
 215   %lv1 = load i32, ptr %arrayidx5
 216   %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %j,  i64 %i30
 217   %lv2 = load i32, ptr %arrayidx9
 218   %add = add nsw i32 %lv1, %lv2
 219   %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j,  i64 0
 220   store i32 %add, ptr %arrayidx13
 221   %i.next = add nuw nsw i64 %j,  1
 222   %exitcond = icmp eq i64 %j,  99
 223   br i1 %exitcond, label %for1.inc14, label %for2
 224
 225 for1.inc14:
 226   %i.next31 = add nuw nsw i64 %i30, 1
 227   %exitcond33 = icmp eq i64 %i30, 99
 228   br i1 %exitcond33, label %for.end16, label %for2.preheader
 229
 230 for.end16:
 231   ret void
 232 }
 233