[xray] Function coverage groups

[ianlevesque]

Summary

Add the ability to selectively instrument a subset of functions by dividing the functions into N logical groups and then selecting a group to cover. By selecting different groups over time you could cover the entire application incrementally with lower overhead than instrumenting the entire application at once.

[dberris]

clang/lib/CodeGen/CodeGenFunction.cpp

817

I'm a little concerned that this is randomly determined. Could we think about using a function attribute instead that opts functions into groups by name? Or is the intent to have "sampling" in the coverage information instead of full coverage?

[ianlevesque]

clang/lib/CodeGen/CodeGenFunction.cpp

817

The intention is to have something deterministic across builds but yeah sampled-ish across the entire codebase. By iterating over the groups with different builds we are hoping to cover every function eventually.

[MaskRay]

The idea seems fine.

By selecting different groups over time you could cover the entire application incrementally with lower overhead than instrumenting the entire application at once.

How large the overhead is? This is somewhat surprising to me.

clang/include/clang/Driver/Options.td

1343

Joined.

Separate is for a space between the option name and its value.

1345

It is "N groups", not "N functions".

clang/lib/CodeGen/CodeGenFunction.cpp

814

For one group, the branch is skipped, which does not seem correct

815

const ArrayRef<uint8_t> FuncName(..., ...)

820

Omit braces around one-line simple statements.

clang/test/CodeGen/xray-function-groups.cpp

4

You can omit -x c++ -std=c++11 . They are insignificant.

Then consider packing more options on one line to reduce the total number of lines.

[kyulee]

clang/lib/CodeGen/CodeGenFunction.cpp

814

Should we check or assert XRaySelectedFunctionGroups > 0 && XRaySelectedFunctionGroup < XRaySelectedFunctionGroups or the former at minimum?

[MaskRay]

clang/lib/CodeGen/CodeGenFunction.cpp

814

Such checks are usually done in Driver. In CodeGen, as long as it doesn't crash, there is no need imposing stricter checks.

[ianlevesque]

clang/lib/CodeGen/CodeGenFunction.cpp

814

If there is only 1 group (the default value), then all functions that would be otherwise instrumented are. So there should be no need to do anything.

[ianlevesque]

Address code review feedback

[ianlevesque]

In D87953#2284071, @MaskRay wrote:

How large the overhead is? This is somewhat surprising to me.

It is the binary size overhead, not the runtime overhead, that we are limited on (when deployed on Android).

[ianlevesque]

const

[ianlevesque]

This is ready for another review, I think I addressed everything.

[MaskRay]

clang/lib/Frontend/CompilerInvocation.cpp

1136

Errors here are not necessary. The driver has reported errors.

[ianlevesque]

Remove extraneous parameter validations.

[kyulee]

I think it looks good to me. @MaskRay Any further feedback on this?

[MaskRay]

In D87953#2293024, @kyulee wrote:

I think it looks good to me. @MaskRay Any further feedback on this?

This looks good from my viewpoint. One thing remains unanswered (https://reviews.llvm.org/D87953#2284071) is how the overhead is so large that you want to have multiple groups.
Deploying N versions of an executable can bring more challenges to the build system and deployment system.
I am also concerned about some internal functions whose names are optional (in ELF symbol table they don't really need a name).

I'd want to know how you weigh the tradeoff and decide to go this route.

This is a larger stuff that I want @dberris to sign off.

clang/lib/CodeGen/CodeGenFunction.cpp

815

You can use some variants of makeArrayRef

[ianlevesque]

Thanks @MaskRay - I tried to answer that question in https://reviews.llvm.org/D87953#2286430. At present we are deploying instrumentation to an arbitrary subset of our application using the instruction threshold. I would like to make the selection of how many and which functions more deterministic, and be able to instrument different subsets over time. The overhead we are concerned with is purely binary size as we are deploying to Android devices. We are using features from my previous XRay patches to omit the function index already, but the sheer number of sleds and size of the associated xray_instr_map are the limiting factor of how much we can instrument in any given app release. For our use case it is fine to gradually over a period of weeks work our way across the entire app group by group.

[MaskRay]

In D87953#2293162, @ianlevesque wrote:

Thanks @MaskRay - I tried to answer that question in https://reviews.llvm.org/D87953#2286430. At present we are deploying instrumentation to an arbitrary subset of our application using the instruction threshold. I would like to make the selection of how many and which functions more deterministic, and be able to instrument different subsets over time. The overhead we are concerned with is purely binary size as we are deploying to Android devices. We are using features from my previous XRay patches to omit the function index already, but the sheer number of sleds and size of the associated xray_instr_map are the limiting factor of how much we can instrument in any given app release. For our use case it is fine to gradually over a period of weeks work our way across the entire app group by group.

Thanks for clarification. It is the size overhead, instead of the runtime overhead:) This makes sense. You probably want to enhance the test to check internal linkage (e.g. static functions). You can change bar or yarr instead of introducing new functions.

[MaskRay]

I probably have asked too much... but it'd be nice if you also add some documentation to llvm/docs/XRay*.rst That helps users :)

[dberris]

There's two tensions I'm trying to resolve in my mind with this patch:

• Is there a way to make this more deterministic, instead of using a random sampling mechanism based on the name?
• This looks like it's a subset of a more general facility to group functions by "module" or some logical grouping mechanism. Will this be superseded by a feature that allows for example to provide filters in the driver to define groupings? If so, wouldn't something like that be more flexible for your needs (group names in the IR)?

[ianlevesque]

I can update the docs @MaskRay, not a problem. I'll tweak the test a little too per your comment.

@dberris I think if we wanted to control it in a non-'random' (the crc32 was chosen so it would be consistent even though it's not really predictable up front) way we'd have to emit some lists of function attributes and use the -fxray-attr-list=FILE option to really dial that in. If we wanted entire modules we could have the build system apply xray's flags to each module differently, but we are unlikely to want to instrument every function of a module at the same time so we are back to having to use instruction thresholds to cut down on it. Ultimately I think those two suggestions are legitimate alternative use cases but don't, for what we're trying to do, replace this strategy.

[dberris]

Okay, I think I understand the motivation a little bit more now (i.e. sampling seems to be a useful thing to do anyway, regardless of whether we have the other facilities).

[ianlevesque]

Add static function to the test case, update documentation.

clang/include/clang/Basic/CodeGenOptions.def

 ///< Set with -fno-xray-function-index to omit the index section.
 CODEGENOPT(XRayOmitFunctionIndex , 1, 0)
 
 
 ///< Set the minimum number of instructions in a function to determine selective
 ///< XRay instrumentation.
 VALUE_CODEGENOPT(XRayInstructionThreshold , 32, 200)
 
+///< Only instrument 1 in N functions, by dividing functions into N total groups and
+///< instrumenting only the specified group at a time. Group numbers start at 0
+///< and end at N-1.
+VALUE_CODEGENOPT(XRayTotalFunctionGroups, 32, 1)
+VALUE_CODEGENOPT(XRaySelectedFunctionGroup, 32, 0)
+
 VALUE_CODEGENOPT(PatchableFunctionEntryCount , 32, 0) ///< Number of NOPs at function entry
 VALUE_CODEGENOPT(PatchableFunctionEntryOffset , 32, 0)
 
 CODEGENOPT(InstrumentForProfiling , 1, 0) ///< Set when -pg is enabled.
 CODEGENOPT(CallFEntry , 1, 0) ///< Set when -mfentry is enabled.
 CODEGENOPT(MNopMCount , 1, 0) ///< Set when -mnop-mcount is enabled.
 CODEGENOPT(RecordMCount , 1, 0) ///< Set when -mrecord-mcount is enabled.
 CODEGENOPT(PackedStack , 1, 0) ///< Set when -mpacked-stack is enabled.

clang/include/clang/Driver/Options.td

 def fnoxray_link_deps : Flag<["-"], "fnoxray-link-deps">, Group<f_Group>,
   Flags<[CC1Option]>;
 
 def fxray_instrumentation_bundle :
   JoinedOrSeparate<["-"], "fxray-instrumentation-bundle=">,
   Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Select which XRay instrumentation points to emit. Options: all, none, function-entry, function-exit, function, custom. Default is 'all'.  'function' includes both 'function-entry' and 'function-exit'.">;
 
+def fxray_function_groups :
+  JoinedOrSeparate<["-"], "fxray-function-groups=">,
+  Group<f_Group>, Flags<[CC1Option]>,
+  HelpText<"Only instrument 1 of N functions">;
+
+def fxray_selected_function_group :
+  JoinedOrSeparate<["-"], "fxray-selected-function-group=">,
+  Group<f_Group>, Flags<[CC1Option]>,
+  HelpText<"When using -fxray-function-groups, select which group of functions to instrument. Valid range is 0 to fxray-function-groups - 1">;
+
+
 def ffine_grained_bitfield_accesses : Flag<["-"],
   "ffine-grained-bitfield-accesses">, Group<f_clang_Group>, Flags<[CC1Option]>,
   HelpText<"Use separate accesses for consecutive bitfield runs with legal widths and alignments.">;
 def fno_fine_grained_bitfield_accesses : Flag<["-"],
   "fno-fine-grained-bitfield-accesses">, Group<f_clang_Group>, Flags<[CC1Option]>,
   HelpText<"Use large-integer access for consecutive bitfield runs.">;
 
 def fexperimental_relative_cxx_abi_vtables : Flag<["-"], "fexperimental-relative-c++-abi-vtables">,

clang/include/clang/Driver/XRayArgs.h

class XRayArgs {
   XRayInstrSet InstrumentationBundle;
   bool XRayInstrument = false;
   int InstructionThreshold = 200;
   bool XRayAlwaysEmitCustomEvents = false;
   bool XRayAlwaysEmitTypedEvents = false;
   bool XRayRT = true;
   bool XRayIgnoreLoops = false;
   bool XRayFunctionIndex;
+  int XRayFunctionGroups = 1;
+  int XRaySelectedFunctionGroup;
 
 public:
   /// Parses the XRay arguments from an argument list.
   XRayArgs(const ToolChain &TC, const llvm::opt::ArgList &Args);
   void addArgs(const ToolChain &TC, const llvm::opt::ArgList &Args,
                llvm::opt::ArgStringList &CmdArgs, types::ID InputType) const;
 
   bool needsXRayRt() const { return XRayInstrument && XRayRT; }
   llvm::ArrayRef<std::string> modeList() const { return Modes; }
   XRayInstrSet instrumentationBundle() const { return InstrumentationBundle; }
 };
 
 } // namespace driver
 } // namespace clang
 
 #endif // LLVM_CLANG_DRIVER_XRAYARGS_H

clang/lib/CodeGen/CodeGenFunction.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtObjC.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/CodeGenOptions.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "clang/Frontend/FrontendDiagnostic.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/FPEnv.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/Support/CRC.h"
 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
 using namespace clang;
 using namespace CodeGen;
 
 /// shouldEmitLifetimeMarkers - Decide whether we need emit the life-time
 /// markers.
 static bool shouldEmitLifetimeMarkers(const CodeGenOptions &CGOpts,
                                       const LangOptions &LangOpts) {
#undef SANITIZER
   // coroutine boundaries.
   if (D && SanOpts.has(SanitizerKind::Null))
     if (const auto *FD = dyn_cast<FunctionDecl>(D))
       if (FD->getBody() &&
           FD->getBody()->getStmtClass() == Stmt::CoroutineBodyStmtClass)
         SanOpts.Mask &= ~SanitizerKind::Null;
 
   // Apply xray attributes to the function (as a string, for now)
+  bool AlwaysXRayAttr = false;
   if (const auto *XRayAttr = D ? D->getAttr<XRayInstrumentAttr>() : nullptr) {
     if (CGM.getCodeGenOpts().XRayInstrumentationBundle.has(
             XRayInstrKind::FunctionEntry) ||
         CGM.getCodeGenOpts().XRayInstrumentationBundle.has(
             XRayInstrKind::FunctionExit)) {
-      if (XRayAttr->alwaysXRayInstrument() && ShouldXRayInstrumentFunction())
+      if (XRayAttr->alwaysXRayInstrument() && ShouldXRayInstrumentFunction()) {
         Fn->addFnAttr("function-instrument", "xray-always");
+        AlwaysXRayAttr = true;
+      }
       if (XRayAttr->neverXRayInstrument())
         Fn->addFnAttr("function-instrument", "xray-never");
       if (const auto *LogArgs = D->getAttr<XRayLogArgsAttr>())
         if (ShouldXRayInstrumentFunction())
           Fn->addFnAttr("xray-log-args",
                         llvm::utostr(LogArgs->getArgumentCount()));
     }
   } else {
if (ShouldXRayInstrumentFunction()) {
 
     if (!CGM.getCodeGenOpts().XRayInstrumentationBundle.has(
             XRayInstrKind::FunctionExit))
       Fn->addFnAttr("xray-skip-exit");
 
     if (!CGM.getCodeGenOpts().XRayInstrumentationBundle.has(
             XRayInstrKind::FunctionEntry))
       Fn->addFnAttr("xray-skip-entry");
+
+    auto FuncGroups = CGM.getCodeGenOpts().XRayTotalFunctionGroups;
+    if (FuncGroups > 1) {
+      auto FuncName = ArrayRef<uint8_t>(CurFn->getName().bytes_begin(),
+                                        CurFn->getName().bytes_end());
+      auto Group = crc32(FuncName) % FuncGroups;
+      if (Group != CGM.getCodeGenOpts().XRaySelectedFunctionGroup &&
+          !AlwaysXRayAttr) {
+        Fn->addFnAttr("function-instrument", "xray-never");
+      }
+    }
   }
 
   unsigned Count, Offset;
   if (const auto *Attr =
           D ? D->getAttr<PatchableFunctionEntryAttr>() : nullptr) {
     Count = Attr->getCount();
     Offset = Attr->getOffset();
   } else {

clang/lib/Driver/XRayArgs.cpp

for (const auto &Arg : SpecifiedModes) {
         if (M == "none")
           Modes.clear();
         else if (M == "all")
           llvm::copy(XRaySupportedModes, std::back_inserter(Modes));
         else
           Modes.push_back(std::string(M));
     }
 
+  if (const Arg *A = Args.getLastArg(options::OPT_fxray_function_groups)) {
+    StringRef S = A->getValue();
+    if (S.getAsInteger(0, XRayFunctionGroups) || XRayFunctionGroups < 1)
+      D.Diag(clang::diag::err_drv_invalid_value) << A->getAsString(Args) << S;
+  }
+
+  if (const Arg *A =
+          Args.getLastArg(options::OPT_fxray_selected_function_group)) {
+    StringRef S = A->getValue();
+    if (S.getAsInteger(0, XRaySelectedFunctionGroup) ||
+        XRaySelectedFunctionGroup < 0 ||
+        XRaySelectedFunctionGroup >= XRayFunctionGroups)
+      D.Diag(clang::diag::err_drv_invalid_value) << A->getAsString(Args) << S;
+  }
+
   // Then we want to sort and unique the modes we've collected.
   llvm::sort(Modes);
   Modes.erase(std::unique(Modes.begin(), Modes.end()), Modes.end());
 }
 
 void XRayArgs::addArgs(const ToolChain &TC, const ArgList &Args,
                        ArgStringList &CmdArgs, types::ID InputType) const {
   if (!XRayInstrument)
     return;
 
   CmdArgs.push_back(XRayInstrumentOption);
 
   if (XRayAlwaysEmitCustomEvents)
     CmdArgs.push_back("-fxray-always-emit-customevents");
 
   if (XRayAlwaysEmitTypedEvents)
     CmdArgs.push_back("-fxray-always-emit-typedevents");
 
   if (XRayIgnoreLoops)
     CmdArgs.push_back("-fxray-ignore-loops");
 
   if (!XRayFunctionIndex)
     CmdArgs.push_back("-fno-xray-function-index");
 
+  if (XRayFunctionGroups > 1) {
+    CmdArgs.push_back(Args.MakeArgString(Twine("-fxray-function-groups=") +
+                                         Twine(XRayFunctionGroups)));
+  }
+
+  if (XRaySelectedFunctionGroup != 0) {
+    CmdArgs.push_back(
+        Args.MakeArgString(Twine("-fxray-selected-function-group=") +
+                           Twine(XRaySelectedFunctionGroup)));
+  }
+
   CmdArgs.push_back(Args.MakeArgString(Twine(XRayInstructionThresholdOption) +
                                        Twine(InstructionThreshold)));
 
   for (const auto &Always : AlwaysInstrumentFiles) {
     SmallString<64> AlwaysInstrumentOpt("-fxray-always-instrument=");
     AlwaysInstrumentOpt += Always;
     CmdArgs.push_back(Args.MakeArgString(AlwaysInstrumentOpt));
   }

clang/lib/Frontend/CompilerInvocation.cpp

static bool ParseCodeGenArgs(CodeGenOptions &Opts, ArgList &Args, InputKind IK,
   Opts.XRayAlwaysEmitCustomEvents =
       Args.hasArg(OPT_fxray_always_emit_customevents);
   Opts.XRayAlwaysEmitTypedEvents =
       Args.hasArg(OPT_fxray_always_emit_typedevents);
   Opts.XRayInstructionThreshold =
       getLastArgIntValue(Args, OPT_fxray_instruction_threshold_EQ, 200, Diags);
   Opts.XRayIgnoreLoops = Args.hasArg(OPT_fxray_ignore_loops);
   Opts.XRayOmitFunctionIndex = Args.hasArg(OPT_fno_xray_function_index);
+  Opts.XRayTotalFunctionGroups =
+      getLastArgIntValue(Args, OPT_fxray_function_groups, 1, Diags);
+  if (Opts.XRayTotalFunctionGroups < 1) {
+    const Arg *A = Args.getLastArg(OPT_fxray_function_groups);
+    Diags.Report(diag::err_drv_invalid_value)
+        << A->getAsString(Args) << A->getValue();
+  }
+  Opts.XRaySelectedFunctionGroup =
+      getLastArgIntValue(Args, OPT_fxray_selected_function_group, 0, Diags);
+  if (Opts.XRaySelectedFunctionGroup >= Opts.XRayTotalFunctionGroups) {
+    const Arg *A = Args.getLastArg(OPT_fxray_selected_function_group);
+    Diags.Report(diag::err_drv_invalid_value)
+        << A->getAsString(Args) << A->getValue();
+  }
 
   auto XRayInstrBundles =
       Args.getAllArgValues(OPT_fxray_instrumentation_bundle);
   if (XRayInstrBundles.empty())
     Opts.XRayInstrumentationBundle.Mask = XRayInstrKind::All;
   else
     for (const auto &A : XRayInstrBundles)
       parseXRayInstrumentationBundle("-fxray-instrumentation-bundle=", A, Args,

clang/test/CodeGen/xray-function-groups.cpp

+// RUN: %clang_cc1 -fxray-instrument -fxray-instruction-threshold=1 \
+// RUN:            -fxray-function-groups=3 \
+// RUN:            -fxray-selected-function-group=0 \
+// RUN:            -x c++ -std=c++11 -emit-llvm -o - %s \
+// RUN:            -triple x86_64-unknown-linux-gnu | FileCheck --check-prefix=GROUP0 %s
+
+// RUN: %clang_cc1 -fxray-instrument -fxray-instruction-threshold=1 \
+// RUN:            -fxray-function-groups=3 \
+// RUN:            -fxray-selected-function-group=1 \
+// RUN:            -x c++ -std=c++11 -emit-llvm -o - %s \
+// RUN:            -triple x86_64-unknown-linux-gnu | FileCheck --check-prefix=GROUP1 %s
+
+// RUN: %clang_cc1 -fxray-instrument -fxray-instruction-threshold=1 \
+// RUN:            -fxray-function-groups=3 \
+// RUN:            -fxray-selected-function-group=2 \
+// RUN:            -x c++ -std=c++11 -emit-llvm -o - %s \
+// RUN:            -triple x86_64-unknown-linux-gnu | FileCheck --check-prefix=GROUP2 %s
+
+int foo() { // part of group 0
+  return 1;
+}
+
+int bar() { // part of group 2
+  return 1;
+}
+
+int yarr() { // part of group 1
+  return 1;
+}
+
+[[clang::xray_always_instrument]] int always() { // part of group 0
+  return 1;
+}
+
+[[clang::xray_never_instrument]] int never() { // part of group 1
+  return 1;
+}
+
+// GROUP0: define{{.*}} i32 @_Z3foov() #[[ATTRS_FOO:[0-9]+]] {
+// GROUP0: define{{.*}} i32 @_Z3barv() #[[ATTRS_BAR:[0-9]+]] {
+// GROUP0: define{{.*}} i32 @_Z4yarrv() #[[ATTRS_BAR]] {
+// GROUP0: define{{.*}} i32 @_Z6alwaysv() #[[ATTRS_ALWAYS:[0-9]+]] {
+// GROUP0: define{{.*}} i32 @_Z5neverv() #[[ATTRS_NEVER:[0-9]+]] {
+// GROUP0-DAG: attributes #[[ATTRS_BAR]] = {{.*}} "function-instrument"="xray-never" {{.*}}
+// GROUP0-DAG: attributes #[[ATTRS_ALWAYS]] = {{.*}} "function-instrument"="xray-always" {{.*}}
+// GROUP0-DAG: attributes #[[ATTRS_NEVER]] = {{.*}} "function-instrument"="xray-never" {{.*}}
+
+// GROUP1: define{{.*}} i32 @_Z3foov() #[[ATTRS_FOO:[0-9]+]] {
+// GROUP1: define{{.*}} i32 @_Z3barv() #[[ATTRS_FOO]] {
+// GROUP1: define{{.*}} i32 @_Z4yarrv() #[[ATTRS_YARR:[0-9]+]] {
+// GROUP1: define{{.*}} i32 @_Z6alwaysv() #[[ATTRS_ALWAYS:[0-9]+]] {
+// GROUP1: define{{.*}} i32 @_Z5neverv() #[[ATTRS_NEVER:[0-9]+]] {
+// GROUP1-DAG: attributes #[[ATTRS_FOO]] = {{.*}} "function-instrument"="xray-never" {{.*}}
+// GROUP1-DAG: attributes #[[ATTRS_ALWAYS]] = {{.*}} "function-instrument"="xray-always" {{.*}}
+// GROUP1-DAG: attributes #[[ATTRS_NEVER]] = {{.*}} "function-instrument"="xray-never" {{.*}}
+
+// GROUP2: define{{.*}} i32 @_Z3foov() #[[ATTRS_FOO:[0-9]+]] {
+// GROUP2: define{{.*}} i32 @_Z3barv() #[[ATTRS_BAR:[0-9]+]] {
+// GROUP2: define{{.*}} i32 @_Z4yarrv() #[[ATTRS_FOO]] {
+// GROUP2: define{{.*}} i32 @_Z6alwaysv() #[[ATTRS_ALWAYS:[0-9]+]] {
+// GROUP2: define{{.*}} i32 @_Z5neverv() #[[ATTRS_NEVER:[0-9]+]] {
+// GROUP2-DAG: attributes #[[ATTRS_FOO]] = {{.*}} "function-instrument"="xray-never" {{.*}}
+// GROUP2-DAG: attributes #[[ATTRS_ALWAYS]] = {{.*}} "function-instrument"="xray-always" {{.*}}
+// GROUP2-DAG: attributes #[[ATTRS_NEVER]] = {{.*}} "function-instrument"="xray-never" {{.*}}