- Add "Commutative" property to intrinsics. This allows tblgen to generate the commut...
[oota-llvm.git] / utils / TableGen / CodeGenDAGPatterns.h
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
23 namespace 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.
36 namespace 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
53 typedef 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.
57 struct 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.
104 class 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;
112 public:
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!
144 class 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;
170 public:
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   
232 public:   // 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 ///
290 class 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;
311 public:
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   
366 private:
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.
372 struct DAGDefaultOperand {
373   std::vector<TreePatternNode*> DefaultOps;
374 };
375
376 class 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;
383 public:
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.
427 struct 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   
449 class 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;
469 public:
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   
555 private:
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