DAGISelEmitter.cpp revision 206083
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 "DAGISelEmitter.h" 15#include "DAGISelMatcher.h" 16#include "Record.h" 17#include "llvm/Support/Debug.h" 18using namespace llvm; 19 20//===----------------------------------------------------------------------===// 21// DAGISelEmitter Helper methods 22// 23 24/// getResultPatternCost - Compute the number of instructions for this pattern. 25/// This is a temporary hack. We should really include the instruction 26/// latencies in this calculation. 27static unsigned getResultPatternCost(TreePatternNode *P, 28 CodeGenDAGPatterns &CGP) { 29 if (P->isLeaf()) return 0; 30 31 unsigned Cost = 0; 32 Record *Op = P->getOperator(); 33 if (Op->isSubClassOf("Instruction")) { 34 Cost++; 35 CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op); 36 if (II.usesCustomInserter) 37 Cost += 10; 38 } 39 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 40 Cost += getResultPatternCost(P->getChild(i), CGP); 41 return Cost; 42} 43 44/// getResultPatternCodeSize - Compute the code size of instructions for this 45/// pattern. 46static unsigned getResultPatternSize(TreePatternNode *P, 47 CodeGenDAGPatterns &CGP) { 48 if (P->isLeaf()) return 0; 49 50 unsigned Cost = 0; 51 Record *Op = P->getOperator(); 52 if (Op->isSubClassOf("Instruction")) { 53 Cost += Op->getValueAsInt("CodeSize"); 54 } 55 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 56 Cost += getResultPatternSize(P->getChild(i), CGP); 57 return Cost; 58} 59 60//===----------------------------------------------------------------------===// 61// Predicate emitter implementation. 62// 63 64void DAGISelEmitter::EmitPredicateFunctions(raw_ostream &OS) { 65 OS << "\n// Predicate functions.\n"; 66 67 // Walk the pattern fragments, adding them to a map, which sorts them by 68 // name. 69 typedef std::map<std::string, std::pair<Record*, TreePattern*> > PFsByNameTy; 70 PFsByNameTy PFsByName; 71 72 for (CodeGenDAGPatterns::pf_iterator I = CGP.pf_begin(), E = CGP.pf_end(); 73 I != E; ++I) 74 PFsByName.insert(std::make_pair(I->first->getName(), *I)); 75 76 77 for (PFsByNameTy::iterator I = PFsByName.begin(), E = PFsByName.end(); 78 I != E; ++I) { 79 Record *PatFragRecord = I->second.first;// Record that derives from PatFrag. 80 TreePattern *P = I->second.second; 81 82 // If there is a code init for this fragment, emit the predicate code. 83 std::string Code = PatFragRecord->getValueAsCode("Predicate"); 84 if (Code.empty()) continue; 85 86 if (P->getOnlyTree()->isLeaf()) 87 OS << "inline bool Predicate_" << PatFragRecord->getName() 88 << "(SDNode *N) const {\n"; 89 else { 90 std::string ClassName = 91 CGP.getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName(); 92 const char *C2 = ClassName == "SDNode" ? "N" : "inN"; 93 94 OS << "inline bool Predicate_" << PatFragRecord->getName() 95 << "(SDNode *" << C2 << ") const {\n"; 96 if (ClassName != "SDNode") 97 OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n"; 98 } 99 OS << Code << "\n}\n"; 100 } 101 102 OS << "\n\n"; 103} 104 105namespace { 106// PatternSortingPredicate - return true if we prefer to match LHS before RHS. 107// In particular, we want to match maximal patterns first and lowest cost within 108// a particular complexity first. 109struct PatternSortingPredicate { 110 PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {} 111 CodeGenDAGPatterns &CGP; 112 113 bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) { 114 const TreePatternNode *LHSSrc = LHS->getSrcPattern(); 115 const TreePatternNode *RHSSrc = RHS->getSrcPattern(); 116 117 if (LHSSrc->getNumTypes() != 0 && RHSSrc->getNumTypes() != 0 && 118 LHSSrc->getType(0) != RHSSrc->getType(0)) { 119 MVT::SimpleValueType V1 = LHSSrc->getType(0), V2 = RHSSrc->getType(0); 120 if (MVT(V1).isVector() != MVT(V2).isVector()) 121 return MVT(V2).isVector(); 122 123 if (MVT(V1).isFloatingPoint() != MVT(V2).isFloatingPoint()) 124 return MVT(V2).isFloatingPoint(); 125 } 126 127 // Otherwise, if the patterns might both match, sort based on complexity, 128 // which means that we prefer to match patterns that cover more nodes in the 129 // input over nodes that cover fewer. 130 unsigned LHSSize = LHS->getPatternComplexity(CGP); 131 unsigned RHSSize = RHS->getPatternComplexity(CGP); 132 if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost 133 if (LHSSize < RHSSize) return false; 134 135 // If the patterns have equal complexity, compare generated instruction cost 136 unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP); 137 unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP); 138 if (LHSCost < RHSCost) return true; 139 if (LHSCost > RHSCost) return false; 140 141 unsigned LHSPatSize = getResultPatternSize(LHS->getDstPattern(), CGP); 142 unsigned RHSPatSize = getResultPatternSize(RHS->getDstPattern(), CGP); 143 if (LHSPatSize < RHSPatSize) return true; 144 if (LHSPatSize > RHSPatSize) return false; 145 146 // Sort based on the UID of the pattern, giving us a deterministic ordering 147 // if all other sorting conditions fail. 148 assert(LHS == RHS || LHS->ID != RHS->ID); 149 return LHS->ID < RHS->ID; 150 } 151}; 152} 153 154 155void DAGISelEmitter::run(raw_ostream &OS) { 156 EmitSourceFileHeader("DAG Instruction Selector for the " + 157 CGP.getTargetInfo().getName() + " target", OS); 158 159 OS << "// *** NOTE: This file is #included into the middle of the target\n" 160 << "// *** instruction selector class. These functions are really " 161 << "methods.\n\n"; 162 163 DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n"; 164 for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), 165 E = CGP.ptm_end(); I != E; ++I) { 166 errs() << "PATTERN: "; I->getSrcPattern()->dump(); 167 errs() << "\nRESULT: "; I->getDstPattern()->dump(); 168 errs() << "\n"; 169 }); 170 171 // FIXME: These are being used by hand written code, gross. 172 EmitPredicateFunctions(OS); 173 174 // Add all the patterns to a temporary list so we can sort them. 175 std::vector<const PatternToMatch*> Patterns; 176 for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end(); 177 I != E; ++I) 178 Patterns.push_back(&*I); 179 180 // We want to process the matches in order of minimal cost. Sort the patterns 181 // so the least cost one is at the start. 182 std::sort(Patterns.begin(), Patterns.end(), PatternSortingPredicate(CGP)); 183 184 185 // Convert each variant of each pattern into a Matcher. 186 std::vector<Matcher*> PatternMatchers; 187 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 188 for (unsigned Variant = 0; ; ++Variant) { 189 if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP)) 190 PatternMatchers.push_back(M); 191 else 192 break; 193 } 194 } 195 196 Matcher *TheMatcher = new ScopeMatcher(&PatternMatchers[0], 197 PatternMatchers.size()); 198 199 TheMatcher = OptimizeMatcher(TheMatcher, CGP); 200 //Matcher->dump(); 201 EmitMatcherTable(TheMatcher, CGP, OS); 202 delete TheMatcher; 203} 204