; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes="function(loop(indvars,loop-idiom,loop-deletion),simplifycfg)" -S < %s | FileCheck %s
; Compile command:
; $ clang -m32 -fno-discard-value-names -O0 -S -emit-llvm -Xclang -disable-O0-optnone Code.c
; $ bin/opt -S -passes=mem2reg,loop-simplify,lcssa,loop-rotate \
; -passes=licm,simple-loop-unswitch -enable-nontrivial-unswitch -passes=loop-simplify \
; -passes=loop-deletion,simplifycfg,indvars Code.ll > CodeOpt.ll
target 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"
; void PositiveFor32(int *ar, int n, int m)
; {
;   int i;
;   for (i=0; i<n; ++i) {
;     int *arr = ar + i * m;
;     memset(arr, 0, m * sizeof(int));
;   }
; }
define dso_local void @PositiveFor32(ptr %ar, i32 %n, i32 %m) {
; CHECK-LABEL: @PositiveFor32(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 0, [[N:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
; CHECK:       for.body.lr.ph:
; CHECK-NEXT:    [[MUL1:%.*]] = mul i32 [[M:%.*]], 4
; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], [[N]]
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[TMP0]], 2
; CHECK-NEXT:    call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP1]], i1 false)
; CHECK-NEXT:    br label [[FOR_END]]
; CHECK:       for.end:
; CHECK-NEXT:    ret void
;
entry:
  %cmp1 = icmp slt i32 0, %n
  br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
  %mul1 = mul i32 %m, 4
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph, %for.body
  %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
  %mul = mul nsw i32 %i.02, %m
  %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %mul
  call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %mul1, i1 false)
  %inc = add nsw i32 %i.02, 1
  %cmp = icmp slt i32 %inc, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}
; void Negative32(int *ar, int n, int m)
; {
;   int i;
;   for (i=n-1; i>=0; i--) {
;     int *arr = ar + i * m;
;     memset(arr, 0, m * sizeof(int));
;   }
; }
define void @NegativeFor32(ptr %ar, i32 %n, i32 %m) {
; CHECK-LABEL: @NegativeFor32(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[N:%.*]], 1
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[SUB]], 0
; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
; CHECK:       for.body.lr.ph:
; CHECK-NEXT:    [[MUL1:%.*]] = mul i32 [[M:%.*]], 4
; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[M]], [[N]]
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[TMP0]], 2
; CHECK-NEXT:    call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP1]], i1 false)
; CHECK-NEXT:    br label [[FOR_END]]
; CHECK:       for.end:
; CHECK-NEXT:    ret void
;
entry:
  %sub = sub nsw i32 %n, 1
  %cmp1 = icmp sge i32 %sub, 0
  br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
  %mul1 = mul i32 %m, 4
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph, %for.body
  %i.02 = phi i32 [ %sub, %for.body.lr.ph ], [ %dec, %for.body ]
  %mul = mul nsw i32 %i.02, %m
  %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %mul
  call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %mul1, i1 false)
  %dec = add nsw i32 %i.02, -1
  %cmp = icmp sge i32 %dec, 0
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}
; void NestedFor32(int *ar, int n, int m, int o)
; {
;   int i, j;
;   for (i=0; i<n; ++i) {
;     for (j=0; j<m; ++j) {
;       int *arr = ar + i * m * o + j * o;
;       memset(arr, 0, o * sizeof(int));
;     }
;   }
; }
define void @NestedFor32(ptr %ar, i32 %n, i32 %m, i32 %o) {
; CHECK-LABEL: @NestedFor32(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP3:%.*]] = icmp slt i32 0, [[N:%.*]]
; CHECK-NEXT:    [[CMP21:%.*]] = icmp slt i32 0, [[M:%.*]]
; CHECK-NEXT:    [[MUL7:%.*]] = mul i32 [[O:%.*]], 4
; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP3]], i1 [[CMP21]], i1 false
; CHECK-NEXT:    br i1 [[OR_COND]], label [[FOR_BODY_US_PREHEADER:%.*]], label [[FOR_END10:%.*]]
; CHECK:       for.body.us.preheader:
; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[O]], [[M]]
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[TMP0]], 2
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], [[N]]
; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP2]], 2
; CHECK-NEXT:    call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP3]], i1 false)
; CHECK-NEXT:    br label [[FOR_END10]]
; CHECK:       for.end10:
; CHECK-NEXT:    ret void
;
entry:
  %cmp3 = icmp slt i32 0, %n
  br i1 %cmp3, label %for.body.lr.ph, label %for.end10

for.body.lr.ph:                                   ; preds = %entry
  %cmp21 = icmp slt i32 0, %m
  %mul7 = mul i32 %o, 4
  br i1 %cmp21, label %for.body.us.preheader, label %for.end10

for.body.us.preheader:                            ; preds = %for.body.lr.ph
  br label %for.body.us

for.body.us:                                      ; preds = %for.body.us.preheader, %for.cond1.for.end_crit_edge.us
  %i.04.us = phi i32 [ %inc9.us, %for.cond1.for.end_crit_edge.us ], [ 0, %for.body.us.preheader ]
  %mul.us = mul nsw i32 %i.04.us, %m
  %mul4.us = mul nsw i32 %mul.us, %o
  %add.ptr.us = getelementptr inbounds i32, ptr %ar, i32 %mul4.us
  br label %for.body3.us

for.body3.us:                                     ; preds = %for.body.us, %for.body3.us
  %j.02.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body3.us ]
  %mul5.us = mul nsw i32 %j.02.us, %o
  %add.ptr6.us = getelementptr inbounds i32, ptr %add.ptr.us, i32 %mul5.us
  call void @llvm.memset.p0.i32(ptr align 4 %add.ptr6.us, i8 0, i32 %mul7, i1 false)
  %inc.us = add nuw nsw i32 %j.02.us, 1
  %exitcond = icmp ne i32 %inc.us, %m
  br i1 %exitcond, label %for.body3.us, label %for.cond1.for.end_crit_edge.us

for.cond1.for.end_crit_edge.us:                   ; preds = %for.body3.us
  %inc9.us = add nuw nsw i32 %i.04.us, 1
  %exitcond5 = icmp ne i32 %inc9.us, %n
  br i1 %exitcond5, label %for.body.us, label %for.end10.loopexit

for.end10.loopexit:                               ; preds = %for.cond1.for.end_crit_edge.us
  br label %for.end10

for.end10:                                        ; preds = %for.end10.loopexit, %for.body.lr.ph, %entry
  ret void
}
; void PositiveFor64(int *ar, long long n, long long m)
; {
;   int i;
;   for (i=0; i<n; ++i) {
;     int *arr = ar + i * m;
;     memset(arr, 0, m * sizeof(int));
;   }
; }
define dso_local void @PositiveFor64(ptr %ar, i64 %n, i64 %m) #0 {
; CHECK-LABEL: @PositiveFor64(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 0, [[N:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
; CHECK:       for.body.lr.ph:
; CHECK-NEXT:    [[MUL3:%.*]] = mul nsw i64 [[M:%.*]], 4
; CHECK-NEXT:    [[CONV4:%.*]] = trunc i64 [[MUL3]] to i32
; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[M]] to i32
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[N]] to i32
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP2]], 2
; CHECK-NEXT:    call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP3]], i1 false)
; CHECK-NEXT:    br label [[FOR_END]]
; CHECK:       for.end:
; CHECK-NEXT:    ret void
;
entry:
  %cmp1 = icmp slt i64 0, %n
  br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
  %mul3 = mul nsw i64 %m, 4
  %conv4 = trunc i64 %mul3 to i32
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph, %for.body
  %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
  %conv2 = sext i32 %i.02 to i64
  %mul = mul nsw i64 %conv2, %m
  %idx.ext = trunc i64 %mul to i32
  %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %idx.ext
  call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %conv4, i1 false)
  %inc = add nuw nsw i32 %i.02, 1
  %conv = sext i32 %inc to i64
  %cmp = icmp slt i64 %conv, %n
  br i1 %cmp, label %for.body, label %for.end.loopexit

for.end.loopexit:                                 ; preds = %for.body
  br label %for.end

for.end:                                          ; preds = %for.end.loopexit, %entry
  ret void
}
; void NegativeFor64(int *ar, long long n, long long m)
; {
;   int i;
;   for (i=n-1; i>=0; --i) {
;     int *arr = ar + i * m;
;     memset(arr, 0, m * sizeof(int));
;   }
; }
define dso_local void @NegativeFor64(ptr %ar, i64 %n, i64 %m) #0 {
; CHECK-LABEL: @NegativeFor64(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i64 [[N:%.*]], 1
; CHECK-NEXT:    [[CONV:%.*]] = trunc i64 [[SUB]] to i32
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[CONV]], 0
; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
; CHECK:       for.body.lr.ph:
; CHECK-NEXT:    [[MUL3:%.*]] = mul nsw i64 [[M:%.*]], 4
; CHECK-NEXT:    [[CONV4:%.*]] = trunc i64 [[MUL3]] to i32
; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[M]] to i32
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[N]] to i32
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP2]], 2
; CHECK-NEXT:    call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP3]], i1 false)
; CHECK-NEXT:    br label [[FOR_END]]
; CHECK:       for.end:
; CHECK-NEXT:    ret void
;
entry:
  %sub = sub nsw i64 %n, 1
  %conv = trunc i64 %sub to i32
  %cmp1 = icmp sge i32 %conv, 0
  br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
  %mul3 = mul nsw i64 %m, 4
  %conv4 = trunc i64 %mul3 to i32
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph, %for.body
  %i.02 = phi i32 [ %conv, %for.body.lr.ph ], [ %dec, %for.body ]
  %conv2 = sext i32 %i.02 to i64
  %mul = mul nsw i64 %conv2, %m
  %idx.ext = trunc i64 %mul to i32
  %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %idx.ext
  call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %conv4, i1 false)
  %dec = add nsw i32 %i.02, -1
  %cmp = icmp sge i32 %dec, 0
  br i1 %cmp, label %for.body, label %for.end.loopexit

for.end.loopexit:                                 ; preds = %for.body
  br label %for.end

for.end:                                          ; preds = %for.end.loopexit, %entry
  ret void
}
; void NestedFor64(int *ar, long long n, long long m, long long o)
; {
;   int i, j;
;   for (i=0; i<n; ++i) {
;     for (j=0; j<m; j++) {
;       int *arr = ar + i * m * o + j * o;
;       memset(arr, 0, o * sizeof(int));
;     }
;   }
; }
define dso_local void @NestedFor64(ptr %ar, i64 %n, i64 %m, i64 %o) #0 {
; CHECK-LABEL: @NestedFor64(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP3:%.*]] = icmp slt i64 0, [[N:%.*]]
; CHECK-NEXT:    [[CMP41:%.*]] = icmp slt i64 0, [[M:%.*]]
; CHECK-NEXT:    [[MUL13:%.*]] = mul nsw i64 [[O:%.*]], 4
; CHECK-NEXT:    [[CONV14:%.*]] = trunc i64 [[MUL13]] to i32
; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[CMP3]], i1 [[CMP41]], i1 false
; CHECK-NEXT:    br i1 [[OR_COND]], label [[FOR_BODY_US_PREHEADER:%.*]], label [[FOR_END17:%.*]]
; CHECK:       for.body.us.preheader:
; CHECK-NEXT:    [[TMP0:%.*]] = mul i64 [[O]], [[M]]
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[TMP0]] to i32
; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[TMP1]], 2
; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[O]] to i32
; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[M]] to i32
; CHECK-NEXT:    [[TMP5:%.*]] = mul i32 [[TMP3]], [[TMP4]]
; CHECK-NEXT:    [[TMP6:%.*]] = shl i32 [[TMP5]], 2
; CHECK-NEXT:    br label [[FOR_BODY_US:%.*]]
; CHECK:       for.body.us:
; CHECK-NEXT:    [[I_04_US:%.*]] = phi i32 [ [[INC16_US:%.*]], [[FOR_BODY_US]] ], [ 0, [[FOR_BODY_US_PREHEADER]] ]
; CHECK-NEXT:    [[TMP7:%.*]] = mul i32 [[TMP2]], [[I_04_US]]
; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, ptr [[AR:%.*]], i32 [[TMP7]]
; CHECK-NEXT:    [[CONV7_US:%.*]] = sext i32 [[I_04_US]] to i64
; CHECK-NEXT:    [[MUL_US:%.*]] = mul nsw i64 [[CONV7_US]], [[M]]
; CHECK-NEXT:    [[MUL8_US:%.*]] = mul nsw i64 [[MUL_US]], [[O]]
; CHECK-NEXT:    [[IDX_EXT_US:%.*]] = trunc i64 [[MUL8_US]] to i32
; CHECK-NEXT:    [[ADD_PTR_US:%.*]] = getelementptr inbounds i32, ptr [[AR]], i32 [[IDX_EXT_US]]
; CHECK-NEXT:    call void @llvm.memset.p0.i32(ptr align 4 [[UGLYGEP]], i8 0, i32 [[TMP6]], i1 false)
; CHECK-NEXT:    [[INC16_US]] = add nuw nsw i32 [[I_04_US]], 1
; CHECK-NEXT:    [[CONV_US:%.*]] = sext i32 [[INC16_US]] to i64
; CHECK-NEXT:    [[CMP_US:%.*]] = icmp slt i64 [[CONV_US]], [[N]]
; CHECK-NEXT:    br i1 [[CMP_US]], label [[FOR_BODY_US]], label [[FOR_END17]]
; CHECK:       for.end17:
; CHECK-NEXT:    ret void
;
entry:
  %cmp3 = icmp slt i64 0, %n
  br i1 %cmp3, label %for.body.lr.ph, label %for.end17

for.body.lr.ph:                                   ; preds = %entry
  %cmp41 = icmp slt i64 0, %m
  %mul13 = mul nsw i64 %o, 4
  %conv14 = trunc i64 %mul13 to i32
  br i1 %cmp41, label %for.body.us.preheader, label %for.end17

for.body.us.preheader:                            ; preds = %for.body.lr.ph
  br label %for.body.us

for.body.us:                                      ; preds = %for.body.us.preheader, %for.cond2.for.end_crit_edge.us
  %i.04.us = phi i32 [ %inc16.us, %for.cond2.for.end_crit_edge.us ], [ 0, %for.body.us.preheader ]
  %conv7.us = sext i32 %i.04.us to i64
  %mul.us = mul nsw i64 %conv7.us, %m
  %mul8.us = mul nsw i64 %mul.us, %o
  %idx.ext.us = trunc i64 %mul8.us to i32
  %add.ptr.us = getelementptr inbounds i32, ptr %ar, i32 %idx.ext.us
  br label %for.body6.us

for.body6.us:                                     ; preds = %for.body.us, %for.body6.us
  %j.02.us = phi i32 [ 0, %for.body.us ], [ %inc.us, %for.body6.us ]
  %conv9.us = sext i32 %j.02.us to i64
  %mul10.us = mul nsw i64 %conv9.us, %o
  %idx.ext11.us = trunc i64 %mul10.us to i32
  %add.ptr12.us = getelementptr inbounds i32, ptr %add.ptr.us, i32 %idx.ext11.us
  call void @llvm.memset.p0.i32(ptr align 4 %add.ptr12.us, i8 0, i32 %conv14, i1 false)
  %inc.us = add nuw nsw i32 %j.02.us, 1
  %conv3.us = sext i32 %inc.us to i64
  %cmp4.us = icmp slt i64 %conv3.us, %m
  br i1 %cmp4.us, label %for.body6.us, label %for.cond2.for.end_crit_edge.us

for.cond2.for.end_crit_edge.us:                   ; preds = %for.body6.us
  %inc16.us = add nuw nsw i32 %i.04.us, 1
  %conv.us = sext i32 %inc16.us to i64
  %cmp.us = icmp slt i64 %conv.us, %n
  br i1 %cmp.us, label %for.body.us, label %for.end17.loopexit

for.end17.loopexit:                               ; preds = %for.cond2.for.end_crit_edge.us
  br label %for.end17

for.end17:                                        ; preds = %for.end17.loopexit, %for.body.lr.ph, %entry
  ret void
}

; void NegStart(int n, int m, int *ar) {
;   for (int i = -100; i < n; i++) {
;     int *arr = ar + (i + 100) * m;
;     memset(arr, 0, m * sizeof(int));
;   }
; }
define void @NegStart(i32 %n, i32 %m, ptr %ar) {
; CHECK-LABEL: @NegStart(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 -100, [[N:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
; CHECK:       for.body.lr.ph:
; CHECK-NEXT:    [[MUL1:%.*]] = mul i32 [[M:%.*]], 4
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], 100
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[M]], [[TMP0]]
; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[TMP1]], 2
; CHECK-NEXT:    call void @llvm.memset.p0.i32(ptr align 4 [[AR:%.*]], i8 0, i32 [[TMP2]], i1 false)
; CHECK-NEXT:    br label [[FOR_END]]
; CHECK:       for.end:
; CHECK-NEXT:    ret void
;
entry:
  %cmp1 = icmp slt i32 -100, %n
  br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
  %mul1 = mul i32 %m, 4
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph, %for.body
  %i.02 = phi i32 [ -100, %for.body.lr.ph ], [ %inc, %for.body ]
  %add = add nsw i32 %i.02, 100
  %mul = mul nsw i32 %add, %m
  %add.ptr = getelementptr inbounds i32, ptr %ar, i32 %mul
  call void @llvm.memset.p0.i32(ptr align 4 %add.ptr, i8 0, i32 %mul1, i1 false)
  %inc = add nsw i32 %i.02, 1
  %exitcond = icmp ne i32 %inc, %n
  br i1 %exitcond, label %for.body, label %for.end.loopexit

for.end.loopexit:                                 ; preds = %for.body
  br label %for.end

for.end:                                          ; preds = %for.end.loopexit, %entry
  ret void
}

declare void @llvm.memset.p0.i32(ptr nocapture writeonly, i8, i32, i1 immarg)