237 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 52; RUN: opt < %s -passes=loop-interchange -verify-dom-info -verify-loop-info -S 2>&1 | FileCheck %s3 4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"5 6@A = common global [100 x [100 x i32]] zeroinitializer7@B = common global [100 x i32] zeroinitializer8@C = common global [100 x [100 x i32]] zeroinitializer9@D = common global [100 x [100 x [100 x i32]]] zeroinitializer10 11; Loops not tightly nested are not interchanged12;13; for(int j=0;j<N;j++) {14; B[j] = j+k;15; for(int i=0;i<N;i++)16; A[j][i] = A[j][i]+B[j];17; }18;19define void @interchange_05(i32 %k, i32 %N){20; CHECK-LABEL: define void @interchange_05(21; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]]) {22; CHECK-NEXT: [[ENTRY:.*:]]23; CHECK-NEXT: [[CMP30:%.*]] = icmp sgt i32 [[N]], 024; CHECK-NEXT: br i1 [[CMP30]], label %[[FOR_BODY_LR_PH:.*]], label %[[FOR_END17:.*]]25; CHECK: [[FOR_BODY_LR_PH]]:26; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N]], -127; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[K]] to i6428; CHECK-NEXT: br label %[[FOR_BODY:.*]]29; CHECK: [[FOR_BODY]]:30; CHECK-NEXT: [[INDVARS_IV32:%.*]] = phi i64 [ 0, %[[FOR_BODY_LR_PH]] ], [ [[INDVARS_IV_NEXT33:%.*]], %[[FOR_INC15:.*]] ]31; CHECK-NEXT: [[TMP2:%.*]] = add nsw i64 [[INDVARS_IV32]], [[TMP1]]32; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds [100 x i32], ptr @B, i64 0, i64 [[INDVARS_IV32]]33; CHECK-NEXT: [[TMP3:%.*]] = trunc i64 [[TMP2]] to i3234; CHECK-NEXT: store i32 [[TMP3]], ptr [[ARRAYIDX]], align 435; CHECK-NEXT: br label %[[FOR_BODY3:.*]]36; CHECK: [[FOR_BODY3]]:37; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ 0, %[[FOR_BODY]] ], [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY3]] ]38; CHECK-NEXT: [[ARRAYIDX7:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV32]], i64 [[INDVARS_IV]]39; CHECK-NEXT: [[TMP4:%.*]] = load i32, ptr [[ARRAYIDX7]], align 440; CHECK-NEXT: [[ADD10:%.*]] = add nsw i32 [[TMP3]], [[TMP4]]41; CHECK-NEXT: store i32 [[ADD10]], ptr [[ARRAYIDX7]], align 442; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 143; CHECK-NEXT: [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV]] to i3244; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[TMP0]]45; CHECK-NEXT: br i1 [[EXITCOND]], label %[[FOR_INC15]], label %[[FOR_BODY3]]46; CHECK: [[FOR_INC15]]:47; CHECK-NEXT: [[INDVARS_IV_NEXT33]] = add nuw nsw i64 [[INDVARS_IV32]], 148; CHECK-NEXT: [[LFTR_WIDEIV35:%.*]] = trunc i64 [[INDVARS_IV32]] to i3249; CHECK-NEXT: [[EXITCOND36:%.*]] = icmp eq i32 [[LFTR_WIDEIV35]], [[TMP0]]50; CHECK-NEXT: br i1 [[EXITCOND36]], label %[[FOR_END17_LOOPEXIT:.*]], label %[[FOR_BODY]]51; CHECK: [[FOR_END17_LOOPEXIT]]:52; CHECK-NEXT: br label %[[FOR_END17]]53; CHECK: [[FOR_END17]]:54; CHECK-NEXT: ret void55;56entry:57 %cmp30 = icmp sgt i32 %N, 058 br i1 %cmp30, label %for.body.lr.ph, label %for.end1759 60for.body.lr.ph:61 %0 = add i32 %N, -162 %1 = zext i32 %k to i6463 br label %for.body64 65for.body:66 %indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ]67 %2 = add nsw i64 %indvars.iv32, %168 %arrayidx = getelementptr inbounds [100 x i32], ptr @B, i64 0, i64 %indvars.iv3269 %3 = trunc i64 %2 to i3270 store i32 %3, ptr %arrayidx71 br label %for.body372 73for.body3:74 %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ]75 %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv76 %4 = load i32, ptr %arrayidx777 %add10 = add nsw i32 %3, %478 store i32 %add10, ptr %arrayidx779 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 180 %lftr.wideiv = trunc i64 %indvars.iv to i3281 %exitcond = icmp eq i32 %lftr.wideiv, %082 br i1 %exitcond, label %for.inc15, label %for.body383 84for.inc15:85 %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 186 %lftr.wideiv35 = trunc i64 %indvars.iv32 to i3287 %exitcond36 = icmp eq i32 %lftr.wideiv35, %088 br i1 %exitcond36, label %for.end17, label %for.body89 90for.end17:91 ret void92}93 94declare void @foo(...) readnone95 96; Loops not tightly nested are not interchanged97; for(int j=0;j<N;j++) {98; foo();99; for(int i=2;i<N;i++)100; A[j][i] = A[j][i]+k;101; }102;103define void @interchange_06(i32 %k, i32 %N) {104; CHECK-LABEL: define void @interchange_06(105; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]]) {106; CHECK-NEXT: [[ENTRY:.*:]]107; CHECK-NEXT: [[CMP22:%.*]] = icmp sgt i32 [[N]], 0108; CHECK-NEXT: br i1 [[CMP22]], label %[[FOR_BODY_LR_PH:.*]], label %[[FOR_END12:.*]]109; CHECK: [[FOR_BODY_LR_PH]]:110; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N]], -1111; CHECK-NEXT: br label %[[FOR_BODY:.*]]112; CHECK: [[FOR_BODY]]:113; CHECK-NEXT: [[INDVARS_IV24:%.*]] = phi i64 [ 0, %[[FOR_BODY_LR_PH]] ], [ [[INDVARS_IV_NEXT25:%.*]], %[[FOR_INC10:.*]] ]114; CHECK-NEXT: tail call void (...) @foo()115; CHECK-NEXT: br label %[[FOR_BODY3:.*]]116; CHECK: [[FOR_BODY3]]:117; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY3]] ], [ 2, %[[FOR_BODY]] ]118; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV24]], i64 [[INDVARS_IV]]119; CHECK-NEXT: [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4120; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[TMP1]], [[K]]121; CHECK-NEXT: store i32 [[ADD]], ptr [[ARRAYIDX5]], align 4122; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1123; CHECK-NEXT: [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV]] to i32124; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[TMP0]]125; CHECK-NEXT: br i1 [[EXITCOND]], label %[[FOR_INC10]], label %[[FOR_BODY3]]126; CHECK: [[FOR_INC10]]:127; CHECK-NEXT: [[INDVARS_IV_NEXT25]] = add nuw nsw i64 [[INDVARS_IV24]], 1128; CHECK-NEXT: [[LFTR_WIDEIV26:%.*]] = trunc i64 [[INDVARS_IV24]] to i32129; CHECK-NEXT: [[EXITCOND27:%.*]] = icmp eq i32 [[LFTR_WIDEIV26]], [[TMP0]]130; CHECK-NEXT: br i1 [[EXITCOND27]], label %[[FOR_END12_LOOPEXIT:.*]], label %[[FOR_BODY]]131; CHECK: [[FOR_END12_LOOPEXIT]]:132; CHECK-NEXT: br label %[[FOR_END12]]133; CHECK: [[FOR_END12]]:134; CHECK-NEXT: ret void135;136entry:137 %cmp22 = icmp sgt i32 %N, 0138 br i1 %cmp22, label %for.body.lr.ph, label %for.end12139 140for.body.lr.ph:141 %0 = add i32 %N, -1142 br label %for.body143 144for.body:145 %indvars.iv24 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next25, %for.inc10 ]146 tail call void (...) @foo()147 br label %for.body3148 149for.body3:150 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body ]151 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv24, i64 %indvars.iv152 %1 = load i32, ptr %arrayidx5153 %add = add nsw i32 %1, %k154 store i32 %add, ptr %arrayidx5155 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1156 %lftr.wideiv = trunc i64 %indvars.iv to i32157 %exitcond = icmp eq i32 %lftr.wideiv, %0158 br i1 %exitcond, label %for.inc10, label %for.body3159 160for.inc10:161 %indvars.iv.next25 = add nuw nsw i64 %indvars.iv24, 1162 %lftr.wideiv26 = trunc i64 %indvars.iv24 to i32163 %exitcond27 = icmp eq i32 %lftr.wideiv26, %0164 br i1 %exitcond27, label %for.end12, label %for.body165 166for.end12:167 ret void168}169 170; The following Loop is not considered tightly nested and is not interchanged.171; The outer loop header does not branch to the inner loop preheader, or the172; inner loop header, or the outer loop latch.173;174define void @interchange_07(i32 %k, i32 %N, i64 %ny) {175; CHECK-LABEL: define void @interchange_07(176; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]], i64 [[NY:%.*]]) {177; CHECK-NEXT: [[ENTRY:.*]]:178; CHECK-NEXT: br label %[[FOR1_HEADER:.*]]179; CHECK: [[FOR1_HEADER]]:180; CHECK-NEXT: [[J23:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[J_NEXT24:%.*]], %[[FOR1_INC10:.*]] ]181; CHECK-NEXT: [[CMP21:%.*]] = icmp slt i64 0, [[NY]]182; CHECK-NEXT: br label %[[SINGLESUCC:.*]]183; CHECK: [[SINGLESUCC]]:184; CHECK-NEXT: br i1 [[CMP21]], label %[[PREHEADER_J:.*]], label %[[FOR1_INC10]]185; CHECK: [[PREHEADER_J]]:186; CHECK-NEXT: br label %[[FOR2:.*]]187; CHECK: [[FOR2]]:188; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[J_NEXT:%.*]], %[[FOR2]] ], [ 0, %[[PREHEADER_J]] ]189; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[J]], i64 [[J23]]190; CHECK-NEXT: [[LV:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4191; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[LV]], [[K]]192; CHECK-NEXT: store i32 [[ADD]], ptr [[ARRAYIDX5]], align 4193; CHECK-NEXT: [[J_NEXT]] = add nuw nsw i64 [[J]], 1194; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J]], 99195; CHECK-NEXT: br i1 [[EXITCOND]], label %[[FOR1_INC10_LOOPEXIT:.*]], label %[[FOR2]]196; CHECK: [[FOR1_INC10_LOOPEXIT]]:197; CHECK-NEXT: br label %[[FOR1_INC10]]198; CHECK: [[FOR1_INC10]]:199; CHECK-NEXT: [[J_NEXT24]] = add nuw nsw i64 [[J23]], 1200; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 99201; CHECK-NEXT: br i1 [[EXITCOND26]], label %[[FOR_END12:.*]], label %[[FOR1_HEADER]]202; CHECK: [[FOR_END12]]:203; CHECK-NEXT: ret void204;205entry:206 br label %for1.header207 208for1.header:209 %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ]210 %cmp21 = icmp slt i64 0, %ny211 br label %singleSucc212 213singleSucc:214 br i1 %cmp21, label %preheader.j, label %for1.inc10215 216preheader.j:217 br label %for2218 219for2:220 %j = phi i64 [ %j.next, %for2 ], [ 0, %preheader.j ]221 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 %j23222 %lv = load i32, ptr %arrayidx5223 %add = add nsw i32 %lv, %k224 store i32 %add, ptr %arrayidx5225 %j.next = add nuw nsw i64 %j, 1226 %exitcond = icmp eq i64 %j, 99227 br i1 %exitcond, label %for1.inc10, label %for2228 229for1.inc10:230 %j.next24 = add nuw nsw i64 %j23, 1231 %exitcond26 = icmp eq i64 %j23, 99232 br i1 %exitcond26, label %for.end12, label %for1.header233 234for.end12:235 ret void236}237