1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; REQUIRES: asserts 3; RUN: opt < %s -S -debug -passes=loop-idiom 2>&1 | FileCheck %s 4; 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.body 16; CHECK-NEXT: memset size is non-constant 17; CHECK-NEXT: memset size is not a loop-invariant, abort 18; CHECK: loop-idiom Scanning: F[MemsetSize_Stride_Mismatch] Countable Loop %for.body 19; CHECK-NEXT: memset size is non-constant 20; 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 guard 23; 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, abort 26; CHECK: loop-idiom Scanning: F[NonZeroAddressSpace] Countable Loop %for.cond1.preheader 27; CHECK-NEXT: memset size is non-constant 28; CHECK-NEXT: pointer is not in address space zero, abort 29; CHECK: loop-idiom Scanning: F[NonAffinePointer] Countable Loop %for.body 30; CHECK-NEXT: Pointer is not affine, abort 31 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 i64 36; 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 i64 40; CHECK-NEXT: [[CONV2:%.*]] = sext i32 [[M]] to i64 41; CHECK-NEXT: [[MUL3:%.*]] = mul i64 [[CONV2]], 4 42; 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]], 1 52; 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 void 58; 59entry: 60 %conv = sext i32 %n to i64 61 %cmp1 = icmp slt i64 0, %conv 62 br i1 %cmp1, label %for.body.lr.ph, label %for.end 63 64for.body.lr.ph: ; preds = %entry 65 %conv1 = sext i32 %m to i64 66 %conv2 = sext i32 %m to i64 67 %mul3 = mul i64 %conv2, 4 68 br label %for.body 69 70for.body: ; preds = %for.body.lr.ph, %for.inc 71 %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ] 72 %mul = mul nsw i64 %i.02, %conv1 73 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %mul 74 %add = add nsw i64 %i.02, %mul3 75 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %add, i1 false) 76 br label %for.inc 77 78for.inc: ; preds = %for.body 79 %inc = add nuw nsw i64 %i.02, 1 80 %cmp = icmp slt i64 %inc, %conv 81 br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge 82 83for.cond.for.end_crit_edge: ; preds = %for.inc 84 br label %for.end 85 86for.end: ; preds = %for.cond.for.end_crit_edge, %entry 87 ret void 88} 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 i64 101; 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 i64 105; CHECK-NEXT: [[CONV3:%.*]] = sext i32 [[M]] to i64 106; CHECK-NEXT: [[MUL4:%.*]] = mul i64 [[CONV3]], 4 107; 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]], 1 117; 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 void 123; 124entry: 125 %conv = sext i32 %n to i64 126 %cmp1 = icmp slt i64 0, %conv 127 br i1 %cmp1, label %for.body.lr.ph, label %for.end 128 129for.body.lr.ph: ; preds = %entry 130 %conv1 = sext i32 %m to i64 131 %conv3 = sext i32 %m to i64 132 %mul4 = mul i64 %conv3, 4 133 br label %for.body 134 135for.body: ; preds = %for.body.lr.ph, %for.inc 136 %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ] 137 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %i.02 138 %mul = mul nsw i64 %i.02, %conv1 139 %add.ptr2 = getelementptr inbounds i32, ptr %add.ptr, i64 %mul 140 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr2, i8 0, i64 %mul4, i1 false) 141 br label %for.inc 142 143for.inc: ; preds = %for.body 144 %inc = add nuw nsw i64 %i.02, 1 145 %cmp = icmp slt i64 %inc, %conv 146 br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge 147 148for.cond.for.end_crit_edge: ; preds = %for.inc 149 br label %for.end 150 151for.end: ; preds = %for.cond.for.end_crit_edge, %entry 152 ret void 153} 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:%.*]], 2 159; 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]], 1 169; 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 void 173; 174entry: 175 %0 = shl nuw i64 %m, 2 176 br label %for.cond1.preheader 177 178for.cond1.preheader: ; preds = %for.inc4, %entry 179 %i.017 = phi i64 [ 0, %entry ], [ %inc5, %for.inc4 ] 180 %1 = mul i64 %m, %i.017 181 %scevgep = getelementptr i32, ptr addrspace(2) %ar, i64 %1 182 %mul = mul nsw i64 %i.017, %m 183 call void @llvm.memset.p2.i64(ptr addrspace(2) align 4 %scevgep, i8 0, i64 %0, i1 false) 184 br label %for.inc4 185 186for.inc4: ; preds = %for.cond1.preheader 187 %inc5 = add nuw nsw i64 %i.017, 1 188 %exitcond18.not = icmp eq i64 %inc5, %n 189 br i1 %exitcond18.not, label %for.end6, label %for.cond1.preheader 190 191for.end6: ; preds = %for.inc4 192 ret void 193} 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 i64 208; 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 i64 212; CHECK-NEXT: [[CONV2:%.*]] = sext i32 [[M]] to i64 213; CHECK-NEXT: [[MUL3:%.*]] = mul i64 [[CONV2]], 4 214; 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]], 1 225; 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 void 231; 232entry: 233 %conv = sext i32 %n to i64 234 %cmp1 = icmp slt i64 0, %conv 235 br i1 %cmp1, label %for.body.lr.ph, label %for.end 236 237for.body.lr.ph: ; preds = %entry 238 %conv1 = sext i32 %m to i64 239 %conv2 = sext i32 %m to i64 240 %mul3 = mul i64 %conv2, 4 241 br label %for.body 242 243for.body: ; preds = %for.body.lr.ph, %for.inc 244 %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, %conv1 247 %add.ptr = getelementptr inbounds i32, ptr %ar.addr.03, i64 %mul 248 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.02 250 br label %for.inc 251 252for.inc: ; preds = %for.body 253 %inc = add nuw nsw i64 %i.02, 1 254 %cmp = icmp slt i64 %inc, %conv 255 br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge 256 257for.cond.for.end_crit_edge: ; preds = %for.inc 258 br label %for.end 259 260for.end: ; preds = %for.cond.for.end_crit_edge, %entry 261 ret void 262} 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