203 lines · cpp
1//===- DAGISelEmitter.cpp - Generate an instruction selector --------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This tablegen backend emits a DAG instruction selector.10//11//===----------------------------------------------------------------------===//12 13#include "Common/CodeGenDAGPatterns.h"14#include "Common/CodeGenInstruction.h"15#include "Common/CodeGenTarget.h"16#include "Common/DAGISelMatcher.h"17#include "llvm/Support/Debug.h"18#include "llvm/TableGen/Record.h"19#include "llvm/TableGen/TGTimer.h"20#include "llvm/TableGen/TableGenBackend.h"21using namespace llvm;22 23#define DEBUG_TYPE "dag-isel-emitter"24 25namespace {26/// DAGISelEmitter - The top-level class which coordinates construction27/// and emission of the instruction selector.28class DAGISelEmitter {29 const RecordKeeper &Records; // Just so we can get at the timing functions.30 const CodeGenDAGPatterns CGP;31 32public:33 explicit DAGISelEmitter(const RecordKeeper &R) : Records(R), CGP(R) {}34 void run(raw_ostream &OS);35};36} // End anonymous namespace37 38//===----------------------------------------------------------------------===//39// DAGISelEmitter Helper methods40//41 42/// Compute the number of instructions for this pattern.43/// This is a temporary hack. We should really include the instruction44/// latencies in this calculation.45static unsigned getResultPatternCost(const TreePatternNode &P,46 const CodeGenDAGPatterns &CGP) {47 if (P.isLeaf())48 return 0;49 50 unsigned Cost = 0;51 const Record *Op = P.getOperator();52 if (Op->isSubClassOf("Instruction")) {53 Cost++;54 const CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op);55 if (II.usesCustomInserter)56 Cost += 10;57 }58 for (const TreePatternNode &Child : P.children())59 Cost += getResultPatternCost(Child, CGP);60 return Cost;61}62 63/// getResultPatternCodeSize - Compute the code size of instructions for this64/// pattern.65static unsigned getResultPatternSize(const TreePatternNode &P,66 const CodeGenDAGPatterns &CGP) {67 if (P.isLeaf())68 return 0;69 70 unsigned Cost = 0;71 const Record *Op = P.getOperator();72 if (Op->isSubClassOf("Instruction")) {73 Cost += Op->getValueAsInt("CodeSize");74 }75 for (const TreePatternNode &Child : P.children())76 Cost += getResultPatternSize(Child, CGP);77 return Cost;78}79 80namespace {81// PatternSortingPredicate - return true if we prefer to match LHS before RHS.82// In particular, we want to match maximal patterns first and lowest cost within83// a particular complexity first.84struct PatternSortingPredicate {85 PatternSortingPredicate(const CodeGenDAGPatterns &cgp) : CGP(cgp) {}86 const CodeGenDAGPatterns &CGP;87 88 bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) {89 const TreePatternNode < = LHS->getSrcPattern();90 const TreePatternNode &RT = RHS->getSrcPattern();91 92 MVT LHSVT = LT.getNumTypes() != 0 ? LT.getSimpleType(0) : MVT::Other;93 MVT RHSVT = RT.getNumTypes() != 0 ? RT.getSimpleType(0) : MVT::Other;94 if (LHSVT.isVector() != RHSVT.isVector())95 return RHSVT.isVector();96 97 if (LHSVT.isFloatingPoint() != RHSVT.isFloatingPoint())98 return RHSVT.isFloatingPoint();99 100 // Otherwise, if the patterns might both match, sort based on complexity,101 // which means that we prefer to match patterns that cover more nodes in the102 // input over nodes that cover fewer.103 int LHSSize = LHS->getPatternComplexity(CGP);104 int RHSSize = RHS->getPatternComplexity(CGP);105 if (LHSSize > RHSSize)106 return true; // LHS -> bigger -> less cost107 if (LHSSize < RHSSize)108 return false;109 110 // If the patterns have equal complexity, compare generated instruction cost111 unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP);112 unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP);113 if (LHSCost < RHSCost)114 return true;115 if (LHSCost > RHSCost)116 return false;117 118 unsigned LHSPatSize = getResultPatternSize(LHS->getDstPattern(), CGP);119 unsigned RHSPatSize = getResultPatternSize(RHS->getDstPattern(), CGP);120 if (LHSPatSize < RHSPatSize)121 return true;122 if (LHSPatSize > RHSPatSize)123 return false;124 125 // Sort based on the UID of the pattern, to reflect source order.126 // Note that this is not guaranteed to be unique, since a single source127 // pattern may have been resolved into multiple match patterns due to128 // alternative fragments. To ensure deterministic output, always use129 // std::stable_sort with this predicate.130 return LHS->getID() < RHS->getID();131 }132};133} // End anonymous namespace134 135void DAGISelEmitter::run(raw_ostream &OS) {136 TGTimer &Timer = Records.getTimer();137 Timer.startTimer("Parse patterns");138 emitSourceFileHeader("DAG Instruction Selector for the " +139 CGP.getTargetInfo().getName().str() + " target",140 OS);141 142 OS << "// *** NOTE: This file is #included into the middle of the target\n"143 << "// *** instruction selector class. These functions are really "144 << "methods.\n\n";145 146 OS << "// If GET_DAGISEL_DECL is #defined with any value, only function\n"147 "// declarations will be included when this file is included.\n"148 "// If GET_DAGISEL_BODY is #defined, its value should be the name of\n"149 "// the instruction selector class. Function bodies will be emitted\n"150 "// and each function's name will be qualified with the name of the\n"151 "// class.\n"152 "//\n"153 "// When neither of the GET_DAGISEL* macros is defined, the functions\n"154 "// are emitted inline.\n\n";155 156 LLVM_DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n";157 for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),158 E = CGP.ptm_end();159 I != E; ++I) {160 errs() << "PATTERN: ";161 I->getSrcPattern().dump();162 errs() << "\nRESULT: ";163 I->getDstPattern().dump();164 errs() << "\n";165 });166 167 // Add all the patterns to a temporary list so we can sort them.168 Timer.startTimer("Sort patterns");169 std::vector<const PatternToMatch *> Patterns;170 for (const PatternToMatch &PTM : CGP.ptms())171 Patterns.push_back(&PTM);172 173 // We want to process the matches in order of minimal cost. Sort the patterns174 // so the least cost one is at the start.175 llvm::stable_sort(Patterns, PatternSortingPredicate(CGP));176 177 // Convert each variant of each pattern into a Matcher.178 Timer.startTimer("Convert to matchers");179 SmallVector<Matcher *, 0> PatternMatchers;180 for (const PatternToMatch *PTM : Patterns) {181 for (unsigned Variant = 0;; ++Variant) {182 if (Matcher *M = ConvertPatternToMatcher(*PTM, Variant, CGP))183 PatternMatchers.push_back(M);184 else185 break;186 }187 }188 189 std::unique_ptr<Matcher> TheMatcher =190 std::make_unique<ScopeMatcher>(std::move(PatternMatchers));191 192 Timer.startTimer("Optimize matchers");193 OptimizeMatcher(TheMatcher, CGP);194 195 // Matcher->dump();196 197 Timer.startTimer("Emit matcher table");198 EmitMatcherTable(TheMatcher.get(), CGP, OS);199}200 201static TableGen::Emitter::OptClass<DAGISelEmitter>202 X("gen-dag-isel", "Generate a DAG instruction selector");203