clang-misexpect: a standalone tool for verifying the use of __builtin_expect with PGO data

[paulkirth]

Summary

This is a continuation of the work in D66324 that creates a standalone tool that can simply be run over an entire codebase through the use of a compile commands database. This simplifies the need to support custom build targets to check a project's use of __builtin_expect().

The design is fairly straightforward: use a libTooling executor to walk the compilation database, and run the compiler over each target after curating some compiler flags. Mainly, we remove any incompatible flags, and then configure the codegen options to support using the selected type of profile data. We also process the LLVMArgs, as libTooling executors seem to bypass the normal mechanisms for passing flags to the LLVM backend. Other than these few changes we rely on the existing compiler infrastructure to generate our diagnostics.

Currently the use of the CodeGenAction with the libTooling Executor seems to be surfacing some race conditions within the compiler infrastructure. For now I plan to limit the concurrency of the executor to run single threaded, but eventually, I would like to have this run with full parallelism. If a CodeGenAction can never be safely run in parallel, then it may become necessary to use an external driver script, similar to run_clang_tidy.py to take advantage of parallelism.

[nickdesaulniers]

clang-tools-extra/clang-misexpect/tool/ClangMisExpectMain.cpp

34

The using statements here should match clang-tools-extra/clang-misexpect/ClangMisExpect.cpp.

63

accidentally committed?

79–80

I recognize the shorthand, but it seems like it could be created earlier?

90

unnecessary

117

use OS

122

Capture/use OS

[leonardchan]

clang-tools-extra/clang-misexpect/ClangMisExpect.cpp

78

Nit: llvm_unreackable is unneeded since you cover all ProfileKinds here.

[paulkirth]

Address code review

[paulkirth]

Remove commented out code

[paulkirth]

Addresses problems running the standalone tool w/ the libTooling executors.

When using the CodeGenAction and setting LLVM backend options, I found several places where data races occurred. This seems like a more significant architectural issue than mitigating access to a few global variables. To avoid these issues I've locked the executor concurrency to 1, i.e. single threaded. This prevents any data races when the executor is configuring the backends for each compiler invocation.

I've included a python script based on the run-clang-tidy.py that tidy uses. This allows the standalone tool to take advantage of parallellism without running into the data races between threads.

I have also added a new checking mechanism to ensure that PGO profiles and the command line options are compatible.

Lastly, I've included new documentation and tests for the standalone tool.

[lebedev.ri]

Layering feels weird here.
Can this be implemented as/limited to just a
run-clang-misexpect.py wrapper over clang itself?
That would be best IMHO.

[paulkirth]

In D67253#1670569, @lebedev.ri wrote:

Layering feels weird here.
Can this be implemented as/limited to just a
run-clang-misexpect.py wrapper over clang itself?
That would be best IMHO.

I discussed the concurrency issue with some folks who work on libTooling, notably Sam McCall & Dmitri Gribenko. This was the approach they suggested I follow. LibTooling also provides some nice mechanisms for curating compiler options, which is possible, but less than ideal to reimplement in a python script. There are probably more benefits that escape me at the moment, but that was the first one I thought of.

Out of curiosity, if the concurrency issue was fixed in the compiler and the python script was removed/deprecated, would you still feel the same way?

[lebedev.ri]

Re concurrency - you had standalone LLVMContext for each thread, right?

In D67253#1670667, @paulkirth wrote:

In D67253#1670569, @lebedev.ri wrote:

Layering feels weird here.
Can this be implemented as/limited to just a
run-clang-misexpect.py wrapper over clang itself?
That would be best IMHO.

I discussed the concurrency issue with some folks who work on libTooling, notably Sam McCall & Dmitri Gribenko. This was the approach they suggested I follow. LibTooling also provides some nice mechanisms for curating compiler options, which is possible, but less than ideal to reimplement in a python script. There are probably more benefits that escape me at the moment, but that was the first one I thought of.

Out of curiosity, if the concurrency issue was fixed in the compiler and the python script was removed/deprecated, would you still feel the same way?

I was actually talking/thinking about the opposite direction, only having the .py wrapper, no standalone tool;
so the opposite solution (no .py, only the tool) is tangential/has different direction.

clang-tools-extra/docs/clang-misexpect.rst

1–3 ↗

(On Diff #220239)

I was just thinking that i forgot to mention docs in the original review, so thanks.

That being said, i do wonder whether this docs should be reworked
into two separate pages as it is a bit misleading right now.
The bulk of this should talk about
clang's -Wmisexpect/llvm's -pgo-warn-misexpect.

Because right now it seems as-if one has to use the tool,
and as it was brought up in the lists multiple times,
[depending on the exact workflow] that is more involved
than simply passing one more warning flag to the compiler.

(Yes, after specifically looking for it, i can see that
there are mentions/hints that the tool isn't required,
but it's a bit too subtle.)

[paulkirth]

In D67253#1670681, @lebedev.ri wrote:

Re concurrency - you had standalone LLVMContext for each thread, right?

I believe there was, but this is just whatever happens when libtooling creates and executes a compiler invocation. It seems to me that there is some global state that ends up being shared between threads. I wasn’t able to fully trace the issue, but it at least partly involves the processing of backend options. I believe there is more, that needs to be addressed but this is probably a good place for me to start. Thanks for the suggestion.

In D67253#1670667, @paulkirth wrote:

In D67253#1670569, @lebedev.ri wrote:

Layering feels weird here.
Can this be implemented as/limited to just a
run-clang-misexpect.py wrapper over clang itself?
That would be best IMHO.

I discussed the concurrency issue with some folks who work on libTooling, notably Sam McCall & Dmitri Gribenko. This was the approach they suggested I follow. LibTooling also provides some nice mechanisms for curating compiler options, which is possible, but less than ideal to reimplement in a python script. There are probably more benefits that escape me at the moment, but that was the first one I thought of.

Out of curiosity, if the concurrency issue was fixed in the compiler and the python script was removed/deprecated, would you still feel the same way?

I was actually talking/thinking about the opposite direction, only having the .py wrapper, no standalone tool;
so the opposite solution (no .py, only the tool) is tangential/has different direction.

Right, I was asking if you still see this as an issue if the python script wasn’t necessary. I take from this comment that it would not make you feel differently.

I think ultimately keeping the implementation in c++ makes the most sense and can evolve with the rest of libtooling.

[lebedev.ri]

In D67253#1670704, @paulkirth wrote:

In D67253#1670681, @lebedev.ri wrote:

Re concurrency - you had standalone LLVMContext for each thread, right?

I believe there was, but this is just whatever happens when libtooling creates and executes a compiler invocation. It seems to me that there is some global state that ends up being shared between threads. I wasn’t able to fully trace the issue, but it at least partly involves the processing of backend options. I believe there is more, that needs to be addressed but this is probably a good place for me to start. Thanks for the suggestion.

Ah yes, i don't think this can work given existing interface.

In D67253#1670667, @paulkirth wrote:

In D67253#1670569, @lebedev.ri wrote:

Layering feels weird here.
Can this be implemented as/limited to just a
run-clang-misexpect.py wrapper over clang itself?
That would be best IMHO.

I discussed the concurrency issue with some folks who work on libTooling, notably Sam McCall & Dmitri Gribenko. This was the approach they suggested I follow. LibTooling also provides some nice mechanisms for curating compiler options, which is possible, but less than ideal to reimplement in a python script. There are probably more benefits that escape me at the moment, but that was the first one I thought of.

Out of curiosity, if the concurrency issue was fixed in the compiler and the python script was removed/deprecated, would you still feel the same way?

I was actually talking/thinking about the opposite direction, only having the .py wrapper, no standalone tool;
so the opposite solution (no .py, only the tool) is tangential/has different direction.

Right, I was asking if you still see this as an issue if the python script wasn’t necessary. I take from this comment that it would not make you feel differently.

Right. Not really a blocker, just seems counter-general - there already is a
similar script to run clang-tidy on compilation database, and this script/tool
will have the same purpose - to just ran clang -Wmisexpect+profile on compilation database.
It really seems like some generalization is missing.

I think ultimately keeping the implementation in c++ makes the most sense and can evolve with the rest of libtooling.

[lebedev.ri]

Abandon this? D66324 landed.

clang-tools-extra/CMakeLists.txt

 include(CMakeDependentOption)
 
 add_subdirectory(clang-apply-replacements)
 add_subdirectory(clang-reorder-fields)
 add_subdirectory(modularize)
 add_subdirectory(clang-tidy)
+add_subdirectory(clang-misexpect)
 
 add_subdirectory(clang-change-namespace)
 add_subdirectory(clang-doc)
 add_subdirectory(clang-include-fixer)
 add_subdirectory(clang-move)
 add_subdirectory(clang-query)
 add_subdirectory(pp-trace)
 add_subdirectory(tool-template)

clang-tools-extra/clang-misexpect/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_clang_library(clangMisExpect
+  ClangMisExpect.cpp
+
+  LINK_LIBS
+  clangBasic
+  clangCodeGen
+  clangFrontend
+  clangFrontendTool
+  clangTooling
+  clangToolingCore
+  )
+
+add_subdirectory(tool)

clang-tools-extra/clang-misexpect/ClangMisExpect.h

+//===-- ClangMisExpect.h - ClangMisexpect -----------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a method to create the FrontendActionFactory for the
+// clang-misexpect tool. The factory consumes a compilation database and valid
+// profiling data to run the compiler over a codebase and issue warnings
+// generated from the -Wmisexpect compiler flags.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendActions.h"
+#include "clang/Frontend/FrontendDiagnostic.h"
+#include "clang/Frontend/FrontendOptions.h"
+#include "clang/Frontend/TextDiagnosticPrinter.h"
+#include "clang/Rewrite/Frontend/FrontendActions.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/StringRef.h"
+#include <string>
+
+namespace clang {
+namespace misexpect {
+
+enum ProfileKind {
+  Clang,
+  IR,
+  CSIR,
+  Sample,
+};
+
+class MisExpectFactory : public tooling::FrontendActionFactory {
+  using Path = std::string;
+
+public:
+  MisExpectFactory(Path Profile, ProfileKind ProfileType);
+
+  bool runInvocation(std::shared_ptr<CompilerInvocation> Invocation,
+                     FileManager *Files,
+                     std::shared_ptr<PCHContainerOperations> PCHContainerOps,
+                     DiagnosticConsumer *DiagConsumer) override;
+
+  std::unique_ptr<FrontendAction> create() override;
+
+private:
+  Path ProfilePath;
+  ProfileKind ProfileType;
+};
+
+} // namespace misexpect
+} // namespace clang

clang-tools-extra/clang-misexpect/ClangMisExpect.cpp

+//===-- ClangMisExpect.cpp - ClangMisexpect ---------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a method to create the FrontendActionFactory for the
+// clang-misexpect tool. The factory consumes a compilation database and valid
+// profiling data to run the compiler over a codebase and issue warnings
+// generated from the -Wmisexpect compiler flags.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangMisExpect.h"
+#include "clang/Basic/CodeGenOptions.h"
+#include "clang/CodeGen/CodeGenAction.h"
+#include "clang/Frontend/FrontendActions.h"
+#include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/Support/Regex.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace clang;
+using namespace clang::tooling;
+using namespace misexpect;
+
+#define DEBUG_TYPE "misexpect"
+
+MisExpectFactory::MisExpectFactory(Path ProfilePath, ProfileKind ProfileType)
+    : ProfilePath(ProfilePath), ProfileType(ProfileType) {}
+
+std::unique_ptr<FrontendAction> MisExpectFactory::create() {
+  return std::make_unique<EmitLLVMOnlyAction>();
+}
+
+bool MisExpectFactory::runInvocation(
+    std::shared_ptr<CompilerInvocation> Invocation, FileManager *Files,
+    std::shared_ptr<PCHContainerOperations> PCHContainerOps,
+    DiagnosticConsumer *DiagConsumer) {
+  // Only run the compiler through IR generation
+  Invocation->getFrontendOpts().ProgramAction = frontend::EmitLLVMOnly;
+
+  // clear the existing profile flags and metadata
+  Invocation->getCodeGenOpts().setProfileUse(CodeGenOptions::ProfileNone);
+  Invocation->getCodeGenOpts().setProfileInstr(CodeGenOptions::ProfileNone);
+  Invocation->getCodeGenOpts().ProfileInstrumentUsePath = "";
+  Invocation->getCodeGenOpts().SampleProfileFile = "";
+
+  // duplicate the logic in ExecuteCompilerInvocation to process llvm options
+  if (!Invocation->getFrontendOpts().LLVMArgs.empty()) {
+    unsigned NumArgs = Invocation->getFrontendOpts().LLVMArgs.size();
+    auto Args = std::make_unique<const char *[]>(NumArgs + 2);
+    Args[0] = "clang (LLVM option parsing)";
+    for (unsigned i = 0; i != NumArgs; ++i)
+      Args[i + 1] = Invocation->getFrontendOpts().LLVMArgs[i].c_str();
+    Args[NumArgs + 1] = nullptr;
+    llvm::cl::ParseCommandLineOptions(NumArgs + 1, Args.get());
+  }
+
+  // set new profiling options based on profile type
+  switch (ProfileType) {
+  case ProfileKind::Clang:
+    Invocation->getCodeGenOpts().setProfileUse(
+        CodeGenOptions::ProfileClangInstr);
+    break;
+  case ProfileKind::IR:
+    Invocation->getCodeGenOpts().setProfileUse(CodeGenOptions::ProfileIRInstr);
+    break;
+  case ProfileKind::CSIR:
+    Invocation->getCodeGenOpts().setProfileUse(
+        CodeGenOptions::ProfileCSIRInstr);
+    break;
+  case ProfileKind::Sample:
+    Invocation->getCodeGenOpts().SampleProfileFile = ProfilePath;
+    break;
+  };
+
+  if (ProfileType != ProfileKind::Sample)
+    Invocation->getCodeGenOpts().ProfileInstrumentUsePath = ProfilePath;
+
+  return FrontendActionFactory::runInvocation(Invocation, Files,
+                                              PCHContainerOps, DiagConsumer);
+}
+
+#undef DEBUG_TYPE

clang-tools-extra/clang-misexpect/tool/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  AllTargetsAsmParsers
+  AllTargetsDescs
+  AllTargetsInfos
+  support
+  )
+
+add_clang_tool(clang-misexpect
+  ClangMisExpectMain.cpp
+  )
+add_dependencies(clang-misexpect
+  clang-resource-headers
+  )
+target_link_libraries(clang-misexpect
+  PRIVATE
+  clangBasic
+  clangMisExpect
+  clangFrontend
+  clangCodeGen
+  clangTooling
+  clangToolingCore
+  clangToolingSyntax
+  )
+

clang-tools-extra/clang-misexpect/tool/ClangMisExpectMain.cpp

+//===-- ClangMisExpectMain.cpp - ClangMisexpect -----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the main function for clang misexpect. It uses a
+// libTooling exectutor to check each file in the compiler_commands.json against
+// a provided PGO profile. When profile counters disagree with the compiler's
+// threshold values for likely and unlike branches clang-misexpect will issue a
+// diagnostic message.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../ClangMisExpect.h"
+#include "clang/Basic/CodeGenOptions.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Tooling/AllTUsExecution.h"
+#include "clang/Tooling/ArgumentsAdjusters.h"
+#include "clang/Tooling/CommonOptionsParser.h"
+#include "clang/Tooling/Execution.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Signals.h"
+#include <string>
+
+using namespace clang;
+using namespace clang::tooling;
+using namespace clang::misexpect;
+using Path = std::string;
+
+static llvm::cl::extrahelp CommonHelp(CommonOptionsParser::HelpMessage);
+static llvm::cl::OptionCategory
+    ClangMisExpectCategory("clang-misexpect options");
+
+static llvm::cl::opt<Path> ProfileDir(
+    "profile-dir",
+    llvm::cl::desc(
+        "Specify a path to the profile data to use during validation"),
+    llvm::cl::cat(ClangMisExpectCategory));
+
+static llvm::cl::opt<ProfileKind> ProfFormat(
+    "profile-format",
+    llvm::cl::desc(
+        "Specify the format of the profile data used during validation"),
+    llvm::cl::init(Clang),
+    llvm::cl::values(clEnumValN(Clang, "clang", "Clang Instrumentation"),
+                     clEnumValN(IR, "llvm", "IR Instrumentation"),
+                     clEnumValN(CSIR, "csllvm",
+                                "Context sensitive IR Instrumentation"),
+                     clEnumValN(Sample, "sample", "Sampling Instrumentation")),
+    llvm::cl::cat(ClangMisExpectCategory));
+
+int main(int argc, const char **argv) {
+  llvm::sys::PrintStackTraceOnErrorSignal(argv[0]);
+
+  ExecutorName.setInitialValue("all-TUs");
+
+  auto &OS = llvm::errs();
+  auto Executor =
+      createExecutorFromCommandLineArgs(argc, argv, ClangMisExpectCategory);
+
+  if (!Executor) {
+    OS << "Failed to create executor --- "
+       << llvm::toString(Executor.takeError()) << "\n";
+    return 1;
+  }
+
+  OS << "Executor Created ... \n";
+
+  CommonOptionsParser OptionsParser(argc, argv, ClangMisExpectCategory,
+                                    llvm::cl::ZeroOrMore);
+
+  OS << "Starting execution ... \n";
+  auto ArgAdjuster = getStripPluginsAdjuster();
+  auto StripProfileWarnings = [](const CommandLineArguments &Args,
+                                 StringRef /*unused*/ Unused) {
+    CommandLineArguments AdjustedArgs;
+    std::set<std::string> FilteredArgs = {"-Wprofile-instr-unprofiled",
+                                          "-fcoverage-mapping", "-Werror"};
+    for (size_t I = 0, E = Args.size(); I != E; I++) {
+      if (FilteredArgs.find(Args[I]) != FilteredArgs.end())
+        continue;
+
+      AdjustedArgs.push_back(Args[I]);
+    }
+    return AdjustedArgs;
+  };
+
+  ArgAdjuster = combineAdjusters(StripProfileWarnings, ArgAdjuster);
+
+  ArgAdjuster = combineAdjusters(
+      getInsertArgumentAdjuster({"-Wmisexpect", "-Wno-profile-instr-unprofiled",
+                                 "-Wno-profile-instr-out-of-date"},
+                                tooling::ArgumentInsertPosition::END),
+      ArgAdjuster);
+
+  auto Err = Executor->get()->execute(
+      std::make_unique<misexpect::MisExpectFactory>(ProfileDir, ProfFormat),
+      ArgAdjuster);
+  if (Err) {
+    OS.changeColor(raw_ostream::Colors::RED, true);
+    OS << "Error: ";
+    OS.resetColor();
+    OS << llvm::toString(std::move(Err)) << "\n";
+  }
+
+  OS << "Execution complete\n";
+
+  // Emit collected data.
+  Executor->get()->getToolResults()->forEachResult(
+      [&OS](llvm::StringRef Key, llvm::StringRef Value) {
+        OS << "----" << Key.str() << "\n" << Value.str() << "\n";
+      });
+  return 0;
+}

clang/cmake/caches/Fuchsia-stage2.cmake

set(LLVM_TOOLCHAIN_TOOLS
   CACHE STRING "")
 
 set(LLVM_DISTRIBUTION_COMPONENTS
   clang
   lld
   LTO
   clang-apply-replacements
   clang-doc
+  clang-misexpect
   clang-format
   clang-resource-headers
   clang-include-fixer
   clang-refactor
   clang-tidy
   clangd
   builtins
   runtimes
   ${LLVM_TOOLCHAIN_TOOLS}
   CACHE STRING "")

llvm/lib/Transforms/Utils/MisExpect.cpp

 
 namespace llvm {
 
 // Command line option to enable/disable the warning when profile data suggests
 // a mismatch with the use of the llvm.expect intrinsic
 static cl::opt<bool> PGOWarnMisExpect(
     "pgo-warn-misexpect", cl::init(false), cl::Hidden,
     cl::desc("Use this option to turn on/off "
-             "warnings about incorrect usage of llvm.expect intrinsics."));
+             "warnings about incorrect usage of llvm.expect intrinsics."),
+    cl::ZeroOrMore);
 
 } // namespace llvm
 
 namespace {
 
 Instruction *getOprndOrInst(Instruction *I) {
   assert(I != nullptr && "MisExpect target Instruction cannot be nullptr");
   Instruction *Ret = nullptr;