DAGISelMatcherGen.cpp revision da272d1a704bd564272e88cbdbcf14712e3abbdc 
1//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===//
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#include "DAGISelMatcher.h"
11#include "CodeGenDAGPatterns.h"
12#include "Record.h"
13#include "llvm/ADT/StringMap.h"
14using namespace llvm;
15
16namespace {
17  class MatcherGen {
18    const PatternToMatch &Pattern;
19    const CodeGenDAGPatterns &CGP;
20
21    /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts
22    /// out with all of the types removed.  This allows us to insert type checks
23    /// as we scan the tree.
24    TreePatternNode *PatWithNoTypes;
25
26    /// VariableMap - A map from variable names ('$dst') to the recorded operand
27    /// number that they were captured as.  These are biased by 1 to make
28    /// insertion easier.
29    StringMap<unsigned> VariableMap;
30    unsigned NextRecordedOperandNo;
31
32    MatcherNodeWithChild *Matcher;
33    MatcherNodeWithChild *CurPredicate;
34  public:
35    MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp);
36
37    ~MatcherGen() {
38      delete PatWithNoTypes;
39    }
40
41    void EmitMatcherCode();
42
43    MatcherNodeWithChild *GetMatcher() const { return Matcher; }
44    MatcherNodeWithChild *GetCurPredicate() const { return CurPredicate; }
45  private:
46    void AddMatcherNode(MatcherNodeWithChild *NewNode);
47    void InferPossibleTypes();
48    void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes);
49    void EmitLeafMatchCode(const TreePatternNode *N);
50    void EmitOperatorMatchCode(const TreePatternNode *N,
51                               TreePatternNode *NodeNoTypes);
52  };
53
54} // end anon namespace.
55
56MatcherGen::MatcherGen(const PatternToMatch &pattern,
57                       const CodeGenDAGPatterns &cgp)
58: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0),
59  Matcher(0), CurPredicate(0) {
60  // We need to produce the matcher tree for the patterns source pattern.  To do
61  // this we need to match the structure as well as the types.  To do the type
62  // matching, we want to figure out the fewest number of type checks we need to
63  // emit.  For example, if there is only one integer type supported by a
64  // target, there should be no type comparisons at all for integer patterns!
65  //
66  // To figure out the fewest number of type checks needed, clone the pattern,
67  // remove the types, then perform type inference on the pattern as a whole.
68  // If there are unresolved types, emit an explicit check for those types,
69  // apply the type to the tree, then rerun type inference.  Iterate until all
70  // types are resolved.
71  //
72  PatWithNoTypes = Pattern.getSrcPattern()->clone();
73  PatWithNoTypes->RemoveAllTypes();
74
75  // If there are types that are manifestly known, infer them.
76  InferPossibleTypes();
77}
78
79/// InferPossibleTypes - As we emit the pattern, we end up generating type
80/// checks and applying them to the 'PatWithNoTypes' tree.  As we do this, we
81/// want to propagate implied types as far throughout the tree as possible so
82/// that we avoid doing redundant type checks.  This does the type propagation.
83void MatcherGen::InferPossibleTypes() {
84  // TP - Get *SOME* tree pattern, we don't care which.  It is only used for
85  // diagnostics, which we know are impossible at this point.
86  TreePattern &TP = *CGP.pf_begin()->second;
87
88  try {
89    bool MadeChange = true;
90    while (MadeChange)
91      MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP,
92                                                true/*Ignore reg constraints*/);
93  } catch (...) {
94    errs() << "Type constraint application shouldn't fail!";
95    abort();
96  }
97}
98
99
100/// AddMatcherNode - Add a matcher node to the current graph we're building.
101void MatcherGen::AddMatcherNode(MatcherNodeWithChild *NewNode) {
102  if (CurPredicate != 0)
103    CurPredicate->setChild(NewNode);
104  else
105    Matcher = NewNode;
106  CurPredicate = NewNode;
107}
108
109
110
111/// EmitLeafMatchCode - Generate matching code for leaf nodes.
112void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) {
113  assert(N->isLeaf() && "Not a leaf?");
114  // Direct match against an integer constant.
115  if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue()))
116    return AddMatcherNode(new CheckIntegerMatcherNode(II->getValue()));
117
118  DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue());
119  if (DI == 0) {
120    errs() << "Unknown leaf kind: " << *DI << "\n";
121    abort();
122  }
123
124  Record *LeafRec = DI->getDef();
125  if (// Handle register references.  Nothing to do here, they always match.
126      LeafRec->isSubClassOf("RegisterClass") ||
127      LeafRec->isSubClassOf("PointerLikeRegClass") ||
128      LeafRec->isSubClassOf("Register") ||
129      // Place holder for SRCVALUE nodes. Nothing to do here.
130      LeafRec->getName() == "srcvalue")
131    return;
132
133  if (LeafRec->isSubClassOf("ValueType"))
134    return AddMatcherNode(new CheckValueTypeMatcherNode(LeafRec->getName()));
135
136  if (LeafRec->isSubClassOf("CondCode"))
137    return AddMatcherNode(new CheckCondCodeMatcherNode(LeafRec->getName()));
138
139  if (LeafRec->isSubClassOf("ComplexPattern")) {
140    // Handle complex pattern.
141    const ComplexPattern &CP = CGP.getComplexPattern(LeafRec);
142    return AddMatcherNode(new CheckComplexPatMatcherNode(CP));
143  }
144
145  errs() << "Unknown leaf kind: " << *N << "\n";
146  abort();
147}
148
149void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N,
150                                       TreePatternNode *NodeNoTypes) {
151  assert(!N->isLeaf() && "Not an operator?");
152  const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator());
153
154  // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is
155  // a constant without a predicate fn that has more that one bit set, handle
156  // this as a special case.  This is usually for targets that have special
157  // handling of certain large constants (e.g. alpha with it's 8/16/32-bit
158  // handling stuff).  Using these instructions is often far more efficient
159  // than materializing the constant.  Unfortunately, both the instcombiner
160  // and the dag combiner can often infer that bits are dead, and thus drop
161  // them from the mask in the dag.  For example, it might turn 'AND X, 255'
162  // into 'AND X, 254' if it knows the low bit is set.  Emit code that checks
163  // to handle this.
164  if ((N->getOperator()->getName() == "and" ||
165       N->getOperator()->getName() == "or") &&
166      N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty()) {
167    if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) {
168      if (!isPowerOf2_32(II->getValue())) {  // Don't bother with single bits.
169        if (N->getOperator()->getName() == "and")
170          AddMatcherNode(new CheckAndImmMatcherNode(II->getValue()));
171        else
172          AddMatcherNode(new CheckOrImmMatcherNode(II->getValue()));
173
174        // Match the LHS of the AND as appropriate.
175        AddMatcherNode(new MoveChildMatcherNode(0));
176        EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0));
177        AddMatcherNode(new MoveParentMatcherNode());
178        return;
179      }
180    }
181  }
182
183  // Check that the current opcode lines up.
184  AddMatcherNode(new CheckOpcodeMatcherNode(CInfo.getEnumName()));
185
186  // If this node has a chain, then the chain is operand #0 is the SDNode, and
187  // the child numbers of the node are all offset by one.
188  unsigned OpNo = 0;
189  if (N->NodeHasProperty(SDNPHasChain, CGP))
190    OpNo = 1;
191
192  if (N->TreeHasProperty(SDNPHasChain, CGP)) {
193    // FIXME: Handle Chains with multiple uses etc.
194    //         [ld]
195    //         ^  ^
196    //         |  |
197    //        /   \---
198    //      /        [YY]
199    //      |         ^
200    //     [XX]-------|
201  }
202
203  // FIXME: Handle Flags & .hasOneUse()
204
205  for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) {
206    // Get the code suitable for matching this child.  Move to the child, check
207    // it then move back to the parent.
208    AddMatcherNode(new MoveChildMatcherNode(i));
209    EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i));
210    AddMatcherNode(new MoveParentMatcherNode());
211  }
212}
213
214
215void MatcherGen::EmitMatchCode(const TreePatternNode *N,
216                               TreePatternNode *NodeNoTypes) {
217  // If N and NodeNoTypes don't agree on a type, then this is a case where we
218  // need to do a type check.  Emit the check, apply the tyep to NodeNoTypes and
219  // reinfer any correlated types.
220  if (NodeNoTypes->getExtTypes() != N->getExtTypes()) {
221    AddMatcherNode(new CheckTypeMatcherNode(N->getTypeNum(0)));
222    NodeNoTypes->setTypes(N->getExtTypes());
223    InferPossibleTypes();
224  }
225
226
227  // If this node has a name associated with it, capture it in VariableMap. If
228  // we already saw this in the pattern, emit code to verify dagness.
229  if (!N->getName().empty()) {
230    unsigned &VarMapEntry = VariableMap[N->getName()];
231    if (VarMapEntry == 0) {
232      VarMapEntry = ++NextRecordedOperandNo;
233      AddMatcherNode(new RecordMatcherNode());
234    } else {
235      // If we get here, this is a second reference to a specific name.  Since
236      // we already have checked that the first reference is valid, we don't
237      // have to recursively match it, just check that it's the same as the
238      // previously named thing.
239      AddMatcherNode(new CheckSameMatcherNode(VarMapEntry-1));
240      return;
241    }
242  }
243
244  // If there are node predicates for this node, generate their checks.
245  for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i)
246    AddMatcherNode(new CheckPredicateMatcherNode(N->getPredicateFns()[i]));
247
248  if (N->isLeaf())
249    EmitLeafMatchCode(N);
250  else
251    EmitOperatorMatchCode(N, NodeNoTypes);
252}
253
254void MatcherGen::EmitMatcherCode() {
255  // If the pattern has a predicate on it (e.g. only enabled when a subtarget
256  // feature is around, do the check).
257  if (!Pattern.getPredicateCheck().empty())
258    AddMatcherNode(new
259                 CheckPatternPredicateMatcherNode(Pattern.getPredicateCheck()));
260
261  // Emit the matcher for the pattern structure and types.
262  EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes);
263}
264
265
266MatcherNode *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern,
267                                           const CodeGenDAGPatterns &CGP) {
268  MatcherGen Gen(Pattern, CGP);
269
270  // Generate the code for the matcher.
271  Gen.EmitMatcherCode();
272
273  // If the match succeeds, then we generate Pattern.
274  EmitNodeMatcherNode *Result = new EmitNodeMatcherNode(Pattern);
275
276  // Link it into the pattern.
277  if (MatcherNodeWithChild *Pred = Gen.GetCurPredicate()) {
278    Pred->setChild(Result);
279    return Gen.GetMatcher();
280  }
281
282  // Unconditional match.
283  return Result;
284}
285
286
287
288