[2/2] Prime path coverage in gcc/gcov

These are the main highlights since v2:

1. Significant performance improvement in finding prime paths --
   primarily from reducing work when merging tries, but also smaller
   optimizations.

2. JSON output

3. Much improved gcov output, including inlining aware gcov output. See
   demo.

4. Flag for giving up after #-of-paths -- see discussion.

5. Minor bugfixes, destructors, refactoring, helpers etc.

Compile times are still brutal, but much better than before. It doesn't
seem like I emit more instructions than I absolutely have to (but I
would like a counter example here). I don't know if there is too much
that can be done about this other than general speed improvements in
verify-ssa, verify-gimple, verify-control-flow and the likes.

The feature is shaping up nicely, and I think it would be ok to review
now. After some feedback I will write the manual entry for it.

--

This patch adds prime path coverage to gcc/gcov. First, a quick
introduction to path coverage, before I explain a bit on the pieces of
the patch.

PRIME PATHS

Path coverage is recording the paths taken through the program. Here is a
simple example:

if (cond1)  BB 1
  then1 ()  BB 2
else
  else1 ()  BB 3

if (cond2)  BB 4
  then2 ()  BB 5
else
  else2 ()  BB 6

_           BB 7

To cover all paths you must run {then1 then2}, {then1 else2}, {else1 then1},
{else1 else2}. This is in contrast with line/statement coverage where it is
sufficient to execute then2, and it does not matter if it was reached through
then1 or else1.

1 2 4 5 7
1 2 4 6 7
1 3 4 5 7
1 3 4 6 7

This gets more complicated with loops, because 0, 1, 2, ..., N iterations are
all different paths. There are different ways of addressing this, a promising
one being prime paths. A prime path is a simple path (a path with no repeated
vertices except for the first/last in a cycle) that does not appear as a subpath
of any other simple path. Prime paths seem to strike a decent balance between
number of tests, path growth, and loop coverage. Of course, the number of paths
still grows very fast with program complexity - for example, this program has
14 prime paths:

  while (a)
    {
      if (b)
        return;
      while (c--)
        a++;
    }

--

ALGORITHM

Since the numbers of paths grows so fast, we need a good algorithm. The naive
approach of generating all paths and discarding redundancies (see
reference_prime_paths in the diff) simply doesn't complete for even pretty
simple functions with a few ten thousand paths (granted, the implementation is
also poor, but only serves as a reference). Fazli & Afsharchi in their paper
"Time and Space-Efficient Compositional Method for Prime and Test Paths
Generation from describe a neat algorithm which drastically improves on this
and brings complexity down to something managable. This patch implements that
algorithm with a few minor tweaks.

The algorithm first finds the strongly connected components (SCC) of the graph
and creates a new graph where the vertices are the SCCs of the CFG. Within
these vertices different paths are found - regular prime paths, paths that
start in the SCCs entries, and paths that end in the SCCs exits. These per-SCC
paths are combined with paths through the CFG which greatly reduces of paths
needed to be evaluated just to be thrown away.

Using this algorithm we can generate the prime paths for somewhat complicated
functions in a reasonable time. This is the prime_paths function. Please note
that some paths don't benefit from this at all. We need to find the prime paths
within a SCC, so if a single SCC is very large the function degenerates to the
naive implementation. Improving on this is a later project.

--

OVERALL ARCHITECTURE

Like the other coverages in gcc, this operates on the CFG in the profiling
phase, just after branch and condition coverage, in phases:

1. All prime paths are generated, counted, and enumerated from the CFG
2. The paths are evaluted and counter instructions and accumulators are
   emitted
3. gcov reads the CFG and computes the prime paths (same as step 1)
4. gcov prints a report

Simply writing out all the paths in the .gcno file is not really viable,
the files would be too big. Additionally, there are limits to the
practicality of measuring (and reporting) on millions of paths, so for
most programs where coverage is feasible, computing paths should be
plenty fast. As a result, path coverage really only adds 1 bit to the
counter, rounded up to nearest 64 ("bucket"), so 64 paths takes up 8
bytes, 65 paths take up 16 bytes.

Recording paths is really just massaging large bitsets. Per function,
ceil(paths/64 or 32) buckets (gcov_type) are allocated. Paths are
sorted, so the first path maps to the lowest bit, the second path to the
second lowest bit, and so on. On taking an edge and entering a basic
block, a few bitmasks are applied to unset the bits corresponding to the
paths outside the block and set the bits of the paths that start in that
block. Finally, the right buckets are masked and written to the global
accumulators for the paths that end in the block. Full coverage is
achieved when all bits are set.

gcc does not really inform gcov of abnormal paths, so paths with
abnormal paths are ignored. This probably possible, but requires some
changes to the graph gcc writes to the .gcno file.

--

IMPLEMENTATION

In order to remove non-prime paths (subpaths) I use a non-clever suffix tree,
by inserting all subpaths into a trie. Fazli & Afsharchi do not discuss how
duplicates or subpaths are removed, and using the trie turned out to work
really well. The same prime_paths function is used both in gcc and in gcov
which meant adding some more objects in Makefile.in.

As for speed, I would say that it is acceptable (but see missing pieces
on knobs). It is a problem that is combinatorial in its very nature, so
if you enable this feature you can reasonably expect it taking a while.
My main benchmark tree.c generates approx 2M paths across the 20
functions or so in it (where most functions have less than 1500 paths,
and 2 around a million each). Finding the paths takes 3.5-4s, but the
instrumentation phase takes approx. 2.5 minutes and generates a 32M
binary. Not bad for a 1429 line source file.

There are some selftests which deconstruct the algorithm, so it can be
easily referenced with the Fazli & Afsharchi. I hope that including them
both help to catch regression, clarify the assumptions, and help
understanding the algorithm by breaking up the phases.

DEMO

This is the denser line-aware (grep-friendlier) output. Every missing
path is summarized as the lines you need to run in what order, annotated
with the true/false/throw decision.

$ gcc -fpath-coverage --coverage bs.c -c -o bs
$ gcov -et bs.o
bs.gcda:cannot open data file, assuming not executed
        -:    0:Source:bs.c
        -:    0:Graph:bs.gcno
        -:    0:Data:-
        -:    0:Runs:0
paths covered 0 of 17
path  0 not covered: lines 6 6(true) 11(true) 12
path  1 not covered: lines 6 6(true) 11(false) 13(true) 14
path  2 not covered: lines 6 6(true) 11(false) 13(false) 16
path  3 not covered: lines 6 6(false) 18
path  4 not covered: lines 11(true) 12 6(true) 11
path  5 not covered: lines 11(true) 12 6(false) 18
path  6 not covered: lines 11(false) 13(true) 14 6(true) 11
path  7 not covered: lines 11(false) 13(true) 14 6(false) 18
path  8 not covered: lines 12 6(true) 11(true) 12
path  9 not covered: lines 12 6(true) 11(false) 13(true) 14
path 10 not covered: lines 12 6(true) 11(false) 13(false) 16
path 11 not covered: lines 13(true) 14 6(true) 11(true) 12
path 12 not covered: lines 13(true) 14 6(true) 11(false) 13
path 13 not covered: lines 14 6(true) 11(false) 13(true) 14
path 14 not covered: lines 14 6(true) 11(false) 13(false) 16
path 15 not covered: lines 6(true) 11(true) 12 6
path 16 not covered: lines 6(true) 11(false) 13(true) 14 6
    #####:    1:int binary_search(int a[], int len, int from, int to, int key)
        -:    2:{
    #####:    3:    int low = from;
    #####:    4:    int high = to - 1;
        -:    5:
    #####:    6:    while (low <= high)
        -:    7:    {
    #####:    8:        int mid = (low + high) >> 1;
    #####:    9:        long midVal = a[mid];
        -:   10:
    #####:   11:        if (midVal < key)
    #####:   12:            low = mid + 1;
    #####:   13:        else if (midVal > key)
    #####:   14:            high = mid - 1;
        -:   15:        else
    #####:   16:            return mid; // key found
        -:   17:    }
    #####:   18:    return -1;
        -:   19:}

Then there's this mode, which I personally like quite a lot for
understanding paths. Because it is so verbose I have limited the demo to
2 paths. In this mode gcov will print the sequence of *lines* through
the program and in what order to cover the path, including what basic
block the line is a part of. Like its denser sibling, this also prints
the true/false/throw decision, if there is one.

$ gcov -t --prime-paths-source bs.o
bs.gcda:cannot open data file, assuming not executed
        -:    0:Source:bs.c
        -:    0:Graph:bs.gcno
        -:    0:Data:-
        -:    0:Runs:0
paths covered 0 of 17
path 0:
BB  2:           1:int binary_search(int a[], int len, int from, int to, int key)
BB  2:           3:    int low = from;
BB  2:           4:    int high = to - 1;
BB  2:           6:    while (low <= high)
BB  8: (true)    6:    while (low <= high)
BB  3:           8:     int mid = (low + high) >> 1;
BB  3:           9:     long midVal = a[mid];
BB  3: (true)   11:     if (midVal < key)
BB  4:          12:         low = mid + 1;

path 1:
BB  2:           1:int binary_search(int a[], int len, int from, int to, int key)
BB  2:           3:    int low = from;
BB  2:           4:    int high = to - 1;
BB  2:           6:    while (low <= high)
BB  8: (true)    6:    while (low <= high)
BB  3:           8:     int mid = (low + high) >> 1;
BB  3:           9:     long midVal = a[mid];
BB  3: (false)  11:     if (midVal < key)
BB  5: (true)   13:     else if (midVal > key)
BB  6:          14:         high = mid - 1;

The listing is also aware of inlining:

hello.c:

    #include <stdio.h>
    #include "hello.h"

    int notmain(const char *entity)
    {
      return hello (entity);
    }

    #include <stdio.h>

    inline __attribute__((always_inline))
    int hello (const char *s)
    {
      if (s)
        printf ("hello, %s!\n", s);
      else
        printf ("hello, world!\n");
      return 0;
    }

$ gcov -t --prime-paths-source hello

paths covered 0 of 2
path 0:
BB  2: (true)    4:int notmain(const char *entity)
 == inlined from hello.h ==
BB  2: (true)    6:  if (s)
BB  3:           7:    printf ("hello, %s!\n", s);
BB  5:          10:  return 0;
-------------------------
BB  7:           6:  return hello (entity);
BB  8:           6:  return hello (entity);

path 1:
BB  2: (false)   4:int notmain(const char *entity)
 == inlined from hello.h ==
BB  2: (false)   6:  if (s)
BB  4:           9:    printf ("hello, world!\n");
BB  5:          10:  return 0;
-------------------------
BB  7:           6:  return hello (entity);
BB  8:           6:  return hello (entity);

And finally, JSON (abbreviated). It is quite sparse and very nested, but
is mostly a JSON version of the source listing. It has to be this nested
in order to consistently capture multiple locations. It is always
includes the file name per location for consistency, even though this is
very much redundant in almost all cases. This format is in no way set in
stone, and without targeting it with other tooling I am not sure if it
does the job well.

  "gcc_version": "15.0.0 20240704 (experimental)",
  "current_working_directory": "dir",
  "data_file": "hello.o",
  "files": [
    {
      "file": "hello.c",
      "functions": [
        {
          "name": "notmain",
          "demangled_name": "notmain",
          "start_line": 4,
          "start_column": 5,
          "end_line": 7,
          "end_column": 1,
          "blocks": 7,
          "blocks_executed": 0,
          "execution_count": 0,
          "total_prime_paths": 2,
          "covered_prime_paths": 0,
          "prime_path_coverage": [
            {
              "id": 0,
              "sequence": [
                {
                  "block_id": 2,
                  "locations": [
                    {
                      "file": "hello.c",
                      "line_numbers": [
                        4
                      ]
                    },
                    {
                      "file": "hello.h",
                      "line_numbers": [
                        6
                      ]
                    }
                  ],
                  "edge_kind": "fallthru"
                },
                ...

--

LIMITING NUMBER OF PATHS

This flag controls when gcc gives up on path coverage. To be fast it
uses an approximation where it tracks the worst-case number of paths by
counting inserts into the partial tries (before merging) which means it
also counts effectively redundant paths. In practice this is a fuzzy
upper limit (as estimating the number of paths is very hard, and has no
immediate relationship to the number of edges or vertices), and is
typically set to a high value. The idea is to avoid instrumenting the
absolute worst functions and keep compile times reasonable, and not so
much abour rejecting functions with 101357 paths and accepting 101356
paths.

OPEN QUESTIONS

Suffix arrays or suffix tree algorithms. I experimented with an
implementation of the skew suffix array construction algorithm I found
online, but could not get it to perform well enough to warrant swapping
to it. I don't think working on this matters too much right now
considering the compile time added by the instrumentation phase
dominates running time -- when finding paths adds seconds,
instrumentation adds minutes.

The compile times are brutal. Obviously finding prime paths could be
faster, but right now the real bottleneck is actually instrumentation,
or rather, the work created by emitting a bunch of SSAs and gimple
assigns.
---
 gcc/Makefile.in                        |    6 +-
 gcc/builtins.cc                        |    2 +-
 gcc/collect2.cc                        |    5 +-
 gcc/common.opt                         |   14 +
 gcc/gcc.cc                             |    4 +-
 gcc/gcov-counter.def                   |    3 +
 gcc/gcov-io.h                          |    3 +
 gcc/gcov.cc                            |  426 +++++-
 gcc/gimple-iterator.cc                 |    2 +
 gcc/ipa-inline.cc                      |    2 +-
 gcc/passes.cc                          |    4 +-
 gcc/path-coverage.cc                   |  627 ++++++++
 gcc/prime-paths.cc                     | 1939 ++++++++++++++++++++++++
 gcc/profile.cc                         |    6 +-
 gcc/selftest-run-tests.cc              |    1 +
 gcc/selftest.h                         |    1 +
 gcc/testsuite/g++.dg/gcov/gcov-22.C    |   68 +
 gcc/testsuite/gcc.misc-tests/gcov-29.c |  861 +++++++++++
 gcc/testsuite/lib/gcov.exp             |   92 +-
 gcc/tree-profile.cc                    |   11 +-
 20 files changed, 4060 insertions(+), 17 deletions(-)
 create mode 100644 gcc/path-coverage.cc
 create mode 100644 gcc/prime-paths.cc
 create mode 100644 gcc/testsuite/g++.dg/gcov/gcov-22.C
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-29.c

Message ID	20240711071042.2484895-2-j@lambda.is
State	New
Headers	show Return-Path: <gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org> X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=kolabnow.com header.i=@kolabnow.com header.a=rsa-sha256 header.s=dkim20240523 header.b=gXL+2FgL; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WKQt74pxkz1xpd for <incoming@patchwork.ozlabs.org>; Thu, 11 Jul 2024 17:13:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C55933861027 for <incoming@patchwork.ozlabs.org>; Thu, 11 Jul 2024 07:13:01 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx.kolabnow.com (mx.kolabnow.com [212.103.80.155]) by sourceware.org (Postfix) with ESMTPS id 855833861809 for <gcc-patches@gcc.gnu.org>; Thu, 11 Jul 2024 07:10:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 855833861809 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=lambda.is Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=lambda.is ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 855833861809 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=212.103.80.155 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720681866; cv=none; b=ZDLR6Zi+KK3fBrJ4CQBvEz6MbuKIYL7J5jEiXrMZNupuyk3wjxsFo+FyuJYDXKePpyAMebg/+U2VGUxVEeQnlSU08O+1TCh5vtJR94Zc2BJpE43mDqH+k5IlHRnrOnRekL9yxmq0EQe+UY1T3W26JWT4m0+Jl17rXdsAfJENfrQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720681866; c=relaxed/simple; bh=GK2Cr5h4bGHwYbTfLNgtuFyi4J9XFiBlrepSUme4GRk=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=bTJCW34VaoCoT2mXCkqGhsLY4NWHYooTCFuaq1Pvq7SOA4jpdAmt9r1kF9C+aJGB7dKCAlqYlmq/zxBfC67XCs0+dyWRIvzNFzfJQNKkTx1cjt0UvfZi7ATmRBP3a/dEKzk9FgdXXOdTiHNO77dEbIb4+QyO6XFBCY8wxGG6yGY= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from localhost (unknown [127.0.0.1]) by mx.kolabnow.com (Postfix) with ESMTP id 925D220E5A80; Thu, 11 Jul 2024 09:10:57 +0200 (CEST) Authentication-Results: ext-mx-out011.mykolab.com (amavis); dkim=pass (2048-bit key) reason="pass (just generated, assumed good)" header.d=kolabnow.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kolabnow.com; h= content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:date:subject:subject:from:from:received :received:received; s=dkim20240523; t=1720681851; x=1722496252; bh=MzT11zqYDOWzw/4PWPo8c9ugbIQ7NRiQBOSZHVakW90=; b=gXL+2FgL0iCJ 02zZbEwY0JfU3zp1ecrKDe6h4pb2gPvugVw9W6P8hcee1809/+tpp9NdRg9v/Eui wwyJ0RgiGe7USW3PPaSkx8QLt7NxtM053m0mZ9yJCfHJF4C7iJyWFZt5mFyis9qb 32QGXT0EempWHoEmW+vbui3sSJdzgjhLXJ9nTWdQWo88FNAdo3zLI0z6H07DhRTB Puh1BYWYO0DHGRZZtBFHjBrRIzC97QsN7U5S1kEWTN1xbowYDzPX1cnYHhFrGejg zFiv62cTM8KFx+jh4Qwsq59e4dnsbsE3JKNKzAMg42sgObmfzRk+94+bl9dZrtZV mxOW+5LiLw== X-Virus-Scanned: amavis at mykolab.com X-Spam-Score: -0.999 X-Spam-Level: X-Spam-Status: No, score=-12.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 Received: from mx.kolabnow.com ([127.0.0.1]) by localhost (ext-mx-out011.mykolab.com [127.0.0.1]) (amavis, port 10024) with ESMTP id p3X7kv1AJGtr; Thu, 11 Jul 2024 09:10:51 +0200 (CEST) Received: from int-mx009.mykolab.com (unknown [10.9.13.9]) by mx.kolabnow.com (Postfix) with ESMTPS id 73A3120E2EE4; Thu, 11 Jul 2024 09:10:51 +0200 (CEST) Received: from ext-subm010.mykolab.com (unknown [10.9.6.10]) by int-mx009.mykolab.com (Postfix) with ESMTPS id 3A2A420AB036; Thu, 11 Jul 2024 09:10:51 +0200 (CEST) From: =?utf-8?q?J=C3=B8rgen_Kvalsvik?= <j@lambda.is> To: gcc-patches@gcc.gnu.org Cc: hubicka@ucw.cz, =?utf-8?q?J=C3=B8rgen_Kvalsvik?= <j@lambda.is> Subject: [PATCH 2/2] Prime path coverage in gcc/gcov Date: Thu, 11 Jul 2024 09:10:42 +0200 Message-Id: <20240711071042.2484895-2-j@lambda.is> In-Reply-To: <20240711071042.2484895-1-j@lambda.is> References: <20240711071042.2484895-1-j@lambda.is> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list <gcc-patches.gcc.gnu.org> List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe> List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help> List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe> Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org
Series	[1/2] gcov: Cache source files \| expand [1/2] gcov: Cache source files [2/2] Prime path coverage in gcc/gcov

[2/2] Prime path coverage in gcc/gcov

Commit Message

Patch