This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] PR c++/55135


Hello,

Bug c++/55135 is another one of those almost-insane large test cases
that triggers some of the worst time complexity behavior GCC has to
offer. The attached patch doesn't actually fix anything the bug poster
complained about, but something I ran into myself while trying to
compile the file at -O0. It's a regression from older GCC releases and
a test case for which clang kicks our butts.

What happens at -O0 for this test case, is that there are 179972 EH
regions and all but 3 of them are removed in
remove_unreachable_handlers, which calls remove_eh_handler one region
at a time in a loop. Because the EH tree is almost flat (almost a
linked list), and remove_eh_handler has to look up the dead region in
the tree, this results in O(N_EH_regions^2) run time in
pass_cleanup_eh.

The solution I propose in the attached patch, is to remove all
unreachable regions in a single walk over the EH tree. This makes
remove_unreachable_handlers run in no worse than O(N_EH_regions) time.
If there are only a few regions to be removed, then this is
potentially slower than the existing algorithm, but there is already a
complete function walk in remove_unreachable_handlers and in the
non-O0 case the EH tree is usually relatively small even for large
functions. In any case, I have measured compile time on some C++ and
Java cases and there were no measurable compile time regressions at
-O1+, and a few improvements at -O0.

Bootstrapped&tested on x86_64-unknown-linux-gnu. OK for trunk?

Ciao!
Steven


gcc/
        PR c++/55135
        * except.h (remove_unreachable_eh_regions): New prototype.
        * except.c (remove_eh_handler_splicer): New function, split out
        of remove_eh_handler.
        (remove_eh_handler): Use remove_eh_handler_splicer.  Add comment
        warning about running it on many EH regions one at a time.
        (remove_unreachable_eh_regions_worker): New function, walk the
        EH tree in depth-first order and remove non-marked regions.
        (remove_unreachable_eh_regions): New function.
        * tree-eh.c (mark_reachable_handlers): New function, split out
        from remove_unreachable_handlers.
        (remove_unreachable_handlers): Use mark_reachable_handlers and
        remove_unreachable_eh_regions.
        (remove_unreachable_handlers_no_lp): Use mark_reachable_handlers
        and remove_unreachable_eh_regions.

Attachment: PR55135_O0_EH.diff.txt
Description: Text document


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]