[globalisel][tablegen] Generate rule coverage and use it to identify untested rules

[dsanders]

Summary

This patch adds a LLVM_ENABLE_GISEL_COV which, like LLVM_ENABLE_DAGISEL_COV,
causes TableGen to instrument the generated table to collect rule coverage
information. However, LLVM_ENABLE_GISEL_COV goes a bit further than
LLVM_ENABLE_DAGISEL_COV. The information is written to files
(${CMAKE_BINARY_DIR}/gisel-coverage-* by default). These files can then be
concatenated into ${LLVM_GISEL_COV_PREFIX}-all after which TableGen will
read this information and use it to emit warnings about untested rules.

This technique could also be used by SelectionDAG and can be further
extended to detect hot rules and give them priority over colder rules.

Usage:

• Enable LLVM_ENABLE_GISEL_COV in CMake
• Build the compiler and run some tests
• cat gisel-coverage-[0-9]* > gisel-coverage-all
• Delete lib/Target/*/*GenGlobalISel.inc*
• Build the compiler

Known issues:

• ${LLVM_GISEL_COV_PREFIX}-all must be generated as a manual step due to a lack of a portable 'cat' command. It should be the concatenation of all ${LLVM_GISEL_COV_PREFIX}-[0-9]* files.
• There's no mechanism to discard coverage information when the ruleset changes

Depends on D39742

[vsk]

include/llvm/Support/CodeGenCoverage.h

28

Name this 'setCovered' to be more explicit?

lib/Support/CodeGenCoverage.cpp

30

Could you use llvm::SmartMutex<true> and make this a member of CodeGenCoverage?

84

llvm::SmartScopedLock<true>

97

This is starting to look like sys::fs::createUniqueFile(). It might be better to just use the existing utility.

utils/llvm-gisel-cov.py

20

Missing doc string?

[dsanders]

include/llvm/Support/CodeGenCoverage.h

28

Ok

lib/Support/CodeGenCoverage.cpp

30

Could you use llvm::SmartMutex<true>

Sure.

and make this a member of CodeGenCoverage?

I don't think so. It needs to be a process-wide mutex and if I put it in CodeGenCoverage then there will be separate mutexes for each subtarget. I could put it in as a static member but then anyone that includes the header will have to include all the mutex support too.

84

Ok

97

I'm not sure on this one, createUniqueFile() would solve the multiple-writer problem too but it goes a lot further than necessary. It's ok for the files to be re-used as the OS recycles process id's.

utils/llvm-gisel-cov.py

20

Well spotted. I've forgotten to add the usage information for this script.

[dsanders]

CodeGenCoverage::covered() -> setCovered()
Use SmartMutex and SmartScopedLock
Add missing docstring

[vsk]

This looks good to me, but it'd be worth getting another +1.

[rovka]

Awesome, I could use something like this. LGTM with a few nits.

Is the long-term intention to try and drive this coverage to 100% via in-tree tests, or rather via the test-suite? I'm asking because I was actually considering removing some of the arm-instruction-selector.mir tests which cover the same kind of pattern - e.g. ADD, SUB, AND, OR etc are all derived from an AsI1_bin_irs, so it should be enough to test one of them. We already have tests for the TableGen emitter, so each backend should only have acceptance tests, to make sure TableGen does the right thing for each kind of pattern that it's interested in. Having one test for each rule would just explode the number of tests to the point where they can only be managed automatically, which would really reduce my confidence in them (mostly because TableGen is quirky and I would expect whatever edge cases are handled incorrectly in the emitter to also be handled incorrectly in whatever automatic test generator we'd derive with TableGen).

cmake/modules/TableGen.cmake

59

"use-gisel-coverage" sounds more like a true/false option. How about "gisel-coverage-file" or something along those lines?

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

682

I'm not a compiler, but this looks like it should be setCovered :)

include/llvm/Support/CodeGenCoverage.h

2

The path seems out of date here.

lib/Support/CodeGenCoverage.cpp

2

Wrong path.

utils/TableGen/GlobalISelEmitter.cpp

74

I'm not convinced this is a good default, since it ends with a '-'

75

This should be in the GlobalISelEmitterCat.

[kristof.beyls]

In D39747#918954, @rovka wrote:

Is the long-term intention to try and drive this coverage to 100% via in-tree tests, or rather via the test-suite?

In D39747#918954, @rovka wrote:

Awesome, I could use something like this. LGTM with a few nits.

Is the long-term intention to try and drive this coverage to 100% via in-tree tests, or rather via the test-suite? I'm asking because I was actually considering removing some of the arm-instruction-selector.mir tests which cover the same kind of pattern - e.g. ADD, SUB, AND, OR etc are all derived from an AsI1_bin_irs, so it should be enough to test one of them. We already have tests for the TableGen emitter, so each backend should only have acceptance tests, to make sure TableGen does the right thing for each kind of pattern that it's interested in. Having one test for each rule would just explode the number of tests to the point where they can only be managed automatically, which would really reduce my confidence in them (mostly because TableGen is quirky and I would expect whatever edge cases are handled incorrectly in the emitter to also be handled incorrectly in whatever automatic test generator we'd derive with TableGen).

I'd definitely be interested in knowing what the statistics show today on coverage of regression tests vs test-suite. My expectation is that we actually have higher coverage via the regression tests rather than the test-suite, since the regression tests try harder to cover the paths of logic in the compiler.
My guess is that trying to get 100% code coverage via the test-suite is not going to work. If we'd need to get 100% coverage, I guess it needs to be done via the regression tests. But as you say - if they are going to be mostly automatically generated and not manually inspected, there is a lot of scope for the tests to be wrong.

[dsanders]

In D39747#918954, @rovka wrote:

Awesome, I could use something like this. LGTM with a few nits.

Is the long-term intention to try and drive this coverage to 100% via in-tree tests, or rather via the test-suite? I'm asking because I was actually considering removing some of the arm-instruction-selector.mir tests which cover the same kind of pattern - e.g. ADD, SUB, AND, OR etc are all derived from an AsI1_bin_irs, so it should be enough to test one of them. We already have tests for the TableGen emitter, so each backend should only have acceptance tests, to make sure TableGen does the right thing for each kind of pattern that it's interested in. Having one test for each rule would just explode the number of tests to the point where they can only be managed automatically, which would really reduce my confidence in them (mostly because TableGen is quirky and I would expect whatever edge cases are handled incorrectly in the emitter to also be handled incorrectly in whatever automatic test generator we'd derive with TableGen).

Via the test-suite and any other testing people generally run to qualify a release. I don't think we should try to cover everything with the in-tree tests for the same reasons you give. There is an optimization to the table I'd like to have that would make it a bit more feasible to have high coverage with in-tree tests (I want very-similar imported rules to share an implementation in the generated table) but even then I don't think we should aim for 100% coverage with in-tree tests..

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

682

I'm not sure how I missed that.

utils/TableGen/GlobalISelEmitter.cpp

74

That's a good point. It made more sense before I fixed the multiple-writers problem.

[dsanders]

Fix covered() -> setCovered() change that was somehow missed, and the other nits.

[EricWF]

lib/CodeGen/GlobalISel/InstructionSelect.cpp

23

config.h isn't an installed header, so this breaks the use of installed LLVM versions.

Could you please revert or fix?

CMakeLists.txt

if(NOT CMAKE_HOST_APPLE)
     message(FATAL_ERROR "Dependency debugging is only currently supported on Darwin hosts.")
   endif()
   if(LLVM_CCACHE_BUILD)
     message(FATAL_ERROR "Cannot enable dependency debugging while using ccache.")
   endif()
 endif()
 
 option(LLVM_ENABLE_DAGISEL_COV "Debug: Prints tablegen patterns that were used for selecting" OFF)
+option(LLVM_ENABLE_GISEL_COV "Enable collection of GlobalISel rule coverage" OFF)
+if(LLVM_ENABLE_GISEL_COV)
+  set(LLVM_GISEL_COV_PREFIX "${CMAKE_BINARY_DIR}/gisel-coverage-" CACHE STRING "Provide a filename prefix to collect the GlobalISel rule coverage")
+endif()
 
 # Add path for custom modules
 set(CMAKE_MODULE_PATH
   ${CMAKE_MODULE_PATH}
   "${CMAKE_CURRENT_SOURCE_DIR}/cmake"
   "${CMAKE_CURRENT_SOURCE_DIR}/cmake/modules"
   )
 

cmake/modules/TableGen.cmake

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()
+  if (LLVM_ENABLE_GISEL_COV)
+    list(FIND ARGN "-gen-global-isel" idx)
+    if( NOT idx EQUAL -1 )
+      list(APPEND LLVM_TABLEGEN_FLAGS "-instrument-gisel-coverage")
+      list(APPEND LLVM_TABLEGEN_FLAGS "-use-gisel-coverage=${LLVM_GISEL_COV_PREFIX}all")
+    endif()
+  endif()
 
   # We need both _TABLEGEN_TARGET and _TABLEGEN_EXE in the  DEPENDS list
   # (both the target and the file) to have .inc files rebuilt on
   # a tablegen change, as cmake does not propagate file-level dependencies
   # of custom targets. See the following ticket for more information:
   # https://cmake.org/Bug/view.php?id=15858
   # The dependency on both, the target and the file, produces the same
   # dependency twice in the result file when

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

 /// It's implemented by the target. It's used by the InstructionSelect pass.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/CodeGenCoverage.h"
 #include <bitset>
 #include <cstddef>
 #include <cstdint>
 #include <functional>
 #include <initializer_list>
 #include <vector>
 
 namespace llvm {
 
 class APInt;
 class APFloat;
 class LLT;
 class MachineInstr;
 class MachineInstrBuilder;
+class MachineFunction;
 class MachineOperand;
 class MachineRegisterInfo;
 class RegisterBankInfo;
 class TargetInstrInfo;
 class TargetRegisterClass;
 class TargetRegisterInfo;
 
 /// Container class for CodeGen predicate results.
enum {
   GIR_EraseFromParent,
   /// Create a new temporary register that's not constrained.
   /// - TempRegID - The temporary register ID to initialize.
   /// - Expected type
   GIR_MakeTempReg,
 
   /// A successful emission
   GIR_Done,
+
+  /// Increment the rule coverage counter.
+  /// - RuleID - The ID of the rule that was covered.
+  GIR_Coverage,
 };
 
 enum {
   /// Indicates the end of the variable-length MergeInsnID list in a
   /// GIR_MergeMemOperands opcode.
   GIU_MergeMemOperands_EndOfList = -1,
 };
 
public:
   /// generic pre-isel instructions.
   ///
   /// \returns whether selection succeeded.
   /// \pre  I.getParent() && I.getParent()->getParent()
   /// \post
   ///   if returns true:
   ///     for I in all mutated/inserted instructions:
   ///       !isPreISelGenericOpcode(I.getOpcode())
-  virtual bool select(MachineInstr &I) const = 0;
+  virtual bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const = 0;
 
 protected:
   using ComplexRendererFns =
       Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>;
   using RecordedMIVector = SmallVector<MachineInstr *, 4>;
   using NewMIVector = SmallVector<MachineInstrBuilder, 4>;
 
   struct MatcherState {
protected:
   /// and false otherwise.
   template <class TgtInstructionSelector, class PredicateBitset,
             class ComplexMatcherMemFn>
   bool executeMatchTable(
       TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
       const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> &MatcherInfo,
       const int64_t *MatchTable, const TargetInstrInfo &TII,
       MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
-      const RegisterBankInfo &RBI,
-      const PredicateBitset &AvailableFeatures) const;
+      const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
+      CodeGenCoverage &CoverageInfo) const;
 
   /// Constrain a register operand of an instruction \p I to a specified
   /// register class. This could involve inserting COPYs before (for uses) or
   /// after (for defs) and may replace the operand of \p I.
   /// \returns whether operand regclass constraining succeeded.
   bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
                                      const TargetRegisterClass &RC,
                                      const TargetInstrInfo &TII,

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

 
 template <class TgtInstructionSelector, class PredicateBitset,
           class ComplexMatcherMemFn>
 bool InstructionSelector::executeMatchTable(
     TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
     const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> &MatcherInfo,
     const int64_t *MatchTable, const TargetInstrInfo &TII,
     MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
-    const RegisterBankInfo &RBI,
-    const PredicateBitset &AvailableFeatures) const {
+    const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
+    CodeGenCoverage &CoverageInfo) const {
   uint64_t CurrentIdx = 0;
   SmallVector<uint64_t, 8> OnFailResumeAt;
 
   enum RejectAction { RejectAndGiveUp, RejectAndResume };
   auto handleReject = [&]() -> RejectAction {
     DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
                     dbgs() << CurrentIdx << ": Rejected\n");
     if (OnFailResumeAt.empty())
case GIR_MakeTempReg: {
       State.TempRegisters[TempRegID] =
           MRI.createGenericVirtualRegister(MatcherInfo.TypeObjects[TypeID]);
       DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
                       dbgs() << CurrentIdx << ": TempRegs[" << TempRegID
                              << "] = GIR_MakeTempReg(" << TypeID << ")\n");
       break;
     }
 
+    case GIR_Coverage: {
+      int64_t RuleID = MatchTable[CurrentIdx++];
+      CoverageInfo.covered(RuleID);
+
+      DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
+                      dbgs()
+                          << CurrentIdx << ": GIR_Coverage(" << RuleID << ")");
+      break;
+    }
+
     case GIR_Done:
       DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
                       dbgs() << CurrentIdx << ": GIR_Done");
       return true;
 
     default:
       llvm_unreachable("Unexpected command");
     }
   }
 }
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTORIMPL_H

include/llvm/Config/config.h.cmake

 #cmakedefine strtoull ${strtoull}
 
 /* Define to a function implementing stricmp */
 #cmakedefine stricmp ${stricmp}
 
 /* Define to a function implementing strdup */
 #cmakedefine strdup ${strdup}
 
+/* Whether GlobalISel rule coverage is being collected */
+#cmakedefine01 LLVM_GISEL_COV_ENABLED
+
+/* Define to the default GlobalISel coverage file prefix */
+#cmakedefine LLVM_GISEL_COV_PREFIX "${LLVM_GISEL_COV_PREFIX}"
+
 #endif

include/llvm/Support/CodeGenCoverage.h

+//== llvm/CodeGen/GlobalISel/CodeGenCoverage.h -------------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file This file provides rule coverage tracking for tablegen-erated CodeGen.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CODEGENCOVERAGE_H
+#define LLVM_SUPPORT_CODEGENCOVERAGE_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Config/config.h"
+
+namespace llvm {
+class LLVMContext;
+
+class CodeGenCoverage {
+protected:
+  BitVector RuleCoverage;
+
+public:
+  CodeGenCoverage();
+
+  void covered(uint64_t RuleID);
+  bool isCovered(uint64_t RuleID);
+
+  bool parse(MemoryBuffer &Buffer, StringRef BackendName);
+  bool emit(StringRef FilePrefix, StringRef BackendName) const;
+  void reset();
+};
+} // end namespace llvm
+
+#endif // ifndef LLVM_SUPPORT_CODEGENCOVERAGE_H

lib/CodeGen/GlobalISel/InstructionSelect.cpp

 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/Config/config.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/TargetRegistry.h"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 
 #define DEBUG_TYPE "instruction-select"
 
 using namespace llvm;
 
+static cl::opt<std::string>
+    CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
+                   cl::desc("Record GlobalISel rule coverage files of this "
+                            "prefix if instrumentation was generated"));
+
 char InstructionSelect::ID = 0;
 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
                       "Select target instructions out of generic instructions",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
                     "Select target instructions out of generic instructions",
                     false, false)
bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
 
   DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
 
   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
   const InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
+  CodeGenCoverage CoverageInfo;
   assert(ISel && "Cannot work without InstructionSelector");
 
   // An optimization remark emitter. Used to report failures.
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   // FIXME: There are many other MF/MFI fields we need to initialize.
 
 #ifndef NDEBUG
#endif
       // We could have folded this instruction away already, making it dead.
       // If so, erase it.
       if (isTriviallyDead(MI, MRI)) {
         DEBUG(dbgs() << "Is dead; erasing.\n");
         MI.eraseFromParentAndMarkDBGValuesForRemoval();
         continue;
       }
 
-      if (!ISel->select(MI)) {
+      if (!ISel->select(MI, CoverageInfo)) {
         // FIXME: It would be nice to dump all inserted instructions.  It's
         // not obvious how, esp. considering select() can insert after MI.
         reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
         return false;
       }
 
       // Dump the range of instructions that MI expanded into.
       DEBUG({
if (MF.size() != NumBlocks) {
     R << "inserting blocks is not supported yet";
     reportGISelFailure(MF, TPC, MORE, R);
     return false;
   }
 
   auto &TLI = *MF.getSubtarget().getTargetLowering();
   TLI.finalizeLowering(MF);
 
+  CoverageInfo.emit(CoveragePrefix,
+                    MF.getSubtarget()
+                        .getTargetLowering()
+                        ->getTargetMachine()
+                        .getTarget()
+                        .getBackendName());
+
   // FIXME: Should we accurately track changes?
   return true;
 }

lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   BinaryStreamRef.cpp
   BinaryStreamWriter.cpp
   BlockFrequency.cpp
   BranchProbability.cpp
   CachePruning.cpp
   circular_raw_ostream.cpp
   Chrono.cpp
   COM.cpp
+  CodeGenCoverage.cpp
   CommandLine.cpp
   Compression.cpp
   ConvertUTF.cpp
   ConvertUTFWrapper.cpp
   CrashRecoveryContext.cpp
   DataExtractor.cpp
   Debug.cpp
   DebugCounter.cpp

lib/Support/CodeGenCoverage.cpp

+//===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file implements the CodeGenCoverage class.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/CodeGenCoverage.h"
+
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include <mutex>
+
+#if LLVM_ON_UNIX
+#include <unistd.h>
+#elif LLVM_ON_WIN32
+#include <windows.h>
+#endif
+
+using namespace llvm;
+
+#if LLVM_ENABLE_THREADS == 1
+static std::mutex OutputMutex;
+#endif
+
+CodeGenCoverage::CodeGenCoverage() {}
+
+void CodeGenCoverage::covered(uint64_t RuleID) {
+  if (RuleCoverage.size() <= RuleID)
+    RuleCoverage.resize(RuleID + 1, 0);
+  RuleCoverage[RuleID] = true;
+}
+
+bool CodeGenCoverage::isCovered(uint64_t RuleID) {
+  if (RuleCoverage.size() <= RuleID)
+    return false;
+  return RuleCoverage[RuleID];
+}
+
+bool CodeGenCoverage::parse(MemoryBuffer &Buffer, StringRef BackendName) {
+  const char *CurPtr = Buffer.getBufferStart();
+
+  while (CurPtr != Buffer.getBufferEnd()) {
+    // Read the backend name from the input.
+    const char *LexedBackendName = CurPtr;
+    while (*CurPtr++ != 0)
+      ;
+    if (CurPtr == Buffer.getBufferEnd())
+      return false; // Data is invalid, expected rule id's to follow.
+
+    bool IsForThisBackend = BackendName.equals(LexedBackendName);
+    while (CurPtr != Buffer.getBufferEnd()) {
+      if (std::distance(CurPtr, Buffer.getBufferEnd()) < 8)
+        return false; // Data is invalid. Not enough bytes for another rule id.
+
+      uint64_t RuleID = support::endian::read64(CurPtr, support::native);
+      CurPtr += 8;
+
+      // ~0ull terminates the rule id list.
+      if (RuleID == ~0ull)
+        break;
+
+      // Anything else, is recorded or ignored depending on whether it's
+      // intended for the backend we're interested in.
+      if (IsForThisBackend)
+        covered(RuleID);
+    }
+  }
+
+  return true;
+}
+
+bool CodeGenCoverage::emit(StringRef CoveragePrefix,
+                           StringRef BackendName) const {
+  if (!CoveragePrefix.empty() && !RuleCoverage.empty()) {
+#if LLVM_ENABLE_THREADS == 1
+    std::lock_guard<std::mutex> Lock(OutputMutex);
+#endif
+
+    // We can handle locking within a process easily enough but we don't want to
+    // manage it between multiple processes. Use the process ID to ensure no
+    // more than one process is ever writing to the same file at the same time.
+    std::string Pid =
+#if LLVM_ON_UNIX
+        llvm::to_string(::getpid());
+#elif LLVM_ON_WIN32
+        llvm::to_string(::GetCurrentProcessId());
+#else
+        "";
+#endif
+
+    std::string CoverageFilename = (CoveragePrefix + Pid).str();
+
+    std::error_code EC;
+    sys::fs::OpenFlags OpenFlags = sys::fs::F_Append;
+    std::unique_ptr<ToolOutputFile> CoverageFile =
+        llvm::make_unique<ToolOutputFile>(CoverageFilename, EC, OpenFlags);
+    if (EC)
+      return false;
+
+    uint64_t Zero = 0;
+    uint64_t InvZero = ~0ull;
+    CoverageFile->os() << BackendName;
+    CoverageFile->os().write((const char *)&Zero, sizeof(unsigned char));
+    for (uint64_t I : RuleCoverage.set_bits())
+      CoverageFile->os().write((const char *)&I, sizeof(uint64_t));
+    CoverageFile->os().write((const char *)&InvZero, sizeof(uint64_t));
+
+    CoverageFile->keep();
+  }
+
+  return true;
+}
+
+void CodeGenCoverage::reset() { RuleCoverage.resize(0); }

lib/Target/AArch64/AArch64InstructionSelector.cpp

 #undef GET_GLOBALISEL_PREDICATE_BITSET
 
 class AArch64InstructionSelector : public InstructionSelector {
 public:
   AArch64InstructionSelector(const AArch64TargetMachine &TM,
                              const AArch64Subtarget &STI,
                              const AArch64RegisterBankInfo &RBI);
 
-  bool select(MachineInstr &I) const override;
+  bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const override;
   static const char *getName() { return DEBUG_TYPE; }
 
 private:
   /// tblgen-erated 'select' implementation, used as the initial selector for
   /// the patterns that don't require complex C++.
-  bool selectImpl(MachineInstr &I) const;
+  bool selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const;
 
   bool selectVaStartAAPCS(MachineInstr &I, MachineFunction &MF,
                           MachineRegisterInfo &MRI) const;
   bool selectVaStartDarwin(MachineInstr &I, MachineFunction &MF,
                            MachineRegisterInfo &MRI) const;
 
   bool selectCompareBranch(MachineInstr &I, MachineFunction &MF,
                            MachineRegisterInfo &MRI) const;
MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(AArch64::STRXui))
             .addImm(0)
             .addMemOperand(*I.memoperands_begin());
 
   constrainSelectedInstRegOperands(*MIB, TII, TRI, RBI);
   I.eraseFromParent();
   return true;
 }
 
-bool AArch64InstructionSelector::select(MachineInstr &I) const {
+bool AArch64InstructionSelector::select(MachineInstr &I,
+                                        CodeGenCoverage &CoverageInfo) const {
   assert(I.getParent() && "Instruction should be in a basic block!");
   assert(I.getParent()->getParent() && "Instruction should be in a function!");
 
   MachineBasicBlock &MBB = *I.getParent();
   MachineFunction &MF = *MBB.getParent();
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   unsigned Opcode = I.getOpcode();
bool AArch64InstructionSelector::select(MachineInstr &I,
   }
 
 
   if (I.getNumOperands() != I.getNumExplicitOperands()) {
     DEBUG(dbgs() << "Generic instruction has unexpected implicit operands\n");
     return false;
   }
 
-  if (selectImpl(I))
+  if (selectImpl(I, CoverageInfo))
     return true;
 
   LLT Ty =
       I.getOperand(0).isReg() ? MRI.getType(I.getOperand(0).getReg()) : LLT{};
 
   switch (Opcode) {
   case TargetOpcode::G_BRCOND: {
     if (Ty.getSizeInBits() > 32) {

lib/Target/AMDGPU/AMDGPUInstructionSelector.h

 class SIRegisterInfo;
 class SISubtarget;
 
 class AMDGPUInstructionSelector : public InstructionSelector {
 public:
   AMDGPUInstructionSelector(const SISubtarget &STI,
                             const AMDGPURegisterBankInfo &RBI);
 
-  bool select(MachineInstr &I) const override;
+  bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const override;
+
 private:
   struct GEPInfo {
     const MachineInstr &GEP;
     SmallVector<unsigned, 2> SgprParts;
     SmallVector<unsigned, 2> VgprParts;
     int64_t Imm;
     GEPInfo(const MachineInstr &GEP) : GEP(GEP), Imm(0) { }
   };

lib/Target/AMDGPU/AMDGPUInstructionSelector.cpp

MachineInstr *Flat = BuildMI(*BB, &I, DL, TII.get(Opcode))
                                .addImm(0)  // glc
                                .addImm(0); // slc
 
   bool Ret = constrainSelectedInstRegOperands(*Flat, TII, TRI, RBI);
   I.eraseFromParent();
   return Ret;
 }
 
-bool AMDGPUInstructionSelector::select(MachineInstr &I) const {
+bool AMDGPUInstructionSelector::select(MachineInstr &I,
+                                       CodeGenCoverage &CoverageInfo) const {
 
   if (!isPreISelGenericOpcode(I.getOpcode()))
     return true;
 
   switch (I.getOpcode()) {
   default:
     break;
   case TargetOpcode::G_ADD:

lib/Target/ARM/ARMInstructionSelector.cpp

 #include "ARMGenGlobalISel.inc"
 #undef GET_GLOBALISEL_PREDICATE_BITSET
 
 class ARMInstructionSelector : public InstructionSelector {
 public:
   ARMInstructionSelector(const ARMBaseTargetMachine &TM, const ARMSubtarget &STI,
                          const ARMRegisterBankInfo &RBI);
 
-  bool select(MachineInstr &I) const override;
+  bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const override;
   static const char *getName() { return DEBUG_TYPE; }
 
 private:
-  bool selectImpl(MachineInstr &I) const;
+  bool selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const;
 
   struct CmpConstants;
   struct InsertInfo;
 
   bool selectCmp(CmpConstants Helper, MachineInstrBuilder &MIB,
                  MachineRegisterInfo &MRI) const;
 
   // Helper for inserting a comparison sequence that sets \p ResReg to either 1

 bool ARMInstructionSelector::selectShift(unsigned ShiftOpc,
                                          MachineInstrBuilder &MIB) const {
   MIB->setDesc(TII.get(ARM::MOVsr));
   MIB.addImm(ShiftOpc);
   MIB.add(predOps(ARMCC::AL)).add(condCodeOp());
   return constrainSelectedInstRegOperands(*MIB, TII, TRI, RBI);
 }
 
-bool ARMInstructionSelector::select(MachineInstr &I) const {
+bool ARMInstructionSelector::select(MachineInstr &I,
+                                    CodeGenCoverage &CoverageInfo) const {
   assert(I.getParent() && "Instruction should be in a basic block!");
   assert(I.getParent()->getParent() && "Instruction should be in a function!");
 
   auto &MBB = *I.getParent();
   auto &MF = *MBB.getParent();
   auto &MRI = MF.getRegInfo();
 
   if (!isPreISelGenericOpcode(I.getOpcode())) {
     if (I.isCopy())
       return selectCopy(I, TII, MRI, TRI, RBI);
 
     return true;
   }
 
-  if (selectImpl(I))
+  if (selectImpl(I, CoverageInfo))
     return true;
 
   MachineInstrBuilder MIB{MF, I};
   bool isSExt = false;
 
   using namespace TargetOpcode;
   switch (I.getOpcode()) {
   case G_SEXT:

lib/Target/X86/X86InstructionSelector.cpp

 #include "X86GenGlobalISel.inc"
 #undef GET_GLOBALISEL_PREDICATE_BITSET
 
 class X86InstructionSelector : public InstructionSelector {
 public:
   X86InstructionSelector(const X86TargetMachine &TM, const X86Subtarget &STI,
                          const X86RegisterBankInfo &RBI);
 
-  bool select(MachineInstr &I) const override;
+  bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const override;
   static const char *getName() { return DEBUG_TYPE; }
 
 private:
   /// tblgen-erated 'select' implementation, used as the initial selector for
   /// the patterns that don't require complex C++.
-  bool selectImpl(MachineInstr &I) const;
+  bool selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const;
 
   // TODO: remove after supported by Tablegen-erated instruction selection.
   unsigned getLoadStoreOp(const LLT &Ty, const RegisterBank &RB, unsigned Opc,
                           uint64_t Alignment) const;
 
   bool selectLoadStoreOp(MachineInstr &I, MachineRegisterInfo &MRI,
                          MachineFunction &MF) const;
   bool selectFrameIndexOrGep(MachineInstr &I, MachineRegisterInfo &MRI,
private:
   bool selectAnyext(MachineInstr &I, MachineRegisterInfo &MRI,
                     MachineFunction &MF) const;
   bool selectCmp(MachineInstr &I, MachineRegisterInfo &MRI,
                  MachineFunction &MF) const;
   bool selectUadde(MachineInstr &I, MachineRegisterInfo &MRI,
                    MachineFunction &MF) const;
   bool selectCopy(MachineInstr &I, MachineRegisterInfo &MRI) const;
   bool selectUnmergeValues(MachineInstr &I, MachineRegisterInfo &MRI,
-                           MachineFunction &MF) const;
+                           MachineFunction &MF,
+                           CodeGenCoverage &CoverageInfo) const;
   bool selectMergeValues(MachineInstr &I, MachineRegisterInfo &MRI,
-                         MachineFunction &MF) const;
+                         MachineFunction &MF,
+                         CodeGenCoverage &CoverageInfo) const;
   bool selectInsert(MachineInstr &I, MachineRegisterInfo &MRI,
                     MachineFunction &MF) const;
   bool selectExtract(MachineInstr &I, MachineRegisterInfo &MRI,
                      MachineFunction &MF) const;
   bool selectCondBranch(MachineInstr &I, MachineRegisterInfo &MRI,
                         MachineFunction &MF) const;
   bool materializeFP(MachineInstr &I, MachineRegisterInfo &MRI,
                      MachineFunction &MF) const;
if (!RBI.constrainGenericRegister(DstReg, *DstRC, MRI)) {
                    << " operand\n");
       return false;
     }
   }
   I.setDesc(TII.get(X86::COPY));
   return true;
 }
 
-bool X86InstructionSelector::select(MachineInstr &I) const {
+bool X86InstructionSelector::select(MachineInstr &I,
+                                    CodeGenCoverage &CoverageInfo) const {
   assert(I.getParent() && "Instruction should be in a basic block!");
   assert(I.getParent()->getParent() && "Instruction should be in a function!");
 
   MachineBasicBlock &MBB = *I.getParent();
   MachineFunction &MF = *MBB.getParent();
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   unsigned Opcode = I.getOpcode();
   if (!isPreISelGenericOpcode(Opcode)) {
     // Certain non-generic instructions also need some special handling.
 
     if (Opcode == TargetOpcode::LOAD_STACK_GUARD)
       return false;
 
     if (I.isCopy())
       return selectCopy(I, MRI);
 
     return true;
   }
 
   assert(I.getNumOperands() == I.getNumExplicitOperands() &&
          "Generic instruction has unexpected implicit operands\n");
 
-  if (selectImpl(I))
+  if (selectImpl(I, CoverageInfo))
     return true;
 
   DEBUG(dbgs() << " C++ instruction selection: "; I.print(dbgs()));
 
   // TODO: This should be implemented by tblgen.
   switch (I.getOpcode()) {
   default:
     return false;
case TargetOpcode::G_ZEXT:
     return selectZext(I, MRI, MF);
   case TargetOpcode::G_ANYEXT:
     return selectAnyext(I, MRI, MF);
   case TargetOpcode::G_ICMP:
     return selectCmp(I, MRI, MF);
   case TargetOpcode::G_UADDE:
     return selectUadde(I, MRI, MF);
   case TargetOpcode::G_UNMERGE_VALUES:
-    return selectUnmergeValues(I, MRI, MF);
+    return selectUnmergeValues(I, MRI, MF, CoverageInfo);
   case TargetOpcode::G_MERGE_VALUES:
-    return selectMergeValues(I, MRI, MF);
+    return selectMergeValues(I, MRI, MF, CoverageInfo);
   case TargetOpcode::G_EXTRACT:
     return selectExtract(I, MRI, MF);
   case TargetOpcode::G_INSERT:
     return selectInsert(I, MRI, MF);
   case TargetOpcode::G_BRCOND:
     return selectCondBranch(I, MRI, MF);
   case TargetOpcode::G_IMPLICIT_DEF:
   case TargetOpcode::G_PHI:
bool X86InstructionSelector::selectInsert(MachineInstr &I,
   // Convert to X86 VINSERT immediate.
   Index = Index / InsertRegTy.getSizeInBits();
 
   I.getOperand(3).setImm(Index);
 
   return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
 }
 
-bool X86InstructionSelector::selectUnmergeValues(MachineInstr &I,
-                                                 MachineRegisterInfo &MRI,
-                                                 MachineFunction &MF) const {
+bool X86InstructionSelector::selectUnmergeValues(
+    MachineInstr &I, MachineRegisterInfo &MRI, MachineFunction &MF,
+    CodeGenCoverage &CoverageInfo) const {
   assert((I.getOpcode() == TargetOpcode::G_UNMERGE_VALUES) &&
          "unexpected instruction");
 
   // Split to extracts.
   unsigned NumDefs = I.getNumOperands() - 1;
   unsigned SrcReg = I.getOperand(NumDefs).getReg();
   unsigned DefSize = MRI.getType(I.getOperand(0).getReg()).getSizeInBits();
 
   for (unsigned Idx = 0; Idx < NumDefs; ++Idx) {
     MachineInstr &ExtrInst =
         *BuildMI(*I.getParent(), I, I.getDebugLoc(),
                  TII.get(TargetOpcode::G_EXTRACT), I.getOperand(Idx).getReg())
              .addReg(SrcReg)
              .addImm(Idx * DefSize);
 
-    if (!select(ExtrInst))
+    if (!select(ExtrInst, CoverageInfo))
       return false;
   }
 
   I.eraseFromParent();
   return true;
 }
 
-bool X86InstructionSelector::selectMergeValues(MachineInstr &I,
-                                               MachineRegisterInfo &MRI,
-                                               MachineFunction &MF) const {
+bool X86InstructionSelector::selectMergeValues(
+    MachineInstr &I, MachineRegisterInfo &MRI, MachineFunction &MF,
+    CodeGenCoverage &CoverageInfo) const {
   assert((I.getOpcode() == TargetOpcode::G_MERGE_VALUES) &&
          "unexpected instruction");
 
   // Split to inserts.
   unsigned DstReg = I.getOperand(0).getReg();
   unsigned SrcReg0 = I.getOperand(1).getReg();
 
   const LLT DstTy = MRI.getType(DstReg);
for (unsigned Idx = 2; Idx < I.getNumOperands(); ++Idx) {
     MachineInstr &InsertInst = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
                                         TII.get(TargetOpcode::G_INSERT), Tmp)
                                     .addReg(DefReg)
                                     .addReg(I.getOperand(Idx).getReg())
                                     .addImm((Idx - 1) * SrcSize);
 
     DefReg = Tmp;
 
-    if (!select(InsertInst))
+    if (!select(InsertInst, CoverageInfo))
       return false;
   }
 
   MachineInstr &CopyInst = *BuildMI(*I.getParent(), I, I.getDebugLoc(),
                                     TII.get(TargetOpcode::COPY), DstReg)
                                 .addReg(DefReg);
 
-  if (!select(CopyInst))
+  if (!select(CopyInst, CoverageInfo))
     return false;
 
   I.eraseFromParent();
   return true;
 }
 
 bool X86InstructionSelector::selectCondBranch(MachineInstr &I,
                                               MachineRegisterInfo &MRI,

test/TableGen/GlobalISelEmitter.td

 
 // CHECK-LABEL: MyTargetInstructionSelector::ComplexMatcherMemFn
 // CHECK-NEXT:  MyTargetInstructionSelector::ComplexPredicateFns[] = {
 // CHECK-NEXT:    nullptr, // GICP_Invalid
 // CHECK-NEXT:    &MyTargetInstructionSelector::selectComplexPattern, // gi_complex
 // CHECK-NEXT:    &MyTargetInstructionSelector::selectComplexPatternRR, // gi_complex_rr
 // CHECK-NEXT:  }
 
-// CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I) const {
+// CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const {
 // CHECK-NEXT: MachineFunction &MF = *I.getParent()->getParent();
 // CHECK-NEXT: MachineRegisterInfo &MRI = MF.getRegInfo();
 // CHECK:      AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, &MF);
 // CHECK-NEXT: const PredicateBitset AvailableFeatures = getAvailableFeatures();
 // CHECK-NEXT: NewMIVector OutMIs;
 // CHECK-NEXT: State.MIs.clear();
 // CHECK-NEXT: State.MIs.push_back(&I);
 

 // CHECK-NEXT:    GIR_Done,
 // CHECK-NEXT:  // Label 23: @[[LABEL]]
 
 def BR : I<(outs), (ins unknown:$target),
             [(br bb:$target)]>;
 
 // CHECK-NEXT:    GIM_Reject,
 // CHECK-NEXT:  };
-// CHECK-NEXT:  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable0, TII, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable0, TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {
 // CHECK-NEXT:    return true;
 // CHECK-NEXT:  }

utils/TableGen/GlobalISelEmitter.cpp

 //===----------------------------------------------------------------------===//
 
 #include "CodeGenDAGPatterns.h"
 #include "SubtargetFeatureInfo.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineValueType.h"
+#include "llvm/Config/config.h"
+#include "llvm/Support/CodeGenCoverage.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
-#include <string>
 #include <numeric>
+#include <string>
 using namespace llvm;
 
 #define DEBUG_TYPE "gisel-emitter"
 
 STATISTIC(NumPatternTotal, "Total number of patterns");
 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
+STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information");
 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
 
 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
 
 static cl::opt<bool> WarnOnSkippedPatterns(
     "warn-on-skipped-patterns",
     cl::desc("Explain why a pattern was skipped for inclusion "
              "in the GlobalISel selector"),
     cl::init(false), cl::cat(GlobalISelEmitterCat));
 
+static cl::opt<bool> GenerateCoverage(
+    "instrument-gisel-coverage",
+    cl::desc("Generate coverage instrumentation for GlobalISel"),
+    cl::init(false), cl::cat(GlobalISelEmitterCat));
+
+static cl::opt<std::string>
+    UseCoverage("use-gisel-coverage", cl::init(LLVM_GISEL_COV_PREFIX),
+                cl::desc("Use coverage information for GlobalISel"));
+
 namespace {
 //===- Helper functions ---------------------------------------------------===//
 
 
 /// Get the name of the enum value used to number the predicate function.
 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
   return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
          Predicate.getFnName();
protected:
 
   typedef std::tuple<Record *, unsigned, unsigned>
       DefinedComplexPatternSubOperand;
   typedef StringMap<DefinedComplexPatternSubOperand>
       DefinedComplexPatternSubOperandMap;
   /// A map of Symbolic Names to ComplexPattern sub-operands.
   DefinedComplexPatternSubOperandMap ComplexSubOperands;
 
+  uint64_t RuleID;
+  static uint64_t NextRuleID;
+
 public:
   RuleMatcher(ArrayRef<SMLoc> SrcLoc)
       : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
         DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
-        NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands() {}
+        NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
+        RuleID(NextRuleID++) {}
   RuleMatcher(RuleMatcher &&Other) = default;
   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 
+  uint64_t getRuleID() const { return RuleID; }
+
   InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
   void addRequiredFeature(Record *Feature);
   const std::vector<Record *> &getRequiredFeatures() const;
 
   template <class Kind, class... Args> Kind &addAction(Args &&... args);
   template <class Kind, class... Args>
   action_iterator insertAction(action_iterator InsertPt, Args &&... args);
 
public:
 
   // FIXME: Remove this as soon as possible
   InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
 
   unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
   unsigned allocateTempRegID() { return NextTempRegID++; }
 };
 
+uint64_t RuleMatcher::NextRuleID = 0;
+
 using action_iterator = RuleMatcher::action_iterator;
 
 template <class PredicateTy> class PredicateListMatcher {
 private:
   typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
   PredicateVec Predicates;
 
   /// Template instantiations should specialize this to return a string to use
for (const auto &InsnID : InsnIDs) {
       //          It's not always safe to sink %0 across control flow. In this
       //          case it may introduce a memory fault. We currentl handle this
       //          by rejecting all loads.
     }
   }
 
   for (const auto &MA : Actions)
     MA->emitActionOpcodes(Table, *this);
+
+  if (GenerateCoverage)
+    Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
+          << MatchTable::LineBreak;
+
   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
         << MatchTable::Label(LabelID);
 }
 
 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
   // Rules involving more match roots have higher priority.
   if (Matchers.size() > B.Matchers.size())
     return true;
private:
   /// Keep track of the equivalence between ComplexPattern's and
   /// GIComplexOperandMatcher. Map entries are specified by subclassing
   /// GIComplexPatternEquiv.
   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
 
   // Map of predicates to their subtarget features.
   SubtargetFeatureInfoMap SubtargetFeatures;
 
+  // Rule coverage information.
+  Optional<CodeGenCoverage> RuleCoverage;
+
   void gatherNodeEquivs();
   Record *findNodeEquiv(Record *N) const;
 
   Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
   Expected<InstructionMatcher &> createAndImportSelDAGMatcher(
       RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
       const TreePatternNode *Src, unsigned &TempOpIdx) const;
   Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
OS << "static InstructionSelector::" << TypeIdentifier
      << "ImmediatePredicateFn " << TypeIdentifier << "ImmPredicateFns[] = {\n"
      << "  nullptr,\n";
   for (const auto *Record : MatchedRecords)
     OS << "  Predicate_" << Record->getName() << ",\n";
   OS << "};\n";
 }
 
 void GlobalISelEmitter::run(raw_ostream &OS) {
+  if (!UseCoverage.empty()) {
+    RuleCoverage = CodeGenCoverage();
+    auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverage);
+    if (!RuleCoverageBufOrErr) {
+      PrintWarning(SMLoc(), "Missing rule coverage data");
+      RuleCoverage = None;
+    } else {
+      if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
+        PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
+        RuleCoverage = None;
+      }
+    }
+  }
+
   // Track the GINodeEquiv definitions.
   gatherNodeEquivs();
 
   emitSourceFileHeader(("Global Instruction Selector for the " +
                        Target.getName() + " target").str(), OS);
   std::vector<RuleMatcher> Rules;
   // Look through the SelectionDAG patterns we found, possibly emitting some.
   for (const PatternToMatch &Pat : CGP.ptms()) {
     ++NumPatternTotal;
     auto MatcherOrErr = runOnPattern(Pat);
 
     // The pattern analysis can fail, indicating an unsupported pattern.
     // Report that if we've been asked to do so.
     if (auto Err = MatcherOrErr.takeError()) {
       if (WarnOnSkippedPatterns) {
         PrintWarning(Pat.getSrcRecord()->getLoc(),
                      "Skipped pattern: " + toString(std::move(Err)));
       } else {
         consumeError(std::move(Err));
       }
       ++NumPatternImportsSkipped;
       continue;
     }
 
+    if (RuleCoverage) {
+      if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
+        ++NumPatternsTested;
+      else
+        PrintWarning(Pat.getSrcRecord()->getLoc(),
+                     "Pattern is not covered by a test");
+    }
     Rules.push_back(std::move(MatcherOrErr.get()));
   }
 
   std::stable_sort(Rules.begin(), Rules.end(),
             [&](const RuleMatcher &A, const RuleMatcher &B) {
               if (A.isHigherPriorityThan(B)) {
                 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
                                                      "and less important at "
OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
      << "  nullptr, // GICP_Invalid\n";
   for (const auto &Record : ComplexPredicates)
     OS << "  &" << Target.getName()
        << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
        << ", // " << Record->getName() << "\n";
   OS << "};\n\n";
 
   OS << "bool " << Target.getName()
-     << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
+     << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
+        "&CoverageInfo) const {\n"
      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
      << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
      << "  // FIXME: This should be computed on a per-function basis rather "
         "than per-insn.\n"
      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
         "&MF);\n"
      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
      << "  NewMIVector OutMIs;\n"
      << "  State.MIs.clear();\n"
      << "  State.MIs.push_back(&I);\n\n";
 
   MatchTable Table(0);
   for (auto &Rule : Rules) {
     Rule.emit(Table);
     ++NumPatternEmitted;
   }
   Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
   Table.emitDeclaration(OS);
   OS << "  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, ";
   Table.emitUse(OS);
-  OS << ", TII, MRI, TRI, RBI, AvailableFeatures)) {\n"
+  OS << ", TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {\n"
      << "    return true;\n"
      << "  }\n\n";
 
   OS << "  return false;\n"
      << "}\n"
      << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
 
   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"

utils/llvm-gisel-cov.py

+#!/usr/bin/env python
+
+import argparse
+import struct
+
+class FileFormatError(Exception):
+  pass
+
+def backend_int_pair(s):
+  backend, sep, value = s.partition('=')
+  if (sep is None):
+    raise argparse.ArgumentTypeError("'=' missing, expected name=value")
+  if (not backend):
+    raise argparse.ArgumentTypeError("Expected name=value")
+  if (not value):
+    raise argparse.ArgumentTypeError("Expected name=value")
+  return backend, int(value)
+
+def main():
+  parser = argparse.ArgumentParser(description=__doc__)
+  parser.add_argument('input', nargs='+')
+  parser.add_argument('--num-rules', type=backend_int_pair, action='append')
+  args = parser.parse_args()
+
+  covered_rules = {}
+
+  for input_filename in args.input:
+    with open(input_filename, 'rb') as input_fh:
+      data = input_fh.read()
+      pos = 0
+      while data:
+        backend, _, data = data.partition('\0')
+        pos += len(backend)
+        pos += 1
+
+        if len(backend) == 0:
+          raise FileFormatError()
+        backend, = struct.unpack("%ds" % len(backend), backend)
+
+        while data:
+          if len(data) < 8:
+            raise FileFormatError()
+          rule_id, = struct.unpack("Q", data[:8])
+          pos += 8
+          data = data[8:]
+          if rule_id == (2 ** 64) - 1:
+            break
+          covered_rules[backend] = covered_rules.get(backend, {})
+          covered_rules[backend][rule_id] = covered_rules[backend].get(rule_id, 0) + 1
+
+  num_rules = dict(args.num_rules)
+  for backend, rules_for_backend in covered_rules.items():
+    if backend in num_rules:
+      print "%s: %3.2f%% of rules covered" % (backend, (float(len(rules_for_backend.keys())) / num_rules[backend]) * 100)
+    else:
+      print "%s: %d rules covered" % (backend, len(rules_for_backend.keys()))
+
+if __name__ == '__main__':
+  main()