1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s 3 4define i1 @idx_known_positive_via_len_1(i8 %len, i8 %idx) { 5; CHECK-LABEL: @idx_known_positive_via_len_1( 6; CHECK-NEXT: entry: 7; CHECK-NEXT: [[LEN_POS:%.*]] = icmp sge i8 [[LEN:%.*]], 0 8; CHECK-NEXT: [[IDX_ULT_LEN:%.*]] = icmp ult i8 [[IDX:%.*]], [[LEN]] 9; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[LEN_POS]], [[IDX_ULT_LEN]] 10; CHECK-NEXT: br i1 [[AND_1]], label [[THEN_1:%.*]], label [[ELSE:%.*]] 11; CHECK: then.1: 12; CHECK-NEXT: [[R_1:%.*]] = xor i1 true, true 13; CHECK-NEXT: [[C_1:%.*]] = icmp sge i8 [[IDX]], 1 14; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[C_1]] 15; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], true 16; CHECK-NEXT: ret i1 [[R_3]] 17; CHECK: else: 18; CHECK-NEXT: [[C_3:%.*]] = icmp sge i8 [[IDX]], 0 19; CHECK-NEXT: ret i1 [[C_3]] 20; 21entry: 22 %len.pos = icmp sge i8 %len, 0 23 %idx.ult.len = icmp ult i8 %idx, %len 24 %and.1 = and i1 %len.pos, %idx.ult.len 25 br i1 %and.1, label %then.1, label %else 26 27then.1: 28 %t.1 = icmp ult i8 %idx, %len 29 %t.2 = icmp sge i8 %idx, 0 30 %r.1 = xor i1 %t.1, %t.2 31 32 %c.1 = icmp sge i8 %idx, 1 33 %r.2 = xor i1 %r.1, %c.1 34 35 %c.2 = icmp sge i8 %len, 1 36 %r.3 = xor i1 %r.2, %c.2 37 ret i1 %r.3 38 39else: 40 %c.3 = icmp sge i8 %idx, 0 41 ret i1 %c.3 42} 43 44; Like @idx_known_positive_via_len_1, but with a different order of known facts. 45define i1 @idx_known_positive_via_len_2(i8 %len, i8 %idx) { 46; CHECK-LABEL: @idx_known_positive_via_len_2( 47; CHECK-NEXT: entry: 48; CHECK-NEXT: [[IDX_ULT_LEN:%.*]] = icmp ult i8 [[IDX:%.*]], [[LEN:%.*]] 49; CHECK-NEXT: [[LEN_POS:%.*]] = icmp sge i8 [[LEN]], 0 50; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[IDX_ULT_LEN]], [[LEN_POS]] 51; CHECK-NEXT: br i1 [[AND_1]], label [[THEN_1:%.*]], label [[ELSE:%.*]] 52; CHECK: then.1: 53; CHECK-NEXT: [[R_1:%.*]] = xor i1 true, true 54; CHECK-NEXT: [[C_1:%.*]] = icmp sge i8 [[IDX]], 1 55; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[C_1]] 56; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], true 57; CHECK-NEXT: ret i1 [[R_3]] 58; CHECK: else: 59; CHECK-NEXT: [[C_3:%.*]] = icmp sge i8 [[IDX]], 0 60; CHECK-NEXT: ret i1 [[C_3]] 61; 62entry: 63 %idx.ult.len = icmp ult i8 %idx, %len 64 %len.pos = icmp sge i8 %len, 0 65 %and.1 = and i1 %idx.ult.len, %len.pos 66 br i1 %and.1, label %then.1, label %else 67 68then.1: 69 %t.1 = icmp ult i8 %idx, %len 70 %t.2 = icmp sge i8 %idx, 0 71 %r.1 = xor i1 %t.1, %t.2 72 73 %c.1 = icmp sge i8 %idx, 1 74 %r.2 = xor i1 %r.1, %c.1 75 76 %c.2 = icmp sge i8 %len, 1 77 %r.3 = xor i1 %r.2, %c.2 78 ret i1 %r.3 79 80else: 81 %c.3 = icmp sge i8 %idx, 0 82 ret i1 %c.3 83} 84 85 86; %len >=u 0 is not enough to determine idx >=s 0. 87define i1 @idx_not_known_positive_via_len_uge(i8 %len, i8 %idx) { 88; CHECK-LABEL: @idx_not_known_positive_via_len_uge( 89; CHECK-NEXT: entry: 90; CHECK-NEXT: [[IDX_ULT_LEN:%.*]] = icmp ult i8 [[IDX:%.*]], [[LEN:%.*]] 91; CHECK-NEXT: [[AND_1:%.*]] = and i1 true, [[IDX_ULT_LEN]] 92; CHECK-NEXT: br i1 [[AND_1]], label [[THEN_1:%.*]], label [[ELSE:%.*]] 93; CHECK: then.1: 94; CHECK-NEXT: [[C_2:%.*]] = icmp sge i8 [[IDX]], 0 95; CHECK-NEXT: [[R_1:%.*]] = xor i1 true, [[C_2]] 96; CHECK-NEXT: [[C_3:%.*]] = icmp sge i8 [[IDX]], 1 97; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[C_3]] 98; CHECK-NEXT: [[C_4:%.*]] = icmp sge i8 [[LEN]], 1 99; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], [[C_4]] 100; CHECK-NEXT: ret i1 [[R_3]] 101; CHECK: else: 102; CHECK-NEXT: [[C_5:%.*]] = icmp sge i8 [[IDX]], 0 103; CHECK-NEXT: ret i1 [[C_5]] 104; 105entry: 106 %len.pos = icmp uge i8 %len, 0 107 %idx.ult.len = icmp ult i8 %idx, %len 108 %and.1 = and i1 %len.pos, %idx.ult.len 109 br i1 %and.1, label %then.1, label %else 110 111then.1: 112 %c.1 = icmp ult i8 %idx, %len 113 %c.2 = icmp sge i8 %idx, 0 114 %r.1 = xor i1 %c.1, %c.2 115 116 %c.3 = icmp sge i8 %idx, 1 117 %r.2 = xor i1 %r.1, %c.3 118 119 %c.4 = icmp sge i8 %len, 1 120 %r.3 = xor i1 %r.2, %c.4 121 ret i1 %r.3 122 123else: 124 %c.5 = icmp sge i8 %idx, 0 125 ret i1 %c.5 126} 127 128; There's no information about %len which could be used to determine %len >=s 0. 129define i1 @idx_not_known_positive_via_len(i8 %len, i8 %idx) { 130; CHECK-LABEL: @idx_not_known_positive_via_len( 131; CHECK-NEXT: entry: 132; CHECK-NEXT: [[IDX_ULT_LEN:%.*]] = icmp ult i8 [[IDX:%.*]], [[LEN:%.*]] 133; CHECK-NEXT: br i1 [[IDX_ULT_LEN]], label [[THEN_1:%.*]], label [[ELSE:%.*]] 134; CHECK: then.1: 135; CHECK-NEXT: [[C_2:%.*]] = icmp sge i8 [[IDX]], 0 136; CHECK-NEXT: [[R_1:%.*]] = xor i1 true, [[C_2]] 137; CHECK-NEXT: [[C_3:%.*]] = icmp sge i8 [[IDX]], 1 138; CHECK-NEXT: [[R_2:%.*]] = xor i1 [[R_1]], [[C_3]] 139; CHECK-NEXT: [[C_4:%.*]] = icmp sge i8 [[LEN]], 1 140; CHECK-NEXT: [[R_3:%.*]] = xor i1 [[R_2]], [[C_4]] 141; CHECK-NEXT: ret i1 [[R_3]] 142; CHECK: else: 143; CHECK-NEXT: [[C_5:%.*]] = icmp sge i8 [[IDX]], 0 144; CHECK-NEXT: ret i1 [[C_5]] 145; 146entry: 147 %idx.ult.len = icmp ult i8 %idx, %len 148 br i1 %idx.ult.len, label %then.1, label %else 149 150then.1: 151 %c.1 = icmp ult i8 %idx, %len 152 %c.2 = icmp sge i8 %idx, 0 153 %r.1 = xor i1 %c.1, %c.2 154 155 %c.3 = icmp sge i8 %idx, 1 156 %r.2 = xor i1 %r.1, %c.3 157 158 %c.4 = icmp sge i8 %len, 1 159 %r.3 = xor i1 %r.2, %c.4 160 ret i1 %r.3 161 162else: 163 %c.5 = icmp sge i8 %idx, 0 164 ret i1 %c.5 165} 166 167define i1 @ult_signed_pos_constant(i8 %a) { 168; CHECK-LABEL: @ult_signed_pos_constant( 169; CHECK-NEXT: [[A_ULT_4:%.*]] = icmp ult i8 [[A:%.*]], 4 170; CHECK-NEXT: br i1 [[A_ULT_4]], label [[THEN:%.*]], label [[ELSE:%.*]] 171; CHECK: then: 172; CHECK-NEXT: [[RES_1:%.*]] = xor i1 true, true 173; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], true 174; CHECK-NEXT: ret i1 [[RES_2]] 175; CHECK: else: 176; CHECK-NEXT: [[C_2:%.*]] = icmp sge i8 [[A]], 0 177; CHECK-NEXT: [[C_3:%.*]] = icmp slt i8 [[A]], 4 178; CHECK-NEXT: [[RES_3:%.*]] = xor i1 [[C_2]], [[C_3]] 179; CHECK-NEXT: [[C_4:%.*]] = icmp slt i8 [[A]], 5 180; CHECK-NEXT: [[RES_4:%.*]] = xor i1 [[RES_3]], [[C_4]] 181; CHECK-NEXT: ret i1 [[RES_4]] 182; 183 %a.ult.4 = icmp ult i8 %a, 4 184 br i1 %a.ult.4, label %then, label %else 185 186then: 187 %t.0 = icmp sge i8 %a, 0 188 %t.1 = icmp slt i8 %a, 4 189 %res.1 = xor i1 %t.0, %t.1 190 191 %c.0 = icmp slt i8 %a, 5 192 %res.2 = xor i1 %res.1, %c.0 193 ret i1 %res.2 194 195else: 196 %c.2 = icmp sge i8 %a, 0 197 %c.3 = icmp slt i8 %a, 4 198 %res.3 = xor i1 %c.2, %c.3 199 200 %c.4 = icmp slt i8 %a, 5 201 %res.4 = xor i1 %res.3, %c.4 202 203 ret i1 %res.4 204} 205 206define i1 @ult_signed_neg_constant(i8 %a) { 207; CHECK-LABEL: @ult_signed_neg_constant( 208; CHECK-NEXT: [[A_ULT_4:%.*]] = icmp ult i8 [[A:%.*]], -2 209; CHECK-NEXT: br i1 [[A_ULT_4]], label [[THEN:%.*]], label [[ELSE:%.*]] 210; CHECK: then: 211; CHECK-NEXT: [[C_0:%.*]] = icmp sge i8 [[A]], 0 212; CHECK-NEXT: [[C_1:%.*]] = icmp slt i8 [[A]], -2 213; CHECK-NEXT: [[RES_1:%.*]] = xor i1 [[C_0]], [[C_1]] 214; CHECK-NEXT: ret i1 [[RES_1]] 215; CHECK: else: 216; CHECK-NEXT: ret i1 false 217; 218 %a.ult.4 = icmp ult i8 %a, -2 219 br i1 %a.ult.4, label %then, label %else 220 221then: 222 %c.0 = icmp sge i8 %a, 0 223 %c.1 = icmp slt i8 %a, -2 224 %res.1 = xor i1 %c.0, %c.1 225 ret i1 %res.1 226 227else: 228 ret i1 0 229} 230 231define i1 @ule_signed_pos_constant_1(i8 %a, i8 %b) { 232; CHECK-LABEL: @ule_signed_pos_constant_1( 233; CHECK-NEXT: [[B_NON_NEG:%.*]] = icmp sge i8 [[B:%.*]], 0 234; CHECK-NEXT: call void @llvm.assume(i1 [[B_NON_NEG]]) 235; CHECK-NEXT: [[A_ULE_B:%.*]] = icmp ule i8 [[A:%.*]], [[B]] 236; CHECK-NEXT: call void @llvm.assume(i1 [[A_ULE_B]]) 237; CHECK-NEXT: [[SLT_TEST:%.*]] = icmp slt i8 [[A]], [[B]] 238; CHECK-NEXT: [[RESULT_XOR:%.*]] = xor i1 true, [[SLT_TEST]] 239; CHECK-NEXT: ret i1 [[RESULT_XOR]] 240; 241 %b_non_neg = icmp sge i8 %b, 0 242 call void @llvm.assume(i1 %b_non_neg) 243 %a_ule_b = icmp ule i8 %a, %b 244 call void @llvm.assume(i1 %a_ule_b) 245 246 %sle_test = icmp sle i8 %a, %b 247 %slt_test = icmp slt i8 %a, %b 248 %result_xor = xor i1 %sle_test, %slt_test 249 250 ret i1 %result_xor 251} 252 253define i1 @ule_signed_pos_constant_2(i8 %a) { 254; CHECK-LABEL: @ule_signed_pos_constant_2( 255; CHECK-NEXT: [[A_ULT_4:%.*]] = icmp ule i8 [[A:%.*]], 4 256; CHECK-NEXT: br i1 [[A_ULT_4]], label [[THEN:%.*]], label [[ELSE:%.*]] 257; CHECK: then: 258; CHECK-NEXT: [[RES_1:%.*]] = xor i1 true, true 259; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], true 260; CHECK-NEXT: ret i1 [[RES_2]] 261; CHECK: else: 262; CHECK-NEXT: [[C_2:%.*]] = icmp sge i8 [[A]], 0 263; CHECK-NEXT: [[C_3:%.*]] = icmp sle i8 [[A]], 4 264; CHECK-NEXT: [[RES_3:%.*]] = xor i1 [[C_2]], [[C_3]] 265; CHECK-NEXT: [[C_4:%.*]] = icmp sle i8 [[A]], 5 266; CHECK-NEXT: [[RES_4:%.*]] = xor i1 [[RES_3]], [[C_4]] 267; CHECK-NEXT: ret i1 [[RES_4]] 268; 269 %a.ult.4 = icmp ule i8 %a, 4 270 br i1 %a.ult.4, label %then, label %else 271 272then: 273 %t.0 = icmp sge i8 %a, 0 274 %t.1 = icmp sle i8 %a, 4 275 %res.1 = xor i1 %t.0, %t.1 276 277 %c.0 = icmp sle i8 %a, 5 278 %res.2 = xor i1 %res.1, %c.0 279 ret i1 %res.2 280 281else: 282 %c.2 = icmp sge i8 %a, 0 283 %c.3 = icmp sle i8 %a, 4 284 %res.3 = xor i1 %c.2, %c.3 285 286 %c.4 = icmp sle i8 %a, 5 287 %res.4 = xor i1 %res.3, %c.4 288 289 ret i1 %res.4 290} 291 292define i1 @uge_assumed_positive_values(i8 %a, i8 %b) { 293; CHECK-LABEL: @uge_assumed_positive_values( 294; CHECK-NEXT: [[A_NON_NEG:%.*]] = icmp sge i8 [[A:%.*]], 0 295; CHECK-NEXT: call void @llvm.assume(i1 [[A_NON_NEG]]) 296; CHECK-NEXT: [[A_UGT_B:%.*]] = icmp uge i8 [[A]], [[B:%.*]] 297; CHECK-NEXT: call void @llvm.assume(i1 [[A_UGT_B]]) 298; CHECK-NEXT: ret i1 true 299; 300 %a_non_neg = icmp sge i8 %a, 0 301 call void @llvm.assume(i1 %a_non_neg) 302 %a_ugt_b = icmp uge i8 %a, %b 303 call void @llvm.assume(i1 %a_ugt_b) 304 305 %result = icmp sge i8 %a, %b 306 307 ret i1 %result 308} 309 310define i1 @ugt_assumed_positive_values(i8 %a, i8 %b) { 311; CHECK-LABEL: @ugt_assumed_positive_values( 312; CHECK-NEXT: [[A_NON_NEG:%.*]] = icmp sge i8 [[A:%.*]], 0 313; CHECK-NEXT: call void @llvm.assume(i1 [[A_NON_NEG]]) 314; CHECK-NEXT: [[A_UGT_B:%.*]] = icmp ugt i8 [[A]], [[B:%.*]] 315; CHECK-NEXT: call void @llvm.assume(i1 [[A_UGT_B]]) 316; CHECK-NEXT: ret i1 true 317; 318 %a_non_neg = icmp sge i8 %a, 0 319 call void @llvm.assume(i1 %a_non_neg) 320 %a_ugt_b = icmp ugt i8 %a, %b 321 call void @llvm.assume(i1 %a_ugt_b) 322 323 %result = icmp sgt i8 %a, %b 324 325 ret i1 %result 326} 327 328declare void @llvm.assume(i1) 329