1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s 3 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 5 12; 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 i64 15; CHECK-NEXT: [[SRC_IDX_4:%.*]] = getelementptr i32, ptr [[SRC]], i64 4 16; CHECK-NEXT: [[CMP_UPPER_4:%.*]] = icmp ule ptr [[SRC_IDX_4]], [[UPPER]] 17; CHECK-NEXT: [[SRC_IDX_5:%.*]] = getelementptr i32, ptr [[SRC]], i64 5 18; 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 6 21; 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 -1 24; 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 5 30 call void @noundef(ptr %upper) 31 %cmp.idx = icmp ult i32 %idx, %n 32 %idx.ext = zext i32 %idx to i64 33 %src.idx.4 = getelementptr i32, ptr %src, i64 4 34 %cmp.upper.4 = icmp ule ptr %src.idx.4, %upper 35 %src.idx.5 = getelementptr i32, ptr %src, i64 5 36 %cmp.upper.5 = icmp ule ptr %src.idx.5, %upper 37 %res.0 = xor i1 %cmp.upper.4, %cmp.upper.5 38 39 %src.idx.6 = getelementptr i32, ptr %src, i64 6 40 %cmp.upper.6 = icmp ule ptr %src.idx.6, %upper 41 %res.1 = xor i1 %res.0, %cmp.upper.6 42 43 %src.idx.neg.1 = getelementptr i32, ptr %src, i64 -1 44 %cmp.upper.neg.1 = icmp ule ptr %src.idx.neg.1, %upper 45 %res.2 = xor i1 %res.1, %cmp.upper.neg.1 46 ret i1 %res.2 47} 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 i64 55; 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 i64 59; 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 i64 70 %upper = getelementptr inbounds i32, ptr %src, i64 %n.ext 71 call void @noundef(ptr %upper) 72 %cmp.idx = icmp ult i32 %idx, %n 73 %idx.ext = zext i32 %idx to i64 74 %src.idx = getelementptr i32, ptr %src, i64 %idx.ext 75 br i1 %cmp.idx, label %then, label %else 76 77then: 78 %cmp.upper.1 = icmp ule ptr %src.idx, %upper 79 ret i1 %cmp.upper.1 80 81else: 82 %cmp.upper.2 = icmp ule ptr %src.idx, %upper 83 ret i1 %cmp.upper.2 84} 85 86; Same as inbounds_poison_is_ub2, but with individual GEPs in the %then and 87; %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 i64 92; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64 93; 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 i64 110 %idx.ext = zext i32 %idx to i64 111 %cmp.idx = icmp ult i64 %idx.ext, %n.ext 112 br i1 %cmp.idx, label %then, label %else 113 114then: 115 %upper.1 = getelementptr inbounds i32, ptr %src, i64 %n.ext 116 call void @noundef(ptr %upper.1) 117 %src.idx.1 = getelementptr i32, ptr %src, i64 %idx.ext 118 %cmp.upper.1 = icmp ule ptr %src.idx.1, %upper.1 119 ret i1 %cmp.upper.1 120 121else: 122 %upper.2 = getelementptr inbounds i32, ptr %src, i64 %n.ext 123 call void @noundef(ptr %upper.2) 124 %src.idx.2 = getelementptr i32, ptr %src, i64 %idx.ext 125 %cmp.upper.2 = icmp ule ptr %src.idx.2, %upper.2 126 ret i1 %cmp.upper.2 127} 128 129; The function does not have UB if %upper is poison because of an overflow. Do 130; not simplify anything. In this particular case, the returned result will be 131; poison in this case, so it could be simplified, but currently we cannot 132; 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 i64 137; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64 138; 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 i64 151 %idx.ext = zext i32 %idx to i64 152 %upper = getelementptr inbounds i32, ptr %src, i64 %n.ext 153 %src.idx = getelementptr i32, ptr %src, i64 %idx.ext 154 %cmp.idx = icmp ult i64 %idx.ext, %n.ext 155 br i1 %cmp.idx, label %then, label %else 156 157then: 158 %cmp.upper.1 = icmp ule ptr %src.idx, %upper 159 ret i1 %cmp.upper.1 160 161else: 162 %cmp.upper.2 = icmp ule ptr %src.idx, %upper 163 ret i1 %cmp.upper.2 164} 165 166; Same as @inbounds_poison_does_not_cause_ub, but with separate GEPs in the 167; %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 i64 172; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[IDX:%.*]] to i64 173; 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 i64 188 %idx.ext = zext i32 %idx to i64 189 %cmp.idx = icmp ult i64 %idx.ext, %n.ext 190 br i1 %cmp.idx, label %then, label %else 191 192then: 193 %upper.1 = getelementptr inbounds i32, ptr %src, i64 %n.ext 194 %src.idx.1 = getelementptr i32, ptr %src, i64 %idx.ext 195 %cmp.upper.1 = icmp ule ptr %src.idx.1, %upper.1 196 ret i1 %cmp.upper.1 197 198else: 199 %src.idx.2 = getelementptr i32, ptr %src, i64 %idx.ext 200 %upper.2 = getelementptr inbounds i32, ptr %src, i64 %n.ext 201 %cmp.upper.2 = icmp ule ptr %src.idx.2, %upper.2 202 ret i1 %cmp.upper.2 203} 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 %n 222 call void @noundef(ptr %upper) 223 %src.idx = getelementptr i32, ptr %src, i32 %idx 224 %cmp.idx = icmp ult i32 %idx, %n 225 br i1 %cmp.idx, label %then, label %else 226 227then: 228 %cmp.upper.1 = icmp ule ptr %src.idx, %upper 229 ret i1 %cmp.upper.1 230 231else: 232 %cmp.upper.2 = icmp ule ptr %src.idx, %upper 233 ret i1 %cmp.upper.2 234} 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 i64 241; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 1 242; 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 i64 247; 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 i64 258 %upper.1 = getelementptr inbounds i32, ptr %src, i64 1 259 call void @noundef(ptr %upper.1) 260 %upper.2 = getelementptr inbounds i32, ptr %src, i64 %n.ext 261 call void @noundef(ptr %upper.2) 262 %cmp.idx = icmp ult i32 %idx, %n 263 %idx.ext = zext i32 %idx to i64 264 %src.idx = getelementptr i32, ptr %src, i64 %idx.ext 265 br i1 %cmp.idx, label %then, label %else 266 267then: 268 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.2 269 ret i1 %cmp.upper.1 270 271else: 272 %cmp.upper.2 = icmp ule ptr %src.idx, %upper.2 273 ret i1 %cmp.upper.2 274} 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 i64 280; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 1 281; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]]) 282; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 4 283; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]]) 284; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 4 285; 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 i64 290 %upper.1 = getelementptr inbounds i32, ptr %src, i64 1 291 call void @noundef(ptr %upper.1) 292 %upper.2 = getelementptr inbounds i32, ptr %src, i64 4 293 call void @noundef(ptr %upper.2) 294 %src.idx = getelementptr i32, ptr %src, i64 4 295 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.2 296 ret i1 %cmp.upper.1 297} 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 i64 303; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 4 304; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]]) 305; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 1 306; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]]) 307; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 4 308; 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 i64 313 %upper.1 = getelementptr inbounds i32, ptr %src, i64 4 314 call void @noundef(ptr %upper.1) 315 %upper.2 = getelementptr inbounds i32, ptr %src, i64 1 316 call void @noundef(ptr %upper.2) 317 %src.idx = getelementptr i32, ptr %src, i64 4 318 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.1 319 ret i1 %cmp.upper.1 320} 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 i64 327; CHECK-NEXT: [[UPPER_1:%.*]] = getelementptr inbounds i32, ptr [[SRC:%.*]], i64 1 328; CHECK-NEXT: call void @noundef(ptr [[UPPER_1]]) 329; CHECK-NEXT: [[UPPER_2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 4 330; CHECK-NEXT: call void @noundef(ptr [[UPPER_2]]) 331; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr i32, ptr [[SRC]], i64 5 332; 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 i64 337 %upper.1 = getelementptr inbounds i32, ptr %src, i64 1 338 call void @noundef(ptr %upper.1) 339 %upper.2 = getelementptr inbounds i32, ptr %src, i64 4 340 call void @noundef(ptr %upper.2) 341 %src.idx = getelementptr i32, ptr %src, i64 5 342 %cmp.upper.1 = icmp ule ptr %src.idx, %upper.2 343 ret i1 %cmp.upper.1 344} 345