CodeGenDAGPatterns.h revision 443e3f9dd61b8d0974bb13d484195ce1a9b7536c
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 208 const std::string &getPredicateFn() const { return PredicateFn; } 209 void setPredicateFn(const std::string &Fn) { PredicateFn = Fn; } 210 211 Record *getTransformFn() const { return TransformFn; } 212 void setTransformFn(Record *Fn) { TransformFn = Fn; } 213 214 void print(std::ostream &OS) const; 215 void dump() const; 216 217public: // Higher level manipulation routines. 218 219 /// clone - Return a new copy of this tree. 220 /// 221 TreePatternNode *clone() const; 222 223 /// isIsomorphicTo - Return true if this node is recursively isomorphic to 224 /// the specified node. For this comparison, all of the state of the node 225 /// is considered, except for the assigned name. Nodes with differing names 226 /// that are otherwise identical are considered isomorphic. 227 bool isIsomorphicTo(const TreePatternNode *N) const; 228 229 /// SubstituteFormalArguments - Replace the formal arguments in this tree 230 /// with actual values specified by ArgMap. 231 void SubstituteFormalArguments(std::map<std::string, 232 TreePatternNode*> &ArgMap); 233 234 /// InlinePatternFragments - If this pattern refers to any pattern 235 /// fragments, inline them into place, giving us a pattern without any 236 /// PatFrag references. 237 TreePatternNode *InlinePatternFragments(TreePattern &TP); 238 239 /// ApplyTypeConstraints - Apply all of the type constraints relevent to 240 /// this node and its children in the tree. This returns true if it makes a 241 /// change, false otherwise. If a type contradiction is found, throw an 242 /// exception. 243 bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters); 244 245 /// UpdateNodeType - Set the node type of N to VT if VT contains 246 /// information. If N already contains a conflicting type, then throw an 247 /// exception. This returns true if any information was updated. 248 /// 249 bool UpdateNodeType(const std::vector<unsigned char> &ExtVTs, 250 TreePattern &TP); 251 bool UpdateNodeType(unsigned char ExtVT, TreePattern &TP) { 252 std::vector<unsigned char> ExtVTs(1, ExtVT); 253 return UpdateNodeType(ExtVTs, TP); 254 } 255 256 /// ContainsUnresolvedType - Return true if this tree contains any 257 /// unresolved types. 258 bool ContainsUnresolvedType() const { 259 if (!hasTypeSet() && !isTypeDynamicallyResolved()) return true; 260 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 261 if (getChild(i)->ContainsUnresolvedType()) return true; 262 return false; 263 } 264 265 /// canPatternMatch - If it is impossible for this pattern to match on this 266 /// target, fill in Reason and return false. Otherwise, return true. 267 bool canPatternMatch(std::string &Reason, CodegenDAGPatterns &CDP); 268}; 269 270 271/// TreePattern - Represent a pattern, used for instructions, pattern 272/// fragments, etc. 273/// 274class TreePattern { 275 /// Trees - The list of pattern trees which corresponds to this pattern. 276 /// Note that PatFrag's only have a single tree. 277 /// 278 std::vector<TreePatternNode*> Trees; 279 280 /// TheRecord - The actual TableGen record corresponding to this pattern. 281 /// 282 Record *TheRecord; 283 284 /// Args - This is a list of all of the arguments to this pattern (for 285 /// PatFrag patterns), which are the 'node' markers in this pattern. 286 std::vector<std::string> Args; 287 288 /// CDP - the top-level object coordinating this madness. 289 /// 290 CodegenDAGPatterns &CDP; 291 292 /// isInputPattern - True if this is an input pattern, something to match. 293 /// False if this is an output pattern, something to emit. 294 bool isInputPattern; 295public: 296 297 /// TreePattern constructor - Parse the specified DagInits into the 298 /// current record. 299 TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 300 CodegenDAGPatterns &ise); 301 TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 302 CodegenDAGPatterns &ise); 303 TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 304 CodegenDAGPatterns &ise); 305 306 /// getTrees - Return the tree patterns which corresponds to this pattern. 307 /// 308 const std::vector<TreePatternNode*> &getTrees() const { return Trees; } 309 unsigned getNumTrees() const { return Trees.size(); } 310 TreePatternNode *getTree(unsigned i) const { return Trees[i]; } 311 TreePatternNode *getOnlyTree() const { 312 assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); 313 return Trees[0]; 314 } 315 316 /// getRecord - Return the actual TableGen record corresponding to this 317 /// pattern. 318 /// 319 Record *getRecord() const { return TheRecord; } 320 321 unsigned getNumArgs() const { return Args.size(); } 322 const std::string &getArgName(unsigned i) const { 323 assert(i < Args.size() && "Argument reference out of range!"); 324 return Args[i]; 325 } 326 std::vector<std::string> &getArgList() { return Args; } 327 328 CodegenDAGPatterns &getDAGPatterns() const { return CDP; } 329 330 /// InlinePatternFragments - If this pattern refers to any pattern 331 /// fragments, inline them into place, giving us a pattern without any 332 /// PatFrag references. 333 void InlinePatternFragments() { 334 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 335 Trees[i] = Trees[i]->InlinePatternFragments(*this); 336 } 337 338 /// InferAllTypes - Infer/propagate as many types throughout the expression 339 /// patterns as possible. Return true if all types are infered, false 340 /// otherwise. Throw an exception if a type contradiction is found. 341 bool InferAllTypes(); 342 343 /// error - Throw an exception, prefixing it with information about this 344 /// pattern. 345 void error(const std::string &Msg) const; 346 347 void print(std::ostream &OS) const; 348 void dump() const; 349 350private: 351 TreePatternNode *ParseTreePattern(DagInit *DI); 352}; 353 354/// DAGDefaultOperand - One of these is created for each PredicateOperand 355/// or OptionalDefOperand that has a set ExecuteAlways / DefaultOps field. 356struct DAGDefaultOperand { 357 std::vector<TreePatternNode*> DefaultOps; 358}; 359 360class DAGInstruction { 361 TreePattern *Pattern; 362 std::vector<Record*> Results; 363 std::vector<Record*> Operands; 364 std::vector<Record*> ImpResults; 365 std::vector<Record*> ImpOperands; 366 TreePatternNode *ResultPattern; 367public: 368 DAGInstruction(TreePattern *TP, 369 const std::vector<Record*> &results, 370 const std::vector<Record*> &operands, 371 const std::vector<Record*> &impresults, 372 const std::vector<Record*> &impoperands) 373 : Pattern(TP), Results(results), Operands(operands), 374 ImpResults(impresults), ImpOperands(impoperands), 375 ResultPattern(0) {} 376 377 TreePattern *getPattern() const { return Pattern; } 378 unsigned getNumResults() const { return Results.size(); } 379 unsigned getNumOperands() const { return Operands.size(); } 380 unsigned getNumImpResults() const { return ImpResults.size(); } 381 unsigned getNumImpOperands() const { return ImpOperands.size(); } 382 const std::vector<Record*>& getImpResults() const { return ImpResults; } 383 384 void setResultPattern(TreePatternNode *R) { ResultPattern = R; } 385 386 Record *getResult(unsigned RN) const { 387 assert(RN < Results.size()); 388 return Results[RN]; 389 } 390 391 Record *getOperand(unsigned ON) const { 392 assert(ON < Operands.size()); 393 return Operands[ON]; 394 } 395 396 Record *getImpResult(unsigned RN) const { 397 assert(RN < ImpResults.size()); 398 return ImpResults[RN]; 399 } 400 401 Record *getImpOperand(unsigned ON) const { 402 assert(ON < ImpOperands.size()); 403 return ImpOperands[ON]; 404 } 405 406 TreePatternNode *getResultPattern() const { return ResultPattern; } 407}; 408 409/// PatternToMatch - Used by CodegenDAGPatterns to keep tab of patterns 410/// processed to produce isel. 411struct PatternToMatch { 412 PatternToMatch(ListInit *preds, 413 TreePatternNode *src, TreePatternNode *dst, 414 const std::vector<Record*> &dstregs, 415 unsigned complexity): 416 Predicates(preds), SrcPattern(src), DstPattern(dst), Dstregs(dstregs), 417 AddedComplexity(complexity) {}; 418 419 ListInit *Predicates; // Top level predicate conditions to match. 420 TreePatternNode *SrcPattern; // Source pattern to match. 421 TreePatternNode *DstPattern; // Resulting pattern. 422 std::vector<Record*> Dstregs; // Physical register defs being matched. 423 unsigned AddedComplexity; // Add to matching pattern complexity. 424 425 ListInit *getPredicates() const { return Predicates; } 426 TreePatternNode *getSrcPattern() const { return SrcPattern; } 427 TreePatternNode *getDstPattern() const { return DstPattern; } 428 const std::vector<Record*> &getDstRegs() const { return Dstregs; } 429 unsigned getAddedComplexity() const { return AddedComplexity; } 430}; 431 432 433class CodegenDAGPatterns { 434 RecordKeeper &Records; 435 CodeGenTarget Target; 436 std::vector<CodeGenIntrinsic> Intrinsics; 437 438 std::map<Record*, SDNodeInfo> SDNodes; 439 std::map<Record*, std::pair<Record*, std::string> > SDNodeXForms; 440 std::map<Record*, ComplexPattern> ComplexPatterns; 441 std::map<Record*, TreePattern*> PatternFragments; 442 std::map<Record*, DAGDefaultOperand> DefaultOperands; 443 std::map<Record*, DAGInstruction> Instructions; 444 445 // Specific SDNode definitions: 446 Record *intrinsic_void_sdnode; 447 Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode; 448 449 /// PatternsToMatch - All of the things we are matching on the DAG. The first 450 /// value is the pattern to match, the second pattern is the result to 451 /// emit. 452 std::vector<PatternToMatch> PatternsToMatch; 453public: 454 CodegenDAGPatterns(RecordKeeper &R); 455 ~CodegenDAGPatterns(); 456 457 const CodeGenTarget &getTargetInfo() const { return Target; } 458 459 Record *getSDNodeNamed(const std::string &Name) const; 460 461 const SDNodeInfo &getSDNodeInfo(Record *R) const { 462 assert(SDNodes.count(R) && "Unknown node!"); 463 return SDNodes.find(R)->second; 464 } 465 466 // Node transformation lookups. 467 typedef std::pair<Record*, std::string> NodeXForm; 468 const NodeXForm &getSDNodeTransform(Record *R) const { 469 assert(SDNodeXForms.count(R) && "Invalid transform!"); 470 return SDNodeXForms.find(R)->second; 471 } 472 473 typedef std::map<Record*, NodeXForm>::const_iterator nx_iterator; 474 nx_iterator nx_begin() const { return SDNodeXForms.begin(); } 475 nx_iterator nx_end() const { return SDNodeXForms.end(); } 476 477 478 const ComplexPattern &getComplexPattern(Record *R) const { 479 assert(ComplexPatterns.count(R) && "Unknown addressing mode!"); 480 return ComplexPatterns.find(R)->second; 481 } 482 483 const CodeGenIntrinsic &getIntrinsic(Record *R) const { 484 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 485 if (Intrinsics[i].TheDef == R) return Intrinsics[i]; 486 assert(0 && "Unknown intrinsic!"); 487 abort(); 488 } 489 490 const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { 491 assert(IID-1 < Intrinsics.size() && "Bad intrinsic ID!"); 492 return Intrinsics[IID-1]; 493 } 494 495 unsigned getIntrinsicID(Record *R) const { 496 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 497 if (Intrinsics[i].TheDef == R) return i; 498 assert(0 && "Unknown intrinsic!"); 499 abort(); 500 } 501 502 const DAGDefaultOperand &getDefaultOperand(Record *R) { 503 assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!"); 504 return DefaultOperands.find(R)->second; 505 } 506 507 // Pattern Fragment information. 508 TreePattern *getPatternFragment(Record *R) const { 509 assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); 510 return PatternFragments.find(R)->second; 511 } 512 typedef std::map<Record*, TreePattern*>::const_iterator pf_iterator; 513 pf_iterator pf_begin() const { return PatternFragments.begin(); } 514 pf_iterator pf_end() const { return PatternFragments.end(); } 515 516 // Patterns to match information. 517 typedef std::vector<PatternToMatch>::const_iterator ptm_iterator; 518 ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } 519 ptm_iterator ptm_end() const { return PatternsToMatch.end(); } 520 521 522 523 const DAGInstruction &getInstruction(Record *R) const { 524 assert(Instructions.count(R) && "Unknown instruction!"); 525 return Instructions.find(R)->second; 526 } 527 528 Record *get_intrinsic_void_sdnode() const { 529 return intrinsic_void_sdnode; 530 } 531 Record *get_intrinsic_w_chain_sdnode() const { 532 return intrinsic_w_chain_sdnode; 533 } 534 Record *get_intrinsic_wo_chain_sdnode() const { 535 return intrinsic_wo_chain_sdnode; 536 } 537 538private: 539 void ParseNodeInfo(); 540 void ParseNodeTransforms(); 541 void ParseComplexPatterns(); 542 void ParsePatternFragments(); 543 void ParseDefaultOperands(); 544 void ParseInstructions(); 545 void ParsePatterns(); 546 void GenerateVariants(); 547 548 void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 549 std::map<std::string, 550 TreePatternNode*> &InstInputs, 551 std::map<std::string, 552 TreePatternNode*> &InstResults, 553 std::vector<Record*> &InstImpInputs, 554 std::vector<Record*> &InstImpResults); 555}; 556} // end namespace llvm 557 558#endif 559