#include "InstCombine.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/PatternMatch.h"
#include "llvm/Transforms/Utils/CmpInstAnalysis.h"

Include dependency graph for InstCombineAndOrXor.cpp:

Enumerations
enum	MaskedICmpType { FoldMskICmp_AMask_AllOnes = 1, FoldMskICmp_AMask_NotAllOnes = 2, FoldMskICmp_BMask_AllOnes = 4, FoldMskICmp_BMask_NotAllOnes = 8, FoldMskICmp_Mask_AllZeroes = 16, FoldMskICmp_Mask_NotAllZeroes = 32, FoldMskICmp_AMask_Mixed = 64, FoldMskICmp_AMask_NotMixed = 128, FoldMskICmp_BMask_Mixed = 256, FoldMskICmp_BMask_NotMixed = 512 }

Functions
static Constant *	AddOne (ConstantInt *C)
	AddOne - Add one to a ConstantInt. More...

static Constant *	SubOne (ConstantInt *C)
	SubOne - Subtract one from a ConstantInt. More...

static bool	isFreeToInvert (Value *V)

static Value *	dyn_castNotVal (Value *V)

static unsigned	getFCmpCode (FCmpInst::Predicate CC, bool &isOrdered)

static Value *	getNewICmpValue (bool Sign, unsigned Code, Value LHS, Value RHS, InstCombiner::BuilderTy *Builder)

static Value *	getFCmpValue (bool isordered, unsigned code, Value LHS, Value RHS, InstCombiner::BuilderTy *Builder)

static bool	isRunOfOnes (ConstantInt *Val, uint32_t &MB, uint32_t &ME)

static unsigned	getTypeOfMaskedICmp (Value A, Value B, Value *C, ICmpInst::Predicate SCC)

static unsigned	conjugateICmpMask (unsigned Mask)

static bool	decomposeBitTestICmp (const ICmpInst I, ICmpInst::Predicate &Pred, Value &X, Value &Y, Value &Z)

static unsigned	foldLogOpOfMaskedICmpsHelper (Value &A, Value &B, Value &C, Value &D, Value &E, ICmpInst LHS, ICmpInst *RHS, ICmpInst::Predicate &LHSCC, ICmpInst::Predicate &RHSCC)

static Value *	foldLogOpOfMaskedICmps (ICmpInst LHS, ICmpInst RHS, bool IsAnd, llvm::InstCombiner::BuilderTy *Builder)

static bool	CollectBSwapParts (Value V, int OverallLeftShift, uint32_t ByteMask, SmallVectorImpl< Value > &ByteValues)

static Instruction *	MatchSelectFromAndOr (Value A, Value B, Value C, Value D)

static bool	IsOneHotValue (Value *V)

Enumeration Type Documentation

enum MaskedICmpType

enum for classifying (icmp eq (A & B), C) and (icmp ne (A & B), C) One of A and B is considered the mask, the other the value. This is described as the "AMask" or "BMask" part of the enum. If the enum contains only "Mask", then both A and B can be considered masks. If A is the mask, then it was proven, that (A & C) == C. This is trivial if C == A, or C == 0. If both A and C are constants, this proof is also easy. For the following explanations we assume that A is the mask. The part "AllOnes" declares, that the comparison is true only if (A & B) == A, or all bits of A are set in B. Example: (icmp eq (A & 3), 3) -> FoldMskICmp_AMask_AllOnes The part "AllZeroes" declares, that the comparison is true only if (A & B) == 0, or all bits of A are cleared in B. Example: (icmp eq (A & 3), 0) -> FoldMskICmp_Mask_AllZeroes The part "Mixed" declares, that (A & B) == C and C might or might not contain any number of one bits and zero bits. Example: (icmp eq (A & 3), 1) -> FoldMskICmp_AMask_Mixed The Part "Not" means, that in above descriptions "==" should be replaced by "!=". Example: (icmp ne (A & 3), 3) -> FoldMskICmp_AMask_NotAllOnes If the mask A contains a single bit, then the following is equivalent: (icmp eq (A & B), A) equals (icmp ne (A & B), 0) (icmp ne (A & B), A) equals (icmp eq (A & B), 0)

Enumerator
FoldMskICmp_AMask_AllOnes
FoldMskICmp_AMask_NotAllOnes
FoldMskICmp_BMask_AllOnes
FoldMskICmp_BMask_NotAllOnes
FoldMskICmp_Mask_AllZeroes
FoldMskICmp_Mask_NotAllZeroes
FoldMskICmp_AMask_Mixed
FoldMskICmp_AMask_NotMixed
FoldMskICmp_BMask_Mixed
FoldMskICmp_BMask_NotMixed

Definition at line 409 of file InstCombineAndOrXor.cpp.

Function Documentation

static Constant* AddOne ( ConstantInt * C )

static

AddOne - Add one to a ConstantInt.

Definition at line 25 of file InstCombineAndOrXor.cpp.

References llvm::ConstantInt::get(), llvm::Value::getContext(), and llvm::ConstantInt::getValue().

Referenced by llvm::InstCombiner::FoldAndOfICmps(), and llvm::InstCombiner::FoldOrOfICmps().

static bool CollectBSwapParts	(	Value *	V,
		int	OverallLeftShift,
		uint32_t	ByteMask,
		SmallVectorImpl< Value * > &	ByteValues
	)

static

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.

Definition at line 1390 of file InstCombineAndOrXor.cpp.

References llvm::APIntOps::And(), llvm::countTrailingZeros(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Value::getType(), llvm::Instruction::isLogicalShift(), llvm::isPowerOf2_32(), llvm::APIntOps::Or(), and llvm::SmallVectorTemplateCommon< T >::size().

static unsigned conjugateICmpMask ( unsigned Mask )

static

Convert an analysis of a masked ICmp into its equivalent if all boolean operations had the opposite sense. Since each "NotXXX" flag (recording !=) is adjacent to the corresponding normal flag (recording ==), this just involves swapping those bits over.

Definition at line 495 of file InstCombineAndOrXor.cpp.

References FoldMskICmp_AMask_AllOnes, FoldMskICmp_AMask_Mixed, FoldMskICmp_AMask_NotAllOnes, FoldMskICmp_AMask_NotMixed, FoldMskICmp_BMask_AllOnes, FoldMskICmp_BMask_Mixed, FoldMskICmp_BMask_NotAllOnes, FoldMskICmp_BMask_NotMixed, FoldMskICmp_Mask_AllZeroes, and FoldMskICmp_Mask_NotAllZeroes.

Referenced by foldLogOpOfMaskedICmps().

static bool decomposeBitTestICmp	(	const ICmpInst *	I,
		ICmpInst::Predicate &	Pred,
		Value *&	X,
		Value *&	Y,
		Value *&	Z
	)

static

decomposeBitTestICmp - Decompose an icmp into the form ((X & Y) pred Z) if possible. The returned predicate is either == or !=. Returns false if decomposition fails.

Definition at line 514 of file InstCombineAndOrXor.cpp.

References llvm::CallingConv::C, llvm::ConstantInt::get(), llvm::Value::getContext(), llvm::Constant::getNullValue(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::APInt::getSignBit(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, and llvm::Constant::isAllOnesValue().

Referenced by foldLogOpOfMaskedICmpsHelper().

static Value* dyn_castNotVal ( Value * V )

inlinestatic

Definition at line 51 of file InstCombineAndOrXor.cpp.

References llvm::CallingConv::C, llvm::ConstantInt::get(), llvm::BinaryOperator::getNotArgument(), isFreeToInvert(), and llvm::BinaryOperator::isNot().

Referenced by llvm::InstCombiner::visitAnd(), llvm::InstCombiner::visitOr(), and llvm::InstCombiner::visitXor().

static Value* foldLogOpOfMaskedICmps	(	ICmpInst *	LHS,
		ICmpInst *	RHS,
		bool	IsAnd,
		llvm::InstCombiner::BuilderTy *	Builder
	)

static

foldLogOpOfMaskedICmps: try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y)

Definition at line 661 of file InstCombineAndOrXor.cpp.

References llvm::ARM_PROC::A, llvm::CallingConv::C, conjugateICmpMask(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateAnd(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateICmp(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateOr(), llvm::dyn_cast(), foldLogOpOfMaskedICmpsHelper(), FoldMskICmp_AMask_AllOnes, FoldMskICmp_AMask_NotAllOnes, FoldMskICmp_BMask_AllOnes, FoldMskICmp_BMask_Mixed, FoldMskICmp_BMask_NotAllOnes, FoldMskICmp_Mask_AllZeroes, FoldMskICmp_Mask_NotAllZeroes, llvm::ConstantExpr::getAnd(), llvm::Constant::getNullValue(), llvm::ConstantExpr::getOr(), llvm::CmpInst::getPredicate(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::ConstantExpr::getXor(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, and llvm::ICmpInst::isEquality().

Referenced by llvm::InstCombiner::FoldAndOfICmps(), and llvm::InstCombiner::FoldOrOfICmps().

static unsigned foldLogOpOfMaskedICmpsHelper	(	Value *&	A,
		Value *&	B,
		Value *&	C,
		Value *&	D,
		Value *&	E,
		ICmpInst *	LHS,
		ICmpInst *	RHS,
		ICmpInst::Predicate &	LHSCC,
		ICmpInst::Predicate &	RHSCC
	)

static

foldLogOpOfMaskedICmpsHelper: handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) return the set of pattern classes (from MaskedICmpType) that both LHS and RHS satisfy

Definition at line 547 of file InstCombineAndOrXor.cpp.

References decomposeBitTestICmp(), llvm::Constant::getAllOnesValue(), llvm::User::getOperand(), llvm::Value::getType(), getTypeOfMaskedICmp(), llvm::ICmpInst::isEquality(), llvm::Type::isIntegerTy(), llvm::Type::isVectorTy(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and R2.

Referenced by foldLogOpOfMaskedICmps().

static unsigned getFCmpCode	(	FCmpInst::Predicate	CC,
		bool &	isOrdered
	)

static

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.

Definition at line 69 of file InstCombineAndOrXor.cpp.

References llvm::CmpInst::FCMP_OEQ, llvm::CmpInst::FCMP_OGE, llvm::CmpInst::FCMP_OGT, llvm::CmpInst::FCMP_OLE, llvm::CmpInst::FCMP_OLT, llvm::CmpInst::FCMP_ONE, llvm::CmpInst::FCMP_ORD, llvm::CmpInst::FCMP_UEQ, llvm::CmpInst::FCMP_UGE, llvm::CmpInst::FCMP_UGT, llvm::CmpInst::FCMP_ULE, llvm::CmpInst::FCMP_ULT, llvm::CmpInst::FCMP_UNE, llvm::CmpInst::FCMP_UNO, and llvm_unreachable.

Referenced by llvm::InstCombiner::FoldAndOfFCmps(), and llvm::InstCombiner::FoldOrOfFCmps().

static Value* getFCmpValue	(	bool	isordered,
		unsigned	code,
		Value *	LHS,
		Value *	RHS,
		InstCombiner::BuilderTy *	Builder
	)

static

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.

Definition at line 108 of file InstCombineAndOrXor.cpp.

Referenced by llvm::InstCombiner::FoldAndOfFCmps(), and llvm::InstCombiner::FoldOrOfFCmps().

static Value* getNewICmpValue	(	bool	Sign,
		unsigned	Code,
		Value *	LHS,
		Value *	RHS,
		InstCombiner::BuilderTy *	Builder
	)

static

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.

Definition at line 97 of file InstCombineAndOrXor.cpp.

References llvm::IRBuilder< preserveNames, T, Inserter >::CreateICmp(), and llvm::getICmpValue().

Referenced by llvm::InstCombiner::FoldAndOfICmps(), llvm::InstCombiner::FoldOrOfICmps(), and llvm::InstCombiner::visitXor().

static unsigned getTypeOfMaskedICmp	(	Value *	A,
		Value *	B,
		Value *	C,
		ICmpInst::Predicate	SCC
	)

static

return the set of pattern classes (from MaskedICmpType) that (icmp SCC (A & B), C) satisfies

Definition at line 424 of file InstCombineAndOrXor.cpp.

References llvm::ARM_PROC::A, llvm::CallingConv::C, llvm::dyn_cast(), FoldMskICmp_AMask_AllOnes, FoldMskICmp_AMask_Mixed, FoldMskICmp_AMask_NotAllOnes, FoldMskICmp_AMask_NotMixed, FoldMskICmp_BMask_AllOnes, FoldMskICmp_BMask_Mixed, FoldMskICmp_BMask_NotAllOnes, FoldMskICmp_BMask_NotMixed, FoldMskICmp_Mask_AllZeroes, FoldMskICmp_Mask_NotAllZeroes, llvm::ConstantExpr::getAnd(), llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_EQ, llvm::APInt::isPowerOf2(), and llvm::ConstantInt::isZero().

Referenced by foldLogOpOfMaskedICmpsHelper().

static bool isFreeToInvert ( Value * V )

inlinestatic

isFreeToInvert - Return true if the specified value is free to invert (apply ~ to). This happens in cases where the ~ can be eliminated.

Definition at line 35 of file InstCombineAndOrXor.cpp.

References llvm::BinaryOperator::isNot().

Referenced by dyn_castNotVal(), and llvm::InstCombiner::visitXor().

static bool IsOneHotValue ( Value * V )

static

IsOneHotValue - Returns true for "one-hot" values (values where at most one bit can be set).

Definition at line 1548 of file InstCombineAndOrXor.cpp.

References llvm::dyn_cast(), and llvm::ConstantInt::isOne().

Referenced by llvm::InstCombiner::FoldOrOfICmps().

static bool isRunOfOnes	(	ConstantInt *	Val,
		uint32_t &	MB,
		uint32_t &	ME
	)

static

Definition at line 318 of file InstCombineAndOrXor.cpp.

References llvm::APInt::getActiveBits(), llvm::IntegerType::getBitWidth(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), and llvm::APIntOps::isShiftedMask().

static Instruction* MatchSelectFromAndOr	(	Value *	A,
		Value *	B,
		Value *	C,
		Value *	D
	)

static

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".

Definition at line 1524 of file InstCombineAndOrXor.cpp.

References llvm::SelectInst::Create(), llvm::Value::getType(), llvm::Type::isIntegerTy(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by llvm::InstCombiner::visitOr().

static Constant* SubOne ( ConstantInt * C )

static

SubOne - Subtract one from a ConstantInt.

Definition at line 29 of file InstCombineAndOrXor.cpp.

References llvm::ConstantInt::get(), llvm::Value::getContext(), and llvm::ConstantInt::getValue().

Referenced by llvm::InstCombiner::FoldAndOfICmps(), and llvm::InstCombiner::FoldOrOfICmps().

Enumerations

Functions

Enumeration Type Documentation

Function Documentation