266 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; REQUIRES: asserts3; RUN: opt < %s -S -debug -passes=loop-idiom 2>&1 | FileCheck %s4; The C code to generate this testcase:5; void test(int *ar, int n, int m)6; {7; long i;8; for (i=0; i<n; ++i) {9; int *arr = ar + i * m;10; memset(arr, 0, i + m * sizeof(int));11; }12; }13 14; Check on debug outputs...15; CHECK: loop-idiom Scanning: F[MemsetSize_LoopVariant] Countable Loop %for.body16; CHECK-NEXT: memset size is non-constant17; CHECK-NEXT: memset size is not a loop-invariant, abort18; CHECK: loop-idiom Scanning: F[MemsetSize_Stride_Mismatch] Countable Loop %for.body19; CHECK-NEXT: memset size is non-constant20; CHECK-NEXT: MemsetSizeSCEV: (4 * (sext i32 %m to i64))<nsw>21; CHECK-NEXT: PositiveStrideSCEV: (4 + (4 * (sext i32 %m to i64))<nsw>)<nsw>22; CHECK-NEXT: Try to fold SCEV based on loop guard23; CHECK-NEXT: FoldedMemsetSize: (4 * (sext i32 %m to i64))<nsw>24; CHECK-NEXT: FoldedPositiveStride: (4 + (4 * (sext i32 %m to i64))<nsw>)<nsw>25; CHECK-NEXT: SCEV don't match, abort26; CHECK: loop-idiom Scanning: F[NonZeroAddressSpace] Countable Loop %for.cond1.preheader27; CHECK-NEXT: memset size is non-constant28; CHECK-NEXT: pointer is not in address space zero, abort29; CHECK: loop-idiom Scanning: F[NonAffinePointer] Countable Loop %for.body30; CHECK-NEXT: Pointer is not affine, abort31 32define void @MemsetSize_LoopVariant(ptr %ar, i32 %n, i32 %m) {33; CHECK-LABEL: @MemsetSize_LoopVariant(34; CHECK-NEXT: entry:35; CHECK-NEXT: [[CONV:%.*]] = sext i32 [[N:%.*]] to i6436; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i64 0, [[CONV]]37; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]38; CHECK: for.body.lr.ph:39; CHECK-NEXT: [[CONV1:%.*]] = sext i32 [[M:%.*]] to i6440; CHECK-NEXT: [[CONV2:%.*]] = sext i32 [[M]] to i6441; CHECK-NEXT: [[MUL3:%.*]] = mul i64 [[CONV2]], 442; CHECK-NEXT: br label [[FOR_BODY:%.*]]43; CHECK: for.body:44; CHECK-NEXT: [[I_02:%.*]] = phi i64 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]45; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[I_02]], [[CONV1]]46; CHECK-NEXT: [[ADD_PTR:%.*]] = getelementptr inbounds i32, ptr [[AR:%.*]], i64 [[MUL]]47; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[I_02]], [[MUL3]]48; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[ADD_PTR]], i8 0, i64 [[ADD]], i1 false)49; CHECK-NEXT: br label [[FOR_INC]]50; CHECK: for.inc:51; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[I_02]], 152; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[INC]], [[CONV]]53; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]54; CHECK: for.cond.for.end_crit_edge:55; CHECK-NEXT: br label [[FOR_END]]56; CHECK: for.end:57; CHECK-NEXT: ret void58;59entry:60 %conv = sext i32 %n to i6461 %cmp1 = icmp slt i64 0, %conv62 br i1 %cmp1, label %for.body.lr.ph, label %for.end63 64for.body.lr.ph: ; preds = %entry65 %conv1 = sext i32 %m to i6466 %conv2 = sext i32 %m to i6467 %mul3 = mul i64 %conv2, 468 br label %for.body69 70for.body: ; preds = %for.body.lr.ph, %for.inc71 %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]72 %mul = mul nsw i64 %i.02, %conv173 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %mul74 %add = add nsw i64 %i.02, %mul375 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %add, i1 false)76 br label %for.inc77 78for.inc: ; preds = %for.body79 %inc = add nuw nsw i64 %i.02, 180 %cmp = icmp slt i64 %inc, %conv81 br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge82 83for.cond.for.end_crit_edge: ; preds = %for.inc84 br label %for.end85 86for.end: ; preds = %for.cond.for.end_crit_edge, %entry87 ret void88}89; void test(int *ar, int n, int m)90; {91; long i;92; for (i=0; i<n; ++i) {93; int *arr = ar + i + i * m;94; memset(arr, 0, m * sizeof(int));95; }96; }97define void @MemsetSize_Stride_Mismatch(ptr %ar, i32 %n, i32 %m) {98; CHECK-LABEL: @MemsetSize_Stride_Mismatch(99; CHECK-NEXT: entry:100; CHECK-NEXT: [[CONV:%.*]] = sext i32 [[N:%.*]] to i64101; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i64 0, [[CONV]]102; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]103; CHECK: for.body.lr.ph:104; CHECK-NEXT: [[CONV1:%.*]] = sext i32 [[M:%.*]] to i64105; CHECK-NEXT: [[CONV3:%.*]] = sext i32 [[M]] to i64106; CHECK-NEXT: [[MUL4:%.*]] = mul i64 [[CONV3]], 4107; CHECK-NEXT: br label [[FOR_BODY:%.*]]108; CHECK: for.body:109; CHECK-NEXT: [[I_02:%.*]] = phi i64 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]110; CHECK-NEXT: [[ADD_PTR:%.*]] = getelementptr inbounds i32, ptr [[AR:%.*]], i64 [[I_02]]111; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[I_02]], [[CONV1]]112; CHECK-NEXT: [[ADD_PTR2:%.*]] = getelementptr inbounds i32, ptr [[ADD_PTR]], i64 [[MUL]]113; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[ADD_PTR2]], i8 0, i64 [[MUL4]], i1 false)114; CHECK-NEXT: br label [[FOR_INC]]115; CHECK: for.inc:116; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[I_02]], 1117; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[INC]], [[CONV]]118; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]119; CHECK: for.cond.for.end_crit_edge:120; CHECK-NEXT: br label [[FOR_END]]121; CHECK: for.end:122; CHECK-NEXT: ret void123;124entry:125 %conv = sext i32 %n to i64126 %cmp1 = icmp slt i64 0, %conv127 br i1 %cmp1, label %for.body.lr.ph, label %for.end128 129for.body.lr.ph: ; preds = %entry130 %conv1 = sext i32 %m to i64131 %conv3 = sext i32 %m to i64132 %mul4 = mul i64 %conv3, 4133 br label %for.body134 135for.body: ; preds = %for.body.lr.ph, %for.inc136 %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]137 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %i.02138 %mul = mul nsw i64 %i.02, %conv1139 %add.ptr2 = getelementptr inbounds i32, ptr %add.ptr, i64 %mul140 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr2, i8 0, i64 %mul4, i1 false)141 br label %for.inc142 143for.inc: ; preds = %for.body144 %inc = add nuw nsw i64 %i.02, 1145 %cmp = icmp slt i64 %inc, %conv146 br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge147 148for.cond.for.end_crit_edge: ; preds = %for.inc149 br label %for.end150 151for.end: ; preds = %for.cond.for.end_crit_edge, %entry152 ret void153}154 155define void @NonZeroAddressSpace(ptr addrspace(2) nocapture %ar, i64 %n, i64 %m) {156; CHECK-LABEL: @NonZeroAddressSpace(157; CHECK-NEXT: entry:158; CHECK-NEXT: [[TMP0:%.*]] = shl nuw i64 [[M:%.*]], 2159; CHECK-NEXT: br label [[FOR_COND1_PREHEADER:%.*]]160; CHECK: for.cond1.preheader:161; CHECK-NEXT: [[I_017:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC5:%.*]], [[FOR_INC4:%.*]] ]162; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[M]], [[I_017]]163; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i32, ptr addrspace(2) [[AR:%.*]], i64 [[TMP1]]164; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[I_017]], [[M]]165; CHECK-NEXT: call void @llvm.memset.p2.i64(ptr addrspace(2) align 4 [[SCEVGEP]], i8 0, i64 [[TMP0]], i1 false)166; CHECK-NEXT: br label [[FOR_INC4]]167; CHECK: for.inc4:168; CHECK-NEXT: [[INC5]] = add nuw nsw i64 [[I_017]], 1169; CHECK-NEXT: [[EXITCOND18_NOT:%.*]] = icmp eq i64 [[INC5]], [[N:%.*]]170; CHECK-NEXT: br i1 [[EXITCOND18_NOT]], label [[FOR_END6:%.*]], label [[FOR_COND1_PREHEADER]]171; CHECK: for.end6:172; CHECK-NEXT: ret void173;174entry:175 %0 = shl nuw i64 %m, 2176 br label %for.cond1.preheader177 178for.cond1.preheader: ; preds = %for.inc4, %entry179 %i.017 = phi i64 [ 0, %entry ], [ %inc5, %for.inc4 ]180 %1 = mul i64 %m, %i.017181 %scevgep = getelementptr i32, ptr addrspace(2) %ar, i64 %1182 %mul = mul nsw i64 %i.017, %m183 call void @llvm.memset.p2.i64(ptr addrspace(2) align 4 %scevgep, i8 0, i64 %0, i1 false)184 br label %for.inc4185 186for.inc4: ; preds = %for.cond1.preheader187 %inc5 = add nuw nsw i64 %i.017, 1188 %exitcond18.not = icmp eq i64 %inc5, %n189 br i1 %exitcond18.not, label %for.end6, label %for.cond1.preheader190 191for.end6: ; preds = %for.inc4192 ret void193}194 195; void test(int *ar, int n, int m)196; {197; long i;198; for (i=0; i<n; ++i) {199; int *arr = ar + i * m;200; memset(arr, 0, m * sizeof(int));201; ar = ar + i;202; }203; }204define void @NonAffinePointer(ptr %ar, i32 %n, i32 %m) {205; CHECK-LABEL: @NonAffinePointer(206; CHECK-NEXT: entry:207; CHECK-NEXT: [[CONV:%.*]] = sext i32 [[N:%.*]] to i64208; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i64 0, [[CONV]]209; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]210; CHECK: for.body.lr.ph:211; CHECK-NEXT: [[CONV1:%.*]] = sext i32 [[M:%.*]] to i64212; CHECK-NEXT: [[CONV2:%.*]] = sext i32 [[M]] to i64213; CHECK-NEXT: [[MUL3:%.*]] = mul i64 [[CONV2]], 4214; CHECK-NEXT: br label [[FOR_BODY:%.*]]215; CHECK: for.body:216; CHECK-NEXT: [[AR_ADDR_03:%.*]] = phi ptr [ [[AR:%.*]], [[FOR_BODY_LR_PH]] ], [ [[ADD_PTR4:%.*]], [[FOR_INC:%.*]] ]217; CHECK-NEXT: [[I_02:%.*]] = phi i64 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[FOR_INC]] ]218; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[I_02]], [[CONV1]]219; CHECK-NEXT: [[ADD_PTR:%.*]] = getelementptr inbounds i32, ptr [[AR_ADDR_03]], i64 [[MUL]]220; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[ADD_PTR]], i8 0, i64 [[MUL3]], i1 false)221; CHECK-NEXT: [[ADD_PTR4]] = getelementptr inbounds i32, ptr [[AR_ADDR_03]], i64 [[I_02]]222; CHECK-NEXT: br label [[FOR_INC]]223; CHECK: for.inc:224; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[I_02]], 1225; CHECK-NEXT: [[CMP:%.*]] = icmp slt i64 [[INC]], [[CONV]]226; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]227; CHECK: for.cond.for.end_crit_edge:228; CHECK-NEXT: br label [[FOR_END]]229; CHECK: for.end:230; CHECK-NEXT: ret void231;232entry:233 %conv = sext i32 %n to i64234 %cmp1 = icmp slt i64 0, %conv235 br i1 %cmp1, label %for.body.lr.ph, label %for.end236 237for.body.lr.ph: ; preds = %entry238 %conv1 = sext i32 %m to i64239 %conv2 = sext i32 %m to i64240 %mul3 = mul i64 %conv2, 4241 br label %for.body242 243for.body: ; preds = %for.body.lr.ph, %for.inc244 %ar.addr.03 = phi ptr [ %ar, %for.body.lr.ph ], [ %add.ptr4, %for.inc ]245 %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]246 %mul = mul nsw i64 %i.02, %conv1247 %add.ptr = getelementptr inbounds i32, ptr %ar.addr.03, i64 %mul248 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %mul3, i1 false)249 %add.ptr4 = getelementptr inbounds i32, ptr %ar.addr.03, i64 %i.02250 br label %for.inc251 252for.inc: ; preds = %for.body253 %inc = add nuw nsw i64 %i.02, 1254 %cmp = icmp slt i64 %inc, %conv255 br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge256 257for.cond.for.end_crit_edge: ; preds = %for.inc258 br label %for.end259 260for.end: ; preds = %for.cond.for.end_crit_edge, %entry261 ret void262}263 264declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg)265declare void @llvm.memset.p2.i64(ptr addrspace(2) nocapture writeonly, i8, i64, i1 immarg)266