325 lines
11 KiB
LLVM
325 lines
11 KiB
LLVM
|
; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 | FileCheck %s
|
||
|
|
|
||
|
|
; Test a perfect 2-dim loop nest of the form:
|
||
|
|
; for(i=0; i<nx; ++i)
|
||
|
|
; for(j=0; j<nx; ++j)
|
||
|
|
; y[i][j] = x[i][j];
|
||
|
|
|
||
|
|
define void @perf_nest_2D_1(i32** %y, i32** %x, i64 signext %nx, i64 signext %ny) {
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_2D_1_loop_j, Loops: ( perf_nest_2D_1_loop_j )
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_2D_1_loop_i, Loops: ( perf_nest_2D_1_loop_i perf_nest_2D_1_loop_j )
|
||
|
|
entry:
|
||
|
|
br label %perf_nest_2D_1_loop_i
|
||
|
|
|
||
|
|
perf_nest_2D_1_loop_i:
|
||
|
|
%i = phi i64 [ 0, %entry ], [ %inc13, %inc_i ]
|
||
|
|
%cmp21 = icmp slt i64 0, %ny
|
||
|
|
br i1 %cmp21, label %perf_nest_2D_1_loop_j, label %inc_i
|
||
|
|
|
||
|
|
perf_nest_2D_1_loop_j:
|
||
|
|
%j = phi i64 [ 0, %perf_nest_2D_1_loop_i ], [ %inc, %inc_j ]
|
||
|
|
%arrayidx = getelementptr inbounds i32*, i32** %x, i64 %j
|
||
|
|
%0 = load i32*, i32** %arrayidx, align 8
|
||
|
|
%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %j
|
||
|
|
%1 = load i32, i32* %arrayidx6, align 4
|
||
|
|
%arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %j
|
||
|
|
%2 = load i32*, i32** %arrayidx8, align 8
|
||
|
|
%arrayidx11 = getelementptr inbounds i32, i32* %2, i64 %i
|
||
|
|
store i32 %1, i32* %arrayidx11, align 4
|
||
|
|
br label %inc_j
|
||
|
|
|
||
|
|
inc_j:
|
||
|
|
%inc = add nsw i64 %j, 1
|
||
|
|
%cmp2 = icmp slt i64 %inc, %ny
|
||
|
|
br i1 %cmp2, label %perf_nest_2D_1_loop_j, label %inc_i
|
||
|
|
|
||
|
|
inc_i:
|
||
|
|
%inc13 = add nsw i64 %i, 1
|
||
|
|
%cmp = icmp slt i64 %inc13, %nx
|
||
|
|
br i1 %cmp, label %perf_nest_2D_1_loop_i, label %perf_nest_2D_1_loop_i_end
|
||
|
|
|
||
|
|
perf_nest_2D_1_loop_i_end:
|
||
|
|
ret void
|
||
|
|
}
|
||
|
|
|
||
|
|
; Test a perfect 2-dim loop nest of the form:
|
||
|
|
; for (i=0; i<100; ++i)
|
||
|
|
; for (j=0; j<100; ++j)
|
||
|
|
; y[i][j] = x[i][j];
|
||
|
|
define void @perf_nest_2D_2(i32** %y, i32** %x) {
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_2D_2_loop_j, Loops: ( perf_nest_2D_2_loop_j )
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_2D_2_loop_i, Loops: ( perf_nest_2D_2_loop_i perf_nest_2D_2_loop_j )
|
||
|
|
entry:
|
||
|
|
br label %perf_nest_2D_2_loop_i
|
||
|
|
|
||
|
|
perf_nest_2D_2_loop_i:
|
||
|
|
%i = phi i64 [ 0, %entry ], [ %inc13, %inc_i ]
|
||
|
|
br label %perf_nest_2D_2_loop_j
|
||
|
|
|
||
|
|
perf_nest_2D_2_loop_j:
|
||
|
|
%j = phi i64 [ 0, %perf_nest_2D_2_loop_i ], [ %inc, %inc_j ]
|
||
|
|
%arrayidx = getelementptr inbounds i32*, i32** %x, i64 %j
|
||
|
|
%0 = load i32*, i32** %arrayidx, align 8
|
||
|
|
%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %j
|
||
|
|
%1 = load i32, i32* %arrayidx6, align 4
|
||
|
|
%arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %j
|
||
|
|
%2 = load i32*, i32** %arrayidx8, align 8
|
||
|
|
%arrayidx11 = getelementptr inbounds i32, i32* %2, i64 %i
|
||
|
|
store i32 %1, i32* %arrayidx11, align 4
|
||
|
|
br label %inc_j
|
||
|
|
|
||
|
|
inc_j:
|
||
|
|
%inc = add nsw i64 %j, 1
|
||
|
|
%cmp2 = icmp slt i64 %inc, 100
|
||
|
|
br i1 %cmp2, label %perf_nest_2D_2_loop_j, label %loop_j_end
|
||
|
|
|
||
|
|
loop_j_end:
|
||
|
|
br label %inc_i
|
||
|
|
|
||
|
|
inc_i:
|
||
|
|
%inc13 = add nsw i64 %i, 1
|
||
|
|
%cmp = icmp slt i64 %inc13, 100
|
||
|
|
br i1 %cmp, label %perf_nest_2D_2_loop_i, label %perf_nest_2D_2_loop_i_end
|
||
|
|
|
||
|
|
perf_nest_2D_2_loop_i_end:
|
||
|
|
ret void
|
||
|
|
}
|
||
|
|
|
||
|
|
define void @perf_nest_2D_3(i32** %y, i32** %x, i64 signext %nx, i64 signext %ny) {
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_2D_3_loop_j, Loops: ( perf_nest_2D_3_loop_j )
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_2D_3_loop_i, Loops: ( perf_nest_2D_3_loop_i perf_nest_2D_3_loop_j )
|
||
|
|
entry:
|
||
|
|
br label %perf_nest_2D_3_loop_i
|
||
|
|
|
||
|
|
perf_nest_2D_3_loop_i:
|
||
|
|
%i = phi i64 [ 0, %entry ], [ %inc13, %inc_i ]
|
||
|
|
%cmp21 = icmp slt i64 0, %ny
|
||
|
|
br label %singleSucc
|
||
|
|
|
||
|
|
singleSucc:
|
||
|
|
br i1 %cmp21, label %preheader.j, label %for.end
|
||
|
|
|
||
|
|
preheader.j:
|
||
|
|
br label %perf_nest_2D_3_loop_j
|
||
|
|
|
||
|
|
perf_nest_2D_3_loop_j:
|
||
|
|
%j = phi i64 [ 0, %preheader.j ], [ %inc, %inc_j ]
|
||
|
|
%arrayidx = getelementptr inbounds i32*, i32** %x, i64 %j
|
||
|
|
%0 = load i32*, i32** %arrayidx, align 8
|
||
|
|
%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %j
|
||
|
|
%1 = load i32, i32* %arrayidx6, align 4
|
||
|
|
%arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %j
|
||
|
|
%2 = load i32*, i32** %arrayidx8, align 8
|
||
|
|
%arrayidx11 = getelementptr inbounds i32, i32* %2, i64 %i
|
||
|
|
store i32 %1, i32* %arrayidx11, align 4
|
||
|
|
br label %inc_j
|
||
|
|
|
||
|
|
inc_j:
|
||
|
|
%inc = add nsw i64 %j, 1
|
||
|
|
%cmp2 = icmp slt i64 %inc, %ny
|
||
|
|
br i1 %cmp2, label %perf_nest_2D_3_loop_j, label %for.exit
|
||
|
|
|
||
|
|
for.exit:
|
||
|
|
br label %for.end
|
||
|
|
|
||
|
|
for.end:
|
||
|
|
br label %inc_i
|
||
|
|
|
||
|
|
inc_i:
|
||
|
|
%inc13 = add nsw i64 %i, 1
|
||
|
|
%cmp = icmp slt i64 %inc13, %nx
|
||
|
|
br i1 %cmp, label %perf_nest_2D_3_loop_i, label %perf_nest_2D_3_loop_i_end
|
||
|
|
|
||
|
|
perf_nest_2D_3_loop_i_end:
|
||
|
|
ret void
|
||
|
|
}
|
||
|
|
|
||
|
|
; Test a perfect 3-dim loop nest of the form:
|
||
|
|
; for (i=0; i<nx; ++i)
|
||
|
|
; for (j=0; j<ny; ++j)
|
||
|
|
; for (k=0; j<nk; ++k)
|
||
|
|
; y[j][j][k] = x[i][j][k];
|
||
|
|
;
|
||
|
|
|
||
|
|
define void @perf_nest_3D_1(i32*** %y, i32*** %x, i32 signext %nx, i32 signext %ny, i32 signext %nk) {
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_3D_1_loop_k, Loops: ( perf_nest_3D_1_loop_k )
|
||
|
|
; CHECK-NEXT: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_3D_1_loop_j, Loops: ( perf_nest_3D_1_loop_j perf_nest_3D_1_loop_k )
|
||
|
|
; CHECK-NEXT: IsPerfect=true, Depth=3, OutermostLoop: perf_nest_3D_1_loop_i, Loops: ( perf_nest_3D_1_loop_i perf_nest_3D_1_loop_j perf_nest_3D_1_loop_k )
|
||
|
|
entry:
|
||
|
|
br label %perf_nest_3D_1_loop_i
|
||
|
|
|
||
|
|
perf_nest_3D_1_loop_i:
|
||
|
|
%i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]
|
||
|
|
%cmp21 = icmp slt i32 0, %ny
|
||
|
|
br i1 %cmp21, label %perf_nest_3D_1_loop_j, label %for.inci
|
||
|
|
|
||
|
|
perf_nest_3D_1_loop_j:
|
||
|
|
%j = phi i32 [ 0, %perf_nest_3D_1_loop_i ], [ %incj, %for.incj ]
|
||
|
|
%cmp22 = icmp slt i32 0, %nk
|
||
|
|
br i1 %cmp22, label %perf_nest_3D_1_loop_k, label %for.incj
|
||
|
|
|
||
|
|
perf_nest_3D_1_loop_k:
|
||
|
|
%k = phi i32 [ 0, %perf_nest_3D_1_loop_j ], [ %inck, %for.inck ]
|
||
|
|
%idxprom = sext i32 %i to i64
|
||
|
|
%arrayidx = getelementptr inbounds i32**, i32*** %x, i64 %idxprom
|
||
|
|
%0 = load i32**, i32*** %arrayidx, align 8
|
||
|
|
%idxprom7 = sext i32 %j to i64
|
||
|
|
%arrayidx8 = getelementptr inbounds i32*, i32** %0, i64 %idxprom7
|
||
|
|
%1 = load i32*, i32** %arrayidx8, align 8
|
||
|
|
%idxprom9 = sext i32 %k to i64
|
||
|
|
%arrayidx10 = getelementptr inbounds i32, i32* %1, i64 %idxprom9
|
||
|
|
%2 = load i32, i32* %arrayidx10, align 4
|
||
|
|
%idxprom11 = sext i32 %j to i64
|
||
|
|
%arrayidx12 = getelementptr inbounds i32**, i32*** %y, i64 %idxprom11
|
||
|
|
%3 = load i32**, i32*** %arrayidx12, align 8
|
||
|
|
%idxprom13 = sext i32 %j to i64
|
||
|
|
%arrayidx14 = getelementptr inbounds i32*, i32** %3, i64 %idxprom13
|
||
|
|
%4 = load i32*, i32** %arrayidx14, align 8
|
||
|
|
%idxprom15 = sext i32 %k to i64
|
||
|
|
%arrayidx16 = getelementptr inbounds i32, i32* %4, i64 %idxprom15
|
||
|
|
store i32 %2, i32* %arrayidx16, align 4
|
||
|
|
br label %for.inck
|
||
|
|
|
||
|
|
for.inck:
|
||
|
|
%inck = add nsw i32 %k, 1
|
||
|
|
%cmp5 = icmp slt i32 %inck, %nk
|
||
|
|
br i1 %cmp5, label %perf_nest_3D_1_loop_k, label %for.incj
|
||
|
|
|
||
|
|
for.incj:
|
||
|
|
%incj = add nsw i32 %j, 1
|
||
|
|
%cmp2 = icmp slt i32 %incj, %ny
|
||
|
|
br i1 %cmp2, label %perf_nest_3D_1_loop_j, label %for.inci
|
||
|
|
|
||
|
|
for.inci:
|
||
|
|
%inci = add nsw i32 %i, 1
|
||
|
|
%cmp = icmp slt i32 %inci, %nx
|
||
|
|
br i1 %cmp, label %perf_nest_3D_1_loop_i, label %perf_nest_3D_1_loop_i_end
|
||
|
|
|
||
|
|
perf_nest_3D_1_loop_i_end:
|
||
|
|
ret void
|
||
|
|
}
|
||
|
|
|
||
|
|
; Test a perfect 3-dim loop nest of the form:
|
||
|
|
; for (i=0; i<100; ++i)
|
||
|
|
; for (j=0; j<100; ++j)
|
||
|
|
; for (k=0; j<100; ++k)
|
||
|
|
; y[j][j][k] = x[i][j][k];
|
||
|
|
;
|
||
|
|
|
||
|
|
define void @perf_nest_3D_2(i32*** %y, i32*** %x) {
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_3D_2_loop_k, Loops: ( perf_nest_3D_2_loop_k )
|
||
|
|
; CHECK-NEXT: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_3D_2_loop_j, Loops: ( perf_nest_3D_2_loop_j perf_nest_3D_2_loop_k )
|
||
|
|
; CHECK-NEXT: IsPerfect=true, Depth=3, OutermostLoop: perf_nest_3D_2_loop_i, Loops: ( perf_nest_3D_2_loop_i perf_nest_3D_2_loop_j perf_nest_3D_2_loop_k )
|
||
|
|
entry:
|
||
|
|
br label %perf_nest_3D_2_loop_i
|
||
|
|
|
||
|
|
perf_nest_3D_2_loop_i:
|
||
|
|
%i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]
|
||
|
|
br label %perf_nest_3D_2_loop_j
|
||
|
|
|
||
|
|
perf_nest_3D_2_loop_j:
|
||
|
|
%j = phi i32 [ 0, %perf_nest_3D_2_loop_i ], [ %incj, %for.incj ]
|
||
|
|
br label %perf_nest_3D_2_loop_k
|
||
|
|
|
||
|
|
perf_nest_3D_2_loop_k:
|
||
|
|
%k = phi i32 [ 0, %perf_nest_3D_2_loop_j ], [ %inck, %for.inck ]
|
||
|
|
%idxprom = sext i32 %i to i64
|
||
|
|
%arrayidx = getelementptr inbounds i32**, i32*** %x, i64 %idxprom
|
||
|
|
%0 = load i32**, i32*** %arrayidx, align 8
|
||
|
|
%idxprom7 = sext i32 %j to i64
|
||
|
|
%arrayidx8 = getelementptr inbounds i32*, i32** %0, i64 %idxprom7
|
||
|
|
%1 = load i32*, i32** %arrayidx8, align 8
|
||
|
|
%idxprom9 = sext i32 %k to i64
|
||
|
|
%arrayidx10 = getelementptr inbounds i32, i32* %1, i64 %idxprom9
|
||
|
|
%2 = load i32, i32* %arrayidx10, align 4
|
||
|
|
%idxprom11 = sext i32 %j to i64
|
||
|
|
%arrayidx12 = getelementptr inbounds i32**, i32*** %y, i64 %idxprom11
|
||
|
|
%3 = load i32**, i32*** %arrayidx12, align 8
|
||
|
|
%idxprom13 = sext i32 %j to i64
|
||
|
|
%arrayidx14 = getelementptr inbounds i32*, i32** %3, i64 %idxprom13
|
||
|
|
%4 = load i32*, i32** %arrayidx14, align 8
|
||
|
|
%idxprom15 = sext i32 %k to i64
|
||
|
|
%arrayidx16 = getelementptr inbounds i32, i32* %4, i64 %idxprom15
|
||
|
|
store i32 %2, i32* %arrayidx16, align 4
|
||
|
|
br label %for.inck
|
||
|
|
|
||
|
|
for.inck:
|
||
|
|
%inck = add nsw i32 %k, 1
|
||
|
|
%cmp5 = icmp slt i32 %inck, 100
|
||
|
|
br i1 %cmp5, label %perf_nest_3D_2_loop_k, label %loop_k_end
|
||
|
|
|
||
|
|
loop_k_end:
|
||
|
|
br label %for.incj
|
||
|
|
|
||
|
|
for.incj:
|
||
|
|
%incj = add nsw i32 %j, 1
|
||
|
|
%cmp2 = icmp slt i32 %incj, 100
|
||
|
|
br i1 %cmp2, label %perf_nest_3D_2_loop_j, label %loop_j_end
|
||
|
|
|
||
|
|
loop_j_end:
|
||
|
|
br label %for.inci
|
||
|
|
|
||
|
|
for.inci:
|
||
|
|
%inci = add nsw i32 %i, 1
|
||
|
|
%cmp = icmp slt i32 %inci, 100
|
||
|
|
br i1 %cmp, label %perf_nest_3D_2_loop_i, label %perf_nest_3D_2_loop_i_end
|
||
|
|
|
||
|
|
perf_nest_3D_2_loop_i_end:
|
||
|
|
ret void
|
||
|
|
}
|
||
|
|
|
||
|
|
; Test a perfect loop nest with a live out reduction:
|
||
|
|
; for (i = 0; i<ni; ++i)
|
||
|
|
; if (0<nj) { // guard branch for the j-loop
|
||
|
|
; for (j=0; j<nj; j+=1)
|
||
|
|
; x+=(i+j);
|
||
|
|
; }
|
||
|
|
; return x;
|
||
|
|
|
||
|
|
define signext i32 @perf_nest_live_out(i32 signext %x, i32 signext %ni, i32 signext %nj) {
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_live_out_loop_j, Loops: ( perf_nest_live_out_loop_j )
|
||
|
|
; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_live_out_loop_i, Loops: ( perf_nest_live_out_loop_i perf_nest_live_out_loop_j )
|
||
|
|
entry:
|
||
|
|
%cmp4 = icmp slt i32 0, %ni
|
||
|
|
br i1 %cmp4, label %perf_nest_live_out_loop_i.lr.ph, label %for.end7
|
||
|
|
|
||
|
|
perf_nest_live_out_loop_i.lr.ph:
|
||
|
|
br label %perf_nest_live_out_loop_i
|
||
|
|
|
||
|
|
perf_nest_live_out_loop_i:
|
||
|
|
%x.addr.06 = phi i32 [ %x, %perf_nest_live_out_loop_i.lr.ph ], [ %x.addr.1.lcssa, %for.inc5 ]
|
||
|
|
%i.05 = phi i32 [ 0, %perf_nest_live_out_loop_i.lr.ph ], [ %inc6, %for.inc5 ]
|
||
|
|
%cmp21 = icmp slt i32 0, %nj
|
||
|
|
br i1 %cmp21, label %perf_nest_live_out_loop_j.lr.ph, label %for.inc5
|
||
|
|
|
||
|
|
perf_nest_live_out_loop_j.lr.ph:
|
||
|
|
br label %perf_nest_live_out_loop_j
|
||
|
|
|
||
|
|
perf_nest_live_out_loop_j:
|
||
|
|
%x.addr.13 = phi i32 [ %x.addr.06, %perf_nest_live_out_loop_j.lr.ph ], [ %add4, %perf_nest_live_out_loop_j ]
|
||
|
|
%j.02 = phi i32 [ 0, %perf_nest_live_out_loop_j.lr.ph ], [ %inc, %perf_nest_live_out_loop_j ]
|
||
|
|
%add = add nsw i32 %i.05, %j.02
|
||
|
|
%add4 = add nsw i32 %x.addr.13, %add
|
||
|
|
%inc = add nsw i32 %j.02, 1
|
||
|
|
%cmp2 = icmp slt i32 %inc, %nj
|
||
|
|
br i1 %cmp2, label %perf_nest_live_out_loop_j, label %for.cond1.for.inc5_crit_edge
|
||
|
|
|
||
|
|
for.cond1.for.inc5_crit_edge:
|
||
|
|
%split = phi i32 [ %add4, %perf_nest_live_out_loop_j ]
|
||
|
|
br label %for.inc5
|
||
|
|
|
||
|
|
for.inc5:
|
||
|
|
%x.addr.1.lcssa = phi i32 [ %split, %for.cond1.for.inc5_crit_edge ], [ %x.addr.06, %perf_nest_live_out_loop_i ]
|
||
|
|
%inc6 = add nsw i32 %i.05, 1
|
||
|
|
%cmp = icmp slt i32 %inc6, %ni
|
||
|
|
br i1 %cmp, label %perf_nest_live_out_loop_i, label %for.cond.for.end7_crit_edge
|
||
|
|
|
||
|
|
for.cond.for.end7_crit_edge:
|
||
|
|
%split7 = phi i32 [ %x.addr.1.lcssa, %for.inc5 ]
|
||
|
|
br label %for.end7
|
||
|
|
|
||
|
|
for.end7:
|
||
|
|
%x.addr.0.lcssa = phi i32 [ %split7, %for.cond.for.end7_crit_edge ], [ %x, %entry ]
|
||
|
|
ret i32 %x.addr.0.lcssa
|
||
|
|
}
|