Malformed MC/DC Coverage record with macro definitions

[chapuni]

Clang -fcoverage-mcdc emits malformed records to crash llvm-cov with assert(NumConds == 0); if:

1. At least two decisions (passes with one decision)
2. Each expression has terms that come from macro definitions

Reproducible code (https://godbolt.org/z/xMGPafdvG)

#define D 1

extern void bar(void);

void foo(int a, int b) {
  if (a && D) bar();
  if (b && D) bar();
}

Unexpected Branch order will be seen.

  Decision,File 0, 6:7 -> 6:13 = M:0, C:2
  Branch,File 0, 6:7 -> 6:8 = #2, (#0 - #2) [1,2,0] 
  Expansion,File 0, 6:12 -> 6:13 = #2 (Expanded file = 1)
...
  Decision,File 0, 7:7 -> 7:13 = M:1, C:2
  Branch,File 0, 7:7 -> 7:8 = #5, (#0 - #5) [1,2,0] 
  Expansion,File 0, 7:12 -> 7:13 = #5 (Expanded file = 2)
...
  Branch,File 1, 1:11 -> 1:12 = 0, 0 [2,0,0] 
...
  Branch,File 2, 1:11 -> 1:12 = 0, 0 [2,0,0] 

("Decision, branch, branch, decision, branch, branch" is expected)

[chapuni]

I think an easy workaround is to replace StartLoc for MC/DC branches and decisions (ID > 0).

[evodius96]

I've got a fix for this; just testing it a bit more. I should have the PR hopefully tomorrow.

[MaskRay]

To summarize the problem:
-fcoverage-mcdc instrumentation emits Decision/Branch records.
The current llvm-cov implementation assumes that a MCDCDecisionRegion is followed by all its MCDCBranchRegion before another MCDCDecisionRegion is seen (assert(NumConds == 0)).
This breaks when a MCDCBranchRegion is inside a macro expansion (due to stable_sort mentioned later).

#78819 tries to scan forward to collect all MCDCBranchRegion for a MCDCDecisionRegion. The native implementation has an exponential time complexity.

#78969 tries to scan backward to find the associated MCDCDecisionRegion for a MCDCBranchRegion. The theoretical time complexity is quadratic, but it should be like linear in practice because logical operators in macros are presumably few.

I agree that #78969 is preferred.

Note: if we can avoid stable_sort in llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp and ensure that MCDCBranchRegion always immediately MCDCDecisionRegion, and change https://llvm.org/docs/CoverageMappingFormat.html#file-id-mapping not require the same FileID, the current llvm-cov implementation can be used again. But this may require require some code from the writer side.

[chapuni]

Yet another interesting case (https://godbolt.org/z/hzeqoGcd8)

// The issue by RecursiveASTVisitor::TraverseParmVarDecl

#define BODY(code) { code; }

bool foo(int c) {
    BODY({
        if (c == '.' || c == '/') return true;
        if ('0' <= c && c <= '9') return true;
    });
    return false;
}

_Z3fooi:
  File 0, 5:17 -> 11:2 = #0
  Expansion,File 0, 6:5 -> 6:9 = #0 (Expanded file = 1)
  File 0, 6:9 -> 10:17 = ((#0 - #1) - #4)
  File 0, 6:9 -> 11:2 = (#0 - #1)
  File 1, 3:20 -> 3:29 = #0
  File 1, 3:22 -> 3:26 = #0
  File 1, 3:22 -> 3:26 = #2
  File 1, 3:22 -> 3:26 = #0
  File 1, 3:22 -> 3:26 = #1
  File 1, 3:22 -> 3:26 = (#0 - #1)
  File 1, 3:22 -> 3:26 = #5
  File 1, 3:22 -> 3:26 = (#0 - #1)
  File 1, 3:22 -> 3:26 = #4
  File 1, 3:22 -> 3:29 = (#0 - #1)
  Decision,File 1, 3:22 -> 3:26 = M:0, C:2
  Decision,File 1, 3:22 -> 3:26 = M:1, C:2
  Branch,File 1, 3:22 -> 3:26 = (#0 - #2), #2 [1,0,2] 
  Branch,File 1, 3:22 -> 3:26 = (#2 - #3), #3 [2,0,0] 
  Branch,File 1, 3:22 -> 3:26 = #5, ((#0 - #1) - #5) [1,2,0] 
  Branch,File 1, 3:22 -> 3:26 = #6, (#5 - #6) [2,0,0] 
  File 1, 3:26 -> 3:29 = ((#0 - #1) - #4)

[chapuni]

/cherry-pick 438fe1d d912f1f

[llvmbot]

/pull-request #80513

[tstellar]

The PR has been created so we will track status there.