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 namespace {
     22 /// DAGISelEmitter - The top-level class which coordinates construction
     23 /// and emission of the instruction selector.
     24 class DAGISelEmitter {
     25   CodeGenDAGPatterns CGP;
     26 public:
     27   explicit DAGISelEmitter(RecordKeeper &R) : CGP(R) {}
     28   void run(raw_ostream &OS);
     29 };
     30 } // End anonymous namespace
     31 
     32 //===----------------------------------------------------------------------===//
     33 // DAGISelEmitter Helper methods
     34 //
     35 
     36 /// getResultPatternCost - Compute the number of instructions for this pattern.
     37 /// This is a temporary hack.  We should really include the instruction
     38 /// latencies in this calculation.
     39 static unsigned getResultPatternCost(TreePatternNode *P,
     40                                      CodeGenDAGPatterns &CGP) {
     41   if (P->isLeaf()) return 0;
     42 
     43   unsigned Cost = 0;
     44   Record *Op = P->getOperator();
     45   if (Op->isSubClassOf("Instruction")) {
     46     Cost++;
     47     CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);
     48     if (II.usesCustomInserter)
     49       Cost += 10;
     50   }
     51   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
     52     Cost += getResultPatternCost(P->getChild(i), CGP);
     53   return Cost;
     54 }
     55 
     56 /// getResultPatternCodeSize - Compute the code size of instructions for this
     57 /// pattern.
     58 static unsigned getResultPatternSize(TreePatternNode *P,
     59                                      CodeGenDAGPatterns &CGP) {
     60   if (P->isLeaf()) return 0;
     61 
     62   unsigned Cost = 0;
     63   Record *Op = P->getOperator();
     64   if (Op->isSubClassOf("Instruction")) {
     65     Cost += Op->getValueAsInt("CodeSize");
     66   }
     67   for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
     68     Cost += getResultPatternSize(P->getChild(i), CGP);
     69   return Cost;
     70 }
     71 
     72 namespace {
     73 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
     74 // In particular, we want to match maximal patterns first and lowest cost within
     75 // a particular complexity first.
     76 struct PatternSortingPredicate {
     77   PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {}
     78   CodeGenDAGPatterns &CGP;
     79 
     80   bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) {
     81     const TreePatternNode *LHSSrc = LHS->getSrcPattern();
     82     const TreePatternNode *RHSSrc = RHS->getSrcPattern();
     83 
     84     if (LHSSrc->getNumTypes() != 0 && RHSSrc->getNumTypes() != 0 &&
     85         LHSSrc->getType(0) != RHSSrc->getType(0)) {
     86       MVT::SimpleValueType V1 = LHSSrc->getType(0), V2 = RHSSrc->getType(0);
     87       if (MVT(V1).isVector() != MVT(V2).isVector())
     88         return MVT(V2).isVector();
     89 
     90       if (MVT(V1).isFloatingPoint() != MVT(V2).isFloatingPoint())
     91         return MVT(V2).isFloatingPoint();
     92     }
     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[0],
    161                                          PatternMatchers.size());
    162 
    163   TheMatcher = OptimizeMatcher(TheMatcher, CGP);
    164   //Matcher->dump();
    165   EmitMatcherTable(TheMatcher, CGP, OS);
    166   delete TheMatcher;
    167 }
    168 
    169 namespace llvm {
    170 
    171 void EmitDAGISel(RecordKeeper &RK, raw_ostream &OS) {
    172   DAGISelEmitter(RK).run(OS);
    173 }
    174 
    175 } // End llvm namespace
    176