aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/InstructionSimplify.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis/InstructionSimplify.cpp')
-rw-r--r--llvm/lib/Analysis/InstructionSimplify.cpp184
1 files changed, 112 insertions, 72 deletions
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 864eeea4f8bf..22d2ce11cc90 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2180,6 +2180,55 @@ Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
}
+static Value *simplifyOrLogic(Value *X, Value *Y) {
+ assert(X->getType() == Y->getType() && "Expected same type for 'or' ops");
+ Type *Ty = X->getType();
+
+ // X | ~X --> -1
+ if (match(Y, m_Not(m_Specific(X))))
+ return ConstantInt::getAllOnesValue(Ty);
+
+ // X | ~(X & ?) = -1
+ if (match(Y, m_Not(m_c_And(m_Specific(X), m_Value()))))
+ return ConstantInt::getAllOnesValue(Ty);
+
+ // X | (X & ?) --> X
+ if (match(Y, m_c_And(m_Specific(X), m_Value())))
+ return X;
+
+ Value *A, *B;
+
+ // (A & ~B) | (A ^ B) --> A ^ B
+ // (~B & A) | (A ^ B) --> A ^ B
+ // (A & ~B) | (B ^ A) --> B ^ A
+ // (~B & A) | (B ^ A) --> B ^ A
+ if (match(X, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
+ match(Y, m_c_Xor(m_Specific(A), m_Specific(B))))
+ return Y;
+
+ // (~A ^ B) | (A & B) --> ~A ^ B
+ // (B ^ ~A) | (A & B) --> B ^ ~A
+ // (~A ^ B) | (B & A) --> ~A ^ B
+ // (B ^ ~A) | (B & A) --> B ^ ~A
+ if (match(X, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
+ match(Y, m_c_And(m_Specific(A), m_Specific(B))))
+ return X;
+
+ // (A ^ B) | (A | B) --> A | B
+ // (A ^ B) | (B | A) --> B | A
+ if (match(X, m_Xor(m_Value(A), m_Value(B))) &&
+ match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
+ return Y;
+
+ // ~(A ^ B) | (A | B) --> -1
+ // ~(A ^ B) | (B | A) --> -1
+ if (match(X, m_Not(m_Xor(m_Value(A), m_Value(B)))) &&
+ match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
+ return ConstantInt::getAllOnesValue(Ty);
+
+ return nullptr;
+}
+
/// Given operands for an Or, see if we can fold the result.
/// If not, this returns null.
static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
@@ -2202,81 +2251,15 @@ static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
if (Op0 == Op1 || match(Op1, m_Zero()))
return Op0;
- // A | ~A = ~A | A = -1
- if (match(Op0, m_Not(m_Specific(Op1))) ||
- match(Op1, m_Not(m_Specific(Op0))))
- return Constant::getAllOnesValue(Op0->getType());
-
- // (A & ?) | A = A
- if (match(Op0, m_c_And(m_Specific(Op1), m_Value())))
- return Op1;
-
- // A | (A & ?) = A
- if (match(Op1, m_c_And(m_Specific(Op0), m_Value())))
- return Op0;
-
- // ~(A & ?) | A = -1
- if (match(Op0, m_Not(m_c_And(m_Specific(Op1), m_Value()))))
- return Constant::getAllOnesValue(Op1->getType());
-
- // A | ~(A & ?) = -1
- if (match(Op1, m_Not(m_c_And(m_Specific(Op0), m_Value()))))
- return Constant::getAllOnesValue(Op0->getType());
+ if (Value *R = simplifyOrLogic(Op0, Op1))
+ return R;
+ if (Value *R = simplifyOrLogic(Op1, Op0))
+ return R;
if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::Or))
return V;
Value *A, *B, *NotA;
- // (A & ~B) | (A ^ B) -> (A ^ B)
- // (~B & A) | (A ^ B) -> (A ^ B)
- // (A & ~B) | (B ^ A) -> (B ^ A)
- // (~B & A) | (B ^ A) -> (B ^ A)
- if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
- (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
- match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
- return Op1;
-
- // Commute the 'or' operands.
- // (A ^ B) | (A & ~B) -> (A ^ B)
- // (A ^ B) | (~B & A) -> (A ^ B)
- // (B ^ A) | (A & ~B) -> (B ^ A)
- // (B ^ A) | (~B & A) -> (B ^ A)
- if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
- (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
- match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
- return Op0;
-
- // (A & B) | (~A ^ B) -> (~A ^ B)
- // (B & A) | (~A ^ B) -> (~A ^ B)
- // (A & B) | (B ^ ~A) -> (B ^ ~A)
- // (B & A) | (B ^ ~A) -> (B ^ ~A)
- if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
- (match(Op1, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
- match(Op1, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
- return Op1;
-
- // Commute the 'or' operands.
- // (~A ^ B) | (A & B) -> (~A ^ B)
- // (~A ^ B) | (B & A) -> (~A ^ B)
- // (B ^ ~A) | (A & B) -> (B ^ ~A)
- // (B ^ ~A) | (B & A) -> (B ^ ~A)
- if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
- (match(Op0, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
- match(Op0, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
- return Op0;
-
- // (A | B) | (A ^ B) --> A | B
- // (B | A) | (A ^ B) --> B | A
- if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
- match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
- return Op0;
-
- // Commute the outer 'or' operands.
- // (A ^ B) | (A | B) --> A | B
- // (A ^ B) | (B | A) --> B | A
- if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
- match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
- return Op1;
// (~A & B) | ~(A | B) --> ~A
// (~A & B) | ~(B | A) --> ~A
@@ -2414,6 +2397,30 @@ static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
match(Op1, m_Not(m_Specific(Op0))))
return Constant::getAllOnesValue(Op0->getType());
+ auto foldAndOrNot = [](Value *X, Value *Y) -> Value * {
+ Value *A, *B;
+ // (~A & B) ^ (A | B) --> A -- There are 8 commuted variants.
+ if (match(X, m_c_And(m_Not(m_Value(A)), m_Value(B))) &&
+ match(Y, m_c_Or(m_Specific(A), m_Specific(B))))
+ return A;
+
+ // (~A | B) ^ (A & B) --> ~A -- There are 8 commuted variants.
+ // The 'not' op must contain a complete -1 operand (no undef elements for
+ // vector) for the transform to be safe.
+ Value *NotA;
+ if (match(X,
+ m_c_Or(m_CombineAnd(m_NotForbidUndef(m_Value(A)), m_Value(NotA)),
+ m_Value(B))) &&
+ match(Y, m_c_And(m_Specific(A), m_Specific(B))))
+ return NotA;
+
+ return nullptr;
+ };
+ if (Value *R = foldAndOrNot(Op0, Op1))
+ return R;
+ if (Value *R = foldAndOrNot(Op1, Op0))
+ return R;
+
if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::Xor))
return V;
@@ -2935,8 +2942,10 @@ static Value *simplifyICmpWithBinOpOnLHS(
return getFalse(ITy);
}
- // x >> y <=u x
- // x udiv y <=u x.
+ // x >>u y <=u x --> true.
+ // x >>u y >u x --> false.
+ // x udiv y <=u x --> true.
+ // x udiv y >u x --> false.
if (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
// icmp pred (X op Y), X
@@ -2946,6 +2955,37 @@ static Value *simplifyICmpWithBinOpOnLHS(
return getTrue(ITy);
}
+ // If x is nonzero:
+ // x >>u C <u x --> true for C != 0.
+ // x >>u C != x --> true for C != 0.
+ // x >>u C >=u x --> false for C != 0.
+ // x >>u C == x --> false for C != 0.
+ // x udiv C <u x --> true for C != 1.
+ // x udiv C != x --> true for C != 1.
+ // x udiv C >=u x --> false for C != 1.
+ // x udiv C == x --> false for C != 1.
+ // TODO: allow non-constant shift amount/divisor
+ const APInt *C;
+ if ((match(LBO, m_LShr(m_Specific(RHS), m_APInt(C))) && *C != 0) ||
+ (match(LBO, m_UDiv(m_Specific(RHS), m_APInt(C))) && *C != 1)) {
+ if (isKnownNonZero(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT)) {
+ switch (Pred) {
+ default:
+ break;
+ case ICmpInst::ICMP_EQ:
+ case ICmpInst::ICMP_UGE:
+ return getFalse(ITy);
+ case ICmpInst::ICMP_NE:
+ case ICmpInst::ICMP_ULT:
+ return getTrue(ITy);
+ case ICmpInst::ICMP_UGT:
+ case ICmpInst::ICMP_ULE:
+ // UGT/ULE are handled by the more general case just above
+ llvm_unreachable("Unexpected UGT/ULE, should have been handled");
+ }
+ }
+ }
+
// (x*C1)/C2 <= x for C1 <= C2.
// This holds even if the multiplication overflows: Assume that x != 0 and
// arithmetic is modulo M. For overflow to occur we must have C1 >= M/x and
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-12 04:00:24 +0000