[llvm-cov][MC/DC] "Branch not found in Decisions" when handling complicated macros #87000

whentojump · 2024-03-28T20:07:05Z

Example file perfmon.c (It currently looks tedious and should be able to be further minimized, I'll work on that)

// A example simplified from https://elixir.bootlin.com/linux/v6.8.1/source/drivers/iommu/intel/perfmon.c
// Reproducible with clang version 18.1.3 (git@github.com:llvm/llvm-project.git
// 2498e3a07f3df2272fec885f53f09ae13214ca38) and Ubuntu clang version 18.1.3
// (++20240322073153+ef6d1ec07c69-1~exp1~20240322193300.86).
//
// Note that assertions *might* have to be enabled, therefore prebuilt packages
// from apt.llvm.org etc *might* not behave the same. E.g. as of Mar 28,
// llvm-cov-18 from apt.llvm.org ends up with "Segmentation fault", llvm-cov-19
// doesn't fail at least explicitly. On the other hand, if we build LLVM from
// source and enable assertion, we can observe explicit "UNREACHABLE executed"
// messages.
//
// Steps:
//
//   $ rm -rf a.out *.profraw *.profdata
//   $ clang -Wno-c23-extensions -fprofile-instr-generate -fcoverage-mapping -fcoverage-mcdc perfmon.c
//   $ ./a.out
//   $ llvm-profdata merge default.profraw -o default.profdata
//   $ llvm-cov show --show-mcdc -instr-profile default.profdata a.out
//

// Dummy definitions to make this file compile.
// (Some of them are also kernel code but incomplete or modified)

struct attr {
	long config1;
	long config2;
};

struct hw_perf_event {
	long idx;
	long config;
};

struct perf_event {
	struct hw_perf_event hw;
	struct attr attr;
};

struct iommu_pmu {
	long filter;
	long cfg_reg;
	struct perf_event *event_list[100];
	long num_cntr;
	long used_mask;
};

long test_and_set_bit(long, long) { return 0; }
long iommu_pmu_validate_per_cntr_event(struct iommu_pmu *, long, struct perf_event *) { return 1; }
void clear_bit(long, long) {}
void writeq(long, long) {}
void writel(long, long) {}
long iommu_config_base(struct iommu_pmu *, long) { return 0; }
long variable_ffs(long) { return 1; }

#define UL(X) X##UL

// Actually copied from kernel source

#define BIT(nr)			(UL(1) << (nr))

#define ffs(x) (__builtin_constant_p(x) ? __builtin_ffs(x) : variable_ffs(x))

#define dmar_readq(a) readq(a)
#define dmar_writeq(a,v) writeq(v,a)
#define dmar_readl(a) readl(a)
#define dmar_writel(a, v) writel(v, a)

#define iommu_pmu_en_requester_id(e)		((e) & 0x1)
#define iommu_pmu_en_domain(e)			(((e) >> 1) & 0x1)
#define iommu_pmu_en_pasid(e)			(((e) >> 2) & 0x1)
#define iommu_pmu_en_ats(e)			(((e) >> 3) & 0x1)
#define iommu_pmu_en_page_table(e)		(((e) >> 4) & 0x1)
#define iommu_pmu_get_requester_id(filter)	(((filter) >> 16) & 0xffff)
#define iommu_pmu_get_domain(filter)		(((filter) >> 32) & 0xffff)
#define iommu_pmu_get_pasid(filter)		((filter) & 0x3fffff)
#define iommu_pmu_get_ats(filter)		(((filter) >> 24) & 0x1f)
#define iommu_pmu_get_page_table(filter)	(((filter) >> 32) & 0x1f)

#define IOMMU_PMU_NUM_OFF_REGS			4
#define IOMMU_PMU_OFF_REGS_STEP			4

#define IOMMU_PMU_FILTER_REQUESTER_ID		0x01
#define IOMMU_PMU_FILTER_DOMAIN			0x02
#define IOMMU_PMU_FILTER_PASID			0x04
#define IOMMU_PMU_FILTER_ATS			0x08
#define IOMMU_PMU_FILTER_PAGE_TABLE		0x10

#define IOMMU_PMU_FILTER_EN			BIT(31)

#define IOMMU_PMU_CFG_OFFSET			0x100
#define IOMMU_PMU_CFG_CNTRCAP_OFFSET		0x80
#define IOMMU_PMU_CFG_CNTREVCAP_OFFSET		0x84
#define IOMMU_PMU_CFG_SIZE			0x8
#define IOMMU_PMU_CFG_FILTERS_OFFSET		0x4

#define IOMMU_PMU_CAP_REGS_STEP			8

#define iommu_pmu_set_filter(_name, _config, _filter, _idx, _econfig)		\
{										\
	if ((iommu_pmu->filter & _filter) && iommu_pmu_en_##_name(_econfig)) {	\
		dmar_writel(iommu_pmu->cfg_reg + _idx * IOMMU_PMU_CFG_OFFSET +	\
			    IOMMU_PMU_CFG_SIZE +				\
			    (ffs(_filter) - 1) * IOMMU_PMU_CFG_FILTERS_OFFSET,	\
			    iommu_pmu_get_##_name(_config) | IOMMU_PMU_FILTER_EN);\
	}									\
}

// Part of https://elixir.bootlin.com/linux/v6.8.1/source/drivers/iommu/intel/perfmon.c#L408

static int iommu_pmu_assign_event(struct iommu_pmu *iommu_pmu,
				  struct perf_event *event)
{
	int idx;

	iommu_pmu_set_filter(requester_id, event->attr.config1,
			     IOMMU_PMU_FILTER_REQUESTER_ID, idx,
			     event->attr.config1);
	// iommu_pmu_set_filter(domain, event->attr.config1,
	// 		     IOMMU_PMU_FILTER_DOMAIN, idx,
	// 		     event->attr.config1);

	return 0;
}

// Dummy main

int main(void) {
	struct iommu_pmu iommu_pmu;
	struct perf_event event;
	iommu_pmu_assign_event(&iommu_pmu, &event);
	return 0;
}

Steps to reproduce:

rm -rf a.out *.profraw *.profdata
clang -Wno-c23-extensions -fprofile-instr-generate -fcoverage-mapping -fcoverage-mcdc perfmon.c
./a.out
llvm-profdata merge default.profraw -o default.profdata
# Crash
llvm-cov show --show-mcdc -instr-profile default.profdata a.out

Message:

Branch not found in Decisions
UNREACHABLE executed at /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp:784!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: llvm-cov "llvm-cov show" --show-mcdc -instr-profile default.profdata a.out
 #0 0x000055cfdb4bf61f llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/Support/Unix/Signals.inc:727:3
 #1 0x000055cfdb4bd30f llvm::sys::RunSignalHandlers() /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/Support/Signals.cpp:105:20
 #2 0x000055cfdb4bd666 SignalHandler(int) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/Support/Unix/Signals.inc:413:1
 #3 0x00007f0aefc5e520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #4 0x00007f0aefcb29fc __pthread_kill_implementation ./nptl/pthread_kill.c:44:76
 #5 0x00007f0aefcb29fc __pthread_kill_internal ./nptl/pthread_kill.c:78:10
 #6 0x00007f0aefcb29fc pthread_kill ./nptl/pthread_kill.c:89:10
 #7 0x00007f0aefc5e476 gsignal ./signal/../sysdeps/posix/raise.c:27:6
 #8 0x00007f0aefc447f3 abort ./stdlib/abort.c:81:7
 #9 0x000055cfdb46736e (/users/wtj/have-been/llvm-project/build/bin/llvm-cov+0x45436e)
#10 0x000055cfdb55527f (anonymous namespace)::MCDCDecisionRecorder::processBranch(llvm::coverage::CounterMappingRegion const&) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp:784:5
#11 0x000055cfdb55b030 llvm::coverage::CoverageMapping::loadFunctionRecord(llvm::coverage::CoverageMappingRecord const&, llvm::IndexedInstrProfReader&) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp:879:5
#12 0x000055cfdb55c260 llvm::Error::setChecked(bool) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/include/llvm/Support/Error.h:307:22
#13 0x000055cfdb55c260 llvm::Error::operator bool() /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/include/llvm/Support/Error.h:239:15
#14 0x000055cfdb55c260 llvm::coverage::CoverageMapping::loadFromReaders(llvm::ArrayRef<std::unique_ptr<llvm::coverage::CoverageMappingReader, std::default_delete<llvm::coverage::CoverageMappingReader>>>, llvm::IndexedInstrProfReader&, llvm::coverage::CoverageMapping&) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp:933:71
#15 0x000055cfdb55c8b9 llvm::Error::setChecked(bool) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/include/llvm/Support/Error.h:307:22
#16 0x000055cfdb55c8b9 llvm::Error::operator bool() /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/include/llvm/Support/Error.h:239:15
#17 0x000055cfdb55c8b9 llvm::coverage::CoverageMapping::loadFromFile(llvm::StringRef, llvm::StringRef, llvm::StringRef, llvm::IndexedInstrProfReader&, llvm::coverage::CoverageMapping&, bool&, llvm::SmallVectorImpl<llvm::SmallVector<unsigned char, 10u>>*) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp:992:66
#18 0x000055cfdb55d35a llvm::Error::setChecked(bool) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/include/llvm/Support/Error.h:307:22
#19 0x000055cfdb55d35a llvm::Error::operator bool() /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/include/llvm/Support/Error.h:239:15
#20 0x000055cfdb55d35a llvm::coverage::CoverageMapping::load(llvm::ArrayRef<llvm::StringRef>, llvm::StringRef, llvm::vfs::FileSystem&, llvm::ArrayRef<llvm::StringRef>, llvm::StringRef, llvm::object::BuildIDFetcher const*, bool) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp:1020:80
#21 0x000055cfdb2ad4c2 llvm::Expected<std::unique_ptr<llvm::coverage::CoverageMapping, std::default_delete<llvm::coverage::CoverageMapping>>>::takeError() /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/include/llvm/Support/Error.h:603:15
#22 0x000055cfdb2ad4c2 (anonymous namespace)::CodeCoverageTool::load() /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/tools/llvm-cov/CodeCoverage.cpp:486:41
#23 0x000055cfdb2b118f (anonymous namespace)::CodeCoverageTool::doShow(int, char const**, llvm::function_ref<int (int, char const**)>) (.constprop.0) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/tools/llvm-cov/CodeCoverage.cpp:1143:3
#24 0x000055cfdb2b6d58 (anonymous namespace)::CodeCoverageTool::run((anonymous namespace)::CodeCoverageTool::Command, int, char const**) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/tools/llvm-cov/CodeCoverage.cpp:980:18
#25 0x000055cfdb2b764f showMain(int, char const**) /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/tools/llvm-cov/CodeCoverage.cpp:1348:1
#26 0x000055cfdb29908d std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::~basic_string() /usr/include/c++/11/bits/basic_string.h:672:19
#27 0x000055cfdb29908d main /users/wtj/have-been/enhanced-gcov/llvm-mcdc/llvm/llvm/tools/llvm-cov/llvm-cov.cpp:82:5
#28 0x00007f0aefc45d90 __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#29 0x00007f0aefc45e40 call_init ./csu/../csu/libc-start.c:128:20
#30 0x00007f0aefc45e40 __libc_start_main ./csu/../csu/libc-start.c:379:5
#31 0x000055cfdb298625 _start (/users/wtj/have-been/llvm-project/build/bin/llvm-cov+0x285625)
Aborted

It somewhat looks like #77871 and perhaps has something to do with region ordering.

cc @chapuni @evodius96

The text was updated successfully, but these errors were encountered:

whentojump · 2024-03-28T21:02:52Z

Also reproduced on compiler explorer: link

chapuni · 2024-03-28T22:36:09Z

It's a Clang's bug in synthesizing an identifier with ## in macro, aka <scratch space>.
Reproducible in clang-18.

A tweaked testcase with avoiding ## https://godbolt.org/z/qPTEh4c8n
An expansion disappeared there.

The reduced testcase: https://godbolt.org/z/sMscqWeq7

#if 0
#define FOO(x) x
#else
#define FOO(x) foo_##x
#endif

int foo(int a, int b, int foo_b) {
  return (a && FOO(b));
}

The wrong case (#if 0):
Cond[2,0,0] disappears.

foo:
  File 0, 7:34 -> 9:2 = #0
  File 0, 8:11 -> 8:12 = #0
  Decision,File 0, 8:11 -> 8:19 = M:0, C:2
  Branch,File 0, 8:11 -> 8:12 = #1, (#0 - #1) [1,2,0] 
  Expansion,File 0, 8:16 -> 8:19 = 0 (Expanded file = 1)
  File 1, 4:16 -> 4:20 = 0

Should be (#if 1)

foo:
  File 0, 7:34 -> 9:2 = #0
  File 0, 8:11 -> 8:12 = #0
  Decision,File 0, 8:11 -> 8:19 = M:0, C:2
  Branch,File 0, 8:11 -> 8:12 = #1, (#0 - #1) [1,2,0] 
  Expansion,File 0, 8:16 -> 8:19 = #1 (Expanded file = 1)
  File 1, 2:16 -> 2:17 = #1
  Branch,File 1, 2:16 -> 2:17 = #2, (#1 - #2) [2,0,0]

whentojump · 2024-03-29T01:51:20Z

Thanks for reducing the example! Great insight!

whentojump · 2024-04-22T03:41:24Z

@chapuni Thanks again for your input! I'll prepare a patch for it.

May I ask how did you get this reduced program? Do you use some automatic tools like creduce? Or you experienced with similar problems and had a hunch? Just curious :))

A synthesized identifier with `##` is emitted to `<scratch space>`. `llvm-cov` cannot handle `<scratch space> since it doesn't have actual files. As a workaround, peel `<scratch space>` to the actual definition if the definition is present. This affects predefined built-in macros, like __LINE__. Fixes llvm#87000

`emitSourceRegions()` has bugs to emit malformed MC/DC coverage mappings. They were detected in `llvm-cov` as the crash. Detect inconsistencies earlier in `clang` with assertions. * mcdc-system-headers.cpp covers llvm#78920. * mcdc-scratch-space.c covers llvm#87000.

chapuni · 2024-04-22T06:44:01Z

I've created #89573 as the fix.

chapuni · 2024-04-22T06:56:17Z

@whentojump Sorry, I haven't noticed your reply while I was working.
Please give your comments in #89573 , or push your changes if you knew better resolution.

I have been aware of it for a while but I forgot to file since I was too lazy.
I can find it since I am working for improving mcdc.

whentojump · 2024-04-23T02:40:44Z

Sorry, I haven't noticed your reply while I was working.

No problem at all! And thanks as always for your contributions to the tool :))

I've created #89573 as the fix.

This is awesome! I will test it and comment there

A synthesized identifier with `##` is emitted to `<scratch space>`. `llvm-cov` cannot handle `<scratch space> since it doesn't have actual files. As a workaround, peel `<scratch space>` to the actual definition if the definition is present. This affects predefined built-in macros, like __LINE__. Fixes llvm#87000

`emitSourceRegions()` has bugs to emit malformed MC/DC coverage mappings. They were detected in `llvm-cov` as the crash. Detect inconsistencies earlier in `clang` with assertions. * mcdc-scratch-space.c covers #87000.

@chapuni

The problematic program is as follows: ```shell void f(void) { PRE(a) && 0; } int main(void) { return 0; } ``` in which after token concatenation (`##`), there's another nested macro `pre_a`. Currently only the outer expansion region will be produced. ([compiler explorer link](https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:29,endLineNumber:8,positionColumn:29,positionLineNumber:8,selectionStartColumn:29,selectionStartLineNumber:8,startColumn:29,startLineNumber:8),source:'%23define+pre_a+0%0A%23define+PRE(x)+pre_%23%23x%0A%0Avoid+f(void)+%7B%0A++++PRE(a)+%26%26+0%3B%0A%7D%0A%0Aint+main(void)+%7B+return+0%3B+%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:51.69491525423727,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:cclang_assertions_trunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'0',intel:'0',libraryCode:'1',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:2,lang:___c,libs:!(),options:'-fprofile-instr-generate+-fcoverage-mapping+-fcoverage-mcdc+-Xclang+-dump-coverage-mapping+',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+(assertions+trunk)+(Editor+%231)',t:'0')),k:34.5741843594503,l:'4',m:28.903654485049834,n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(compilerName:'x86-64+clang+(trunk)',editorid:1,fontScale:14,fontUsePx:'0',j:2,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+clang+(assertions+trunk)+(Compiler+%232)',t:'0')),header:(),l:'4',m:71.09634551495017,n:'0',o:'',s:0,t:'0')),k:48.30508474576271,l:'3',n:'0',o:'',t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4)) ```text f: File 0, 4:14 -> 6:2 = #0 Decision,File 0, 5:5 -> 5:16 = M:0, C:2 Expansion,File 0, 5:5 -> 5:8 = #0 (Expanded file = 1) File 0, 5:15 -> 5:16 = llvm#1 Branch,File 0, 5:15 -> 5:16 = 0, 0 [2,0,0] File 1, 2:16 -> 2:23 = #0 File 2, 1:15 -> 1:16 = #0 File 2, 1:15 -> 1:16 = #0 Branch,File 2, 1:15 -> 1:16 = 0, 0 [1,2,0] ``` The inner expansion region isn't produced because: 1. In the range-based for loop quoted below, each sloc is processed and possibly emit a corresponding expansion region. 2. For our sloc in question, its direct parent returned by `getIncludeOrExpansionLoc()` is a `<scratch space>`, because that's how `##` is processed. https://github.com/llvm/llvm-project/blob/88b6186af3908c55b357858eb348b5143f21c289/clang/lib/CodeGen/CoverageMappingGen.cpp#L518-L520 3. This `<scratch space>` cannot be found in the FileID mapping so `ParentFileID` will be assigned an `std::nullopt` https://github.com/llvm/llvm-project/blob/88b6186af3908c55b357858eb348b5143f21c289/clang/lib/CodeGen/CoverageMappingGen.cpp#L521-L526 4. As a result this iteration of for loop finishes early and no expansion region is added for the sloc. This problem gets worse with MC/DC: as the example shows, there's a branch from File 2 but File 2 itself is missing. This will trigger assertion failures. The fix is more or less a workaround and takes a similar approach as ~~Depends on llvm#89573.~~ This includes llvm#89573. Kudos to @chapuni! This and llvm#89573 together fix llvm#87000: I tested locally, both the reduced program and my original use case (fwiw, Linux kernel) can run successfully. --------- Co-authored-by: NAKAMURA Takumi <geek4civic@gmail.com> llvmorg-19-init-12274-gf9e9e599c013

chapuni · 2024-05-27T06:55:02Z

A patch for releae/18.x is available.
release/18.x...chapuni:llvm-project:release/18.x
fb5f215

whentojump added the tools:llvm-cov label Mar 28, 2024

This was referenced Apr 22, 2024

[MC/DC][Coverage] Add assertions into emitSourceRegions() #89572

Merged

[MC/DC][Coverage] Workaround for ## conditions #89573

Closed

whentojump mentioned this issue Apr 24, 2024

[Coverage][Expansion] handle nested macros in scratch space #89869

Merged

whentojump mentioned this issue May 15, 2024

[llvm-cov][MC/DC] "Branch not found in Decisions" when handling variadic macros #92216

Open

chapuni mentioned this issue May 21, 2024

Weird Clang's branch coverage with macros from system headers #78920

Closed

chapuni added this to the LLVM 18.X Release milestone May 21, 2024

github-project-automation bot added this to LLVM Release Status May 21, 2024

github-project-automation bot moved this to Needs Triage in LLVM Release Status May 21, 2024

chapuni closed this as completed in #89869 May 24, 2024

chapuni closed this as completed in f9e9e59 May 24, 2024

github-project-automation bot moved this from Needs Triage to Done in LLVM Release Status May 24, 2024

EugeneZelenko removed the tools:llvm-cov label May 24, 2024

EugeneZelenko added the coverage label May 24, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[llvm-cov][MC/DC] "Branch not found in Decisions" when handling complicated macros #87000

[llvm-cov][MC/DC] "Branch not found in Decisions" when handling complicated macros #87000

whentojump commented Mar 28, 2024

whentojump commented Mar 28, 2024

chapuni commented Mar 28, 2024

whentojump commented Mar 29, 2024

whentojump commented Apr 22, 2024

chapuni commented Apr 22, 2024

chapuni commented Apr 22, 2024

whentojump commented Apr 23, 2024

chapuni commented May 27, 2024

[llvm-cov][MC/DC] "Branch not found in Decisions" when handling complicated macros #87000

[llvm-cov][MC/DC] "Branch not found in Decisions" when handling complicated macros #87000

Comments

whentojump commented Mar 28, 2024

whentojump commented Mar 28, 2024

chapuni commented Mar 28, 2024

whentojump commented Mar 29, 2024

whentojump commented Apr 22, 2024

chapuni commented Apr 22, 2024

chapuni commented Apr 22, 2024

whentojump commented Apr 23, 2024

chapuni commented May 27, 2024