--- Additional Comments From pinskia at gcc dot gnu dot org 2005-02-13
23:14 ---
Moving to 4.1 as I don't care much if this gets fixed.
--
What|Removed |Added
Target Miles
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-27 20:38 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
> > Another idea: would it be possible to insert the invalidated names
> > during the o
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-27 19:10 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> Another idea: would it be possible to insert the invalidated names
> during the optimization pass instead of invalidating all the symb
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-27 15:12 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
> the patch is below (in stronger form -- only removing entries that
> contain invalida
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-27 15:00 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> --- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
> 2005-01-27 13:18 ---
> Subject: Re: [4.0 Regressio
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-27 13:18 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
With the following patch I got some speedup for depth 100.
from:
tree iv optimization : 2.62 (62%) usr 0.27 (82%) sys 2.92 (62%) wall
t
--
What|Removed |Added
Severity|normal |minor
Priority|P2 |P3
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-25 16:26 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> > If you decide to reconstruct the tree expression, there is no reason
> > to stop on a phi node that has a single argument. Why would you like
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 15:54 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
> > More seriously -- which of the possibilities? If I have loops like
> >
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-25 12:44 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
> More seriously -- which of the possibilities? If I have loops like
>
> while (...)
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-25 12:03 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
>
> --- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
> d
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 11:29 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> > (*) I hope; scev is a mess of mutualy recursive functions --
> > analyze_scalar_evolution calling number_of_iterations calling
> > i
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 11:16 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> > How? If the reference is left in symbolic form, it means that you know
> > nothing about its value, so the only thing you can do wi
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 11:14 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
> > Adding the instantiation cache was compile time neutral on normal code,
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-25 11:02 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
>
> (*) I hope; scev is a mess of mutualy recursive functions --
> analyze_scalar_evol
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-25 10:39 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
>
> How? If the reference is left in symbolic form, it means that you know
> nothing
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-25 10:32 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
> Adding the instantiation cache was compile time neutral on normal code,
> so I don't
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 01:57 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> >> * tree-data-ref.c (analyze_overlapping_iterations): chrecs that
> >> are equal overlap on every iteration.
> >>
>
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 01:52 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> Do remember that this bug is about bad behavior with deeply nested loops
> and we already have other algorithms that are quadratic in
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-25
01:42 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
>>
>> * tree-data-ref.c (analyze_overlapping_iterations): chrecs that
>> are equal overlap on every iteration.
>>
>> This stuff is just sim
--- Additional Comments From steven at gcc dot gnu dot org 2005-01-25
01:28 ---
Do remember that this bug is about bad behavior with deeply nested loops
and we already have other algorithms that are quadratic in the loop nest
depth. So I really wouldn't consider this to be a very seri
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 01:24 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> > Which one? I cannot find anything relevant in changelog.
> >
>
>
> * tree-data-ref.c (analyze_subscript_affine_affine): I
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-25
01:15 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> Which one? I cannot find anything relevant in changelog.
>
* tree-data-ref.c (analyze_subscript_affine_affine): Implement a
solution f
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-25
01:11 ---
Which one? I cannot find anything relevant in changelog.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-25
00:52 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> See autovec branch.
You could also look at recent patches posted by sebastian and i for the
autovect branch that have been adding this support.
--
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-25
00:50 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
On Mon, 25 Jan 2005, rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
>
> --- Additional Comments From rakdver at atrey dot karlin dot mff d
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 00:49 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> Uh, symbolic references are or will be used to do data dependence when
> MEM_REF and ARRAY_REF couldn't be generated from th
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-25
00:39 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
Uh, symbolic references are or will be used to do data dependence when
MEM_REF and ARRAY_REF couldn't be generated from the pointers.
>>>
>>>
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-25 00:27 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> >>> Other part is that scev tries to be too clever. Without need to
> >>> represent nonaffine induction variables (that we do not use
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-24
23:12 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
On Mon, 24 Jan 2005, rakdver at atrey dot karlin dot mff dot cuni dot cz wrote:
>
> --- Additional Comments From rakdver at atrey dot karlin dot mff d
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-24 23:09 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> > Other part is that scev tries to be too clever. Without need to
> > represent nonaffine induction variables (that we do not use any
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-24
22:25 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
>
> Other part is that scev tries to be too clever. Without need to
> represent nonaffine induction variables (that we do not use anywhere)
> we could use m
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-24 22:16 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> > Still there remain some inefficiences within the scev analysis itself.
> >
>
> Zdenek, have you tried to revert the patch that cac
--- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-24 21:36 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
>
> Still there remain some inefficiences within the scev analysis itself.
>
Zdenek, have you tried to revert the patch that caches the
instant
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-24
01:57 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
>> On a side note, PRE also seems to have problems with the testcase. With the
>> patch mentioned above, the largest consumers of compile time are ivopts (4
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-24
01:49 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
On Sun, 24 Jan 2005, rakdver at gcc dot gnu dot org wrote:
>
> --- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-24
> 01:46 --
On Sun, 24 Jan 2005, rakdver at gcc dot gnu dot org wrote:
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-24
01:46 ---
On a side note, PRE also seems to have problems with the testcase. With the
patch mentioned above, the largest consumers of compile time are ivopts
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-24
01:46 ---
On a side note, PRE also seems to have problems with the testcase. With the
patch mentioned above, the largest consumers of compile time are ivopts (45%)
and pre (20%).
--
What|Removed
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-24
01:40 ---
The patch that causes ivopts to reset just the relevant parts of the scev cache
(just regtesting) instead of clearing it completely helps a bit -- the compile
time for N=100 gets about 2x better and memory c
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-23
17:04 ---
One extra N factor seems to be coming from simple_iv
(analyze_scalar_evolution_in_loop). The function was created before
loop closed ssa form, under assumptions of lcssa it should be possible
to get rid of
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-23
17:14 ---
Also did not help much.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
--- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-23
16:38 ---
Sebastian's patch does not help significantly :-(
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2005-01-23 15:06 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> I believe seb/zdenek already submitted patches for speeding up scev quite
> recently, with the goal of alleviating this problem.
> I'
--- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-23
15:01 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
I believe seb/zdenek already submitted patches for speeding up scev quite
recently, with the goal of alleviating this problem.
I'm pretty sure they have not
I believe seb/zdenek already submitted patches for speeding up scev quite
recently, with the goal of alleviating this problem.
I'm pretty sure they have not been applied yet.
--- Additional Comments From steven at gcc dot gnu dot org 2005-01-23
14:22 ---
More profile data:
---
0.00 187.04 1/1 execute_pass_list [6]
[7] 76.50.00 187.04 1 tree_ssa_iv_optimize
--- Additional Comments From steven at gcc dot gnu dot org 2005-01-23
14:24 ---
One more, because I also run out of memory pretty quickly:
---
0.000.00 1/22863854 c_build_bind_expr [1608]
0.00
--- Additional Comments From steven at gcc dot gnu dot org 2005-01-23
14:23 ---
Looks to me like Seb may want to look at this bug too...
--
What|Removed |Added
--- Additional Comments From steven at gcc dot gnu dot org 2005-01-23
14:18 ---
It's definitely not the bitmaps:
time seconds secondscalls s/call s/call name
10.28 25.1425.14 24356740 0.00 0.00 ggc_alloc_stat
5.39 38.3213.18 3133403 0.00
--- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni
dot cz 2004-12-23 01:29 ---
Subject: Re: [4.0 Regression] IV-OPTS is O(N^3)
> hmmm maybe the extra O(N) comes from O(N) bitmap operations? (Just guessing)
that might be the case, but I don't think it is likely
--- Additional Comments From steven at gcc dot gnu dot org 2004-12-23
01:26 ---
hmmm maybe the extra O(N) comes from O(N) bitmap operations? (Just guessing)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
--- Additional Comments From belyshev at depni dot sinp dot msu dot ru
2004-12-22 23:40 ---
It seems that extra O(N) factor comes from high memory usage. For smaller N
(0..30) compiler behaves like O(2) and for larger (> 50) like O(2.5 .. 3).
gnuplot> fit [0:30] A*x**k+B "data" via A,k,
--- Additional Comments From rakdver at gcc dot gnu dot org 2004-11-28
18:42 ---
IVOPTs should behave quadratically on this type of tests; I do not know where
does the extra O(N) factor come from, and I would not expect the times to grow
this fast.
--
What|Removed
--
What|Removed |Added
OtherBugsDependingO||18693
nThis||
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
--- Additional Comments From belyshev at lubercy dot com 2004-11-27 01:45
---
(In reply to comment #3)
> Of course it's not very useful to claim that some algorithm
> is O(N^x) when you don't say what N is...
N is number of nested loops.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?
--- Additional Comments From steven at gcc dot gnu dot org 2004-11-27
01:10 ---
Of course it's not very useful to claim that some algorithm
is O(N^x) when you don't say what N is...
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18595
--- Additional Comments From belyshev at lubercy dot com 2004-11-25 11:16
---
use this awk script to generate testcase (first arg is number of loops):
BEGIN {
ORS=""
print "int f ()\n
57 matches
Mail list logo
