InstCombineShifts.cpp File Reference

#include "InstCombineInternal.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "instcombine"

Functions
bool	canTryToConstantAddTwoShiftAmounts (Value *Sh0, Value *ShAmt0, Value *Sh1, Value *ShAmt1)
static Instruction *	dropRedundantMaskingOfLeftShiftInput (BinaryOperator *OuterShift, const SimplifyQuery &Q, InstCombiner::BuilderTy &Builder)
static Instruction *	foldShiftOfShiftedBinOp (BinaryOperator &I, InstCombiner::BuilderTy &Builder)
	If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/ shl) that itself has a shift-by-constant operand with identical opcode, we may be able to convert that into 2 independent shifts followed by the logic op.
static bool	canEvaluateShiftedShift (unsigned OuterShAmt, bool IsOuterShl, Instruction *InnerShift, InstCombinerImpl &IC, Instruction *CxtI)
	Return true if we can simplify two logical (either left or right) shifts that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
static bool	canEvaluateShifted (Value *V, unsigned NumBits, bool IsLeftShift, InstCombinerImpl &IC, Instruction *CxtI)
	See if we can compute the specified value, but shifted logically to the left or right by some number of bits.
static Value *	foldShiftedShift (BinaryOperator *InnerShift, unsigned OuterShAmt, bool IsOuterShl, InstCombiner::BuilderTy &Builder)
	Fold OuterShift (InnerShift X, C1), C2.
static Value *	getShiftedValue (Value *V, unsigned NumBits, bool isLeftShift, InstCombinerImpl &IC, const DataLayout &DL)
	When canEvaluateShifted() returns true for an expression, this function inserts the new computation that produces the shifted value.
static bool	canShiftBinOpWithConstantRHS (BinaryOperator &Shift, BinaryOperator *BO)
static bool	setShiftFlags (BinaryOperator &I, const SimplifyQuery &Q)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "instcombine"

Definition at line 21 of file InstCombineShifts.cpp.

Function Documentation

canEvaluateShifted()

static bool canEvaluateShifted ( Value *  V, unsigned  NumBits, bool  IsLeftShift, InstCombinerImpl &  IC, Instruction *  CxtI  )

static

See if we can compute the specified value, but shifted logically to the left or right by some number of bits.

This should return true if the expression can be computed for the same cost as the current expression tree. This is used to eliminate extraneous shifting from things like: C = shl i128 A, 64 D = shl i128 B, 96 E = or i128 C, D F = lshr i128 E, 64 where the client will ask if E can be computed shifted right by 64-bits. If this succeeds, getShiftedValue() will be called to produce the value.

Definition at line 586 of file InstCombineShifts.cpp.

References canEvaluateShifted(), canEvaluateShiftedShift(), llvm::APInt::countr_zero(), I, llvm::PHINode::incoming_values(), llvm::APInt::isNegatedPowerOf2(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_ImmConstant(), and llvm::PatternMatch::match().

Referenced by canEvaluateShifted(), and llvm::InstCombinerImpl::FoldShiftByConstant().

canEvaluateShiftedShift()

static bool canEvaluateShiftedShift ( unsigned  OuterShAmt, bool  IsOuterShl, Instruction *  InnerShift, InstCombinerImpl &  IC, Instruction *  CxtI  )

static

Return true if we can simplify two logical (either left or right) shifts that have constant shift amounts: OuterShift (InnerShift X, C1), C2.

Definition at line 534 of file InstCombineShifts.cpp.

References assert(), llvm::APInt::getLowBitsSet(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::APInt::getZExtValue(), llvm::Instruction::isLogicalShift(), llvm::PatternMatch::m_APInt(), llvm::InstCombiner::MaskedValueIsZero(), MaskShift(), llvm::PatternMatch::match(), llvm::APInt::ugt(), and llvm::APInt::ult().

Referenced by canEvaluateShifted().

canShiftBinOpWithConstantRHS()

static bool canShiftBinOpWithConstantRHS ( BinaryOperator &  Shift, BinaryOperator *  BO  )

static

Definition at line 765 of file InstCombineShifts.cpp.

References llvm::BinaryOperator::getOpcode(), llvm::Instruction::isLogicalShift(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

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

canTryToConstantAddTwoShiftAmounts()

bool canTryToConstantAddTwoShiftAmounts	(	Value *	Sh0,
		Value *	ShAmt0,
		Value *	Sh1,
		Value *	ShAmt1
	)

Definition at line 23 of file InstCombineShifts.cpp.

References llvm::APInt::getAllOnes(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), and llvm::APInt::uge().

Referenced by dropRedundantMaskingOfLeftShiftInput(), and llvm::InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts().

dropRedundantMaskingOfLeftShiftInput()

static Instruction * dropRedundantMaskingOfLeftShiftInput ( BinaryOperator *  OuterShift, const SimplifyQuery &  Q, InstCombiner::BuilderTy &  Builder  )

static

Definition at line 189 of file InstCombineShifts.cpp.

References assert(), canTryToConstantAddTwoShiftAmounts(), llvm::ConstantFoldBinaryOpOperands(), llvm::ConstantFoldCastOperand(), llvm::BinaryOperator::Create(), llvm::IRBuilderBase::CreateTrunc(), llvm::SimplifyQuery::DL, llvm::Constant::getAllOnesValue(), llvm::Type::getExtendedType(), llvm::ConstantExpr::getNot(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::ConstantExpr::getSub(), llvm::ConstantExpr::getTrunc(), llvm::Value::getType(), llvm::Value::hasOneUse(), llvm::IRBuilderBase::Insert(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_AllOnes(), llvm::PatternMatch::m_AShr(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_CombineAnd(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_Deferred(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Shift(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Shr(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExtOrSelf(), llvm::Masked, llvm::PatternMatch::match(), llvm::Constant::replaceUndefsWith(), llvm::simplifyAddInst(), llvm::simplifySubInst(), and X.

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

foldShiftedShift()

static Value * foldShiftedShift ( BinaryOperator *  InnerShift, unsigned  OuterShAmt, bool  IsOuterShl, InstCombiner::BuilderTy &  Builder  )

static

Fold OuterShift (InnerShift X, C1), C2.

See canEvaluateShiftedShift() for the constraints on these instructions.

Definition at line 640 of file InstCombineShifts.cpp.

References llvm::And, assert(), llvm::IRBuilderBase::CreateAnd(), llvm::APInt::getHighBitsSet(), llvm::APInt::getLowBitsSet(), llvm::Constant::getNullValue(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::APInt::getZExtValue(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::match(), llvm::Instruction::setHasNoSignedWrap(), llvm::Instruction::setHasNoUnsignedWrap(), llvm::Instruction::setIsExact(), llvm::User::setOperand(), and llvm::Value::takeName().

Referenced by getShiftedValue().

foldShiftOfShiftedBinOp()

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

static

If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/ shl) that itself has a shift-by-constant operand with identical opcode, we may be able to convert that into 2 independent shifts followed by the logic op.

This eliminates a use of an intermediate value (reduces dependency chain).

Definition at line 348 of file InstCombineShifts.cpp.

References assert(), llvm::BinaryOperator::Create(), llvm::IRBuilderBase::CreateBinOp(), llvm::ConstantExpr::getAdd(), llvm::Type::getScalarSizeInBits(), I, llvm::CmpInst::ICMP_ULT, llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_ImmConstant(), llvm::PatternMatch::m_SpecificInt_ICMP(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), Size, X, and Y.

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

getShiftedValue()

static Value * getShiftedValue ( Value *  V, unsigned  NumBits, bool  isLeftShift, InstCombinerImpl &  IC, const DataLayout &  DL  )

static

When canEvaluateShifted() returns true for an expression, this function inserts the new computation that produces the shifted value.

Definition at line 703 of file InstCombineShifts.cpp.

References llvm::InstCombiner::addToWorklist(), llvm::And, assert(), llvm::InstCombiner::Builder, llvm::CallingConv::C, llvm::IRBuilderBase::CreateLShr(), llvm::BinaryOperator::CreateNeg(), llvm::IRBuilderBase::CreateShl(), DL, foldShiftedShift(), llvm::PHINode::getIncomingValue(), llvm::APInt::getLowBitsSet(), llvm::PHINode::getNumIncomingValues(), getShiftedValue(), I, llvm::InstCombiner::InsertNewInstWith(), llvm_unreachable, and llvm::PHINode::setIncomingValue().

Referenced by llvm::InstCombinerImpl::FoldShiftByConstant(), and getShiftedValue().

setShiftFlags()

static bool setShiftFlags ( BinaryOperator &  I, const SimplifyQuery &  Q  )

static

Definition at line 981 of file InstCombineShifts.cpp.

References llvm::SimplifyQuery::AC, assert(), llvm::BitWidth, llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::KnownBits::countMinLeadingZeros(), llvm::KnownBits::countMinSignBits(), llvm::KnownBits::countMinTrailingZeros(), llvm::SimplifyQuery::CxtI, llvm::SimplifyQuery::DL, llvm::SimplifyQuery::DT, llvm::KnownBits::getBitWidth(), llvm::APInt::getLimitedValue(), llvm::KnownBits::getMaxValue(), I, llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by llvm::InstCombinerImpl::visitAShr(), llvm::InstCombinerImpl::visitLShr(), and llvm::InstCombinerImpl::visitShl().