DAGCombiner.cpp

Go to the documentation of this file.

//===- DAGCombiner.cpp - Implement a DAG node combiner --------------------===//
//
// 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 pass combines dag nodes to form fewer, simpler DAG nodes.  It can be run
// both before and after the DAG is legalized.
//
// This pass is not a substitute for the LLVM IR instcombine pass. This pass is
// primarily intended to handle simplification opportunities that are implicit
// in the LLVM IR and exposed by the various codegen lowering phases.
//
//===----------------------------------------------------------------------===//
 
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/CodeGen/ByteProvider.h"
#include "llvm/CodeGen/DAGCombine.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/SDPatternMatch.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/CodeGen/SelectionDAGTargetInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/CodeGenTypes/MachineValueType.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Metadata.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iterator>
#include <optional>
#include <string>
#include <tuple>
#include <utility>
#include <variant>
 
#include "MatchContext.h"
 
using namespace llvm;
using namespace llvm::SDPatternMatch;
 
#define DEBUG_TYPE "dagcombine"
 
STATISTIC(NodesCombined   , "Number of dag nodes combined");
STATISTIC(PreIndexedNodes , "Number of pre-indexed nodes created");
STATISTIC(PostIndexedNodes, "Number of post-indexed nodes created");
STATISTIC(OpsNarrowed     , "Number of load/op/store narrowed");
STATISTIC(LdStFP2Int      , "Number of fp load/store pairs transformed to int");
STATISTIC(SlicedLoads, "Number of load sliced");
STATISTIC(NumFPLogicOpsConv, "Number of logic ops converted to fp ops");
 
DEBUG_COUNTER(DAGCombineCounter, "dagcombine",
              "Controls whether a DAG combine is performed for a node");
 
static cl::opt<bool>
CombinerGlobalAA("combiner-global-alias-analysis", cl::Hidden,
                 cl::desc("Enable DAG combiner's use of IR alias analysis"));
 
static cl::opt<bool>
UseTBAA("combiner-use-tbaa", cl::Hidden, cl::init(true),
        cl::desc("Enable DAG combiner's use of TBAA"));
 
#ifndef NDEBUG
static cl::opt<std::string>
CombinerAAOnlyFunc("combiner-aa-only-func", cl::Hidden,
                   cl::desc("Only use DAG-combiner alias analysis in this"
                            " function"));
#endif
 
/// Hidden option to stress test load slicing, i.e., when this option
/// is enabled, load slicing bypasses most of its profitability guards.
static cl::opt<bool>
StressLoadSlicing("combiner-stress-load-slicing", cl::Hidden,
                  cl::desc("Bypass the profitability model of load slicing"),
                  cl::init(false));
 
static cl::opt<bool>
  MaySplitLoadIndex("combiner-split-load-index", cl::Hidden, cl::init(true),
                    cl::desc("DAG combiner may split indexing from loads"));
 
static cl::opt<bool>
    EnableStoreMerging("combiner-store-merging", cl::Hidden, cl::init(true),
                       cl::desc("DAG combiner enable merging multiple stores "
                                "into a wider store"));
 
static cl::opt<unsigned> TokenFactorInlineLimit(
    "combiner-tokenfactor-inline-limit", cl::Hidden, cl::init(2048),
    cl::desc("Limit the number of operands to inline for Token Factors"));
 
static cl::opt<unsigned> StoreMergeDependenceLimit(
    "combiner-store-merge-dependence-limit", cl::Hidden, cl::init(10),
    cl::desc("Limit the number of times for the same StoreNode and RootNode "
             "to bail out in store merging dependence check"));
 
static cl::opt<bool> EnableReduceLoadOpStoreWidth(
    "combiner-reduce-load-op-store-width", cl::Hidden, cl::init(true),
    cl::desc("DAG combiner enable reducing the width of load/op/store "
             "sequence"));
static cl::opt<bool> ReduceLoadOpStoreWidthForceNarrowingProfitable(
    "combiner-reduce-load-op-store-width-force-narrowing-profitable",
    cl::Hidden, cl::init(false),
    cl::desc("DAG combiner force override the narrowing profitable check when"
             "reducing the width of load/op/store sequences"));
 
static cl::opt<bool> EnableShrinkLoadReplaceStoreWithStore(
    "combiner-shrink-load-replace-store-with-store", cl::Hidden, cl::init(true),
    cl::desc("DAG combiner enable load/<replace bytes>/store with "
             "a narrower store"));
 
static cl::opt<bool> EnableVectorFCopySignExtendRound(
    "combiner-vector-fcopysign-extend-round", cl::Hidden, cl::init(false),
    cl::desc(
        "Enable merging extends and rounds into FCOPYSIGN on vector types"));
namespace {
 
  class DAGCombiner {
    SelectionDAG &DAG;
    const TargetLowering &TLI;
    const SelectionDAGTargetInfo *STI;
    CombineLevel Level = BeforeLegalizeTypes;
    CodeGenOptLevel OptLevel;
    bool LegalDAG = false;
    bool LegalOperations = false;
    bool LegalTypes = false;
    bool ForCodeSize;
    bool DisableGenericCombines;
 
    /// Worklist of all of the nodes that need to be simplified.
    ///
    /// This must behave as a stack -- new nodes to process are pushed onto the
    /// back and when processing we pop off of the back.
    ///
    /// The worklist will not contain duplicates but may contain null entries
    /// due to nodes being deleted from the underlying DAG. For fast lookup and
    /// deduplication, the index of the node in this vector is stored in the
    /// node in SDNode::CombinerWorklistIndex.
    SmallVector<SDNode *, 64> Worklist;
 
    /// This records all nodes attempted to be added to the worklist since we
    /// considered a new worklist entry. As we keep do not add duplicate nodes
    /// in the worklist, this is different from the tail of the worklist.
    SmallSetVector<SDNode *, 32> PruningList;
 
    /// Map from candidate StoreNode to the pair of RootNode and count.
    /// The count is used to track how many times we have seen the StoreNode
    /// with the same RootNode bail out in dependence check. If we have seen
    /// the bail out for the same pair many times over a limit, we won't
    /// consider the StoreNode with the same RootNode as store merging
    /// candidate again.
    DenseMap<SDNode *, std::pair<SDNode *, unsigned>> StoreRootCountMap;
 
    // AA - Used for DAG load/store alias analysis.
    AliasAnalysis *AA;
 
    /// This caches all chains that have already been processed in
    /// DAGCombiner::getStoreMergeCandidates() and found to have no mergeable
    /// stores candidates.
    SmallPtrSet<SDNode *, 4> ChainsWithoutMergeableStores;
 
    /// When an instruction is simplified, add all users of the instruction to
    /// the work lists because they might get more simplified now.
    void AddUsersToWorklist(SDNode *N) {
      for (SDNode *Node : N->users())
        AddToWorklist(Node);
    }
 
    /// Convenient shorthand to add a node and all of its user to the worklist.
    void AddToWorklistWithUsers(SDNode *N) {
      AddUsersToWorklist(N);
      AddToWorklist(N);
    }
 
    // Prune potentially dangling nodes. This is called after
    // any visit to a node, but should also be called during a visit after any
    // failed combine which may have created a DAG node.
    void clearAddedDanglingWorklistEntries() {
      // Check any nodes added to the worklist to see if they are prunable.
      while (!PruningList.empty()) {
        auto *N = PruningList.pop_back_val();
        if (N->use_empty())
          recursivelyDeleteUnusedNodes(N);
      }
    }
 
    SDNode *getNextWorklistEntry() {
      // Before we do any work, remove nodes that are not in use.
      clearAddedDanglingWorklistEntries();
      SDNode *N = nullptr;
      // The Worklist holds the SDNodes in order, but it may contain null
      // entries.
      while (!N && !Worklist.empty()) {
        N = Worklist.pop_back_val();
      }
 
      if (N) {
        assert(N->getCombinerWorklistIndex() >= 0 &&
               "Found a worklist entry without a corresponding map entry!");
        // Set to -2 to indicate that we combined the node.
        N->setCombinerWorklistIndex(-2);
      }
      return N;
    }
 
    /// Call the node-specific routine that folds each particular type of node.
    SDValue visit(SDNode *N);
 
  public:
    DAGCombiner(SelectionDAG &D, AliasAnalysis *AA, CodeGenOptLevel OL)
        : DAG(D), TLI(D.getTargetLoweringInfo()),
          STI(D.getSubtarget().getSelectionDAGInfo()), OptLevel(OL), AA(AA) {
      ForCodeSize = DAG.shouldOptForSize();
      DisableGenericCombines = STI && STI->disableGenericCombines(OptLevel);
 
      MaximumLegalStoreInBits = 0;
      // We use the minimum store size here, since that's all we can guarantee
      // for the scalable vector types.
      for (MVT VT : MVT::all_valuetypes())
        if (EVT(VT).isSimple() && VT != MVT::Other &&
            TLI.isTypeLegal(EVT(VT)) &&
            VT.getSizeInBits().getKnownMinValue() >= MaximumLegalStoreInBits)
          MaximumLegalStoreInBits = VT.getSizeInBits().getKnownMinValue();
    }
 
    void ConsiderForPruning(SDNode *N) {
      // Mark this for potential pruning.
      PruningList.insert(N);
    }
 
    /// Add to the worklist making sure its instance is at the back (next to be
    /// processed.)
    void AddToWorklist(SDNode *N, bool IsCandidateForPruning = true,
                       bool SkipIfCombinedBefore = false) {
      assert(N->getOpcode() != ISD::DELETED_NODE &&
             "Deleted Node added to Worklist");
 
      // Skip handle nodes as they can't usefully be combined and confuse the
      // zero-use deletion strategy.
      if (N->getOpcode() == ISD::HANDLENODE)
        return;
 
      if (SkipIfCombinedBefore && N->getCombinerWorklistIndex() == -2)
        return;
 
      if (IsCandidateForPruning)
        ConsiderForPruning(N);
 
      if (N->getCombinerWorklistIndex() < 0) {
        N->setCombinerWorklistIndex(Worklist.size());
        Worklist.push_back(N);
      }
    }
 
    /// Remove all instances of N from the worklist.
    void removeFromWorklist(SDNode *N) {
      PruningList.remove(N);
      StoreRootCountMap.erase(N);
 
      int WorklistIndex = N->getCombinerWorklistIndex();
      // If not in the worklist, the index might be -1 or -2 (was combined
      // before). As the node gets deleted anyway, there's no need to update
      // the index.
      if (WorklistIndex < 0)
        return; // Not in the worklist.
 
      // Null out the entry rather than erasing it to avoid a linear operation.
      Worklist[WorklistIndex] = nullptr;
      N->setCombinerWorklistIndex(-1);
    }
 
    void deleteAndRecombine(SDNode *N);
    bool recursivelyDeleteUnusedNodes(SDNode *N);
 
    /// Replaces all uses of the results of one DAG node with new values.
    SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
                      bool AddTo = true);
 
    /// Replaces all uses of the results of one DAG node with new values.
    SDValue CombineTo(SDNode *N, SDValue Res, bool AddTo = true) {
      return CombineTo(N, &Res, 1, AddTo);
    }
 
    /// Replaces all uses of the results of one DAG node with new values.
    SDValue CombineTo(SDNode *N, SDValue Res0, SDValue Res1,
                      bool AddTo = true) {
      SDValue To[] = { Res0, Res1 };
      return CombineTo(N, To, 2, AddTo);
    }
 
    void CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO);
 
  private:
    unsigned MaximumLegalStoreInBits;
 
    /// Check the specified integer node value to see if it can be simplified or
    /// if things it uses can be simplified by bit propagation.
    /// If so, return true.
    bool SimplifyDemandedBits(SDValue Op) {
      unsigned BitWidth = Op.getScalarValueSizeInBits();
      APInt DemandedBits = APInt::getAllOnes(BitWidth);
      return SimplifyDemandedBits(Op, DemandedBits);
    }
 
    bool SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits) {
      EVT VT = Op.getValueType();
      APInt DemandedElts = VT.isFixedLengthVector()
                               ? APInt::getAllOnes(VT.getVectorNumElements())
                               : APInt(1, 1);
      return SimplifyDemandedBits(Op, DemandedBits, DemandedElts, false);
    }
 
    /// Check the specified vector node value to see if it can be simplified or
    /// if things it uses can be simplified as it only uses some of the
    /// elements. If so, return true.
    bool SimplifyDemandedVectorElts(SDValue Op) {
      // TODO: For now just pretend it cannot be simplified.
      if (Op.getValueType().isScalableVector())
        return false;
 
      unsigned NumElts = Op.getValueType().getVectorNumElements();
      APInt DemandedElts = APInt::getAllOnes(NumElts);
      return SimplifyDemandedVectorElts(Op, DemandedElts);
    }
 
    bool SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
                              const APInt &DemandedElts,
                              bool AssumeSingleUse = false);
    bool SimplifyDemandedVectorElts(SDValue Op, const APInt &DemandedElts,
                                    bool AssumeSingleUse = false);
 
    bool CombineToPreIndexedLoadStore(SDNode *N);
    bool CombineToPostIndexedLoadStore(SDNode *N);
    SDValue SplitIndexingFromLoad(LoadSDNode *LD);
    bool SliceUpLoad(SDNode *N);
 
    // Looks up the chain to find a unique (unaliased) store feeding the passed
    // load. If no such store is found, returns a nullptr.
    // Note: This will look past a CALLSEQ_START if the load is chained to it so
    //       so that it can find stack stores for byval params.
    StoreSDNode *getUniqueStoreFeeding(LoadSDNode *LD, int64_t &Offset);
    // Scalars have size 0 to distinguish from singleton vectors.
    SDValue ForwardStoreValueToDirectLoad(LoadSDNode *LD);
    bool getTruncatedStoreValue(StoreSDNode *ST, SDValue &Val);
    bool extendLoadedValueToExtension(LoadSDNode *LD, SDValue &Val);
 
    /// Replace an ISD::EXTRACT_VECTOR_ELT of a load with a narrowed
    ///   load.
    ///
    /// \param EVE ISD::EXTRACT_VECTOR_ELT to be replaced.
    /// \param InVecVT type of the input vector to EVE with bitcasts resolved.
    /// \param EltNo index of the vector element to load.
    /// \param OriginalLoad load that EVE came from to be replaced.
    /// \returns EVE on success SDValue() on failure.
    SDValue scalarizeExtractedVectorLoad(SDNode *EVE, EVT InVecVT,
                                         SDValue EltNo,
                                         LoadSDNode *OriginalLoad);
    void ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad);
    SDValue PromoteOperand(SDValue Op, EVT PVT, bool &Replace);
    SDValue SExtPromoteOperand(SDValue Op, EVT PVT);
    SDValue ZExtPromoteOperand(SDValue Op, EVT PVT);
    SDValue PromoteIntBinOp(SDValue Op);
    SDValue PromoteIntShiftOp(SDValue Op);
    SDValue PromoteExtend(SDValue Op);
    bool PromoteLoad(SDValue Op);
 
    SDValue foldShiftToAvg(SDNode *N);
 
    SDValue combineMinNumMaxNum(const SDLoc &DL, EVT VT, SDValue LHS,
                                SDValue RHS, SDValue True, SDValue False,
                                ISD::CondCode CC);
 
    /// Call the node-specific routine that knows how to fold each
    /// particular type of node. If that doesn't do anything, try the
    /// target-specific DAG combines.
    SDValue combine(SDNode *N);
 
    // Visitation implementation - Implement dag node combining for different
    // node types.  The semantics are as follows:
    // Return Value:
    //   SDValue.getNode() == 0 - No change was made
    //   SDValue.getNode() == N - N was replaced, is dead and has been handled.
    //   otherwise              - N should be replaced by the returned Operand.
    //
    SDValue visitTokenFactor(SDNode *N);
    SDValue visitMERGE_VALUES(SDNode *N);
    SDValue visitADD(SDNode *N);
    SDValue visitADDLike(SDNode *N);
    SDValue visitADDLikeCommutative(SDValue N0, SDValue N1, SDNode *LocReference);
    SDValue visitSUB(SDNode *N);
    SDValue visitADDSAT(SDNode *N);
    SDValue visitSUBSAT(SDNode *N);
    SDValue visitADDC(SDNode *N);
    SDValue visitADDO(SDNode *N);
    SDValue visitUADDOLike(SDValue N0, SDValue N1, SDNode *N);
    SDValue visitSUBC(SDNode *N);
    SDValue visitSUBO(SDNode *N);
    SDValue visitADDE(SDNode *N);
    SDValue visitUADDO_CARRY(SDNode *N);
    SDValue visitSADDO_CARRY(SDNode *N);
    SDValue visitUADDO_CARRYLike(SDValue N0, SDValue N1, SDValue CarryIn,
                                 SDNode *N);
    SDValue visitSADDO_CARRYLike(SDValue N0, SDValue N1, SDValue CarryIn,
                                 SDNode *N);
    SDValue visitSUBE(SDNode *N);
    SDValue visitUSUBO_CARRY(SDNode *N);
    SDValue visitSSUBO_CARRY(SDNode *N);
    template <class MatchContextClass> SDValue visitMUL(SDNode *N);
    SDValue visitMULFIX(SDNode *N);
    SDValue useDivRem(SDNode *N);
    SDValue visitSDIV(SDNode *N);
    SDValue visitSDIVLike(SDValue N0, SDValue N1, SDNode *N);
    SDValue visitUDIV(SDNode *N);
    SDValue visitUDIVLike(SDValue N0, SDValue N1, SDNode *N);
    SDValue visitREM(SDNode *N);
    SDValue visitMULHU(SDNode *N);
    SDValue visitMULHS(SDNode *N);
    SDValue visitAVG(SDNode *N);
    SDValue visitABD(SDNode *N);
    SDValue visitSMUL_LOHI(SDNode *N);
    SDValue visitUMUL_LOHI(SDNode *N);
    SDValue visitMULO(SDNode *N);
    SDValue visitIMINMAX(SDNode *N);
    SDValue visitAND(SDNode *N);
    SDValue visitANDLike(SDValue N0, SDValue N1, SDNode *N);
    SDValue visitOR(SDNode *N);
    SDValue visitORLike(SDValue N0, SDValue N1, const SDLoc &DL);
    SDValue visitXOR(SDNode *N);
    SDValue SimplifyVCastOp(SDNode *N, const SDLoc &DL);
    SDValue SimplifyVBinOp(SDNode *N, const SDLoc &DL);
    SDValue visitSHL(SDNode *N);
    SDValue visitSRA(SDNode *N);
    SDValue visitSRL(SDNode *N);
    SDValue visitFunnelShift(SDNode *N);
    SDValue visitSHLSAT(SDNode *N);
    SDValue visitRotate(SDNode *N);
    SDValue visitABS(SDNode *N);
    SDValue visitBSWAP(SDNode *N);
    SDValue visitBITREVERSE(SDNode *N);
    SDValue visitCTLZ(SDNode *N);
    SDValue visitCTLZ_ZERO_UNDEF(SDNode *N);
    SDValue visitCTTZ(SDNode *N);
    SDValue visitCTTZ_ZERO_UNDEF(SDNode *N);
    SDValue visitCTPOP(SDNode *N);
    SDValue visitSELECT(SDNode *N);
    SDValue visitVSELECT(SDNode *N);
    SDValue visitVP_SELECT(SDNode *N);
    SDValue visitSELECT_CC(SDNode *N);
    SDValue visitSETCC(SDNode *N);
    SDValue visitSETCCCARRY(SDNode *N);
    SDValue visitSIGN_EXTEND(SDNode *N);
    SDValue visitZERO_EXTEND(SDNode *N);
    SDValue visitANY_EXTEND(SDNode *N);
    SDValue visitAssertExt(SDNode *N);
    SDValue visitAssertAlign(SDNode *N);
    SDValue visitSIGN_EXTEND_INREG(SDNode *N);
    SDValue visitEXTEND_VECTOR_INREG(SDNode *N);
    SDValue visitTRUNCATE(SDNode *N);
    SDValue visitTRUNCATE_USAT_U(SDNode *N);
    SDValue visitBITCAST(SDNode *N);
    SDValue visitFREEZE(SDNode *N);
    SDValue visitBUILD_PAIR(SDNode *N);
    SDValue visitFADD(SDNode *N);
    SDValue visitVP_FADD(SDNode *N);
    SDValue visitVP_FSUB(SDNode *N);
    SDValue visitSTRICT_FADD(SDNode *N);
    SDValue visitFSUB(SDNode *N);
    SDValue visitFMUL(SDNode *N);
    template <class MatchContextClass> SDValue visitFMA(SDNode *N);
    SDValue visitFMAD(SDNode *N);
    SDValue visitFDIV(SDNode *N);
    SDValue visitFREM(SDNode *N);
    SDValue visitFSQRT(SDNode *N);
    SDValue visitFCOPYSIGN(SDNode *N);
    SDValue visitFPOW(SDNode *N);
    SDValue visitFCANONICALIZE(SDNode *N);
    SDValue visitSINT_TO_FP(SDNode *N);
    SDValue visitUINT_TO_FP(SDNode *N);
    SDValue visitFP_TO_SINT(SDNode *N);
    SDValue visitFP_TO_UINT(SDNode *N);
    SDValue visitXROUND(SDNode *N);
    SDValue visitFP_ROUND(SDNode *N);
    SDValue visitFP_EXTEND(SDNode *N);
    SDValue visitFNEG(SDNode *N);
    SDValue visitFABS(SDNode *N);
    SDValue visitFCEIL(SDNode *N);
    SDValue visitFTRUNC(SDNode *N);
    SDValue visitFFREXP(SDNode *N);
    SDValue visitFFLOOR(SDNode *N);
    SDValue visitFMinMax(SDNode *N);
    SDValue visitBRCOND(SDNode *N);
    SDValue visitBR_CC(SDNode *N);
    SDValue visitLOAD(SDNode *N);
 
    SDValue replaceStoreChain(StoreSDNode *ST, SDValue BetterChain);
    SDValue replaceStoreOfFPConstant(StoreSDNode *ST);
    SDValue replaceStoreOfInsertLoad(StoreSDNode *ST);
 
    bool refineExtractVectorEltIntoMultipleNarrowExtractVectorElts(SDNode *N);
 
    SDValue visitSTORE(SDNode *N);
    SDValue visitATOMIC_STORE(SDNode *N);
    SDValue visitLIFETIME_END(SDNode *N);
    SDValue visitINSERT_VECTOR_ELT(SDNode *N);
    SDValue visitEXTRACT_VECTOR_ELT(SDNode *N);
    SDValue visitBUILD_VECTOR(SDNode *N);
    SDValue visitCONCAT_VECTORS(SDNode *N);
    SDValue visitEXTRACT_SUBVECTOR(SDNode *N);
    SDValue visitVECTOR_SHUFFLE(SDNode *N);
    SDValue visitSCALAR_TO_VECTOR(SDNode *N);
    SDValue visitINSERT_SUBVECTOR(SDNode *N);
    SDValue visitVECTOR_COMPRESS(SDNode *N);
    SDValue visitMLOAD(SDNode *N);
    SDValue visitMSTORE(SDNode *N);
    SDValue visitMGATHER(SDNode *N);
    SDValue visitMSCATTER(SDNode *N);
    SDValue visitMHISTOGRAM(SDNode *N);
    SDValue visitVPGATHER(SDNode *N);
    SDValue visitVPSCATTER(SDNode *N);
    SDValue visitVP_STRIDED_LOAD(SDNode *N);
    SDValue visitVP_STRIDED_STORE(SDNode *N);
    SDValue visitFP_TO_FP16(SDNode *N);
    SDValue visitFP16_TO_FP(SDNode *N);
    SDValue visitFP_TO_BF16(SDNode *N);
    SDValue visitBF16_TO_FP(SDNode *N);
    SDValue visitVECREDUCE(SDNode *N);
    SDValue visitVPOp(SDNode *N);
    SDValue visitGET_FPENV_MEM(SDNode *N);
    SDValue visitSET_FPENV_MEM(SDNode *N);
 
    template <class MatchContextClass>
    SDValue visitFADDForFMACombine(SDNode *N);
    template <class MatchContextClass>
    SDValue visitFSUBForFMACombine(SDNode *N);
    SDValue visitFMULForFMADistributiveCombine(SDNode *N);
 
    SDValue XformToShuffleWithZero(SDNode *N);
    bool reassociationCanBreakAddressingModePattern(unsigned Opc,
                                                    const SDLoc &DL,
                                                    SDNode *N,
                                                    SDValue N0,
                                                    SDValue N1);
    SDValue reassociateOpsCommutative(unsigned Opc, const SDLoc &DL, SDValue N0,
                                      SDValue N1, SDNodeFlags Flags);
    SDValue reassociateOps(unsigned Opc, const SDLoc &DL, SDValue N0,
                           SDValue N1, SDNodeFlags Flags);
    SDValue reassociateReduction(unsigned RedOpc, unsigned Opc, const SDLoc &DL,
                                 EVT VT, SDValue N0, SDValue N1,
                                 SDNodeFlags Flags = SDNodeFlags());
 
    SDValue visitShiftByConstant(SDNode *N);
 
    SDValue foldSelectOfConstants(SDNode *N);
    SDValue foldVSelectOfConstants(SDNode *N);
    SDValue foldBinOpIntoSelect(SDNode *BO);
    bool SimplifySelectOps(SDNode *SELECT, SDValue LHS, SDValue RHS);
    SDValue hoistLogicOpWithSameOpcodeHands(SDNode *N);
    SDValue SimplifySelect(const SDLoc &DL, SDValue N0, SDValue N1, SDValue N2);
    SDValue SimplifySelectCC(const SDLoc &DL, SDValue N0, SDValue N1,
                             SDValue N2, SDValue N3, ISD::CondCode CC,
                             bool NotExtCompare = false);
    SDValue convertSelectOfFPConstantsToLoadOffset(
        const SDLoc &DL, SDValue N0, SDValue N1, SDValue N2, SDValue N3,
        ISD::CondCode CC);
    SDValue foldSignChangeInBitcast(SDNode *N);
    SDValue foldSelectCCToShiftAnd(const SDLoc &DL, SDValue N0, SDValue N1,
                                   SDValue N2, SDValue N3, ISD::CondCode CC);
    SDValue foldSelectOfBinops(SDNode *N);
    SDValue foldSextSetcc(SDNode *N);
    SDValue foldLogicOfSetCCs(bool IsAnd, SDValue N0, SDValue N1,
                              const SDLoc &DL);
    SDValue foldSubToUSubSat(EVT DstVT, SDNode *N, const SDLoc &DL);
    SDValue foldABSToABD(SDNode *N, const SDLoc &DL);
    SDValue foldSelectToABD(SDValue LHS, SDValue RHS, SDValue True,
                            SDValue False, ISD::CondCode CC, const SDLoc &DL);
    SDValue unfoldMaskedMerge(SDNode *N);
    SDValue unfoldExtremeBitClearingToShifts(SDNode *N);
    SDValue SimplifySetCC(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
                          const SDLoc &DL, bool foldBooleans);
    SDValue rebuildSetCC(SDValue N);
 
    bool isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
                           SDValue &CC, bool MatchStrict = false) const;
    bool isOneUseSetCC(SDValue N) const;
 
    SDValue foldAddToAvg(SDNode *N, const SDLoc &DL);
    SDValue foldSubToAvg(SDNode *N, const SDLoc &DL);
 
    SDValue SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
                                         unsigned HiOp);
    SDValue CombineConsecutiveLoads(SDNode *N, EVT VT);
    SDValue foldBitcastedFPLogic(SDNode *N, SelectionDAG &DAG,
                                 const TargetLowering &TLI);
 
    SDValue CombineExtLoad(SDNode *N);
    SDValue CombineZExtLogicopShiftLoad(SDNode *N);
    SDValue combineRepeatedFPDivisors(SDNode *N);
    SDValue combineFMulOrFDivWithIntPow2(SDNode *N);
    SDValue mergeInsertEltWithShuffle(SDNode *N, unsigned InsIndex);
    SDValue combineInsertEltToShuffle(SDNode *N, unsigned InsIndex);
    SDValue combineInsertEltToLoad(SDNode *N, unsigned InsIndex);
    SDValue ConstantFoldBITCASTofBUILD_VECTOR(SDNode *, EVT);
    SDValue BuildSDIV(SDNode *N);
    SDValue BuildSDIVPow2(SDNode *N);
    SDValue BuildUDIV(SDNode *N);
    SDValue BuildSREMPow2(SDNode *N);
    SDValue buildOptimizedSREM(SDValue N0, SDValue N1, SDNode *N);
    SDValue BuildLogBase2(SDValue V, const SDLoc &DL,
                          bool KnownNeverZero = false,
                          bool InexpensiveOnly = false,
                          std::optional<EVT> OutVT = std::nullopt);
    SDValue BuildDivEstimate(SDValue N, SDValue Op, SDNodeFlags Flags);
    SDValue buildRsqrtEstimate(SDValue Op, SDNodeFlags Flags);
    SDValue buildSqrtEstimate(SDValue Op, SDNodeFlags Flags);
    SDValue buildSqrtEstimateImpl(SDValue Op, SDNodeFlags Flags, bool Recip);
    SDValue buildSqrtNROneConst(SDValue Arg, SDValue Est, unsigned Iterations,
                                SDNodeFlags Flags, bool Reciprocal);
    SDValue buildSqrtNRTwoConst(SDValue Arg, SDValue Est, unsigned Iterations,
                                SDNodeFlags Flags, bool Reciprocal);
    SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
                               bool DemandHighBits = true);
    SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
    SDValue MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
                              SDValue InnerPos, SDValue InnerNeg, bool HasPos,
                              unsigned PosOpcode, unsigned NegOpcode,
                              const SDLoc &DL);
    SDValue MatchFunnelPosNeg(SDValue N0, SDValue N1, SDValue Pos, SDValue Neg,
                              SDValue InnerPos, SDValue InnerNeg, bool HasPos,
                              unsigned PosOpcode, unsigned NegOpcode,
                              const SDLoc &DL);
    SDValue MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL);
    SDValue MatchLoadCombine(SDNode *N);
    SDValue mergeTruncStores(StoreSDNode *N);
    SDValue reduceLoadWidth(SDNode *N);
    SDValue ReduceLoadOpStoreWidth(SDNode *N);
    SDValue splitMergedValStore(StoreSDNode *ST);
    SDValue TransformFPLoadStorePair(SDNode *N);
    SDValue convertBuildVecZextToZext(SDNode *N);
    SDValue convertBuildVecZextToBuildVecWithZeros(SDNode *N);
    SDValue reduceBuildVecExtToExtBuildVec(SDNode *N);
    SDValue reduceBuildVecTruncToBitCast(SDNode *N);
    SDValue reduceBuildVecToShuffle(SDNode *N);
    SDValue createBuildVecShuffle(const SDLoc &DL, SDNode *N,
                                  ArrayRef<int> VectorMask, SDValue VecIn1,
                                  SDValue VecIn2, unsigned LeftIdx,
                                  bool DidSplitVec);
    SDValue matchVSelectOpSizesWithSetCC(SDNode *Cast);
 
    /// Walk up chain skipping non-aliasing memory nodes,
    /// looking for aliasing nodes and adding them to the Aliases vector.
    void GatherAllAliases(SDNode *N, SDValue OriginalChain,
                          SmallVectorImpl<SDValue> &Aliases);
 
    /// Return true if there is any possibility that the two addresses overlap.
    bool mayAlias(SDNode *Op0, SDNode *Op1) const;
 
    /// Walk up chain skipping non-aliasing memory nodes, looking for a better
    /// chain (aliasing node.)
    SDValue FindBetterChain(SDNode *N, SDValue Chain);
 
    /// Try to replace a store and any possibly adjacent stores on
    /// consecutive chains with better chains. Return true only if St is
    /// replaced.
    ///
    /// Notice that other chains may still be replaced even if the function
    /// returns false.
    bool findBetterNeighborChains(StoreSDNode *St);
 
    // Helper for findBetterNeighborChains. Walk up store chain add additional
    // chained stores that do not overlap and can be parallelized.
    bool parallelizeChainedStores(StoreSDNode *St);
 
    /// Holds a pointer to an LSBaseSDNode as well as information on where it
    /// is located in a sequence of memory operations connected by a chain.
    struct MemOpLink {
      // Ptr to the mem node.
      LSBaseSDNode *MemNode;
 
      // Offset from the base ptr.
      int64_t OffsetFromBase;
 
      MemOpLink(LSBaseSDNode *N, int64_t Offset)
          : MemNode(N), OffsetFromBase(Offset) {}
    };
 
    // Classify the origin of a stored value.
    enum class StoreSource { Unknown, Constant, Extract, Load };
    StoreSource getStoreSource(SDValue StoreVal) {
      switch (StoreVal.getOpcode()) {
      case ISD::Constant:
      case ISD::ConstantFP:
        return StoreSource::Constant;
      case ISD::BUILD_VECTOR:
        if (ISD::isBuildVectorOfConstantSDNodes(StoreVal.getNode()) ||
            ISD::isBuildVectorOfConstantFPSDNodes(StoreVal.getNode()))
          return StoreSource::Constant;
        return StoreSource::Unknown;
      case ISD::EXTRACT_VECTOR_ELT:
      case ISD::EXTRACT_SUBVECTOR:
        return StoreSource::Extract;
      case ISD::LOAD:
        return StoreSource::Load;
      default:
        return StoreSource::Unknown;
      }
    }
 
    /// This is a helper function for visitMUL to check the profitability
    /// of folding (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2).
    /// MulNode is the original multiply, AddNode is (add x, c1),
    /// and ConstNode is c2.
    bool isMulAddWithConstProfitable(SDNode *MulNode, SDValue AddNode,
                                     SDValue ConstNode);
 
    /// This is a helper function for visitAND and visitZERO_EXTEND.  Returns
    /// true if the (and (load x) c) pattern matches an extload.  ExtVT returns
    /// the type of the loaded value to be extended.
    bool isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
                          EVT LoadResultTy, EVT &ExtVT);
 
    /// Helper function to calculate whether the given Load/Store can have its
    /// width reduced to ExtVT.
    bool isLegalNarrowLdSt(LSBaseSDNode *LDSTN, ISD::LoadExtType ExtType,
                           EVT &MemVT, unsigned ShAmt = 0);
 
    /// Used by BackwardsPropagateMask to find suitable loads.
    bool SearchForAndLoads(SDNode *N, SmallVectorImpl<LoadSDNode*> &Loads,
                           SmallPtrSetImpl<SDNode*> &NodesWithConsts,
                           ConstantSDNode *Mask, SDNode *&NodeToMask);
    /// Attempt to propagate a given AND node back to load leaves so that they
    /// can be combined into narrow loads.
    bool BackwardsPropagateMask(SDNode *N);
 
    /// Helper function for mergeConsecutiveStores which merges the component
    /// store chains.
    SDValue getMergeStoreChains(SmallVectorImpl<MemOpLink> &StoreNodes,
                                unsigned NumStores);
 
    /// Helper function for mergeConsecutiveStores which checks if all the store
    /// nodes have the same underlying object. We can still reuse the first
    /// store's pointer info if all the stores are from the same object.
    bool hasSameUnderlyingObj(ArrayRef<MemOpLink> StoreNodes);
 
    /// This is a helper function for mergeConsecutiveStores. When the source
    /// elements of the consecutive stores are all constants or all extracted
    /// vector elements, try to merge them into one larger store introducing
    /// bitcasts if necessary.  \return True if a merged store was created.
    bool mergeStoresOfConstantsOrVecElts(SmallVectorImpl<MemOpLink> &StoreNodes,
                                         EVT MemVT, unsigned NumStores,
                                         bool IsConstantSrc, bool UseVector,
                                         bool UseTrunc);
 
    /// This is a helper function for mergeConsecutiveStores. Stores that
    /// potentially may be merged with St are placed in StoreNodes. On success,
    /// returns a chain predecessor to all store candidates.
    SDNode *getStoreMergeCandidates(StoreSDNode *St,
                                    SmallVectorImpl<MemOpLink> &StoreNodes);
 
    /// Helper function for mergeConsecutiveStores. Checks if candidate stores
    /// have indirect dependency through their operands. RootNode is the
    /// predecessor to all stores calculated by getStoreMergeCandidates and is
    /// used to prune the dependency check. \return True if safe to merge.
    bool checkMergeStoreCandidatesForDependencies(
        SmallVectorImpl<MemOpLink> &StoreNodes, unsigned NumStores,
        SDNode *RootNode);
 
    /// This is a helper function for mergeConsecutiveStores. Given a list of
    /// store candidates, find the first N that are consecutive in memory.
    /// Returns 0 if there are not at least 2 consecutive stores to try merging.
    unsigned getConsecutiveStores(SmallVectorImpl<MemOpLink> &StoreNodes,
                                  int64_t ElementSizeBytes) const;
 
    /// This is a helper function for mergeConsecutiveStores. It is used for
    /// store chains that are composed entirely of constant values.
    bool tryStoreMergeOfConstants(SmallVectorImpl<MemOpLink> &StoreNodes,
                                  unsigned NumConsecutiveStores,
                                  EVT MemVT, SDNode *Root, bool AllowVectors);
 
    /// This is a helper function for mergeConsecutiveStores. It is used for
    /// store chains that are composed entirely of extracted vector elements.
    /// When extracting multiple vector elements, try to store them in one
    /// vector store rather than a sequence of scalar stores.
    bool tryStoreMergeOfExtracts(SmallVectorImpl<MemOpLink> &StoreNodes,
                                 unsigned NumConsecutiveStores, EVT MemVT,
                                 SDNode *Root);
 
    /// This is a helper function for mergeConsecutiveStores. It is used for
    /// store chains that are composed entirely of loaded values.
    bool tryStoreMergeOfLoads(SmallVectorImpl<MemOpLink> &StoreNodes,
                              unsigned NumConsecutiveStores, EVT MemVT,
                              SDNode *Root, bool AllowVectors,
                              bool IsNonTemporalStore, bool IsNonTemporalLoad);
 
    /// Merge consecutive store operations into a wide store.
    /// This optimization uses wide integers or vectors when possible.
    /// \return true if stores were merged.
    bool mergeConsecutiveStores(StoreSDNode *St);
 
    /// Try to transform a truncation where C is a constant:
    ///     (trunc (and X, C)) -> (and (trunc X), (trunc C))
    ///
    /// \p N needs to be a truncation and its first operand an AND. Other
    /// requirements are checked by the function (e.g. that trunc is
    /// single-use) and if missed an empty SDValue is returned.
    SDValue distributeTruncateThroughAnd(SDNode *N);
 
    /// Helper function to determine whether the target supports operation
    /// given by \p Opcode for type \p VT, that is, whether the operation
    /// is legal or custom before legalizing operations, and whether is
    /// legal (but not custom) after legalization.
    bool hasOperation(unsigned Opcode, EVT VT) {
      return TLI.isOperationLegalOrCustom(Opcode, VT, LegalOperations);
    }
 
  public:
    /// Runs the dag combiner on all nodes in the work list
    void Run(CombineLevel AtLevel);
 
    SelectionDAG &getDAG() const { return DAG; }
 
    /// Convenience wrapper around TargetLowering::getShiftAmountTy.
    EVT getShiftAmountTy(EVT LHSTy) {
      return TLI.getShiftAmountTy(LHSTy, DAG.getDataLayout());
    }
 
    /// This method returns true if we are running before type legalization or
    /// if the specified VT is legal.
    bool isTypeLegal(const EVT &VT) {
      if (!LegalTypes) return true;
      return TLI.isTypeLegal(VT);
    }
 
    /// Convenience wrapper around TargetLowering::getSetCCResultType
    EVT getSetCCResultType(EVT VT) const {
      return TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
    }
 
    void ExtendSetCCUses(const SmallVectorImpl<SDNode *> &SetCCs,
                         SDValue OrigLoad, SDValue ExtLoad,
                         ISD::NodeType ExtType);
  };
 
/// This class is a DAGUpdateListener that removes any deleted
/// nodes from the worklist.
class WorklistRemover : public SelectionDAG::DAGUpdateListener {
  DAGCombiner &DC;
 
public:
  explicit WorklistRemover(DAGCombiner &dc)
    : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
 
  void NodeDeleted(SDNode *N, SDNode *E) override {
    DC.removeFromWorklist(N);
  }
};
 
class WorklistInserter : public SelectionDAG::DAGUpdateListener {
  DAGCombiner &DC;
 
public:
  explicit WorklistInserter(DAGCombiner &dc)
      : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
 
  // FIXME: Ideally we could add N to the worklist, but this causes exponential
  //        compile time costs in large DAGs, e.g. Halide.
  void NodeInserted(SDNode *N) override { DC.ConsiderForPruning(N); }
};
 
} // end anonymous namespace
 
//===----------------------------------------------------------------------===//
//  TargetLowering::DAGCombinerInfo implementation
//===----------------------------------------------------------------------===//
 
void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) {
  ((DAGCombiner*)DC)->AddToWorklist(N);
}
 
SDValue TargetLowering::DAGCombinerInfo::
CombineTo(SDNode *N, ArrayRef<SDValue> To, bool AddTo) {
  return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size(), AddTo);
}
 
SDValue TargetLowering::DAGCombinerInfo::
CombineTo(SDNode *N, SDValue Res, bool AddTo) {
  return ((DAGCombiner*)DC)->CombineTo(N, Res, AddTo);
}
 
SDValue TargetLowering::DAGCombinerInfo::
CombineTo(SDNode *N, SDValue Res0, SDValue Res1, bool AddTo) {
  return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1, AddTo);
}
 
bool TargetLowering::DAGCombinerInfo::
recursivelyDeleteUnusedNodes(SDNode *N) {
  return ((DAGCombiner*)DC)->recursivelyDeleteUnusedNodes(N);
}
 
void TargetLowering::DAGCombinerInfo::
CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO) {
  return ((DAGCombiner*)DC)->CommitTargetLoweringOpt(TLO);
}
 
//===----------------------------------------------------------------------===//
// Helper Functions
//===----------------------------------------------------------------------===//
 
void DAGCombiner::deleteAndRecombine(SDNode *N) {
  removeFromWorklist(N);
 
  // If the operands of this node are only used by the node, they will now be
  // dead. Make sure to re-visit them and recursively delete dead nodes.
  for (const SDValue &Op : N->ops())
    // For an operand generating multiple values, one of the values may
    // become dead allowing further simplification (e.g. split index
    // arithmetic from an indexed load).
    if (Op->hasOneUse() || Op->getNumValues() > 1)
      AddToWorklist(Op.getNode());
 
  DAG.DeleteNode(N);
}
 
// APInts must be the same size for most operations, this helper
// function zero extends the shorter of the pair so that they match.
// We provide an Offset so that we can create bitwidths that won't overflow.
static void zeroExtendToMatch(APInt &LHS, APInt &RHS, unsigned Offset = 0) {
  unsigned Bits = Offset + std::max(LHS.getBitWidth(), RHS.getBitWidth());
  LHS = LHS.zext(Bits);
  RHS = RHS.zext(Bits);
}
 
// Return true if this node is a setcc, or is a select_cc
// that selects between the target values used for true and false, making it
// equivalent to a setcc. Also, set the incoming LHS, RHS, and CC references to
// the appropriate nodes based on the type of node we are checking. This
// simplifies life a bit for the callers.
bool DAGCombiner::isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
                                    SDValue &CC, bool MatchStrict) const {
  if (N.getOpcode() == ISD::SETCC) {
    LHS = N.getOperand(0);
    RHS = N.getOperand(1);
    CC  = N.getOperand(2);
    return true;
  }
 
  if (MatchStrict &&
      (N.getOpcode() == ISD::STRICT_FSETCC ||
       N.getOpcode() == ISD::STRICT_FSETCCS)) {
    LHS = N.getOperand(1);
    RHS = N.getOperand(2);
    CC  = N.getOperand(3);
    return true;
  }
 
  if (N.getOpcode() != ISD::SELECT_CC || !TLI.isConstTrueVal(N.getOperand(2)) ||
      !TLI.isConstFalseVal(N.getOperand(3)))
    return false;
 
  if (TLI.getBooleanContents(N.getValueType()) ==
      TargetLowering::UndefinedBooleanContent)
    return false;
 
  LHS = N.getOperand(0);
  RHS = N.getOperand(1);
  CC  = N.getOperand(4);
  return true;
}
 
/// Return true if this is a SetCC-equivalent operation with only one use.
/// If this is true, it allows the users to invert the operation for free when
/// it is profitable to do so.
bool DAGCombiner::isOneUseSetCC(SDValue N) const {
  SDValue N0, N1, N2;
  if (isSetCCEquivalent(N, N0, N1, N2) && N->hasOneUse())
    return true;
  return false;
}
 
static bool isConstantSplatVectorMaskForType(SDNode *N, EVT ScalarTy) {
  if (!ScalarTy.isSimple())
    return false;
 
  uint64_t MaskForTy = 0ULL;
  switch (ScalarTy.getSimpleVT().SimpleTy) {
  case MVT::i8:
    MaskForTy = 0xFFULL;
    break;
  case MVT::i16:
    MaskForTy = 0xFFFFULL;
    break;
  case MVT::i32:
    MaskForTy = 0xFFFFFFFFULL;
    break;
  default:
    return false;
    break;
  }
 
  APInt Val;
  if (ISD::isConstantSplatVector(N, Val))
    return Val.getLimitedValue() == MaskForTy;
 
  return false;
}
 
// Determines if it is a constant integer or a splat/build vector of constant
// integers (and undefs).
// Do not permit build vector implicit truncation.
static bool isConstantOrConstantVector(SDValue N, bool NoOpaques = false) {
  if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N))
    return !(Const->isOpaque() && NoOpaques);
  if (N.getOpcode() != ISD::BUILD_VECTOR && N.getOpcode() != ISD::SPLAT_VECTOR)
    return false;
  unsigned BitWidth = N.getScalarValueSizeInBits();
  for (const SDValue &Op : N->op_values()) {
    if (Op.isUndef())
      continue;
    ConstantSDNode *Const = dyn_cast<ConstantSDNode>(Op);
    if (!Const || Const->getAPIntValue().getBitWidth() != BitWidth ||
        (Const->isOpaque() && NoOpaques))
      return false;
  }
  return true;
}
 
// Determines if a BUILD_VECTOR is composed of all-constants possibly mixed with
// undef's.
static bool isAnyConstantBuildVector(SDValue V, bool NoOpaques = false) {
  if (V.getOpcode() != ISD::BUILD_VECTOR)
    return false;
  return isConstantOrConstantVector(V, NoOpaques) ||
         ISD::isBuildVectorOfConstantFPSDNodes(V.getNode());
}
 
// Determine if this an indexed load with an opaque target constant index.
static bool canSplitIdx(LoadSDNode *LD) {
  return MaySplitLoadIndex &&
         (LD->getOperand(2).getOpcode() != ISD::TargetConstant ||
          !cast<ConstantSDNode>(LD->getOperand(2))->isOpaque());
}
 
bool DAGCombiner::reassociationCanBreakAddressingModePattern(unsigned Opc,
                                                             const SDLoc &DL,
                                                             SDNode *N,
                                                             SDValue N0,
                                                             SDValue N1) {
  // Currently this only tries to ensure we don't undo the GEP splits done by
  // CodeGenPrepare when shouldConsiderGEPOffsetSplit is true. To ensure this,
  // we check if the following transformation would be problematic:
  // (load/store (add, (add, x, offset1), offset2)) ->
  // (load/store (add, x, offset1+offset2)).
 
  // (load/store (add, (add, x, y), offset2)) ->
  // (load/store (add, (add, x, offset2), y)).
 
  if (N0.getOpcode() != ISD::ADD)
    return false;
 
  // Check for vscale addressing modes.
  // (load/store (add/sub (add x, y), vscale))
  // (load/store (add/sub (add x, y), (lsl vscale, C)))
  // (load/store (add/sub (add x, y), (mul vscale, C)))
  if ((N1.getOpcode() == ISD::VSCALE ||
       ((N1.getOpcode() == ISD::SHL || N1.getOpcode() == ISD::MUL) &&
        N1.getOperand(0).getOpcode() == ISD::VSCALE &&
        isa<ConstantSDNode>(N1.getOperand(1)))) &&
      N1.getValueType().getFixedSizeInBits() <= 64) {
    int64_t ScalableOffset = N1.getOpcode() == ISD::VSCALE
                                 ? N1.getConstantOperandVal(0)
                                 : (N1.getOperand(0).getConstantOperandVal(0) *
                                    (N1.getOpcode() == ISD::SHL
                                         ? (1LL << N1.getConstantOperandVal(1))
                                         : N1.getConstantOperandVal(1)));
    if (Opc == ISD::SUB)
      ScalableOffset = -ScalableOffset;
    if (all_of(N->users(), [&](SDNode *Node) {
          if (auto *LoadStore = dyn_cast<MemSDNode>(Node);
              LoadStore && LoadStore->getBasePtr().getNode() == N) {
            TargetLoweringBase::AddrMode AM;
            AM.HasBaseReg = true;
            AM.ScalableOffset = ScalableOffset;
            EVT VT = LoadStore->getMemoryVT();
            unsigned AS = LoadStore->getAddressSpace();
            Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
            return TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy,
                                             AS);
          }
          return false;
        }))
      return true;
  }
 
  if (Opc != ISD::ADD)
    return false;
 
  auto *C2 = dyn_cast<ConstantSDNode>(N1);
  if (!C2)
    return false;
 
  const APInt &C2APIntVal = C2->getAPIntValue();
  if (C2APIntVal.getSignificantBits() > 64)
    return false;
 
  if (auto *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
    if (N0.hasOneUse())
      return false;
 
    const APInt &C1APIntVal = C1->getAPIntValue();
    const APInt CombinedValueIntVal = C1APIntVal + C2APIntVal;
    if (CombinedValueIntVal.getSignificantBits() > 64)
      return false;
    const int64_t CombinedValue = CombinedValueIntVal.getSExtValue();
 
    for (SDNode *Node : N->users()) {
      if (auto *LoadStore = dyn_cast<MemSDNode>(Node)) {
        // Is x[offset2] already not a legal addressing mode? If so then
        // reassociating the constants breaks nothing (we test offset2 because
        // that's the one we hope to fold into the load or store).
        TargetLoweringBase::AddrMode AM;
        AM.HasBaseReg = true;
        AM.BaseOffs = C2APIntVal.getSExtValue();
        EVT VT = LoadStore->getMemoryVT();
        unsigned AS = LoadStore->getAddressSpace();
        Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
        if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
          continue;
 
        // Would x[offset1+offset2] still be a legal addressing mode?
        AM.BaseOffs = CombinedValue;
        if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
          return true;
      }
    }
  } else {
    if (auto *GA = dyn_cast<GlobalAddressSDNode>(N0.getOperand(1)))
      if (GA->getOpcode() == ISD::GlobalAddress && TLI.isOffsetFoldingLegal(GA))
        return false;
 
    for (SDNode *Node : N->users()) {
      auto *LoadStore = dyn_cast<MemSDNode>(Node);
      if (!LoadStore)
        return false;
 
      // Is x[offset2] a legal addressing mode? If so then
      // reassociating the constants breaks address pattern
      TargetLoweringBase::AddrMode AM;
      AM.HasBaseReg = true;
      AM.BaseOffs = C2APIntVal.getSExtValue();
      EVT VT = LoadStore->getMemoryVT();
      unsigned AS = LoadStore->getAddressSpace();
      Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
      if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
        return false;
    }
    return true;
  }
 
  return false;
}
 
/// Helper for DAGCombiner::reassociateOps. Try to reassociate (Opc N0, N1) if
/// \p N0 is the same kind of operation as \p Opc.
SDValue DAGCombiner::reassociateOpsCommutative(unsigned Opc, const SDLoc &DL,
                                               SDValue N0, SDValue N1,
                                               SDNodeFlags Flags) {
  EVT VT = N0.getValueType();
 
  if (N0.getOpcode() != Opc)
    return SDValue();
 
  SDValue N00 = N0.getOperand(0);
  SDValue N01 = N0.getOperand(1);
 
  if (DAG.isConstantIntBuildVectorOrConstantInt(N01)) {
    SDNodeFlags NewFlags;
    if (N0.getOpcode() == ISD::ADD && N0->getFlags().hasNoUnsignedWrap() &&
        Flags.hasNoUnsignedWrap())
      NewFlags |= SDNodeFlags::NoUnsignedWrap;
 
    if (DAG.isConstantIntBuildVectorOrConstantInt(N1)) {
      // Reassociate: (op (op x, c1), c2) -> (op x, (op c1, c2))
      if (SDValue OpNode = DAG.FoldConstantArithmetic(Opc, DL, VT, {N01, N1})) {
        NewFlags.setDisjoint(Flags.hasDisjoint() &&
                             N0->getFlags().hasDisjoint());
        return DAG.getNode(Opc, DL, VT, N00, OpNode, NewFlags);
      }
      return SDValue();
    }
    if (TLI.isReassocProfitable(DAG, N0, N1)) {
      // Reassociate: (op (op x, c1), y) -> (op (op x, y), c1)
      //              iff (op x, c1) has one use
      SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N00, N1, NewFlags);
      return DAG.getNode(Opc, DL, VT, OpNode, N01, NewFlags);
    }
  }
 
  // Check for repeated operand logic simplifications.
  if (Opc == ISD::AND || Opc == ISD::OR) {
    // (N00 & N01) & N00 --> N00 & N01
    // (N00 & N01) & N01 --> N00 & N01
    // (N00 | N01) | N00 --> N00 | N01
    // (N00 | N01) | N01 --> N00 | N01
    if (N1 == N00 || N1 == N01)
      return N0;
  }
  if (Opc == ISD::XOR) {
    // (N00 ^ N01) ^ N00 --> N01
    if (N1 == N00)
      return N01;
    // (N00 ^ N01) ^ N01 --> N00
    if (N1 == N01)
      return N00;
  }
 
  if (TLI.isReassocProfitable(DAG, N0, N1)) {
    if (N1 != N01) {
      // Reassociate if (op N00, N1) already exist
      if (SDNode *NE = DAG.getNodeIfExists(Opc, DAG.getVTList(VT), {N00, N1})) {
        // if Op (Op N00, N1), N01 already exist
        // we need to stop reassciate to avoid dead loop
        if (!DAG.doesNodeExist(Opc, DAG.getVTList(VT), {SDValue(NE, 0), N01}))
          return DAG.getNode(Opc, DL, VT, SDValue(NE, 0), N01);
      }
    }
 
    if (N1 != N00) {
      // Reassociate if (op N01, N1) already exist
      if (SDNode *NE = DAG.getNodeIfExists(Opc, DAG.getVTList(VT), {N01, N1})) {
        // if Op (Op N01, N1), N00 already exist
        // we need to stop reassciate to avoid dead loop
        if (!DAG.doesNodeExist(Opc, DAG.getVTList(VT), {SDValue(NE, 0), N00}))
          return DAG.getNode(Opc, DL, VT, SDValue(NE, 0), N00);
      }
    }
 
    // Reassociate the operands from (OR/AND (OR/AND(N00, N001)), N1) to (OR/AND
    // (OR/AND(N00, N1)), N01) when N00 and N1 are comparisons with the same
    // predicate or to (OR/AND (OR/AND(N1, N01)), N00) when N01 and N1 are
    // comparisons with the same predicate. This enables optimizations as the
    // following one:
    // CMP(A,C)||CMP(B,C) => CMP(MIN/MAX(A,B), C)
    // CMP(A,C)&&CMP(B,C) => CMP(MIN/MAX(A,B), C)
    if (Opc == ISD::AND || Opc == ISD::OR) {
      if (N1->getOpcode() == ISD::SETCC && N00->getOpcode() == ISD::SETCC &&
          N01->getOpcode() == ISD::SETCC) {
        ISD::CondCode CC1 = cast<CondCodeSDNode>(N1.getOperand(2))->get();
        ISD::CondCode CC00 = cast<CondCodeSDNode>(N00.getOperand(2))->get();
        ISD::CondCode CC01 = cast<CondCodeSDNode>(N01.getOperand(2))->get();
        if (CC1 == CC00 && CC1 != CC01) {
          SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N00, N1, Flags);
          return DAG.getNode(Opc, DL, VT, OpNode, N01, Flags);
        }
        if (CC1 == CC01 && CC1 != CC00) {
          SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N01, N1, Flags);
          return DAG.getNode(Opc, DL, VT, OpNode, N00, Flags);
        }
      }
    }
  }
 
  return SDValue();
}
 
/// Try to reassociate commutative (Opc N0, N1) if either \p N0 or \p N1 is the
/// same kind of operation as \p Opc.
SDValue DAGCombiner::reassociateOps(unsigned Opc, const SDLoc &DL, SDValue N0,
                                    SDValue N1, SDNodeFlags Flags) {
  assert(TLI.isCommutativeBinOp(Opc) && "Operation not commutative.");
 
  // Floating-point reassociation is not allowed without loose FP math.
  if (N0.getValueType().isFloatingPoint() ||
      N1.getValueType().isFloatingPoint())
    if (!Flags.hasAllowReassociation() || !Flags.hasNoSignedZeros())
      return SDValue();
 
  if (SDValue Combined = reassociateOpsCommutative(Opc, DL, N0, N1, Flags))
    return Combined;
  if (SDValue Combined = reassociateOpsCommutative(Opc, DL, N1, N0, Flags))
    return Combined;
  return SDValue();
}
 
// Try to fold Opc(vecreduce(x), vecreduce(y)) -> vecreduce(Opc(x, y))
// Note that we only expect Flags to be passed from FP operations. For integer
// operations they need to be dropped.
SDValue DAGCombiner::reassociateReduction(unsigned RedOpc, unsigned Opc,
                                          const SDLoc &DL, EVT VT, SDValue N0,
                                          SDValue N1, SDNodeFlags Flags) {
  if (N0.getOpcode() == RedOpc && N1.getOpcode() == RedOpc &&
      N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType() &&
      N0->hasOneUse() && N1->hasOneUse() &&
      TLI.isOperationLegalOrCustom(Opc, N0.getOperand(0).getValueType()) &&
      TLI.shouldReassociateReduction(RedOpc, N0.getOperand(0).getValueType())) {
    SelectionDAG::FlagInserter FlagsInserter(DAG, Flags);
    return DAG.getNode(RedOpc, DL, VT,
                       DAG.getNode(Opc, DL, N0.getOperand(0).getValueType(),
                                   N0.getOperand(0), N1.getOperand(0)));
  }
  return SDValue();
}
 
SDValue DAGCombiner::CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
                               bool AddTo) {
  assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
  ++NodesCombined;
  LLVM_DEBUG(dbgs() << "\nReplacing.1 "; N->dump(&DAG); dbgs() << "\nWith: ";
             To[0].dump(&DAG);
             dbgs() << " and " << NumTo - 1 << " other values\n");
  for (unsigned i = 0, e = NumTo; i != e; ++i)
    assert((!To[i].getNode() ||
            N->getValueType(i) == To[i].getValueType()) &&
           "Cannot combine value to value of different type!");
 
  WorklistRemover DeadNodes(*this);
  DAG.ReplaceAllUsesWith(N, To);
  if (AddTo) {
    // Push the new nodes and any users onto the worklist
    for (unsigned i = 0, e = NumTo; i != e; ++i) {
      if (To[i].getNode())
        AddToWorklistWithUsers(To[i].getNode());
    }
  }
 
  // Finally, if the node is now dead, remove it from the graph.  The node
  // may not be dead if the replacement process recursively simplified to
  // something else needing this node.
  if (N->use_empty())
    deleteAndRecombine(N);
  return SDValue(N, 0);
}
 
void DAGCombiner::
CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO) {
  // Replace the old value with the new one.
  ++NodesCombined;
  LLVM_DEBUG(dbgs() << "\nReplacing.2 "; TLO.Old.dump(&DAG);
             dbgs() << "\nWith: "; TLO.New.dump(&DAG); dbgs() << '\n');
 
  // Replace all uses.
  DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New);
 
  // Push the new node and any (possibly new) users onto the worklist.
  AddToWorklistWithUsers(TLO.New.getNode());
 
  // Finally, if the node is now dead, remove it from the graph.
  recursivelyDeleteUnusedNodes(TLO.Old.getNode());
}
 
/// Check the specified integer node value to see if it can be simplified or if
/// things it uses can be simplified by bit propagation. If so, return true.
bool DAGCombiner::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
                                       const APInt &DemandedElts,
                                       bool AssumeSingleUse) {
  TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
  KnownBits Known;
  if (!TLI.SimplifyDemandedBits(Op, DemandedBits, DemandedElts, Known, TLO, 0,
                                AssumeSingleUse))
    return false;
 
  // Revisit the node.
  AddToWorklist(Op.getNode());
 
  CommitTargetLoweringOpt(TLO);
  return true;
}
 
/// Check the specified vector node value to see if it can be simplified or
/// if things it uses can be simplified as it only uses some of the elements.
/// If so, return true.
bool DAGCombiner::SimplifyDemandedVectorElts(SDValue Op,
                                             const APInt &DemandedElts,
                                             bool AssumeSingleUse) {
  TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
  APInt KnownUndef, KnownZero;
  if (!TLI.SimplifyDemandedVectorElts(Op, DemandedElts, KnownUndef, KnownZero,
                                      TLO, 0, AssumeSingleUse))
    return false;
 
  // Revisit the node.
  AddToWorklist(Op.getNode());
 
  CommitTargetLoweringOpt(TLO);
  return true;
}
 
void DAGCombiner::ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad) {
  SDLoc DL(Load);
  EVT VT = Load->getValueType(0);
  SDValue Trunc = DAG.getNode(ISD::TRUNCATE, DL, VT, SDValue(ExtLoad, 0));
 
  LLVM_DEBUG(dbgs() << "\nReplacing.9 "; Load->dump(&DAG); dbgs() << "\nWith: ";
             Trunc.dump(&DAG); dbgs() << '\n');
 
  DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 0), Trunc);
  DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 1), SDValue(ExtLoad, 1));
 
  AddToWorklist(Trunc.getNode());
  recursivelyDeleteUnusedNodes(Load);
}
 
SDValue DAGCombiner::PromoteOperand(SDValue Op, EVT PVT, bool &Replace) {
  Replace = false;
  SDLoc DL(Op);
  if (ISD::isUNINDEXEDLoad(Op.getNode())) {
    LoadSDNode *LD = cast<LoadSDNode>(Op);
    EVT MemVT = LD->getMemoryVT();
    ISD::LoadExtType ExtType = ISD::isNON_EXTLoad(LD) ? ISD::EXTLOAD
                                                      : LD->getExtensionType();
    Replace = true;
    return DAG.getExtLoad(ExtType, DL, PVT,
                          LD->getChain(), LD->getBasePtr(),
                          MemVT, LD->getMemOperand());
  }
 
  unsigned Opc = Op.getOpcode();
  switch (Opc) {
  default: break;
  case ISD::AssertSext:
    if (SDValue Op0 = SExtPromoteOperand(Op.getOperand(0), PVT))
      return DAG.getNode(ISD::AssertSext, DL, PVT, Op0, Op.getOperand(1));
    break;
  case ISD::AssertZext:
    if (SDValue Op0 = ZExtPromoteOperand(Op.getOperand(0), PVT))
      return DAG.getNode(ISD::AssertZext, DL, PVT, Op0, Op.getOperand(1));
    break;
  case ISD::Constant: {
    unsigned ExtOpc =
      Op.getValueType().isByteSized() ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
    return DAG.getNode(ExtOpc, DL, PVT, Op);
  }
  }
 
  if (!TLI.isOperationLegal(ISD::ANY_EXTEND, PVT))
    return SDValue();
  return DAG.getNode(ISD::ANY_EXTEND, DL, PVT, Op);
}
 
SDValue DAGCombiner::SExtPromoteOperand(SDValue Op, EVT PVT) {
  if (!TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, PVT))
    return SDValue();
  EVT OldVT = Op.getValueType();
  SDLoc DL(Op);
  bool Replace = false;
  SDValue NewOp = PromoteOperand(Op, PVT, Replace);
  if (!NewOp.getNode())
    return SDValue();
  AddToWorklist(NewOp.getNode());
 
  if (Replace)
    ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
  return DAG.getNode(ISD::SIGN_EXTEND_INREG, DL, NewOp.getValueType(), NewOp,
                     DAG.getValueType(OldVT));
}
 
SDValue DAGCombiner::ZExtPromoteOperand(SDValue Op, EVT PVT) {
  EVT OldVT = Op.getValueType();
  SDLoc DL(Op);
  bool Replace = false;
  SDValue NewOp = PromoteOperand(Op, PVT, Replace);
  if (!NewOp.getNode())
    return SDValue();
  AddToWorklist(NewOp.getNode());
 
  if (Replace)
    ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
  return DAG.getZeroExtendInReg(NewOp, DL, OldVT);
}
 
/// Promote the specified integer binary operation if the target indicates it is
/// beneficial. e.g. On x86, it's usually better to promote i16 operations to
/// i32 since i16 instructions are longer.
SDValue DAGCombiner::PromoteIntBinOp(SDValue Op) {
  if (!LegalOperations)
    return SDValue();
 
  EVT VT = Op.getValueType();
  if (VT.isVector() || !VT.isInteger())
    return SDValue();
 
  // If operation type is 'undesirable', e.g. i16 on x86, consider
  // promoting it.
  unsigned Opc = Op.getOpcode();
  if (TLI.isTypeDesirableForOp(Opc, VT))
    return SDValue();
 
  EVT PVT = VT;
  // Consult target whether it is a good idea to promote this operation and
  // what's the right type to promote it to.
  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
    assert(PVT != VT && "Don't know what type to promote to!");
 
    LLVM_DEBUG(dbgs() << "\nPromoting "; Op.dump(&DAG));
 
    bool Replace0 = false;
    SDValue N0 = Op.getOperand(0);
    SDValue NN0 = PromoteOperand(N0, PVT, Replace0);
 
    bool Replace1 = false;
    SDValue N1 = Op.getOperand(1);
    SDValue NN1 = PromoteOperand(N1, PVT, Replace1);
    SDLoc DL(Op);
 
    SDValue RV =
        DAG.getNode(ISD::TRUNCATE, DL, VT, DAG.getNode(Opc, DL, PVT, NN0, NN1));
 
    // We are always replacing N0/N1's use in N and only need additional
    // replacements if there are additional uses.
    // Note: We are checking uses of the *nodes* (SDNode) rather than values
    //       (SDValue) here because the node may reference multiple values
    //       (for example, the chain value of a load node).
    Replace0 &= !N0->hasOneUse();
    Replace1 &= (N0 != N1) && !N1->hasOneUse();
 
    // Combine Op here so it is preserved past replacements.
    CombineTo(Op.getNode(), RV);
 
    // If operands have a use ordering, make sure we deal with
    // predecessor first.
    if (Replace0 && Replace1 && N0->isPredecessorOf(N1.getNode())) {
      std::swap(N0, N1);
      std::swap(NN0, NN1);
    }
 
    if (Replace0) {
      AddToWorklist(NN0.getNode());
      ReplaceLoadWithPromotedLoad(N0.getNode(), NN0.getNode());
    }
    if (Replace1) {
      AddToWorklist(NN1.getNode());
      ReplaceLoadWithPromotedLoad(N1.getNode(), NN1.getNode());
    }
    return Op;
  }
  return SDValue();
}
 
/// Promote the specified integer shift operation if the target indicates it is
/// beneficial. e.g. On x86, it's usually better to promote i16 operations to
/// i32 since i16 instructions are longer.
SDValue DAGCombiner::PromoteIntShiftOp(SDValue Op) {
  if (!LegalOperations)
    return SDValue();
 
  EVT VT = Op.getValueType();
  if (VT.isVector() || !VT.isInteger())
    return SDValue();
 
  // If operation type is 'undesirable', e.g. i16 on x86, consider
  // promoting it.
  unsigned Opc = Op.getOpcode();
  if (TLI.isTypeDesirableForOp(Opc, VT))
    return SDValue();
 
  EVT PVT = VT;
  // Consult target whether it is a good idea to promote this operation and
  // what's the right type to promote it to.
  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
    assert(PVT != VT && "Don't know what type to promote to!");
 
    LLVM_DEBUG(dbgs() << "\nPromoting "; Op.dump(&DAG));
 
    bool Replace = false;
    SDValue N0 = Op.getOperand(0);
    if (Opc == ISD::SRA)
      N0 = SExtPromoteOperand(N0, PVT);
    else if (Opc == ISD::SRL)
      N0 = ZExtPromoteOperand(N0, PVT);
    else
      N0 = PromoteOperand(N0, PVT, Replace);
 
    if (!N0.getNode())
      return SDValue();
 
    SDLoc DL(Op);
    SDValue N1 = Op.getOperand(1);
    SDValue RV =
        DAG.getNode(ISD::TRUNCATE, DL, VT, DAG.getNode(Opc, DL, PVT, N0, N1));
 
    if (Replace)
      ReplaceLoadWithPromotedLoad(Op.getOperand(0).getNode(), N0.getNode());
 
    // Deal with Op being deleted.
    if (Op && Op.getOpcode() != ISD::DELETED_NODE)
      return RV;
  }
  return SDValue();
}
 
SDValue DAGCombiner::PromoteExtend(SDValue Op) {
  if (!LegalOperations)
    return SDValue();
 
  EVT VT = Op.getValueType();
  if (VT.isVector() || !VT.isInteger())
    return SDValue();
 
  // If operation type is 'undesirable', e.g. i16 on x86, consider
  // promoting it.
  unsigned Opc = Op.getOpcode();
  if (TLI.isTypeDesirableForOp(Opc, VT))
    return SDValue();
 
  EVT PVT = VT;
  // Consult target whether it is a good idea to promote this operation and
  // what's the right type to promote it to.
  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
    assert(PVT != VT && "Don't know what type to promote to!");
    // fold (aext (aext x)) -> (aext x)
    // fold (aext (zext x)) -> (zext x)
    // fold (aext (sext x)) -> (sext x)
    LLVM_DEBUG(dbgs() << "\nPromoting "; Op.dump(&DAG));
    return DAG.getNode(Op.getOpcode(), SDLoc(Op), VT, Op.getOperand(0));
  }
  return SDValue();
}
 
bool DAGCombiner::PromoteLoad(SDValue Op) {
  if (!LegalOperations)
    return false;
 
  if (!ISD::isUNINDEXEDLoad(Op.getNode()))
    return false;
 
  EVT VT = Op.getValueType();
  if (VT.isVector() || !VT.isInteger())
    return false;
 
  // If operation type is 'undesirable', e.g. i16 on x86, consider
  // promoting it.
  unsigned Opc = Op.getOpcode();
  if (TLI.isTypeDesirableForOp(Opc, VT))
    return false;
 
  EVT PVT = VT;
  // Consult target whether it is a good idea to promote this operation and
  // what's the right type to promote it to.
  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
    assert(PVT != VT && "Don't know what type to promote to!");
 
    SDLoc DL(Op);
    SDNode *N = Op.getNode();
    LoadSDNode *LD = cast<LoadSDNode>(N);
    EVT MemVT = LD->getMemoryVT();
    ISD::LoadExtType ExtType = ISD::isNON_EXTLoad(LD) ? ISD::EXTLOAD
                                                      : LD->getExtensionType();
    SDValue NewLD = DAG.getExtLoad(ExtType, DL, PVT,
                                   LD->getChain(), LD->getBasePtr(),
                                   MemVT, LD->getMemOperand());
    SDValue Result = DAG.getNode(ISD::TRUNCATE, DL, VT, NewLD);
 
    LLVM_DEBUG(dbgs() << "\nPromoting "; N->dump(&DAG); dbgs() << "\nTo: ";
               Result.dump(&DAG); dbgs() << '\n');
 
    DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
    DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), NewLD.getValue(1));
 
    AddToWorklist(Result.getNode());
    recursivelyDeleteUnusedNodes(N);
    return true;
  }
 
  return false;
}
 
/// Recursively delete a node which has no uses and any operands for
/// which it is the only use.
///
/// Note that this both deletes the nodes and removes them from the worklist.
/// It also adds any nodes who have had a user deleted to the worklist as they
/// may now have only one use and subject to other combines.
bool DAGCombiner::recursivelyDeleteUnusedNodes(SDNode *N) {
  if (!N->use_empty())
    return false;
 
  SmallSetVector<SDNode *, 16> Nodes;
  Nodes.insert(N);
  do {
    N = Nodes.pop_back_val();
    if (!N)
      continue;
 
    if (N->use_empty()) {
      for (const SDValue &ChildN : N->op_values())
        Nodes.insert(ChildN.getNode());
 
      removeFromWorklist(N);
      DAG.DeleteNode(N);
    } else {
      AddToWorklist(N);
    }
  } while (!Nodes.empty());
  return true;
}
 
//===----------------------------------------------------------------------===//
//  Main DAG Combiner implementation
//===----------------------------------------------------------------------===//
 
void DAGCombiner::Run(CombineLevel AtLevel) {
  // set the instance variables, so that the various visit routines may use it.
  Level = AtLevel;
  LegalDAG = Level >= AfterLegalizeDAG;
  LegalOperations = Level >= AfterLegalizeVectorOps;
  LegalTypes = Level >= AfterLegalizeTypes;
 
  WorklistInserter AddNodes(*this);
 
  // Add all the dag nodes to the worklist.
  //
  // Note: All nodes are not added to PruningList here, this is because the only
  // nodes which can be deleted are those which have no uses and all other nodes
  // which would otherwise be added to the worklist by the first call to
  // getNextWorklistEntry are already present in it.
  for (SDNode &Node : DAG.allnodes())
    AddToWorklist(&Node, /* IsCandidateForPruning */ Node.use_empty());
 
  // Create a dummy node (which is not added to allnodes), that adds a reference
  // to the root node, preventing it from being deleted, and tracking any
  // changes of the root.
  HandleSDNode Dummy(DAG.getRoot());
 
  // While we have a valid worklist entry node, try to combine it.
  while (SDNode *N = getNextWorklistEntry()) {
    // If N has no uses, it is dead.  Make sure to revisit all N's operands once
    // N is deleted from the DAG, since they too may now be dead or may have a
    // reduced number of uses, allowing other xforms.
    if (recursivelyDeleteUnusedNodes(N))
      continue;
 
    WorklistRemover DeadNodes(*this);
 
    // If this combine is running after legalizing the DAG, re-legalize any
    // nodes pulled off the worklist.
    if (LegalDAG) {
      SmallSetVector<SDNode *, 16> UpdatedNodes;
      bool NIsValid = DAG.LegalizeOp(N, UpdatedNodes);
 
      for (SDNode *LN : UpdatedNodes)
        AddToWorklistWithUsers(LN);
 
      if (!NIsValid)
        continue;
    }
 
    LLVM_DEBUG(dbgs() << "\nCombining: "; N->dump(&DAG));
 
    // Add any operands of the new node which have not yet been combined to the
    // worklist as well. getNextWorklistEntry flags nodes that have been
    // combined before. Because the worklist uniques things already, this won't
    // repeatedly process the same operand.
    for (const SDValue &ChildN : N->op_values())
      AddToWorklist(ChildN.getNode(), /*IsCandidateForPruning=*/true,
                    /*SkipIfCombinedBefore=*/true);
 
    SDValue RV = combine(N);
 
    if (!RV.getNode())
      continue;
 
    ++NodesCombined;
 
    // Invalidate cached info.
    ChainsWithoutMergeableStores.clear();
 
    // If we get back the same node we passed in, rather than a new node or
    // zero, we know that the node must have defined multiple values and
    // CombineTo was used.  Since CombineTo takes care of the worklist
    // mechanics for us, we have no work to do in this case.
    if (RV.getNode() == N)
      continue;
 
    assert(N->getOpcode() != ISD::DELETED_NODE &&
           RV.getOpcode() != ISD::DELETED_NODE &&
           "Node was deleted but visit returned new node!");
 
    LLVM_DEBUG(dbgs() << " ... into: "; RV.dump(&DAG));
 
    if (N->getNumValues() == RV->getNumValues())
      DAG.ReplaceAllUsesWith(N, RV.getNode());
    else {
      assert(N->getValueType(0) == RV.getValueType() &&
             N->getNumValues() == 1 && "Type mismatch");
      DAG.ReplaceAllUsesWith(N, &RV);
    }
 
    // Push the new node and any users onto the worklist.  Omit this if the
    // new node is the EntryToken (e.g. if a store managed to get optimized
    // out), because re-visiting the EntryToken and its users will not uncover
    // any additional opportunities, but there may be a large number of such
    // users, potentially causing compile time explosion.
    if (RV.getOpcode() != ISD::EntryToken)
      AddToWorklistWithUsers(RV.getNode());
 
    // Finally, if the node is now dead, remove it from the graph.  The node
    // may not be dead if the replacement process recursively simplified to
    // something else needing this node. This will also take care of adding any
    // operands which have lost a user to the worklist.
    recursivelyDeleteUnusedNodes(N);
  }
 
  // If the root changed (e.g. it was a dead load, update the root).
  DAG.setRoot(Dummy.getValue());
  DAG.RemoveDeadNodes();
}
 
SDValue DAGCombiner::visit(SDNode *N) {
  // clang-format off
  switch (N->getOpcode()) {
  default: break;
  case ISD::TokenFactor:        return visitTokenFactor(N);
  case ISD::MERGE_VALUES:       return visitMERGE_VALUES(N);
  case ISD::ADD:                return visitADD(N);
  case ISD::SUB:                return visitSUB(N);
  case ISD::SADDSAT:
  case ISD::UADDSAT:            return visitADDSAT(N);
  case ISD::SSUBSAT:
  case ISD::USUBSAT:            return visitSUBSAT(N);
  case ISD::ADDC:               return visitADDC(N);
  case ISD::SADDO:
  case ISD::UADDO:              return visitADDO(N);
  case ISD::SUBC:               return visitSUBC(N);
  case ISD::SSUBO:
  case ISD::USUBO:              return visitSUBO(N);
  case ISD::ADDE:               return visitADDE(N);
  case ISD::UADDO_CARRY:        return visitUADDO_CARRY(N);
  case ISD::SADDO_CARRY:        return visitSADDO_CARRY(N);
  case ISD::SUBE:               return visitSUBE(N);
  case ISD::USUBO_CARRY:        return visitUSUBO_CARRY(N);
  case ISD::SSUBO_CARRY:        return visitSSUBO_CARRY(N);
  case ISD::SMULFIX:
  case ISD::SMULFIXSAT:
  case ISD::UMULFIX:
  case ISD::UMULFIXSAT:         return visitMULFIX(N);
  case ISD::MUL:                return visitMUL<EmptyMatchContext>(N);
  case ISD::SDIV:               return visitSDIV(N);
  case ISD::UDIV:               return visitUDIV(N);
  case ISD::SREM:
  case ISD::UREM:               return visitREM(N);
  case ISD::MULHU:              return visitMULHU(N);
  case ISD::MULHS:              return visitMULHS(N);
  case ISD::AVGFLOORS:
  case ISD::AVGFLOORU:
  case ISD::AVGCEILS:
  case ISD::AVGCEILU:           return visitAVG(N);
  case ISD::ABDS:
  case ISD::ABDU:               return visitABD(N);
  case ISD::SMUL_LOHI:          return visitSMUL_LOHI(N);
  case ISD::UMUL_LOHI:          return visitUMUL_LOHI(N);
  case ISD::SMULO:
  case ISD::UMULO:              return visitMULO(N);
  case ISD::SMIN:
  case ISD::SMAX:
  case ISD::UMIN:
  case ISD::UMAX:               return visitIMINMAX(N);
  case ISD::AND:                return visitAND(N);
  case ISD::OR:                 return visitOR(N);
  case ISD::XOR:                return visitXOR(N);
  case ISD::SHL:                return visitSHL(N);
  case ISD::SRA:                return visitSRA(N);
  case ISD::SRL:                return visitSRL(N);
  case ISD::ROTR:
  case ISD::ROTL:               return visitRotate(N);
  case ISD::FSHL:
  case ISD::FSHR:               return visitFunnelShift(N);
  case ISD::SSHLSAT:
  case ISD::USHLSAT:            return visitSHLSAT(N);
  case ISD::ABS:                return visitABS(N);
  case ISD::BSWAP:              return visitBSWAP(N);
  case ISD::BITREVERSE:         return visitBITREVERSE(N);
  case ISD::CTLZ:               return visitCTLZ(N);
  case ISD::CTLZ_ZERO_UNDEF:    return visitCTLZ_ZERO_UNDEF(N);
  case ISD::CTTZ:               return visitCTTZ(N);
  case ISD::CTTZ_ZERO_UNDEF:    return visitCTTZ_ZERO_UNDEF(N);
  case ISD::CTPOP:              return visitCTPOP(N);
  case ISD::SELECT:             return visitSELECT(N);
  case ISD::VSELECT:            return visitVSELECT(N);
  case ISD::SELECT_CC:          return visitSELECT_CC(N);
  case ISD::SETCC:              return visitSETCC(N);
  case ISD::SETCCCARRY:         return visitSETCCCARRY(N);
  case ISD::SIGN_EXTEND:        return visitSIGN_EXTEND(N);
  case ISD::ZERO_EXTEND:        return visitZERO_EXTEND(N);
  case ISD::ANY_EXTEND:         return visitANY_EXTEND(N);
  case ISD::AssertSext:
  case ISD::AssertZext:         return visitAssertExt(N);
  case ISD::AssertAlign:        return visitAssertAlign(N);
  case ISD::SIGN_EXTEND_INREG:  return visitSIGN_EXTEND_INREG(N);
  case ISD::SIGN_EXTEND_VECTOR_INREG:
  case ISD::ZERO_EXTEND_VECTOR_INREG:
  case ISD::ANY_EXTEND_VECTOR_INREG: return visitEXTEND_VECTOR_INREG(N);
  case ISD::TRUNCATE:           return visitTRUNCATE(N);
  case ISD::TRUNCATE_USAT_U:    return visitTRUNCATE_USAT_U(N);
  case ISD::BITCAST:            return visitBITCAST(N);
  case ISD::BUILD_PAIR:         return visitBUILD_PAIR(N);
  case ISD::FADD:               return visitFADD(N);
  case ISD::STRICT_FADD:        return visitSTRICT_FADD(N);
  case ISD::FSUB:               return visitFSUB(N);
  case ISD::FMUL:               return visitFMUL(N);
  case ISD::FMA:                return visitFMA<EmptyMatchContext>(N);
  case ISD::FMAD:               return visitFMAD(N);
  case ISD::FDIV:               return visitFDIV(N);
  case ISD::FREM:               return visitFREM(N);
  case ISD::FSQRT:              return visitFSQRT(N);
  case ISD::FCOPYSIGN:          return visitFCOPYSIGN(N);
  case ISD::FPOW:               return visitFPOW(N);
  case ISD::SINT_TO_FP:         return visitSINT_TO_FP(N);
  case ISD::UINT_TO_FP:         return visitUINT_TO_FP(N);
  case ISD::FP_TO_SINT:         return visitFP_TO_SINT(N);
  case ISD::FP_TO_UINT:         return visitFP_TO_UINT(N);
  case ISD::LROUND:
  case ISD::LLROUND:
  case ISD::LRINT:
  case ISD::LLRINT:             return visitXROUND(N);
  case ISD::FP_ROUND:           return visitFP_ROUND(N);
  case ISD::FP_EXTEND:          return visitFP_EXTEND(N);
  case ISD::FNEG:               return visitFNEG(N);
  case ISD::FABS:               return visitFABS(N);
  case ISD::FFLOOR:             return visitFFLOOR(N);
  case ISD::FMINNUM:
  case ISD::FMAXNUM:
  case ISD::FMINIMUM:
  case ISD::FMAXIMUM:
  case ISD::FMINIMUMNUM:
  case ISD::FMAXIMUMNUM:       return visitFMinMax(N);
  case ISD::FCEIL:              return visitFCEIL(N);
  case ISD::FTRUNC:             return visitFTRUNC(N);
  case ISD::FFREXP:             return visitFFREXP(N);
  case ISD::BRCOND:             return visitBRCOND(N);
  case ISD::BR_CC:              return visitBR_CC(N);
  case ISD::LOAD:               return visitLOAD(N);
  case ISD::STORE:              return visitSTORE(N);
  case ISD::ATOMIC_STORE:       return visitATOMIC_STORE(N);
  case ISD::INSERT_VECTOR_ELT:  return visitINSERT_VECTOR_ELT(N);
  case ISD::EXTRACT_VECTOR_ELT: return visitEXTRACT_VECTOR_ELT(N);
  case ISD::BUILD_VECTOR:       return visitBUILD_VECTOR(N);
  case ISD::CONCAT_VECTORS:     return visitCONCAT_VECTORS(N);
  case ISD::EXTRACT_SUBVECTOR:  return visitEXTRACT_SUBVECTOR(N);
  case ISD::VECTOR_SHUFFLE:     return visitVECTOR_SHUFFLE(N);
  case ISD::SCALAR_TO_VECTOR:   return visitSCALAR_TO_VECTOR(N);
  case ISD::INSERT_SUBVECTOR:   return visitINSERT_SUBVECTOR(N);
  case ISD::MGATHER:            return visitMGATHER(N);
  case ISD::MLOAD:              return visitMLOAD(N);
  case ISD::MSCATTER:           return visitMSCATTER(N);
  case ISD::MSTORE:             return visitMSTORE(N);
  case ISD::EXPERIMENTAL_VECTOR_HISTOGRAM: return visitMHISTOGRAM(N);
  case ISD::VECTOR_COMPRESS:    return visitVECTOR_COMPRESS(N);
  case ISD::LIFETIME_END:       return visitLIFETIME_END(N);
  case ISD::FP_TO_FP16:         return visitFP_TO_FP16(N);
  case ISD::FP16_TO_FP:         return visitFP16_TO_FP(N);
  case ISD::FP_TO_BF16:         return visitFP_TO_BF16(N);
  case ISD::BF16_TO_FP:         return visitBF16_TO_FP(N);
  case ISD::FREEZE:             return visitFREEZE(N);
  case ISD::GET_FPENV_MEM:      return visitGET_FPENV_MEM(N);
  case ISD::SET_FPENV_MEM:      return visitSET_FPENV_MEM(N);
  case ISD::FCANONICALIZE:      return visitFCANONICALIZE(N);
  case ISD::VECREDUCE_FADD:
  case ISD::VECREDUCE_FMUL:
  case ISD::VECREDUCE_ADD:
  case ISD::VECREDUCE_MUL:
  case ISD::VECREDUCE_AND:
  case ISD::VECREDUCE_OR:
  case ISD::VECREDUCE_XOR:
  case ISD::VECREDUCE_SMAX:
  case ISD::VECREDUCE_SMIN:
  case ISD::VECREDUCE_UMAX:
  case ISD::VECREDUCE_UMIN:
  case ISD::VECREDUCE_FMAX:
  case ISD::VECREDUCE_FMIN:
  case ISD::VECREDUCE_FMAXIMUM:
  case ISD::VECREDUCE_FMINIMUM:     return visitVECREDUCE(N);
#define BEGIN_REGISTER_VP_SDNODE(SDOPC, ...) case ISD::SDOPC:
#include "llvm/IR/VPIntrinsics.def"
    return visitVPOp(N);
  }
  // clang-format on
  return SDValue();
}
 
SDValue DAGCombiner::combine(SDNode *N) {
  if (!DebugCounter::shouldExecute(DAGCombineCounter))
    return SDValue();
 
  SDValue RV;
  if (!DisableGenericCombines)
    RV = visit(N);
 
  // If nothing happened, try a target-specific DAG combine.
  if (!RV.getNode()) {
    assert(N->getOpcode() != ISD::DELETED_NODE &&
           "Node was deleted but visit returned NULL!");
 
    if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
        TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) {
 
      // Expose the DAG combiner to the target combiner impls.
      TargetLowering::DAGCombinerInfo
        DagCombineInfo(DAG, Level, false, this);
 
      RV = TLI.PerformDAGCombine(N, DagCombineInfo);
    }
  }
 
  // If nothing happened still, try promoting the operation.
  if (!RV.getNode()) {
    switch (N->getOpcode()) {
    default: break;
    case ISD::ADD:
    case ISD::SUB:
    case ISD::MUL:
    case ISD::AND:
    case ISD::OR:
    case ISD::XOR:
      RV = PromoteIntBinOp(SDValue(N, 0));
      break;
    case ISD::SHL:
    case ISD::SRA:
    case ISD::SRL:
      RV = PromoteIntShiftOp(SDValue(N, 0));
      break;
    case ISD::SIGN_EXTEND:
    case ISD::ZERO_EXTEND:
    case ISD::ANY_EXTEND:
      RV = PromoteExtend(SDValue(N, 0));
      break;
    case ISD::LOAD:
      if (PromoteLoad(SDValue(N, 0)))
        RV = SDValue(N, 0);
      break;
    }
  }
 
  // If N is a commutative binary node, try to eliminate it if the commuted
  // version is already present in the DAG.
  if (!RV.getNode() && TLI.isCommutativeBinOp(N->getOpcode())) {
    SDValue N0 = N->getOperand(0);
    SDValue N1 = N->getOperand(1);
 
    // Constant operands are canonicalized to RHS.
    if (N0 != N1 && (isa<ConstantSDNode>(N0) || !isa<ConstantSDNode>(N1))) {
      SDValue Ops[] = {N1, N0};
      SDNode *CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), Ops,
                                            N->getFlags());
      if (CSENode)
        return SDValue(CSENode, 0);
    }
  }
 
  return RV;
}
 
/// Given a node, return its input chain if it has one, otherwise return a null
/// sd operand.
static SDValue getInputChainForNode(SDNode *N) {
  if (unsigned NumOps = N->getNumOperands()) {
    if (N->getOperand(0).getValueType() == MVT::Other)
      return N->getOperand(0);
    if (N->getOperand(NumOps-1).getValueType() == MVT::Other)
      return N->getOperand(NumOps-1);
    for (unsigned i = 1; i < NumOps-1; ++i)
      if (N->getOperand(i).getValueType() == MVT::Other)
        return N->getOperand(i);
  }
  return SDValue();
}
 
SDValue DAGCombiner::visitFCANONICALIZE(SDNode *N) {
  SDValue Operand = N->getOperand(0);
  EVT VT = Operand.getValueType();
  SDLoc dl(N);
 
  // Canonicalize undef to quiet NaN.
  if (Operand.isUndef()) {
    APFloat CanonicalQNaN = APFloat::getQNaN(VT.getFltSemantics());
    return DAG.getConstantFP(CanonicalQNaN, dl, VT);
  }
  return SDValue();
}
 
SDValue DAGCombiner::visitTokenFactor(SDNode *N) {
  // If N has two operands, where one has an input chain equal to the other,
  // the 'other' chain is redundant.
  if (N->getNumOperands() == 2) {
    if (getInputChainForNode(N->getOperand(0).getNode()) == N->getOperand(1))
      return N->getOperand(0);
    if (getInputChainForNode(N->getOperand(1).getNode()) == N->getOperand(0))
      return N->getOperand(1);
  }
 
  // Don't simplify token factors if optnone.
  if (OptLevel == CodeGenOptLevel::None)
    return SDValue();
 
  // Don't simplify the token factor if the node itself has too many operands.
  if (N->getNumOperands() > TokenFactorInlineLimit)
    return SDValue();
 
  // If the sole user is a token factor, we should make sure we have a
  // chance to merge them together. This prevents TF chains from inhibiting
  // optimizations.
  if (N->hasOneUse() && N->user_begin()->getOpcode() == ISD::TokenFactor)
    AddToWorklist(*(N->user_begin()));
 
  SmallVector<SDNode *, 8> TFs;     // List of token factors to visit.
  SmallVector<SDValue, 8> Ops;      // Ops for replacing token factor.
  SmallPtrSet<SDNode*, 16> SeenOps;
  bool Changed = false;             // If we should replace this token factor.
 
  // Start out with this token factor.
  TFs.push_back(N);
 
  // Iterate through token factors.  The TFs grows when new token factors are
  // encountered.
  for (unsigned i = 0; i < TFs.size(); ++i) {
    // Limit number of nodes to inline, to avoid quadratic compile times.
    // We have to add the outstanding Token Factors to Ops, otherwise we might
    // drop Ops from the resulting Token Factors.
    if (Ops.size() > TokenFactorInlineLimit) {
      for (unsigned j = i; j < TFs.size(); j++)
        Ops.emplace_back(TFs[j], 0);
      // Drop unprocessed Token Factors from TFs, so we do not add them to the
      // combiner worklist later.
      TFs.resize(i);
      break;
    }
 
    SDNode *TF = TFs[i];
    // Check each of the operands.
    for (const SDValue &Op : TF->op_values()) {
      switch (Op.getOpcode()) {
      case ISD::EntryToken:
        // Entry tokens don't need to be added to the list. They are
        // redundant.
        Changed = true;
        break;
 
      case ISD::TokenFactor:
        if (Op.hasOneUse() && !is_contained(TFs, Op.getNode())) {
          // Queue up for processing.
          TFs.push_back(Op.getNode());
          Changed = true;
          break;
        }
        [[fallthrough]];
 
      default:
        // Only add if it isn't already in the list.
        if (SeenOps.insert(Op.getNode()).second)
          Ops.push_back(Op);
        else
          Changed = true;
        break;
      }
    }
  }
 
  // Re-visit inlined Token Factors, to clean them up in case they have been
  // removed. Skip the first Token Factor, as this is the current node.
  for (unsigned i = 1, e = TFs.size(); i < e; i++)
    AddToWorklist(TFs[i]);
 
  // Remove Nodes that are chained to another node in the list. Do so
  // by walking up chains breath-first stopping when we've seen
  // another operand. In general we must climb to the EntryNode, but we can exit
  // early if we find all remaining work is associated with just one operand as
  // no further pruning is possible.
 
  // List of nodes to search through and original Ops from which they originate.
  SmallVector<std::pair<SDNode *, unsigned>, 8> Worklist;
  SmallVector<unsigned, 8> OpWorkCount; // Count of work for each Op.
  SmallPtrSet<SDNode *, 16> SeenChains;
  bool DidPruneOps = false;
 
  unsigned NumLeftToConsider = 0;
  for (const SDValue &Op : Ops) {
    Worklist.push_back(std::make_pair(Op.getNode(), NumLeftToConsider++));
    OpWorkCount.push_back(1);
  }
 
  auto AddToWorklist = [&](unsigned CurIdx, SDNode *Op, unsigned OpNumber) {
    // If this is an Op, we can remove the op from the list. Remark any
    // search associated with it as from the current OpNumber.
    if (SeenOps.contains(Op)) {
      Changed = true;
      DidPruneOps = true;
      unsigned OrigOpNumber = 0;
      while (OrigOpNumber < Ops.size() && Ops[OrigOpNumber].getNode() != Op)
        OrigOpNumber++;
      assert((OrigOpNumber != Ops.size()) &&
             "expected to find TokenFactor Operand");
      // Re-mark worklist from OrigOpNumber to OpNumber
      for (unsigned i = CurIdx + 1; i < Worklist.size(); ++i) {
        if (Worklist[i].second == OrigOpNumber) {
          Worklist[i].second = OpNumber;
        }
      }
      OpWorkCount[OpNumber] += OpWorkCount[OrigOpNumber];
      OpWorkCount[OrigOpNumber] = 0;
      NumLeftToConsider--;
    }
    // Add if it's a new chain
    if (SeenChains.insert(Op).second) {
      OpWorkCount[OpNumber]++;
      Worklist.push_back(std::make_pair(Op, OpNumber));
    }
  };
 
  for (unsigned i = 0; i < Worklist.size() && i < 1024; ++i) {
    // We need at least be consider at least 2 Ops to prune.
    if (NumLeftToConsider <= 1)
      break;
    auto CurNode = Worklist[i].first;
    auto CurOpNumber = Worklist[i].second;
    assert((OpWorkCount[CurOpNumber] > 0) &&
           "Node should not appear in worklist");
    switch (CurNode->getOpcode()) {
    case ISD::EntryToken:
      // Hitting EntryToken is the only way for the search to terminate without
      // hitting
      // another operand's search. Prevent us from marking this operand
      // considered.
      NumLeftToConsider++;
      break;
    case ISD::TokenFactor:
      for (const SDValue &Op : CurNode->op_values())
        AddToWorklist(i, Op.getNode(), CurOpNumber);
      break;
    case ISD::LIFETIME_START:
    case ISD::LIFETIME_END:
    case ISD::CopyFromReg:
    case ISD::CopyToReg:
      AddToWorklist(i, CurNode->getOperand(0).getNode(), CurOpNumber);
      break;
    default:
      if (auto *MemNode = dyn_cast<MemSDNode>(CurNode))
        AddToWorklist(i, MemNode->getChain().getNode(), CurOpNumber);
      break;
    }
    OpWorkCount[CurOpNumber]--;
    if (OpWorkCount[CurOpNumber] == 0)
      NumLeftToConsider--;
  }
 
  // If we've changed things around then replace token factor.
  if (Changed) {
    SDValue Result;
    if (Ops.empty()) {
      // The entry token is the only possible outcome.
      Result = DAG.getEntryNode();
    } else {
      if (DidPruneOps) {
        SmallVector<SDValue, 8> PrunedOps;
        //
        for (const SDValue &Op : Ops) {
          if (SeenChains.count(Op.getNode()) == 0)
            PrunedOps.push_back(Op);
        }
        Result = DAG.getTokenFactor(SDLoc(N), PrunedOps);
      } else {
        Result = DAG.getTokenFactor(SDLoc(N), Ops);
      }
    }
    return Result;
  }
  return SDValue();
}
 
/// MERGE_VALUES can always be eliminated.
SDValue DAGCombiner::visitMERGE_VALUES(SDNode *N) {
  WorklistRemover DeadNodes(*this);
  // Replacing results may cause a different MERGE_VALUES to suddenly
  // be CSE'd with N, and carry its uses with it. Iterate until no
  // uses remain, to ensure that the node can be safely deleted.
  // First add the users of this node to the work list so that they
  // can be tried again once they have new operands.
  AddUsersToWorklist(N);
  do {
    // Do as a single replacement to avoid rewalking use lists.
    SmallVector<SDValue, 8> Ops(N->ops());
    DAG.ReplaceAllUsesWith(N, Ops.data());
  } while (!N->use_empty());
  deleteAndRecombine(N);
  return SDValue(N, 0);   // Return N so it doesn't get rechecked!
}
 
/// If \p N is a ConstantSDNode with isOpaque() == false return it casted to a
/// ConstantSDNode pointer else nullptr.
static ConstantSDNode *getAsNonOpaqueConstant(SDValue N) {
  ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N);
  return Const != nullptr && !Const->isOpaque() ? Const : nullptr;
}
 
// isTruncateOf - If N is a truncate of some other value, return true, record
// the value being truncated in Op and which of Op's bits are zero/one in Known.
// This function computes KnownBits to avoid a duplicated call to
// computeKnownBits in the caller.
static bool isTruncateOf(SelectionDAG &DAG, SDValue N, SDValue &Op,
                         KnownBits &Known) {
  if (N->getOpcode() == ISD::TRUNCATE) {
    Op = N->getOperand(0);
    Known = DAG.computeKnownBits(Op);
    if (N->getFlags().hasNoUnsignedWrap())
      Known.Zero.setBitsFrom(N.getScalarValueSizeInBits());
    return true;
  }
 
  if (N.getValueType().getScalarType() != MVT::i1 ||
      !sd_match(
          N, m_c_SetCC(m_Value(Op), m_Zero(), m_SpecificCondCode(ISD::SETNE))))
    return false;
 
  Known = DAG.computeKnownBits(Op);
  return (Known.Zero | 1).isAllOnes();
}
 
/// Return true if 'Use' is a load or a store that uses N as its base pointer
/// and that N may be folded in the load / store addressing mode.
static bool canFoldInAddressingMode(SDNode *N, SDNode *Use, SelectionDAG &DAG,
                                    const TargetLowering &TLI) {
  EVT VT;
  unsigned AS;
 
  if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Use)) {
    if (LD->isIndexed() || LD->getBasePtr().getNode() != N)
      return false;
    VT = LD->getMemoryVT();
    AS = LD->getAddressSpace();
  } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(Use)) {
    if (ST->isIndexed() || ST->getBasePtr().getNode() != N)
      return false;
    VT = ST->getMemoryVT();
    AS = ST->getAddressSpace();
  } else if (MaskedLoadSDNode *LD = dyn_cast<MaskedLoadSDNode>(Use)) {
    if (LD->isIndexed() || LD->getBasePtr().getNode() != N)
      return false;
    VT = LD->getMemoryVT();
    AS = LD->getAddressSpace();
  } else if (MaskedStoreSDNode *ST = dyn_cast<MaskedStoreSDNode>(Use)) {
    if (ST->isIndexed() || ST->getBasePtr().getNode() != N)
      return false;
    VT = ST->getMemoryVT();
    AS = ST->getAddressSpace();
  } else {
    return false;
  }
 
  TargetLowering::AddrMode AM;
  if (N->getOpcode() == ISD::ADD) {
    AM.HasBaseReg = true;
    ConstantSDNode *Offset = dyn_cast<ConstantSDNode>(N->getOperand(1));
    if (Offset)
      // [reg +/- imm]
      AM.BaseOffs = Offset->getSExtValue();
    else
      // [reg +/- reg]
      AM.Scale = 1;
  } else if (N->getOpcode() == ISD::SUB) {
    AM.HasBaseReg = true;
    ConstantSDNode *Offset = dyn_cast<ConstantSDNode>(N->getOperand(1));
    if (Offset)
      // [reg +/- imm]
      AM.BaseOffs = -Offset->getSExtValue();
    else
      // [reg +/- reg]
      AM.Scale = 1;
  } else {
    return false;
  }
 
  return TLI.isLegalAddressingMode(DAG.getDataLayout(), AM,
                                   VT.getTypeForEVT(*DAG.getContext()), AS);
}
 
/// This inverts a canonicalization in IR that replaces a variable select arm
/// with an identity constant. Codegen improves if we re-use the variable
/// operand rather than load a constant. This can also be converted into a
/// masked vector operation if the target supports it.
static SDValue foldSelectWithIdentityConstant(SDNode *N, SelectionDAG &DAG,
                                              bool ShouldCommuteOperands) {
  // Match a select as operand 1. The identity constant that we are looking for
  // is only valid as operand 1 of a non-commutative binop.
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  if (ShouldCommuteOperands)
    std::swap(N0, N1);
 
  // TODO: Should this apply to scalar select too?
  if (N1.getOpcode() != ISD::VSELECT || !N1.hasOneUse())
    return SDValue();
 
  // We can't hoist all instructions because of immediate UB (not speculatable).
  // For example div/rem by zero.
  if (!DAG.isSafeToSpeculativelyExecuteNode(N))
    return SDValue();
 
  unsigned Opcode = N->getOpcode();
  EVT VT = N->getValueType(0);
  SDValue Cond = N1.getOperand(0);
  SDValue TVal = N1.getOperand(1);
  SDValue FVal = N1.getOperand(2);
 
  // This transform increases uses of N0, so freeze it to be safe.
  // binop N0, (vselect Cond, IDC, FVal) --> vselect Cond, N0, (binop N0, FVal)
  unsigned OpNo = ShouldCommuteOperands ? 0 : 1;
  if (isNeutralConstant(Opcode, N->getFlags(), TVal, OpNo)) {
    SDValue F0 = DAG.getFreeze(N0);
    SDValue NewBO = DAG.getNode(Opcode, SDLoc(N), VT, F0, FVal, N->getFlags());
    return DAG.getSelect(SDLoc(N), VT, Cond, F0, NewBO);
  }
  // binop N0, (vselect Cond, TVal, IDC) --> vselect Cond, (binop N0, TVal), N0
  if (isNeutralConstant(Opcode, N->getFlags(), FVal, OpNo)) {
    SDValue F0 = DAG.getFreeze(N0);
    SDValue NewBO = DAG.getNode(Opcode, SDLoc(N), VT, F0, TVal, N->getFlags());
    return DAG.getSelect(SDLoc(N), VT, Cond, NewBO, F0);
  }
 
  return SDValue();
}
 
SDValue DAGCombiner::foldBinOpIntoSelect(SDNode *BO) {
  assert(TLI.isBinOp(BO->getOpcode()) && BO->getNumValues() == 1 &&
         "Unexpected binary operator");
 
  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
  auto BinOpcode = BO->getOpcode();
  EVT VT = BO->getValueType(0);
  if (TLI.shouldFoldSelectWithIdentityConstant(BinOpcode, VT)) {
    if (SDValue Sel = foldSelectWithIdentityConstant(BO, DAG, false))
      return Sel;
 
    if (TLI.isCommutativeBinOp(BO->getOpcode()))
      if (SDValue Sel = foldSelectWithIdentityConstant(BO, DAG, true))
        return Sel;
  }
 
  // Don't do this unless the old select is going away. We want to eliminate the
  // binary operator, not replace a binop with a select.
  // TODO: Handle ISD::SELECT_CC.
  unsigned SelOpNo = 0;
  SDValue Sel = BO->getOperand(0);
  if (Sel.getOpcode() != ISD::SELECT || !Sel.hasOneUse()) {
    SelOpNo = 1;
    Sel = BO->getOperand(1);
 
    // Peek through trunc to shift amount type.
    if ((BinOpcode == ISD::SHL || BinOpcode == ISD::SRA ||
         BinOpcode == ISD::SRL) && Sel.hasOneUse()) {
      // This is valid when the truncated bits of x are already zero.
      SDValue Op;
      KnownBits Known;
      if (isTruncateOf(DAG, Sel, Op, Known) &&
          Known.countMaxActiveBits() < Sel.getScalarValueSizeInBits())
        Sel = Op;
    }
  }
 
  if (Sel.getOpcode() != ISD::SELECT || !Sel.hasOneUse())
    return SDValue();
 
  SDValue CT = Sel.getOperand(1);
  if (!isConstantOrConstantVector(CT, true) &&
      !DAG.isConstantFPBuildVectorOrConstantFP(CT))
    return SDValue();
 
  SDValue CF = Sel.getOperand(2);
  if (!isConstantOrConstantVector(CF, true) &&
      !DAG.isConstantFPBuildVectorOrConstantFP(CF))
    return SDValue();
 
  // Bail out if any constants are opaque because we can't constant fold those.
  // The exception is "and" and "or" with either 0 or -1 in which case we can
  // propagate non constant operands into select. I.e.:
  // and (select Cond, 0, -1), X --> select Cond, 0, X
  // or X, (select Cond, -1, 0) --> select Cond, -1, X
  bool CanFoldNonConst =
      (BinOpcode == ISD::AND || BinOpcode == ISD::OR) &&
      ((isNullOrNullSplat(CT) && isAllOnesOrAllOnesSplat(CF)) ||
       (isNullOrNullSplat(CF) && isAllOnesOrAllOnesSplat(CT)));
 
  SDValue CBO = BO->getOperand(SelOpNo ^ 1);
  if (!CanFoldNonConst &&
      !isConstantOrConstantVector(CBO, true) &&
      !DAG.isConstantFPBuildVectorOrConstantFP(CBO))
    return SDValue();
 
  SDLoc DL(Sel);
  SDValue NewCT, NewCF;
 
  if (CanFoldNonConst) {
    // If CBO is an opaque constant, we can't rely on getNode to constant fold.
    if ((BinOpcode == ISD::AND && isNullOrNullSplat(CT)) ||
        (BinOpcode == ISD::OR && isAllOnesOrAllOnesSplat(CT)))
      NewCT = CT;
    else
      NewCT = CBO;
 
    if ((BinOpcode == ISD::AND && isNullOrNullSplat(CF)) ||
        (BinOpcode == ISD::OR && isAllOnesOrAllOnesSplat(CF)))
      NewCF = CF;
    else
      NewCF = CBO;
  } else {
    // We have a select-of-constants followed by a binary operator with a
    // constant. Eliminate the binop by pulling the constant math into the
    // select. Example: add (select Cond, CT, CF), CBO --> select Cond, CT +
    // CBO, CF + CBO
    NewCT = SelOpNo ? DAG.FoldConstantArithmetic(BinOpcode, DL, VT, {CBO, CT})
                    : DAG.FoldConstantArithmetic(BinOpcode, DL, VT, {CT, CBO});
    if (!NewCT)
      return SDValue();
 
    NewCF = SelOpNo ? DAG.FoldConstantArithmetic(BinOpcode, DL, VT, {CBO, CF})
                    : DAG.FoldConstantArithmetic(BinOpcode, DL, VT, {CF, CBO});
    if (!NewCF)
      return SDValue();
  }
 
  SDValue SelectOp = DAG.getSelect(DL, VT, Sel.getOperand(0), NewCT, NewCF);
  SelectOp->setFlags(BO->getFlags());
  return SelectOp;
}
 
static SDValue foldAddSubBoolOfMaskedVal(SDNode *N, const SDLoc &DL,
                                         SelectionDAG &DAG) {
  assert((N->getOpcode() == ISD::ADD || N->getOpcode() == ISD::SUB) &&
         "Expecting add or sub");
 
  // Match a constant operand and a zext operand for the math instruction:
  // add Z, C
  // sub C, Z
  bool IsAdd = N->getOpcode() == ISD::ADD;
  SDValue C = IsAdd ? N->getOperand(1) : N->getOperand(0);
  SDValue Z = IsAdd ? N->getOperand(0) : N->getOperand(1);
  auto *CN = dyn_cast<ConstantSDNode>(C);
  if (!CN || Z.getOpcode() != ISD::ZERO_EXTEND)
    return SDValue();
 
  // Match the zext operand as a setcc of a boolean.
  if (Z.getOperand(0).getValueType() != MVT::i1)
    return SDValue();
 
  // Match the compare as: setcc (X & 1), 0, eq.
  if (!sd_match(Z.getOperand(0), m_SetCC(m_And(m_Value(), m_One()), m_Zero(),
                                         m_SpecificCondCode(ISD::SETEQ))))
    return SDValue();
 
  // We are adding/subtracting a constant and an inverted low bit. Turn that
  // into a subtract/add of the low bit with incremented/decremented constant:
  // add (zext i1 (seteq (X & 1), 0)), C --> sub C+1, (zext (X & 1))
  // sub C, (zext i1 (seteq (X & 1), 0)) --> add C-1, (zext (X & 1))
  EVT VT = C.getValueType();
  SDValue LowBit = DAG.getZExtOrTrunc(Z.getOperand(0).getOperand(0), DL, VT);
  SDValue C1 = IsAdd ? DAG.getConstant(CN->getAPIntValue() + 1, DL, VT)
                     : DAG.getConstant(CN->getAPIntValue() - 1, DL, VT);
  return DAG.getNode(IsAdd ? ISD::SUB : ISD::ADD, DL, VT, C1, LowBit);
}
 
// Attempt to form avgceil(A, B) from (A | B) - ((A ^ B) >> 1)
SDValue DAGCombiner::foldSubToAvg(SDNode *N, const SDLoc &DL) {
  SDValue N0 = N->getOperand(0);
  EVT VT = N0.getValueType();
  SDValue A, B;
 
  if ((!LegalOperations || hasOperation(ISD::AVGCEILU, VT)) &&
      sd_match(N, m_Sub(m_Or(m_Value(A), m_Value(B)),
                        m_Srl(m_Xor(m_Deferred(A), m_Deferred(B)), m_One())))) {
    return DAG.getNode(ISD::AVGCEILU, DL, VT, A, B);
  }
  if ((!LegalOperations || hasOperation(ISD::AVGCEILS, VT)) &&
      sd_match(N, m_Sub(m_Or(m_Value(A), m_Value(B)),
                        m_Sra(m_Xor(m_Deferred(A), m_Deferred(B)), m_One())))) {
    return DAG.getNode(ISD::AVGCEILS, DL, VT, A, B);
  }
  return SDValue();
}
 
/// Try to fold a 'not' shifted sign-bit with add/sub with constant operand into
/// a shift and add with a different constant.
static SDValue foldAddSubOfSignBit(SDNode *N, const SDLoc &DL,
                                   SelectionDAG &DAG) {
  assert((N->getOpcode() == ISD::ADD || N->getOpcode() == ISD::SUB) &&
         "Expecting add or sub");
 
  // We need a constant operand for the add/sub, and the other operand is a
  // logical shift right: add (srl), C or sub C, (srl).
  bool IsAdd = N->getOpcode() == ISD::ADD;
  SDValue ConstantOp = IsAdd ? N->getOperand(1) : N->getOperand(0);
  SDValue ShiftOp = IsAdd ? N->getOperand(0) : N->getOperand(1);
  if (!DAG.isConstantIntBuildVectorOrConstantInt(ConstantOp) ||
      ShiftOp.getOpcode() != ISD::SRL)
    return SDValue();
 
  // The shift must be of a 'not' value.
  SDValue Not = ShiftOp.getOperand(0);
  if (!Not.hasOneUse() || !isBitwiseNot(Not))
    return SDValue();
 
  // The shift must be moving the sign bit to the least-significant-bit.
  EVT VT = ShiftOp.getValueType();
  SDValue ShAmt = ShiftOp.getOperand(1);
  ConstantSDNode *ShAmtC = isConstOrConstSplat(ShAmt);
  if (!ShAmtC || ShAmtC->getAPIntValue() != (VT.getScalarSizeInBits() - 1))
    return SDValue();
 
  // Eliminate the 'not' by adjusting the shift and add/sub constant:
  // add (srl (not X), 31), C --> add (sra X, 31), (C + 1)
  // sub C, (srl (not X), 31) --> add (srl X, 31), (C - 1)
  if (SDValue NewC = DAG.FoldConstantArithmetic(
          IsAdd ? ISD::ADD : ISD::SUB, DL, VT,
          {ConstantOp, DAG.getConstant(1, DL, VT)})) {
    SDValue NewShift = DAG.getNode(IsAdd ? ISD::SRA : ISD::SRL, DL, VT,
                                   Not.getOperand(0), ShAmt);
    return DAG.getNode(ISD::ADD, DL, VT, NewShift, NewC);
  }
 
  return SDValue();
}
 
static bool
areBitwiseNotOfEachother(SDValue Op0, SDValue Op1) {
  return (isBitwiseNot(Op0) && Op0.getOperand(0) == Op1) ||
         (isBitwiseNot(Op1) && Op1.getOperand(0) == Op0);
}
 
/// Try to fold a node that behaves like an ADD (note that N isn't necessarily
/// an ISD::ADD here, it could for example be an ISD::OR if we know that there
/// are no common bits set in the operands).
SDValue DAGCombiner::visitADDLike(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  EVT VT = N0.getValueType();
  SDLoc DL(N);
 
  // fold (add x, undef) -> undef
  if (N0.isUndef())
    return N0;
  if (N1.isUndef())
    return N1;
 
  // fold (add c1, c2) -> c1+c2
  if (SDValue C = DAG.FoldConstantArithmetic(ISD::ADD, DL, VT, {N0, N1}))
    return C;
 
  // canonicalize constant to RHS
  if (DAG.isConstantIntBuildVectorOrConstantInt(N0) &&
      !DAG.isConstantIntBuildVectorOrConstantInt(N1))
    return DAG.getNode(ISD::ADD, DL, VT, N1, N0);
 
  if (areBitwiseNotOfEachother(N0, N1))
    return DAG.getConstant(APInt::getAllOnes(VT.getScalarSizeInBits()), DL, VT);
 
  // fold vector ops
  if (VT.isVector()) {
    if (SDValue FoldedVOp = SimplifyVBinOp(N, DL))
      return FoldedVOp;
 
    // fold (add x, 0) -> x, vector edition
    if (ISD::isConstantSplatVectorAllZeros(N1.getNode()))
      return N0;
  }
 
  // fold (add x, 0) -> x
  if (isNullConstant(N1))
    return N0;
 
  if (N0.getOpcode() == ISD::SUB) {
    SDValue N00 = N0.getOperand(0);
    SDValue N01 = N0.getOperand(1);
 
    // fold ((A-c1)+c2) -> (A+(c2-c1))
    if (SDValue Sub = DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, {N1, N01}))
      return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), Sub);
 
    // fold ((c1-A)+c2) -> (c1+c2)-A
    if (SDValue Add = DAG.FoldConstantArithmetic(ISD::ADD, DL, VT, {N1, N00}))
      return DAG.getNode(ISD::SUB, DL, VT, Add, N0.getOperand(1));
  }
 
  // add (sext i1 X), 1 -> zext (not i1 X)
  // We don't transform this pattern:
  //   add (zext i1 X), -1 -> sext (not i1 X)
  // because most (?) targets generate better code for the zext form.
  if (N0.getOpcode() == ISD::SIGN_EXTEND && N0.hasOneUse() &&
      isOneOrOneSplat(N1)) {
    SDValue X = N0.getOperand(0);
    if ((!LegalOperations ||
         (TLI.isOperationLegal(ISD::XOR, X.getValueType()) &&
          TLI.isOperationLegal(ISD::ZERO_EXTEND, VT))) &&
        X.getScalarValueSizeInBits() == 1) {
      SDValue Not = DAG.getNOT(DL, X, X.getValueType());
      return DAG.getNode(ISD::ZERO_EXTEND, DL, VT, Not);
    }
  }
 
  // Fold (add (or x, c0), c1) -> (add x, (c0 + c1))
  // iff (or x, c0) is equivalent to (add x, c0).
  // Fold (add (xor x, c0), c1) -> (add x, (c0 + c1))
  // iff (xor x, c0) is equivalent to (add x, c0).
  if (DAG.isADDLike(N0)) {
    SDValue N01 = N0.getOperand(1);
    if (SDValue Add = DAG.FoldConstantArithmetic(ISD::ADD, DL, VT, {N1, N01}))
      return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), Add);
  }
 
  if (SDValue NewSel = foldBinOpIntoSelect(N))
    return NewSel;
 
  // reassociate add
  if (!reassociationCanBreakAddressingModePattern(ISD::ADD, DL, N, N0, N1)) {
    if (SDValue RADD = reassociateOps(ISD::ADD, DL, N0, N1, N->getFlags()))
      return RADD;
 
    // Reassociate (add (or x, c), y) -> (add add(x, y), c)) if (or x, c) is
    // equivalent to (add x, c).
    // Reassociate (add (xor x, c), y) -> (add add(x, y), c)) if (xor x, c) is
    // equivalent to (add x, c).
    // Do this optimization only when adding c does not introduce instructions
    // for adding carries.
    auto ReassociateAddOr = [&](SDValue N0, SDValue N1) {
      if (DAG.isADDLike(N0) && N0.hasOneUse() &&
          isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true)) {
        // If N0's type does not split or is a sign mask, it does not introduce
        // add carry.
        auto TyActn = TLI.getTypeAction(*DAG.getContext(), N0.getValueType());
        bool NoAddCarry = TyActn == TargetLoweringBase::TypeLegal ||
                          TyActn == TargetLoweringBase::TypePromoteInteger ||
                          isMinSignedConstant(N0.getOperand(1));
        if (NoAddCarry)
          return DAG.getNode(
              ISD::ADD, DL, VT,
              DAG.getNode(ISD::ADD, DL, VT, N1, N0.getOperand(0)),
              N0.getOperand(1));
      }
      return SDValue();
    };
    if (SDValue Add = ReassociateAddOr(N0, N1))
      return Add;
    if (SDValue Add = ReassociateAddOr(N1, N0))
      return Add;
 
    // Fold add(vecreduce(x), vecreduce(y)) -> vecreduce(add(x, y))
    if (SDValue SD =
            reassociateReduction(ISD::VECREDUCE_ADD, ISD::ADD, DL, VT, N0, N1))
      return SD;
  }
 
  SDValue A, B, C, D;
 
  // fold ((0-A) + B) -> B-A
  if (sd_match(N0, m_Neg(m_Value(A))))
    return DAG.getNode(ISD::SUB, DL, VT, N1, A);
 
  // fold (A + (0-B)) -> A-B
  if (sd_match(N1, m_Neg(m_Value(B))))
    return DAG.getNode(ISD::SUB, DL, VT, N0, B);
 
  // fold (A+(B-A)) -> B
  if (sd_match(N1, m_Sub(m_Value(B), m_Specific(N0))))
    return B;
 
  // fold ((B-A)+A) -> B
  if (sd_match(N0, m_Sub(m_Value(B), m_Specific(N1))))
    return B;
 
  // fold ((A-B)+(C-A)) -> (C-B)
  if (sd_match(N0, m_Sub(m_Value(A), m_Value(B))) &&
      sd_match(N1, m_Sub(m_Value(C), m_Specific(A))))
    return DAG.getNode(ISD::SUB, DL, VT, C, B);
 
  // fold ((A-B)+(B-C)) -> (A-C)
  if (sd_match(N0, m_Sub(m_Value(A), m_Value(B))) &&
      sd_match(N1, m_Sub(m_Specific(B), m_Value(C))))
    return DAG.getNode(ISD::SUB, DL, VT, A, C);
 
  // fold (A+(B-(A+C))) to (B-C)
  // fold (A+(B-(C+A))) to (B-C)
  if (sd_match(N1, m_Sub(m_Value(B), m_Add(m_Specific(N0), m_Value(C)))))
    return DAG.getNode(ISD::SUB, DL, VT, B, C);
 
  // fold (A+((B-A)+or-C)) to (B+or-C)
  if (sd_match(N1,
               m_AnyOf(m_Add(m_Sub(m_Value(B), m_Specific(N0)), m_Value(C)),
                       m_Sub(m_Sub(m_Value(B), m_Specific(N0)), m_Value(C)))))
    return DAG.getNode(N1.getOpcode(), DL, VT, B, C);
 
  // fold (A-B)+(C-D) to (A+C)-(B+D) when A or C is constant
  if (sd_match(N0, m_OneUse(m_Sub(m_Value(A), m_Value(B)))) &&
      sd_match(N1, m_OneUse(m_Sub(m_Value(C), m_Value(D)))) &&
      (isConstantOrConstantVector(A) || isConstantOrConstantVector(C)))
    return DAG.getNode(ISD::SUB, DL, VT,
                       DAG.getNode(ISD::ADD, SDLoc(N0), VT, A, C),
                       DAG.getNode(ISD::ADD, SDLoc(N1), VT, B, D));
 
  // fold (add (umax X, C), -C) --> (usubsat X, C)
  if (N0.getOpcode() == ISD::UMAX && hasOperation(ISD::USUBSAT, VT)) {
    auto MatchUSUBSAT = [](ConstantSDNode *Max, ConstantSDNode *Op) {
      return (!Max && !Op) ||
             (Max && Op && Max->getAPIntValue() == (-Op->getAPIntValue()));
    };
    if (ISD::matchBinaryPredicate(N0.getOperand(1), N1, MatchUSUBSAT,
                                  /*AllowUndefs*/ true))
      return DAG.getNode(ISD::USUBSAT, DL, VT, N0.getOperand(0),
                         N0.getOperand(1));
  }
 
  if (SimplifyDemandedBits(SDValue(N, 0)))
    return SDValue(N, 0);
 
  if (isOneOrOneSplat(N1)) {
    // fold (add (xor a, -1), 1) -> (sub 0, a)
    if (isBitwiseNot(N0))
      return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT),
                         N0.getOperand(0));
 
    // fold (add (add (xor a, -1), b), 1) -> (sub b, a)
    if (N0.getOpcode() == ISD::ADD) {
      SDValue A, Xor;
 
      if (isBitwiseNot(N0.getOperand(0))) {
        A = N0.getOperand(1);
        Xor = N0.getOperand(0);
      } else if (isBitwiseNot(N0.getOperand(1))) {
        A = N0.getOperand(0);
        Xor = N0.getOperand(1);
      }
 
      if (Xor)
        return DAG.getNode(ISD::SUB, DL, VT, A, Xor.getOperand(0));
    }
 
    // Look for:
    //   add (add x, y), 1
    // And if the target does not like this form then turn into:
    //   sub y, (xor x, -1)
    if (!TLI.preferIncOfAddToSubOfNot(VT) && N0.getOpcode() == ISD::ADD &&
        N0.hasOneUse() &&
        // Limit this to after legalization if the add has wrap flags
        (Level >= AfterLegalizeDAG || (!N->getFlags().hasNoUnsignedWrap() &&
                                       !N->getFlags().hasNoSignedWrap()))) {
      SDValue Not = DAG.getNOT(DL, N0.getOperand(0), VT);
      return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(1), Not);
    }
  }
 
  // (x - y) + -1  ->  add (xor y, -1), x
  if (N0.getOpcode() == ISD::SUB && N0.hasOneUse() &&
      isAllOnesOrAllOnesSplat(N1, /*AllowUndefs=*/true)) {
    SDValue Not = DAG.getNOT(DL, N0.getOperand(1), VT);
    return DAG.getNode(ISD::ADD, DL, VT, Not, N0.getOperand(0));
  }
 
  // Fold add(mul(add(A, CA), CM), CB) -> add(mul(A, CM), CM*CA+CB).
  // This can help if the inner add has multiple uses.
  APInt CM, CA;
  if (ConstantSDNode *CB = dyn_cast<ConstantSDNode>(N1)) {
    if (VT.getScalarSizeInBits() <= 64) {
      if (sd_match(N0, m_OneUse(m_Mul(m_Add(m_Value(A), m_ConstInt(CA)),
                                      m_ConstInt(CM)))) &&
          TLI.isLegalAddImmediate(
              (CA * CM + CB->getAPIntValue()).getSExtValue())) {
        SDNodeFlags Flags;
        // If all the inputs are nuw, the outputs can be nuw. If all the input
        // are _also_ nsw the outputs can be too.
        if (N->getFlags().hasNoUnsignedWrap() &&
            N0->getFlags().hasNoUnsignedWrap() &&
            N0.getOperand(0)->getFlags().hasNoUnsignedWrap()) {
          Flags |= SDNodeFlags::NoUnsignedWrap;
          if (N->getFlags().hasNoSignedWrap() &&
              N0->getFlags().hasNoSignedWrap() &&
              N0.getOperand(0)->getFlags().hasNoSignedWrap())
            Flags |= SDNodeFlags::NoSignedWrap;
        }
        SDValue Mul = DAG.getNode(ISD::MUL, SDLoc(N1), VT, A,
                                  DAG.getConstant(CM, DL, VT), Flags);
        return DAG.getNode(
            ISD::ADD, DL, VT, Mul,
            DAG.getConstant(CA * CM + CB->getAPIntValue(), DL, VT), Flags);
      }
      // Also look in case there is an intermediate add.
      if (sd_match(N0, m_OneUse(m_Add(
                           m_OneUse(m_Mul(m_Add(m_Value(A), m_ConstInt(CA)),
                                          m_ConstInt(CM))),
                           m_Value(B)))) &&
          TLI.isLegalAddImmediate(
              (CA * CM + CB->getAPIntValue()).getSExtValue())) {
        SDNodeFlags Flags;
        // If all the inputs are nuw, the outputs can be nuw. If all the input
        // are _also_ nsw the outputs can be too.
        SDValue OMul =
            N0.getOperand(0) == B ? N0.getOperand(1) : N0.getOperand(0);
        if (N->getFlags().hasNoUnsignedWrap() &&
            N0->getFlags().hasNoUnsignedWrap() &&
            OMul->getFlags().hasNoUnsignedWrap() &&
            OMul.getOperand(0)->getFlags().hasNoUnsignedWrap()) {
          Flags |= SDNodeFlags::NoUnsignedWrap;
          if (N->getFlags().hasNoSignedWrap() &&
              N0->getFlags().hasNoSignedWrap() &&
              OMul->getFlags().hasNoSignedWrap() &&
              OMul.getOperand(0)->getFlags().hasNoSignedWrap())
            Flags |= SDNodeFlags::NoSignedWrap;
        }
        SDValue Mul = DAG.getNode(ISD::MUL, SDLoc(N1), VT, A,
                                  DAG.getConstant(CM, DL, VT), Flags);
        SDValue Add = DAG.getNode(ISD::ADD, SDLoc(N1), VT, Mul, B, Flags);
        return DAG.getNode(
            ISD::ADD, DL, VT, Add,
            DAG.getConstant(CA * CM + CB->getAPIntValue(), DL, VT), Flags);
      }
    }
  }
 
  if (SDValue Combined = visitADDLikeCommutative(N0, N1, N))
    return Combined;
 
  if (SDValue Combined = visitADDLikeCommutative(N1, N0, N))
    return Combined;
 
  return SDValue();
}
 
// Attempt to form avgfloor(A, B) from (A & B) + ((A ^ B) >> 1)
SDValue DAGCombiner::foldAddToAvg(SDNode *N, const SDLoc &DL) {
  SDValue N0 = N->getOperand(0);
  EVT VT = N0.getValueType();
  SDValue A, B;
 
  if ((!LegalOperations || hasOperation(ISD::AVGFLOORU, VT)) &&
      sd_match(N, m_Add(m_And(m_Value(A), m_Value(B)),
                        m_Srl(m_Xor(m_Deferred(A), m_Deferred(B)), m_One())))) {
    return DAG.getNode(ISD::AVGFLOORU, DL, VT, A, B);
  }
  if ((!LegalOperations || hasOperation(ISD::AVGFLOORS, VT)) &&
      sd_match(N, m_Add(m_And(m_Value(A), m_Value(B)),
                        m_Sra(m_Xor(m_Deferred(A), m_Deferred(B)), m_One())))) {
    return DAG.getNode(ISD::AVGFLOORS, DL, VT, A, B);
  }
 
  return SDValue();
}
 
SDValue DAGCombiner::visitADD(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  EVT VT = N0.getValueType();
  SDLoc DL(N);
 
  if (SDValue Combined = visitADDLike(N))
    return Combined;
 
  if (SDValue V = foldAddSubBoolOfMaskedVal(N, DL, DAG))
    return V;
 
  if (SDValue V = foldAddSubOfSignBit(N, DL, DAG))
    return V;
 
  // Try to match AVGFLOOR fixedwidth pattern
  if (SDValue V = foldAddToAvg(N, DL))
    return V;
 
  // fold (a+b) -> (a|b) iff a and b share no bits.
  if ((!LegalOperations || TLI.isOperationLegal(ISD::OR, VT)) &&
      DAG.haveNoCommonBitsSet(N0, N1))
    return DAG.getNode(ISD::OR, DL, VT, N0, N1, SDNodeFlags::Disjoint);
 
  // Fold (add (vscale * C0), (vscale * C1)) to (vscale * (C0 + C1)).
  if (N0.getOpcode() == ISD::VSCALE && N1.getOpcode() == ISD::VSCALE) {
    const APInt &C0 = N0->getConstantOperandAPInt(0);
    const APInt &C1 = N1->getConstantOperandAPInt(0);
    return DAG.getVScale(DL, VT, C0 + C1);
  }
 
  // fold a+vscale(c1)+vscale(c2) -> a+vscale(c1+c2)
  if (N0.getOpcode() == ISD::ADD &&
      N0.getOperand(1).getOpcode() == ISD::VSCALE &&
      N1.getOpcode() == ISD::VSCALE) {
    const APInt &VS0 = N0.getOperand(1)->getConstantOperandAPInt(0);
    const APInt &VS1 = N1->getConstantOperandAPInt(0);
    SDValue VS = DAG.getVScale(DL, VT, VS0 + VS1);
    return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), VS);
  }
 
  // Fold (add step_vector(c1), step_vector(c2)  to step_vector(c1+c2))
  if (N0.getOpcode() == ISD::STEP_VECTOR &&
      N1.getOpcode() == ISD::STEP_VECTOR) {
    const APInt &C0 = N0->getConstantOperandAPInt(0);
    const APInt &C1 = N1->getConstantOperandAPInt(0);
    APInt NewStep = C0 + C1;
    return DAG.getStepVector(DL, VT, NewStep);
  }
 
  // Fold a + step_vector(c1) + step_vector(c2) to a + step_vector(c1+c2)
  if (N0.getOpcode() == ISD::ADD &&
      N0.getOperand(1).getOpcode() == ISD::STEP_VECTOR &&
      N1.getOpcode() == ISD::STEP_VECTOR) {
    const APInt &SV0 = N0.getOperand(1)->getConstantOperandAPInt(0);
    const APInt &SV1 = N1->getConstantOperandAPInt(0);
    APInt NewStep = SV0 + SV1;
    SDValue SV = DAG.getStepVector(DL, VT, NewStep);
    return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), SV);
  }
 
  return SDValue();
}
 
SDValue DAGCombiner::visitADDSAT(SDNode *N) {
  unsigned Opcode = N->getOpcode();
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  EVT VT = N0.getValueType();
  bool IsSigned = Opcode == ISD::SADDSAT;
  SDLoc DL(N);
 
  // fold (add_sat x, undef) -> -1
  if (N0.isUndef() || N1.isUndef())
    return DAG.getAllOnesConstant(DL, VT);
 
  // fold (add_sat c1, c2) -> c3
  if (SDValue C = DAG.FoldConstantArithmetic(Opcode, DL, VT, {N0, N1}))
    return C;
 
  // canonicalize constant to RHS
  if (DAG.isConstantIntBuildVectorOrConstantInt(N0) &&
      !DAG.isConstantIntBuildVectorOrConstantInt(N1))
    return DAG.getNode(Opcode, DL, VT, N1, N0);
 
  // fold vector ops
  if (VT.isVector()) {
    if (SDValue FoldedVOp = SimplifyVBinOp(N, DL))
      return FoldedVOp;
 
    // fold (add_sat x, 0) -> x, vector edition
    if (ISD::isConstantSplatVectorAllZeros(N1.getNode()))
      return N0;
  }
 
  // fold (add_sat x, 0) -> x
  if (isNullConstant(N1))
    return N0;
 
  // If it cannot overflow, transform into an add.
  if (DAG.willNotOverflowAdd(IsSigned, N0, N1))
    return DAG.getNode(ISD::ADD, DL, VT, N0, N1);
 
  return SDValue();
}
 
static SDValue getAsCarry(const TargetLowering &TLI, SDValue V,
                          bool ForceCarryReconstruction = false) {
  bool Masked = false;
 
  // First, peel away TRUNCATE/ZERO_EXTEND/AND nodes due to legalization.
  while (true) {
    if (V.getOpcode() == ISD::TRUNCATE || V.getOpcode() == ISD::ZERO_EXTEND) {
      V = V.getOperand(0);
      continue;
    }
 
    if (V.getOpcode() == ISD::AND && isOneConstant(V.getOperand(1))) {
      if (ForceCarryReconstruction)
        return V;
 
      Masked = true;
      V = V.getOperand(0);
      continue;
    }
 
    if (ForceCarryReconstruction && V.getValueType() == MVT::i1)
      return V;
 
    break;
  }
 
  // If this is not a carry, return.
  if (V.getResNo() != 1)
    return SDValue();
 
  if (V.getOpcode() != ISD::UADDO_CARRY && V.getOpcode() != ISD::USUBO_CARRY &&
      V.getOpcode() != ISD::UADDO && V.getOpcode() != ISD::USUBO)
    return SDValue();
 
  EVT VT = V->getValueType(0);
  if (!TLI.isOperationLegalOrCustom(V.getOpcode(), VT))
    return SDValue();
 
  // If the result is masked, then no matter what kind of bool it is we can
  // return. If it isn't, then we need to make sure the bool type is either 0 or
  // 1 and not other values.
  if (Masked ||
      TLI.getBooleanContents(V.getValueType()) ==
          TargetLoweringBase::ZeroOrOneBooleanContent)
    return V;
 
  return SDValue();
}
 
/// Given the operands of an add/sub operation, see if the 2nd operand is a
/// masked 0/1 whose source operand is actually known to be 0/-1. If so, invert
/// the opcode and bypass the mask operation.
static SDValue foldAddSubMasked1(bool IsAdd, SDValue N0, SDValue N1,
                                 SelectionDAG &DAG, const SDLoc &DL) {
  if (N1.getOpcode() == ISD::ZERO_EXTEND)
    N1 = N1.getOperand(0);
 
  if (N1.getOpcode() != ISD::AND || !isOneOrOneSplat(N1->getOperand(1)))
    return SDValue();
 
  EVT VT = N0.getValueType();
  SDValue N10 = N1.getOperand(0);
  if (N10.getValueType() != VT && N10.getOpcode() == ISD::TRUNCATE)
    N10 = N10.getOperand(0);
 
  if (N10.getValueType() != VT)
    return SDValue();
 
  if (DAG.ComputeNumSignBits(N10) != VT.getScalarSizeInBits())
    return SDValue();
 
  // add N0, (and (AssertSext X, i1), 1) --> sub N0, X
  // sub N0, (and (AssertSext X, i1), 1) --> add N0, X
  return DAG.getNode(IsAdd ? ISD::SUB : ISD::ADD, DL, VT, N0, N10);
}
 
/// Helper for doing combines based on N0 and N1 being added to each other.
SDValue DAGCombiner::visitADDLikeCommutative(SDValue N0, SDValue N1,
                                             SDNode *LocReference) {
  EVT VT = N0.getValueType();
  SDLoc DL(LocReference);
 
  // fold (add x, shl(0 - y, n)) -> sub(x, shl(y, n))
  SDValue Y, N;
  if (sd_match(N1, m_Shl(m_Neg(m_Value(Y)), m_Value(N))))
    return DAG.getNode(ISD::SUB, DL, VT, N0,
                       DAG.getNode(ISD::SHL, DL, VT, Y, N));
 
  if (SDValue V = foldAddSubMasked1(true, N0, N1, DAG, DL))
    return V;
 
  // Look for:
  //   add (add x, 1), y
  // And if the target does not like this form then turn into:
  //   sub y, (xor x, -1)
  if (!TLI.preferIncOfAddToSubOfNot(VT) && N0.getOpcode() == ISD::ADD &&
      N0.hasOneUse() && isOneOrOneSplat(N0.getOperand(1)) &&
      // Limit this to after legalization if the add has wrap flags
      (Level >= AfterLegalizeDAG || (!N0->getFlags().hasNoUnsignedWrap() &&
                                     !N0->getFlags().hasNoSignedWrap()))) {
    SDValue Not = DAG.getNOT(DL, N0.getOperand(0), VT);
    return DAG.getNode(ISD::SUB, DL, VT, N1, Not);
  }
 
  if (N0.getOpcode() == ISD::SUB && N0.hasOneUse()) {
    // Hoist one-use subtraction by non-opaque constant:
    //   (x - C) + y  ->  (x + y) - C
    // This is necessary because SUB(X,C) -> ADD(X,-C) doesn't work for vectors.
    if (isConstantOrConstantVector(N0.getOperand(1), /*NoOpaques=*/true)) {
      SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), N1);
      return DAG.getNode(ISD::SUB, DL, VT, Add, N0.getOperand(1));
    }
    // Hoist one-use subtraction from non-opaque constant:
    //   (C - x) + y  ->  (y - x) + C
    if (isConstantOrConstantVector(N0.getOperand(0), /*NoOpaques=*/true)) {
      SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N1, N0.getOperand(1));
      return DAG.getNode(ISD::ADD, DL, VT, Sub, N0.getOperand(0));
    }
  }
 
  // add (mul x, C), x -> mul x, C+1
  if (N0.getOpcode() == ISD::MUL && N0.getOperand(0) == N1 &&
      isConstantOrConstantVector(N0.getOperand(1), /*NoOpaques=*/true) &&
      N0.hasOneUse()) {
    SDValue NewC = DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(1),
                               DAG.getConstant(1, DL, VT));
    return DAG.getNode(ISD::MUL, DL, VT, N0.getOperand(0), NewC);
  }
 
  // If the target's bool is represented as 0/1, prefer to make this 'sub 0/1'
  // rather than 'add 0/-1' (the zext should get folded).
  // add (sext i1 Y), X --> sub X, (zext i1 Y)
  if (N0.getOpcode() == ISD::SIGN_EXTEND &&
      N0.getOperand(0).getScalarValueSizeInBits() == 1 &&
      TLI.getBooleanContents(VT) == TargetLowering::ZeroOrOneBooleanContent) {
    SDValue ZExt = DAG.getNode(ISD::ZERO_EXTEND, DL, VT, N0.getOperand(0));
    return DAG.getNode(ISD::SUB, DL, VT, N1, ZExt);
  }
 
  // add X, (sextinreg Y i1) -> sub X, (and Y 1)
  if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
    VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
    if (TN->getVT() == MVT::i1) {
      SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
                                 DAG.getConstant(1, DL, VT));
      return DAG.getNode(ISD::SUB, DL, VT, N0, ZExt);
    }
  }
 
  // (add X, (uaddo_carry Y, 0, Carry)) -> (uaddo_carry X, Y, Carry)
  if (N1.getOpcode() == ISD::UADDO_CARRY && isNullConstant(N1.getOperand(1)) &&
      N1.getResNo() == 0)
    return DAG.getNode(ISD::UADDO_CARRY, DL, N1->getVTList(),
                       N0, N1.getOperand(0), N1.getOperand(2));
 
  // (add X, Carry) -> (uaddo_carry X, 0, Carry)
  if (TLI.isOperationLegalOrCustom(ISD::UADDO_CARRY, VT))
    if (SDValue Carry = getAsCarry(TLI, N1))
      return DAG.getNode(ISD::UADDO_CARRY, DL,
                         DAG.getVTList(VT, Carry.getValueType()), N0,
                         DAG.getConstant(0, DL, VT), Carry);
 
  return SDValue();
}
 
SDValue DAGCombiner::visitADDC(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  EVT VT = N0.getValueType();
  SDLoc DL(N);
 
  // If the flag result is dead, turn this into an ADD.
  if (!N->hasAnyUseOfValue(1))
    return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
                     DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
 
  // canonicalize constant to RHS.
  ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
  if (N0C && !N1C)
    return DAG.getNode(ISD::ADDC, DL, N->getVTList(), N1, N0);
 
  // fold (addc x, 0) -> x + no carry out
  if (isNullConstant(N1))
    return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE,
                                        DL, MVT::Glue));
 
  // If it cannot overflow, transform into an add.
  if (DAG.computeOverflowForUnsignedAdd(N0, N1) == SelectionDAG::OFK_Never)
    return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
                     DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
 
  return SDValue();
}
 
/**
 * Flips a boolean if it is cheaper to compute. If the Force parameters is set,
 * then the flip also occurs if computing the inverse is the same cost.
 * This function returns an empty SDValue in case it cannot flip the boolean
 * without increasing the cost of the computation. If you want to flip a boolean
 * no matter what, use DAG.getLogicalNOT.
 */
static SDValue extractBooleanFlip(SDValue V, SelectionDAG &DAG,
                                  const TargetLowering &TLI,
                                  bool Force) {
  if (Force && isa<ConstantSDNode>(V))
    return DAG.getLogicalNOT(SDLoc(V), V, V.getValueType());
 
  if (V.getOpcode() != ISD::XOR)
    return SDValue();
 
  if (DAG.isBoolConstant(V.getOperand(1)) == true)
    return V.getOperand(0);
  if (Force && isConstOrConstSplat(V.getOperand(1), false))
    return DAG.getLogicalNOT(SDLoc(V), V, V.getValueType());
  return SDValue();
}
 
SDValue DAGCombiner::visitADDO(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  EVT VT = N0.getValueType();
  bool IsSigned = (ISD::SADDO == N->getOpcode());
 
  EVT CarryVT = N->getValueType(1);
  SDLoc DL(N);
 
  // If the flag result is dead, turn this into an ADD.
  if (!N->hasAnyUseOfValue(1))
    return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
                     DAG.getUNDEF(CarryVT));
 
  // canonicalize constant to RHS.
  if (DAG.isConstantIntBuildVectorOrConstantInt(N0) &&
      !DAG.isConstantIntBuildVectorOrConstantInt(N1))
    return DAG.getNode(N->getOpcode(), DL, N->getVTList(), N1, N0);
 
  // fold (addo x, 0) -> x + no carry out
  if (isNullOrNullSplat(N1))
    return CombineTo(N, N0, DAG.getConstant(0, DL, CarryVT));
 
  // If it cannot overflow, transform into an add.
  if (DAG.willNotOverflowAdd(IsSigned, N0, N1))
    return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
                     DAG.getConstant(0, DL, CarryVT));
 
  if (IsSigned) {
    // fold (saddo (xor a, -1), 1) -> (ssub 0, a).
    if (isBitwiseNot(N0) && isOneOrOneSplat(N1))
      return DAG.getNode(ISD::SSUBO, DL, N->getVTList(),
                         DAG.getConstant(0, DL, VT), N0.getOperand(0));
  } else {
    // fold (uaddo (xor a, -1), 1) -> (usub 0, a) and flip carry.
    if (isBitwiseNot(N0) && isOneOrOneSplat(N1)) {
      SDValue Sub = DAG.getNode(ISD::USUBO, DL, N->getVTList(),
                                DAG.getConstant(0, DL, VT), N0.getOperand(0));
      return CombineTo(
          N, Sub, DAG.getLogicalNOT(DL, Sub.getValue(1), Sub->getValueType(1)));
    }
 
    if (SDValue Combined = visitUADDOLike(N0, N1, N))
      return Combined;
 
    if (SDValue Combined = visitUADDOLike(N1, N0, N))
      return Combined;
  }
 
  return SDValue();
}
 
SDValue DAGCombiner::visitUADDOLike(SDValue N0, SDValue N1, SDNode *N) {
  EVT VT = N0.getValueType();
  if (VT.isVector())
    return SDValue();
 
  // (uaddo X, (uaddo_carry Y, 0, Carry)) -> (uaddo_carry X, Y, Carry)
  // If Y + 1 cannot overflow.
  if (N1.getOpcode() == ISD::UADDO_CARRY && isNullConstant(N1.getOperand(1))) {
    SDValue Y = N1.getOperand(0);
    SDValue One = DAG.getConstant(1, SDLoc(N), Y.getValueType());
    if (DAG.computeOverflowForUnsignedAdd(Y, One) == SelectionDAG::OFK_Never)
      return DAG.getNode(ISD::UADDO_CARRY, SDLoc(N), N->getVTList(), N0, Y,
                         N1.getOperand(2));
  }
 
  // (uaddo X, Carry) -> (uaddo_carry X, 0, Carry)
  if (TLI.isOperationLegalOrCustom(ISD::UADDO_CARRY, VT))
    if (SDValue Carry = getAsCarry(TLI, N1))
      return DAG.getNode(ISD::UADDO_CARRY, SDLoc(N), N->getVTList(), N0,
                         DAG.getConstant(0, SDLoc(N), VT), Carry);
 
  return SDValue();
}
 
SDValue DAGCombiner::visitADDE(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  SDValue CarryIn = N->getOperand(2);
 
  // canonicalize constant to RHS
  ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
  if (N0C && !N1C)
    return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(),
                       N1, N0, CarryIn);
 
  // fold (adde x, y, false) -> (addc x, y)
  if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
    return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N0, N1);
 
  return SDValue();
}
 
SDValue DAGCombiner::visitUADDO_CARRY(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  SDValue CarryIn = N->getOperand(2);
  SDLoc DL(N);
 
  // canonicalize constant to RHS
  ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
  if (N0C && !N1C)
    return DAG.getNode(ISD::UADDO_CARRY, DL, N->getVTList(), N1, N0, CarryIn);
 
  // fold (uaddo_carry x, y, false) -> (uaddo x, y)
  if (isNullConstant(CarryIn)) {
    if (!LegalOperations ||
        TLI.isOperationLegalOrCustom(ISD::UADDO, N->getValueType(0)))
      return DAG.getNode(ISD::UADDO, DL, N->getVTList(), N0, N1);
  }
 
  // fold (uaddo_carry 0, 0, X) -> (and (ext/trunc X), 1) and no carry.
  if (isNullConstant(N0) && isNullConstant(N1)) {
    EVT VT = N0.getValueType();
    EVT CarryVT = CarryIn.getValueType();
    SDValue CarryExt = DAG.getBoolExtOrTrunc(CarryIn, DL, VT, CarryVT);
    AddToWorklist(CarryExt.getNode());
    return CombineTo(N, DAG.getNode(ISD::AND, DL, VT, CarryExt,
                                    DAG.getConstant(1, DL, VT)),
                     DAG.getConstant(0, DL, CarryVT));
  }
 
  if (SDValue Combined = visitUADDO_CARRYLike(N0, N1, CarryIn, N))
    return Combined;
 
  if (SDValue Combined = visitUADDO_CARRYLike(N1, N0, CarryIn, N))
    return Combined;
 
  // We want to avoid useless duplication.
  // TODO: This is done automatically for binary operations. As UADDO_CARRY is
  // not a binary operation, this is not really possible to leverage this
  // existing mechanism for it. However, if more operations require the same
  // deduplication logic, then it may be worth generalize.
  SDValue Ops[] = {N1, N0, CarryIn};
  SDNode *CSENode =
      DAG.getNodeIfExists(ISD::UADDO_CARRY, N->getVTList(), Ops, N->getFlags());
  if (CSENode)
    return SDValue(CSENode, 0);
 
  return SDValue();
}
 
/**
 * If we are facing some sort of diamond carry propagation pattern try to
 * break it up to generate something like:
 *   (uaddo_carry X, 0, (uaddo_carry A, B, Z):Carry)
 *
 * The end result is usually an increase in operation required, but because the
 * carry is now linearized, other transforms can kick in and optimize the DAG.
 *
 * Patterns typically look something like
 *                (uaddo A, B)
 *                /          \
 *             Carry         Sum
 *               |             \
 *               | (uaddo_carry *, 0, Z)
 *               |       /
 *                \   Carry
 *                 |   /
 * (uaddo_carry X, *, *)
 *
 * But numerous variation exist. Our goal is to identify A, B, X and Z and
 * produce a combine with a single path for carry propagation.
 */
static SDValue combineUADDO_CARRYDiamond(DAGCombiner &Combiner,
                                         SelectionDAG &DAG, SDValue X,
                                         SDValue Carry0, SDValue Carry1,
                                         SDNode *N) {
  if (Carry1.getResNo() != 1 || Carry0.getResNo() != 1)
    return SDValue();
  if (Carry1.getOpcode() != ISD::UADDO)
    return SDValue();
 
  SDValue Z;
 
  /**
   * First look for a suitable Z. It will present itself in the form of
   * (uaddo_carry Y, 0, Z) or its equivalent (uaddo Y, 1) for Z=true
   */
  if (Carry0.getOpcode() == ISD::UADDO_CARRY &&
      isNullConstant(Carry0.getOperand(1))) {
    Z = Carry0.getOperand(2);
  } else if (Carry0.getOpcode() == ISD::UADDO &&
             isOneConstant(Carry0.getOperand(1))) {
    EVT VT = Carry0->getValueType(1);
    Z = DAG.getConstant(1, SDLoc(Carry0.getOperand(1)), VT);
  } else {
    // We couldn't find a suitable Z.
    return SDValue();
  }
 
 
  auto cancelDiamond = [&](SDValue A,SDValue B) {
    SDLoc DL(N);
    SDValue NewY =
        DAG.getNode(ISD::UADDO_CARRY, DL, Carry0->getVTList(), A, B, Z);
    Combiner.AddToWorklist(NewY.getNode());
    return DAG.getNode(ISD::UADDO_CARRY, DL, N->getVTList(), X,
                       DAG.getConstant(0, DL, X.getValueType()),
                       NewY.getValue(1));
  };
 
  /**
   *         (uaddo A, B)
   *              |
   *             Sum
   *              |
   * (uaddo_carry *, 0, Z)
   */
  if (Carry0.getOperand(0) == Carry1.getValue(0)) {
    return cancelDiamond(Carry1.getOperand(0), Carry1.getOperand(1));
  }
 
  /**
   * (uaddo_carry A, 0, Z)
   *         |
   *        Sum
   *         |
   *  (uaddo *, B)
   */
  if (Carry1.getOperand(0) == Carry0.getValue(0)) {
    return cancelDiamond(Carry0.getOperand(0), Carry1.getOperand(1));
  }
 
  if (Carry1.getOperand(1) == Carry0.getValue(0)) {
    return cancelDiamond(Carry1.getOperand(0), Carry0.getOperand(0));
  }
 
  return SDValue();
}
 
// If we are facing some sort of diamond carry/borrow in/out pattern try to
// match patterns like:
//
//          (uaddo A, B)            CarryIn
//            |  \                     |
//            |   \                    |
//    PartialSum   PartialCarryOutX   /
//            |        |             /
//            |    ____|____________/
//            |   /    |
//     (uaddo *, *)    \________
//       |  \                   \
//       |   \                   |
//       |    PartialCarryOutY   |
//       |        \              |
//       |         \            /
//   AddCarrySum    |    ______/
//                  |   /
//   CarryOut = (or *, *)
//
// And generate UADDO_CARRY (or USUBO_CARRY) with two result values:
//
//    {AddCarrySum, CarryOut} = (uaddo_carry A, B, CarryIn)
//
// Our goal is to identify A, B, and CarryIn and produce UADDO_CARRY/USUBO_CARRY
// with a single path for carry/borrow out propagation.
static SDValue combineCarryDiamond(SelectionDAG &DAG, const TargetLowering &TLI,
                                   SDValue N0, SDValue N1, SDNode *N) {
  SDValue Carry0 = getAsCarry(TLI, N0);
  if (!Carry0)
    return SDValue();
  SDValue Carry1 = getAsCarry(TLI, N1);
  if (!Carry1)
    return SDValue();
 
  unsigned Opcode = Carry0.getOpcode();
  if (Opcode != Carry1.getOpcode())
    return SDValue();
  if (Opcode != ISD::UADDO && Opcode != ISD::USUBO)
    return SDValue();
  // Guarantee identical type of CarryOut
  EVT CarryOutType = N->getValueType(0);
  if (CarryOutType != Carry0.getValue(1).getValueType() ||
      CarryOutType != Carry1.getValue(1).getValueType())
    return SDValue();
 
  // Canonicalize the add/sub of A and B (the top node in the above ASCII art)
  // as Carry0 and the add/sub of the carry in as Carry1 (the middle node).
  if (Carry1.getNode()->isOperandOf(Carry0.getNode()))
    std::swap(Carry0, Carry1);
 
  // Check if nodes are connected in expected way.
  if (Carry1.getOperand(0) != Carry0.getValue(0) &&
      Carry1.getOperand(1) != Carry0.getValue(0))
    return SDValue();
 
  // The carry in value must be on the righthand side for subtraction.
  unsigned CarryInOperandNum =
      Carry1.getOperand(0) == Carry0.getValue(0) ? 1 : 0;
  if (Opcode == ISD::USUBO && CarryInOperandNum != 1)
    return SDValue();
  SDValue CarryIn = Carry1.getOperand(CarryInOperandNum);
 
  unsigned NewOp = Opcode == ISD::UADDO ? ISD::UADDO_CARRY : ISD::USUBO_CARRY;
  if (!TLI.isOperationLegalOrCustom(NewOp, Carry0.getValue(0).getValueType()))
    return SDValue();
 
  // Verify that the carry/borrow in is plausibly a carry/borrow bit.
  CarryIn = getAsCarry(TLI, CarryIn, true);
  if (!CarryIn)
    return SDValue();
 
  SDLoc DL(N);
  CarryIn = DAG.getBoolExtOrTrunc(CarryIn, DL, Carry1->getValueType(1),
                                  Carry1->getValueType(0));
  SDValue Merged =
      DAG.getNode(NewOp, DL, Carry1->getVTList(), Carry0.getOperand(0),
                  Carry0.getOperand(1), CarryIn);
 
  // Please note that because we have proven that the result of the UADDO/USUBO
  // of A and B feeds into the UADDO/USUBO that does the carry/borrow in, we can
  // therefore prove that if the first UADDO/USUBO overflows, the second
  // UADDO/USUBO cannot. For example consider 8-bit numbers where 0xFF is the
  // maximum value.
  //
  //   0xFF + 0xFF == 0xFE with carry but 0xFE + 1 does not carry
  //   0x00 - 0xFF == 1 with a carry/borrow but 1 - 1 == 0 (no carry/borrow)
  //
  // This is important because it means that OR and XOR can be used to merge
  // carry flags; and that AND can return a constant zero.
  //
  // TODO: match other operations that can merge flags (ADD, etc)
  DAG.ReplaceAllUsesOfValueWith(Carry1.getValue(0), Merged.getValue(0));
  if (N->getOpcode() == ISD::AND)
    return DAG.getConstant(0, DL, CarryOutType);
  return Merged.getValue(1);
}
 
SDValue DAGCombiner::visitUADDO_CARRYLike(SDValue N0, SDValue N1,
                                          SDValue CarryIn, SDNode *N) {
  // fold (uaddo_carry (xor a, -1), b, c) -> (usubo_carry b, a, !c) and flip
  // carry.
  if (isBitwiseNot(N0))
    if (SDValue NotC = extractBooleanFlip(CarryIn, DAG, TLI, true)) {
      SDLoc DL(N);
      SDValue Sub = DAG.getNode(ISD::USUBO_CARRY, DL, N->getVTList(), N1,
                                N0.getOperand(0), NotC);
      return CombineTo(
          N, Sub, DAG.getLogicalNOT(DL, Sub.getValue(1), Sub->getValueType(1)));
    }
 
  // Iff the flag result is dead:
  // (uaddo_carry (add|uaddo X, Y), 0, Carry) -> (uaddo_carry X, Y, Carry)
  // Don't do this if the Carry comes from the uaddo. It won't remove the uaddo
  // or the dependency between the instructions.
  if ((N0.getOpcode() == ISD::ADD ||
       (N0.getOpcode() == ISD::UADDO && N0.getResNo() == 0 &&
        N0.getValue(1) != CarryIn)) &&
      isNullConstant(N1) && !N->hasAnyUseOfValue(1))
    return DAG.getNode(ISD::UADDO_CARRY, SDLoc(N), N->getVTList(),
                       N0.getOperand(0), N0.getOperand(1), CarryIn);
 
  /**
   * When one of the uaddo_carry argument is itself a carry, we may be facing
   * a diamond carry propagation. In which case we try to transform the DAG
   * to ensure linear carry propagation if that is possible.
   */
  if (auto Y = getAsCarry(TLI, N1)) {
    // Because both are carries, Y and Z can be swapped.
    if (auto R = combineUADDO_CARRYDiamond(*this, DAG, N0, Y, CarryIn, N))
      return R;
    if (auto R = combineUADDO_CARRYDiamond(*this, DAG, N0, CarryIn, Y, N))
      return R;
  }
 
  return SDValue();
}
 
SDValue DAGCombiner::visitSADDO_CARRYLike(SDValue N0, SDValue N1,
                                          SDValue CarryIn, SDNode *N) {
  // fold (saddo_carry (xor a, -1), b, c) -> (ssubo_carry b, a, !c)
  if (isBitwiseNot(N0)) {
    if (SDValue NotC = extractBooleanFlip(CarryIn, DAG, TLI, true))
      return DAG.getNode(ISD::SSUBO_CARRY, SDLoc(N), N->getVTList(), N1,
                         N0.getOperand(0), NotC);
  }
 
  return SDValue();
}
 
SDValue DAGCombiner::visitSADDO_CARRY(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  SDValue CarryIn = N->getOperand(2);
  SDLoc DL(N);
 
  // canonicalize constant to RHS
  ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
  ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
  if (N0C && !N1C)
    return DAG.getNode(ISD::SADDO_CARRY, DL, N->getVTList(), N1, N0, CarryIn);
 
  // fold (saddo_carry x, y, false) -> (saddo x, y)
  if (isNullConstant(CarryIn)) {
    if (!LegalOperations ||
        TLI.isOperationLegalOrCustom(ISD::SADDO, N->getValueType(0)))
      return DAG.getNode(ISD::SADDO, DL, N->getVTList(), N0, N1);
  }
 
  if (SDValue Combined = visitSADDO_CARRYLike(N0, N1, CarryIn, N))
    return Combined;
 
  if (SDValue Combined = visitSADDO_CARRYLike(N1, N0, CarryIn, N))
    return Combined;
 
  return SDValue();
}
 
// Attempt to create a USUBSAT(LHS, RHS) node with DstVT, performing a
// clamp/truncation if necessary.
static SDValue getTruncatedUSUBSAT(EVT DstVT, EVT SrcVT, SDValue LHS,
                                   SDValue RHS, SelectionDAG &DAG,
                                   const SDLoc &DL) {
  assert(DstVT.getScalarSizeInBits() <= SrcVT.getScalarSizeInBits() &&
         "Illegal truncation");
 
  if (DstVT == SrcVT)
    return DAG.getNode(ISD::USUBSAT, DL, DstVT, LHS, RHS);
 
  // If the LHS is zero-extended then we can perform the USUBSAT as DstVT by
  // clamping RHS.
  APInt UpperBits = APInt::getBitsSetFrom(SrcVT.getScalarSizeInBits(),
                                          DstVT.getScalarSizeInBits());
  if (!DAG.MaskedValueIsZero(LHS, UpperBits))
    return SDValue();
 
  SDValue SatLimit =
      DAG.getConstant(APInt::getLowBitsSet(SrcVT.getScalarSizeInBits(),
                                           DstVT.getScalarSizeInBits()),
                      DL, SrcVT);
  RHS = DAG.getNode(ISD::UMIN, DL, SrcVT, RHS, SatLimit);
  RHS = DAG.getNode(ISD::TRUNCATE, DL, DstVT, RHS);
  LHS = DAG.getNode(ISD::TRUNCATE, DL, DstVT, LHS);
  return DAG.getNode(ISD::USUBSAT, DL, DstVT, LHS, RHS);
}
 
// Try to find umax(a,b) - b or a - umin(a,b) patterns that may be converted to
// usubsat(a,b), optionally as a truncated type.
SDValue DAGCombiner::foldSubToUSubSat(EVT DstVT, SDNode *N, const SDLoc &DL) {
  if (N->getOpcode() != ISD::SUB ||
      !(!LegalOperations || hasOperation(ISD::USUBSAT, DstVT)))
    return SDValue();
 
  EVT SubVT = N->getValueType(0);
  SDValue Op0 = N->getOperand(0);
  SDValue Op1 = N->getOperand(1);
 
  // Try to find umax(a,b) - b or a - umin(a,b) patterns
  // they may be converted to usubsat(a,b).
  if (Op0.getOpcode() == ISD::UMAX && Op0.hasOneUse()) {
    SDValue MaxLHS = Op0.getOperand(0);
    SDValue MaxRHS = Op0.getOperand(1);
    if (MaxLHS == Op1)
      return getTruncatedUSUBSAT(DstVT, SubVT, MaxRHS, Op1, DAG, DL);
    if (MaxRHS == Op1)
      return getTruncatedUSUBSAT(DstVT, SubVT, MaxLHS, Op1, DAG, DL);
  }
 
  if (Op1.getOpcode() == ISD::UMIN && Op1.hasOneUse()) {
    SDValue MinLHS = Op1.getOperand(0);
    SDValue MinRHS = Op1.getOperand(1);
    if (MinLHS == Op0)
      return getTruncatedUSUBSAT(DstVT, SubVT, Op0, MinRHS, DAG, DL);
    if (MinRHS == Op0)
      return getTruncatedUSUBSAT(DstVT, SubVT, Op0, MinLHS, DAG, DL);
  }
 
  // sub(a,trunc(umin(zext(a),b))) -> usubsat(a,trunc(umin(b,SatLimit)))
  if (Op1.getOpcode() == ISD::TRUNCATE &&
      Op1.getOperand(0).getOpcode() == ISD::UMIN &&
      Op1.getOperand(0).hasOneUse()) {
    SDValue MinLHS = Op1.getOperand(0).getOperand(0);
    SDValue MinRHS = Op1.getOperand(0).getOperand(1);
    if (MinLHS.getOpcode() == ISD::ZERO_EXTEND && MinLHS.getOperand(0) == Op0)
      return getTruncatedUSUBSAT(DstVT, MinLHS.getValueType(), MinLHS, MinRHS,
                                 DAG, DL);
    if (MinRHS.getOpcode() == ISD::ZERO_EXTEND && MinRHS.getOperand(0) == Op0)
      return getTruncatedUSUBSAT(DstVT, MinLHS.getValueType(), MinRHS, MinLHS,
                                 DAG, DL);
  }
 
  return SDValue();
}
 
// Refinement of DAG/Type Legalisation (promotion) when CTLZ is used for
// counting leading ones. Broadly, it replaces the substraction with a left
// shift.
//
// * DAG Legalisation Pattern:
//
//     (sub (ctlz (zeroextend (not Src)))
//          BitWidthDiff)
//
//       if BitWidthDiff == BitWidth(Node) - BitWidth(Src)
//       -->
//
//     (ctlz_zero_undef (not (shl (anyextend Src)
//                                BitWidthDiff)))
//
// * Type Legalisation Pattern:
//
//     (sub (ctlz (and (xor Src XorMask)
//                     AndMask))
//          BitWidthDiff)
//
//       if AndMask has only trailing ones
//       and MaskBitWidth(AndMask) == BitWidth(Node) - BitWidthDiff
//       and XorMask has more trailing ones than AndMask
//       -->
//
//     (ctlz_zero_undef (not (shl Src BitWidthDiff)))
template <class MatchContextClass>
static SDValue foldSubCtlzNot(SDNode *N, SelectionDAG &DAG) {
  const SDLoc DL(N);
  SDValue N0 = N->getOperand(0);
  EVT VT = N0.getValueType();
  unsigned BitWidth = VT.getScalarSizeInBits();
 
  MatchContextClass Matcher(DAG, DAG.getTargetLoweringInfo(), N);
 
  APInt AndMask;
  APInt XorMask;
  APInt BitWidthDiff;
 
  SDValue CtlzOp;
  SDValue Src;
 
  if (!sd_context_match(
          N, Matcher, m_Sub(m_Ctlz(m_Value(CtlzOp)), m_ConstInt(BitWidthDiff))))
    return SDValue();
 
  if (sd_context_match(CtlzOp, Matcher, m_ZExt(m_Not(m_Value(Src))))) {
    // DAG Legalisation Pattern:
    // (sub (ctlz (zero_extend (not Op)) BitWidthDiff))
    if ((BitWidth - Src.getValueType().getScalarSizeInBits()) != BitWidthDiff)
      return SDValue();
 
    Src = DAG.getNode(ISD::ANY_EXTEND, DL, VT, Src);
  } else if (sd_context_match(CtlzOp, Matcher,
                              m_And(m_Xor(m_Value(Src), m_ConstInt(XorMask)),
                                    m_ConstInt(AndMask)))) {
    // Type Legalisation Pattern:
    // (sub (ctlz (and (xor Op XorMask) AndMask)) BitWidthDiff)
    unsigned AndMaskWidth = BitWidth - BitWidthDiff.getZExtValue();
    if (!(AndMask.isMask(AndMaskWidth) && XorMask.countr_one() >= AndMaskWidth))
      return SDValue();
  } else
    return SDValue();
 
  SDValue ShiftConst = DAG.getShiftAmountConstant(BitWidthDiff, VT, DL);
  SDValue LShift = Matcher.getNode(ISD::SHL, DL, VT, Src, ShiftConst);
  SDValue Not =
      Matcher.getNode(ISD::XOR, DL, VT, LShift, DAG.getAllOnesConstant(DL, VT));
 
  return Matcher.getNode(ISD::CTLZ_ZERO_UNDEF, DL, VT, Not);
}
 
// Since it may not be valid to emit a fold to zero for vector initializers
// check if we can before folding.
static SDValue tryFoldToZero(const SDLoc &DL, const TargetLowering &TLI, EVT VT,
                             SelectionDAG &DAG, bool LegalOperations) {
  if (!VT.isVector())
    return DAG.getConstant(0, DL, VT);
  if (!LegalOperations || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT))
    return DAG.getConstant(0, DL, VT);
  return SDValue();
}
 
SDValue DAGCombiner::visitSUB(SDNode *N) {
  SDValue N0 = N->getOperand(0);
  SDValue N1 = N->getOperand(1);
  EVT VT = N0.getValueType();
  unsigned BitWidth = VT.getScalarSizeInBits();
  SDLoc DL(N);
 
  auto PeekThroughFreeze = [](SDValue N) {
    if (N->getOpcode() == ISD::FREEZE && N.hasOneUse())
      return N->getOperand(0);
    return N;
  };
 
  if (SDValue V = foldSubCtlzNot<EmptyMatchContext>(N, DAG))
    return V;
 
  // fold (sub x, x) -> 0
  // FIXME: Refactor this and xor and other similar operations together.
  if (PeekThroughFreeze(N0) == PeekThroughFreeze(N1))
    return tryFoldToZero(DL, TLI, VT, DAG, LegalOperations);
 
  // fold (sub c1, c2) -> c3
  if (SDValue C = DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, {N0, N1}))
    return C;
 
  // fold vector ops
  if (VT.isVector()) {
    if (SDValue FoldedVOp = SimplifyVBinOp(N, DL))
      return FoldedVOp;
 
    // fold (sub x, 0) -> x, vector edition
    if (ISD::isConstantSplatVectorAllZeros(N1.getNode()))
      return N0;
  }
 
  if (SDValue NewSel = foldBinOpIntoSelect(N))
    return NewSel;
 
  // fold (sub x, c) -> (add x, -c)
  if (ConstantSDNode *N1C = getAsNonOpaqueConstant(N1))
    return DAG.getNode(ISD::ADD, DL, VT, N0,
                       DAG.getConstant(-N1C->getAPIntValue(), DL, VT));
 
  if (isNullOrNullSplat(N0)) {
    // Right-shifting everything out but the sign bit followed by negation is
    // the same as flipping arithmetic/logical shift type without the negation:
    // -(X >>u 31) -> (X >>s 31)
    // -(X >>s 31) -> (X >>u 31)
    if (N1->getOpcode() == ISD::SRA || N1->getOpcode() == ISD::SRL) {
      ConstantSDNode *ShiftAmt = isConstOrConstSplat(N1.getOperand(1));
      if (ShiftAmt && ShiftAmt->getAPIntValue() == (BitWidth - 1)) {
        auto NewSh = N1->getOpcode() == ISD::SRA ? ISD::SRL : ISD::SRA;
        if (!LegalOperations || TLI.isOperationLegal(NewSh, VT))
          return DAG.getNode(NewSh, DL, VT, N1.getOperand(0), N1.getOperand(1));
      }
    }
 
    // 0 - X --> 0 if the sub is NUW.
    if (N->getFlags().hasNoUnsignedWrap())
      return N0;
 
    if (DAG.MaskedValueIsZero(N1, ~APInt::getSignMask(BitWidth))) {
      // N1 is either 0 or the minimum signed value. If the sub is NSW, then
      // N1 must be 0 because negating the minimum signed value is undefined.
      if (N->getFlags().hasNoSignedWrap())
        return N0;
 
      // 0 - X --> X if X is 0 or the minimum signed value.
      return N1;
    }
 
    // Convert 0 - abs(x).
    if (N1.getOpcode() == ISD::ABS && N1.hasOneUse() &&
        !TLI.isOperationLegalOrCustom(ISD::ABS, VT))
      if (SDValue Result = TLI.expandABS(N1.getNode(), DAG, true))
        return Result;
 
    // Similar to the previous rule, but this time targeting an expanded abs.
    // (sub 0, (max X, (sub 0, X))) --> (min X, (sub 0, X))
    // as well as
    // (sub 0, (min X, (sub 0, X))) --> (max X, (sub 0, X))
    // Note that these two are applicable to both signed and unsigned min/max.
    SDValue X;
    SDValue S0;
    auto NegPat = m_AllOf(m_Neg(m_Deferred(X)), m_Value(S0));
    if (sd_match(N1, m_OneUse(m_AnyOf(m_SMax(m_Value(X), NegPat),
                                      m_UMax(m_Value(X), NegPat),
                                      m_SMin(m_Value(X), NegPat),
                                      m_UMin(m_Value(X), NegPat))))) {
      unsigned NewOpc = ISD::getInverseMinMaxOpcode(N1->getOpcode());
      if (hasOperation(NewOpc, VT))
        return DAG.getNode(NewOpc, DL, VT, X, S0);
    }
 
    // Fold neg(splat(neg(x)) -> splat(x)
    if (VT.isVector()) {
      SDValue N1S = DAG.getSplatValue(N1, true);
      if (N1S && N1S.getOpcode() == ISD::SUB &&
          isNullConstant(N1S.getOperand(0)))
        return DAG.getSplat(VT, DL, N1S.getOperand(1));
    }
  }
 
  // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1)
  if (isAllOnesOrAllOnesSplat(N0))
    return DAG.getNode(ISD::XOR, DL, VT, N1, N0);
 
  // fold (A - (0-B)) -> A+B
  if (N1.getOpcode() == ISD::SUB && isNullOrNullSplat(N1.getOperand(0)))
    return DAG.getNode(ISD::ADD, DL, VT, N0, N1.getOperand(1));
 
  // fold A-(A-B) -> B
  if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(0))
    return N1.getOperand(1);
 
  // fold (A+B)-A -> B
  if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
    return N0.getOperand(1);
 
  // fold (A+B)-B -> A
  if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
    return N0.getOperand(0);
 
  // fold (A+C1)-C2 -> A+(C1-C2)
  if (N0.getOpcode() == ISD::ADD) {
    SDValue N01 = N0.getOperand(1);
    if (SDValue NewC = DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, {N01, N1}))
      return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), NewC);
  }
 
  // fold C2-(A+C1) -> (C2-C1)-A
  if (N1.getOpcode() == ISD::ADD) {
    SDValue N11 = N1.getOperand(1);
    if (SDValue NewC = DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, {N0, N11}))
      return DAG.getNode(ISD::SUB, DL, VT, NewC, N1.getOperand(0));
  }
 
  // fold (A-C1)-C2 -> A-(C1+C2)
  if (N0.getOpcode() == ISD::SUB) {
    SDValue N01 = N0.getOperand(1);
    if (SDValue NewC = DAG.FoldConstantArithmetic(ISD::ADD, DL, VT, {N01, N1}))
      return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), NewC);
  }
 
  // fold (c1-A)-c2 -> (c1-c2)-A
  if (N0.getOpcode() == ISD::SUB) {
    SDValue N00 = N0.getOperand(0);
    if (SDValue NewC = DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, {N00, N1}))
      return DAG.getNode(ISD::SUB, DL, VT, NewC, N0.getOperand(1));
  }
 
  SDValue A, B, C;
 
  // fold ((A+(B+C))-B) -> A+C
  if (sd_match(N0, m_Add(m_Value(A), m_Add(m_Specific(N1), m_Value(C)))))
    return DAG.getNode(ISD::ADD, DL, VT, A, C);
 
  // fold ((A+(B-C))-B) -> A-C
  if (sd_match(N0, m_Add(m_Value(A), m_Sub(m_Specific(N1), m_Value(C)))))
    return DAG.getNode(ISD::SUB, DL, VT, A, C);
 
  // fold ((A-(B-C))-C) -> A-B
  if (sd_match(N0, m_Sub(m_Value(A), m_Sub(m_Value(B), m_Specific(N1)))))
    return DAG.getNode(ISD::SUB, DL, VT, A, B);
 
  // fold (A-(B-C)) -> A+(C-B)
  if (sd_match(N1, m_OneUse(m_Sub(m_Value(B), m_Value(C)))))
    return DAG.getNode(ISD::ADD, DL, VT, N0,
                       DAG.getNode(ISD::SUB, DL, VT, C, B));
 
  // A - (A & B)  ->  A & (~B)
  if (sd_match(N1, m_And(m_Specific(N0), m_Value(B))) &&
      (N1.hasOneUse() || isConstantOrConstantVector(B, /*NoOpaques=*/true)))
    return DAG.getNode(ISD::AND, DL, VT, N0, DAG.getNOT(DL, B, VT));
 
  // fold (A - (-B * C)) -> (A + (B * C))
  if (sd_match(N1, m_OneUse(m_Mul(m_Neg(m_Value(B)), m_Value(C)))))
    return DAG.getNode(ISD::ADD, DL, VT, N0,
                       DAG.getNode(ISD::MUL, DL, VT, B, C));
 
  // If either operand of a sub is undef, the result is undef
  if (N0.isUndef())
    return N0;
  if (N1.isUndef())
    return N1;
 
  if (SDValue V = foldAddSubBoolOfMaskedVal(N, DL, DAG))
    return V;
 
  if (SDValue V = foldAddSubOfSignBit(N, DL, DAG))
    return V;
 
  // Try to match AVGCEIL fixedwidth pattern
  if (SDValue V = foldSubToAvg(N, DL))
    return V;
 
  if (SDValue V = foldAddSubMasked1(false, N0, N1, DAG, DL))
    return V;
 
  if (SDValue V = foldSubToUSubSat(VT, N, DL))
    return V;
 
  // (A - B) - 1  ->  add (xor B, -1), A
  if (sd_match(N, m_Sub(m_OneUse(m_Sub(m_Value(A), m_Value(B))),