CodeGenDAGPatterns.h revision 4d452de1506344bf1d28bb4a8c4ddb78c51a28c8 
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
469  std::map<Record*, SDNodeInfo> SDNodes;
470  std::map<Record*, std::pair<Record*, std::string> > SDNodeXForms;
471  std::map<Record*, ComplexPattern> ComplexPatterns;
472  std::map<Record*, TreePattern*> PatternFragments;
473  std::map<Record*, DAGDefaultOperand> DefaultOperands;
474  std::map<Record*, DAGInstruction> Instructions;
475
476  // Specific SDNode definitions:
477  Record *intrinsic_void_sdnode;
478  Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode;
479
480  /// PatternsToMatch - All of the things we are matching on the DAG.  The first
481  /// value is the pattern to match, the second pattern is the result to
482  /// emit.
483  std::vector<PatternToMatch> PatternsToMatch;
484public:
485  CodeGenDAGPatterns(RecordKeeper &R);
486  ~CodeGenDAGPatterns();
487
488  CodeGenTarget &getTargetInfo() { return Target; }
489  const CodeGenTarget &getTargetInfo() const { return Target; }
490
491  Record *getSDNodeNamed(const std::string &Name) const;
492
493  const SDNodeInfo &getSDNodeInfo(Record *R) const {
494    assert(SDNodes.count(R) && "Unknown node!");
495    return SDNodes.find(R)->second;
496  }
497
498  // Node transformation lookups.
499  typedef std::pair<Record*, std::string> NodeXForm;
500  const NodeXForm &getSDNodeTransform(Record *R) const {
501    assert(SDNodeXForms.count(R) && "Invalid transform!");
502    return SDNodeXForms.find(R)->second;
503  }
504
505  typedef std::map<Record*, NodeXForm>::const_iterator nx_iterator;
506  nx_iterator nx_begin() const { return SDNodeXForms.begin(); }
507  nx_iterator nx_end() const { return SDNodeXForms.end(); }
508
509
510  const ComplexPattern &getComplexPattern(Record *R) const {
511    assert(ComplexPatterns.count(R) && "Unknown addressing mode!");
512    return ComplexPatterns.find(R)->second;
513  }
514
515  const CodeGenIntrinsic &getIntrinsic(Record *R) const {
516    for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
517      if (Intrinsics[i].TheDef == R) return Intrinsics[i];
518    assert(0 && "Unknown intrinsic!");
519    abort();
520  }
521
522  const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const {
523    assert(IID-1 < Intrinsics.size() && "Bad intrinsic ID!");
524    return Intrinsics[IID-1];
525  }
526
527  unsigned getIntrinsicID(Record *R) const {
528    for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
529      if (Intrinsics[i].TheDef == R) return i;
530    assert(0 && "Unknown intrinsic!");
531    abort();
532  }
533
534  const DAGDefaultOperand &getDefaultOperand(Record *R) {
535    assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!");
536    return DefaultOperands.find(R)->second;
537  }
538
539  // Pattern Fragment information.
540  TreePattern *getPatternFragment(Record *R) const {
541    assert(PatternFragments.count(R) && "Invalid pattern fragment request!");
542    return PatternFragments.find(R)->second;
543  }
544  typedef std::map<Record*, TreePattern*>::const_iterator pf_iterator;
545  pf_iterator pf_begin() const { return PatternFragments.begin(); }
546  pf_iterator pf_end() const { return PatternFragments.end(); }
547
548  // Patterns to match information.
549  typedef std::vector<PatternToMatch>::const_iterator ptm_iterator;
550  ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); }
551  ptm_iterator ptm_end() const { return PatternsToMatch.end(); }
552
553
554
555  const DAGInstruction &getInstruction(Record *R) const {
556    assert(Instructions.count(R) && "Unknown instruction!");
557    return Instructions.find(R)->second;
558  }
559
560  Record *get_intrinsic_void_sdnode() const {
561    return intrinsic_void_sdnode;
562  }
563  Record *get_intrinsic_w_chain_sdnode() const {
564    return intrinsic_w_chain_sdnode;
565  }
566  Record *get_intrinsic_wo_chain_sdnode() const {
567    return intrinsic_wo_chain_sdnode;
568  }
569
570private:
571  void ParseNodeInfo();
572  void ParseNodeTransforms();
573  void ParseComplexPatterns();
574  void ParsePatternFragments();
575  void ParseDefaultOperands();
576  void ParseInstructions();
577  void ParsePatterns();
578  void InferInstructionFlags();
579  void GenerateVariants();
580
581  void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
582                                   std::map<std::string,
583                                   TreePatternNode*> &InstInputs,
584                                   std::map<std::string,
585                                   TreePatternNode*> &InstResults,
586                                   std::vector<Record*> &InstImpInputs,
587                                   std::vector<Record*> &InstImpResults);
588};
589} // end namespace llvm
590
591#endif
592