<commit_before>//===- InstCombineMulDivRem.cpp -------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
// srem, urem, frem.
//
//===----------------------------------------------------------------------===//

#include "InstCombine.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
using namespace llvm;
using namespace PatternMatch;

#define DEBUG_TYPE "instcombine"


/// simplifyValueKnownNonZero - 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.
static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
                                        Instruction *CxtI) {
  // If V has multiple uses, then we would have to do more analysis to determine
  // if this is safe.  For example, the use could be in dynamically unreached
  // code.
  if (!V->hasOneUse()) return nullptr;

  bool MadeChange = false;

  // ((1 << A) >>u B) --> (1 << (A-B))
  // Because V cannot be zero, we know that B is less than A.
  Value *A = nullptr, *B = nullptr, *PowerOf2 = nullptr;
  if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))),
                      m_Value(B))) &&
      // The "1" can be any value known to be a power of 2.
      isKnownToBeAPowerOfTwo(PowerOf2, false, 0, IC.getAssumptionTracker(),
                             CxtI, IC.getDominatorTree())) {
    A = IC.Builder->CreateSub(A, B);
    return IC.Builder->CreateShl(PowerOf2, A);
  }

  // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
  // inexact.  Similarly for <<.
  if (BinaryOperator *I = dyn_cast<BinaryOperator>(V))
    if (I->isLogicalShift() && isKnownToBeAPowerOfTwo(I->getOperand(0), false,
                                                      0, IC.getAssumptionTracker(),
                                                      CxtI,
                                                      IC.getDominatorTree())) {
      // We know that this is an exact/nuw shift and that the input is a
      // non-zero context as well.
      if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
        I->setOperand(0, V2);
        MadeChange = true;
      }

      if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
        I->setIsExact();
        MadeChange = true;
      }

      if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
        I->setHasNoUnsignedWrap();
        MadeChange = true;
      }
    }

  // TODO: Lots more we could do here:
  //    If V is a phi node, we can call this on each of its operands.
  //    "select cond, X, 0" can simplify to "X".

  return MadeChange ? V : nullptr;
}


/// MultiplyOverflows - True if the multiply can not be expressed in an int
/// this size.
static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
  uint32_t W = C1->getBitWidth();
  APInt LHSExt = C1->getValue(), RHSExt = C2->getValue();
  if (sign) {
    LHSExt = LHSExt.sext(W * 2);
    RHSExt = RHSExt.sext(W * 2);
  } else {
    LHSExt = LHSExt.zext(W * 2);
    RHSExt = RHSExt.zext(W * 2);
  }

  APInt MulExt = LHSExt * RHSExt;

  if (!sign)
    return MulExt.ugt(APInt::getLowBitsSet(W * 2, W));

  APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
  APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
  return MulExt.slt(Min) || MulExt.sgt(Max);
}

/// \brief True if C2 is a multiple of C1. Quotient contains C2/C1.
static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
                       bool IsSigned) {
  assert(C1.getBitWidth() == C2.getBitWidth() &&
         "Inconsistent width of constants!");

  APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned);
  if (IsSigned)
    APInt::sdivrem(C1, C2, Quotient, Remainder);
  else
    APInt::udivrem(C1, C2, Quotient, Remainder);

  return Remainder.isMinValue();
}

/// \brief A helper routine of InstCombiner::visitMul().
///
/// If C is a vector of known powers of 2, then this function returns
/// a new vector obtained from C replacing each element with its logBase2.
/// Return a null pointer otherwise.
static Constant *getLogBase2Vector(ConstantDataVector *CV) {
  const APInt *IVal;
  SmallVector<Constant *, 4> Elts;

  for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) {
    Constant *Elt = CV->getElementAsConstant(I);
    if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
      return nullptr;
    Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2()));
  }

  return ConstantVector::get(Elts);
}

Instruction *InstCombiner::visitMul(BinaryOperator &I) {
  bool Changed = SimplifyAssociativeOrCommutative(I);
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);

  if (Value *V = SimplifyVectorOp(I))
    return ReplaceInstUsesWith(I, V);

  if (Value *V = SimplifyMulInst(Op0, Op1, DL, TLI, DT, AT))
    return ReplaceInstUsesWith(I, V);

  if (Value *V = SimplifyUsingDistributiveLaws(I))
    return ReplaceInstUsesWith(I, V);

  if (match(Op1, m_AllOnes()))  // X * -1 == 0 - X
    return BinaryOperator::CreateNeg(Op0, I.getName());

  // Also allow combining multiply instructions on vectors.
  {
    Value *NewOp;
    Constant *C1, *C2;
    const APInt *IVal;
    if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
                        m_Constant(C1))) &&
        match(C1, m_APInt(IVal)))
      // ((X << C1)*C2) == (X * (C2 << C1))
      return BinaryOperator::CreateMul(NewOp, ConstantExpr::getShl(C1, C2));

    if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
      Constant *NewCst = nullptr;
      if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2())
        // Replace X*(2^C) with X << C, where C is either a scalar or a splat.
        NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2());
      else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1))
        // Replace X*(2^C) with X << C, where C is a vector of known
        // constant powers of 2.
        NewCst = getLogBase2Vector(CV);

      if (NewCst) {
        BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
        if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap();
        if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap();
        return Shl;
      }
    }
  }

  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
    // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
    // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
    // The "* (2**n)" thus becomes a potential shifting opportunity.
    {
      const APInt &   Val = CI->getValue();
      const APInt &PosVal = Val.abs();
      if (Val.isNegative() && PosVal.isPowerOf2()) {<commit_msg>[InstCombine] Reformat if statements to comply with LLVM Coding Standards.<commit_after>//===- InstCombineMulDivRem.cpp -------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
// srem, urem, frem.
//
//===----------------------------------------------------------------------===//

#include "InstCombine.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
using namespace llvm;
using namespace PatternMatch;

#define DEBUG_TYPE "instcombine"


/// simplifyValueKnownNonZero - 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.
static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
                                        Instruction *CxtI) {
  // If V has multiple uses, then we would have to do more analysis to determine
  // if this is safe.  For example, the use could be in dynamically unreached
  // code.
  if (!V->hasOneUse()) return nullptr;

  bool MadeChange = false;

  // ((1 << A) >>u B) --> (1 << (A-B))
  // Because V cannot be zero, we know that B is less than A.
  Value *A = nullptr, *B = nullptr, *PowerOf2 = nullptr;
  if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))),
                      m_Value(B))) &&
      // The "1" can be any value known to be a power of 2.
      isKnownToBeAPowerOfTwo(PowerOf2, false, 0, IC.getAssumptionTracker(),
                             CxtI, IC.getDominatorTree())) {
    A = IC.Builder->CreateSub(A, B);
    return IC.Builder->CreateShl(PowerOf2, A);
  }

  // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
  // inexact.  Similarly for <<.
  if (BinaryOperator *I = dyn_cast<BinaryOperator>(V))
    if (I->isLogicalShift() && isKnownToBeAPowerOfTwo(I->getOperand(0), false,
                                                      0, IC.getAssumptionTracker(),
                                                      CxtI,
                                                      IC.getDominatorTree())) {
      // We know that this is an exact/nuw shift and that the input is a
      // non-zero context as well.
      if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
        I->setOperand(0, V2);
        MadeChange = true;
      }

      if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
        I->setIsExact();
        MadeChange = true;
      }

      if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
        I->setHasNoUnsignedWrap();
        MadeChange = true;
      }
    }

  // TODO: Lots more we could do here:
  //    If V is a phi node, we can call this on each of its operands.
  //    "select cond, X, 0" can simplify to "X".

  return MadeChange ? V : nullptr;
}


/// MultiplyOverflows - True if the multiply can not be expressed in an int
/// this size.
static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
  uint32_t W = C1->getBitWidth();
  APInt LHSExt = C1->getValue(), RHSExt = C2->getValue();
  if (sign) {
    LHSExt = LHSExt.sext(W * 2);
    RHSExt = RHSExt.sext(W * 2);
  } else {
    LHSExt = LHSExt.zext(W * 2);
    RHSExt = RHSExt.zext(W * 2);
  }

  APInt MulExt = LHSExt * RHSExt;

  if (!sign)
    return MulExt.ugt(APInt::getLowBitsSet(W * 2, W));

  APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
  APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
  return MulExt.slt(Min) || MulExt.sgt(Max);
}

/// \brief True if C2 is a multiple of C1. Quotient contains C2/C1.
static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
                       bool IsSigned) {
  assert(C1.getBitWidth() == C2.getBitWidth() &&
         "Inconsistent width of constants!");

  APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned);
  if (IsSigned)
    APInt::sdivrem(C1, C2, Quotient, Remainder);
  else
    APInt::udivrem(C1, C2, Quotient, Remainder);

  return Remainder.isMinValue();
}

/// \brief A helper routine of InstCombiner::visitMul().
///
/// If C is a vector of known powers of 2, then this function returns
/// a new vector obtained from C replacing each element with its logBase2.
/// Return a null pointer otherwise.
static Constant *getLogBase2Vector(ConstantDataVector *CV) {
  const APInt *IVal;
  SmallVector<Constant *, 4> Elts;

  for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) {
    Constant *Elt = CV->getElementAsConstant(I);
    if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
      return nullptr;
    Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2()));
  }

  return ConstantVector::get(Elts);
}

Instruction *InstCombiner::visitMul(BinaryOperator &I) {
  bool Changed = SimplifyAssociativeOrCommutative(I);
  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);

  if (Value *V = SimplifyVectorOp(I))
    return ReplaceInstUsesWith(I, V);

  if (Value *V = SimplifyMulInst(Op0, Op1, DL, TLI, DT, AT))
    return ReplaceInstUsesWith(I, V);

  if (Value *V = SimplifyUsingDistributiveLaws(I))
    return ReplaceInstUsesWith(I, V);

  if (match(Op1, m_AllOnes()))  // X * -1 == 0 - X
    return BinaryOperator::CreateNeg(Op0, I.getName());

  // Also allow combining multiply instructions on vectors.
  {
    Value *NewOp;
    Constant *C1, *C2;
    const APInt *IVal;
    if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
                        m_Constant(C1))) &&
        match(C1, m_APInt(IVal)))
      // ((X << C1)*C2) == (X * (C2 << C1))
      return BinaryOperator::CreateMul(NewOp, ConstantExpr::getShl(C1, C2));

    if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
      Constant *NewCst = nullptr;
      if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2())
        // Replace X*(2^C) with X << C, where C is either a scalar or a splat.
        NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2());
      else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1))
        // Replace X*(2^C) with X << C, where C is a vector of known
        // constant powers of 2.
        NewCst = getLogBase2Vector(CV);

      if (NewCst) {
        BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);

        if (I.hasNoSignedWrap())
          Shl->setHasNoSignedWrap();
        if (I.hasNoUnsignedWrap())
          Shl->setHasNoUnsignedWrap();

        return Shl;
      }
    }
  }

  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
    // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
    // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
    // The "* (2**n)" thus becomes a potential shifting opportunity.
    {
      const APInt &   Val = CI->getValue();
      const APInt &PosVal = Val.abs();
      if (Val.isNegative() && PosVal.isPowerOf2()) {
{'fraction_non_alphanumeric': 0.1667949884510394, 'fraction_numerical': 0.01231889129978302, 'mean_word_length': 2.4288456923446122, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 81, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5930813', 'n_tokens_mistral': 4874, 'n_tokens_neox': 4711, 'n_words': 1329}