Re: Out-of-sight compile times for calculate_loop_depth

[Michael Hayes <m dot hayes at elec dot canterbury dot ac dot nz>]

Brad Lucier writes:

 > Well, it's extreme even by my standards, but it is no more than 5
 > times as big as the typical programs I compile, which themselves do not
 > compile quickly.  Code like this is typical if you want to support
 > continuations and complete tail-call elimination, things that are
 > not supported directly in C (so the code implements a trampoline).

I can see where you're coming from, but I cannot see how any loop with
5000 odd exiting edges is ever going to be easy to optimise or able to
run quickly (especially with your program where the exiting edges are
from a basic block that is always executed within the loop).

 > I can run some tests myself if that will help you.  Or I can find
 > you a smaller test case.

Could you please try the attached patch on your program.  This should
improve the loop tree construction time.  Currently it has quadratic
behaviour in the worst case.  This patch should nail this problem in
the interim although I've got an inlinking for an even better scheme.

 > > We probably need a bailout mechanism if we detect a CFG with many
 > > shared loop headers.  These will never be optimised very well anyway.
 > 
 > I don't feel so great about this option.  Some optimizations are already
 > left out in -O2 if the CFG is big enough, if I remember correctly. That
 > doesn't affect me directly, because I generally don't use -O2; but I don't
 > think it's a good idea to bury "problem" optimizations that take a lot
 > of time and don't produce good results on some programs, because then
 > there is very little chance that they will ever be improved.

It's not really the size of the CFG that is the problem; it's the
shape.  (Seeing a goto for every half-dozen source lines is a dead
give-away.)

One of the current bottlenecks with your program is having to search a
very long list of edges for every basic block in a loop, viz:

  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
    for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
      {
	basic_block dest = e->dest;	  

	/* Record edges that exit the loop.  */
	if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
	  (*exits)[num_exits++] = e;
      }
  });

Any ideas for souping this up would be appreciated.  One idea is to
only compute it for passes that require this info.

Michael.

flow.patch.gz