sancov -not-covered-functions.

[aizatsky]

Summary

The command prints out list of functions that were not entered.

[aizatsky]

nits

[krasin]

First bunch of comments from Friday. Will add more later.

tools/sancov/sancov.cc

63

LLVM tools use flags (with a notable exception of llvm-dwarfdump) with a dash instead of an underscore.
Please rename the flag to --not-covered-functions, and also do the same with --covered-functions.

95–106

Ditto, exit(1)

95–106

Why not exit(1)? LLVM tools use 1 as the exit code in case of an error:

ag "exit[(]1[)]" tools | wc -l
109

There's 3 python scripts which violate that, but otherwise the rule is followed pretty much everywhere.

442–453

Please fix the comment: "Print list of not covered functions".

444

Per LLVM style guide: http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

Variable names should be nouns (as they represent state). The name should be camel case, and start with an upper case letter (e.g. Leader or Boats).

Please, change everywhere (except main)

[aizatsky]

review

[krasin]

tools/sancov/sancov.cc

344

What if some file names are in /usr/include? This could happen if some of the functions are inlined from a system header.

[aizatsky]

All done. PTAL

[aizatsky]

nit

[krasin]

tools/sancov/sancov.cc

157

FailIfError, as implemented right now, drops the context in which it occurred. I would expect something like:

Error: The end of the file was unexpectedly encountered (4)

Please, add an additional string param (like Message) and print it into stderr. In this case the invocation will be like

FailIfError("symbolizeInlinedCode: " + ClBinaryName, InliningInfo);

and the error message will suddenly become much more useful:

Error: symbolizeInlinedCode: lala.o: The end of the file was unexpectedly encountered (4)

Note: feel free to improve the actual error message format. The point is to have all the needed data points in the error message. Otherwise, we'll waste our own time later.

[pcc]

lib/Object/ObjectFile.cpp

118

I'd probably prefer if this function returned a Target * to reflect the fact that it isn't really supposed to (nor can it) return an accurate triple but rather something that can be used to summon appropriate bits of MC etc.

[krasin]

tools/sancov/sancov.cc

157

You may also consider to have a macro instead of a function, as it would allow to preserve the code of line. See for example: https://github.com/llvm-mirror/llvm/blob/358918e8dd375e41b4f51e7570a57e123b2951c6/unittests/Support/Path.cpp#L31

The macro in the example is gtest-specific, but it still gives an idea.

227

Why is lookupTarget error critical, while an error in createMCSubtargetInfo is not?

249

Please, remove this empty line. There's no empty line in the similar places above.

262

Could createMCInstrAnalysis fail? If yes, please, add error handling as you did above.

267

A comment why do we skip virtual .text sections is appreated.

275

The more I think, the more it looks to me that an assert or CHECK should be used here. The problem is that asserts are disabled in some environments, and it would be unwise to proceed here.

295

Please, add a better TODO description (if you wish to address some issue here later)

296

A comment about the way you compute this address is appreciated.

347

What happens if you only have a single file? I have a feeling that the file name will be printed as an empty string.

[samsonov]

Mostly fine, several nits below (in addition to Ivan's comments).

I don't quite agree on the change to LLVMObject, that method looks somewhat weird to me. We can probably discuss that separately: for now you seem to only support x86_64-linux anyway.

lib/Object/ObjectFile.cpp

118

Agree: you can't rely deduce triple from object file. At the very least, you should reflect that you're guessing the triple in method name.

tools/sancov/sancov.cc

102

nit: please use "static" keyword consistently: it's not really needed for functions, as they are enclosed in anonymous namespace, but if you're willing to keep it - keep it everywhere.

136

Nit: LLVM tends to use RHS variant (as it's an abbreviation).

$ grep -rnH "RHS" lib/* | wc -l
10263
$ grep -rnH "Rhs" lib/* | wc -l
4

210

llvm_unreachable()

352

TBH I don't understand the rationale behind stripping (calculated) common prefix. I can construct weird examples, e.g. imagine I have built my executable from /tmp/a.cc with function foo() and /tmp2/a.cc with function foo(). Suppose I suspect that when I ran my executable only one was executed. I call llvm-cov my.exe and see

a.cc:1 foo()

Well, thanks :)

358

Just FYI: file names may contain colons, as well as spaces. It's probably not a big deal, but just note that the output of llvm-cov might be not machine-readable.

411

return llvm::make_unique<CoverageData>(std::move(Addrs));

439

Just *Addrs

493

Add llvm_unreachable() at the end?

[pcc]

lib/Object/ObjectFile.cpp

118

Actually it seems that since the MC constructors use the target triple string we should return a triple string here at least for now.

[aizatsky]

review

[aizatsky]

ptal

lib/Object/ObjectFile.cpp

118

Sorry, can't do. Triple name is used to obtain various pieces of MC.
Plus target lookup changes Triple object (!). That's why I can't simply return std::string instead of Triple here. I've added the clarifying comment to the .h files about the function.

tools/sancov/sancov.cc

157

This doesn't seem to be the way things are done in llvm tools. I'd keep it as is if you don't mind.

267

I have no idea. This is how it is in objdump. Do you know why?

347

It won't see the if (FileName.size() > FilePrefix.size()) below.

[aizatsky]

ptal

lib/Object/ObjectFile.cpp

118

I don't feel attached to it. If you'd rather see me copy this code - I'm fine.

tools/sancov/sancov.cc

411

can't do because CoverageData constructor is private.

493

again, why?

[aizatsky]

review

[samsonov]

lib/Object/ObjectFile.cpp

118

Yeah, let's copy the code, and remove the cases we don't really support yet (MachO/COFF).

tools/sancov/sancov.cc

493

See http://llvm.org/docs/CodingStandards.html#don-t-use-default-labels-in-fully-covered-switches-over-enumerations
Also, it serves as an annotation that you're not supposed to exit from switch.

[aizatsky]

review

[aizatsky]

ptal

[samsonov]

LGTM, passing this back to Ivan.

[krasin]

tools/sancov/sancov.cc

157

Can you please give me examples of that in llvm tools?

267

No I don't. Please, at least, add a comment that the code was stolen from objdump. Please, give a more precise location, so that it would be possible to lookup later for a reader that is not you or me.

365

I also think that it's not the right feature. If we want strip prefixes, that should be a flag that specifies the prefix, not auto-magic.

[aizatsky]

extracted path::common_prefix.

[aizatsky]

I have extracted path::common_prefix for all of you nitpickers :P

[aizatsky]

removed common path functionality.

[aizatsky]

I removed common path functionality and implemented strip_path_prefix flag instead. PTAL.

[krasin]

Please, mark the comments which are addressed as done. It will make it
easier to follow the review.

[aizatsky]

nit

[aizatsky]

Submitted in http://reviews.llvm.org/rL254742

include/llvm/Object/ObjectFile.h

 // This file declares a file format independent ObjectFile class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_OBJECT_OBJECTFILE_H
 #define LLVM_OBJECT_OBJECTFILE_H
 
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Triple.h"
 #include "llvm/Object/SymbolicFile.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <cstring>
 #include <vector>
 
public:
   }
 
   /// @brief The number of bytes used to represent an address in this object
   ///        file format.
   virtual uint8_t getBytesInAddress() const = 0;
 
   virtual StringRef getFileFormatName() const = 0;
   virtual /* Triple::ArchType */ unsigned getArch() const = 0;
+  Triple getTriple() const;
 
   /// Returns platform-specific object flags, if any.
   virtual std::error_code getPlatformFlags(unsigned &Result) const {
     Result = 0;
     return object_error::invalid_file_type;
   }
 
   /// True if this is a relocatable object (.o/.obj).

lib/Object/ObjectFile.cpp

ObjectFile::createObjectFile(StringRef ObjectPath) {
   ErrorOr<std::unique_ptr<ObjectFile>> ObjOrErr =
       createObjectFile(Buffer->getMemBufferRef());
   if (std::error_code EC = ObjOrErr.getError())
     return EC;
   std::unique_ptr<ObjectFile> Obj = std::move(ObjOrErr.get());
 
   return OwningBinary<ObjectFile>(std::move(Obj), std::move(Buffer));
 }
+
+Triple ObjectFile::getTriple() const {
+  llvm::Triple TheTriple("unknown-unknown-unknown");
+
+  TheTriple.setArch(Triple::ArchType(getArch()));
+  // TheTriple defaults to ELF, and COFF doesn't have an environment:
+  // the best we can do here is indicate that it is mach-o.
+  if (isMachO())
+    TheTriple.setObjectFormat(Triple::MachO);
+
+  if (isCOFF() && getArch() == Triple::thumb)
+    TheTriple.setTriple("thumbv7-windows");
+
+  return TheTriple;
+}

test/tools/sancov/not_covered_functions.test

+REQUIRES: x86_64-linux
+RUN: sancov -obj %p/Inputs/test-linux_x86_64 -not_covered_functions %p/Inputs/test-linux_x86_64.sancov | FileCheck %s
+RUN: sancov -obj %p/Inputs/test-linux_x86_64 -not_covered_functions %p/Inputs/test-linux_x86_64-1.sancov | FileCheck --check-prefix=CHECK1 --allow-empty %s
+
+CHECK: Inputs{{[/\\]}}foo.cpp:5 foo()
+CHECK1-NOT: {{.}}*
+

tools/llvm-objdump/llvm-objdump.cpp

static void report_error(StringRef File, std::error_code EC) {
   errs() << ToolName << ": '" << File << "': " << EC.message() << ".\n";
   exit(1);
 }
 
 static const Target *getTarget(const ObjectFile *Obj = nullptr) {
   // Figure out the target triple.
   llvm::Triple TheTriple("unknown-unknown-unknown");
   if (TripleName.empty()) {
-    if (Obj) {
-      TheTriple.setArch(Triple::ArchType(Obj->getArch()));
-      // TheTriple defaults to ELF, and COFF doesn't have an environment:
-      // the best we can do here is indicate that it is mach-o.
-      if (Obj->isMachO())
-        TheTriple.setObjectFormat(Triple::MachO);
-
-      if (Obj->isCOFF()) {
-        const auto COFFObj = dyn_cast<COFFObjectFile>(Obj);
-        if (COFFObj->getArch() == Triple::thumb)
-          TheTriple.setTriple("thumbv7-windows");
-      }
-    }
+    if (Obj)
+      TheTriple = Obj->getTriple();
   } else
     TheTriple.setTriple(Triple::normalize(TripleName));
 
   // Get the target specific parser.
   std::string Error;
   const Target *TheTarget = TargetRegistry::lookupTarget(ArchName, TheTriple,
                                                          Error);
   if (!TheTarget) {

tools/sancov/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
+  AllTargetsAsmPrinters
+  AllTargetsDescs
+  AllTargetsDisassemblers
+  AllTargetsInfos
   DebugInfoDWARF
   DebugInfoPDB
   Object
   Support
   Symbolize
   )
 
 add_llvm_tool(sancov
   sancov.cc
   )

tools/sancov/sancov.cc

 //===-- sancov.cc --------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a command-line tool for reading and analyzing sanitizer
 // coverage.
 //===----------------------------------------------------------------------===//
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/DebugInfo/Symbolize/Symbolize.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/ObjectFile.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Signals.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <set>
 #include <stdio.h>
 #include <vector>
 
 using namespace llvm;
 
 namespace {
 
 // --------- COMMAND LINE FLAGS ---------
 
-enum ActionType { PrintAction, CoveredFunctionsAction };
+enum ActionType {
+  PrintAction,
+  CoveredFunctionsAction,
+  NotCoveredFunctionsAction
+};
 
 cl::opt<ActionType> Action(
     cl::desc("Action (required)"), cl::Required,
     cl::values(clEnumValN(PrintAction, "print", "Print coverage addresses"),
-               clEnumValN(CoveredFunctionsAction, "covered_functions",
+               clEnumValN(CoveredFunctionsAction, "covered-functions",
                           "Print all covered funcions."),
+               clEnumValN(NotCoveredFunctionsAction, "not-covered-functions",
+                          "Print all not covered funcions."),
                clEnumValEnd));
 
 static cl::list<std::string> ClInputFiles(cl::Positional, cl::OneOrMore,
                                           cl::desc("<filenames...>"));
 
 static cl::opt<std::string>
     ClBinaryName("obj", cl::Required,
                  cl::desc("Path to object file to be symbolized"));

 };
 
 static const uint32_t BinCoverageMagic = 0xC0BFFFFF;
 static const uint32_t Bitness32 = 0xFFFFFF32;
 static const uint32_t Bitness64 = 0xFFFFFF64;
 
 // ---------
 
-template <typename T> static void FailIfError(const ErrorOr<T> &E) {
-  if (E)
+static void FailIfError(std::error_code Error) {
+  if (!Error)
     return;
-
-  auto Error = E.getError();
   errs() << "Error: " << Error.message() << "(" << Error.value() << ")\n";
-  exit(-2);
+  exit(1);
+}
+
+template <typename T> static void FailIfError(const ErrorOr<T> &E) {
+  FailIfError(E.getError());
+}
+
+void FailIfNotEmpty(const std::string &E) {
+  if (E.empty())
+    return;
+  errs() << "Error: " << E << "\n";
+  exit(1);
 }
 
 template <typename T>
 static void readInts(const char *Start, const char *End,
-                     std::vector<uint64_t> *V) {
+                     std::set<uint64_t> *Ints) {
   const T *S = reinterpret_cast<const T *>(Start);
   const T *E = reinterpret_cast<const T *>(End);
-  V->reserve(E - S);
-  std::copy(S, E, std::back_inserter(*V));
+  std::copy(S, E, std::inserter(*Ints, Ints->end()));
 }
 
 static std::string CommonPrefix(std::string A, std::string B) {
   if (A.size() > B.size())
     return std::string(B.begin(),
                        std::mismatch(B.begin(), B.end(), A.begin()).first);
   else
     return std::string(A.begin(),
                        std::mismatch(A.begin(), A.end(), B.begin()).first);
 }
 
+struct FileLoc {
+  bool operator<(const FileLoc &Rhs) const {
+    return std::tie(FileName, Line) < std::tie(Rhs.FileName, Rhs.Line);
+  }
+
+  std::string FileName;
+  uint32_t Line;
+};
+
+struct FunctionLoc {
+  bool operator<(const FunctionLoc &Rhs) const {
+    return std::tie(Loc, FunctionName) < std::tie(Rhs.Loc, Rhs.FunctionName);
+  }
+
+  FileLoc Loc;
+  std::string FunctionName;
+};
+
+// Compute [FileLoc -> FunctionName] map for given addresses.
+static std::map<FileLoc, std::string>
+computeFunctionsMap(const std::set<uint64_t> &Addrs) {
+  std::map<FileLoc, std::string> Fns;
+
+  symbolize::LLVMSymbolizer::Options SymbolizerOptions;
+  SymbolizerOptions.Demangle = ClDemangle;
+  SymbolizerOptions.UseSymbolTable = true;
+  symbolize::LLVMSymbolizer Symbolizer(SymbolizerOptions);
+
+  // Fill in Fns map.
+  for (auto Addr : Addrs) {
+    auto InliningInfo = Symbolizer.symbolizeInlinedCode(ClBinaryName, Addr);
+    FailIfError(InliningInfo);
+    for (uint32_t i = 0; i < InliningInfo->getNumberOfFrames(); ++i) {
+      auto FrameInfo = InliningInfo->getFrame(i);
+      SmallString<256> FileName(FrameInfo.FileName);
+      sys::path::remove_dots(FileName, /* remove_dot_dot */ true);
+      FileLoc Loc = {FileName.str(), FrameInfo.Line};
+      Fns[Loc] = FrameInfo.FunctionName;
+    }
+  }
+
+  return Fns;
+}
+
+// Compute functions for given addresses. It keeps only the first
+// occurence of a function within a file.
+std::set<FunctionLoc> computeFunctionLocs(const std::set<uint64_t> &Addrs) {
+  std::map<FileLoc, std::string> Fns = computeFunctionsMap(Addrs);
+
+  std::set<FunctionLoc> result;
+  std::string LastFileName;
+  std::set<std::string> ProcessedFunctions;
+
+  for (const auto &P : Fns) {
+    std::string FileName = P.first.FileName;
+    std::string FunctionName = P.second;
+
+    if (LastFileName != FileName)
+      ProcessedFunctions.clear();
+    LastFileName = FileName;
+
+    if (!ProcessedFunctions.insert(FunctionName).second)
+      continue;
+
+    result.insert(FunctionLoc{P.first, P.second});
+  }
+
+  return result;
+}
+
+// Locate __sanitizer_cov function address.
+static uint64_t findSanitizerCovFunction(const object::ObjectFile &O) {
+  for (const object::SymbolRef &Symbol : O.symbols()) {
+    ErrorOr<uint64_t> AddressOrErr = Symbol.getAddress();
+    FailIfError(AddressOrErr);
+
+    ErrorOr<StringRef> Name = Symbol.getName();
+    FailIfError(Name);
+
+    if (Name.get() == "__sanitizer_cov") {
+      return AddressOrErr.get();
+    }
+  }
+  FailIfNotEmpty("__sanitizer_cov not found");
+  return 0; // not reachable.
+}
+
+// Locate addresses of all coverage points in a file. Coverage point
+// is defined as the 'address of instruction following __sanitizer_cov
+// call - 1'.
+static void getObjectCoveragePoints(const object::ObjectFile &O,
+                                    std::set<uint64_t> *Addrs) {
+  Triple TheTriple = O.getTriple();
+  auto TripleName = TheTriple.getTriple();
+  std::string Error;
+  const Target *TheTarget = TargetRegistry::lookupTarget(TripleName, Error);
+  FailIfNotEmpty(Error);
+
+  std::unique_ptr<const MCSubtargetInfo> STI(
+      TheTarget->createMCSubtargetInfo(TripleName, "", ""));
+  if (!STI) {
+    errs() << "error: no subtarget info for target " << TripleName << "\n";
+    return;
+  }
+
+  std::unique_ptr<const MCRegisterInfo> MRI(
+      TheTarget->createMCRegInfo(TripleName));
+  if (!MRI) {
+    errs() << "error: no register info for target " << TripleName << "\n";
+    return;
+  }
+
+  std::unique_ptr<const MCAsmInfo> AsmInfo(
+      TheTarget->createMCAsmInfo(*MRI, TripleName));
+  if (!AsmInfo) {
+    errs() << "error: no assembly info for target " << TripleName << "\n";
+    return;
+  }
+
+  std::unique_ptr<const MCObjectFileInfo> MOFI(new MCObjectFileInfo);
+  MCContext Ctx(AsmInfo.get(), MRI.get(), MOFI.get());
+  std::unique_ptr<MCDisassembler> DisAsm(
+      TheTarget->createMCDisassembler(*STI, Ctx));
+
+  if (!DisAsm) {
+    errs() << "error: no disassembler for target " << TripleName << "\n";
+    return;
+  }
+
+  std::unique_ptr<const MCInstrInfo> MII(TheTarget->createMCInstrInfo());
+  if (!MII) {
+    errs() << "error: no instruction info for target " << TripleName << "\n";
+    return;
+  }
+
+  std::unique_ptr<const MCInstrAnalysis> MIA(
+      TheTarget->createMCInstrAnalysis(MII.get()));
+
+  uint64_t SanCovAddr = findSanitizerCovFunction(O);
+
+  for (const auto Section : O.sections()) {
+    if (Section.isVirtual() || !Section.isText())
+      continue;
+    uint64_t SectionAddr = Section.getAddress();
+    uint64_t SectSize = Section.getSize();
+    if (!SectSize)
+      continue;
+
+    StringRef SectionName;
+    FailIfError(Section.getName(SectionName));
+
+    StringRef BytesStr;
+    FailIfError(Section.getContents(BytesStr));
+    ArrayRef<uint8_t> Bytes(reinterpret_cast<const uint8_t *>(BytesStr.data()),
+                            BytesStr.size());
+
+    for (uint64_t Index = 0, Size = 0; Index < Section.getSize();
+         Index += Size) {
+      MCInst Inst;
+      if (!DisAsm->getInstruction(Inst, Size, Bytes.slice(Index),
+                                  SectionAddr + Index, nulls(), nulls())) {
+        if (Size == 0)
+          Size = 1;
+        continue;
+      }
+      uint64_t Target;
+      if (MIA->isCall(Inst) &&
+          MIA->evaluateBranch(Inst, SectionAddr + Index, Size, Target)) {
+        if (Target == SanCovAddr) {
+          // todo
+          Addrs->insert(Index + SectionAddr + Size - 1);
+        }
+      }
+    }
+  }
+}
+
+static void getArchiveCoveragePoints(const object::Archive &A,
+                                     std::set<uint64_t> *Addrs) {
+  for (auto &ErrorOrChild : A.children()) {
+    FailIfError(ErrorOrChild);
+    const object::Archive::Child &C = *ErrorOrChild;
+    ErrorOr<std::unique_ptr<object::Binary>> ChildOrErr = C.getAsBinary();
+    FailIfError(ChildOrErr);
+    if (object::ObjectFile *O =
+            dyn_cast<object::ObjectFile>(&*ChildOrErr.get()))
+      getObjectCoveragePoints(*O, Addrs);
+    else
+      FailIfError(object::object_error::invalid_file_type);
+  }
+}
+
+// Locate addresses of all coverage points in a file. Coverage point
+// is defined as the 'address of instruction following __sanitizer_cov
+// call - 1'.
+std::set<uint64_t> getCoveragePoints(std::string FileName) {
+  std::set<uint64_t> Result;
+
+  ErrorOr<object::OwningBinary<object::Binary>> BinaryOrErr =
+      object::createBinary(FileName);
+  FailIfError(BinaryOrErr);
+
+  object::Binary &Binary = *BinaryOrErr.get().getBinary();
+  if (object::Archive *A = dyn_cast<object::Archive>(&Binary))
+    getArchiveCoveragePoints(*A, &Result);
+  else if (object::ObjectFile *O = dyn_cast<object::ObjectFile>(&Binary))
+    getObjectCoveragePoints(*O, &Result);
+  else
+    FailIfError(object::object_error::invalid_file_type);
+
+  return Result;
+}
+
+static void printFunctionLocs(const std::set<FunctionLoc> &FnLocs,
+                              raw_ostream &OS) {
+  if (FnLocs.empty())
+    return;
+
+  // Compute file names common prefix.
+  std::string FilePrefix = FnLocs.begin()->Loc.FileName;
+  for (const auto &FnLoc : FnLocs)
+    FilePrefix = CommonPrefix(FilePrefix, FnLoc.Loc.FileName);
+
+  if (FilePrefix == "/" || FilePrefix == "\\")
+    FilePrefix = "";
+
+  for (const FunctionLoc &FnLoc : FnLocs) {
+    std::string FileName = FnLoc.Loc.FileName;
+
+    if (FileName.size() > FilePrefix.size())
+      FileName = FileName.substr(FilePrefix.size());
+
+    OS << FileName << ":" << FnLoc.Loc.Line << " " << FnLoc.FunctionName
+        << "\n";
+  }
+}
+
 class CoverageData {
  public:
   // Read single file coverage data.
   static ErrorOr<std::unique_ptr<CoverageData>> read(std::string FileName) {
     ErrorOr<std::unique_ptr<MemoryBuffer>> BufOrErr =
         MemoryBuffer::getFile(FileName);
     if (!BufOrErr)
       return BufOrErr.getError();
     std::unique_ptr<MemoryBuffer> Buf = std::move(BufOrErr.get());
     if (Buf->getBufferSize() < 8) {
       errs() << "File too small (<8): " << Buf->getBufferSize();
       return make_error_code(errc::illegal_byte_sequence);
     }
     const FileHeader *Header =
         reinterpret_cast<const FileHeader *>(Buf->getBufferStart());
 
     if (Header->Magic != BinCoverageMagic) {
       errs() << "Wrong magic: " << Header->Magic;
       return make_error_code(errc::illegal_byte_sequence);
     }
 
-    auto Addrs = llvm::make_unique<std::vector<uint64_t>>();
+    auto Addrs = llvm::make_unique<std::set<uint64_t>>();
 
     switch (Header->Bitness) {
     case Bitness64:
       readInts<uint64_t>(Buf->getBufferStart() + 8, Buf->getBufferEnd(),
                          Addrs.get());
       break;
     case Bitness32:
       readInts<uint32_t>(Buf->getBufferStart() + 8, Buf->getBufferEnd(),
                          Addrs.get());
       break;
     default:
       errs() << "Unsupported bitness: " << Header->Bitness;
       return make_error_code(errc::illegal_byte_sequence);
     }
 
     return std::unique_ptr<CoverageData>(new CoverageData(std::move(Addrs)));
   }
 
   // Merge multiple coverage data together.
   static std::unique_ptr<CoverageData>
   merge(const std::vector<std::unique_ptr<CoverageData>> &Covs) {
-    std::set<uint64_t> Addrs;
+    auto Addrs = llvm::make_unique<std::set<uint64_t>>();
 
     for (const auto &Cov : Covs)
-      Addrs.insert(Cov->Addrs->begin(), Cov->Addrs->end());
+      Addrs->insert(Cov->Addrs->begin(), Cov->Addrs->end());
 
-    auto AddrsVector = llvm::make_unique<std::vector<uint64_t>>(
-        Addrs.begin(), Addrs.end());
-    return std::unique_ptr<CoverageData>(
-        new CoverageData(std::move(AddrsVector)));
+    return std::unique_ptr<CoverageData>(new CoverageData(std::move(Addrs)));
   }
 
   // Read list of files and merges their coverage info.
   static ErrorOr<std::unique_ptr<CoverageData>>
   readAndMerge(const std::vector<std::string> &FileNames) {
     std::vector<std::unique_ptr<CoverageData>> Covs;
     for (const auto &FileName : FileNames) {
       auto Cov = read(FileName);
       if (!Cov)
         return Cov.getError();
       Covs.push_back(std::move(Cov.get()));
     }
     return merge(Covs);
   }
 
   // Print coverage addresses.
-  void printAddrs(raw_ostream &out) {
+  void printAddrs(raw_ostream &OS) {
     for (auto Addr : *Addrs) {
-      out << "0x";
-      out.write_hex(Addr);
-      out << "\n";
+      OS << "0x";
+      OS.write_hex(Addr);
+      OS << "\n";
     }
   }
 
   // Print list of covered functions.
   // Line format: <file_name>:<line> <function_name>
-  void printCoveredFunctions(raw_ostream &out) {
-    if (Addrs->empty())
-      return;
-    symbolize::LLVMSymbolizer::Options SymbolizerOptions;
-    SymbolizerOptions.Demangle = ClDemangle;
-    symbolize::LLVMSymbolizer Symbolizer(SymbolizerOptions);
-
-    struct FileLoc {
-      std::string FileName;
-      uint32_t Line;
-      bool operator<(const FileLoc &Rhs) const {
-        return std::tie(FileName, Line) < std::tie(Rhs.FileName, Rhs.Line);
-      }
-    };
-
-    // FileLoc -> FunctionName
-    std::map<FileLoc, std::string> Fns;
-
-    // Fill in Fns map.
-    for (auto Addr : *Addrs) {
-      auto InliningInfo = Symbolizer.symbolizeInlinedCode(ClBinaryName, Addr);
-      FailIfError(InliningInfo);
-      for (uint32_t i = 0; i < InliningInfo->getNumberOfFrames(); ++i) {
-        auto FrameInfo = InliningInfo->getFrame(i);
-        SmallString<256> FileName(FrameInfo.FileName);
-        sys::path::remove_dots(FileName, /* remove_dot_dot */ true);
-        FileLoc Loc = { FileName.str(), FrameInfo.Line };
-        Fns[Loc] = FrameInfo.FunctionName;
-      }
-    }
-
-    // Compute file names common prefix.
-    std::string FilePrefix = Fns.begin()->first.FileName;
-    for (const auto &P : Fns)
-      FilePrefix = CommonPrefix(FilePrefix, P.first.FileName);
+  void printCoveredFunctions(raw_ostream &OS) {
+    printFunctionLocs(computeFunctionLocs(*Addrs.get()), OS);
 
-    // Print first function occurence in a file.
-    {
-      std::string LastFileName;
-      std::set<std::string> ProcessedFunctions;
-
-      for (const auto &P : Fns) {
-        std::string FileName = P.first.FileName;
-        std::string FunctionName = P.second;
-        uint32_t Line = P.first.Line;
-
-        if (LastFileName != FileName)
-          ProcessedFunctions.clear();
-        LastFileName = FileName;
-
-        if (!ProcessedFunctions.insert(FunctionName).second)
-          continue;
-
-        // Don't strip prefix if we only have a single file.
-        if (FileName.size() > FilePrefix.size())
-          FileName = FileName.substr(FilePrefix.size());
-
-        out << FileName << ":" << Line << " " << FunctionName << "\n";
-      }
-    }
+  // Print list of not covered functions.
+  // Line format: <file_name>:<line> <function_name>
+  void printNotCoveredFunctions(raw_ostream &OS) {
+    std::set<FunctionLoc> AllFns =
+        computeFunctionLocs(getCoveragePoints(ClBinaryName));
+    std::set<FunctionLoc> CoveredFns = computeFunctionLocs(*Addrs);
+
+    std::set<FunctionLoc> NotCoveredFns;
+    std::set_difference(AllFns.begin(), AllFns.end(), CoveredFns.begin(),
+                        CoveredFns.end(),
+                        std::inserter(NotCoveredFns, NotCoveredFns.end()));
+    printFunctionLocs(NotCoveredFns, OS);
   }
 
- private:
-  explicit CoverageData(std::unique_ptr<std::vector<uint64_t>> Addrs)
+  explicit CoverageData(std::unique_ptr<std::set<uint64_t>> Addrs)
       : Addrs(std::move(Addrs)) {}
 
-  std::unique_ptr<std::vector<uint64_t>> Addrs;
+  std::unique_ptr<std::set<uint64_t>> Addrs;
 };
 } // namespace
 
 int main(int argc, char **argv) {
   // Print stack trace if we signal out.
   sys::PrintStackTraceOnErrorSignal();
   PrettyStackTraceProgram X(argc, argv);
   llvm_shutdown_obj Y; // Call llvm_shutdown() on exit.
 
+  llvm::InitializeAllTargetInfos();
+  llvm::InitializeAllTargetMCs();
+  llvm::InitializeAllDisassemblers();
+
   cl::ParseCommandLineOptions(argc, argv, "Sanitizer Coverage Processing Tool");
 
   auto CovData = CoverageData::readAndMerge(ClInputFiles);
   FailIfError(CovData);
 
   switch (Action) {
   case PrintAction: {
     CovData.get()->printAddrs(outs());
     return 0;
   }
   case CoveredFunctionsAction: {
     CovData.get()->printCoveredFunctions(outs());
     return 0;
   }
+  case NotCoveredFunctionsAction: {
+    CovData.get()->printNotCoveredFunctions(outs());
+    return 0;
+  }
   }
 }