#include "InstCombine.h"
#include "llvm/Intrinsics.h"
#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/PatternMatch.h"
using namespace llvm;
using namespace PatternMatch;
ConstantInt *CI = ConstantInt::get(AndRHS->getContext(),
AndRHS->getValue() & ShlMask);
- if (CI->getValue() == ShlMask) {
- // Masking out bits that the shift already masks
+ if (CI->getValue() == ShlMask)
+ // Masking out bits that the shift already masks.
return ReplaceInstUsesWith(TheAnd, Op); // No need for the and.
- } else if (CI != AndRHS) { // Reducing bits set in and.
+
+ if (CI != AndRHS) { // Reducing bits set in and.
TheAnd.setOperand(1, CI);
return &TheAnd;
}
ConstantInt *CI = ConstantInt::get(Op->getContext(),
AndRHS->getValue() & ShrMask);
- if (CI->getValue() == ShrMask) {
- // Masking out bits that the shift already masks.
+ if (CI->getValue() == ShrMask)
+ // Masking out bits that the shift already masks.
return ReplaceInstUsesWith(TheAnd, Op);
- } else if (CI != AndRHS) {
+
+ if (CI != AndRHS) {
TheAnd.setOperand(1, CI); // Reduce bits set in and cst.
return &TheAnd;
}
/// InsertRangeTest - Emit a computation of: (V >= Lo && V < Hi) if Inside is
-/// true, otherwise (V < Lo || V >= Hi). In pratice, we emit the more efficient
+/// true, otherwise (V < Lo || V >= Hi). In practice, we emit the more efficient
/// (V-Lo) <u Hi-Lo. This method expects that Lo <= Hi. isSigned indicates
/// whether to treat the V, Lo and HI as signed or not. IB is the location to
/// insert new instructions.
Value *NewOr = Builder->CreateOr(Val, Val2);
return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
}
+
+ // (icmp slt A, 0) & (icmp slt B, 0) --> (icmp slt (A&B), 0)
+ if (LHSCC == ICmpInst::ICMP_SLT && LHSCst->isZero()) {
+ Value *NewAnd = Builder->CreateAnd(Val, Val2);
+ return Builder->CreateICmp(LHSCC, NewAnd, LHSCst);
+ }
+
+ // (icmp sgt A, -1) & (icmp sgt B, -1) --> (icmp sgt (A|B), -1)
+ if (LHSCC == ICmpInst::ICMP_SGT && LHSCst->isAllOnesValue()) {
+ Value *NewOr = Builder->CreateOr(Val, Val2);
+ return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
+ }
+ }
+
+ // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
+ // where CMAX is the all ones value for the truncated type,
+ // iff the lower bits of C2 and CA are zero.
+ if (LHSCC == RHSCC && ICmpInst::isEquality(LHSCC) &&
+ LHS->hasOneUse() && RHS->hasOneUse()) {
+ Value *V;
+ ConstantInt *AndCst, *SmallCst = 0, *BigCst = 0;
+
+ // (trunc x) == C1 & (and x, CA) == C2
+ if (match(Val2, m_Trunc(m_Value(V))) &&
+ match(Val, m_And(m_Specific(V), m_ConstantInt(AndCst)))) {
+ SmallCst = RHSCst;
+ BigCst = LHSCst;
+ }
+ // (and x, CA) == C2 & (trunc x) == C1
+ else if (match(Val, m_Trunc(m_Value(V))) &&
+ match(Val2, m_And(m_Specific(V), m_ConstantInt(AndCst)))) {
+ SmallCst = LHSCst;
+ BigCst = RHSCst;
+ }
+
+ if (SmallCst && BigCst) {
+ unsigned BigBitSize = BigCst->getType()->getBitWidth();
+ unsigned SmallBitSize = SmallCst->getType()->getBitWidth();
+
+ // Check that the low bits are zero.
+ APInt Low = APInt::getLowBitsSet(BigBitSize, SmallBitSize);
+ if ((Low & AndCst->getValue()) == 0 && (Low & BigCst->getValue()) == 0) {
+ Value *NewAnd = Builder->CreateAnd(V, Low | AndCst->getValue());
+ APInt N = SmallCst->getValue().zext(BigBitSize) | BigCst->getValue();
+ Value *NewVal = ConstantInt::get(AndCst->getType()->getContext(), N);
+ return Builder->CreateICmp(LHSCC, NewAnd, NewVal);
+ }
+ }
}
// From here on, we only handle:
LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE ||
RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE)
return 0;
-
+
+ // Make a constant range that's the intersection of the two icmp ranges.
+ // If the intersection is empty, we know that the result is false.
+ ConstantRange LHSRange =
+ ConstantRange::makeICmpRegion(LHSCC, LHSCst->getValue());
+ ConstantRange RHSRange =
+ ConstantRange::makeICmpRegion(RHSCC, RHSCst->getValue());
+
+ if (LHSRange.intersectWith(RHSRange).isEmptySet())
+ return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
+
// We can't fold (ugt x, C) & (sgt x, C2).
if (!PredicatesFoldable(LHSCC, RHSCC))
return 0;
case ICmpInst::ICMP_EQ:
switch (RHSCC) {
default: llvm_unreachable("Unknown integer condition code!");
- case ICmpInst::ICMP_EQ: // (X == 13 & X == 15) -> false
- case ICmpInst::ICMP_UGT: // (X == 13 & X > 15) -> false
- case ICmpInst::ICMP_SGT: // (X == 13 & X > 15) -> false
- return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
case ICmpInst::ICMP_NE: // (X == 13 & X != 15) -> X == 13
case ICmpInst::ICMP_ULT: // (X == 13 & X < 15) -> X == 13
case ICmpInst::ICMP_SLT: // (X == 13 & X < 15) -> X == 13
case ICmpInst::ICMP_SLT:
switch (RHSCC) {
default: llvm_unreachable("Unknown integer condition code!");
- case ICmpInst::ICMP_EQ: // (X s< 13 & X == 15) -> false
- case ICmpInst::ICMP_SGT: // (X s< 13 & X s> 15) -> false
- return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
case ICmpInst::ICMP_UGT: // (X s< 13 & X u> 15) -> no change
break;
case ICmpInst::ICMP_NE: // (X s< 13 & X != 15) -> X < 13
}
break;
}
-
+
if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
return Res;
cast<BinaryOperator>(Op1)->swapOperands();
std::swap(A, B);
}
- if (A == Op0) // A&(A^B) -> A & ~B
+ // Notice that the patten (A&(~B)) is actually (A&(-1^B)), so if
+ // A is originally -1 (or a vector of -1 and undefs), then we enter
+ // an endless loop. By checking that A is non-constant we ensure that
+ // we will never get to the loop.
+ if (A == Op0 && !isa<Constant>(A)) // A&(A^B) -> A & ~B
return BinaryOperator::CreateAnd(A, Builder->CreateNot(B, "tmp"));
}
/// MatchBSwap - Given an OR instruction, check to see if this is a bswap idiom.
/// If so, insert the new bswap intrinsic and return it.
Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
- const IntegerType *ITy = dyn_cast<IntegerType>(I.getType());
+ IntegerType *ITy = dyn_cast<IntegerType>(I.getType());
if (!ITy || ITy->getBitWidth() % 16 ||
// ByteMask only allows up to 32-byte values.
ITy->getBitWidth() > 32*8)
for (unsigned i = 1, e = ByteValues.size(); i != e; ++i)
if (ByteValues[i] != V)
return 0;
- const Type *Tys[] = { ITy };
Module *M = I.getParent()->getParent()->getParent();
- Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, Tys, 1);
+ Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, ITy);
return CallInst::Create(F, V);
}
Value *NewOr = Builder->CreateOr(Val, Val2);
return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
}
+
+ // (icmp slt A, 0) | (icmp slt B, 0) --> (icmp slt (A|B), 0)
+ if (LHSCC == ICmpInst::ICMP_SLT && LHSCst->isZero()) {
+ Value *NewOr = Builder->CreateOr(Val, Val2);
+ return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
+ }
+
+ // (icmp sgt A, -1) | (icmp sgt B, -1) --> (icmp sgt (A&B), -1)
+ if (LHSCC == ICmpInst::ICMP_SGT && LHSCst->isAllOnesValue()) {
+ Value *NewAnd = Builder->CreateAnd(Val, Val2);
+ return Builder->CreateICmp(LHSCC, NewAnd, LHSCst);
+ }
}
// (icmp ult (X + CA), C1) | (icmp eq X, C2) -> (icmp ule (X + CA), C1)
return BinaryOperator::CreateNot(And);
}
+ // Canonicalize xor to the RHS.
+ if (match(Op0, m_Xor(m_Value(), m_Value())))
+ std::swap(Op0, Op1);
+
+ // A | ( A ^ B) -> A | B
+ // A | (~A ^ B) -> A | ~B
+ if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
+ if (Op0 == A || Op0 == B)
+ return BinaryOperator::CreateOr(A, B);
+
+ if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
+ Value *Not = Builder->CreateNot(B, B->getName()+".not");
+ return BinaryOperator::CreateOr(Not, Op0);
+ }
+ if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
+ Value *Not = Builder->CreateNot(A, A->getName()+".not");
+ return BinaryOperator::CreateOr(Not, Op0);
+ }
+ }
+
+ // A | ~(A | B) -> A | ~B
+ // A | ~(A ^ B) -> A | ~B
+ if (match(Op1, m_Not(m_Value(A))))
+ if (BinaryOperator *B = dyn_cast<BinaryOperator>(A))
+ if ((Op0 == B->getOperand(0) || Op0 == B->getOperand(1)) &&
+ Op1->hasOneUse() && (B->getOpcode() == Instruction::Or ||
+ B->getOpcode() == Instruction::Xor)) {
+ Value *NotOp = Op0 == B->getOperand(0) ? B->getOperand(1) :
+ B->getOperand(0);
+ Value *Not = Builder->CreateNot(NotOp, NotOp->getName()+".not");
+ return BinaryOperator::CreateOr(Not, Op0);
+ }
+
if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
if (Value *Res = FoldOrOfICmps(LHS, RHS))
}
}
}
-
+
+ // or(sext(A), B) -> A ? -1 : B where A is an i1
+ // or(A, sext(B)) -> B ? -1 : A where B is an i1
+ if (match(Op0, m_SExt(m_Value(A))) && A->getType()->isIntegerTy(1))
+ return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op1);
+ if (match(Op1, m_SExt(m_Value(A))) && A->getType()->isIntegerTy(1))
+ return SelectInst::Create(A, ConstantInt::getSigned(I.getType(), -1), Op0);
+
// Note: If we've gotten to the point of visiting the outer OR, then the
// inner one couldn't be simplified. If it was a constant, then it won't
// be simplified by a later pass either, so we try swapping the inner/outer
projects / oota-llvm.git / blobdiff