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