[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #16 from spop at gcc dot gnu dot org 2007-11-05 15:42 --- Subject: Bug 32540 Author: spop Date: Mon Nov 5 15:42:30 2007 New Revision: 129901 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=129901 Log: 2007-11-05 Nick Clifton [EMAIL PROTECTED] Sebastian Pop [EMAIL PROTECTED] PR tree-optimization/32540 PR tree-optimization/33922 * doc/invoke.texi: Document PARAM_MAX_PARTIAL_ANTIC_LENGTH. * tree-ssa-pre.c: Include params.h. (compute_partial_antic_aux): Use PARAM_MAX_PARTIAL_ANTIC_LENGTH to limit the maximum length of the PA set for a given block. * Makefile.in: Add a dependency upon params.h for tree-ssa-pre.c * params.def (PARAM_MAX_PARTIAL_ANTIC_LENGTH): New parameter. * gcc.dg/tree-ssa/pr32540-1.c: New. * gcc.dg/tree-ssa/pr32540-2.c: New. * gcc.dg/tree-ssa/pr33922.c: New. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/pr32540-1.c trunk/gcc/testsuite/gcc.dg/tree-ssa/pr32540-2.c trunk/gcc/testsuite/gcc.dg/tree-ssa/pr33922.c Modified: trunk/gcc/ChangeLog trunk/gcc/Makefile.in trunk/gcc/doc/invoke.texi trunk/gcc/params.def trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-pre.c -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #17 from spop at gcc dot gnu dot org 2007-11-05 15:44 --- Fixed. -- spop at gcc dot gnu dot org changed: What|Removed |Added Status|REOPENED|RESOLVED Resolution||FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #13 from sebpop at gmail dot com 2007-11-03 05:19 --- Subject: Re: [4.3 Regression] Exponential time behavior in PRE Yes, the heuristics can sometimes generate a very large number of copies to eliminate a single redundancy. This is jsut the way the standard PRE heuristics work. If you want to try to come up with a better one, you are welcome to :) What about stopping the computation when we see that there are too many values that are anticipable? Here is a patch that restores the compile time on all the reported testcases. The constant should be a param, and the default value should be higher probably. Index: tree-ssa-pre.c === --- tree-ssa-pre.c (revision 129775) +++ tree-ssa-pre.c (working copy) @@ -1847,6 +1847,13 @@ compute_partial_antic_aux (basic_block b if (block_has_abnormal_pred_edge) goto maybe_dump_sets; + /* If there are too many partially anticipatable values in the + block, phi_translate_set can take an exponential time: stop + before the translation starts. */ + if (single_succ_p (block) + bitmap_count_bits (PA_IN (single_succ (block))-expressions) 10) +goto maybe_dump_sets; + old_PA_IN = PA_IN (block); PA_OUT = bitmap_set_new (); -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #14 from sebpop at gmail dot com 2007-11-03 05:26 --- Subject: Re: [4.3 Regression] Exponential time behavior in PRE With the patch, compile time goes down also for PR33922. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #15 from sebpop at gmail dot com 2007-11-03 05:54 --- Subject: Re: [4.3 Regression] Exponential time behavior in PRE And I just saw that there is already a patch for this bug attached unfortunately to PR32575. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #10 from rguenth at gcc dot gnu dot org 2007-11-01 15:26
---
That is, the following testcase:
int f(void);
void acceptloop_th(int *t, int options) {
if (f()) options |= 0x1 0;
if (f()) options |= 0x1 1;
if (f()) options |= 0x1 2;
if (f()) options |= 0x1 3;
if (f()) options |= 0x1 4;
if (f()) options |= 0x1 5;
if (f()) options |= 0x1 6;
if (f()) options |= 0x1 7;
if (f()) options |= 0x1 8;
if (f()) options |= 0x1 9;
if (f()) options |= 0x1 10;
if (f()) options |= 0x1 11;
if (f()) options |= 0x1 12;
if (f()) options |= 0x1 13;
if (f()) options |= 0x1 14;
if (f()) options |= 0x1 15;
if (f()) options |= 0x1 16;
if (f()) options |= 0x1 17;
if (f()) options |= 0x1 18;
if (f()) options |= 0x1 19;
if (f()) options |= 0x1 20;
if (f()) options |= 0x1 21;
if (f()) options |= 0x1 22;
if (f()) options |= 0x1 23;
if (f()) options |= 0x1 24;
if (f()) options |= 0x1 25;
if (f()) options |= 0x1 26;
if (f()) *t = options;
}
it's interesting that this one is not different from the zero-initialized
options case just because PHIOPT which runs before PRE changes
bb 2:
D.1179_5 = f ();
if (D.1179_5 != 0)
goto bb 3;
else
goto bb 4;
bb 3:
bb 4:
# options_1 = PHI 0(2), 1(3)
to
bb 2:
D.1179_5 = f ();
options_1 = D.1179_5 != 0;
which then causes PHI translation to not be able to figure out the constants
(but create value expressions). With PHIOPT disabled we even perform PRE
on this testcase ;) So, take the following modified testcase as well:
int f(void);
void acceptloop_th(int *t) {
int options = 0;
if (f()) options |= 0x1 1;
if (f()) options |= 0x1 2;
if (f()) options |= 0x1 3;
if (f()) options |= 0x1 4;
if (f()) options |= 0x1 5;
if (f()) options |= 0x1 6;
if (f()) options |= 0x1 7;
if (f()) options |= 0x1 8;
if (f()) options |= 0x1 9;
if (f()) options |= 0x1 10;
if (f()) options |= 0x1 11;
if (f()) options |= 0x1 12;
if (f()) options |= 0x1 13;
if (f()) options |= 0x1 14;
if (f()) options |= 0x1 15;
if (f()) options |= 0x1 16;
if (f()) options |= 0x1 17;
if (f()) options |= 0x1 18;
if (f()) options |= 0x1 19;
if (f()) options |= 0x1 20;
if (f()) options |= 0x1 21;
if (f()) options |= 0x1 22;
if (f()) options |= 0x1 23;
if (f()) options |= 0x1 24;
if (f()) options |= 0x1 25;
if (f()) options |= 0x1 26;
if (f()) *t = options;
}
which causes an exponential number of PHI nodes to be inserted. Like for
example (shortened testcase):
bb 4:
# prephitmp.9_30 = PHI 16(13), 18(3)
# prephitmp.9_29 = PHI 24(13), 26(3)
# prephitmp.9_28 = PHI 8(13), 10(3)
# prephitmp.9_27 = PHI 20(13), 22(3)
# prephitmp.9_26 = PHI 28(13), 30(3)
# prephitmp.9_25 = PHI 12(13), 14(3)
# prephitmp.9_24 = PHI 4(13), 6(3)
# options_1 = PHI 0(13), 2(3)
# SMT.4_18 = VDEF SMT.4_17
D.1180_8 = f ();
if (D.1180_8 != 0)
goto bb 5;
else
goto bb 14;
where all the computed constants materialize! :)
How interesting.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #11 from jakub at gcc dot gnu dot org 2007-11-01 21:16 --- This isn't just a compile time hog, but sometimes (see PR33922) it creates many times bigger and far slower code as well. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #12 from dberlin at gcc dot gnu dot org 2007-11-01 21:24 --- Subject: Re: [4.3 Regression] Exponential time behavior in PRE Yes, the heuristics can sometimes generate a very large number of copies to eliminate a single redundancy. This is jsut the way the standard PRE heuristics work. If you want to try to come up with a better one, you are welcome to :) On 1 Nov 2007 21:16:45 -, jakub at gcc dot gnu dot org [EMAIL PROTECTED] wrote: --- Comment #11 from jakub at gcc dot gnu dot org 2007-11-01 21:16 --- This isn't just a compile time hog, but sometimes (see PR33922) it creates many times bigger and far slower code as well. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540 --- You are receiving this mail because: --- You are on the CC list for the bug, or are watching someone who is. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #6 from tbm at cyrius dot com 2007-10-20 08:02 --- Adding Danny to CC since this is not yet fixed. -- tbm at cyrius dot com changed: What|Removed |Added CC||dberlin at gcc dot gnu dot ||org http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #7 from rguenth at gcc dot gnu dot org 2007-10-20 10:14 --- I guess we just compute all 2**26 constants that can end up at the conditional store. And indeed, the number of 'Created value .*' in the dump matches this (modulo some constant offset). This is PPRE at work, which probably should be limited to a sub-CFG somehow. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #8 from dberlin at gcc dot gnu dot org 2007-10-20 20:49 --- Subject: Re: [4.3 Regression] Exponential time behavior in PRE We may just want to disable PPRE of constants entirely :) On 20 Oct 2007 10:14:53 -, rguenth at gcc dot gnu dot org [EMAIL PROTECTED] wrote: --- Comment #7 from rguenth at gcc dot gnu dot org 2007-10-20 10:14 --- I guess we just compute all 2**26 constants that can end up at the conditional store. And indeed, the number of 'Created value .*' in the dump matches this (modulo some constant offset). This is PPRE at work, which probably should be limited to a sub-CFG somehow. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540 --- You are receiving this mail because: --- You are on the CC list for the bug, or are watching someone who is. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #9 from rguenther at suse dot de 2007-10-20 20:52 --- Subject: Re: [4.3 Regression] Exponential time behavior in PRE On Sat, 20 Oct 2007, dberlin at dberlin dot org wrote: --- Comment #8 from dberlin at gcc dot gnu dot org 2007-10-20 20:49 --- Subject: Re: [4.3 Regression] Exponential time behavior in PRE We may just want to disable PPRE of constants entirely :) If you don't initialize the variable to zero we or in all the bits then the value will be not constant, but still 'var | constant' with 2**24 different constants... Richard. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #5 from falk at debian dot org 2007-09-24 20:18 ---
As noted by Edvin Török, the bug is not fixed for the original test case
(although it is fixed for the small test case). A small test case that still
fails is
int f(void);
void acceptloop_th(int *t) {
int options = 0;
if (f()) options |= 0x1 0;
if (f()) options |= 0x1 1;
if (f()) options |= 0x1 2;
if (f()) options |= 0x1 3;
if (f()) options |= 0x1 4;
if (f()) options |= 0x1 5;
if (f()) options |= 0x1 6;
if (f()) options |= 0x1 7;
if (f()) options |= 0x1 8;
if (f()) options |= 0x1 9;
if (f()) options |= 0x1 10;
if (f()) options |= 0x1 11;
if (f()) options |= 0x1 12;
if (f()) options |= 0x1 13;
if (f()) options |= 0x1 14;
if (f()) options |= 0x1 15;
if (f()) options |= 0x1 16;
if (f()) options |= 0x1 17;
if (f()) options |= 0x1 18;
if (f()) options |= 0x1 19;
if (f()) options |= 0x1 20;
if (f()) options |= 0x1 21;
if (f()) options |= 0x1 22;
if (f()) options |= 0x1 23;
if (f()) options |= 0x1 24;
if (f()) options |= 0x1 25;
if (f()) options |= 0x1 26;
if (f()) *t = options;
}
(the only change is that the last line is conditional).
--
falk at debian dot org changed:
What|Removed |Added
Status|RESOLVED|REOPENED
Resolution|FIXED |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #3 from dberlin at gcc dot gnu dot org 2007-06-30 14:15 --- Subject: Bug 32540 Author: dberlin Date: Sat Jun 30 14:15:26 2007 New Revision: 126149 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=126149 Log: 2007-06-30 Daniel Berlin [EMAIL PROTECTED] Fix PR tree-optimization/32540 Fix PR tree-optimization/31651 * tree-ssa-sccvn.c: New file. * tree-ssa-sccvn.h: Ditto. * tree-vn.c: Include tree-ssa-sccvn.h (val_expr_paid_d): Removed. (value_table): Ditto. (vn_compute): Ditto. (val_expr_pair_hash): Ditto. (val_expr_pair_expr_eq): Ditto. (copy_vuses_from_stmt): Ditto. (vn_delete): Ditto. (vn_init): Ditto. (shared_vuses_from_stmt): Ditto. (print_creation_to_file): Moved up. (sort_vuses): Ditto. (sort_vuses_heap): Ditto. (set_value_handle): Make non-static. (make_value_handle): Ditto. (vn_add): Rewritten to use sccvn lookups. (vn_add_with_vuses): Ditto. (vn_lookup): Ditto (and second argument removed). (vn_lookup_with_vuses): Ditto. (vn_lookup_or_add): Ditto (and second argument removed); (vn_lookup_or_add_with_vuses): Ditto. (vn_lookup_with_stmt): New. (vn_lookup_or_add_with_stmt): Ditto. (create_value_handle_for_expr): Ditto. * tree-ssa-pre.c: Include tree-ssa-sccvn.h. (seen_during_translate): New function. (phi_trans_lookup): Use iterative_hash_expr, not vn_compute. (phi_trans_add): Ditto. (constant_expr_p): FIELD_DECL is always constant. (phi_translate_1): Renamed from phi_translate, add seen bitmap. Use constant_expr_p. Avoid infinite recursion on mutually valued expressions. Change callers of vn_lookup_or_add. (phi_translate): New function. (compute_antic_safe): Allow phi nodes. (create_component_ref_by_pieces): Update for FIELD_DECL change. (find_or_generate_expression): Rewrite slightly. (create_expression_by_pieces): Updated for vn_lookup_or_add change. Update VN_INFO for new names. (insert_into_preds_of_block): Update for new names. (add_to_exp_gen): New function. (add_to_sets): Use vn_lookup_or_add_with_stmt. (find_existing_value_expr): Rewrite to changed vn_lookup. (create_value_expr_from): Ditto, and use add_to_exp_gen. (try_look_through_load): Removed. (try_combine_conversion): Ditto. (get_sccvn_value): New function. (make_values_for_phi): Ditto. (make_values_for_stmt): Ditto. (compute_avail): Rewritten for vn_lookup_or_add changes and to use SCCVN. (init_pre): Update for SCCVN changes. (fini_pre): Ditto. (execute_pre): Ditto. * tree-flow.h (make_value_handle): Declare. (set_value_handle): Ditto. (sort_vuses_heap): Ditto. (vn_lookup_or_add_with_stmt): Ditto. (vn_lookup_with_stmt): Ditto. (vn_compute): Remove. (vn_init): Ditto. (vn_delete): Ditto. (vn_lookup): Update arguments. * Makefile.in (tree-ssa-pre.o): Add tree-ssa-sccvn.h (tree-vn.o): Ditto. (tree-ssa-sccvn.o): New. (OBJS-common): Add tree-ssa-sccvn.o Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c - copied unchanged from r125553, branches/gcc-pre-vn/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-1.c trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c - copied unchanged from r125553, branches/gcc-pre-vn/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-3.c - copied unchanged from r125553, branches/gcc-pre-vn/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-3.c trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c - copied unchanged from r125553, branches/gcc-pre-vn/gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-4.c trunk/gcc/tree-ssa-sccvn.c - copied, changed from r125553, branches/gcc-pre-vn/gcc/tree-ssa-sccvn.c trunk/gcc/tree-ssa-sccvn.h - copied, changed from r125553, branches/gcc-pre-vn/gcc/tree-ssa-sccvn.h Modified: trunk/gcc/ChangeLog trunk/gcc/Makefile.in trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-1.c trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-3.c trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-4.c trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-5.c trunk/gcc/tree-flow.h trunk/gcc/tree-ssa-operands.h trunk/gcc/tree-ssa-pre.c trunk/gcc/tree-vn.c -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #4 from dberlin at gcc dot gnu dot org 2007-06-30 14:16 --- Fixed -- dberlin at gcc dot gnu dot org changed: What|Removed |Added Status|NEW |RESOLVED Resolution||FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
-- mmitchel at gcc dot gnu dot org changed: What|Removed |Added Priority|P3 |P1 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
[Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
--- Comment #2 from rguenth at gcc dot gnu dot org 2007-06-28 20:25 --- Confirmed. -- rguenth at gcc dot gnu dot org changed: What|Removed |Added CC||rguenth at gcc dot gnu dot ||org Status|UNCONFIRMED |NEW Ever Confirmed|0 |1 Last reconfirmed|-00-00 00:00:00 |2007-06-28 20:25:29 date|| Summary|Exponential time behavior in|[4.3 Regression] Exponential |PRE |time behavior in PRE Target Milestone|--- |4.3.0 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
