217 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -S -passes=loop-predication -loop-predication-enable-iv-truncation=true < %s 2>&1 | FileCheck %s3; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s4declare void @llvm.experimental.guard(i1, ...)5 6declare i32 @length(ptr)7 8declare i16 @short_length(ptr)9; Consider range check of type i16 and i32, while IV is of type i6410; We can loop predicate this because the IV range is within i16 and within i32.11define i64 @iv_wider_type_rc_two_narrow_types(i32 %offA, i16 %offB, ptr %arrA, ptr %arrB) {12; CHECK-LABEL: @iv_wider_type_rc_two_narrow_types(13; CHECK-NEXT: entry:14; CHECK-NEXT: [[LENGTHA:%.*]] = call i32 @length(ptr [[ARRA:%.*]])15; CHECK-NEXT: [[LENGTHB:%.*]] = call i16 @short_length(ptr [[ARRB:%.*]])16; CHECK-NEXT: [[TMP0:%.*]] = sub i16 [[LENGTHB]], [[OFFB:%.*]]17; CHECK-NEXT: [[TMP1:%.*]] = icmp ule i16 16, [[TMP0]]18; CHECK-NEXT: [[TMP2:%.*]] = icmp ult i16 [[OFFB]], [[LENGTHB]]19; CHECK-NEXT: [[TMP3:%.*]] = and i1 [[TMP2]], [[TMP1]]20; CHECK-NEXT: [[TMP4:%.*]] = freeze i1 [[TMP3]]21; CHECK-NEXT: [[TMP5:%.*]] = sub i32 [[LENGTHA]], [[OFFA:%.*]]22; CHECK-NEXT: [[TMP6:%.*]] = icmp ule i32 16, [[TMP5]]23; CHECK-NEXT: [[TMP7:%.*]] = icmp ult i32 [[OFFA]], [[LENGTHA]]24; CHECK-NEXT: [[TMP8:%.*]] = and i1 [[TMP7]], [[TMP6]]25; CHECK-NEXT: [[TMP9:%.*]] = freeze i1 [[TMP8]]26; CHECK-NEXT: [[TMP10:%.*]] = and i1 [[TMP4]], [[TMP9]]27; CHECK-NEXT: br label [[LOOP:%.*]]28; CHECK: loop:29; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]30; CHECK-NEXT: [[IV_TRUNC_32:%.*]] = trunc i64 [[IV]] to i3231; CHECK-NEXT: [[IV_TRUNC_16:%.*]] = trunc i64 [[IV]] to i1632; CHECK-NEXT: [[INDEXA:%.*]] = add i32 [[IV_TRUNC_32]], [[OFFA]]33; CHECK-NEXT: [[INDEXB:%.*]] = add i16 [[IV_TRUNC_16]], [[OFFB]]34; CHECK-NEXT: [[RCA:%.*]] = icmp ult i32 [[INDEXA]], [[LENGTHA]]35; CHECK-NEXT: [[RCB:%.*]] = icmp ult i16 [[INDEXB]], [[LENGTHB]]36; CHECK-NEXT: [[WIDE_CHK:%.*]] = and i1 [[RCA]], [[RCB]]37; CHECK-NEXT: call void (i1, ...) @llvm.experimental.guard(i1 [[TMP10]], i32 9) [ "deopt"() ]38; CHECK-NEXT: call void @llvm.assume(i1 [[WIDE_CHK]])39; CHECK-NEXT: [[INDEXA_EXT:%.*]] = zext i32 [[INDEXA]] to i6440; CHECK-NEXT: [[ADDRA:%.*]] = getelementptr inbounds i8, ptr [[ARRA]], i64 [[INDEXA_EXT]]41; CHECK-NEXT: [[ELTA:%.*]] = load i8, ptr [[ADDRA]], align 142; CHECK-NEXT: [[INDEXB_EXT:%.*]] = zext i16 [[INDEXB]] to i6443; CHECK-NEXT: [[ADDRB:%.*]] = getelementptr inbounds i8, ptr [[ARRB]], i64 [[INDEXB_EXT]]44; CHECK-NEXT: store i8 [[ELTA]], ptr [[ADDRB]], align 145; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 146; CHECK-NEXT: [[LATCH_CHECK:%.*]] = icmp ult i64 [[IV_NEXT]], 1647; CHECK-NEXT: br i1 [[LATCH_CHECK]], label [[LOOP]], label [[EXIT:%.*]]48; CHECK: exit:49; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i64 [ [[IV]], [[LOOP]] ]50; CHECK-NEXT: ret i64 [[IV_LCSSA]]51;52entry:53 %lengthA = call i32 @length(ptr %arrA)54 %lengthB = call i16 @short_length(ptr %arrB)55 br label %loop56 57loop:58 %iv = phi i64 [0, %entry ], [ %iv.next, %loop ]59 %iv.trunc.32 = trunc i64 %iv to i3260 %iv.trunc.16 = trunc i64 %iv to i1661 %indexA = add i32 %iv.trunc.32, %offA62 %indexB = add i16 %iv.trunc.16, %offB63 %rcA = icmp ult i32 %indexA, %lengthA64 %rcB = icmp ult i16 %indexB, %lengthB65 %wide.chk = and i1 %rcA, %rcB66 call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk, i32 9) [ "deopt"() ]67 %indexA.ext = zext i32 %indexA to i6468 %addrA = getelementptr inbounds i8, ptr %arrA, i64 %indexA.ext69 %eltA = load i8, ptr %addrA70 %indexB.ext = zext i16 %indexB to i6471 %addrB = getelementptr inbounds i8, ptr %arrB, i64 %indexB.ext72 store i8 %eltA, ptr %addrB73 %iv.next = add nuw nsw i64 %iv, 174 %latch.check = icmp ult i64 %iv.next, 1675 br i1 %latch.check, label %loop, label %exit76 77exit:78 ret i64 %iv79}80 81 82; Consider an IV of type long and an array access into int array.83; IV is of type i64 while the range check operands are of type i32 and i64.84define i64 @iv_rc_different_types(i32 %offA, i32 %offB, ptr %arrA, ptr %arrB, i64 %max)85; CHECK-LABEL: @iv_rc_different_types(86; CHECK-NEXT: entry:87; CHECK-NEXT: [[LENGTHA:%.*]] = call i32 @length(ptr [[ARRA:%.*]])88; CHECK-NEXT: [[LENGTHB:%.*]] = call i32 @length(ptr [[ARRB:%.*]])89; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LENGTHB]], -190; CHECK-NEXT: [[TMP1:%.*]] = sub i32 [[TMP0]], [[OFFB:%.*]]91; CHECK-NEXT: [[TMP2:%.*]] = icmp ule i32 15, [[TMP1]]92; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 [[OFFB]], [[LENGTHB]]93; CHECK-NEXT: [[TMP4:%.*]] = and i1 [[TMP3]], [[TMP2]]94; CHECK-NEXT: [[TMP5:%.*]] = freeze i1 [[TMP4]]95; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[MAX:%.*]], -196; CHECK-NEXT: [[TMP7:%.*]] = icmp ule i64 15, [[TMP6]]97; CHECK-NEXT: [[TMP8:%.*]] = icmp ult i64 0, [[MAX]]98; CHECK-NEXT: [[TMP9:%.*]] = and i1 [[TMP8]], [[TMP7]]99; CHECK-NEXT: [[TMP10:%.*]] = freeze i1 [[TMP9]]100; CHECK-NEXT: [[TMP11:%.*]] = add i32 [[LENGTHA]], -1101; CHECK-NEXT: [[TMP12:%.*]] = sub i32 [[TMP11]], [[OFFA:%.*]]102; CHECK-NEXT: [[TMP13:%.*]] = icmp ule i32 15, [[TMP12]]103; CHECK-NEXT: [[TMP14:%.*]] = icmp ult i32 [[OFFA]], [[LENGTHA]]104; CHECK-NEXT: [[TMP15:%.*]] = and i1 [[TMP14]], [[TMP13]]105; CHECK-NEXT: [[TMP16:%.*]] = freeze i1 [[TMP15]]106; CHECK-NEXT: [[TMP17:%.*]] = and i1 [[TMP5]], [[TMP10]]107; CHECK-NEXT: [[TMP18:%.*]] = and i1 [[TMP17]], [[TMP16]]108; CHECK-NEXT: br label [[LOOP:%.*]]109; CHECK: loop:110; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]111; CHECK-NEXT: [[IV_TRUNC:%.*]] = trunc i64 [[IV]] to i32112; CHECK-NEXT: [[INDEXA:%.*]] = add i32 [[IV_TRUNC]], [[OFFA]]113; CHECK-NEXT: [[INDEXB:%.*]] = add i32 [[IV_TRUNC]], [[OFFB]]114; CHECK-NEXT: [[RCA:%.*]] = icmp ult i32 [[INDEXA]], [[LENGTHA]]115; CHECK-NEXT: [[RCIV:%.*]] = icmp ult i64 [[IV]], [[MAX]]116; CHECK-NEXT: [[WIDE_CHK:%.*]] = and i1 [[RCA]], [[RCIV]]117; CHECK-NEXT: [[RCB:%.*]] = icmp ult i32 [[INDEXB]], [[LENGTHB]]118; CHECK-NEXT: [[WIDE_CHK_FINAL:%.*]] = and i1 [[WIDE_CHK]], [[RCB]]119; CHECK-NEXT: call void (i1, ...) @llvm.experimental.guard(i1 [[TMP18]], i32 9) [ "deopt"() ]120; CHECK-NEXT: call void @llvm.assume(i1 [[WIDE_CHK_FINAL]])121; CHECK-NEXT: [[INDEXA_EXT:%.*]] = zext i32 [[INDEXA]] to i64122; CHECK-NEXT: [[ADDRA:%.*]] = getelementptr inbounds i8, ptr [[ARRA]], i64 [[INDEXA_EXT]]123; CHECK-NEXT: [[ELTA:%.*]] = load i8, ptr [[ADDRA]], align 1124; CHECK-NEXT: [[INDEXB_EXT:%.*]] = zext i32 [[INDEXB]] to i64125; CHECK-NEXT: [[ADDRB:%.*]] = getelementptr inbounds i8, ptr [[ARRB]], i64 [[INDEXB_EXT]]126; CHECK-NEXT: [[ELTB:%.*]] = load i8, ptr [[ADDRB]], align 1127; CHECK-NEXT: [[RESULT:%.*]] = xor i8 [[ELTA]], [[ELTB]]128; CHECK-NEXT: store i8 [[RESULT]], ptr [[ADDRA]], align 1129; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1130; CHECK-NEXT: [[LATCH_CHECK:%.*]] = icmp ult i64 [[IV]], 15131; CHECK-NEXT: br i1 [[LATCH_CHECK]], label [[LOOP]], label [[EXIT:%.*]]132; CHECK: exit:133; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i64 [ [[IV]], [[LOOP]] ]134; CHECK-NEXT: ret i64 [[IV_LCSSA]]135;136{137entry:138 %lengthA = call i32 @length(ptr %arrA)139 %lengthB = call i32 @length(ptr %arrB)140 br label %loop141 142loop:143 %iv = phi i64 [0, %entry ], [ %iv.next, %loop ]144 %iv.trunc = trunc i64 %iv to i32145 %indexA = add i32 %iv.trunc, %offA146 %indexB = add i32 %iv.trunc, %offB147 %rcA = icmp ult i32 %indexA, %lengthA148 %rcIV = icmp ult i64 %iv, %max149 %wide.chk = and i1 %rcA, %rcIV150 %rcB = icmp ult i32 %indexB, %lengthB151 %wide.chk.final = and i1 %wide.chk, %rcB152 call void (i1, ...) @llvm.experimental.guard(i1 %wide.chk.final, i32 9) [ "deopt"() ]153 %indexA.ext = zext i32 %indexA to i64154 %addrA = getelementptr inbounds i8, ptr %arrA, i64 %indexA.ext155 %eltA = load i8, ptr %addrA156 %indexB.ext = zext i32 %indexB to i64157 %addrB = getelementptr inbounds i8, ptr %arrB, i64 %indexB.ext158 %eltB = load i8, ptr %addrB159 %result = xor i8 %eltA, %eltB160 store i8 %result, ptr %addrA161 %iv.next = add nuw nsw i64 %iv, 1162 %latch.check = icmp ult i64 %iv, 15163 br i1 %latch.check, label %loop, label %exit164 165exit:166 ret i64 %iv167}168 169; cannot narrow the IV to the range type, because we lose information.170; for (i64 i= 5; i>= 2; i++)171; this loop wraps around after reaching 2^64.172define i64 @iv_rc_different_type(i32 %offA, ptr %arrA) {173; CHECK-LABEL: @iv_rc_different_type(174; CHECK-NEXT: entry:175; CHECK-NEXT: [[LENGTHA:%.*]] = call i32 @length(ptr [[ARRA:%.*]])176; CHECK-NEXT: br label [[LOOP:%.*]]177; CHECK: loop:178; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 5, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]179; CHECK-NEXT: [[IV_TRUNC_32:%.*]] = trunc i64 [[IV]] to i32180; CHECK-NEXT: [[INDEXA:%.*]] = add i32 [[IV_TRUNC_32]], [[OFFA:%.*]]181; CHECK-NEXT: [[RCA:%.*]] = icmp ult i32 [[INDEXA]], [[LENGTHA]]182; CHECK-NEXT: call void (i1, ...) @llvm.experimental.guard(i1 [[RCA]], i32 9) [ "deopt"() ]183; CHECK-NEXT: [[INDEXA_EXT:%.*]] = zext i32 [[INDEXA]] to i64184; CHECK-NEXT: [[ADDRA:%.*]] = getelementptr inbounds i8, ptr [[ARRA]], i64 [[INDEXA_EXT]]185; CHECK-NEXT: [[ELTA:%.*]] = load i8, ptr [[ADDRA]], align 1186; CHECK-NEXT: [[RES:%.*]] = add i8 [[ELTA]], 2187; CHECK-NEXT: store i8 [[ELTA]], ptr [[ADDRA]], align 1188; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1189; CHECK-NEXT: [[LATCH_CHECK:%.*]] = icmp sge i64 [[IV_NEXT]], 2190; CHECK-NEXT: br i1 [[LATCH_CHECK]], label [[LOOP]], label [[EXIT:%.*]]191; CHECK: exit:192; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i64 [ [[IV]], [[LOOP]] ]193; CHECK-NEXT: ret i64 [[IV_LCSSA]]194;195entry:196 %lengthA = call i32 @length(ptr %arrA)197 br label %loop198 199loop:200 %iv = phi i64 [ 5, %entry ], [ %iv.next, %loop ]201 %iv.trunc.32 = trunc i64 %iv to i32202 %indexA = add i32 %iv.trunc.32, %offA203 %rcA = icmp ult i32 %indexA, %lengthA204 call void (i1, ...) @llvm.experimental.guard(i1 %rcA, i32 9) [ "deopt"() ]205 %indexA.ext = zext i32 %indexA to i64206 %addrA = getelementptr inbounds i8, ptr %arrA, i64 %indexA.ext207 %eltA = load i8, ptr %addrA208 %res = add i8 %eltA, 2209 store i8 %eltA, ptr %addrA210 %iv.next = add i64 %iv, 1211 %latch.check = icmp sge i64 %iv.next, 2212 br i1 %latch.check, label %loop, label %exit213 214exit:215 ret i64 %iv216}217