This is an archive of the discontinued LLVM Phabricator instance.

Differential D45207

[LoopInterchange] Update tests so DA can handle access after D35430.
ClosedPublic

Authored by fhahn on Apr 3 2018, 7:14 AM.

Details

Reviewers
karthikthecool
sebpop
grosser
Commits
rGb79217077dfb: [LoopInterchange] Update tests so DA can handle access after D35430.
rL329081: [LoopInterchange] Update tests so DA can handle access after D35430.
Summary

I have taken the opportunity to simplify some tests slightly and move
parts around.

It also brings back a few IR checks for interchangable loops.

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Apr 3 2018, 7:14 AM
fhahn added a subscriber: llvm-commits.
fhahn mentioned this in D43237: [LoopInterchange] Allow some loops with PHI nodes in the exit block..Apr 3 2018, 7:21 AM
fhahn added a child revision: D45209: [LoopInterchange] Add stats counter for number of interchanged loops..Apr 3 2018, 7:30 AM
sebpop accepted this revision.Apr 3 2018, 8:56 AM

lgtm. Thanks!

This revision is now accepted and ready to land.Apr 3 2018, 8:56 AM
Closed by commit rL329081: [LoopInterchange] Update tests so DA can handle access after D35430. (authored by fhahn). · Explain WhyApr 3 2018, 9:42 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

Diff 140815

llvm/trunk/test/Transforms/LoopInterchange/interchange-not-profitable.ll

; REQUIRES: asserts
; RUN: opt < %s -basicaa -loop-interchange -S -debug 2>&1 | FileCheck %s
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@A = common global [100 x [100 x i32]] zeroinitializer
@B = common global [100 x i32] zeroinitializer
;; Loops should not be interchanged in this case as it is not profitable.
;; for(int i=0;i<100;i++)
;; for(int j=0;j<100;j++)
;; A[i][j] = A[i][j]+k;
; CHECK: Interchanging loops not profitable.
define void @interchange_03(i32 %k) {
entry:
br label %for.cond1.preheader
for.cond1.preheader:
%indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ]
br label %for.body3
for.body3:
%indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]
%arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv
%0 = load i32, i32* %arrayidx5
%add = add nsw i32 %0, %k
store i32 %add, i32* %arrayidx5
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%exitcond = icmp eq i64 %indvars.iv.next, 100
br i1 %exitcond, label %for.inc10, label %for.body3
for.inc10:
%indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
%exitcond23 = icmp eq i64 %indvars.iv.next22, 100
br i1 %exitcond23, label %for.end12, label %for.cond1.preheader
for.end12:
ret void
}

llvm/trunk/test/Transforms/LoopInterchange/interchange-output-dependencies.ll

; REQUIRES: asserts
; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@A = common global [100 x [100 x i32]] zeroinitializer
;; Test to make sure we can handle output dependencies.
;;
;; for (int i = 0; i < 2; ++i)
;; for(int j = 0; j < 3; ++j) {
;; A[j][i] = i;
;; A[j][i+1] = j;
;; }
; CHECK: Not interchanging loops. Cannot prove legality.
@A10 = local_unnamed_addr global [3 x [3 x i32]] zeroinitializer, align 16
define void @interchange_10() {
entry:
br label %for.cond1.preheader
for.cond.loopexit: ; preds = %for.body4
%exitcond28 = icmp ne i64 %indvars.iv.next27, 2
br i1 %exitcond28, label %for.cond1.preheader, label %for.cond.cleanup
for.cond1.preheader: ; preds = %for.cond.loopexit, %entry
%indvars.iv26 = phi i64 [ 0, %entry ], [ %indvars.iv.next27, %for.cond.loopexit ]
%indvars.iv.next27 = add nuw nsw i64 %indvars.iv26, 1
br label %for.body4
for.cond.cleanup: ; preds = %for.cond.loopexit
ret void
for.body4: ; preds = %for.body4, %for.cond1.preheader
%indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
%arrayidx6 = getelementptr inbounds [3 x [3 x i32]], [3 x [3 x i32]]* @A10, i64 0, i64 %indvars.iv, i64 %indvars.iv26
%tmp = trunc i64 %indvars.iv26 to i32
store i32 %tmp, i32* %arrayidx6, align 4
%arrayidx10 = getelementptr inbounds [3 x [3 x i32]], [3 x [3 x i32]]* @A10, i64 0, i64 %indvars.iv, i64 %indvars.iv.next27
%tmp1 = trunc i64 %indvars.iv to i32
store i32 %tmp1, i32* %arrayidx10, align 4
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%exitcond = icmp ne i64 %indvars.iv.next, 3
br i1 %exitcond, label %for.body4, label %for.cond.loopexit
}

llvm/trunk/test/Transforms/LoopInterchange/interchange-simple-count-down.ll

; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -pass-remarks=loop-interchange 2>&1 | FileCheck %s
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@A = common global [100 x [100 x i32]] zeroinitializer
@B = common global [100 x i32] zeroinitializer
;; for(int i=0;i<100;i++)
;; for(int j=100;j>=0;j--)
;; A[j][i] = A[j][i]+k;
; CHECK: Loop interchanged with enclosing loop.
define void @interchange_02(i32 %k) {
entry:
br label %for.cond1.preheader
for.cond1.preheader:
%indvars.iv19 = phi i64 [ 0, %entry ], [ %indvars.iv.next20, %for.inc10 ]
br label %for.body3
for.body3:
%indvars.iv = phi i64 [ 100, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]
%arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv19
%0 = load i32, i32* %arrayidx5
%add = add nsw i32 %0, %k
store i32 %add, i32* %arrayidx5
%indvars.iv.next = add nsw i64 %indvars.iv, -1
%cmp2 = icmp sgt i64 %indvars.iv, 0
br i1 %cmp2, label %for.body3, label %for.inc10
for.inc10:
%indvars.iv.next20 = add nuw nsw i64 %indvars.iv19, 1
%exitcond = icmp eq i64 %indvars.iv.next20, 100
br i1 %exitcond, label %for.end11, label %for.cond1.preheader
for.end11:
ret void
}

llvm/trunk/test/Transforms/LoopInterchange/interchange-simple-count-up.ll

; REQUIRES: asserts
; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@A = common global [100 x [100 x i32]] zeroinitializer
@B = common global [100 x i32] zeroinitializer
;; for(int i=0;i<N;i++)
;; for(int j=1;j<N;j++)
;; A[j][i] = A[j][i]+k;
; CHECK: Not interchanging loops. Cannot prove legality.
define void @interchange_01(i32 %k, i32 %N) {
entry:
%cmp21 = icmp sgt i32 %N, 0
br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end12
for.cond1.preheader.lr.ph:
%cmp219 = icmp sgt i32 %N, 1
%0 = add i32 %N, -1
br label %for.cond1.preheader
for.cond1.preheader:
%indvars.iv23 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next24, %for.inc10 ]
br i1 %cmp219, label %for.body3, label %for.inc10
for.body3:
%indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ]
%arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv23
%1 = load i32, i32* %arrayidx5
%add = add nsw i32 %1, %k
store i32 %add, i32* %arrayidx5
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%lftr.wideiv = trunc i64 %indvars.iv to i32
%exitcond = icmp eq i32 %lftr.wideiv, %0
br i1 %exitcond, label %for.inc10, label %for.body3
for.inc10:
%indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
%lftr.wideiv25 = trunc i64 %indvars.iv23 to i32
%exitcond26 = icmp eq i32 %lftr.wideiv25, %0
br i1 %exitcond26, label %for.end12, label %for.cond1.preheader
for.end12:
ret void
}

llvm/trunk/test/Transforms/LoopInterchange/interchangeable.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
@A = common global [100 x [100 x i64]] zeroinitializer
@B = common global [100 x i64] zeroinitializer
;; for(int i=0;i<100;i++)
;; for(int j=0;j<100;j++)
;; A[j][i] = A[j][i]+k;
define void @interchange_01(i64 %k, i64 %N) {
; CHECK-LABEL: @interchange_01(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[FOR2_PREHEADER:%.*]]
; CHECK: for1.header.preheader:
; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]
; CHECK: for1.header:
; CHECK-NEXT: [[INDVARS_IV23:%.*]] = phi i64 [ [[INDVARS_IV_NEXT24:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]
; CHECK-NEXT: br label [[FOR2_SPLIT1:%.*]]
; CHECK: for2.preheader:
; CHECK-NEXT: br label [[FOR2:%.*]]
; CHECK: for2:
; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR2_SPLIT:%.*]] ], [ 0, [[FOR2_PREHEADER]] ]
; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]
; CHECK: for2.split1:
; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV23]]
; CHECK-NEXT: [[LV:%.*]] = load i64, i64* [[ARRAYIDX5]]
; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[LV]], [[K:%.*]]
; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]]
; CHECK-NEXT: br label [[FOR1_INC10]]
; CHECK: for2.split:
; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 99
; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_END12:%.*]], label [[FOR2]]
; CHECK: for1.inc10:
; CHECK-NEXT: [[INDVARS_IV_NEXT24]] = add nuw nsw i64 [[INDVARS_IV23]], 1
; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[INDVARS_IV23]], 99
; CHECK-NEXT: br i1 [[EXITCOND26]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]]
; CHECK: for.end12:
; CHECK-NEXT: ret void
;
entry:
br label %for1.header
for1.header:
%j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ]
br label %for2
for2:
%j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]
%arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23
%lv = load i64, i64* %arrayidx5
%add = add nsw i64 %lv, %k
store i64 %add, i64* %arrayidx5
%j.next = add nuw nsw i64 %j, 1
%exitcond = icmp eq i64 %j, 99
br i1 %exitcond, label %for1.inc10, label %for2
for1.inc10:
%j.next24 = add nuw nsw i64 %j23, 1
%exitcond26 = icmp eq i64 %j23, 99
br i1 %exitcond26, label %for.end12, label %for1.header
for.end12:
ret void
}
;; for(int i=0;i<100;i++)
;; for(int j=100;j>=0;j--)
;; A[j][i] = A[j][i]+k;
define void @interchange_02(i64 %k) {
; CHECK-LABEL: @interchange_02(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[FOR3_PREHEADER:%.*]]
; CHECK: for1.header.preheader:
; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]
; CHECK: for1.header:
; CHECK-NEXT: [[INDVARS_IV19:%.*]] = phi i64 [ [[INDVARS_IV_NEXT20:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]
; CHECK-NEXT: br label [[FOR3_SPLIT1:%.*]]
; CHECK: for3.preheader:
; CHECK-NEXT: br label [[FOR3:%.*]]
; CHECK: for3:
; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR3_SPLIT:%.*]] ], [ 100, [[FOR3_PREHEADER]] ]
; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]
; CHECK: for3.split1:
; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV19]]
; CHECK-NEXT: [[TMP0:%.*]] = load i64, i64* [[ARRAYIDX5]]
; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[TMP0]], [[K:%.*]]
; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]]
; CHECK-NEXT: br label [[FOR1_INC10]]
; CHECK: for3.split:
; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i64 [[INDVARS_IV]], 0
; CHECK-NEXT: br i1 [[CMP2]], label [[FOR3]], label [[FOR_END11:%.*]]
; CHECK: for1.inc10:
; CHECK-NEXT: [[INDVARS_IV_NEXT20]] = add nuw nsw i64 [[INDVARS_IV19]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT20]], 100
; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR3_SPLIT]], label [[FOR1_HEADER]]
; CHECK: for.end11:
; CHECK-NEXT: ret void
;
entry:
br label %for1.header
for1.header:
%j19 = phi i64 [ 0, %entry ], [ %j.next20, %for1.inc10 ]
br label %for3
for3:
%j = phi i64 [ 100, %for1.header ], [ %j.next, %for3 ]
%arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j19
%0 = load i64, i64* %arrayidx5
%add = add nsw i64 %0, %k
store i64 %add, i64* %arrayidx5
%j.next = add nsw i64 %j, -1
%cmp2 = icmp sgt i64 %j, 0
br i1 %cmp2, label %for3, label %for1.inc10
for1.inc10:
%j.next20 = add nuw nsw i64 %j19, 1
%exitcond = icmp eq i64 %j.next20, 100
br i1 %exitcond, label %for.end11, label %for1.header
for.end11:
ret void
}
;; Test to make sure we can handle output dependencies.
;;
;; for (int i = 1; i < 100; ++i)
;; for(int j = 1; j < 99; ++j) {
;; A[j][i] = i;
;; A[j][i+1] = j;
;; }
;; FIXME: DA misses this case after D35430
define void @interchange_10() {
entry:
br label %for1.header
for1.header:
%j23 = phi i64 [ 1, %entry ], [ %j.next24, %for1.inc10 ]
%j.next24 = add nuw nsw i64 %j23, 1
br label %for2
for2:
%j = phi i64 [ %j.next, %for2 ], [ 1, %for1.header ]
%j.next = add nuw nsw i64 %j, 1
%arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23
store i64 %j, i64* %arrayidx5
%arrayidx10 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j.next24
store i64 %j23, i64* %arrayidx10
%exitcond = icmp eq i64 %j, 99
br i1 %exitcond, label %for1.inc10, label %for2
for1.inc10:
%exitcond26 = icmp eq i64 %j23, 98
br i1 %exitcond26, label %for.end12, label %for1.header
for.end12:
ret void
}

llvm/trunk/test/Transforms/LoopInterchange/phi-ordering.ll

; REQUIRES: asserts ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s ; RUN: opt < %s -loop-interchange -verify-dom-info -S 2>&1 | FileCheck %s
;; Checks the order of the inner phi nodes does not cause havoc. ;; Checks the order of the inner phi nodes does not cause havoc.
;; The inner loop has a reduction into c. The IV is not the first phi. ;; The inner loop has a reduction into c. The IV is not the first phi.
; CHECK: Not interchanging loops. Cannot prove legality.
target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
target triple = "armv8--linux-gnueabihf" target triple = "armv8--linux-gnueabihf"
; Function Attrs: norecurse nounwind ; Function Attrs: norecurse nounwind
define void @test(i32 %T, [90 x i32]* noalias nocapture %C, i16* noalias nocapture readonly %A, i16* noalias nocapture readonly %B) local_unnamed_addr #0 { define void @test(i32 %T, [90 x i32]* noalias nocapture %C, i16* noalias nocapture readonly %A, i16* noalias nocapture readonly %B) local_unnamed_addr #0 {
; CHECK-LABEL: @test(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[FOR3_PREHEADER:%.*]]
; CHECK: for1.header.preheader:
; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]
; CHECK: for1.header:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[INC20:%.*]], [[FOR1_INC19:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul nsw i32 [[I]], 90
; CHECK-NEXT: br label [[FOR2_HEADER_PREHEADER:%.*]]
; CHECK: for2.header.preheader:
; CHECK-NEXT: br label [[FOR2_HEADER:%.*]]
; CHECK: for2.header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ [[INC17:%.*]], [[FOR2_INC16:%.*]] ], [ 0, [[FOR2_HEADER_PREHEADER]] ]
; CHECK-NEXT: [[ARRAYIDX14:%.*]] = getelementptr inbounds [90 x i32], [90 x i32]* [[C:%.*]], i32 [[I]], i32 [[J]]
; CHECK-NEXT: [[ARRAYIDX14_PROMOTED:%.*]] = load i32, i32* [[ARRAYIDX14]], align 4
; CHECK-NEXT: br label [[FOR3_SPLIT1:%.*]]
; CHECK: for3.preheader:
; CHECK-NEXT: br label [[FOR3:%.*]]
; CHECK: for3:
; CHECK-NEXT: [[K:%.*]] = phi i32 [ [[INC:%.*]], [[FOR3_SPLIT:%.*]] ], [ 1, [[FOR3_PREHEADER]] ]
; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]
; CHECK: for3.split1:
; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[K]], [[MUL]]
; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i16, i16* [[A:%.*]], i32 [[ADD]]
; CHECK-NEXT: [[TMP0:%.*]] = load i16, i16* [[ARRAYIDX]], align 2
; CHECK-NEXT: [[CONV:%.*]] = sext i16 [[TMP0]] to i32
; CHECK-NEXT: [[ADD15:%.*]] = add nsw i32 [[CONV]], [[ARRAYIDX14_PROMOTED]]
; CHECK-NEXT: br label [[FOR2_INC16]]
; CHECK: for3.split:
; CHECK-NEXT: [[INC]] = add nuw nsw i32 [[K]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 90
; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR1_LOOPEXIT:%.*]], label [[FOR3]]
; CHECK: for2.inc16:
; CHECK-NEXT: store i32 [[ADD15]], i32* [[ARRAYIDX14]], align 4
; CHECK-NEXT: [[INC17]] = add nuw nsw i32 [[J]], 1
; CHECK-NEXT: [[EXITCOND47:%.*]] = icmp eq i32 [[INC17]], 90
; CHECK-NEXT: br i1 [[EXITCOND47]], label [[FOR1_INC19]], label [[FOR2_HEADER]]
; CHECK: for1.inc19:
; CHECK-NEXT: [[INC20]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT: [[EXITCOND48:%.*]] = icmp eq i32 [[INC20]], 90
; CHECK-NEXT: br i1 [[EXITCOND48]], label [[FOR3_SPLIT]], label [[FOR1_HEADER]]
; CHECK: for1.loopexit:
; CHECK-NEXT: br label [[EXIT:%.*]]
; CHECK: exit:
; CHECK-NEXT: ret void
;
entry: entry:
%cmp45 = icmp sgt i32 %T, 0 br label %for1.header
br i1 %cmp45, label %for.body3.lr.ph.preheader, label %for.end21
for.body3.lr.ph.preheader: ; preds = %entry
br label %for.body3.lr.ph
for.body3.lr.ph: ; preds = %for.body3.lr.ph.preheader, %for.inc19 for1.header: ; preds = %entry
%i.046 = phi i32 [ %inc20, %for.inc19 ], [ 0, %for.body3.lr.ph.preheader ] %i = phi i32 [ %inc20, %for1.inc19 ], [ 0, %entry ]
%mul = mul nsw i32 %i.046, %T %mul = mul nsw i32 %i, 90
br label %for.body6.lr.ph br label %for2.header
for.body6.lr.ph: ; preds = %for.inc16, %for.body3.lr.ph for2.header: ; preds = %for2.inc16, %for1.header
%j.043 = phi i32 [ 0, %for.body3.lr.ph ], [ %inc17, %for.inc16 ] %j = phi i32 [ 0, %for1.header ], [ %inc17, %for2.inc16 ]
%arrayidx14 = getelementptr inbounds [90 x i32], [90 x i32]* %C, i32 %i.046, i32 %j.043 %arrayidx14 = getelementptr inbounds [90 x i32], [90 x i32]* %C, i32 %i, i32 %j
%arrayidx14.promoted = load i32, i32* %arrayidx14, align 4 %arrayidx14.promoted = load i32, i32* %arrayidx14, align 4
br label %for.body6 br label %for3
for.body6: ; preds = %for.body6, %for.body6.lr.ph for3: ; preds = %for3, %for2.header
%add1541 = phi i32 [ %arrayidx14.promoted, %for.body6.lr.ph ], [ %add15, %for.body6 ] %add1541 = phi i32 [ %arrayidx14.promoted, %for2.header ], [ %add15, %for3 ]
%k.040 = phi i32 [ 0, %for.body6.lr.ph ], [ %inc, %for.body6 ] %k = phi i32 [ 1, %for2.header ], [ %inc, %for3 ]
%add = add nsw i32 %k.040, %mul %add = add nsw i32 %k, %mul
%arrayidx = getelementptr inbounds i16, i16* %A, i32 %add %arrayidx = getelementptr inbounds i16, i16* %A, i32 %add
%0 = load i16, i16* %arrayidx, align 2 %0 = load i16, i16* %arrayidx, align 2
%conv = sext i16 %0 to i32 %conv = sext i16 %0 to i32
%mul7 = mul nsw i32 %k.040, %T %add15 = add nsw i32 %conv, %add1541
%add8 = add nsw i32 %mul7, %j.043 %inc = add nuw nsw i32 %k, 1
%arrayidx9 = getelementptr inbounds i16, i16* %B, i32 %add8 %exitcond = icmp eq i32 %inc, 90
%1 = load i16, i16* %arrayidx9, align 2 br i1 %exitcond, label %for2.inc16, label %for3
%conv10 = sext i16 %1 to i32
%mul11 = mul nsw i32 %conv10, %conv
%add15 = add nsw i32 %mul11, %add1541
%inc = add nuw nsw i32 %k.040, 1
%exitcond = icmp eq i32 %inc, %T
br i1 %exitcond, label %for.inc16, label %for.body6
for.inc16: ; preds = %for.body6 for2.inc16: ; preds = %for.body6
%add15.lcssa = phi i32 [ %add15, %for.body6 ] %add15.lcssa = phi i32 [ %add15, %for3 ]
store i32 %add15.lcssa, i32* %arrayidx14, align 4 store i32 %add15.lcssa, i32* %arrayidx14, align 4
%inc17 = add nuw nsw i32 %j.043, 1 %inc17 = add nuw nsw i32 %j, 1
%exitcond47 = icmp eq i32 %inc17, %T %exitcond47 = icmp eq i32 %inc17, 90
br i1 %exitcond47, label %for.inc19, label %for.body6.lr.ph br i1 %exitcond47, label %for1.inc19, label %for2.header
for.inc19: ; preds = %for.inc16 for1.inc19: ; preds = %for2.inc16
%inc20 = add nuw nsw i32 %i.046, 1 %inc20 = add nuw nsw i32 %i, 1
%exitcond48 = icmp eq i32 %inc20, %T %exitcond48 = icmp eq i32 %inc20, 90
br i1 %exitcond48, label %for.end21.loopexit, label %for.body3.lr.ph br i1 %exitcond48, label %for1.loopexit, label %for1.header
for.end21.loopexit: ; preds = %for.inc19 for1.loopexit: ; preds = %for1.inc19
br label %for.end21 br label %exit
for.end21: ; preds = %for.end21.loopexit, %entry exit: ; preds = %for1.loopexit
ret void ret void
} }

llvm/trunk/test/Transforms/LoopInterchange/profitability.ll

; REQUIRES: asserts ; RUN: opt < %s -loop-interchange -pass-remarks-output=%t \
; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S -debug 2>&1 | FileCheck %s ; RUN: -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange
; RUN: FileCheck -input-file %t %s
;; We test profitability model in these test cases. ;; We test profitability model in these test cases.
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu" target triple = "x86_64-unknown-linux-gnu"
@A = common global [100 x [100 x i32]] zeroinitializer @A = common global [100 x [100 x i32]] zeroinitializer
@B = common global [100 x [100 x i32]] zeroinitializer @B = common global [100 x [100 x i32]] zeroinitializer
;;---------------------------------------Test case 01--------------------------------- ;;---------------------------------------Test case 01---------------------------------
;; Loops interchange will result in code vectorization and hence profitable. Check for interchange. ;; Loops interchange will result in code vectorization and hence profitable. Check for interchange.
;; for(int i=1;i<N;i++) ;; for(int i=1;i<100;i++)
;; for(int j=1;j<N;j++) ;; for(int j=1;j<100;j++)
;; A[j][i] = A[j - 1][i] + B[j][i]; ;; A[j][i] = A[j - 1][i] + B[j][i];
;; FIXME: DA misses this case after D35430
; CHECK: Not interchanging loops. Cannot prove legality. ; CHECK: Name: Dependence
; CHECK-NEXT: Function: interchange_01
define void @interchange_01(i32 %N) { define void @interchange_01() {
entry: entry:
%cmp27 = icmp sgt i32 %N, 1 br label %for2.preheader
br i1 %cmp27, label %for.cond1.preheader.lr.ph, label %for.end16
for.cond1.preheader.lr.ph:
%0 = add i32 %N, -1
br label %for.body3.preheader
for.body3.preheader:
%indvars.iv30 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next31, %for.inc14 ]
br label %for.body3
for.body3: for2.preheader:
%indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.body3.preheader ] %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]
%1 = add nsw i64 %indvars.iv, -1 br label %for2
%arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %1, i64 %indvars.iv30
%2 = load i32, i32* %arrayidx5 for2:
%arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %indvars.iv, i64 %indvars.iv30 %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]
%3 = load i32, i32* %arrayidx9 %j.prev = add nsw i64 %j, -1
%add = add nsw i32 %3, %2 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j.prev, i64 %i30
%arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv30 %lv1 = load i32, i32* %arrayidx5
%arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %j, i64 %i30
%lv2 = load i32, i32* %arrayidx9
%add = add nsw i32 %lv1, %lv2
%arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j, i64 %i30
store i32 %add, i32* %arrayidx13 store i32 %add, i32* %arrayidx13
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 %i.next = add nuw nsw i64 %j, 1
%lftr.wideiv = trunc i64 %indvars.iv to i32 %exitcond = icmp eq i64 %j, 99
%exitcond = icmp eq i32 %lftr.wideiv, %0 br i1 %exitcond, label %for1.inc14, label %for2
br i1 %exitcond, label %for.inc14, label %for.body3
for1.inc14:
for.inc14: %i.next31 = add nuw nsw i64 %i30, 1
%indvars.iv.next31 = add nuw nsw i64 %indvars.iv30, 1 %exitcond33 = icmp eq i64 %i30, 99
%lftr.wideiv32 = trunc i64 %indvars.iv30 to i32 br i1 %exitcond33, label %for.end16, label %for2.preheader
%exitcond33 = icmp eq i32 %lftr.wideiv32, %0
br i1 %exitcond33, label %for.end16, label %for.body3.preheader
for.end16: for.end16:
ret void ret void
} }
;; ---------------------------------------Test case 02--------------------------------- ;; ---------------------------------------Test case 02---------------------------------
;; Check loop interchange profitability model. ;; Check loop interchange profitability model.
;; This tests profitability model when operands of getelementpointer and not exactly the induction variable but some ;; This tests profitability model when operands of getelementpointer and not exactly the induction variable but some
;; arithmetic operation on them. ;; arithmetic operation on them.
;; for(int i=1;i<N;i++) ;; for(int i=1;i<N;i++)
;; for(int j=1;j<N;j++) ;; for(int j=1;j<N;j++)
;; A[j-1][i-1] = A[j - 1][i-1] + B[j-1][i-1]; ;; A[j-1][i-1] = A[j - 1][i-1] + B[j-1][i-1];
; CHECK: Not interchanging loops. Cannot prove legality. ; CHECK: Name: Interchanged
; CHECK-NEXT: Function: interchange_02
define void @interchange_02(i32 %N) { define void @interchange_02() {
entry: entry:
%cmp32 = icmp sgt i32 %N, 1 br label %for1.header
br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end21
for.cond1.preheader.lr.ph: for1.header:
%0 = add i32 %N, -1 %i35 = phi i64 [ 1, %entry ], [ %i.next36, %for1.inc19 ]
br label %for.body3.lr.ph %i.prev = add nsw i64 %i35, -1
br label %for2
for.body3.lr.ph:
%indvars.iv35 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next36, %for.inc19 ] for2:
%1 = add nsw i64 %indvars.iv35, -1 %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
br label %for.body3 %j.prev = add nsw i64 %j, -1
%arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %j.prev, i64 %i.prev
for.body3: %lv1 = load i32, i32* %arrayidx6
%indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ] %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %j.prev, i64 %i.prev
%2 = add nsw i64 %indvars.iv, -1 %lv2 = load i32, i32* %arrayidx12
%arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %2, i64 %1 %add = add nsw i32 %lv1, %lv2
%3 = load i32, i32* %arrayidx6
%arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %2, i64 %1
%4 = load i32, i32* %arrayidx12
%add = add nsw i32 %4, %3
store i32 %add, i32* %arrayidx6 store i32 %add, i32* %arrayidx6
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 %i.next = add nuw nsw i64 %j, 1
%lftr.wideiv = trunc i64 %indvars.iv to i32 %exitcond = icmp eq i64 %j, 99
%exitcond = icmp eq i32 %lftr.wideiv, %0 br i1 %exitcond, label %for1.inc19, label %for2
br i1 %exitcond, label %for.inc19, label %for.body3
for1.inc19:
for.inc19: %i.next36 = add nuw nsw i64 %i35, 1
%indvars.iv.next36 = add nuw nsw i64 %indvars.iv35, 1 %exitcond39 = icmp eq i64 %i35, 99
%lftr.wideiv38 = trunc i64 %indvars.iv35 to i32 br i1 %exitcond39, label %for.end21, label %for1.header
%exitcond39 = icmp eq i32 %lftr.wideiv38, %0
br i1 %exitcond39, label %for.end21, label %for.body3.lr.ph
for.end21: for.end21:
ret void ret void
} }
;;---------------------------------------Test case 03--------------------------------- ;;---------------------------------------Test case 03---------------------------------
;; Loops interchange is not profitable. ;; Loops interchange is not profitable.
;; for(int i=1;i<N;i++) ;; for(int i=1;i<100;i++)
;; for(int j=1;j<N;j++) ;; for(int j=1;j<100;j++)
;; A[i-1][j-1] = A[i - 1][j-1] + B[i][j]; ;; A[i-1][j-1] = A[i - 1][j-1] + B[i][j];
; CHECK: Not interchanging loops. Cannot prove legality. ; CHECK: Name: InterchangeNotProfitable
; CHECK-ENXT: Function: interchange_03
define void @interchange_03(){
entry:
br label %for1.header
define void @interchange_03(i32 %N){ for1.header:
%i34 = phi i64 [ 1, %entry ], [ %i.next35, %for1.inc17 ]
%i.prev = add nsw i64 %i34, -1
br label %for2
for2:
%j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]
%j.prev = add nsw i64 %j, -1
%arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %i.prev, i64 %j.prev
%lv1 = load i32, i32* %arrayidx6
%arrayidx10 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %i34, i64 %j
%lv2 = load i32, i32* %arrayidx10
%add = add nsw i32 %lv1, %lv2
store i32 %add, i32* %arrayidx6
%i.next = add nuw nsw i64 %j, 1
%exitcond = icmp eq i64 %j, 99
br i1 %exitcond, label %for1.inc17, label %for2
for1.inc17:
%i.next35 = add nuw nsw i64 %i34, 1
%exitcond38 = icmp eq i64 %i34, 99
br i1 %exitcond38, label %for.end19, label %for1.header
for.end19:
ret void
}
;; Loops should not be interchanged in this case as it is not profitable.
;; for(int i=0;i<100;i++)
;; for(int j=0;j<100;j++)
;; A[i][j] = A[i][j]+k;
; CHECK: Name: InterchangeNotProfitable
; CHECK-ENXT: Function: interchange_04
define void @interchange_04(i32 %k) {
entry: entry:
%cmp31 = icmp sgt i32 %N, 1 br label %for.cond1.preheader
br i1 %cmp31, label %for.cond1.preheader.lr.ph, label %for.end19
for.cond1.preheader.lr.ph: for.cond1.preheader:
%0 = add i32 %N, -1 %indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ]
br label %for.body3.lr.ph
for.body3.lr.ph:
%indvars.iv34 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next35, %for.inc17 ]
%1 = add nsw i64 %indvars.iv34, -1
br label %for.body3 br label %for.body3
for.body3: for.body3:
%indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ] %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]
%2 = add nsw i64 %indvars.iv, -1 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv
%arrayidx6 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %1, i64 %2 %0 = load i32, i32* %arrayidx5
%3 = load i32, i32* %arrayidx6 %add = add nsw i32 %0, %k
%arrayidx10 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @B, i64 0, i64 %indvars.iv34, i64 %indvars.iv store i32 %add, i32* %arrayidx5
%4 = load i32, i32* %arrayidx10
%add = add nsw i32 %4, %3
store i32 %add, i32* %arrayidx6
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%lftr.wideiv = trunc i64 %indvars.iv to i32 %exitcond = icmp eq i64 %indvars.iv.next, 100
%exitcond = icmp eq i32 %lftr.wideiv, %0 br i1 %exitcond, label %for.inc10, label %for.body3
br i1 %exitcond, label %for.inc17, label %for.body3
for.inc17:
%indvars.iv.next35 = add nuw nsw i64 %indvars.iv34, 1
%lftr.wideiv37 = trunc i64 %indvars.iv34 to i32
%exitcond38 = icmp eq i32 %lftr.wideiv37, %0
br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph
for.end19: for.inc10:
%indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
%exitcond23 = icmp eq i64 %indvars.iv.next22, 100
br i1 %exitcond23, label %for.end12, label %for.cond1.preheader
for.end12:
ret void ret void
} }

llvm/trunk/test/Transforms/LoopInterchange/reductions.ll

Show First 20 Lines • Show All 108 Lines • ▼ Show 20 Lines
;; for( int j=1;j<N;j++) { ;; for( int j=1;j<N;j++) {
;; for( int k=1;k<N;k++) { ;; for( int k=1;k<N;k++) {
;; X+=A[k][j]; ;; X+=A[k][j];
;; } ;; }
;; Y+=B[j][i]; ;; Y+=B[j][i];
;; } ;; }
;; Not tightly nested. Do not interchange. ;; Not tightly nested. Do not interchange.
;; Not interchanged hence the phi's in the inner loop will not be split. Check for the same. ;; Not interchanged hence the phi's in the inner loop will not be split.
; CHECK: Not interchanging loops. Cannot prove legality. ; CHECK: Outer loops with reductions are not supported currently.
define void @reduction_03(i32 %N) { define void @reduction_03(i32 %N) {
entry: entry:
%cmp35 = icmp sgt i32 %N, 1 %cmp35 = icmp sgt i32 %N, 1
br i1 %cmp35, label %for.cond4.preheader.lr.ph, label %for.end19 br i1 %cmp35, label %for.cond4.preheader.lr.ph, label %for.end19
for.cond4.preheader.lr.ph: ; preds = %entry, %for.cond1.for.inc17_crit_edge for.cond4.preheader.lr.ph: ; preds = %entry, %for.cond1.for.inc17_crit_edge
%indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ] %indvars.iv41 = phi i64 [ %indvars.iv.next42, %for.cond1.for.inc17_crit_edge ], [ 1, %entry ]
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 Lines
;; Multiple use of reduction not safe. Do not interchange. ;; Multiple use of reduction not safe. Do not interchange.
;; for( int i=1;i<N;i++) ;; for( int i=1;i<N;i++)
;; for( int j=1;j<N;j++) ;; for( int j=1;j<N;j++)
;; for( int k=1;k<N;k++) { ;; for( int k=1;k<N;k++) {
;; X+=A[k][j]; ;; X+=A[k][j];
;; Y+=X; ;; Y+=X;
;; } ;; }
;; Not interchanged hence the phi's in the inner loop will not be split. Check for the same. ;; Not interchanged hence the phi's in the inner loop will not be split.
; CHECK: Not interchanging loops. Cannot prove legality. ; CHECK: Only inner loops with induction or reduction PHI nodes are supported currently.
define void @reduction_04(i32 %N) { define void @reduction_04(i32 %N) {
entry: entry:
%cmp28 = icmp sgt i32 %N, 1 %cmp28 = icmp sgt i32 %N, 1
br i1 %cmp28, label %for.cond4.preheader.preheader, label %for.end15 br i1 %cmp28, label %for.cond4.preheader.preheader, label %for.end15
for.cond4.preheader.preheader: ; preds = %entry, %for.inc13 for.cond4.preheader.preheader: ; preds = %entry, %for.inc13
%i.029 = phi i32 [ %inc14, %for.inc13 ], [ 1, %entry ] %i.029 = phi i32 [ %inc14, %for.inc13 ], [ 1, %entry ]
Show All 37 Lines
llvm/trunk/test/Transforms/LoopInterchange/interchange-simple-count-down.ll