Home | History | Annotate | Download | only in TableGen 
      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     unsigned LHSSize = LHS->getPatternComplexity(CGP);
     98     unsigned 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   Matcher *TheMatcher = new ScopeMatcher(PatternMatchers);
    161 
    162   TheMatcher = OptimizeMatcher(TheMatcher, CGP);
    163   //Matcher->dump();
    164   EmitMatcherTable(TheMatcher, CGP, OS);
    165   delete TheMatcher;
    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
    175