* PR c++/5504: Optimization breaks wei-ku-1 from blitz @ 2002-03-25 21:41 Diego Novillo 2002-04-03 18:04 ` Jason Merrill 2002-04-05 15:08 ` Jason Merrill 0 siblings, 2 replies; 8+ messages in thread From: Diego Novillo @ 2002-03-25 21:41 UTC (permalink / raw) To: Jason Merrill; +Cc: gcc, gcc-prs Jason, Although the PR indicates that g++ ICEs, the program actually compiles. However, it takes about 7 hours and cc1plus grows to ~650 Mb. The problem seems to be in the expansion of EH cleanups. I've been comparing gcc 3.0.4 with the 3.1 branch. This is what I found so far: - Both compilers seem to generate roughly the same number of trees. They both grow to about 47 Mb right before the call to expand_stmt() in semantics.c:expand_body(). - However, when expand_stmt() is called to expand the body of main(), the 3.1 compiler grows to 415Mb, while the 3.0.4. compiler grows to about 53 Mb. - The difference is in the calls to expand_eh_region_end_cleanup() The 3.0.4 compiler calls it 76 times. The 3.1 compiler calls it 59,212 times. Not surprisingly, we spend no more than a couple of minutes generating the initial RTL, and 7 hours trying to optimize it. We seem to be generating mostly fluff because the final .s file doesn't look overly large (a couple of Mb, IIRC). - The program seems to compile fine with -fno-exceptions. Jakub tracked the problem to your destructor cleanup patch from Dec01: http://gcc.gnu.org/ml/gcc-patches/2001-12/msg01532.html I don't know enough C++ to determine whether this is to be expected or not. The test case is rather large, so it may well be that 3.0.4 was not doing the right thing. Any ideas on what to try next? Thanks. Diego. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz 2002-03-25 21:41 PR c++/5504: Optimization breaks wei-ku-1 from blitz Diego Novillo @ 2002-04-03 18:04 ` Jason Merrill 2002-04-03 19:23 ` Diego Novillo 2002-04-05 15:08 ` Jason Merrill 1 sibling, 1 reply; 8+ messages in thread From: Jason Merrill @ 2002-04-03 18:04 UTC (permalink / raw) To: Diego Novillo; +Cc: gcc, gcc-prs Interesting. I'll take over this PR, if you don't mind. Jason ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz 2002-04-03 18:04 ` Jason Merrill @ 2002-04-03 19:23 ` Diego Novillo 0 siblings, 0 replies; 8+ messages in thread From: Diego Novillo @ 2002-04-03 19:23 UTC (permalink / raw) To: Jason Merrill; +Cc: gcc, gcc-prs On Wed, 2002-04-03 at 20:57, Jason Merrill wrote: > Interesting. I'll take over this PR, if you don't mind. > Sure. Thanks. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz 2002-03-25 21:41 PR c++/5504: Optimization breaks wei-ku-1 from blitz Diego Novillo 2002-04-03 18:04 ` Jason Merrill @ 2002-04-05 15:08 ` Jason Merrill 2002-04-05 16:14 ` Jason Merrill ` (2 more replies) 1 sibling, 3 replies; 8+ messages in thread From: Jason Merrill @ 2002-04-05 15:08 UTC (permalink / raw) To: Richard Henderson, Diego Novillo; +Cc: gcc, gcc-gnats, Jason Merrill This seems to be a problem with combinatorial explosion of EH regions. The explosion itself is a necessary consequence of the use of expression templates, which produces a lot of little recursive functions inlined into one another, ideally optimizing out to very simple code. In this case, since IndexPlaceholder has a destructor, all of the expression template classes parameterized on it need to call it. As the expression (A = 11111 + ...) grows, the classes involved get more and more complicated. We used to handle cleanups in destructors by manually calling the base and member destructors from finish_function. My patch changed this to use normal cleanups for destroying bases and members, in order to get proper semantics if the destructor itself or one of the subobject destructors throw; previously we would have skipped the other subobject destructors. This change is necessary for correctness. But as a result, we now have a lot more EH regions than we used to. Counting calls to expand_eh_region_end_cleanup, I see: With one term, 67; two, 379; three, 1657; four, 6779. It's not entirely clear to me that this explosion is due to the nature of expression templates, but I think it is. And the vast majority of these aren't needed; the function ends up with 43 entries in the action table. For the four term expression, the maximal expression template class looks like _bz_ArrayExpr <blitz::_bz_ArrayExprOp <blitz::_bz_ArrayExpr <blitz::_bz_ArrayExprOp <blitz::_bz_ArrayExpr <blitz::_bz_ArrayExprOp <blitz::_bz_ArrayExprConstant<int>, blitz::_bz_ArrayExpr <blitz::_bz_ArrayExprOp <blitz::_bz_ArrayExprConstant<int>, blitz::IndexPlaceholder<0>, blitz::Multiply<int, int> > >, blitz::Add<int, int> > >, blitz::_bz_ArrayExpr <blitz::_bz_ArrayExprOp <blitz::_bz_ArrayExprConstant<int>, blitz::IndexPlaceholder<1>, blitz::Multiply<int, int> > >, blitz::Add<int, int> > >, blitz::_bz_ArrayExpr <blitz::_bz_ArrayExprOp <blitz::_bz_ArrayExprConstant<int>, blitz::IndexPlaceholder<2>, blitz::Multiply<int, int> > >, blitz::Add<int, int> > > which itself involves 15 destructor calls, for the IndexPlaceholder members and all the types that (perhaps indirectly) contain one. Each of these is expanded twice, once for the normal flow case, and once for the EH case. If fully inlined, destroying one temporary of this type adds 30 exception regions to the list. And such temporaries are created every time the expression object is passed by value, as it uniformly is. Unfortunately, the backend doesn't seem to be prepared to handle this number of EH regions; many of the data structures can only be searched linearly. For the four-term case, gprof shows that we're spending the vast majority of our time traversing them: % cumulative self self total time seconds seconds calls ms/call ms/call name 37.35 211.09 211.09 110832 1.90 2.32 maybe_remove_eh_handler 26.59 361.36 150.27 344409 0.44 0.44 in_expr_list_p 10.00 417.89 56.53 305399 0.19 0.19 next_nonnote_insn 6.59 455.11 37.22 28896 1.29 1.29 remove_exception_handler_label ... where the time in in_expr_list_p comes from the call in can_delete_label_p to see if a label is in exception_handler_labels. with -O0 -finline, it looks a bit different: 28.70 106.27 106.27 100111 1.06 1.30 maybe_remove_eh_handler 20.71 182.94 76.67 306819 0.25 0.25 in_expr_list_p 12.38 228.77 45.83 92573 0.50 0.50 pop_temp_slots 7.12 255.12 26.35 56221 0.47 0.47 free_temp_slots 5.03 273.73 18.61 28872 0.64 0.64 remove_exception_handler_label Here again we're running into linear traversals of lists that got larger than we ever expected, but this time it's the list of temp slots. I'm not sure what to do about this. We need to support this sort of code; this is a very common C++ programming idiom. Obvious ways to improve performance would be: Adjust the EH data structures so that we can do more efficient searches in them. Try to avoid creating EH regions that will just be deleted again. If nothing in the region can throw, we can discard it at expand_eh_region_end time. For 3.1, one option would be to go back to doing destructor cleanups only on the normal flow path; this would break EH semantics again for this case, but that would not be a regression and I don't think I've ever seen a bug report about it in past releases. Thoughts? Jason ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: c++/5504: Optimization breaks wei-ku-1 from blitz 2002-04-05 15:08 ` Jason Merrill @ 2002-04-05 16:14 ` Jason Merrill 2002-04-06 15:36 ` PR " Mark Mitchell 2002-04-09 0:20 ` Richard Henderson 2 siblings, 0 replies; 8+ messages in thread From: Jason Merrill @ 2002-04-05 16:14 UTC (permalink / raw) To: Richard Henderson; +Cc: Diego Novillo, gcc, gcc-gnats >>>>> "Jason" == Jason Merrill <jason@redhat.com> writes: > For 3.1, one option would be to go back to doing destructor cleanups only > on the normal flow path; this would break EH semantics again for this case, > but that would not be a regression and I don't think I've ever seen a bug > report about it in past releases. I take it back; PR c++/411 is for this bug. We may still want to do this, though. Jason ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz 2002-04-05 15:08 ` Jason Merrill 2002-04-05 16:14 ` Jason Merrill @ 2002-04-06 15:36 ` Mark Mitchell 2002-04-06 23:38 ` Richard Henderson 2002-04-09 0:20 ` Richard Henderson 2 siblings, 1 reply; 8+ messages in thread From: Mark Mitchell @ 2002-04-06 15:36 UTC (permalink / raw) To: Jason Merrill, Richard Henderson, Diego Novillo; +Cc: gcc, gcc-gnats > For 3.1, one option would be to go back to doing destructor cleanups only > on the normal flow path; this would break EH semantics again for this > case, but that would not be a regression and I don't think I've ever seen > a bug report about it in past releases. I think this is the most practical solution under the circumstances. At some point, we clearly need to explore the other alternatives you suggest. Thanks, -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz 2002-04-06 15:36 ` PR " Mark Mitchell @ 2002-04-06 23:38 ` Richard Henderson 0 siblings, 0 replies; 8+ messages in thread From: Richard Henderson @ 2002-04-06 23:38 UTC (permalink / raw) To: Mark Mitchell; +Cc: Jason Merrill, Diego Novillo, gcc, gcc-gnats On Sat, Apr 06, 2002 at 02:48:54PM -0800, Mark Mitchell wrote: > I think this is the most practical solution under the circumstances. Hold off a bit. I don't think either of the solutions that Jason suggests are hard to implement. I'd certainly prefer a solution that doesn't re-introduce bugs... r~ ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz 2002-04-05 15:08 ` Jason Merrill 2002-04-05 16:14 ` Jason Merrill 2002-04-06 15:36 ` PR " Mark Mitchell @ 2002-04-09 0:20 ` Richard Henderson 2 siblings, 0 replies; 8+ messages in thread From: Richard Henderson @ 2002-04-09 0:20 UTC (permalink / raw) To: Jason Merrill; +Cc: Diego Novillo, gcc, mark On Fri, Apr 05, 2002 at 11:34:40PM +0100, Jason Merrill wrote: > Unfortunately, the backend doesn't seem to be prepared to handle this > number of EH regions; many of the data structures can only be searched > linearly. For the four-term case, gprof shows that we're spending the vast > majority of our time traversing them: > > % cumulative self self total > time seconds seconds calls ms/call ms/call name > 37.35 211.09 211.09 110832 1.90 2.32 maybe_remove_eh_handler > 26.59 361.36 150.27 344409 0.44 0.44 in_expr_list_p > 10.00 417.89 56.53 305399 0.19 0.19 next_nonnote_insn > 6.59 455.11 37.22 28896 1.29 1.29 remove_exception_handler_label [...] > I'm not sure what to do about this. We need to support this sort of code; > this is a very common C++ programming idiom. Obvious ways to improve > performance would be: > > [1] Adjust the EH data structures so that we can do more efficient > searches in them. > [2] Try to avoid creating EH regions that will just be deleted again. > If nothing in the region can throw, we can discard it at > expand_eh_region_end time. It turns out that [2] is annoyingly difficult. FIXUP regions created by expand_cleanups want to insert code into the *parent* of a CLEANUP region, after that region has already been finalized by expand_eh_region_end. I.e. if we simply fail to create the cleanup region based on the fact that it'll never be used, we'll not have all the data structures needed to resolve the fixup region. :-( Doing [1] is within our power. I found a whole series of quadratic (or worse) operations here -- not all of them in the EH code. I'm currently testing a patch that brings the original test case to % cumulative self self total time seconds seconds calls s/call s/call name 5.14 7.34 7.34 2662100 0.00 0.00 walk_tree 4.57 13.87 6.53 701 0.01 0.01 fixup_var_refs_insns 4.30 20.01 6.14 34516896 0.00 0.00 ggc_alloc 3.20 24.58 4.57 62692969 0.00 0.00 statement_code_p 2.96 28.81 4.23 7488030 0.00 0.00 fixup_var_refs_1 2.70 32.66 3.85 77455616 0.00 0.00 add_insn expand : 207.49 (59%) usr 8.39 (68%) sys 216.25 (59%) wall parser : 38.15 (11%) usr 0.77 ( 6%) sys 38.52 (11%) wall garbage collection : 29.99 ( 9%) usr 1.31 (11%) sys 31.30 ( 9%) wall cfg construction : 18.96 ( 5%) usr 0.46 ( 4%) sys 19.56 ( 5%) wall cfg cleanup : 16.27 ( 5%) usr 0.04 ( 0%) sys 16.23 ( 4%) wall TOTAL : 351.17 12.35 363.83 I.e. we're down below 6 minutes compile time instead of 7 hours. Unfortunately, it still consumes unacceptable amounts of memory. Somewhere near 1.2GB peak. I think I can improve this by eliding some of the *code* associated with cleanup regions, even though I cannot elide the cleanup region data structure itself. I'll test the patch I have overnight and post if it succeeds. r~ ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2002-04-09 7:01 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2002-03-25 21:41 PR c++/5504: Optimization breaks wei-ku-1 from blitz Diego Novillo 2002-04-03 18:04 ` Jason Merrill 2002-04-03 19:23 ` Diego Novillo 2002-04-05 15:08 ` Jason Merrill 2002-04-05 16:14 ` Jason Merrill 2002-04-06 15:36 ` PR " Mark Mitchell 2002-04-06 23:38 ` Richard Henderson 2002-04-09 0:20 ` Richard Henderson
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).