[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952 Marek Polacek changed: What|Removed |Added CC||sshannin at gmail dot com --- Comment #8 from Marek Polacek --- *** Bug 98980 has been marked as a duplicate of this bug. ***
[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952 Jakub Jelinek changed: What|Removed |Added CC||joerg.rich...@pdv-fs.de --- Comment #7 from Jakub Jelinek --- *** Bug 89850 has been marked as a duplicate of this bug. ***
[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952
Volker Reichelt changed:
What|Removed |Added
CC||reichelt at gcc dot gnu.org
--- Comment #6 from Volker Reichelt ---
Here's a short example that shows that something exponential is going on:
struct A
{
virtual ~A() {}
A& operator<<(int) { return *this; }
};
void foo(A& a, bool b)
{
if (b)
a << 1 << 2 << 3 << 4 << 5
<< 6 << 7 << 8 << 9 << 10
<< 11 << 12 << 13 << 14 << 15;
}
Increasing the number of calls to the operator<< increases the compile
time roughly by a factor of 4 as the following table shows:
calls | compile time
--+-
10 | 0.25s
11 | 0.95s
12 | 3.7 s
13 |14.8 s
14 |59 s
15 | 234 s
For 20 calls the estimated compile time would be almost 3 days.
With any of the two options removed, the compile time for 20 calls
is way below 0.1s.
This happens since GCC 7.1.0 which introduced the "-Wduplicated-branches"
option.
[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952 --- Comment #5 from Richard Biener --- (In reply to Jakub Jelinek from comment #4) > Yeah, indeed. I'd say in this case the biggest problem is probably repeated > traversal of SAVE_EXPRs in inchash::add_expr (which BTW doesn't seem to be > something that operand_equal_p with OEP_LEXICOGRAPHICS handles). > But generally you're right, even without SAVE_EXPRs with hundreds of nested > COND_EXPRs the compile time complexity isn't tollerable either. > So, shall we before those > /* Compute the hash of the then branch. */ > inchash::hash hstate0 (0); > inchash::add_expr (thenb, hstate0); > hashval_t h0 = hstate0.end (); > > /* Compute the hash of the else branch. */ > inchash::hash hstate1 (0); > inchash::add_expr (elseb, hstate1); > hashval_t h1 = hstate1.end (); > walk thenb as well as elseb and count trees we've walked (and punt if seen > more than some constant or PARAM trees)? That could also punt if both > numbers of trees are below the limit, but different (though > inchash::add_expr as well as opernad_equal_p has some spots with STRIP_NOPS, > which we'd no longer then recognize if different). Some form of limiting would be nice. At one point I thought that maybe we should have an EXPR_HASH value sitting in the tree nodes ... but another form of caching might work here, too. Still the whole walk is too costly in extreme cases even when fixing the hashing (which as far as I understand was done to make the actual compare chepaer...) > And/or add some optional hash table for remembering SAVE_EXPRs? Though, I'd > prefer not to slow down the normal add_expr... > Shall we handle SAVE_EXPR in operand_equal_p if OEP_LEXICOGRAPHICS? Experimenting with that makes sense.
[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952 Jakub Jelinek changed: What|Removed |Added CC||mpolacek at gcc dot gnu.org --- Comment #4 from Jakub Jelinek --- Yeah, indeed. I'd say in this case the biggest problem is probably repeated traversal of SAVE_EXPRs in inchash::add_expr (which BTW doesn't seem to be something that operand_equal_p with OEP_LEXICOGRAPHICS handles). But generally you're right, even without SAVE_EXPRs with hundreds of nested COND_EXPRs the compile time complexity isn't tollerable either. So, shall we before those /* Compute the hash of the then branch. */ inchash::hash hstate0 (0); inchash::add_expr (thenb, hstate0); hashval_t h0 = hstate0.end (); /* Compute the hash of the else branch. */ inchash::hash hstate1 (0); inchash::add_expr (elseb, hstate1); hashval_t h1 = hstate1.end (); walk thenb as well as elseb and count trees we've walked (and punt if seen more than some constant or PARAM trees)? That could also punt if both numbers of trees are below the limit, but different (though inchash::add_expr as well as opernad_equal_p has some spots with STRIP_NOPS, which we'd no longer then recognize if different). And/or add some optional hash table for remembering SAVE_EXPRs? Though, I'd prefer not to slow down the normal add_expr... Shall we handle SAVE_EXPR in operand_equal_p if OEP_LEXICOGRAPHICS?
[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952 Richard Biener changed: What|Removed |Added Keywords||compile-time-hog Status|UNCONFIRMED |NEW Last reconfirmed||2017-11-13 CC||jakub at gcc dot gnu.org Ever confirmed|0 |1 --- Comment #3 from Richard Biener --- Confirmed. I suspect UBSAN creates a large number of branches and -Wduplicated-branches isn't very effective. In fact it looks quadratic given we do 128 if (warn_duplicated_branches) 129 walk_tree_without_duplicates (&DECL_SAVED_TREE (fndecl), 130 do_warn_duplicated_branches_r, NULL); and do_warn_duplicated_branches_r does itself /* Compute the hash of the then branch. */ inchash::hash hstate0 (0); inchash::add_expr (thenb, hstate0); hashval_t h0 = hstate0.end (); ... && !walk_tree_without_duplicates (&thenb, expr_from_macro_expansion_r, NULL) thus we process each tree (in COND_EXPRs) a quadratic amount of times. inchash is very likely also not avoiding walking duplicates multiple times, as SAVE_EXPR is tcc_expression it even walks those multiple times. As a band-aid I suggest to limit the depth we walk here somehow...
[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952 Ahmad Fatoum changed: What|Removed |Added Target||x86_64-pc-linux-gnu Host||x86_64-pc-linux-gnu Build||revision 253932 --- Comment #2 from Ahmad Fatoum --- I missed that --with-bugurl=http://bugs.opensuse.org/ the first time. I just built GCC's master branch (commit 179137d80882c7b6b58ee59eacf56fe6f8cc7596) and it's reproducible Using built-in specs. COLLECT_GCC=/opt/cross/bin/x86_64-pc-linux-gnu-g++ COLLECT_LTO_WRAPPER=/home/a3f/prjs/gcc/install/bin/../lib/gcc/x86_64-pc-linux-gnu/8.0.0/lto-wrapper x86_64-pc-linux-gnu-g++ (GCC) 8.0.0 2017 (experimental) Copyright (C) 2017 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
[Bug c++/82952] Hang compiling with g++ -fsanitize=undefined -Wduplicated-branches
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82952 --- Comment #1 from Ahmad Fatoum --- Created attachment 42587 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=42587&action=edit File that hangs g++ I didn't manage to reduce it by much, because of the halting problem. At least it reliably shows the problem.
