CodeGenDAGPatterns.h revision 49de98214b82fefeb8f16efbf8cdd8813a85469b
1//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file declares the CodeGenDAGPatterns class, which is used to read and 11// represent the patterns present in a .td file for instructions. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef CODEGEN_DAGPATTERNS_H 16#define CODEGEN_DAGPATTERNS_H 17 18#include <set> 19#include <algorithm> 20#include <vector> 21 22#include "CodeGenTarget.h" 23#include "CodeGenIntrinsics.h" 24 25namespace llvm { 26 class Record; 27 struct Init; 28 class ListInit; 29 class DagInit; 30 class SDNodeInfo; 31 class TreePattern; 32 class TreePatternNode; 33 class CodeGenDAGPatterns; 34 class ComplexPattern; 35 36/// EMVT::DAGISelGenValueType - These are some extended forms of 37/// MVT::SimpleValueType that we use as lattice values during type inference. 38namespace EMVT { 39 enum DAGISelGenValueType { 40 isFP = MVT::LAST_VALUETYPE, 41 isInt, 42 isUnknown 43 }; 44 45 /// isExtIntegerVT - Return true if the specified extended value type vector 46 /// contains isInt or an integer value type. 47 bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs); 48 49 /// isExtFloatingPointVT - Return true if the specified extended value type 50 /// vector contains isFP or a FP value type. 51 bool isExtFloatingPointInVTs(const std::vector<unsigned char> &EVTs); 52} 53 54/// Set type used to track multiply used variables in patterns 55typedef std::set<std::string> MultipleUseVarSet; 56 57/// SDTypeConstraint - This is a discriminated union of constraints, 58/// corresponding to the SDTypeConstraint tablegen class in Target.td. 59struct SDTypeConstraint { 60 SDTypeConstraint(Record *R); 61 62 unsigned OperandNo; // The operand # this constraint applies to. 63 enum { 64 SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisSameAs, 65 SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisIntVectorOfSameSize, 66 SDTCisEltOfVec 67 } ConstraintType; 68 69 union { // The discriminated union. 70 struct { 71 unsigned char VT; 72 } SDTCisVT_Info; 73 struct { 74 unsigned OtherOperandNum; 75 } SDTCisSameAs_Info; 76 struct { 77 unsigned OtherOperandNum; 78 } SDTCisVTSmallerThanOp_Info; 79 struct { 80 unsigned BigOperandNum; 81 } SDTCisOpSmallerThanOp_Info; 82 struct { 83 unsigned OtherOperandNum; 84 } SDTCisIntVectorOfSameSize_Info; 85 struct { 86 unsigned OtherOperandNum; 87 } SDTCisEltOfVec_Info; 88 } x; 89 90 /// ApplyTypeConstraint - Given a node in a pattern, apply this type 91 /// constraint to the nodes operands. This returns true if it makes a 92 /// change, false otherwise. If a type contradiction is found, throw an 93 /// exception. 94 bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, 95 TreePattern &TP) const; 96 97 /// getOperandNum - Return the node corresponding to operand #OpNo in tree 98 /// N, which has NumResults results. 99 TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, 100 unsigned NumResults) const; 101}; 102 103/// SDNodeInfo - One of these records is created for each SDNode instance in 104/// the target .td file. This represents the various dag nodes we will be 105/// processing. 106class SDNodeInfo { 107 Record *Def; 108 std::string EnumName; 109 std::string SDClassName; 110 unsigned Properties; 111 unsigned NumResults; 112 int NumOperands; 113 std::vector<SDTypeConstraint> TypeConstraints; 114public: 115 SDNodeInfo(Record *R); // Parse the specified record. 116 117 unsigned getNumResults() const { return NumResults; } 118 int getNumOperands() const { return NumOperands; } 119 Record *getRecord() const { return Def; } 120 const std::string &getEnumName() const { return EnumName; } 121 const std::string &getSDClassName() const { return SDClassName; } 122 123 const std::vector<SDTypeConstraint> &getTypeConstraints() const { 124 return TypeConstraints; 125 } 126 127 /// hasProperty - Return true if this node has the specified property. 128 /// 129 bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } 130 131 /// ApplyTypeConstraints - Given a node in a pattern, apply the type 132 /// constraints for this node to the operands of the node. This returns 133 /// true if it makes a change, false otherwise. If a type contradiction is 134 /// found, throw an exception. 135 bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const { 136 bool MadeChange = false; 137 for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) 138 MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP); 139 return MadeChange; 140 } 141}; 142 143/// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped 144/// patterns), and as such should be ref counted. We currently just leak all 145/// TreePatternNode objects! 146class TreePatternNode { 147 /// The inferred type for this node, or EMVT::isUnknown if it hasn't 148 /// been determined yet. 149 std::vector<unsigned char> Types; 150 151 /// Operator - The Record for the operator if this is an interior node (not 152 /// a leaf). 153 Record *Operator; 154 155 /// Val - The init value (e.g. the "GPRC" record, or "7") for a leaf. 156 /// 157 Init *Val; 158 159 /// Name - The name given to this node with the :$foo notation. 160 /// 161 std::string Name; 162 163 /// PredicateFns - The predicate functions to execute on this node to check 164 /// for a match. If this list is empty, no predicate is involved. 165 std::vector<std::string> PredicateFns; 166 167 /// TransformFn - The transformation function to execute on this node before 168 /// it can be substituted into the resulting instruction on a pattern match. 169 Record *TransformFn; 170 171 std::vector<TreePatternNode*> Children; 172public: 173 TreePatternNode(Record *Op, const std::vector<TreePatternNode*> &Ch) 174 : Types(), Operator(Op), Val(0), TransformFn(0), 175 Children(Ch) { Types.push_back(EMVT::isUnknown); } 176 TreePatternNode(Init *val) // leaf ctor 177 : Types(), Operator(0), Val(val), TransformFn(0) { 178 Types.push_back(EMVT::isUnknown); 179 } 180 ~TreePatternNode(); 181 182 const std::string &getName() const { return Name; } 183 void setName(const std::string &N) { Name = N; } 184 185 bool isLeaf() const { return Val != 0; } 186 bool hasTypeSet() const { 187 return (Types[0] < MVT::LAST_VALUETYPE) || (Types[0] == MVT::iPTR) || 188 (Types[0] == MVT::iPTRAny); 189 } 190 bool isTypeCompletelyUnknown() const { 191 return Types[0] == EMVT::isUnknown; 192 } 193 bool isTypeDynamicallyResolved() const { 194 return (Types[0] == MVT::iPTR) || (Types[0] == MVT::iPTRAny); 195 } 196 MVT::SimpleValueType getTypeNum(unsigned Num) const { 197 assert(hasTypeSet() && "Doesn't have a type yet!"); 198 assert(Types.size() > Num && "Type num out of range!"); 199 return (MVT::SimpleValueType)Types[Num]; 200 } 201 unsigned char getExtTypeNum(unsigned Num) const { 202 assert(Types.size() > Num && "Extended type num out of range!"); 203 return Types[Num]; 204 } 205 const std::vector<unsigned char> &getExtTypes() const { return Types; } 206 void setTypes(const std::vector<unsigned char> &T) { Types = T; } 207 void removeTypes() { Types = std::vector<unsigned char>(1, EMVT::isUnknown); } 208 209 Init *getLeafValue() const { assert(isLeaf()); return Val; } 210 Record *getOperator() const { assert(!isLeaf()); return Operator; } 211 212 unsigned getNumChildren() const { return Children.size(); } 213 TreePatternNode *getChild(unsigned N) const { return Children[N]; } 214 void setChild(unsigned i, TreePatternNode *N) { 215 Children[i] = N; 216 } 217 218 const std::vector<std::string> &getPredicateFns() const { return PredicateFns; } 219 void clearPredicateFns() { PredicateFns.clear(); } 220 void setPredicateFns(const std::vector<std::string> &Fns) { 221 assert(PredicateFns.empty() && "Overwriting non-empty predicate list!"); 222 PredicateFns = Fns; 223 } 224 void addPredicateFn(const std::string &Fn) { 225 assert(!Fn.empty() && "Empty predicate string!"); 226 if (std::find(PredicateFns.begin(), PredicateFns.end(), Fn) == 227 PredicateFns.end()) 228 PredicateFns.push_back(Fn); 229 } 230 231 Record *getTransformFn() const { return TransformFn; } 232 void setTransformFn(Record *Fn) { TransformFn = Fn; } 233 234 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 235 /// CodeGenIntrinsic information for it, otherwise return a null pointer. 236 const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const; 237 238 /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is 239 /// marked isCommutative. 240 bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const; 241 242 void print(std::ostream &OS) const; 243 void dump() const; 244 245public: // Higher level manipulation routines. 246 247 /// clone - Return a new copy of this tree. 248 /// 249 TreePatternNode *clone() const; 250 251 /// isIsomorphicTo - Return true if this node is recursively isomorphic to 252 /// the specified node. For this comparison, all of the state of the node 253 /// is considered, except for the assigned name. Nodes with differing names 254 /// that are otherwise identical are considered isomorphic. 255 bool isIsomorphicTo(const TreePatternNode *N, 256 const MultipleUseVarSet &DepVars) const; 257 258 /// SubstituteFormalArguments - Replace the formal arguments in this tree 259 /// with actual values specified by ArgMap. 260 void SubstituteFormalArguments(std::map<std::string, 261 TreePatternNode*> &ArgMap); 262 263 /// InlinePatternFragments - If this pattern refers to any pattern 264 /// fragments, inline them into place, giving us a pattern without any 265 /// PatFrag references. 266 TreePatternNode *InlinePatternFragments(TreePattern &TP); 267 268 /// ApplyTypeConstraints - Apply all of the type constraints relevant to 269 /// this node and its children in the tree. This returns true if it makes a 270 /// change, false otherwise. If a type contradiction is found, throw an 271 /// exception. 272 bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters); 273 274 /// UpdateNodeType - Set the node type of N to VT if VT contains 275 /// information. If N already contains a conflicting type, then throw an 276 /// exception. This returns true if any information was updated. 277 /// 278 bool UpdateNodeType(const std::vector<unsigned char> &ExtVTs, 279 TreePattern &TP); 280 bool UpdateNodeType(unsigned char ExtVT, TreePattern &TP) { 281 std::vector<unsigned char> ExtVTs(1, ExtVT); 282 return UpdateNodeType(ExtVTs, TP); 283 } 284 285 /// ContainsUnresolvedType - Return true if this tree contains any 286 /// unresolved types. 287 bool ContainsUnresolvedType() const { 288 if (!hasTypeSet() && !isTypeDynamicallyResolved()) return true; 289 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 290 if (getChild(i)->ContainsUnresolvedType()) return true; 291 return false; 292 } 293 294 /// canPatternMatch - If it is impossible for this pattern to match on this 295 /// target, fill in Reason and return false. Otherwise, return true. 296 bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP); 297}; 298 299 300/// TreePattern - Represent a pattern, used for instructions, pattern 301/// fragments, etc. 302/// 303class TreePattern { 304 /// Trees - The list of pattern trees which corresponds to this pattern. 305 /// Note that PatFrag's only have a single tree. 306 /// 307 std::vector<TreePatternNode*> Trees; 308 309 /// TheRecord - The actual TableGen record corresponding to this pattern. 310 /// 311 Record *TheRecord; 312 313 /// Args - This is a list of all of the arguments to this pattern (for 314 /// PatFrag patterns), which are the 'node' markers in this pattern. 315 std::vector<std::string> Args; 316 317 /// CDP - the top-level object coordinating this madness. 318 /// 319 CodeGenDAGPatterns &CDP; 320 321 /// isInputPattern - True if this is an input pattern, something to match. 322 /// False if this is an output pattern, something to emit. 323 bool isInputPattern; 324public: 325 326 /// TreePattern constructor - Parse the specified DagInits into the 327 /// current record. 328 TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 329 CodeGenDAGPatterns &ise); 330 TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 331 CodeGenDAGPatterns &ise); 332 TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 333 CodeGenDAGPatterns &ise); 334 335 /// getTrees - Return the tree patterns which corresponds to this pattern. 336 /// 337 const std::vector<TreePatternNode*> &getTrees() const { return Trees; } 338 unsigned getNumTrees() const { return Trees.size(); } 339 TreePatternNode *getTree(unsigned i) const { return Trees[i]; } 340 TreePatternNode *getOnlyTree() const { 341 assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); 342 return Trees[0]; 343 } 344 345 /// getRecord - Return the actual TableGen record corresponding to this 346 /// pattern. 347 /// 348 Record *getRecord() const { return TheRecord; } 349 350 unsigned getNumArgs() const { return Args.size(); } 351 const std::string &getArgName(unsigned i) const { 352 assert(i < Args.size() && "Argument reference out of range!"); 353 return Args[i]; 354 } 355 std::vector<std::string> &getArgList() { return Args; } 356 357 CodeGenDAGPatterns &getDAGPatterns() const { return CDP; } 358 359 /// InlinePatternFragments - If this pattern refers to any pattern 360 /// fragments, inline them into place, giving us a pattern without any 361 /// PatFrag references. 362 void InlinePatternFragments() { 363 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 364 Trees[i] = Trees[i]->InlinePatternFragments(*this); 365 } 366 367 /// InferAllTypes - Infer/propagate as many types throughout the expression 368 /// patterns as possible. Return true if all types are infered, false 369 /// otherwise. Throw an exception if a type contradiction is found. 370 bool InferAllTypes(); 371 372 /// error - Throw an exception, prefixing it with information about this 373 /// pattern. 374 void error(const std::string &Msg) const; 375 376 void print(std::ostream &OS) const; 377 void dump() const; 378 379private: 380 TreePatternNode *ParseTreePattern(DagInit *DI); 381}; 382 383/// DAGDefaultOperand - One of these is created for each PredicateOperand 384/// or OptionalDefOperand that has a set ExecuteAlways / DefaultOps field. 385struct DAGDefaultOperand { 386 std::vector<TreePatternNode*> DefaultOps; 387}; 388 389class DAGInstruction { 390 TreePattern *Pattern; 391 std::vector<Record*> Results; 392 std::vector<Record*> Operands; 393 std::vector<Record*> ImpResults; 394 std::vector<Record*> ImpOperands; 395 TreePatternNode *ResultPattern; 396public: 397 DAGInstruction(TreePattern *TP, 398 const std::vector<Record*> &results, 399 const std::vector<Record*> &operands, 400 const std::vector<Record*> &impresults, 401 const std::vector<Record*> &impoperands) 402 : Pattern(TP), Results(results), Operands(operands), 403 ImpResults(impresults), ImpOperands(impoperands), 404 ResultPattern(0) {} 405 406 const TreePattern *getPattern() const { return Pattern; } 407 unsigned getNumResults() const { return Results.size(); } 408 unsigned getNumOperands() const { return Operands.size(); } 409 unsigned getNumImpResults() const { return ImpResults.size(); } 410 unsigned getNumImpOperands() const { return ImpOperands.size(); } 411 const std::vector<Record*>& getImpResults() const { return ImpResults; } 412 413 void setResultPattern(TreePatternNode *R) { ResultPattern = R; } 414 415 Record *getResult(unsigned RN) const { 416 assert(RN < Results.size()); 417 return Results[RN]; 418 } 419 420 Record *getOperand(unsigned ON) const { 421 assert(ON < Operands.size()); 422 return Operands[ON]; 423 } 424 425 Record *getImpResult(unsigned RN) const { 426 assert(RN < ImpResults.size()); 427 return ImpResults[RN]; 428 } 429 430 Record *getImpOperand(unsigned ON) const { 431 assert(ON < ImpOperands.size()); 432 return ImpOperands[ON]; 433 } 434 435 TreePatternNode *getResultPattern() const { return ResultPattern; } 436}; 437 438/// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns 439/// processed to produce isel. 440struct PatternToMatch { 441 PatternToMatch(ListInit *preds, 442 TreePatternNode *src, TreePatternNode *dst, 443 const std::vector<Record*> &dstregs, 444 unsigned complexity): 445 Predicates(preds), SrcPattern(src), DstPattern(dst), Dstregs(dstregs), 446 AddedComplexity(complexity) {}; 447 448 ListInit *Predicates; // Top level predicate conditions to match. 449 TreePatternNode *SrcPattern; // Source pattern to match. 450 TreePatternNode *DstPattern; // Resulting pattern. 451 std::vector<Record*> Dstregs; // Physical register defs being matched. 452 unsigned AddedComplexity; // Add to matching pattern complexity. 453 454 ListInit *getPredicates() const { return Predicates; } 455 TreePatternNode *getSrcPattern() const { return SrcPattern; } 456 TreePatternNode *getDstPattern() const { return DstPattern; } 457 const std::vector<Record*> &getDstRegs() const { return Dstregs; } 458 unsigned getAddedComplexity() const { return AddedComplexity; } 459 460 std::string getPredicateCheck() const; 461}; 462 463 464class CodeGenDAGPatterns { 465 RecordKeeper &Records; 466 CodeGenTarget Target; 467 std::vector<CodeGenIntrinsic> Intrinsics; 468 std::vector<CodeGenIntrinsic> TgtIntrinsics; 469 470 std::map<Record*, SDNodeInfo> SDNodes; 471 std::map<Record*, std::pair<Record*, std::string> > SDNodeXForms; 472 std::map<Record*, ComplexPattern> ComplexPatterns; 473 std::map<Record*, TreePattern*> PatternFragments; 474 std::map<Record*, DAGDefaultOperand> DefaultOperands; 475 std::map<Record*, DAGInstruction> Instructions; 476 477 // Specific SDNode definitions: 478 Record *intrinsic_void_sdnode; 479 Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode; 480 481 /// PatternsToMatch - All of the things we are matching on the DAG. The first 482 /// value is the pattern to match, the second pattern is the result to 483 /// emit. 484 std::vector<PatternToMatch> PatternsToMatch; 485public: 486 CodeGenDAGPatterns(RecordKeeper &R); 487 ~CodeGenDAGPatterns(); 488 489 CodeGenTarget &getTargetInfo() { return Target; } 490 const CodeGenTarget &getTargetInfo() const { return Target; } 491 492 Record *getSDNodeNamed(const std::string &Name) const; 493 494 const SDNodeInfo &getSDNodeInfo(Record *R) const { 495 assert(SDNodes.count(R) && "Unknown node!"); 496 return SDNodes.find(R)->second; 497 } 498 499 // Node transformation lookups. 500 typedef std::pair<Record*, std::string> NodeXForm; 501 const NodeXForm &getSDNodeTransform(Record *R) const { 502 assert(SDNodeXForms.count(R) && "Invalid transform!"); 503 return SDNodeXForms.find(R)->second; 504 } 505 506 typedef std::map<Record*, NodeXForm>::const_iterator nx_iterator; 507 nx_iterator nx_begin() const { return SDNodeXForms.begin(); } 508 nx_iterator nx_end() const { return SDNodeXForms.end(); } 509 510 511 const ComplexPattern &getComplexPattern(Record *R) const { 512 assert(ComplexPatterns.count(R) && "Unknown addressing mode!"); 513 return ComplexPatterns.find(R)->second; 514 } 515 516 const CodeGenIntrinsic &getIntrinsic(Record *R) const { 517 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 518 if (Intrinsics[i].TheDef == R) return Intrinsics[i]; 519 for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 520 if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i]; 521 assert(0 && "Unknown intrinsic!"); 522 abort(); 523 } 524 525 const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { 526 if (IID-1 < Intrinsics.size()) 527 return Intrinsics[IID-1]; 528 if (IID-Intrinsics.size()-1 < TgtIntrinsics.size()) 529 return TgtIntrinsics[IID-Intrinsics.size()-1]; 530 assert(0 && "Bad intrinsic ID!"); 531 } 532 533 unsigned getIntrinsicID(Record *R) const { 534 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 535 if (Intrinsics[i].TheDef == R) return i; 536 for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 537 if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size(); 538 assert(0 && "Unknown intrinsic!"); 539 abort(); 540 } 541 542 const DAGDefaultOperand &getDefaultOperand(Record *R) { 543 assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!"); 544 return DefaultOperands.find(R)->second; 545 } 546 547 // Pattern Fragment information. 548 TreePattern *getPatternFragment(Record *R) const { 549 assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); 550 return PatternFragments.find(R)->second; 551 } 552 typedef std::map<Record*, TreePattern*>::const_iterator pf_iterator; 553 pf_iterator pf_begin() const { return PatternFragments.begin(); } 554 pf_iterator pf_end() const { return PatternFragments.end(); } 555 556 // Patterns to match information. 557 typedef std::vector<PatternToMatch>::const_iterator ptm_iterator; 558 ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } 559 ptm_iterator ptm_end() const { return PatternsToMatch.end(); } 560 561 562 563 const DAGInstruction &getInstruction(Record *R) const { 564 assert(Instructions.count(R) && "Unknown instruction!"); 565 return Instructions.find(R)->second; 566 } 567 568 Record *get_intrinsic_void_sdnode() const { 569 return intrinsic_void_sdnode; 570 } 571 Record *get_intrinsic_w_chain_sdnode() const { 572 return intrinsic_w_chain_sdnode; 573 } 574 Record *get_intrinsic_wo_chain_sdnode() const { 575 return intrinsic_wo_chain_sdnode; 576 } 577 578private: 579 void ParseNodeInfo(); 580 void ParseNodeTransforms(); 581 void ParseComplexPatterns(); 582 void ParsePatternFragments(); 583 void ParseDefaultOperands(); 584 void ParseInstructions(); 585 void ParsePatterns(); 586 void InferInstructionFlags(); 587 void GenerateVariants(); 588 589 void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 590 std::map<std::string, 591 TreePatternNode*> &InstInputs, 592 std::map<std::string, 593 TreePatternNode*> &InstResults, 594 std::vector<Record*> &InstImpInputs, 595 std::vector<Record*> &InstImpResults); 596}; 597} // end namespace llvm 598 599#endif 600