[llvm-cov] Multi-threaded implementation of prepareFileReports method.

[Dor1s]

Summary

Local testing has demonstrated a great speed improvement, compare the following:

1. Existing version:

$ time llvm-cov show -format=html -output-dir=report -instr-profile=... ...
The tool has been launched:                            00:00:00
Loading coverage data:                                 00:00:00
Get unique source files:                               00:00:33
Creating an index out of the source files:             00:00:34
Going into prepareFileReports:                         00:00:34
Going to emit summary information for each file:       00:28:55 <-- 28:21 min!
Going to emit links to files with no function:         00:28:55
Launching 32 threads for generating HTML files:        00:28:55

real  37m43.651s
user  112m5.540s
sys   7m39.872s

2. Multi-threaded version with 32 CPUs:

$ time llvm-cov show -format=html -output-dir=report -instr-profile=... ...
The tool has been launched:                            00:00:00
Loading coverage data:                                 00:00:00
Get unique source files:                               00:00:38
Creating an index out of the source files:             00:00:40
Going into prepareFileReports:                         00:00:40
Preparing file reports using 32 threads:               00:00:40
# Creating thread tasks for the following number of files: 16422
Going to emit summary information for each file:       00:01:57 <-- 1:17 min!
Going to emit links to files with no function:         00:01:58
Launching 32 threads for generating HTML files:        00:01:58

real  11m2.044s
user  134m48.124s
sys   7m53.388s

[Dor1s]

Another local version, that one seems to work...

[Dor1s]

Some initial clean up, remove unnecessary code.

[Dor1s]

More clean up.

[Dor1s]

Removing more unnecessary code and rename an argument

[Dor1s]

Remove another racy component

[vsk]

Nice!

For a test, I suggest creating a report for >1 files with/without threading, and asserting that the reports are identical. It would be good to exercise the new summary aggregation logic by including different instantiations of the same template function in >1 files.

tools/llvm-cov/CoverageReport.cpp

365

IIUC, PartialTotals should contain exactly the same results as the FileReports vector after Pool.wait(). Why not get rid of it?

376

clang-format?

tools/llvm-cov/CoverageReport.h

48

Since StringRef is immutable and cheap to copy, could you pass it by value?

tools/llvm-cov/CoverageSummaryInfo.h

181

I don't think we should make it possible to create file summaries with empty names. Was this introduced so the std::vector could default-initialize FileCoverageSummary? If so, would make_unique<FileCoverageSummary[]>(N) suffice as an alternative?

186

If we stipulate that file summaries have valid names, we could avoid a bit of this complexity.

[Dor1s]

Thanks for the comments, Vedant! I have some questions now :)

tools/llvm-cov/CoverageReport.cpp

365

You're certainly right, thanks for catching!

tools/llvm-cov/CoverageSummaryInfo.h

181

Yes :( I'm not sure how make_unique may help, e.g. if I do:

auto FileReports = std::make_unique<FileCoverageSummary[]>(Files.size());

It still needs a default constructor. Did you mean llvm::make_unique by any chance? It still looks for an empty constructor though

186

Sure! But we still need to verify that RHS.Name == LHS.Name, right?

[Dor1s]

tools/llvm-cov/CoverageSummaryInfo.h

181

Either way, I found another solution. Let me upload it real quick so you can take a look :)

[Dor1s]

Address review comments

[vsk]

tools/llvm-cov/CoverageSummaryInfo.h

181

Looks good.

186

Right, that can't hurt.

[Dor1s]

tools/llvm-cov/CoverageSummaryInfo.h

186

Wait, I'm stupid... Removing this assert right now.

[Dor1s]

Clean up, will add some tricky test later today or tomorrow

[Dor1s]

Added the test, but other tests seem to be failing on my machine, updating my checkout now

[Dor1s]

Interesting. Actually, the new test seems to work fine, but bunch of others are failing with my change:

Failing Tests (15):
    LLVM :: tools/llvm-cov/binary-formats.c
    LLVM :: tools/llvm-cov/dir-with-filtering.test
    LLVM :: tools/llvm-cov/load-multiple-objects.test
    LLVM :: tools/llvm-cov/multiple-files.test
    LLVM :: tools/llvm-cov/multiple-objects.test
    LLVM :: tools/llvm-cov/prevent_false_instantiations.h
    LLVM :: tools/llvm-cov/report.cpp
    LLVM :: tools/llvm-cov/showExpansions.cpp
    LLVM :: tools/llvm-cov/showHighlightedRanges.cpp
    LLVM :: tools/llvm-cov/showLineExecutionCounts.cpp
    LLVM :: tools/llvm-cov/showRegionMarkers.cpp
    LLVM :: tools/llvm-cov/showTemplateInstantiations.cpp
    LLVM :: tools/llvm-cov/sources-specified.test
    LLVM :: tools/llvm-cov/universal-binary.c
    LLVM :: tools/llvm-cov/zeroFunctionFile.c

  Expected Passes    : 21
  Unsupported Tests  : 1
  Unexpected Failures: 15

with the following crash:

terminate called after throwing an instance of 'std::system_error'
  what():  Resource temporarily unavailable
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x47e81a]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x47cb1e]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x47cc5a]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x10330)[0x7ff4e2fb5330]
/lib/x86_64-linux-gnu/libc.so.6(gsignal+0x37)[0x7ff4e1fb0c37]
/lib/x86_64-linux-gnu/libc.so.6(abort+0x148)[0x7ff4e1fb4028]
/usr/lib/x86_64-linux-gnu/libstdc++.so.6(_ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x155)[0x7ff4e28bf535]
/usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x5e6d6)[0x7ff4e28bd6d6]
/usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x5e703)[0x7ff4e28bd703]
/usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x5e922)[0x7ff4e28bd922]
/usr/lib/x86_64-linux-gnu/libstdc++.so.6(_ZSt20__throw_system_errori+0x80)[0x7ff4e290f800]
/usr/lib/x86_64-linux-gnu/libstdc++.so.6(_ZNSt6thread15_M_start_threadESt10shared_ptrINS_10_Impl_baseEE+0x248)[0x7ff4e2910d68]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x461b55]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x434f16]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x435b37]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x4368d8]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x436aff]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x424c2b]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x42555b]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x40dd57]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf5)[0x7ff4e1f9bf45]
/usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov[0x412567]
Stack dump:
0.	Program arguments: /usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov /usr/local/google/home/mmoroz/Projects/llvm/build/bin/llvm-cov report /usr/local/google/home/mmoroz/Projects/llvm/llvm/test/tools/llvm-cov/Inputs/report.covmapping -instr-profile /usr/local/google/home/mmoroz/Projects/llvm/llvm/test/tools/llvm-cov/Inputs/report.profdata -path-equivalence=/tmp,/usr/local/google/home/mmoroz/Projects/llvm/llvm/test/tools/llvm-cov -show-region-summary -show-instantiation-summary 
Aborted (core dumped)

I've certainly broken something, will debug.

[Dor1s]

Now only one test is failing, continue debugging.

[Dor1s]

Woohoo, everything works!

[Dor1s]

Minor changes

[Dor1s]

All comments have been addressed + a test have been added.

tools/llvm-cov/CoverageReport.h

53

I don't like having raw pointers here, but I can't get it to work otherwise. The most recent issue I had: Filters were not applied, when I've been using const reference. Once I changed that to a pointer, it started to work. Is there any better pattern of using ThreadPool?

[Dor1s]

Happy New Year and friendly ping, if you guys got back to work already :)

[morehouse]

LGTM, but let Vedant comment since he's more familiar with this code.

tools/llvm-cov/CoverageReport.h

53

This is probably caused by pass-by-reference issues with the std::bind that occurs in the multi-parameter ThreadPool::async. You could try using a lambda that captures the arguments to prepareSingleFileReport and then calls it with those arguments. That should let you use the single-parameter ThreadPool::async and avoid the bind.

Otherwise, pointers work too.

[vsk]

Thanks, LGTM.

tools/llvm-cov/CoverageReport.h

53

Right, ThreadPool will try to make a copy of data pointed-to by a captured reference, which won't compile for the move-only filters. Using pointers here sounds fine.

[Dor1s]

Re-build test files

test/tools/llvm-cov/Inputs/multithreaded_report/abs.h

+template<typename T>
+T abs(T x) {
+  if (x < 0) {
+    return -x;
+  }
+  return x;
+}

test/tools/llvm-cov/Inputs/multithreaded_report/bytes.h

+#include <cmath>
+#include <cstdint>
+
+inline double logarithm(uint8_t v) {
+  return log(v);
+}
+
+bool loopBytes();

test/tools/llvm-cov/Inputs/multithreaded_report/bytes.cc

+#include "abs.h"
+#include "bytes.h"
+#include "pow.h"
+
+bool loopBytes() {
+  uint64_t totalInt = 0;
+  double totalFloat = 0;
+  for (uint8_t i = 1; i != 0; ++i) {
+    double a = logarithm(i);
+    a = abs(a);
+    totalInt += abs(pow(i, static_cast<uint8_t>(a)));
+    totalFloat += pow(static_cast<decltype(a)>(i), a);
+  }
+  return totalInt > totalFloat;
+}

test/tools/llvm-cov/Inputs/multithreaded_report/main.cc

+#include "bytes.h"
+#include "words.h"
+
+int main() {
+  bool result = false;
+  if (loopBytes())
+    result |= true;
+  if (loopWords())
+    result |= true;
+
+  if (result)
+    return 0;
+
+  return result;
+}

test/tools/llvm-cov/Inputs/multithreaded_report/pow.h

+template<typename T>
+T pow(T b, T p) {
+  if (!p)
+    return 1;
+
+  while (--p) {
+    b *= b;
+  }
+
+  return b;
+}

test/tools/llvm-cov/Inputs/multithreaded_report/words.h

+#include <cmath>
+#include <cstdint>
+
+inline double logarithm(uint16_t v) {
+  return log(v);
+}
+
+bool loopWords();

test/tools/llvm-cov/Inputs/multithreaded_report/words.cc

+#include "abs.h"
+#include "bytes.h"
+#include "pow.h"
+
+bool loopWords() {
+  uint64_t totalInt = 0;
+  double totalFloat = 0;
+  for (uint16_t i = 1; i != 0; ++i) {
+    double a = logarithm(i);
+    a = abs(a);
+    totalInt += abs(pow(i, static_cast<uint16_t>(a)));
+    totalFloat += pow(static_cast<decltype(a)>(i), a);
+  }
+  return totalInt > totalFloat;
+}

test/tools/llvm-cov/multithreaded-report.test

+RUN: llvm-cov show -format=html \
+RUN:   -path-equivalence=/tmp,%S/Inputs \
+RUN:   -instr-profile %S/Inputs/multithreaded_report/main.profdata \
+RUN:   %S/Inputs/multithreaded_report/main.covmapping > %t.1.html
+
+RUN: llvm-cov show -format=html -num-threads=10 \
+RUN:   -path-equivalence=/tmp,%S/Inputs \
+RUN:   -instr-profile %S/Inputs/multithreaded_report/main.profdata \
+RUN:   %S/Inputs/multithreaded_report/main.covmapping > %t.2.html
+
+RUN: diff %t.1.html %t.2.html 
+
+Instructions for regenerating the test:
+
+# cd %S/Inputs/multithreaded_report
+
+cp -r . /tmp/multithreaded_report
+
+clang++ -std=c++11 -mllvm -enable-name-compression=false \
+    -fprofile-instr-generate -fcoverage-mapping \
+    /tmp/multithreaded_report/*.cc -o main
+
+LLVM_PROFILE_FILE="main.profraw" ./main
+llvm-profdata merge main.profraw -o main.profdata
+llvm-cov convert-for-testing ./main -o ./main.covmapping
+rm main main.profraw

tools/llvm-cov/CodeCoverage.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/ScopedPrinter.h"
-#include "llvm/Support/Threading.h"
 #include "llvm/Support/ThreadPool.h"
+#include "llvm/Support/Threading.h"
 #include "llvm/Support/ToolOutputFile.h"
 
 #include <functional>
 #include <map>
 #include <system_error>
 
 using namespace llvm;
 using namespace coverage;
int CodeCoverageTool::show(int argc, const char **argv,
   ViewOpts.ShowLineStats = ShowLineExecutionCounts.getNumOccurrences() != 0 ||
                            !ShowRegions || ShowBestLineRegionsCounts;
   ViewOpts.ShowRegionMarkers = ShowRegions || ShowBestLineRegionsCounts;
   ViewOpts.ShowExpandedRegions = ShowExpansions;
   ViewOpts.ShowFunctionInstantiations = ShowInstantiations;
   ViewOpts.ShowOutputDirectory = ShowOutputDirectory;
   ViewOpts.TabSize = TabSize;
   ViewOpts.ProjectTitle = ProjectTitle;
+  ViewOpts.NumThreads = NumThreads;
 
   if (ViewOpts.hasOutputDirectory()) {
     if (auto E = sys::fs::create_directories(ViewOpts.ShowOutputDirectory)) {
       error("Could not create output directory!", E.message());
       return 1;
     }
   }
 

tools/llvm-cov/CoverageReport.h

public:
 
   /// Prepare file reports for the files specified in \p Files.
   static std::vector<FileCoverageSummary>
   prepareFileReports(const coverage::CoverageMapping &Coverage,
                      FileCoverageSummary &Totals, ArrayRef<std::string> Files,
                      const CoverageViewOptions &Options,
                      const CoverageFilter &Filters = CoverageFiltersMatchAll());
 
+  static void
+  prepareSingleFileReport(const StringRef &Filename,
+                          const coverage::CoverageMapping *Coverage,
+                          const CoverageViewOptions &Options,
+                          const unsigned LCP,
+                          FileCoverageSummary *FileReport,
+                          const CoverageFilter &Filters);
+
   /// Render file reports for every unique file in the coverage mapping.
   void renderFileReports(raw_ostream &OS) const;
 
   /// Render file reports for the files specified in \p Files.
   void renderFileReports(raw_ostream &OS, ArrayRef<std::string> Files) const;
 
   /// Render file reports for the files specified in \p Files and the functions
   /// in \p Filters.
   void renderFileReports(raw_ostream &OS, ArrayRef<std::string> Files,
                          const CoverageFiltersMatchAll &Filters) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_COV_COVERAGEREPORT_H

tools/llvm-cov/CoverageReport.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "CoverageReport.h"
 #include "RenderingSupport.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/ThreadPool.h"
+#include "llvm/Support/Threading.h"
 #include <numeric>
 
 using namespace llvm;
 
 namespace {
 
 /// \brief Helper struct which prints trimmed and aligned columns.
 struct Column {
for (StringRef Filename : Files) {
     if (Totals.ExecutionCount) {
       renderDivider(FunctionReportColumns, OS);
       OS << "\n";
       render(Totals, DC, OS);
     }
   }
 }
 
-std::vector<FileCoverageSummary> CoverageReport::prepareFileReports(
-    const coverage::CoverageMapping &Coverage, FileCoverageSummary &Totals,
-    ArrayRef<std::string> Files, const CoverageViewOptions &Options,
-    const CoverageFilter &Filters) {
-  std::vector<FileCoverageSummary> FileReports;
-  unsigned LCP = getRedundantPrefixLen(Files);
-
-  for (StringRef Filename : Files) {
-    FileCoverageSummary Summary(Filename.drop_front(LCP));
-
-    for (const auto &Group : Coverage.getInstantiationGroups(Filename)) {
-      std::vector<FunctionCoverageSummary> InstantiationSummaries;
-      for (const coverage::FunctionRecord *F : Group.getInstantiations()) {
-        if (!Filters.matches(Coverage, *F))
-          continue;
-        auto InstantiationSummary = FunctionCoverageSummary::get(Coverage, *F);
-        Summary.addInstantiation(InstantiationSummary);
-        Totals.addInstantiation(InstantiationSummary);
-        InstantiationSummaries.push_back(InstantiationSummary);
-      }
-      if (InstantiationSummaries.empty())
-        continue;
+void CoverageReport::prepareSingleFileReport(const StringRef &Filename,
+    const coverage::CoverageMapping *Coverage,
+    const CoverageViewOptions &Options, const unsigned LCP,
+    FileCoverageSummary *FileReport, const CoverageFilter &Filters) {
+  for (const auto &Group : Coverage->getInstantiationGroups(Filename)) {
+      if (!Filters.matches(*Coverage, *F))
+      auto InstantiationSummary = FunctionCoverageSummary::get(*Coverage, *F);
+      FileReport->addInstantiation(InstantiationSummary);
 
-      auto GroupSummary =
-          FunctionCoverageSummary::get(Group, InstantiationSummaries);
 
-      if (Options.Debug)
-        outs() << "InstantiationGroup: " << GroupSummary.Name << " with "
-               << "size = " << Group.size() << "\n";
 
-      Summary.addFunction(GroupSummary);
-      Totals.addFunction(GroupSummary);
-    }
+    FileReport->addFunction(GroupSummary);
+}
+
+std::vector<FileCoverageSummary> CoverageReport::prepareFileReports(
+    const coverage::CoverageMapping &Coverage, FileCoverageSummary &Totals,
+    ArrayRef<std::string> Files, const CoverageViewOptions &Options,
+    const CoverageFilter &Filters) {
+  unsigned LCP = getRedundantPrefixLen(Files);
+  auto NumThreads = Options.NumThreads;
+
+  // If NumThreads is not specified, auto-detect a good default.
+  if (NumThreads == 0)
+    NumThreads =
+        std::max(1U, std::min(llvm::heavyweight_hardware_concurrency(),
+                              unsigned(Files.size())));
 
-    FileReports.push_back(Summary);
+  ThreadPool Pool(NumThreads);
+
+  std::vector<FileCoverageSummary> FileReports;
+  FileReports.reserve(Files.size());
+
+  for (StringRef Filename : Files) {
+    FileReports.emplace_back(Filename.drop_front(LCP));
+    Pool.async(&CoverageReport::prepareSingleFileReport, Filename,
+               &Coverage, Options, LCP, &FileReports.back(), Filters);
   }
+  Pool.wait();
+
+  for (const auto &FileReport : FileReports)
+    Totals += FileReport;
 
   return FileReports;
 }
 
 void CoverageReport::renderFileReports(raw_ostream &OS) const {
   std::vector<std::string> UniqueSourceFiles;
   for (StringRef SF : Coverage.getUniqueSourceFiles())
     UniqueSourceFiles.emplace_back(SF.str());

tools/llvm-cov/CoverageSummaryInfo.h

class FunctionCoverageInfo {
   size_t NumFunctions;
 
 public:
   FunctionCoverageInfo() : Executed(0), NumFunctions(0) {}
 
   FunctionCoverageInfo(size_t Executed, size_t NumFunctions)
       : Executed(Executed), NumFunctions(NumFunctions) {}
 
+  FunctionCoverageInfo &operator+=(const FunctionCoverageInfo &RHS) {
+    Executed += RHS.Executed;
+    NumFunctions += RHS.NumFunctions;
+    return *this;
+  }
+
   void addFunction(bool Covered) {
     if (Covered)
       ++Executed;
     ++NumFunctions;
   }
 
   size_t getExecuted() const { return Executed; }
 

 /// \brief A summary of file's code coverage.
 struct FileCoverageSummary {
   StringRef Name;
   RegionCoverageInfo RegionCoverage;
   LineCoverageInfo LineCoverage;
   FunctionCoverageInfo FunctionCoverage;
   FunctionCoverageInfo InstantiationCoverage;
 
   FileCoverageSummary(StringRef Name)
       : Name(Name), RegionCoverage(), LineCoverage(), FunctionCoverage(),
         InstantiationCoverage() {}
 
+  FileCoverageSummary &operator+=(const FileCoverageSummary &RHS) {
+    RegionCoverage += RHS.RegionCoverage;
+    LineCoverage += RHS.LineCoverage;
+    FunctionCoverage += RHS.FunctionCoverage;
+    InstantiationCoverage += RHS.InstantiationCoverage;
+    return *this;
+  }
+
   void addFunction(const FunctionCoverageSummary &Function) {
     RegionCoverage += Function.RegionCoverage;
     LineCoverage += Function.LineCoverage;
     FunctionCoverage.addFunction(/*Covered=*/Function.ExecutionCount > 0);
   }
 
   void addInstantiation(const FunctionCoverageSummary &Function) {
     InstantiationCoverage.addFunction(/*Covered=*/Function.ExecutionCount > 0);

tools/llvm-cov/CoverageViewOptions.h

struct CoverageViewOptions {
   bool ShowInstantiationSummary;
   bool ExportSummaryOnly;
   OutputFormat Format;
   std::string ShowOutputDirectory;
   std::vector<std::string> DemanglerOpts;
   uint32_t TabSize;
   std::string ProjectTitle;
   std::string CreatedTimeStr;
+  unsigned NumThreads;
 
   /// \brief Change the output's stream color if the colors are enabled.
   ColoredRawOstream colored_ostream(raw_ostream &OS,
                                     raw_ostream::Colors Color) const {
     return llvm::colored_ostream(OS, Color, Colors);
   }
 
   /// \brief Check if an output directory has been specified.