402 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -passes="function(loop(indvars,loop-idiom,loop-deletion),simplifycfg)" -S < %s | FileCheck %s3; Compile command:4; $ clang -m64 -fno-discard-value-names -O0 -S -emit-llvm -Xclang -disable-O0-optnone Code.c5; $ bin/opt -S -passes=mem2reg,loop-simplify,lcssa,loop-rotate \6; -passes=licm,simple-loop-unswitch -enable-nontrivial-unswitch -passes=loop-simplify \7; -passes=loop-deletion,simplifycfg,indvars Code.ll > CodeOpt.ll8target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"9; void PositiveFor64(int *ar, long long n, long long m)10; {11; long long i;12; for (i=0; i<n; ++i) {13; int *arr = ar + i * m;14; memset(arr, 0, m * sizeof(int));15; }16; }17define dso_local void @PositiveFor64(ptr %ar, i64 %n, i64 %m) {18; CHECK-LABEL: @PositiveFor64(19; CHECK-NEXT: entry:20; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i64 0, [[N:%.*]]21; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]22; CHECK: for.body.lr.ph:23; CHECK-NEXT: [[MUL1:%.*]] = mul i64 [[M:%.*]], 424; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[M]], [[N]]25; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[TMP0]], 226; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[AR:%.*]], i8 0, i64 [[TMP1]], i1 false)27; CHECK-NEXT: br label [[FOR_END]]28; CHECK: for.end:29; CHECK-NEXT: ret void30;31entry:32 %cmp1 = icmp slt i64 0, %n33 br i1 %cmp1, label %for.body.lr.ph, label %for.end34 35for.body.lr.ph: ; preds = %entry36 %mul1 = mul i64 %m, 437 br label %for.body38 39for.body: ; preds = %for.body.lr.ph, %for.body40 %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]41 %mul = mul nsw i64 %i.02, %m42 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %mul43 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %mul1, i1 false)44 %inc = add nsw i64 %i.02, 145 %cmp = icmp slt i64 %inc, %n46 br i1 %cmp, label %for.body, label %for.end47 48for.end: ; preds = %for.body, %entry49 ret void50}51; void NegativeFor64(int *ar, long long n, long long m)52; {53; long long i;54; for (i=n-1; i>=0; --i) {55; int *arr = ar + i * m;56; memset(arr, 0, m * sizeof(int));57; }58; }59define dso_local void @NegativeFor64(ptr %ar, i64 %n, i64 %m) {60; CHECK-LABEL: @NegativeFor64(61; CHECK-NEXT: entry:62; CHECK-NEXT: [[SUB:%.*]] = sub nsw i64 [[N:%.*]], 163; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i64 [[SUB]], 064; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]65; CHECK: for.body.lr.ph:66; CHECK-NEXT: [[MUL1:%.*]] = mul i64 [[M:%.*]], 467; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[M]], [[N]]68; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[TMP0]], 269; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[AR:%.*]], i8 0, i64 [[TMP1]], i1 false)70; CHECK-NEXT: br label [[FOR_END]]71; CHECK: for.end:72; CHECK-NEXT: ret void73;74entry:75 %sub = sub nsw i64 %n, 176 %cmp1 = icmp sge i64 %sub, 077 br i1 %cmp1, label %for.body.lr.ph, label %for.end78 79for.body.lr.ph: ; preds = %entry80 %mul1 = mul i64 %m, 481 br label %for.body82 83for.body: ; preds = %for.body.lr.ph, %for.body84 %i.02 = phi i64 [ %sub, %for.body.lr.ph ], [ %dec, %for.body ]85 %mul = mul nsw i64 %i.02, %m86 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %mul87 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %mul1, i1 false)88 %dec = add nsw i64 %i.02, -189 %cmp = icmp sge i64 %dec, 090 br i1 %cmp, label %for.body, label %for.end91 92for.end: ; preds = %for.body, %entry93 ret void94}95; void NestedFor64(int *ar, long long n, long long m, long long o)96; {97; long long i, j;98; for (i=0; i<n; ++i) {99; for (j=0; j<m; j++) {100; int *arr = ar + i * m * o + j * o;101; memset(arr, 0, o * sizeof(int));102; }103; }104; }105define void @NestedFor64(ptr %ar, i64 %n, i64 %m, i64 %o) {106; CHECK-LABEL: @NestedFor64(107; CHECK-NEXT: entry:108; CHECK-NEXT: [[CMP3:%.*]] = icmp slt i64 0, [[N:%.*]]109; CHECK-NEXT: [[CMP21:%.*]] = icmp slt i64 0, [[M:%.*]]110; CHECK-NEXT: [[MUL7:%.*]] = mul i64 [[O:%.*]], 4111; CHECK-NEXT: [[OR_COND:%.*]] = select i1 [[CMP3]], i1 [[CMP21]], i1 false112; CHECK-NEXT: br i1 [[OR_COND]], label [[FOR_BODY_US_PREHEADER:%.*]], label [[FOR_END10:%.*]]113; CHECK: for.body.us.preheader:114; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[O]], [[M]]115; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[TMP0]], 2116; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[TMP0]], [[N]]117; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2118; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[AR:%.*]], i8 0, i64 [[TMP3]], i1 false)119; CHECK-NEXT: br label [[FOR_END10]]120; CHECK: for.end10:121; CHECK-NEXT: ret void122;123entry:124 %cmp3 = icmp slt i64 0, %n125 br i1 %cmp3, label %for.body.lr.ph, label %for.end10126 127for.body.lr.ph: ; preds = %entry128 %cmp21 = icmp slt i64 0, %m129 %mul7 = mul i64 %o, 4130 br i1 %cmp21, label %for.body.us.preheader, label %for.end10131 132for.body.us.preheader: ; preds = %for.body.lr.ph133 br label %for.body.us134 135for.body.us: ; preds = %for.body.us.preheader, %for.cond1.for.end_crit_edge.us136 %i.04.us = phi i64 [ %inc9.us, %for.cond1.for.end_crit_edge.us ], [ 0, %for.body.us.preheader ]137 %mul.us = mul nsw i64 %i.04.us, %m138 %mul4.us = mul nsw i64 %mul.us, %o139 %add.ptr.us = getelementptr inbounds i32, ptr %ar, i64 %mul4.us140 br label %for.body3.us141 142for.body3.us: ; preds = %for.body.us, %for.body3.us143 %j.02.us = phi i64 [ 0, %for.body.us ], [ %inc.us, %for.body3.us ]144 %mul5.us = mul nsw i64 %j.02.us, %o145 %add.ptr6.us = getelementptr inbounds i32, ptr %add.ptr.us, i64 %mul5.us146 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr6.us, i8 0, i64 %mul7, i1 false)147 %inc.us = add nuw nsw i64 %j.02.us, 1148 %exitcond = icmp ne i64 %inc.us, %m149 br i1 %exitcond, label %for.body3.us, label %for.cond1.for.end_crit_edge.us150 151for.cond1.for.end_crit_edge.us: ; preds = %for.body3.us152 %inc9.us = add nuw nsw i64 %i.04.us, 1153 %exitcond5 = icmp ne i64 %inc9.us, %n154 br i1 %exitcond5, label %for.body.us, label %for.end10.loopexit155 156for.end10.loopexit: ; preds = %for.cond1.for.end_crit_edge.us157 br label %for.end10158 159for.end10: ; preds = %for.end10.loopexit, %for.body.lr.ph, %entry160 ret void161}162; void PositiveFor32(int *ar, int n, int m)163; {164; int i;165; for (i=0; i<n; ++i) {166; int *arr = ar + i * m;167; memset(arr, 0, m * sizeof(int));168; }169; }170define void @PositiveFor32(ptr %ar, i32 %n, i32 %m) {171; CHECK-LABEL: @PositiveFor32(172; CHECK-NEXT: entry:173; CHECK-NEXT: [[CONV:%.*]] = sext i32 [[N:%.*]] to i64174; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i64 0, [[CONV]]175; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]176; CHECK: for.body.lr.ph:177; CHECK-NEXT: [[CONV1:%.*]] = sext i32 [[M:%.*]] to i64178; CHECK-NEXT: [[CONV2:%.*]] = sext i32 [[M]] to i64179; CHECK-NEXT: [[MUL3:%.*]] = mul i64 [[CONV2]], 4180; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[CONV1]], [[CONV]]181; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[TMP0]], 2182; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[AR:%.*]], i8 0, i64 [[TMP1]], i1 false)183; CHECK-NEXT: br label [[FOR_END]]184; CHECK: for.end:185; CHECK-NEXT: ret void186;187entry:188 %conv = sext i32 %n to i64189 %cmp1 = icmp slt i64 0, %conv190 br i1 %cmp1, label %for.body.lr.ph, label %for.end191 192for.body.lr.ph: ; preds = %entry193 %conv1 = sext i32 %m to i64194 %conv2 = sext i32 %m to i64195 %mul3 = mul i64 %conv2, 4196 br label %for.body197 198for.body: ; preds = %for.body.lr.ph, %for.body199 %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]200 %mul = mul nsw i64 %i.02, %conv1201 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %mul202 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %mul3, i1 false)203 %inc = add nsw i64 %i.02, 1204 %cmp = icmp slt i64 %inc, %conv205 br i1 %cmp, label %for.body, label %for.end206 207for.end: ; preds = %for.body, %entry208 ret void209}210; void Negative32(int *ar, int n, int m)211; {212; long long i;213; for (i=n-1; i>=0; i--) {214; int *arr = ar + i * m;215; memset(arr, 0, m * sizeof(int));216; }217; }218define void @Negative32(ptr %ar, i32 %n, i32 %m) {219; CHECK-LABEL: @Negative32(220; CHECK-NEXT: entry:221; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[N:%.*]], 1222; CHECK-NEXT: [[CONV:%.*]] = sext i32 [[SUB]] to i64223; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i64 [[CONV]], 0224; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]225; CHECK: for.body.lr.ph:226; CHECK-NEXT: [[CONV1:%.*]] = sext i32 [[M:%.*]] to i64227; CHECK-NEXT: [[CONV2:%.*]] = sext i32 [[M]] to i64228; CHECK-NEXT: [[MUL3:%.*]] = mul i64 [[CONV2]], 4229; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[N]] to i64230; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[CONV1]], [[TMP0]]231; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2232; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[AR:%.*]], i8 0, i64 [[TMP2]], i1 false)233; CHECK-NEXT: br label [[FOR_END]]234; CHECK: for.end:235; CHECK-NEXT: ret void236;237entry:238 %sub = sub nsw i32 %n, 1239 %conv = sext i32 %sub to i64240 %cmp1 = icmp sge i64 %conv, 0241 br i1 %cmp1, label %for.body.lr.ph, label %for.end242 243for.body.lr.ph: ; preds = %entry244 %conv1 = sext i32 %m to i64245 %conv2 = sext i32 %m to i64246 %mul3 = mul i64 %conv2, 4247 br label %for.body248 249for.body: ; preds = %for.body.lr.ph, %for.body250 %i.02 = phi i64 [ %conv, %for.body.lr.ph ], [ %dec, %for.body ]251 %mul = mul nsw i64 %i.02, %conv1252 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %mul253 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %mul3, i1 false)254 %dec = add nsw i64 %i.02, -1255 %cmp = icmp sge i64 %dec, 0256 br i1 %cmp, label %for.body, label %for.end257 258for.end: ; preds = %for.body, %entry259 ret void260}261; This case requires SCEVFolder in LoopIdiomRecognize.cpp to fold SCEV prior to comparison.262; For the inner-loop, SCEVFolder is not needed, however the promoted memset size would be based263; on the trip count of inner-loop (which is an unsigned integer).264; Then in the outer loop, the pointer stride SCEV for memset needs to be converted based on the265; loop guard for it to equal to the memset size SCEV. The loop guard guaranteeds that m >= 0266; inside the loop, so m can be converted from sext to zext, making the two SCEV-s equal.267; void NestedFor32(int *ar, int n, int m, int o)268; {269; int i, j;270; for (i=0; i<n; ++i) {271; for (j=0; j<m; j++) {272; int *arr = ar + i * m * o + j * o;273; memset(arr, 0, o * sizeof(int));274; }275; }276; }277define void @NestedFor32(ptr %ar, i32 %n, i32 %m, i32 %o) {278; CHECK-LABEL: @NestedFor32(279; CHECK-NEXT: entry:280; CHECK-NEXT: [[CMP3:%.*]] = icmp slt i32 0, [[N:%.*]]281; CHECK-NEXT: br i1 [[CMP3]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END11:%.*]]282; CHECK: for.body.lr.ph:283; CHECK-NEXT: [[CMP21:%.*]] = icmp slt i32 0, [[M:%.*]]284; CHECK-NEXT: [[CONV:%.*]] = sext i32 [[O:%.*]] to i64285; CHECK-NEXT: [[MUL8:%.*]] = mul i64 [[CONV]], 4286; CHECK-NEXT: br i1 [[CMP21]], label [[FOR_BODY_US_PREHEADER:%.*]], label [[FOR_END11]]287; CHECK: for.body.us.preheader:288; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[O]] to i64289; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[M]] to i64290; CHECK-NEXT: [[WIDE_TRIP_COUNT10:%.*]] = zext i32 [[N]] to i64291; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[TMP0]], [[TMP1]]292; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2293; CHECK-NEXT: [[TMP4:%.*]] = zext i32 [[M]] to i64294; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[TMP0]], [[TMP4]]295; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2296; CHECK-NEXT: [[TMP7:%.*]] = mul i64 [[TMP5]], [[WIDE_TRIP_COUNT10]]297; CHECK-NEXT: [[TMP8:%.*]] = shl i64 [[TMP7]], 2298; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[AR:%.*]], i8 0, i64 [[TMP8]], i1 false)299; CHECK-NEXT: br label [[FOR_END11]]300; CHECK: for.end11:301; CHECK-NEXT: ret void302;303entry:304 %cmp3 = icmp slt i32 0, %n305 br i1 %cmp3, label %for.body.lr.ph, label %for.end11306 307for.body.lr.ph: ; preds = %entry308 %cmp21 = icmp slt i32 0, %m309 %conv = sext i32 %o to i64310 %mul8 = mul i64 %conv, 4311 br i1 %cmp21, label %for.body.us.preheader, label %for.end11312 313for.body.us.preheader: ; preds = %for.body.lr.ph314 %0 = sext i32 %o to i64315 %1 = sext i32 %m to i64316 %2 = sext i32 %o to i64317 %wide.trip.count10 = zext i32 %n to i64318 br label %for.body.us319 320for.body.us: ; preds = %for.body.us.preheader, %for.cond1.for.end_crit_edge.us321 %indvars.iv6 = phi i64 [ 0, %for.body.us.preheader ], [ %indvars.iv.next7, %for.cond1.for.end_crit_edge.us ]322 %3 = mul nsw i64 %indvars.iv6, %1323 %4 = mul nsw i64 %3, %2324 %add.ptr.us = getelementptr inbounds i32, ptr %ar, i64 %4325 %wide.trip.count = zext i32 %m to i64326 br label %for.body3.us327 328for.body3.us: ; preds = %for.body.us, %for.body3.us329 %indvars.iv = phi i64 [ 0, %for.body.us ], [ %indvars.iv.next, %for.body3.us ]330 %5 = mul nsw i64 %indvars.iv, %0331 %add.ptr7.us = getelementptr inbounds i32, ptr %add.ptr.us, i64 %5332 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr7.us, i8 0, i64 %mul8, i1 false)333 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1334 %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count335 br i1 %exitcond, label %for.body3.us, label %for.cond1.for.end_crit_edge.us336 337for.cond1.for.end_crit_edge.us: ; preds = %for.body3.us338 %indvars.iv.next7 = add nuw nsw i64 %indvars.iv6, 1339 %exitcond11 = icmp ne i64 %indvars.iv.next7, %wide.trip.count10340 br i1 %exitcond11, label %for.body.us, label %for.end11.loopexit341 342for.end11.loopexit: ; preds = %for.cond1.for.end_crit_edge.us343 br label %for.end11344 345for.end11: ; preds = %for.end11.loopexit, %for.body.lr.ph, %entry346 ret void347}348 349; void NegStart(int n, int m, int *ar) {350; for (int i = -100; i < n; i++) {351; int *arr = ar + (i + 100) * m;352; memset(arr, 0, m * sizeof(int));353; }354; }355define void @NegStart(i32 %n, i32 %m, ptr %ar) {356; CHECK-LABEL: @NegStart(357; CHECK-NEXT: entry:358; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 -100, [[N:%.*]]359; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]360; CHECK: for.body.lr.ph:361; CHECK-NEXT: [[CONV:%.*]] = sext i32 [[M:%.*]] to i64362; CHECK-NEXT: [[MUL1:%.*]] = mul i64 [[CONV]], 4363; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[M]] to i64364; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = sext i32 [[N]] to i64365; CHECK-NEXT: [[TMP1:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], 100366; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[TMP1]], [[TMP0]]367; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2368; CHECK-NEXT: call void @llvm.memset.p0.i64(ptr align 4 [[AR:%.*]], i8 0, i64 [[TMP3]], i1 false)369; CHECK-NEXT: br label [[FOR_END]]370; CHECK: for.end:371; CHECK-NEXT: ret void372;373entry:374 %cmp1 = icmp slt i32 -100, %n375 br i1 %cmp1, label %for.body.lr.ph, label %for.end376 377for.body.lr.ph: ; preds = %entry378 %conv = sext i32 %m to i64379 %mul1 = mul i64 %conv, 4380 %0 = sext i32 %m to i64381 %wide.trip.count = sext i32 %n to i64382 br label %for.body383 384for.body: ; preds = %for.body.lr.ph, %for.body385 %indvars.iv = phi i64 [ -100, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]386 %1 = add nsw i64 %indvars.iv, 100387 %2 = mul nsw i64 %1, %0388 %add.ptr = getelementptr inbounds i32, ptr %ar, i64 %2389 call void @llvm.memset.p0.i64(ptr align 4 %add.ptr, i8 0, i64 %mul1, i1 false)390 %indvars.iv.next = add nsw i64 %indvars.iv, 1391 %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count392 br i1 %exitcond, label %for.body, label %for.end.loopexit393 394for.end.loopexit: ; preds = %for.body395 br label %for.end396 397for.end: ; preds = %for.end.loopexit, %entry398 ret void399}400 401declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg)402