[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