Reapply: [MC/DC][Coverage] Loosen the limit of NumConds from 6 (#82448)

By storing possible test vectors instead of combinations of conditions,
the restriction is dramatically relaxed.

This introduces two options to `cc1`:

* `-fmcdc-max-conditions=32767`
* `-fmcdc-max-test-vectors=2147483646`

This change makes coverage mapping, profraw, and profdata incompatible
with Clang-18.

- Bitmap semantics changed. It is incompatible with previous format.
- `BitmapIdx` in `Decision` points to the end of the bitmap.
- Bitmap is packed per function.
- `llvm-cov` can understand `profdata` generated by `llvm-profdata-18`.

RFC:
https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798

--
Change(s) since llvmorg-19-init-14288-g7ead2d8c7e91

- Update compiler-rt/test/profile/ContinuousSyncMode/image-with-mcdc.c

1 files changed, 25 insertions, 4 deletions

diff --git a/clang/docs/SourceBasedCodeCoverage.rst b/clang/docs/SourceBasedCodeCoverage.rst
index cee7062..73910e13 100644
--- a/clang/docs/SourceBasedCodeCoverage.rst
+++ b/clang/docs/SourceBasedCodeCoverage.rst
@@ -484,10 +484,31 @@ MC/DC Instrumentation
 ---------------------
 
 When instrumenting for Modified Condition/Decision Coverage (MC/DC) using the
-clang option ``-fcoverage-mcdc``, users are limited to at most **six** leaf-level
-conditions in a boolean expression.  A warning will be generated for boolean
-expressions that contain more than six, and they will not be instrumented for
-MC/DC.
+clang option ``-fcoverage-mcdc``, there are two hard limits.
+
+The maximum number of terms is limited to 32767, which is practical for
+handwritten expressions. To be more restrictive in order to enforce coding rules,
+use ``-Xclang -fmcdc-max-conditions=n``. Expressions with exceeded condition
+counts ``n`` will generate warnings and will be excluded in the MC/DC coverage.
+
+The number of test vectors (the maximum number of possible combinations of
+expressions) is limited to 2,147,483,646. In this case, approximately
+256MiB (==2GiB/8) is used to record test vectors.
+
+To reduce memory usage, users can limit the maximum number of test vectors per
+expression with ``-Xclang -fmcdc-max-test-vectors=m``.
+If the number of test vectors resulting from the analysis of an expression
+exceeds ``m``, a warning will be issued and the expression will be excluded
+from the MC/DC coverage.
+
+The number of test vectors ``m``, for ``n`` terms in an expression, can be
+``m <= 2^n`` in the theoretical worst case, but is usually much smaller.
+In simple cases, such as expressions consisting of a sequence of single
+operators, ``m == n+1``. For example, ``(a && b && c && d && e && f && g)``
+requires 8 test vectors.
+
+Expressions such as ``((a0 && b0) || (a1 && b1) || ...)`` can cause the
+number of test vectors to increase exponentially.
 
 Also, if a boolean expression is embedded in the nest of another boolean
 expression but separated by a non-logical operator, this is also not supported.