[Bug sanitizer/108880] New: slow compilation with "-fsanitize=undefined"

[Bug sanitizer/108880] New: slow compilation with "-fsanitize=undefined"

[qrzhang at gatech dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

            Bug ID: 108880
           Summary: slow compilation with "-fsanitize=undefined"
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: sanitizer
          Assignee: unassigned at gcc dot gnu.org
          Reporter: qrzhang at gatech dot edu
                CC: dodji at gcc dot gnu.org, dvyukov at gcc dot gnu.org,
                    jakub at gcc dot gnu.org, kcc at gcc dot gnu.org, marxin at gcc dot gnu.org
  Target Milestone: ---

gcc-10 works fine.

$ time gcc-10 -fsanitize=undefined  abc.c

real    0m0.081s


$ time gcc-11 -fsanitize=undefined  abc.c

real    0m7.045s

$ time gcc-trunk -fsanitize=undefined  abc.c

real    0m10.346s

$ gcc-trunk -v
gcc version 13.0.1 20230218 (experimental) [master r13-6132-g32b5875c911] (GCC)


$ cat abc.c
long a;
short b, e;
char c;
int d, f, g;
void h() {
  int i;
  f &= i ^= (((g &= 0 / d / d % 8 << 0 << 2) % a >> e) / c >> b) / 1 % 8 << 3;
}
void main() {}

[Bug sanitizer/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |10.5
            Summary|slow compilation with       |[11/12/13 Regression] slow
                   |"-fsanitize=undefined"      |compilation with
                   |                            |"-fsanitize=undefined"
           Keywords|                            |compile-time-hog

[Bug sanitizer/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|slow compilation with       |[11/12/13 Regression] slow
                   |"-fsanitize=undefined"      |compilation with
                   |                            |"-fsanitize=undefined"
   Target Milestone|10.5                        |11.4

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note with -fdump-tree-all it times out too.

[Bug sanitizer/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
 phase parsing                      :   7.10 (100%)   0.02 (100%)   7.32 ( 99%)
  216k ( 11%)

[Bug sanitizer/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
It is still fast with the C++ front-end.

It is also still fast with -std=gnu90 in GCC 11+.

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-02-22
            Version|unknown                     |13.0
          Component|sanitizer                   |c

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
It's not only "slow", it also produces a gigantic executable, the .original
dump was 7.1GB when I stopped the compilation ...

The culprit is c_genericize calling c_genericize_control_r which must somehow
do the ubsan instrumentation as well.

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Started with r11-3299:

commit cba079f354a55363916759f6f186f92c5616b98a
Author: Sandra Loosemore <sandra@codesourcery.com>
Date:   Sat Sep 19 07:32:35 2020 -0700

    Move loop and switch tree data structures from cp/ to c-family/.

    This patch moves the definitions for DO_STMT, FOR_STMT, WHILE_STMT,
    SWITCH_STMT, BREAK_STMT, and CONTINUE_STMT from the C++ front end to
    c-family.  This includes the genericizers, pretty-printers, and dump
    support as well as the tree definitions and accessors.  Some related
    code for OMP_FOR and similar OMP constructs is also moved.

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #6 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
FWIW, -fsanitize=signed-integer-overflow,shift seems to be enough to trigger
the runaway compilation.

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #7 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
The C90/C99 difference is due to ubsan_instrument_shift:

193   /* For signed x << y, in C99 and later, the following:
194      (unsigned) x >> (uprecm1 - y)
195      if non-zero, is undefined.  */
196   else if (code == LSHIFT_EXPR && flag_isoc99 && cxx_dialect < cxx11)
197     {
198       tree x = fold_build2 (MINUS_EXPR, op1_utype, uprecm1,
199                             fold_convert (op1_utype, unshare_expr (op1)));

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #8 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
We generate HUGE trees for the div sanitization, but I notice that
c_genericize_control_r doesn't use pset, like cp_genericize_r does.  So I think
the fix would be to add a hash_set to c_genericize_control_r.

Indeed, if I remove p_set->add (*stmt_p); in cp_genericize_r, the compilation
with cc1plus also takes around 10s.

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |mpolacek at gcc dot gnu.org

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> It's not only "slow", it also produces a gigantic executable, the .original
> dump was 7.1GB when I stopped the compilation ...

Well, original dump for deeply nested SAVE_EXPRs is pretty unusable, even when
the actual trees are fairly small, because it prints each SAVE_EXPR in full.
If we wanted to avoid that, we'd need to use during the printing some hash
table on which SAVE_EXPRs we have printed already and print some id for them
and print just that id rather than full content next time we see it.  Or
perhaps trigger that behavior when we see deeper SAVE_EXPR nesting.

> The culprit is c_genericize calling c_genericize_control_r which must
> somehow do the ubsan instrumentation as well.

As Marek said, on the C++ FE side this is handled by cp-gimplify.cc using a
pset on its own and not trying to genericize a control stmt which has been
handled already (e.g. when seeing it again in another SAVE_EXPR), or even
SAVE_EXPRs that have been handled already.
So, adding another pset that would be used also for C++ would be a waste.
Now, the C FE in c-gimplify.cc has:
      walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
                                    c_genericize_control_r, NULL);
so it effectively already creates a pset.
Thus, I think we should replace this walk_tree_without_duplicates with a new
pset + walk_tree, pass &pset twice - as pset and data and in
c_genericize_control_r don't walk again what we've already walked.
which

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #10 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Another simple patch is

--- a/gcc/c-family/c-gimplify.cc
+++ b/gcc/c-family/c-gimplify.cc
@@ -516,7 +516,7 @@ c_genericize_control_stmt (tree *stmt_p, int
*walk_subtrees, void *data,
          tree t = tsi_stmt (i);
          if (TREE_CODE (t) != DEBUG_BEGIN_STMT && nondebug_stmts < 2)
        nondebug_stmts++;
-         walk_tree_1 (tsi_stmt_ptr (i), func, data, NULL, lh);
+         walk_tree_without_duplicates_1 (tsi_stmt_ptr (i), func, data, lh);
          if (TREE_CODE (t) != DEBUG_BEGIN_STMT
          && (nondebug_stmts > 1 || TREE_SIDE_EFFECTS (tsi_stmt (i))))
        clear_side_effects = false;

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Marek Polacek from comment #10)
> Another simple patch is
> 
> --- a/gcc/c-family/c-gimplify.cc
> +++ b/gcc/c-family/c-gimplify.cc
> @@ -516,7 +516,7 @@ c_genericize_control_stmt (tree *stmt_p, int
> *walk_subtrees, void *data,
>           tree t = tsi_stmt (i);
>           if (TREE_CODE (t) != DEBUG_BEGIN_STMT && nondebug_stmts < 2)
>         nondebug_stmts++;
> -         walk_tree_1 (tsi_stmt_ptr (i), func, data, NULL, lh);
> +         walk_tree_without_duplicates_1 (tsi_stmt_ptr (i), func, data, lh);
>           if (TREE_CODE (t) != DEBUG_BEGIN_STMT
>           && (nondebug_stmts > 1 || TREE_SIDE_EFFECTS (tsi_stmt (i))))
>         clear_side_effects = false;

But that creates another pset, this time another one for each statement in each
STATEMENT_LIST seen.  That would be terribly expensive.
While the cp_genericize_r pset is just one for the whole function, the one used
by
walk_tree_without_duplicates for C is also one for the whole function.

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #12 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Sure, it worked for the testcase because the STATEMENT_LIST only had two stmts.
 I'm testing:

--- a/gcc/c-family/c-gimplify.cc
+++ b/gcc/c-family/c-gimplify.cc
@@ -516,7 +516,8 @@ c_genericize_control_stmt (tree *stmt_p, int
*walk_subtrees, void *data,
          tree t = tsi_stmt (i);
          if (TREE_CODE (t) != DEBUG_BEGIN_STMT && nondebug_stmts < 2)
        nondebug_stmts++;
-         walk_tree_1 (tsi_stmt_ptr (i), func, data, NULL, lh);
+         walk_tree_1 (tsi_stmt_ptr (i), func, data,
+              static_cast<hash_set<tree> *>(data), lh);
          if (TREE_CODE (t) != DEBUG_BEGIN_STMT
          && (nondebug_stmts > 1 || TREE_SIDE_EFFECTS (tsi_stmt (i))))
        clear_side_effects = false;
@@ -572,8 +573,9 @@ c_genericize (tree fndecl)
       bc_state_t save_state;
       push_cfun (DECL_STRUCT_FUNCTION (fndecl));
       save_bc_state (&save_state);
-      walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl),
-                   c_genericize_control_r, NULL);
+      hash_set<tree> pset;
+      walk_tree (&DECL_SAVED_TREE (fndecl), c_genericize_control_r, &pset,
+        &pset);
       restore_bc_state (&save_state);
       pop_cfun ();
     }

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Marek Polacek from comment #12)
> Sure, it worked for the testcase because the STATEMENT_LIST only had two
> stmts.  I'm testing:
> 
> --- a/gcc/c-family/c-gimplify.cc
> +++ b/gcc/c-family/c-gimplify.cc
> @@ -516,7 +516,8 @@ c_genericize_control_stmt (tree *stmt_p, int
> *walk_subtrees, void *data,
>           tree t = tsi_stmt (i);
>           if (TREE_CODE (t) != DEBUG_BEGIN_STMT && nondebug_stmts < 2)
>         nondebug_stmts++;
> -         walk_tree_1 (tsi_stmt_ptr (i), func, data, NULL, lh);
> +         walk_tree_1 (tsi_stmt_ptr (i), func, data,
> +              static_cast<hash_set<tree> *>(data), lh);

I'd limit this change to !c_dialect_cxx () only, I'm afraid if it is done
for C++ too, then cp_genericize_r won't then walk into those trees later on and
could avoid replacing there something important.  While for C, there is
walk_tree solely for the purposes of c_genericize_control* and nothing else.
To avoid testing it in every iteration you could have a hash_set<tree> *pset
temporary initialized based on c_dialect_cxx () to NULL or data and then just
use it in the loop.

>           if (TREE_CODE (t) != DEBUG_BEGIN_STMT
>           && (nondebug_stmts > 1 || TREE_SIDE_EFFECTS (tsi_stmt (i))))
>         clear_side_effects = false;

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #14 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #13)
> (In reply to Marek Polacek from comment #12)
> > Sure, it worked for the testcase because the STATEMENT_LIST only had two
> > stmts.  I'm testing:
> > 
> > --- a/gcc/c-family/c-gimplify.cc
> > +++ b/gcc/c-family/c-gimplify.cc
> > @@ -516,7 +516,8 @@ c_genericize_control_stmt (tree *stmt_p, int
> > *walk_subtrees, void *data,
> >           tree t = tsi_stmt (i);
> >           if (TREE_CODE (t) != DEBUG_BEGIN_STMT && nondebug_stmts < 2)
> >         nondebug_stmts++;
> > -         walk_tree_1 (tsi_stmt_ptr (i), func, data, NULL, lh);
> > +         walk_tree_1 (tsi_stmt_ptr (i), func, data,
> > +              static_cast<hash_set<tree> *>(data), lh);
> 
> I'd limit this change to !c_dialect_cxx () only, I'm afraid if it is done
> for C++ too, then cp_genericize_r won't then walk into those trees later on
> and could avoid replacing there something important.  While for C, there is
> walk_tree solely for the purposes of c_genericize_control* and nothing else.
> To avoid testing it in every iteration you could have a hash_set<tree> *pset
> temporary initialized based on c_dialect_cxx () to NULL or data and then
> just use it in the loop.

Yeah, in C++ I get a crash in check_complete_insertion anyway.  I don't really
see why but best to limit it to C.

[Bug c/108880] [11/12/13 Regression] slow compilation with "-fsanitize=undefined"

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #15 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Marek Polacek <mpolacek@gcc.gnu.org>:

https://gcc.gnu.org/g:1370014f2ea02ec185cf1199027575916f79fe63

commit r13-6290-g1370014f2ea02ec185cf1199027575916f79fe63
Author: Marek Polacek <polacek@redhat.com>
Date:   Wed Feb 22 15:17:03 2023 -0500

    c-family: avoid compile-time-hog in c_genericize [PR108880]

    This fixes a compile-time hog with UBSan.  This only happened in cc1 but
    not cc1plus.  The problem is ultimately that c_genericize_control_stmt/
    STATEMENT_LIST -> walk_tree_1 doesn't use a hash_set to remember visited
    nodes, so it kept on recursing for a long time.  We should be able to
    use the pset that c_genericize created.  We just need to use walk_tree
    instead of walk_tree_w_d so that the pset is explicit.

            PR c/108880

    gcc/c-family/ChangeLog:

            * c-gimplify.cc (c_genericize_control_stmt) <case STATEMENT_LIST>:
Pass
            pset to walk_tree_1.
            (c_genericize): Call walk_tree with an explicit pset.

    gcc/testsuite/ChangeLog:

            * c-c++-common/ubsan/pr108880.c: New test.

[Bug c/108880] [11/12 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13 Regression] slow  |[11/12 Regression] slow
                   |compilation with            |compilation with
                   |"-fsanitize=undefined"      |"-fsanitize=undefined"

--- Comment #16 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Fixed on trunk so far.

[Bug c/108880] [11/12 Regression] slow compilation with "-fsanitize=undefined"

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

--- Comment #17 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Marek Polacek
<mpolacek@gcc.gnu.org>:

https://gcc.gnu.org/g:6ab4c8759754f34f5285924652238c829960cd4c

commit r12-9218-g6ab4c8759754f34f5285924652238c829960cd4c
Author: Marek Polacek <polacek@redhat.com>
Date:   Wed Feb 22 15:17:03 2023 -0500

    c-family: avoid compile-time-hog in c_genericize [PR108880]

    This fixes a compile-time hog with UBSan.  This only happened in cc1 but
    not cc1plus.  The problem is ultimately that c_genericize_control_stmt/
    STATEMENT_LIST -> walk_tree_1 doesn't use a hash_set to remember visited
    nodes, so it kept on recursing for a long time.  We should be able to
    use the pset that c_genericize created.  We just need to use walk_tree
    instead of walk_tree_w_d so that the pset is explicit.

            PR c/108880

    gcc/c-family/ChangeLog:

            * c-gimplify.cc (c_genericize_control_stmt) <case STATEMENT_LIST>:
Pass
            pset to walk_tree_1.
            (c_genericize): Call walk_tree with an explicit pset.

    gcc/testsuite/ChangeLog:

            * c-c++-common/ubsan/pr108880.c: New test.

    (cherry picked from commit 1370014f2ea02ec185cf1199027575916f79fe63)

[Bug c/108880] [11 Regression] slow compilation with "-fsanitize=undefined"

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108880

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED
            Summary|[11/12 Regression] slow     |[11 Regression] slow
                   |compilation with            |compilation with
                   |"-fsanitize=undefined"      |"-fsanitize=undefined"

--- Comment #18 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Fixed.