[InstrProf] Single byte counters in coverage

[gulfem]

Summary

This patch inserts 1-byte counters instead of an 8-byte counters
into llvm profiles for source-based code coverage. The origial idea
was proposed as block-cov for PGO, and this patch repurposes that
idea for coverage: https://groups.google.com/g/llvm-dev/c/r03Z6JoN7d4

The current 8-byte counters mechanism add counters to minimal regions,
and infer the counters in the remaining regions via adding or
subtracting counters. For example, it infers the counter in the if.else
region by subtracting the counters between if.entry and if.then regions
in an if statement. Whenever there is a control-flow merge, it adds
the counters from all the incoming regions. However, we are not going to be
able to infer counters by subtracting two execution counts when using
single-byte counters. Therefore, this patch conservatively inserts additional
counters for the cases where we need to add or subtract counters.

[paulkirth]

I think somewhere in this patch there should be a description of the new algorithm. I also don't see any description of the old algorithm, so maybe we should describe both of them so that it's easy to understand the differences in between the different profiling approaches. For example llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp describes the MST approach in detail. I don't think it needs to be quite that detailed, but a diagram contrasting where counters are inserted in both approaches would help explain the differences.

Can you also describe how this works w/ the SwitchStmt? It appears to me to just exit early, but the summary seems to indicate that it is part of the current patch. Is that part still WIP? I expected to see similar handling there as we see w/ IfStmt.

clang/lib/CodeGen/CodeGenPGO.cpp

245–256

clang/lib/CodeGen/CoverageMappingGen.cpp

1445

Won't ElseCount be uninitialized when S->getElse() == false? originally it was always initialized by subtractCounters.

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h

96–98

Do these changes need to be explained in the comment above?

152

nit: added whitespace

[gulfem]

Describe the high-level changes to adding and subtracting counters.

[gulfem]

@davidxl and @vsk,
This is a WIP prototype implementation, and I would love to hear your early feedback on using 1-byte counters for coverage idea if possible. I'll continue extending the prototype, but that would be great to learn if there is anything fundamentally wrong or missing.

[davidxl]

For coverage mode, why using 'incrementProfileCounter'? Should it be set to '1' instead? Also is the 'or' expression needed? The expression can be folded to either zero or 1.

[gulfem]

In D126586#3646197, @davidxl wrote:

For coverage mode, why using 'incrementProfileCounter'? Should it be set to '1' instead? Also is the 'or' expression needed? The expression can be folded to either zero or 1.

@davidxl I used incrementProfileCounter(), but it emits llvm.instrprof.cover intrinsic instead of llvm.instrprof.increment in emitCounterIncrement(). If it's confusing, I can move the boolean counter handling into another function and name it like setProfileCounter, setProfileCovered or something like that.

I have one concern that I would like to hear your recommendation: incrementProfileCounter() is embedded into Clang CodeGen for various AST nodes. So, even for implementing a simple prototype to collect some numbers will require me doing invasive changes to Clang CodeGen. These are going to be small changes to several AST nodes. I have only done it for some frequently used AST nodes, but there are many more of them. Can you think of a better way of designing that? Based on the current implementation of instrumentation, I could not find a less invasive way of implementing boolean counters. If that's the only way to go, shall we land them in stages after the reviews?

[gulfem]

• Extend the prototype by implementing the rest of the control-flow statements
• Rename the prototype to single byte counters to be consistent with the single byte coverage used in PGO

[gulfem]

Ensure the correct traversal order for loops in CodeGenPGO to fix the profile test failures (Profile/cxx-hash-v2.cpp and Profile/cxx-rangefor.cpp)

[gulfem]

Remove hyphen between "single counter" for consistency

[ayzhao]

Thanks for your work on this!

FYI, I'm getting the following crash when I try to build Chrome's base_unittests with -mllvm -enable-single-byte-coverage=true:

[195/4447] CXX obj/base/allocator/partition_allocator/allocator_core/pcscan_internal.o
FAILED: obj/base/allocator/partition_allocator/allocator_core/pcscan_internal.o
"python3" ../../build/toolchain/clang_code_coverage_wrapper.py --target-os=linux  /usr/local/google/home/ayzhao/src/llvm-project/build-debug/bin/clang++ -MMD -MF obj/base/allocator/partition_allocator/allocator_core/pcscan_internal.o.d -DUSE_UDEV -DUSE_AURA=1 -DUSE_GLIB=1 -DUSE_OZONE=1 -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D_FORTIFY_SOURCE=2 -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -D_LARGEFILE64_SOURCE -D_GNU_SOURCE -D_LIBCPP_ENABLE_ASSERTIONS=1 -D_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS -D_LIBCXXABI_DISABLE_VISIBILITY_ANNOTATIONS -DCR_LIBCXX_REVISION=84fb809dd6dae36d556dc0bb702c6cc2ce9d4b80 -DCR_SYSROOT_KEY=20230611T210420Z-2 -DNDEBUG -DNVALGRIND -DDYNAMIC_ANNOTATIONS_ENABLED=0 -DIS_PARTITION_ALLOC_IMPL -I../.. -Igen -I../../buildtools/third_party/libc++ -Wall -Werror -Wextra -Wimplicit-fallthrough -Wextra-semi -Wunreachable-code-aggressive -Wthread-safety -Wno-missing-field-initializers -Wno-unused-parameter -Wno-psabi -Wloop-analysis -Wno-unneeded-internal-declaration -Wenum-compare-conditional -Wno-ignored-pragma-optimize -Wno-deprecated-builtins -Wno-bitfield-constant-conversion -Wno-deprecated-this-capture -Wshadow -fno-delete-null-pointer-checks -fno-ident -fno-strict-aliasing --param=ssp-buffer-size=4 -fstack-protector -funwind-tables -fPIC -pthread -fcolor-diagnostics -fmerge-all-constants -fcrash-diagnostics-dir=../../tools/clang/crashreports -mllvm -instcombine-lower-dbg-declare=0 -ffp-contract=off -fcomplete-member-pointers -m64 -msse3 -Wno-builtin-macro-redefined -D__DATE__= -D__TIME__= -D__TIMESTAMP__= -ffile-compilation-dir=. -no-canonical-prefixes -ftrivial-auto-var-init=pattern -fno-omit-frame-pointer -g0 -fprofile-instr-generate -fcoverage-mapping -mllvm -enable-single-byte-coverage=true -mllvm -limited-coverage-experimental=true -fno-use-cxa-atexit -fvisibility=hidden -Wheader-hygiene -Wstring-conversion -Wtautological-overlap-compare -Wexit-time-destructors -O3 -fdata-sections -ffunction-sections -fno-unique-section-names -std=c++20 -Wno-trigraphs -gsimple-template-names -fno-exceptions -fno-rtti -nostdinc++ -isystem../../third_party/libc++/src/include -isystem../../third_party/libc++abi/src/include --sysroot=../../build/linux/debian_bullseye_amd64-sysroot -fvisibility-inlines-hidden -c ../../base/allocator/partition_allocator/starscan/pcscan_internal.cc -o obj/base/allocator/partition_allocator/allocator_core/pcscan_internal.o
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: /usr/local/google/home/ayzhao/src/llvm-project/build-debug/bin/clang++ -MMD -MF obj/base/allocator/partition_allocator/allocator_core/pcscan_internal.o.d -DUSE_UDEV -DUSE_AURA=1 -DUSE_GLIB=1 -DUSE_OZONE=1 -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D_FORTIFY_SOURCE=2 -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -D_LARGEFILE64_SOURCE -D_GNU_SOURCE -D_LIBCPP_ENABLE_ASSERTIONS=1 -D_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS -D_LIBCXXABI_DISABLE_VISIBILITY_ANNOTATIONS -DCR_LIBCXX_REVISION=84fb809dd6dae36d556dc0bb702c6cc2ce9d4b80 -DCR_SYSROOT_KEY=20230611T210420Z-2 -DNDEBUG -DNVALGRIND -DDYNAMIC_ANNOTATIONS_ENABLED=0 -DIS_PARTITION_ALLOC_IMPL -I../.. -Igen -I../../buildtools/third_party/libc++ -Wall -Werror -Wextra -Wimplicit-fallthrough -Wextra-semi -Wunreachable-code-aggressive -Wthread-safety -Wno-missing-field-initializers -Wno-unused-parameter -Wno-psabi -Wloop-analysis -Wno-unneeded-internal-declaration -Wenum-compare-conditional -Wno-ignored-pragma-optimize -Wno-deprecated-builtins -Wno-bitfield-constant-conversion -Wno-deprecated-this-capture -Wshadow -fno-delete-null-pointer-checks -fno-ident -fno-strict-aliasing --param=ssp-buffer-size=4 -fstack-protector -funwind-tables -fPIC -pthread -fcolor-diagnostics -fmerge-all-constants -fcrash-diagnostics-dir=../../tools/clang/crashreports -mllvm -instcombine-lower-dbg-declare=0 -ffp-contract=off -fcomplete-member-pointers -m64 -msse3 -Wno-builtin-macro-redefined -D__DATE__= -D__TIME__= -D__TIMESTAMP__= -ffile-compilation-dir=. -no-canonical-prefixes -ftrivial-auto-var-init=pattern -fno-omit-frame-pointer -g0 -fprofile-instr-generate -fcoverage-mapping -mllvm -enable-single-byte-coverage=true -mllvm -limited-coverage-experimental=true -fno-use-cxa-atexit -fvisibility=hidden -Wheader-hygiene -Wstring-conversion -Wtautological-overlap-compare -Wexit-time-destructors -O3 -fdata-sections -ffunction-sections -fno-unique-section-names -std=c++20 -Wno-trigraphs -gsimple-template-names -fno-exceptions -fno-rtti -nostdinc++ -isystem../../third_party/libc++/src/include -isystem../../third_party/libc++abi/src/include --sysroot=../../build/linux/debian_bullseye_amd64-sysroot -fvisibility-inlines-hidden -c ../../base/allocator/partition_allocator/starscan/pcscan_internal.cc -o obj/base/allocator/partition_allocator/allocator_core/pcscan_internal.o
1.      <eof> parser at end of file
2.      Optimizer
 #0 0x000055a9e376956d llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Support/Unix/Signals.inc:602:11
 #1 0x000055a9e3769a0b PrintStackTraceSignalHandler(void*) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Support/Unix/Signals.inc:675:1
 #2 0x000055a9e3767c86 llvm::sys::RunSignalHandlers() /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Support/Signals.cpp:104:5
 #3 0x000055a9e3768dde llvm::sys::CleanupOnSignal(unsigned long) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Support/Unix/Signals.inc:368:1
 #4 0x000055a9e36a2f04 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:0:7
 #5 0x000055a9e36a32c2 CrashRecoverySignalHandler(int) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:391:1
 #6 0x00007f2407a5a540 (/lib/x86_64-linux-gnu/libc.so.6+0x3c540)
 #7 0x000055a9e120d134 llvm::detail::PunnedPointer<llvm::ilist_node_base<true>*>::asInt() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/PointerIntPair.h:41:5
 #8 0x000055a9e120d115 llvm::detail::PunnedPointer<llvm::ilist_node_base<true>*>::operator long() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/PointerIntPair.h:45:41
 #9 0x000055a9e120e655 llvm::PointerIntPair<llvm::ilist_node_base<true>*, 1u, unsigned int, llvm::PointerLikeTypeTraits<llvm::ilist_node_base<true>*>, llvm::PointerIntPairInfo<llvm::ilist_node_base<true>*, 1u, llvm::PointerLikeTypeTraits<llvm::ilist_node_base<true>*>>>::getInt() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/PointerIntPair.h:96:57
#10 0x000055a9e120e625 llvm::ilist_node_base<true>::isSentinel() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/ilist_node_base.h:45:36
#11 0x000055a9e120e5e5 llvm::ilist_node_base<true>::isKnownSentinel() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/ilist_node_base.h:46:34
#12 0x000055a9e12c5b8c llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, true, true>::operator*() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/ilist_iterator.h:138:5
#13 0x000055a9e12c5a92 llvm::simple_ilist<llvm::Instruction>::back() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/simple_ilist.h:139:34
#14 0x000055a9e12c5a12 llvm::BasicBlock::getTerminator() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/IR/BasicBlock.h:128:39
#15 0x000055a9e12c1ef5 llvm::BasicBlock::getTerminator() /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/IR/BasicBlock.h:133:5
#16 0x000055a9e56a9e55 llvm::SparseSolver<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>, (anonymous namespace)::CVPLatticeVal, llvm::LatticeKeyInfo<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>>>::isEdgeFeasible(llvm::BasicBlock*, llvm::BasicBlock*, bool) /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/Analysis/SparsePropagation.h:374:27
#17 0x000055a9e56a96a4 llvm::SparseSolver<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>, (anonymous namespace)::CVPLatticeVal, llvm::LatticeKeyInfo<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>>>::visitPHINode(llvm::PHINode&) /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/Analysis/SparsePropagation.h:433:9
#18 0x000055a9e56a91e6 llvm::SparseSolver<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>, (anonymous namespace)::CVPLatticeVal, llvm::LatticeKeyInfo<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>>>::visitInst(llvm::Instruction&) /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/Analysis/SparsePropagation.h:455:5
#19 0x000055a9e56a59fe llvm::SparseSolver<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>, (anonymous namespace)::CVPLatticeVal, llvm::LatticeKeyInfo<llvm::PointerIntPair<llvm::Value*, 2u, (anonymous namespace)::IPOGrouping, llvm::PointerLikeTypeTraits<llvm::Value*>, llvm::PointerIntPairInfo<llvm::Value*, 2u, llvm::PointerLikeTypeTraits<llvm::Value*>>>>>::Solve() /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/Analysis/SparsePropagation.h:495:27
#20 0x000055a9e56a5367 runCVP(llvm::Module&) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp:386:8
#21 0x000055a9e56a525c llvm::CalledValuePropagationPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp:403:3
#22 0x000055a9e5474cc7 llvm::detail::PassModel<llvm::Module, llvm::CalledValuePropagationPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:89:17
#23 0x000055a9e302d9aa llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/IR/PassManager.h:521:7
#24 0x000055a9e3b0a68c (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>&, std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile>>&) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1100:5
#25 0x000055a9e3b04545 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1157:3
#26 0x000055a9e3b03a17 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1320:3
#27 0x000055a9e52f0154 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:386:7
#28 0x000055a9e79475b3 clang::ParseAST(clang::Sema&, bool, bool) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Parse/ParseAST.cpp:183:12
#29 0x000055a9e47d1e2c clang::ASTFrontendAction::ExecuteAction() /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1170:1
#30 0x000055a9e52eb256 clang::CodeGenAction::ExecuteAction() /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:1208:5
#31 0x000055a9e47d182c clang::FrontendAction::Execute() /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1062:7
#32 0x000055a9e46fbc68 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Frontend/CompilerInstance.cpp:1053:23
#33 0x000055a9e499cd47 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:272:8
#34 0x000055a9e12092d3 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /usr/local/google/home/ayzhao/src/llvm-project/clang/tools/driver/cc1_main.cpp:249:13
#35 0x000055a9e11f8f8a ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) /usr/local/google/home/ayzhao/src/llvm-project/clang/tools/driver/driver.cpp:366:5
#36 0x000055a9e11fa8fd clang_main(int, char**, llvm::ToolContext const&)::$_0::operator()(llvm::SmallVectorImpl<char const*>&) const /usr/local/google/home/ayzhao/src/llvm-project/clang/tools/driver/driver.cpp:506:7
#37 0x000055a9e11fa8cd int llvm::function_ref<int (llvm::SmallVectorImpl<char const*>&)>::callback_fn<clang_main(int, char**, llvm::ToolContext const&)::$_0>(long, llvm::SmallVectorImpl<char const*>&) /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:5
#38 0x000055a9e459a6a9 llvm::function_ref<int (llvm::SmallVectorImpl<char const*>&)>::operator()(llvm::SmallVectorImpl<char const*>&) const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:5
#39 0x000055a9e4596e08 clang::driver::CC1Command::Execute(llvm::ArrayRef<std::optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const::$_1::operator()() const /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Driver/Job.cpp:440:34
#40 0x000055a9e4596dd5 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<std::optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const::$_1>(long) /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:5
#41 0x000055a9e2468ca9 llvm::function_ref<void ()>::operator()() const /usr/local/google/home/ayzhao/src/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:5
#42 0x000055a9e36a2d1a llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) /usr/local/google/home/ayzhao/src/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:427:3
#43 0x000055a9e4596727 clang::driver::CC1Command::Execute(llvm::ArrayRef<std::optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Driver/Job.cpp:440:7
#44 0x000055a9e4530abf clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Driver/Compilation.cpp:199:15
#45 0x000055a9e4530cc7 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&, bool) const /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Driver/Compilation.cpp:253:13
#46 0x000055a9e454b9d8 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&) /usr/local/google/home/ayzhao/src/llvm-project/clang/lib/Driver/Driver.cpp:1906:7
#47 0x000055a9e11f8a48 clang_main(int, char**, llvm::ToolContext const&) /usr/local/google/home/ayzhao/src/llvm-project/clang/tools/driver/driver.cpp:542:9
#48 0x000055a9e122d74d main /usr/local/google/home/ayzhao/src/llvm-project/build-debug/tools/clang/tools/driver/clang-driver.cpp:15:3
#49 0x00007f2407a456ca __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:74:3
#50 0x00007f2407a45785 call_init ./csu/../csu/libc-start.c:128:20
#51 0x00007f2407a45785 __libc_start_main ./csu/../csu/libc-start.c:347:5
#52 0x000055a9e11f76e1 _start (/usr/local/google/home/ayzhao/src/llvm-project/build-debug/bin/clang+++0x1b156e1)
clang++: error: clang frontend command failed with exit code 139 (use -v to see invocation)
clang version 18.0.0 ([e-mail]:llvm/llvm-project.git f5980dad855c06e6110d954f8f33d0a385b77756)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/google/home/ayzhao/src/llvm-project/build-debug/bin
clang++: note: diagnostic msg:
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang++: note: diagnostic msg: ../../tools/clang/crashreports/pcscan_internal-09d280.cpp
clang++: note: diagnostic msg: ../../tools/clang/crashreports/pcscan_internal-09d280.sh
clang++: note: diagnostic msg:

********************
ninja: build stopped: subcommand failed.{F28818444}

{F28818443}

[gulfem]

Fixed the issue that causes a crash in InstCombinePHI.cpp. Phi instructions need to be inserted at the beginning of basic blocks, and profile increments need to be inserted after phis for conditional operators.

[zequanwu]

clang/lib/CodeGen/CGExprScalar.cpp

4812 ↗

(On Diff #553992)

This can be hoist outside if (llvm::EnableSingleByteCoverage)

clang/lib/CodeGen/CodeGenPGO.cpp

1047–1048

I thinkit's better to emit the profile version global variable in CoverageMappingModuleGen::emit so this check CGM.getCodeGenOpts().hasProfileClangInstr() is not necessary.

Also we should always emit the profile version global variable so that the runtime/backend knows if single byte coverage is enabled or not by looking at the version.

[ayzhao]

In D126586#4622003, @gulfem wrote:

Fixed the issue that causes a crash in InstCombinePHI.cpp. Phi instructions need to be inserted at the beginning of basic blocks, and profile increments need to be inserted after phis for conditional operators.

I can confirm that this fixes the crash reported in https://reviews.llvm.org/D126586#4615344. Thanks!

[gulfem]

1. Use || to merge counters that refer to the same regions
2. Use || to merge counters from raw profiles

[gulfem]

clang/lib/CodeGen/CodeGenPGO.cpp

1047–1048

CoverageMappingModuleGen is only invoked when -fcoverage-mapping flag is provided, and single byte counters are emitted when -fprofile-instr-generate flag is provided. We provide both flags for coverage purposes, but if we move this global to CoverageMappingModuleGen::emit, single byte counters won't work if -fcoverage-mapping is not provided. I don't know whether there will be such use cases, but for this reason it might not be a good idea to put that into CoverageMappingModuleGen.

clang/lib/CodeGen/CGStmt.cpp

 
 using namespace clang;
 using namespace CodeGen;
 
 //===----------------------------------------------------------------------===//
 //                              Statement Emission
 //===----------------------------------------------------------------------===//
 
+namespace llvm {
+extern cl::opt<bool> EnableBooleanCounters;
+}
+
 void CodeGenFunction::EmitStopPoint(const Stmt *S) {
   if (CGDebugInfo *DI = getDebugInfo()) {
     SourceLocation Loc;
     Loc = S->getBeginLoc();
     DI->EmitLocation(Builder, Loc);
 
     LastStopPoint = Loc;
   }
void CodeGenFunction::EmitIfStmt(const IfStmt &S) {
   Stmt::Likelihood LH = Stmt::LH_None;
   uint64_t Count = getProfileCount(S.getThen());
   if (!Count && CGM.getCodeGenOpts().OptimizationLevel)
     LH = Stmt::getLikelihood(S.getThen(), S.getElse());
   EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, Count, LH);
 
   // Emit the 'then' code.
   EmitBlock(ThenBlock);
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(S.getThen());
+  else
     incrementProfileCounter(&S);
   {
     RunCleanupsScope ThenScope(*this);
     EmitStmt(S.getThen());
   }
   EmitBranch(ContBlock);
 
   // Emit the 'else' code if present.
   if (const Stmt *Else = S.getElse()) {
     {
       // There is no need to emit line number for an unconditional branch.
       auto NL = ApplyDebugLocation::CreateEmpty(*this);
       EmitBlock(ElseBlock);
     }
+    // When boolean counters are enabled, add a counter to else block.
+    if (llvm::EnableBooleanCounters)
+      incrementProfileCounter(Else);
     {
       RunCleanupsScope ElseScope(*this);
       EmitStmt(Else);
     }
     {
       // There is no need to emit line number for an unconditional branch.
       auto NL = ApplyDebugLocation::CreateEmpty(*this);
       EmitBranch(ContBlock);
     }
   }
 
   // Emit the continuation block for code after the if.
   EmitBlock(ContBlock, true);
+  // When there is no else, add a counter to continuation block.
+  if (llvm::EnableBooleanCounters && !S.getElse())
+    incrementProfileCounter(&S);
 }
 
 void CodeGenFunction::EmitWhileStmt(const WhileStmt &S,
                                     ArrayRef<const Attr *> WhileAttrs) {
   // Emit the header for the loop, which will also become
   // the continue target.
   JumpDest LoopHeader = getJumpDestInCurrentScope("while.cond");
   EmitBlock(LoopHeader.getBlock());
CGM.getDiags().Report(
         << SourceRange(S.getWhileLoc(), S.getRParenLoc());
   }
 
   // Emit the loop body.  We have to emit this in a cleanup scope
   // because it might be a singleton DeclStmt.
   {
     RunCleanupsScope BodyScope(*this);
     EmitBlock(LoopBody);
+    if (llvm::EnableBooleanCounters)
+      incrementProfileCounter(S.getBody());
+    else
       incrementProfileCounter(&S);
     EmitStmt(S.getBody());
   }
 
   BreakContinueStack.pop_back();
 
   // Immediately force cleanup.
   ConditionScope.ForceCleanup();
 
   EmitStopPoint(&S);
   // Branch to the loop header again.
   EmitBranch(LoopHeader.getBlock());
 
   LoopStack.pop();
 
   // Emit the exit block.
   EmitBlock(LoopExit.getBlock(), true);
 
   // The LoopHeader typically is just a branch if we skipped emitting
   // a branch, try to erase it.
   if (!EmitBoolCondBranch)
     SimplifyForwardingBlocks(LoopHeader.getBlock());
+
+  // When boolean counters are enabled, add a counter to continuation block.
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(&S);
 }
 
 void CodeGenFunction::EmitDoStmt(const DoStmt &S,
                                  ArrayRef<const Attr *> DoAttrs) {
   JumpDest LoopExit = getJumpDestInCurrentScope("do.end");
   JumpDest LoopCond = getJumpDestInCurrentScope("do.cond");
 
   uint64_t ParentCount = getCurrentProfileCount();
if (ExitBlock != LoopExit.getBlock()) {
       EmitBranchThroughCleanup(LoopExit);
     }
 
     EmitBlock(ForBody);
   } else {
     // Treat it as a non-zero constant.  Don't even create a new block for the
     // body, just fall into it.
   }
-  incrementProfileCounter(&S);
 
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(S.getBody());
+  else
+    incrementProfileCounter(&S);
   {
     // Create a separate cleanup scope for the body, in case it is not
     // a compound statement.
     RunCleanupsScope BodyScope(*this);
     EmitStmt(S.getBody());
   }
 
   // If there is an increment, emit it next.
void CodeGenFunction::EmitForStmt(const ForStmt &S,
   EmitBranch(CondBlock);
 
   ForScope.ForceCleanup();
 
   LoopStack.pop();
 
   // Emit the fall-through block.
   EmitBlock(LoopExit.getBlock(), true);
+
+  // When boolean counters are enabled, add a counter to continuation block.
+  if (llvm::EnableBooleanCounters)
+    incrementProfileCounter(&S);
 }
 
 void
 CodeGenFunction::EmitCXXForRangeStmt(const CXXForRangeStmt &S,
                                      ArrayRef<const Attr *> ForAttrs) {
   JumpDest LoopExit = getJumpDestInCurrentScope("for.end");
 
   LexicalScope ForScope(*this, S.getSourceRange());

clang/lib/CodeGen/CodeGenModule.cpp

void CodeGenModule::Release() {
   }
   EmitCtorList(GlobalCtors, "llvm.global_ctors");
   EmitCtorList(GlobalDtors, "llvm.global_dtors");
   EmitGlobalAnnotations();
   EmitStaticExternCAliases();
   checkAliases();
   EmitDeferredUnusedCoverageMappings();
   CodeGenPGO(*this).setValueProfilingFlag(getModule());
+  CodeGenPGO(*this).setProfileVersion(getModule());
   if (CoverageMapping)
     CoverageMapping->emit();
   if (CodeGenOpts.SanitizeCfiCrossDso) {
     CodeGenFunction(*this).EmitCfiCheckFail();
     CodeGenFunction(*this).EmitCfiCheckStub();
   }
   emitAtAvailableLinkGuard();
   if (Context.getTargetInfo().getTriple().isWasm() &&

clang/lib/CodeGen/CodeGenPGO.h

void emitEmptyCounterMapping(const Decl *D, StringRef FuncName,
                                llvm::GlobalValue::LinkageTypes Linkage);
   // Insert instrumentation or attach profile metadata at value sites
   void valueProfile(CGBuilderTy &Builder, uint32_t ValueKind,
                     llvm::Instruction *ValueSite, llvm::Value *ValuePtr);
 
   // Set a module flag indicating if value profiling is enabled.
   void setValueProfilingFlag(llvm::Module &M);
 
+  void setProfileVersion(llvm::Module &M);
+
 private:
   void setFuncName(llvm::Function *Fn);
   void setFuncName(StringRef Name, llvm::GlobalValue::LinkageTypes Linkage);
   void mapRegionCounters(const Decl *D);
   void computeRegionCounts(const Decl *D);
   void applyFunctionAttributes(llvm::IndexedInstrProfReader *PGOReader,
                                llvm::Function *Fn);
   void loadRegionCounts(llvm::IndexedInstrProfReader *PGOReader,

clang/lib/CodeGen/CodeGenPGO.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenPGO.h"
 #include "CodeGenFunction.h"
 #include "CoverageMappingGen.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/StmtVisitor.h"
+#include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MD5.h"
 
+namespace llvm {
+cl::opt<bool> EnableBooleanCounters("enable-boolean-counters",
+                                    llvm::cl::ZeroOrMore,
+                                    llvm::cl::desc("Enable boolean counters"),
+                                    llvm::cl::Hidden, llvm::cl::init(false));
+} // namespace llvm
+
 static llvm::cl::opt<bool>
     EnableValueProfiling("enable-value-profiling", llvm::cl::ZeroOrMore,
                          llvm::cl::desc("Enable value profiling"),
                          llvm::cl::Hidden, llvm::cl::init(false));
 
 using namespace clang;
 using namespace CodeGen;
 
struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
   }
 
   bool TraverseIfStmt(IfStmt *If) {
     // If we used the V1 hash, use the default traversal.
     if (Hash.getHashVersion() == PGO_HASH_V1)
       return Base::TraverseIfStmt(If);
 
     // Otherwise, keep track of which branch we're in while traversing.
+    // When boolean counters are enabled and if has an else part,
+    // do not add a counter for IfStmt, but still include in the function hash.
+    if (llvm::EnableBooleanCounters && If->getElse()) {
+      auto Type = getHashType(PGO_HASH_V1, If);
+      if (Hash.getHashVersion() != PGO_HASH_V1)
+        Type = getHashType(Hash.getHashVersion(), If);
+      if (Type != PGOHash::None)
+        Hash.combine(Type);
+    } else
       VisitStmt(If);
+
     for (Stmt *CS : If->children()) {
       if (!CS)
         continue;
-      if (CS == If->getThen())
+      if (CS == If->getThen()) {
         Hash.combine(PGOHash::IfThenBranch);
-      else if (CS == If->getElse())
+        if (llvm::EnableBooleanCounters)
+          CounterMap[If->getThen()] = NextCounter++;
+      } else if (CS == If->getElse()) {
         Hash.combine(PGOHash::IfElseBranch);
+        if (llvm::EnableBooleanCounters)
+          CounterMap[If->getElse()] = NextCounter++;
+      }
+      TraverseStmt(CS);
+    }
+    Hash.combine(PGOHash::EndOfScope);
+    return true;
+  }
+
+  bool TraverseWhileStmt(WhileStmt *While) {
+    // If we used the V1 hash, use the default traversal.
+    if (Hash.getHashVersion() == PGO_HASH_V1)
+      return Base::TraverseWhileStmt(While);
+
+    VisitStmt(While);
+    for (Stmt *CS : While->children()) {
+      if (!CS)
+        continue;
+      if (llvm::EnableBooleanCounters && CS == While->getBody())
+        CounterMap[While->getBody()] = NextCounter++;
+      TraverseStmt(CS);
+    }
+
+    if (Hash.getHashVersion() != PGO_HASH_V1)
+      Hash.combine(PGOHash::EndOfScope);
+
+    return true;
+  }
+
+  bool TraverseForStmt(ForStmt *For) {
+    // If we used the V1 hash, use the default traversal.
+    if (Hash.getHashVersion() == PGO_HASH_V1)
+      return Base::TraverseForStmt(For);
+    VisitStmt(For);
+    for (Stmt *CS : For->children()) {
+      if (!CS)
+        continue;
+      if (CS == For->getBody()) {
+        if (llvm::EnableBooleanCounters)
+          CounterMap[For->getBody()] = NextCounter++;
+      }
       TraverseStmt(CS);
     }
+
+    if (Hash.getHashVersion() != PGO_HASH_V1)
       Hash.combine(PGOHash::EndOfScope);
     return true;
   }
 
 // If the statement type \p N is nestable, and its nesting impacts profile
 // stability, define a custom traversal which tracks the end of the statement
 // in the hash (provided we're not using the V1 hash).
 #define DEFINE_NESTABLE_TRAVERSAL(N)                                           \
   bool Traverse##N(N *S) {                                                     \
     Base::Traverse##N(S);                                                      \
     if (Hash.getHashVersion() != PGO_HASH_V1)                                  \
       Hash.combine(PGOHash::EndOfScope);                                       \
     return true;                                                               \
   }
 
-  DEFINE_NESTABLE_TRAVERSAL(WhileStmt)
   DEFINE_NESTABLE_TRAVERSAL(DoStmt)
-  DEFINE_NESTABLE_TRAVERSAL(ForStmt)
   DEFINE_NESTABLE_TRAVERSAL(CXXForRangeStmt)
   DEFINE_NESTABLE_TRAVERSAL(ObjCForCollectionStmt)
   DEFINE_NESTABLE_TRAVERSAL(CXXTryStmt)
   DEFINE_NESTABLE_TRAVERSAL(CXXCatchStmt)
 
   /// Get version \p HashVersion of the PGO hash for \p S.
   PGOHash::HashType getHashType(PGOHashVersion HashVersion, const Stmt *S) {
     switch (S->getStmtClass()) {
void CodeGenPGO::emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S,
 
   unsigned Counter = (*RegionCounterMap)[S];
   auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
 
   llvm::Value *Args[] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
                          Builder.getInt64(FunctionHash),
                          Builder.getInt32(NumRegionCounters),
                          Builder.getInt32(Counter), StepV};
+
+  if (llvm::EnableBooleanCounters)
+    Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::instrprof_cover),
+                       makeArrayRef(Args, 4));
+  else {
     if (!StepV)
       Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment),
                          makeArrayRef(Args, 4));
     else
       Builder.CreateCall(
           CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment_step),
           makeArrayRef(Args));
   }
+}
 
 void CodeGenPGO::setValueProfilingFlag(llvm::Module &M) {
   if (CGM.getCodeGenOpts().hasProfileClangInstr())
     M.addModuleFlag(llvm::Module::Warning, "EnableValueProfiling",
                     uint32_t(EnableValueProfiling));
 }
 
+void CodeGenPGO::setProfileVersion(llvm::Module &M) {
+  if (CGM.getCodeGenOpts().hasProfileClangInstr() &&
+      llvm::EnableBooleanCounters) {
+    const StringRef VarName(INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR));
+    llvm::Type *IntTy64 = llvm::Type::getInt64Ty(M.getContext());
+    uint64_t ProfileVersion =
+        (INSTR_PROF_RAW_VERSION | VARIANT_MASK_BYTE_COVERAGE);
+
+    auto IRLevelVersionVariable = new llvm::GlobalVariable(
+        M, IntTy64, true, llvm::GlobalValue::WeakAnyLinkage,
+        llvm::Constant::getIntegerValue(IntTy64,
+                                        llvm::APInt(64, ProfileVersion)),
+        VarName);
+
+    IRLevelVersionVariable->setVisibility(llvm::GlobalValue::DefaultVisibility);
+    llvm::Triple TT(M.getTargetTriple());
+    if (TT.supportsCOMDAT()) {
+      IRLevelVersionVariable->setLinkage(llvm::GlobalValue::ExternalLinkage);
+      IRLevelVersionVariable->setComdat(M.getOrInsertComdat(VarName));
+    }
+  }
+}
+
 // This method either inserts a call to the profile run-time during
 // instrumentation or puts profile data into metadata for PGO use.
 void CodeGenPGO::valueProfile(CGBuilderTy &Builder, uint32_t ValueKind,
     llvm::Instruction *ValueSite, llvm::Value *ValuePtr) {
 
   if (!EnableValueProfiling)
     return;
 

clang/lib/CodeGen/CoverageMappingGen.cpp

 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 
 // This selects the coverage mapping format defined when `InstrProfData.inc`
 // is textually included.
 #define COVMAP_V3
 
+namespace llvm {
+extern cl::opt<bool> EnableBooleanCounters;
+}
+
 static llvm::cl::opt<bool> EmptyLineCommentCoverage(
     "emptyline-comment-coverage",
     llvm::cl::desc("Emit emptylines and comment lines as skipped regions (only "
                    "disable it on test)"),
     llvm::cl::init(true), llvm::cl::Hidden);
 
 using namespace clang;
 using namespace CodeGen;
Counter addCounters(Counter LHS, Counter RHS, bool Simplify = true) {
     return Builder.add(LHS, RHS, Simplify);
   }
 
   Counter addCounters(Counter C1, Counter C2, Counter C3,
                       bool Simplify = true) {
     return addCounters(addCounters(C1, C2, Simplify), C3, Simplify);
   }
 
+  /// Return a counter for the result of \c LHS or \c RHS.
+  Counter orCounters(Counter LHS, Counter RHS) {
+    return Builder.orCounters(LHS, RHS);
+  }
+
+  Counter orCounters(Counter C1, Counter C2, Counter C3) {
+    return orCounters(orCounters(C1, C2), C3);
+  }
+
   /// Return the region counter for the given statement.
   ///
   /// This should only be called on statements that have a dedicated counter.
   Counter getRegionCounter(const Stmt *S) {
     return Counter::getCounter(CounterMap[S]);
   }
 
   /// Push a region onto the stack.
void VisitLabelStmt(const LabelStmt *S) {
     // We can't extendRegion here or we risk overlapping with our new region.
     handleFileExit(Start);
     pushRegion(LabelCount, Start);
     Visit(S->getSubStmt());
   }
 
   void VisitBreakStmt(const BreakStmt *S) {
     assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
+    if (llvm::EnableBooleanCounters)
+      BreakContinueStack.back().BreakCount = orCounters(
+          BreakContinueStack.back().BreakCount, getRegion().getCounter());
+    else
       BreakContinueStack.back().BreakCount = addCounters(
           BreakContinueStack.back().BreakCount, getRegion().getCounter());
     // FIXME: a break in a switch should terminate regions for all preceding
     // case statements, not just the most recent one.
     terminateRegion(S);
   }
 
   void VisitContinueStmt(const ContinueStmt *S) {
     assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
+    if (llvm::EnableBooleanCounters)
+      BreakContinueStack.back().ContinueCount = orCounters(
+          BreakContinueStack.back().ContinueCount, getRegion().getCounter());
+    else
       BreakContinueStack.back().ContinueCount = addCounters(
           BreakContinueStack.back().ContinueCount, getRegion().getCounter());
     terminateRegion(S);
   }
 
   void VisitCallExpr(const CallExpr *E) {
     VisitStmt(E);
 
     // Terminate the region when we hit a noreturn function.
     // (This is helpful dealing with switch statements.)
     QualType CalleeType = E->getCallee()->getType();
     if (getFunctionExtInfo(*CalleeType).getNoReturn())
       terminateRegion(E);
   }
 
   void VisitWhileStmt(const WhileStmt *S) {
     extendRegion(S);
 
     Counter ParentCount = getRegion().getCounter();
-    Counter BodyCount = getRegionCounter(S);
+    Counter BodyCount = llvm::EnableBooleanCounters
+                            ? getRegionCounter(S->getBody())
+                            : getRegionCounter(S);
 
     // Handle the body first so that we can get the backedge count.
     BreakContinueStack.push_back(BreakContinue());
     extendRegion(S->getBody());
     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
     BreakContinue BC = BreakContinueStack.pop_back_val();
 
     bool BodyHasTerminateStmt = HasTerminateStmt;
     HasTerminateStmt = false;
 
     // Go back to handle the condition.
     Counter CondCount =
-        addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
+        llvm::EnableBooleanCounters
+            ? orCounters(ParentCount, BackedgeCount, BC.ContinueCount)
+            : addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
+
     propagateCounts(CondCount, S->getCond());
     adjustForOutOfOrderTraversal(getEnd(S));
 
     // The body count applies to the area immediately after the increment.
     auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody()));
     if (Gap)
       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
 
     Counter OutCount =
-        addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
+        llvm::EnableBooleanCounters
+            ? getRegionCounter(S)
+            : addCounters(BC.BreakCount,
+                          subtractCounters(CondCount, BodyCount));
+
     if (OutCount != ParentCount) {
       pushRegion(OutCount);
       GapRegionCounter = OutCount;
       if (BodyHasTerminateStmt)
         HasTerminateStmt = true;
     }
 
     // Create Branch Region around condition.
+    if (!llvm::EnableBooleanCounters)
       createBranchRegion(S->getCond(), BodyCount,
                          subtractCounters(CondCount, BodyCount));
   }
 
   void VisitDoStmt(const DoStmt *S) {
     extendRegion(S);
 
     Counter ParentCount = getRegion().getCounter();
     Counter BodyCount = getRegionCounter(S);
 
struct CounterCoverageMappingBuilder
   }
 
   void VisitForStmt(const ForStmt *S) {
     extendRegion(S);
     if (S->getInit())
       Visit(S->getInit());
 
     Counter ParentCount = getRegion().getCounter();
-    Counter BodyCount = getRegionCounter(S);
+    Counter BodyCount = llvm::EnableBooleanCounters
+                            ? getRegionCounter(S->getBody())
+                            : getRegionCounter(S);
 
     // The loop increment may contain a break or continue.
     if (S->getInc())
       BreakContinueStack.emplace_back();
 
     // Handle the body first so that we can get the backedge count.
     BreakContinueStack.emplace_back();
     extendRegion(S->getBody());
     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
     BreakContinue BodyBC = BreakContinueStack.pop_back_val();
 
     bool BodyHasTerminateStmt = HasTerminateStmt;
     HasTerminateStmt = false;
 
     // The increment is essentially part of the body but it needs to include
     // the count for all the continue statements.
     BreakContinue IncrementBC;
     if (const Stmt *Inc = S->getInc()) {
+      if (llvm::EnableBooleanCounters)
+        propagateCounts(orCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
+      else
         propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
       IncrementBC = BreakContinueStack.pop_back_val();
     }
 
     // Go back to handle the condition.
-    Counter CondCount = addCounters(
+    Counter CondCount =
+        llvm::EnableBooleanCounters
+            ? orCounters(
+                  orCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
+                  IncrementBC.ContinueCount)
+            : addCounters(
                   addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
                   IncrementBC.ContinueCount);
+
     if (const Expr *Cond = S->getCond()) {
       propagateCounts(CondCount, Cond);
       adjustForOutOfOrderTraversal(getEnd(S));
     }
 
     // The body count applies to the area immediately after the increment.
     auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody()));
     if (Gap)
       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
 
-    Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
-                                   subtractCounters(CondCount, BodyCount));
+    Counter OutCount =
+        llvm::EnableBooleanCounters
+            ? getRegionCounter(S)
+            : addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
     if (OutCount != ParentCount) {
       pushRegion(OutCount);
       GapRegionCounter = OutCount;
       if (BodyHasTerminateStmt)
         HasTerminateStmt = true;
     }
 
     // Create Branch Region around condition.
+    if (!llvm::EnableBooleanCounters)
       createBranchRegion(S->getCond(), BodyCount,
                          subtractCounters(CondCount, BodyCount));
   }
 
   void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
     extendRegion(S);
     if (S->getInit())
       Visit(S->getInit());
     Visit(S->getLoopVarStmt());
     Visit(S->getRangeStmt());
void VisitSwitchStmt(const SwitchStmt *S) {
     pushRegion(ExitCount);
     GapRegionCounter = ExitCount;
 
     // Ensure that handleFileExit recognizes when the end location is located
     // in a different file.
     MostRecentLocation = getStart(S);
     handleFileExit(ExitLoc);
 
+    // Early return so do not create branch regions when boolean counters are
+    // enabled.
+    if (llvm::EnableBooleanCounters)
+      return;
+
     // Create a Branch Region around each Case. Subtract the case's
     // counter from the Parent counter to track the "False" branch count.
     Counter CaseCountSum;
     bool HasDefaultCase = false;
     const SwitchCase *Case = S->getSwitchCaseList();
     for (; Case; Case = Case->getNextSwitchCase()) {
       HasDefaultCase = HasDefaultCase || isa<DefaultStmt>(Case);
       CaseCountSum =
void VisitIfStmt(const IfStmt *S) {
     if (S->getInit())
       Visit(S->getInit());
 
     // Extend into the condition before we propagate through it below - this is
     // needed to handle macros that generate the "if" but not the condition.
     extendRegion(S->getCond());
 
     Counter ParentCount = getRegion().getCounter();
-    Counter ThenCount = getRegionCounter(S);
+    Counter ThenCount = llvm::EnableBooleanCounters
+                            ? getRegionCounter(S->getThen())
+                            : getRegionCounter(S);
 
     // Emitting a counter for the condition makes it easier to interpret the
     // counter for the body when looking at the coverage.
     propagateCounts(ParentCount, S->getCond());
 
     // The 'then' count applies to the area immediately after the condition.
     auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getThen()));
     if (Gap)
       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount);
 
     extendRegion(S->getThen());
     Counter OutCount = propagateCounts(ThenCount, S->getThen());
 
-    Counter ElseCount = subtractCounters(ParentCount, ThenCount);
+    Counter ElseCount;
+    if (llvm::EnableBooleanCounters) {
+      if (S->getElse())
+        ElseCount = getRegionCounter(S->getElse());
+    } else
+      ElseCount = subtractCounters(ParentCount, ThenCount);
+
     if (const Stmt *Else = S->getElse()) {
       bool ThenHasTerminateStmt = HasTerminateStmt;
       HasTerminateStmt = false;
 
       // The 'else' count applies to the area immediately after the 'then'.
       Gap = findGapAreaBetween(getEnd(S->getThen()), getStart(Else));
       if (Gap)
         fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount);
       extendRegion(Else);
-      OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
+      Counter ElseOutCount = propagateCounts(ElseCount, Else);
+      OutCount = llvm::EnableBooleanCounters
+                     ? orCounters(OutCount, ElseOutCount)
+                     : addCounters(OutCount, ElseOutCount);
 
       if (ThenHasTerminateStmt)
         HasTerminateStmt = true;
     } else
-      OutCount = addCounters(OutCount, ElseCount);
+      OutCount = llvm::EnableBooleanCounters ? getRegionCounter(S)
+                                             : addCounters(OutCount, ElseCount);
 
     if (OutCount != ParentCount) {
       pushRegion(OutCount);
       GapRegionCounter = OutCount;
     }
 
     // Create Branch Region around condition.
+    if (!llvm::EnableBooleanCounters)
       createBranchRegion(S->getCond(), ThenCount,
                          subtractCounters(ParentCount, ThenCount));
   }
 
   void VisitCXXTryStmt(const CXXTryStmt *S) {
     extendRegion(S);
     // Handle macros that generate the "try" but not the rest.
     extendRegion(S->getTryBlock());
 
     Counter ParentCount = getRegion().getCounter();

clang/test/CoverageMapping/boolean-counters.cpp

+// RUN: %clang_cc1 -mllvm -emptyline-comment-coverage=false -mllvm -enable-boolean-counters=true -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name return.c %s | FileCheck %s
+
+// CHECK: _Z6testIfi
+int testIf(int x) { // CHECK-NEXT: File 0, [[@LINE]]:19 -> [[@LINE+10]]:2 = #0
+                    // CHECK-NEXT: File 0, [[@LINE+5]]:7 -> [[@LINE+5]]:13 = #0
+                    // CHECK-NEXT: Gap,File 0, [[@LINE+4]]:14 -> [[@LINE+5]]:5 = #2
+                    // CHECK-NEXT: File 0, [[@LINE+4]]:5 -> [[@LINE+4]]:16 = #2
+                    // CHECK-NEXT: File 0, [[@LINE+5]]:3 -> [[@LINE+5]]:16 = #1
+  int result = 0;
+  if (x == 0)
+    result = -1;
+
+  return result;
+}
+
+// CHECK-NEXT: _Z10testIfElsei
+int testIfElse(int x) { // CHECK-NEXT: File 0, [[@LINE]]:23 -> [[@LINE+13]]:2 = #0
+                        // CHECK-NEXT: File 0, [[@LINE+7]]:7 -> [[@LINE+7]]:12 = #0
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+6]]:13 -> [[@LINE+7]]:5 = #1
+                        // CHECK-NEXT: File 0, [[@LINE+6]]:5 -> [[@LINE+6]]:15 = #1
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+5]]:16 -> [[@LINE+7]]:5 = #2
+                        // CHECK-NEXT: File 0, [[@LINE+6]]:5 -> [[@LINE+6]]:19 = #2
+                        // CHECK-NEXT: File 0, [[@LINE+6]]:3 -> [[@LINE+6]]:16 = (#1 || #2)
+  int result = 0;
+  if (x < 0)
+    result = 0;
+  else
+    result = x * x;
+  return result;
+}
+
+// CHECK-NEXT: _Z16testIfElseReturni
+int testIfElseReturn(int x) { // CHECK-NEXT: File 0, [[@LINE]]:29 -> [[@LINE+14]]:2 = #0
+                              // CHECK-NEXT: File 0, [[@LINE+8]]:7 -> [[@LINE+8]]:12 = #0
+                              // CHECK-NEXT: Gap,File 0, [[@LINE+7]]:13 -> [[@LINE+8]]:5 = #1
+                              // CHECK-NEXT: File 0, [[@LINE+7]]:5 -> [[@LINE+7]]:19 = #1
+                              // CHECK-NEXT: Gap,File 0, [[@LINE+6]]:20 -> [[@LINE+8]]:5 = #2
+                              // CHECK-NEXT: File 0, [[@LINE+7]]:5 -> [[@LINE+7]]:13 = #2
+                              // CHECK-NEXT: Gap,File 0, [[@LINE+6]]:14 -> [[@LINE+7]]:3 = #1
+                              // CHECK-NEXT: File 0, [[@LINE+6]]:3 -> [[@LINE+6]]:16 = #1
+  int result = 0;
+  if (x > 0)
+    result = x * x;
+  else
+    return 0;
+  return result;
+}
+
+// CHECK-NEXT: _Z10testSwitchi
+int testSwitch(int x) { // CHECK-NEXT: File 0, [[@LINE]]:23 -> [[@LINE+22]]:2 = #0
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+9]]:14 -> [[@LINE+17]]:15 = 0
+                        // CHECK-NEXT: File 0, [[@LINE+9]]:3 -> [[@LINE+11]]:10 = #2
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+10]]:11 -> [[@LINE+11]]:3 = 0
+                        // CHECK-NEXT: File 0, [[@LINE+10]]:3 -> [[@LINE+12]]:10 = #3
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+11]]:11 -> [[@LINE+12]]:3 = 0
+                        // CHECK-NEXT: File 0, [[@LINE+11]]:3 -> [[@LINE+12]]:15 = #4
+                        // CHECK-NEXT: Gap,File 0, [[@LINE+12]]:4 -> [[@LINE+14]]:3 = #1
+                        // CHECK-NEXT: File 0, [[@LINE+13]]:3 -> [[@LINE+13]]:16 = #1
+  int result;
+  switch (x) {
+  case 1:
+    result = 1;
+    break;
+  case 2:
+    result = 2;
+    break;
+  default:
+    result = 0;
+  }
+
+  return result;
+}
+
+// CHECK-NEXT: _Z9testWhilei
+int testWhile(int x) { // CHECK-NEXT: File 0, [[@LINE]]:22 -> [[@LINE+13]]:2 = #0
+                       // CHECK-NEXT: File 0, [[@LINE+6]]:10 -> [[@LINE+6]]:16 = #0
+                       // CHECK-NEXT: Gap,File 0, [[@LINE+5]]:17 -> [[@LINE+5]]:18 = #2
+                       // CHECK-NEXT: File 0, [[@LINE+4]]:18 -> [[@LINE+7]]:4 = #2
+                       // CHECK-NEXT: File 0, [[@LINE+8]]:3 -> [[@LINE+8]]:13 = #1
+  int i = x;
+  int sum = 0;
+  while (i < 10) {
+    sum += i;
+    i++;
+  }
+
+  return sum;
+}
+
+// CHECK-NEXT: _Z12testContinuei
+int testContinue(int x) { // CHECK-NEXT: File 0, [[@LINE]]:25 -> [[@LINE+21]]:2 = #0
+                          // CHECK-NEXT: File 0, [[@LINE+12]]:10 -> [[@LINE+12]]:16 = ((#0 || #3) || #4)
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+11]]:17 -> [[@LINE+11]]:18 = #2
+                          // CHECK-NEXT: File 0, [[@LINE+10]]:18 -> [[@LINE+15]]:4 = #2
+                          // CHECK-NEXT: File 0, [[@LINE+10]]:9 -> [[@LINE+10]]:15 = #2
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+9]]:16 -> [[@LINE+10]]:7 = #4
+                          // CHECK-NEXT: File 0, [[@LINE+9]]:7 -> [[@LINE+9]]:15 = #4
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+8]]:16 -> [[@LINE+9]]:5 = #3
+                          // CHECK-NEXT: File 0, [[@LINE+8]]:5 -> [[@LINE+10]]:4 = #3
+                          // CHECK-NEXT: Gap,File 0, [[@LINE+9]]:4 -> [[@LINE+11]]:3 = #1
+                          // CHECK-NEXT: File 0, [[@LINE+10]]:3 -> [[@LINE+10]]:13 = #1
+  int i = x;
+  int sum = 0;
+  while (i < 10) {
+    if (i == 4)
+      continue;
+    sum += i;
+    i++;
+  }
+
+  return sum;
+}

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h

 };
 
 /// A Counter is an abstract value that describes how to compute the
 /// execution count for a region of code using the collected profile count data.
 struct Counter {
   /// The CounterExpression kind (Add or Subtract) is encoded in bit 0 next to
   /// the CounterKind. This means CounterKind has to leave bit 0 free.
   enum CounterKind { Zero, CounterValueReference, Expression };
-  static const unsigned EncodingTagBits = 2;
-  static const unsigned EncodingTagMask = 0x3;
+  static const unsigned EncodingTagBits = 3;
+  static const unsigned EncodingTagMask = 0x7;
   static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
       EncodingTagBits + 1;
 
 private:
   CounterKind Kind = Zero;
   unsigned ID = 0;
 
   Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
 
public:
   static Counter getExpression(unsigned ExpressionId) {
     return Counter(Expression, ExpressionId);
   }
 };
 
 /// A Counter expression is a value that represents an arithmetic operation
 /// with two counters.
 struct CounterExpression {
-  enum ExprKind { Subtract, Add };
+  enum ExprKind { Subtract, Add, Or };
   ExprKind Kind;
   Counter LHS, RHS;
 
   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
       : Kind(Kind), LHS(LHS), RHS(RHS) {}
 };
 
 /// A Counter expression builder is used to construct the counter expressions.
 /// It avoids unnecessary duplication and simplifies algebraic expressions.
 class CounterExpressionBuilder {
public:
   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 
   /// Return a counter that represents the expression that adds LHS and RHS.
   Counter add(Counter LHS, Counter RHS, bool Simplify = true);
 
   /// Return a counter that represents the expression that subtracts RHS from
   /// LHS.
   Counter subtract(Counter LHS, Counter RHS, bool Simplify = true);
+
+  /// Return a counter that represents the expression RHS || LHS
+  Counter orCounters(Counter LHS, Counter RHS);
 };
 
 using LineColPair = std::pair<unsigned, unsigned>;
 
 /// A Counter mapping region associates a source range with a specific counter.
 struct CounterMappingRegion {
   enum RegionKind {
     /// A CodeRegion associates some code with a counter

llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

 }
 
 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS,
                                            bool Simplify) {
   auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS));
   return Simplify ? simplify(Cnt) : Cnt;
 }
 
+Counter CounterExpressionBuilder::orCounters(Counter LHS, Counter RHS) {
+  if (LHS.getKind() == Counter::Zero)
+    return Counter::getCounter(RHS.getCounterID());
+  if (RHS.getKind() == Counter::Zero)
+    return Counter::getCounter(LHS.getCounterID());
+  return get(CounterExpression(CounterExpression::Or, LHS, RHS));
+}
+
 void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {
   switch (C.getKind()) {
   case Counter::Zero:
     OS << '0';
     return;
   case Counter::CounterValueReference:
     OS << '#' << C.getCounterID();
     break;
   case Counter::Expression: {
     if (C.getExpressionID() >= Expressions.size())
       return;
     const auto &E = Expressions[C.getExpressionID()];
     OS << '(';
     dump(E.LHS, OS);
+    if (E.Kind == CounterExpression::Or)
+      OS << " || ";
+    else
       OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
     dump(E.RHS, OS);
     OS << ')';
     break;
   }
   }
   if (CounterValues.empty())
     return;
   Expected<int64_t> Value = evaluate(C);
if (C.getExpressionID() >= Expressions.size())
       return errorCodeToError(errc::argument_out_of_domain);
     const auto &E = Expressions[C.getExpressionID()];
     Expected<int64_t> LHS = evaluate(E.LHS);
     if (!LHS)
       return LHS;
     Expected<int64_t> RHS = evaluate(E.RHS);
     if (!RHS)
       return RHS;
+    if (E.Kind == CounterExpression::Or)
+      return *RHS || *LHS;
+
     return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
   }
   }
   llvm_unreachable("Unhandled CounterKind");
 }
 
 unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const {
   switch (C.getKind()) {

llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp

case Counter::CounterValueReference:
     C = Counter::getCounter(Value >> Counter::EncodingTagBits);
     return Error::success();
   default:
     break;
   }
   Tag -= Counter::Expression;
   switch (Tag) {
   case CounterExpression::Subtract:
-  case CounterExpression::Add: {
+  case CounterExpression::Add:
+  case CounterExpression::Or: {
     auto ID = Value >> Counter::EncodingTagBits;
     if (ID >= Expressions.size())
       return make_error<CoverageMapError>(coveragemap_error::malformed);
     Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
     C = Counter::getExpression(ID);
     break;
   }
   default: