Index: CMakeLists.txt =================================================================== --- CMakeLists.txt +++ CMakeLists.txt @@ -174,6 +174,8 @@ add_definitions(-DLLVM_BUILD_GLOBAL_ISEL) endif() +option(LLVM_ENABLE_DAGISEL_COV "Debug: Prints tablegen patterns that were used for selecting" OFF) + # Add path for custom modules set(CMAKE_MODULE_PATH ${CMAKE_MODULE_PATH} Index: cmake/modules/TableGen.cmake =================================================================== --- cmake/modules/TableGen.cmake +++ cmake/modules/TableGen.cmake @@ -23,6 +23,13 @@ set(LLVM_TARGET_DEFINITIONS_ABSOLUTE ${CMAKE_CURRENT_SOURCE_DIR}/${LLVM_TARGET_DEFINITIONS}) endif() + if (LLVM_ENABLE_DAGISEL_COV) + list(FIND ARGN "-gen-dag-isel" idx) + if( NOT idx EQUAL -1 ) + list(APPEND LLVM_TABLEGEN_FLAGS "-instrument-coverage") + endif() + endif() + add_custom_command(OUTPUT ${CMAKE_CURRENT_BINARY_DIR}/${ofn}.tmp # Generate tablegen output in a temporary file. COMMAND ${${project}_TABLEGEN_EXE} ${ARGN} -I ${CMAKE_CURRENT_SOURCE_DIR} Index: include/llvm/CodeGen/SelectionDAGISel.h =================================================================== --- include/llvm/CodeGen/SelectionDAGISel.h +++ include/llvm/CodeGen/SelectionDAGISel.h @@ -151,7 +151,9 @@ OPC_MorphNodeTo, // Space-optimized forms that implicitly encode number of result VTs. OPC_MorphNodeTo0, OPC_MorphNodeTo1, OPC_MorphNodeTo2, - OPC_CompleteMatch + OPC_CompleteMatch, + // Contains offset in table for pattern being selected + OPC_Coverage }; enum { @@ -213,6 +215,15 @@ void SelectInlineAsmMemoryOperands(std::vector &Ops, const SDLoc &DL); + /// getPatternForIndex - Patterns selected by tablegen during ISEL + virtual StringRef getPatternForIndex(unsigned index) { + llvm_unreachable("Tblgen should generate the implementation of this!"); + } + + /// getIncludePathForIndex - get the td source location of pattern instantiation + virtual StringRef getIncludePathForIndex(unsigned index) { + llvm_unreachable("Tblgen should generate the implementation of this!"); + } public: // Calls to these predicates are generated by tblgen. bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS, Index: lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -3492,6 +3492,15 @@ RecordedNodes.push_back(std::pair(Res, nullptr)); continue; } + case OPC_Coverage: { + // This is emitted right before MorphNode/EmitNode. + // So it should be safe to assume that this node has been selected + unsigned index = MatcherTable[MatcherIndex++]; + index |= (MatcherTable[MatcherIndex++] << 8); + dbgs() << "COVERED: " << getPatternForIndex(index) << "\n"; + dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n"; + continue; + } case OPC_EmitNode: case OPC_MorphNodeTo: case OPC_EmitNode0: case OPC_EmitNode1: case OPC_EmitNode2: Index: utils/TableGen/DAGISelMatcherEmitter.cpp =================================================================== --- utils/TableGen/DAGISelMatcherEmitter.cpp +++ utils/TableGen/DAGISelMatcherEmitter.cpp @@ -11,14 +11,18 @@ // //===----------------------------------------------------------------------===// -#include "DAGISelMatcher.h" #include "CodeGenDAGPatterns.h" +#include "DAGISelMatcher.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/FormattedStream.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/TableGen/Error.h" #include "llvm/TableGen/Record.h" using namespace llvm; @@ -31,6 +35,11 @@ OmitComments("omit-comments", cl::desc("Do not generate comments"), cl::init(false)); +static cl::opt InstrumentCoverage( + "instrument-coverage", + cl::desc("Generates tables to help identify patterns matched"), + cl::init(false)); + namespace { class MatcherTableEmitter { const CodeGenDAGPatterns &CGP; @@ -52,6 +61,19 @@ DenseMap NodeXFormMap; std::vector NodeXForms; + std::vector VecIncludeStrings; + MapVector > VecPatterns; + + unsigned getPatternIdxFromTable(std::string &&P, std::string &&include_loc) { + const auto It = VecPatterns.find(P); + if (It == VecPatterns.end()) { + VecPatterns.insert(make_pair(std::move(P), VecPatterns.size())); + VecIncludeStrings.push_back(std::move(include_loc)); + return VecIncludeStrings.size() - 1; + } + return It->second; + } + public: MatcherTableEmitter(const CodeGenDAGPatterns &cgp) : CGP(cgp) {} @@ -62,6 +84,9 @@ void EmitPredicateFunctions(formatted_raw_ostream &OS); void EmitHistogram(const Matcher *N, formatted_raw_ostream &OS); + + void EmitPatternMatchTable(raw_ostream &OS); + private: unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, formatted_raw_ostream &OS); @@ -117,6 +142,14 @@ }; } // end anonymous namespace. +static std::string GetPatFromTreePatternNode(const TreePatternNode *N) { + std::string str; + raw_string_ostream Stream(str); + Stream << *N; + Stream.str(); + return str; +} + static unsigned GetVBRSize(unsigned Val) { if (Val <= 127) return 1; @@ -150,6 +183,56 @@ return NumBytes+1; } +// This is expensive and slow. +static std::string getIncludePath(const Record *R) { + std::string str; + raw_string_ostream Stream(str); + auto Locs = R->getLoc(); + SMLoc L; + if (Locs.size() > 1) { + // Get where the pattern prototype was instantiated + L = Locs[1]; + } else if (Locs.size() == 1) { + L = Locs[0]; + } + unsigned CurBuf = SrcMgr.FindBufferContainingLoc(L); + assert(CurBuf && "Invalid or unspecified location!"); + + Stream << SrcMgr.getBufferInfo(CurBuf).Buffer->getBufferIdentifier() << ":" + << SrcMgr.FindLineNumber(L, CurBuf); + Stream.str(); + return str; +} + +void MatcherTableEmitter::EmitPatternMatchTable(raw_ostream &OS) { + + assert(isUInt<16>(VecPatterns.size()) && + "Using only 16 bits to encode offset into Pattern Table"); + assert(VecPatterns.size() == VecIncludeStrings.size() && + "The sizes of Pattern and include vectors should be the same"); + OS << "StringRef getPatternForIndex(unsigned Index) override {\n"; + OS << "static const char * PATTERN_MATCH_TABLE[] = {\n"; + + for (const auto &It : VecPatterns) { + OS << "\"" << It.first << "\",\n"; + } + + OS << "\n};"; + OS << "\nreturn StringRef(PATTERN_MATCH_TABLE[Index]);"; + OS << "\n}"; + + OS << "\nStringRef getIncludePathForIndex(unsigned Index) override {\n"; + OS << "static const char * INCLUDE_PATH_TABLE[] = {\n"; + + for (const auto &It : VecIncludeStrings) { + OS << "\"" << It << "\",\n"; + } + + OS << "\n};"; + OS << "\nreturn StringRef(INCLUDE_PATH_TABLE[Index]);"; + OS << "\n}"; +} + /// EmitMatcher - Emit bytes for the specified matcher and return /// the number of bytes emitted. unsigned MatcherTableEmitter:: @@ -537,6 +620,23 @@ case Matcher::EmitNode: case Matcher::MorphNodeTo: { + auto NumCoveredBytes = 0; + if (InstrumentCoverage) { + if (const MorphNodeToMatcher *SNT = dyn_cast(N)) { + NumCoveredBytes = 3; + OS << "OPC_Coverage, "; + std::string src = + GetPatFromTreePatternNode(SNT->getPattern().getSrcPattern()); + std::string dst = + GetPatFromTreePatternNode(SNT->getPattern().getDstPattern()); + Record *PatRecord = SNT->getPattern().getSrcRecord(); + std::string include_src = getIncludePath(PatRecord); + unsigned Offset = + getPatternIdxFromTable(src + " -> " + dst, std::move(include_src)); + OS << "TARGET_VAL(" << Offset << "),\n"; + OS.PadToColumn(Indent * 2); + } + } const EmitNodeMatcherCommon *EN = cast(N); OS << (isa(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo"); bool CompressVTs = EN->getNumVTs() < 3; @@ -593,10 +693,26 @@ } else OS << '\n'; - return 5 + !CompressVTs + EN->getNumVTs() + NumOperandBytes; + return 5 + !CompressVTs + EN->getNumVTs() + NumOperandBytes + + NumCoveredBytes; } case Matcher::CompleteMatch: { const CompleteMatchMatcher *CM = cast(N); + auto NumCoveredBytes = 0; + if (InstrumentCoverage) { + NumCoveredBytes = 3; + OS << "OPC_Coverage, "; + std::string src = + GetPatFromTreePatternNode(CM->getPattern().getSrcPattern()); + std::string dst = + GetPatFromTreePatternNode(CM->getPattern().getDstPattern()); + Record *PatRecord = CM->getPattern().getSrcRecord(); + std::string include_src = getIncludePath(PatRecord); + unsigned Offset = + getPatternIdxFromTable(src + " -> " + dst, std::move(include_src)); + OS << "TARGET_VAL(" << Offset << "),\n"; + OS.PadToColumn(Indent * 2); + } OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", "; unsigned NumResultBytes = 0; for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) @@ -610,7 +726,7 @@ << *CM->getPattern().getDstPattern(); } OS << '\n'; - return 2 + NumResultBytes; + return 2 + NumResultBytes + NumCoveredBytes; } } llvm_unreachable("Unreachable"); @@ -686,8 +802,13 @@ ++NumOps; // Get the chained node too. OS << " case " << i << ":\n"; + if (InstrumentCoverage) + OS << " {\n"; OS << " Result.resize(NextRes+" << NumOps << ");\n"; - OS << " return " << P.getSelectFunc(); + if (InstrumentCoverage) + OS << " bool Succeeded = " << P.getSelectFunc(); + else + OS << " return " << P.getSelectFunc(); OS << "("; // If the complex pattern wants the root of the match, pass it in as the @@ -704,6 +825,13 @@ for (unsigned i = 0; i != NumOps; ++i) OS << ", Result[NextRes+" << i << "].first"; OS << ");\n"; + if (InstrumentCoverage) { + OS << " if (Succeeded)\n"; + OS << " dbgs() << \"\\nCOMPLEX_PATTERN: " << P.getSelectFunc() + << "\\n\" ;\n"; + OS << " return Succeeded;\n"; + OS << " }\n"; + } } OS << " }\n"; OS << "}\n\n"; @@ -847,4 +975,7 @@ // Next up, emit the function for node and pattern predicates: MatcherEmitter.EmitPredicateFunctions(OS); + + if (InstrumentCoverage) + MatcherEmitter.EmitPatternMatchTable(OS); }