* [Bug tree-optimization/32540] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
@ 2007-06-28 20:16 ` falk at debian dot org
2007-06-28 20:25 ` [Bug tree-optimization/32540] [4.3 Regression] " rguenth at gcc dot gnu dot org
` (16 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: falk at debian dot org @ 2007-06-28 20:16 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from falk at debian dot org 2007-06-28 20:15 -------
Created an attachment (id=13801)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13801&action=view)
Original test case
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
2007-06-28 20:16 ` [Bug tree-optimization/32540] " falk at debian dot org
@ 2007-06-28 20:25 ` rguenth at gcc dot gnu dot org
2007-06-29 18:59 ` mmitchel at gcc dot gnu dot org
` (15 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2007-06-28 20:25 UTC (permalink / raw)
To: gcc-bugs
------- 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|0000-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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
2007-06-28 20:16 ` [Bug tree-optimization/32540] " falk at debian dot org
2007-06-28 20:25 ` [Bug tree-optimization/32540] [4.3 Regression] " rguenth at gcc dot gnu dot org
@ 2007-06-29 18:59 ` mmitchel at gcc dot gnu dot org
2007-06-30 14:16 ` dberlin at gcc dot gnu dot org
` (14 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: mmitchel at gcc dot gnu dot org @ 2007-06-29 18:59 UTC (permalink / raw)
To: gcc-bugs
--
mmitchel at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Priority|P3 |P1
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32540
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (2 preceding siblings ...)
2007-06-29 18:59 ` mmitchel at gcc dot gnu dot org
@ 2007-06-30 14:16 ` dberlin at gcc dot gnu dot org
2007-06-30 14:17 ` dberlin at gcc dot gnu dot org
` (13 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: dberlin at gcc dot gnu dot org @ 2007-06-30 14:16 UTC (permalink / raw)
To: gcc-bugs
------- 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=gcc&view=rev&rev=126149
Log:
2007-06-30 Daniel Berlin <dberlin@dberlin.org>
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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (3 preceding siblings ...)
2007-06-30 14:16 ` dberlin at gcc dot gnu dot org
@ 2007-06-30 14:17 ` dberlin at gcc dot gnu dot org
2007-09-24 20:18 ` falk at debian dot org
` (12 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: dberlin at gcc dot gnu dot org @ 2007-06-30 14:17 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (4 preceding siblings ...)
2007-06-30 14:17 ` dberlin at gcc dot gnu dot org
@ 2007-09-24 20:18 ` falk at debian dot org
2007-10-20 8:03 ` tbm at cyrius dot com
` (11 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: falk at debian dot org @ 2007-09-24 20:18 UTC (permalink / raw)
To: gcc-bugs
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1654 bytes --]
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (5 preceding siblings ...)
2007-09-24 20:18 ` falk at debian dot org
@ 2007-10-20 8:03 ` tbm at cyrius dot com
2007-10-20 10:15 ` rguenth at gcc dot gnu dot org
` (10 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: tbm at cyrius dot com @ 2007-10-20 8:03 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (6 preceding siblings ...)
2007-10-20 8:03 ` tbm at cyrius dot com
@ 2007-10-20 10:15 ` rguenth at gcc dot gnu dot org
2007-10-20 20:49 ` dberlin at dberlin dot org
` (9 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2007-10-20 10:15 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (7 preceding siblings ...)
2007-10-20 10:15 ` rguenth at gcc dot gnu dot org
@ 2007-10-20 20:49 ` dberlin at dberlin dot org
2007-10-20 20:52 ` rguenther at suse dot de
` (8 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: dberlin at dberlin dot org @ 2007-10-20 20:49 UTC (permalink / raw)
To: gcc-bugs
------- 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 -0000, rguenth at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (8 preceding siblings ...)
2007-10-20 20:49 ` dberlin at dberlin dot org
@ 2007-10-20 20:52 ` rguenther at suse dot de
2007-11-01 15:26 ` rguenth at gcc dot gnu dot org
` (7 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: rguenther at suse dot de @ 2007-10-20 20:52 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (9 preceding siblings ...)
2007-10-20 20:52 ` rguenther at suse dot de
@ 2007-11-01 15:26 ` rguenth at gcc dot gnu dot org
2007-11-01 21:16 ` jakub at gcc dot gnu dot org
` (6 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2007-11-01 15:26 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (10 preceding siblings ...)
2007-11-01 15:26 ` rguenth at gcc dot gnu dot org
@ 2007-11-01 21:16 ` jakub at gcc dot gnu dot org
2007-11-01 21:24 ` dberlin at dberlin dot org
` (5 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: jakub at gcc dot gnu dot org @ 2007-11-01 21:16 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (11 preceding siblings ...)
2007-11-01 21:16 ` jakub at gcc dot gnu dot org
@ 2007-11-01 21:24 ` dberlin at dberlin dot org
2007-11-03 5:19 ` sebpop at gmail dot com
` (4 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: dberlin at dberlin dot org @ 2007-11-01 21:24 UTC (permalink / raw)
To: gcc-bugs
------- 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 -0000, jakub at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (12 preceding siblings ...)
2007-11-01 21:24 ` dberlin at dberlin dot org
@ 2007-11-03 5:19 ` sebpop at gmail dot com
2007-11-03 5:26 ` sebpop at gmail dot com
` (3 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: sebpop at gmail dot com @ 2007-11-03 5:19 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (13 preceding siblings ...)
2007-11-03 5:19 ` sebpop at gmail dot com
@ 2007-11-03 5:26 ` sebpop at gmail dot com
2007-11-03 5:54 ` sebpop at gmail dot com
` (2 subsequent siblings)
17 siblings, 0 replies; 19+ messages in thread
From: sebpop at gmail dot com @ 2007-11-03 5:26 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (14 preceding siblings ...)
2007-11-03 5:26 ` sebpop at gmail dot com
@ 2007-11-03 5:54 ` sebpop at gmail dot com
2007-11-05 15:42 ` spop at gcc dot gnu dot org
2007-11-05 15:45 ` spop at gcc dot gnu dot org
17 siblings, 0 replies; 19+ messages in thread
From: sebpop at gmail dot com @ 2007-11-03 5:54 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (15 preceding siblings ...)
2007-11-03 5:54 ` sebpop at gmail dot com
@ 2007-11-05 15:42 ` spop at gcc dot gnu dot org
2007-11-05 15:45 ` spop at gcc dot gnu dot org
17 siblings, 0 replies; 19+ messages in thread
From: spop at gcc dot gnu dot org @ 2007-11-05 15:42 UTC (permalink / raw)
To: gcc-bugs
------- 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=gcc&view=rev&rev=129901
Log:
2007-11-05 Nick Clifton <nickc@redhat.com>
Sebastian Pop <sebastian.pop@amd.com>
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
^ permalink raw reply [flat|nested] 19+ messages in thread
* [Bug tree-optimization/32540] [4.3 Regression] Exponential time behavior in PRE
2007-06-28 20:15 [Bug tree-optimization/32540] New: Exponential time behavior in PRE falk at debian dot org
` (16 preceding siblings ...)
2007-11-05 15:42 ` spop at gcc dot gnu dot org
@ 2007-11-05 15:45 ` spop at gcc dot gnu dot org
17 siblings, 0 replies; 19+ messages in thread
From: spop at gcc dot gnu dot org @ 2007-11-05 15:45 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 19+ messages in thread