1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -passes="function(loop(indvars,loop-idiom,loop-deletion),simplifycfg)" -S < %s | FileCheck %s 3; Compile command: 4; $ clang -m32 -fno-discard-value-names -O0 -S -emit-llvm -Xclang -disable-O0-optnone Code.c 5; $ 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.ll 8target datalayout = "e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-f64:32:64-f80:32-n8:16:32-S128" 9; void PositiveFor32(int *ar, int n, int m) 10; { 11; int 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 @PositiveFor32(ptr %ar, i32 %n, i32 %m) { 18; CHECK-LABEL: @PositiveFor32( 19; CHECK-NEXT: entry: 20; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 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 i32 [[M:%.*]], 4 24; CHECK-NEXT: [[TMP0:%.*]] = mul i32 [[M]], [[N]] 25; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[TMP0]], 2 26; CHECK-NEXT: call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP1]], i1 false) 27; CHECK-NEXT: br label [[FOR_END]] 28; CHECK: for.end: 29; CHECK-NEXT: ret void 30; 31entry: 32 %cmp1 = icmp slt i32 0, %n 33 br i1 %cmp1, label %for.body.lr.ph, label %for.end 34 35for.body.lr.ph: ; preds = %entry 36 %mul1 = mul i32 %m, 4 37 br label %for.body 38 39for.body: ; preds = %for.body.lr.ph, %for.body 40 %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ] 41 %mul = mul nsw i32 %i.02, %m 42 %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %mul 43 call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %mul1, i1 false) 44 %inc = add nsw i32 %i.02, 1 45 %cmp = icmp slt i32 %inc, %n 46 br i1 %cmp, label %for.body, label %for.end 47 48for.end: ; preds = %for.body, %entry 49 ret void 50} 51; void Negative32(int *ar, int n, int m) 52; { 53; int 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 void @NegativeFor32(ptr %ar, i32 %n, i32 %m) { 60; CHECK-LABEL: @NegativeFor32( 61; CHECK-NEXT: entry: 62; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[N:%.*]], 1 63; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i32 [[SUB]], 0 64; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]] 65; CHECK: for.body.lr.ph: 66; CHECK-NEXT: [[MUL1:%.*]] = mul i32 [[M:%.*]], 4 67; CHECK-NEXT: [[TMP0:%.*]] = mul i32 [[M]], [[N]] 68; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[TMP0]], 2 69; CHECK-NEXT: call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP1]], i1 false) 70; CHECK-NEXT: br label [[FOR_END]] 71; CHECK: for.end: 72; CHECK-NEXT: ret void 73; 74entry: 75 %sub = sub nsw i32 %n, 1 76 %cmp1 = icmp sge i32 %sub, 0 77 br i1 %cmp1, label %for.body.lr.ph, label %for.end 78 79for.body.lr.ph: ; preds = %entry 80 %mul1 = mul i32 %m, 4 81 br label %for.body 82 83for.body: ; preds = %for.body.lr.ph, %for.body 84 %i.02 = phi i32 [ %sub, %for.body.lr.ph ], [ %dec, %for.body ] 85 %mul = mul nsw i32 %i.02, %m 86 %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %mul 87 call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %mul1, i1 false) 88 %dec = add nsw i32 %i.02, -1 89 %cmp = icmp sge i32 %dec, 0 90 br i1 %cmp, label %for.body, label %for.end 91 92for.end: ; preds = %for.body, %entry 93 ret void 94} 95; void NestedFor32(int *ar, int n, int m, int o) 96; { 97; int 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 @NestedFor32(ptr %ar, i32 %n, i32 %m, i32 %o) { 106; CHECK-LABEL: @NestedFor32( 107; CHECK-NEXT: entry: 108; CHECK-NEXT: [[CMP3:%.*]] = icmp slt i32 0, [[N:%.*]] 109; CHECK-NEXT: [[CMP21:%.*]] = icmp slt i32 0, [[M:%.*]] 110; CHECK-NEXT: [[MUL7:%.*]] = mul i32 [[O:%.*]], 4 111; CHECK-NEXT: [[OR_COND:%.*]] = select i1 [[CMP3]], i1 [[CMP21]], i1 false 112; 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 i32 [[O]], [[M]] 115; CHECK-NEXT: [[TMP1:%.*]] = shl i32 [[TMP0]], 2 116; CHECK-NEXT: [[TMP2:%.*]] = mul i32 [[TMP0]], [[N]] 117; CHECK-NEXT: [[TMP3:%.*]] = shl i32 [[TMP2]], 2 118; CHECK-NEXT: call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP3]], i1 false) 119; CHECK-NEXT: br label [[FOR_END10]] 120; CHECK: for.end10: 121; CHECK-NEXT: ret void 122; 123entry: 124 %cmp3 = icmp slt i32 0, %n 125 br i1 %cmp3, label %for.body.lr.ph, label %for.end10 126 127for.body.lr.ph: ; preds = %entry 128 %cmp21 = icmp slt i32 0, %m 129 %mul7 = mul i32 %o, 4 130 br i1 %cmp21, label %for.body.us.preheader, label %for.end10 131 132for.body.us.preheader: ; preds = %for.body.lr.ph 133 br label %for.body.us 134 135for.body.us: ; preds = %for.body.us.preheader, %for.cond1.for.end_crit_edge.us 136 %i.04.us = phi i32 [ %inc9.us, %for.cond1.for.end_crit_edge.us ], [ 0, %for.body.us.preheader ] 137 %mul.us = mul nsw i32 %i.04.us, %m 138 %mul4.us = mul nsw i32 %mul.us, %o 139 %add.ptr.us = getelementptr inbounds i32, ptr %ar, i32 %mul4.us 140 br label %for.body3.us 141 142for.body3.us: ; preds = %for.body.us, %for.body3.us 143 %j.02.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body3.us ] 144 %mul5.us = mul nsw i32 %j.02.us, %o 145 %add.ptr6.us = getelementptr inbounds i32, ptr %add.ptr.us, i32 %mul5.us 146 call void @llvm.memset.p0.i32(ptr align 4 %add.ptr6.us, i8 0, i32 %mul7, i1 false) 147 %inc.us = add nuw nsw i32 %j.02.us, 1 148 %exitcond = icmp ne i32 %inc.us, %m 149 br i1 %exitcond, label %for.body3.us, label %for.cond1.for.end_crit_edge.us 150 151for.cond1.for.end_crit_edge.us: ; preds = %for.body3.us 152 %inc9.us = add nuw nsw i32 %i.04.us, 1 153 %exitcond5 = icmp ne i32 %inc9.us, %n 154 br i1 %exitcond5, label %for.body.us, label %for.end10.loopexit 155 156for.end10.loopexit: ; preds = %for.cond1.for.end_crit_edge.us 157 br label %for.end10 158 159for.end10: ; preds = %for.end10.loopexit, %for.body.lr.ph, %entry 160 ret void 161} 162; void PositiveFor64(int *ar, long long n, long long 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 dso_local void @PositiveFor64(ptr %ar, i64 %n, i64 %m) #0 { 171; CHECK-LABEL: @PositiveFor64( 172; CHECK-NEXT: entry: 173; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i64 0, [[N:%.*]] 174; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]] 175; CHECK: for.body.lr.ph: 176; CHECK-NEXT: [[MUL3:%.*]] = mul nsw i64 [[M:%.*]], 4 177; CHECK-NEXT: [[CONV4:%.*]] = trunc i64 [[MUL3]] to i32 178; CHECK-NEXT: [[TMP0:%.*]] = trunc i64 [[M]] to i32 179; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[N]] to i32 180; CHECK-NEXT: [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]] 181; CHECK-NEXT: [[TMP3:%.*]] = shl i32 [[TMP2]], 2 182; CHECK-NEXT: call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP3]], i1 false) 183; CHECK-NEXT: br label [[FOR_END]] 184; CHECK: for.end: 185; CHECK-NEXT: ret void 186; 187entry: 188 %cmp1 = icmp slt i64 0, %n 189 br i1 %cmp1, label %for.body.lr.ph, label %for.end 190 191for.body.lr.ph: ; preds = %entry 192 %mul3 = mul nsw i64 %m, 4 193 %conv4 = trunc i64 %mul3 to i32 194 br label %for.body 195 196for.body: ; preds = %for.body.lr.ph, %for.body 197 %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ] 198 %conv2 = sext i32 %i.02 to i64 199 %mul = mul nsw i64 %conv2, %m 200 %idx.ext = trunc i64 %mul to i32 201 %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %idx.ext 202 call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %conv4, i1 false) 203 %inc = add nuw nsw i32 %i.02, 1 204 %conv = sext i32 %inc to i64 205 %cmp = icmp slt i64 %conv, %n 206 br i1 %cmp, label %for.body, label %for.end.loopexit 207 208for.end.loopexit: ; preds = %for.body 209 br label %for.end 210 211for.end: ; preds = %for.end.loopexit, %entry 212 ret void 213} 214; void NegativeFor64(int *ar, long long n, long long m) 215; { 216; int i; 217; for (i=n-1; i>=0; --i) { 218; int *arr = ar + i * m; 219; memset(arr, 0, m * sizeof(int)); 220; } 221; } 222define dso_local void @NegativeFor64(ptr %ar, i64 %n, i64 %m) #0 { 223; CHECK-LABEL: @NegativeFor64( 224; CHECK-NEXT: entry: 225; CHECK-NEXT: [[SUB:%.*]] = sub nsw i64 [[N:%.*]], 1 226; CHECK-NEXT: [[CONV:%.*]] = trunc i64 [[SUB]] to i32 227; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i32 [[CONV]], 0 228; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]] 229; CHECK: for.body.lr.ph: 230; CHECK-NEXT: [[MUL3:%.*]] = mul nsw i64 [[M:%.*]], 4 231; CHECK-NEXT: [[CONV4:%.*]] = trunc i64 [[MUL3]] to i32 232; CHECK-NEXT: [[TMP0:%.*]] = trunc i64 [[M]] to i32 233; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[N]] to i32 234; CHECK-NEXT: [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]] 235; CHECK-NEXT: [[TMP3:%.*]] = shl i32 [[TMP2]], 2 236; CHECK-NEXT: call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP3]], i1 false) 237; CHECK-NEXT: br label [[FOR_END]] 238; CHECK: for.end: 239; CHECK-NEXT: ret void 240; 241entry: 242 %sub = sub nsw i64 %n, 1 243 %conv = trunc i64 %sub to i32 244 %cmp1 = icmp sge i32 %conv, 0 245 br i1 %cmp1, label %for.body.lr.ph, label %for.end 246 247for.body.lr.ph: ; preds = %entry 248 %mul3 = mul nsw i64 %m, 4 249 %conv4 = trunc i64 %mul3 to i32 250 br label %for.body 251 252for.body: ; preds = %for.body.lr.ph, %for.body 253 %i.02 = phi i32 [ %conv, %for.body.lr.ph ], [ %dec, %for.body ] 254 %conv2 = sext i32 %i.02 to i64 255 %mul = mul nsw i64 %conv2, %m 256 %idx.ext = trunc i64 %mul to i32 257 %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %idx.ext 258 call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %conv4, i1 false) 259 %dec = add nsw i32 %i.02, -1 260 %cmp = icmp sge i32 %dec, 0 261 br i1 %cmp, label %for.body, label %for.end.loopexit 262 263for.end.loopexit: ; preds = %for.body 264 br label %for.end 265 266for.end: ; preds = %for.end.loopexit, %entry 267 ret void 268} 269; void NestedFor64(int *ar, long long n, long long m, long long o) 270; { 271; int i, j; 272; for (i=0; i<n; ++i) { 273; for (j=0; j<m; j++) { 274; int *arr = ar + i * m * o + j * o; 275; memset(arr, 0, o * sizeof(int)); 276; } 277; } 278; } 279define dso_local void @NestedFor64(ptr %ar, i64 %n, i64 %m, i64 %o) #0 { 280; CHECK-LABEL: @NestedFor64( 281; CHECK-NEXT: entry: 282; CHECK-NEXT: [[CMP3:%.*]] = icmp slt i64 0, [[N:%.*]] 283; CHECK-NEXT: [[CMP41:%.*]] = icmp slt i64 0, [[M:%.*]] 284; CHECK-NEXT: [[MUL13:%.*]] = mul nsw i64 [[O:%.*]], 4 285; CHECK-NEXT: [[CONV14:%.*]] = trunc i64 [[MUL13]] to i32 286; CHECK-NEXT: [[OR_COND:%.*]] = select i1 [[CMP3]], i1 [[CMP41]], i1 false 287; CHECK-NEXT: br i1 [[OR_COND]], label [[FOR_BODY_US_PREHEADER:%.*]], label [[FOR_END17:%.*]] 288; CHECK: for.body.us.preheader: 289; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[O]], [[M]] 290; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[TMP0]] to i32 291; CHECK-NEXT: [[TMP2:%.*]] = shl i32 [[TMP1]], 2 292; CHECK-NEXT: [[TMP3:%.*]] = trunc i64 [[O]] to i32 293; CHECK-NEXT: [[TMP4:%.*]] = trunc i64 [[M]] to i32 294; CHECK-NEXT: [[TMP5:%.*]] = mul i32 [[TMP3]], [[TMP4]] 295; CHECK-NEXT: [[TMP6:%.*]] = shl i32 [[TMP5]], 2 296; CHECK-NEXT: br label [[FOR_BODY_US:%.*]] 297; CHECK: for.body.us: 298; CHECK-NEXT: [[I_04_US:%.*]] = phi i32 [ [[INC16_US:%.*]], [[FOR_BODY_US]] ], [ 0, [[FOR_BODY_US_PREHEADER]] ] 299; CHECK-NEXT: [[TMP7:%.*]] = mul i32 [[TMP2]], [[I_04_US]] 300; CHECK-NEXT: [[UGLYGEP:%.*]] = getelementptr i8, ptr [[AR:%.*]], i32 [[TMP7]] 301; CHECK-NEXT: [[CONV7_US:%.*]] = sext i32 [[I_04_US]] to i64 302; CHECK-NEXT: [[MUL_US:%.*]] = mul nsw i64 [[CONV7_US]], [[M]] 303; CHECK-NEXT: [[MUL8_US:%.*]] = mul nsw i64 [[MUL_US]], [[O]] 304; CHECK-NEXT: [[IDX_EXT_US:%.*]] = trunc i64 [[MUL8_US]] to i32 305; CHECK-NEXT: [[ADD_PTR_US:%.*]] = getelementptr inbounds i32, ptr [[AR]], i32 [[IDX_EXT_US]] 306; CHECK-NEXT: call void @llvm.memset.p0.i32(ptr align 4 [[UGLYGEP]], i8 0, i32 [[TMP6]], i1 false) 307; CHECK-NEXT: [[INC16_US]] = add nuw nsw i32 [[I_04_US]], 1 308; CHECK-NEXT: [[CONV_US:%.*]] = sext i32 [[INC16_US]] to i64 309; CHECK-NEXT: [[CMP_US:%.*]] = icmp slt i64 [[CONV_US]], [[N]] 310; CHECK-NEXT: br i1 [[CMP_US]], label [[FOR_BODY_US]], label [[FOR_END17]] 311; CHECK: for.end17: 312; CHECK-NEXT: ret void 313; 314entry: 315 %cmp3 = icmp slt i64 0, %n 316 br i1 %cmp3, label %for.body.lr.ph, label %for.end17 317 318for.body.lr.ph: ; preds = %entry 319 %cmp41 = icmp slt i64 0, %m 320 %mul13 = mul nsw i64 %o, 4 321 %conv14 = trunc i64 %mul13 to i32 322 br i1 %cmp41, label %for.body.us.preheader, label %for.end17 323 324for.body.us.preheader: ; preds = %for.body.lr.ph 325 br label %for.body.us 326 327for.body.us: ; preds = %for.body.us.preheader, %for.cond2.for.end_crit_edge.us 328 %i.04.us = phi i32 [ %inc16.us, %for.cond2.for.end_crit_edge.us ], [ 0, %for.body.us.preheader ] 329 %conv7.us = sext i32 %i.04.us to i64 330 %mul.us = mul nsw i64 %conv7.us, %m 331 %mul8.us = mul nsw i64 %mul.us, %o 332 %idx.ext.us = trunc i64 %mul8.us to i32 333 %add.ptr.us = getelementptr inbounds i32, ptr %ar, i32 %idx.ext.us 334 br label %for.body6.us 335 336for.body6.us: ; preds = %for.body.us, %for.body6.us 337 %j.02.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body6.us ] 338 %conv9.us = sext i32 %j.02.us to i64 339 %mul10.us = mul nsw i64 %conv9.us, %o 340 %idx.ext11.us = trunc i64 %mul10.us to i32 341 %add.ptr12.us = getelementptr inbounds i32, ptr %add.ptr.us, i32 %idx.ext11.us 342 call void @llvm.memset.p0.i32(ptr align 4 %add.ptr12.us, i8 0, i32 %conv14, i1 false) 343 %inc.us = add nuw nsw i32 %j.02.us, 1 344 %conv3.us = sext i32 %inc.us to i64 345 %cmp4.us = icmp slt i64 %conv3.us, %m 346 br i1 %cmp4.us, label %for.body6.us, label %for.cond2.for.end_crit_edge.us 347 348for.cond2.for.end_crit_edge.us: ; preds = %for.body6.us 349 %inc16.us = add nuw nsw i32 %i.04.us, 1 350 %conv.us = sext i32 %inc16.us to i64 351 %cmp.us = icmp slt i64 %conv.us, %n 352 br i1 %cmp.us, label %for.body.us, label %for.end17.loopexit 353 354for.end17.loopexit: ; preds = %for.cond2.for.end_crit_edge.us 355 br label %for.end17 356 357for.end17: ; preds = %for.end17.loopexit, %for.body.lr.ph, %entry 358 ret void 359} 360 361; void NegStart(int n, int m, int *ar) { 362; for (int i = -100; i < n; i++) { 363; int *arr = ar + (i + 100) * m; 364; memset(arr, 0, m * sizeof(int)); 365; } 366; } 367define void @NegStart(i32 %n, i32 %m, ptr %ar) { 368; CHECK-LABEL: @NegStart( 369; CHECK-NEXT: entry: 370; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 -100, [[N:%.*]] 371; CHECK-NEXT: br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]] 372; CHECK: for.body.lr.ph: 373; CHECK-NEXT: [[MUL1:%.*]] = mul i32 [[M:%.*]], 4 374; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N]], 100 375; CHECK-NEXT: [[TMP1:%.*]] = mul i32 [[M]], [[TMP0]] 376; CHECK-NEXT: [[TMP2:%.*]] = shl i32 [[TMP1]], 2 377; CHECK-NEXT: call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP2]], i1 false) 378; CHECK-NEXT: br label [[FOR_END]] 379; CHECK: for.end: 380; CHECK-NEXT: ret void 381; 382entry: 383 %cmp1 = icmp slt i32 -100, %n 384 br i1 %cmp1, label %for.body.lr.ph, label %for.end 385 386for.body.lr.ph: ; preds = %entry 387 %mul1 = mul i32 %m, 4 388 br label %for.body 389 390for.body: ; preds = %for.body.lr.ph, %for.body 391 %i.02 = phi i32 [ -100, %for.body.lr.ph ], [ %inc, %for.body ] 392 %add = add nsw i32 %i.02, 100 393 %mul = mul nsw i32 %add, %m 394 %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %mul 395 call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %mul1, i1 false) 396 %inc = add nsw i32 %i.02, 1 397 %exitcond = icmp ne i32 %inc, %n 398 br i1 %exitcond, label %for.body, label %for.end.loopexit 399 400for.end.loopexit: ; preds = %for.body 401 br label %for.end 402 403for.end: ; preds = %for.end.loopexit, %entry 404 ret void 405} 406 407declare void @llvm.memset.p0.i32(ptr nocapture writeonly, i8, i32, i1 immarg) 408