summaryrefslogtreecommitdiff
path: root/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/InstCombine/InstCombineAndOrXor.cpp')
-rw-r--r--lib/Transforms/InstCombine/InstCombineAndOrXor.cpp126
1 files changed, 67 insertions, 59 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index a881bda5ba98d..d3d8cefe97353 100644
--- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1097,20 +1097,11 @@ static Instruction *foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast,
Type *DestTy = Logic.getType();
Type *SrcTy = Cast->getSrcTy();
- // If the first operand is bitcast, move the logic operation ahead of the
- // bitcast (do the logic operation in the original type). This can eliminate
- // bitcasts and allow combines that would otherwise be impeded by the bitcast.
+ // Move the logic operation ahead of a zext if the constant is unchanged in
+ // the smaller source type. Performing the logic in a smaller type may provide
+ // more information to later folds, and the smaller logic instruction may be
+ // cheaper (particularly in the case of vectors).
Value *X;
- if (match(Cast, m_BitCast(m_Value(X)))) {
- Value *NewConstant = ConstantExpr::getBitCast(C, SrcTy);
- Value *NewOp = Builder->CreateBinOp(LogicOpc, X, NewConstant);
- return CastInst::CreateBitOrPointerCast(NewOp, DestTy);
- }
-
- // Similarly, move the logic operation ahead of a zext if the constant is
- // unchanged in the smaller source type. Performing the logic in a smaller
- // type may provide more information to later folds, and the smaller logic
- // instruction may be cheaper (particularly in the case of vectors).
if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
@@ -1239,9 +1230,10 @@ static Instruction *foldAndToXor(BinaryOperator &I,
// (A | ~B) & (B | ~A) --> ~(A ^ B)
// (~B | A) & (~A | B) --> ~(A ^ B)
// (~B | A) & (B | ~A) --> ~(A ^ B)
- if (match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) &&
- match(Op1, m_c_Or(m_Not(m_Specific(A)), m_Specific(B))))
- return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
+ if (Op0->hasOneUse() || Op1->hasOneUse())
+ if (match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) &&
+ match(Op1, m_c_Or(m_Not(m_Specific(A)), m_Specific(B))))
+ return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
return nullptr;
}
@@ -1256,9 +1248,10 @@ static Instruction *foldOrToXor(BinaryOperator &I,
// Operand complexity canonicalization guarantees that the 'and' is Op0.
// (A & B) | ~(A | B) --> ~(A ^ B)
// (A & B) | ~(B | A) --> ~(A ^ B)
- if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
- match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
- return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
+ if (Op0->hasOneUse() || Op1->hasOneUse())
+ if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
+ match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
+ return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
// (A & ~B) | (~A & B) --> A ^ B
// (A & ~B) | (B & ~A) --> A ^ B
@@ -1442,13 +1435,13 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
// (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
- if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
+ if (Op1->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
return BinaryOperator::CreateAnd(Op0, Builder->CreateNot(C));
// ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
- if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
+ if (Op0->hasOneUse() || IsFreeToInvert(C, C->hasOneUse()))
return BinaryOperator::CreateAnd(Op1, Builder->CreateNot(C));
// (A | B) & ((~A) ^ B) -> (A & B)
@@ -1579,11 +1572,14 @@ static Value *getSelectCondition(Value *A, Value *B,
// If A and B are sign-extended, look through the sexts to find the booleans.
Value *Cond;
+ Value *NotB;
if (match(A, m_SExt(m_Value(Cond))) &&
Cond->getType()->getScalarType()->isIntegerTy(1) &&
- match(B, m_CombineOr(m_Not(m_SExt(m_Specific(Cond))),
- m_SExt(m_Not(m_Specific(Cond))))))
- return Cond;
+ match(B, m_OneUse(m_Not(m_Value(NotB))))) {
+ NotB = peekThroughBitcast(NotB, true);
+ if (match(NotB, m_SExt(m_Specific(Cond))))
+ return Cond;
+ }
// All scalar (and most vector) possibilities should be handled now.
// Try more matches that only apply to non-splat constant vectors.
@@ -1615,12 +1611,8 @@ static Value *matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D,
// The potential condition of the select may be bitcasted. In that case, look
// through its bitcast and the corresponding bitcast of the 'not' condition.
Type *OrigType = A->getType();
- Value *SrcA, *SrcB;
- if (match(A, m_OneUse(m_BitCast(m_Value(SrcA)))) &&
- match(B, m_OneUse(m_BitCast(m_Value(SrcB))))) {
- A = SrcA;
- B = SrcB;
- }
+ A = peekThroughBitcast(A, true);
+ B = peekThroughBitcast(B, true);
if (Value *Cond = getSelectCondition(A, B, Builder)) {
// ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
@@ -1922,8 +1914,9 @@ Value *InstCombiner::foldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
/// (A & C1) | B
///
/// when the XOR of the two constants is "all ones" (-1).
-Instruction *InstCombiner::FoldOrWithConstants(BinaryOperator &I, Value *Op,
- Value *A, Value *B, Value *C) {
+static Instruction *FoldOrWithConstants(BinaryOperator &I, Value *Op,
+ Value *A, Value *B, Value *C,
+ InstCombiner::BuilderTy *Builder) {
ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
if (!CI1) return nullptr;
@@ -1944,15 +1937,16 @@ Instruction *InstCombiner::FoldOrWithConstants(BinaryOperator &I, Value *Op,
/// \brief This helper function folds:
///
-/// ((A | B) & C1) ^ (B & C2)
+/// ((A ^ B) & C1) | (B & C2)
///
/// into:
///
/// (A & C1) ^ B
///
/// when the XOR of the two constants is "all ones" (-1).
-Instruction *InstCombiner::FoldXorWithConstants(BinaryOperator &I, Value *Op,
- Value *A, Value *B, Value *C) {
+static Instruction *FoldXorWithConstants(BinaryOperator &I, Value *Op,
+ Value *A, Value *B, Value *C,
+ InstCombiner::BuilderTy *Builder) {
ConstantInt *CI1 = dyn_cast<ConstantInt>(C);
if (!CI1)
return nullptr;
@@ -2112,46 +2106,36 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) {
}
// ((A|B)&1)|(B&-2) -> (A&1) | B
- if (match(A, m_Or(m_Value(V1), m_Specific(B))) ||
- match(A, m_Or(m_Specific(B), m_Value(V1)))) {
- Instruction *Ret = FoldOrWithConstants(I, Op1, V1, B, C);
- if (Ret) return Ret;
+ if (match(A, m_c_Or(m_Value(V1), m_Specific(B)))) {
+ if (Instruction *Ret = FoldOrWithConstants(I, Op1, V1, B, C, Builder))
+ return Ret;
}
// (B&-2)|((A|B)&1) -> (A&1) | B
- if (match(B, m_Or(m_Specific(A), m_Value(V1))) ||
- match(B, m_Or(m_Value(V1), m_Specific(A)))) {
- Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D);
- if (Ret) return Ret;
+ if (match(B, m_c_Or(m_Specific(A), m_Value(V1)))) {
+ if (Instruction *Ret = FoldOrWithConstants(I, Op0, A, V1, D, Builder))
+ return Ret;
}
// ((A^B)&1)|(B&-2) -> (A&1) ^ B
- if (match(A, m_Xor(m_Value(V1), m_Specific(B))) ||
- match(A, m_Xor(m_Specific(B), m_Value(V1)))) {
- Instruction *Ret = FoldXorWithConstants(I, Op1, V1, B, C);
- if (Ret) return Ret;
+ if (match(A, m_c_Xor(m_Value(V1), m_Specific(B)))) {
+ if (Instruction *Ret = FoldXorWithConstants(I, Op1, V1, B, C, Builder))
+ return Ret;
}
// (B&-2)|((A^B)&1) -> (A&1) ^ B
- if (match(B, m_Xor(m_Specific(A), m_Value(V1))) ||
- match(B, m_Xor(m_Value(V1), m_Specific(A)))) {
- Instruction *Ret = FoldXorWithConstants(I, Op0, A, V1, D);
- if (Ret) return Ret;
+ if (match(B, m_c_Xor(m_Specific(A), m_Value(V1)))) {
+ if (Instruction *Ret = FoldXorWithConstants(I, Op0, A, V1, D, Builder))
+ return Ret;
}
}
// (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
- // FIXME: The two hasOneUse calls here are the same call, maybe we were
- // supposed to check Op1->operand(0)?
if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
- if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
- return BinaryOperator::CreateOr(Op0, C);
+ return BinaryOperator::CreateOr(Op0, C);
// ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
- // FIXME: The two hasOneUse calls here are the same call, maybe we were
- // supposed to check Op0->operand(0)?
if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
- if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
- return BinaryOperator::CreateOr(Op1, C);
+ return BinaryOperator::CreateOr(Op1, C);
// ((B | C) & A) | B -> B | (A & C)
if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
@@ -2357,6 +2341,30 @@ Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
}
}
+ // Instead of trying to imitate the folds for and/or, decompose this 'xor'
+ // into those logic ops. That is, try to turn this into an and-of-icmps
+ // because we have many folds for that pattern.
+ //
+ // This is based on a truth table definition of xor:
+ // X ^ Y --> (X | Y) & !(X & Y)
+ if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
+ // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
+ // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
+ if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
+ // TODO: Independently handle cases where the 'and' side is a constant.
+ if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) {
+ // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS
+ RHS->setPredicate(RHS->getInversePredicate());
+ return Builder->CreateAnd(LHS, RHS);
+ }
+ if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) {
+ // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS
+ LHS->setPredicate(LHS->getInversePredicate());
+ return Builder->CreateAnd(LHS, RHS);
+ }
+ }
+ }
+
return nullptr;
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-01 23:49:17 +0000