1193323Sed//===- DAGISelEmitter.cpp - Generate an instruction selector --------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This tablegen backend emits a DAG instruction selector. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14239462Sdim#include "CodeGenDAGPatterns.h" 15203954Srdivacky#include "DAGISelMatcher.h" 16239462Sdim#include "llvm/Support/Debug.h" 17226633Sdim#include "llvm/TableGen/Record.h" 18239462Sdim#include "llvm/TableGen/TableGenBackend.h" 19193323Sedusing namespace llvm; 20193323Sed 21239462Sdimnamespace { 22239462Sdim/// DAGISelEmitter - The top-level class which coordinates construction 23239462Sdim/// and emission of the instruction selector. 24239462Sdimclass DAGISelEmitter { 25239462Sdim CodeGenDAGPatterns CGP; 26239462Sdimpublic: 27239462Sdim explicit DAGISelEmitter(RecordKeeper &R) : CGP(R) {} 28239462Sdim void run(raw_ostream &OS); 29239462Sdim}; 30239462Sdim} // End anonymous namespace 31239462Sdim 32193323Sed//===----------------------------------------------------------------------===// 33193323Sed// DAGISelEmitter Helper methods 34193323Sed// 35193323Sed 36193323Sed/// getResultPatternCost - Compute the number of instructions for this pattern. 37193323Sed/// This is a temporary hack. We should really include the instruction 38193323Sed/// latencies in this calculation. 39193323Sedstatic unsigned getResultPatternCost(TreePatternNode *P, 40193323Sed CodeGenDAGPatterns &CGP) { 41193323Sed if (P->isLeaf()) return 0; 42221345Sdim 43193323Sed unsigned Cost = 0; 44193323Sed Record *Op = P->getOperator(); 45193323Sed if (Op->isSubClassOf("Instruction")) { 46193323Sed Cost++; 47205407Srdivacky CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op); 48198892Srdivacky if (II.usesCustomInserter) 49193323Sed Cost += 10; 50193323Sed } 51193323Sed for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 52193323Sed Cost += getResultPatternCost(P->getChild(i), CGP); 53193323Sed return Cost; 54193323Sed} 55193323Sed 56193323Sed/// getResultPatternCodeSize - Compute the code size of instructions for this 57193323Sed/// pattern. 58221345Sdimstatic unsigned getResultPatternSize(TreePatternNode *P, 59193323Sed CodeGenDAGPatterns &CGP) { 60193323Sed if (P->isLeaf()) return 0; 61193323Sed 62193323Sed unsigned Cost = 0; 63193323Sed Record *Op = P->getOperator(); 64193323Sed if (Op->isSubClassOf("Instruction")) { 65193323Sed Cost += Op->getValueAsInt("CodeSize"); 66193323Sed } 67193323Sed for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 68193323Sed Cost += getResultPatternSize(P->getChild(i), CGP); 69193323Sed return Cost; 70193323Sed} 71193323Sed 72204642Srdivackynamespace { 73204642Srdivacky// PatternSortingPredicate - return true if we prefer to match LHS before RHS. 74204642Srdivacky// In particular, we want to match maximal patterns first and lowest cost within 75204642Srdivacky// a particular complexity first. 76204642Srdivackystruct PatternSortingPredicate { 77204642Srdivacky PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {} 78193323Sed CodeGenDAGPatterns &CGP; 79221345Sdim 80206083Srdivacky bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) { 81206083Srdivacky const TreePatternNode *LHSSrc = LHS->getSrcPattern(); 82206083Srdivacky const TreePatternNode *RHSSrc = RHS->getSrcPattern(); 83221345Sdim 84263508Sdim MVT LHSVT = (LHSSrc->getNumTypes() != 0 ? LHSSrc->getType(0) : MVT::Other); 85263508Sdim MVT RHSVT = (RHSSrc->getNumTypes() != 0 ? RHSSrc->getType(0) : MVT::Other); 86263508Sdim if (LHSVT.isVector() != RHSVT.isVector()) 87263508Sdim return RHSVT.isVector(); 88221345Sdim 89263508Sdim if (LHSVT.isFloatingPoint() != RHSVT.isFloatingPoint()) 90263508Sdim return RHSVT.isFloatingPoint(); 91221345Sdim 92206083Srdivacky // Otherwise, if the patterns might both match, sort based on complexity, 93206083Srdivacky // which means that we prefer to match patterns that cover more nodes in the 94206083Srdivacky // input over nodes that cover fewer. 95206083Srdivacky unsigned LHSSize = LHS->getPatternComplexity(CGP); 96206083Srdivacky unsigned RHSSize = RHS->getPatternComplexity(CGP); 97204642Srdivacky if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost 98204642Srdivacky if (LHSSize < RHSSize) return false; 99221345Sdim 100204642Srdivacky // If the patterns have equal complexity, compare generated instruction cost 101204642Srdivacky unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP); 102204642Srdivacky unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP); 103204642Srdivacky if (LHSCost < RHSCost) return true; 104204642Srdivacky if (LHSCost > RHSCost) return false; 105221345Sdim 106204642Srdivacky unsigned LHSPatSize = getResultPatternSize(LHS->getDstPattern(), CGP); 107204642Srdivacky unsigned RHSPatSize = getResultPatternSize(RHS->getDstPattern(), CGP); 108204642Srdivacky if (LHSPatSize < RHSPatSize) return true; 109204642Srdivacky if (LHSPatSize > RHSPatSize) return false; 110221345Sdim 111206083Srdivacky // Sort based on the UID of the pattern, giving us a deterministic ordering 112206083Srdivacky // if all other sorting conditions fail. 113204642Srdivacky assert(LHS == RHS || LHS->ID != RHS->ID); 114204642Srdivacky return LHS->ID < RHS->ID; 115203954Srdivacky } 116204642Srdivacky}; 117239462Sdim} // End anonymous namespace 118193323Sed 119193323Sed 120195340Sedvoid DAGISelEmitter::run(raw_ostream &OS) { 121239462Sdim emitSourceFileHeader("DAG Instruction Selector for the " + 122193323Sed CGP.getTargetInfo().getName() + " target", OS); 123221345Sdim 124193323Sed OS << "// *** NOTE: This file is #included into the middle of the target\n" 125193323Sed << "// *** instruction selector class. These functions are really " 126193323Sed << "methods.\n\n"; 127193323Sed 128204642Srdivacky DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n"; 129204642Srdivacky for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), 130204642Srdivacky E = CGP.ptm_end(); I != E; ++I) { 131204642Srdivacky errs() << "PATTERN: "; I->getSrcPattern()->dump(); 132204642Srdivacky errs() << "\nRESULT: "; I->getDstPattern()->dump(); 133204642Srdivacky errs() << "\n"; 134204642Srdivacky }); 135204642Srdivacky 136204642Srdivacky // Add all the patterns to a temporary list so we can sort them. 137204642Srdivacky std::vector<const PatternToMatch*> Patterns; 138193323Sed for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end(); 139204642Srdivacky I != E; ++I) 140204642Srdivacky Patterns.push_back(&*I); 141204642Srdivacky 142204642Srdivacky // We want to process the matches in order of minimal cost. Sort the patterns 143204642Srdivacky // so the least cost one is at the start. 144206083Srdivacky std::sort(Patterns.begin(), Patterns.end(), PatternSortingPredicate(CGP)); 145221345Sdim 146221345Sdim 147204642Srdivacky // Convert each variant of each pattern into a Matcher. 148204642Srdivacky std::vector<Matcher*> PatternMatchers; 149204642Srdivacky for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 150204642Srdivacky for (unsigned Variant = 0; ; ++Variant) { 151204642Srdivacky if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP)) 152204642Srdivacky PatternMatchers.push_back(M); 153204642Srdivacky else 154204642Srdivacky break; 155204642Srdivacky } 156203954Srdivacky } 157221345Sdim 158204642Srdivacky Matcher *TheMatcher = new ScopeMatcher(&PatternMatchers[0], 159204642Srdivacky PatternMatchers.size()); 160204642Srdivacky 161204642Srdivacky TheMatcher = OptimizeMatcher(TheMatcher, CGP); 162203954Srdivacky //Matcher->dump(); 163204642Srdivacky EmitMatcherTable(TheMatcher, CGP, OS); 164204642Srdivacky delete TheMatcher; 165193323Sed} 166239462Sdim 167239462Sdimnamespace llvm { 168239462Sdim 169239462Sdimvoid EmitDAGISel(RecordKeeper &RK, raw_ostream &OS) { 170239462Sdim DAGISelEmitter(RK).run(OS); 171239462Sdim} 172239462Sdim 173239462Sdim} // End llvm namespace 174