[DFSan] Add efficient fast16labels instrumentation mode.

[morehouse]

Summary

Adds the -fast-16-labels flag, which enables efficient instrumentation
for DFSan when the user needs <=16 labels. The instrumentation
eliminates most branches and most calls to dfsan_union or
dfsan_union_load.

We also add a call into the runtime during preinit to enable
fast16labels mode there, since we may still call __dfsan_union[_load] in
rare cases.

[kcc]

In what cases do we still call __dfsan_union?

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

184

please add the documentation.
Probably into this change, so that we review it together.

[kcc]

compiler-rt/lib/dfsan/dfsan.cpp

163

I wonder if we can get away w/o these flags.
Just assume that fast16mode works only when the fast16mode instrumentation is enabled.
(remember, fast16mode is currently experimental, we are free to change its behavior)

[vitalybuka]

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

1049

what we are going to do in __dfsan_fast16labels_preinit?

1291

have you considered a loop?

[morehouse]

• Add documentation.
• Remove fast16labels runtime flag.

[morehouse]

In D84371#2168367, @kcc wrote:

In what cases do we still call __dfsan_union?

We still call __dfsan_union_load when we load sizes greater than 2 bytes but not divisible by 4. I actually am not sure what instruction sequence would hit this case, but it was already in DFSan so I left it there.

__dfsan_union_load then calls __dfsan_union.

compiler-rt/lib/dfsan/dfsan.cpp

163

SGTM. I only know of @Dor1s using it at the moment.

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

1049

This global is simply a pointer to dfsan_use_fast16labels() so that it runs during preinit. dfsan_use_fast16labels just enables fast16labels mode in the runtime.

1291

I think we should avoid loop overhead at least for the common case here (loading 8-16 bytes of shadow).

I think it's also possible to hit this case with vector instructions, but vanilla DFSan currently doesn't use a loop in that case either. If we want to use a loop for vector loads, I think we should do it in a different patch.

[morehouse]

• Fix libfuzzer dataflow tests.

[kcc]

Yep, cool.
LGTM from me, but please get another pair if eyes (Vitaly?)

clang/docs/DataFlowSanitizer.rst

182

maybe -dataflow-fast-16-labels?

201

perhaps unconfuse the test a bit by using other constants

i = 100;
j = 200;
k = 300;

[vitalybuka]

compiler-rt/lib/dfsan/dfsan.cpp

165–166

isn't better just create new set of callbacks?
e.g __dfsan_fast16_union
and then we don't need any flags or preinit array initialization

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

784

DFSanUseFast16LabelsFnTy and DFSanUseFast16LabelsFn is used one in one place
I'd make them local variables. in if (ClFast16Labels) of runOnModule

[morehouse]

• Rename flag
• Clarify doc example
• Use temporary variables.

compiler-rt/lib/dfsan/dfsan.cpp

165–166

Should work for __dfsan_union and __dfsan_union_load, but what about all the other API functions the user can call directly? We wouldn't be able to warn in those cases.

[vitalybuka]

LGTM either way

compiler-rt/lib/dfsan/dfsan.cpp

165–166

Should work for __dfsan_union and __dfsan_union_load, but what about all the other API functions the user can call directly? We wouldn't be able to warn in those cases.

Those calls are no-op, it would be nice, but it's not worth it.
You can avoid state variable fast16labels, and avoid preinit_array which time to time conflicts with other libs. Which looks more useful then warning.

[morehouse]

• Remove preinit stuff and API warnings; use custom union-load callback.

compiler-rt/lib/dfsan/dfsan.cpp

165–166

Thanks. Turns out we only need __dfsan_union_load_fast16labels, which makes things simpler.

[morehouse]

compiler-rt/lib/dfsan/dfsan.cpp

165–166

Turns out we might need a fast16 flag and preinit_array after all, since many of the custom wrappers call dfsan_union...

@vitalybuka Any ideas to avoid this?

[morehouse]

compiler-rt/lib/dfsan/dfsan.cpp

165–166

One idea: In fast16 mode, we never call dfsan_create_label, so probably we can just check whether any labels have been created, and if not compute the OR.

clang/docs/DataFlowSanitizer.rst

int main(void) {
     dfsan_label ijk_label = dfsan_get_label(i + j + k);
     assert(dfsan_has_label(ijk_label, i_label));
     assert(dfsan_has_label(ijk_label, j_label));
     assert(dfsan_has_label(ijk_label, k_label));
 
     return 0;
   }
 
+fast16labels mode
+=================
+
+If you need 16 or fewer labels, you can use fast16labels instrumentation for
+less CPU and code size overhead.  To use fast16labels instrumentation, you'll
+need to specify `-fsanitize=dataflow -mllvm -dfsan-fast-16-labels` in your
+compile and link commands and use a modified API for creating and managing
+labels.
+
+In fast16labels mode, base labels are simply 16-bit unsigned integers that are
+powers of 2 (i.e. 1, 2, 4, 8, ..., 32768), and union labels are created by ORing
+base labels.  In this mode DFSan does not manage any label metadata, so the
+functions `dfsan_create_label`, `dfsan_union`, `dfsan_get_label_info`,
+`dfsan_has_label`, `dfsan_has_label_with_desc`, `dfsan_get_label_count`, and
+`dfsan_dump_labels` are unsupported.  Instead of using them, the user should
+maintain any necessary metadata about base labels themselves.
+
+For example:
+
+.. code-block:: c++
+
+  #include <sanitizer/dfsan_interface.h>
+  #include <assert.h>
+
+  int main(void) {
+    int i = 100;
+    int j = 200;
+    int k = 300;
+    dfsan_label i_label = 1;
+    dfsan_label j_label = 2;
+    dfsan_label k_label = 4;
+    dfsan_set_label(i_label, &i, sizeof(i));
+    dfsan_set_label(j_label, &j, sizeof(j));
+    dfsan_set_label(k_label, &k, sizeof(k));
+
+    dfsan_label ij_label = dfsan_get_label(i + j);
+
+    assert(ij_label & i_label);  // ij_label has i_label
+    assert(ij_label & j_label);  // ij_label has j_label
+    assert(!(ij_label & k_label));  // ij_label doesn't have k_label
+    assert(ij_label == 3)  // Verifies all of the above
+
+    dfsan_label ijk_label = dfsan_get_label(i + j + k);
+
+    assert(ijk_label & i_label);  // ijk_label has i_label
+    assert(ijk_label & j_label);  // ijk_label has j_label
+    assert(ijk_label & k_label);  // ijk_label has k_label
+    assert(ijk_label == 7);  // Verifies all of the above
+
+    return 0;
+  }
+
 Current status
 ==============
 
 DataFlowSanitizer is a work in progress, currently under development for
 x86\_64 Linux.
 
 Design
 ======
 
 Please refer to the :doc:`design document<DataFlowSanitizerDesign>`.

compiler-rt/lib/dfsan/dfsan.cpp

 // called automatically by the compiler (specifically the instrumentation pass
 // in llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp).
 //
 // The public interface is defined in include/sanitizer/dfsan_interface.h whose
 // functions are prefixed dfsan_ while the compiler interface functions are
 // prefixed __dfsan_.
 //===----------------------------------------------------------------------===//
 
+#include "dfsan/dfsan.h"
+
 #include "sanitizer_common/sanitizer_atomic.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_file.h"
-#include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_flag_parser.h"
+#include "sanitizer_common/sanitizer_flags.h"
+#include "sanitizer_common/sanitizer_internal_defs.h"
 #include "sanitizer_common/sanitizer_libc.h"
 
-#include "dfsan/dfsan.h"
-
 using namespace __dfsan;
 
 typedef atomic_uint16_t atomic_dfsan_label;
 static const dfsan_label kInitializingLabel = -1;
 
 static const uptr kNumLabels = 1 << (sizeof(dfsan_label) * 8);
 
 static atomic_dfsan_label __dfsan_last_label;

 // Checks we do not run out of labels.
 static void dfsan_check_label(dfsan_label label) {
   if (label == kInitializingLabel) {
     Report("FATAL: DataFlowSanitizer: out of labels\n");
     Die();
   }
 }
 
-static void ReportUnsupportedFast16(const char *func) {
-  Report("FATAL: DataFlowSanitizer: %s is unsupported in fast16labels mode\n",
-         func);
-  Die();
-}
-
 // Resolves the union of two unequal labels.  Nonequality is a precondition for
 // this function (the instrumentation pass inlines the equality test).
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 dfsan_label __dfsan_union(dfsan_label l1, dfsan_label l2) {
-  if (flags().fast16labels)
-    return l1 | l2;
   DCHECK_NE(l1, l2);
 
   if (l1 == 0)
     return l2;
   if (l2 == 0)
     return l1;
 
   if (l1 > l2)
     Swap(l1, l2);
for (uptr i = 1; i != n; ++i) {
     dfsan_label next_label = ls[i];
     if (label != next_label)
       label = __dfsan_union(label, next_label);
   }
   return label;
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
+dfsan_label __dfsan_union_load_fast16labels(const dfsan_label *ls, uptr n) {
+  dfsan_label label = ls[0];
+  for (uptr i = 1; i != n; ++i)
+    label |= ls[i];
+  return label;
+}
+
+extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 void __dfsan_unimplemented(char *fname) {
   if (flags().warn_unimplemented)
     Report("WARNING: DataFlowSanitizer: call to uninstrumented function %s\n",
            fname);
 }
 
 // Use '-mllvm -dfsan-debug-nonzero-labels' and break on this function
 // to try to figure out where labels are being introduced in a nominally

 dfsan_union(dfsan_label l1, dfsan_label l2) {
   if (l1 == l2)
     return l1;
   return __dfsan_union(l1, l2);
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 dfsan_label dfsan_create_label(const char *desc, void *userdata) {
-  if (flags().fast16labels)
-    ReportUnsupportedFast16("dfsan_create_label");
   dfsan_label label =
       atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1;
   dfsan_check_label(label);
   __dfsan_label_info[label].l1 = __dfsan_label_info[label].l2 = 0;
   __dfsan_label_info[label].desc = desc;
   __dfsan_label_info[label].userdata = userdata;
   return label;
 }

 dfsan_read_label(const void *addr, uptr size) {
   if (size == 0)
     return 0;
   return __dfsan_union_load(shadow_for(addr), size);
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
-  if (flags().fast16labels)
-    ReportUnsupportedFast16("dfsan_get_label_info");
   return &__dfsan_label_info[label];
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE int
 dfsan_has_label(dfsan_label label, dfsan_label elem) {
-  if (flags().fast16labels)
-    return label & elem;
   if (label == elem)
     return true;
   const dfsan_label_info *info = dfsan_get_label_info(label);
   if (info->l1 != 0) {
     return dfsan_has_label(info->l1, elem) || dfsan_has_label(info->l2, elem);
   } else {
     return false;
   }
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
 dfsan_has_label_with_desc(dfsan_label label, const char *desc) {
-  if (flags().fast16labels)
-    ReportUnsupportedFast16("dfsan_has_label_with_desc");
   const dfsan_label_info *info = dfsan_get_label_info(label);
   if (info->l1 != 0) {
     return dfsan_has_label_with_desc(info->l1, desc) ||
            dfsan_has_label_with_desc(info->l2, desc);
   } else {
     return internal_strcmp(desc, info->desc) == 0;
   }
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE uptr
 dfsan_get_label_count(void) {
   dfsan_label max_label_allocated =
       atomic_load(&__dfsan_last_label, memory_order_relaxed);
 
   return static_cast<uptr>(max_label_allocated);
 }
 
 extern "C" SANITIZER_INTERFACE_ATTRIBUTE void
 dfsan_dump_labels(int fd) {
-  if (flags().fast16labels)
-    return;
-
   dfsan_label last_label =
       atomic_load(&__dfsan_last_label, memory_order_relaxed);
   for (uptr l = 1; l <= last_label; ++l) {
     char buf[64];
     internal_snprintf(buf, sizeof(buf), "%u %u %u ", l,
                       __dfsan_label_info[l].l1, __dfsan_label_info[l].l2);
     WriteToFile(fd, buf, internal_strlen(buf));
     if (__dfsan_label_info[l].l1 == 0 && __dfsan_label_info[l].desc) {

compiler-rt/lib/dfsan/dfsan_flags.inc

DFSAN_FLAG(
     bool, strict_data_dependencies, true,
     "Whether to propagate labels only when there is an obvious data dependency"
     "(e.g., when comparing strings, ignore the fact that the output of the"
     "comparison might be data-dependent on the content of the strings). This"
     "applies only to the custom functions defined in 'custom.c'.")
 DFSAN_FLAG(const char *, dump_labels_at_exit, "", "The path of the file where "
                                                   "to dump the labels when the "
                                                   "program terminates.")
-DFSAN_FLAG(bool, fast16labels, false,
-    "Enables experimental mode where DFSan supports only 16 power-of-2 labels "
-    "(1, 2, 4, 8, ... 32768) and the label union is computed as a bit-wise OR."
-)

compiler-rt/lib/dfsan/done_abilist.txt

 fun:dfsan_has_label=uninstrumented
 fun:dfsan_has_label=discard
 fun:dfsan_has_label_with_desc=uninstrumented
 fun:dfsan_has_label_with_desc=discard
 fun:dfsan_set_write_callback=uninstrumented
 fun:dfsan_set_write_callback=custom
 fun:dfsan_flush=uninstrumented
 fun:dfsan_flush=discard
+fun:dfsan_use_fast16labels=uninstrumented
+fun:dfsan_use_fast16labels=discard
 
 ###############################################################################
 # glibc
 ###############################################################################
 fun:malloc=discard
 fun:free=discard
 
 # Functions that return a value that depends on the input, but the output might

compiler-rt/lib/fuzzer/FuzzerDataFlowTrace.cpp

int CollectDataFlow(const std::string &DFTBinary, const std::string &DirPath,
                     const Vector<SizedFile> &CorporaFiles) {
   Printf("INFO: collecting data flow: bin: %s dir: %s files: %zd\n",
          DFTBinary.c_str(), DirPath.c_str(), CorporaFiles.size());
   if (CorporaFiles.empty()) {
     Printf("ERROR: can't collect data flow without corpus provided.");
     return 1;
   }
 
-  static char DFSanEnv[] = "DFSAN_OPTIONS=fast16labels=1:warn_unimplemented=0";
+  static char DFSanEnv[] = "DFSAN_OPTIONS=warn_unimplemented=0";
   putenv(DFSanEnv);
   MkDir(DirPath);
   for (auto &F : CorporaFiles) {
     // For every input F we need to collect the data flow and the coverage.
     // Data flow collection may fail if we request too many DFSan tags at once.
     // So, we start from requesting all tags in range [0,Size) and if that fails
     // we then request tags in [0,Size/2) and [Size/2, Size), and so on.
     // Function number => DFT.

compiler-rt/lib/fuzzer/dataflow/DataFlow.cpp

 //
 // It executes the fuzz target on the given input while monitoring the
 // data flow for every instrumented comparison instruction.
 //
 // The output shows which functions depend on which bytes of the input,
 // and also provides basic-block coverage for every input.
 //
 // Build:
-//   1. Compile this file (DataFlow.cpp) with -fsanitize=dataflow and -O2.
+//   1. Compile this file (DataFlow.cpp) with -fsanitize=dataflow -mllvm
+//       -dfsan-fast-16-labels and -O2.
 //   2. Compile DataFlowCallbacks.cpp with -O2 -fPIC.
 //   3. Build the fuzz target with -g -fsanitize=dataflow
+//       -mllvm -dfsan-fast-16-labels
 //       -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp
 //   4. Link those together with -fsanitize=dataflow
 //
 //  -fsanitize-coverage=trace-cmp inserts callbacks around every comparison
 //  instruction, DFSan modifies the calls to pass the data flow labels.
 //  The callbacks update the data flow label for the current function.
 //  See e.g. __dfsw___sanitizer_cov_trace_cmp1 below.
 //
 //  -fsanitize-coverage=trace-pc-guard,pc-table,bb instruments function
 //  entries so that the comparison callback knows that current function.
 //  -fsanitize-coverage=...,bb also allows to collect basic block coverage.
 //
 //
 // Run:
 //   # Collect data flow and coverage for INPUT_FILE
 //   # write to OUTPUT_FILE (default: stdout)
-//   export DFSAN_OPTIONS=fast16labels=1:warn_unimplemented=0
+//   export DFSAN_OPTIONS=warn_unimplemented=0
 //   ./a.out INPUT_FILE [OUTPUT_FILE]
 //
 //   # Print all instrumented functions. llvm-symbolizer must be present in PATH
 //   ./a.out
 //
 // Example output:
 // ===============
 //  F0 11111111111111

compiler-rt/test/dfsan/fast16labels.c

-// RUN: %clang_dfsan %s -o %t
-// RUN: DFSAN_OPTIONS=fast16labels=1 %run %t
-// RUN: DFSAN_OPTIONS=fast16labels=1 not %run %t dfsan_create_label 2>&1 \
-// RUN:   | FileCheck %s --check-prefix=CREATE-LABEL
-// RUN: DFSAN_OPTIONS=fast16labels=1 not %run %t dfsan_get_label_info 2>&1 \
-// RUN:   | FileCheck %s --check-prefix=GET-LABEL-INFO
-// RUN: DFSAN_OPTIONS=fast16labels=1 not %run %t dfsan_has_label_with_desc \
-// RUN:   2>&1 | FileCheck %s --check-prefix=HAS-LABEL-WITH-DESC
-//
-// Tests DFSAN_OPTIONS=fast16labels=1
+// RUN: %clang_dfsan %s -mllvm -dfsan-fast-16-labels -o %t
+// RUN: %run %t
 //
+// Tests fast16labels mode.
+
 #include <sanitizer/dfsan_interface.h>
 
 #include <assert.h>
 #include <stdio.h>
 #include <string.h>
 
 int foo(int a, int b) {
   return a + b;
 }
 
 int main(int argc, char *argv[]) {
-  // Death tests for unsupported API usage.
-  const char *command = (argc < 2) ? "" : argv[1];
-  // CREATE-LABEL: FATAL: DataFlowSanitizer: dfsan_create_label is unsupported
-  if (strcmp(command, "dfsan_create_label") == 0)
-    dfsan_create_label("", NULL);
-  // GET-LABEL-INFO: FATAL: DataFlowSanitizer: dfsan_get_label_info is unsupported
-  if (strcmp(command, "dfsan_get_label_info") == 0)
-    dfsan_get_label_info(1);
-  // HAS-LABEL-WITH-DESC: FATAL: DataFlowSanitizer: dfsan_has_label_with_desc is unsupported
-  if (strcmp(command, "dfsan_has_label_with_desc") == 0)
-    dfsan_has_label_with_desc(1, "");
-
-  // Supported usage.
   int a = 10;
   int b = 20;
   dfsan_set_label(8, &a, sizeof(a));
   dfsan_set_label(512, &b, sizeof(b));
   int c = foo(a, b);
   printf("A: 0x%x\n", dfsan_get_label(a));
   printf("B: 0x%x\n", dfsan_get_label(b));
   dfsan_label l = dfsan_get_label(c);
   printf("C: 0x%x\n", l);
   assert(l == 520);  // OR of the other two labels.
-  assert(dfsan_has_label(l, 8));
-  assert(dfsan_has_label(l, 512));
-  assert(!dfsan_has_label(l, 1));
 }

compiler-rt/test/fuzzer/dataflow.test

 # Tests the data flow tracer.
 REQUIRES: linux, x86_64
 
 # Build the tracer and the test.
-RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fsanitize=dataflow  %S/../../lib/fuzzer/dataflow/DataFlow.cpp -o  %t-DataFlow.o
+RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fsanitize=dataflow -mllvm -dfsan-fast-16-labels  %S/../../lib/fuzzer/dataflow/DataFlow.cpp -o  %t-DataFlow.o
 RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fPIC                %S/../../lib/fuzzer/dataflow/DataFlowCallbacks.cpp -o  %t-DataFlowCallbacks.o
-RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/ThreeFunctionsTest.cpp     %t-DataFlow*.o -o %t-ThreeFunctionsTestDF
-RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/Labels20Test.cpp     %t-DataFlow*.o -o %t-Labels20TestDF
+RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -mllvm -dfsan-fast-16-labels -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/ThreeFunctionsTest.cpp     %t-DataFlow*.o -o %t-ThreeFunctionsTestDF
+RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -mllvm -dfsan-fast-16-labels -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/Labels20Test.cpp     %t-DataFlow*.o -o %t-Labels20TestDF
 RUN: %cpp_compiler %S/ThreeFunctionsTest.cpp -o %t-ThreeFunctionsTest
 
 # Dump the function list.
 RUN:  %t-ThreeFunctionsTestDF 2>&1 | FileCheck %s --check-prefix=FUNC_LIST
 FUNC_LIST-DAG: LLVMFuzzerTestOneInput
 FUNC_LIST-DAG: Func1
 FUNC_LIST-DAG: Func2
 
 # Prepare the inputs.
 RUN: rm -rf %t/IN %t/IN20
 RUN: mkdir -p %t/IN %t/IN20
 RUN: echo -n ABC    > %t/IN/ABC
 RUN: echo -n FUABC  > %t/IN/FUABC
 RUN: echo -n FUZZR  > %t/IN/FUZZR
 RUN: echo -n FUZZM  > %t/IN/FUZZM
 RUN: echo -n FUZZMU > %t/IN/FUZZMU
 RUN: echo -n 1234567890123456 > %t/IN/1234567890123456
 
 RUN: echo -n FUZZxxxxxxxxxxxxxxxx > %t/IN20/FUZZxxxxxxxxxxxxxxxx
 RUN: echo -n FUZZxxxxxxxxxxxxMxxx > %t/IN20/FUZZxxxxxxxxxxxxMxxx
 RUN: echo -n FUZxxxxxxxxxxxxxxxxx > %t/IN20/FUZxxxxxxxxxxxxxxxxx
 RUN: echo -n FUxxxxxxxxxxxxxxxxxx > %t/IN20/FUxxxxxxxxxxxxxxxxxx
 
 
-RUN: export DFSAN_OPTIONS=fast16labels=1:warn_unimplemented=0
+RUN: export DFSAN_OPTIONS=warn_unimplemented=0
 
 # This test assumes that the functions in ThreeFunctionsTestDF are instrumented
 # in a specific order:
 # LLVMFuzzerTestOneInput: F0
 # Func1: F1
 # Func2: F2
 
 # ABC: No data is used

compiler-rt/test/fuzzer/only-some-bytes-fork.test

 # Tests the data flow tracer.
 REQUIRES: linux, x86_64
 
 # Build the tracer and the test.
-RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fsanitize=dataflow  %S/../../lib/fuzzer/dataflow/DataFlow.cpp -o  %t-DataFlow.o
+RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fsanitize=dataflow -mllvm -dfsan-fast-16-labels %S/../../lib/fuzzer/dataflow/DataFlow.cpp -o  %t-DataFlow.o
 RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fPIC                %S/../../lib/fuzzer/dataflow/DataFlowCallbacks.cpp -o  %t-DataFlowCallbacks.o
-RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/OnlySomeBytesTest.cpp     %t-DataFlow*.o -o %t-DFT
+RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -mllvm -dfsan-fast-16-labels -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/OnlySomeBytesTest.cpp     %t-DataFlow*.o -o %t-DFT
 RUN: %cpp_compiler %S/OnlySomeBytesTest.cpp -o %t-Fuzz
 
 # Test that the fork mode can collect and use the DFT
 RUN: rm -rf %t && mkdir %t
 RUN: not %t-Fuzz -collect_data_flow=%t-DFT -use_value_profile=1 -runs=100000000 -fork=20 2> %t/log
 RUN: grep BINGO %t/log

compiler-rt/test/fuzzer/only-some-bytes.test

 # Tests the data flow tracer.
 REQUIRES: linux, x86_64
 
 # Build the tracer and the test.
-RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fsanitize=dataflow  %S/../../lib/fuzzer/dataflow/DataFlow.cpp -o  %t-DataFlow.o
+RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fsanitize=dataflow -mllvm -dfsan-fast-16-labels %S/../../lib/fuzzer/dataflow/DataFlow.cpp -o  %t-DataFlow.o
 RUN: %no_fuzzer_cpp_compiler -c -fno-sanitize=all -fPIC                %S/../../lib/fuzzer/dataflow/DataFlowCallbacks.cpp -o  %t-DataFlowCallbacks.o
-RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/OnlySomeBytesTest.cpp     %t-DataFlow*.o -o %t-DFT
+RUN: %no_fuzzer_cpp_compiler    -fno-sanitize=all -fsanitize=dataflow -mllvm -dfsan-fast-16-labels -fsanitize-coverage=trace-pc-guard,pc-table,bb,trace-cmp   %S/OnlySomeBytesTest.cpp     %t-DataFlow*.o -o %t-DFT
 RUN: %cpp_compiler %S/OnlySomeBytesTest.cpp -o %t-Fuzz
 
 # Prepare the inputs.
 RUN: rm -rf %t/*
 RUN: mkdir -p %t/IN
 RUN: echo -n 0123456789012345678901234567890123456789012345678901234567891234 > %t/IN/6
 RUN: cat  %t/IN/6 %t/IN/6 %t/IN/6 %t/IN/6 > %t/IN/8
 RUN: cat  %t/IN/8 %t/IN/8 %t/IN/8 %t/IN/8 > %t/IN/10

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

 //   void __dfsan_store_callback(dfsan_label Label);
 //   void __dfsan_mem_transfer_callback(dfsan_label *Start, size_t Len);
 //   void __dfsan_cmp_callback(dfsan_label CombinedLabel);
 static cl::opt<bool> ClEventCallbacks(
     "dfsan-event-callbacks",
     cl::desc("Insert calls to __dfsan_*_callback functions on data events."),
     cl::Hidden, cl::init(false));
 
+// Use a distinct bit for each base label, enabling faster unions with less
+// instrumentation.  Limits the max number of base labels to 16.
+static cl::opt<bool> ClFast16Labels(
+    "dfsan-fast-16-labels",
+    cl::desc("Use more efficient instrumentation, limiting the number of "
+             "labels to 16."),
+    cl::Hidden, cl::init(false));
+
 static StringRef GetGlobalTypeString(const GlobalValue &G) {
   // Types of GlobalVariables are always pointer types.
   Type *GType = G.getValueType();
   // For now we support excluding struct types only.
   if (StructType *SGType = dyn_cast<StructType>(GType)) {
     if (!SGType->isLiteral())
       return SGType->getName();
   }
class DataFlowSanitizer {
   FunctionType *DFSanSetLabelFnTy;
   FunctionType *DFSanNonzeroLabelFnTy;
   FunctionType *DFSanVarargWrapperFnTy;
   FunctionType *DFSanLoadStoreCmpCallbackFnTy;
   FunctionType *DFSanMemTransferCallbackFnTy;
   FunctionCallee DFSanUnionFn;
   FunctionCallee DFSanCheckedUnionFn;
   FunctionCallee DFSanUnionLoadFn;
+  FunctionCallee DFSanUnionLoadFast16LabelsFn;
   FunctionCallee DFSanUnimplementedFn;
   FunctionCallee DFSanSetLabelFn;
   FunctionCallee DFSanNonzeroLabelFn;
   FunctionCallee DFSanVarargWrapperFn;
   FunctionCallee DFSanLoadCallbackFn;
   FunctionCallee DFSanStoreCallbackFn;
   FunctionCallee DFSanMemTransferCallbackFn;
   FunctionCallee DFSanCmpCallbackFn;
AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex,
                          Attribute::NoUnwind);
     AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex,
                          Attribute::ReadOnly);
     AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex,
                          Attribute::ZExt);
     DFSanUnionLoadFn =
         Mod->getOrInsertFunction("__dfsan_union_load", DFSanUnionLoadFnTy, AL);
   }
+  {
+    AttributeList AL;
+    AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex,
+                         Attribute::NoUnwind);
+    AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex,
+                         Attribute::ReadOnly);
+    AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex,
+                         Attribute::ZExt);
+    DFSanUnionLoadFast16LabelsFn = Mod->getOrInsertFunction(
+        "__dfsan_union_load_fast16labels", DFSanUnionLoadFnTy, AL);
+  }
   DFSanUnimplementedFn =
       Mod->getOrInsertFunction("__dfsan_unimplemented", DFSanUnimplementedFnTy);
   {
     AttributeList AL;
     AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt);
     DFSanSetLabelFn =
         Mod->getOrInsertFunction("__dfsan_set_label", DFSanSetLabelFnTy, AL);
   }
   DFSanNonzeroLabelFn =
       Mod->getOrInsertFunction("__dfsan_nonzero_label", DFSanNonzeroLabelFnTy);
   DFSanVarargWrapperFn = Mod->getOrInsertFunction("__dfsan_vararg_wrapper",
                                                   DFSanVarargWrapperFnTy);
 }
 
 // Initializes event callback functions and declare them in the module
 void DataFlowSanitizer::initializeCallbackFunctions(Module &M) {
   DFSanLoadCallbackFn = Mod->getOrInsertFunction("__dfsan_load_callback",
                                                  DFSanLoadStoreCmpCallbackFnTy);
   DFSanStoreCallbackFn = Mod->getOrInsertFunction(
       "__dfsan_store_callback", DFSanLoadStoreCmpCallbackFnTy);
   DFSanMemTransferCallbackFn = Mod->getOrInsertFunction(
       "__dfsan_mem_transfer_callback", DFSanMemTransferCallbackFnTy);
bool DataFlowSanitizer::runImpl(Module &M) {
 
   std::vector<Function *> FnsToInstrument;
   SmallPtrSet<Function *, 2> FnsWithNativeABI;
   for (Function &i : M) {
     if (!i.isIntrinsic() &&
         &i != DFSanUnionFn.getCallee()->stripPointerCasts() &&
         &i != DFSanCheckedUnionFn.getCallee()->stripPointerCasts() &&
         &i != DFSanUnionLoadFn.getCallee()->stripPointerCasts() &&
+        &i != DFSanUnionLoadFast16LabelsFn.getCallee()->stripPointerCasts() &&
         &i != DFSanUnimplementedFn.getCallee()->stripPointerCasts() &&
         &i != DFSanSetLabelFn.getCallee()->stripPointerCasts() &&
         &i != DFSanNonzeroLabelFn.getCallee()->stripPointerCasts() &&
         &i != DFSanVarargWrapperFn.getCallee()->stripPointerCasts() &&
         &i != DFSanLoadCallbackFn.getCallee()->stripPointerCasts() &&
         &i != DFSanStoreCallbackFn.getCallee()->stripPointerCasts() &&
         &i != DFSanMemTransferCallbackFn.getCallee()->stripPointerCasts() &&
         &i != DFSanCmpCallbackFn.getCallee()->stripPointerCasts())
bool DataFlowSanitizer::runImpl(Module &M) {
 
   return Changed || !FnsToInstrument.empty() ||
          M.global_size() != InitialGlobalSize || M.size() != InitialModuleSize;
 }
 
 Value *DFSanFunction::getArgTLSPtr() {
   if (ArgTLSPtr)
     return ArgTLSPtr;
   if (DFS.ArgTLS)
     return ArgTLSPtr = DFS.ArgTLS;
 
   IRBuilder<> IRB(&F->getEntryBlock().front());
   return ArgTLSPtr = IRB.CreateCall(DFS.GetArgTLSTy, DFS.GetArgTLS, {});
 }
 
 Value *DFSanFunction::getRetvalTLS() {
   if (RetvalTLSPtr)
Value *DFSanFunction::combineShadows(Value *V1, Value *V2, Instruction *Pos) {
   auto Key = std::make_pair(V1, V2);
   if (V1 > V2)
     std::swap(Key.first, Key.second);
   CachedCombinedShadow &CCS = CachedCombinedShadows[Key];
   if (CCS.Block && DT.dominates(CCS.Block, Pos->getParent()))
     return CCS.Shadow;
 
   IRBuilder<> IRB(Pos);
-  if (AvoidNewBlocks) {
+  if (ClFast16Labels) {
+    CCS.Block = Pos->getParent();
+    CCS.Shadow = IRB.CreateOr(V1, V2);
+  } else if (AvoidNewBlocks) {
     CallInst *Call = IRB.CreateCall(DFS.DFSanCheckedUnionFn, {V1, V2});
     Call->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt);
     Call->addParamAttr(0, Attribute::ZExt);
     Call->addParamAttr(1, Attribute::ZExt);
 
     CCS.Block = Pos->getParent();
     CCS.Shadow = Call;
   } else {
case 2: {
     IRBuilder<> IRB(Pos);
     Value *ShadowAddr1 = IRB.CreateGEP(DFS.ShadowTy, ShadowAddr,
                                        ConstantInt::get(DFS.IntptrTy, 1));
     return combineShadows(
         IRB.CreateAlignedLoad(DFS.ShadowTy, ShadowAddr, ShadowAlign),
         IRB.CreateAlignedLoad(DFS.ShadowTy, ShadowAddr1, ShadowAlign), Pos);
   }
   }
+
+  if (ClFast16Labels && Size % (64 / DFS.ShadowWidthBits) == 0) {
+    // First OR all the WideShadows, then OR individual shadows within the
+    // combined WideShadow.  This is fewer instructions than ORing shadows
+    // individually.
+    IRBuilder<> IRB(Pos);
+    Value *WideAddr =
+        IRB.CreateBitCast(ShadowAddr, Type::getInt64PtrTy(*DFS.Ctx));
+    Value *CombinedWideShadow =
+        IRB.CreateAlignedLoad(IRB.getInt64Ty(), WideAddr, ShadowAlign);
+    for (uint64_t Ofs = 64 / DFS.ShadowWidthBits; Ofs != Size;
+         Ofs += 64 / DFS.ShadowWidthBits) {
+      WideAddr = IRB.CreateGEP(Type::getInt64Ty(*DFS.Ctx), WideAddr,
+                               ConstantInt::get(DFS.IntptrTy, 1));
+      Value *NextWideShadow =
+          IRB.CreateAlignedLoad(IRB.getInt64Ty(), WideAddr, ShadowAlign);
+      CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, NextWideShadow);
+    }
+    for (unsigned Width = 32; Width >= DFS.ShadowWidthBits; Width >>= 1) {
+      Value *ShrShadow = IRB.CreateLShr(CombinedWideShadow, Width);
+      CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, ShrShadow);
+    }
+    return IRB.CreateTrunc(CombinedWideShadow, DFS.ShadowTy);
+  }
   if (!AvoidNewBlocks && Size % (64 / DFS.ShadowWidthBits) == 0) {
     // Fast path for the common case where each byte has identical shadow: load
     // shadow 64 bits at a time, fall out to a __dfsan_union_load call if any
     // shadow is non-equal.
     BasicBlock *FallbackBB = BasicBlock::Create(*DFS.Ctx, "", F);
     IRBuilder<> FallbackIRB(FallbackBB);
     CallInst *FallbackCall = FallbackIRB.CreateCall(
         DFS.DFSanUnionLoadFn,
if (!AvoidNewBlocks && Size % (64 / DFS.ShadowWidthBits) == 0) {
     FallbackIRB.CreateBr(Tail);
     PHINode *Shadow = PHINode::Create(DFS.ShadowTy, 2, "", &Tail->front());
     Shadow->addIncoming(FallbackCall, FallbackBB);
     Shadow->addIncoming(TruncShadow, LastBr->getParent());
     return Shadow;
   }
 
   IRBuilder<> IRB(Pos);
+  FunctionCallee &UnionLoadFn =
+      ClFast16Labels ? DFS.DFSanUnionLoadFast16LabelsFn : DFS.DFSanUnionLoadFn;
   CallInst *FallbackCall = IRB.CreateCall(
-      DFS.DFSanUnionLoadFn, {ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)});
+      UnionLoadFn, {ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)});
   FallbackCall->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt);
   return FallbackCall;
 }
 
 void DFSanVisitor::visitLoadInst(LoadInst &LI) {
   auto &DL = LI.getModule()->getDataLayout();
   uint64_t Size = DL.getTypeStoreSize(LI.getType());
   if (Size == 0) {

llvm/test/Instrumentation/DataFlowSanitizer/fast16labels.ll

+; Test that -dfsan-fast-16-labels mode uses inline ORs rather than calling
+; __dfsan_union or __dfsan_union_load.
+; RUN: opt < %s -dfsan -dfsan-fast-16-labels -S | FileCheck %s --implicit-check-not="call{{.*}}__dfsan_union"
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i8 @add(i8 %a, i8 %b) {
+  ; CHECK-LABEL: define i8 @"dfs$add"
+  ; CHECK-DAG: %[[ALABEL:.*]] = load{{.*}}__dfsan_arg_tls, i64 0, i64 0
+  ; CHECK-DAG: %[[BLABEL:.*]] = load{{.*}}__dfsan_arg_tls, i64 0, i64 1
+  ; CHECK: %[[ADDLABEL:.*]] = or i16 %[[ALABEL]], %[[BLABEL]]
+  ; CHECK: add i8
+  ; CHECK: store i16 %[[ADDLABEL]], i16* @__dfsan_retval_tls
+  ; CHECK: ret i8
+  %c = add i8 %a, %b
+  ret i8 %c
+}
+
+define i8 @load8(i8* %p) {
+  ; CHECK-LABEL: define i8 @"dfs$load8"
+  ; CHECK: load i16, i16*
+  ; CHECK: ptrtoint i8* {{.*}} to i64
+  ; CHECK: and i64
+  ; CHECK: mul i64
+  ; CHECK: inttoptr i64
+  ; CHECK: load i16, i16*
+  ; CHECK: or i16
+  ; CHECK: load i8, i8*
+  ; CHECK: store i16 {{.*}} @__dfsan_retval_tls
+  ; CHECK: ret i8
+
+  %a = load i8, i8* %p
+  ret i8 %a
+}
+
+define i16 @load16(i16* %p) {
+  ; CHECK-LABEL: define i16 @"dfs$load16"
+  ; CHECK: ptrtoint i16*
+  ; CHECK: and i64
+  ; CHECK: mul i64
+  ; CHECK: inttoptr i64 {{.*}} i16*
+  ; CHECK: getelementptr i16
+  ; CHECK: load i16, i16*
+  ; CHECK: load i16, i16*
+  ; CHECK: or i16
+  ; CHECK: or i16
+  ; CHECK: load i16, i16*
+  ; CHECK: store {{.*}} @__dfsan_retval_tls
+  ; CHECK: ret i16
+
+  %a = load i16, i16* %p
+  ret i16 %a
+}
+
+define i32 @load32(i32* %p) {
+  ; CHECK-LABEL: define i32 @"dfs$load32"
+  ; CHECK: ptrtoint i32*
+  ; CHECK: and i64
+  ; CHECK: mul i64
+  ; CHECK: inttoptr i64 {{.*}} i16*
+  ; CHECK: bitcast i16* {{.*}} i64*
+  ; CHECK: load i64, i64*
+  ; CHECK: lshr i64 {{.*}}, 32
+  ; CHECK: or i64
+  ; CHECK: lshr i64 {{.*}}, 16
+  ; CHECK: or i64
+  ; CHECK: trunc i64 {{.*}} i16
+  ; CHECK: or i16
+  ; CHECK: load i32, i32*
+  ; CHECK: store i16 {{.*}} @__dfsan_retval_tls
+  ; CHECK: ret i32
+
+  %a = load i32, i32* %p
+  ret i32 %a
+}
+
+define i64 @load64(i64* %p) {
+  ; CHECK-LABEL: define i64 @"dfs$load64"
+  ; CHECK: ptrtoint i64*
+  ; CHECK: and i64
+  ; CHECK: mul i64
+  ; CHECK: inttoptr i64 {{.*}} i16*
+  ; CHECK: bitcast i16* {{.*}} i64*
+  ; CHECK: load i64, i64*
+  ; CHECK: getelementptr i64, i64* {{.*}}, i64 1
+  ; CHECK: load i64, i64*
+  ; CHECK: or i64
+  ; CHECK: lshr i64 {{.*}}, 32
+  ; CHECK: or i64
+  ; CHECK: lshr i64 {{.*}}, 16
+  ; CHECK: or i64
+  ; CHECK: trunc i64 {{.*}} i16
+  ; CHECK: or i16
+  ; CHECK: load i64, i64*
+  ; CHECK: store i16 {{.*}} @__dfsan_retval_tls
+  ; CHECK: ret i64
+
+  %a = load i64, i64* %p
+  ret i64 %a
+}