Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -307,15 +307,17 @@ /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E). /// Return the set of pattern classes (from MaskedICmpType) that both LHS and /// RHS satisfy. -static unsigned getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, - Value *&D, Value *&E, ICmpInst *LHS, - ICmpInst *RHS, - ICmpInst::Predicate &PredL, - ICmpInst::Predicate &PredR) { +static +Optional> +getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C, + Value *&D, Value *&E, ICmpInst *LHS, + ICmpInst *RHS, + ICmpInst::Predicate &PredL, + ICmpInst::Predicate &PredR) { // vectors are not (yet?) supported. Don't support pointers either. if (!LHS->getOperand(0)->getType()->isIntegerTy() || !RHS->getOperand(0)->getType()->isIntegerTy()) - return 0; + return None; // Here comes the tricky part: // LHS might be of the form L11 & L12 == X, X == L21 & L22, @@ -346,7 +348,7 @@ // Bail if LHS was a icmp that can't be decomposed into an equality. if (!ICmpInst::isEquality(PredL)) - return 0; + return None; Value *R1 = RHS->getOperand(0); Value *R2 = RHS->getOperand(1); @@ -360,7 +362,7 @@ A = R12; D = R11; } else { - return 0; + return None; } E = R2; R1 = nullptr; @@ -388,7 +390,7 @@ // Bail if RHS was a icmp that can't be decomposed into an equality. if (!ICmpInst::isEquality(PredR)) - return 0; + return None; // Look for ANDs on the right side of the RHS icmp. if (!Ok) { @@ -408,11 +410,11 @@ E = R1; Ok = true; } else { - return 0; + return None; } } if (!Ok) - return 0; + return None; if (L11 == A) { B = L12; @@ -430,7 +432,88 @@ unsigned LeftType = getMaskedICmpType(A, B, C, PredL); unsigned RightType = getMaskedICmpType(A, D, E, PredR); - return LeftType & RightType; + return Optional>(std::make_pair(LeftType, RightType)); +} + +static Value * foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed( + ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, + Value *A, Value *B, Value *C, Value *D, Value *E, + ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, + unsigned LHSMask, unsigned RHSMask) { + // We are given the canonical form: + // (icmp ne (A & B), 0) && (icmp eq (A & D), E). + // where D & E == E. + // + // If IsAnd is false, we get it in negated form: + // (icmp eq (A & B), 0) || (icmp ne (A & D), E) -> + // !((icmp ne (A & B), 0) && (icmp eq (A & D), E)). + // + // We currently handle the case of B, C, D, E are constant. + // + // If there's no contradiction, ((B & D) & E) != 0, then RHS implies LHS, so + // (LHS && RHS) == RHS. Otherwise, the whole expression becomes false (or true + // if negated.) + // + // For example, + // (icmp ne (A & 255), 0) && (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8). + // (icmp ne (A & 7), 0) && (icmp eq (A & 15), 8) -> false. + // (icmp ne (A & 12), 0) && (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8). + ConstantInt *BCst = dyn_cast(B); + if (!BCst) + return nullptr; + ConstantInt *CCst = dyn_cast(C); + if (!CCst) + return nullptr; + ConstantInt *DCst = dyn_cast(D); + if (!DCst) + return nullptr; + ConstantInt *ECst = dyn_cast(E); + if (!ECst) + return nullptr; + + // Update E to the canonical form when D is a power of two and RHS is + // canonicalized as, + // (icmp ne (A & D), 0) -> (icmp eq (A & D), D) or + // (icmp ne (A & D), D) -> (icmp eq (A & D, 0). + if (PredR != (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) + ECst = cast(ConstantExpr::getXor(DCst, ECst)); + + if (ConstantExpr::getAnd(ConstantExpr::getAnd(BCst, DCst), ECst) != + ConstantInt::get(BCst->getType(), 0)) + return RHS; + return ConstantInt::get(LHS->getType(), !IsAnd); +} + +static Value *foldLogOpOfMaskedICmpsAsymmetric( + ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, + Value *A, Value *B, Value *C, Value *D, Value *E, + ICmpInst::Predicate PredL, ICmpInst::Predicate PredR, + unsigned LHSMask, unsigned RHSMask) { + assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) && + "Expected equality predicates for masked type of icmps."); + // Handle Mask_NotAllZeros-BMask_Mixed cases. + // (icmp ne/eq (A & B), C) &&/|| (icmp eq/ne (A & D), E), or + // (icmp eq/ne (A & B), C) &&/|| (icmp ne/eq (A & D), E) + // which gets swapped to + // (icmp ne/eq (A & D), E) &&/|| (icmp eq/ne (A & B), C). + if (!IsAnd) { + LHSMask = conjugateICmpMask(LHSMask); + RHSMask = conjugateICmpMask(RHSMask); + } + if ((LHSMask & Mask_NotAllZeros) && (RHSMask & BMask_Mixed)) { + if (Value *V = foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed( + LHS, RHS, IsAnd, A, B, C, D, E, + PredL, PredR, LHSMask, RHSMask)) { + return V; + } + } else if ((LHSMask & BMask_Mixed) && (RHSMask & Mask_NotAllZeros)) { + if (Value *V = foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed( + RHS, LHS, IsAnd, A, D, E, B, C, + PredR, PredL, RHSMask, LHSMask)) { + return V; + } + } + return nullptr; } /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) @@ -439,13 +522,23 @@ llvm::InstCombiner::BuilderTy &Builder) { Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr; ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate(); - unsigned Mask = + Optional> MaskPair = getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR); - if (Mask == 0) + if (!MaskPair) return nullptr; - assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) && "Expected equality predicates for masked type of icmps."); + unsigned LHSMask = MaskPair->first; + unsigned RHSMask = MaskPair->second; + unsigned Mask = LHSMask & RHSMask; + if (Mask == 0) { + // Even if the two sides don't share a common pattern, check if folding can + // still happen. + if (Value *V = foldLogOpOfMaskedICmpsAsymmetric( + LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask)) + return V; + return nullptr; + } // In full generality: // (icmp (A & B) Op C) | (icmp (A & D) Op E) Index: test/Transforms/InstCombine/icmp-logical.ll =================================================================== --- test/Transforms/InstCombine/icmp-logical.ll +++ test/Transforms/InstCombine/icmp-logical.ll @@ -183,3 +183,122 @@ ret <2 x i1> %cmp } +; ((X & 15) != 0 && (X & 15) == 8) -> (X & 15) == 8 +define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_0(i32 %x) { +; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_0( +; CHECK-NEXT: [[AND1:%.*]] = and i32 %x, 15 +; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[AND1]], 8 +; CHECK-NEXT: ret i1 [[CMP1]] +; + %1 = and i32 %x, 15 + %2 = icmp ne i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp eq i32 %3, 8 + %5 = and i1 %2, %4 + ret i1 %5 +} + +; ((X & 255) != 0 && (X & 15) == 8) -> (X & 15) == 8 +define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_1(i32 %x) { +; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_1( +; CHECK-NEXT: [[AND1:%.*]] = and i32 %x, 15 +; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[AND1]], 8 +; CHECK-NEXT: ret i1 [[CMP1]] +; + %1 = and i32 %x, 255 + %2 = icmp ne i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp eq i32 %3, 8 + %5 = and i1 %2, %4 + ret i1 %5 +} + +; ((X & 7) != 0 && (X & 15) == 8) -> false +define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_2(i32 %x) { +; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_2( +; CHECK-NEXT: ret i1 false +; + %1 = and i32 %x, 7 + %2 = icmp ne i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp eq i32 %3, 8 + %5 = and i1 %2, %4 + ret i1 %5 +} + +; ((X & 12) != 0 && (X & 15) == 8) -> (X & 15) == 8 +define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_3(i32 %x) { +; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_3( +; CHECK-NEXT: [[AND1:%.*]] = and i32 %x, 15 +; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[AND1]], 8 +; CHECK-NEXT: ret i1 [[CMP1]] +; + %1 = and i32 %x, 12 + %2 = icmp ne i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp eq i32 %3, 8 + %5 = and i1 %2, %4 + ret i1 %5 +} + +; ((X & 15) == 0 || (X & 15) != 8) -> !((X & 15) != 0 && (X & 15) == 8)) -> +; !((X & 15) == 8) -> (X & 15) != 8 +define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_0(i32 %x) { +; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_0( +; CHECK-NEXT: [[AND1:%.*]] = and i32 %x, 15 +; CHECK-NEXT: [[CMP1:%.*]] = icmp ne i32 [[AND1]], 8 +; CHECK-NEXT: ret i1 [[CMP1]] +; + %1 = and i32 %x, 15 + %2 = icmp eq i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp ne i32 %3, 8 + %5 = or i1 %2, %4 + ret i1 %5 +} + +; ((X & 255) == 0 || (X & 15) != 8) -> !((X & 255) != 0 && (X & 15) == 8) -> +; !((X & 15) == 8) -> (X & 15) != 8 +define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_1(i32 %x) { +; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_1( +; CHECK-NEXT: [[AND1:%.*]] = and i32 %x, 15 +; CHECK-NEXT: [[CMP1:%.*]] = icmp ne i32 [[AND1]], 8 +; CHECK-NEXT: ret i1 [[CMP1]] +; + %1 = and i32 %x, 255 + %2 = icmp eq i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp ne i32 %3, 8 + %5 = or i1 %2, %4 + ret i1 %5 +} + +; ((X & 7) == 0 || (X & 15) != 8) -> !((X & 7) != 0 && (X & 15) == 8) -> +; !(false) -> true +define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_2(i32 %x) { +; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_2( +; CHECK-NEXT: ret i1 true +; + %1 = and i32 %x, 7 + %2 = icmp eq i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp ne i32 %3, 8 + %5 = or i1 %2, %4 + ret i1 %5 +} + +; ((X & 12) == 0 || (X & 15) != 8) -> !((X & 12) != 0 && (X & 15) == 8) -> +; !((X & 15) == 8) -> (X & 15) != 8 +define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_3(i32 %x) { +; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_3( +; CHECK-NEXT: [[AND1:%.*]] = and i32 %x, 15 +; CHECK-NEXT: [[CMP1:%.*]] = icmp ne i32 [[AND1]], 8 +; CHECK-NEXT: ret i1 [[CMP1]] +; + %1 = and i32 %x, 12 + %2 = icmp eq i32 %1, 0 + %3 = and i32 %x, 15 + %4 = icmp ne i32 %3, 8 + %5 = or i1 %2, %4 + ret i1 %5 +}