+/// CombineChildVariants - A helper function for binary operators.
+///
+static void CombineChildVariants(TreePatternNode *Orig,
+ const std::vector<TreePatternNode*> &LHS,
+ const std::vector<TreePatternNode*> &RHS,
+ std::vector<TreePatternNode*> &OutVariants,
+ DAGISelEmitter &ISE) {
+ std::vector<std::vector<TreePatternNode*> > ChildVariants;
+ ChildVariants.push_back(LHS);
+ ChildVariants.push_back(RHS);
+ CombineChildVariants(Orig, ChildVariants, OutVariants, ISE);
+}
+
+
+static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N,
+ std::vector<TreePatternNode *> &Children) {
+ assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!");
+ Record *Operator = N->getOperator();
+
+ // Only permit raw nodes.
+ if (!N->getName().empty() || !N->getPredicateFn().empty() ||
+ N->getTransformFn()) {
+ Children.push_back(N);
+ return;
+ }
+
+ if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator)
+ Children.push_back(N->getChild(0));
+ else
+ GatherChildrenOfAssociativeOpcode(N->getChild(0), Children);
+
+ if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator)
+ Children.push_back(N->getChild(1));
+ else
+ GatherChildrenOfAssociativeOpcode(N->getChild(1), Children);
+}
+
+/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of
+/// the (potentially recursive) pattern by using algebraic laws.
+///
+static void GenerateVariantsOf(TreePatternNode *N,
+ std::vector<TreePatternNode*> &OutVariants,
+ DAGISelEmitter &ISE) {
+ // We cannot permute leaves.
+ if (N->isLeaf()) {
+ OutVariants.push_back(N);
+ return;
+ }
+
+ // Look up interesting info about the node.
+ const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(N->getOperator());
+
+ // If this node is associative, reassociate.
+ if (NodeInfo.hasProperty(SDNodeInfo::SDNPAssociative)) {
+ // Reassociate by pulling together all of the linked operators
+ std::vector<TreePatternNode*> MaximalChildren;
+ GatherChildrenOfAssociativeOpcode(N, MaximalChildren);
+
+ // Only handle child sizes of 3. Otherwise we'll end up trying too many
+ // permutations.
+ if (MaximalChildren.size() == 3) {
+ // Find the variants of all of our maximal children.
+ std::vector<TreePatternNode*> AVariants, BVariants, CVariants;
+ GenerateVariantsOf(MaximalChildren[0], AVariants, ISE);
+ GenerateVariantsOf(MaximalChildren[1], BVariants, ISE);
+ GenerateVariantsOf(MaximalChildren[2], CVariants, ISE);
+
+ // There are only two ways we can permute the tree:
+ // (A op B) op C and A op (B op C)
+ // Within these forms, we can also permute A/B/C.
+
+ // Generate legal pair permutations of A/B/C.
+ std::vector<TreePatternNode*> ABVariants;
+ std::vector<TreePatternNode*> BAVariants;
+ std::vector<TreePatternNode*> ACVariants;
+ std::vector<TreePatternNode*> CAVariants;
+ std::vector<TreePatternNode*> BCVariants;
+ std::vector<TreePatternNode*> CBVariants;
+ CombineChildVariants(N, AVariants, BVariants, ABVariants, ISE);
+ CombineChildVariants(N, BVariants, AVariants, BAVariants, ISE);
+ CombineChildVariants(N, AVariants, CVariants, ACVariants, ISE);
+ CombineChildVariants(N, CVariants, AVariants, CAVariants, ISE);
+ CombineChildVariants(N, BVariants, CVariants, BCVariants, ISE);
+ CombineChildVariants(N, CVariants, BVariants, CBVariants, ISE);
+
+ // Combine those into the result: (x op x) op x
+ CombineChildVariants(N, ABVariants, CVariants, OutVariants, ISE);
+ CombineChildVariants(N, BAVariants, CVariants, OutVariants, ISE);
+ CombineChildVariants(N, ACVariants, BVariants, OutVariants, ISE);
+ CombineChildVariants(N, CAVariants, BVariants, OutVariants, ISE);
+ CombineChildVariants(N, BCVariants, AVariants, OutVariants, ISE);
+ CombineChildVariants(N, CBVariants, AVariants, OutVariants, ISE);
+
+ // Combine those into the result: x op (x op x)
+ CombineChildVariants(N, CVariants, ABVariants, OutVariants, ISE);
+ CombineChildVariants(N, CVariants, BAVariants, OutVariants, ISE);
+ CombineChildVariants(N, BVariants, ACVariants, OutVariants, ISE);
+ CombineChildVariants(N, BVariants, CAVariants, OutVariants, ISE);
+ CombineChildVariants(N, AVariants, BCVariants, OutVariants, ISE);
+ CombineChildVariants(N, AVariants, CBVariants, OutVariants, ISE);
+ return;
+ }
+ }
+
+ // Compute permutations of all children.
+ std::vector<std::vector<TreePatternNode*> > ChildVariants;
+ ChildVariants.resize(N->getNumChildren());
+ for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
+ GenerateVariantsOf(N->getChild(i), ChildVariants[i], ISE);
+
+ // Build all permutations based on how the children were formed.
+ CombineChildVariants(N, ChildVariants, OutVariants, ISE);
+
+ // If this node is commutative, consider the commuted order.
+ if (NodeInfo.hasProperty(SDNodeInfo::SDNPCommutative)) {
+ assert(N->getNumChildren()==2 &&"Commutative but doesn't have 2 children!");
+ // Consider the commuted order.
+ CombineChildVariants(N, ChildVariants[1], ChildVariants[0],
+ OutVariants, ISE);
+ }
+}
+
+
+// GenerateVariants - Generate variants. For example, commutative patterns can
+// match multiple ways. Add them to PatternsToMatch as well.
+void DAGISelEmitter::GenerateVariants() {
+
+ DEBUG(std::cerr << "Generating instruction variants.\n");
+
+ // Loop over all of the patterns we've collected, checking to see if we can
+ // generate variants of the instruction, through the exploitation of
+ // identities. This permits the target to provide agressive matching without
+ // the .td file having to contain tons of variants of instructions.
+ //
+ // Note that this loop adds new patterns to the PatternsToMatch list, but we
+ // intentionally do not reconsider these. Any variants of added patterns have
+ // already been added.
+ //
+ for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) {
+ std::vector<TreePatternNode*> Variants;
+ GenerateVariantsOf(PatternsToMatch[i].first, Variants, *this);
+
+ assert(!Variants.empty() && "Must create at least original variant!");
+ Variants.erase(Variants.begin()); // Remove the original pattern.
+
+ if (Variants.empty()) // No variants for this pattern.
+ continue;
+
+ DEBUG(std::cerr << "FOUND VARIANTS OF: ";
+ PatternsToMatch[i].first->dump();
+ std::cerr << "\n");
+
+ for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
+ TreePatternNode *Variant = Variants[v];
+
+ DEBUG(std::cerr << " VAR#" << v << ": ";
+ Variant->dump();
+ std::cerr << "\n");
+
+ // Scan to see if an instruction or explicit pattern already matches this.
+ bool AlreadyExists = false;
+ for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) {
+ // Check to see if this variant already exists.
+ if (Variant->isIsomorphicTo(PatternsToMatch[p].first)) {
+ DEBUG(std::cerr << " *** ALREADY EXISTS, ignoring variant.\n");
+ AlreadyExists = true;
+ break;
+ }
+ }
+ // If we already have it, ignore the variant.
+ if (AlreadyExists) continue;
+
+ // Otherwise, add it to the list of patterns we have.
+ PatternsToMatch.push_back(std::make_pair(Variant,
+ PatternsToMatch[i].second));
+ }
+
+ DEBUG(std::cerr << "\n");
+ }
+}
+
+
+/// 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(TreePatternNode *P) {
+ assert(isExtIntegerVT(P->getExtType()) ||
+ isExtFloatingPointVT(P->getExtType()) &&
+ "Not a valid pattern node to size!");
+ unsigned Size = 1; // The node itself.
+
+ // Count children in the count if they are also nodes.
+ for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
+ TreePatternNode *Child = P->getChild(i);
+ if (!Child->isLeaf() && Child->getExtType() != MVT::Other)
+ Size += getPatternSize(Child);
+ }
+
+ return Size;
+}
+
+/// getResultPatternCost - Compute the number of instructions for this pattern.
+/// This is a temporary hack. We should really include the instruction
+/// latencies in this calculation.
+static unsigned getResultPatternCost(TreePatternNode *P) {
+ if (P->isLeaf()) return 0;
+
+ unsigned Cost = P->getOperator()->isSubClassOf("Instruction");
+ for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
+ Cost += getResultPatternCost(P->getChild(i));
+ return Cost;
+}
+
+// PatternSortingPredicate - return true if we prefer to match LHS before RHS.
+// In particular, we want to match maximal patterns first and lowest cost within
+// a particular complexity first.
+struct PatternSortingPredicate {
+ bool operator()(DAGISelEmitter::PatternToMatch *LHS,
+ DAGISelEmitter::PatternToMatch *RHS) {
+ unsigned LHSSize = getPatternSize(LHS->first);
+ unsigned RHSSize = getPatternSize(RHS->first);
+ if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost
+ if (LHSSize < RHSSize) return false;
+
+ // If the patterns have equal complexity, compare generated instruction cost
+ return getResultPatternCost(LHS->second) <getResultPatternCost(RHS->second);
+ }
+};
+