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