This is an archive of the discontinued LLVM Phabricator instance.

Show First 20 Lines • Show All 645 Lines • ▼ Show 20 Lines	public:
/// intrinsic.		/// intrinsic.
Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,		Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
bool MatchBitReversals);		bool MatchBitReversals);

Instruction SimplifyAnyMemTransfer(AnyMemTransferInst MI);		Instruction SimplifyAnyMemTransfer(AnyMemTransferInst MI);
Instruction SimplifyAnyMemSet(AnyMemSetInst MI);		Instruction SimplifyAnyMemSet(AnyMemSetInst MI);

Value EvaluateInDifferentType(Value V, Type *Ty, bool isSigned);		Value EvaluateInDifferentType(Value V, Type *Ty, bool isSigned);

/// Returns a value X such that Val = X * Scale, or null if none.
///
/// If the multiplication is known not to overflow then NoSignedWrap is set.
Value Descale(Value Val, APInt Scale, bool &NoSignedWrap);
};		};

class Negator final {		class Negator final {
/// Top-to-bottom, def-to-use negated instruction tree we produced.		/// Top-to-bottom, def-to-use negated instruction tree we produced.
SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;		SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;

using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;		using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
BuilderTy Builder;		BuilderTy Builder;
▲ Show 20 Lines • Show All 47 Lines • Show Last 20 Lines

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

Show First 20 Lines • Show All 1,360 Lines • ▼ Show 20 Lines	static bool shouldMergeGEPs(GEPOperator &GEP, GEPOperator &Src) {
// Src. If Src is not a trivial GEP too, don't combine		// Src. If Src is not a trivial GEP too, don't combine
// the indices.		// the indices.
if (GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&		if (GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&
!Src.hasOneUse())		!Src.hasOneUse())
return false;		return false;
return true;		return true;
}		}

/// Return a value X such that Val = X * Scale, or null if none.
/// If the multiplication is known not to overflow, then NoSignedWrap is set.
Value InstCombinerImpl::Descale(Value Val, APInt Scale, bool &NoSignedWrap) {
assert(isa<IntegerType>(Val->getType()) && "Can only descale integers!");
assert(cast<IntegerType>(Val->getType())->getBitWidth() ==
Scale.getBitWidth() && "Scale not compatible with value!");

// If Val is zero or Scale is one then Val = Val * Scale.
if (match(Val, m_Zero()) \|\| Scale == 1) {
NoSignedWrap = true;
return Val;
}

// If Scale is zero then it does not divide Val.
if (Scale.isMinValue())
return nullptr;

// Look through chains of multiplications, searching for a constant that is
// divisible by Scale. For example, descaling X(Y(Z*4)) by a factor of 4
// will find the constant factor 4 and produce X(YZ). Descaling X(Y8) by
// a factor of 4 will produce X(Y2). The principle of operation is to bore
// down from Val:
//
// Val = M1 * X \|\| Analysis starts here and works down
// M1 = M2 * Y \|\| Doesn't descend into terms with more
// M2 = Z * 4 \/ than one use
//
// Then to modify a term at the bottom:
//
// Val = M1 * X
// M1 = Z * Y \|\| Replaced M2 with Z
//
// Then to work back up correcting nsw flags.

// Op - the term we are currently analyzing. Starts at Val then drills down.
// Replaced with its descaled value before exiting from the drill down loop.
Value *Op = Val;

// Parent - initially null, but after drilling down notes where Op came from.
// In the example above, Parent is (Val, 0) when Op is M1, because M1 is the
// 0'th operand of Val.
std::pair<Instruction *, unsigned> Parent;

// Set if the transform requires a descaling at deeper levels that doesn't
// overflow.
bool RequireNoSignedWrap = false;

// Log base 2 of the scale. Negative if not a power of 2.
int32_t logScale = Scale.exactLogBase2();

for (;; Op = Parent.first->getOperand(Parent.second)) { // Drill down
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
// If Op is a constant divisible by Scale then descale to the quotient.
APInt Quotient(Scale), Remainder(Scale); // Init ensures right bitwidth.
APInt::sdivrem(CI->getValue(), Scale, Quotient, Remainder);
if (!Remainder.isMinValue())
// Not divisible by Scale.
return nullptr;
// Replace with the quotient in the parent.
Op = ConstantInt::get(CI->getType(), Quotient);
NoSignedWrap = true;
break;
}

if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op)) {
if (BO->getOpcode() == Instruction::Mul) {
// Multiplication.
NoSignedWrap = BO->hasNoSignedWrap();
if (RequireNoSignedWrap && !NoSignedWrap)
return nullptr;

// There are three cases for multiplication: multiplication by exactly
// the scale, multiplication by a constant different to the scale, and
// multiplication by something else.
Value *LHS = BO->getOperand(0);
Value *RHS = BO->getOperand(1);

if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
// Multiplication by a constant.
if (CI->getValue() == Scale) {
// Multiplication by exactly the scale, replace the multiplication
// by its left-hand side in the parent.
Op = LHS;
break;
}

// Otherwise drill down into the constant.
if (!Op->hasOneUse())
return nullptr;

Parent = std::make_pair(BO, 1);
continue;
}

// Multiplication by something else. Drill down into the left-hand side
// since that's where the reassociate pass puts the good stuff.
if (!Op->hasOneUse())
return nullptr;

Parent = std::make_pair(BO, 0);
continue;
}

if (logScale > 0 && BO->getOpcode() == Instruction::Shl &&
isa<ConstantInt>(BO->getOperand(1))) {
// Multiplication by a power of 2.
NoSignedWrap = BO->hasNoSignedWrap();
if (RequireNoSignedWrap && !NoSignedWrap)
return nullptr;

Value *LHS = BO->getOperand(0);
int32_t Amt = cast<ConstantInt>(BO->getOperand(1))->
getLimitedValue(Scale.getBitWidth());
// Op = LHS << Amt.

if (Amt == logScale) {
// Multiplication by exactly the scale, replace the multiplication
// by its left-hand side in the parent.
Op = LHS;
break;
}
if (Amt < logScale \|\| !Op->hasOneUse())
return nullptr;

// Multiplication by more than the scale. Reduce the multiplying amount
// by the scale in the parent.
Parent = std::make_pair(BO, 1);
Op = ConstantInt::get(BO->getType(), Amt - logScale);
break;
}
}

if (!Op->hasOneUse())
return nullptr;

if (CastInst *Cast = dyn_cast<CastInst>(Op)) {
if (Cast->getOpcode() == Instruction::SExt) {
// Op is sign-extended from a smaller type, descale in the smaller type.
unsigned SmallSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
APInt SmallScale = Scale.trunc(SmallSize);
// Suppose Op = sext X, and we descale X as Y * SmallScale. We want to
// descale Op as (sext Y) * Scale. In order to have
// sext (Y * SmallScale) = (sext Y) * Scale
// some conditions need to hold however: SmallScale must sign-extend to
// Scale and the multiplication Y * SmallScale should not overflow.
if (SmallScale.sext(Scale.getBitWidth()) != Scale)
// SmallScale does not sign-extend to Scale.
return nullptr;
assert(SmallScale.exactLogBase2() == logScale);
// Require that Y * SmallScale must not overflow.
RequireNoSignedWrap = true;

// Drill down through the cast.
Parent = std::make_pair(Cast, 0);
Scale = SmallScale;
continue;
}

if (Cast->getOpcode() == Instruction::Trunc) {
// Op is truncated from a larger type, descale in the larger type.
// Suppose Op = trunc X, and we descale X as Y * sext Scale. Then
// trunc (Y * sext Scale) = (trunc Y) * Scale
// always holds. However (trunc Y) * Scale may overflow even if
// trunc (Y * sext Scale) does not, so nsw flags need to be cleared
// from this point up in the expression (see later).
if (RequireNoSignedWrap)
return nullptr;

// Drill down through the cast.
unsigned LargeSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
Parent = std::make_pair(Cast, 0);
Scale = Scale.sext(LargeSize);
if (logScale + 1 == (int32_t)Cast->getType()->getPrimitiveSizeInBits())
logScale = -1;
assert(Scale.exactLogBase2() == logScale);
continue;
}
}

// Unsupported expression, bail out.
return nullptr;
}

// If Op is zero then Val = Op * Scale.
if (match(Op, m_Zero())) {
NoSignedWrap = true;
return Op;
}

// We know that we can successfully descale, so from here on we can safely
// modify the IR. Op holds the descaled version of the deepest term in the
// expression. NoSignedWrap is 'true' if multiplying Op by Scale is known
// not to overflow.

if (!Parent.first)
// The expression only had one term.
return Op;

// Rewrite the parent using the descaled version of its operand.
assert(Parent.first->hasOneUse() && "Drilled down when more than one use!");
assert(Op != Parent.first->getOperand(Parent.second) &&
"Descaling was a no-op?");
replaceOperand(*Parent.first, Parent.second, Op);
Worklist.push(Parent.first);

// Now work back up the expression correcting nsw flags. The logic is based
// on the following observation: if X * Y is known not to overflow as a signed
// multiplication, and Y is replaced by a value Z with smaller absolute value,
// then X * Z will not overflow as a signed multiplication either. As we work
// our way up, having NoSignedWrap 'true' means that the descaled value at the
// current level has strictly smaller absolute value than the original.
Instruction *Ancestor = Parent.first;
do {
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Ancestor)) {
// If the multiplication wasn't nsw then we can't say anything about the
// value of the descaled multiplication, and we have to clear nsw flags
// from this point on up.
bool OpNoSignedWrap = BO->hasNoSignedWrap();
NoSignedWrap &= OpNoSignedWrap;
if (NoSignedWrap != OpNoSignedWrap) {
BO->setHasNoSignedWrap(NoSignedWrap);
Worklist.push(Ancestor);
}
} else if (Ancestor->getOpcode() == Instruction::Trunc) {
// The fact that the descaled input to the trunc has smaller absolute
// value than the original input doesn't tell us anything useful about
// the absolute values of the truncations.
NoSignedWrap = false;
}
assert((Ancestor->getOpcode() != Instruction::SExt \|\| NoSignedWrap) &&
"Failed to keep proper track of nsw flags while drilling down?");

if (Ancestor == Val)
// Got to the top, all done!
return Val;

// Move up one level in the expression.
assert(Ancestor->hasOneUse() && "Drilled down when more than one use!");
Ancestor = Ancestor->user_back();
} while (true);
}

Instruction *InstCombinerImpl::foldVectorBinop(BinaryOperator &Inst) {		Instruction *InstCombinerImpl::foldVectorBinop(BinaryOperator &Inst) {
if (!isa<VectorType>(Inst.getType()))		if (!isa<VectorType>(Inst.getType()))
return nullptr;		return nullptr;

BinaryOperator::BinaryOps Opcode = Inst.getOpcode();		BinaryOperator::BinaryOps Opcode = Inst.getOpcode();
Value LHS = Inst.getOperand(0), RHS = Inst.getOperand(1);		Value LHS = Inst.getOperand(0), RHS = Inst.getOperand(1);
assert(cast<VectorType>(LHS->getType())->getElementCount() ==		assert(cast<VectorType>(LHS->getType())->getElementCount() ==
cast<VectorType>(Inst.getType())->getElementCount());		cast<VectorType>(Inst.getType())->getElementCount());
▲ Show 20 Lines • Show All 2,765 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Remove DescaleClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 520136

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

[InstCombine] Remove Descale
ClosedPublic