InstCombineAddSub.cpp | Explore in Territory

//===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===//
//
// 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 add, fadd, sub, and fsub.
//
//===----------------------------------------------------------------------===//

#include "InstCombineInternal.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueTracking.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/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include <cassert>
#include <utility>

usingnamespacellvm;
usingnamespacePatternMatch;

#define DEBUG_TYPE …

namespace {

  /// Class representing coefficient of floating-point addend.
  /// This class needs to be highly efficient, which is especially true for
  /// the constructor. As of I write this comment, the cost of the default
  /// constructor is merely 4-byte-store-zero (Assuming compiler is able to
  /// perform write-merging).
  ///
  class FAddendCoef { … };

  /// FAddend is used to represent floating-point addend. An addend is
  /// represented as <C, V>, where the V is a symbolic value, and C is a
  /// constant coefficient. A constant addend is represented as <C, 0>.
  class FAddend { … };

  /// FAddCombine is the class for optimizing an unsafe fadd/fsub along
  /// with its neighboring at most two instructions.
  ///
  class FAddCombine { … };

} // end anonymous namespace

//===----------------------------------------------------------------------===//
//
// Implementation of
//    {FAddendCoef, FAddend, FAddition, FAddCombine}.
//
//===----------------------------------------------------------------------===//
FAddendCoef::~FAddendCoef() { … }

void FAddendCoef::set(const APFloat& C) { … }

void FAddendCoef::convertToFpType(const fltSemantics &Sem) { … }

APFloat FAddendCoef::createAPFloatFromInt(const fltSemantics &Sem, int Val) { … }

void FAddendCoef::operator=(const FAddendCoef &That) { … }

void FAddendCoef::operator+=(const FAddendCoef &That) { … }

void FAddendCoef::operator*=(const FAddendCoef &That) { … }

void FAddendCoef::negate() { … }

Value *FAddendCoef::getValue(Type *Ty) const { … }

// The definition of <Val>     Addends
// =========================================
//  A + B                     <1, A>, <1,B>
//  A - B                     <1, A>, <1,B>
//  0 - B                     <-1, B>
//  C * A,                    <C, A>
//  A + C                     <1, A> <C, NULL>
//  0 +/- 0                   <0, NULL> (corner case)
//
// Legend: A and B are not constant, C is constant
unsigned FAddend::drillValueDownOneStep
  (Value *Val, FAddend &Addend0, FAddend &Addend1) { … }

// Try to break *this* addend into two addends. e.g. Suppose this addend is
// <2.3, V>, and V = X + Y, by calling this function, we obtain two addends,
// i.e. <2.3, X> and <2.3, Y>.
unsigned FAddend::drillAddendDownOneStep
  (FAddend &Addend0, FAddend &Addend1) const { … }

Value *FAddCombine::simplify(Instruction *I) { … }

Value *FAddCombine::simplifyFAdd(AddendVect& Addends, unsigned InstrQuota) { … }

Value *FAddCombine::createNaryFAdd
  (const AddendVect &Opnds, unsigned InstrQuota) { … }

Value *FAddCombine::createFSub(Value *Opnd0, Value *Opnd1) { … }

Value *FAddCombine::createFNeg(Value *V) { … }

Value *FAddCombine::createFAdd(Value *Opnd0, Value *Opnd1) { … }

Value *FAddCombine::createFMul(Value *Opnd0, Value *Opnd1) { … }

void FAddCombine::createInstPostProc(Instruction *NewInstr, bool NoNumber) { … }

// Return the number of instruction needed to emit the N-ary addition.
// NOTE: Keep this function in sync with createAddendVal().
unsigned FAddCombine::calcInstrNumber(const AddendVect &Opnds) { … }

// Input Addend        Value           NeedNeg(output)
// ================================================================
// Constant C          C               false
// <+/-1, V>           V               coefficient is -1
// <2/-2, V>          "fadd V, V"      coefficient is -2
// <C, V>             "fmul V, C"      false
//
// NOTE: Keep this function in sync with FAddCombine::calcInstrNumber.
Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) { … }

// Checks if any operand is negative and we can convert add to sub.
// This function checks for following negative patterns
//   ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
//   ADD(XOR(AND(Z, C), C), 1) == NEG(OR(Z, ~C))
//   XOR(AND(Z, C), (C + 1)) == NEG(OR(Z, ~C)) if C is even
static Value *checkForNegativeOperand(BinaryOperator &I,
                                      InstCombiner::BuilderTy &Builder) { … }

/// Wrapping flags may allow combining constants separated by an extend.
static Instruction *foldNoWrapAdd(BinaryOperator &Add,
                                  InstCombiner::BuilderTy &Builder) { … }

Instruction *InstCombinerImpl::foldAddWithConstant(BinaryOperator &Add) { … }

// match variations of a^2 + 2*a*b + b^2
//
// to reuse the code between the FP and Int versions, the instruction OpCodes
//  and constant types have been turned into template parameters.
//
// Mul2Rhs: The constant to perform the multiplicative equivalent of X*2 with;
//  should be `m_SpecificFP(2.0)` for FP and `m_SpecificInt(1)` for Int
//  (we're matching `X<<1` instead of `X*2` for Int)
template <bool FP, typename Mul2Rhs>
static bool matchesSquareSum(BinaryOperator &I, Mul2Rhs M2Rhs, Value *&A,
                             Value *&B) { … }

// Fold integer variations of a^2 + 2*a*b + b^2 -> (a + b)^2
Instruction *InstCombinerImpl::foldSquareSumInt(BinaryOperator &I) { … }

// Fold floating point variations of a^2 + 2*a*b + b^2 -> (a + b)^2
// Requires `nsz` and `reassoc`.
Instruction *InstCombinerImpl::foldSquareSumFP(BinaryOperator &I) { … }

// Matches multiplication expression Op * C where C is a constant. Returns the
// constant value in C and the other operand in Op. Returns true if such a
// match is found.
static bool MatchMul(Value *E, Value *&Op, APInt &C) { … }

// Matches remainder expression Op % C where C is a constant. Returns the
// constant value in C and the other operand in Op. Returns the signedness of
// the remainder operation in IsSigned. Returns true if such a match is
// found.
static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) { … }

// Matches division expression Op / C with the given signedness as indicated
// by IsSigned, where C is a constant. Returns the constant value in C and the
// other operand in Op. Returns true if such a match is found.
static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) { … }

// Returns whether C0 * C1 with the given signedness overflows.
static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) { … }

// Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1)
// does not overflow.
// Simplifies (X / C0) * C1 + (X % C0) * C2 to
// (X / C0) * (C1 - C2 * C0) + X * C2
Value *InstCombinerImpl::SimplifyAddWithRemainder(BinaryOperator &I) { … }

/// Fold
///   (1 << NBits) - 1
/// Into:
///   ~(-(1 << NBits))
/// Because a 'not' is better for bit-tracking analysis and other transforms
/// than an 'add'. The new shl is always nsw, and is nuw if old `and` was.
static Instruction *canonicalizeLowbitMask(BinaryOperator &I,
                                           InstCombiner::BuilderTy &Builder) { … }

static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) { … }

// Transform:
//  (add A, (shl (neg B), Y))
//      -> (sub A, (shl B, Y))
static Instruction *combineAddSubWithShlAddSub(InstCombiner::BuilderTy &Builder,
                                               const BinaryOperator &I) { … }

/// Try to reduce signed division by power-of-2 to an arithmetic shift right.
static Instruction *foldAddToAshr(BinaryOperator &Add) { … }

Instruction *InstCombinerImpl::foldAddLikeCommutative(Value *LHS, Value *RHS,
                                                      bool NSW, bool NUW) { … }

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

/// This is a specialization of a more general transform from
/// foldUsingDistributiveLaws. If that code can be made to work optimally
/// for multi-use cases or propagating nsw/nuw, then we would not need this.
static Instruction *factorizeMathWithShlOps(BinaryOperator &I,
                                            InstCombiner::BuilderTy &Builder) { … }

/// Reduce a sequence of masked half-width multiplies to a single multiply.
/// ((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y
static Instruction *foldBoxMultiply(BinaryOperator &I) { … }

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

/// Eliminate an op from a linear interpolation (lerp) pattern.
static Instruction *factorizeLerp(BinaryOperator &I,
                                  InstCombiner::BuilderTy &Builder) { … }

/// Factor a common operand out of fadd/fsub of fmul/fdiv.
static Instruction *factorizeFAddFSub(BinaryOperator &I,
                                      InstCombiner::BuilderTy &Builder) { … }

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

/// Optimize pointer differences into the same array into a size.  Consider:
///  &A[10] - &A[0]: we should compile this to "10".  LHS/RHS are the pointer
/// operands to the ptrtoint instructions for the LHS/RHS of the subtract.
Value *InstCombinerImpl::OptimizePointerDifference(Value *LHS, Value *RHS,
                                                   Type *Ty, bool IsNUW) { … }

static Instruction *foldSubOfMinMax(BinaryOperator &I,
                                    InstCombiner::BuilderTy &Builder) { … }

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

/// This eliminates floating-point negation in either 'fneg(X)' or
/// 'fsub(-0.0, X)' form by combining into a constant operand.
static Instruction *foldFNegIntoConstant(Instruction &I, const DataLayout &DL) { … }

Instruction *InstCombinerImpl::hoistFNegAboveFMulFDiv(Value *FNegOp,
                                                      Instruction &FMFSource) { … }

Instruction *InstCombinerImpl::visitFNeg(UnaryOperator &I) { … }

Instruction *InstCombinerImpl::visitFSub(BinaryOperator &I) { … }
llvm/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
