InstCombineMulDivRem.cpp File Reference

#include "InstCombineInternal.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
#include <cassert>
#include "llvm/Transforms/Utils/InstructionWorklist.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "instcombine"

Functions
static Value *	simplifyValueKnownNonZero (Value *V, InstCombinerImpl &IC, Instruction &CxtI)
	The specific integer value is used in a context where it is known to be non-zero.
static Value *	foldMulSelectToNegate (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Value *	foldMulShl1 (BinaryOperator &Mul, bool CommuteOperands, InstCombiner::BuilderTy &Builder)
	Reduce integer multiplication patterns that contain a (+/-1 << Z) factor.
static Value *	takeLog2 (IRBuilderBase &Builder, Value *Op, unsigned Depth, bool AssumeNonZero, bool DoFold)
static bool	multiplyOverflows (const APInt &C1, const APInt &C2, APInt &Product, bool IsSigned)
	True if the multiply can not be expressed in an int this size.
static bool	isMultiple (const APInt &C1, const APInt &C2, APInt &Quotient, bool IsSigned)
	True if C1 is a multiple of C2. Quotient contains C1/C2.
static Value *	foldIDivShl (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
static Instruction *	narrowUDivURem (BinaryOperator &I, InstCombinerImpl &IC)
	If we have zero-extended operands of an unsigned div or rem, we may be able to narrow the operation (sink the zext below the math).
static Instruction *	foldFDivConstantDividend (BinaryOperator &I)
	Remove negation and try to reassociate constant math.
static Instruction *	foldFDivPowDivisor (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	Negate the exponent of pow/exp to fold division-by-pow() into multiply.
static Instruction *	foldFDivSqrtDivisor (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	Convert div to mul if we have an sqrt divisor iff sqrt's operand is a fdiv instruction.
static Instruction *	simplifyIRemMulShl (BinaryOperator &I, InstCombinerImpl &IC)

Variables
static const unsigned	MaxDepth = 6

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "instcombine"

Definition at line 37 of file InstCombineMulDivRem.cpp.

Function Documentation

foldFDivConstantDividend()

static Instruction * foldFDivConstantDividend ( BinaryOperator &  I )

static

Remove negation and try to reassociate constant math.

Definition at line 1823 of file InstCombineMulDivRem.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldBinaryOpOperands(), llvm::ConstantFoldUnaryOpOperand(), llvm::BinaryOperator::CreateFDivFMF(), DL, I, llvm::Constant::isNormalFP(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_FDiv(), llvm::PatternMatch::m_FMul(), llvm::PatternMatch::m_FNeg(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and X.

Referenced by llvm::InstCombinerImpl::visitFDiv().

foldFDivPowDivisor()

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

static

Negate the exponent of pow/exp to fold division-by-pow() into multiply.

Definition at line 1858 of file InstCombineMulDivRem.cpp.

References llvm::BinaryOperator::CreateFMulFMF(), llvm::IRBuilderBase::CreateFNegFMF(), llvm::IRBuilderBase::CreateIntrinsic(), llvm::IRBuilderBase::CreateNeg(), I, and II.

Referenced by llvm::InstCombinerImpl::visitFDiv().

foldFDivSqrtDivisor()

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

static

Convert div to mul if we have an sqrt divisor iff sqrt's operand is a fdiv instruction.

Definition at line 1904 of file InstCombineMulDivRem.cpp.

References llvm::IRBuilderBase::CreateFDivFMF(), llvm::BinaryOperator::CreateFMulFMF(), llvm::IRBuilderBase::CreateUnaryIntrinsic(), I, II, llvm::PatternMatch::m_FDiv(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and Y.

Referenced by llvm::InstCombinerImpl::visitFDiv().

foldIDivShl()

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

static

Definition at line 1081 of file InstCombineMulDivRem.cpp.

References assert(), llvm::IRBuilderBase::CreateLShr(), llvm::IRBuilderBase::CreateSDiv(), llvm::IRBuilderBase::CreateShl(), llvm::IRBuilderBase::CreateUDiv(), llvm::Value::hasOneUse(), I, llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::Mul, X, and Y.

Referenced by llvm::InstCombinerImpl::commonIDivTransforms().

foldMulSelectToNegate()

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

static

Definition at line 99 of file InstCombineMulDivRem.cpp.

References Cond, llvm::IRBuilderBase::CreateFNeg(), llvm::IRBuilderBase::CreateNeg(), llvm::IRBuilderBase::CreateSelect(), I, llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_c_FMul(), llvm::PatternMatch::m_c_Mul(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_SpecificFP(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::IRBuilderBase::setFastMathFlags().

Referenced by llvm::InstCombinerImpl::visitFMul(), and llvm::InstCombinerImpl::visitMul().

foldMulShl1()

static Value * foldMulShl1 ( BinaryOperator &  Mul, bool  CommuteOperands, InstCombiner::BuilderTy &  Builder  )

static

Reduce integer multiplication patterns that contain a (+/-1 << Z) factor.

Callers are expected to call this twice to handle commuted patterns.

Definition at line 145 of file InstCombineMulDivRem.cpp.

References llvm::IRBuilderBase::CreateAdd(), llvm::IRBuilderBase::CreateFreeze(), llvm::IRBuilderBase::CreateShl(), llvm::IRBuilderBase::CreateSub(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Instruction::hasNoSignedWrap(), llvm::Instruction::hasNoUnsignedWrap(), llvm::isGuaranteedNotToBeUndef(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), Mul, std::swap(), X, and Y.

Referenced by llvm::InstCombinerImpl::visitMul().

isMultiple()

static bool isMultiple ( const APInt &  C1, const APInt &  C2, APInt &  Quotient, bool  IsSigned  )

static

True if C1 is a multiple of C2. Quotient contains C1/C2.

Definition at line 1060 of file InstCombineMulDivRem.cpp.

References assert(), llvm::APInt::getBitWidth(), llvm::APInt::isAllOnes(), llvm::APInt::isMinSignedValue(), llvm::APInt::isMinValue(), llvm::APInt::isZero(), llvm::APInt::sdivrem(), and llvm::APInt::udivrem().

Referenced by llvm::InstCombinerImpl::commonIDivTransforms().

multiplyOverflows()

static bool multiplyOverflows ( const APInt &  C1, const APInt &  C2, APInt &  Product, bool  IsSigned  )

static

True if the multiply can not be expressed in an int this size.

Definition at line 1052 of file InstCombineMulDivRem.cpp.

References llvm::APInt::smul_ov(), and llvm::APInt::umul_ov().

Referenced by llvm::InstCombinerImpl::commonIDivTransforms().

narrowUDivURem()

static Instruction * narrowUDivURem ( BinaryOperator &  I, InstCombinerImpl &  IC  )

static

If we have zero-extended operands of an unsigned div or rem, we may be able to narrow the operation (sink the zext below the math).

Definition at line 1527 of file InstCombineMulDivRem.cpp.

References llvm::InstCombiner::Builder, llvm::CallingConv::C, llvm::IRBuilderBase::CreateBinOp(), D, llvm::InstCombinerImpl::getLosslessUnsignedTrunc(), I, llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), N, X, and Y.

Referenced by llvm::InstCombinerImpl::visitUDiv(), and llvm::InstCombinerImpl::visitURem().

simplifyIRemMulShl()

static Instruction * simplifyIRemMulShl ( BinaryOperator &  I, InstCombinerImpl &  IC  )

static

Definition at line 2062 of file InstCombineMulDivRem.cpp.

References llvm::CallingConv::C, llvm::APInt::getBitWidth(), llvm::Constant::getNullValue(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), llvm::OverflowingBinaryOperator::hasNoUnsignedWrap(), I, llvm::APInt::isZero(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::InstCombiner::replaceInstUsesWith(), llvm::Instruction::setHasNoSignedWrap(), llvm::Instruction::setHasNoUnsignedWrap(), X, and Y.

Referenced by llvm::InstCombinerImpl::commonIRemTransforms().

simplifyValueKnownNonZero()

static Value * simplifyValueKnownNonZero ( Value *  V, InstCombinerImpl &  IC, Instruction &  CxtI  )

static

The specific integer value is used in a context where it is known to be non-zero.

If this allows us to simplify the computation, do so and return the new operand, otherwise return null.

Definition at line 46 of file InstCombineMulDivRem.cpp.

References A, B, llvm::InstCombiner::Builder, llvm::IRBuilderBase::CreateShl(), llvm::IRBuilderBase::CreateSub(), I, llvm::InstCombiner::isKnownToBeAPowerOfTwo(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::InstCombiner::replaceOperand(), and simplifyValueKnownNonZero().

Referenced by llvm::InstCombinerImpl::commonIDivRemTransforms(), and simplifyValueKnownNonZero().

takeLog2()

static Value * takeLog2 ( IRBuilderBase &  Builder, Value *  Op, unsigned  Depth, bool  AssumeNonZero, bool  DoFold  )

static

Definition at line 1425 of file InstCombineMulDivRem.cpp.

References llvm::CallingConv::C, llvm::IRBuilderBase::CreateAdd(), llvm::IRBuilderBase::CreateBinaryIntrinsic(), llvm::IRBuilderBase::CreateSelect(), llvm::IRBuilderBase::CreateSub(), llvm::IRBuilderBase::CreateTrunc(), llvm::IRBuilderBase::CreateZExt(), llvm::Depth, llvm::ConstantExpr::getExactLogBase2(), llvm_unreachable, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Power2(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), MaxDepth, takeLog2(), X, and Y.

Referenced by takeLog2(), llvm::InstCombinerImpl::visitMul(), and llvm::InstCombinerImpl::visitUDiv().

Variable Documentation

MaxDepth

const unsigned MaxDepth = 6

static

Definition at line 1420 of file InstCombineMulDivRem.cpp.

Referenced by llvm::SUnit::biasCriticalPath(), combineX86ShufflesRecursively(), llvm::SelectionDAG::copyExtraInfo(), countToEliminateCompares(), directlyImpliesPoison(), llvm::MachineInstr::dumpr(), llvm::GISelKnownBitsAnalysis::get(), llvm::WindowScheduler::getEstimatedII(), impliesPoison(), llvm::SITargetLowering::isCanonicalized(), isDereferenceableAndAlignedPointer(), llvm::longestCommonSequence(), and takeLog2().