[Bug tree-optimization/18601] [4.0 Regression] tree cfglceanup is slow

["rakdver at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-11-22 16:45 -------
The code in this testcase looks basically this way:

c:
switch (b)
  {
    case 1:
      b = 2; goto c;
    case 2:
      b = 3; goto c;
    ...
  }

What happens is that dom peforms jump threading over the switch, thus turning
the code into

switch (b)
  {
    case 1: goto l1;
    case 2: goto l2;
    case 3: goto l3;
  }

l1: b = ...; goto l2;
l2: b = ...; goto l3;
l3: b = ...; goto l4;
...

The assignments to b get removed in dce, and cfgcleanup jump starts propagating
the edges from the switch statement over the chain of thousands of empty blocks.
I.e. the first of them is threaded over 1 block, next over 2, ..., the last over
2000, resulting in a quadratic behavior by itself.

The other source for quadratic behavior in this case indeed is updating of
dominators (concretely the recount_dominators step for the last basic block
in the chain -- its degree increases by one in each step, and
recount_dominator is by itself linear in number of predecessors of a block.
I will try to come up with something for at least the later problem.  Throwing
the dominance information away is of course an option, but I think we should be
able to avoid it easily.

-- 


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