1094 lines · cpp
1//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "Basic/SDNodeProperties.h"10#include "Common/CodeGenDAGPatterns.h"11#include "Common/CodeGenInstruction.h"12#include "Common/CodeGenRegisters.h"13#include "Common/CodeGenTarget.h"14#include "Common/DAGISelMatcher.h"15#include "Common/InfoByHwMode.h"16#include "llvm/ADT/SmallVector.h"17#include "llvm/ADT/StringMap.h"18#include "llvm/TableGen/Error.h"19#include "llvm/TableGen/Record.h"20#include <utility>21using namespace llvm;22 23/// getRegisterValueType - Look up and return the ValueType of the specified24/// register. If the register is a member of multiple register classes, they25/// must all have the same type.26static MVT getRegisterValueType(const Record *R, const CodeGenTarget &T) {27 bool FoundRC = false;28 MVT VT = MVT::Other;29 const CodeGenRegister *Reg = T.getRegBank().getReg(R);30 31 for (const auto &RC : T.getRegBank().getRegClasses()) {32 if (!RC.contains(Reg))33 continue;34 35 if (!FoundRC) {36 FoundRC = true;37 const ValueTypeByHwMode &VVT = RC.getValueTypeNum(0);38 assert(VVT.isSimple());39 VT = VVT.getSimple();40 continue;41 }42 43#ifndef NDEBUG44 // If this occurs in multiple register classes, they all have to agree.45 const ValueTypeByHwMode &VVT = RC.getValueTypeNum(0);46 assert(VVT.isSimple() && VVT.getSimple() == VT &&47 "ValueType mismatch between register classes for this register");48#endif49 }50 return VT;51}52 53namespace {54class MatcherGen {55 const PatternToMatch &Pattern;56 const CodeGenDAGPatterns &CGP;57 58 /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts59 /// out with all of the types removed. This allows us to insert type checks60 /// as we scan the tree.61 TreePatternNodePtr PatWithNoTypes;62 63 /// VariableMap - A map from variable names ('$dst') to the recorded operand64 /// number that they were captured as. These are biased by 1 to make65 /// insertion easier.66 StringMap<unsigned> VariableMap;67 68 /// This maintains the recorded operand number that OPC_CheckComplexPattern69 /// drops each sub-operand into. We don't want to insert these into70 /// VariableMap because that leads to identity checking if they are71 /// encountered multiple times. Biased by 1 like VariableMap for72 /// consistency.73 StringMap<unsigned> NamedComplexPatternOperands;74 75 /// NextRecordedOperandNo - As we emit opcodes to record matched values in76 /// the RecordedNodes array, this keeps track of which slot will be next to77 /// record into.78 unsigned NextRecordedOperandNo = 0;79 80 /// MatchedChainNodes - This maintains the position in the recorded nodes81 /// array of all of the recorded input nodes that have chains.82 SmallVector<unsigned, 2> MatchedChainNodes;83 84 /// MatchedComplexPatterns - This maintains a list of all of the85 /// ComplexPatterns that we need to check. The second element of each pair86 /// is the recorded operand number of the input node.87 SmallVector<std::pair<const TreePatternNode *, unsigned>, 2>88 MatchedComplexPatterns;89 90 /// PhysRegInputs - List list has an entry for each explicitly specified91 /// physreg input to the pattern. The first elt is the Register node, the92 /// second is the recorded slot number the input pattern match saved it in.93 SmallVector<std::pair<const Record *, unsigned>, 2> PhysRegInputs;94 95 /// Matcher - This is the top level of the generated matcher, the result.96 Matcher *TheMatcher = nullptr;97 98 /// CurPredicate - As we emit matcher nodes, this points to the latest check99 /// which should have future checks stuck into its Next position.100 Matcher *CurPredicate = nullptr;101 102public:103 MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);104 105 bool EmitMatcherCode(unsigned Variant);106 void EmitResultCode();107 108 Matcher *GetMatcher() const { return TheMatcher; }109 110private:111 void AddMatcher(Matcher *NewNode);112 void InferPossibleTypes();113 114 // Matcher Generation.115 void EmitMatchCode(const TreePatternNode &N, TreePatternNode &NodeNoTypes);116 void EmitLeafMatchCode(const TreePatternNode &N);117 void EmitOperatorMatchCode(const TreePatternNode &N,118 TreePatternNode &NodeNoTypes);119 120 /// If this is the first time a node with unique identifier Name has been121 /// seen, record it. Otherwise, emit a check to make sure this is the same122 /// node. Returns true if this is the first encounter.123 bool recordUniqueNode(ArrayRef<std::string> Names);124 125 // Result Code Generation.126 unsigned getNamedArgumentSlot(StringRef Name) {127 unsigned VarMapEntry = VariableMap[Name];128 assert(VarMapEntry != 0 &&129 "Variable referenced but not defined and not caught earlier!");130 return VarMapEntry - 1;131 }132 133 void EmitResultOperand(const TreePatternNode &N,134 SmallVectorImpl<unsigned> &ResultOps);135 void EmitResultOfNamedOperand(const TreePatternNode &N,136 SmallVectorImpl<unsigned> &ResultOps);137 void EmitResultLeafAsOperand(const TreePatternNode &N,138 SmallVectorImpl<unsigned> &ResultOps);139 void EmitResultInstructionAsOperand(const TreePatternNode &N,140 SmallVectorImpl<unsigned> &ResultOps);141 void EmitResultSDNodeXFormAsOperand(const TreePatternNode &N,142 SmallVectorImpl<unsigned> &ResultOps);143};144 145} // end anonymous namespace146 147MatcherGen::MatcherGen(const PatternToMatch &pattern,148 const CodeGenDAGPatterns &cgp)149 : Pattern(pattern), CGP(cgp) {150 // We need to produce the matcher tree for the patterns source pattern. To151 // do this we need to match the structure as well as the types. To do the152 // type matching, we want to figure out the fewest number of type checks we153 // need to emit. For example, if there is only one integer type supported154 // by a target, there should be no type comparisons at all for integer155 // patterns!156 //157 // To figure out the fewest number of type checks needed, clone the pattern,158 // remove the types, then perform type inference on the pattern as a whole.159 // If there are unresolved types, emit an explicit check for those types,160 // apply the type to the tree, then rerun type inference. Iterate until all161 // types are resolved.162 //163 PatWithNoTypes = Pattern.getSrcPattern().clone();164 PatWithNoTypes->RemoveAllTypes();165 166 // If there are types that are manifestly known, infer them.167 InferPossibleTypes();168}169 170/// InferPossibleTypes - As we emit the pattern, we end up generating type171/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we172/// want to propagate implied types as far throughout the tree as possible so173/// that we avoid doing redundant type checks. This does the type propagation.174void MatcherGen::InferPossibleTypes() {175 // TP - Get *SOME* tree pattern, we don't care which. It is only used for176 // diagnostics, which we know are impossible at this point.177 TreePattern &TP = *CGP.pf_begin()->second;178 179 bool MadeChange = true;180 while (MadeChange)181 MadeChange = PatWithNoTypes->ApplyTypeConstraints(182 TP, true /*Ignore reg constraints*/);183}184 185/// AddMatcher - Add a matcher node to the current graph we're building.186void MatcherGen::AddMatcher(Matcher *NewNode) {187 if (CurPredicate)188 CurPredicate->setNext(NewNode);189 else190 TheMatcher = NewNode;191 CurPredicate = NewNode;192}193 194//===----------------------------------------------------------------------===//195// Pattern Match Generation196//===----------------------------------------------------------------------===//197 198/// EmitLeafMatchCode - Generate matching code for leaf nodes.199void MatcherGen::EmitLeafMatchCode(const TreePatternNode &N) {200 assert(N.isLeaf() && "Not a leaf?");201 202 // Direct match against an integer constant.203 if (const IntInit *II = dyn_cast<IntInit>(N.getLeafValue())) {204 // If this is the root of the dag we're matching, we emit a redundant opcode205 // check to ensure that this gets folded into the normal top-level206 // OpcodeSwitch.207 if (&N == &Pattern.getSrcPattern()) {208 const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed("imm"));209 AddMatcher(new CheckOpcodeMatcher(NI));210 }211 212 return AddMatcher(new CheckIntegerMatcher(II->getValue()));213 }214 215 // An UnsetInit represents a named node without any constraints.216 if (isa<UnsetInit>(N.getLeafValue())) {217 assert(N.hasName() && "Unnamed ? leaf");218 return;219 }220 221 const DefInit *DI = dyn_cast<DefInit>(N.getLeafValue());222 if (!DI) {223 errs() << "Unknown leaf kind: " << N << "\n";224 abort();225 }226 227 const Record *LeafRec = DI->getDef();228 229 // A ValueType leaf node can represent a register when named, or itself when230 // unnamed.231 if (LeafRec->isSubClassOf("ValueType")) {232 // A named ValueType leaf always matches: (add i32:$a, i32:$b).233 if (N.hasName())234 return;235 // An unnamed ValueType as in (sext_inreg GPR:$foo, i8).236 return AddMatcher(new CheckValueTypeMatcher(llvm::getValueType(LeafRec)));237 }238 239 if ( // Handle register references. Nothing to do here, they always match.240 LeafRec->isSubClassOf("RegisterClassLike") ||241 LeafRec->isSubClassOf("RegisterOperand") ||242 LeafRec->isSubClassOf("SubRegIndex") ||243 // Place holder for SRCVALUE nodes. Nothing to do here.244 LeafRec->getName() == "srcvalue")245 return;246 247 // If we have a physreg reference like (mul gpr:$src, EAX) then we need to248 // record the register249 if (LeafRec->isSubClassOf("Register")) {250 AddMatcher(new RecordMatcher("physreg input " + LeafRec->getName().str(),251 NextRecordedOperandNo));252 PhysRegInputs.emplace_back(LeafRec, NextRecordedOperandNo++);253 return;254 }255 256 if (LeafRec->isSubClassOf("CondCode"))257 return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName()));258 259 if (LeafRec->isSubClassOf("ComplexPattern")) {260 // We can't model ComplexPattern uses that don't have their name taken yet.261 // The OPC_CheckComplexPattern operation implicitly records the results.262 if (N.getName().empty()) {263 std::string S;264 raw_string_ostream OS(S);265 OS << "We expect complex pattern uses to have names: " << N;266 PrintFatalError(S);267 }268 269 // Remember this ComplexPattern so that we can emit it after all the other270 // structural matches are done.271 unsigned InputOperand = VariableMap[N.getName()] - 1;272 MatchedComplexPatterns.emplace_back(&N, InputOperand);273 return;274 }275 276 if (LeafRec->getName() == "immAllOnesV" ||277 LeafRec->getName() == "immAllZerosV") {278 // If this is the root of the dag we're matching, we emit a redundant opcode279 // check to ensure that this gets folded into the normal top-level280 // OpcodeSwitch.281 if (&N == &Pattern.getSrcPattern()) {282 MVT VT = N.getSimpleType(0);283 StringRef Name = VT.isScalableVector() ? "splat_vector" : "build_vector";284 const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed(Name));285 AddMatcher(new CheckOpcodeMatcher(NI));286 }287 if (LeafRec->getName() == "immAllOnesV")288 AddMatcher(new CheckImmAllOnesVMatcher());289 else290 AddMatcher(new CheckImmAllZerosVMatcher());291 return;292 }293 294 errs() << "Unknown leaf kind: " << N << "\n";295 abort();296}297 298void MatcherGen::EmitOperatorMatchCode(const TreePatternNode &N,299 TreePatternNode &NodeNoTypes) {300 assert(!N.isLeaf() && "Not an operator?");301 302 if (N.getOperator()->isSubClassOf("ComplexPattern")) {303 // The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is304 // "MY_PAT:op1:op2". We should already have validated that the uses are305 // consistent.306 std::string PatternName = N.getOperator()->getName().str();307 for (const TreePatternNode &Child : N.children()) {308 PatternName += ":";309 PatternName += Child.getName();310 }311 312 if (recordUniqueNode(PatternName)) {313 auto NodeAndOpNum = std::pair(&N, NextRecordedOperandNo - 1);314 MatchedComplexPatterns.push_back(NodeAndOpNum);315 }316 317 return;318 }319 320 const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N.getOperator());321 322 // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is323 // a constant without a predicate fn that has more than one bit set, handle324 // this as a special case. This is usually for targets that have special325 // handling of certain large constants (e.g. alpha with it's 8/16/32-bit326 // handling stuff). Using these instructions is often far more efficient327 // than materializing the constant. Unfortunately, both the instcombiner328 // and the dag combiner can often infer that bits are dead, and thus drop329 // them from the mask in the dag. For example, it might turn 'AND X, 255'330 // into 'AND X, 254' if it knows the low bit is set. Emit code that checks331 // to handle this.332 if ((N.getOperator()->getName() == "and" ||333 N.getOperator()->getName() == "or") &&334 N.getChild(1).isLeaf() && N.getChild(1).getPredicateCalls().empty() &&335 N.getPredicateCalls().empty()) {336 if (const IntInit *II = dyn_cast<IntInit>(N.getChild(1).getLeafValue())) {337 if (!llvm::has_single_bit<uint32_t>(338 II->getValue())) { // Don't bother with single bits.339 // If this is at the root of the pattern, we emit a redundant340 // CheckOpcode so that the following checks get factored properly under341 // a single opcode check.342 if (&N == &Pattern.getSrcPattern())343 AddMatcher(new CheckOpcodeMatcher(CInfo));344 345 // Emit the CheckAndImm/CheckOrImm node.346 if (N.getOperator()->getName() == "and")347 AddMatcher(new CheckAndImmMatcher(II->getValue()));348 else349 AddMatcher(new CheckOrImmMatcher(II->getValue()));350 351 // Match the LHS of the AND as appropriate.352 AddMatcher(new MoveChildMatcher(0));353 EmitMatchCode(N.getChild(0), NodeNoTypes.getChild(0));354 AddMatcher(new MoveParentMatcher());355 return;356 }357 }358 }359 360 // Check that the current opcode lines up.361 AddMatcher(new CheckOpcodeMatcher(CInfo));362 363 // If this node has memory references (i.e. is a load or store), tell the364 // interpreter to capture them in the memref array.365 if (N.NodeHasProperty(SDNPMemOperand, CGP))366 AddMatcher(new RecordMemRefMatcher());367 368 // If this node has a chain, then the chain is operand #0 is the SDNode, and369 // the child numbers of the node are all offset by one.370 unsigned OpNo = 0;371 if (N.NodeHasProperty(SDNPHasChain, CGP)) {372 // Record the node and remember it in our chained nodes list.373 AddMatcher(new RecordMatcher("'" + N.getOperator()->getName().str() +374 "' chained node",375 NextRecordedOperandNo));376 // Remember all of the input chains our pattern will match.377 MatchedChainNodes.push_back(NextRecordedOperandNo++);378 379 // Don't look at the input chain when matching the tree pattern to the380 // SDNode.381 OpNo = 1;382 383 // If this node is not the root and the subtree underneath it produces a384 // chain, then the result of matching the node is also produce a chain.385 // Beyond that, this means that we're also folding (at least) the root node386 // into the node that produce the chain (for example, matching387 // "(add reg, (load ptr))" as a add_with_memory on X86). This is388 // problematic, if the 'reg' node also uses the load (say, its chain).389 // Graphically:390 //391 // [LD]392 // ^ ^393 // | \ DAG's like cheese.394 // / |395 // / [YY]396 // | ^397 // [XX]--/398 //399 // It would be invalid to fold XX and LD. In this case, folding the two400 // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG'401 // To prevent this, we emit a dynamic check for legality before allowing402 // this to be folded.403 //404 const TreePatternNode &Root = Pattern.getSrcPattern();405 if (&N != &Root) { // Not the root of the pattern.406 // If there is a node between the root and this node, then we definitely407 // need to emit the check.408 bool NeedCheck = !Root.hasChild(&N);409 410 // If it *is* an immediate child of the root, we can still need a check if411 // the root SDNode has multiple inputs. For us, this means that it is an412 // intrinsic, has multiple operands, or has other inputs like chain or413 // glue).414 if (!NeedCheck) {415 const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root.getOperator());416 NeedCheck =417 Root.getOperator() == CGP.get_intrinsic_void_sdnode() ||418 Root.getOperator() == CGP.get_intrinsic_w_chain_sdnode() ||419 Root.getOperator() == CGP.get_intrinsic_wo_chain_sdnode() ||420 PInfo.getNumOperands() > 1 || PInfo.hasProperty(SDNPHasChain) ||421 PInfo.hasProperty(SDNPInGlue) || PInfo.hasProperty(SDNPOptInGlue);422 }423 424 if (NeedCheck)425 AddMatcher(new CheckFoldableChainNodeMatcher());426 }427 }428 429 // If this node has an output glue and isn't the root, remember it.430 if (N.NodeHasProperty(SDNPOutGlue, CGP) && &N != &Pattern.getSrcPattern()) {431 // TODO: This redundantly records nodes with both glues and chains.432 433 // Record the node and remember it in our chained nodes list.434 AddMatcher(new RecordMatcher("'" + N.getOperator()->getName().str() +435 "' glue output node",436 NextRecordedOperandNo));437 }438 439 // If this node is known to have an input glue or if it *might* have an input440 // glue, capture it as the glue input of the pattern.441 if (N.NodeHasProperty(SDNPOptInGlue, CGP) ||442 N.NodeHasProperty(SDNPInGlue, CGP))443 AddMatcher(new CaptureGlueInputMatcher());444 445 for (unsigned i = 0, e = N.getNumChildren(); i != e; ++i, ++OpNo) {446 // Get the code suitable for matching this child. Move to the child, check447 // it then move back to the parent.448 AddMatcher(new MoveChildMatcher(OpNo));449 EmitMatchCode(N.getChild(i), NodeNoTypes.getChild(i));450 AddMatcher(new MoveParentMatcher());451 }452}453 454bool MatcherGen::recordUniqueNode(ArrayRef<std::string> Names) {455 unsigned Entry = 0;456 for (const std::string &Name : Names) {457 unsigned &VarMapEntry = VariableMap[Name];458 if (!Entry)459 Entry = VarMapEntry;460 assert(Entry == VarMapEntry);461 }462 463 bool NewRecord = false;464 if (Entry == 0) {465 // If it is a named node, we must emit a 'Record' opcode.466 std::string WhatFor;467 for (const std::string &Name : Names) {468 if (!WhatFor.empty())469 WhatFor += ',';470 WhatFor += "$" + Name;471 }472 AddMatcher(new RecordMatcher(WhatFor, NextRecordedOperandNo));473 Entry = ++NextRecordedOperandNo;474 NewRecord = true;475 } else {476 // If we get here, this is a second reference to a specific name. Since477 // we already have checked that the first reference is valid, we don't478 // have to recursively match it, just check that it's the same as the479 // previously named thing.480 AddMatcher(new CheckSameMatcher(Entry - 1));481 }482 483 for (const std::string &Name : Names)484 VariableMap[Name] = Entry;485 486 return NewRecord;487}488 489void MatcherGen::EmitMatchCode(const TreePatternNode &N,490 TreePatternNode &NodeNoTypes) {491 // If N and NodeNoTypes don't agree on a type, then this is a case where we492 // need to do a type check. Emit the check, apply the type to NodeNoTypes and493 // reinfer any correlated types.494 SmallVector<unsigned, 2> ResultsToTypeCheck;495 496 for (unsigned i = 0, e = NodeNoTypes.getNumTypes(); i != e; ++i) {497 if (NodeNoTypes.getExtType(i) == N.getExtType(i))498 continue;499 NodeNoTypes.setType(i, N.getExtType(i));500 InferPossibleTypes();501 ResultsToTypeCheck.push_back(i);502 }503 504 // If this node has a name associated with it, capture it in VariableMap. If505 // we already saw this in the pattern, emit code to verify dagness.506 SmallVector<std::string, 4> Names;507 if (!N.getName().empty())508 Names.push_back(N.getName().str());509 510 for (const ScopedName &Name : N.getNamesAsPredicateArg()) {511 Names.push_back(512 ("pred:" + Twine(Name.getScope()) + ":" + Name.getIdentifier()).str());513 }514 515 if (!Names.empty()) {516 if (!recordUniqueNode(Names))517 return;518 }519 520 if (N.isLeaf())521 EmitLeafMatchCode(N);522 else523 EmitOperatorMatchCode(N, NodeNoTypes);524 525 // If there are node predicates for this node, generate their checks.526 for (const TreePredicateCall &Pred : N.getPredicateCalls()) {527 SmallVector<unsigned, 4> Operands;528 if (Pred.Fn.usesOperands()) {529 TreePattern *TP = Pred.Fn.getOrigPatFragRecord();530 for (const std::string &Arg : TP->getArgList()) {531 std::string Name = ("pred:" + Twine(Pred.Scope) + ":" + Arg).str();532 Operands.push_back(getNamedArgumentSlot(Name));533 }534 }535 AddMatcher(new CheckPredicateMatcher(Pred.Fn, Operands));536 }537 538 for (unsigned I : ResultsToTypeCheck)539 AddMatcher(new CheckTypeMatcher(N.getSimpleType(I), I));540}541 542/// EmitMatcherCode - Generate the code that matches the predicate of this543/// pattern for the specified Variant. If the variant is invalid this returns544/// true and does not generate code, if it is valid, it returns false.545bool MatcherGen::EmitMatcherCode(unsigned Variant) {546 // If the root of the pattern is a ComplexPattern and if it is specified to547 // match some number of root opcodes, these are considered to be our variants.548 // Depending on which variant we're generating code for, emit the root opcode549 // check.550 if (const ComplexPattern *CP =551 Pattern.getSrcPattern().getComplexPatternInfo(CGP)) {552 ArrayRef<const Record *> OpNodes = CP->getRootNodes();553 assert(!OpNodes.empty() &&554 "Complex Pattern must specify what it can match");555 if (Variant >= OpNodes.size())556 return true;557 558 AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant])));559 } else {560 if (Variant != 0)561 return true;562 }563 564 // Emit the matcher for the pattern structure and types.565 EmitMatchCode(Pattern.getSrcPattern(), *PatWithNoTypes);566 567 // If the pattern has a predicate on it (e.g. only enabled when a subtarget568 // feature is around, do the check).569 std::string PredicateCheck = Pattern.getPredicateCheck();570 if (!PredicateCheck.empty())571 AddMatcher(new CheckPatternPredicateMatcher(PredicateCheck));572 573 // Now that we've completed the structural type match, emit any ComplexPattern574 // checks (e.g. addrmode matches). We emit this after the structural match575 // because they are generally more expensive to evaluate and more difficult to576 // factor.577 for (const auto &MCP : MatchedComplexPatterns) {578 auto &N = *MCP.first;579 580 // Remember where the results of this match get stuck.581 if (N.isLeaf()) {582 NamedComplexPatternOperands[N.getName()] = NextRecordedOperandNo + 1;583 } else {584 unsigned CurOp = NextRecordedOperandNo;585 for (const TreePatternNode &Child : N.children()) {586 NamedComplexPatternOperands[Child.getName()] = CurOp + 1;587 CurOp += Child.getNumMIResults(CGP);588 }589 }590 591 // Get the slot we recorded the value in from the name on the node.592 unsigned RecNodeEntry = MCP.second;593 594 const ComplexPattern *CP = N.getComplexPatternInfo(CGP);595 assert(CP && "Not a valid ComplexPattern!");596 597 // Emit a CheckComplexPat operation, which does the match (aborting if it598 // fails) and pushes the matched operands onto the recorded nodes list.599 AddMatcher(new CheckComplexPatMatcher(*CP, RecNodeEntry, N.getName(),600 NextRecordedOperandNo));601 602 // Record the right number of operands.603 NextRecordedOperandNo += CP->getNumOperands();604 if (CP->hasProperty(SDNPHasChain)) {605 // If the complex pattern has a chain, then we need to keep track of the606 // fact that we just recorded a chain input. The chain input will be607 // matched as the last operand of the predicate if it was successful.608 ++NextRecordedOperandNo; // Chained node operand.609 610 // It is the last operand recorded.611 assert(NextRecordedOperandNo > 1 &&612 "Should have recorded input/result chains at least!");613 MatchedChainNodes.push_back(NextRecordedOperandNo - 1);614 }615 616 // TODO: Complex patterns can't have output glues, if they did, we'd want617 // to record them.618 }619 620 return false;621}622 623//===----------------------------------------------------------------------===//624// Node Result Generation625//===----------------------------------------------------------------------===//626 627void MatcherGen::EmitResultOfNamedOperand(628 const TreePatternNode &N, SmallVectorImpl<unsigned> &ResultOps) {629 assert(!N.getName().empty() && "Operand not named!");630 631 if (unsigned SlotNo = NamedComplexPatternOperands[N.getName()]) {632 // Complex operands have already been completely selected, just find the633 // right slot ant add the arguments directly.634 for (unsigned i = 0; i < N.getNumMIResults(CGP); ++i)635 ResultOps.push_back(SlotNo - 1 + i);636 637 return;638 }639 640 unsigned SlotNo = getNamedArgumentSlot(N.getName());641 642 // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target643 // version of the immediate so that it doesn't get selected due to some other644 // node use.645 if (!N.isLeaf()) {646 StringRef OperatorName = N.getOperator()->getName();647 if (OperatorName == "imm" || OperatorName == "fpimm") {648 AddMatcher(new EmitConvertToTargetMatcher(SlotNo, NextRecordedOperandNo));649 ResultOps.push_back(NextRecordedOperandNo++);650 return;651 }652 }653 654 for (unsigned i = 0; i < N.getNumMIResults(CGP); ++i)655 ResultOps.push_back(SlotNo + i);656}657 658void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode &N,659 SmallVectorImpl<unsigned> &ResultOps) {660 assert(N.isLeaf() && "Must be a leaf");661 662 if (const IntInit *II = dyn_cast<IntInit>(N.getLeafValue())) {663 AddMatcher(new EmitIntegerMatcher(II->getValue(), N.getSimpleType(0),664 NextRecordedOperandNo));665 ResultOps.push_back(NextRecordedOperandNo++);666 return;667 }668 669 // If this is an explicit register reference, handle it.670 if (const DefInit *DI = dyn_cast<DefInit>(N.getLeafValue())) {671 const Record *Def = DI->getDef();672 if (Def->isSubClassOf("Register")) {673 const CodeGenRegister *Reg = CGP.getTargetInfo().getRegBank().getReg(Def);674 AddMatcher(new EmitRegisterMatcher(Reg, N.getSimpleType(0),675 NextRecordedOperandNo));676 ResultOps.push_back(NextRecordedOperandNo++);677 return;678 }679 680 if (Def->getName() == "zero_reg") {681 AddMatcher(new EmitRegisterMatcher(nullptr, N.getSimpleType(0),682 NextRecordedOperandNo));683 ResultOps.push_back(NextRecordedOperandNo++);684 return;685 }686 687 if (Def->getName() == "undef_tied_input") {688 MVT ResultVT = N.getSimpleType(0);689 auto IDOperandNo = NextRecordedOperandNo++;690 const Record *ImpDef = Def->getRecords().getDef("IMPLICIT_DEF");691 const CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(ImpDef);692 AddMatcher(new EmitNodeMatcher(II, ResultVT, {}, false, false, false,693 false, -1, IDOperandNo));694 ResultOps.push_back(IDOperandNo);695 return;696 }697 698 // Handle a reference to a register class. This is used699 // in COPY_TO_SUBREG instructions.700 if (Def->isSubClassOf("RegisterOperand"))701 Def = Def->getValueAsDef("RegClass");702 if (Def->isSubClassOf("RegisterClass")) {703 // If the register class has an enum integer value greater than 127, the704 // encoding overflows the limit of 7 bits, which precludes the use of705 // StringIntegerMatcher. In this case, fallback to using IntegerMatcher.706 const CodeGenRegisterClass &RC =707 CGP.getTargetInfo().getRegisterClass(Def);708 if (RC.EnumValue <= 127) {709 std::string Value = RC.getQualifiedIdName();710 AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32,711 NextRecordedOperandNo));712 } else {713 AddMatcher(new EmitIntegerMatcher(RC.EnumValue, MVT::i32,714 NextRecordedOperandNo));715 }716 ResultOps.push_back(NextRecordedOperandNo++);717 return;718 }719 720 // Handle a subregister index. This is used for INSERT_SUBREG etc.721 if (Def->isSubClassOf("SubRegIndex")) {722 const CodeGenRegBank &RB = CGP.getTargetInfo().getRegBank();723 // If we have more than 127 subreg indices the encoding can overflow724 // 7 bit and we cannot use StringInteger.725 if (RB.getSubRegIndices().size() > 127) {726 const CodeGenSubRegIndex *I = RB.findSubRegIdx(Def);727 if (I->EnumValue > 127) {728 AddMatcher(new EmitIntegerMatcher(I->EnumValue, MVT::i32,729 NextRecordedOperandNo));730 ResultOps.push_back(NextRecordedOperandNo++);731 return;732 }733 }734 std::string Value = getQualifiedName(Def);735 AddMatcher(736 new EmitStringIntegerMatcher(Value, MVT::i32, NextRecordedOperandNo));737 ResultOps.push_back(NextRecordedOperandNo++);738 return;739 }740 }741 742 errs() << "unhandled leaf node:\n";743 N.dump();744}745 746static bool mayInstNodeLoadOrStore(const TreePatternNode &N,747 const CodeGenDAGPatterns &CGP) {748 const Record *Op = N.getOperator();749 const CodeGenTarget &CGT = CGP.getTargetInfo();750 const CodeGenInstruction &II = CGT.getInstruction(Op);751 return II.mayLoad || II.mayStore;752}753 754static unsigned numNodesThatMayLoadOrStore(const TreePatternNode &N,755 const CodeGenDAGPatterns &CGP) {756 if (N.isLeaf())757 return 0;758 759 const Record *OpRec = N.getOperator();760 if (!OpRec->isSubClassOf("Instruction"))761 return 0;762 763 unsigned Count = 0;764 if (mayInstNodeLoadOrStore(N, CGP))765 ++Count;766 767 for (const TreePatternNode &Child : N.children())768 Count += numNodesThatMayLoadOrStore(Child, CGP);769 770 return Count;771}772 773void MatcherGen::EmitResultInstructionAsOperand(774 const TreePatternNode &N, SmallVectorImpl<unsigned> &OutputOps) {775 const Record *Op = N.getOperator();776 const CodeGenTarget &CGT = CGP.getTargetInfo();777 const CodeGenInstruction &II = CGT.getInstruction(Op);778 const DAGInstruction &Inst = CGP.getInstruction(Op);779 780 bool isRoot = &N == &Pattern.getDstPattern();781 782 // TreeHasOutGlue - True if this tree has glue.783 bool TreeHasInGlue = false, TreeHasOutGlue = false;784 if (isRoot) {785 const TreePatternNode &SrcPat = Pattern.getSrcPattern();786 TreeHasInGlue = SrcPat.TreeHasProperty(SDNPOptInGlue, CGP) ||787 SrcPat.TreeHasProperty(SDNPInGlue, CGP);788 789 // FIXME2: this is checking the entire pattern, not just the node in790 // question, doing this just for the root seems like a total hack.791 TreeHasOutGlue = SrcPat.TreeHasProperty(SDNPOutGlue, CGP);792 }793 794 // NumResults - This is the number of results produced by the instruction in795 // the "outs" list.796 unsigned NumResults = Inst.getNumResults();797 798 // Number of operands we know the output instruction must have. If it is799 // variadic, we could have more operands.800 unsigned NumFixedOperands = II.Operands.size();801 802 SmallVector<unsigned, 8> InstOps;803 804 // Loop over all of the fixed operands of the instruction pattern, emitting805 // code to fill them all in. The node 'N' usually has number children equal to806 // the number of input operands of the instruction. However, in cases where807 // there are predicate operands for an instruction, we need to fill in the808 // 'execute always' values. Match up the node operands to the instruction809 // operands to do this.810 unsigned ChildNo = 0;811 812 // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the813 // number of operands at the end of the list which have default values.814 // Those can come from the pattern if it provides enough arguments, or be815 // filled in with the default if the pattern hasn't provided them. But any816 // operand with a default value _before_ the last mandatory one will be817 // filled in with their defaults unconditionally.818 unsigned NonOverridableOperands = NumFixedOperands;819 while (NonOverridableOperands > NumResults &&820 CGP.operandHasDefault(II.Operands[NonOverridableOperands - 1].Rec))821 --NonOverridableOperands;822 823 for (unsigned InstOpNo = NumResults, e = NumFixedOperands; InstOpNo != e;824 ++InstOpNo) {825 // Determine what to emit for this operand.826 const Record *OperandNode = II.Operands[InstOpNo].Rec;827 if (CGP.operandHasDefault(OperandNode) &&828 (InstOpNo < NonOverridableOperands || ChildNo >= N.getNumChildren())) {829 // This is a predicate or optional def operand which the pattern has not830 // overridden, or which we aren't letting it override; emit the 'default831 // ops' operands.832 const DAGDefaultOperand &DefaultOp = CGP.getDefaultOperand(OperandNode);833 for (const TreePatternNodePtr &Op : DefaultOp.DefaultOps)834 EmitResultOperand(*Op, InstOps);835 continue;836 }837 838 // Otherwise this is a normal operand or a predicate operand without839 // 'execute always'; emit it.840 841 // For operands with multiple sub-operands we may need to emit842 // multiple child patterns to cover them all. However, ComplexPattern843 // children may themselves emit multiple MI operands.844 unsigned NumSubOps = 1;845 if (OperandNode->isSubClassOf("Operand")) {846 const DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo");847 if (unsigned NumArgs = MIOpInfo->getNumArgs())848 NumSubOps = NumArgs;849 }850 851 unsigned FinalNumOps = InstOps.size() + NumSubOps;852 while (InstOps.size() < FinalNumOps) {853 const TreePatternNode &Child = N.getChild(ChildNo);854 unsigned BeforeAddingNumOps = InstOps.size();855 EmitResultOperand(Child, InstOps);856 assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands");857 858 // If the operand is an instruction and it produced multiple results, just859 // take the first one.860 if (!Child.isLeaf() && Child.getOperator()->isSubClassOf("Instruction"))861 InstOps.resize(BeforeAddingNumOps + 1);862 863 ++ChildNo;864 }865 }866 867 // If this is a variadic output instruction (i.e. REG_SEQUENCE), we can't868 // expand suboperands, use default operands, or other features determined from869 // the CodeGenInstruction after the fixed operands, which were handled870 // above. Emit the remaining instructions implicitly added by the use for871 // variable_ops.872 if (II.Operands.isVariadic) {873 for (unsigned I = ChildNo, E = N.getNumChildren(); I < E; ++I)874 EmitResultOperand(N.getChild(I), InstOps);875 }876 877 // If this node has input glue or explicitly specified input physregs, we878 // need to add chained and glued copyfromreg nodes and materialize the glue879 // input.880 if (isRoot && !PhysRegInputs.empty()) {881 // Emit all of the CopyToReg nodes for the input physical registers. These882 // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src).883 for (const auto &PhysRegInput : PhysRegInputs) {884 const CodeGenRegister *Reg =885 CGP.getTargetInfo().getRegBank().getReg(PhysRegInput.first);886 AddMatcher(new EmitCopyToRegMatcher(PhysRegInput.second, Reg));887 }888 889 // Even if the node has no other glue inputs, the resultant node must be890 // glued to the CopyFromReg nodes we just generated.891 TreeHasInGlue = true;892 }893 894 // Result order: node results, chain, glue895 896 // Determine the result types.897 SmallVector<MVT, 4> ResultVTs;898 for (unsigned i = 0, e = N.getNumTypes(); i != e; ++i)899 ResultVTs.push_back(N.getSimpleType(i));900 901 // If this is the root instruction of a pattern that has physical registers in902 // its result pattern, add output VTs for them. For example, X86 has:903 // (set AL, (mul ...))904 if (isRoot && !Pattern.getDstRegs().empty()) {905 // If the root came from an implicit def in the instruction handling stuff,906 // don't re-add it.907 const Record *HandledReg = nullptr;908 if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other)909 HandledReg = II.ImplicitDefs[0];910 911 for (const Record *Reg : Pattern.getDstRegs()) {912 if (!Reg->isSubClassOf("Register") || Reg == HandledReg)913 continue;914 ResultVTs.push_back(getRegisterValueType(Reg, CGT));915 }916 }917 918 // If this is the root of the pattern and the pattern we're matching includes919 // a node that is variadic, mark the generated node as variadic so that it920 // gets the excess operands from the input DAG.921 int NumFixedArityOperands = -1;922 if (isRoot && Pattern.getSrcPattern().NodeHasProperty(SDNPVariadic, CGP))923 NumFixedArityOperands = Pattern.getSrcPattern().getNumChildren();924 925 // If this is the root node and multiple matched nodes in the input pattern926 // have MemRefs in them, have the interpreter collect them and plop them onto927 // this node. If there is just one node with MemRefs, leave them on that node928 // even if it is not the root.929 //930 // FIXME3: This is actively incorrect for result patterns with multiple931 // memory-referencing instructions.932 bool PatternHasMemOperands =933 Pattern.getSrcPattern().TreeHasProperty(SDNPMemOperand, CGP);934 935 bool NodeHasMemRefs = false;936 if (PatternHasMemOperands) {937 unsigned NumNodesThatLoadOrStore =938 numNodesThatMayLoadOrStore(Pattern.getDstPattern(), CGP);939 bool NodeIsUniqueLoadOrStore =940 mayInstNodeLoadOrStore(N, CGP) && NumNodesThatLoadOrStore == 1;941 NodeHasMemRefs =942 NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) ||943 NumNodesThatLoadOrStore != 1));944 }945 946 // Determine whether we need to attach a chain to this node.947 bool NodeHasChain = false;948 if (Pattern.getSrcPattern().TreeHasProperty(SDNPHasChain, CGP)) {949 // For some instructions, we were able to infer from the pattern whether950 // they should have a chain. Otherwise, attach the chain to the root.951 //952 // FIXME2: This is extremely dubious for several reasons, not the least of953 // which it gives special status to instructions with patterns that Pat<>954 // nodes can't duplicate.955 if (II.hasChain_Inferred)956 NodeHasChain = II.hasChain;957 else958 NodeHasChain = isRoot;959 // Instructions which load and store from memory should have a chain,960 // regardless of whether they happen to have a pattern saying so.961 if (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad ||962 II.hasSideEffects)963 NodeHasChain = true;964 }965 966 assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) &&967 "Node has no result");968 969 AddMatcher(new EmitNodeMatcher(II, ResultVTs, InstOps, NodeHasChain,970 TreeHasInGlue, TreeHasOutGlue, NodeHasMemRefs,971 NumFixedArityOperands, NextRecordedOperandNo));972 973 // The non-chain and non-glue results of the newly emitted node get recorded.974 for (MVT ResultVT : ResultVTs) {975 if (ResultVT == MVT::Other || ResultVT == MVT::Glue)976 break;977 OutputOps.push_back(NextRecordedOperandNo++);978 }979}980 981void MatcherGen::EmitResultSDNodeXFormAsOperand(982 const TreePatternNode &N, SmallVectorImpl<unsigned> &ResultOps) {983 assert(N.getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?");984 985 // Emit the operand.986 SmallVector<unsigned, 8> InputOps;987 988 // FIXME2: Could easily generalize this to support multiple inputs and outputs989 // to the SDNodeXForm. For now we just support one input and one output like990 // the old instruction selector.991 assert(N.getNumChildren() == 1);992 EmitResultOperand(N.getChild(0), InputOps);993 994 // The input currently must have produced exactly one result.995 assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm");996 997 AddMatcher(new EmitNodeXFormMatcher(InputOps[0], N.getOperator(),998 NextRecordedOperandNo));999 ResultOps.push_back(NextRecordedOperandNo++);1000}1001 1002void MatcherGen::EmitResultOperand(const TreePatternNode &N,1003 SmallVectorImpl<unsigned> &ResultOps) {1004 // This is something selected from the pattern we matched.1005 if (!N.getName().empty())1006 return EmitResultOfNamedOperand(N, ResultOps);1007 1008 if (N.isLeaf())1009 return EmitResultLeafAsOperand(N, ResultOps);1010 1011 const Record *OpRec = N.getOperator();1012 if (OpRec->isSubClassOf("Instruction"))1013 return EmitResultInstructionAsOperand(N, ResultOps);1014 if (OpRec->isSubClassOf("SDNodeXForm"))1015 return EmitResultSDNodeXFormAsOperand(N, ResultOps);1016 errs() << "Unknown result node to emit code for: " << N << '\n';1017 PrintFatalError("Unknown node in result pattern!");1018}1019 1020void MatcherGen::EmitResultCode() {1021 // Patterns that match nodes with (potentially multiple) chain inputs have to1022 // merge them together into a token factor. This informs the generated code1023 // what all the chained nodes are.1024 if (!MatchedChainNodes.empty())1025 AddMatcher(new EmitMergeInputChainsMatcher(MatchedChainNodes));1026 1027 // Codegen the root of the result pattern, capturing the resulting values.1028 SmallVector<unsigned, 8> Ops;1029 EmitResultOperand(Pattern.getDstPattern(), Ops);1030 1031 // At this point, we have however many values the result pattern produces.1032 // However, the input pattern might not need all of these. If there are1033 // excess values at the end (such as implicit defs of condition codes etc)1034 // just lop them off. This doesn't need to worry about glue or chains, just1035 // explicit results.1036 //1037 unsigned NumSrcResults = Pattern.getSrcPattern().getNumTypes();1038 1039 // If the pattern also has implicit results, count them as well.1040 if (!Pattern.getDstRegs().empty()) {1041 // If the root came from an implicit def in the instruction handling stuff,1042 // don't re-add it.1043 const Record *HandledReg = nullptr;1044 const TreePatternNode &DstPat = Pattern.getDstPattern();1045 if (!DstPat.isLeaf() && DstPat.getOperator()->isSubClassOf("Instruction")) {1046 const CodeGenTarget &CGT = CGP.getTargetInfo();1047 const CodeGenInstruction &II = CGT.getInstruction(DstPat.getOperator());1048 1049 if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other)1050 HandledReg = II.ImplicitDefs[0];1051 }1052 1053 for (const Record *Reg : Pattern.getDstRegs()) {1054 if (!Reg->isSubClassOf("Register") || Reg == HandledReg)1055 continue;1056 ++NumSrcResults;1057 }1058 }1059 1060 SmallVector<unsigned, 8> Results(Ops);1061 1062 // Apply result permutation.1063 for (unsigned ResNo = 0; ResNo < Pattern.getDstPattern().getNumResults();1064 ++ResNo) {1065 Results[ResNo] = Ops[Pattern.getDstPattern().getResultIndex(ResNo)];1066 }1067 1068 Results.resize(NumSrcResults);1069 AddMatcher(new CompleteMatchMatcher(Results, Pattern));1070}1071 1072/// ConvertPatternToMatcher - Create the matcher for the specified pattern with1073/// the specified variant. If the variant number is invalid, this returns null.1074Matcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern,1075 unsigned Variant,1076 const CodeGenDAGPatterns &CGP) {1077 MatcherGen Gen(Pattern, CGP);1078 1079 // Generate the code for the matcher.1080 if (Gen.EmitMatcherCode(Variant))1081 return nullptr;1082 1083 // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence.1084 // FIXME2: Split result code out to another table, and make the matcher end1085 // with an "Emit <index>" command. This allows result generation stuff to be1086 // shared and factored?1087 1088 // If the match succeeds, then we generate Pattern.1089 Gen.EmitResultCode();1090 1091 // Unconditional match.1092 return Gen.GetMatcher();1093}1094