diff --git a/meson.build b/meson.build
index 638c01066..213745954 100644
--- a/meson.build
+++ b/meson.build
@@ -173,6 +173,7 @@ math = cc.find_library('m')
 realtime = cc.find_library('rt')
 dlsym = cc.find_library('dl')
 zlib = cc.find_library('z')
+yaml = cc.find_library('yaml', required: false)
 
 if cc.has_header('linux/kd.h')
 	config.set('HAVE_LINUX_KD_H', 1)
diff --git a/tools/Makefile.am b/tools/Makefile.am
index a0b016ddd..ae70f5a76 100644
--- a/tools/Makefile.am
+++ b/tools/Makefile.am
@@ -1,6 +1,7 @@
 include Makefile.sources
 
-bin_PROGRAMS = $(tools_prog_lists)
+bin_PROGRAMS = $(tools_prog_lists) igt_kcov
+lib_LTLIBRARIES = igt_kcov_edges.la
 
 if HAVE_LIBDRM_INTEL
 bin_PROGRAMS += $(LIBDRM_INTEL_BIN)
@@ -30,6 +31,14 @@ intel_aubdump_la_LIBADD = $(top_builddir)/lib/libintel_tools.la -ldl
 
 intel_gpu_top_LDADD = $(top_builddir)/lib/libigt_perf.la
 
+# XXX FIXME
+igt_kcov_SOURCES = igt_kcov.c
+igt_kcov_LDADD = -lyaml -lz -lrt -lm
+
+igt_kcov_edges_la_SOURCES = igt_kcov_edges.c
+igt_kcov_edges_la_LDFLAGS = -module -no-undefined -avoid-version
+igt_kcov_edges_la_LIBADD = -ldl
+
 bin_SCRIPTS = intel_aubdump
 CLEANFILES = $(bin_SCRIPTS)
 
diff --git a/tools/igt_kcov.c b/tools/igt_kcov.c
new file mode 100644
index 000000000..e9179a4b3
--- /dev/null
+++ b/tools/igt_kcov.c
@@ -0,0 +1,1218 @@
+#include <sys/types.h>
+#include <sys/file.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <sys/wait.h>
+
+#include <ctype.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <getopt.h>
+#include <inttypes.h>
+#include <math.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+
+#include <yaml.h>
+#include <zlib.h>
+
+#define SZ_8 (1 << 16)
+#define SZ_32 (sizeof(uint32_t) * SZ_8)
+
+static pid_t child = 0;
+
+static void sighandler(int sig)
+{
+	kill(sig, child);
+}
+
+static uint64_t gettime(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+
+	return ts.tv_sec * 1000000000 + ts.tv_nsec;
+}
+
+struct exec {
+	const char *preload;
+	int uid;
+	int gid;
+};
+
+static int edges_exec(const struct exec *args, char **argv, uint64_t *elapsed)
+{
+	char buf[10];
+	int status;
+	int kcov;
+	int shm;
+	int ret;
+
+	kcov = open("/sys/kernel/debug/kcov", O_RDWR);
+	if (kcov < 0)
+		return -errno;
+
+	shm = memfd_create("igt_kcov", 0);
+	if (shm == -1) {
+		close(kcov);
+		return -errno;
+	}
+
+	ftruncate(shm, SZ_32);
+
+	switch ((child = fork())) {
+	case 0: /* child */
+		if (args->gid)
+			setgid(args->gid);
+		if (args->uid)
+			setuid(args->uid);
+
+		sprintf(buf, "%d", shm);
+		setenv("IGT_SHM_FD", buf, 1);
+
+		sprintf(buf, "%d", kcov);
+		setenv("IGT_KCOV_FD", buf, 1);
+
+		setenv("LD_PRELOAD", args->preload, 1);
+		exit(execvp(argv[0], argv));
+		break;
+
+	case -1:
+		ret = -errno;
+		break;
+
+	default:
+		signal(SIGINT, sighandler);
+
+		*elapsed = -gettime();
+		do {
+			ret = waitpid(child, &status, 0);
+			if (ret == -1)
+				ret = -errno;
+		} while (ret == -EINTR);
+		*elapsed += gettime();
+
+		signal(SIGINT, SIG_DFL);
+		child = 0;
+	}
+
+	close(kcov);
+	if (ret < 0) {
+		close(shm);
+		shm = ret;
+	}
+
+	return shm;
+}
+
+static inline unsigned long __fls(unsigned long word)
+{
+#if defined(__GNUC__) && (defined(__i386__) || defined(__x86__) || defined(__x86_64__))
+	asm("bsr %1,%0"
+	    : "=r" (word)
+	    : "rm" (word));
+	return word;
+#else
+	unsigned int v = 0;
+
+	while (word >>= 1)
+		v++;
+
+	return v;
+#endif
+}
+
+static uint8_t lower_u32(uint32_t x)
+{
+	if (x < 16)
+		return x;
+	else
+		return (x >> (__fls(x) - 2)) + ((__fls(x) - 1) << 2);
+}
+
+static uint8_t *lower_edges(int shm)
+{
+	uint8_t *lower;
+	uint32_t *tbl;
+	unsigned int n;
+
+	tbl = mmap(NULL, SZ_32, PROT_READ, MAP_SHARED, shm, 0);
+	if (tbl == MAP_FAILED)
+		return NULL;
+
+	if (tbl[0] == 0) /* empty */
+		goto out;
+
+	lower = malloc(SZ_8);
+	if (!lower)
+		goto out;
+
+	for (n = 0; n < 1 << 16; n++)
+		lower[n] = lower_u32(tbl[n]);
+
+out:
+	munmap(tbl, SZ_32);
+	return lower;
+}
+
+static bool ascii85_encode(uint32_t in, char *out)
+{
+	int i;
+
+	if (in == 0)
+		return false;
+
+	for (i = 5; i--; ) {
+		out[i] = '!' + in % 85;
+		in /= 85;
+	}
+
+	return true;
+}
+
+static char *edges_to_ascii85(uint8_t *tbl)
+{
+	z_stream zs;
+	uint32_t *p;
+	void *out;
+	char *str, *s;
+	int sz;
+
+	sz = SZ_8 * 3 /2;
+	out = malloc(sz);
+	if (!out)
+		return NULL;
+
+	memset(&zs, 0, sizeof(zs));
+	if (deflateInit(&zs, 9)) {
+		free(out);
+		return NULL;
+	}
+
+	zs.next_in = tbl;
+	zs.avail_in = SZ_8;
+	zs.total_in = 0;
+	zs.avail_out = sz;
+	zs.total_out = 0;
+	zs.next_out = out;
+
+	deflate(&zs, Z_FINISH);
+	deflateEnd(&zs);
+
+	if (zs.total_out & 3)
+		memset((char *)out + zs.total_out, 0, 4 - (zs.total_out & 3));
+	zs.total_out = (zs.total_out + 3) / 4;
+
+	str = malloc(zs.total_out * 5 + 1);
+	if (!str) {
+		free(out);
+		return NULL;
+	}
+
+	p = out;
+	s = str;
+	for (int i = 0; i < zs.total_out; i++) {
+		if (ascii85_encode(*p++, s))
+			s += 5;
+		else
+			*s++ = 'z';
+	}
+	*s++ = '\0';
+	free(out);
+
+	return str;
+}
+
+static void edges(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"output", required_argument, 0, 'o'},
+		{"preload", required_argument, 0, 'p'},
+		{"user", required_argument, 0, 'u'},
+		{"group", required_argument, 0, 'g'},
+		{ NULL, 0, NULL, 0 }
+	};
+	struct exec args = {
+		.preload = "/tmp/igt_kcov_edges.so",
+	};
+	FILE *out = stdout;
+	uint64_t elapsed;
+	uint8_t *tbl;
+	char *str, *s;
+	int shm, i;
+
+	while ((i = getopt_long(argc, argv,
+				"+o:g:u:",
+				longopts, NULL)) != -1) {
+		switch (i) {
+		case 'o':
+			if (strcmp(optarg, "-"))
+				out = fopen(optarg, "a");
+			if (!out) {
+				fprintf(stderr,
+					"Unable to open output file '%s'\n",
+					optarg);
+				exit(1);
+			}
+			break;
+		case 'p':
+			args.preload = optarg;
+			break;
+		case 'u':
+			args.uid = atoi(optarg);
+			break;
+		case 'g':
+			args.gid = atoi(optarg);
+			break;
+		}
+	}
+	argc -= optind;
+	argv += optind;
+
+	if (argc < 1) {
+		fprintf(stderr,
+			"usage: igt_kcov edges [options] program-to-trace args...\n");
+		exit(1);
+	}
+
+	shm = edges_exec(&args, argv, &elapsed);
+	if (shm < 0) {
+		fprintf(stderr,
+			"Execution of %s failed: err=%d\n",
+			argv[0], shm);
+		exit(1);
+	}
+
+	tbl = lower_edges(shm);
+	close(shm);
+	if (!tbl)
+		exit(1);
+
+	str = edges_to_ascii85(tbl);
+
+	flock(fileno(out), LOCK_EX);
+	fprintf(out, "---\n");
+
+	fprintf(out, "cmd: |  \n");
+	for (i = 0; i < argc; i++) {
+		fprintf(out, " '");
+		for (s = argv[i]; *s; s++) {
+			if (*s == '\'')
+				fprintf(out, "\\\'");
+			else
+				fprintf(out, "%c", *s);
+		}
+		fprintf(out, "'");
+	}
+	fprintf(out, "\n");
+
+	fprintf(out, "elapsed: %"PRIu64" # %.1fms\n", elapsed, 1e-6 * elapsed);
+
+	fprintf(out, "edges: !!ascii85.gz |\n");
+	i = strlen(str);
+	s = str;
+	while (i) {
+		int len = i > 70 ? 70 : i;
+		char tmp;
+
+		tmp = s[len];
+		s[len] = '\0';
+		fprintf(out, "  %s\n", s);
+		s[len] = tmp;
+
+		s += len;
+		i -= len;
+	}
+
+	fflush(out);
+	flock(fileno(out), LOCK_UN);
+
+	free(str);
+}
+
+static unsigned long zlib_inflate(void *in, unsigned long len,
+				  void *ptr, unsigned long max)
+{
+	struct z_stream_s zstream;
+
+	memset(&zstream, 0, sizeof(zstream));
+
+	zstream.next_in = in;
+	zstream.avail_in = len;
+
+	if (inflateInit(&zstream) != Z_OK)
+		return 0;
+
+	zstream.next_out = ptr;
+	zstream.avail_out = max;
+
+	switch (inflate(&zstream, Z_SYNC_FLUSH)) {
+	case Z_STREAM_END:
+	case Z_OK:
+		break;
+	default:
+		zstream.total_out = 0;
+		break;
+	}
+
+	inflateEnd(&zstream);
+	return zstream.total_out;
+}
+
+static unsigned long ascii85_decode(const char *in,
+				    void *ptr, unsigned long max)
+{
+	unsigned long sz = max / sizeof(uint32_t);
+	unsigned long len = 0;
+	uint32_t *out;
+
+	out = malloc(sz * sizeof(uint32_t));
+	if (out == NULL)
+		return 0;
+
+	while (*in) {
+		uint32_t v = 0;
+
+		if (isspace(*in)) {
+			in++;
+			continue;
+		}
+
+		if (*in < '!' || *in > 'z') {
+			fprintf(stderr, "Invalid value in ascii85 block\n");
+			free(out);
+			return 0;
+		}
+
+		if (len == sz) {
+			sz *= 2;
+			out = realloc(out, sz * sizeof(uint32_t));
+			if (out == NULL)
+				return 0;
+		}
+
+		if (*in == 'z') {
+			in++;
+		} else {
+			v += in[0] - 33; v *= 85;
+			v += in[1] - 33; v *= 85;
+			v += in[2] - 33; v *= 85;
+			v += in[3] - 33; v *= 85;
+			v += in[4] - 33;
+			in += 5;
+		}
+		out[len++] = v;
+	}
+
+	len = zlib_inflate(out, len * sizeof(*out), ptr, max);
+	free(out);
+
+	return len;
+}
+
+static void yaml_print_parser_error(yaml_parser_t *parser, FILE *stream)
+{
+	switch (parser->error) {
+	case YAML_MEMORY_ERROR:
+		fprintf(stderr, "Memory error: Not enough memory for parsing\n");
+		break;
+
+	case YAML_READER_ERROR:
+		if (parser->problem_value != -1) {
+			fprintf(stderr, "Reader error: %s: #%X at %zd\n", parser->problem,
+				parser->problem_value, parser->problem_offset);
+		} else {
+			fprintf(stderr, "Reader error: %s at %zd\n", parser->problem,
+				parser->problem_offset);
+		}
+		break;
+
+	case YAML_SCANNER_ERROR:
+		if (parser->context) {
+			fprintf(stderr, "Scanner error: %s at line %lu, column %lu\n"
+				"%s at line %lu, column %lu\n", parser->context,
+				parser->context_mark.line+1, parser->context_mark.column+1,
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		} else {
+			fprintf(stderr, "Scanner error: %s at line %lu, column %lu\n",
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		}
+		break;
+
+	case YAML_PARSER_ERROR:
+		if (parser->context) {
+			fprintf(stderr, "Parser error: %s at line %lu, column %lu\n"
+				"%s at line %lu, column %lu\n", parser->context,
+				parser->context_mark.line+1, parser->context_mark.column+1,
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		} else {
+			fprintf(stderr, "Parser error: %s at line %lu, column %lu\n",
+				parser->problem, parser->problem_mark.line+1,
+				parser->problem_mark.column+1);
+		}
+		break;
+
+	default:
+		/* Couldn't happen. */
+		fprintf(stderr, "Internal error\n");
+		break;
+	}
+}
+
+struct edges {
+	struct edges *next;
+
+	char *command;
+	uint64_t elapsed;
+
+	unsigned int weight;
+
+	uint8_t tbl[SZ_8];
+};
+
+struct sort {
+	struct edges *edges;
+	unsigned int count;
+
+	unsigned int max_weight;
+	struct edges *best;
+};
+
+static bool sort_parse_command(struct sort *sort,
+			       struct edges *e,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+	int len;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+
+	s = (const char *)ev.data.scalar.value;
+	len = strlen(s);
+	while (s[len - 1] == '\n')
+		len--;
+	e->command = malloc(len + 1);
+	if (e->command) {
+		memcpy(e->command, s, len);
+		e->command[len] = '\0';
+	}
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool sort_parse_elapsed(struct sort *sort,
+			       struct edges *e,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+	s = (const char *)ev.data.scalar.value;
+	e->elapsed = strtoull(s, NULL, 0);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static unsigned int bitmap_weight(const void *bitmap, unsigned int bits)
+{
+	const uint32_t *b = bitmap;
+	unsigned int k, lim = bits / 32;
+	unsigned int w = 0;
+
+	for (k = 0; k < lim; k++)
+		w += __builtin_popcount(b[k]);
+
+	if (bits % 32)
+		w += __builtin_popcount(b[k] << (32 - bits % 32));
+
+	return w;
+}
+
+static bool sort_parse_edges(struct sort *sort,
+			     struct edges *e,
+			     yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+	s = (const char *)ev.data.scalar.value;
+	if (ascii85_decode(s, e->tbl, sizeof(e->tbl)))
+		e->weight = bitmap_weight(e->tbl, sizeof(e->tbl) * 8);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool edges_valid(const struct edges *e)
+{
+	if (!e->command)
+		return false;
+
+	if (!e->weight)
+		return false;
+
+	if (!e->elapsed)
+		return false;
+
+	return true; /* good enough at least */
+}
+
+static bool sort_add_edges(struct sort *sort, struct edges *e)
+{
+	if (!edges_valid(e))
+		return false;
+
+	e->next = sort->edges;
+	sort->edges = e;
+
+	if (e->weight > sort->max_weight) {
+		sort->max_weight = e->weight;
+		sort->best = e;
+	}
+
+	sort->count++;
+
+	return true;
+}
+
+static bool sort_parse_node(struct sort *sort, yaml_parser_t *parser)
+{
+	struct edges *e;
+	yaml_event_t ev;
+	char *s;
+
+	e = malloc(sizeof(*e));
+	if (!e)
+		return false;
+
+	e->weight = 0;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			goto err;
+
+		switch (ev.type) {
+		case YAML_MAPPING_END_EVENT:
+			if (!sort_add_edges(sort, e))
+				goto err;
+
+			return true;
+
+		case YAML_SCALAR_EVENT:
+			break;
+
+		default:
+			goto err;
+		}
+
+		s = (char *)ev.data.scalar.value;
+		if (!strcmp(s, "cmd")) {
+			sort_parse_command(sort, e, parser);
+		} else if (!strcmp(s, "elapsed")) {
+			sort_parse_elapsed(sort, e, parser);
+		} else if (!strcmp(s, "edges")) {
+			sort_parse_edges(sort, e, parser);
+		} else {
+			fprintf(stderr,
+				"Unknown element in edges file: %s\n",
+				s);
+		}
+
+		yaml_event_delete(&ev);
+	} while (1);
+
+err:
+	free(e);
+	return false;
+}
+
+static bool sort_parse_doc(struct sort *sort, yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_END_EVENT:
+			return true;
+
+		case YAML_MAPPING_START_EVENT:
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+
+		if (!sort_parse_node(sort, parser))
+			return false;
+	} while(1);
+}
+
+static bool sort_add(struct sort *sort, FILE *file)
+{
+	yaml_parser_t parser;
+	bool done = false;
+	yaml_event_t ev;
+
+	yaml_parser_initialize(&parser);
+	yaml_parser_set_input_file(&parser, file);
+
+	memset(&ev, 0, sizeof(ev));
+	yaml_parser_parse(&parser, &ev);
+	if (ev.type != YAML_STREAM_START_EVENT) {
+		fprintf(stderr, "Parser setup failed\n");
+		return false;
+	}
+	yaml_event_delete(&ev);
+
+	do {
+		if (!yaml_parser_parse(&parser, &ev)) {
+			yaml_print_parser_error(&parser, stderr);
+			return false;
+		}
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_START_EVENT:
+			break;
+
+		case YAML_STREAM_END_EVENT:
+			done = true;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+
+		sort_parse_doc(sort, &parser);
+	} while (!done);
+
+	yaml_parser_delete(&parser);
+	return true;
+}
+
+static double edges_similarity(const struct edges *ta, const struct edges *tb)
+{
+	uint64_t sab, saa, sbb;
+	const uint8_t *a, *b;
+
+	if (ta == tb)
+		return 1;
+
+	a = ta->tbl;
+	b = tb->tbl;
+	sab = 0;
+	saa = 0;
+	sbb = 0;
+
+	for (unsigned int i = 0; i < SZ_8; i++) {
+		sab += (uint32_t)a[i] * b[i];
+		saa += (uint32_t)a[i] * a[i];
+		sbb += (uint32_t)b[i] * b[i];
+	}
+
+	return ((long double)sab * sab) / ((long double)saa * sbb);
+}
+
+static void rank_by_dissimilarity(struct sort *sort, FILE *out)
+{
+	const unsigned int count = sort->count;
+	double *M, *dis, *sim;
+	struct edges **edges, **t;
+	bool *used;
+	int last = -1;
+
+	t = edges = malloc(count * sizeof(*edges));
+	for (struct edges *e = sort->edges; e; e = e->next)
+		*t++ = e;
+
+	M = malloc(sizeof(double) * count * (count + 2));
+	dis = M + count * count;
+	sim = dis + count;
+	for (int i = 0; i < count; i++) {
+		dis[i] = 0.;
+		sim[i] = 1.;
+		for (int j = 0; j < i; j++)
+			dis[i] += M[j*count + i];
+		for (int j = i + 1; j < count; j++) {
+			double d = 1. - edges_similarity(edges[i], edges[j]);
+			M[i*count + j] = d;
+			dis[i] += d;
+		}
+	}
+
+	fprintf(out, "---\n");
+
+	used = calloc(count, sizeof(bool));
+	for (int rank = 0; rank < count; rank++) {
+		struct edges *e;
+		double best = -HUGE_VAL;
+		int this = -1;
+
+		for (int i = 0; i < count; i++) {
+			double d;
+
+			if (used[i])
+				continue;
+
+			d = dis[i];
+			if (last != -1) {
+				double s;
+
+				if (last < i)
+					s = M[last * count + i];
+				else
+					s = M[i * count + last];
+
+				s *= sim[i];
+				sim[i] = s;
+
+				d *= sqrt(s);
+			}
+			if (d > best) {
+				best = d;
+				this = i;
+			}
+		}
+
+		if (this < 0)
+			break;
+
+		e = edges[this];
+		used[this] = true;
+		last = this;
+
+		fprintf(out, "- cmd: |\n    %s\n", e->command);
+		fprintf(out, "  elapsed: %"PRIu64" # %.1fms\n",
+			e->elapsed, 1e-6 * e->elapsed);
+		fprintf(out, "  dissimilarity: %.4g\n",
+			sqrt(best / (count - rank)));
+	}
+
+	free(M);
+	free(edges);
+}
+
+static void sort(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"output", required_argument, 0, 'o'},
+		{ NULL, 0, NULL, 0 }
+	};
+	FILE *out = stdout;
+	struct sort sort;
+	int i;
+
+	while ((i = getopt_long(argc, argv,
+				"+o:",
+				longopts, NULL)) != -1) {
+		switch (i) {
+		case 'o':
+			if (strcmp(optarg, "-"))
+				out = fopen(optarg, "a");
+			if (!out) {
+				fprintf(stderr,
+					"Unable to open output file '%s'\n",
+					optarg);
+				exit(1);
+			}
+			break;
+		}
+	}
+	argc -= optind;
+	argv += optind;
+
+	memset(&sort, 0, sizeof(sort));
+
+	if (argc == 0) {
+		sort_add(&sort, stdin);
+	} else {
+		for (i = 0; i < argc; i++) {
+			FILE *in;
+
+			in = fopen(argv[i], "r");
+			if (!in) {
+				fprintf(stderr, "unable to open input '%s'\n",
+					argv[i]);
+				exit(1);
+			}
+
+			sort_add(&sort, in);
+
+			fclose(in);
+		}
+	}
+
+	if (!sort.count)
+		return;
+
+	rank_by_dissimilarity(&sort, out);
+}
+
+struct list {
+	struct {
+		double single;
+		double total;
+	} limit;
+	double total;
+	FILE *out;
+};
+
+struct list_node {
+	char *cmd;
+	uint64_t elapsed;
+};
+
+static bool list_parse_command(struct list *list,
+			       struct list_node *node,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+	int len;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+
+	s = (const char *)ev.data.scalar.value;
+	len = strlen(s);
+	while (len > 0 && isspace(s[len - 1]))
+		len--;
+
+	node->cmd = strndup(s, len);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool list_parse_elapsed(struct list *list,
+			       struct list_node *node,
+			       yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+	const char *s;
+
+	if (!yaml_parser_parse(parser, &ev))
+		return false;
+
+	switch (ev.type) {
+	case YAML_SCALAR_EVENT:
+		break;
+
+	default:
+		return false;
+	}
+
+	s = (const char *)ev.data.scalar.value;
+	node->elapsed = strtoull(s, NULL, 0);
+	yaml_event_delete(&ev);
+
+	return true;
+}
+
+static bool list_parse_node(struct list *list, yaml_parser_t *parser)
+{
+	struct list_node node = {};
+	yaml_event_t ev;
+	char *s;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_MAPPING_END_EVENT:
+			if (list->limit.single &&
+			    1e-9 * node.elapsed > list->limit.single) {
+				free(node.cmd);
+				return true;
+			}
+
+			if (list->limit.total &&
+			    list->total + 1e-9 * node.elapsed > list->limit.total) {
+				free(node.cmd);
+				return true;
+			}
+
+			if (node.cmd) {
+				list->total += 1e-9 * node.elapsed;
+				fprintf(list->out,
+					"%s # %.3fms, total %.1fms\n",
+					node.cmd,
+					1e-6 * node.elapsed,
+					1e3 * list->total);
+				free(node.cmd);
+			}
+			return true;
+
+		case YAML_SCALAR_EVENT:
+			break;
+
+		default:
+			return false;
+		}
+
+		s = (char *)ev.data.scalar.value;
+		if (!strcmp(s, "cmd")) {
+			list_parse_command(list, &node, parser);
+		} else if (!strcmp(s, "elapsed")) {
+			if (!list_parse_elapsed(list, &node,parser))
+				return false;
+		}
+		yaml_event_delete(&ev);
+	} while (1);
+}
+
+static bool list_parse_sequence(struct list *list, yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_SEQUENCE_END_EVENT:
+			return true;
+
+		case YAML_MAPPING_START_EVENT:
+			if (!list_parse_node(list, parser))
+				return false;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+	} while(1);
+}
+
+static bool list_parse_doc(struct list *list, yaml_parser_t *parser)
+{
+	yaml_event_t ev;
+
+	do {
+		if (!yaml_parser_parse(parser, &ev))
+			return false;
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_END_EVENT:
+			return true;
+
+		case YAML_MAPPING_START_EVENT:
+			if (!list_parse_node(list, parser))
+				return false;
+			break;
+
+		case YAML_SEQUENCE_START_EVENT:
+			if (!list_parse_sequence(list, parser))
+				return false;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+	} while(1);
+}
+
+static bool list_show(struct list *list, FILE *file)
+{
+	yaml_parser_t parser;
+	bool done = false;
+	yaml_event_t ev;
+
+	yaml_parser_initialize(&parser);
+	yaml_parser_set_input_file(&parser, file);
+
+	memset(&ev, 0, sizeof(ev));
+	yaml_parser_parse(&parser, &ev);
+	if (ev.type != YAML_STREAM_START_EVENT) {
+		fprintf(stderr, "Parser setup failed\n");
+		return false;
+	}
+	yaml_event_delete(&ev);
+
+	do {
+		if (!yaml_parser_parse(&parser, &ev)) {
+			yaml_print_parser_error(&parser, stderr);
+			return false;
+		}
+
+		switch (ev.type) {
+		case YAML_DOCUMENT_START_EVENT:
+			break;
+
+		case YAML_STREAM_END_EVENT:
+			done = true;
+			break;
+
+		default:
+			return false;
+		}
+		yaml_event_delete(&ev);
+
+		list_parse_doc(list, &parser);
+	} while (!done);
+
+	yaml_parser_delete(&parser);
+	return true;
+}
+
+static void list(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"output", required_argument, 0, 'o'},
+		{"total", required_argument, 0, 't'},
+		{"single", required_argument, 0, 's'},
+		{ NULL, 0, NULL, 0 }
+	};
+	struct list list;
+	int i;
+
+	memset(&list, 0, sizeof(list));
+	list.out = stdout;
+
+	while ((i = getopt_long(argc, argv,
+				"+o:t:",
+				longopts, NULL)) != -1) {
+		switch (i) {
+		case 'o':
+			if (strcmp(optarg, "-"))
+				list.out = fopen(optarg, "a");
+			if (!list.out) {
+				fprintf(stderr,
+					"Unable to open output file '%s'\n",
+					optarg);
+				exit(1);
+			}
+			break;
+		case 's':
+			list.limit.single = atof(optarg);
+			break;
+		case 't':
+			list.limit.total = atof(optarg);
+			break;
+		}
+	}
+	argc -= optind;
+	argv += optind;
+
+	if (argc == 0) {
+		list_show(&list, stdin);
+	} else {
+		for (i = 0; i < argc; i++) {
+			FILE *in;
+
+			in = fopen(argv[i], "r");
+			if (!in) {
+				fprintf(stderr, "unable to open input '%s'\n",
+					argv[i]);
+				exit(1);
+			}
+
+			if (!list_show(&list, in))
+				i = argc;
+
+			fclose(in);
+		}
+	}
+}
+
+int main(int argc, char **argv)
+{
+	static const struct option longopts[] = {
+		{"verbose", no_argument, 0, 'v'},
+		{ NULL, 0, NULL, 0 }
+	};
+	int o;
+
+	while ((o = getopt_long(argc, argv,
+				"+v",
+				longopts, NULL)) != -1) {
+		switch (o) {
+		case 'v':
+			break;
+		default:
+			break;
+		}
+	}
+
+	if (optind == argc) {
+		fprintf(stderr, "no subcommand specified\n");
+		exit(1);
+	}
+
+	argc -= optind;
+	argv += optind;
+	optind = 1;
+
+	if (!strcmp(argv[0], "edges")) {
+		edges(argc, argv);
+	} else if (!strcmp(argv[0], "sort")) {
+		sort(argc, argv);
+	} else if (!strcmp(argv[0], "list")) {
+		list(argc, argv);
+	} else {
+		fprintf(stderr, "Unknown command '%s'\n", argv[0]);
+		exit(1);
+	}
+
+	return 0;
+}
diff --git a/tools/igt_kcov_edges.c b/tools/igt_kcov_edges.c
new file mode 100644
index 000000000..750d4f8b5
--- /dev/null
+++ b/tools/igt_kcov_edges.c
@@ -0,0 +1,145 @@
+#include <sys/ioctl.h>
+#include <sys/mman.h>
+#include <sys/types.h>
+
+#include <dlfcn.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <pthread.h>
+
+#include <linux/types.h>
+
+static int (*libc_ioctl)(int fd, unsigned long request, void *argp);
+
+static struct kcov {
+	unsigned long *trace;
+	uint32_t *table;
+	int fd;
+} kcov;
+
+#define KCOV_INIT_TRACE                 _IOR('c', 1, unsigned long)
+#define KCOV_ENABLE                     _IO('c', 100)
+#define   KCOV_TRACE_PC  0
+#define   KCOV_TRACE_CMP 1
+#define KCOV_DISABLE                    _IO('c', 101)
+
+#define DRM_IOCTL_BASE 'd'
+
+#define GOLDEN_RATIO_32 0x61C88647
+#define GOLDEN_RATIO_64 0x61C8864680B583EBull
+
+static inline uint32_t hash_32(uint32_t val, unsigned int bits)
+{
+        return val * GOLDEN_RATIO_32 >> (32 - bits);
+}
+
+static inline uint32_t hash_64(uint64_t val, unsigned int bits)
+{
+        return val * GOLDEN_RATIO_64 >> (64 - bits);
+}
+
+#define hash_long(x, y) hash_64(x, y)
+
+static bool kcov_open(struct kcov *kc, unsigned long count)
+{
+	const char *env;
+	int shm;
+
+	env = getenv("IGT_SHM_FD");
+	if (!env)
+		return false;
+
+	shm = atoi(env);
+	kc->table = mmap(NULL, sizeof(uint32_t) << 16,
+			 PROT_WRITE, MAP_SHARED, shm, 0);
+	close(shm);
+	if (kc->table == (uint32_t *)MAP_FAILED)
+		return false;
+
+	env = getenv("IGT_KCOV_FD");
+	if (!env)
+		goto err_shm;
+
+	kc->fd = atoi(env);
+	if (libc_ioctl(kc->fd, KCOV_INIT_TRACE, (void *)count))
+		goto err_close;
+
+	kc->trace = mmap(NULL, count * sizeof(unsigned long),
+			 PROT_WRITE, MAP_SHARED, kc->fd, 0);
+	if (kc->trace == MAP_FAILED)
+		goto err_close;
+
+	return true;
+
+err_close:
+	close(kc->fd);
+err_shm:
+	munmap(kc->table, sizeof(uint32_t) << 16);
+	return false;
+}
+
+static void kcov_enable(struct kcov *kc)
+{
+	libc_ioctl(kc->fd, KCOV_ENABLE, KCOV_TRACE_PC);
+	__atomic_store_n(&kc->trace[0], 0, __ATOMIC_RELAXED);
+}
+
+static unsigned long kcov_disable(struct kcov *kc)
+{
+	unsigned long depth;
+
+	depth = __atomic_load_n(&kc->trace[0], __ATOMIC_RELAXED);
+	if (libc_ioctl(kc->fd, KCOV_DISABLE, 0))
+		depth = 0;
+
+	return depth;
+}
+
+int ioctl(int fd, unsigned long request, ...)
+{
+	static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
+	unsigned long count, n, prev;
+	va_list args;
+	void *argp;
+	int res;
+
+	va_start(args, request);
+	argp = va_arg(args, void *);
+	va_end(args);
+
+	if (kcov.fd < 0 || _IOC_TYPE(request) != DRM_IOCTL_BASE)
+		return libc_ioctl(fd, request, argp);
+
+	pthread_mutex_lock(&mutex);
+	kcov_enable(&kcov);
+
+	res = libc_ioctl(fd, request, argp);
+
+	count = kcov_disable(&kcov);
+	prev = hash_long(kcov.trace[1], 16);
+	for (n = 2; n <= count; n++) {
+		unsigned long loc = hash_long(kcov.trace[n], 16);
+
+		kcov.table[prev ^ loc]++;
+		prev = loc >> 1;
+	}
+	kcov.table[0] |= 1;
+	pthread_mutex_unlock(&mutex);
+
+	return res;
+}
+
+__attribute__((constructor))
+static void init(void)
+{
+	libc_ioctl = dlsym(RTLD_NEXT, "ioctl");
+
+	if (!kcov_open(&kcov, 64 << 10))
+		kcov.fd = -1;
+}
diff --git a/tools/meson.build b/tools/meson.build
index 8ed1ccf48..d0d9c9c91 100644
--- a/tools/meson.build
+++ b/tools/meson.build
@@ -104,6 +104,19 @@ executable('intel_reg', sources : intel_reg_src,
 	     '-DIGT_DATADIR="@0@"'.format(join_paths(prefix, datadir)),
 	   ])
 
+if yaml.found()
+	executable('igt_kcov',
+		   sources: [ 'igt_kcov.c' ],
+		   dependencies: [ zlib, realtime, math, yaml ],
+		   install: true) # setuid me!
+
+	shared_module('igt_kcov_edges',
+		      sources: [ 'igt_kcov_edges.c' ],
+		      name_prefix: '',
+		      dependencies: [ dlsym ],
+		      install: true) # -version, -Dlibdir
+endif
+
 install_data('intel_gpu_abrt', install_dir : bindir)
 
 install_subdir('registers', install_dir : datadir,
