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