Make try_unroll_loop_completely to use loop bounds recorded

Hi,
while looking into RTL loop peeling micopmilation I found that we now do a lot of
RTL loop peeling for loops of the form

int a[2];
test(int c)
{
  int i;
  for (i=0;i<c;i++)
    a[i]=5;
}
this is because tree-ssa-loop-niter is able to prove that the loop iterates at
most twice.  This is better to be done on gimple level because destroying the
loop enables more propagation.

This patch started as simple attempt to make try_unroll_loop_completely
to use max_loop_iterations_int.  I had to track several issues

1) try_unroll_loop_completely handles only inner loops.  I am fine with not
   peeling loops with subloops, but if the loop is known to iterate 0 times,
   we should turn it into non-loop.
2) try_unroll_loop_completely now handles removal of the loop by making
   exit edge conditional to be true and relying on cleanup_cfg to do
   the job.  This does not work for all the cases we can handle
   by max_loop_iterations_int.  When loop has multiple possible exits
   we don't really know what exit will be taken (we know it will be one
   of them).

   I added logic handling simple case where loop has single exit and
   in generic case I unloop it by adding __builtin_unreachable on the
   loopback path.  While this seems bit involved it works well.
3) The last iteration has parts that are provably unreachable and should
   be optimized out later.  VRP however tends to report array bound warnings
   that breaks -O3 bootstrap.
   I sent separate fix for that.  Still I need to add 3 initializations
   to avoid maybe used uninitialized warning to get -O3 bootstrap working
   with this patch.

The patch got quite a lot of snowballing effect, so I decided to not include:

1) the cost model is skewed for last iteration.  It is often just duplicated
   loop header - i.e. all code dominated by the optmized out exit test should
   not be accounted. This would make cunroll-4.c testcase bellow to be unlooped
   during cunrolli rather than during complette unroling.
2) profile updating is broken for any loop containing non-trivial control flow.
   We need to teach loop duplication code to update sanely the profile when
   wont_exit is true and we need to update profile
3) we probably want to do less unrolling when result is not a single basic
   block. Current limit of 400 isnsns seems bit too large; making one basic
   block is important win. Making sequence of basic blocks with exits is
   less so.

	* gcc.dg/tree-ssa/cunroll-1.c: New testcase.
	* gcc.dg/tree-ssa/cunroll-2.c: New testcase.
	* gcc.dg/tree-ssa/cunroll-3.c: New testcase.
	* gcc.dg/tree-ssa/cunroll-4.c: New testcase.
	* gcc.dg/tree-ssa/cunroll-5.c: New testcase.

	* cfgloopmanip.c (unloop): Export.
	* tree-ssa-loop-ivcanon.c (tree_estimate_loop_size): Estimate
	also with unknown exit conditoinal.
	(try_unroll_loop_completely): Use max_loop_iterations_int to unroll
	also loops with low upper bound; handle unlooping of the last loop
	even when exit conditional is not known; unloop loop that do not loop
	even if they are not innermost.
	(canonicalize_loop_induction_variables): Record niter bounds known;
	try unrolling even if number of iterations is not known;
	(canonicalize_induction_variables): Be ready for loops disappearing.
	(tree_unroll_loops_completely): Likewise.
	* cfgloop.h (unloop): Declare.

	* f95-lang.c (gfc_init_builtin_functions): Build __builtin_unreachable.

Make try_unroll_loop_completely to use loop bounds recorded

Commit Message

Comments

Patch