323 lines · plain
1; RUN: opt < %s -passes=loop-interchange -pass-remarks-output=%t -disable-output2; RUN: FileCheck -input-file %t %s3 4; This is a collection of cases where the loops were incorrectly interchanged5; due to mishandling of scalar dependencies.6 7;; The original code is as follows, with some simplifications from the one in8;; the issue #46867. The interchange is illegal due to the dependency of `s`.9;;10;; void issue46867(int *s, int c, int ff[4][9]) {11;; for (int d = 0; d <= 2; d++) {12;; for (int e = 0; e <= 2; e++) {13;; if ((long)(ff[e][d] && (*s = 3), c) % 4073709551606)14;; ++*s;15;; }16;; }17;; }18 19; CHECK: --- !Missed20; CHECK-NEXT: Pass: loop-interchange21; CHECK-NEXT: Name: Dependence22; CHECK-NEXT: Function: issue4686723; CHECK-NEXT: Args:24; CHECK-NEXT: - String: All loops have dependencies in all directions.25; CHECK: --- !Missed26; CHECK-NEXT: Pass: loop-interchange27; CHECK-NEXT: Name: Dependence28; CHECK-NEXT: Function: issue4686729; CHECK-NEXT: Args:30; CHECK-NEXT: - String: All loops have dependencies in all directions.31define void @issue46867(ptr noundef captures(none) %s, i32 noundef %c, ptr noundef readonly captures(none) %ff) {32entry:33 %tobool7.not = icmp eq i32 %c, 034 br i1 %tobool7.not, label %for.cond1.preheader.us.preheader, label %entry.split35 36for.cond1.preheader.us.preheader:37 br label %for.cond1.preheader.us38 39for.cond1.preheader.us:40 %indvars.iv31 = phi i64 [ 0, %for.cond1.preheader.us.preheader ], [ %indvars.iv.next32, %for.cond.cleanup3.split.us.us ]41 br label %for.body4.us.us42 43for.body4.us.us:44 %indvars.iv27 = phi i64 [ %indvars.iv.next28, %land.end.us.us ], [ 0, %for.cond1.preheader.us ]45 %arrayidx6.us.us = getelementptr inbounds nuw [9 x i32], ptr %ff, i64 %indvars.iv27, i64 %indvars.iv3146 %0 = load i32, ptr %arrayidx6.us.us, align 447 %tobool.not.us.us = icmp eq i32 %0, 048 br i1 %tobool.not.us.us, label %land.end.us.us, label %land.rhs.us.us49 50land.rhs.us.us:51 store i32 3, ptr %s, align 452 br label %land.end.us.us53 54land.end.us.us:55 %indvars.iv.next28 = add nuw nsw i64 %indvars.iv27, 156 %exitcond30 = icmp ne i64 %indvars.iv.next28, 357 br i1 %exitcond30, label %for.body4.us.us, label %for.cond.cleanup3.split.us.us58 59for.cond.cleanup3.split.us.us:60 %indvars.iv.next32 = add nuw nsw i64 %indvars.iv31, 161 %exitcond34 = icmp ne i64 %indvars.iv.next32, 362 br i1 %exitcond34, label %for.cond1.preheader.us, label %for.cond.cleanup.loopexit63 64entry.split:65 %s.promoted19 = load i32, ptr %s, align 466 br label %for.cond1.preheader67 68for.cond1.preheader:69 %indvars.iv23 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next24, %for.cond.cleanup3.split ]70 %s.promoted20 = phi i32 [ %s.promoted19, %entry.split ], [ %inc.lcssa, %for.cond.cleanup3.split ]71 br label %for.body472 73for.cond.cleanup.loopexit:74 br label %for.cond.cleanup75 76for.cond.cleanup.loopexit21:77 br label %for.cond.cleanup78 79for.cond.cleanup:80 ret void81 82for.cond.cleanup3.split:83 %inc.lcssa = phi i32 [ %inc, %land.end ]84 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 185 %exitcond26 = icmp ne i64 %indvars.iv.next24, 386 br i1 %exitcond26, label %for.cond1.preheader, label %for.cond.cleanup.loopexit2187 88for.body4:89 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %land.end ]90 %1 = phi i32 [ %s.promoted20, %for.cond1.preheader ], [ %inc, %land.end ]91 %arrayidx6 = getelementptr inbounds nuw [9 x i32], ptr %ff, i64 %indvars.iv, i64 %indvars.iv2392 %2 = load i32, ptr %arrayidx6, align 493 %tobool.not = icmp eq i32 %2, 094 br i1 %tobool.not, label %land.end, label %land.rhs95 96land.rhs:97 store i32 3, ptr %s, align 498 br label %land.end99 100land.end:101 %3 = phi i32 [ 3, %land.rhs ], [ %1, %for.body4 ]102 %inc = add nsw i32 %3, 1103 store i32 %inc, ptr %s, align 4104 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1105 %exitcond = icmp ne i64 %indvars.iv.next, 3106 br i1 %exitcond, label %for.body4, label %for.cond.cleanup3.split107}108 109 110;; The original code is as follows, with some simplifications from the one in111;; the issue #47401. The interchange is illegal due to the dependency of `e`.112;;113;; void issue47401(int *e, int bb[][8]) {114;; for (int c = 0; c <= 7; c++)115;; for (int d = 4; d; d--)116;; bb[d + 2][c] && (*e = bb[d][0]);117;; }118 119; CHECK: --- !Missed120; CHECK-NEXT: Pass: loop-interchange121; CHECK-NEXT: Name: Dependence122; CHECK-NEXT: Function: issue47401123; CHECK-NEXT: Args:124; CHECK-NEXT: - String: All loops have dependencies in all directions.125define void @issue47401(ptr noundef writeonly captures(none) %e, ptr noundef readonly captures(none) %bb) {126entry:127 br label %for.cond1.preheader128 129for.cond1.preheader:130 %indvars.iv22 = phi i64 [ 0, %entry ], [ %indvars.iv.next23, %for.cond.cleanup2 ]131 br label %for.body3132 133for.cond.cleanup:134 ret void135 136for.cond.cleanup2:137 %indvars.iv.next23 = add nuw nsw i64 %indvars.iv22, 1138 %exitcond = icmp ne i64 %indvars.iv.next23, 8139 br i1 %exitcond, label %for.cond1.preheader, label %for.cond.cleanup140 141for.body3:142 %indvars.iv = phi i64 [ 4, %for.cond1.preheader ], [ %indvars.iv.next, %land.end ]143 %0 = getelementptr [8 x i32], ptr %bb, i64 %indvars.iv144 %arrayidx = getelementptr i8, ptr %0, i64 64145 %arrayidx5 = getelementptr inbounds nuw [8 x i32], ptr %arrayidx, i64 0, i64 %indvars.iv22146 %1 = load i32, ptr %arrayidx5, align 4147 %tobool6.not = icmp eq i32 %1, 0148 br i1 %tobool6.not, label %land.end, label %land.rhs149 150land.rhs:151 %2 = load i32, ptr %0, align 4152 store i32 %2, ptr %e, align 4153 br label %land.end154 155land.end:156 %indvars.iv.next = add nsw i64 %indvars.iv, -1157 %tobool.not = icmp eq i64 %indvars.iv.next, 0158 br i1 %tobool.not, label %for.cond.cleanup2, label %for.body3159}160 161;; The original code is as follows, with some simplifications from the one in162;; the issue #47295. The interchange is illegal due to the dependency of `f`.163;;164;; void issue47295(int *f, int cc[4][4]) {165;; for (int i = 0; i <= 3; i++) {166;; for (int j = 0; j <= 3; j++) {167;; *f ^= 0x1000;168;; cc[j][i] = *f;169;; }170;; }171;; }172 173; CHECK: --- !Missed174; CHECK-NEXT: Pass: loop-interchange175; CHECK-NEXT: Name: Dependence176; CHECK-NEXT: Function: issue47295177; CHECK-NEXT: Args:178; CHECK-NEXT: - String: All loops have dependencies in all directions.179define void @issue47295(ptr noundef captures(none) %f, ptr noundef writeonly captures(none) %cc) {180entry:181 br label %for.cond1.preheader182 183for.cond1.preheader:184 %indvars.iv18 = phi i64 [ 0, %entry ], [ %indvars.iv.next19, %for.cond.cleanup3 ]185 br label %for.body4186 187for.cond.cleanup:188 ret void189 190for.cond.cleanup3:191 %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1192 %exitcond21 = icmp ne i64 %indvars.iv.next19, 4193 br i1 %exitcond21, label %for.cond1.preheader, label %for.cond.cleanup194 195for.body4:196 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]197 %0 = load i32, ptr %f, align 4198 %xor = xor i32 %0, 4096199 store i32 %xor, ptr %f, align 4200 %arrayidx6 = getelementptr inbounds nuw [4 x i32], ptr %cc, i64 %indvars.iv, i64 %indvars.iv18201 store i32 %xor, ptr %arrayidx6, align 4202 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1203 %exitcond = icmp ne i64 %indvars.iv.next, 4204 br i1 %exitcond, label %for.body4, label %for.cond.cleanup3205}206 207;; The original code is as follows, with some simplifications from the one in208;; the issue #54176. The interchange is illegal due to the dependency of `aa`.209;;210;; void issue54176(int n, int m, float aa[1024][128], float bb[1024][128], float cc[1024][128]) {211;; for (int j = 1; j < 128; j++) {212;; for (int i = 1; i < 1024; i++) {213;; cc[i][j] = aa[1][j];214;; aa[1][j-1] += bb[i][j];215;; }216;; }217;; }218 219; CHECK: --- !Missed220; CHECK-NEXT: Pass: loop-interchange221; CHECK-NEXT: Name: Dependence222; CHECK-NEXT: Function: issue54176223; CHECK-NEXT: Args:224; CHECK-NEXT: - String: All loops have dependencies in all directions.225define void @issue54176(i32 noundef %n, i32 noundef %m, ptr noundef captures(none) %aa, ptr noundef readonly captures(none) %bb, ptr noundef writeonly captures(none) %cc) {226 227entry:228 %arrayidx = getelementptr inbounds nuw i8, ptr %aa, i64 512229 br label %for.cond1.preheader230 231for.cond1.preheader:232 %indvars.iv32 = phi i64 [ 1, %entry ], [ %indvars.iv.next33, %for.cond.cleanup3 ]233 %arrayidx5 = getelementptr inbounds nuw [128 x float], ptr %arrayidx, i64 0, i64 %indvars.iv32234 %0 = add nsw i64 %indvars.iv32, -1235 %arrayidx16 = getelementptr inbounds [128 x float], ptr %arrayidx, i64 0, i64 %0236 br label %for.body4237 238for.cond.cleanup3:239 %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1240 %exitcond36 = icmp ne i64 %indvars.iv.next33, 128241 br i1 %exitcond36, label %for.cond1.preheader, label %for.cond.cleanup242 243for.body4:244 %indvars.iv = phi i64 [ 1, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]245 %1 = load float, ptr %arrayidx5, align 4246 %arrayidx9 = getelementptr inbounds nuw [128 x float], ptr %cc, i64 %indvars.iv, i64 %indvars.iv32247 store float %1, ptr %arrayidx9, align 4248 %arrayidx13 = getelementptr inbounds nuw [128 x float], ptr %bb, i64 %indvars.iv, i64 %indvars.iv32249 %2 = load float, ptr %arrayidx13, align 4250 %3 = load float, ptr %arrayidx16, align 4251 %add = fadd float %2, %3252 store float %add, ptr %arrayidx16, align 4253 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1254 %exitcond = icmp ne i64 %indvars.iv.next, 1024255 br i1 %exitcond, label %for.body4, label %for.cond.cleanup3256 257for.cond.cleanup:258 ret void259}260 261;; The original code is as follows, with some simplifications from the one in262;; the issue #116114. The interchange is illegal due to the dependency of `A`.263;;264;; void issue116114(int *A, int x, unsigned N, unsigned M) {265;; for (unsigned m = 0; m < M; ++m)266;; for (unsigned i = 0U; i < N - 1; ++i) {267;; A[i] = A[i + 1] + x;268;; }269;; }270 271; CHECK: --- !Missed272; CHECK-NEXT: Pass: loop-interchange273; CHECK-NEXT: Name: Dependence274; CHECK-NEXT: Function: issue116114275; CHECK-NEXT: Args:276; CHECK-NEXT: - String: Cannot interchange loops due to dependences.277define void @issue116114(ptr noundef captures(none) %A, i32 noundef %x, i32 noundef %N, i32 noundef %M) {278entry:279 %cmp18.not = icmp eq i32 %M, 0280 br i1 %cmp18.not, label %for.cond.cleanup, label %for.cond1.preheader.lr.ph281 282for.cond1.preheader.lr.ph:283 %sub = add i32 %N, -1284 %cmp216.not = icmp eq i32 %sub, 0285 br i1 %cmp216.not, label %for.cond1.preheader.preheader, label %for.cond1.preheader.us.preheader286 287for.cond1.preheader.us.preheader:288 br label %for.cond1.preheader.us289 290for.cond1.preheader.preheader:291 br label %for.cond.cleanup.loopexit292 293for.cond1.preheader.us:294 %m.019.us = phi i32 [ %inc9.us, %for.cond1.for.cond.cleanup3_crit_edge.us ], [ 0, %for.cond1.preheader.us.preheader ]295 %wide.trip.count = zext i32 %sub to i64296 br label %for.body4.us297 298for.body4.us:299 %indvars.iv = phi i64 [ 0, %for.cond1.preheader.us ], [ %indvars.iv.next, %for.body4.us ]300 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1301 %arrayidx.us = getelementptr inbounds nuw i32, ptr %A, i64 %indvars.iv.next302 %0 = load i32, ptr %arrayidx.us, align 4303 %add5.us = add nsw i32 %0, %x304 %arrayidx7.us = getelementptr inbounds nuw i32, ptr %A, i64 %indvars.iv305 store i32 %add5.us, ptr %arrayidx7.us, align 4306 %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count307 br i1 %exitcond, label %for.body4.us, label %for.cond1.for.cond.cleanup3_crit_edge.us308 309for.cond1.for.cond.cleanup3_crit_edge.us:310 %inc9.us = add nuw i32 %m.019.us, 1311 %exitcond22 = icmp ne i32 %inc9.us, %M312 br i1 %exitcond22, label %for.cond1.preheader.us, label %for.cond.cleanup.loopexit20313 314for.cond.cleanup.loopexit:315 br label %for.cond.cleanup316 317for.cond.cleanup.loopexit20:318 br label %for.cond.cleanup319 320for.cond.cleanup:321 ret void322}323