249 lines · plain
1; RUN: opt -S -passes='print<loopnest>' < %s 2>&1 > /dev/null | FileCheck %s2 3; int f(int N, int M) {4; int res = 0;5; for (int i = 0; i < N; ++i) {6; for (int j = 0; j < M; ++j) res += i * j;7; }8; return res;9; }10 11define i32 @f(i32 %N, i32 %M) #0 {12; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.j, Loops: ( for.j )13; CHECK: IsPerfect=true, Depth=2, OutermostLoop: for.i, Loops: ( for.i for.j )14entry:15 %cmp4 = icmp slt i32 0, %N16 br i1 %cmp4, label %for.i.ph, label %for.i.end17 18for.i.ph: ; preds = %entry19 br label %for.i20 21for.i: ; preds = %for.i.ph, %for.i.inc22 %i.06 = phi i32 [ 0, %for.i.ph ], [ %inc5, %for.i.inc ]23 %res.05 = phi i32 [ 0, %for.i.ph ], [ %res.1.lcssa, %for.i.inc ]24 %cmp21 = icmp slt i32 0, %M25 br i1 %cmp21, label %for.j.ph, label %for.j.end26 27for.j.ph: ; preds = %for.i28 br label %for.j29 30for.j: ; preds = %for.j.ph, %for.j.inc31 %j.03 = phi i32 [ 0, %for.j.ph ], [ %inc, %for.j.inc ]32 %res.12 = phi i32 [ %res.05, %for.j.ph ], [ %add, %for.j.inc ]33 %mul = mul nsw i32 %i.06, %j.0334 %add = add nsw i32 %res.12, %mul35 br label %for.j.inc36 37for.j.inc: ; preds = %for.j38 %inc = add nsw i32 %j.03, 139 %cmp2 = icmp slt i32 %inc, %M40 br i1 %cmp2, label %for.j, label %for.j.end_crit_edge41 42for.j.end_crit_edge: ; preds = %for.j.inc43 %split = phi i32 [ %add, %for.j.inc ]44 br label %for.j.end45 46for.j.end: ; preds = %for.j.end_crit_edge, %for.i47 %res.1.lcssa = phi i32 [ %split, %for.j.end_crit_edge ], [ %res.05, %for.i ]48 br label %for.i.inc49 50for.i.inc: ; preds = %for.j.end51 %inc5 = add nsw i32 %i.06, 152 %cmp = icmp slt i32 %inc5, %N53 br i1 %cmp, label %for.i, label %for.i.end_crit_edge54 55for.i.end_crit_edge: ; preds = %for.i.inc56 %split7 = phi i32 [ %res.1.lcssa, %for.i.inc ]57 br label %for.i.end58 59for.i.end: ; preds = %for.i.end_crit_edge, %entry60 %res.0.lcssa = phi i32 [ %split7, %for.i.end_crit_edge ], [ 0, %entry ]61 ret i32 %res.0.lcssa62}63 64; int g(int N, int M, int K) {65; int sum = 0, prod = 1;66; for (int i = 0; i < N; ++i) {67; for (int j = 0; j < M; ++j) {68; for (int k = 0; k < K; ++k) {69; sum += i * j * k;70; }71; prod *= (i + j);72; }73; }74; return sum + prod;75; }76define i32 @g(i32 %N, i32 %M, i32 %K) #0 {77; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.k, Loops: ( for.k )78; CHECK: IsPerfect=false, Depth=2, OutermostLoop: for.j, Loops: ( for.j for.k )79; CHECK: IsPerfect=false, Depth=3, OutermostLoop: for.i, Loops: ( for.i for.j for.k )80entry:81 %cmp10 = icmp slt i32 0, %N82 br i1 %cmp10, label %for.i.ph, label %for.i.end83 84for.i.ph: ; preds = %entry85 br label %for.i86 87for.i: ; preds = %for.i.ph, %for.i.inc88 %i.013 = phi i32 [ 0, %for.i.ph ], [ %inc14, %for.i.inc ]89 %sum.012 = phi i32 [ 0, %for.i.ph ], [ %sum.1.lcssa, %for.i.inc ]90 %prod.011 = phi i32 [ 1, %for.i.ph ], [ %prod.1.lcssa, %for.i.inc ]91 %cmp24 = icmp slt i32 0, %M92 br i1 %cmp24, label %for.j.ph, label %for.j.end93 94for.j.ph: ; preds = %for.i95 br label %for.j96 97for.j: ; preds = %for.j.ph, %for.j.inc98 %j.07 = phi i32 [ 0, %for.j.ph ], [ %inc11, %for.j.inc ]99 %sum.16 = phi i32 [ %sum.012, %for.j.ph ], [ %sum.2.lcssa, %for.j.inc ]100 %prod.15 = phi i32 [ %prod.011, %for.j.ph ], [ %mul9, %for.j.inc ]101 %cmp51 = icmp slt i32 0, %K102 br i1 %cmp51, label %for.k.ph, label %for.k.end103 104for.k.ph: ; preds = %for.j105 br label %for.k106 107for.k: ; preds = %for.k.ph, %for.k.inc108 %k.03 = phi i32 [ 0, %for.k.ph ], [ %inc, %for.k.inc ]109 %sum.22 = phi i32 [ %sum.16, %for.k.ph ], [ %add, %for.k.inc ]110 %mul = mul nsw i32 %i.013, %j.07111 %mul7 = mul nsw i32 %mul, %k.03112 %add = add nsw i32 %sum.22, %mul7113 br label %for.k.inc114 115for.k.inc: ; preds = %for.k116 %inc = add nsw i32 %k.03, 1117 %cmp5 = icmp slt i32 %inc, %K118 br i1 %cmp5, label %for.k, label %for.k.end_crit_edge119 120for.k.end_crit_edge: ; preds = %for.k.inc121 %split = phi i32 [ %add, %for.k.inc ]122 br label %for.k.end123 124for.k.end: ; preds = %for.k.end_crit_edge, %for.j125 %sum.2.lcssa = phi i32 [ %split, %for.k.end_crit_edge ], [ %sum.16, %for.j ]126 %add8 = add nsw i32 %i.013, %j.07127 %mul9 = mul nsw i32 %prod.15, %add8128 br label %for.j.inc129 130for.j.inc: ; preds = %for.k.end131 %inc11 = add nsw i32 %j.07, 1132 %cmp2 = icmp slt i32 %inc11, %M133 br i1 %cmp2, label %for.j, label %for.j.end_crit_edge134 135for.j.end_crit_edge: ; preds = %for.j.inc136 %split8 = phi i32 [ %mul9, %for.j.inc ]137 %split9 = phi i32 [ %sum.2.lcssa, %for.j.inc ]138 br label %for.j.end139 140for.j.end: ; preds = %for.j.end1crit_edge, %for.i141 %prod.1.lcssa = phi i32 [ %split8, %for.j.end_crit_edge ], [ %prod.011, %for.i ]142 %sum.1.lcssa = phi i32 [ %split9, %for.j.end_crit_edge ], [ %sum.012, %for.i ]143 br label %for.i.inc144 145for.i.inc: ; preds = %for.j.end146 %inc14 = add nsw i32 %i.013, 1147 %cmp = icmp slt i32 %inc14, %N148 br i1 %cmp, label %for.i, label %for.i.end_crit_edge149 150for.i.end_crit_edge: ; preds = %for.i.inc151 %split14 = phi i32 [ %prod.1.lcssa, %for.i.inc ]152 %split15 = phi i32 [ %sum.1.lcssa, %for.i.inc ]153 br label %for.i.end154 155for.i.end: ; preds = %for.i.end_crit_edge, %entry156 %prod.0.lcssa = phi i32 [ %split14, %for.i.end_crit_edge ], [ 1, %entry ]157 %sum.0.lcssa = phi i32 [ %split15, %for.i.end_crit_edge ], [ 0, %entry ]158 %add16 = add nsw i32 %sum.0.lcssa, %prod.0.lcssa159 ret i32 %add16160}161 162; int h(int N, int M, int K) {163; int sum = 0;164; for (int i = 0; i < N; ++i) {165; for (int j = 0; j < M; ++j) {166; for (int k = 0; k < K; ++k) {167; sum += i * j * k;168; }169; }170; }171; return sum;172; }173define i32 @h(i32 %N, i32 %M, i32 %K) #0 {174; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.k, Loops: ( for.k )175; CHECK: IsPerfect=true, Depth=2, OutermostLoop: for.j, Loops: ( for.j for.k )176; CHECK: IsPerfect=true, Depth=3, OutermostLoop: for.i, Loops: ( for.i for.j for.k )177entry:178 %cmp8 = icmp slt i32 0, %N179 br i1 %cmp8, label %for.i.ph, label %for.i.end180 181for.i.ph: ; preds = %entry182 br label %for.i183 184for.i: ; preds = %for.i.ph, %for.i.inc185 %i.010 = phi i32 [ 0, %for.i.ph ], [ %inc12, %for.i.inc ]186 %sum.09 = phi i32 [ 0, %for.i.ph ], [ %sum.1.lcssa, %for.i.inc ]187 %cmp24 = icmp slt i32 0, %M188 br i1 %cmp24, label %for.j.ph, label %for.j.end189 190for.j.ph: ; preds = %for.i191 br label %for.j192 193for.j: ; preds = %for.j.ph, %for.j.inc194 %j.06 = phi i32 [ 0, %for.j.ph ], [ %inc9, %for.j.inc ]195 %sum.15 = phi i32 [ %sum.09, %for.j.ph ], [ %sum.2.lcssa, %for.j.inc ]196 %cmp51 = icmp slt i32 0, %K197 br i1 %cmp51, label %for.k.ph, label %for.k.end198 199for.k.ph: ; preds = %for.j200 br label %for.k201 202for.k: ; preds = %for.k.ph, %for.k.inc203 %k.03 = phi i32 [ 0, %for.k.ph ], [ %inc, %for.k.inc ]204 %sum.22 = phi i32 [ %sum.15, %for.k.ph ], [ %add, %for.k.inc ]205 %mul = mul nsw i32 %i.010, %j.06206 %mul7 = mul nsw i32 %mul, %k.03207 %add = add nsw i32 %sum.22, %mul7208 br label %for.k.inc209 210for.k.inc: ; preds = %for.k211 %inc = add nsw i32 %k.03, 1212 %cmp5 = icmp slt i32 %inc, %K213 br i1 %cmp5, label %for.k, label %for.k.end_crit_edge214 215for.k.end_crit_edge: ; preds = %for.k.inc216 %split = phi i32 [ %add, %for.k.inc ]217 br label %for.k.end218 219for.k.end: ; preds = %for.k.end_crit_edge, %for.j220 %sum.2.lcssa = phi i32 [ %split, %for.k.end_crit_edge ], [ %sum.15, %for.j ]221 br label %for.j.inc222 223for.j.inc: ; preds = %for.k.end224 %inc9 = add nsw i32 %j.06, 1225 %cmp2 = icmp slt i32 %inc9, %M226 br i1 %cmp2, label %for.j, label %for.j.end_crit_edge227 228for.j.end_crit_edge: ; preds = %for.j.inc229 %split7 = phi i32 [ %sum.2.lcssa, %for.j.inc ]230 br label %for.j.end231 232for.j.end: ; preds = %for.j.end_crit_edge, %for.i233 %sum.1.lcssa = phi i32 [ %split7, %for.j.end_crit_edge ], [ %sum.09, %for.i ]234 br label %for.i.inc235 236for.i.inc: ; preds = %for.j.end237 %inc12 = add nsw i32 %i.010, 1238 %cmp = icmp slt i32 %inc12, %N239 br i1 %cmp, label %for.i, label %for.i.end_crit_edge240 241for.i.end_crit_edge: ; preds = %for.i.inc242 %split11 = phi i32 [ %sum.1.lcssa, %for.i.inc ]243 br label %for.i.end244 245for.i.end: ; preds = %for.i.end_crit_edge, %entry246 %sum.0.lcssa = phi i32 [ %split11, %for.i.end_crit_edge ], [ 0, %entry ]247 ret i32 %sum.0.lcssa248}249