210 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -aa-pipeline=basic-aa -passes='loop(loop-interchange)' -cache-line-size=64 -S %s | FileCheck %s --check-prefixes INTC3; RUN: opt -aa-pipeline=basic-aa -passes='loop-mssa(lnicm),loop(loop-interchange)' -cache-line-size=64 -S %s | FileCheck %s --check-prefixes LNICM4; RUN: opt -aa-pipeline=basic-aa -passes='loop-mssa(licm),loop(loop-interchange)' -cache-line-size=64 -S %s | FileCheck %s --check-prefixes LICM5 6; This test represents the following function:7; void test(int n, int m, int x[m][n], int y[n], int *z) {8; for (int k = 0; k < n; k++) {9; int tmp = *z;10; for (int i = 0; i < m; i++)11; x[i][k] += y[k] + tmp;12; }13; }14; We only want to hoist the load of z out of the loop nest.15; LICM hoists the load of y[k] out of the i-loop, but LNICM doesn't do so16; to keep perfect loop nest. This enables optimizations that require17; perfect loop nest (e.g. loop-interchange) to perform.18 19 20define dso_local void @test(i64 %n, i64 %m, ptr noalias %x, ptr noalias readonly %y, ptr readonly %z) {21; The loopnest is not interchanged when we only run loop interchange.22; INTC-LABEL: @test(23; INTC-NEXT: gurad:24; INTC-NEXT: [[CMP23:%.*]] = icmp sgt i64 [[M:%.*]], 025; INTC-NEXT: [[CMP32:%.*]] = icmp sgt i64 [[N:%.*]], 026; INTC-NEXT: br i1 [[CMP23]], label [[FOR_COND1_PREHEADER_LR_PH:%.*]], label [[FOR_END11:%.*]]27; INTC: for.cond1.preheader.lr.ph:28; INTC-NEXT: br i1 [[CMP32]], label [[FOR_I_PREHEADER:%.*]], label [[FOR_END11]]29; INTC: for.i.preheader:30; INTC-NEXT: br label [[ENTRY:%.*]]31; INTC: entry:32; INTC-NEXT: br label [[FOR_BODY:%.*]]33; INTC: for.body:34; INTC-NEXT: [[K_02:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC10:%.*]], [[FOR_END:%.*]] ]35; INTC-NEXT: [[TMP0:%.*]] = load i32, ptr [[Z:%.*]], align 436; INTC-NEXT: br label [[FOR_BODY3:%.*]]37; INTC: for.body3:38; INTC-NEXT: [[I_01:%.*]] = phi i32 [ 0, [[FOR_BODY]] ], [ [[INC:%.*]], [[FOR_BODY3]] ]39; INTC-NEXT: [[IDXPROM:%.*]] = sext i32 [[K_02]] to i6440; INTC-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[Y:%.*]], i64 [[IDXPROM]]41; INTC-NEXT: [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX]], align 442; INTC-NEXT: [[ADD:%.*]] = add nsw i32 [[TMP1]], [[TMP0]]43; INTC-NEXT: [[IDXPROM4:%.*]] = sext i32 [[I_01]] to i6444; INTC-NEXT: [[INDEX0:%.*]] = mul i64 [[IDXPROM4]], [[N]]45; INTC-NEXT: [[INDEX1:%.*]] = add i64 [[INDEX0]], [[IDXPROM]]46; INTC-NEXT: [[ARRAYIDX7:%.*]] = getelementptr inbounds i32, ptr [[X:%.*]], i64 [[INDEX1]]47; INTC-NEXT: [[TMP2:%.*]] = load i32, ptr [[ARRAYIDX7]], align 448; INTC-NEXT: [[ADD8:%.*]] = add nsw i32 [[TMP2]], [[ADD]]49; INTC-NEXT: store i32 [[ADD8]], ptr [[ARRAYIDX7]], align 450; INTC-NEXT: [[INC]] = add nsw i32 [[I_01]], 151; INTC-NEXT: [[INC_EXT:%.*]] = sext i32 [[INC]] to i6452; INTC-NEXT: [[CMP2:%.*]] = icmp slt i64 [[INC_EXT]], [[M]]53; INTC-NEXT: br i1 [[CMP2]], label [[FOR_BODY3]], label [[FOR_END]], !llvm.loop [[LOOP0:![0-9]+]]54; INTC: for.end:55; INTC-NEXT: [[INC10]] = add nsw i32 [[K_02]], 156; INTC-NEXT: [[INC10_EXT:%.*]] = sext i32 [[INC10]] to i6457; INTC-NEXT: [[CMP:%.*]] = icmp slt i64 [[INC10_EXT]], [[N]]58; INTC-NEXT: br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END11_LOOPEXIT:%.*]], !llvm.loop [[LOOP2:![0-9]+]]59; INTC: for.end11.loopexit:60; INTC-NEXT: br label [[FOR_END11]]61; INTC: for.end11:62; INTC-NEXT: ret void63;64; The loopnest is interchanged when we run lnicm and loop interchange.65; LNICM-LABEL: @test(66; LNICM-NEXT: gurad:67; LNICM-NEXT: [[CMP23:%.*]] = icmp sgt i64 [[M:%.*]], 068; LNICM-NEXT: [[CMP32:%.*]] = icmp sgt i64 [[N:%.*]], 069; LNICM-NEXT: br i1 [[CMP23]], label [[FOR_COND1_PREHEADER_LR_PH:%.*]], label [[FOR_END11:%.*]]70; LNICM: for.cond1.preheader.lr.ph:71; LNICM-NEXT: br i1 [[CMP32]], label [[FOR_I_PREHEADER:%.*]], label [[FOR_END11]]72; LNICM: for.i.preheader:73; LNICM-NEXT: br label [[FOR_BODY3_PREHEADER:%.*]]74; LNICM: entry:75; LNICM-NEXT: br label [[FOR_BODY:%.*]]76; LNICM: for.body:77; LNICM-NEXT: [[K_02:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC10:%.*]], [[FOR_END:%.*]] ]78; LNICM-NEXT: br label [[FOR_BODY3_SPLIT1:%.*]]79; LNICM: for.body3.preheader:80; LNICM-NEXT: [[TMP0:%.*]] = load i32, ptr [[Z:%.*]], align 481; LNICM-NEXT: br label [[FOR_BODY3:%.*]]82; LNICM: for.body3:83; LNICM-NEXT: [[I_01:%.*]] = phi i32 [ [[TMP3:%.*]], [[FOR_BODY3_SPLIT:%.*]] ], [ 0, [[FOR_BODY3_PREHEADER]] ]84; LNICM-NEXT: br label [[ENTRY]]85; LNICM: for.body3.split1:86; LNICM-NEXT: [[IDXPROM:%.*]] = sext i32 [[K_02]] to i6487; LNICM-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[Y:%.*]], i64 [[IDXPROM]]88; LNICM-NEXT: [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX]], align 489; LNICM-NEXT: [[ADD:%.*]] = add nsw i32 [[TMP1]], [[TMP0]]90; LNICM-NEXT: [[IDXPROM4:%.*]] = sext i32 [[I_01]] to i6491; LNICM-NEXT: [[INDEX0:%.*]] = mul i64 [[IDXPROM4]], [[N]]92; LNICM-NEXT: [[INDEX1:%.*]] = add i64 [[INDEX0]], [[IDXPROM]]93; LNICM-NEXT: [[ARRAYIDX7:%.*]] = getelementptr inbounds i32, ptr [[X:%.*]], i64 [[INDEX1]]94; LNICM-NEXT: [[TMP2:%.*]] = load i32, ptr [[ARRAYIDX7]], align 495; LNICM-NEXT: [[ADD8:%.*]] = add nsw i32 [[TMP2]], [[ADD]]96; LNICM-NEXT: store i32 [[ADD8]], ptr [[ARRAYIDX7]], align 497; LNICM-NEXT: [[INC:%.*]] = add nsw i32 [[I_01]], 198; LNICM-NEXT: [[INC_EXT:%.*]] = sext i32 [[INC]] to i6499; LNICM-NEXT: [[CMP2:%.*]] = icmp slt i64 [[INC_EXT]], [[M]]100; LNICM-NEXT: br label [[FOR_END]]101; LNICM: for.body3.split:102; LNICM-NEXT: [[TMP3]] = add nsw i32 [[I_01]], 1103; LNICM-NEXT: [[TMP4:%.*]] = sext i32 [[TMP3]] to i64104; LNICM-NEXT: [[TMP5:%.*]] = icmp slt i64 [[TMP4]], [[M]]105; LNICM-NEXT: br i1 [[TMP5]], label [[FOR_BODY3]], label [[FOR_END11_LOOPEXIT:%.*]], !llvm.loop [[LOOP0:![0-9]+]]106; LNICM: for.end:107; LNICM-NEXT: [[INC10]] = add nsw i32 [[K_02]], 1108; LNICM-NEXT: [[INC10_EXT:%.*]] = sext i32 [[INC10]] to i64109; LNICM-NEXT: [[CMP:%.*]] = icmp slt i64 [[INC10_EXT]], [[N]]110; LNICM-NEXT: br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_BODY3_SPLIT]], !llvm.loop [[LOOP2:![0-9]+]]111; LNICM: for.end11.loopexit:112; LNICM-NEXT: br label [[FOR_END11]]113; LNICM: for.end11:114; LNICM-NEXT: ret void115;116; The loopnest is not interchanged when we run licm and loop interchange.117; LICM-LABEL: @test(118; LICM-NEXT: gurad:119; LICM-NEXT: [[CMP23:%.*]] = icmp sgt i64 [[M:%.*]], 0120; LICM-NEXT: [[CMP32:%.*]] = icmp sgt i64 [[N:%.*]], 0121; LICM-NEXT: br i1 [[CMP23]], label [[FOR_COND1_PREHEADER_LR_PH:%.*]], label [[FOR_END11:%.*]]122; LICM: for.cond1.preheader.lr.ph:123; LICM-NEXT: br i1 [[CMP32]], label [[FOR_I_PREHEADER:%.*]], label [[FOR_END11]]124; LICM: for.i.preheader:125; LICM-NEXT: br label [[ENTRY:%.*]]126; LICM: entry:127; LICM-NEXT: [[TMP0:%.*]] = load i32, ptr [[Z:%.*]], align 4128; LICM-NEXT: br label [[FOR_BODY:%.*]]129; LICM: for.body:130; LICM-NEXT: [[K_02:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC10:%.*]], [[FOR_END:%.*]] ]131; LICM-NEXT: [[IDXPROM:%.*]] = sext i32 [[K_02]] to i64132; LICM-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[Y:%.*]], i64 [[IDXPROM]]133; LICM-NEXT: [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX]], align 4134; LICM-NEXT: [[ADD:%.*]] = add nsw i32 [[TMP1]], [[TMP0]]135; LICM-NEXT: br label [[FOR_BODY3:%.*]]136; LICM: for.body3:137; LICM-NEXT: [[I_01:%.*]] = phi i32 [ 0, [[FOR_BODY]] ], [ [[INC:%.*]], [[FOR_BODY3]] ]138; LICM-NEXT: [[IDXPROM4:%.*]] = sext i32 [[I_01]] to i64139; LICM-NEXT: [[INDEX0:%.*]] = mul i64 [[IDXPROM4]], [[N]]140; LICM-NEXT: [[INDEX1:%.*]] = add i64 [[INDEX0]], [[IDXPROM]]141; LICM-NEXT: [[ARRAYIDX7:%.*]] = getelementptr inbounds i32, ptr [[X:%.*]], i64 [[INDEX1]]142; LICM-NEXT: [[TMP2:%.*]] = load i32, ptr [[ARRAYIDX7]], align 4143; LICM-NEXT: [[ADD8:%.*]] = add nsw i32 [[TMP2]], [[ADD]]144; LICM-NEXT: store i32 [[ADD8]], ptr [[ARRAYIDX7]], align 4145; LICM-NEXT: [[INC]] = add nsw i32 [[I_01]], 1146; LICM-NEXT: [[INC_EXT:%.*]] = sext i32 [[INC]] to i64147; LICM-NEXT: [[CMP2:%.*]] = icmp slt i64 [[INC_EXT]], [[M]]148; LICM-NEXT: br i1 [[CMP2]], label [[FOR_BODY3]], label [[FOR_END]], !llvm.loop [[LOOP0:![0-9]+]]149; LICM: for.end:150; LICM-NEXT: [[INC10]] = add nsw i32 [[K_02]], 1151; LICM-NEXT: [[INC10_EXT:%.*]] = sext i32 [[INC10]] to i64152; LICM-NEXT: [[CMP:%.*]] = icmp slt i64 [[INC10_EXT]], [[N]]153; LICM-NEXT: br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END11_LOOPEXIT:%.*]], !llvm.loop [[LOOP2:![0-9]+]]154; LICM: for.end11.loopexit:155; LICM-NEXT: br label [[FOR_END11]]156; LICM: for.end11:157; LICM-NEXT: ret void158;159 160gurad:161 %cmp23 = icmp sgt i64 %m, 0162 %cmp32 = icmp sgt i64 %n, 0163 br i1 %cmp23, label %for.cond1.preheader.lr.ph, label %for.end11164 165for.cond1.preheader.lr.ph: ; preds = %gurad166 br i1 %cmp32, label %for.i.preheader, label %for.end11167 168for.i.preheader: ; preds = %for.cond1.preheader.lr.ph169 br label %entry170 171entry: ; preds = %for.i.preheader172 br label %for.body173 174for.body:175 %k.02 = phi i32 [ 0, %entry ], [ %inc10, %for.end ]176 %0 = load i32, ptr %z, align 4177 br label %for.body3178 179for.body3:180 %i.01 = phi i32 [ 0, %for.body ], [ %inc, %for.body3 ]181 %idxprom = sext i32 %k.02 to i64182 %arrayidx = getelementptr inbounds i32, ptr %y, i64 %idxprom183 %1 = load i32, ptr %arrayidx, align 4184 %add = add nsw i32 %1, %0185 %idxprom4 = sext i32 %i.01 to i64186 %index0 = mul i64 %idxprom4, %n187 %index1 = add i64 %index0, %idxprom188 %arrayidx7 = getelementptr inbounds i32, ptr %x, i64 %index1189 %2 = load i32, ptr %arrayidx7, align 4190 %add8 = add nsw i32 %2, %add191 store i32 %add8, ptr %arrayidx7, align 4192 %inc = add nsw i32 %i.01, 1193 %inc.ext = sext i32 %inc to i64194 %cmp2 = icmp slt i64 %inc.ext, %m195 br i1 %cmp2, label %for.body3, label %for.end, !llvm.loop !0196 197for.end:198 %inc10 = add nsw i32 %k.02, 1199 %inc10.ext = sext i32 %inc10 to i64200 %cmp = icmp slt i64 %inc10.ext, %n201 br i1 %cmp, label %for.body, label %for.end11, !llvm.loop !2202 203for.end11:204 ret void205}206 207!0 = distinct !{!0, !1}208!1 = !{!"llvm.loop.mustprogress"}209!2 = distinct !{!2, !1}210