llvm/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

//===- InstCombineMulDivRem.cpp -------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
// srem, urem, frem.
//
//===----------------------------------------------------------------------===//

#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>

#define DEBUG_TYPE …
#include "llvm/Transforms/Utils/InstructionWorklist.h"

usingnamespacellvm;
usingnamespacePatternMatch;

/// 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, InstCombinerImpl &IC,
                                        Instruction &CxtI) { … }

// TODO: This is a specific form of a much more general pattern.
//       We could detect a select with any binop identity constant, or we
//       could use SimplifyBinOp to see if either arm of the select reduces.
//       But that needs to be done carefully and/or while removing potential
//       reverse canonicalizations as in InstCombiner::foldSelectIntoOp().
static Value *foldMulSelectToNegate(BinaryOperator &I,
                                    InstCombiner::BuilderTy &Builder) { … }

/// Reduce integer multiplication patterns that contain a (+/-1 << Z) factor.
/// Callers are expected to call this twice to handle commuted patterns.
static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands,
                          InstCombiner::BuilderTy &Builder) { … }

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

Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::foldPowiReassoc(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::foldFMulReassoc(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::visitFMul(BinaryOperator &I) { … }

/// Fold a divide or remainder with a select instruction divisor when one of the
/// select operands is zero. In that case, we can use the other select operand
/// because div/rem by zero is undefined.
bool InstCombinerImpl::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) { … }

/// True if the multiply can not be expressed in an int this size.
static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
                              bool IsSigned) { … }

/// True if C1 is a multiple of C2. Quotient contains C1/C2.
static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
                       bool IsSigned) { … }

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

/// This function implements the transforms common to both integer division
/// instructions (udiv and sdiv). It is called by the visitors to those integer
/// division instructions.
/// Common integer divide transforms
Instruction *InstCombinerImpl::commonIDivTransforms(BinaryOperator &I) { … }

static const unsigned MaxDepth = …;

// Take the exact integer log2 of the value. If DoFold is true, create the
// actual instructions, otherwise return a non-null dummy value. Return nullptr
// on failure.
static Value *takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth,
                       bool AssumeNonZero, bool DoFold) { … }

/// 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 *narrowUDivURem(BinaryOperator &I,
                                   InstCombinerImpl &IC) { … }

Instruction *InstCombinerImpl::visitUDiv(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::visitSDiv(BinaryOperator &I) { … }

/// Remove negation and try to convert division into multiplication.
Instruction *InstCombinerImpl::foldFDivConstantDivisor(BinaryOperator &I) { … }

/// Remove negation and try to reassociate constant math.
static Instruction *foldFDivConstantDividend(BinaryOperator &I) { … }

/// Negate the exponent of pow/exp to fold division-by-pow() into multiply.
static Instruction *foldFDivPowDivisor(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 *foldFDivSqrtDivisor(BinaryOperator &I,
                                        InstCombiner::BuilderTy &Builder) { … }

Instruction *InstCombinerImpl::visitFDiv(BinaryOperator &I) { … }

// Variety of transform for:
//  (urem/srem (mul X, Y), (mul X, Z))
//  (urem/srem (shl X, Y), (shl X, Z))
//  (urem/srem (shl Y, X), (shl Z, X))
// NB: The shift cases are really just extensions of the mul case. We treat
// shift as Val * (1 << Amt).
static Instruction *simplifyIRemMulShl(BinaryOperator &I,
                                       InstCombinerImpl &IC) { … }

/// This function implements the transforms common to both integer remainder
/// instructions (urem and srem). It is called by the visitors to those integer
/// remainder instructions.
/// Common integer remainder transforms
Instruction *InstCombinerImpl::commonIRemTransforms(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::visitURem(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::visitSRem(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::visitFRem(BinaryOperator &I) { … }