test/Analysis/LoopNestAnalysis/imperfectnest.ll - llvm-project/llvm - Git at Google

 ; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 | FileCheck %s

 ; Test an imperfect 2-dim loop nest of the form:
 ;   for (int i = 0; i < nx; ++i) {
 ;     x[i] = i;
 ;     for (int j = 0; j < ny; ++j)
 ;       y[j][i] = x[i] + j;
 ;   }

 define void @imperf_nest_1(i32 signext %nx, i32 signext %ny) {
 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_1_loop_i, Loops: ( imperf_nest_1_loop_i imperf_nest_1_loop_j )
 entry:
   %0 = zext i32 %ny to i64
   %1 = zext i32 %nx to i64
   %2 = mul nuw i64 %0, %1
   %vla = alloca double, i64 %2, align 8
   %3 = zext i32 %ny to i64
   %vla1 = alloca double, i64 %3, align 8
   br label %imperf_nest_1_loop_i

 imperf_nest_1_loop_i:
   %i2.0 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]
   %cmp = icmp slt i32 %i2.0, %nx
   br i1 %cmp, label %for.body, label %for.end17

 for.body:
   %conv = sitofp i32 %i2.0 to double
   %idxprom = sext i32 %i2.0 to i64
   %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
   store double %conv, double* %arrayidx, align 8
   br label %imperf_nest_1_loop_j

 imperf_nest_1_loop_j:
   %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %cmp5 = icmp slt i32 %j3.0, %ny
   br i1 %cmp5, label %for.body7, label %for.end

 for.body7:
   %idxprom8 = sext i32 %i2.0 to i64
   %arrayidx9 = getelementptr inbounds double, double* %vla1, i64 %idxprom8
   %4 = load double, double* %arrayidx9, align 8
   %conv10 = sitofp i32 %j3.0 to double
   %add = fadd double %4, %conv10
   %idxprom11 = sext i32 %j3.0 to i64
   %5 = mul nsw i64 %idxprom11, %1
   %arrayidx12 = getelementptr inbounds double, double* %vla, i64 %5
   %idxprom13 = sext i32 %i2.0 to i64
   %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
   store double %add, double* %arrayidx14, align 8
   br label %for.inc

 for.inc:
   %inc = add nsw i32 %j3.0, 1
   br label %imperf_nest_1_loop_j

 for.end:
   br label %for.inc15

 for.inc15:
   %inc16 = add nsw i32 %i2.0, 1
   br label %imperf_nest_1_loop_i

 for.end17:
   ret void
 }

 ; Test an imperfect 2-dim loop nest of the form:
 ;   for (int i = 0; i < nx; ++i) {
 ;     for (int j = 0; j < ny; ++j)
 ;       y[j][i] = x[i] + j;
 ;     y[0][i] += i;
 ;   }

 define void @imperf_nest_2(i32 signext %nx, i32 signext %ny) {
 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_2_loop_i, Loops: ( imperf_nest_2_loop_i imperf_nest_2_loop_j )
 entry:
   %0 = zext i32 %ny to i64
   %1 = zext i32 %nx to i64
   %2 = mul nuw i64 %0, %1
   %vla = alloca double, i64 %2, align 8
   %3 = zext i32 %ny to i64
   %vla1 = alloca double, i64 %3, align 8
   br label %imperf_nest_2_loop_i

 imperf_nest_2_loop_i:
   %i2.0 = phi i32 [ 0, %entry ], [ %inc17, %for.inc16 ]
   %cmp = icmp slt i32 %i2.0, %nx
   br i1 %cmp, label %for.body, label %for.end18

 for.body:
   br label %imperf_nest_2_loop_j

 imperf_nest_2_loop_j:
   %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %cmp5 = icmp slt i32 %j3.0, %ny
   br i1 %cmp5, label %for.body6, label %for.end

 for.body6:
   %idxprom = sext i32 %i2.0 to i64
   %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
   %4 = load double, double* %arrayidx, align 8
   %conv = sitofp i32 %j3.0 to double
   %add = fadd double %4, %conv
   %idxprom7 = sext i32 %j3.0 to i64
   %5 = mul nsw i64 %idxprom7, %1
   %arrayidx8 = getelementptr inbounds double, double* %vla, i64 %5
   %idxprom9 = sext i32 %i2.0 to i64
   %arrayidx10 = getelementptr inbounds double, double* %arrayidx8, i64 %idxprom9
   store double %add, double* %arrayidx10, align 8
   br label %for.inc

 for.inc:
   %inc = add nsw i32 %j3.0, 1
   br label %imperf_nest_2_loop_j

 for.end:
   %conv11 = sitofp i32 %i2.0 to double
   %6 = mul nsw i64 0, %1
   %arrayidx12 = getelementptr inbounds double, double* %vla, i64 %6
   %idxprom13 = sext i32 %i2.0 to i64
   %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
   %7 = load double, double* %arrayidx14, align 8
   %add15 = fadd double %7, %conv11
   store double %add15, double* %arrayidx14, align 8
   br label %for.inc16

 for.inc16:
   %inc17 = add nsw i32 %i2.0, 1
   br label %imperf_nest_2_loop_i

 for.end18:
   ret void
 }

 ; Test an imperfect 2-dim loop nest of the form:
 ;   for (i = 0; i < nx; ++i) {
 ;     for (j = 0; j < ny-nk; ++j)
 ;       y[i][j] = x[i] + j;
 ;     for (j = ny-nk; j < ny; ++j)
 ;       y[i][j] = x[i] - j;
 ;   }

 define void @imperf_nest_3(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_3_loop_i, Loops: ( imperf_nest_3_loop_i imperf_nest_3_loop_j imperf_nest_3_loop_k )
 entry:
   %0 = zext i32 %nx to i64
   %1 = zext i32 %ny to i64
   %2 = mul nuw i64 %0, %1
   %vla = alloca double, i64 %2, align 8
   %3 = zext i32 %ny to i64
   %vla1 = alloca double, i64 %3, align 8
   br label %imperf_nest_3_loop_i

 imperf_nest_3_loop_i:                                         ; preds = %for.inc25, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %inc26, %for.inc25 ]
   %cmp = icmp slt i32 %i.0, %nx
   br i1 %cmp, label %for.body, label %for.end27

 for.body:                                         ; preds = %for.cond
   br label %imperf_nest_3_loop_j

 imperf_nest_3_loop_j:                                        ; preds = %for.inc, %for.body
   %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %sub = sub nsw i32 %ny, %nk
   %cmp3 = icmp slt i32 %j.0, %sub
   br i1 %cmp3, label %for.body4, label %for.end

 for.body4:                                        ; preds = %imperf_nest_3_loop_j
   %idxprom = sext i32 %i.0 to i64
   %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
   %4 = load double, double* %arrayidx, align 8
   %conv = sitofp i32 %j.0 to double
   %add = fadd double %4, %conv
   %idxprom5 = sext i32 %i.0 to i64
   %5 = mul nsw i64 %idxprom5, %1
   %arrayidx6 = getelementptr inbounds double, double* %vla, i64 %5
   %idxprom7 = sext i32 %j.0 to i64
   %arrayidx8 = getelementptr inbounds double, double* %arrayidx6, i64 %idxprom7
   store double %add, double* %arrayidx8, align 8
   br label %for.inc

 for.inc:                                          ; preds = %for.body4
   %inc = add nsw i32 %j.0, 1
   br label %imperf_nest_3_loop_j

 for.end:                                          ; preds = %imperf_nest_3_loop_j
   %sub9 = sub nsw i32 %ny, %nk
   br label %imperf_nest_3_loop_k

 imperf_nest_3_loop_k:                                       ; preds = %for.inc22, %for.end
   %j.1 = phi i32 [ %sub9, %for.end ], [ %inc23, %for.inc22 ]
   %cmp11 = icmp slt i32 %j.1, %ny
   br i1 %cmp11, label %for.body13, label %for.end24

 for.body13:                                       ; preds = %imperf_nest_3_loop_k
   %idxprom14 = sext i32 %i.0 to i64
   %arrayidx15 = getelementptr inbounds double, double* %vla1, i64 %idxprom14
   %6 = load double, double* %arrayidx15, align 8
   %conv16 = sitofp i32 %j.1 to double
   %sub17 = fsub double %6, %conv16
   %idxprom18 = sext i32 %i.0 to i64
   %7 = mul nsw i64 %idxprom18, %1
   %arrayidx19 = getelementptr inbounds double, double* %vla, i64 %7
   %idxprom20 = sext i32 %j.1 to i64
   %arrayidx21 = getelementptr inbounds double, double* %arrayidx19, i64 %idxprom20
   store double %sub17, double* %arrayidx21, align 8
   br label %for.inc22

 for.inc22:                                        ; preds = %for.body13
   %inc23 = add nsw i32 %j.1, 1
   br label %imperf_nest_3_loop_k

 for.end24:                                        ; preds = %imperf_nest_3_loop_k
   br label %for.inc25

 for.inc25:                                        ; preds = %for.end24
   %inc26 = add nsw i32 %i.0, 1
   br label %imperf_nest_3_loop_i

 for.end27:                                        ; preds = %for.cond
   ret void
 }

 ; Test an imperfect loop nest of the form:
 ;   for (i = 0; i < nx; ++i) {
 ;     for (j = 0; j < ny-nk; ++j)
 ;       for (k = 0; k < nk; ++k)
 ;         y[i][j][k] = x[i+j] + k;
 ;     for (j = ny-nk; j < ny; ++j)
 ;       y[i][j][0] = x[i] - j;
 ;   }

 define void @imperf_nest_4(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_4_loop_j, Loops: ( imperf_nest_4_loop_j imperf_nest_4_loop_k )
 ; CHECK-LABEL: IsPerfect=false, Depth=3, OutermostLoop: imperf_nest_4_loop_i, Loops: ( imperf_nest_4_loop_i imperf_nest_4_loop_j imperf_nest_4_loop_j2 imperf_nest_4_loop_k )
 entry:
   %0 = zext i32 %nx to i64
   %1 = zext i32 %ny to i64
   %2 = zext i32 %nk to i64
   %3 = mul nuw i64 %0, %1
   %4 = mul nuw i64 %3, %2
   %vla = alloca double, i64 %4, align 8
   %5 = zext i32 %ny to i64
   %vla1 = alloca double, i64 %5, align 8
   %cmp5 = icmp slt i32 0, %nx
   br i1 %cmp5, label %imperf_nest_4_loop_i.lr.ph, label %for.end37

 imperf_nest_4_loop_i.lr.ph:
   br label %imperf_nest_4_loop_i

 imperf_nest_4_loop_i:
   %i.0 = phi i32 [ 0, %imperf_nest_4_loop_i.lr.ph ], [ %inc36, %for.inc35 ]
   %sub2 = sub nsw i32 %ny, %nk
   %cmp33 = icmp slt i32 0, %sub2
   br i1 %cmp33, label %imperf_nest_4_loop_j.lr.ph, label %for.end17

 imperf_nest_4_loop_j.lr.ph:
   br label %imperf_nest_4_loop_j

 imperf_nest_4_loop_j:
   %j.0 = phi i32 [ 0, %imperf_nest_4_loop_j.lr.ph ], [ %inc16, %for.inc15 ]
   %cmp61 = icmp slt i32 0, %nk
   br i1 %cmp61, label %imperf_nest_4_loop_k.lr.ph, label %for.end

 imperf_nest_4_loop_k.lr.ph:
   br label %imperf_nest_4_loop_k

 imperf_nest_4_loop_k:
   %k.0 = phi i32 [ 0, %imperf_nest_4_loop_k.lr.ph ], [ %inc, %for.inc ]
   %add = add nsw i32 %i.0, %j.0
   %idxprom = sext i32 %add to i64
   %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
   %6 = load double, double* %arrayidx, align 8
   %conv = sitofp i32 %k.0 to double
   %add8 = fadd double %6, %conv
   %idxprom9 = sext i32 %i.0 to i64
   %7 = mul nuw i64 %1, %2
   %8 = mul nsw i64 %idxprom9, %7
   %arrayidx10 = getelementptr inbounds double, double* %vla, i64 %8
   %idxprom11 = sext i32 %j.0 to i64
   %9 = mul nsw i64 %idxprom11, %2
   %arrayidx12 = getelementptr inbounds double, double* %arrayidx10, i64 %9
   %idxprom13 = sext i32 %k.0 to i64
   %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
   store double %add8, double* %arrayidx14, align 8
   br label %for.inc

 for.inc:
   %inc = add nsw i32 %k.0, 1
   %cmp6 = icmp slt i32 %inc, %nk
   br i1 %cmp6, label %imperf_nest_4_loop_k, label %for.cond5.for.end_crit_edge

 for.cond5.for.end_crit_edge:
   br label %for.end

 for.end:
   br label %for.inc15

 for.inc15:
   %inc16 = add nsw i32 %j.0, 1
   %sub = sub nsw i32 %ny, %nk
   %cmp3 = icmp slt i32 %inc16, %sub
   br i1 %cmp3, label %imperf_nest_4_loop_j, label %for.cond2.for.end17_crit_edge

 for.cond2.for.end17_crit_edge:
   br label %for.end17

 for.end17:
   %sub18 = sub nsw i32 %ny, %nk
   %cmp204 = icmp slt i32 %sub18, %ny
   br i1 %cmp204, label %imperf_nest_4_loop_j2.lr.ph, label %for.end34

 imperf_nest_4_loop_j2.lr.ph:
   br label %imperf_nest_4_loop_j2

 imperf_nest_4_loop_j2:
   %j.1 = phi i32 [ %sub18, %imperf_nest_4_loop_j2.lr.ph ], [ %inc33, %for.inc32 ]
   %idxprom23 = sext i32 %i.0 to i64
   %arrayidx24 = getelementptr inbounds double, double* %vla1, i64 %idxprom23
   %10 = load double, double* %arrayidx24, align 8
   %conv25 = sitofp i32 %j.1 to double
   %sub26 = fsub double %10, %conv25
   %idxprom27 = sext i32 %i.0 to i64
   %idxprom29 = sext i32 %j.1 to i64
   %11 = mul nsw i64 %idxprom29, %2
   %12 = mul nuw i64 %1, %2
   %13 = mul nsw i64 %idxprom27, %12
   %arrayidx28 = getelementptr inbounds double, double* %vla, i64 %13
   %arrayidx30 = getelementptr inbounds double, double* %arrayidx28, i64 %11
   %arrayidx31 = getelementptr inbounds double, double* %arrayidx30, i64 0
   store double %sub26, double* %arrayidx31, align 8
   br label %for.inc32

 for.inc32:
   %inc33 = add nsw i32 %j.1, 1
   %cmp20 = icmp slt i32 %inc33, %ny
   br i1 %cmp20, label %imperf_nest_4_loop_j2, label %for.cond19.for.end34_crit_edge

 for.cond19.for.end34_crit_edge:
   br label %for.end34

 for.end34:
   br label %for.inc35

 for.inc35:
   %inc36 = add nsw i32 %i.0, 1
   %cmp = icmp slt i32 %inc36, %nx
   br i1 %cmp, label %imperf_nest_4_loop_i, label %for.cond.for.end37_crit_edge

 for.cond.for.end37_crit_edge:
   br label %for.end37

 for.end37:
   ret void
 }

 ; Test an imperfect loop nest of the form:
 ;   for (int i = 0; i < nx; ++i)
 ;     if (i > 5) {
 ;       for (int j = 0; j < ny; ++j)
 ;         y[j][i] = x[i][j] + j;
 ;     }

 define void @imperf_nest_5(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_5_loop_i, Loops: ( imperf_nest_5_loop_i imperf_nest_5_loop_j )
 entry:
   %cmp2 = icmp slt i32 0, %nx
   br i1 %cmp2, label %imperf_nest_5_loop_i.lr.ph, label %for.end13

 imperf_nest_5_loop_i.lr.ph:
   br label %imperf_nest_5_loop_i

 imperf_nest_5_loop_i:
   %i.0 = phi i32 [ 0, %imperf_nest_5_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
   %cmp1 = icmp sgt i32 %i.0, 5
   br i1 %cmp1, label %if.then, label %if.end

 if.then:
   %cmp31 = icmp slt i32 0, %ny
   br i1 %cmp31, label %imperf_nest_5_loop_j.lr.ph, label %for.end

 imperf_nest_5_loop_j.lr.ph:
   br label %imperf_nest_5_loop_j

 imperf_nest_5_loop_j:
   %j.0 = phi i32 [ 0, %imperf_nest_5_loop_j.lr.ph ], [ %inc, %for.inc ]
   %idxprom = sext i32 %i.0 to i64
   %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
   %0 = load i32*, i32** %arrayidx, align 8
   %idxprom5 = sext i32 %j.0 to i64
   %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
   %1 = load i32, i32* %arrayidx6, align 4
   %add = add nsw i32 %1, %j.0
   %idxprom7 = sext i32 %j.0 to i64
   %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
   %2 = load i32*, i32** %arrayidx8, align 8
   %idxprom9 = sext i32 %i.0 to i64
   %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
   store i32 %add, i32* %arrayidx10, align 4
   br label %for.inc

 for.inc:
   %inc = add nsw i32 %j.0, 1
   %cmp3 = icmp slt i32 %inc, %ny
   br i1 %cmp3, label %imperf_nest_5_loop_j, label %for.cond2.for.end_crit_edge

 for.cond2.for.end_crit_edge:
   br label %for.end

 for.end:
   br label %if.end

 if.end:
   br label %for.inc11

 for.inc11:
   %inc12 = add nsw i32 %i.0, 1
   %cmp = icmp slt i32 %inc12, %nx
   br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge

 for.cond.for.end13_crit_edge:
   br label %for.end13

 for.end13:
   ret void
 }

 ; Test an imperfect loop nest of the form:
 ;   for (int i = 0; i < nx; ++i)
 ;     if (i > 5) { // user branch
 ;       for (int j = 1; j <= 5; j+=2)
 ;         y[j][i] = x[i][j] + j;
 ;     }

 define void @imperf_nest_6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
 ;    CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_6_loop_i, Loops: ( imperf_nest_6_loop_i imperf_nest_6_loop_j )
 entry:
   %cmp2 = icmp slt i32 0, %nx
   br i1 %cmp2, label %imperf_nest_6_loop_i.lr.ph, label %for.end13

 imperf_nest_6_loop_i.lr.ph:
   br label %imperf_nest_6_loop_i

 imperf_nest_6_loop_i:
   %i.0 = phi i32 [ 0, %imperf_nest_6_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
   %cmp1 = icmp sgt i32 %i.0, 5
   br i1 %cmp1, label %imperf_nest_6_loop_j.lr.ph, label %if.end

 imperf_nest_6_loop_j.lr.ph:
   br label %imperf_nest_6_loop_j

 imperf_nest_6_loop_j:
   %j.0 = phi i32 [ 1, %imperf_nest_6_loop_j.lr.ph ], [ %inc, %for.inc ]
   %idxprom = sext i32 %i.0 to i64
   %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
   %0 = load i32*, i32** %arrayidx, align 8
   %idxprom5 = sext i32 %j.0 to i64
   %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
   %1 = load i32, i32* %arrayidx6, align 4
   %add = add nsw i32 %1, %j.0
   %idxprom7 = sext i32 %j.0 to i64
   %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
   %2 = load i32*, i32** %arrayidx8, align 8
   %idxprom9 = sext i32 %i.0 to i64
   %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
   store i32 %add, i32* %arrayidx10, align 4
   br label %for.inc

 for.inc:
   %inc = add nsw i32 %j.0, 2
   %cmp3 = icmp sle i32 %inc, 5
   br i1 %cmp3, label %imperf_nest_6_loop_j, label %for.cond2.for.end_crit_edge

 for.cond2.for.end_crit_edge:
   br label %for.end

 for.end:
   br label %if.end

 if.end:
   br label %for.inc11

 for.inc11:
   %inc12 = add nsw i32 %i.0, 1
   %cmp = icmp slt i32 %inc12, %nx
   br i1 %cmp, label %imperf_nest_6_loop_i, label %for.cond.for.end13_crit_edge

 for.cond.for.end13_crit_edge:
   br label %for.end13

 for.end13:
   ret void
 }
	; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 \| FileCheck %s

	; Test an imperfect 2-dim loop nest of the form:
	; for (int i = 0; i < nx; ++i) {
	; x[i] = i;
	; for (int j = 0; j < ny; ++j)
	; y[j][i] = x[i] + j;
	; }

	define void @imperf_nest_1(i32 signext %nx, i32 signext %ny) {
	; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_1_loop_i, Loops: ( imperf_nest_1_loop_i imperf_nest_1_loop_j )
	entry:
	%0 = zext i32 %ny to i64
	%1 = zext i32 %nx to i64
	%2 = mul nuw i64 %0, %1
	%vla = alloca double, i64 %2, align 8
	%3 = zext i32 %ny to i64
	%vla1 = alloca double, i64 %3, align 8
	br label %imperf_nest_1_loop_i

	imperf_nest_1_loop_i:
	%i2.0 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]
	%cmp = icmp slt i32 %i2.0, %nx
	br i1 %cmp, label %for.body, label %for.end17

	for.body:
	%conv = sitofp i32 %i2.0 to double
	%idxprom = sext i32 %i2.0 to i64
	%arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
	store double %conv, double* %arrayidx, align 8
	br label %imperf_nest_1_loop_j

	imperf_nest_1_loop_j:
	%j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
	%cmp5 = icmp slt i32 %j3.0, %ny
	br i1 %cmp5, label %for.body7, label %for.end

	for.body7:
	%idxprom8 = sext i32 %i2.0 to i64
	%arrayidx9 = getelementptr inbounds double, double* %vla1, i64 %idxprom8
	%4 = load double, double* %arrayidx9, align 8
	%conv10 = sitofp i32 %j3.0 to double
	%add = fadd double %4, %conv10
	%idxprom11 = sext i32 %j3.0 to i64
	%5 = mul nsw i64 %idxprom11, %1
	%arrayidx12 = getelementptr inbounds double, double* %vla, i64 %5
	%idxprom13 = sext i32 %i2.0 to i64
	%arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
	store double %add, double* %arrayidx14, align 8
	br label %for.inc

	for.inc:
	%inc = add nsw i32 %j3.0, 1
	br label %imperf_nest_1_loop_j

	for.end:
	br label %for.inc15

	for.inc15:
	%inc16 = add nsw i32 %i2.0, 1
	br label %imperf_nest_1_loop_i

	for.end17:
	ret void
	}

	; Test an imperfect 2-dim loop nest of the form:
	; for (int i = 0; i < nx; ++i) {
	; for (int j = 0; j < ny; ++j)
	; y[j][i] = x[i] + j;
	; y[0][i] += i;
	; }

	define void @imperf_nest_2(i32 signext %nx, i32 signext %ny) {
	; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_2_loop_i, Loops: ( imperf_nest_2_loop_i imperf_nest_2_loop_j )
	entry:
	%0 = zext i32 %ny to i64
	%1 = zext i32 %nx to i64
	%2 = mul nuw i64 %0, %1
	%vla = alloca double, i64 %2, align 8
	%3 = zext i32 %ny to i64
	%vla1 = alloca double, i64 %3, align 8
	br label %imperf_nest_2_loop_i

	imperf_nest_2_loop_i:
	%i2.0 = phi i32 [ 0, %entry ], [ %inc17, %for.inc16 ]
	%cmp = icmp slt i32 %i2.0, %nx
	br i1 %cmp, label %for.body, label %for.end18

	for.body:
	br label %imperf_nest_2_loop_j

	imperf_nest_2_loop_j:
	%j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
	%cmp5 = icmp slt i32 %j3.0, %ny
	br i1 %cmp5, label %for.body6, label %for.end

	for.body6:
	%idxprom = sext i32 %i2.0 to i64
	%arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
	%4 = load double, double* %arrayidx, align 8
	%conv = sitofp i32 %j3.0 to double
	%add = fadd double %4, %conv
	%idxprom7 = sext i32 %j3.0 to i64
	%5 = mul nsw i64 %idxprom7, %1
	%arrayidx8 = getelementptr inbounds double, double* %vla, i64 %5
	%idxprom9 = sext i32 %i2.0 to i64
	%arrayidx10 = getelementptr inbounds double, double* %arrayidx8, i64 %idxprom9
	store double %add, double* %arrayidx10, align 8
	br label %for.inc

	for.inc:
	%inc = add nsw i32 %j3.0, 1
	br label %imperf_nest_2_loop_j

	for.end:
	%conv11 = sitofp i32 %i2.0 to double
	%6 = mul nsw i64 0, %1
	%arrayidx12 = getelementptr inbounds double, double* %vla, i64 %6
	%idxprom13 = sext i32 %i2.0 to i64
	%arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
	%7 = load double, double* %arrayidx14, align 8
	%add15 = fadd double %7, %conv11
	store double %add15, double* %arrayidx14, align 8
	br label %for.inc16

	for.inc16:
	%inc17 = add nsw i32 %i2.0, 1
	br label %imperf_nest_2_loop_i

	for.end18:
	ret void
	}

	; Test an imperfect 2-dim loop nest of the form:
	; for (i = 0; i < nx; ++i) {
	; for (j = 0; j < ny-nk; ++j)
	; y[i][j] = x[i] + j;
	; for (j = ny-nk; j < ny; ++j)
	; y[i][j] = x[i] - j;
	; }

	define void @imperf_nest_3(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
	; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_3_loop_i, Loops: ( imperf_nest_3_loop_i imperf_nest_3_loop_j imperf_nest_3_loop_k )
	entry:
	%0 = zext i32 %nx to i64
	%1 = zext i32 %ny to i64
	%2 = mul nuw i64 %0, %1
	%vla = alloca double, i64 %2, align 8
	%3 = zext i32 %ny to i64
	%vla1 = alloca double, i64 %3, align 8
	br label %imperf_nest_3_loop_i

	imperf_nest_3_loop_i: ; preds = %for.inc25, %entry
	%i.0 = phi i32 [ 0, %entry ], [ %inc26, %for.inc25 ]
	%cmp = icmp slt i32 %i.0, %nx
	br i1 %cmp, label %for.body, label %for.end27

	for.body: ; preds = %for.cond
	br label %imperf_nest_3_loop_j

	imperf_nest_3_loop_j: ; preds = %for.inc, %for.body
	%j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
	%sub = sub nsw i32 %ny, %nk
	%cmp3 = icmp slt i32 %j.0, %sub
	br i1 %cmp3, label %for.body4, label %for.end

	for.body4: ; preds = %imperf_nest_3_loop_j
	%idxprom = sext i32 %i.0 to i64
	%arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
	%4 = load double, double* %arrayidx, align 8
	%conv = sitofp i32 %j.0 to double
	%add = fadd double %4, %conv
	%idxprom5 = sext i32 %i.0 to i64
	%5 = mul nsw i64 %idxprom5, %1
	%arrayidx6 = getelementptr inbounds double, double* %vla, i64 %5
	%idxprom7 = sext i32 %j.0 to i64
	%arrayidx8 = getelementptr inbounds double, double* %arrayidx6, i64 %idxprom7
	store double %add, double* %arrayidx8, align 8
	br label %for.inc

	for.inc: ; preds = %for.body4
	%inc = add nsw i32 %j.0, 1
	br label %imperf_nest_3_loop_j

	for.end: ; preds = %imperf_nest_3_loop_j
	%sub9 = sub nsw i32 %ny, %nk
	br label %imperf_nest_3_loop_k

	imperf_nest_3_loop_k: ; preds = %for.inc22, %for.end
	%j.1 = phi i32 [ %sub9, %for.end ], [ %inc23, %for.inc22 ]
	%cmp11 = icmp slt i32 %j.1, %ny
	br i1 %cmp11, label %for.body13, label %for.end24

	for.body13: ; preds = %imperf_nest_3_loop_k
	%idxprom14 = sext i32 %i.0 to i64
	%arrayidx15 = getelementptr inbounds double, double* %vla1, i64 %idxprom14
	%6 = load double, double* %arrayidx15, align 8
	%conv16 = sitofp i32 %j.1 to double
	%sub17 = fsub double %6, %conv16
	%idxprom18 = sext i32 %i.0 to i64
	%7 = mul nsw i64 %idxprom18, %1
	%arrayidx19 = getelementptr inbounds double, double* %vla, i64 %7
	%idxprom20 = sext i32 %j.1 to i64
	%arrayidx21 = getelementptr inbounds double, double* %arrayidx19, i64 %idxprom20
	store double %sub17, double* %arrayidx21, align 8
	br label %for.inc22

	for.inc22: ; preds = %for.body13
	%inc23 = add nsw i32 %j.1, 1
	br label %imperf_nest_3_loop_k

	for.end24: ; preds = %imperf_nest_3_loop_k
	br label %for.inc25

	for.inc25: ; preds = %for.end24
	%inc26 = add nsw i32 %i.0, 1
	br label %imperf_nest_3_loop_i

	for.end27: ; preds = %for.cond
	ret void
	}

	; Test an imperfect loop nest of the form:
	; for (i = 0; i < nx; ++i) {
	; for (j = 0; j < ny-nk; ++j)
	; for (k = 0; k < nk; ++k)
	; y[i][j][k] = x[i+j] + k;
	; for (j = ny-nk; j < ny; ++j)
	; y[i][j][0] = x[i] - j;
	; }

	define void @imperf_nest_4(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
	; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_4_loop_j, Loops: ( imperf_nest_4_loop_j imperf_nest_4_loop_k )
	; CHECK-LABEL: IsPerfect=false, Depth=3, OutermostLoop: imperf_nest_4_loop_i, Loops: ( imperf_nest_4_loop_i imperf_nest_4_loop_j imperf_nest_4_loop_j2 imperf_nest_4_loop_k )
	entry:
	%0 = zext i32 %nx to i64
	%1 = zext i32 %ny to i64
	%2 = zext i32 %nk to i64
	%3 = mul nuw i64 %0, %1
	%4 = mul nuw i64 %3, %2
	%vla = alloca double, i64 %4, align 8
	%5 = zext i32 %ny to i64
	%vla1 = alloca double, i64 %5, align 8
	%cmp5 = icmp slt i32 0, %nx
	br i1 %cmp5, label %imperf_nest_4_loop_i.lr.ph, label %for.end37

	imperf_nest_4_loop_i.lr.ph:
	br label %imperf_nest_4_loop_i

	imperf_nest_4_loop_i:
	%i.0 = phi i32 [ 0, %imperf_nest_4_loop_i.lr.ph ], [ %inc36, %for.inc35 ]
	%sub2 = sub nsw i32 %ny, %nk
	%cmp33 = icmp slt i32 0, %sub2
	br i1 %cmp33, label %imperf_nest_4_loop_j.lr.ph, label %for.end17

	imperf_nest_4_loop_j.lr.ph:
	br label %imperf_nest_4_loop_j

	imperf_nest_4_loop_j:
	%j.0 = phi i32 [ 0, %imperf_nest_4_loop_j.lr.ph ], [ %inc16, %for.inc15 ]
	%cmp61 = icmp slt i32 0, %nk
	br i1 %cmp61, label %imperf_nest_4_loop_k.lr.ph, label %for.end

	imperf_nest_4_loop_k.lr.ph:
	br label %imperf_nest_4_loop_k

	imperf_nest_4_loop_k:
	%k.0 = phi i32 [ 0, %imperf_nest_4_loop_k.lr.ph ], [ %inc, %for.inc ]
	%add = add nsw i32 %i.0, %j.0
	%idxprom = sext i32 %add to i64
	%arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
	%6 = load double, double* %arrayidx, align 8
	%conv = sitofp i32 %k.0 to double
	%add8 = fadd double %6, %conv
	%idxprom9 = sext i32 %i.0 to i64
	%7 = mul nuw i64 %1, %2
	%8 = mul nsw i64 %idxprom9, %7
	%arrayidx10 = getelementptr inbounds double, double* %vla, i64 %8
	%idxprom11 = sext i32 %j.0 to i64
	%9 = mul nsw i64 %idxprom11, %2
	%arrayidx12 = getelementptr inbounds double, double* %arrayidx10, i64 %9
	%idxprom13 = sext i32 %k.0 to i64
	%arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
	store double %add8, double* %arrayidx14, align 8
	br label %for.inc

	for.inc:
	%inc = add nsw i32 %k.0, 1
	%cmp6 = icmp slt i32 %inc, %nk
	br i1 %cmp6, label %imperf_nest_4_loop_k, label %for.cond5.for.end_crit_edge

	for.cond5.for.end_crit_edge:
	br label %for.end

	for.end:
	br label %for.inc15

	for.inc15:
	%inc16 = add nsw i32 %j.0, 1
	%sub = sub nsw i32 %ny, %nk
	%cmp3 = icmp slt i32 %inc16, %sub
	br i1 %cmp3, label %imperf_nest_4_loop_j, label %for.cond2.for.end17_crit_edge

	for.cond2.for.end17_crit_edge:
	br label %for.end17

	for.end17:
	%sub18 = sub nsw i32 %ny, %nk
	%cmp204 = icmp slt i32 %sub18, %ny
	br i1 %cmp204, label %imperf_nest_4_loop_j2.lr.ph, label %for.end34

	imperf_nest_4_loop_j2.lr.ph:
	br label %imperf_nest_4_loop_j2

	imperf_nest_4_loop_j2:
	%j.1 = phi i32 [ %sub18, %imperf_nest_4_loop_j2.lr.ph ], [ %inc33, %for.inc32 ]
	%idxprom23 = sext i32 %i.0 to i64
	%arrayidx24 = getelementptr inbounds double, double* %vla1, i64 %idxprom23
	%10 = load double, double* %arrayidx24, align 8
	%conv25 = sitofp i32 %j.1 to double
	%sub26 = fsub double %10, %conv25
	%idxprom27 = sext i32 %i.0 to i64
	%idxprom29 = sext i32 %j.1 to i64
	%11 = mul nsw i64 %idxprom29, %2
	%12 = mul nuw i64 %1, %2
	%13 = mul nsw i64 %idxprom27, %12
	%arrayidx28 = getelementptr inbounds double, double* %vla, i64 %13
	%arrayidx30 = getelementptr inbounds double, double* %arrayidx28, i64 %11
	%arrayidx31 = getelementptr inbounds double, double* %arrayidx30, i64 0
	store double %sub26, double* %arrayidx31, align 8
	br label %for.inc32

	for.inc32:
	%inc33 = add nsw i32 %j.1, 1
	%cmp20 = icmp slt i32 %inc33, %ny
	br i1 %cmp20, label %imperf_nest_4_loop_j2, label %for.cond19.for.end34_crit_edge

	for.cond19.for.end34_crit_edge:
	br label %for.end34

	for.end34:
	br label %for.inc35

	for.inc35:
	%inc36 = add nsw i32 %i.0, 1
	%cmp = icmp slt i32 %inc36, %nx
	br i1 %cmp, label %imperf_nest_4_loop_i, label %for.cond.for.end37_crit_edge

	for.cond.for.end37_crit_edge:
	br label %for.end37

	for.end37:
	ret void
	}

	; Test an imperfect loop nest of the form:
	; for (int i = 0; i < nx; ++i)
	; if (i > 5) {
	; for (int j = 0; j < ny; ++j)
	; y[j][i] = x[i][j] + j;
	; }

	define void @imperf_nest_5(i32 %y, i32 %x, i32 signext %nx, i32 signext %ny) {
	; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_5_loop_i, Loops: ( imperf_nest_5_loop_i imperf_nest_5_loop_j )
	entry:
	%cmp2 = icmp slt i32 0, %nx
	br i1 %cmp2, label %imperf_nest_5_loop_i.lr.ph, label %for.end13

	imperf_nest_5_loop_i.lr.ph:
	br label %imperf_nest_5_loop_i

	imperf_nest_5_loop_i:
	%i.0 = phi i32 [ 0, %imperf_nest_5_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
	%cmp1 = icmp sgt i32 %i.0, 5
	br i1 %cmp1, label %if.then, label %if.end

	if.then:
	%cmp31 = icmp slt i32 0, %ny
	br i1 %cmp31, label %imperf_nest_5_loop_j.lr.ph, label %for.end

	imperf_nest_5_loop_j.lr.ph:
	br label %imperf_nest_5_loop_j

	imperf_nest_5_loop_j:
	%j.0 = phi i32 [ 0, %imperf_nest_5_loop_j.lr.ph ], [ %inc, %for.inc ]
	%idxprom = sext i32 %i.0 to i64
	%arrayidx = getelementptr inbounds i32, i32* %x, i64 %idxprom
	%0 = load i32, i32* %arrayidx, align 8
	%idxprom5 = sext i32 %j.0 to i64
	%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
	%1 = load i32, i32* %arrayidx6, align 4
	%add = add nsw i32 %1, %j.0
	%idxprom7 = sext i32 %j.0 to i64
	%arrayidx8 = getelementptr inbounds i32, i32* %y, i64 %idxprom7
	%2 = load i32, i32* %arrayidx8, align 8
	%idxprom9 = sext i32 %i.0 to i64
	%arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
	store i32 %add, i32* %arrayidx10, align 4
	br label %for.inc

	for.inc:
	%inc = add nsw i32 %j.0, 1
	%cmp3 = icmp slt i32 %inc, %ny
	br i1 %cmp3, label %imperf_nest_5_loop_j, label %for.cond2.for.end_crit_edge

	for.cond2.for.end_crit_edge:
	br label %for.end

	for.end:
	br label %if.end

	if.end:
	br label %for.inc11

	for.inc11:
	%inc12 = add nsw i32 %i.0, 1
	%cmp = icmp slt i32 %inc12, %nx
	br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge

	for.cond.for.end13_crit_edge:
	br label %for.end13

	for.end13:
	ret void
	}

	; Test an imperfect loop nest of the form:
	; for (int i = 0; i < nx; ++i)
	; if (i > 5) { // user branch
	; for (int j = 1; j <= 5; j+=2)
	; y[j][i] = x[i][j] + j;
	; }

	define void @imperf_nest_6(i32 %y, i32 %x, i32 signext %nx, i32 signext %ny) {
	; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_6_loop_i, Loops: ( imperf_nest_6_loop_i imperf_nest_6_loop_j )
	entry:
	%cmp2 = icmp slt i32 0, %nx
	br i1 %cmp2, label %imperf_nest_6_loop_i.lr.ph, label %for.end13

	imperf_nest_6_loop_i.lr.ph:
	br label %imperf_nest_6_loop_i

	imperf_nest_6_loop_i:
	%i.0 = phi i32 [ 0, %imperf_nest_6_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
	%cmp1 = icmp sgt i32 %i.0, 5
	br i1 %cmp1, label %imperf_nest_6_loop_j.lr.ph, label %if.end

	imperf_nest_6_loop_j.lr.ph:
	br label %imperf_nest_6_loop_j

	imperf_nest_6_loop_j:
	%j.0 = phi i32 [ 1, %imperf_nest_6_loop_j.lr.ph ], [ %inc, %for.inc ]
	%idxprom = sext i32 %i.0 to i64
	%arrayidx = getelementptr inbounds i32, i32* %x, i64 %idxprom
	%0 = load i32, i32* %arrayidx, align 8
	%idxprom5 = sext i32 %j.0 to i64
	%arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
	%1 = load i32, i32* %arrayidx6, align 4
	%add = add nsw i32 %1, %j.0
	%idxprom7 = sext i32 %j.0 to i64
	%arrayidx8 = getelementptr inbounds i32, i32* %y, i64 %idxprom7
	%2 = load i32, i32* %arrayidx8, align 8
	%idxprom9 = sext i32 %i.0 to i64
	%arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
	store i32 %add, i32* %arrayidx10, align 4
	br label %for.inc

	for.inc:
	%inc = add nsw i32 %j.0, 2
	%cmp3 = icmp sle i32 %inc, 5
	br i1 %cmp3, label %imperf_nest_6_loop_j, label %for.cond2.for.end_crit_edge

	for.cond2.for.end_crit_edge:
	br label %for.end

	for.end:
	br label %if.end

	if.end:
	br label %for.inc11

	for.inc11:
	%inc12 = add nsw i32 %i.0, 1
	%cmp = icmp slt i32 %inc12, %nx
	br i1 %cmp, label %imperf_nest_6_loop_i, label %for.cond.for.end13_crit_edge

	for.cond.for.end13_crit_edge:
	br label %for.end13

	for.end13:
	ret void
	}