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