llvm/test/Transforms/LoopInterchange/profitability.ll

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