This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [CFG] Loop unrolling
> Hello.
>
> This patch implements loop unrolling, replacing the one in old loop optimizer.
> We currently handle only simple cases (preconditioning for simple for loops +
> just unrolling for rest if asked to). We cannot do much better without
> induction variables (on that we are going to work as soon as we have mid-rtl
> (or we see that we won't have it soon enough)).
>
> Zdenek
>
> * Makefile.in (loop-new.o): Fix dependency on params.h.
> * basic-block.h (create_preheaders, create_preheader):
> Declaration changed.
> * cfgloopanal.c (create_preheaders, create_preheader):
> Modified for use between cfg_layout_initialize and finalize.
> * loop-new.c (unroll_loop_new, unroll_simple_loop, simple_loop_p,
> unroll_loops): New, loop unrolling.
> (loop_optimizer_init): Moved create preheaders behind
> cfg_layout_initialize.
> * params.def (MAX_UNROLLED_INSNS, MAX_UNROLL_TIMES): New options.
> * toplev.c (rest_of_compilation): Added parameters for
> create_preheaders. Disabled old loop unrolling and added new one.
>
> Index: Makefile.in
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
> retrieving revision 1.775.2.25
> diff -c -3 -p -r1.775.2.25 Makefile.in
> *** Makefile.in 2002/02/25 16:50:21 1.775.2.25
> --- Makefile.in 2002/02/26 22:20:22
> *************** loop.o : loop.c $(CONFIG_H) $(SYSTEM_H)
> *** 1485,1491 ****
> toplev.h varray.h except.h cselib.h $(OPTABS_H) $(TM_P_H)
> loop-new.o : loop-new.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h $(LOOP_H) \
> insn-config.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) \
> ! real.h $(PREDICT_H) $(BASIC_BLOCK_H) function.h params.h \
> toplev.h varray.h except.h cselib.h $(TM_P_H) cfglayout.h
> doloop.o : doloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h $(LOOP_H) \
> $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) toplev.h
> --- 1485,1491 ----
> toplev.h varray.h except.h cselib.h $(OPTABS_H) $(TM_P_H)
> loop-new.o : loop-new.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h $(LOOP_H) \
> insn-config.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) \
> ! real.h $(PREDICT_H) $(BASIC_BLOCK_H) function.h $(PARAMS_H) \
> toplev.h varray.h except.h cselib.h $(TM_P_H) cfglayout.h
> doloop.o : doloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h $(LOOP_H) \
> $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) toplev.h
> Index: basic-block.h
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
> retrieving revision 1.127.2.16
> diff -c -3 -p -r1.127.2.16 basic-block.h
> *** basic-block.h 2002/02/25 16:50:23 1.127.2.16
> --- basic-block.h 2002/02/26 22:20:22
> *************** void test_invariants PARAMS ((struct l
> *** 771,778 ****
> bool loop_invariant_rtx_p PARAMS ((struct loop_invariants *, rtx, rtx));
> basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *));
> void force_single_succ_latches PARAMS ((struct loops *));
> ! void create_preheaders PARAMS ((struct loops *));
> ! basic_block create_preheader PARAMS ((struct loop *, sbitmap *, int));
> bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *, basic_block));
> int num_loop_insns PARAMS ((struct loop *));
>
> --- 771,778 ----
> bool loop_invariant_rtx_p PARAMS ((struct loop_invariants *, rtx, rtx));
> basic_block loop_split_edge_with PARAMS ((edge, rtx, struct loops *));
> void force_single_succ_latches PARAMS ((struct loops *));
> ! void create_preheaders PARAMS ((struct loops *, int, int));
> ! basic_block create_preheader PARAMS ((struct loop *, sbitmap *, int, int));
> bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *, basic_block));
> int num_loop_insns PARAMS ((struct loop *));
>
> Index: cfgloopanal.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/Attic/cfgloopanal.c,v
> retrieving revision 1.1.2.5
> diff -c -3 -p -r1.1.2.5 cfgloopanal.c
> *** cfgloopanal.c 2002/02/25 16:50:24 1.1.2.5
> --- cfgloopanal.c 2002/02/26 22:20:22
> *************** test_invariants (loops)
> *** 419,428 ****
> SIMPLE_PREHEADER is set, we only force LOOP to have single entry; otherwise
> we also force preheader block to have only one successor. */
> basic_block
> ! create_preheader (loop, dom, simple_preheader)
> struct loop *loop;
> sbitmap *dom;
> int simple_preheader;
> {
> edge e, fallthru;
> basic_block dummy;
> --- 419,429 ----
> SIMPLE_PREHEADER is set, we only force LOOP to have single entry; otherwise
> we also force preheader block to have only one successor. */
> basic_block
> ! create_preheader (loop, dom, simple_preheader, inside_cfglayout)
Perhaps it is better to use flags here to avoid problem with adding arguments
all the time...
> *************** create_preheader (loop, dom, simple_preh
> *** 455,460 ****
> --- 456,464 ----
> if (loop->latch == loop->header)
> loop->latch = fallthru->dest;
> loop->header = fallthru->dest;
> +
> + if (inside_cfglayout)
> + alloc_aux_for_block (fallthru->dest, sizeof (struct reorder_block_def));
Shouldn't we use cfg_layout_split_bb (I suspect it exists already)
that will do the job for us?
If it doesn't, just please create it. I am not happy to see the aux
garbage outside cfglayout, once we will want to kill it, we should have it
localized in one place.
> +
> + /* Tests whether LOOP is simple for loop. POSTINCR is set to 1 if
> + increment/decrement is done after LOOP exit test. VAR is set to
> + LOOP control variable. GROW is set to 1 if it is incremented.
> + COND is set to exit condition. LIM is expression VAR is compared with.
> + NEG is set to 1 if LOOP ends when COND is satisfied. */
> + static bool
> + simple_loop_p (loops, loop, postincr, var, grow, lim, cond, neg)
Hmm, perhaps this even makes sense.
I think we can use highlevel AST stuff to revamp loop for us to be in this
canonical shape in all cases. This is what SGI is doing I suspect and it is
convenient. That way we won't have to handle all the side cases with
induction variables.
After all it is just slightly weaker than the original code :)
> +
> + /* Unroll a simple for loop. For explanation of parameters see
> + simple_loop_p. MAX_UNROLL is the maximum number of unrollings
> + allowed. */
> + /* FIXME there is probably a lot of bad semantic errors (overflows, etc.) */
Did you take a look at the old code?
I feel bit unconfortable to check in the code that is known to produce invalid
results even th te devel branch.
The comments in old code are quite good to guide you out of the posible
pitfalls.
Also it would be probably desriable to split those two big functions to smaller
one.
Unrolling seems to be tricky enoguth to derve seaprate file as well. Loop-new.c
should probably contain only the basic loop body duplicating code to avoid
huge functions.
Also we will probably attempt to put this to mainline separately and it would
be nice to make it clear what is needed and when.
> *************** rest_of_compilation (decl)
> *** 3057,3062 ****
> --- 3057,3065 ----
> if (flag_unswitch_loops)
> unswitch_loops (loops);
>
> + if (flag_unroll_loops)
> + unroll_loops (loops, flag_unroll_all_loops);
> +
> loop_optimizer_finalize (loops, rtl_dump_file);
At the moment, for tunning, just please invent new flag, like -fnew-unroll-loops
or -funroll-natural-loops, so we can easilly compare both implementations.
Thanks!
Honza