MC/DC in LLVM Source-Based Code Coverage: clang

[alanphipps]

Summary

MC/DC in LLVM Source-based Code Coverage: Review 3/3

Background
I previously upstreamed work to enable Branch Coverage (https://reviews.llvm.org/D84467), which was pushed in early 2021. MC/DC (Modified Condition/Decision Coverage) is a planned enhancement to Source-based Code Coverage. Implementation was completed in May for our downstream Arm compiler, and in general use it has not yielded any issues.

Patches have been tested on windows (stage1) and linux/mac (stage1 and stage2). Fuchsia is not yet supported.

See attached file for Background, Motivation, Design, and Implementation Concepts:

mcdc-design-doc.pdf317 KBDownload

See attached PDF for Technical Talk slides from 2022 LLVM Developers' Meeting:

PhippsAlan_MCDC_LLVM_Conf_Talk_final.pdf614 KBDownload

I am also available at Discord @alanphipps

Review
This review is for the clang front-end components.

Start with the front-end changes:

• New Option and common parameters
  • CodeGenOptions.def
  • Options.td
  • Clang.cpp
• Bitmap Coverage Object Allocation:
  • CodeGenPGO.h, CodeGenPGO.cpp
• Source Region Mapping:
  • CoverageMappingGen.h, CoverageMappingGen.cpp
• Instrumentation (during IR lowering):
  • CGExprScalar.cpp
  • CGStmt.cpp
  • CodeGenFunction.h, CodeGenFunction.cpp

[alanphipps]

@peter.smith I know you may not feel comfortable reviewing everything or signing-off on the review, but for changes pertinent to clang, I think you made some substantive suggestions, so I am including you in the reviewer list. Thanks for your input.

[alanphipps]

Update diff to fix a small bug and add a test case to test intrinsic generation (based off a comment in the backend review)

[michaelplatings]

I'm no expert here but since you've been waiting a while for review I'll have a go.

Since this is so testing focused it would be great to see some unit tests in addition to the integration tests you've already added.

clang/include/clang/Basic/CodeGenOptions.def

226

Looks like there's no way to set MCDCMaxConditionCount, in which case perhaps it's best to omit the option for now.

clang/include/clang/Driver/Options.td

1310

If I saw -fmcdc in a long list of command line options I'm not sure its purpose would be clear. Perhaps -fcoverage-mcdc? You could also have it imply -fcoverage-mapping.

clang/lib/CodeGen/CodeGenPGO.cpp

164

I think it would make the code more readable to put MCDC in this variable name since it's specific to MC/DC. Ditto for MaxCond.

174

Not used?

282

Should this be static_cast?
Alternatively maybe you could just dyn_cast to Expr and use that instead of isa

1185

Does this handle multiple nots? e.g. bool B = !!SomeInt.

More comments here would be appreciated to explain the intended behaviour.

I notice stripCond() does the same thing as this code so perhaps that function should be called instead of duplicating the behaviour here.

[markww]

Took a look and added some comments. I'm new to Clang reviews, so do let me know if I'm not following official practices for this repo.

clang/lib/CodeGen/CGExprScalar.cpp

4521

The way this code is structured is making me wonder if the if was intentionally a single-statement if or if that was an accident. Suggest adding curly braces to disambiguate or just a newline to make the grouping intent clearer.

4521

It looks like, with these push_back and pop_back MCDCLogOpStack operations, that you are essentially opening and closing contexts for tracking MC/DC concerns, and that every MC/DC push should be paired with a pop directly afterwards. Could this be made a bit easier to manage and read by having the MCDCLogOpStack instead have a MCDCOpStack method, taking as its only argument a lambda containing the code that should operate within that op context, which performs the push and pop behind the scenes? That would also hide more of the implementation details of the MCDC tracking.

So this would shift the code from looking like this:

CGF.MCDCLogOpStack.push_back(E);

/* code dealing with the current operation */

CGF.MCDCLogOpStack.pop_back(E);

To something more like this:

CGF.OpenMCDCOpContext(E, []() {
  /* code dealing with the current operation */
}

with OpenMCDCOpContext just being:

template <class ContextFn>
void OpenMCDCOpContext(const BinaryOperator *E, ContextFn fn) {
  MCDCLogOpStack.push_back(E);
  fn();
  MCDCLogOpStack.pop_back(E);
  // If the top of the logical operator nest, update the MCDC bitmap.
  if (CGF.MCDCLogOpStack.empty())
    CGF.updateMCDCTestVectorBitmap(E);
}

Alternatively, you could use an RAII object in a statement block to achieve a similar effect.

clang/lib/CodeGen/CodeGenFunction.cpp

1699

The use of this ConditionalOp parameter is very subtle and non-obvious. It may warrant surfacing some explanation of its use in this top-level method comment.

clang/lib/CodeGen/CodeGenFunction.h

1550

The naming of this function and its comment make it sound like it's definitely going to create an MCDC temporary. But, in reality, it's only going to create such a temporary if isMCDCCoverageEnabled. Perhaps this should be maybeCreateMCDCCondBitmap?

1558

It looks like this method does not modify its this object; should it formalize this with a trailing const qualifier, similar to isMCDCCoverageEnabled?

1573

Here (and in a few other methods around here) you refer to the parameter as a "Statement` and name it S, but the type is Expr. Could confusion be reduced by instead describing it as an "Expression" and naming the variable E?

clang/lib/CodeGen/CodeGenPGO.cpp

282

I'd like to +1 this. This should either use Clang's cast function instead of reinterpret_cast or both the check and the cast should be rolled into a dyn_cast like so:

if (const Expr *E = dyn_cast<Expr>(S)) {

Similar for all uses of reinterpret_cast added in this file.

292–295

Does this mean that if I tried to use this coverage functionality in a repository with split-nested conditions, the coverage tool would error out from under me? That's not a great user experience for trying to make MC/DC progress on a codebase not previously using MC/DC coverage. Perhaps split conditions can just be marked as uncovered, which would force unnesting them without stopping the tool?

Alternatively, you can see split conditions as merely passing a boolean expression to another function. That's arguably outside the scope of what MC/DC attempts to govern, and so these split conditions could be ignored and exercised only within the called function.

335

It looks like you're putting this counting of conditions inside a block that checks whether the IndexedInstrProf is greater than Version7. Is that what you want, or was this an accidental nesting? Alternatively, you could imagine writing this code like this:

bool VisitBinaryOperator(BinaryOperator *S) {
  if (S->isLogicalOp()) {
    bool lhs_is_instrumented = CodeGenFunction::isInstrumentedCondition(S->getLHS());
    bool rhs_is_instrumented = CodeGenFunction::isInstrumentedCondition(S->getRHS());
    NumCond += (lhs_is_instrumented) ? 1 : 0;
    NumCond += (rhs_is_instrumented) ? 1 : 0;
    if (ProfileVersion >= llvm::IndexedInstrProf::Version7 && rhs_is_instrumented) {
      CounterMap[S->getRHS()] = NextCounter++;    }
  }
}

1143–1147

If you just assign the iterator returned by find to a local, you can prevent looking the expression up again with operator[]. Similar for other uses of find followed by operator[] throughout.

clang/lib/CodeGen/CoverageMappingGen.cpp

106–111

These fields are named after fairly general, common concepts one might think about in source code, but are used in a fashion that is specific to MC/DC coverage. Should these be grouped in a struct layer, such as MC_DC_Metrics or something, to prevent confusion and misuse of these metrics? This may also help reduce the number of easily-confusable, primitive-typed parameters this change adds to SourceMappingRegion and similar.

182–184

MC/DC's use of "condition" and "decision" is in conflict with the general usage of "condition" in programming language discussion. For instance, I usually would say in a code review "the condition of this if statement" to mean the top-level boolean expression that MC/DC would describe as a decision. It would be useful to qualify the uses of Condition and Decision in these methods with MCDC, or make them methods of the MCDC-focused struct I recommended elsewhere.

657

Throughout the code, you track an MC/DC condition ID with the unsigned type. It might be better, to prevent accidentally confusing different pieces of data, to make an MCDC_ID class or struct, even if that just ends up containing a single unsigned field.

657–659

Unless otherwise specified, a std::stack is a std::deque under the hood ( see https://en.cppreference.com/w/cpp/container/stack ). Do you need that level of flexibility, or would a std::vector with push_back and pop_back work ok and give you better cache locality?

685–687

Rather than a C-style cast, the most unsafe of casts, you probably want Clang's cast function. Similar throughout file.

706–718

I think all of these methods can, and should, have a trailing const qualifier to make them take a const this object.

712

Why does this take a Expr * instead of a const Expr * when you're not modifying the expression?

742

This cast is completely unnecessary, as BinaryOperator has Expr as its superclass. Just remove the cast entirely, here and in similar cases throughout file.

862–863

emplace_back should only be used over push_back when absolutely necessary ( see https://abseil.io/tips/112 ). Modern C++ does a good job of eliding copies of temporaries and push_back has clearer, safer semantics than emplace_back in the face of implicit conversions. Similar throughout.

[chapuni]

@alanphipps Haven't you forgot updating this?
Excuse me if you are working for other ongoing issues.

[alanphipps]

clang/include/clang/Driver/Options.td

1310

Thanks! I'm favorable toward -fcoverage-mcdc. I'm not sure I want it to imply -fcoverage-mapping because I want to reinforce that mcdc is enabled in-addition-to existing coverage, rather than instead-of, although it's debatable.

clang/lib/CodeGen/CodeGenPGO.cpp

282

Thanks -- you are both right, using dyn_cast is much better for this.

292–295

That's right -- treating it as another function would be beyond what MC/DC would track in its present function context.

I see your point, and I did previously debate the proper way to deal with the split-nest case. I opted against skipping / not covering the conditions because that information would too easily get lost in the overall coverage results; even if clang were to warn users when these cases are seen, the visualization tool has no way to express this information in the summary report in a meaningful way (though in the source view it's more clear). If we wanted to enable better support for that, it would mean marking/tracking uncovered conditions through extensions to the infrastructure, and frankly this corner case didn't seem common enough in code most pertinent to MC/DC (including embedded code coverage) to warrant that level of support, at least not yet.

I opted for the explicit error as a better user experience because to test meaningfully for MC/DC, users are going to be confronted with having to deal with these odd cases anyway -- best to make them aware of it up front.

At the end of the day, it's a corner case that (in my opinion) isn't worth adding special support for.

[alanphipps]

clang/lib/CodeGen/CGExprScalar.cpp

4521

Yes, that looks like a reasonable way to clean that up, and would certainly help this file, although it gets a bit more hairy in CodeGenFunction.cpp. I'd prefer to handle this suggestion in a subsequent patch.

clang/lib/CodeGen/CodeGenPGO.cpp

335

You're right that the instrumentation of the NextCounter for the logical operator is for >= Version7. I'll fix this to make it more clear. I did that work originally for branch coverage instrumentation, and I was thinking of MC/DC in terms of an extension to that work. But for MC/DC, this function is simply counting conditions, and so doesn't have to be guarded the same way.

clang/lib/CodeGen/CoverageMappingGen.cpp

657

A type alias may be simple enough to make the distinction.

862–863

That's a fair point.

In this case, I decided to follow the pattern for how region objects are pushed onto the RegionStack throughout the rest of the file. Without knowing why that was done (other than others just following what came before, as I did, which is probably the case), I'm reluctant to change all instances of emplace_back() to push_back() here. It might be worth a subsequent patch to clean that up.

[alanphipps]

In D138849#4424457, @chapuni wrote:

@alanphipps Haven't you forgot updating this?
Excuse me if you are working for other ongoing issues.

Hi -- no I hadn't forgotten; it was just taking me a while to work through all of the comments after I updated the other reviews. I'm still working on it and will upload a new patch shortly.

[markww]

I'm ok with to happy with your resolutions so far @alanphipps , but I do want to push back on that split decision error. I think that could greatly impact the usability of this tool for people who aren't starting from a clean slate.

clang/lib/CodeGen/CodeGenPGO.cpp

292–295

The big thing I'm worried about is the "incrementality" story of turning on this coverage tool if this case is treated as a capital E Error.

Imagine if I have a million lines of code that I've gotten into good shape in terms of statement coverage and I want to start measuring MC/DC coverage for this project. This code was not written with MC/DC coverage in mind, but maybe I have some automotive/aerospace/etc clients that are interested in using it and I want to give them an indication of how well it adheres to their testing standards. My first step is usually just to turn on the code to measure this new metric and see how it does.

At this point, I don't care how bad this metric is, I can fix that slowly over time. What I do care about is that I successfully get some numbers. If I get an error during this process, that's significant friction: I need to change the code to get what I want. If I get 100 errors, I probably just give up.

This is what I'm worried about with making the split-condition case a diagnostic error. From my perspective as a code owner, almost anything would be better, even marking the line as uncovered with no recourse other than to refactor, because that allows me to get numbers now and prioritize fixing it later.

I would also like to note that you're never going to get the whole class of boolean conditions that are kind of like split conditions correctly marked in MC/DC. If, for instance, this was a bitvector represented as a uint64_t containing multiple conditions that I "check" by transforming via arithmetic and bitwise expressions, that won't be handled. If this condition were wrapped in a function that happened to return the boolean expression, that also would not be handled. I think issuing a diagnostic here is a very special handling, and one that's inconsistent with the "threat model" (metaphorically) adhered to elsewhere in this PR for capturing untracked boolean expressions. The most consistent handling is either ignore this or mark it as uncovered.

[alanphipps]

clang/lib/CodeGen/CodeGenPGO.cpp

1185

Good catch! I modified this to ignore multiple logical-NOTs as well as parens, and I abstracted this into one function as you suggested. In fact, I'm pretty sure not handling multiple nots would've still yielded correct code, but it wouldn't have been consistent with the way conditions are handled elsewhere, and it could've been a lurking bug.

[alanphipps]

clang/lib/CodeGen/CodeGenPGO.cpp

292–295

This is what I'm worried about with making the split-condition case a diagnostic error. From my perspective as a code owner, almost anything would be better

OK, fair enough. While I'm not 100% aligned on this, I'm inclined to make the diagnostic a warning, which will mean that the expression will be excluded by MC/DC (i.e. ignored). It still concerns me that llvm-cov will not reflect this when reporting MC/DC coverage. llvm-cov doesn't know whether it should've been covered, so I'd like to address that in a subsequent patch -- that is, figure out a straightforward way to explicitly mark the expression (and/or its constituent conditions) as being uncovered by MC/DC so that llvm-cov can reflect that in the overall MC/DC metric.

I would also like to note that you're never going to get the whole class of boolean conditions that are kind of like split conditions correctly marked in MC/DC.

Yes, and wherever possible, I want to encourage folks to enhance these clang checks too in order to be more useful and meaningful for users attempting to use MC/DC.

[alanphipps]

Rebase and updated based on review comments. Thank you for all of the great suggestions!

[alanphipps]

clang/lib/CodeGen/CoverageMappingGen.cpp

106–111

What I ended up doing here was abstracting these parameters into the CounterMappingRegion class defined in CoverageMapping.h and just used that here. This reduces the coupling. The CoverageMapping updates are in the preceding review, https://reviews.llvm.org/D138847

[markww]

This looks good to me. Thank you for changing the split condition case to a warning, I think that will be quite helpful for initial runs. It also allows people who want to scrub their codebase of split conditions to upgrade it to an error, so I think that's a pretty good user experience.

[chapuni]

@alanphipps Thanks for the update.
Could you please apply https://github.com/chapuni/llvm-project/commit/c8b8e86ed5755ff471b003e483237551b49c15ba as clang-format?

I have tried this to the llvm-project tree with the modified LLVM_BUILD_INSTRUMENTED_COVERAGE and met a few issues.

• MCDCMaxConditions is too small. The largest case I saw is ShouldUpgradeX86Intrinsic() in https://github.com/llvm/llvm-project/blob/main/llvm/lib/IR/AutoUpgrade.cpp#L123 . I guess it would be more helpful if MC/DC would covers such a case.
• Clang crashes if C++ ctor has conditions. I guess other kinda function-like would have same issues.

I met also a case that clang crashes with constexpr.

constexpr bool isBigEndianHost = false;

void foo() {
  if constexpr (IsBigEndianHost) {
    for (int i = 0; i < 8; i++) {}
  }
}

See, https://github.com/llvm/llvm-project/blob/main/llvm/lib/Support/SHA1.cpp#L191 and SHA256.cpp

clang/lib/CodeGen/CodeGenFunction.cpp

1239

I am afraid this would not be called in C++ ctor, dtor, etc.

clang/lib/CodeGen/CodeGenFunction.h

1566

This crashes if maybeCreateMCDCCondBitmap() was not called.

clang/lib/CodeGen/CodeGenPGO.cpp

980

I think 6 is too small for usual cases, if it would cause errors (instead of suppressions as warnings)

[alanphipps]

In D138849#4432682, @chapuni wrote:

@alanphipps Thanks for the update.
Could you please apply https://github.com/chapuni/llvm-project/commit/c8b8e86ed5755ff471b003e483237551b49c15ba as clang-format?

I applied clang-format to each of the patches at the start, but I can apply it again after the mods.

• MCDCMaxConditions is too small. The largest case I saw is ShouldUpgradeX86Intrinsic() in https://github.com/llvm/llvm-project/blob/main/llvm/lib/IR/AutoUpgrade.cpp#L123 .

I do not agree with this. I don't think it is appropriate to track MC/DC coverage on a boolean expression with more than six conditions -- usual cases for embedded code is common 2 or 3 conditions. Eventually we could add an option to allow for more, but the function you point to has 323 conditions in one expression. On top of it being expensive to track test vectors for expressions with more conditions, it would be very difficult to generate test vectors in the first place. The intention with supporting MC/DC is not to run it on LLVM code itself, which clearly is not intended to be run on an embedded system.

• Clang crashes if C++ ctor has conditions. I guess other kinda function-like would have same issues.

I met also a case that clang crashes with constexpr.

constexpr bool isBigEndianHost = false;

void foo() {
  if constexpr (IsBigEndianHost) {
    for (int i = 0; i < 8; i++) {}
  }
}

I will see if I can reproduce this.

[alanphipps]

The intention with supporting MC/DC is not to run it on LLVM code itself, which clearly is not intended to be run on an embedded system.

Nor, I should say, was it developed with functional safety in mind, even if it can be run on an embedded system.

[Ibnmardanis24]

I do not agree with this. I don't think it is appropriate to track MC/DC coverage on a boolean expression with more than six conditions -- usual cases for embedded code is common 2 or 3 conditions. Eventually we could add an option to allow for more, but the function you point to has 323 conditions in one expression. On top of it being expensive to track test vectors for expressions with more conditions, it would be very difficult to generate test vectors in the first place. The intention with supporting MC/DC is not to run it on LLVM code itself, which clearly is not intended to be run on an embedded system.

I can back this claim, applications undergoing MC/DC analysis would never require more than this. The fact that you found an example outside this envelope, inside the compiler, says more about LLVM itself, than this analysis. It could be interesting to see clang certified against avionics standards but I just can't see why would you even try. :D

[alanphipps]

clang/lib/CodeGen/CodeGenFunction.cpp

1239

Thanks for pointing this out. I enabled this and added tests. I'll upload the diff soon.

clang/lib/CodeGen/CodeGenFunction.h

1566

Thanks I will fix this.

clang/lib/CodeGen/CodeGenPGO.cpp

980

What I could do is change this to a warning as well, and eventually we let llvm-cov know that it isn't covered.

[alanphipps]

Updated for additional review comments (C++ constructors, destructors, 'if constexpr') and reapply clang-format.

[chapuni]

I've found the case of assertion failure (in CoverageMapping.cpp:507, llvm-cov)

One of cases is gtest.cc:5524
It seems a Region would not be emitted if its condition consists of macro expansion (from other files).

The easiest reproduction is DemangleTests. I expect other LLVM unittests would unveil such failures.

clang/lib/CodeGen/CoverageMappingGen.cpp

447–450

Conditions aren't emitted sometimes due to this.

[paquette]

clang/lib/CodeGen/CoverageMappingGen.cpp

447–450

I think that's true in all coverage modes, not just this one. If we want to change that, I think we should change it in a separate patch since it will impact more than MC/DC.

666

Maybe use SmallVector? It's generally preferred over std::vector in the LLVM codebase.

https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h

[paquette]

clang/lib/CodeGen/CoverageMappingGen.cpp

447–450

@chapuni Could you check and see if this reproduces with non-MC/DC coverage and create a GitHub issue for it?

[chapuni]

Sorry for the delay. I am investigating RegionStack if PopRegions() would destroy branches.

clang/lib/CodeGen/CoverageMappingGen.cpp

447–450

@paquette Seems this is not the culprit. Sorry for noise.

[alanphipps]

clang/lib/CodeGen/CoverageMappingGen.cpp

447–450

No problem! Feel free to create an issue for it.

[paquette]

clang/lib/CodeGen/CodeGenPGO.cpp

297

Can you early-return true here? Then we can eliminate the else-after-return (https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return)

299

Somehow we should turn this into a plain if statement.

334

I think this needs clang-format.

980

So, why not have a uint max maximum here or something?

IIUC it might be expensive, but if embedded code rarely exceeds 6, then it shouldn't have a serious performance/compile-time impact, right?

Maybe it'd be good to elaborate in the comment why this is set to a small hardcoded value.

[alanphipps]

Update diff based clang-format and review comments...

clang/lib/CodeGen/CodeGenPGO.cpp

334

I don't see clang-format catching anything here, but I can remove the unnecessary braces.

[paquette]

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

4

Flag needs to be updated

[alanphipps]

Updating Diff -- fix Darwin test with updated option

[paquette]

alright this lgtm

maybe @phosek has some extra thoughts?

[alanphipps]

One thing that I haven't yet done is update clang/docs/SourceBasedCodeCoverage.rst to describe MC/DC. While I don't expect that to be difficult, if nobody objects (and unless there are additional comments), I am inclined to post a simple follow-on review for that update while I start landing the incremental functional commits here, beginning with https://reviews.llvm.org/D138846

I'm sure many of you are in the same boat with trying to manage competing project priorities, so I apologize that my updates haven't been as timely of late! But I'm very grateful for all of the assistance everyone has provided to this project.

[MaskRay]

clang/lib/CodeGen/CodeGenPGO.cpp

302

https://llvm.org/docs/CodingStandards.html#error-and-warning-messages

"start the first sentence with a lower-case letter, and finish the last sentence without a period"

312

consider std::max instead of alignTo

313

no parens here.

clang/test/CoverageMapping/mcdc-logical-stmt-ids.cpp

52

If a line mismatches, it will be difficult for a contributor that's unfamiliar with the code to fix the tests.

Consider whether some CHECKs can be changed to CHECK-NEXT: and whether some Decision,File can be changed to CHECK-LABEL:

clang/test/Profile/c-mcdc-class.cpp

7 ↗

(On Diff #546505)

2-space indentation is more common.

8 ↗

(On Diff #546505)

no spaces after ( or before )

[alanphipps]

Update diff based on more recent comments. Thanks! If there's nothing more, I will plan to land this in September.

[chapuni]

Merge conflict in Options.td (D157150, D157151, D158037). Could you follow?

[paquette]

Would it be possible to get this landed before the Phabricator shutdown?

[alanphipps]

In D138849#4646366, @paquette wrote:

Would it be possible to get this landed before the Phabricator shutdown?

Yes, absolutely -- I'd like to get everything landed this month. I plan to rebase and land D138846 within the next few days to start. Thank you for your and everyone's help with this and your patience.

[phosek]

LGTM

clang/lib/CodeGen/CodeGenPGO.cpp

1142

Nit: This name doesn't follow LLVM naming conventions.

1193

Nit: This name doesn't follow LLVM naming conventions.

clang/include/clang/Basic/CodeGenOptions.def

 /// Partition functions into N groups and select only functions in group i to be
 /// instrumented. Selected group numbers can be 0 to N-1 inclusive.
 VALUE_CODEGENOPT(ProfileTotalFunctionGroups, 32, 1)
 VALUE_CODEGENOPT(ProfileSelectedFunctionGroup, 32, 0)
 CODEGENOPT(CoverageMapping , 1, 0) ///< Generate coverage mapping regions to
                                    ///< enable code coverage analysis.
 CODEGENOPT(DumpCoverageMapping , 1, 0) ///< Dump the generated coverage mapping
                                        ///< regions.
+CODEGENOPT(MCDCCoverage , 1, 0) ///< Enable MC/DC code coverage criteria.
+CODEGENOPT(MCDCMaxConditionCount , 8, 6) ///< MC/DC Maximum Condition Count.
 
   /// If -fpcc-struct-return or -freg-struct-return is specified.
 ENUM_CODEGENOPT(StructReturnConvention, StructReturnConventionKind, 2, SRCK_Default)
 
 CODEGENOPT(RelaxAll          , 1, 0) ///< Relax all machine code instructions.
 CODEGENOPT(RelaxedAliasing   , 1, 0) ///< Set when -fno-strict-aliasing is enabled.
 CODEGENOPT(StructPathTBAA    , 1, 0) ///< Whether or not to use struct-path TBAA.
 CODEGENOPT(NewStructPathTBAA , 1, 0) ///< Whether or not to use enhanced struct-path TBAA.

clang/include/clang/Driver/Options.td

 def fprofile_remapping_file_EQ : Joined<["-"], "fprofile-remapping-file=">,
     Group<f_Group>, Flags<[CC1Option, CoreOption]>, MetaVarName<"<file>">,
     HelpText<"Use the remappings described in <file> to match the profile data against names in the program">,
     MarshallingInfoString<CodeGenOpts<"ProfileRemappingFile">>;
 defm coverage_mapping : BoolFOption<"coverage-mapping",
   CodeGenOpts<"CoverageMapping">, DefaultFalse,
   PosFlag<SetTrue, [CC1Option], "Generate coverage mapping to enable code coverage analysis">,
   NegFlag<SetFalse, [], "Disable code coverage analysis">, BothFlags<[CoreOption]>>;
+defm mcdc_coverage : BoolFOption<"mcdc",
+  CodeGenOpts<"MCDCCoverage">, DefaultFalse,
+  PosFlag<SetTrue, [CC1Option], "Enable MC/DC criteria when generating code coverage">,
+  NegFlag<SetFalse, [], "Disable MC/DC coverage criteria">, BothFlags<[CoreOption]>>;
 def fprofile_generate : Flag<["-"], "fprofile-generate">,
     Group<f_Group>, Flags<[CoreOption]>,
     HelpText<"Generate instrumented code to collect execution counts into default.profraw (overridden by LLVM_PROFILE_FILE env var)">;
 def fprofile_generate_EQ : Joined<["-"], "fprofile-generate=">,
     Group<f_Group>, Flags<[CoreOption]>, MetaVarName<"<directory>">,
     HelpText<"Generate instrumented code to collect execution counts into <directory>/default.profraw (overridden by LLVM_PROFILE_FILE env var)">;
 def fcs_profile_generate : Flag<["-"], "fcs-profile-generate">,
     Group<f_Group>, Flags<[CoreOption]>,

clang/lib/CodeGen/CGExprScalar.cpp

Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) {
 
   // If we have 0 && RHS, see if we can elide RHS, if so, just return 0.
   // If we have 1 && X, just emit X without inserting the control flow.
   bool LHSCondVal;
   if (CGF.ConstantFoldsToSimpleInteger(E->getLHS(), LHSCondVal)) {
     if (LHSCondVal) { // If we have 1 && X, just emit X.
       CGF.incrementProfileCounter(E);
 
+      // If the top of the logical operator nest, reset the MCDC temp to 0.
+      if (CGF.MCDCLogOpStack.empty())
+        CGF.resetMCDCCondBitmap(E);
+      CGF.MCDCLogOpStack.push_back(E);
+
       Value *RHSCond = CGF.EvaluateExprAsBool(E->getRHS());
 
       // If we're generating for profiling or coverage, generate a branch to a
       // block that increments the RHS counter needed to track branch condition
       // coverage. In this case, use "FBlock" as both the final "TrueBlock" and
       // "FalseBlock" after the increment is done.
       if (InstrumentRegions &&
           CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+        CGF.updateMCDCCondBitmap(E->getRHS(), RHSCond);
         llvm::BasicBlock *FBlock = CGF.createBasicBlock("land.end");
         llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("land.rhscnt");
         Builder.CreateCondBr(RHSCond, RHSBlockCnt, FBlock);
         CGF.EmitBlock(RHSBlockCnt);
         CGF.incrementProfileCounter(E->getRHS());
         CGF.EmitBranch(FBlock);
         CGF.EmitBlock(FBlock);
       }
 
+      CGF.MCDCLogOpStack.pop_back();
+      // If the top of the logical operator nest, update the MCDC bitmap.
+      if (CGF.MCDCLogOpStack.empty())
+        CGF.updateMCDCTestVectorBitmap(E);
+
       // ZExt result to int or bool.
       return Builder.CreateZExtOrBitCast(RHSCond, ResTy, "land.ext");
     }
 
     // 0 && RHS: If it is safe, just elide the RHS, and return 0/false.
     if (!CGF.ContainsLabel(E->getRHS()))
       return llvm::Constant::getNullValue(ResTy);
   }
 
+  // If the top of the logical operator nest, reset the MCDC temp to 0.
+  if (CGF.MCDCLogOpStack.empty())
+    CGF.resetMCDCCondBitmap(E);
+
+  CGF.MCDCLogOpStack.push_back(E);
+
   llvm::BasicBlock *ContBlock = CGF.createBasicBlock("land.end");
   llvm::BasicBlock *RHSBlock  = CGF.createBasicBlock("land.rhs");
 
   CodeGenFunction::ConditionalEvaluation eval(CGF);
 
   // Branch on the LHS first.  If it is false, go to the failure (cont) block.
   CGF.EmitBranchOnBoolExpr(E->getLHS(), RHSBlock, ContBlock,
                            CGF.getProfileCount(E->getRHS()));
Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) {
   // Reaquire the RHS block, as there may be subblocks inserted.
   RHSBlock = Builder.GetInsertBlock();
 
   // If we're generating for profiling or coverage, generate a branch on the
   // RHS to a block that increments the RHS true counter needed to track branch
   // condition coverage.
   if (InstrumentRegions &&
       CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+    CGF.updateMCDCCondBitmap(E->getRHS(), RHSCond);
     llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("land.rhscnt");
     Builder.CreateCondBr(RHSCond, RHSBlockCnt, ContBlock);
     CGF.EmitBlock(RHSBlockCnt);
     CGF.incrementProfileCounter(E->getRHS());
     CGF.EmitBranch(ContBlock);
     PN->addIncoming(RHSCond, RHSBlockCnt);
   }
 
   // Emit an unconditional branch from this block to ContBlock.
   {
     // There is no need to emit line number for unconditional branch.
     auto NL = ApplyDebugLocation::CreateEmpty(CGF);
     CGF.EmitBlock(ContBlock);
   }
   // Insert an entry into the phi node for the edge with the value of RHSCond.
   PN->addIncoming(RHSCond, RHSBlock);
 
+  CGF.MCDCLogOpStack.pop_back();
+  // If the top of the logical operator nest, update the MCDC bitmap.
+  if (CGF.MCDCLogOpStack.empty())
+    CGF.updateMCDCTestVectorBitmap(E);
+
   // Artificial location to preserve the scope information
   {
     auto NL = ApplyDebugLocation::CreateArtificial(CGF);
     PN->setDebugLoc(Builder.getCurrentDebugLocation());
   }
 
   // ZExt result to int.
   return Builder.CreateZExtOrBitCast(PN, ResTy, "land.ext");
Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) {
 
   // If we have 1 || RHS, see if we can elide RHS, if so, just return 1.
   // If we have 0 || X, just emit X without inserting the control flow.
   bool LHSCondVal;
   if (CGF.ConstantFoldsToSimpleInteger(E->getLHS(), LHSCondVal)) {
     if (!LHSCondVal) { // If we have 0 || X, just emit X.
       CGF.incrementProfileCounter(E);
 
+      // If the top of the logical operator nest, reset the MCDC temp to 0.
+      if (CGF.MCDCLogOpStack.empty())
+        CGF.resetMCDCCondBitmap(E);
+      CGF.MCDCLogOpStack.push_back(E);
+
       Value *RHSCond = CGF.EvaluateExprAsBool(E->getRHS());
 
       // If we're generating for profiling or coverage, generate a branch to a
       // block that increments the RHS counter need to track branch condition
       // coverage. In this case, use "FBlock" as both the final "TrueBlock" and
       // "FalseBlock" after the increment is done.
       if (InstrumentRegions &&
           CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+        CGF.updateMCDCCondBitmap(E->getRHS(), RHSCond);
         llvm::BasicBlock *FBlock = CGF.createBasicBlock("lor.end");
         llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("lor.rhscnt");
         Builder.CreateCondBr(RHSCond, FBlock, RHSBlockCnt);
         CGF.EmitBlock(RHSBlockCnt);
         CGF.incrementProfileCounter(E->getRHS());
         CGF.EmitBranch(FBlock);
         CGF.EmitBlock(FBlock);
       }
 
+      CGF.MCDCLogOpStack.pop_back();
+      // If the top of the logical operator nest, update the MCDC bitmap.
+      if (CGF.MCDCLogOpStack.empty())
+        CGF.updateMCDCTestVectorBitmap(E);
+
       // ZExt result to int or bool.
       return Builder.CreateZExtOrBitCast(RHSCond, ResTy, "lor.ext");
     }
 
     // 1 || RHS: If it is safe, just elide the RHS, and return 1/true.
     if (!CGF.ContainsLabel(E->getRHS()))
       return llvm::ConstantInt::get(ResTy, 1);
   }
 
+  // If the top of the logical operator nest, reset the MCDC temp to 0.
+  if (CGF.MCDCLogOpStack.empty())
+    CGF.resetMCDCCondBitmap(E);
+
+  CGF.MCDCLogOpStack.push_back(E);
+
   llvm::BasicBlock *ContBlock = CGF.createBasicBlock("lor.end");
   llvm::BasicBlock *RHSBlock = CGF.createBasicBlock("lor.rhs");
 
   CodeGenFunction::ConditionalEvaluation eval(CGF);
 
   // Branch on the LHS first.  If it is true, go to the success (cont) block.
   CGF.EmitBranchOnBoolExpr(E->getLHS(), ContBlock, RHSBlock,
                            CGF.getCurrentProfileCount() -
Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) {
   // Reaquire the RHS block, as there may be subblocks inserted.
   RHSBlock = Builder.GetInsertBlock();
 
   // If we're generating for profiling or coverage, generate a branch on the
   // RHS to a block that increments the RHS true counter needed to track branch
   // condition coverage.
   if (InstrumentRegions &&
       CodeGenFunction::isInstrumentedCondition(E->getRHS())) {
+    CGF.updateMCDCCondBitmap(E->getRHS(), RHSCond);
     llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("lor.rhscnt");
     Builder.CreateCondBr(RHSCond, ContBlock, RHSBlockCnt);
     CGF.EmitBlock(RHSBlockCnt);
     CGF.incrementProfileCounter(E->getRHS());
     CGF.EmitBranch(ContBlock);
     PN->addIncoming(RHSCond, RHSBlockCnt);
   }
 
   // Emit an unconditional branch from this block to ContBlock.  Insert an entry
   // into the phi node for the edge with the value of RHSCond.
   CGF.EmitBlock(ContBlock);
   PN->addIncoming(RHSCond, RHSBlock);
 
+  CGF.MCDCLogOpStack.pop_back();
+  // If the top of the logical operator nest, update the MCDC bitmap.
+  if (CGF.MCDCLogOpStack.empty())
+    CGF.updateMCDCTestVectorBitmap(E);
+
   // ZExt result to int.
   return Builder.CreateZExtOrBitCast(PN, ResTy, "lor.ext");
 }
 
 Value *ScalarExprEmitter::VisitBinComma(const BinaryOperator *E) {
   CGF.EmitIgnoredExpr(E->getLHS());
   CGF.EnsureInsertPoint();
   return Visit(E->getRHS());
if (isCheapEnoughToEvaluateUnconditionally(lhsExpr, CGF) &&
     if (!LHS) {
       // If the conditional has void type, make sure we return a null Value*.
       assert(!RHS && "LHS and RHS types must match");
       return nullptr;
     }
     return Builder.CreateSelect(CondV, LHS, RHS, "cond");
   }
 
+  // If the top of the logical operator nest, reset the MCDC temp to 0.
+  if (CGF.MCDCLogOpStack.empty())
+    CGF.resetMCDCCondBitmap(condExpr);
+
   llvm::BasicBlock *LHSBlock = CGF.createBasicBlock("cond.true");
   llvm::BasicBlock *RHSBlock = CGF.createBasicBlock("cond.false");
   llvm::BasicBlock *ContBlock = CGF.createBasicBlock("cond.end");
 
   CodeGenFunction::ConditionalEvaluation eval(CGF);
   CGF.EmitBranchOnBoolExpr(condExpr, LHSBlock, RHSBlock,
                            CGF.getProfileCount(lhsExpr));
 
if (!LHS)
     return RHS;
   if (!RHS)
     return LHS;
 
   // Create a PHI node for the real part.
   llvm::PHINode *PN = Builder.CreatePHI(LHS->getType(), 2, "cond");
   PN->addIncoming(LHS, LHSBlock);
   PN->addIncoming(RHS, RHSBlock);
+
+  // If the top of the logical operator nest, update the MCDC bitmap.
+  if (CGF.MCDCLogOpStack.empty())
+    CGF.updateMCDCTestVectorBitmap(condExpr);
+
   return PN;
 }
 
 Value *ScalarExprEmitter::VisitChooseExpr(ChooseExpr *E) {
   return Visit(E->getChosenSubExpr());
 }
 
 Value *ScalarExprEmitter::VisitVAArgExpr(VAArgExpr *VE) {

clang/lib/CodeGen/CGStmt.cpp

void CodeGenFunction::EmitIfStmt(const IfStmt &S) {
   // beneficial.
   // As an approximation, preserve the attribute only if both the branch and the
   // parent context were not executed.
   Stmt::Likelihood LH = Stmt::LH_None;
   uint64_t ThenCount = getProfileCount(S.getThen());
   if (!ThenCount && !getCurrentProfileCount() &&
       CGM.getCodeGenOpts().OptimizationLevel)
     LH = Stmt::getLikelihood(S.getThen(), S.getElse());
+
+  // When measuring MC/DC, always fully evaluate the condition up front using
+  // EvaluateExprAsBool() so that the test vector bitmap can be updated prior to
+  // executing the body of the if.then or if.else. This is useful for when
+  // there is a 'return' within the body, but this is particularly beneficial
+  // when one if-stmt is nested within another if-stmt so that all of the MC/DC
+  // updates are kept linear and consistent.
+  if (!CGM.getCodeGenOpts().MCDCCoverage)
     EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, ThenCount, LH);
+  else {
+    llvm::Value *BoolCondVal = EvaluateExprAsBool(S.getCond());
+    Builder.CreateCondBr(BoolCondVal, ThenBlock, ElseBlock);
+  }
 
   // Emit the 'then' code.
   EmitBlock(ThenBlock);
   incrementProfileCounter(&S);
   {
     RunCleanupsScope ThenScope(*this);
     EmitStmt(S.getThen());
   }

clang/lib/CodeGen/CodeGenFunction.h

public:
   /// OMPEmitOMPCanonicalLoop called by it will add its CanonicalLoopInfo to
   /// this stack when done. Entering a new loop requires clearing this list; it
   /// either means we start parsing a new loop nest (in which case the previous
   /// loop nest goes out of scope) or a second loop in the same level in which
   /// case it would be ambiguous into which of the two (or more) loops the loop
   /// nest would extend.
   SmallVector<llvm::CanonicalLoopInfo *, 4> OMPLoopNestStack;
 
+  /// Stack to track the Logical Operator recursion nest for MC/DC.
+  SmallVector<const BinaryOperator *, 16> MCDCLogOpStack;
+
   /// Number of nested loop to be consumed by the last surrounding
   /// loop-associated directive.
   int ExpectedOMPLoopDepth = 0;
 
   // CodeGen lambda for loops and support for ordered clause
   typedef llvm::function_ref<void(CodeGenFunction &, const OMPLoopDirective &,
                                   JumpDest)>
       CodeGenLoopTy;
private:
   OpenMPCancelExitStack OMPCancelStack;
 
   /// Lower the Likelihood knowledge about the \p Cond via llvm.expect intrin.
   llvm::Value *emitCondLikelihoodViaExpectIntrinsic(llvm::Value *Cond,
                                                     Stmt::Likelihood LH);
 
   CodeGenPGO PGO;
 
+  /// Bitmap used by MC/DC to track condition outcomes of a boolean expression.
+  Address MCDCCondBitmapAddr = Address::invalid();
+
   /// Calculate branch weights appropriate for PGO data
   llvm::MDNode *createProfileWeights(uint64_t TrueCount,
                                      uint64_t FalseCount) const;
   llvm::MDNode *createProfileWeights(ArrayRef<uint64_t> Weights) const;
   llvm::MDNode *createProfileWeightsForLoop(const Stmt *Cond,
                                             uint64_t LoopCount) const;
 
 public:
   /// Increment the profiler's counter for the given statement by \p StepV.
   /// If \p StepV is null, the default increment is 1.
   void incrementProfileCounter(const Stmt *S, llvm::Value *StepV = nullptr) {
     if (CGM.getCodeGenOpts().hasProfileClangInstr() &&
         !CurFn->hasFnAttribute(llvm::Attribute::NoProfile) &&
         !CurFn->hasFnAttribute(llvm::Attribute::SkipProfile))
       PGO.emitCounterIncrement(Builder, S, StepV);
     PGO.setCurrentStmt(S);
   }
 
+  bool isMCDCCoverageEnabled() const {
+    return (CGM.getCodeGenOpts().hasProfileClangInstr() &&
+            CGM.getCodeGenOpts().MCDCCoverage &&
+            !CurFn->hasFnAttribute(llvm::Attribute::NoProfile));
+  }
+
+  /// Allocate a temp value on the stack that MCDC can use to track condition
+  /// results.
+  void createMCDCCondBitmap() {
+    if (isMCDCCoverageEnabled()) {
+      PGO.emitMCDCParameters(Builder);
+      MCDCCondBitmapAddr = CreateIRTemp(getContext().UnsignedIntTy,
+                                        "mcdc.addr");
+    }
+  }
+
+  bool isBinaryLogicalOp(const Expr *S) {
+    const BinaryOperator *BOp = dyn_cast<BinaryOperator>(S->IgnoreParens());
+    return (BOp && BOp->isLogicalOp());
+  }
+
+  /// Zero-init the MCDC temp value.
+  void resetMCDCCondBitmap(const Expr *S) {
+    if (isMCDCCoverageEnabled() && isBinaryLogicalOp(S)) {
+      PGO.emitMCDCCondBitmapReset(Builder, S, MCDCCondBitmapAddr);
+      PGO.setCurrentStmt(S);
+    }
+  }
+
+  /// Increment the profiler's counter for the given statement by \p StepV.
+  /// If \p StepV is null, the default increment is 1.
+  void updateMCDCTestVectorBitmap(const Expr *S) {
+    if (isMCDCCoverageEnabled() && isBinaryLogicalOp(S)) {
+      PGO.emitMCDCTestVectorBitmapUpdate(Builder, S, MCDCCondBitmapAddr);
+      PGO.setCurrentStmt(S);
+    }
+  }
+
+  /// Update the MCDC temp value with the condition's evaluated result.
+  void updateMCDCCondBitmap(const Expr *S, llvm::Value *Val) {
+    if (isMCDCCoverageEnabled()) {
+      PGO.emitMCDCCondBitmapUpdate(Builder, S, MCDCCondBitmapAddr, Val);
+      PGO.setCurrentStmt(S);
+    }
+  }
+
   /// Get the profiler's count for the given statement.
   uint64_t getProfileCount(const Stmt *S) {
     return PGO.getStmtCount(S).value_or(0);
   }
 
   /// Set the profiler's current count.
   void setCurrentProfileCount(uint64_t Count) {
     PGO.setCurrentRegionCount(Count);
public:
 
   /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an
   /// if statement) to the specified blocks.  Based on the condition, this might
   /// try to simplify the codegen of the conditional based on the branch.
   /// TrueCount should be the number of times we expect the condition to
   /// evaluate to true based on PGO data.
   void EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock,
                             llvm::BasicBlock *FalseBlock, uint64_t TrueCount,
-                            Stmt::Likelihood LH = Stmt::LH_None);
+                            Stmt::Likelihood LH = Stmt::LH_None,
+                            const Expr *ConditionalOp = nullptr);
 
   /// Given an assignment `*LHS = RHS`, emit a test that checks if \p RHS is
   /// nonnull, if \p LHS is marked _Nonnull.
   void EmitNullabilityCheck(LValue LHS, llvm::Value *RHS, SourceLocation Loc);
 
   /// An enumeration which makes it easier to specify whether or not an
   /// operation is a subtraction.
   enum { NotSubtraction = false, IsSubtraction = true };

clang/lib/CodeGen/CodeGenFunction.cpp

#undef SANITIZER
   // target-features/target-cpu?
   if (CurFuncDecl)
     if (const auto *VecWidth = CurFuncDecl->getAttr<MinVectorWidthAttr>())
       LargestVectorWidth = VecWidth->getVectorWidth();
 }
 
 void CodeGenFunction::EmitFunctionBody(const Stmt *Body) {
   incrementProfileCounter(Body);
+  createMCDCCondBitmap();
   if (const CompoundStmt *S = dyn_cast<CompoundStmt>(Body))
     EmitCompoundStmtWithoutScope(*S);
   else
     EmitStmt(Body);
 
   // This is checked after emitting the function body so we know if there
   // are any permitted infinite loops.
   if (checkIfFunctionMustProgress())

 }
 
 /// ConstantFoldsToSimpleInteger - If the specified expression does not fold
 /// to a constant, or if it does but contains a label, return false.  If it
 /// constant folds return true and set the boolean result in Result.
 bool CodeGenFunction::ConstantFoldsToSimpleInteger(const Expr *Cond,
                                                    bool &ResultBool,
                                                    bool AllowLabels) {
+  // If MC/DC is enabled, disable folding so that we can instrument all
+  // conditions to yield complete test vectors. We still keep track of
+  // folded conditions during region mapping and visualization.
+  if (CGM.getCodeGenOpts().hasProfileClangInstr() &&
+      CGM.getCodeGenOpts().MCDCCoverage)
+    return false;
+
   llvm::APSInt ResultInt;
   if (!ConstantFoldsToSimpleInteger(Cond, ResultInt, AllowLabels))
     return false;
 
   ResultBool = ResultInt.getBoolValue();
   return true;
 }
 
void CodeGenFunction::EmitBranchToCounterBlock(
   // Go to the next block.
   EmitBranch(NextBlock);
 }
 
 /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an if
 /// statement) to the specified blocks.  Based on the condition, this might try
 /// to simplify the codegen of the conditional based on the branch.
 /// \param LH The value of the likelihood attribute on the True branch.
-void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
-                                           llvm::BasicBlock *TrueBlock,
-                                           llvm::BasicBlock *FalseBlock,
-                                           uint64_t TrueCount,
-                                           Stmt::Likelihood LH) {
+void CodeGenFunction::EmitBranchOnBoolExpr(
+    const Expr *Cond, llvm::BasicBlock *TrueBlock, llvm::BasicBlock *FalseBlock,
+    uint64_t TrueCount, Stmt::Likelihood LH, const Expr *ConditionalOp) {
   Cond = Cond->IgnoreParens();
 
   if (const BinaryOperator *CondBOp = dyn_cast<BinaryOperator>(Cond)) {
-
     // Handle X && Y in a condition.
     if (CondBOp->getOpcode() == BO_LAnd) {
+      MCDCLogOpStack.push_back(CondBOp);
+
       // If we have "1 && X", simplify the code.  "0 && X" would have constant
       // folded if the case was simple enough.
       bool ConstantBool = false;
       if (ConstantFoldsToSimpleInteger(CondBOp->getLHS(), ConstantBool) &&
           ConstantBool) {
         // br(1 && X) -> br(X).
         incrementProfileCounter(CondBOp);
-        return EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock,
-                                        FalseBlock, TrueCount, LH);
+        EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock,
+        MCDCLogOpStack.pop_back();
+        return;
       }
 
       // If we have "X && 1", simplify the code to use an uncond branch.
       // "X && 0" would have been constant folded to 0.
       if (ConstantFoldsToSimpleInteger(CondBOp->getRHS(), ConstantBool) &&
           ConstantBool) {
         // br(X && 1) -> br(X).
-        return EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LAnd, TrueBlock,
-                                        FalseBlock, TrueCount, LH, CondBOp);
+        EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LAnd, TrueBlock,
+        MCDCLogOpStack.pop_back();
+        return;
       }
 
       // Emit the LHS as a conditional.  If the LHS conditional is false, we
       // want to jump to the FalseBlock.
       llvm::BasicBlock *LHSTrue = createBasicBlock("land.lhs.true");
       // The counter tells us how often we evaluate RHS, and all of TrueCount
       // can be propagated to that branch.
       uint64_t RHSCount = getProfileCount(CondBOp->getRHS());
if (CondBOp->getOpcode() == BO_LAnd) {
       incrementProfileCounter(CondBOp);
       setCurrentProfileCount(getProfileCount(CondBOp->getRHS()));
 
       // Any temporaries created here are conditional.
       eval.begin(*this);
       EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock,
                                FalseBlock, TrueCount, LH);
       eval.end(*this);
-
+      MCDCLogOpStack.pop_back();
       return;
     }
 
     if (CondBOp->getOpcode() == BO_LOr) {
+      MCDCLogOpStack.push_back(CondBOp);
+
       // If we have "0 || X", simplify the code.  "1 || X" would have constant
       // folded if the case was simple enough.
       bool ConstantBool = false;
       if (ConstantFoldsToSimpleInteger(CondBOp->getLHS(), ConstantBool) &&
           !ConstantBool) {
         // br(0 || X) -> br(X).
         incrementProfileCounter(CondBOp);
-        return EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LOr, TrueBlock,
-                                        FalseBlock, TrueCount, LH);
+        EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LOr, TrueBlock,
+        MCDCLogOpStack.pop_back();
+        return;
       }
 
       // If we have "X || 0", simplify the code to use an uncond branch.
       // "X || 1" would have been constant folded to 1.
       if (ConstantFoldsToSimpleInteger(CondBOp->getRHS(), ConstantBool) &&
           !ConstantBool) {
         // br(X || 0) -> br(X).
-        return EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LOr, TrueBlock,
-                                        FalseBlock, TrueCount, LH, CondBOp);
+        EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LOr, TrueBlock,
+        MCDCLogOpStack.pop_back();
+        return;
       }
-
       // Emit the LHS as a conditional.  If the LHS conditional is true, we
       // want to jump to the TrueBlock.
       llvm::BasicBlock *LHSFalse = createBasicBlock("lor.lhs.false");
       // We have the count for entry to the RHS and for the whole expression
       // being true, so we can divy up True count between the short circuit and
       // the RHS.
       uint64_t LHSCount =
           getCurrentProfileCount() - getProfileCount(CondBOp->getRHS());
if (CondBOp->getOpcode() == BO_LOr) {
       setCurrentProfileCount(getProfileCount(CondBOp->getRHS()));
 
       // Any temporaries created here are conditional.
       eval.begin(*this);
       EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LOr, TrueBlock, FalseBlock,
                                RHSCount, LH);
 
       eval.end(*this);
-
+      MCDCLogOpStack.pop_back();
       return;
     }
   }
 
   if (const UnaryOperator *CondUOp = dyn_cast<UnaryOperator>(Cond)) {
     // br(!x, t, f) -> br(x, f, t)
-    if (CondUOp->getOpcode() == UO_LNot) {
+    // Avoid doing this optimization when instrumenting a condition for MC/DC.
+    // LNot is taken as part of the condition for simplicity, and changing its
+    // sense negatively impacts test vector tracking.
+    bool MCDCCondition = CGM.getCodeGenOpts().hasProfileClangInstr() &&
+                         CGM.getCodeGenOpts().MCDCCoverage &&
+                         isInstrumentedCondition(Cond);
+    if (CondUOp->getOpcode() == UO_LNot && !MCDCCondition) {
       // Negate the count.
       uint64_t FalseCount = getCurrentProfileCount() - TrueCount;
       // The values of the enum are chosen to make this negation possible.
       LH = static_cast<Stmt::Likelihood>(-LH);
       // Negate the condition and swap the destination blocks.
       return EmitBranchOnBoolExpr(CondUOp->getSubExpr(), FalseBlock, TrueBlock,
                                   FalseCount, LH);
     }
if (const ConditionalOperator *CondOp = dyn_cast<ConditionalOperator>(Cond)) {
     }
 
     cond.begin(*this);
     EmitBlock(LHSBlock);
     incrementProfileCounter(CondOp);
     {
       ApplyDebugLocation DL(*this, Cond);
       EmitBranchOnBoolExpr(CondOp->getLHS(), TrueBlock, FalseBlock,
-                           LHSScaledTrueCount, LH);
+                           LHSScaledTrueCount, LH, CondOp);
     }
     cond.end(*this);
 
     cond.begin(*this);
     EmitBlock(RHSBlock);
     EmitBranchOnBoolExpr(CondOp->getRHS(), TrueBlock, FalseBlock,
-                         TrueCount - LHSScaledTrueCount, LH);
+                         TrueCount - LHSScaledTrueCount, LH, CondOp);
     cond.end(*this);
 
     return;
   }
 
   if (const CXXThrowExpr *Throw = dyn_cast<CXXThrowExpr>(Cond)) {
     // Conditional operator handling can give us a throw expression as a
     // condition for a case like:
     //   br(c ? throw x : y, t, f) -> br(c, br(throw x, t, f), br(y, t, f)
     // Fold this to:
     //   br(c, throw x, br(y, t, f))
     EmitCXXThrowExpr(Throw, /*KeepInsertionPoint*/false);
     return;
   }
 
   // Emit the code with the fully general case.
   llvm::Value *CondV;
   {
     ApplyDebugLocation DL(*this, Cond);
     CondV = EvaluateExprAsBool(Cond);
   }
 
+  // If not at the top of the logical operator nest, update MCDC temp with the
+  // boolean result of the evaluated condition.
+  if (!MCDCLogOpStack.empty()) {
+    const Expr *MCDCBaseExpr = Cond;
+    // When a nested ConditionalOperator (ternary) is encountered in a boolean
+    // expression, MC/DC tracks the result of the ternary, and this is tied to
+    // the ConditionalOperator expression and not the ternary's LHS or RHS. If
+    // this is the case, the ConditionalOperator expression is passed through
+    // the ConditionalOp parameter and then used as the MCDC base expression.
+    if (ConditionalOp)
+      MCDCBaseExpr = ConditionalOp;
+    updateMCDCCondBitmap(MCDCBaseExpr, CondV);
+  }
+
   llvm::MDNode *Weights = nullptr;
   llvm::MDNode *Unpredictable = nullptr;
 
   // If the branch has a condition wrapped by __builtin_unpredictable,
   // create metadata that specifies that the branch is unpredictable.
   // Don't bother if not optimizing because that metadata would not be used.
   auto *Call = dyn_cast<CallExpr>(Cond->IgnoreImpCasts());
   if (Call && CGM.getCodeGenOpts().OptimizationLevel != 0) {

clang/lib/CodeGen/CodeGenPGO.h

 class CodeGenPGO {
 private:
   CodeGenModule &CGM;
   std::string FuncName;
   llvm::GlobalVariable *FuncNameVar;
 
   std::array <unsigned, llvm::IPVK_Last + 1> NumValueSites;
   unsigned NumRegionCounters;
+  unsigned MCDCBitmapBytes;
   uint64_t FunctionHash;
   std::unique_ptr<llvm::DenseMap<const Stmt *, unsigned>> RegionCounterMap;
+  std::unique_ptr<llvm::DenseMap<const Stmt *, unsigned>> RegionMCDCBitmapMap;
+  std::unique_ptr<llvm::DenseMap<const Stmt *, unsigned>> RegionCondIDMap;
   std::unique_ptr<llvm::DenseMap<const Stmt *, uint64_t>> StmtCountMap;
   std::unique_ptr<llvm::InstrProfRecord> ProfRecord;
   std::vector<uint64_t> RegionCounts;
   uint64_t CurrentRegionCount;
 
 public:
   CodeGenPGO(CodeGenModule &CGModule)
       : CGM(CGModule), FuncNameVar(nullptr), NumValueSites({{0}}),
-        NumRegionCounters(0), FunctionHash(0), CurrentRegionCount(0) {}
+        NumRegionCounters(0), MCDCBitmapBytes(0), FunctionHash(0),
+        CurrentRegionCount(0) {}
 
   /// Whether or not we have PGO region data for the current function. This is
   /// false both when we have no data at all and when our data has been
   /// discarded.
   bool haveRegionCounts() const { return !RegionCounts.empty(); }
 
   /// Return the counter value of the current region.
   uint64_t getCurrentRegionCount() const { return CurrentRegionCount; }
private:
   void mapRegionCounters(const Decl *D);
   void computeRegionCounts(const Decl *D);
   void applyFunctionAttributes(llvm::IndexedInstrProfReader *PGOReader,
                                llvm::Function *Fn);
   void loadRegionCounts(llvm::IndexedInstrProfReader *PGOReader,
                         bool IsInMainFile);
   bool skipRegionMappingForDecl(const Decl *D);
   void emitCounterRegionMapping(const Decl *D);
+  bool canEmitMCDCCoverage(const CGBuilderTy &Builder);
 
 public:
   void emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S,
                             llvm::Value *StepV);
+  void emitMCDCTestVectorBitmapUpdate(CGBuilderTy &Builder, const Expr *S,
+                                      Address MCDCCondBitmapAddr);
+  void emitMCDCParameters(CGBuilderTy &Builder);
+  void emitMCDCCondBitmapReset(CGBuilderTy &Builder, const Expr *S,
+                               Address MCDCCondBitmapAddr);
+  void emitMCDCCondBitmapUpdate(CGBuilderTy &Builder, const Expr *S,
+                                Address MCDCCondBitmapAddr, llvm::Value *Val);
 
   /// Return the region count for the counter at the given index.
   uint64_t getRegionCount(const Stmt *S) {
     if (!RegionCounterMap)
       return 0;
     if (!haveRegionCounts())
       return 0;
     return RegionCounts[(*RegionCounterMap)[S]];
   }
 };
 
 }  // end namespace CodeGen
 }  // end namespace clang
 
 #endif

clang/lib/CodeGen/CodeGenPGO.cpp

struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
   using Base = RecursiveASTVisitor<MapRegionCounters>;
 
   /// The next counter value to assign.
   unsigned NextCounter;
   /// The function hash.
   PGOHash Hash;
   /// The map of statements to counters.
   llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
+  /// The next bitmap byte index to assign.
+  unsigned NextBitmapIdx;
+  /// The map of statements to MC/DC bitmap coverage objects.
+  llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap;
+  /// Maximum number of supported MC/DC conditions in a boolean expression.
+  unsigned MaxCond;
   /// The profile version.
   uint64_t ProfileVersion;
+  /// Diagnostics Engine used to report warnings.
+  DiagnosticsEngine &Diag;
+  /// Whether counters are limited only to functions.
+  bool FunctionCoverageOnly;
 
   MapRegionCounters(PGOHashVersion HashVersion, uint64_t ProfileVersion,
-                    llvm::DenseMap<const Stmt *, unsigned> &CounterMap)
+                    llvm::DenseMap<const Stmt *, unsigned> &CounterMap,
+                    llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap,
+                    unsigned MaxCond, DiagnosticsEngine &Diag)
       : NextCounter(0), Hash(HashVersion), CounterMap(CounterMap),
-        ProfileVersion(ProfileVersion) {}
+        NextBitmapIdx(0), MCDCBitmapMap(MCDCBitmapMap), MaxCond(MaxCond),
+        ProfileVersion(ProfileVersion), Diag(Diag) {}
 
   // Blocks and lambdas are handled as separate functions, so we need not
   // traverse them in the parent context.
   bool TraverseBlockExpr(BlockExpr *BE) { return true; }
   bool TraverseLambdaExpr(LambdaExpr *LE) {
     // Traverse the captures, but not the body.
     for (auto C : zip(LE->captures(), LE->capture_inits()))
       TraverseLambdaCapture(LE, &std::get<0>(C), std::get<1>(C));
struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
   /// V1 hash of \p S.
   PGOHash::HashType updateCounterMappings(Stmt *S) {
     auto Type = getHashType(PGO_HASH_V1, S);
     if (Type != PGOHash::None)
       CounterMap[S] = NextCounter++;
     return Type;
   }
 
+  /// The following stacks are used with dataTraverseStmtPre() and
+  /// dataTraverseStmtPost() to track the depth of nested logical operators in a
+  /// boolean expression in a function.  The ultimate purpose is to keep track
+  /// of the number of leaf-level conditions in the boolean expression so that a
+  /// profile bitmap can be allocated based on that number.
+  ///
+  /// The stacks are also used to find error cases and notify the user.  A
+  /// standard logical operator nest for a boolean expression could be in a form
+  /// similar to this: "x = a && b && c && (d || f)"
+  unsigned NumCond = 0;
+  bool SplitNestedLogicalOp = false;
+  SmallVector<const Stmt *, 16> NonLogOpStack;
+  SmallVector<const BinaryOperator *, 16> LogOpStack;
+
+  // Hook: dataTraverseStmtPre() is invoked prior to visiting an AST Stmt node.
+  bool dataTraverseStmtPre(Stmt *S) {
+    /// If MC/DC is not enabled, MaxCond will be set to 0. Don't do anything.
+    if (MaxCond == 0)
+      return true;
+
+    /// At the top of the logical operator nest, reset the number of conditions.
+    if (LogOpStack.empty())
+      NumCond = 0;
+
+    if (isa<Expr>(S)) {
+      const Expr *E = reinterpret_cast<Expr *>(S);
+      const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(E->IgnoreParens());
+      if (BinOp && BinOp->isLogicalOp()) {
+        /// Check for "split-nested" logical operators. This happens when a new
+        /// boolean expression logical-op nest is encountered within an existing
+        /// boolean expression, separated by a non-logical operator.  For
+        /// example, in "x = (a && b && c && foo(d && f))", the "d && f" case
+        /// starts a new boolean expression that is separated from the other
+        /// conditions by the operator foo(). Split-nested cases are not
+        /// supported by MC/DC.
+        SplitNestedLogicalOp = SplitNestedLogicalOp || !NonLogOpStack.empty();
+  
+        LogOpStack.push_back(BinOp);
+        return true;
+      }
+    }
+
+    if (!LogOpStack.empty()) {
+      /// Keep track of non-logical operators. These are OK as long as we don't
+      /// encounter a new logical operator after seeing one.
+      NonLogOpStack.push_back(S);
+    }
+
+    return true;
+  }
+
+  // Hook: dataTraverseStmtPost() is invoked by the AST visitor after visiting
+  // an AST Stmt node.  MC/DC will use it to to signal when the top of a
+  // logical operation (boolean expression) nest is encountered.
+  bool dataTraverseStmtPost(Stmt *S) {
+    /// If MC/DC is not enabled, MaxCond will be set to 0. Don't do anything.
+    if (MaxCond == 0)
+      return true;
+
+    if (isa<Expr>(S)) {
+      const Expr *E = reinterpret_cast<Expr *>(S);
+      const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(E->IgnoreParens());
+      if (BinOp && BinOp->isLogicalOp()) {
+        assert(LogOpStack.back() == BinOp);
+        LogOpStack.pop_back();
+  
+        /// At the top of logical operator nest:
+        if (LogOpStack.empty()) {
+          /// Was the "split-nested" logical operator case encountered?
+          if (SplitNestedLogicalOp) {
+            unsigned DiagID = Diag.getCustomDiagID(
+                DiagnosticsEngine::Error,
+                "MC/DC: Unsupported boolean expression; "
+                "contains an operation with a nested boolean expression.");
+            Diag.Report(S->getBeginLoc(), DiagID);
+            return false;
+  
+            /// Was the maximum number of conditions encountered?
+          } else if (NumCond > MaxCond) {
+            unsigned DiagID = Diag.getCustomDiagID(
+                DiagnosticsEngine::Error,
+                "MC/DC: Unsupported boolean expression; "
+                "number of conditions (%0) exceeds max (%1).");
+            Diag.Report(S->getBeginLoc(), DiagID) << NumCond << MaxCond;
+            return false;
+  
+            // Otherwise, allocate the number of bytes required for the bitmap
+            // based on the number of conditions. Must be at least 1-byte long.
+          } else {
+            MCDCBitmapMap[BinOp] = NextBitmapIdx;
+            unsigned SizeInBits = llvm::alignTo(1L << NumCond, CHAR_BIT);
+            NextBitmapIdx += (SizeInBits / CHAR_BIT);
+          }
+        }
+        return true;
+      }
+    }
+
+    if (!LogOpStack.empty()) {
+      NonLogOpStack.pop_back();
+    }
+
+    return true;
+  }
+
   /// The RHS of all logical operators gets a fresh counter in order to count
   /// how many times the RHS evaluates to true or false, depending on the
   /// semantics of the operator. This is only valid for ">= v7" of the profile
-  /// version so that we facilitate backward compatibility.
+  /// version so that we facilitate backward compatibility. In addition, in
+  /// order to use MC/DC, count the number of total LHS and RHS conditions.
   bool VisitBinaryOperator(BinaryOperator *S) {
-    if (ProfileVersion >= llvm::IndexedInstrProf::Version7)
-      if (S->isLogicalOp() &&
-          CodeGenFunction::isInstrumentedCondition(S->getRHS()))
+    if (ProfileVersion >= llvm::IndexedInstrProf::Version7) {
+      if (S->isLogicalOp()) {
+        if (CodeGenFunction::isInstrumentedCondition(S->getLHS())) {
+          NumCond++;
+        }
+        if (CodeGenFunction::isInstrumentedCondition(S->getRHS())) {
           CounterMap[S->getRHS()] = NextCounter++;
+          NumCond++;
+        }
+      }
+    }
     return Base::VisitBinaryOperator(S);
   }
 
   /// Include \p S in the function hash.
   bool VisitStmt(Stmt *S) {
     auto Type = updateCounterMappings(S);
     if (Hash.getHashVersion() != PGO_HASH_V1)
       Type = getHashType(Hash.getHashVersion(), S);
void CodeGenPGO::mapRegionCounters(const Decl *D) {
   // version in the indexed profile if we're reading PGO data.
   PGOHashVersion HashVersion = PGO_HASH_LATEST;
   uint64_t ProfileVersion = llvm::IndexedInstrProf::Version;
   if (auto *PGOReader = CGM.getPGOReader()) {
     HashVersion = getPGOHashVersion(PGOReader, CGM);
     ProfileVersion = PGOReader->getVersion();
   }
 
+  // If MC/DC is enabled, set the MaxConditions to the preset value. Otherwise,
+  // set it to zero.
+  unsigned MCDCMaxConditions = (CGM.getCodeGenOpts().MCDCCoverage) ?
+    CGM.getCodeGenOpts().MCDCMaxConditionCount : 0;
+
   RegionCounterMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
-  MapRegionCounters Walker(HashVersion, ProfileVersion, *RegionCounterMap);
+  RegionMCDCBitmapMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
+  MapRegionCounters Walker(HashVersion, ProfileVersion, *RegionCounterMap,
+                           *RegionMCDCBitmapMap, MCDCMaxConditions,
+                           CGM.getDiags());
   if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D))
     Walker.TraverseDecl(const_cast<FunctionDecl *>(FD));
   else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D))
     Walker.TraverseDecl(const_cast<ObjCMethodDecl *>(MD));
   else if (const BlockDecl *BD = dyn_cast_or_null<BlockDecl>(D))
     Walker.TraverseDecl(const_cast<BlockDecl *>(BD));
   else if (const CapturedDecl *CD = dyn_cast_or_null<CapturedDecl>(D))
     Walker.TraverseDecl(const_cast<CapturedDecl *>(CD));
   assert(Walker.NextCounter > 0 && "no entry counter mapped for decl");
   NumRegionCounters = Walker.NextCounter;
+  MCDCBitmapBytes = Walker.NextBitmapIdx;
   FunctionHash = Walker.Hash.finalize();
 }
 
 bool CodeGenPGO::skipRegionMappingForDecl(const Decl *D) {
   if (!D->getBody())
     return true;
 
   // Skip host-only functions in the CUDA device compilation and device-only

 }
 
 void CodeGenPGO::emitCounterRegionMapping(const Decl *D) {
   if (skipRegionMappingForDecl(D))
     return;
 
   std::string CoverageMapping;
   llvm::raw_string_ostream OS(CoverageMapping);
+  RegionCondIDMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
   CoverageMappingGen MappingGen(*CGM.getCoverageMapping(),
                                 CGM.getContext().getSourceManager(),
-                                CGM.getLangOpts(), RegionCounterMap.get());
+                                CGM.getLangOpts(), RegionCounterMap.get(),
+                                RegionMCDCBitmapMap.get(),
+                                RegionCondIDMap.get());
   MappingGen.emitCounterMapping(D, OS);
   OS.flush();
 
   if (CoverageMapping.empty())
     return;
 
   CGM.getCoverageMapping()->addFunctionMappingRecord(
       FuncNameVar, FuncName, FunctionHash, CoverageMapping);
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));
 }
 
+bool CodeGenPGO::canEmitMCDCCoverage(const CGBuilderTy &Builder) {
+  return (CGM.getCodeGenOpts().hasProfileClangInstr() &&
+          CGM.getCodeGenOpts().MCDCCoverage &&
+          Builder.GetInsertBlock());
+}
+
+void CodeGenPGO::emitMCDCParameters(CGBuilderTy &Builder) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap)
+    return;
+
+  auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
+
+  // Emit intrinsic representing MCDC bitmap parameters at function entry.
+  // This is used by the instrumentation pass, but it isn't actually lowered to
+  // anything.
+  llvm::Value *Args[3] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
+                          Builder.getInt64(FunctionHash),
+                          Builder.getInt32(MCDCBitmapBytes)};
+  Builder.CreateCall(
+      CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_parameters), Args);
+}
+
+void CodeGenPGO::emitMCDCTestVectorBitmapUpdate(CGBuilderTy &Builder,
+                                                const Expr *S,
+                                                Address MCDCCondBitmapAddr) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap)
+    return;
+
+  S = S->IgnoreParens();
+
+  if (RegionMCDCBitmapMap->find(S) == RegionMCDCBitmapMap->end())
+    return;
+
+  // Extract the ID of the global bitmap associated with this expression.
+  unsigned MCDCTestVectorBitmapID = (*RegionMCDCBitmapMap)[S];
+  auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
+
+  // Emit intrinsic responsible for updating the global bitmap corresponding to
+  // a boolean expression. The index being set is based on the value loaded
+  // from a pointer to a dedicated temporary value on the stack that is itself
+  // updated via emitMCDCCondBitmapReset() and emitMCDCCondBitmapUpdate(). The
+  // index represents an executed test vector.
+  llvm::Value *Args[5] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
+                          Builder.getInt64(FunctionHash),
+                          Builder.getInt32(MCDCBitmapBytes),
+                          Builder.getInt32(MCDCTestVectorBitmapID),
+                          MCDCCondBitmapAddr.getPointer()};
+  Builder.CreateCall(
+      CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_tvbitmap_update), Args);
+}
+
+void CodeGenPGO::emitMCDCCondBitmapReset(CGBuilderTy &Builder, const Expr *S,
+                                         Address MCDCCondBitmapAddr) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap)
+    return;
+
+  S = S->IgnoreParens();
+
+  if (RegionMCDCBitmapMap->find(S) == RegionMCDCBitmapMap->end())
+    return;
+
+  // Emit intrinsic that resets a dedicated temporary value on the stack to 0.
+  Builder.CreateStore(Builder.getInt32(0), MCDCCondBitmapAddr);
+}
+
+void CodeGenPGO::emitMCDCCondBitmapUpdate(CGBuilderTy &Builder, const Expr *S,
+                                          Address MCDCCondBitmapAddr,
+                                          llvm::Value *Val) {
+  if (!canEmitMCDCCoverage(Builder) || !RegionCondIDMap)
+    return;
+
+  if (const UnaryOperator *UnOp = dyn_cast<UnaryOperator>(S->IgnoreParens()))
+    if (UnOp->getOpcode() == UO_LNot)
+      S = UnOp->getSubExpr();
+  S = S->IgnoreParens();
+
+  if (RegionCondIDMap->find(S) == RegionCondIDMap->end())
+    return;
+
+  // Extract the ID of the condition we are setting in the bitmap.
+  unsigned CondID = (*RegionCondIDMap)[S];
+  assert(CondID > 0 && "Condition has no ID!");
+
+  auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
+
+  // Emit intrinsic that updates a dedicated temporary value on the stack after
+  // a condition is evaluated. After the set of conditions has been updated,
+  // the resulting value is used to update the boolean expression's bitmap.
+  llvm::Value *Args[5] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
+                          Builder.getInt64(FunctionHash),
+                          Builder.getInt32(CondID - 1),
+                          MCDCCondBitmapAddr.getPointer(), Val};
+  Builder.CreateCall(CGM.getIntrinsic(
+      llvm::Intrinsic::instrprof_mcdc_condbitmap_update), Args);
+}
+
 void CodeGenPGO::setValueProfilingFlag(llvm::Module &M) {
   if (CGM.getCodeGenOpts().hasProfileClangInstr())
     M.addModuleFlag(llvm::Module::Warning, "EnableValueProfiling",
                     uint32_t(EnableValueProfiling));
 }
 
 // This method either inserts a call to the profile run-time during
 // instrumentation or puts profile data into metadata for PGO use.

clang/lib/CodeGen/CoverageMappingGen.h

 
 /// Organizes the per-function state that is used while generating
 /// code coverage mapping data.
 class CoverageMappingGen {
   CoverageMappingModuleGen &CVM;
   SourceManager &SM;
   const LangOptions &LangOpts;
   llvm::DenseMap<const Stmt *, unsigned> *CounterMap;
+  llvm::DenseMap<const Stmt *, unsigned> *MCDCBitmapMap;
+  llvm::DenseMap<const Stmt *, unsigned> *CondIDMap;
 
 public:
   CoverageMappingGen(CoverageMappingModuleGen &CVM, SourceManager &SM,
                      const LangOptions &LangOpts)
-      : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(nullptr) {}
+      : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(nullptr),
+        MCDCBitmapMap(nullptr), CondIDMap(nullptr) {}
 
   CoverageMappingGen(CoverageMappingModuleGen &CVM, SourceManager &SM,
                      const LangOptions &LangOpts,
-                     llvm::DenseMap<const Stmt *, unsigned> *CounterMap)
-      : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(CounterMap) {}
+                     llvm::DenseMap<const Stmt *, unsigned> *CounterMap,
+                     llvm::DenseMap<const Stmt *, unsigned> *MCDCBitmapMap,
+                     llvm::DenseMap<const Stmt *, unsigned> *CondIDMap)
+      : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(CounterMap),
+        MCDCBitmapMap(MCDCBitmapMap), CondIDMap(CondIDMap) {}
 
   /// Emit the coverage mapping data which maps the regions of
   /// code to counters that will be used to find the execution
   /// counts for those regions.
   void emitCounterMapping(const Decl *D, llvm::raw_ostream &OS);
 
   /// Emit the coverage mapping data for an unused function.
   /// It creates mapping regions with the counter of zero.
   void emitEmptyMapping(const Decl *D, llvm::raw_ostream &OS);
 };
 
 } // end namespace CodeGen
 } // end namespace clang
 
 #endif

clang/lib/CodeGen/CoverageMappingGen.cpp

 /// A region of source code that can be mapped to a counter.
 class SourceMappingRegion {
   /// Primary Counter that is also used for Branch Regions for "True" branches.
   Counter Count;
 
   /// Secondary Counter used for Branch Regions for "False" branches.
   Optional<Counter> FalseCount;
 
+  /// Bitmap Index used for MC/DC.
+  unsigned BitmapIdx = 0;
+
+  /// Number of Conditions in a Boolean Expression used for MC/DC.
+  unsigned Conditions = 0;
+
+  /// Condition IDs used to model branch control flow for MC/DC.
+  unsigned ID = 0;
+  unsigned TrueID = 0;
+  unsigned FalseID = 0;
+
   /// The region's starting location.
   Optional<SourceLocation> LocStart;
 
   /// The region's ending location.
   Optional<SourceLocation> LocEnd;
 
   /// Whether this region is a gap region. The count from a gap region is set
   /// as the line execution count if there are no other regions on the line.
   bool GapRegion;
 
 public:
   SourceMappingRegion(Counter Count, Optional<SourceLocation> LocStart,
                       Optional<SourceLocation> LocEnd, bool GapRegion = false)
       : Count(Count), LocStart(LocStart), LocEnd(LocEnd), GapRegion(GapRegion) {
   }
 
   SourceMappingRegion(Counter Count, Optional<Counter> FalseCount,
+                      unsigned ID, unsigned TrueID, unsigned FalseID,
                       Optional<SourceLocation> LocStart,
                       Optional<SourceLocation> LocEnd, bool GapRegion = false)
-      : Count(Count), FalseCount(FalseCount), LocStart(LocStart),
-        LocEnd(LocEnd), GapRegion(GapRegion) {}
+      : Count(Count), FalseCount(FalseCount), ID(ID), TrueID(TrueID),
+        FalseID(FalseID), LocStart(LocStart), LocEnd(LocEnd),
+        GapRegion(GapRegion) {}
+
+  SourceMappingRegion(unsigned BitmapIdx, unsigned Conditions,
+                      Optional<SourceLocation> LocStart,
+                      Optional<SourceLocation> LocEnd)
+      : BitmapIdx(BitmapIdx), Conditions(Conditions), LocStart(LocStart),
+        LocEnd(LocEnd), GapRegion(false) {}
 
   const Counter &getCounter() const { return Count; }
 
   const Counter &getFalseCounter() const {
     assert(FalseCount && "Region has no alternate counter");
     return *FalseCount;
   }
 
SourceLocation getEndLoc() const {
     return *LocEnd;
   }
 
   bool isGap() const { return GapRegion; }
 
   void setGap(bool Gap) { GapRegion = Gap; }
 
   bool isBranch() const { return FalseCount.has_value(); }
+  unsigned getID() const { return ID; }
+  unsigned getTrueID() const { return TrueID; }
+  unsigned getFalseID() const { return FalseID; }
+
+  bool isDecision() const { return Conditions != 0; }
+  unsigned getBitmapIdx() const { return BitmapIdx; }
+  unsigned getConditions() const { return Conditions; }
 };
 
 /// Spelling locations for the start and end of a source region.
 struct SpellingRegion {
   /// The line where the region starts.
   unsigned LineStart;
 
   /// The column where the region starts.
for (const auto &Region : SourceRegions) {
 
       SourceLocation LocStart = Region.getBeginLoc();
       assert(SM.getFileID(LocStart).isValid() && "region in invalid file");
 
       // Ignore regions from system headers.
       if (SM.isInSystemHeader(SM.getSpellingLoc(LocStart)))
         continue;
 
       auto CovFileID = getCoverageFileID(LocStart);
       // Ignore regions that don't have a file, such as builtin macros.
       if (!CovFileID)
         continue;
 
       SourceLocation LocEnd = Region.getEndLoc();
       assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
              "region spans multiple files");
 
       // Don't add code regions for the area covered by expansion regions.
       // This not only suppresses redundant regions, but sometimes prevents
       // creating regions with wrong counters if, for example, a statement's
       // body ends at the end of a nested macro.
       if (Filter.count(std::make_pair(LocStart, LocEnd)))
         continue;
 
       // Find the spelling locations for the mapping region.
       SpellingRegion SR{SM, LocStart, LocEnd};
       assert(SR.isInSourceOrder() && "region start and end out of order");
 
       if (Region.isGap()) {
         MappingRegions.push_back(CounterMappingRegion::makeGapRegion(
             Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
             SR.LineEnd, SR.ColumnEnd));
       } else if (Region.isBranch()) {
         MappingRegions.push_back(CounterMappingRegion::makeBranchRegion(
-            Region.getCounter(), Region.getFalseCounter(), *CovFileID,
+            Region.getCounter(), Region.getFalseCounter(), Region.getID(),
+            Region.getTrueID(), Region.getFalseID(), *CovFileID, SR.LineStart,
+            SR.ColumnStart, SR.LineEnd, SR.ColumnEnd));
+      } else if (Region.isDecision()) {
+        MappingRegions.push_back(CounterMappingRegion::makeDecisionRegion(
+            Region.getBitmapIdx(), Region.getConditions(), *CovFileID,
             SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd));
       } else {
         MappingRegions.push_back(CounterMappingRegion::makeRegion(
             Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
             SR.LineEnd, SR.ColumnEnd));
       }
     }
   }
void write(llvm::raw_ostream &OS) {
     if (MappingRegions.empty())
       return;
 
     CoverageMappingWriter Writer(FileIDMapping, None, MappingRegions);
     Writer.write(OS);
   }
 };
 
+/// A wrapper object for maintaining stacks to track the resursive AST visitor
+/// walks for the purpose of assigning IDs to leaf-level conditions measured by
+/// MC/DC. The object is created with a reference to the MCDCBitmapMap that was
+/// created during the initial AST walk. The presence of a bitmap associated
+/// with a boolean expression (top-level logical operator nest) indicates that
+/// the boolean expression qualified for MC/DC.  The resulting condition IDs
+/// are preserved in a map reference that is also provided during object
+/// creation.
+struct MCDCCoverageBuilder {
+
+  /// The AST walk recursively visits nested logical-AND or logical-OR binary
+  /// operator nodes and then visits their LHS and RHS children nodes.  As this
+  /// happens, the algorithm will assign IDs to each operator's LHS and RHS side
+  /// as the walk moves deeper into the nest.  At each level of the recursive
+  /// nest, the LHS and RHS may actually correspond to larger subtrees (not
+  /// leaf-conditions). If this is the case, when that node is visited, the ID
+  /// assigned to the subtree is re-assigned to its LHS, and a new ID is given
+  /// to its RHS. At the end of the walk, all leaf-level conditions will have a
+  /// unique ID -- keep in mind that the final set of IDs may not be in
+  /// numerical order from left to right.
+  ///
+  /// Example: "x = (A && B) || (C && D) || (D && F)"
+  ///
+  ///      Visit Depth1:
+  ///              (A && B) || (C && D) || (D && F)
+  ///              ^-------LHS--------^    ^-RHS--^
+  ///                      ID=1              ID=2
+  ///
+  ///      Visit LHS-Depth2:
+  ///              (A && B) || (C && D)
+  ///              ^-LHS--^    ^-RHS--^
+  ///                ID=1        ID=3
+  ///
+  ///      Visit LHS-Depth3:
+  ///               (A && B)
+  ///               LHS   RHS
+  ///               ID=1  ID=4
+  ///
+  ///      Visit RHS-Depth3:
+  ///                         (C && D)
+  ///                         LHS   RHS
+  ///                         ID=3  ID=5
+  ///
+  ///      Visit RHS-Depth2:              (D && F)
+  ///                                     LHS   RHS
+  ///                                     ID=2  ID=6
+  ///
+  ///      Visit Depth1:
+  ///              (A && B)  || (C && D)  || (D && F)
+  ///              ID=1  ID=4   ID=3  ID=5   ID=2  ID=6
+  ///
+  /// A node ID of '0' always means MC/DC isn't being tracked.
+  ///
+  /// As the AST walk proceeds recursively, the algorithm will also use stacks
+  /// to track the IDs of logical-AND and logical-OR operations on the RHS so
+  /// that it can be determined which nodes are executed next, depending on how
+  /// a LHS or RHS of a logical-AND or logical-OR is evaluated.  This
+  /// information relies on the assigned IDs and are embedded within the
+  /// coverage region IDs of each branch region associated with a leaf-level
+  /// condition. This information helps the visualization tool reconstruct all
+  /// possible test vectors for the purposes of MC/DC analysis. if a "next" node
+  /// ID is '0', it means it's the end of the test vector. The following rules
+  /// are used:
+  ///
+  /// For logical-AND ("LHS && RHS"):
+  /// - If LHS is TRUE, execution goes to the RHS node.
+  /// - If LHS is FALSE, execution goes to the LHS node of the next logical-OR.
+  ///   If that does not exist, execution exits (ID == 0).
+  ///
+  /// - If RHS is TRUE, execution goes to LHS node of the next logical-AND.
+  ///   If that does not exist, execution exits (ID == 0).
+  /// - If RHS is FALSE, execution goes to the LHS node of the next logical-OR.
+  ///   If that does not exist, execution exits (ID == 0).
+  ///
+  /// For logical-OR ("LHS || RHS"):
+  /// - If LHS is TRUE, execution goes to the LHS node of the next logical-AND.
+  ///   If that does not exist, execution exits (ID == 0).
+  /// - If LHS is FALSE, execution goes to the RHS node.
+  ///
+  /// - If RHS is TRUE, execution goes to LHS node of the next logical-AND.
+  ///   If that does not exist, execution exits (ID == 0).
+  /// - If RHS is FALSE, execution goes to the LHS node of the next logical-OR.
+  ///   If that does not exist, execution exits (ID == 0).
+  ///
+  /// Finally, the condition IDs are also used when instrumenting the code to
+  /// indicate a unique offset into a temporary bitmap that represents the true
+  /// or false evaluation of that particular condition.
+
+private:
+  CodeGenModule &CGM;
+
+  std::stack<unsigned> AndRHS;
+  std::stack<unsigned> OrRHS;
+  std::stack<const BinaryOperator *> NestLevel;
+  llvm::DenseMap<const Stmt *, unsigned> &CondIDs;
+  llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap;
+  unsigned NextID = 1;
+  bool NotMapped = false;
+
+  /// Is this a logical-AND operation?
+  bool isLAnd(const BinaryOperator *E) const {
+    return E->getOpcode() == BO_LAnd;
+  }
+
+  /// Push an ID onto the corresponding RHS stack.
+  void pushRHS(const BinaryOperator *E) {
+    std::stack<unsigned> &rhs = isLAnd(E) ? AndRHS : OrRHS;
+    rhs.push(CondIDs[stripCond(E->getRHS())]);
+  }
+
+  /// Pop an ID from the corresponding RHS stack.
+  void popRHS(const BinaryOperator *E) {
+    std::stack<unsigned> &rhs = isLAnd(E) ? AndRHS : OrRHS;
+    if (!rhs.empty())
+      rhs.pop();
+  }
+
+  /// If the expected ID is on top, pop it off the corresponding RHS stack.
+  void popRHSifTop(const BinaryOperator *E) {
+    if (!OrRHS.empty() && CondIDs[(Expr *)E] == OrRHS.top())
+      OrRHS.pop();
+    else if (!AndRHS.empty() && CondIDs[(Expr *)E] == AndRHS.top())
+      AndRHS.pop();
+  }
+
+  /// Ignore parentheses and logical-NOT to track conditions consistently.
+  const Expr *stripCond(const Expr *C) {
+    if (const UnaryOperator *UnOp = dyn_cast<UnaryOperator>(C->IgnoreParens()))
+      if (UnOp->getOpcode() == UO_LNot)
+        C = UnOp->getSubExpr();
+    return C->IgnoreParens();
+  }
+
+public:
+  MCDCCoverageBuilder(CodeGenModule &CGM,
+                      llvm::DenseMap<const Stmt *, unsigned> &CondIDMap,
+                      llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap)
+      : CGM(CGM), CondIDs(CondIDMap), MCDCBitmapMap(MCDCBitmapMap) {}
+
+  /// Return the ID of the RHS of the next, upper nest-level logical-OR.
+  unsigned getNextLOrCondID() { return OrRHS.empty() ? 0 : OrRHS.top(); }
+
+  /// Return the ID of the RHS of the next, upper nest-level logical-AND.
+  unsigned getNextLAndCondID() { return AndRHS.empty() ? 0 : AndRHS.top(); }
+
+  /// Return the ID of a given condition.
+  unsigned getCondID(Expr *Cond) {
+    auto I = CondIDs.find(stripCond(Cond));
+    if (I == CondIDs.end())
+      return 0;
+    else
+      return I->second;
+  }
+
+  /// Push the binary operator statement to track the nest level and assign IDs
+  /// to the operator's LHS and RHS.  The RHS may be a larger subtree that is
+  /// broken up on successive levels.
+  void pushAndAssignIDs(const BinaryOperator *E) {
+    if (!CGM.getCodeGenOpts().MCDCCoverage)
+      return;
+
+    // If binary expression is disqualified, don't do mapping.
+    if (NestLevel.empty() &&
+        MCDCBitmapMap.find(stripCond((Expr *)E)) == MCDCBitmapMap.end())
+      NotMapped = true;
+
+    // Push Stmt on 'NestLevel' stack to keep track of nest location.
+    NestLevel.push(E);
+
+    // Don't go any further if we don't need to map condition IDs.
+    if (NotMapped)
+      return;
+
+    // If the operator itself has an assigned ID, this means it represents a
+    // larger subtree.  In this case, pop its ID out of the RHS stack and
+    // assign that ID to its LHS node.  Its RHS will receive a new ID.
+    if (CondIDs.find(stripCond((Expr *)E)) != CondIDs.end()) {
+      // If Stmt has an ID, assign its ID to LHS
+      CondIDs[stripCond(E->getLHS())] = CondIDs[(Expr *)E];
+
+      // Since the operator's LHS assumes the operator's same ID, pop the
+      // operator from the RHS stack so that if LHS short-circuits, it won't be
+      // incorrectly re-used as the node executed next.
+      popRHSifTop(E);
+    } else {
+      // Otherwise, assign ID+1 to LHS.
+      CondIDs[stripCond(E->getLHS())] = NextID++;
+    }
+
+    // Assign ID+1 to RHS.
+    CondIDs[stripCond(E->getRHS())] = NextID++;
+
+    // Push ID of Stmt's RHS so that LHS nodes know about it
+    pushRHS(E);
+  }
+
+  /// Pop the binary operator from the next level. If the walk is at the top of
+  /// the next, assign the total number of conditions.
+  unsigned popAndReturnCondCount(const BinaryOperator *E) {
+    if (!CGM.getCodeGenOpts().MCDCCoverage)
+      return 0;
+
+    unsigned TotalConds = 0;
+
+    // Pop Stmt from 'NestLevel' stack.
+    assert(NestLevel.top() == E);
+    NestLevel.pop();
+
+    // Reset state if not doing mapping.
+    if (NestLevel.empty() && NotMapped) {
+      NotMapped = false;
+      return 0;
+    }
+
+    // Pop RHS ID.
+    popRHS(E);
+
+    // If at the parent (NestLevel=0), set conds and reset.
+    if (NestLevel.empty()) {
+      TotalConds = NextID - 1;
+
+      // Reset ID back to beginning.
+      NextID = 1;
+    }
+    return TotalConds;
+  }
+};
+
 /// A StmtVisitor that creates coverage mapping regions which map
 /// from the source code locations to the PGO counters.
 struct CounterCoverageMappingBuilder
     : public CoverageMappingBuilder,
       public ConstStmtVisitor<CounterCoverageMappingBuilder> {
   /// The map of statements to count values.
   llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
 
+  /// The map of statements to bitmap coverage object values.
+  llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap;
+
   /// A stack of currently live regions.
   std::vector<SourceMappingRegion> RegionStack;
 
+  /// An object to manage MCDC regions.
+  MCDCCoverageBuilder MCDCBuilder;
+
   CounterExpressionBuilder Builder;
 
   /// A location in the most recently visited file or macro.
   ///
   /// This is used to adjust the active source regions appropriately when
   /// expressions cross file or macro boundaries.
   SourceLocation MostRecentLocation;
 
struct CounterCoverageMappingBuilder
 
   /// 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]);
   }
 
+  unsigned getRegionBitmap(const Stmt *S) { return MCDCBitmapMap[S]; }
+
   /// Push a region onto the stack.
   ///
   /// Returns the index on the stack where the region was pushed. This can be
   /// used with popRegions to exit a "scope", ending the region that was pushed.
   size_t pushRegion(Counter Count, Optional<SourceLocation> StartLoc = None,
                     Optional<SourceLocation> EndLoc = None,
-                    Optional<Counter> FalseCount = None) {
+                    Optional<Counter> FalseCount = None, unsigned ID = 0,
+                    unsigned TrueID = 0, unsigned FalseID = 0) {
 
     if (StartLoc && !FalseCount) {
       MostRecentLocation = *StartLoc;
     }
 
-    RegionStack.emplace_back(Count, FalseCount, StartLoc, EndLoc);
+    RegionStack.emplace_back(Count, FalseCount, ID, TrueID, FalseID, StartLoc,
+                             EndLoc);
+
+    return RegionStack.size() - 1;
+  }
+
+  size_t pushRegion(unsigned BitmapIdx, unsigned Conditions,
+                    Optional<SourceLocation> StartLoc = None,
+                    Optional<SourceLocation> EndLoc = None) {
+
+    RegionStack.emplace_back(BitmapIdx, Conditions, StartLoc, EndLoc);
 
     return RegionStack.size() - 1;
   }
 
   size_t locationDepth(SourceLocation Loc) {
     size_t Depth = 0;
     while (Loc.isValid()) {
       Loc = getIncludeOrExpansionLoc(Loc);
bool ConditionFoldsToBool(const Expr *Cond) {
     Expr::EvalResult Result;
     return (Cond->EvaluateAsInt(Result, CVM.getCodeGenModule().getContext()));
   }
 
   /// Create a Branch Region around an instrumentable condition for coverage
   /// and add it to the function's SourceRegions.  A branch region tracks a
   /// "True" counter and a "False" counter for boolean expressions that
   /// result in the generation of a branch.
-  void createBranchRegion(const Expr *C, Counter TrueCnt, Counter FalseCnt) {
+  void createBranchRegion(const Expr *C, Counter TrueCnt, Counter FalseCnt,
+                          unsigned ID = 0, unsigned TrueID = 0,
+                          unsigned FalseID = 0) {
     // Check for NULL conditions.
     if (!C)
       return;
 
     // Ensure we are an instrumentable condition (i.e. no "&&" or "||").  Push
     // region onto RegionStack but immediately pop it (which adds it to the
     // function's SourceRegions) because it doesn't apply to any other source
     // code other than the Condition.
     if (CodeGenFunction::isInstrumentedCondition(C)) {
       // If a condition can fold to true or false, the corresponding branch
       // will be removed.  Create a region with both counters hard-coded to
       // zero. This allows us to visualize them in a special way.
       // Alternatively, we can prevent any optimization done via
       // constant-folding by ensuring that ConstantFoldsToSimpleInteger() in
       // CodeGenFunction.c always returns false, but that is very heavy-handed.
       if (ConditionFoldsToBool(C))
         popRegions(pushRegion(Counter::getZero(), getStart(C), getEnd(C),
-                              Counter::getZero()));
+                              Counter::getZero(), ID, TrueID, FalseID));
       else
         // Otherwise, create a region with the True counter and False counter.
-        popRegions(pushRegion(TrueCnt, getStart(C), getEnd(C), FalseCnt));
+        popRegions(pushRegion(TrueCnt, getStart(C), getEnd(C), FalseCnt, ID,
+                              TrueID, FalseID));
     }
   }
 
+  /// Create a Decision Region with a BitmapIdx and number of Conditions. This
+  /// type of region "contains" branch regions, one for each of the conditions.
+  /// The visualization tool will group everything together.
+  void createDecisionRegion(const Expr *C, unsigned BitmapIdx, unsigned Conds) {
+    popRegions(pushRegion(BitmapIdx, Conds, getStart(C), getEnd(C)));
+  }
+
   /// Create a Branch Region around a SwitchCase for code coverage
   /// and add it to the function's SourceRegions.
   void createSwitchCaseRegion(const SwitchCase *SC, Counter TrueCnt,
                               Counter FalseCnt) {
     // Push region onto RegionStack but immediately pop it (which adds it to
     // the function's SourceRegions) because it doesn't apply to any other
     // source other than the SwitchCase.
     popRegions(pushRegion(TrueCnt, getStart(SC), SC->getColonLoc(), FalseCnt));
for (SourceMappingRegion &I : llvm::reverse(RegionStack)) {
       }
 
       while (!SM.isInFileID(Loc, ParentFile)) {
         // The most nested region for each start location is the one with the
         // correct count. We avoid creating redundant regions by stopping once
         // we've seen this region.
         if (StartLocs.insert(Loc).second) {
           if (I.isBranch())
-            SourceRegions.emplace_back(I.getCounter(), I.getFalseCounter(), Loc,
-                                       getEndOfFileOrMacro(Loc), I.isBranch());
+            SourceRegions.emplace_back(
+                I.getCounter(), I.getFalseCounter(), I.getID(), I.getTrueID(),
+                I.getFalseID(), Loc, getEndOfFileOrMacro(Loc), I.isBranch());
           else
             SourceRegions.emplace_back(I.getCounter(), Loc,
                                        getEndOfFileOrMacro(Loc));
         }
         Loc = getIncludeOrExpansionLoc(Loc);
       }
       I.setStartLoc(getPreciseTokenLocEnd(Loc));
     }
struct CounterCoverageMappingBuilder
   struct BreakContinue {
     Counter BreakCount;
     Counter ContinueCount;
   };
   SmallVector<BreakContinue, 8> BreakContinueStack;
 
   CounterCoverageMappingBuilder(
       CoverageMappingModuleGen &CVM,
-      llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM,
+      llvm::DenseMap<const Stmt *, unsigned> &CounterMap,
+      llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap,
+      llvm::DenseMap<const Stmt *, unsigned> &CondIDMap, SourceManager &SM,
       const LangOptions &LangOpts)
-      : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap) {}
+      : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap),
+        MCDCBitmapMap(MCDCBitmapMap),
+        MCDCBuilder(CVM.getCodeGenModule(), CondIDMap, MCDCBitmapMap) {}
 
   /// Write the mapping data to the output stream
   void write(llvm::raw_ostream &OS) {
     llvm::SmallVector<unsigned, 8> VirtualFileMapping;
     gatherFileIDs(VirtualFileMapping);
     SourceRegionFilter Filter = emitExpansionRegions();
     emitSourceRegions(Filter);
     gatherSkippedRegions();
propagateCounts(subtractCounters(ParentCount, TrueCount),
                     E->getFalseExpr());
 
     // Create Branch Region around condition.
     createBranchRegion(E->getCond(), TrueCount,
                        subtractCounters(ParentCount, TrueCount));
   }
 
   void VisitBinLAnd(const BinaryOperator *E) {
+    // Keep track of Binary Operator and assign MCDC condition IDs
+    MCDCBuilder.pushAndAssignIDs(E);
+
     extendRegion(E->getLHS());
     propagateCounts(getRegion().getCounter(), E->getLHS());
     handleFileExit(getEnd(E->getLHS()));
 
     // Counter tracks the right hand side of a logical and operator.
     extendRegion(E->getRHS());
     propagateCounts(getRegionCounter(E), E->getRHS());
 
+    // Process Binary Operator and create MCDC Decision Region if top-level
+    unsigned NumConds = 0;
+    if ((NumConds = MCDCBuilder.popAndReturnCondCount(E)))
+      createDecisionRegion(E, getRegionBitmap(E), NumConds);
+
     // Extract the RHS's Execution Counter.
     Counter RHSExecCnt = getRegionCounter(E);
 
     // Extract the RHS's "True" Instance Counter.
     Counter RHSTrueCnt = getRegionCounter(E->getRHS());
 
     // Extract the Parent Region Counter.
     Counter ParentCnt = getRegion().getCounter();
 
+    // Extract the MCDC condition IDs (returns 0 if not needed).
+    unsigned NextOrID = MCDCBuilder.getNextLOrCondID();
+    unsigned NextAndID = MCDCBuilder.getNextLAndCondID();
+    unsigned LHSid = MCDCBuilder.getCondID(E->getLHS());
+    unsigned RHSid = MCDCBuilder.getCondID(E->getRHS());
+
     // Create Branch Region around LHS condition.
+    // MC/DC: For "LHS && RHS"
+    // - If LHS is TRUE, execution goes to the RHS.
+    // - If LHS is FALSE, execution goes to the LHS of the next logical-OR.
+    //   If that does not exist, execution exits (ID == 0).
     createBranchRegion(E->getLHS(), RHSExecCnt,
-                       subtractCounters(ParentCnt, RHSExecCnt));
+                       subtractCounters(ParentCnt, RHSExecCnt), LHSid, RHSid,
+                       NextOrID);
 
     // Create Branch Region around RHS condition.
+    // MC/DC: For "LHS && RHS"
+    // - If RHS is TRUE, execution goes to LHS of the next logical-AND.
+    //   If that does not exist, execution exits (ID == 0).
+    // - If RHS is FALSE, execution goes to the LHS of the next logical-OR.
+    //   If that does not exist, execution exits (ID == 0).
     createBranchRegion(E->getRHS(), RHSTrueCnt,
-                       subtractCounters(RHSExecCnt, RHSTrueCnt));
+                       subtractCounters(RHSExecCnt, RHSTrueCnt), RHSid,
+                       NextAndID, NextOrID);
   }
 
   void VisitBinLOr(const BinaryOperator *E) {
+    // Keep track of Binary Operator and assign MCDC condition IDs
+    MCDCBuilder.pushAndAssignIDs(E);
+
     extendRegion(E->getLHS());
     propagateCounts(getRegion().getCounter(), E->getLHS());
     handleFileExit(getEnd(E->getLHS()));
 
     // Counter tracks the right hand side of a logical or operator.
     extendRegion(E->getRHS());
     propagateCounts(getRegionCounter(E), E->getRHS());
 
+    // Process Binary Operator and create MCDC Decision Region if top-level
+    unsigned NumConds = 0;
+    if ((NumConds = MCDCBuilder.popAndReturnCondCount(E)))
+      createDecisionRegion(E, getRegionBitmap(E), NumConds);
+
     // Extract the RHS's Execution Counter.
     Counter RHSExecCnt = getRegionCounter(E);
 
     // Extract the RHS's "False" Instance Counter.
     Counter RHSFalseCnt = getRegionCounter(E->getRHS());
 
     // Extract the Parent Region Counter.
     Counter ParentCnt = getRegion().getCounter();
 
+    // Extract the MCDC condition IDs (returns 0 if not needed).
+    unsigned NextOrID = MCDCBuilder.getNextLOrCondID();
+    unsigned NextAndID = MCDCBuilder.getNextLAndCondID();
+    unsigned LHSid = MCDCBuilder.getCondID(E->getLHS());
+    unsigned RHSid = MCDCBuilder.getCondID(E->getRHS());
+
     // Create Branch Region around LHS condition.
+    // MC/DC: For "LHS || RHS"
+    // - If LHS is TRUE, execution goes to the LHS of the next logical-AND.
+    //   If that does not exist, execution exits (ID == 0).
+    // - If LHS is FALSE, execution goes to the RHS.
     createBranchRegion(E->getLHS(), subtractCounters(ParentCnt, RHSExecCnt),
-                       RHSExecCnt);
+                       RHSExecCnt, LHSid, NextAndID, RHSid);
 
     // Create Branch Region around RHS condition.
+    // MC/DC: For "LHS || RHS"
+    // - If RHS is TRUE, execution goes to LHS of the next logical-AND.
+    //   If that does not exist, execution exits (ID == 0).
+    // - If RHS is FALSE, execution goes to the LHS of the next logical-OR.
+    //   If that does not exist, execution exits (ID == 0).
     createBranchRegion(E->getRHS(), subtractCounters(RHSExecCnt, RHSFalseCnt),
-                       RHSFalseCnt);
+                       RHSFalseCnt, RHSid, NextAndID, NextOrID);
   }
 
   void VisitLambdaExpr(const LambdaExpr *LE) {
     // Lambdas are treated as their own functions for now, so we shouldn't
     // propagate counts into them.
   }
 };
 
case CounterMappingRegion::ExpansionRegion:
       break;
     case CounterMappingRegion::SkippedRegion:
       OS << "Skipped,";
       break;
     case CounterMappingRegion::GapRegion:
       OS << "Gap,";
       break;
     case CounterMappingRegion::BranchRegion:
+    case CounterMappingRegion::MCDCBranchRegion:
       OS << "Branch,";
       break;
+    case CounterMappingRegion::MCDCDecisionRegion:
+      OS << "Decision,";
+      break;
     }
 
     OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
        << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
+
+    if (R.Kind == CounterMappingRegion::MCDCDecisionRegion) {
+      OS << "M:" << R.BitmapIdx << ", C:" << R.NumConditions;
+    } else {
       Ctx.dump(R.Count, OS);
 
-    if (R.Kind == CounterMappingRegion::BranchRegion) {
+      if (R.Kind == CounterMappingRegion::BranchRegion ||
+          R.Kind == CounterMappingRegion::MCDCBranchRegion) {
         OS << ", ";
         Ctx.dump(R.FalseCount, OS);
       }
+    }
+
+    if (R.Kind == CounterMappingRegion::MCDCBranchRegion)
+      OS << " [" << R.ID << "," << R.TrueID << "," << R.FalseID << "] ";
 
     if (R.Kind == CounterMappingRegion::ExpansionRegion)
       OS << " (Expanded file = " << R.ExpandedFileID << ")";
     OS << "\n";
   }
 }
 
 CoverageMappingModuleGen::CoverageMappingModuleGen(
if (It != FileEntries.end())
     return It->second;
   unsigned FileID = FileEntries.size() + 1;
   FileEntries.insert(std::make_pair(File, FileID));
   return FileID;
 }
 
 void CoverageMappingGen::emitCounterMapping(const Decl *D,
                                             llvm::raw_ostream &OS) {
-  assert(CounterMap);
-  CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
+  assert(CounterMap && MCDCBitmapMap);
+  CounterCoverageMappingBuilder Walker(CVM, *CounterMap, *MCDCBitmapMap,
+                                       *CondIDMap, SM, LangOpts);
   Walker.VisitDecl(D);
   Walker.write(OS);
 }
 
 void CoverageMappingGen::emitEmptyMapping(const Decl *D,
                                           llvm::raw_ostream &OS) {
   EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
   Walker.VisitDecl(D);
   Walker.write(OS);
 }

clang/lib/Driver/ToolChains/Clang.cpp

if (Args.hasFlag(options::OPT_fcoverage_mapping,
     if (!ProfileGenerateArg)
       D.Diag(clang::diag::err_drv_argument_only_allowed_with)
           << "-fcoverage-mapping"
           << "-fprofile-instr-generate";
 
     CmdArgs.push_back("-fcoverage-mapping");
   }
 
+  if (Args.hasFlag(options::OPT_fmcdc_coverage, options::OPT_fno_mcdc_coverage,
+                   false)) {
+    if (!Args.hasFlag(options::OPT_fcoverage_mapping,
+                      options::OPT_fno_coverage_mapping, false))
+      D.Diag(clang::diag::err_drv_argument_only_allowed_with)
+          << "-fmcdc"
+          << "-fcoverage-mapping";
+
+    CmdArgs.push_back("-fmcdc");
+  }
+
   if (Arg *A = Args.getLastArg(options::OPT_ffile_compilation_dir_EQ,
                                options::OPT_fcoverage_compilation_dir_EQ)) {
     if (A->getOption().matches(options::OPT_ffile_compilation_dir_EQ))
       CmdArgs.push_back(Args.MakeArgString(
           Twine("-fcoverage-compilation-dir=") + A->getValue()));
     else
       A->render(Args, CmdArgs);
   } else if (llvm::ErrorOr<std::string> CWD =

clang/lib/Driver/ToolChains/Darwin.cpp

void Darwin::addProfileRTLibs(const ArgList &Args,
   // runtime's functionality.
   if (hasExportSymbolDirective(Args) && ForGCOV) {
     addExportedSymbol(CmdArgs, "___gcov_dump");
     addExportedSymbol(CmdArgs, "___gcov_reset");
     addExportedSymbol(CmdArgs, "_writeout_fn_list");
     addExportedSymbol(CmdArgs, "_reset_fn_list");
   }
 
-  // Align __llvm_prf_{cnts,data} sections to the maximum expected page
+  // Align __llvm_prf_{cnts,bits,data} sections to the maximum expected page
   // alignment. This allows profile counters to be mmap()'d to disk. Note that
   // it's not enough to just page-align __llvm_prf_cnts: the following section
   // must also be page-aligned so that its data is not clobbered by mmap().
   //
   // The section alignment is only needed when continuous profile sync is
   // enabled, but this is expected to be the default in Xcode. Specifying the
   // extra alignment also allows the same binary to be used with/without sync
   // enabled.
   if (!ForGCOV) {
-    for (auto IPSK : {llvm::IPSK_cnts, llvm::IPSK_data}) {
+    for (auto IPSK : {llvm::IPSK_cnts, llvm::IPSK_bitmap, llvm::IPSK_data}) {
       addSectalignToPage(
           Args, CmdArgs, "__DATA",
           llvm::getInstrProfSectionName(IPSK, llvm::Triple::MachO,
                                         /*AddSegmentInfo=*/false));
     }
   }
 }
 

clang/test/CoverageMapping/branch-constfolded.cpp

 // Test that branch regions are not generated for constant-folded conditions.
 
 // RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name branch-constfolded.cpp %s | FileCheck %s
+// RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name branch-constfolded.cpp %s | FileCheck %s -check-prefix=MCDC
 
 // CHECK-LABEL: _Z6fand_0b:
-bool fand_0(bool a) {
+bool fand_0(bool a) {      // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:20 = M:0, C:2
   return false && a;       // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:15 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:19 -> [[@LINE-1]]:20 = #2, (#1 - #2)
 
 // CHECK-LABEL: _Z6fand_1b:
-bool fand_1(bool a) {
+bool fand_1(bool a) {      // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:19 = M:0, C:2
   return a && true;        // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = #1, (#0 - #1)
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:19 = 0, 0
 
 // CHECK-LABEL: _Z6fand_2bb:
-bool fand_2(bool a, bool b) {
+bool fand_2(bool a, bool b) {// MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:25 = M:0, C:3
   return false && a && b;  // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:15 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:19 -> [[@LINE-1]]:20 = #4, (#3 - #4)
                            // CHECK: Branch,File 0, [[@LINE-2]]:24 -> [[@LINE-2]]:25 = #2, (#1 - #2)
 
 // CHECK-LABEL: _Z6fand_3bb:
-bool fand_3(bool a, bool b) {
+bool fand_3(bool a, bool b) {// MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:24 = M:0, C:3
   return a && true && b;   // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = #3, (#0 - #3)
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:19 = 0, 0
                            // CHECK: Branch,File 0, [[@LINE-2]]:23 -> [[@LINE-2]]:24 = #2, (#1 - #2)
 
 // CHECK-LABEL: _Z6fand_4bb:
-bool fand_4(bool a, bool b) {
+bool fand_4(bool a, bool b) {// MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:25 = M:0, C:3
   return a && b && false;  // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = #3, (#0 - #3)
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:16 = #4, (#3 - #4)
                            // CHECK: Branch,File 0, [[@LINE-2]]:20 -> [[@LINE-2]]:25 = 0, 0
 
 // CHECK-LABEL: _Z6fand_5b:
-bool fand_5(bool a) {
+bool fand_5(bool a) {      // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:23 = M:0, C:2
   return false && true;    // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:15 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:19 -> [[@LINE-1]]:23 = 0, 0
 
 // CHECK-LABEL: _Z6fand_6b:
-bool fand_6(bool a) {
+bool fand_6(bool a) {      // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:19 = M:0, C:2
   return true && a;        // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:14 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:18 -> [[@LINE-1]]:19 = #2, (#1 - #2)
 
 // CHECK-LABEL: _Z6fand_7b:
-bool fand_7(bool a) {
+bool fand_7(bool a) {      // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:20 = M:0, C:2
   return a && false;       // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = #1, (#0 - #1)
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:20 = 0, 0
 
 // CHECK-LABEL: _Z5for_0b:
-bool for_0(bool a) {
+bool for_0(bool a) {       // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:19 = M:0, C:2
   return true || a;        // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:14 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:18 -> [[@LINE-1]]:19 = (#1 - #2), #2
 
 // CHECK-LABEL: _Z5for_1b:
-bool for_1(bool a) {
+bool for_1(bool a) {       // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:20 = M:0, C:2
   return a || false;       // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = (#0 - #1), #1
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:20 = 0, 0
 
 // CHECK-LABEL: _Z5for_2bb:
-bool for_2(bool a, bool b) {
+bool for_2(bool a, bool b) {// MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:24 = M:0, C:3
   return true || a || b;   // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:14 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:18 -> [[@LINE-1]]:19 = (#3 - #4), #4
                            // CHECK: Branch,File 0, [[@LINE-2]]:23 -> [[@LINE-2]]:24 = (#1 - #2), #2
 
 // CHECK-LABEL: _Z5for_3bb:
-bool for_3(bool a, bool b) {
+bool for_3(bool a, bool b) {// MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:25 = M:0, C:3
   return a || false || b;  // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = (#0 - #3), #3
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:20 = 0, 0
                            // CHECK: Branch,File 0, [[@LINE-2]]:24 -> [[@LINE-2]]:25 = (#1 - #2), #2
 
 // CHECK-LABEL: _Z5for_4bb:
-bool for_4(bool a, bool b) {
+bool for_4(bool a, bool b) {// MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:24 = M:0, C:3
   return a || b || true;   // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = (#0 - #3), #3
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:16 = (#3 - #4), #4
                            // CHECK: Branch,File 0, [[@LINE-2]]:20 -> [[@LINE-2]]:24 = 0, 0
 
 // CHECK-LABEL: _Z5for_5b:
-bool for_5(bool a) {
+bool for_5(bool a) {       // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:23 = M:0, C:2
   return true || false;    // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:14 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:18 -> [[@LINE-1]]:23 = 0, 0
 
 // CHECK-LABEL: _Z5for_6b:
-bool for_6(bool a) {
+bool for_6(bool a) {       // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:20 = M:0, C:2
   return false || a;       // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:15 = 0, 0
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:19 -> [[@LINE-1]]:20 = (#1 - #2), #2
 
 // CHECK-LABEL: _Z5for_7b:
-bool for_7(bool a) {
+bool for_7(bool a) {       // MCDC: Decision,File 0, [[@LINE+1]]:10 -> [[@LINE+1]]:19 = M:0, C:2
   return a || true;        // CHECK: Branch,File 0, [[@LINE]]:10 -> [[@LINE]]:11 = (#0 - #1), #1
 }                          // CHECK: Branch,File 0, [[@LINE-1]]:15 -> [[@LINE-1]]:19 = 0, 0
 

clang/test/CoverageMapping/branch-mincounters.cpp

 // Test to ensure right number of counters are allocated and used for nested
 // logical operators on branch conditions for branch coverage.
 
 // RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name branch-logical-mixed.cpp %s | FileCheck %s
+// RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name branch-logical-mixed.cpp %s | FileCheck %s
 
 
 // CHECK-LABEL: _Z5func1ii:
 bool func1(int a, int b) {
   bool b0 = a <= b;
   bool b1 = a == b;
   bool b2 = a >= b;
 

clang/test/CoverageMapping/branch-templates.cpp

 // Test that branch regions are generated for conditions in function template
 // instantiations.
 
 // RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name branch-templates.cpp %s | FileCheck %s
+// RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name branch-templates.cpp %s | FileCheck %s
 
 template<typename T>
 void unused(T x) {
   return;
 }
 
 template<typename T>
 int func(T x) {

clang/test/CoverageMapping/if.cpp

 // RUN: %clang_cc1 -mllvm -emptyline-comment-coverage=false -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -std=c++2b -triple %itanium_abi_triple -main-file-name if.cpp %s | FileCheck %s
+// RUN: %clang_cc1 -mllvm -emptyline-comment-coverage=false -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -std=c++2b -triple %itanium_abi_triple -main-file-name if.cpp %s | FileCheck %s
 
 int nop() { return 0; }
 
 // CHECK-LABEL: _Z3foov:
                                 // CHECK-NEXT: [[@LINE+3]]:12 -> [[@LINE+8]]:2 = #0
                                 // CHECK-NEXT: [[@LINE+3]]:15 -> [[@LINE+3]]:19 = #0
                                 // CHECK-NEXT: Branch,File 0, [[@LINE+2]]:15 -> [[@LINE+2]]:19 = 0, 0
 void foo() {                    // CHECK-NEXT: Gap,File 0, [[@LINE+1]]:21 -> [[@LINE+1]]:22 = #2

clang/test/CoverageMapping/logical.cpp

 // RUN: %clang_cc1 -mllvm -emptyline-comment-coverage=false -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name logical.cpp %s | FileCheck %s
+// RUN: %clang_cc1 -mllvm -emptyline-comment-coverage=false -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name logical.cpp %s | FileCheck %s -check-prefix=MCDC
 
-int main() {                        // CHECK: File 0, [[@LINE]]:12 -> [[@LINE+22]]:2 = #0
+int main() {                        // CHECK: File 0, [[@LINE]]:12 -> [[@LINE+23]]:2 = #0
   bool bt = true;
-  bool bf = false;
+  bool bf = false;                  // MCDC: Decision,File 0, [[@LINE+1]]:12 -> [[@LINE+1]]:20 = M:0, C:2
   bool a = bt && bf;                // CHECK-NEXT: File 0, [[@LINE]]:12 -> [[@LINE]]:14 = #0
                                     // CHECK-NEXT: Branch,File 0, [[@LINE-1]]:12 -> [[@LINE-1]]:14 = #1, (#0 - #1)
                                     // CHECK-NEXT: File 0, [[@LINE-2]]:18 -> [[@LINE-2]]:20 = #1
                                     // CHECK-NEXT: Branch,File 0, [[@LINE-3]]:18 -> [[@LINE-3]]:20 = #2, (#1 - #2)
-
+                                    // MCDC: Decision,File 0, [[@LINE+1]]:7 -> [[@LINE+2]]:9 = M:1, C:2
   a = bt &&                         // CHECK-NEXT: File 0, [[@LINE]]:7 -> [[@LINE]]:9 = #0
       bf;                           // CHECK-NEXT: Branch,File 0, [[@LINE-1]]:7 -> [[@LINE-1]]:9 = #3, (#0 - #3)
                                     // CHECK-NEXT: File 0, [[@LINE-1]]:7 -> [[@LINE-1]]:9 = #3
                                     // CHECK-NEXT: Branch,File 0, [[@LINE-2]]:7 -> [[@LINE-2]]:9 = #4, (#3 - #4)
+                                    // MCDC: Decision,File 0, [[@LINE+1]]:7 -> [[@LINE+1]]:15 = M:2, C:2
   a = bf || bt;                     // CHECK-NEXT: File 0, [[@LINE]]:7 -> [[@LINE]]:9 = #0
                                     // CHECK-NEXT: Branch,File 0, [[@LINE-1]]:7 -> [[@LINE-1]]:9 = (#0 - #5), #5
                                     // CHECK-NEXT: File 0, [[@LINE-2]]:13 -> [[@LINE-2]]:15 = #5
                                     // CHECK-NEXT: Branch,File 0, [[@LINE-3]]:13 -> [[@LINE-3]]:15 = (#5 - #6), #6
-
+                                    // MCDC: Decision,File 0, [[@LINE+1]]:7 -> [[@LINE+2]]:9 = M:3, C:2
   a = bf ||                         // CHECK-NEXT: File 0, [[@LINE]]:7 -> [[@LINE]]:9 = #0
       bt;                           // CHECK-NEXT: Branch,File 0, [[@LINE-1]]:7 -> [[@LINE-1]]:9 = (#0 - #7), #7
                                     // CHECK-NEXT: File 0, [[@LINE-1]]:7 -> [[@LINE-1]]:9 = #7
                                     // CHECK-NEXT: Branch,File 0, [[@LINE-2]]:7 -> [[@LINE-2]]:9 = (#7 - #8), #8
   return 0;
 }

clang/test/CoverageMapping/mcdc-error-conditions.cpp

+// RUN: not %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only %s 2>&1| FileCheck %s
+
+bool func_conditions(bool a, bool b, bool c, bool d, bool e, bool f, bool g) {
+    return a && b && c && d && e && f && g;
+}
+
+// CHECK: error: MC/DC: Unsupported boolean expression; number of conditions{{.*}} exceeds max

clang/test/CoverageMapping/mcdc-error-nests.cpp

+// RUN: not %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only %s 2>&1| FileCheck %s
+
+// "Split-nest" -- boolean expressions within boolean expressions.
+extern bool bar(bool);
+bool func_split_nest(bool a, bool b, bool c, bool d, bool e, bool f, bool g) {
+    bool res = a && b && c && bar(d && e) && f && g;
+    return bar(res);
+}
+
+// CHECK: error: MC/DC: Unsupported boolean expression; contains an operation with a nested boolean expression.

clang/test/CoverageMapping/mcdc-logical-scalar-ids.cpp

+// RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only %s | FileCheck %s
+
+extern bool bar (bool, bool, bool, bool, bool);
+bool func_scalar_and(bool a, bool b, bool c, bool d, bool e, bool f) {
+    bool res1 = a && b;
+    bool res2 = a && b && c;
+    bool res3 = a && b && c && d;
+    bool res4 = a && b && c && d && e;
+    bool res5 = a && b && c && d && e && f;
+    return bar(res1, res2, res3, res4, res5);
+}
+
+// CHECK: Decision,File 0, 5:17 -> 5:23 = M:0, C:2
+// CHECK: Branch,File 0, 5:17 -> 5:18 = #1, (#0 - #1) [1,2,0]
+// CHECK: Branch,File 0, 5:22 -> 5:23 = #2, (#1 - #2) [2,0,0]
+// CHECK: Decision,File 0, 6:17 -> 6:28 = M:1, C:3
+// CHECK: Branch,File 0, 6:17 -> 6:18 = #5, (#0 - #5) [1,3,0]
+// CHECK: Branch,File 0, 6:22 -> 6:23 = #6, (#5 - #6) [3,2,0]
+// CHECK: Branch,File 0, 6:27 -> 6:28 = #4, (#3 - #4) [2,0,0]
+// CHECK: Decision,File 0, 7:17 -> 7:33 = M:2, C:4
+// CHECK: Branch,File 0, 7:17 -> 7:18 = #11, (#0 - #11) [1,4,0]
+// CHECK: Branch,File 0, 7:22 -> 7:23 = #12, (#11 - #12) [4,3,0]
+// CHECK: Branch,File 0, 7:27 -> 7:28 = #10, (#9 - #10) [3,2,0]
+// CHECK: Branch,File 0, 7:32 -> 7:33 = #8, (#7 - #8) [2,0,0]
+// CHECK: Decision,File 0, 8:17 -> 8:38 = M:4, C:5
+// CHECK: Branch,File 0, 8:17 -> 8:18 = #19, (#0 - #19) [1,5,0]
+// CHECK: Branch,File 0, 8:22 -> 8:23 = #20, (#19 - #20) [5,4,0]
+// CHECK: Branch,File 0, 8:27 -> 8:28 = #18, (#17 - #18) [4,3,0]
+// CHECK: Branch,File 0, 8:32 -> 8:33 = #16, (#15 - #16) [3,2,0]
+// CHECK: Branch,File 0, 8:37 -> 8:38 = #14, (#13 - #14) [2,0,0]
+// CHECK: Decision,File 0, 9:17 -> 9:43 = M:8, C:6
+// CHECK: Branch,File 0, 9:17 -> 9:18 = #29, (#0 - #29) [1,6,0]
+// CHECK: Branch,File 0, 9:22 -> 9:23 = #30, (#29 - #30) [6,5,0]
+// CHECK: Branch,File 0, 9:27 -> 9:28 = #28, (#27 - #28) [5,4,0]
+// CHECK: Branch,File 0, 9:32 -> 9:33 = #26, (#25 - #26) [4,3,0]
+// CHECK: Branch,File 0, 9:37 -> 9:38 = #24, (#23 - #24) [3,2,0]
+// CHECK: Branch,File 0, 9:42 -> 9:43 = #22, (#21 - #22) [2,0,0]
+
+bool func_scalar_or(bool a, bool b, bool c, bool d, bool e, bool f) {
+    bool res1 = a || b;
+    bool res2 = a || b || c;
+    bool res3 = a || b || c || d;
+    bool res4 = a || b || c || d || e;
+    bool res5 = a || b || c || d || e || f;
+    return bar(res1, res2, res3, res4, res5);
+}
+
+// CHECK: Decision,File 0, 40:17 -> 40:23 = M:0, C:2
+// CHECK: Branch,File 0, 40:17 -> 40:18 = (#0 - #1), #1 [1,0,2]
+// CHECK: Branch,File 0, 40:22 -> 40:23 = (#1 - #2), #2 [2,0,0]
+// CHECK: Decision,File 0, 41:17 -> 41:28 = M:1, C:3
+// CHECK: Branch,File 0, 41:17 -> 41:18 = (#0 - #5), #5 [1,0,3]
+// CHECK: Branch,File 0, 41:22 -> 41:23 = (#5 - #6), #6 [3,0,2]
+// CHECK: Branch,File 0, 41:27 -> 41:28 = (#3 - #4), #4 [2,0,0]
+// CHECK: Decision,File 0, 42:17 -> 42:33 = M:2, C:4
+// CHECK: Branch,File 0, 42:17 -> 42:18 = (#0 - #11), #11 [1,0,4]
+// CHECK: Branch,File 0, 42:22 -> 42:23 = (#11 - #12), #12 [4,0,3]
+// CHECK: Branch,File 0, 42:27 -> 42:28 = (#9 - #10), #10 [3,0,2]
+// CHECK: Branch,File 0, 42:32 -> 42:33 = (#7 - #8), #8 [2,0,0]
+// CHECK: Decision,File 0, 43:17 -> 43:38 = M:4, C:5
+// CHECK: Branch,File 0, 43:17 -> 43:18 = (#0 - #19), #19 [1,0,5]
+// CHECK: Branch,File 0, 43:22 -> 43:23 = (#19 - #20), #20 [5,0,4]
+// CHECK: Branch,File 0, 43:27 -> 43:28 = (#17 - #18), #18 [4,0,3]
+// CHECK: Branch,File 0, 43:32 -> 43:33 = (#15 - #16), #16 [3,0,2]
+// CHECK: Branch,File 0, 43:37 -> 43:38 = (#13 - #14), #14 [2,0,0]
+// CHECK: Decision,File 0, 44:17 -> 44:43 = M:8, C:6
+// CHECK: Branch,File 0, 44:17 -> 44:18 = (#0 - #29), #29 [1,0,6]
+// CHECK: Branch,File 0, 44:22 -> 44:23 = (#29 - #30), #30 [6,0,5]
+// CHECK: Branch,File 0, 44:27 -> 44:28 = (#27 - #28), #28 [5,0,4]
+// CHECK: Branch,File 0, 44:32 -> 44:33 = (#25 - #26), #26 [4,0,3]
+// CHECK: Branch,File 0, 44:37 -> 44:38 = (#23 - #24), #24 [3,0,2]
+// CHECK: Branch,File 0, 44:42 -> 44:43 = (#21 - #22), #22 [2,0,0]
+
+
+bool func_scalar_mix(bool a, bool b, bool c, bool d, bool e, bool f) {
+    bool res1 = a || b;
+    bool res2 = a && (b || c);
+    bool res3 = (a || b) && (c || d);
+    bool res4 = a && (b || c) && (d || e);
+    bool res5 = (a || b) && (c || d) && (e || f);
+    return bar(res1, res2, res3, res4, res5);
+}
+
+// CHECK:  Decision,File 0, 76:17 -> 76:23 = M:0, C:2
+// CHECK:  Branch,File 0, 76:17 -> 76:18 = (#0 - #1), #1 [1,0,2]
+// CHECK:  Branch,File 0, 76:22 -> 76:23 = (#1 - #2), #2 [2,0,0]
+// CHECK:  Decision,File 0, 77:17 -> 77:30 = M:1, C:3
+// CHECK:  Branch,File 0, 77:17 -> 77:18 = #3, (#0 - #3) [1,2,0]
+// CHECK:  Branch,File 0, 77:23 -> 77:24 = (#3 - #4), #4 [2,0,3]
+// CHECK:  Branch,File 0, 77:28 -> 77:29 = (#4 - #5), #5 [3,0,0]
+// CHECK:  Decision,File 0, 78:17 -> 78:37 = M:2, C:4
+// CHECK:  Branch,File 0, 78:18 -> 78:19 = (#0 - #7), #7 [1,2,3]
+// CHECK:  Branch,File 0, 78:23 -> 78:24 = (#7 - #8), #8 [3,2,0]
+// CHECK:  Branch,File 0, 78:30 -> 78:31 = (#6 - #9), #9 [2,0,4]
+// CHECK:  Branch,File 0, 78:35 -> 78:36 = (#9 - #10), #10 [4,0,0]
+// CHECK:  Decision,File 0, 79:17 -> 79:42 = M:4, C:5
+// CHECK:  Branch,File 0, 79:17 -> 79:18 = #12, (#0 - #12) [1,3,0]
+// CHECK:  Branch,File 0, 79:23 -> 79:24 = (#12 - #13), #13 [3,2,4]
+// CHECK:  Branch,File 0, 79:28 -> 79:29 = (#13 - #14), #14 [4,2,0]
+// CHECK:  Branch,File 0, 79:35 -> 79:36 = (#11 - #15), #15 [2,0,5]
+// CHECK:  Branch,File 0, 79:40 -> 79:41 = (#15 - #16), #16 [5,0,0]
+// CHECK:  Decision,File 0, 80:17 -> 80:49 = M:8, C:6
+// CHECK:  Branch,File 0, 80:18 -> 80:19 = (#0 - #19), #19 [1,3,4]
+// CHECK:  Branch,File 0, 80:23 -> 80:24 = (#19 - #20), #20 [4,3,0]
+// CHECK:  Branch,File 0, 80:30 -> 80:31 = (#18 - #21), #21 [3,2,5]
+// CHECK:  Branch,File 0, 80:35 -> 80:36 = (#21 - #22), #22 [5,2,0]
+// CHECK:  Branch,File 0, 80:42 -> 80:43 = (#17 - #23), #23 [2,0,6]
+// CHECK:  Branch,File 0, 80:47 -> 80:48 = (#23 - #24), #24 [6,0,0]

clang/test/CoverageMapping/mcdc-logical-stmt-ids-all.cpp

+// RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only %s | FileCheck %s
+
+bool func_if_and(bool a, bool b, bool c, bool d, bool e, bool f) {
+  if (a && b && c && d && e && f)
+    return true;
+  return false;
+}
+
+// CHECK:  Decision,File 0, 4:7 -> 4:33 = M:0, C:6
+// CHECK:  Branch,File 0, 4:7 -> 4:8 = #10, (#0 - #10) [1,6,0]
+// CHECK:  Branch,File 0, 4:12 -> 4:13 = #11, (#10 - #11) [6,5,0]
+// CHECK:  Branch,File 0, 4:17 -> 4:18 = #9, (#8 - #9) [5,4,0]
+// CHECK:  Branch,File 0, 4:22 -> 4:23 = #7, (#6 - #7) [4,3,0]
+// CHECK:  Branch,File 0, 4:27 -> 4:28 = #5, (#4 - #5) [3,2,0]
+// CHECK:  Branch,File 0, 4:32 -> 4:33 = #3, (#2 - #3) [2,0,0]
+
+bool func_if_or(bool a, bool b, bool c, bool d, bool e, bool f) {
+  if (a || b || c || d || e || f)
+    return true;
+  return false;
+}
+
+// CHECK:  Decision,File 0, 18:7 -> 18:33 = M:0, C:6
+// CHECK:  Branch,File 0, 18:7 -> 18:8 = (#0 - #10), #10 [1,0,6]
+// CHECK:  Branch,File 0, 18:12 -> 18:13 = (#10 - #11), #11 [6,0,5]
+// CHECK:  Branch,File 0, 18:17 -> 18:18 = (#8 - #9), #9 [5,0,4]
+// CHECK:  Branch,File 0, 18:22 -> 18:23 = (#6 - #7), #7 [4,0,3]
+// CHECK:  Branch,File 0, 18:27 -> 18:28 = (#4 - #5), #5 [3,0,2]
+// CHECK:  Branch,File 0, 18:32 -> 18:33 = (#2 - #3), #3 [2,0,0]
+
+bool func_while_and(bool a, bool b, bool c, bool d, bool e, bool f) {
+  while (a && b && c && d && e && f) { return true; }
+  return false;
+}
+
+// CHECK:  Decision,File 0, 32:10 -> 32:36 = M:0, C:6
+// CHECK:  Branch,File 0, 32:10 -> 32:11 = #10, (#0 - #10) [1,6,0]
+// CHECK:  Branch,File 0, 32:15 -> 32:16 = #11, (#10 - #11) [6,5,0]
+// CHECK:  Branch,File 0, 32:20 -> 32:21 = #9, (#8 - #9) [5,4,0]
+// CHECK:  Branch,File 0, 32:25 -> 32:26 = #7, (#6 - #7) [4,3,0]
+// CHECK:  Branch,File 0, 32:30 -> 32:31 = #5, (#4 - #5) [3,2,0]
+// CHECK:  Branch,File 0, 32:35 -> 32:36 = #3, (#2 - #3) [2,0,0]
+
+bool func_while_or(bool a, bool b, bool c, bool d, bool e, bool f) {
+  while (a || b || c || d || e || f) { return true; }
+  return false;
+}
+
+// CHECK:  Decision,File 0, 45:10 -> 45:36 = M:0, C:6
+// CHECK:  Branch,File 0, 45:10 -> 45:11 = (#0 - #10), #10 [1,0,6]
+// CHECK:  Branch,File 0, 45:15 -> 45:16 = (#10 - #11), #11 [6,0,5]
+// CHECK:  Branch,File 0, 45:20 -> 45:21 = (#8 - #9), #9 [5,0,4]
+// CHECK:  Branch,File 0, 45:25 -> 45:26 = (#6 - #7), #7 [4,0,3]
+// CHECK:  Branch,File 0, 45:30 -> 45:31 = (#4 - #5), #5 [3,0,2]
+// CHECK:  Branch,File 0, 45:35 -> 45:36 = (#2 - #3), #3 [2,0,0]
+
+bool func_for_and(bool a, bool b, bool c, bool d, bool e, bool f) {
+  for (;a && b && c && d && e && f;) { return true; }
+  return false;
+}
+
+// CHECK:  Decision,File 0, 58:9 -> 58:35 = M:0, C:6
+// CHECK:  Branch,File 0, 58:9 -> 58:10 = #10, (#0 - #10) [1,6,0]
+// CHECK:  Branch,File 0, 58:14 -> 58:15 = #11, (#10 - #11) [6,5,0]
+// CHECK:  Branch,File 0, 58:19 -> 58:20 = #9, (#8 - #9) [5,4,0]
+// CHECK:  Branch,File 0, 58:24 -> 58:25 = #7, (#6 - #7) [4,3,0]
+// CHECK:  Branch,File 0, 58:29 -> 58:30 = #5, (#4 - #5) [3,2,0]
+// CHECK:  Branch,File 0, 58:34 -> 58:35 = #3, (#2 - #3) [2,0,0]
+
+bool func_for_or(bool a, bool b, bool c, bool d, bool e, bool f) {
+  for (;a || b || c || d || e || f;) { return true; }
+  return false;
+}
+
+// CHECK:  Decision,File 0, 71:9 -> 71:35 = M:0, C:6
+// CHECK:  Branch,File 0, 71:9 -> 71:10 = (#0 - #10), #10 [1,0,6]
+// CHECK:  Branch,File 0, 71:14 -> 71:15 = (#10 - #11), #11 [6,0,5]
+// CHECK:  Branch,File 0, 71:19 -> 71:20 = (#8 - #9), #9 [5,0,4]
+// CHECK:  Branch,File 0, 71:24 -> 71:25 = (#6 - #7), #7 [4,0,3]
+// CHECK:  Branch,File 0, 71:29 -> 71:30 = (#4 - #5), #5 [3,0,2]
+// CHECK:  Branch,File 0, 71:34 -> 71:35 = (#2 - #3), #3 [2,0,0]
+
+bool func_do_and(bool a, bool b, bool c, bool d, bool e, bool f) {
+  do {} while (a && b && c && d && e && f);
+  return false;
+}
+
+// CHECK:  Decision,File 0, 84:16 -> 84:42 = M:0, C:6
+// CHECK:  Branch,File 0, 84:16 -> 84:17 = #10, ((#0 + #1) - #10) [1,6,0]
+// CHECK:  Branch,File 0, 84:21 -> 84:22 = #11, (#10 - #11) [6,5,0]
+// CHECK:  Branch,File 0, 84:26 -> 84:27 = #9, (#8 - #9) [5,4,0]
+// CHECK:  Branch,File 0, 84:31 -> 84:32 = #7, (#6 - #7) [4,3,0]
+// CHECK:  Branch,File 0, 84:36 -> 84:37 = #5, (#4 - #5) [3,2,0]
+// CHECK:  Branch,File 0, 84:41 -> 84:42 = #3, (#2 - #3) [2,0,0]
+
+bool func_do_or(bool a, bool b, bool c, bool d, bool e, bool f) {
+  do {} while (a || b || c || d || e || f);
+  return false;
+}
+
+// CHECK:  Decision,File 0, 97:16 -> 97:42 = M:0, C:6
+// CHECK:  Branch,File 0, 97:16 -> 97:17 = ((#0 + #1) - #10), #10 [1,0,6]
+// CHECK:  Branch,File 0, 97:21 -> 97:22 = (#10 - #11), #11 [6,0,5]
+// CHECK:  Branch,File 0, 97:26 -> 97:27 = (#8 - #9), #9 [5,0,4]
+// CHECK:  Branch,File 0, 97:31 -> 97:32 = (#6 - #7), #7 [4,0,3]
+// CHECK:  Branch,File 0, 97:36 -> 97:37 = (#4 - #5), #5 [3,0,2]
+// CHECK:  Branch,File 0, 97:41 -> 97:42 = (#2 - #3), #3 [2,0,0]
+
+bool func_ternary_and(bool a, bool b, bool c, bool d, bool e, bool f) {
+  return (a && b && c && d && e && f) ? true : false;
+}
+
+// CHECK:  Decision,File 0, 110:11 -> 110:37 = M:0, C:6
+// CHECK:  Branch,File 0, 110:11 -> 110:12 = #10, (#0 - #10) [1,6,0]
+// CHECK:  Branch,File 0, 110:16 -> 110:17 = #11, (#10 - #11) [6,5,0]
+// CHECK:  Branch,File 0, 110:21 -> 110:22 = #9, (#8 - #9) [5,4,0]
+// CHECK:  Branch,File 0, 110:26 -> 110:27 = #7, (#6 - #7) [4,3,0]
+// CHECK:  Branch,File 0, 110:31 -> 110:32 = #5, (#4 - #5) [3,2,0]
+// CHECK:  Branch,File 0, 110:36 -> 110:37 = #3, (#2 - #3) [2,0,0]
+
+bool func_ternary_or(bool a, bool b, bool c, bool d, bool e, bool f) {
+  return (a || b || c || d || e || f) ? true : false;
+}
+
+// CHECK: Decision,File 0, 122:11 -> 122:37 = M:0, C:6
+// CHECK:  Branch,File 0, 122:11 -> 122:12 = (#0 - #10), #10 [1,0,6]
+// CHECK:  Branch,File 0, 122:16 -> 122:17 = (#10 - #11), #11 [6,0,5]
+// CHECK:  Branch,File 0, 122:21 -> 122:22 = (#8 - #9), #9 [5,0,4]
+// CHECK:  Branch,File 0, 122:26 -> 122:27 = (#6 - #7), #7 [4,0,3]
+// CHECK:  Branch,File 0, 122:31 -> 122:32 = (#4 - #5), #5 [3,0,2]
+// CHECK:  Branch,File 0, 122:36 -> 122:37 = (#2 - #3), #3 [2,0,0]

clang/test/CoverageMapping/mcdc-logical-stmt-ids.cpp

+// RUN: %clang_cc1 -triple %itanium_abi_triple -std=c++11 -fmcdc -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only %s | FileCheck %s
+
+bool func_if_and(bool a, bool b, bool c, bool d, bool e, bool f) {
+  if (a && b)
+    if (a && b && c)
+      if (a && b && c && d)
+        if (a && b && c && d && e)
+           if (a && b && c && d && e && f)
+              return true;
+  return false;
+}
+
+// CHECK:  Decision,File 0, 4:7 -> 4:13 = M:0, C:2
+// CHECK:  Branch,File 0, 4:7 -> 4:8 = #2, (#0 - #2) [1,2,0]
+// CHECK:  Branch,File 0, 4:12 -> 4:13 = #3, (#2 - #3) [2,0,0]
+// CHECK:  Decision,File 0, 5:9 -> 5:20 = M:1, C:3
+// CHECK:  Branch,File 0, 5:9 -> 5:10 = #7, (#1 - #7) [1,3,0]
+// CHECK:  Branch,File 0, 5:14 -> 5:15 = #8, (#7 - #8) [3,2,0]
+// CHECK:  Branch,File 0, 5:19 -> 5:20 = #6, (#5 - #6) [2,0,0]
+// CHECK:  Decision,File 0, 6:11 -> 6:27 = M:2, C:4
+// CHECK:  Branch,File 0, 6:11 -> 6:12 = #14, (#4 - #14) [1,4,0]
+// CHECK:  Branch,File 0, 6:16 -> 6:17 = #15, (#14 - #15) [4,3,0]
+// CHECK:  Branch,File 0, 6:21 -> 6:22 = #13, (#12 - #13) [3,2,0]
+// CHECK:  Branch,File 0, 6:26 -> 6:27 = #11, (#10 - #11) [2,0,0]
+// CHECK:  Decision,File 0, 7:13 -> 7:34 = M:4, C:5
+// CHECK:  Branch,File 0, 7:13 -> 7:14 = #23, (#9 - #23) [1,5,0]
+// CHECK:  Branch,File 0, 7:18 -> 7:19 = #24, (#23 - #24) [5,4,0]
+// CHECK:  Branch,File 0, 7:23 -> 7:24 = #22, (#21 - #22) [4,3,0]
+// CHECK:  Branch,File 0, 7:28 -> 7:29 = #20, (#19 - #20) [3,2,0]
+// CHECK:  Branch,File 0, 7:33 -> 7:34 = #18, (#17 - #18) [2,0,0]
+// CHECK:  Decision,File 0, 8:16 -> 8:42 = M:8, C:6
+// CHECK:  Branch,File 0, 8:16 -> 8:17 = #34, (#16 - #34) [1,6,0]
+// CHECK:  Branch,File 0, 8:21 -> 8:22 = #35, (#34 - #35) [6,5,0]
+// CHECK:  Branch,File 0, 8:26 -> 8:27 = #33, (#32 - #33) [5,4,0]
+// CHECK:  Branch,File 0, 8:31 -> 8:32 = #31, (#30 - #31) [4,3,0]
+// CHECK:  Branch,File 0, 8:36 -> 8:37 = #29, (#28 - #29) [3,2,0]
+// CHECK:  Branch,File 0, 8:41 -> 8:42 = #27, (#26 - #27) [2,0,0]
+
+bool func_if_or(bool a, bool b, bool c, bool d, bool e, bool f) {
+  if (a || b)
+    if (a || b || c)
+      if (a || b || c || d)
+        if (a || b || c || d || e)
+           if (a || b || c || d || e || f)
+              return true;
+  return false;
+}
+
+// CHECK:  Decision,File 0, 40:7 -> 40:13 = M:0, C:2
+// CHECK:  Branch,File 0, 40:7 -> 40:8 = (#0 - #2), #2 [1,0,2]
+// CHECK:  Branch,File 0, 40:12 -> 40:13 = (#2 - #3), #3 [2,0,0]
+// CHECK:  Decision,File 0, 41:9 -> 41:20 = M:1, C:3
+// CHECK:  Branch,File 0, 41:9 -> 41:10 = (#1 - #7), #7 [1,0,3]
+// CHECK:  Branch,File 0, 41:14 -> 41:15 = (#7 - #8), #8 [3,0,2]
+// CHECK:  Branch,File 0, 41:19 -> 41:20 = (#5 - #6), #6 [2,0,0]
+// CHECK:  Decision,File 0, 42:11 -> 42:27 = M:2, C:4
+// CHECK:  Branch,File 0, 42:11 -> 42:12 = (#4 - #14), #14 [1,0,4]
+// CHECK:  Branch,File 0, 42:16 -> 42:17 = (#14 - #15), #15 [4,0,3]
+// CHECK:  Branch,File 0, 42:21 -> 42:22 = (#12 - #13), #13 [3,0,2]
+// CHECK:  Branch,File 0, 42:26 -> 42:27 = (#10 - #11), #11 [2,0,0]
+// CHECK:  Decision,File 0, 43:13 -> 43:34 = M:4, C:5
+// CHECK:  Branch,File 0, 43:13 -> 43:14 = (#9 - #23), #23 [1,0,5]
+// CHECK:  Branch,File 0, 43:18 -> 43:19 = (#23 - #24), #24 [5,0,4]
+// CHECK:  Branch,File 0, 43:23 -> 43:24 = (#21 - #22), #22 [4,0,3]
+// CHECK:  Branch,File 0, 43:28 -> 43:29 = (#19 - #20), #20 [3,0,2]
+// CHECK:  Branch,File 0, 43:33 -> 43:34 = (#17 - #18), #18 [2,0,0]
+// CHECK:  Decision,File 0, 44:16 -> 44:42 = M:8, C:6
+// CHECK:  Branch,File 0, 44:16 -> 44:17 = (#16 - #34), #34 [1,0,6]
+// CHECK:  Branch,File 0, 44:21 -> 44:22 = (#34 - #35), #35 [6,0,5]
+// CHECK:  Branch,File 0, 44:26 -> 44:27 = (#32 - #33), #33 [5,0,4]
+// CHECK:  Branch,File 0, 44:31 -> 44:32 = (#30 - #31), #31 [4,0,3]
+// CHECK:  Branch,File 0, 44:36 -> 44:37 = (#28 - #29), #29 [3,0,2]
+// CHECK:  Branch,File 0, 44:41 -> 44:42 = (#26 - #27), #27 [2,0,0]
+
+bool func_if_mix(bool a, bool b, bool c, bool d, bool e, bool f) {
+  if (a || b)
+    if (a && (b || c))
+      if ((a || b) && (c || d))
+        if (a && (b || c) && (d || e))
+          if ((a || b) && (c || d) && (e || f))
+            return true;
+  return false;
+}
+
+// CHECK:  Decision,File 0, 76:7 -> 76:13 = M:0, C:2
+// CHECK:  Branch,File 0, 76:7 -> 76:8 = (#0 - #2), #2 [1,0,2]
+// CHECK:  Branch,File 0, 76:12 -> 76:13 = (#2 - #3), #3 [2,0,0]
+// CHECK:  Decision,File 0, 77:9 -> 77:22 = M:1, C:3
+// CHECK:  Branch,File 0, 77:9 -> 77:10 = #5, (#1 - #5) [1,2,0]
+// CHECK:  Branch,File 0, 77:15 -> 77:16 = (#5 - #6), #6 [2,0,3]
+// CHECK:  Branch,File 0, 77:20 -> 77:21 = (#6 - #7), #7 [3,0,0]
+// CHECK:  Decision,File 0, 78:11 -> 78:31 = M:2, C:4
+// CHECK:  Branch,File 0, 78:12 -> 78:13 = (#4 - #10), #10 [1,2,3]
+// CHECK:  Branch,File 0, 78:17 -> 78:18 = (#10 - #11), #11 [3,2,0]
+// CHECK:  Branch,File 0, 78:24 -> 78:25 = (#9 - #12), #12 [2,0,4]
+// CHECK:  Branch,File 0, 78:29 -> 78:30 = (#12 - #13), #13 [4,0,0]
+// CHECK:  Decision,File 0, 79:13 -> 79:38 = M:4, C:5
+// CHECK:  Branch,File 0, 79:13 -> 79:14 = #16, (#8 - #16) [1,3,0]
+// CHECK:  Branch,File 0, 79:19 -> 79:20 = (#16 - #17), #17 [3,2,4]
+// CHECK:  Branch,File 0, 79:24 -> 79:25 = (#17 - #18), #18 [4,2,0]
+// CHECK:  Branch,File 0, 79:31 -> 79:32 = (#15 - #19), #19 [2,0,5]
+// CHECK:  Branch,File 0, 79:36 -> 79:37 = (#19 - #20), #20 [5,0,0]
+// CHECK:  Decision,File 0, 80:15 -> 80:47 = M:8, C:6
+// CHECK:  Branch,File 0, 80:16 -> 80:17 = (#14 - #24), #24 [1,3,4]
+// CHECK:  Branch,File 0, 80:21 -> 80:22 = (#24 - #25), #25 [4,3,0]
+// CHECK:  Branch,File 0, 80:28 -> 80:29 = (#23 - #26), #26 [3,2,5]
+// CHECK:  Branch,File 0, 80:33 -> 80:34 = (#26 - #27), #27 [5,2,0]
+// CHECK:  Branch,File 0, 80:40 -> 80:41 = (#22 - #28), #28 [2,0,6]
+// CHECK:  Branch,File 0, 80:45 -> 80:46 = (#28 - #29), #29 [6,0,0]
+

clang/test/Driver/darwin-ld.c

 // LINK_VERSION_DIGITS: invalid version number in '-mlinker-version=133.3.0.1.2.6'
 // LINK_VERSION_DIGITS: invalid version number in '-mlinker-version=133.3.0.1.a'
 // LINK_VERSION_DIGITS: invalid version number in '-mlinker-version=133.3.0.1a'
 
 // RUN: %clang -target x86_64-apple-darwin12 -fprofile-instr-generate -### %t.o 2> %t.log
 // RUN: FileCheck -check-prefix=PROFILE_SECTALIGN %s < %t.log
 // RUN: %clang -target arm64-apple-ios12 -fprofile-instr-generate -### %t.o 2> %t.log
 // RUN: FileCheck -check-prefix=PROFILE_SECTALIGN %s < %t.log
-// PROFILE_SECTALIGN: "-sectalign" "__DATA" "__llvm_prf_cnts" "0x4000" "-sectalign" "__DATA" "__llvm_prf_data" "0x4000"
+// PROFILE_SECTALIGN: "-sectalign" "__DATA" "__llvm_prf_cnts" "0x4000" "-sectalign" "__DATA" "__llvm_prf_bits" "0x4000" "-sectalign" "__DATA" "__llvm_prf_data" "0x4000"
 
 // RUN: %clang -target x86_64-apple-darwin12 -fprofile-instr-generate --coverage -### %t.o 2> %t.log
 // RUN: FileCheck -check-prefix=NO_PROFILE_EXPORT %s < %t.log
 // NO_PROFILE_EXPORT-NOT: "-exported_symbol"
 //
 // RUN: %clang -target x86_64-apple-darwin12 --coverage -exported_symbols_list /dev/null -### %t.o 2> %t.log
 // RUN: FileCheck -check-prefix=GCOV_EXPORT %s < %t.log
 // RUN: %clang -target x86_64-apple-darwin12 -fprofile-arcs -Wl,-exported_symbols_list,/dev/null -### %t.o 2> %t.log

clang/test/Profile/c-linkage-available_externally.c

 // Make sure instrumentation data from available_externally functions doesn't
 // get thrown out and are emitted with the expected linkage.
 // RUN: %clang_cc1 -no-opaque-pointers -O2 -triple x86_64-apple-macosx10.9 -main-file-name c-linkage-available_externally.c %s -o - -emit-llvm -fprofile-instrument=clang | FileCheck %s
+// RUN: %clang_cc1 -fmcdc -no-opaque-pointers -O2 -triple x86_64-apple-macosx10.9 -main-file-name c-linkage-available_externally.c %s -o - -emit-llvm -fprofile-instrument=clang | FileCheck %s -check-prefix=MCDC
 
 // CHECK: @__profc_foo = linkonce_odr hidden global [1 x i64] zeroinitializer, section "__DATA,__llvm_prf_cnts", align 8
+// MCDC: @__profbm_foo = linkonce_odr hidden global [0 x i8] zeroinitializer, section "__DATA,__llvm_prf_bits", align 1
 // CHECK: @__profd_foo = linkonce_odr hidden global {{.*}} i64 sub (i64 ptrtoint ([1 x i64]* @__profc_foo to i64), i64 ptrtoint ({ i64, i64, i64, i64, i8*, i8*, i32, [2 x i16], i32 }* @__profd_foo to i64)), {{.*}}, section "__DATA,__llvm_prf_data,regular,live_support", align 8
 inline int foo(void) { return 1; }
 
 int main(void) {
   return foo();
 }

clang/test/Profile/c-mcdc-nested-ternary.c

+// RUN: %clang_cc1 -triple %itanium_abi_triple %s -o - -emit-llvm -fprofile-instrument=clang -fcoverage-mapping -fmcdc | FileCheck %s -check-prefix=MCDC
+// RUN: %clang_cc1 -triple %itanium_abi_triple %s -o - -emit-llvm -fprofile-instrument=clang -fcoverage-mapping | FileCheck %s -check-prefix=NOMCDC
+
+int test(int b, int c, int d, int e, int f) {
+  return ((b ? c : d) && e && f);
+}
+
+// NOMCDC-NOT: %mcdc.addr
+// NOMCDC-NOT: __profbm_test
+
+// MCDC BOOKKEEPING.
+// MCDC: @__profbm_test = private global [1 x i8] zeroinitializer
+
+// ALLOCATE MCDC TEMP AND ZERO IT.
+// MCDC-LABEL: @test(
+// MCDC: %mcdc.addr = alloca i32, align 4
+// MCDC: store i32 0, ptr %mcdc.addr, align 4
+
+// TERNARY TRUE SHOULD SHIFT ID = 0 FOR CONDITION 'c'.
+// MCDC-LABEL: cond.true:
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %c.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 0
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// TERNARY FALSE SHOULD SHIFT ID = 0 FOR CONDITION 'd'.
+// MCDC-LABEL: cond.false:
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %d.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 0
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT SECOND CONDITION WITH ID = 2.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %e.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 2
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT THIRD CONDITION WITH ID = 1.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %f.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 1
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// UPDATE FINAL BITMASK WITH RESULT.
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC:  %[[LAB1:[0-9]+]] = lshr i32 %[[TEMP]], 3
+// MCDC:  %[[LAB2:[0-9]+]] = zext i32 %[[LAB1]] to i64
+// MCDC:  %[[LAB3:[0-9]+]] = add i64 ptrtoint (ptr @__profbm_test to i64), %[[LAB2]]
+// MCDC:  %[[LAB4:[0-9]+]] = inttoptr i64 %[[LAB3]] to ptr
+// MCDC:  %[[LAB5:[0-9]+]] = and i32 %[[TEMP]], 7
+// MCDC:  %[[LAB6:[0-9]+]] = trunc i32 %[[LAB5]] to i8
+// MCDC:  %[[LAB7:[0-9]+]] = shl i8 1, %[[LAB6]]
+// MCDC:  %mcdc.bits = load i8, ptr %[[LAB4]], align 1
+// MCDC:  %[[LAB8:[0-9]+]] = or i8 %mcdc.bits, %[[LAB7]]
+// MCDC:  store i8 %[[LAB8]], ptr %[[LAB4]], align 1

clang/test/Profile/c-mcdc-not.c

+// RUN: %clang_cc1 -triple %itanium_abi_triple %s -o - -emit-llvm -fprofile-instrument=clang -fcoverage-mapping -fmcdc | FileCheck %s -check-prefix=MCDC
+// RUN: %clang_cc1 -triple %itanium_abi_triple %s -o - -emit-llvm -fprofile-instrument=clang -fcoverage-mapping | FileCheck %s -check-prefix=NOMCDC
+
+int test(int a, int b, int c, int d, int e, int f) {
+  return ((!a && b) || ((!c && d) || (e && !f)));
+}
+
+// NOMCDC-NOT: %mcdc.addr
+// NOMCDC-NOT: __profbm_test
+
+// MCDC BOOKKEEPING.
+// MCDC: @__profbm_test = private global [8 x i8] zeroinitializer
+// MCDC: @__profc_test = private global [9 x i64] zeroinitializer
+
+// ALLOCATE MCDC TEMP AND ZERO IT.
+// MCDC-LABEL: @test(
+// MCDC: %mcdc.addr = alloca i32, align 4
+// MCDC: store i32 0, ptr %mcdc.addr, align 4
+
+// SHIFT FIRST CONDITION WITH ID = 0.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %a.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[LNOT:lnot[0-9]*]] = xor i1 %[[BOOL]]
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[LNOT]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 0
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT SECOND CONDITION WITH ID = 2.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %b.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 2
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT THIRD CONDITION WITH ID = 1.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %c.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[LNOT:lnot[0-9]*]] = xor i1 %[[BOOL]]
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[LNOT]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 1
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT FOURTH CONDITION WITH ID = 4.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %d.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 4
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT FIFTH CONDITION WITH ID = 3.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %e.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 3
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT SIXTH CONDITION WITH ID = 5.
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %f.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[LNOT:lnot[0-9]*]] = xor i1 %[[BOOL]]
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[LNOT]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 5
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// UPDATE FINAL BITMASK WITH RESULT.
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC:  %[[LAB1:[0-9]+]] = lshr i32 %[[TEMP]], 3
+// MCDC:  %[[LAB2:[0-9]+]] = zext i32 %[[LAB1]] to i64
+// MCDC:  %[[LAB3:[0-9]+]] = add i64 ptrtoint (ptr @__profbm_test to i64), %[[LAB2]]
+// MCDC:  %[[LAB4:[0-9]+]] = inttoptr i64 %[[LAB3]] to ptr
+// MCDC:  %[[LAB5:[0-9]+]] = and i32 %[[TEMP]], 7
+// MCDC:  %[[LAB6:[0-9]+]] = trunc i32 %[[LAB5]] to i8
+// MCDC:  %[[LAB7:[0-9]+]] = shl i8 1, %[[LAB6]]
+// MCDC:  %mcdc.bits = load i8, ptr %[[LAB4]], align 1
+// MCDC:  %[[LAB8:[0-9]+]] = or i8 %mcdc.bits, %[[LAB7]]
+// MCDC:  store i8 %[[LAB8]], ptr %[[LAB4]], align 1

clang/test/Profile/c-mcdc.c

+// RUN: %clang_cc1 -triple %itanium_abi_triple %s -o - -emit-llvm -fprofile-instrument=clang -fcoverage-mapping -fmcdc | FileCheck %s -check-prefix=MCDC
+// RUN: %clang_cc1 -triple %itanium_abi_triple %s -o - -emit-llvm -fprofile-instrument=clang -fcoverage-mapping | FileCheck %s -check-prefix=NOMCDC
+// RUN: %clang_cc1 -triple %itanium_abi_triple %s -o - -emit-llvm -fprofile-instrument=clang -fcoverage-mapping -fmcdc -disable-llvm-passes | FileCheck %s -check-prefix=NOPROFPASS
+
+int test(int a, int b, int c, int d, int e, int f) {
+  return ((a && b) || ((c && d) || (e && f)));
+}
+
+// NOMCDC-NOT: %mcdc.addr
+// NOMCDC-NOT: __profbm_test
+// NOPROFPASS-NOT: __profbm_test
+
+// MCDC BOOKKEEPING.
+// MCDC: @__profbm_test = private global [8 x i8] zeroinitializer
+// MCDC: @__profc_test = private global [9 x i64] zeroinitializer
+
+// ALLOCATE MCDC TEMP AND ZERO IT.
+// NOPROFPASS-LABEL: @test(
+// NOPROFPASS: call void @llvm.instrprof.mcdc.parameters(ptr @__profn_test, i64 [[HASH:[0-9]+]], i32 8)
+// MCDC-LABEL: @test(
+// MCDC: %mcdc.addr = alloca i32, align 4
+// MCDC: store i32 0, ptr %mcdc.addr, align 4
+
+// SHIFT FIRST CONDITION WITH ID = 0.
+// NOPROFPASS: call void @llvm.instrprof.mcdc.condbitmap.update(ptr @__profn_test, i64 [[HASH]], i32 0, ptr %mcdc.addr, i1 %tobool{{[0-9]*}})
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %a.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 0
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT SECOND CONDITION WITH ID = 2.
+// NOPROFPASS-LABEL: land.lhs.true:
+// NOPROFPASS: call void @llvm.instrprof.mcdc.condbitmap.update(ptr @__profn_test, i64 [[HASH]], i32 2, ptr %mcdc.addr, i1 %tobool{{[0-9]*}})
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %b.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 2
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT THIRD CONDITION WITH ID = 1.
+// NOPROFPASS-LABEL: lor.rhs:
+// NOPROFPASS: call void @llvm.instrprof.mcdc.condbitmap.update(ptr @__profn_test, i64 [[HASH]], i32 1, ptr %mcdc.addr, i1 %tobool{{[0-9]*}})
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %c.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 1
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT FOURTH CONDITION WITH ID = 4.
+// NOPROFPASS-LABEL: land.lhs.true3:
+// NOPROFPASS: call void @llvm.instrprof.mcdc.condbitmap.update(ptr @__profn_test, i64 [[HASH]], i32 4, ptr %mcdc.addr, i1 %tobool{{[0-9]*}})
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %d.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 4
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT FIFTH CONDITION WITH ID = 3.
+// NOPROFPASS-LABEL: lor.rhs6:
+// NOPROFPASS: call void @llvm.instrprof.mcdc.condbitmap.update(ptr @__profn_test, i64 [[HASH]], i32 3, ptr %mcdc.addr, i1 %tobool{{[0-9]*}})
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %e.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 3
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// SHIFT SIXTH CONDITION WITH ID = 5.
+// NOPROFPASS-LABEL: land.rhs:
+// NOPROFPASS: call void @llvm.instrprof.mcdc.condbitmap.update(ptr @__profn_test, i64 [[HASH]], i32 5, ptr %mcdc.addr, i1 %tobool{{[0-9]*}})
+// MCDC:  %[[LAB1:[0-9]+]] = load i32, ptr %f.addr, align 4
+// MCDC-DAG:  %[[BOOL:tobool[0-9]*]] = icmp ne i32 %[[LAB1]], 0
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC-DAG:  %[[LAB2:[0-9]+]] = zext i1 %[[BOOL]] to i32
+// MCDC-DAG:  %[[LAB3:[0-9]+]] = shl i32 %[[LAB2]], 5
+// MCDC-DAG:  %[[LAB4:[0-9]+]] = or i32 %[[TEMP]], %[[LAB3]]
+// MCDC-DAG:  store i32 %[[LAB4]], ptr %mcdc.addr, align 4
+
+// UPDATE FINAL BITMASK WITH RESULT.
+// NOPROFPASS-LABEL: lor.end:
+// NOPROFPASS: call void @llvm.instrprof.mcdc.tvbitmap.update(ptr @__profn_test, i64 [[HASH]], i32 8, i32 0, ptr %mcdc.addr)
+// MCDC-DAG:  %[[TEMP:mcdc.temp[0-9]*]] = load i32, ptr %mcdc.addr, align 4
+// MCDC:  %[[LAB1:[0-9]+]] = lshr i32 %[[TEMP]], 3
+// MCDC:  %[[LAB2:[0-9]+]] = zext i32 %[[LAB1]] to i64
+// MCDC:  %[[LAB3:[0-9]+]] = add i64 ptrtoint (ptr @__profbm_test to i64), %[[LAB2]]
+// MCDC:  %[[LAB4:[0-9]+]] = inttoptr i64 %[[LAB3]] to ptr
+// MCDC:  %[[LAB5:[0-9]+]] = and i32 %[[TEMP]], 7
+// MCDC:  %[[LAB6:[0-9]+]] = trunc i32 %[[LAB5]] to i8
+// MCDC:  %[[LAB7:[0-9]+]] = shl i8 1, %[[LAB6]]
+// MCDC:  %mcdc.bits = load i8, ptr %[[LAB4]], align 1
+// MCDC:  %[[LAB8:[0-9]+]] = or i8 %mcdc.bits, %[[LAB7]]
+// MCDC:  store i8 %[[LAB8]], ptr %[[LAB4]], align 1

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

+// REQUIRES: darwin
+
+// RUN: %clang_profgen -fcoverage-mapping -fmcdc -O3 -o %t.exe %s
+// RUN: env LLVM_PROFILE_FILE="%c%t.profraw" %run %t.exe 3 3
+// RUN: llvm-profdata show --text --all-functions %t.profraw | FileCheck %s
+
+// CHECK: Num Bitmap Bytes:
+// CHECK-NEXT: $1
+// CHECK-NEXT: Bitmap Byte Values:
+// CHECK-NEXT: 8
+#include <stdlib.h>
+#include <stdio.h>
+extern int __llvm_profile_is_continuous_mode_enabled(void);
+int main(int argc, char *const argv[]) {
+  if (!__llvm_profile_is_continuous_mode_enabled())
+    return 1;
+
+  if (argc < 3)
+    return 1;
+
+  if ((atoi(argv[1]) > 2) && (atoi(argv[2]) > 2)) {
+    printf("Decision Satisfied");
+  }
+
+  return 0;
+}