llvm/llvm/include/llvm/CodeGen/SelectionDAGNodes.h

//===- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file declares the SDNode class and derived classes, which are used to
// represent the nodes and operations present in a SelectionDAG.  These nodes
// and operations are machine code level operations, with some similarities to
// the GCC RTL representation.
//
// Clients should include the SelectionDAG.h file instead of this file directly.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H
#define LLVM_CODEGEN_SELECTIONDAGNODES_H

#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/CodeGen/ISDOpcodes.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/Register.h"
#include "llvm/CodeGen/ValueTypes.h"
#include "llvm/CodeGenTypes/MachineValueType.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/TypeSize.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <string>
#include <tuple>
#include <utility>

namespace llvm {

class APInt;
class Constant;
class GlobalValue;
class MachineBasicBlock;
class MachineConstantPoolValue;
class MCSymbol;
class raw_ostream;
class SDNode;
class SelectionDAG;
class Type;
class Value;

void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr,
                    bool force = false);

/// This represents a list of ValueType's that has been intern'd by
/// a SelectionDAG.  Instances of this simple value class are returned by
/// SelectionDAG::getVTList(...).
///
struct SDVTList { … };

namespace ISD {

  /// Node predicates

/// If N is a BUILD_VECTOR or SPLAT_VECTOR node whose elements are all the
/// same constant or undefined, return true and return the constant value in
/// \p SplatValue.
bool isConstantSplatVector(const SDNode *N, APInt &SplatValue);

/// Return true if the specified node is a BUILD_VECTOR or SPLAT_VECTOR where
/// all of the elements are ~0 or undef. If \p BuildVectorOnly is set to
/// true, it only checks BUILD_VECTOR.
bool isConstantSplatVectorAllOnes(const SDNode *N,
                                  bool BuildVectorOnly = false);

/// Return true if the specified node is a BUILD_VECTOR or SPLAT_VECTOR where
/// all of the elements are 0 or undef. If \p BuildVectorOnly is set to true, it
/// only checks BUILD_VECTOR.
bool isConstantSplatVectorAllZeros(const SDNode *N,
                                   bool BuildVectorOnly = false);

/// Return true if the specified node is a BUILD_VECTOR where all of the
/// elements are ~0 or undef.
bool isBuildVectorAllOnes(const SDNode *N);

/// Return true if the specified node is a BUILD_VECTOR where all of the
/// elements are 0 or undef.
bool isBuildVectorAllZeros(const SDNode *N);

/// Return true if the specified node is a BUILD_VECTOR node of all
/// ConstantSDNode or undef.
bool isBuildVectorOfConstantSDNodes(const SDNode *N);

/// Return true if the specified node is a BUILD_VECTOR node of all
/// ConstantFPSDNode or undef.
bool isBuildVectorOfConstantFPSDNodes(const SDNode *N);

/// Returns true if the specified node is a vector where all elements can
/// be truncated to the specified element size without a loss in meaning.
bool isVectorShrinkable(const SDNode *N, unsigned NewEltSize, bool Signed);

/// Return true if the node has at least one operand and all operands of the
/// specified node are ISD::UNDEF.
bool allOperandsUndef(const SDNode *N);

/// Return true if the specified node is FREEZE(UNDEF).
bool isFreezeUndef(const SDNode *N);

} // end namespace ISD

//===----------------------------------------------------------------------===//
/// Unlike LLVM values, Selection DAG nodes may return multiple
/// values as the result of a computation.  Many nodes return multiple values,
/// from loads (which define a token and a return value) to ADDC (which returns
/// a result and a carry value), to calls (which may return an arbitrary number
/// of values).
///
/// As such, each use of a SelectionDAG computation must indicate the node that
/// computes it as well as which return value to use from that node.  This pair
/// of information is represented with the SDValue value type.
///
class SDValue { … };

template<> struct DenseMapInfo<SDValue> { … };

/// Allow casting operators to work directly on
/// SDValues as if they were SDNode*'s.
template<> struct simplify_type<SDValue> { … };
template<> struct simplify_type<const SDValue> { … };

/// Represents a use of a SDNode. This class holds an SDValue,
/// which records the SDNode being used and the result number, a
/// pointer to the SDNode using the value, and Next and Prev pointers,
/// which link together all the uses of an SDNode.
///
class SDUse { … };

/// simplify_type specializations - Allow casting operators to work directly on
/// SDValues as if they were SDNode*'s.
template<> struct simplify_type<SDUse> { … };

/// These are IR-level optimization flags that may be propagated to SDNodes.
/// TODO: This data structure should be shared by the IR optimizer and the
/// the backend.
struct SDNodeFlags { … };

/// Represents one node in the SelectionDAG.
///
class SDNode : public FoldingSetNode, public ilist_node<SDNode> { … };

/// Wrapper class for IR location info (IR ordering and DebugLoc) to be passed
/// into SDNode creation functions.
/// When an SDNode is created from the DAGBuilder, the DebugLoc is extracted
/// from the original Instruction, and IROrder is the ordinal position of
/// the instruction.
/// When an SDNode is created after the DAG is being built, both DebugLoc and
/// the IROrder are propagated from the original SDNode.
/// So SDLoc class provides two constructors besides the default one, one to
/// be used by the DAGBuilder, the other to be used by others.
class SDLoc { … };

// Define inline functions from the SDValue class.

inline SDValue::SDValue(SDNode *node, unsigned resno)
    : … { … }

inline unsigned SDValue::getOpcode() const { … }

inline EVT SDValue::getValueType() const { … }

inline unsigned SDValue::getNumOperands() const { … }

inline const SDValue &SDValue::getOperand(unsigned i) const { … }

inline uint64_t SDValue::getConstantOperandVal(unsigned i) const { … }

inline const APInt &SDValue::getConstantOperandAPInt(unsigned i) const { … }

inline bool SDValue::isTargetOpcode() const { … }

inline bool SDValue::isTargetMemoryOpcode() const { … }

inline bool SDValue::isMachineOpcode() const { … }

inline unsigned SDValue::getMachineOpcode() const { … }

inline bool SDValue::isUndef() const { … }

inline bool SDValue::use_empty() const { … }

inline bool SDValue::hasOneUse() const { … }

inline const DebugLoc &SDValue::getDebugLoc() const { … }

inline void SDValue::dump() const { … }

inline void SDValue::dump(const SelectionDAG *G) const { … }

inline void SDValue::dumpr() const { … }

inline void SDValue::dumpr(const SelectionDAG *G) const { … }

// Define inline functions from the SDUse class.

inline void SDUse::set(const SDValue &V) { … }

inline void SDUse::setInitial(const SDValue &V) { … }

inline void SDUse::setNode(SDNode *N) { … }

/// This class is used to form a handle around another node that
/// is persistent and is updated across invocations of replaceAllUsesWith on its
/// operand.  This node should be directly created by end-users and not added to
/// the AllNodes list.
class HandleSDNode : public SDNode { … };

class AddrSpaceCastSDNode : public SDNode { … };

/// This is an abstract virtual class for memory operations.
class MemSDNode : public SDNode { … };

/// This is an SDNode representing atomic operations.
class AtomicSDNode : public MemSDNode { … };

/// This SDNode is used for target intrinsics that touch
/// memory and need an associated MachineMemOperand. Its opcode may be
/// INTRINSIC_VOID, INTRINSIC_W_CHAIN, PREFETCH, or a target-specific opcode
/// with a value not less than FIRST_TARGET_MEMORY_OPCODE.
class MemIntrinsicSDNode : public MemSDNode { … };

/// This SDNode is used to implement the code generator
/// support for the llvm IR shufflevector instruction.  It combines elements
/// from two input vectors into a new input vector, with the selection and
/// ordering of elements determined by an array of integers, referred to as
/// the shuffle mask.  For input vectors of width N, mask indices of 0..N-1
/// refer to elements from the LHS input, and indices from N to 2N-1 the RHS.
/// An index of -1 is treated as undef, such that the code generator may put
/// any value in the corresponding element of the result.
class ShuffleVectorSDNode : public SDNode { … };

class ConstantSDNode : public SDNode { … };

uint64_t SDNode::getConstantOperandVal(unsigned Num) const { … }

uint64_t SDNode::getAsZExtVal() const { … }

const APInt &SDNode::getConstantOperandAPInt(unsigned Num) const { … }

const APInt &SDNode::getAsAPIntVal() const { … }

class ConstantFPSDNode : public SDNode { … };

/// Returns true if \p V is a constant integer zero.
bool isNullConstant(SDValue V);

/// Returns true if \p V is a constant integer zero or an UNDEF node.
bool isNullConstantOrUndef(SDValue V);

/// Returns true if \p V is an FP constant with a value of positive zero.
bool isNullFPConstant(SDValue V);

/// Returns true if \p V is an integer constant with all bits set.
bool isAllOnesConstant(SDValue V);

/// Returns true if \p V is a constant integer one.
bool isOneConstant(SDValue V);

/// Returns true if \p V is a constant min signed integer value.
bool isMinSignedConstant(SDValue V);

/// Returns true if \p V is a neutral element of Opc with Flags.
/// When OperandNo is 0, it checks that V is a left identity. Otherwise, it
/// checks that V is a right identity.
bool isNeutralConstant(unsigned Opc, SDNodeFlags Flags, SDValue V,
                       unsigned OperandNo);

/// Return the non-bitcasted source operand of \p V if it exists.
/// If \p V is not a bitcasted value, it is returned as-is.
SDValue peekThroughBitcasts(SDValue V);

/// Return the non-bitcasted and one-use source operand of \p V if it exists.
/// If \p V is not a bitcasted one-use value, it is returned as-is.
SDValue peekThroughOneUseBitcasts(SDValue V);

/// Return the non-extracted vector source operand of \p V if it exists.
/// If \p V is not an extracted subvector, it is returned as-is.
SDValue peekThroughExtractSubvectors(SDValue V);

/// Return the non-truncated source operand of \p V if it exists.
/// If \p V is not a truncation, it is returned as-is.
SDValue peekThroughTruncates(SDValue V);

/// Returns true if \p V is a bitwise not operation. Assumes that an all ones
/// constant is canonicalized to be operand 1.
bool isBitwiseNot(SDValue V, bool AllowUndefs = false);

/// If \p V is a bitwise not, returns the inverted operand. Otherwise returns
/// an empty SDValue. Only bits set in \p Mask are required to be inverted,
/// other bits may be arbitrary.
SDValue getBitwiseNotOperand(SDValue V, SDValue Mask, bool AllowUndefs);

/// Returns the SDNode if it is a constant splat BuildVector or constant int.
ConstantSDNode *isConstOrConstSplat(SDValue N, bool AllowUndefs = false,
                                    bool AllowTruncation = false);

/// Returns the SDNode if it is a demanded constant splat BuildVector or
/// constant int.
ConstantSDNode *isConstOrConstSplat(SDValue N, const APInt &DemandedElts,
                                    bool AllowUndefs = false,
                                    bool AllowTruncation = false);

/// Returns the SDNode if it is a constant splat BuildVector or constant float.
ConstantFPSDNode *isConstOrConstSplatFP(SDValue N, bool AllowUndefs = false);

/// Returns the SDNode if it is a demanded constant splat BuildVector or
/// constant float.
ConstantFPSDNode *isConstOrConstSplatFP(SDValue N, const APInt &DemandedElts,
                                        bool AllowUndefs = false);

/// Return true if the value is a constant 0 integer or a splatted vector of
/// a constant 0 integer (with no undefs by default).
/// Build vector implicit truncation is not an issue for null values.
bool isNullOrNullSplat(SDValue V, bool AllowUndefs = false);

/// Return true if the value is a constant 1 integer or a splatted vector of a
/// constant 1 integer (with no undefs).
/// Build vector implicit truncation is allowed, but the truncated bits need to
/// be zero.
bool isOneOrOneSplat(SDValue V, bool AllowUndefs = false);

/// Return true if the value is a constant -1 integer or a splatted vector of a
/// constant -1 integer (with no undefs).
/// Does not permit build vector implicit truncation.
bool isAllOnesOrAllOnesSplat(SDValue V, bool AllowUndefs = false);

/// Return true if \p V is either a integer or FP constant.
inline bool isIntOrFPConstant(SDValue V) { … }

class GlobalAddressSDNode : public SDNode { … };

class FrameIndexSDNode : public SDNode { … };

/// This SDNode is used for LIFETIME_START/LIFETIME_END values, which indicate
/// the offet and size that are started/ended in the underlying FrameIndex.
class LifetimeSDNode : public SDNode { … };

/// This SDNode is used for PSEUDO_PROBE values, which are the function guid and
/// the index of the basic block being probed. A pseudo probe serves as a place
/// holder and will be removed at the end of compilation. It does not have any
/// operand because we do not want the instruction selection to deal with any.
class PseudoProbeSDNode : public SDNode { … };

class JumpTableSDNode : public SDNode { … };

class ConstantPoolSDNode : public SDNode { … };

/// Completely target-dependent object reference.
class TargetIndexSDNode : public SDNode { … };

class BasicBlockSDNode : public SDNode { … };

/// A "pseudo-class" with methods for operating on BUILD_VECTORs.
class BuildVectorSDNode : public SDNode { … };

/// An SDNode that holds an arbitrary LLVM IR Value. This is
/// used when the SelectionDAG needs to make a simple reference to something
/// in the LLVM IR representation.
///
class SrcValueSDNode : public SDNode { … };

class MDNodeSDNode : public SDNode { … };

class RegisterSDNode : public SDNode { … };

class RegisterMaskSDNode : public SDNode { … };

class BlockAddressSDNode : public SDNode { … };

class LabelSDNode : public SDNode { … };

class ExternalSymbolSDNode : public SDNode { … };

class MCSymbolSDNode : public SDNode { … };

class CondCodeSDNode : public SDNode { … };

/// This class is used to represent EVT's, which are used
/// to parameterize some operations.
class VTSDNode : public SDNode { … };

/// Base class for LoadSDNode and StoreSDNode
class LSBaseSDNode : public MemSDNode { … };

/// This class is used to represent ISD::LOAD nodes.
class LoadSDNode : public LSBaseSDNode { … };

/// This class is used to represent ISD::STORE nodes.
class StoreSDNode : public LSBaseSDNode { … };

/// This base class is used to represent VP_LOAD, VP_STORE,
/// EXPERIMENTAL_VP_STRIDED_LOAD and EXPERIMENTAL_VP_STRIDED_STORE nodes
class VPBaseLoadStoreSDNode : public MemSDNode { … };

/// This class is used to represent a VP_LOAD node
class VPLoadSDNode : public VPBaseLoadStoreSDNode { … };

/// This class is used to represent an EXPERIMENTAL_VP_STRIDED_LOAD node.
class VPStridedLoadSDNode : public VPBaseLoadStoreSDNode { … };

/// This class is used to represent a VP_STORE node
class VPStoreSDNode : public VPBaseLoadStoreSDNode { … };

/// This class is used to represent an EXPERIMENTAL_VP_STRIDED_STORE node.
class VPStridedStoreSDNode : public VPBaseLoadStoreSDNode { … };

/// This base class is used to represent MLOAD and MSTORE nodes
class MaskedLoadStoreSDNode : public MemSDNode { … };

/// This class is used to represent an MLOAD node
class MaskedLoadSDNode : public MaskedLoadStoreSDNode { … };

/// This class is used to represent an MSTORE node
class MaskedStoreSDNode : public MaskedLoadStoreSDNode { … };

/// This is a base class used to represent
/// VP_GATHER and VP_SCATTER nodes
///
class VPGatherScatterSDNode : public MemSDNode { … };

/// This class is used to represent an VP_GATHER node
///
class VPGatherSDNode : public VPGatherScatterSDNode { … };

/// This class is used to represent an VP_SCATTER node
///
class VPScatterSDNode : public VPGatherScatterSDNode { … };

/// This is a base class used to represent
/// MGATHER and MSCATTER nodes
///
class MaskedGatherScatterSDNode : public MemSDNode { … };

/// This class is used to represent an MGATHER node
///
class MaskedGatherSDNode : public MaskedGatherScatterSDNode { … };

/// This class is used to represent an MSCATTER node
///
class MaskedScatterSDNode : public MaskedGatherScatterSDNode { … };

class MaskedHistogramSDNode : public MemSDNode { … };

class FPStateAccessSDNode : public MemSDNode { … };

/// An SDNode that represents everything that will be needed
/// to construct a MachineInstr. These nodes are created during the
/// instruction selection proper phase.
///
/// Note that the only supported way to set the `memoperands` is by calling the
/// `SelectionDAG::setNodeMemRefs` function as the memory management happens
/// inside the DAG rather than in the node.
class MachineSDNode : public SDNode { … };

/// An SDNode that records if a register contains a value that is guaranteed to
/// be aligned accordingly.
class AssertAlignSDNode : public SDNode { … };

class SDNodeIterator { … };

template <> struct GraphTraits<SDNode*> { … };

/// A representation of the largest SDNode, for use in sizeof().
///
/// This needs to be a union because the largest node differs on 32 bit systems
/// with 4 and 8 byte pointer alignment, respectively.
LargestSDNode;

/// The SDNode class with the greatest alignment requirement.
MostAlignedSDNode;

namespace ISD {

  /// Returns true if the specified node is a non-extending and unindexed load.
  inline bool isNormalLoad(const SDNode *N) { … }

  /// Returns true if the specified node is a non-extending load.
  inline bool isNON_EXTLoad(const SDNode *N) { … }

  /// Returns true if the specified node is a EXTLOAD.
  inline bool isEXTLoad(const SDNode *N) { … }

  /// Returns true if the specified node is a SEXTLOAD.
  inline bool isSEXTLoad(const SDNode *N) { … }

  /// Returns true if the specified node is a ZEXTLOAD.
  inline bool isZEXTLoad(const SDNode *N) { … }

  /// Returns true if the specified node is an unindexed load.
  inline bool isUNINDEXEDLoad(const SDNode *N) { … }

  /// Returns true if the specified node is a non-truncating
  /// and unindexed store.
  inline bool isNormalStore(const SDNode *N) { … }

  /// Returns true if the specified node is an unindexed store.
  inline bool isUNINDEXEDStore(const SDNode *N) { … }

  /// Attempt to match a unary predicate against a scalar/splat constant or
  /// every element of a constant BUILD_VECTOR.
  /// If AllowUndef is true, then UNDEF elements will pass nullptr to Match.
  template <typename ConstNodeType>
  bool matchUnaryPredicateImpl(SDValue Op,
                               std::function<bool(ConstNodeType *)> Match,
                               bool AllowUndefs = false);

  /// Hook for matching ConstantSDNode predicate
  inline bool matchUnaryPredicate(SDValue Op,
                                  std::function<bool(ConstantSDNode *)> Match,
                                  bool AllowUndefs = false) { … }

  /// Hook for matching ConstantFPSDNode predicate
  inline bool
  matchUnaryFpPredicate(SDValue Op,
                        std::function<bool(ConstantFPSDNode *)> Match,
                        bool AllowUndefs = false) { … }

  /// Attempt to match a binary predicate against a pair of scalar/splat
  /// constants or every element of a pair of constant BUILD_VECTORs.
  /// If AllowUndef is true, then UNDEF elements will pass nullptr to Match.
  /// If AllowTypeMismatch is true then RetType + ArgTypes don't need to match.
  bool matchBinaryPredicate(
      SDValue LHS, SDValue RHS,
      std::function<bool(ConstantSDNode *, ConstantSDNode *)> Match,
      bool AllowUndefs = false, bool AllowTypeMismatch = false);

  /// Returns true if the specified value is the overflow result from one
  /// of the overflow intrinsic nodes.
  inline bool isOverflowIntrOpRes(SDValue Op) { … }

} // end namespace ISD

} // end namespace llvm

#endif // LLVM_CODEGEN_SELECTIONDAGNODES_H