[Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps

[Bug tree-optimization/17966] New: a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

#define ELSEIF1 else if (a) b = a;
#define ELSEIF2     ELSEIF1     ELSEIF1
#define ELSEIF4     ELSEIF2     ELSEIF2
#define ELSEIF8     ELSEIF4     ELSEIF4
#define ELSEIF16    ELSEIF8     ELSEIF8
#define ELSEIF32    ELSEIF16    ELSEIF16
#define ELSEIF64    ELSEIF32    ELSEIF32
#define ELSEIF128   ELSEIF64    ELSEIF64
#define ELSEIF256   ELSEIF128   ELSEIF128
#define ELSEIF512   ELSEIF256   ELSEIF256
#define ELSEIF1024  ELSEIF512   ELSEIF512
#define ELSEIF2048  ELSEIF1024  ELSEIF1024
#define ELSEIF4096  ELSEIF2048  ELSEIF2048
#define ELSEIF8192  ELSEIF4096  ELSEIF4096
#define ELSEIF16384 ELSEIF8192  ELSEIF8192
#define ELSEIF32768 ELSEIF16384 ELSEIF16384
#define ELSEIF65536 ELSEIF32768 ELSEIF32768

void
foo (int a)
{
  int b;

  if (a)
    b = a;
  ELSEIF8192
}

"tree CFG cleanup" takes 44% of compile time.

Note that all occurrences of "b = a;" are removed by DCE.

One run of thread_jumps can only collapse the last "if" statement.

Collapsing all "if" statements takes roughly as many iterations of
thread_jumps as the number of "if" statements.

So the total running time is O(n^2).

-- 
           Summary: a quadratic behavior in thread_jumps
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[giovannibajo at libero dot it]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[kazu at cs dot umass dot edu]

------- 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

[Bug tree-optimization/17966] a quadratic behavior in thread_jumps

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.0.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17966