llvm/llvm/utils/TableGen/Common/CodeGenDAGPatterns.cpp

//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the CodeGenDAGPatterns class, which is used to read and
// represent the patterns present in a .td file for instructions.
//
//===----------------------------------------------------------------------===//

#include "CodeGenDAGPatterns.h"
#include "CodeGenInstruction.h"
#include "CodeGenRegisters.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/TypeSize.h"
#include "llvm/TableGen/Error.h"
#include "llvm/TableGen/Record.h"
#include <algorithm>
#include <cstdio>
#include <iterator>
#include <set>
usingnamespacellvm;

#define DEBUG_TYPE …

static inline bool isIntegerOrPtr(MVT VT) { … }
static inline bool isFloatingPoint(MVT VT) { … }
static inline bool isVector(MVT VT) { … }
static inline bool isScalar(MVT VT) { … }

template <typename Predicate>
static bool berase_if(MachineValueTypeSet &S, Predicate P) { … }

void MachineValueTypeSet::writeToStream(raw_ostream &OS) const { … }

// --- TypeSetByHwMode

// This is a parameterized type-set class. For each mode there is a list
// of types that are currently possible for a given tree node. Type
// inference will apply to each mode separately.

TypeSetByHwMode::TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList) { … }

bool TypeSetByHwMode::isValueTypeByHwMode(bool AllowEmpty) const { … }

ValueTypeByHwMode TypeSetByHwMode::getValueTypeByHwMode() const { … }

bool TypeSetByHwMode::isPossible() const { … }

bool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) { … }

// Constrain the type set to be the intersection with VTS.
bool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) { … }

template <typename Predicate> bool TypeSetByHwMode::constrain(Predicate P) { … }

template <typename Predicate>
bool TypeSetByHwMode::assign_if(const TypeSetByHwMode &VTS, Predicate P) { … }

void TypeSetByHwMode::writeToStream(raw_ostream &OS) const { … }

bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const { … }

namespace llvm {
raw_ostream &operator<<(raw_ostream &OS, const MachineValueTypeSet &T) { … }
raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T) { … }
} // namespace llvm

LLVM_DUMP_METHOD
void TypeSetByHwMode::dump() const { … }

bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) { … }

bool TypeSetByHwMode::validate() const { … }

// --- TypeInfer

bool TypeInfer::MergeInTypeInfo(TypeSetByHwMode &Out,
                                const TypeSetByHwMode &In) const { … }

bool TypeInfer::forceArbitrary(TypeSetByHwMode &Out) { … }

bool TypeInfer::EnforceInteger(TypeSetByHwMode &Out) { … }

bool TypeInfer::EnforceFloatingPoint(TypeSetByHwMode &Out) { … }

bool TypeInfer::EnforceScalar(TypeSetByHwMode &Out) { … }

bool TypeInfer::EnforceVector(TypeSetByHwMode &Out) { … }

bool TypeInfer::EnforceAny(TypeSetByHwMode &Out) { … }

template <typename Iter, typename Pred, typename Less>
static Iter min_if(Iter B, Iter E, Pred P, Less L) { … }

template <typename Iter, typename Pred, typename Less>
static Iter max_if(Iter B, Iter E, Pred P, Less L) { … }

/// Make sure that for each type in Small, there exists a larger type in Big.
bool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small, TypeSetByHwMode &Big,
                                   bool SmallIsVT) { … }

/// 1. Ensure that for each type T in Vec, T is a vector type, and that
///    for each type U in Elem, U is a scalar type.
/// 2. Ensure that for each (scalar) type U in Elem, there exists a (vector)
///    type T in Vec, such that U is the element type of T.
bool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
                                       TypeSetByHwMode &Elem) { … }

bool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
                                       const ValueTypeByHwMode &VVT) { … }

/// Ensure that for each type T in Sub, T is a vector type, and there
/// exists a type U in Vec such that U is a vector type with the same
/// element type as T and at least as many elements as T.
bool TypeInfer::EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,
                                             TypeSetByHwMode &Sub) { … }

/// 1. Ensure that V has a scalar type iff W has a scalar type.
/// 2. Ensure that for each vector type T in V, there exists a vector
///    type U in W, such that T and U have the same number of elements.
/// 3. Ensure that for each vector type U in W, there exists a vector
///    type T in V, such that T and U have the same number of elements
///    (reverse of 2).
bool TypeInfer::EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W) { … }

namespace {
struct TypeSizeComparator { … };
} // end anonymous namespace

/// 1. Ensure that for each type T in A, there exists a type U in B,
///    such that T and U have equal size in bits.
/// 2. Ensure that for each type U in B, there exists a type T in A
///    such that T and U have equal size in bits (reverse of 1).
bool TypeInfer::EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B) { … }

void TypeInfer::expandOverloads(TypeSetByHwMode &VTS) const { … }

void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
                                const TypeSetByHwMode::SetType &Legal) const { … }

const TypeSetByHwMode &TypeInfer::getLegalTypes() const { … }

TypeInfer::ValidateOnExit::~ValidateOnExit() { … }

//===----------------------------------------------------------------------===//
// ScopedName Implementation
//===----------------------------------------------------------------------===//

bool ScopedName::operator==(const ScopedName &o) const { … }

bool ScopedName::operator!=(const ScopedName &o) const { … }

//===----------------------------------------------------------------------===//
// TreePredicateFn Implementation
//===----------------------------------------------------------------------===//

/// TreePredicateFn constructor.  Here 'N' is a subclass of PatFrag.
TreePredicateFn::TreePredicateFn(TreePattern *N) : … { … }

bool TreePredicateFn::hasPredCode() const { … }

std::string TreePredicateFn::getPredCode() const { … }

bool TreePredicateFn::hasImmCode() const { … }

std::string TreePredicateFn::getImmCode() const { … }

bool TreePredicateFn::immCodeUsesAPInt() const { … }

bool TreePredicateFn::immCodeUsesAPFloat() const { … }

bool TreePredicateFn::isPredefinedPredicateEqualTo(StringRef Field,
                                                   bool Value) const { … }
bool TreePredicateFn::usesOperands() const { … }
bool TreePredicateFn::hasNoUse() const { … }
bool TreePredicateFn::hasOneUse() const { … }
bool TreePredicateFn::isLoad() const { … }
bool TreePredicateFn::isStore() const { … }
bool TreePredicateFn::isAtomic() const { … }
bool TreePredicateFn::isUnindexed() const { … }
bool TreePredicateFn::isNonExtLoad() const { … }
bool TreePredicateFn::isAnyExtLoad() const { … }
bool TreePredicateFn::isSignExtLoad() const { … }
bool TreePredicateFn::isZeroExtLoad() const { … }
bool TreePredicateFn::isNonTruncStore() const { … }
bool TreePredicateFn::isTruncStore() const { … }
bool TreePredicateFn::isAtomicOrderingMonotonic() const { … }
bool TreePredicateFn::isAtomicOrderingAcquire() const { … }
bool TreePredicateFn::isAtomicOrderingRelease() const { … }
bool TreePredicateFn::isAtomicOrderingAcquireRelease() const { … }
bool TreePredicateFn::isAtomicOrderingSequentiallyConsistent() const { … }
bool TreePredicateFn::isAtomicOrderingAcquireOrStronger() const { … }
bool TreePredicateFn::isAtomicOrderingWeakerThanAcquire() const { … }
bool TreePredicateFn::isAtomicOrderingReleaseOrStronger() const { … }
bool TreePredicateFn::isAtomicOrderingWeakerThanRelease() const { … }
const Record *TreePredicateFn::getMemoryVT() const { … }

const ListInit *TreePredicateFn::getAddressSpaces() const { … }

int64_t TreePredicateFn::getMinAlignment() const { … }

const Record *TreePredicateFn::getScalarMemoryVT() const { … }
bool TreePredicateFn::hasGISelPredicateCode() const { … }
std::string TreePredicateFn::getGISelPredicateCode() const { … }

StringRef TreePredicateFn::getImmType() const { … }

StringRef TreePredicateFn::getImmTypeIdentifier() const { … }

/// isAlwaysTrue - Return true if this is a noop predicate.
bool TreePredicateFn::isAlwaysTrue() const { … }

/// Return the name to use in the generated code to reference this, this is
/// "Predicate_foo" if from a pattern fragment "foo".
std::string TreePredicateFn::getFnName() const { … }

/// getCodeToRunOnSDNode - Return the code for the function body that
/// evaluates this predicate.  The argument is expected to be in "Node",
/// not N.  This handles casting and conversion to a concrete node type as
/// appropriate.
std::string TreePredicateFn::getCodeToRunOnSDNode() const { … }

//===----------------------------------------------------------------------===//
// PatternToMatch implementation
//

static bool isImmAllOnesAllZerosMatch(const TreePatternNode &P) { … }

/// getPatternSize - Return the 'size' of this pattern.  We want to match large
/// patterns before small ones.  This is used to determine the size of a
/// pattern.
static unsigned getPatternSize(const TreePatternNode &P,
                               const CodeGenDAGPatterns &CGP) { … }

/// Compute the complexity metric for the input pattern.  This roughly
/// corresponds to the number of nodes that are covered.
int PatternToMatch::getPatternComplexity(const CodeGenDAGPatterns &CGP) const { … }

void PatternToMatch::getPredicateRecords(
    SmallVectorImpl<const Record *> &PredicateRecs) const { … }

/// getPredicateCheck - Return a single string containing all of this
/// pattern's predicates concatenated with "&&" operators.
///
std::string PatternToMatch::getPredicateCheck() const { … }

//===----------------------------------------------------------------------===//
// SDTypeConstraint implementation
//

SDTypeConstraint::SDTypeConstraint(const Record *R, const CodeGenHwModes &CGH) { … }

/// getOperandNum - Return the node corresponding to operand #OpNo in tree
/// N, and the result number in ResNo.
static TreePatternNode &getOperandNum(unsigned OpNo, TreePatternNode &N,
                                      const SDNodeInfo &NodeInfo,
                                      unsigned &ResNo) { … }

/// ApplyTypeConstraint - Given a node in a pattern, apply this type
/// constraint to the nodes operands.  This returns true if it makes a
/// change, false otherwise.  If a type contradiction is found, flag an error.
bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode &N,
                                           const SDNodeInfo &NodeInfo,
                                           TreePattern &TP) const { … }

// Update the node type to match an instruction operand or result as specified
// in the ins or outs lists on the instruction definition. Return true if the
// type was actually changed.
bool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo,
                                             const Record *Operand,
                                             TreePattern &TP) { … }

bool TreePatternNode::ContainsUnresolvedType(TreePattern &TP) const { … }

bool TreePatternNode::hasProperTypeByHwMode() const { … }

bool TreePatternNode::hasPossibleType() const { … }

bool TreePatternNode::setDefaultMode(unsigned Mode) { … }

//===----------------------------------------------------------------------===//
// SDNodeInfo implementation
//
SDNodeInfo::SDNodeInfo(const Record *R, const CodeGenHwModes &CGH) : … { … }

/// getKnownType - If the type constraints on this node imply a fixed type
/// (e.g. all stores return void, etc), then return it as an
/// MVT::SimpleValueType.  Otherwise, return EEVT::Other.
MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const { … }

//===----------------------------------------------------------------------===//
// TreePatternNode implementation
//

static unsigned GetNumNodeResults(const Record *Operator,
                                  CodeGenDAGPatterns &CDP) { … }

void TreePatternNode::print(raw_ostream &OS) const { … }
void TreePatternNode::dump() const { … }

/// isIsomorphicTo - Return true if this node is recursively
/// isomorphic to the specified node.  For this comparison, the node's
/// entire state is considered. The assigned name is ignored, since
/// nodes with differing names are considered isomorphic. However, if
/// the assigned name is present in the dependent variable set, then
/// the assigned name is considered significant and the node is
/// isomorphic if the names match.
bool TreePatternNode::isIsomorphicTo(const TreePatternNode &N,
                                     const MultipleUseVarSet &DepVars) const { … }

/// clone - Make a copy of this tree and all of its children.
///
TreePatternNodePtr TreePatternNode::clone() const { … }

/// RemoveAllTypes - Recursively strip all the types of this tree.
void TreePatternNode::RemoveAllTypes() { … }

/// SubstituteFormalArguments - Replace the formal arguments in this tree
/// with actual values specified by ArgMap.
void TreePatternNode::SubstituteFormalArguments(
    std::map<std::string, TreePatternNodePtr> &ArgMap) { … }

/// InlinePatternFragments - If this pattern refers to any pattern
/// fragments, return the set of inlined versions (this can be more than
/// one if a PatFrags record has multiple alternatives).
void TreePatternNode::InlinePatternFragments(
    TreePattern &TP, std::vector<TreePatternNodePtr> &OutAlternatives) { … }

/// getImplicitType - Check to see if the specified record has an implicit
/// type which should be applied to it.  This will infer the type of register
/// references from the register file information, for example.
///
/// When Unnamed is set, return the type of a DAG operand with no name, such as
/// the F8RC register class argument in:
///
///   (COPY_TO_REGCLASS GPR:$src, F8RC)
///
/// When Unnamed is false, return the type of a named DAG operand such as the
/// GPR:$src operand above.
///
static TypeSetByHwMode getImplicitType(const Record *R, unsigned ResNo,
                                       bool NotRegisters, bool Unnamed,
                                       TreePattern &TP) { … }

/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
/// CodeGenIntrinsic information for it, otherwise return a null pointer.
const CodeGenIntrinsic *
TreePatternNode::getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { … }

/// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
/// return the ComplexPattern information, otherwise return null.
const ComplexPattern *
TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { … }

unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const { … }

/// NodeHasProperty - Return true if this node has the specified property.
bool TreePatternNode::NodeHasProperty(SDNP Property,
                                      const CodeGenDAGPatterns &CGP) const { … }

/// TreeHasProperty - Return true if any node in this tree has the specified
/// property.
bool TreePatternNode::TreeHasProperty(SDNP Property,
                                      const CodeGenDAGPatterns &CGP) const { … }

/// isCommutativeIntrinsic - Return true if the node corresponds to a
/// commutative intrinsic.
bool TreePatternNode::isCommutativeIntrinsic(
    const CodeGenDAGPatterns &CDP) const { … }

static bool isOperandClass(const TreePatternNode &N, StringRef Class) { … }

static void emitTooManyOperandsError(TreePattern &TP, StringRef InstName,
                                     unsigned Expected, unsigned Actual) { … }

static void emitTooFewOperandsError(TreePattern &TP, StringRef InstName,
                                    unsigned Actual) { … }

/// ApplyTypeConstraints - Apply all of the type constraints relevant to
/// this node and its children in the tree.  This returns true if it makes a
/// change, false otherwise.  If a type contradiction is found, flag an error.
bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { … }

/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the
/// RHS of a commutative operation, not the on LHS.
static bool OnlyOnRHSOfCommutative(TreePatternNode &N) { … }

/// canPatternMatch - If it is impossible for this pattern to match on this
/// target, fill in Reason and return false.  Otherwise, return true.  This is
/// used as a sanity check for .td files (to prevent people from writing stuff
/// that can never possibly work), and to prevent the pattern permuter from
/// generating stuff that is useless.
bool TreePatternNode::canPatternMatch(std::string &Reason,
                                      const CodeGenDAGPatterns &CDP) { … }

//===----------------------------------------------------------------------===//
// TreePattern implementation
//

TreePattern::TreePattern(const Record *TheRec, const ListInit *RawPat,
                         bool isInput, CodeGenDAGPatterns &cdp)
    : … { … }

TreePattern::TreePattern(const Record *TheRec, DagInit *Pat, bool isInput,
                         CodeGenDAGPatterns &cdp)
    : … { … }

TreePattern::TreePattern(const Record *TheRec, TreePatternNodePtr Pat,
                         bool isInput, CodeGenDAGPatterns &cdp)
    : … { … }

void TreePattern::error(const Twine &Msg) { … }

void TreePattern::ComputeNamedNodes() { … }

void TreePattern::ComputeNamedNodes(TreePatternNode &N) { … }

TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit,
                                                 StringRef OpName) { … }

/// SimplifyTree - See if we can simplify this tree to eliminate something that
/// will never match in favor of something obvious that will.  This is here
/// strictly as a convenience to target authors because it allows them to write
/// more type generic things and have useless type casts fold away.
///
/// This returns true if any change is made.
static bool SimplifyTree(TreePatternNodePtr &N) { … }

/// InferAllTypes - Infer/propagate as many types throughout the expression
/// patterns as possible.  Return true if all types are inferred, false
/// otherwise.  Flags an error if a type contradiction is found.
bool TreePattern::InferAllTypes(
    const StringMap<SmallVector<TreePatternNode *, 1>> *InNamedTypes) { … }

void TreePattern::print(raw_ostream &OS) const { … }

void TreePattern::dump() const { … }

//===----------------------------------------------------------------------===//
// CodeGenDAGPatterns implementation
//

CodeGenDAGPatterns::CodeGenDAGPatterns(const RecordKeeper &R,
                                       PatternRewriterFn PatternRewriter)
    : … { … }

const Record *CodeGenDAGPatterns::getSDNodeNamed(StringRef Name) const { … }

// Parse all of the SDNode definitions for the target, populating SDNodes.
void CodeGenDAGPatterns::ParseNodeInfo() { … }

/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms
/// map, and emit them to the file as functions.
void CodeGenDAGPatterns::ParseNodeTransforms() { … }

void CodeGenDAGPatterns::ParseComplexPatterns() { … }

/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
/// file, building up the PatternFragments map.  After we've collected them all,
/// inline fragments together as necessary, so that there are no references left
/// inside a pattern fragment to a pattern fragment.
///
void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) { … }

void CodeGenDAGPatterns::ParseDefaultOperands() { … }

/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an
/// instruction input.  Return true if this is a real use.
static bool HandleUse(TreePattern &I, TreePatternNodePtr Pat,
                      std::map<std::string, TreePatternNodePtr> &InstInputs) { … }

/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
/// part of "I", the instruction), computing the set of inputs and outputs of
/// the pattern.  Report errors if we see anything naughty.
void CodeGenDAGPatterns::FindPatternInputsAndOutputs(
    TreePattern &I, TreePatternNodePtr Pat,
    std::map<std::string, TreePatternNodePtr> &InstInputs,
    MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>>
        &InstResults,
    std::vector<const Record *> &InstImpResults) { … }

//===----------------------------------------------------------------------===//
// Instruction Analysis
//===----------------------------------------------------------------------===//

class InstAnalyzer { … };

static bool InferFromPattern(CodeGenInstruction &InstInfo,
                             const InstAnalyzer &PatInfo,
                             const Record *PatDef) { … }

/// hasNullFragReference - Return true if the DAG has any reference to the
/// null_frag operator.
static bool hasNullFragReference(DagInit *DI) { … }

/// hasNullFragReference - Return true if any DAG in the list references
/// the null_frag operator.
static bool hasNullFragReference(ListInit *LI) { … }

/// Get all the instructions in a tree.
static void getInstructionsInTree(TreePatternNode &Tree,
                                  SmallVectorImpl<const Record *> &Instrs) { … }

/// Check the class of a pattern leaf node against the instruction operand it
/// represents.
static bool checkOperandClass(CGIOperandList::OperandInfo &OI,
                              const Record *Leaf) { … }

void CodeGenDAGPatterns::parseInstructionPattern(CodeGenInstruction &CGI,
                                                 const ListInit *Pat,
                                                 DAGInstMap &DAGInsts) { … }

/// ParseInstructions - Parse all of the instructions, inlining and resolving
/// any fragments involved.  This populates the Instructions list with fully
/// resolved instructions.
void CodeGenDAGPatterns::ParseInstructions() { … }

NameRecord;

static void FindNames(TreePatternNode &P,
                      std::map<std::string, NameRecord> &Names,
                      TreePattern *PatternTop) { … }

void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern,
                                           PatternToMatch &&PTM) { … }

void CodeGenDAGPatterns::InferInstructionFlags() { … }

/// Verify instruction flags against pattern node properties.
void CodeGenDAGPatterns::VerifyInstructionFlags() { … }

/// Given a pattern result with an unresolved type, see if we can find one
/// instruction with an unresolved result type.  Force this result type to an
/// arbitrary element if it's possible types to converge results.
static bool ForceArbitraryInstResultType(TreePatternNode &N, TreePattern &TP) { … }

// Promote xform function to be an explicit node wherever set.
static TreePatternNodePtr PromoteXForms(TreePatternNodePtr N) { … }

void CodeGenDAGPatterns::ParseOnePattern(
    const Record *TheDef, TreePattern &Pattern, TreePattern &Result,
    ArrayRef<const Record *> InstImpResults, bool ShouldIgnore) { … }

void CodeGenDAGPatterns::ParsePatterns() { … }

static void collectModes(std::set<unsigned> &Modes, const TreePatternNode &N) { … }

void CodeGenDAGPatterns::ExpandHwModeBasedTypes() { … }

/// Dependent variable map for CodeGenDAGPattern variant generation
DepVarMap;

static void FindDepVarsOf(TreePatternNode &N, DepVarMap &DepMap) { … }

/// Find dependent variables within child patterns
static void FindDepVars(TreePatternNode &N, MultipleUseVarSet &DepVars) { … }

#ifndef NDEBUG
/// Dump the dependent variable set:
static void DumpDepVars(MultipleUseVarSet &DepVars) {
  if (DepVars.empty()) {
    LLVM_DEBUG(errs() << "<empty set>");
  } else {
    LLVM_DEBUG(errs() << "[ ");
    for (const auto &DepVar : DepVars) {
      LLVM_DEBUG(errs() << DepVar.getKey() << " ");
    }
    LLVM_DEBUG(errs() << "]");
  }
}
#endif

/// CombineChildVariants - Given a bunch of permutations of each child of the
/// 'operator' node, put them together in all possible ways.
static void CombineChildVariants(
    TreePatternNodePtr Orig,
    const std::vector<std::vector<TreePatternNodePtr>> &ChildVariants,
    std::vector<TreePatternNodePtr> &OutVariants, CodeGenDAGPatterns &CDP,
    const MultipleUseVarSet &DepVars) { … }

/// CombineChildVariants - A helper function for binary operators.
///
static void CombineChildVariants(TreePatternNodePtr Orig,
                                 const std::vector<TreePatternNodePtr> &LHS,
                                 const std::vector<TreePatternNodePtr> &RHS,
                                 std::vector<TreePatternNodePtr> &OutVariants,
                                 CodeGenDAGPatterns &CDP,
                                 const MultipleUseVarSet &DepVars) { … }

static void
GatherChildrenOfAssociativeOpcode(TreePatternNodePtr N,
                                  std::vector<TreePatternNodePtr> &Children) { … }

/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of
/// the (potentially recursive) pattern by using algebraic laws.
///
static void GenerateVariantsOf(TreePatternNodePtr N,
                               std::vector<TreePatternNodePtr> &OutVariants,
                               CodeGenDAGPatterns &CDP,
                               const MultipleUseVarSet &DepVars) { … }

// GenerateVariants - Generate variants.  For example, commutative patterns can
// match multiple ways.  Add them to PatternsToMatch as well.
void CodeGenDAGPatterns::GenerateVariants() { … }

unsigned CodeGenDAGPatterns::getNewUID() { … }