//
//===----------------------------------------------------------------------===//
-#include "InstCombine.h"
+#include "InstCombineInternal.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Transforms/Utils/CmpInstAnalysis.h"
+#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
using namespace PatternMatch;
#define DEBUG_TYPE "instcombine"
-/// isFreeToInvert - Return true if the specified value is free to invert (apply
-/// ~ to). This happens in cases where the ~ can be eliminated.
-static inline bool isFreeToInvert(Value *V) {
- // ~(~(X)) -> X.
- if (BinaryOperator::isNot(V))
- return true;
-
- // Constants can be considered to be not'ed values.
- if (isa<ConstantInt>(V))
- return true;
-
- // Compares can be inverted if they have a single use.
- if (CmpInst *CI = dyn_cast<CmpInst>(V))
- return CI->hasOneUse();
-
- return false;
-}
-
static inline Value *dyn_castNotVal(Value *V) {
// If this is not(not(x)) don't return that this is a not: we want the two
// not's to be folded first.
if (BinaryOperator::isNot(V)) {
Value *Operand = BinaryOperator::getNotArgument(V);
- if (!isFreeToInvert(Operand))
+ if (!IsFreeToInvert(Operand, Operand->hasOneUse()))
return Operand;
}
return nullptr;
}
-/// getFCmpCode - Similar to getICmpCode but for FCmpInst. This encodes a fcmp
-/// predicate into a three bit mask. It also returns whether it is an ordered
-/// predicate by reference.
+/// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into
+/// a three bit mask. It also returns whether it is an ordered predicate by
+/// reference.
static unsigned getFCmpCode(FCmpInst::Predicate CC, bool &isOrdered) {
isOrdered = false;
switch (CC) {
}
}
-/// getNewICmpValue - This is the complement of getICmpCode, which turns an
-/// opcode and two operands into either a constant true or false, or a brand
-/// new ICmp instruction. The sign is passed in to determine which kind
-/// of predicate to use in the new icmp instruction.
+/// This is the complement of getICmpCode, which turns an opcode and two
+/// operands into either a constant true or false, or a brand new ICmp
+/// instruction. The sign is passed in to determine which kind of predicate to
+/// use in the new icmp instruction.
static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
InstCombiner::BuilderTy *Builder) {
ICmpInst::Predicate NewPred;
return Builder->CreateICmp(NewPred, LHS, RHS);
}
-/// getFCmpValue - This is the complement of getFCmpCode, which turns an
-/// opcode and two operands into either a FCmp instruction. isordered is passed
-/// in to determine which kind of predicate to use in the new fcmp instruction.
+/// This is the complement of getFCmpCode, which turns an opcode and two
+/// operands into either a FCmp instruction. isordered is passed in to determine
+/// which kind of predicate to use in the new fcmp instruction.
static Value *getFCmpValue(bool isordered, unsigned code,
Value *LHS, Value *RHS,
InstCombiner::BuilderTy *Builder) {
case 5: Pred = isordered ? FCmpInst::FCMP_ONE : FCmpInst::FCMP_UNE; break;
case 6: Pred = isordered ? FCmpInst::FCMP_OLE : FCmpInst::FCMP_ULE; break;
case 7:
- if (!isordered) return ConstantInt::getTrue(LHS->getContext());
+ if (!isordered)
+ return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1);
Pred = FCmpInst::FCMP_ORD; break;
}
return Builder->CreateFCmp(Pred, LHS, RHS);
}
-// OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where
-// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is
-// guaranteed to be a binary operator.
+/// \brief Transform BITWISE_OP(BSWAP(A),BSWAP(B)) to BSWAP(BITWISE_OP(A, B))
+/// \param I Binary operator to transform.
+/// \return Pointer to node that must replace the original binary operator, or
+/// null pointer if no transformation was made.
+Value *InstCombiner::SimplifyBSwap(BinaryOperator &I) {
+ IntegerType *ITy = dyn_cast<IntegerType>(I.getType());
+
+ // Can't do vectors.
+ if (I.getType()->isVectorTy()) return nullptr;
+
+ // Can only do bitwise ops.
+ unsigned Op = I.getOpcode();
+ if (Op != Instruction::And && Op != Instruction::Or &&
+ Op != Instruction::Xor)
+ return nullptr;
+
+ Value *OldLHS = I.getOperand(0);
+ Value *OldRHS = I.getOperand(1);
+ ConstantInt *ConstLHS = dyn_cast<ConstantInt>(OldLHS);
+ ConstantInt *ConstRHS = dyn_cast<ConstantInt>(OldRHS);
+ IntrinsicInst *IntrLHS = dyn_cast<IntrinsicInst>(OldLHS);
+ IntrinsicInst *IntrRHS = dyn_cast<IntrinsicInst>(OldRHS);
+ bool IsBswapLHS = (IntrLHS && IntrLHS->getIntrinsicID() == Intrinsic::bswap);
+ bool IsBswapRHS = (IntrRHS && IntrRHS->getIntrinsicID() == Intrinsic::bswap);
+
+ if (!IsBswapLHS && !IsBswapRHS)
+ return nullptr;
+
+ if (!IsBswapLHS && !ConstLHS)
+ return nullptr;
+
+ if (!IsBswapRHS && !ConstRHS)
+ return nullptr;
+
+ /// OP( BSWAP(x), BSWAP(y) ) -> BSWAP( OP(x, y) )
+ /// OP( BSWAP(x), CONSTANT ) -> BSWAP( OP(x, BSWAP(CONSTANT) ) )
+ Value *NewLHS = IsBswapLHS ? IntrLHS->getOperand(0) :
+ Builder->getInt(ConstLHS->getValue().byteSwap());
+
+ Value *NewRHS = IsBswapRHS ? IntrRHS->getOperand(0) :
+ Builder->getInt(ConstRHS->getValue().byteSwap());
+
+ Value *BinOp = nullptr;
+ if (Op == Instruction::And)
+ BinOp = Builder->CreateAnd(NewLHS, NewRHS);
+ else if (Op == Instruction::Or)
+ BinOp = Builder->CreateOr(NewLHS, NewRHS);
+ else //if (Op == Instruction::Xor)
+ BinOp = Builder->CreateXor(NewLHS, NewRHS);
+
+ Function *F = Intrinsic::getDeclaration(I.getModule(), Intrinsic::bswap, ITy);
+ return Builder->CreateCall(F, BinOp);
+}
+
+/// This handles expressions of the form ((val OP C1) & C2). Where
+/// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is
+/// guaranteed to be a binary operator.
Instruction *InstCombiner::OptAndOp(Instruction *Op,
ConstantInt *OpRHS,
ConstantInt *AndRHS,
return Builder->CreateICmpUGT(Add, LowerBound);
}
-// isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
-// any number of 0s on either side. The 1s are allowed to wrap from LSB to
-// MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is
-// not, since all 1s are not contiguous.
+/// Returns true iff Val consists of one contiguous run of 1s with any number
+/// of 0s on either side. The 1s are allowed to wrap from LSB to MSB,
+/// so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is
+/// not, since all 1s are not contiguous.
static bool isRunOfOnes(ConstantInt *Val, uint32_t &MB, uint32_t &ME) {
const APInt& V = Val->getValue();
uint32_t BitWidth = Val->getType()->getBitWidth();
return true;
}
-/// FoldLogicalPlusAnd - This is part of an expression (LHS +/- RHS) & Mask,
-/// where isSub determines whether the operator is a sub. If we can fold one of
-/// the following xforms:
+/// This is part of an expression (LHS +/- RHS) & Mask, where isSub determines
+/// whether the operator is a sub. If we can fold one of the following xforms:
///
/// ((A & N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == Mask
/// ((A | N) +/- B) & Mask -> (A +/- B) & Mask iff N&Mask == 0
FoldMskICmp_BMask_NotMixed = 512
};
-/// return the set of pattern classes (from MaskedICmpType)
-/// that (icmp SCC (A & B), C) satisfies
+/// Return the set of pattern classes (from MaskedICmpType)
+/// that (icmp SCC (A & B), C) satisfies.
static unsigned getTypeOfMaskedICmp(Value* A, Value* B, Value* C,
ICmpInst::Predicate SCC)
{
return NewMask;
}
-/// decomposeBitTestICmp - Decompose an icmp into the form ((X & Y) pred Z)
-/// if possible. The returned predicate is either == or !=. Returns false if
+/// Decompose an icmp into the form ((X & Y) pred Z) if possible.
+/// The returned predicate is either == or !=. Returns false if
/// decomposition fails.
static bool decomposeBitTestICmp(const ICmpInst *I, ICmpInst::Predicate &Pred,
Value *&X, Value *&Y, Value *&Z) {
return true;
}
-/// foldLogOpOfMaskedICmpsHelper:
-/// handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
-/// return the set of pattern classes (from MaskedICmpType)
-/// that both LHS and RHS satisfy
+/// 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 foldLogOpOfMaskedICmpsHelper(Value*& A,
Value*& B, Value*& C,
Value*& D, Value*& E,
unsigned right_type = getTypeOfMaskedICmp(A, D, E, RHSCC);
return left_type & right_type;
}
-/// foldLogOpOfMaskedICmps:
-/// try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
-/// into a single (icmp(A & X) ==/!= Y)
+
+/// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
+/// into a single (icmp(A & X) ==/!= Y).
static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
llvm::InstCombiner::BuilderTy *Builder) {
Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
return nullptr;
}
-/// FoldAndOfICmps - Fold (icmp)&(icmp) if possible.
+/// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
+/// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
+/// If \p Inverted is true then the check is for the inverted range, e.g.
+/// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
+Value *InstCombiner::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1,
+ bool Inverted) {
+ // Check the lower range comparison, e.g. x >= 0
+ // InstCombine already ensured that if there is a constant it's on the RHS.
+ ConstantInt *RangeStart = dyn_cast<ConstantInt>(Cmp0->getOperand(1));
+ if (!RangeStart)
+ return nullptr;
+
+ ICmpInst::Predicate Pred0 = (Inverted ? Cmp0->getInversePredicate() :
+ Cmp0->getPredicate());
+
+ // Accept x > -1 or x >= 0 (after potentially inverting the predicate).
+ if (!((Pred0 == ICmpInst::ICMP_SGT && RangeStart->isMinusOne()) ||
+ (Pred0 == ICmpInst::ICMP_SGE && RangeStart->isZero())))
+ return nullptr;
+
+ ICmpInst::Predicate Pred1 = (Inverted ? Cmp1->getInversePredicate() :
+ Cmp1->getPredicate());
+
+ Value *Input = Cmp0->getOperand(0);
+ Value *RangeEnd;
+ if (Cmp1->getOperand(0) == Input) {
+ // For the upper range compare we have: icmp x, n
+ RangeEnd = Cmp1->getOperand(1);
+ } else if (Cmp1->getOperand(1) == Input) {
+ // For the upper range compare we have: icmp n, x
+ RangeEnd = Cmp1->getOperand(0);
+ Pred1 = ICmpInst::getSwappedPredicate(Pred1);
+ } else {
+ return nullptr;
+ }
+
+ // Check the upper range comparison, e.g. x < n
+ ICmpInst::Predicate NewPred;
+ switch (Pred1) {
+ case ICmpInst::ICMP_SLT: NewPred = ICmpInst::ICMP_ULT; break;
+ case ICmpInst::ICMP_SLE: NewPred = ICmpInst::ICMP_ULE; break;
+ default: return nullptr;
+ }
+
+ // This simplification is only valid if the upper range is not negative.
+ bool IsNegative, IsNotNegative;
+ ComputeSignBit(RangeEnd, IsNotNegative, IsNegative, /*Depth=*/0, Cmp1);
+ if (!IsNotNegative)
+ return nullptr;
+
+ if (Inverted)
+ NewPred = ICmpInst::getInversePredicate(NewPred);
+
+ return Builder->CreateICmp(NewPred, Input, RangeEnd);
+}
+
+/// Fold (icmp)&(icmp) if possible.
Value *InstCombiner::FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate();
if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
return V;
+ // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
+ if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
+ return V;
+
+ // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
+ if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
+ return V;
+
// This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0);
ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1));
// 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::makeAllowedICmpRegion(LHSCC, LHSCst->getValue());
ConstantRange RHSRange =
- ConstantRange::makeICmpRegion(RHSCC, RHSCst->getValue());
+ ConstantRange::makeAllowedICmpRegion(RHSCC, RHSCst->getValue());
if (LHSRange.intersectWith(RHSRange).isEmptySet())
return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
return nullptr;
}
-/// FoldAndOfFCmps - Optimize (fcmp)&(fcmp). NOTE: Unlike the rest of
-/// instcombine, this returns a Value which should already be inserted into the
-/// function.
+/// Optimize (fcmp)&(fcmp). NOTE: Unlike the rest of instcombine, this returns
+/// a Value which should already be inserted into the function.
Value *InstCombiner::FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
if (LHS->getPredicate() == FCmpInst::FCMP_ORD &&
RHS->getPredicate() == FCmpInst::FCMP_ORD) {
return nullptr;
}
+/// Match De Morgan's Laws:
+/// (~A & ~B) == (~(A | B))
+/// (~A | ~B) == (~(A & B))
+static Instruction *matchDeMorgansLaws(BinaryOperator &I,
+ InstCombiner::BuilderTy *Builder) {
+ auto Opcode = I.getOpcode();
+ assert((Opcode == Instruction::And || Opcode == Instruction::Or) &&
+ "Trying to match De Morgan's Laws with something other than and/or");
+ // Flip the logic operation.
+ if (Opcode == Instruction::And)
+ Opcode = Instruction::Or;
+ else
+ Opcode = Instruction::And;
+
+ Value *Op0 = I.getOperand(0);
+ Value *Op1 = I.getOperand(1);
+ // TODO: Use pattern matchers instead of dyn_cast.
+ if (Value *Op0NotVal = dyn_castNotVal(Op0))
+ if (Value *Op1NotVal = dyn_castNotVal(Op1))
+ if (Op0->hasOneUse() && Op1->hasOneUse()) {
+ Value *LogicOp = Builder->CreateBinOp(Opcode, Op0NotVal, Op1NotVal,
+ I.getName() + ".demorgan");
+ return BinaryOperator::CreateNot(LogicOp);
+ }
+
+ // De Morgan's Law in disguise:
+ // (zext(bool A) ^ 1) & (zext(bool B) ^ 1) -> zext(~(A | B))
+ // (zext(bool A) ^ 1) | (zext(bool B) ^ 1) -> zext(~(A & B))
+ Value *A = nullptr;
+ Value *B = nullptr;
+ ConstantInt *C1 = nullptr;
+ if (match(Op0, m_OneUse(m_Xor(m_ZExt(m_Value(A)), m_ConstantInt(C1)))) &&
+ match(Op1, m_OneUse(m_Xor(m_ZExt(m_Value(B)), m_Specific(C1))))) {
+ // TODO: This check could be loosened to handle different type sizes.
+ // Alternatively, we could fix the definition of m_Not to recognize a not
+ // operation hidden by a zext?
+ if (A->getType()->isIntegerTy(1) && B->getType()->isIntegerTy(1) &&
+ C1->isOne()) {
+ Value *LogicOp = Builder->CreateBinOp(Opcode, A, B,
+ I.getName() + ".demorgan");
+ Value *Not = Builder->CreateNot(LogicOp);
+ return CastInst::CreateZExtOrBitCast(Not, I.getType());
+ }
+ }
+
+ return nullptr;
+}
+
Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
bool Changed = SimplifyAssociativeOrCommutative(I);
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (Value *V = SimplifyVectorOp(I))
return ReplaceInstUsesWith(I, V);
- if (Value *V = SimplifyAndInst(Op0, Op1, DL, TLI, DT, AT))
+ if (Value *V = SimplifyAndInst(Op0, Op1, DL, TLI, DT, AC))
return ReplaceInstUsesWith(I, V);
// (A|B)&(A|C) -> A|(B&C) etc
if (SimplifyDemandedInstructionBits(I))
return &I;
+ if (Value *V = SimplifyBSwap(I))
+ return ReplaceInstUsesWith(I, V);
+
if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(Op1)) {
const APInt &AndRHSMask = AndRHS->getValue();
if (Value *V = FoldLogicalPlusAnd(Op0LHS, Op0RHS, AndRHS, true, I))
return BinaryOperator::CreateAnd(V, AndRHS);
+ // -x & 1 -> x & 1
+ if (AndRHSMask == 1 && match(Op0LHS, m_Zero()))
+ return BinaryOperator::CreateAnd(Op0RHS, AndRHS);
+
// (A - N) & AndRHS -> -N & AndRHS iff A&AndRHS==0 and AndRHS
// has 1's for all bits that the subtraction with A might affect.
if (Op0I->hasOneUse() && !match(Op0LHS, m_Zero())) {
return NV;
}
-
- // (~A & ~B) == (~(A | B)) - De Morgan's Law
- if (Value *Op0NotVal = dyn_castNotVal(Op0))
- if (Value *Op1NotVal = dyn_castNotVal(Op1))
- if (Op0->hasOneUse() && Op1->hasOneUse()) {
- Value *Or = Builder->CreateOr(Op0NotVal, Op1NotVal,
- I.getName()+".demorgan");
- return BinaryOperator::CreateNot(Or);
- }
+ if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
+ return DeMorgan;
{
Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
return ReplaceInstUsesWith(I, Res);
- // fold (and (cast A), (cast B)) -> (cast (and A, B))
- if (CastInst *Op0C = dyn_cast<CastInst>(Op0))
+ if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) {
+ Value *Op0COp = Op0C->getOperand(0);
+ Type *SrcTy = Op0COp->getType();
+ // fold (and (cast A), (cast B)) -> (cast (and A, B))
if (CastInst *Op1C = dyn_cast<CastInst>(Op1)) {
- Type *SrcTy = Op0C->getOperand(0)->getType();
if (Op0C->getOpcode() == Op1C->getOpcode() && // same cast kind ?
SrcTy == Op1C->getOperand(0)->getType() &&
SrcTy->isIntOrIntVectorTy()) {
- Value *Op0COp = Op0C->getOperand(0), *Op1COp = Op1C->getOperand(0);
+ Value *Op1COp = Op1C->getOperand(0);
// Only do this if the casts both really cause code to be generated.
if (ShouldOptimizeCast(Op0C->getOpcode(), Op0COp, I.getType()) &&
}
}
+ // If we are masking off the sign bit of a floating-point value, convert
+ // this to the canonical fabs intrinsic call and cast back to integer.
+ // The backend should know how to optimize fabs().
+ // TODO: This transform should also apply to vectors.
+ ConstantInt *CI;
+ if (isa<BitCastInst>(Op0C) && SrcTy->isFloatingPointTy() &&
+ match(Op1, m_ConstantInt(CI)) && CI->isMaxValue(true)) {
+ Module *M = I.getModule();
+ Function *Fabs = Intrinsic::getDeclaration(M, Intrinsic::fabs, SrcTy);
+ Value *Call = Builder->CreateCall(Fabs, Op0COp, "fabs");
+ return CastInst::CreateBitOrPointerCast(Call, I.getType());
+ }
+ }
+
{
Value *X = nullptr;
bool OpsSwapped = false;
return Changed ? &I : nullptr;
}
-/// CollectBSwapParts - Analyze the specified subexpression and see if it is
-/// capable of providing pieces of a bswap. The subexpression provides pieces
-/// of a bswap if it is proven that each of the non-zero bytes in the output of
-/// the expression came from the corresponding "byte swapped" byte in some other
-/// value. For example, if the current subexpression is "(shl i32 %X, 24)" then
-/// we know that the expression deposits the low byte of %X into the high byte
-/// of the bswap result and that all other bytes are zero. This expression is
-/// accepted, the high byte of ByteValues is set to X to indicate a correct
-/// match.
-///
-/// This function returns true if the match was unsuccessful and false if so.
-/// On entry to the function the "OverallLeftShift" is a signed integer value
-/// indicating the number of bytes that the subexpression is later shifted. For
-/// example, if the expression is later right shifted by 16 bits, the
-/// OverallLeftShift value would be -2 on entry. This is used to specify which
-/// byte of ByteValues is actually being set.
-///
-/// Similarly, ByteMask is a bitmask where a bit is clear if its corresponding
-/// byte is masked to zero by a user. For example, in (X & 255), X will be
-/// processed with a bytemask of 1. Because bytemask is 32-bits, this limits
-/// this function to working on up to 32-byte (256 bit) values. ByteMask is
-/// always in the local (OverallLeftShift) coordinate space.
-///
-static bool CollectBSwapParts(Value *V, int OverallLeftShift, uint32_t ByteMask,
- SmallVectorImpl<Value *> &ByteValues) {
- if (Instruction *I = dyn_cast<Instruction>(V)) {
- // If this is an or instruction, it may be an inner node of the bswap.
- if (I->getOpcode() == Instruction::Or) {
- return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask,
- ByteValues) ||
- CollectBSwapParts(I->getOperand(1), OverallLeftShift, ByteMask,
- ByteValues);
- }
-
- // If this is a logical shift by a constant multiple of 8, recurse with
- // OverallLeftShift and ByteMask adjusted.
- if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
- unsigned ShAmt =
- cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
- // Ensure the shift amount is defined and of a byte value.
- if ((ShAmt & 7) || (ShAmt > 8*ByteValues.size()))
- return true;
-
- unsigned ByteShift = ShAmt >> 3;
- if (I->getOpcode() == Instruction::Shl) {
- // X << 2 -> collect(X, +2)
- OverallLeftShift += ByteShift;
- ByteMask >>= ByteShift;
- } else {
- // X >>u 2 -> collect(X, -2)
- OverallLeftShift -= ByteShift;
- ByteMask <<= ByteShift;
- ByteMask &= (~0U >> (32-ByteValues.size()));
- }
-
- if (OverallLeftShift >= (int)ByteValues.size()) return true;
- if (OverallLeftShift <= -(int)ByteValues.size()) return true;
-
- return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask,
- ByteValues);
- }
-
- // If this is a logical 'and' with a mask that clears bytes, clear the
- // corresponding bytes in ByteMask.
- if (I->getOpcode() == Instruction::And &&
- isa<ConstantInt>(I->getOperand(1))) {
- // Scan every byte of the and mask, seeing if the byte is either 0 or 255.
- unsigned NumBytes = ByteValues.size();
- APInt Byte(I->getType()->getPrimitiveSizeInBits(), 255);
- const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
-
- for (unsigned i = 0; i != NumBytes; ++i, Byte <<= 8) {
- // If this byte is masked out by a later operation, we don't care what
- // the and mask is.
- if ((ByteMask & (1 << i)) == 0)
- continue;
-
- // If the AndMask is all zeros for this byte, clear the bit.
- APInt MaskB = AndMask & Byte;
- if (MaskB == 0) {
- ByteMask &= ~(1U << i);
- continue;
- }
-
- // If the AndMask is not all ones for this byte, it's not a bytezap.
- if (MaskB != Byte)
- return true;
-
- // Otherwise, this byte is kept.
- }
-
- return CollectBSwapParts(I->getOperand(0), OverallLeftShift, ByteMask,
- ByteValues);
- }
- }
-
- // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be
- // the input value to the bswap. Some observations: 1) if more than one byte
- // is demanded from this input, then it could not be successfully assembled
- // into a byteswap. At least one of the two bytes would not be aligned with
- // their ultimate destination.
- if (!isPowerOf2_32(ByteMask)) return true;
- unsigned InputByteNo = countTrailingZeros(ByteMask);
-
- // 2) The input and ultimate destinations must line up: if byte 3 of an i32
- // is demanded, it needs to go into byte 0 of the result. This means that the
- // byte needs to be shifted until it lands in the right byte bucket. The
- // shift amount depends on the position: if the byte is coming from the high
- // part of the value (e.g. byte 3) then it must be shifted right. If from the
- // low part, it must be shifted left.
- unsigned DestByteNo = InputByteNo + OverallLeftShift;
- if (ByteValues.size()-1-DestByteNo != InputByteNo)
- return true;
-
- // If the destination byte value is already defined, the values are or'd
- // together, which isn't a bswap (unless it's an or of the same bits).
- if (ByteValues[DestByteNo] && ByteValues[DestByteNo] != V)
- return true;
- ByteValues[DestByteNo] = V;
- return false;
-}
-
-/// 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) {
- IntegerType *ITy = dyn_cast<IntegerType>(I.getType());
- if (!ITy || ITy->getBitWidth() % 16 ||
- // ByteMask only allows up to 32-byte values.
- ITy->getBitWidth() > 32*8)
- return nullptr; // Can only bswap pairs of bytes. Can't do vectors.
-
- /// ByteValues - For each byte of the result, we keep track of which value
- /// defines each byte.
- SmallVector<Value*, 8> ByteValues;
- ByteValues.resize(ITy->getBitWidth()/8);
-
- // Try to find all the pieces corresponding to the bswap.
- uint32_t ByteMask = ~0U >> (32-ByteValues.size());
- if (CollectBSwapParts(&I, 0, ByteMask, ByteValues))
+/// Given an OR instruction, check to see if this is a bswap or bitreverse
+/// idiom. If so, insert the new intrinsic and return it.
+Instruction *InstCombiner::MatchBSwapOrBitReverse(BinaryOperator &I) {
+ SmallVector<Instruction*, 4> Insts;
+ if (!recognizeBitReverseOrBSwapIdiom(&I, true, false, Insts))
return nullptr;
+ Instruction *LastInst = Insts.pop_back_val();
+ LastInst->removeFromParent();
- // Check to see if all of the bytes come from the same value.
- Value *V = ByteValues[0];
- if (!V) return nullptr; // Didn't find a byte? Must be zero.
-
- // Check to make sure that all of the bytes come from the same value.
- for (unsigned i = 1, e = ByteValues.size(); i != e; ++i)
- if (ByteValues[i] != V)
- return nullptr;
- Module *M = I.getParent()->getParent()->getParent();
- Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, ITy);
- return CallInst::Create(F, V);
+ for (auto *Inst : Insts)
+ Worklist.Add(Inst);
+ return LastInst;
}
-/// MatchSelectFromAndOr - We have an expression of the form (A&C)|(B&D). Check
-/// If A is (cond?-1:0) and either B or D is ~(cond?-1,0) or (cond?0,-1), then
-/// we can simplify this expression to "cond ? C : D or B".
+/// We have an expression of the form (A&C)|(B&D). Check if A is (cond?-1:0)
+/// and either B or D is ~(cond?-1,0) or (cond?0,-1), then we can simplify this
+/// expression to "cond ? C : D or B".
static Instruction *MatchSelectFromAndOr(Value *A, Value *B,
Value *C, Value *D) {
// If A is not a select of -1/0, this cannot match.
return nullptr;
}
-/// FoldOrOfICmps - Fold (icmp)|(icmp) if possible.
+/// Fold (icmp)|(icmp) if possible.
Value *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
Instruction *CxtI) {
ICmpInst::Predicate LHSCC = LHS->getPredicate(), RHSCC = RHS->getPredicate();
Value *Mask = nullptr;
Value *Masked = nullptr;
if (LAnd->getOperand(0) == RAnd->getOperand(0) &&
- isKnownToBeAPowerOfTwo(LAnd->getOperand(1), false, 0, AT, CxtI, DT) &&
- isKnownToBeAPowerOfTwo(RAnd->getOperand(1), false, 0, AT, CxtI, DT)) {
+ isKnownToBeAPowerOfTwo(LAnd->getOperand(1), DL, false, 0, AC, CxtI,
+ DT) &&
+ isKnownToBeAPowerOfTwo(RAnd->getOperand(1), DL, false, 0, AC, CxtI,
+ DT)) {
Mask = Builder->CreateOr(LAnd->getOperand(1), RAnd->getOperand(1));
Masked = Builder->CreateAnd(LAnd->getOperand(0), Mask);
} else if (LAnd->getOperand(1) == RAnd->getOperand(1) &&
- isKnownToBeAPowerOfTwo(LAnd->getOperand(0),
- false, 0, AT, CxtI, DT) &&
- isKnownToBeAPowerOfTwo(RAnd->getOperand(0),
- false, 0, AT, CxtI, DT)) {
+ isKnownToBeAPowerOfTwo(LAnd->getOperand(0), DL, false, 0, AC,
+ CxtI, DT) &&
+ isKnownToBeAPowerOfTwo(RAnd->getOperand(0), DL, false, 0, AC,
+ CxtI, DT)) {
Mask = Builder->CreateOr(LAnd->getOperand(0), RAnd->getOperand(0));
Masked = Builder->CreateAnd(LAnd->getOperand(1), Mask);
}
Builder->CreateAdd(B, ConstantInt::getSigned(B->getType(), -1)), A);
}
+ // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
+ if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
+ return V;
+
+ // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
+ if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
+ return V;
+
// This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
if (!LHSCst || !RHSCst) return nullptr;
case ICmpInst::ICMP_EQ:
if (LHS->getOperand(0) == RHS->getOperand(0)) {
// if LHSCst and RHSCst differ only by one bit:
- // (A == C1 || A == C2) -> (A & ~(C1 ^ C2)) == C1
+ // (A == C1 || A == C2) -> (A | (C1 ^ C2)) == C2
assert(LHSCst->getValue().ule(LHSCst->getValue()));
APInt Xor = LHSCst->getValue() ^ RHSCst->getValue();
if (Xor.isPowerOf2()) {
- Value *NegCst = Builder->getInt(~Xor);
- Value *And = Builder->CreateAnd(LHS->getOperand(0), NegCst);
- return Builder->CreateICmp(ICmpInst::ICMP_EQ, And, LHSCst);
+ Value *Cst = Builder->getInt(Xor);
+ Value *Or = Builder->CreateOr(LHS->getOperand(0), Cst);
+ return Builder->CreateICmp(ICmpInst::ICMP_EQ, Or, RHSCst);
}
}
return nullptr;
}
-/// FoldOrOfFCmps - Optimize (fcmp)|(fcmp). NOTE: Unlike the rest of
-/// instcombine, this returns a Value which should already be inserted into the
-/// function.
+/// Optimize (fcmp)|(fcmp). NOTE: Unlike the rest of instcombine, this returns
+/// a Value which should already be inserted into the function.
Value *InstCombiner::FoldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
if (LHS->getPredicate() == FCmpInst::FCMP_UNO &&
RHS->getPredicate() == FCmpInst::FCMP_UNO &&
return nullptr;
}
-/// FoldOrWithConstants - This helper function folds:
+/// This helper function folds:
///
/// ((A | B) & C1) | (B & C2)
///
if (Value *V = SimplifyVectorOp(I))
return ReplaceInstUsesWith(I, V);
- if (Value *V = SimplifyOrInst(Op0, Op1, DL, TLI, DT, AT))
+ if (Value *V = SimplifyOrInst(Op0, Op1, DL, TLI, DT, AC))
return ReplaceInstUsesWith(I, V);
// (A&B)|(A&C) -> A&(B|C) etc
if (SimplifyDemandedInstructionBits(I))
return &I;
+ if (Value *V = SimplifyBSwap(I))
+ return ReplaceInstUsesWith(I, V);
+
if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
ConstantInt *C1 = nullptr; Value *X = nullptr;
// (X & C1) | C2 --> (X | C2) & (C1|C2)
ConstantInt *C1 = nullptr, *C2 = nullptr;
// (A | B) | C and A | (B | C) -> bswap if possible.
+ bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
+ match(Op1, m_Or(m_Value(), m_Value()));
// (A >> B) | (C << D) and (A << B) | (B >> C) -> bswap if possible.
- if (match(Op0, m_Or(m_Value(), m_Value())) ||
- match(Op1, m_Or(m_Value(), m_Value())) ||
- (match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
- match(Op1, m_LogicalShift(m_Value(), m_Value())))) {
- if (Instruction *BSwap = MatchBSwap(I))
+ bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
+ match(Op1, m_LogicalShift(m_Value(), m_Value()));
+ // (A & B) | (C & D) -> bswap if possible.
+ bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
+ match(Op1, m_And(m_Value(), m_Value()));
+
+ if (OrOfOrs || OrOfShifts || OrOfAnds)
+ if (Instruction *BSwap = MatchBSwapOrBitReverse(I))
return BSwap;
- }
// (X^C)|Y -> (X|Y)^C iff Y&C == 0
if (Op0->hasOneUse() &&
if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
return BinaryOperator::CreateOr(Op1, Builder->CreateAnd(A, C));
- // (~A | ~B) == (~(A & B)) - De Morgan's Law
- if (Value *Op0NotVal = dyn_castNotVal(Op0))
- if (Value *Op1NotVal = dyn_castNotVal(Op1))
- if (Op0->hasOneUse() && Op1->hasOneUse()) {
- Value *And = Builder->CreateAnd(Op0NotVal, Op1NotVal,
- I.getName()+".demorgan");
- return BinaryOperator::CreateNot(And);
- }
+ if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
+ return DeMorgan;
// Canonicalize xor to the RHS.
bool SwappedForXor = false;
if (Value *V = SimplifyVectorOp(I))
return ReplaceInstUsesWith(I, V);
- if (Value *V = SimplifyXorInst(Op0, Op1, DL, TLI, DT, AT))
+ if (Value *V = SimplifyXorInst(Op0, Op1, DL, TLI, DT, AC))
return ReplaceInstUsesWith(I, V);
// (A&B)^(A&C) -> A&(B^C) etc
if (SimplifyDemandedInstructionBits(I))
return &I;
+ if (Value *V = SimplifyBSwap(I))
+ return ReplaceInstUsesWith(I, V);
+
// Is this a ~ operation?
if (Value *NotOp = dyn_castNotVal(&I)) {
if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(NotOp)) {
// ~(X & Y) --> (~X | ~Y) - De Morgan's Law
// ~(X | Y) === (~X & ~Y) - De Morgan's Law
- if (isFreeToInvert(Op0I->getOperand(0)) &&
- isFreeToInvert(Op0I->getOperand(1))) {
+ if (IsFreeToInvert(Op0I->getOperand(0),
+ Op0I->getOperand(0)->hasOneUse()) &&
+ IsFreeToInvert(Op0I->getOperand(1),
+ Op0I->getOperand(1)->hasOneUse())) {
Value *NotX =
Builder->CreateNot(Op0I->getOperand(0), "notlhs");
Value *NotY =
}
}
-
- if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
- if (RHS->isOne() && Op0->hasOneUse())
+ if (Constant *RHS = dyn_cast<Constant>(Op1)) {
+ if (RHS->isAllOnesValue() && Op0->hasOneUse())
// xor (cmp A, B), true = not (cmp A, B) = !cmp A, B
if (CmpInst *CI = dyn_cast<CmpInst>(Op0))
return CmpInst::Create(CI->getOpcode(),
CI->getInversePredicate(),
CI->getOperand(0), CI->getOperand(1));
+ }
+ if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
// fold (xor(zext(cmp)), 1) and (xor(sext(cmp)), -1) to ext(!cmp).
if (CastInst *Op0C = dyn_cast<CastInst>(Op0)) {
if (CmpInst *CI = dyn_cast<CmpInst>(Op0C->getOperand(0))) {