← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to utils/TableGen/DAGISelEmitter.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
utils/TableGen/DAGISelEmitter.cpp
 
1
//===- DAGISelEmitter.cpp - Generate an instruction selector --------------===//
 
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 tablegen backend emits a DAG instruction selector.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#include "CodeGenDAGPatterns.h"
 
15
#include "DAGISelMatcher.h"
 
16
#include "llvm/Support/Debug.h"
 
17
#include "llvm/TableGen/Record.h"
 
18
#include "llvm/TableGen/TableGenBackend.h"
 
19
using namespace llvm;
 
20
 
 
21
#define DEBUG_TYPE "dag-isel-emitter"
 
22
 
 
23
namespace {
 
24
/// DAGISelEmitter - The top-level class which coordinates construction
 
25
/// and emission of the instruction selector.
 
26
class DAGISelEmitter {
 
27
  CodeGenDAGPatterns CGP;
 
28
public:
 
29
  explicit DAGISelEmitter(RecordKeeper &R) : CGP(R) {}
 
30
  void run(raw_ostream &OS);
 
31
};
 
32
} // End anonymous namespace
 
33
 
 
34
//===----------------------------------------------------------------------===//
 
35
// DAGISelEmitter Helper methods
 
36
//
 
37
 
 
38
/// getResultPatternCost - Compute the number of instructions for this pattern.
 
39
/// This is a temporary hack.  We should really include the instruction
 
40
/// latencies in this calculation.
 
41
static unsigned getResultPatternCost(TreePatternNode *P,
 
42
                                     CodeGenDAGPatterns &CGP) {
 
43
  if (P->isLeaf()) return 0;
 
44
 
 
45
  unsigned Cost = 0;
 
46
  Record *Op = P->getOperator();
 
47
  if (Op->isSubClassOf("Instruction")) {
 
48
    Cost++;
 
49
    CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);
 
50
    if (II.usesCustomInserter)
 
51
      Cost += 10;
 
52
  }
 
53
  for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
 
54
    Cost += getResultPatternCost(P->getChild(i), CGP);
 
55
  return Cost;
 
56
}
 
57
 
 
58
/// getResultPatternCodeSize - Compute the code size of instructions for this
 
59
/// pattern.
 
60
static unsigned getResultPatternSize(TreePatternNode *P,
 
61
                                     CodeGenDAGPatterns &CGP) {
 
62
  if (P->isLeaf()) return 0;
 
63
 
 
64
  unsigned Cost = 0;
 
65
  Record *Op = P->getOperator();
 
66
  if (Op->isSubClassOf("Instruction")) {
 
67
    Cost += Op->getValueAsInt("CodeSize");
 
68
  }
 
69
  for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
 
70
    Cost += getResultPatternSize(P->getChild(i), CGP);
 
71
  return Cost;
 
72
}
 
73
 
 
74
namespace {
 
75
// PatternSortingPredicate - return true if we prefer to match LHS before RHS.
 
76
// In particular, we want to match maximal patterns first and lowest cost within
 
77
// a particular complexity first.
 
78
struct PatternSortingPredicate {
 
79
  PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {}
 
80
  CodeGenDAGPatterns &CGP;
 
81
 
 
82
  bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) {
 
83
    const TreePatternNode *LHSSrc = LHS->getSrcPattern();
 
84
    const TreePatternNode *RHSSrc = RHS->getSrcPattern();
 
85
 
 
86
    MVT LHSVT = (LHSSrc->getNumTypes() != 0 ? LHSSrc->getType(0) : MVT::Other);
 
87
    MVT RHSVT = (RHSSrc->getNumTypes() != 0 ? RHSSrc->getType(0) : MVT::Other);
 
88
    if (LHSVT.isVector() != RHSVT.isVector())
 
89
      return RHSVT.isVector();
 
90
 
 
91
    if (LHSVT.isFloatingPoint() != RHSVT.isFloatingPoint())
 
92
      return RHSVT.isFloatingPoint();
 
93
 
 
94
    // Otherwise, if the patterns might both match, sort based on complexity,
 
95
    // which means that we prefer to match patterns that cover more nodes in the
 
96
    // input over nodes that cover fewer.
 
97
    int LHSSize = LHS->getPatternComplexity(CGP);
 
98
    int RHSSize = RHS->getPatternComplexity(CGP);
 
99
    if (LHSSize > RHSSize) return true;   // LHS -> bigger -> less cost
 
100
    if (LHSSize < RHSSize) return false;
 
101
 
 
102
    // If the patterns have equal complexity, compare generated instruction cost
 
103
    unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP);
 
104
    unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP);
 
105
    if (LHSCost < RHSCost) return true;
 
106
    if (LHSCost > RHSCost) return false;
 
107
 
 
108
    unsigned LHSPatSize = getResultPatternSize(LHS->getDstPattern(), CGP);
 
109
    unsigned RHSPatSize = getResultPatternSize(RHS->getDstPattern(), CGP);
 
110
    if (LHSPatSize < RHSPatSize) return true;
 
111
    if (LHSPatSize > RHSPatSize) return false;
 
112
 
 
113
    // Sort based on the UID of the pattern, giving us a deterministic ordering
 
114
    // if all other sorting conditions fail.
 
115
    assert(LHS == RHS || LHS->ID != RHS->ID);
 
116
    return LHS->ID < RHS->ID;
 
117
  }
 
118
};
 
119
} // End anonymous namespace
 
120
 
 
121
 
 
122
void DAGISelEmitter::run(raw_ostream &OS) {
 
123
  emitSourceFileHeader("DAG Instruction Selector for the " +
 
124
                       CGP.getTargetInfo().getName() + " target", OS);
 
125
 
 
126
  OS << "// *** NOTE: This file is #included into the middle of the target\n"
 
127
     << "// *** instruction selector class.  These functions are really "
 
128
     << "methods.\n\n";
 
129
 
 
130
  DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n";
 
131
        for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
 
132
             E = CGP.ptm_end(); I != E; ++I) {
 
133
          errs() << "PATTERN: ";   I->getSrcPattern()->dump();
 
134
          errs() << "\nRESULT:  "; I->getDstPattern()->dump();
 
135
          errs() << "\n";
 
136
        });
 
137
 
 
138
  // Add all the patterns to a temporary list so we can sort them.
 
139
  std::vector<const PatternToMatch*> Patterns;
 
140
  for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
 
141
       I != E; ++I)
 
142
    Patterns.push_back(&*I);
 
143
 
 
144
  // We want to process the matches in order of minimal cost.  Sort the patterns
 
145
  // so the least cost one is at the start.
 
146
  std::sort(Patterns.begin(), Patterns.end(), PatternSortingPredicate(CGP));
 
147
 
 
148
 
 
149
  // Convert each variant of each pattern into a Matcher.
 
150
  std::vector<Matcher*> PatternMatchers;
 
151
  for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
 
152
    for (unsigned Variant = 0; ; ++Variant) {
 
153
      if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP))
 
154
        PatternMatchers.push_back(M);
 
155
      else
 
156
        break;
 
157
    }
 
158
  }
 
159
 
 
160
  std::unique_ptr<Matcher> TheMatcher =
 
161
    llvm::make_unique<ScopeMatcher>(PatternMatchers);
 
162
 
 
163
  OptimizeMatcher(TheMatcher, CGP);
 
164
  //Matcher->dump();
 
165
  EmitMatcherTable(TheMatcher.get(), CGP, OS);
 
166
}
 
167
 
 
168
namespace llvm {
 
169
 
 
170
void EmitDAGISel(RecordKeeper &RK, raw_ostream &OS) {
 
171
  DAGISelEmitter(RK).run(OS);
 
172
}
 
173
 
 
174
} // End llvm namespace