345 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s3 4; Tests for using inbounds information from GEPs.5 6declare void @noundef(ptr noundef)7 8define i1 @inbounds_poison_is_ub1(ptr %src, i32 %n, i32 %idx) {9; CHECK-LABEL: @inbounds_poison_is_ub1(10; CHECK-NEXT: entry:11; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 512; CHECK-NEXT: call void @noundef(ptr [[UPPER]])13; CHECK-NEXT: [[CMP_IDX:%.*]] = icmp ult i32 [[IDX:%.*]], [[N:%.*]]14; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX]] to i6415; CHECK-NEXT: [[SRC_IDX_4:%.*]] = getelementptr i32, ptr [[SRC]], i64 416; CHECK-NEXT: [[CMP_UPPER_4:%.*]] = icmp ule ptr [[SRC_IDX_4]], [[UPPER]]17; CHECK-NEXT: [[SRC_IDX_5:%.*]] = getelementptr i32, ptr [[SRC]], i64 518; CHECK-NEXT: [[CMP_UPPER_5:%.*]] = icmp ule ptr [[SRC_IDX_5]], [[UPPER]]19; CHECK-NEXT: [[RES_0:%.*]] = xor i1 [[CMP_UPPER_4]], [[CMP_UPPER_5]]20; CHECK-NEXT: [[SRC_IDX_6:%.*]] = getelementptr i32, ptr [[SRC]], i64 621; CHECK-NEXT: [[CMP_UPPER_6:%.*]] = icmp ule ptr [[SRC_IDX_6]], [[UPPER]]22; CHECK-NEXT: [[RES_1:%.*]] = xor i1 [[RES_0]], [[CMP_UPPER_6]]23; CHECK-NEXT: [[SRC_IDX_NEG_1:%.*]] = getelementptr i32, ptr [[SRC]], i64 -124; CHECK-NEXT: [[CMP_UPPER_NEG_1:%.*]] = icmp ule ptr [[SRC_IDX_NEG_1]], [[UPPER]]25; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], [[CMP_UPPER_NEG_1]]26; CHECK-NEXT: ret i1 [[RES_2]]27;28entry:29 %upper = getelementptr inbounds i32, ptr %src, i64 530 call void @noundef(ptr %upper)31 %cmp.idx = icmp ult i32 %idx, %n32 %idx.ext = zext i32 %idx to i6433 %src.idx.4 = getelementptr i32, ptr %src, i64 434 %cmp.upper.4 = icmp ule ptr %src.idx.4, %upper35 %src.idx.5 = getelementptr i32, ptr %src, i64 536 %cmp.upper.5 = icmp ule ptr %src.idx.5, %upper37 %res.0 = xor i1 %cmp.upper.4, %cmp.upper.538 39 %src.idx.6 = getelementptr i32, ptr %src, i64 640 %cmp.upper.6 = icmp ule ptr %src.idx.6, %upper41 %res.1 = xor i1 %res.0, %cmp.upper.642 43 %src.idx.neg.1 = getelementptr i32, ptr %src, i64 -144 %cmp.upper.neg.1 = icmp ule ptr %src.idx.neg.1, %upper45 %res.2 = xor i1 %res.1, %cmp.upper.neg.146 ret i1 %res.247}48 49; %start + %n.ext is guaranteed to not overflow (due to inbounds).50; %start + %idx.ext does not overflow if %idx.ext <= %n.ext.51define i1 @inbounds_poison_is_ub2(ptr %src, i32 %n, i32 %idx) {52; CHECK-LABEL: @inbounds_poison_is_ub2(53; CHECK-NEXT: entry:54; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i6455; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 [[N_EXT]]56; CHECK-NEXT: call void @noundef(ptr [[UPPER]])57; CHECK-NEXT: [[CMP_IDX:%.*]] = icmp ult i32 [[IDX:%.*]], [[N]]58; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX]] to i6459; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[IDX_EXT]]60; CHECK-NEXT: br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]61; CHECK: then:62; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER]]63; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]64; CHECK: else:65; CHECK-NEXT: [[CMP_UPPER_2:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER]]66; CHECK-NEXT: ret i1 [[CMP_UPPER_2]]67;68entry:69 %n.ext = zext i32 %n to i6470 %upper = getelementptr inbounds i32, ptr %src, i64 %n.ext71 call void @noundef(ptr %upper)72 %cmp.idx = icmp ult i32 %idx, %n73 %idx.ext = zext i32 %idx to i6474 %src.idx = getelementptr i32, ptr %src, i64 %idx.ext75 br i1 %cmp.idx, label %then, label %else76 77then:78 %cmp.upper.1 = icmp ule ptr %src.idx, %upper79 ret i1 %cmp.upper.180 81else:82 %cmp.upper.2 = icmp ule ptr %src.idx, %upper83 ret i1 %cmp.upper.284}85 86; Same as inbounds_poison_is_ub2, but with individual GEPs in the %then and87; %else blocks.88define i1 @inbounds_poison_is_ub3(ptr %src, i32 %n, i32 %idx) {89; CHECK-LABEL: @inbounds_poison_is_ub3(90; CHECK-NEXT: entry:91; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i6492; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i6493; CHECK-NEXT: [[CMP_IDX:%.*]] = icmp ult i64 [[IDX_EXT]], [[N_EXT]]94; CHECK-NEXT: br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]95; CHECK: then:96; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 [[N_EXT]]97; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]])98; CHECK-NEXT: [[SRC_IDX_1:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[IDX_EXT]]99; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX_1]], [[UPPER_1]]100; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]101; CHECK: else:102; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[N_EXT]]103; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]])104; CHECK-NEXT: [[SRC_IDX_2:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[IDX_EXT]]105; CHECK-NEXT: [[CMP_UPPER_2:%.*]] = icmp ule ptr [[SRC_IDX_2]], [[UPPER_2]]106; CHECK-NEXT: ret i1 [[CMP_UPPER_2]]107;108entry:109 %n.ext = zext i32 %n to i64110 %idx.ext = zext i32 %idx to i64111 %cmp.idx = icmp ult i64 %idx.ext, %n.ext112 br i1 %cmp.idx, label %then, label %else113 114then:115 %upper.1 = getelementptr inbounds i32, ptr %src, i64 %n.ext116 call void @noundef(ptr %upper.1)117 %src.idx.1 = getelementptr i32, ptr %src, i64 %idx.ext118 %cmp.upper.1 = icmp ule ptr %src.idx.1, %upper.1119 ret i1 %cmp.upper.1120 121else:122 %upper.2 = getelementptr inbounds i32, ptr %src, i64 %n.ext123 call void @noundef(ptr %upper.2)124 %src.idx.2 = getelementptr i32, ptr %src, i64 %idx.ext125 %cmp.upper.2 = icmp ule ptr %src.idx.2, %upper.2126 ret i1 %cmp.upper.2127}128 129; The function does not have UB if %upper is poison because of an overflow. Do130; not simplify anything. In this particular case, the returned result will be131; poison in this case, so it could be simplified, but currently we cannot132; distinguish that case.133define i1 @inbounds_poison_does_not_cause_ub(ptr %src, i32 %n, i32 %idx) {134; CHECK-LABEL: @inbounds_poison_does_not_cause_ub(135; CHECK-NEXT: entry:136; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64137; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64138; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 [[N_EXT]]139; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[IDX_EXT]]140; CHECK-NEXT: [[CMP_IDX:%.*]] = icmp ult i64 [[IDX_EXT]], [[N_EXT]]141; CHECK-NEXT: br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]142; CHECK: then:143; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER]]144; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]145; CHECK: else:146; CHECK-NEXT: [[CMP_UPPER_2:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER]]147; CHECK-NEXT: ret i1 [[CMP_UPPER_2]]148;149entry:150 %n.ext = zext i32 %n to i64151 %idx.ext = zext i32 %idx to i64152 %upper = getelementptr inbounds i32, ptr %src, i64 %n.ext153 %src.idx = getelementptr i32, ptr %src, i64 %idx.ext154 %cmp.idx = icmp ult i64 %idx.ext, %n.ext155 br i1 %cmp.idx, label %then, label %else156 157then:158 %cmp.upper.1 = icmp ule ptr %src.idx, %upper159 ret i1 %cmp.upper.1160 161else:162 %cmp.upper.2 = icmp ule ptr %src.idx, %upper163 ret i1 %cmp.upper.2164}165 166; Same as @inbounds_poison_does_not_cause_ub, but with separate GEPs in the167; %then and %else blocks.168define i1 @inbounds_poison_does_not_cause_ub2(ptr %src, i32 %n, i32 %idx) {169; CHECK-LABEL: @inbounds_poison_does_not_cause_ub2(170; CHECK-NEXT: entry:171; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64172; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64173; CHECK-NEXT: [[CMP_IDX:%.*]] = icmp ult i64 [[IDX_EXT]], [[N_EXT]]174; CHECK-NEXT: br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]175; CHECK: then:176; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 [[N_EXT]]177; CHECK-NEXT: [[SRC_IDX_1:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[IDX_EXT]]178; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX_1]], [[UPPER_1]]179; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]180; CHECK: else:181; CHECK-NEXT: [[SRC_IDX_2:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[IDX_EXT]]182; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[N_EXT]]183; CHECK-NEXT: [[CMP_UPPER_2:%.*]] = icmp ule ptr [[SRC_IDX_2]], [[UPPER_2]]184; CHECK-NEXT: ret i1 [[CMP_UPPER_2]]185;186entry:187 %n.ext = zext i32 %n to i64188 %idx.ext = zext i32 %idx to i64189 %cmp.idx = icmp ult i64 %idx.ext, %n.ext190 br i1 %cmp.idx, label %then, label %else191 192then:193 %upper.1 = getelementptr inbounds i32, ptr %src, i64 %n.ext194 %src.idx.1 = getelementptr i32, ptr %src, i64 %idx.ext195 %cmp.upper.1 = icmp ule ptr %src.idx.1, %upper.1196 ret i1 %cmp.upper.1197 198else:199 %src.idx.2 = getelementptr i32, ptr %src, i64 %idx.ext200 %upper.2 = getelementptr inbounds i32, ptr %src, i64 %n.ext201 %cmp.upper.2 = icmp ule ptr %src.idx.2, %upper.2202 ret i1 %cmp.upper.2203}204 205define i1 @no_zexts_indices_may_be_negative(ptr %src, i32 %n, i32 %idx) {206; CHECK-LABEL: @no_zexts_indices_may_be_negative(207; CHECK-NEXT: entry:208; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i32 [[N:%.*]]209; CHECK-NEXT: call void @noundef(ptr [[UPPER]])210; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i32 [[IDX:%.*]]211; CHECK-NEXT: [[CMP_IDX:%.*]] = icmp ult i32 [[IDX]], [[N]]212; CHECK-NEXT: br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]213; CHECK: then:214; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER]]215; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]216; CHECK: else:217; CHECK-NEXT: [[CMP_UPPER_2:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER]]218; CHECK-NEXT: ret i1 [[CMP_UPPER_2]]219;220entry:221 %upper = getelementptr inbounds i32, ptr %src, i32 %n222 call void @noundef(ptr %upper)223 %src.idx = getelementptr i32, ptr %src, i32 %idx224 %cmp.idx = icmp ult i32 %idx, %n225 br i1 %cmp.idx, label %then, label %else226 227then:228 %cmp.upper.1 = icmp ule ptr %src.idx, %upper229 ret i1 %cmp.upper.1230 231else:232 %cmp.upper.2 = icmp ule ptr %src.idx, %upper233 ret i1 %cmp.upper.2234}235 236; Tests for multiple inbound GEPs, make sure the largest upper bound is used.237define i1 @multiple_upper_bounds(ptr %src, i32 %n, i32 %idx) {238; CHECK-LABEL: @multiple_upper_bounds(239; CHECK-NEXT: entry:240; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64241; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 1242; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]])243; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[N_EXT]]244; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]])245; CHECK-NEXT: [[CMP_IDX:%.*]] = icmp ult i32 [[IDX:%.*]], [[N]]246; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX]] to i64247; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[IDX_EXT]]248; CHECK-NEXT: br i1 [[CMP_IDX]], label [[THEN:%.*]], label [[ELSE:%.*]]249; CHECK: then:250; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER_2]]251; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]252; CHECK: else:253; CHECK-NEXT: [[CMP_UPPER_2:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER_2]]254; CHECK-NEXT: ret i1 [[CMP_UPPER_2]]255;256entry:257 %n.ext = zext i32 %n to i64258 %upper.1 = getelementptr inbounds i32, ptr %src, i64 1259 call void @noundef(ptr %upper.1)260 %upper.2 = getelementptr inbounds i32, ptr %src, i64 %n.ext261 call void @noundef(ptr %upper.2)262 %cmp.idx = icmp ult i32 %idx, %n263 %idx.ext = zext i32 %idx to i64264 %src.idx = getelementptr i32, ptr %src, i64 %idx.ext265 br i1 %cmp.idx, label %then, label %else266 267then:268 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.2269 ret i1 %cmp.upper.1270 271else:272 %cmp.upper.2 = icmp ule ptr %src.idx, %upper.2273 ret i1 %cmp.upper.2274}275 276define i1 @multiple_upper_bounds2(ptr %src, i32 %n, i32 %idx) {277; CHECK-LABEL: @multiple_upper_bounds2(278; CHECK-NEXT: entry:279; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64280; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 1281; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]])282; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 4283; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]])284; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 4285; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER_2]]286; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]287;288entry:289 %n.ext = zext i32 %n to i64290 %upper.1 = getelementptr inbounds i32, ptr %src, i64 1291 call void @noundef(ptr %upper.1)292 %upper.2 = getelementptr inbounds i32, ptr %src, i64 4293 call void @noundef(ptr %upper.2)294 %src.idx = getelementptr i32, ptr %src, i64 4295 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.2296 ret i1 %cmp.upper.1297}298 299define i1 @multiple_upper_bounds3(ptr %src, i32 %n, i32 %idx) {300; CHECK-LABEL: @multiple_upper_bounds3(301; CHECK-NEXT: entry:302; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64303; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 4304; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]])305; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 1306; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]])307; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 4308; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER_1]]309; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]310;311entry:312 %n.ext = zext i32 %n to i64313 %upper.1 = getelementptr inbounds i32, ptr %src, i64 4314 call void @noundef(ptr %upper.1)315 %upper.2 = getelementptr inbounds i32, ptr %src, i64 1316 call void @noundef(ptr %upper.2)317 %src.idx = getelementptr i32, ptr %src, i64 4318 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.1319 ret i1 %cmp.upper.1320}321 322; %src.idx + 5 may overflow.323define i1 @multiple_upper_bounds4(ptr %src, i32 %n, i32 %idx) {324; CHECK-LABEL: @multiple_upper_bounds4(325; CHECK-NEXT: entry:326; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64327; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 1328; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]])329; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 4330; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]])331; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 5332; CHECK-NEXT: [[CMP_UPPER_1:%.*]] = icmp ule ptr [[SRC_IDX]], [[UPPER_2]]333; CHECK-NEXT: ret i1 [[CMP_UPPER_1]]334;335entry:336 %n.ext = zext i32 %n to i64337 %upper.1 = getelementptr inbounds i32, ptr %src, i64 1338 call void @noundef(ptr %upper.1)339 %upper.2 = getelementptr inbounds i32, ptr %src, i64 4340 call void @noundef(ptr %upper.2)341 %src.idx = getelementptr i32, ptr %src, i64 5342 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.2343 ret i1 %cmp.upper.1344}345