LLVM  6.0.0svn
Macros | Enumerations | Functions
InstCombineAndOrXor.cpp File Reference
#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"
Include dependency graph for InstCombineAndOrXor.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "instcombine"
 

Enumerations

enum  MaskedICmpType {
  AMask_AllOnes = 1, AMask_NotAllOnes = 2, BMask_AllOnes = 4, BMask_NotAllOnes = 8,
  Mask_AllZeros = 16, Mask_NotAllZeros = 32, AMask_Mixed = 64, AMask_NotMixed = 128,
  BMask_Mixed = 256, BMask_NotMixed = 512
}
 Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns that can be simplified. More...
 

Functions

static unsigned getFCmpCode (FCmpInst::Predicate CC)
 Similar to getICmpCode but for FCmpInst. More...
 
static ValuegetNewICmpValue (bool Sign, unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
 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. More...
 
static ValuegetFCmpValue (unsigned Code, Value *LHS, Value *RHS, InstCombiner::BuilderTy &Builder)
 This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp instruction, or a true/false constant. More...
 
static ValueSimplifyBSwap (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
 Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B)) More...
 
static unsigned getMaskedICmpType (Value *A, Value *B, Value *C, ICmpInst::Predicate Pred)
 Return the set of patterns (from MaskedICmpType) that (icmp SCC (A & B), C) satisfies. More...
 
static unsigned conjugateICmpMask (unsigned Mask)
 Convert an analysis of a masked ICmp into its equivalent if all boolean operations had the opposite sense. More...
 
static unsigned getMaskedTypeForICmpPair (Value *&A, Value *&B, Value *&C, Value *&D, Value *&E, ICmpInst *LHS, ICmpInst *RHS, ICmpInst::Predicate &PredL, ICmpInst::Predicate &PredR)
 Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E). More...
 
static ValuefoldLogOpOfMaskedICmps (ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, llvm::InstCombiner::BuilderTy &Builder)
 Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E) into a single (icmp(A & X) ==/!= Y). More...
 
static ValuefoldAndOrOfEqualityCmpsWithConstants (ICmpInst *LHS, ICmpInst *RHS, bool JoinedByAnd, InstCombiner::BuilderTy &Builder)
 
static InstructionmatchDeMorgansLaws (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
 Match De Morgan's Laws: (~A & ~B) == (~(A | B)) (~A | ~B) == (~(A & B)) More...
 
static InstructionfoldLogicCastConstant (BinaryOperator &Logic, CastInst *Cast, InstCombiner::BuilderTy &Builder)
 Fold {and,or,xor} (cast X), C. More...
 
static InstructionfoldBoolSextMaskToSelect (BinaryOperator &I)
 
static InstructionfoldAndToXor (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
 
static InstructionfoldOrToXor (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
 
static bool areInverseVectorBitmasks (Constant *C1, Constant *C2)
 If all elements of two constant vectors are 0/-1 and inverses, return true. More...
 
static ValuegetSelectCondition (Value *A, Value *B, InstCombiner::BuilderTy &Builder)
 We have an expression of the form (A & C) | (B & D). More...
 
static ValuematchSelectFromAndOr (Value *A, Value *C, Value *B, Value *D, InstCombiner::BuilderTy &Builder)
 We have an expression of the form (A & C) | (B & D). More...
 
static InstructionFoldOrWithConstants (BinaryOperator &I, Value *Op, Value *A, Value *B, Value *C, InstCombiner::BuilderTy &Builder)
 This helper function folds: More...
 
static InstructionFoldXorWithConstants (BinaryOperator &I, Value *Op, Value *A, Value *B, Value *C, InstCombiner::BuilderTy &Builder)
 This helper function folds: More...
 
static InstructionfoldXorToXor (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
 A ^ B can be specified using other logic ops in a variety of patterns. More...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "instcombine"

Definition at line 24 of file InstCombineAndOrXor.cpp.

Enumeration Type Documentation

◆ MaskedICmpType

Classify (icmp eq (A & B), C) and (icmp ne (A & B), C) as matching patterns that can be simplified.

One of A and B is considered the mask. The other is 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.

"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) -> AMask_AllOnes

"AllZeros" 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) -> Mask_AllZeroes

"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) -> AMask_Mixed

"Not" means that in above descriptions "==" should be replaced by "!=". Example: (icmp ne (A & 3), 3) -> 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
AMask_AllOnes 
AMask_NotAllOnes 
BMask_AllOnes 
BMask_NotAllOnes 
Mask_AllZeros 
Mask_NotAllZeros 
AMask_Mixed 
AMask_NotMixed 
BMask_Mixed 
BMask_NotMixed 

Definition at line 302 of file InstCombineAndOrXor.cpp.

Function Documentation

◆ areInverseVectorBitmasks()

static bool areInverseVectorBitmasks ( Constant C1,
Constant C2 
)
static

◆ conjugateICmpMask()

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 366 of file InstCombineAndOrXor.cpp.

References AMask_AllOnes, AMask_Mixed, AMask_NotAllOnes, AMask_NotMixed, BMask_AllOnes, BMask_Mixed, BMask_NotAllOnes, BMask_NotMixed, Mask_AllZeros, and Mask_NotAllZeros.

Referenced by foldLogOpOfMaskedICmps().

◆ foldAndOrOfEqualityCmpsWithConstants()

static Value* foldAndOrOfEqualityCmpsWithConstants ( ICmpInst LHS,
ICmpInst RHS,
bool  JoinedByAnd,
InstCombiner::BuilderTy Builder 
)
static

Definition at line 704 of file InstCombineAndOrXor.cpp.

References A, llvm::MCID::Add, llvm::AddOne(), assert(), B, C, llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateICmp(), llvm::IRBuilder< T, Inserter >::CreateOr(), D, llvm::dyn_cast(), llvm::CmpInst::FCMP_ORD, foldLogOpOfMaskedICmps(), llvm::ConstantInt::get(), llvm::IntegerType::getBitWidth(), llvm::Type::getContext(), getFCmpCode(), getFCmpValue(), llvm::getICmpCode(), llvm::APInt::getLowBitsSet(), getNewICmpValue(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::CmpInst::getSwappedPredicate(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::Value::hasOneUse(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::ICmpInst::isEquality(), llvm::isKnownToBeAPowerOfTwo(), llvm::APInt::isNullValue(), llvm::APInt::isPowerOf2(), llvm::CmpInst::isSigned(), llvm::ConstantInt::isZero(), llvm_unreachable, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), N, llvm::PredicatesFoldable(), llvm::APInt::sgt(), llvm::SubOne(), std::swap(), llvm::ICmpInst::swapOperands(), llvm::APInt::ugt(), X, and llvm::APInt::zext().

Referenced by matchSelectFromAndOr().

◆ foldAndToXor()

static Instruction* foldAndToXor ( BinaryOperator I,
InstCombiner::BuilderTy Builder 
)
static

◆ foldBoolSextMaskToSelect()

static Instruction* foldBoolSextMaskToSelect ( BinaryOperator I)
static

◆ foldLogicCastConstant()

static Instruction* foldLogicCastConstant ( BinaryOperator Logic,
CastInst Cast,
InstCombiner::BuilderTy Builder 
)
static

◆ foldLogOpOfMaskedICmps()

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

◆ foldOrToXor()

static Instruction* foldOrToXor ( BinaryOperator I,
InstCombiner::BuilderTy Builder 
)
static

◆ FoldOrWithConstants()

static Instruction* FoldOrWithConstants ( BinaryOperator I,
Value Op,
Value A,
Value B,
Value C,
InstCombiner::BuilderTy Builder 
)
static

This helper function folds:

((A | B) & C1) | (B & C2)

into:

(A & C1) | B

when the XOR of the two constants is "all ones" (-1).

Definition at line 1895 of file InstCombineAndOrXor.cpp.

References C, llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::dyn_cast(), llvm::ConstantInt::getValue(), llvm::APInt::isAllOnesValue(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

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

◆ foldXorToXor()

static Instruction* foldXorToXor ( BinaryOperator I,
InstCombiner::BuilderTy Builder 
)
static

◆ FoldXorWithConstants()

static Instruction* FoldXorWithConstants ( BinaryOperator I,
Value Op,
Value A,
Value B,
Value C,
InstCombiner::BuilderTy Builder 
)
static

This helper function folds:

((A ^ B) & C1) | (B & C2)

into:

(A & C1) ^ B

when the XOR of the two constants is "all ones" (-1).

Definition at line 1925 of file InstCombineAndOrXor.cpp.

References C, llvm::IRBuilder< T, Inserter >::CreateAnd(), llvm::dyn_cast(), llvm::ConstantInt::getValue(), llvm::APInt::isAllOnesValue(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

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

◆ getFCmpCode()

static unsigned getFCmpCode ( FCmpInst::Predicate  CC)
static

◆ getFCmpValue()

static Value* getFCmpValue ( unsigned  Code,
Value LHS,
Value RHS,
InstCombiner::BuilderTy Builder 
)
static

This is the complement of getFCmpCode, which turns an opcode and two operands into either a FCmp instruction, or a true/false constant.

Definition at line 66 of file InstCombineAndOrXor.cpp.

References assert(), llvm::IRBuilder< T, Inserter >::CreateFCmp(), llvm::CmpInst::FCMP_FALSE, llvm::CmpInst::FCMP_TRUE, llvm::ConstantInt::get(), llvm::Value::getType(), and llvm::CmpInst::makeCmpResultType().

Referenced by foldAndOrOfEqualityCmpsWithConstants(), and matchSelectFromAndOr().

◆ getMaskedICmpType()

static unsigned getMaskedICmpType ( Value A,
Value B,
Value C,
ICmpInst::Predicate  Pred 
)
static

◆ getMaskedTypeForICmpPair()

static unsigned getMaskedTypeForICmpPair ( Value *&  A,
Value *&  B,
Value *&  C,
Value *&  D,
Value *&  E,
ICmpInst LHS,
ICmpInst RHS,
ICmpInst::Predicate &  PredL,
ICmpInst::Predicate &  PredR 
)
static

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 382 of file InstCombineAndOrXor.cpp.

References llvm::decomposeBitTestICmp(), llvm::Constant::getAllOnesValue(), getMaskedICmpType(), llvm::User::getOperand(), llvm::Value::getType(), 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().

◆ getNewICmpValue()

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

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 56 of file InstCombineAndOrXor.cpp.

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

Referenced by foldAndOrOfEqualityCmpsWithConstants(), foldXorToXor(), and matchSelectFromAndOr().

◆ getSelectCondition()

static Value* getSelectCondition ( Value A,
Value B,
InstCombiner::BuilderTy Builder 
)
static

◆ matchDeMorgansLaws()

static Instruction* matchDeMorgansLaws ( BinaryOperator I,
InstCombiner::BuilderTy Builder 
)
static

◆ matchSelectFromAndOr()

static Value* matchSelectFromAndOr ( Value A,
Value C,
Value B,
Value D,
InstCombiner::BuilderTy Builder 
)
static

We have an expression of the form (A & C) | (B & D).

Try to simplify this to "A' ? C : D", where A' is a boolean or vector of booleans.

Definition at line 1587 of file InstCombineAndOrXor.cpp.

References A, assert(), B, llvm::IRBuilder< T, Inserter >::CreateBitCast(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dyn_cast(), llvm::CmpInst::FCMP_UNO, foldAndOrOfEqualityCmpsWithConstants(), foldLogOpOfMaskedICmps(), llvm::ConstantInt::get(), getFCmpCode(), getFCmpValue(), llvm::getICmpCode(), getNewICmpValue(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), getSelectCondition(), llvm::ConstantInt::getSigned(), llvm::CmpInst::getSwappedPredicate(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::Value::hasOneUse(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::ICmpInst::isEquality(), llvm::APInt::isPowerOf2(), llvm::CmpInst::isSigned(), llvm::ConstantInt::isZero(), llvm_unreachable, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::peekThroughBitcast(), llvm::PredicatesFoldable(), llvm::MCID::Select, llvm::APInt::sgt(), std::swap(), llvm::ICmpInst::swapOperands(), llvm::APInt::ugt(), and llvm::APInt::ult().

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

◆ SimplifyBSwap()

static Value* SimplifyBSwap ( BinaryOperator I,
InstCombiner::BuilderTy Builder 
)
static

Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B))

Parameters
IBinary operator to transform.
Returns
Pointer to node that must replace the original binary operator, or null pointer if no transformation was made.

Definition at line 83 of file InstCombineAndOrXor.cpp.

References llvm::MCID::Add, assert(), llvm::APInt::byteSwap(), C, llvm::IRBuilder< T, Inserter >::CreateBinOp(), llvm::IRBuilder< T, Inserter >::CreateCall(), llvm::dyn_cast(), F, llvm::ConstantInt::get(), llvm::ConstantExpr::getAnd(), llvm::IntegerType::getBitWidth(), llvm::Intrinsic::getDeclaration(), llvm::ConstantInt::getFalse(), llvm::APInt::getHighBitsSet(), llvm::ConstantInt::getLimitedValue(), llvm::APInt::getLowBitsSet(), llvm::Instruction::getModule(), llvm::Value::getName(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::ICmpInst::getSignedPredicate(), llvm::ConstantInt::getTrue(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::ConstantExpr::getXor(), llvm::Value::hasOneUse(), llvm::MipsISD::Hi, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULT, llvm::Instruction::isBitwiseLogicOp(), llvm::APInt::isMinSignedValue(), llvm::APInt::isMinValue(), llvm::APInt::isPowerOf2(), llvm::Instruction::isShift(), llvm::ConstantInt::isZero(), llvm::MipsISD::Lo, llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_BSwap(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::User::setOperand(), llvm::APInt::sle(), llvm::Value::takeName(), llvm::APInt::ule(), and X.

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