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

[whentojump]

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

[whentojump]

Also reproduced on compiler explorer: link

[chapuni]

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]

Thanks for reducing the example! Great insight!

[whentojump]

@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 :))

[chapuni]

I've created #89573 as the fix.

[chapuni]

@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.