| 1 |
; Test optimization remarks generated by the LoopInterchange pass. |
| 2 |
; |
| 3 |
; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info \ |
| 4 |
; RUN: -pass-remarks-output=%t -pass-remarks-missed='loop-interchange' \ |
| 5 |
; RUN: -pass-remarks='loop-interchange' -S |
| 6 |
; RUN: cat %t | FileCheck %s |
| 7 |
|
| 8 |
; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info \ |
| 9 |
; RUN: -pass-remarks-output=%t -pass-remarks-missed='loop-interchange' \ |
| 10 |
; RUN: -pass-remarks='loop-interchange' -S -da-disable-delinearization-checks |
| 11 |
; RUN: cat %t | FileCheck --check-prefix=DELIN %s |
| 12 |
|
| 13 |
@A = common global [100 x [100 x i32]] zeroinitializer |
| 14 |
@B = common global [100 x [100 x i32]] zeroinitializer |
| 15 |
@C = common global [100 x i32] zeroinitializer |
| 16 |
|
| 17 |
;;---------------------------------------Test case 01--------------------------------- |
| 18 |
;; Loops interchange is not profitable. |
| 19 |
;; for(int i=1;i<N;i++) |
| 20 |
;; for(int j=1;j<N;j++) |
| 21 |
;; A[i-1][j-1] = A[i - 1][j-1] + B[i][j]; |
| 22 |
|
| 23 |
define void @test01(i32 %N){ |
| 24 |
entry: |
| 25 |
%cmp31 = icmp sgt i32 %N, 1 |
| 26 |
br i1 %cmp31, label %for.cond1.preheader.lr.ph, label %for.end19 |
| 27 |
|
| 28 |
for.cond1.preheader.lr.ph: |
| 29 |
%0 = add i32 %N, -1 |
| 30 |
br label %for.body3.lr.ph |
| 31 |
|
| 32 |
for.body3.lr.ph: |
| 33 |
%indvars.iv34 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next35, %for.inc17 ] |
| 34 |
%1 = add nsw i64 %indvars.iv34, -1 |
| 35 |
br label %for.body3 |
| 36 |
|
| 37 |
for.body3: |
| 38 |
%indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ] |
| 39 |
%2 = add nsw i64 %indvars.iv, -1 |
| 40 |
%arrayidx6 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %1, i64 %2 |
| 41 |
%3 = load i32, ptr %arrayidx6 |
| 42 |
%arrayidx10 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %indvars.iv34, i64 %indvars.iv |
| 43 |
%4 = load i32, ptr %arrayidx10 |
| 44 |
%add = add nsw i32 %4, %3 |
| 45 |
store i32 %add, ptr %arrayidx6 |
| 46 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 47 |
%lftr.wideiv = trunc i64 %indvars.iv to i32 |
| 48 |
%exitcond = icmp eq i32 %lftr.wideiv, %0 |
| 49 |
br i1 %exitcond, label %for.inc17, label %for.body3 |
| 50 |
|
| 51 |
for.inc17: |
| 52 |
%indvars.iv.next35 = add nuw nsw i64 %indvars.iv34, 1 |
| 53 |
%lftr.wideiv37 = trunc i64 %indvars.iv34 to i32 |
| 54 |
%exitcond38 = icmp eq i32 %lftr.wideiv37, %0 |
| 55 |
br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph |
| 56 |
|
| 57 |
for.end19: |
| 58 |
ret void |
| 59 |
} |
| 60 |
|
| 61 |
; CHECK: --- !Analysis |
| 62 |
; CHECK-NEXT: Pass: loop-interchange |
| 63 |
; CHECK-NEXT: Name: Dependence |
| 64 |
; CHECK-NEXT: Function: test01 |
| 65 |
; CHECK-NEXT: Args: |
| 66 |
; CHECK-NEXT: - String: Computed dependence info, invoking the transform. |
| 67 |
; CHECK-NEXT: ... |
| 68 |
|
| 69 |
; CHECK: --- !Missed |
| 70 |
; CHECK-NEXT: Pass: loop-interchange |
| 71 |
; CHECK-NEXT: Name: Dependence |
| 72 |
; CHECK-NEXT: Function: test01 |
| 73 |
; CHECK-NEXT: Args: |
| 74 |
; CHECK-NEXT: - String: All loops have dependencies in all directions. |
| 75 |
; CHECK-NEXT: ... |
| 76 |
|
| 77 |
; DELIN: --- !Analysis |
| 78 |
; DELIN-NEXT: Pass: loop-interchange |
| 79 |
; DELIN-NEXT: Name: Dependence |
| 80 |
; DELIN-NEXT: Function: test01 |
| 81 |
; DELIN-NEXT: Args: |
| 82 |
; DELIN-NEXT: - String: Computed dependence info, invoking the transform. |
| 83 |
; DELIN-NEXT: ... |
| 84 |
|
| 85 |
; DELIN: --- !Missed |
| 86 |
; DELIN-NEXT: Pass: loop-interchange |
| 87 |
; DELIN-NEXT: Name: InterchangeNotProfitable |
| 88 |
; DELIN-NEXT: Function: test01 |
| 89 |
; DELIN-NEXT: Args: |
| 90 |
; DELIN-NEXT: - String: Interchanging loops is not considered to improve cache locality nor vectorization. |
| 91 |
; DELIN-NEXT: ... |
| 92 |
|
| 93 |
;;--------------------------------------Test case 02------------------------------------ |
| 94 |
;; [FIXME] This loop though valid is currently not interchanged due to the |
| 95 |
;; limitation that we cannot split the inner loop latch due to multiple use of inner induction |
| 96 |
;; variable.(used to increment the loop counter and to access A[j+1][i+1] |
| 97 |
;; for(int i=0;i<N-1;i++) |
| 98 |
;; for(int j=1;j<N-1;j++) |
| 99 |
;; A[j+1][i+1] = A[j+1][i+1] + k; |
| 100 |
|
| 101 |
define void @test02(i32 %k, i32 %N) { |
| 102 |
entry: |
| 103 |
%sub = add nsw i32 %N, -1 |
| 104 |
%cmp26 = icmp sgt i32 %N, 1 |
| 105 |
br i1 %cmp26, label %for.cond1.preheader.lr.ph, label %for.end17 |
| 106 |
|
| 107 |
for.cond1.preheader.lr.ph: |
| 108 |
%cmp324 = icmp sgt i32 %sub, 1 |
| 109 |
%0 = add i32 %N, -2 |
| 110 |
%1 = sext i32 %sub to i64 |
| 111 |
br label %for.cond1.preheader |
| 112 |
|
| 113 |
for.cond.loopexit: |
| 114 |
%cmp = icmp slt i64 %indvars.iv.next29, %1 |
| 115 |
br i1 %cmp, label %for.cond1.preheader, label %for.end17 |
| 116 |
|
| 117 |
for.cond1.preheader: |
| 118 |
%indvars.iv28 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next29, %for.cond.loopexit ] |
| 119 |
%indvars.iv.next29 = add nuw nsw i64 %indvars.iv28, 1 |
| 120 |
br i1 %cmp324, label %for.body4, label %for.cond.loopexit |
| 121 |
|
| 122 |
for.body4: |
| 123 |
%indvars.iv = phi i64 [ %indvars.iv.next, %for.body4 ], [ 1, %for.cond1.preheader ] |
| 124 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 125 |
%arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv.next, i64 %indvars.iv.next29 |
| 126 |
%2 = load i32, ptr %arrayidx7 |
| 127 |
%add8 = add nsw i32 %2, %k |
| 128 |
store i32 %add8, ptr %arrayidx7 |
| 129 |
%lftr.wideiv = trunc i64 %indvars.iv to i32 |
| 130 |
%exitcond = icmp eq i32 %lftr.wideiv, %0 |
| 131 |
br i1 %exitcond, label %for.cond.loopexit, label %for.body4 |
| 132 |
|
| 133 |
for.end17: |
| 134 |
ret void |
| 135 |
} |
| 136 |
|
| 137 |
; CHECK: --- !Analysis |
| 138 |
; CHECK-NEXT: Pass: loop-interchange |
| 139 |
; CHECK-NEXT: Name: Dependence |
| 140 |
; CHECK-NEXT: Function: test02 |
| 141 |
; CHECK-NEXT: Args: |
| 142 |
; CHECK-NEXT: - String: Computed dependence info, invoking the transform. |
| 143 |
; CHECK-NEXT: ... |
| 144 |
|
| 145 |
; CHECK: --- !Missed |
| 146 |
; CHECK-NEXT: Pass: loop-interchange |
| 147 |
; CHECK-NEXT: Name: Dependence |
| 148 |
; CHECK-NEXT: Function: test02 |
| 149 |
; CHECK-NEXT: Args: |
| 150 |
; CHECK-NEXT: - String: All loops have dependencies in all directions. |
| 151 |
; CHECK-NEXT: ... |
| 152 |
|
| 153 |
; DELIN: --- !Analysis |
| 154 |
; DELIN-NEXT: Pass: loop-interchange |
| 155 |
; DELIN-NEXT: Name: Dependence |
| 156 |
; DELIN-NEXT: Function: test02 |
| 157 |
; DELIN-NEXT: Args: |
| 158 |
; DELIN-NEXT: - String: Computed dependence info, invoking the transform. |
| 159 |
; DELIN-NEXT: ... |
| 160 |
|
| 161 |
; DELIN: --- !Passed |
| 162 |
; DELIN-NEXT: Pass: loop-interchange |
| 163 |
; DELIN-NEXT: Name: Interchanged |
| 164 |
; DELIN-NEXT: Function: test02 |
| 165 |
; DELIN-NEXT: Args: |
| 166 |
; DELIN-NEXT: - String: Loop interchanged with enclosing loop. |
| 167 |
; DELIN-NEXT: ... |
| 168 |
|
| 169 |
;;-----------------------------------Test case 03------------------------------- |
| 170 |
;; Test to make sure we can handle output dependencies. |
| 171 |
;; |
| 172 |
;; for (int i = 0; i < 2; ++i) |
| 173 |
;; for(int j = 0; j < 3; ++j) { |
| 174 |
;; A[j][i] = i; |
| 175 |
;; A[j][i+1] = j; |
| 176 |
;; } |
| 177 |
|
| 178 |
@A10 = local_unnamed_addr global [3 x [3 x i32]] zeroinitializer, align 16 |
| 179 |
|
| 180 |
define void @test03() { |
| 181 |
entry: |
| 182 |
br label %for.cond1.preheader |
| 183 |
|
| 184 |
for.cond.loopexit: ; preds = %for.body4 |
| 185 |
%exitcond28 = icmp ne i64 %indvars.iv.next27, 2 |
| 186 |
br i1 %exitcond28, label %for.cond1.preheader, label %for.cond.cleanup |
| 187 |
|
| 188 |
for.cond1.preheader: ; preds = %for.cond.loopexit, %entry |
| 189 |
%indvars.iv26 = phi i64 [ 0, %entry ], [ %indvars.iv.next27, %for.cond.loopexit ] |
| 190 |
%indvars.iv.next27 = add nuw nsw i64 %indvars.iv26, 1 |
| 191 |
br label %for.body4 |
| 192 |
|
| 193 |
for.cond.cleanup: ; preds = %for.cond.loopexit |
| 194 |
ret void |
| 195 |
|
| 196 |
for.body4: ; preds = %for.body4, %for.cond1.preheader |
| 197 |
%indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ] |
| 198 |
%arrayidx6 = getelementptr inbounds [3 x [3 x i32]], ptr @A10, i64 0, i64 %indvars.iv, i64 %indvars.iv26 |
| 199 |
%tmp = trunc i64 %indvars.iv26 to i32 |
| 200 |
store i32 %tmp, ptr %arrayidx6, align 4 |
| 201 |
%arrayidx10 = getelementptr inbounds [3 x [3 x i32]], ptr @A10, i64 0, i64 %indvars.iv, i64 %indvars.iv.next27 |
| 202 |
%tmp1 = trunc i64 %indvars.iv to i32 |
| 203 |
store i32 %tmp1, ptr %arrayidx10, align 4 |
| 204 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 205 |
%exitcond = icmp ne i64 %indvars.iv.next, 3 |
| 206 |
br i1 %exitcond, label %for.body4, label %for.cond.loopexit |
| 207 |
} |
| 208 |
|
| 209 |
; CHECK: --- !Analysis |
| 210 |
; CHECK-NEXT: Pass: loop-interchange |
| 211 |
; CHECK-NEXT: Name: Dependence |
| 212 |
; CHECK-NEXT: Function: test03 |
| 213 |
; CHECK-NEXT: Args: |
| 214 |
; CHECK-NEXT: - String: Computed dependence info, invoking the transform. |
| 215 |
; CHECK-NEXT: ... |
| 216 |
|
| 217 |
; CHECK: --- !Passed |
| 218 |
; CHECK-NEXT: Pass: loop-interchange |
| 219 |
; CHECK-NEXT: Name: Interchanged |
| 220 |
; CHECK-NEXT: Function: test03 |
| 221 |
; CHECK-NEXT: Args: |
| 222 |
; CHECK-NEXT: - String: Loop interchanged with enclosing loop. |
| 223 |
; CHECK-NEXT: ... |
| 224 |
|
| 225 |
; DELIN: --- !Analysis |
| 226 |
; DELIN-NEXT: Pass: loop-interchange |
| 227 |
; DELIN-NEXT: Name: Dependence |
| 228 |
; DELIN-NEXT: Function: test03 |
| 229 |
; DELIN-NEXT: Args: |
| 230 |
; DELIN-NEXT: - String: Computed dependence info, invoking the transform. |
| 231 |
; DELIN-NEXT: ... |
| 232 |
|
| 233 |
; DELIN: --- !Passed |
| 234 |
; DELIN-NEXT: Pass: loop-interchange |
| 235 |
; DELIN-NEXT: Name: Interchanged |
| 236 |
; DELIN-NEXT: Function: test03 |
| 237 |
; DELIN-NEXT: Args: |
| 238 |
; DELIN-NEXT: - String: Loop interchanged with enclosing loop. |
| 239 |
; DELIN-NEXT: ... |
| 240 |
|
| 241 |
;;--------------------------------------Test case 04------------------------------------- |
| 242 |
;; Loops not tightly nested are not interchanged |
| 243 |
;; for(int j=0;j<N;j++) { |
| 244 |
;; B[j] = j+k; |
| 245 |
;; for(int i=0;i<N;i++) |
| 246 |
;; A[j][i] = A[j][i]+B[j]; |
| 247 |
;; } |
| 248 |
|
| 249 |
define void @test04(i32 %k, i32 %N){ |
| 250 |
entry: |
| 251 |
%cmp30 = icmp sgt i32 %N, 0 |
| 252 |
br i1 %cmp30, label %for.body.lr.ph, label %for.end17 |
| 253 |
|
| 254 |
for.body.lr.ph: |
| 255 |
%0 = add i32 %N, -1 |
| 256 |
%1 = zext i32 %k to i64 |
| 257 |
br label %for.body |
| 258 |
|
| 259 |
for.body: |
| 260 |
%indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ] |
| 261 |
%2 = add nsw i64 %indvars.iv32, %1 |
| 262 |
%arrayidx = getelementptr inbounds [100 x i32], ptr @C, i64 0, i64 %indvars.iv32 |
| 263 |
%3 = trunc i64 %2 to i32 |
| 264 |
store i32 %3, ptr %arrayidx |
| 265 |
br label %for.body3 |
| 266 |
|
| 267 |
for.body3: |
| 268 |
%indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ] |
| 269 |
%arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv |
| 270 |
%4 = load i32, ptr %arrayidx7 |
| 271 |
%add10 = add nsw i32 %3, %4 |
| 272 |
store i32 %add10, ptr %arrayidx7 |
| 273 |
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| 274 |
%lftr.wideiv = trunc i64 %indvars.iv to i32 |
| 275 |
%exitcond = icmp eq i32 %lftr.wideiv, %0 |
| 276 |
br i1 %exitcond, label %for.inc15, label %for.body3 |
| 277 |
|
| 278 |
for.inc15: |
| 279 |
%indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1 |
| 280 |
%lftr.wideiv35 = trunc i64 %indvars.iv32 to i32 |
| 281 |
%exitcond36 = icmp eq i32 %lftr.wideiv35, %0 |
| 282 |
br i1 %exitcond36, label %for.end17, label %for.body |
| 283 |
|
| 284 |
for.end17: |
| 285 |
ret void |
| 286 |
} |
| 287 |
|
| 288 |
; CHECK: --- !Missed |
| 289 |
; CHECK-NEXT: Pass: loop-interchange |
| 290 |
; CHECK-NEXT: Name: Dependence |
| 291 |
; CHECK-NEXT: Function: test04 |
| 292 |
; CHECK-NEXT: Args: |
| 293 |
; CHECK-NEXT: - String: All loops have dependencies in all directions. |
| 294 |
; CHECK-NEXT: ... |
| 295 |
|
| 296 |
; DELIN: --- !Missed |
| 297 |
; DELIN-NEXT: Pass: loop-interchange |
| 298 |
; DELIN-NEXT: Name: NotTightlyNested |
| 299 |
; DELIN-NEXT: Function: test04 |
| 300 |
; DELIN-NEXT: Args: |
| 301 |
; DELIN-NEXT: - String: Cannot interchange loops because they are not tightly nested. |
| 302 |
; DELIN-NEXT: ... |