diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h --- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h @@ -651,11 +651,6 @@ Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI); 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 { diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -1366,248 +1366,6 @@ 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(Val->getType()) && "Can only descale integers!"); - assert(cast(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*(Y*Z). Descaling X*(Y*8) by - // a factor of 4 will produce X*(Y*2). 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 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(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(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(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(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(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(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(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) { if (!isa(Inst.getType())) return nullptr;