* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
@ 2004-10-13 3:55 ` pinskia at gcc dot gnu dot org
2004-10-13 4:14 ` pinskia at gcc dot gnu dot org
` (15 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-13 3:55 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-13 03:55 -------
Confirmed, I have found a related testcase where we are slower than 3.3.3. This one we are faster.
The way to fix this would be run on the BB backwards.
--
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2004-10-13 03:55:39
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
2004-10-13 3:55 ` [Bug tree-optimization/17966] " pinskia at gcc dot gnu dot org
@ 2004-10-13 4:14 ` pinskia at gcc dot gnu dot org
2004-10-13 11:58 ` giovannibajo at libero dot it
` (14 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-13 4:14 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-13 04:14 -------
The related testcase is filed under PR 17967.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
2004-10-13 3:55 ` [Bug tree-optimization/17966] " pinskia at gcc dot gnu dot org
2004-10-13 4:14 ` pinskia at gcc dot gnu dot org
@ 2004-10-13 11:58 ` giovannibajo at libero dot it
2004-10-13 12:11 ` kazu at cs dot umass dot edu
` (13 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: giovannibajo at libero dot it @ 2004-10-13 11:58 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From giovannibajo at libero dot it 2004-10-13 11:58 -------
Is this a regression?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (2 preceding siblings ...)
2004-10-13 11:58 ` giovannibajo at libero dot it
@ 2004-10-13 12:11 ` kazu at cs dot umass dot edu
2004-10-13 12:17 ` pinskia at gcc dot gnu dot org
` (12 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-13 12:11 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From kazu at cs dot umass dot edu 2004-10-13 12:11 -------
In this particular testcase, going through BBs in backwards does help
by cutting down the running time by about half, but I wonder if we can
create an identical testcase except that the order of BBs are reversed.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (3 preceding siblings ...)
2004-10-13 12:11 ` kazu at cs dot umass dot edu
@ 2004-10-13 12:17 ` pinskia at gcc dot gnu dot org
2004-10-13 12:20 ` pinskia at gcc dot gnu dot org
` (11 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-13 12:17 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-13 12:17 -------
No this is not a regression (unless someone can find a testcase which says it is and I cannot find a
testcase). See PR 17967 for a testcase which is a regression but thread_jumps has nothing to do it
though.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (4 preceding siblings ...)
2004-10-13 12:17 ` pinskia at gcc dot gnu dot org
@ 2004-10-13 12:20 ` pinskia at gcc dot gnu dot org
2004-10-13 12:35 ` kazu at cs dot umass dot edu
` (10 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-13 12:20 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-13 12:19 -------
I also cannot think of a testcase where we have the reverse BB but it could happen. Really we should
processoring by post-dom order which gives us the correct way to do this transformation.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (5 preceding siblings ...)
2004-10-13 12:20 ` pinskia at gcc dot gnu dot org
@ 2004-10-13 12:35 ` kazu at cs dot umass dot edu
2004-10-13 13:26 ` pinskia at gcc dot gnu dot org
` (9 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-13 12:35 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From kazu at cs dot umass dot edu 2004-10-13 12:35 -------
Andrew, I did it in the hard way. :-)
void
foo (int a)
{
int b;
goto b1;
b4: return;
b3: if (a) { b = a; return; } else goto b4;
b2: if (a) { b = a; return; } else goto b3;
b1: if (a) { b = a; return; } else goto b2;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (6 preceding siblings ...)
2004-10-13 12:35 ` kazu at cs dot umass dot edu
@ 2004-10-13 13:26 ` pinskia at gcc dot gnu dot org
2004-10-13 13:30 ` kazu at cs dot umass dot edu
` (8 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-13 13:26 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-13 13:26 -------
I can get this down to (with a compiler at -O0):
tree CFG cleanup : 6.30 ( 6%) usr 0.02 ( 1%) sys 13.51 (10%) wall
I will submit a patch once I test it more on some other sources.
But I will attach it here if I don't get around to it.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (7 preceding siblings ...)
2004-10-13 13:26 ` pinskia at gcc dot gnu dot org
@ 2004-10-13 13:30 ` kazu at cs dot umass dot edu
2004-10-13 14:24 ` kazu at cs dot umass dot edu
` (7 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-13 13:30 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From kazu at cs dot umass dot edu 2004-10-13 13:29 -------
I should note that I used -O2 when I came up with "44%" in the initial
description of this bug.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (8 preceding siblings ...)
2004-10-13 13:30 ` kazu at cs dot umass dot edu
@ 2004-10-13 14:24 ` kazu at cs dot umass dot edu
2004-10-13 14:44 ` pinskia at gcc dot gnu dot org
` (6 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-13 14:24 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From kazu at cs dot umass dot edu 2004-10-13 14:24 -------
Andrew,
Regarding your patch, if we have exactly one basic block immediately preceding
EXIT_BLOCK_PTR, and that block happens to be a forwarder block, your algorithm
terminates without doing any further work.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (9 preceding siblings ...)
2004-10-13 14:24 ` kazu at cs dot umass dot edu
@ 2004-10-13 14:44 ` pinskia at gcc dot gnu dot org
2004-10-13 15:38 ` kazu at cs dot umass dot edu
` (5 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-13 14:44 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-13 14:44 -------
Woops I have a fix for that and plus I also fixed an ICE I saw. I will attach a new patch soon.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (10 preceding siblings ...)
2004-10-13 14:44 ` pinskia at gcc dot gnu dot org
@ 2004-10-13 15:38 ` kazu at cs dot umass dot edu
2004-10-13 17:02 ` pinskia at gcc dot gnu dot org
` (4 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-13 15:38 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From kazu at cs dot umass dot edu 2004-10-13 15:38 -------
Andrew,
Your algorithm would still present a quadratic behavior in the
following situation.
bb0 <- a block with COND_EXPR only
| \
| \
| bb1 <- a block with COND_EXPR only
| | \
| | \
| | bb2 <- empty
| | /
| | /
| bb3 <- empty
| /
bb4 <- a block with RETURN_EXPR only
First, note that the whole thing should collapse down to a single
basic block as there is no interesting statement.
Let's assume that the orientation of edges in the above diagram
matches the order of edges present in each edge vector. That is,
bb4's predecessor edge vector looks like (bb0->bb4, bb3->bb4). Here
is the call sequence.
thread_jumps ()
thread_jump (bb4, ...)
no jump threading occurs
thread_jump (bb0)
no jump threading occurs
thread_jump (ENTRY_BLOCK_PTR)
base case
thread_jump (bb3)
no jump threading occurs (as bb3 is a forwarder block)
thread_jump (bb1)
bb1, bb2, and bb3 collapse down to one basic block
thread_jump (bb0)
base case (already visited)
Here is the end result.
bb0
| \
| \
| bb1
| /
| /
bb4
Note that we removed only one "if" statement. If we have n deeply
nested "if" statements, we need n iterations of thread_jumps.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (11 preceding siblings ...)
2004-10-13 15:38 ` kazu at cs dot umass dot edu
@ 2004-10-13 17:02 ` pinskia at gcc dot gnu dot org
2004-10-21 18:18 ` kazu at cs dot umass dot edu
` (3 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-13 17:02 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-13 17:02 -------
Oh, you are right, maybe doing the forwarding before and try doing it after will fix that and we will no
longer have to do while (thread_jumps()) either.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (12 preceding siblings ...)
2004-10-13 17:02 ` pinskia at gcc dot gnu dot org
@ 2004-10-21 18:18 ` kazu at cs dot umass dot edu
2004-10-23 19:18 ` pinskia at gcc dot gnu dot org
` (2 subsequent siblings)
16 siblings, 0 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-21 18:18 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From kazu at cs dot umass dot edu 2004-10-21 18:18 -------
The quadratic behavior of thread_jumps has been solved, but still
mainline is slower than 3.3 on this testcase.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (13 preceding siblings ...)
2004-10-21 18:18 ` kazu at cs dot umass dot edu
@ 2004-10-23 19:18 ` pinskia at gcc dot gnu dot org
2004-10-23 20:48 ` kazu at cs dot umass dot edu
2004-10-23 20:51 ` pinskia at gcc dot gnu dot org
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-23 19:18 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-23 19:18 -------
I think I just fixed the compile time problem in this PR by the patch which I committed for PR 17967,
Can you try again?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (14 preceding siblings ...)
2004-10-23 19:18 ` pinskia at gcc dot gnu dot org
@ 2004-10-23 20:48 ` kazu at cs dot umass dot edu
2004-10-23 20:51 ` pinskia at gcc dot gnu dot org
16 siblings, 0 replies; 18+ messages in thread
From: kazu at cs dot umass dot edu @ 2004-10-23 20:48 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From kazu at cs dot umass dot edu 2004-10-23 20:48 -------
OK. Now mainline is a lot faster than 3.3 on this testcase.
3.3 takes more than 20 seconds
mainlines takes less than 3 seconds
Thanks Andrew!
--
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |RESOLVED
Resolution| |FIXED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug tree-optimization/17966] a quadratic behavior in thread_jumps
2004-10-13 3:13 [Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps kazu at cs dot umass dot edu
` (15 preceding siblings ...)
2004-10-23 20:48 ` kazu at cs dot umass dot edu
@ 2004-10-23 20:51 ` pinskia at gcc dot gnu dot org
16 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-23 20:51 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|--- |4.0.0
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966
^ permalink raw reply [flat|nested] 18+ messages in thread