diff mbox series

[21/22] Walk the cfg in topological order, not depth-first

Message ID 20231004123921.634024-22-j@lambda.is
State Unresolved
Headers
Series [01/22] Add condition coverage profiling |

Checks

Context Check Description
snail/gcc-patch-check warning Git am fail log

Commit Message

Jørgen Kvalsvik Oct. 4, 2023, 12:39 p.m. UTC 
  Depth first order is insufficient to process expressions in the right
order when there are setjmps in optimized builds. This would create
complex paths from the root past conditions and into the middle of
boolean expressions. Traversing the graph in topological order restores
the expectation that expressions will be processed top-down.
---
 gcc/testsuite/gcc.misc-tests/gcov-23.c | 26 ++++++++++++++++++++++++++
 gcc/tree-profile.cc                    |  1 +
 2 files changed, 27 insertions(+)

Comments

Jørgen Kvalsvik Oct. 4, 2023, 3:24 p.m. UTC | #1 
On 04/10/2023 21:39, Jørgen Kvalsvik wrote:
> Depth first order is insufficient to process expressions in the right
> order when there are setjmps in optimized builds. This would create
> complex paths from the root past conditions and into the middle of
> boolean expressions. Traversing the graph in topological order restores
> the expectation that expressions will be processed top-down.
> ---
>   gcc/testsuite/gcc.misc-tests/gcov-23.c | 26 ++++++++++++++++++++++++++
>   gcc/tree-profile.cc                    |  1 +
>   2 files changed, 27 insertions(+)
> 
> diff --git a/gcc/testsuite/gcc.misc-tests/gcov-23.c b/gcc/testsuite/gcc.misc-tests/gcov-23.c
> index 856e97f5088..e5b56a5aa44 100644
> --- a/gcc/testsuite/gcc.misc-tests/gcov-23.c
> +++ b/gcc/testsuite/gcc.misc-tests/gcov-23.c
> @@ -1,5 +1,8 @@
>   /* { dg-options "-fprofile-conditions -ftest-coverage -O2 -c" } */
>   
> +#include <setjmp.h>
> +jmp_buf buf;
> +
>   int id (int);
>   int idp (int *);
>   int err;
> @@ -120,4 +123,27 @@ mcdc003 (const char *locale)
>       return 1;
>   }
>   
> +/* Adapted from jxl 0.8.2 lib/extras/dec/apng.cc processing_start ().
> +   This created a graph where depth-first traversal of the CFG would not
> +   process nodes in the wrong order (the extra control inserted from setjmp
> +   created a path of complexes from root to !b without going through !a).
> +
> +    This only happened under optimization.  */
> +int
> +mcdc004 (int a, int b)
> +{
> +    a = id (a);
> +    b = id (b);
> +
> +    if (a || b) /* conditions(0/4) true(0 1) false(0 1) */
> +		/* conditions(end) */
> +	return 1;
> +
> +    if (setjmp (buf)) /* conditions(0/2) true(0) false(0) */
> +		      /* conditions(end) */
> +	return 1;
> +
> +    return 0;
> +}
> +
>   /* { dg-final { run-gcov conditions { --conditions gcov-23.c } } } */
> diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc
> index d1d7265cd1c..8bf280dc018 100644
> --- a/gcc/tree-profile.cc
> +++ b/gcc/tree-profile.cc
> @@ -1045,6 +1045,7 @@ find_conditions (struct function *fn)
>       int n = dfs_enumerate_from (entry, 0, yes, dfs.address (), nblocks, exit);
>       dfs.truncate (n);
>       make_index_map (dfs, nblocks, ctx.B1, ctx.index_map);
> +    dfs.sort (cmp_index_map, &ctx.index_map);
>   
>       /* Visit all reachable nodes and collect conditions.  DFS order is
>          important so the first node of a boolean expression is visited first

This test fails the build because it missed this change:

 From ef01096021841bc3335aa1e80f0e3e75be9b24a2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=B8rgen=20Kvalsvik?= <j@lambda.is>
Date: Thu, 5 Oct 2023 00:14:53 +0900
Subject: [PATCH] Make right operand function to keep 2-term expr

If this is just the variable and not the function call, the comparsion
gets optimized to a|b which reduces the number of conditions and causes
the counting to fail.

The counting is not really an interesting part of this test, verifying
that it doesn't crash is, but it's nice when the numbers line up. An
alternative is to accept the strength reduction and count it as a 1-term
expression instead.
---
  gcc/testsuite/gcc.misc-tests/gcov-23.c | 4 ++--
  1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/gcc/testsuite/gcc.misc-tests/gcov-23.c 
b/gcc/testsuite/gcc.misc-tests/gcov-23.c
index e5b56a5aa44..98e692fcd01 100644
--- a/gcc/testsuite/gcc.misc-tests/gcov-23.c
+++ b/gcc/testsuite/gcc.misc-tests/gcov-23.c
@@ -135,8 +135,8 @@ mcdc004 (int a, int b)
      a = id (a);
      b = id (b);

-    if (a || b) /* conditions(0/4) true(0 1) false(0 1) */
-               /* conditions(end) */
+    if (a || id (b)) /* conditions(0/4) true(0 1) false(0 1) */
+                    /* conditions(end) */
         return 1;

      if (setjmp (buf)) /* conditions(0/2) true(0) false(0) */
diff mbox series

Patch

diff --git a/gcc/testsuite/gcc.misc-tests/gcov-23.c b/gcc/testsuite/gcc.misc-tests/gcov-23.c
index 856e97f5088..e5b56a5aa44 100644
--- a/gcc/testsuite/gcc.misc-tests/gcov-23.c
+++ b/gcc/testsuite/gcc.misc-tests/gcov-23.c
@@ -1,5 +1,8 @@ 
 /* { dg-options "-fprofile-conditions -ftest-coverage -O2 -c" } */
 
+#include <setjmp.h>
+jmp_buf buf;
+
 int id (int);
 int idp (int *);
 int err;
@@ -120,4 +123,27 @@  mcdc003 (const char *locale)
     return 1;
 }
 
+/* Adapted from jxl 0.8.2 lib/extras/dec/apng.cc processing_start ().
+   This created a graph where depth-first traversal of the CFG would not
+   process nodes in the wrong order (the extra control inserted from setjmp
+   created a path of complexes from root to !b without going through !a).
+
+    This only happened under optimization.  */
+int
+mcdc004 (int a, int b)
+{
+    a = id (a);
+    b = id (b);
+
+    if (a || b) /* conditions(0/4) true(0 1) false(0 1) */
+		/* conditions(end) */
+	return 1;
+
+    if (setjmp (buf)) /* conditions(0/2) true(0) false(0) */
+		      /* conditions(end) */
+	return 1;
+
+    return 0;
+}
+
 /* { dg-final { run-gcov conditions { --conditions gcov-23.c } } } */
diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc
index d1d7265cd1c..8bf280dc018 100644
--- a/gcc/tree-profile.cc
+++ b/gcc/tree-profile.cc
@@ -1045,6 +1045,7 @@  find_conditions (struct function *fn)
     int n = dfs_enumerate_from (entry, 0, yes, dfs.address (), nblocks, exit);
     dfs.truncate (n);
     make_index_map (dfs, nblocks, ctx.B1, ctx.index_map);
+    dfs.sort (cmp_index_map, &ctx.index_map);
 
     /* Visit all reachable nodes and collect conditions.  DFS order is
        important so the first node of a boolean expression is visited first