330 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 cases with explicit checks that %ptr + x >= %ptr. The information can5; be used to determine that certain GEPs do not overflow.6 7define i1 @overflow_check_1(ptr %dst) {8; CHECK-LABEL: @overflow_check_1(9; CHECK-NEXT: entry:10; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 511; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]12; CHECK-NEXT: br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]13; CHECK: then:14; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 415; CHECK-NEXT: [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]16; CHECK-NEXT: ret i1 [[TRUE_DST_4_UGE]]17; CHECK: else:18; CHECK-NEXT: ret i1 false19;20entry:21 %dst.5 = getelementptr i32, ptr %dst, i64 522 %dst.5.uge = icmp uge ptr %dst.5, %dst23 br i1 %dst.5.uge, label %then, label %else24 25then:26 %dst.4 = getelementptr i32, ptr %dst, i64 427 %true.dst.4.uge = icmp uge ptr %dst.4, %dst28 ret i1 %true.dst.4.uge29 30else:31 ret i1 032}33 34define i1 @overflow_check_2_and(ptr %dst) {35; CHECK-LABEL: @overflow_check_2_and(36; CHECK-NEXT: entry:37; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 538; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]39; CHECK-NEXT: br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]40; CHECK: then:41; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 442; CHECK-NEXT: [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]43; CHECK-NEXT: ret i1 [[TRUE_DST_4_UGE]]44; CHECK: else:45; CHECK-NEXT: ret i1 true46;47entry:48 %dst.5 = getelementptr i32, ptr %dst, i64 549 %dst.5.uge = icmp uge ptr %dst.5, %dst50 %and = and i1 %dst.5.uge, %dst.5.uge51 br i1 %and, label %then, label %else52 53then:54 %dst.4 = getelementptr i32, ptr %dst, i64 455 %true.dst.4.uge = icmp uge ptr %dst.4, %dst56 ret i1 %true.dst.4.uge57 58else:59 ret i1 true60}61 62define i1 @overflow_check_3_and(ptr %dst) {63; CHECK-LABEL: @overflow_check_3_and(64; CHECK-NEXT: entry:65; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 566; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]67; CHECK-NEXT: br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]68; CHECK: then:69; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 470; CHECK-NEXT: [[DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]71; CHECK-NEXT: ret i1 [[DST_4_UGE]]72; CHECK: else:73; CHECK-NEXT: [[ELSE_DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 474; CHECK-NEXT: [[ELSE_DST_4_UGE:%.*]] = icmp uge ptr [[ELSE_DST_4]], [[DST]]75; CHECK-NEXT: ret i1 [[ELSE_DST_4_UGE]]76;77entry:78 %dst.5 = getelementptr i32, ptr %dst, i64 579 %dst.5.uge = icmp uge ptr %dst.5, %dst80 %and = and i1 %dst.5.uge, %dst.5.uge81 br i1 %and, label %then, label %else82 83then:84 %dst.4 = getelementptr i32, ptr %dst, i64 485 %dst.4.uge = icmp uge ptr %dst.4, %dst86 ret i1 %dst.4.uge87 88else:89 %else.dst.4 = getelementptr i32, ptr %dst, i64 490 %else.dst.4.uge = icmp uge ptr %else.dst.4, %dst91 ret i1 %else.dst.4.uge92}93 94define i1 @overflow_check_4_and(ptr %dst) {95; CHECK-LABEL: @overflow_check_4_and(96; CHECK-NEXT: entry:97; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 598; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]99; CHECK-NEXT: br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]100; CHECK: then:101; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4102; CHECK-NEXT: [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]103; CHECK-NEXT: [[DST_5_2:%.*]] = getelementptr i32, ptr [[DST]], i64 5104; CHECK-NEXT: [[TRUE_DST_5_UGE:%.*]] = icmp uge ptr [[DST_5_2]], [[DST]]105; CHECK-NEXT: [[RES_0:%.*]] = xor i1 [[TRUE_DST_4_UGE]], [[TRUE_DST_5_UGE]]106; CHECK-NEXT: [[DST_6:%.*]] = getelementptr i32, ptr [[DST]], i64 6107; CHECK-NEXT: [[C_DST_6_UGE:%.*]] = icmp uge ptr [[DST_6]], [[DST]]108; CHECK-NEXT: [[RES_1:%.*]] = xor i1 [[RES_0]], [[C_DST_6_UGE]]109; CHECK-NEXT: ret i1 [[RES_1]]110; CHECK: else:111; CHECK-NEXT: [[ELSE_DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4112; CHECK-NEXT: [[ELSE_DST_4_UGE:%.*]] = icmp uge ptr [[ELSE_DST_4]], [[DST]]113; CHECK-NEXT: [[ELSE_DST_6:%.*]] = getelementptr i32, ptr [[DST]], i64 6114; CHECK-NEXT: [[ELSE_DST_6_UGE:%.*]] = icmp uge ptr [[ELSE_DST_6]], [[DST]]115; CHECK-NEXT: [[ELSE_RES_0:%.*]] = xor i1 [[ELSE_DST_4_UGE]], [[ELSE_DST_6_UGE]]116; CHECK-NEXT: ret i1 [[ELSE_RES_0]]117;118entry:119 %dst.5 = getelementptr i32, ptr %dst, i64 5120 %dst.5.uge = icmp uge ptr %dst.5, %dst121 %and = and i1 %dst.5.uge, %dst.5.uge122 br i1 %and, label %then, label %else123 124then:125 %dst.4 = getelementptr i32, ptr %dst, i64 4126 %true.dst.4.uge = icmp uge ptr %dst.4, %dst127 %dst.5.2 = getelementptr i32, ptr %dst, i64 5128 %true.dst.5.uge = icmp uge ptr %dst.5.2, %dst129 %res.0 = xor i1 %true.dst.4.uge, %true.dst.5.uge130 131 %dst.6 = getelementptr i32, ptr %dst, i64 6132 %c.dst.6.uge = icmp uge ptr %dst.6, %dst133 %res.1 = xor i1 %res.0, %c.dst.6.uge134 135 ret i1 %res.1136 137else:138 %else.dst.4 = getelementptr i32, ptr %dst, i64 4139 %else.dst.4.uge = icmp uge ptr %else.dst.4, %dst140 %else.dst.6 = getelementptr i32, ptr %dst, i64 6141 %else.dst.6.uge = icmp uge ptr %else.dst.6, %dst142 %else.res.0 = xor i1 %else.dst.4.uge, %else.dst.6.uge143 144 ret i1 %else.res.0145}146 147define i1 @overflow_check_3_or(ptr %dst) {148; CHECK-LABEL: @overflow_check_3_or(149; CHECK-NEXT: entry:150; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5151; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]152; CHECK-NEXT: br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]153; CHECK: then:154; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4155; CHECK-NEXT: [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]156; CHECK-NEXT: ret i1 [[TRUE_DST_4_UGE]]157; CHECK: else:158; CHECK-NEXT: ret i1 false159;160entry:161 %dst.5 = getelementptr i32, ptr %dst, i64 5162 %dst.5.uge = icmp uge ptr %dst.5, %dst163 %or = or i1 %dst.5.uge, %dst.5.uge164 br i1 %or, label %then, label %else165 166then:167 %dst.4 = getelementptr i32, ptr %dst, i64 4168 %true.dst.4.uge = icmp uge ptr %dst.4, %dst169 ret i1 %true.dst.4.uge170 171else:172 ret i1 0173}174 175define i1 @upper_and_lower_checks_1(ptr %dst, i32 %n) {176; CHECK-LABEL: @upper_and_lower_checks_1(177; CHECK-NEXT: entry:178; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64179; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST:%.*]], i64 [[N_EXT]]180; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST]], i64 5181; CHECK-NEXT: [[DST_5_ULT:%.*]] = icmp ult ptr [[DST_5]], [[UPPER]]182; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]183; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]184; CHECK-NEXT: br i1 [[AND_1]], label [[THEN:%.*]], label [[ELSE:%.*]]185; CHECK: then:186; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4187; CHECK-NEXT: [[TRUE_DST_4_ULT:%.*]] = icmp ult ptr [[DST_4]], [[UPPER]]188; CHECK-NEXT: [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]189; CHECK-NEXT: [[AND:%.*]] = and i1 [[TRUE_DST_4_ULT]], [[TRUE_DST_4_UGE]]190; CHECK-NEXT: ret i1 [[AND]]191; CHECK: else:192; CHECK-NEXT: ret i1 false193;194entry:195 %n.ext = zext i32 %n to i64196 %upper = getelementptr inbounds i32, ptr %dst, i64 %n.ext197 %dst.5 = getelementptr i32, ptr %dst, i64 5198 %dst.5.ult = icmp ult ptr %dst.5, %upper199 %dst.5.uge = icmp uge ptr %dst.5, %dst200 %and.1 = and i1 %dst.5.ult, %dst.5.uge201 br i1 %and.1, label %then, label %else202 203then:204 %dst.4 = getelementptr i32, ptr %dst, i64 4205 %true.dst.4.ult = icmp ult ptr %dst.4, %upper206 %true.dst.4.uge = icmp uge ptr %dst.4, %dst207 %and = and i1 %true.dst.4.ult, %true.dst.4.uge208 ret i1 %and209 210else:211 ret i1 0212}213 214define i1 @upper_and_lower_checks_2_dst6(ptr %dst, i32 %n) {215; CHECK-LABEL: @upper_and_lower_checks_2_dst6(216; CHECK-NEXT: entry:217; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64218; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST:%.*]], i64 [[N_EXT]]219; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST]], i64 5220; CHECK-NEXT: [[DST_5_ULT:%.*]] = icmp ult ptr [[DST_5]], [[UPPER]]221; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]222; CHECK-NEXT: [[AND:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]223; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]224; CHECK: then:225; CHECK-NEXT: [[DST_6:%.*]] = getelementptr i32, ptr [[DST]], i64 6226; CHECK-NEXT: [[C_DST_6_ULT:%.*]] = icmp ult ptr [[DST_6]], [[UPPER]]227; CHECK-NEXT: [[TRUE_DST_6_UGE:%.*]] = icmp uge ptr [[DST_6]], [[DST]]228; CHECK-NEXT: [[RES:%.*]] = and i1 [[C_DST_6_ULT]], [[TRUE_DST_6_UGE]]229; CHECK-NEXT: ret i1 [[RES]]230; CHECK: else:231; CHECK-NEXT: ret i1 false232;233entry:234 %n.ext = zext i32 %n to i64235 %upper = getelementptr inbounds i32, ptr %dst, i64 %n.ext236 %dst.5 = getelementptr i32, ptr %dst, i64 5237 %dst.5.ult = icmp ult ptr %dst.5, %upper238 %dst.5.uge = icmp uge ptr %dst.5, %dst239 %and = and i1 %dst.5.ult, %dst.5.uge240 br i1 %and, label %then, label %else241 242then:243 %dst.6 = getelementptr i32, ptr %dst, i64 6244 %c.dst.6.ult = icmp ult ptr %dst.6, %upper245 %true.dst.6.uge = icmp uge ptr %dst.6, %dst246 %res = and i1 %c.dst.6.ult, %true.dst.6.uge247 ret i1 %res248 249else:250 ret i1 0251}252 253define i1 @upper_and_lower_checks_2_dst7(ptr %dst, i32 %n) {254; CHECK-LABEL: @upper_and_lower_checks_2_dst7(255; CHECK-NEXT: entry:256; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64257; CHECK-NEXT: [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[DST:%.*]], i64 [[N_EXT]]258; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST]], i64 5259; CHECK-NEXT: [[DST_5_ULT:%.*]] = icmp ult ptr [[DST_5]], [[UPPER]]260; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]261; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]262; CHECK-NEXT: br i1 [[OR_COND]], label [[THEN:%.*]], label [[ELSE:%.*]]263; CHECK: then:264; CHECK-NEXT: [[DST_7:%.*]] = getelementptr i32, ptr [[DST]], i64 7265; CHECK-NEXT: [[C_DST_7_ULT:%.*]] = icmp ult ptr [[DST_7]], [[UPPER]]266; CHECK-NEXT: [[C_DST_7_UGE:%.*]] = icmp uge ptr [[DST_7]], [[DST]]267; CHECK-NEXT: [[RES:%.*]] = and i1 [[C_DST_7_ULT]], [[C_DST_7_UGE]]268; CHECK-NEXT: ret i1 [[RES]]269; CHECK: else:270; CHECK-NEXT: ret i1 false271;272entry:273 %n.ext = zext i32 %n to i64274 %upper = getelementptr inbounds i32, ptr %dst, i64 %n.ext275 %dst.5 = getelementptr i32, ptr %dst, i64 5276 %dst.5.ult = icmp ult ptr %dst.5, %upper277 %dst.5.uge = icmp uge ptr %dst.5, %dst278 %or.cond = and i1 %dst.5.ult, %dst.5.uge279 br i1 %or.cond, label %then, label %else280 281then:282 %dst.7 = getelementptr i32, ptr %dst, i64 7283 %c.dst.7.ult = icmp ult ptr %dst.7, %upper284 %c.dst.7.uge = icmp uge ptr %dst.7, %dst285 %res = and i1 %c.dst.7.ult, %c.dst.7.uge286 ret i1 %res287 288else:289 ret i1 0290}291 292define i1 @upper_and_lower_checks_lt(ptr %dst, i32 %n) {293; CHECK-LABEL: @upper_and_lower_checks_lt(294; CHECK-NEXT: entry:295; CHECK-NEXT: [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64296; CHECK-NEXT: [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 [[N_EXT]]297; CHECK-NEXT: [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]298; CHECK-NEXT: [[N_EXT_UGE:%.*]] = icmp uge i64 [[N_EXT]], 3299; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[DST_5_UGE]], [[N_EXT_UGE]]300; CHECK-NEXT: br i1 [[OR_COND]], label [[THEN:%.*]], label [[ELSE:%.*]]301; CHECK: then:302; CHECK-NEXT: [[DST_3:%.*]] = getelementptr i32, ptr [[DST]], i64 3303; CHECK-NEXT: [[TRUE_DST_3_UGE:%.*]] = icmp uge ptr [[DST_3]], [[DST]]304; CHECK-NEXT: [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4305; CHECK-NEXT: [[C_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]306; CHECK-NEXT: [[RES_0:%.*]] = xor i1 [[TRUE_DST_3_UGE]], [[C_DST_4_UGE]]307; CHECK-NEXT: ret i1 [[RES_0]]308; CHECK: else:309; CHECK-NEXT: ret i1 false310;311entry:312 %n.ext = zext i32 %n to i64313 %dst.5 = getelementptr i32, ptr %dst, i64 %n.ext314 %dst.5.uge = icmp uge ptr %dst.5, %dst315 %n.ext.uge = icmp uge i64 %n.ext, 3316 %or.cond = and i1 %dst.5.uge, %n.ext.uge317 br i1 %or.cond, label %then, label %else318 319then:320 %dst.3 = getelementptr i32, ptr %dst, i64 3321 %true.dst.3.uge = icmp uge ptr %dst.3, %dst322 %dst.4 = getelementptr i32, ptr %dst, i64 4323 %c.dst.4.uge = icmp uge ptr %dst.4, %dst324 %res.0 = xor i1 %true.dst.3.uge, %c.dst.4.uge325 ret i1 %res.0326 327else:328 ret i1 0329}330