Re: [CFG] Loop unrolling

[Jan Hubicka <jh at suse dot cz>]

> Hello.
> 
> Here is the patch after requested changes (splitting functions,
> handling overflows). It also adds loops peeling (only two trivial
> functions, but I was lazy to get them out of the patch now).
> 
> Zdenek
> 
> Changelog:
> 	* Makefile.in (unroll-new.o): New.
> 	* basic-block.h (create_preheaders, create_preheader): Declaration
> 	changed.
> 	* cfgloopanal.c (create_preheaders, create_preheader): Modified to use
> 	flags.
> 	* loop-new.c (duplicate_loop_to_header_edge, can_duplicate_loop_p,
> 	expected_loop_iterations): Made global.
> 	(loop_optimizer_init): Create preheaders after cfglayout.
> 	(try_remove_path): Fixed a stupid bug.
> 	(duplicate_loop_to_header_edge): Modified to use flags.
> 	* loop.h (struct loop_desc): Description of simple loop.
> 	(expected_loop_iterations, can_duplicate_loop_p,
> 	duplicate_loop_to_header_edge): Declare.
> 	* params.def (MAX_UNROLLED_INSNS, MAX_UNROLL_TIMES,
> 	MAX_PEELED_INSNS, MAX_PEEL_TIMES): New options.
> 	* toplev.c (flag_new_unroll_loops, flag_new_unroll_all_loops,
> 	flag_peel_loops): New flags.
> 	(rest_of_compilation): Enable new loop peeling and unrolling.
> 	* unroll-new.c: New file.
> 	(simple_exit, simple_condition_p, simple_increment,
> 	variable_initial_value, simple_loop_p): New, simple loop recognition.
> 	(count_loop_iterations, unroll_loop_constant_iterations,
> 	unroll_loop_runtime_iterations, unroll_simple_loop): Simple loop
> 	unrolling.
> 	(unroll_loop_new, unroll_loops): Loop unrolling.
> 	(peel_loop, peel_loops): Loop peeling.

I am installing the code to branch now.   It is more practical to do incremental
changes than maitain huge patch.
> 
> + /* The maximum number of insns of an unrolled loop.  */
> + DEFPARAM(MAX_UNROLLED_INSNS,
> + 	"max-unrolled-insns",
> + 	"The maximum number of insns of an unrolled loop",
> + 	200)
> + /* The maximum number of unrollings of a single loop.  */
> + DEFPARAM(MAX_UNROLL_TIMES,
> + 	"max-unroll-times",
> + 	"The maximum number of unrollings of a single loop",
> + 	3)

Concerning the unrolling heuristics, we really should try to keep
the factor of unrolling power of 2 to keep the loop straddles and
friends easilly computable, so value if 3 is somewhat curious.

Lets set it to 4 or 8 and implement the code to keep power of two
if possible (for known number of iterations it is of course not always
maitainable).

Honza