Add -fsanitizer-coverage=control-flow

[Navidem]

Bring in the missing commits.

[kcc]

Cool!
please add the documentation and the run-time test to the same CL.

A'll let Vitaly do the next pass of the code, but will review the documentation.

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1055

remove if not needed any more

1057

declare at the first point of use

1061

"can not" ?

1068

hmmm... is it even possible?

1077–1078

typical LLVM code uses this:

if (CallBase *CB = ...)) { ...}

[Navidem]

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1061

Actually I started with "can not", but saw the error message from opt saying "may not". Changing anyways :)

1068

I was being cautious here for the branches (like goto) to the beginning of the function.
But later once checked a concrete example, I was not able to produce such scenario.

something like the following code breaks the entry basic block:

int foo (int x) {
top:
  x += 5;
  if (x > 5)
    bar(x);
  else
    goto top;

  return x;
}

define dso_local i32 @foo(i32 noundef %x) #0 {
entry:
  %x.addr = alloca i32, align 4
  store i32 %x, ptr %x.addr, align 4
  br label %top

top:                                              ; preds = %if.else, %entry
  %0 = load i32, ptr %x.addr, align 4
  %add = add nsw i32 %0, 5
  store i32 %add, ptr %x.addr, align 4
  %1 = load i32, ptr %x.addr, align 4
  %cmp = icmp sgt i32 %1, 5
  br i1 %cmp, label %if.then, label %if.else

if.then:                                          ; preds = %top
  %2 = load i32, ptr %x.addr, align 4
  call void @bar(i32 noundef %2)
  br label %if.end

if.else:                                          ; preds = %top
  br label %top

if.end:                                           ; preds = %if.then
  %3 = load i32, ptr %x.addr, align 4
  ret i32 %3
}

If you think it is impossible, I am fine with simplifying the code here.

[kcc]

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1068

yea, please simplify. ok to leave an assert

[Navidem]

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1068

Happy to!

[Navidem]

Apply comments.

[vitalybuka]

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1055

something more specific, or just remove it?

1061

what does happen?

1062

Here, I guess, "C ? A : B" operator is nicer

1063

static_cast or dyn_cast

1092–1093

llvm/test/Instrumentation/SanitizerCoverage/control-flow.ll

3

you don't have to, but may try to generate test with
llvm/utils/update_test_checks.py --opt-binary bin/opt llvm/test/Instrumentation/SanitizerCoverage/control-flow.ll

It could be reasonable, or not

12

the test does not cover CallBase

[vitalybuka]

the test is gone?

[Navidem]

In D133157#3765866, @vitalybuka wrote:

the test is gone?

Sorry, first time user of arcanist here! The test file is missed from this upgrade somehow :/

[Navidem]

Updated docs, lit test, and added clang option.

[Navidem]

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1061

Gives invalid IR error if blockaddress is used with function entry as arg.

1063

Please check lines 739-746. This usage pattern is already there. Should we change those as well?

[Navidem]

llvm/test/Instrumentation/SanitizerCoverage/control-flow.ll

3

Thanks! I tried it and it added many more checks, which does not seem very useful? Please let me know if you see some value in having these:

+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    call void @__sanitizer_cov_trace_pc_guard(i32* getelementptr inbounds ([3 x i32], [3 x i32]* @__sancov_gen_.1, i32 0, i32 0)) #[[ATTR2:[0-9]+]]
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32* [[A:%.*]], null
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[ENTRY_IF_END_CRIT_EDGE:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       entry.if.end_crit_edge:
+; CHECK-NEXT:    call void @__sanitizer_cov_trace_pc_guard(i32* inttoptr (i64 add (i64 ptrtoint ([3 x i32]* @__sancov_gen_.1 to i64), i64 4) to i32*)) #[[ATTR2]]
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @__sanitizer_cov_trace_pc_guard(i32* inttoptr (i64 add (i64 ptrtoint ([3 x i32]* @__sancov_gen_.1 to i64), i64 8) to i32*)) #[[ATTR2]]
+; CHECK-NEXT:    store i32 0, i32* [[A]], align 4
+; CHECK-NEXT:    call void @foo(i32* [[A]])
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+;

[Navidem]

Added an initial run-time test

[vitalybuka]

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

4 ↗

(On Diff #457754)

this code does not use assertions, so this this flag is not needed

4 ↗

(On Diff #457754)

similar tests set

REQUIRES: has_sancovcc,stable-runtime
UNSUPPORTED: i386-darwin, x86_64-darwin

11 ↗

(On Diff #457754)

Could you please move this test into a separate patch, I suspect this one likely than the rest will be reverted of platforms with limited runtime

38 ↗

(On Diff #457754)

you can use
// RUN: llvm-objdump ... | FIleCheck %s

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1063

Then keep as-is in this patch
you are welcome to fix this in followup patch :)

1069

wouldn't be better to prefix with count instead of separator?

1070

1083

getNullValue

[MaskRay]

clang/docs/SanitizerCoverage.rst

338

This paragraph doesn't describe how the table is encoded.

The description about null-separated is incorrect as it is actually null-ended.

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

1054

Use collectFunctionControlFlow for new functions. CamelCaseFunction is legacy.

I'd prefer createXXX since collectXXX implies returning the object while the function actually creates the needed metadata.

1086

-Wunused-variable

1087

I'd avoid the variable in favor of FunctionCFsArray

llvm/test/Instrumentation/SanitizerCoverage/control-flow.ll

2

End complete sentences in comments with .

7

Avoid i32*. Use opaque pointers ptr for new tests.

[MaskRay]

Add -sanitizer-coverage-control-flow

Add -fsanitizer-coverage=control-flow

[Navidem]

Apply comments.

[vitalybuka]

clang/lib/Driver/SanitizerArgs.cpp

807

shouldn't this be:
,[trace-pc-guard|trace-pc],[control-flow]

probably even:
[,(trace-pc-guard|trace-pc)][,control-flow]

[Navidem]

Add __sanitizer_cov_cfs_init

[Navidem]

Update doc

[Navidem]

clang/lib/Driver/SanitizerArgs.cpp

807

shouldn't this be:
,[trace-pc-guard|trace-pc],[control-flow]

probably even:
[,(trace-pc-guard|trace-pc)][,control-flow]

[vitalybuka]

clang/docs/SanitizerCoverage.rst

382

we can also generate normal structs, per function, and pass them into __sanitizer_cov_cfs_init(const MyStruct* begin, const MyStruct* end);
this was can avoid this magic encoding completely?

clang/lib/Driver/SanitizerArgs.cpp

814

why do you need CoverageEdge if enabled CoverageControlFlow?

[vitalybuka]

we need to update
llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_coverage_interface.inc
llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_interface_internal.h

you can search by __sanitizer_cov_8bit_counters_init if anything missing

Something like SingletonCounterCoverage could be useful.

[vitalybuka]

clang/docs/SanitizerCoverage.rst

382

Works for me either way. @kcc WDYT?

[Navidem]

Bring back the runtime test.

clang/lib/Driver/SanitizerArgs.cpp

807

shouldn't this be:
,[trace-pc-guard|trace-pc],[control-flow]

This makes sense, thanks!

814

No essential need, but here I am implicitly enabling edge when instrumentation type is not specified. This was the way that I could get -fsanitizer-coverage=control-flow working without passing -fsanitizer-coverage=bb,control-flow.

[kcc]

clang/docs/SanitizerCoverage.rst

382

The struct will still have some variable length arrays, right?
Will it be any better?

MyStruct will have to be defined there, and there is no header file for sancov for users to include, and I don't think I want one.

[kcc]

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

1 ↗

(On Diff #459201)

I suggest to make this test smaller:

• foo() can by empty (but avoid inlining)
• main() can have a single conditional call to foo

• main should also have a single conditional indirect call to test the -1 indir call marker.

• __sanitizer_cov_cfs_init should capture its arguments and return

• main should insepct the arguments captured in __sanitizer_cov_cfs_init and verify that it sees main() and foo(), and that main contains calls to foo() and indir function, outside of the entry BB.

[Navidem]

Update the rt test

[vitalybuka]

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

15 ↗

(On Diff #460215)

would you like to add some printing function as for other coverage types?

64 ↗

(On Diff #460215)

new line

[vitalybuka]

LGTM as-is

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

15 ↗

(On Diff #460215)

actually printing can be don't in follow up patch, but it may simplify the test, you will not need iterate it in the test.

[Navidem]

Enhance rt test.

[Navidem]

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

15 ↗

(On Diff #460215)

actually printing can be don't in follow up patch, but it may simplify the test, you will not need iterate it in the test.

I'm not sure I follow what you are suggesting.

[vitalybuka]

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

15 ↗

(On Diff #460215)

Check this out D108405
then you can hook your data into DumpCoverage()
then you can replace entire "while (pt < CFS_END) {" loop with set of CHECK:

[kcc]

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

24 ↗

(On Diff #460232)

syntax nit:

auto main_ptr = &main

33 ↗

(On Diff #460232)

I suggest you move this to a separate function, called from main()

67 ↗

(On Diff #460232)

I don't think you are guaranteed to have main and foo in this order, and similarly dir vs indir call in this order.
So, use CHECK-DAG instead of CHECK for these four lines.

[Navidem]

Use CHECK-DAG and separate function for checking.

[Navidem]

compiler-rt/test/sanitizer_common/TestCases/sanitizer_coverage_control_flow.cpp

15 ↗

(On Diff #460215)

Check this out D108405
then you can hook your data into DumpCoverage()
then you can replace entire "while (pt < CFS_END) {" loop with set of CHECK:

I see, thanks for the pointer. I think I leave it for later.

[kcc]

LGTM

[Navidem]

Thanks @kcc @vitalybuka, I do not have commit access.

[vitalybuka]

clang-format

[MaskRay]

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

155

false can be removed

[vitalybuka]

clang test

[vitalybuka]

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

155

I'll keep it for consistency with the rest of file

clang/docs/SanitizerCoverage.rst

.. code-block:: c++
   void __sanitizer_cov_load16(__int128 *addr);
   // Called before a store of appropriate size. Addr is the address of the store.
   void __sanitizer_cov_store1(uint8_t *addr);
   void __sanitizer_cov_store2(uint16_t *addr);
   void __sanitizer_cov_store4(uint32_t *addr);
   void __sanitizer_cov_store8(uint64_t *addr);
   void __sanitizer_cov_store16(__int128 *addr);
 
+
+Tracing control flow
+====================
+
+With ``-fsanitize-coverage=control-flow`` the compiler will create a table to collect
+control flow for each function. More specifically, for each basic block in the function,
+two lists are populated. One list for successors of the basic block and another list for
+non-intrinsic called functions.
+
+**TODO:** in the current implementation, indirect calls are not tracked
+and are only marked with special value (-1) in the list.
+
+Each table row consists of the basic block address
+followed by ``null``-ended lists of successors and callees.
+The table is encoded in a special section named ``sancov_cfs``
+
+Example:
+
+.. code-block:: c++
+  int foo (int x) {
+    if (x > 0)
+      bar(x);
+    else
+      x = 0;
+    return x;
+  }
+
+The code above contains 4 basic blocks, let's name them A, B, C, D:
+
+.. code-block:: none
+
+    A
+    |\
+    | \
+    B  C
+    | /
+    |/
+    D
+
+The collected control flow table is as follows:
+``A, B, C, null, null, B, D, null, @bar, null, C, D, null, null, D, null, null.``
+
+Users need to implement a single function to capture the CF table at startup:
+
+.. code-block:: c++
+
+  extern "C"
+  void __sanitizer_cov_cfs_init(const uintptr_t *cfs_beg,
+                                const uintptr_t *cfs_end) {
+    // [cfs_beg,cfs_end) is the array of ptr-sized integers representing
+    // the collected control flow.
+  }
+
+
 Disabling instrumentation with ``__attribute__((no_sanitize("coverage")))``
 ===========================================================================
 
 It is possible to disable coverage instrumentation for select functions via the
 function attribute ``__attribute__((no_sanitize("coverage")))``. Because this
 attribute may not be supported by other compilers, it is recommended to use it
 together with ``__has_feature(coverage_sanitizer)``.
 

clang/include/clang/Basic/CodeGenOptions.h

#include "clang/Basic/CodeGenOptions.def"
   bool hasMaybeUnusedDebugInfo() const {
     return getDebugInfo() >= codegenoptions::UnusedTypeInfo;
   }
 
   // Check if any one of SanitizeCoverage* is enabled.
   bool hasSanitizeCoverage() const {
     return SanitizeCoverageType || SanitizeCoverageIndirectCalls ||
            SanitizeCoverageTraceCmp || SanitizeCoverageTraceLoads ||
-           SanitizeCoverageTraceStores;
+           SanitizeCoverageTraceStores || SanitizeCoverageControlFlow;
   }
 };
 
 }  // end namespace clang
 
 #endif

clang/include/clang/Basic/CodeGenOptions.def

CODEGENOPT(SanitizeCoverage8bitCounters, 1, 0) ///< Use 8-bit frequency counters
                                                ///< in sanitizer coverage.
 CODEGENOPT(SanitizeCoverageTracePC, 1, 0) ///< Enable PC tracing
                                           ///< in sanitizer coverage.
 CODEGENOPT(SanitizeCoverageTracePCGuard, 1, 0) ///< Enable PC tracing with guard
                                                ///< in sanitizer coverage.
 CODEGENOPT(SanitizeCoverageInline8bitCounters, 1, 0) ///< Use inline 8bit counters.
 CODEGENOPT(SanitizeCoverageInlineBoolFlag, 1, 0) ///< Use inline bool flag.
 CODEGENOPT(SanitizeCoveragePCTable, 1, 0) ///< Create a PC Table.
+CODEGENOPT(SanitizeCoverageControlFlow, 1, 0) ///< Collect control flow
 CODEGENOPT(SanitizeCoverageNoPrune, 1, 0) ///< Disable coverage pruning.
 CODEGENOPT(SanitizeCoverageStackDepth, 1, 0) ///< Enable max stack depth tracing
 CODEGENOPT(SanitizeCoverageTraceLoads, 1, 0) ///< Enable tracing of loads.
 CODEGENOPT(SanitizeCoverageTraceStores, 1, 0) ///< Enable tracing of stores.
 CODEGENOPT(SanitizeStats     , 1, 0) ///< Collect statistics for sanitizers.
 CODEGENOPT(SimplifyLibCalls  , 1, 1) ///< Set when -fbuiltin is enabled.
 CODEGENOPT(SoftFloat         , 1, 0) ///< -soft-float.
 CODEGENOPT(SpeculativeLoadHardening, 1, 0) ///< Enable speculative load hardening.

clang/include/clang/Driver/Options.td

 def fsanitize_coverage_inline_bool_flag
     : Flag<["-"], "fsanitize-coverage-inline-bool-flag">,
       HelpText<"Enable inline bool flag in sanitizer coverage">,
       MarshallingInfoFlag<CodeGenOpts<"SanitizeCoverageInlineBoolFlag">>;
 def fsanitize_coverage_pc_table
     : Flag<["-"], "fsanitize-coverage-pc-table">,
       HelpText<"Create a table of coverage-instrumented PCs">,
       MarshallingInfoFlag<CodeGenOpts<"SanitizeCoveragePCTable">>;
+def fsanitize_coverage_control_flow
+    : Flag<["-"], "fsanitize-coverage-control-flow">,
+      HelpText<"Collect control flow of function">,
+      MarshallingInfoFlag<CodeGenOpts<"SanitizeCoverageControlFlow">>;
 def fsanitize_coverage_trace_pc
     : Flag<["-"], "fsanitize-coverage-trace-pc">,
       HelpText<"Enable PC tracing in sanitizer coverage">,
       MarshallingInfoFlag<CodeGenOpts<"SanitizeCoverageTracePC">>;
 def fsanitize_coverage_trace_pc_guard
     : Flag<["-"], "fsanitize-coverage-trace-pc-guard">,
       HelpText<"Enable PC tracing with guard in sanitizer coverage">,
       MarshallingInfoFlag<CodeGenOpts<"SanitizeCoverageTracePCGuard">>;

clang/lib/CodeGen/BackendUtil.cpp

getSancovOptsFromCGOpts(const CodeGenOptions &CGOpts) {
   Opts.TracePCGuard = CGOpts.SanitizeCoverageTracePCGuard;
   Opts.NoPrune = CGOpts.SanitizeCoverageNoPrune;
   Opts.Inline8bitCounters = CGOpts.SanitizeCoverageInline8bitCounters;
   Opts.InlineBoolFlag = CGOpts.SanitizeCoverageInlineBoolFlag;
   Opts.PCTable = CGOpts.SanitizeCoveragePCTable;
   Opts.StackDepth = CGOpts.SanitizeCoverageStackDepth;
   Opts.TraceLoads = CGOpts.SanitizeCoverageTraceLoads;
   Opts.TraceStores = CGOpts.SanitizeCoverageTraceStores;
+  Opts.CollectControlFlow = CGOpts.SanitizeCoverageControlFlow;
   return Opts;
 }
 
 // Check if ASan should use GC-friendly instrumentation for globals.
 // First of all, there is no point if -fdata-sections is off (expect for MachO,
 // where this is not a factor). Also, on ELF this feature requires an assembler
 // extension that only works with -integrated-as at the moment.
 static bool asanUseGlobalsGC(const Triple &T, const CodeGenOptions &CGOpts) {

clang/lib/Driver/SanitizerArgs.cpp

enum CoverageFeature {
   CoverageTracePCGuard = 1 << 10,
   CoverageNoPrune = 1 << 11,
   CoverageInline8bitCounters = 1 << 12,
   CoveragePCTable = 1 << 13,
   CoverageStackDepth = 1 << 14,
   CoverageInlineBoolFlag = 1 << 15,
   CoverageTraceLoads = 1 << 16,
   CoverageTraceStores = 1 << 17,
+  CoverageControlFlow = 1 << 18,
 };
 
 /// Parse a -fsanitize= or -fno-sanitize= argument's values, diagnosing any
 /// invalid components. Returns a SanitizerMask.
 static SanitizerMask parseArgValues(const Driver &D, const llvm::opt::Arg *A,
                                     bool DiagnoseErrors);
 
 /// Parse -f(no-)?sanitize-coverage= flag values, diagnosing any invalid
if (CoverageFeatures & Coverage8bitCounters)
       D.Diag(clang::diag::warn_drv_deprecated_arg)
           << "-fsanitize-coverage=8bit-counters"
           << "-fsanitize-coverage=trace-pc-guard";
   }
 
   int InsertionPointTypes = CoverageFunc | CoverageBB | CoverageEdge;
   int InstrumentationTypes = CoverageTracePC | CoverageTracePCGuard |
                              CoverageInline8bitCounters | CoverageTraceLoads |
-                             CoverageTraceStores | CoverageInlineBoolFlag;
+                             CoverageTraceStores | CoverageInlineBoolFlag | CoverageControlFlow;
   if ((CoverageFeatures & InsertionPointTypes) &&
       !(CoverageFeatures & InstrumentationTypes) && DiagnoseErrors) {
     D.Diag(clang::diag::warn_drv_deprecated_arg)
         << "-fsanitize-coverage=[func|bb|edge]"
-        << "-fsanitize-coverage=[func|bb|edge],[trace-pc-guard|trace-pc]";
+        << "-fsanitize-coverage=[func|bb|edge],[trace-pc-guard|trace-pc|control-flow]";
   }
 
   // trace-pc w/o func/bb/edge implies edge.
   if (!(CoverageFeatures & InsertionPointTypes)) {
     if (CoverageFeatures &
         (CoverageTracePC | CoverageTracePCGuard | CoverageInline8bitCounters |
-         CoverageInlineBoolFlag))
+         CoverageInlineBoolFlag | CoverageControlFlow))
       CoverageFeatures |= CoverageEdge;
 
     if (CoverageFeatures & CoverageStackDepth)
       CoverageFeatures |= CoverageFunc;
   }
 
   // Parse -fsanitize-coverage-(allow|ignore)list options if coverage enabled.
   // This also validates special case lists format.
std::pair<int, const char *> CoverageFlags[] = {
       std::make_pair(CoverageInline8bitCounters,
                      "-fsanitize-coverage-inline-8bit-counters"),
       std::make_pair(CoverageInlineBoolFlag,
                      "-fsanitize-coverage-inline-bool-flag"),
       std::make_pair(CoveragePCTable, "-fsanitize-coverage-pc-table"),
       std::make_pair(CoverageNoPrune, "-fsanitize-coverage-no-prune"),
       std::make_pair(CoverageStackDepth, "-fsanitize-coverage-stack-depth"),
       std::make_pair(CoverageTraceLoads, "-fsanitize-coverage-trace-loads"),
-      std::make_pair(CoverageTraceStores, "-fsanitize-coverage-trace-stores")};
+      std::make_pair(CoverageTraceStores, "-fsanitize-coverage-trace-stores"),
+      std::make_pair(CoverageControlFlow, "-fsanitize-coverage-control-flow")};
   for (auto F : CoverageFlags) {
     if (CoverageFeatures & F.first)
       CmdArgs.push_back(F.second);
   }
   addSpecialCaseListOpt(
       Args, CmdArgs, "-fsanitize-coverage-allowlist=", CoverageAllowlistFiles);
   addSpecialCaseListOpt(Args, CmdArgs, "-fsanitize-coverage-ignorelist=",
                         CoverageIgnorelistFiles);
int F = llvm::StringSwitch<int>(Value)
                 .Case("trace-pc-guard", CoverageTracePCGuard)
                 .Case("no-prune", CoverageNoPrune)
                 .Case("inline-8bit-counters", CoverageInline8bitCounters)
                 .Case("inline-bool-flag", CoverageInlineBoolFlag)
                 .Case("pc-table", CoveragePCTable)
                 .Case("stack-depth", CoverageStackDepth)
                 .Case("trace-loads", CoverageTraceLoads)
                 .Case("trace-stores", CoverageTraceStores)
+                .Case("control-flow", CoverageControlFlow)
                 .Default(0);
     if (F == 0 && DiagnoseErrors)
       D.Diag(clang::diag::err_drv_unsupported_option_argument)
           << A->getOption().getName() << Value;
     Features |= F;
   }
   return Features;
 }

llvm/include/llvm/Transforms/Instrumentation.h

struct SanitizerCoverageOptions {
   bool TracePCGuard = false;
   bool Inline8bitCounters = false;
   bool InlineBoolFlag = false;
   bool PCTable = false;
   bool NoPrune = false;
   bool StackDepth = false;
   bool TraceLoads = false;
   bool TraceStores = false;
+  bool CollectControlFlow = false;
 
   SanitizerCoverageOptions() = default;
 };
 
 /// Calculate what to divide by to scale counts.
 ///
 /// Given the maximum count, calculate a divisor that will scale all the
 /// weights to strictly less than std::numeric_limits<uint32_t>::max().

llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

 const char SanCovModuleCtorBoolFlagName[] = "sancov.module_ctor_bool_flag";
 static const uint64_t SanCtorAndDtorPriority = 2;
 
 const char SanCovTracePCGuardName[] = "__sanitizer_cov_trace_pc_guard";
 const char SanCovTracePCGuardInitName[] = "__sanitizer_cov_trace_pc_guard_init";
 const char SanCov8bitCountersInitName[] = "__sanitizer_cov_8bit_counters_init";
 const char SanCovBoolFlagInitName[] = "__sanitizer_cov_bool_flag_init";
 const char SanCovPCsInitName[] = "__sanitizer_cov_pcs_init";
+const char SanCovCFsInitName[] = "__sanitizer_cov_cfs_init";
 
 const char SanCovGuardsSectionName[] = "sancov_guards";
 const char SanCovCountersSectionName[] = "sancov_cntrs";
 const char SanCovBoolFlagSectionName[] = "sancov_bools";
 const char SanCovPCsSectionName[] = "sancov_pcs";
+const char SanCovCFsSectionName[] = "sancov_cfs";
 
 const char SanCovLowestStackName[] = "__sancov_lowest_stack";
 
 static cl::opt<int> ClCoverageLevel(
     "sanitizer-coverage-level",
     cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
              "3: all blocks and critical edges"),
     cl::Hidden, cl::init(0));
static cl::opt<bool>
     ClPruneBlocks("sanitizer-coverage-prune-blocks",
                   cl::desc("Reduce the number of instrumented blocks"),
                   cl::Hidden, cl::init(true));
 
 static cl::opt<bool> ClStackDepth("sanitizer-coverage-stack-depth",
                                   cl::desc("max stack depth tracing"),
                                   cl::Hidden, cl::init(false));
 
+static cl::opt<bool> ClCollectCF("sanitizer-coverage-control-flow",
+                                  cl::desc("collect control flow for each function"),
+                                  cl::Hidden, cl::init(false));
+
 namespace {
 
 SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) {
   SanitizerCoverageOptions Res;
   switch (LegacyCoverageLevel) {
   case 0:
     Res.CoverageType = SanitizerCoverageOptions::SCK_None;
     break;
SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
   Options.NoPrune |= !ClPruneBlocks;
   Options.StackDepth |= ClStackDepth;
   Options.TraceLoads |= ClLoadTracing;
   Options.TraceStores |= ClStoreTracing;
   if (!Options.TracePCGuard && !Options.TracePC &&
       !Options.Inline8bitCounters && !Options.StackDepth &&
       !Options.InlineBoolFlag && !Options.TraceLoads && !Options.TraceStores)
     Options.TracePCGuard = true; // TracePCGuard is default.
+  Options.CollectControlFlow |= ClCollectCF;
   return Options;
 }
 
 using DomTreeCallback = function_ref<const DominatorTree *(Function &F)>;
 using PostDomTreeCallback =
     function_ref<const PostDominatorTree *(Function &F)>;
 
 class ModuleSanitizerCoverage {
 public:
   ModuleSanitizerCoverage(
       const SanitizerCoverageOptions &Options = SanitizerCoverageOptions(),
       const SpecialCaseList *Allowlist = nullptr,
       const SpecialCaseList *Blocklist = nullptr)
       : Options(OverrideFromCL(Options)), Allowlist(Allowlist),
         Blocklist(Blocklist) {}
   bool instrumentModule(Module &M, DomTreeCallback DTCallback,
                         PostDomTreeCallback PDTCallback);
 
 private:
+  void createFunctionControlFlow(Function &F);
   void instrumentFunction(Function &F, DomTreeCallback DTCallback,
                           PostDomTreeCallback PDTCallback);
   void InjectCoverageForIndirectCalls(Function &F,
                                       ArrayRef<Instruction *> IndirCalls);
   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
   void InjectTraceForDiv(Function &F,
                          ArrayRef<BinaryOperator *> DivTraceTargets);
   void InjectTraceForGep(Function &F,
private:
   Triple TargetTriple;
   LLVMContext *C;
   const DataLayout *DL;
 
   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
   GlobalVariable *Function8bitCounterArray;  // for inline-8bit-counters.
   GlobalVariable *FunctionBoolArray;         // for inline-bool-flag.
   GlobalVariable *FunctionPCsArray;  // for pc-table.
+  GlobalVariable *FunctionCFsArray;  // for control flow table
   SmallVector<GlobalValue *, 20> GlobalsToAppendToUsed;
   SmallVector<GlobalValue *, 20> GlobalsToAppendToCompilerUsed;
 
   SanitizerCoverageOptions Options;
 
   const SpecialCaseList *Allowlist;
   const SpecialCaseList *Blocklist;
 };
bool ModuleSanitizerCoverage::instrumentModule(
   DL = &M.getDataLayout();
   CurModule = &M;
   CurModuleUniqueId = getUniqueModuleId(CurModule);
   TargetTriple = Triple(M.getTargetTriple());
   FunctionGuardArray = nullptr;
   Function8bitCounterArray = nullptr;
   FunctionBoolArray = nullptr;
   FunctionPCsArray = nullptr;
+  FunctionCFsArray = nullptr;
   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
   IntptrPtrTy = PointerType::getUnqual(IntptrTy);
   Type *VoidTy = Type::getVoidTy(*C);
   IRBuilder<> IRB(*C);
   Int128PtrTy = PointerType::getUnqual(IRB.getInt128Ty());
   Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
   Int16PtrTy = PointerType::getUnqual(IRB.getInt16Ty());
   Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
bool ModuleSanitizerCoverage::instrumentModule(
   }
   if (Ctor && Options.PCTable) {
     auto SecStartEnd = CreateSecStartEnd(M, SanCovPCsSectionName, IntptrTy);
     FunctionCallee InitFunction = declareSanitizerInitFunction(
         M, SanCovPCsInitName, {IntptrPtrTy, IntptrPtrTy});
     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
     IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});
   }
+
+  if (Ctor && Options.CollectControlFlow) {
+    auto SecStartEnd = CreateSecStartEnd(M, SanCovCFsSectionName, IntptrPtrTy);
+    FunctionCallee InitFunction = declareSanitizerInitFunction(
+        M, SanCovCFsInitName, {IntptrPtrTy, IntptrPtrTy});
+    IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
+    IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});    
+  }
+
   appendToUsed(M, GlobalsToAppendToUsed);
   appendToCompilerUsed(M, GlobalsToAppendToCompilerUsed);
   return true;
 }
 
 // True if block has successors and it dominates all of them.
 static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) {
   if (succ_empty(BB))
for (auto &Inst : BB) {
           Stores.push_back(SI);
       if (Options.StackDepth)
         if (isa<InvokeInst>(Inst) ||
             (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst)))
           IsLeafFunc = false;
     }
   }
 
+  if (Options.CollectControlFlow)
+    createFunctionControlFlow(F);
+
   InjectCoverage(F, BlocksToInstrument, IsLeafFunc);
   InjectCoverageForIndirectCalls(F, IndirCalls);
   InjectTraceForCmp(F, CmpTraceTargets);
   InjectTraceForSwitch(F, SwitchTraceTargets);
   InjectTraceForDiv(F, DivTraceTargets);
   InjectTraceForGep(F, GepTraceTargets);
   InjectTraceForLoadsAndStores(F, Loads, Stores);
 }

 }
 
 std::string
 ModuleSanitizerCoverage::getSectionEnd(const std::string &Section) const {
   if (TargetTriple.isOSBinFormatMachO())
     return "\1section$end$__DATA$__" + Section;
   return "__stop___" + Section;
 }
+
+void ModuleSanitizerCoverage::createFunctionControlFlow(Function &F) {
+  SmallVector<Constant *, 32> CFs;
+  IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
+
+  for (auto &BB: F) {
+    // blockaddress can not be used on function's entry block.
+    if (&BB == &F.getEntryBlock())
+      CFs.push_back((Constant *)IRB.CreatePointerCast(&F, IntptrPtrTy));
+    else
+      CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(&BB), IntptrPtrTy));
+
+    for (auto SuccBB : successors(&BB)) {
+      assert(SuccBB != &F.getEntryBlock());
+      CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(SuccBB), IntptrPtrTy));
+    }
+
+    CFs.push_back((Constant *)Constant::getNullValue(IntptrPtrTy));
+    
+    for (auto &Inst: BB) {
+      if (CallBase *CB = dyn_cast<CallBase>(&Inst)) {
+        if (CB->isIndirectCall()) {
+          // TODO(navidem): handle indirect calls, for now mark its existence.
+          CFs.push_back((Constant *)IRB.CreateIntToPtr(ConstantInt::get(IntptrTy, -1), IntptrPtrTy));
+        }
+        else {
+          auto CalledF = CB->getCalledFunction();
+          if (CalledF && !CalledF->isIntrinsic())
+            CFs.push_back((Constant *)IRB.CreatePointerCast(CalledF, IntptrPtrTy));
+        }
+      }
+    }
+
+    CFs.push_back((Constant *)Constant::getNullValue(IntptrPtrTy));
+  }
+
+  FunctionCFsArray = CreateFunctionLocalArrayInSection(CFs.size(), F, IntptrPtrTy, SanCovCFsSectionName);
+  FunctionCFsArray->setInitializer(ConstantArray::get(ArrayType::get(IntptrPtrTy, CFs.size()), CFs));
+  FunctionCFsArray->setConstant(true);
+}

llvm/test/Instrumentation/SanitizerCoverage/control-flow.ll

+; Test -sanitizer-coverage-control-flow.
+; RUN: opt < %s -passes='module(sancov-module)' -sanitizer-coverage-level=3 -sanitizer-coverage-control-flow -S | FileCheck %s
+
+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"
+target triple = "x86_64-unknown-linux-gnu"
+define void @foo(ptr %a) sanitize_address {
+entry:
+  %tobool = icmp eq i32* %a, null
+  br i1 %tobool, label %if.end, label %if.then
+
+  if.then:                                          ; preds = %entry
+  store i32 0, i32* %a, align 4
+  call void @foo(i32* %a)
+  br label %if.end
+
+  if.end:                                           ; preds = %entry, %if.then
+  ret void
+}
+
+; CHECK: private constant [17 x ptr] [{{.*}}@foo{{.*}}blockaddress{{.*}}blockaddress{{.*}}blockaddress{{.*}}blockaddress{{.*}}blockaddress{{.*}}blockaddress{{.*}}blockaddress{{.*}}@foo{{.*}}null{{.*}}null], section "__sancov_cfs", comdat($foo), align 8
+; CHECK:      @__start___sancov_cfs = extern_weak hidden global
+; CHECK-NEXT: @__stop___sancov_cfs = extern_weak hidden global